src/jalview/datamodel/features/FeatureStore.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
   3  * Copyright (C) $$Year-Rel$$ The Jalview Authors
   4  *
   5  * This file is part of Jalview.
   6  *
   7  * Jalview is free software: you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License
   9  * as published by the Free Software Foundation, either version 3
  10  * of the License, or (at your option) any later version.
  11  *
  12  * Jalview is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty
  14  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE.  See the GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
  19  * The Jalview Authors are detailed in the 'AUTHORS' file.
  20  */
  21 package jalview.datamodel.features;
  22
  23 import jalview.datamodel.SequenceFeature;
  24
  25 import java.util.ArrayList;
  26 import java.util.Collection;
  27 import java.util.Collections;
  28 import java.util.HashSet;
  29 import java.util.List;
  30 import java.util.Set;
  31
  32 import intervalstore.api.IntervalStoreI;
  33 import intervalstore.impl.BinarySearcher;
  34 import intervalstore.impl.BinarySearcher.Compare;
  35
  36 public class FeatureStore
  37 {
  38   public enum IntervalStoreType
  39   {
  40     /**
  41      * original NCList-based IntervalStore
  42      */
  43     INTERVAL_STORE_NCLIST,
  44
  45     /**
  46      * linked-list IntervalStore
  47      */
  48     INTERVAL_STORE_LINKED_LIST,
  49
  50     /**
  51      * NCList as array buffer IntervalStore
  52      */
  53     INTERVAL_STORE_NCARRAY
  54   }
  55
  56   /*
  57    * track largest start for quick insertion of ordered features
  58    */
  59   protected int maxStart = -1;
  60
  61   protected int maxContactStart = -1;
  62
  63   /*
  64    * Non-positional features have no (zero) start/end position.
  65    * Kept as a separate list in case this criterion changes in future.
  66    */
  67   List<SequenceFeature> nonPositionalFeatures;
  68
  69   /*
  70    * contact features ordered by first contact position
  71    */
  72   List<SequenceFeature> contactFeatureStarts;
  73
  74   /*
  75    * contact features ordered by second contact position
  76    */
  77   List<SequenceFeature> contactFeatureEnds;
  78
  79   /*
  80    * IntervalStore holds remaining features and provides efficient
  81    * query for features overlapping any given interval
  82    */
  83   IntervalStoreI<SequenceFeature> features;
  84
  85   /*
  86    * Feature groups represented in stored positional features
  87    * (possibly including null)
  88    */
  89   Set<String> positionalFeatureGroups;
  90
  91   /*
  92    * Feature groups represented in stored non-positional features
  93    * (possibly including null)
  94    */
  95   Set<String> nonPositionalFeatureGroups;
  96
  97   /*
  98    * the total length of all positional features; contact features count 1 to
  99    * the total and 1 to size(), consistent with an average 'feature length' of 1
 100    */
 101   int totalExtent;
 102
 103   float positionalMinScore;
 104
 105   float positionalMaxScore;
 106
 107   float nonPositionalMinScore;
 108
 109   float nonPositionalMaxScore;
 110
 111   /**
 112    * Answers the 'length' of the feature, counting 0 for non-positional features
 113    * and 1 for contact features
 114    *
 115    * @param feature
 116    * @return
 117    */
 118   protected static int getFeatureLength(SequenceFeature feature)
 119   {
 120     if (feature.isNonPositional())
 121     {
 122       return 0;
 123     }
 124     if (feature.isContactFeature())
 125     {
 126       return 1;
 127     }
 128     return 1 + feature.getEnd() - feature.getBegin();
 129   }
 130
 131   /**
 132    * Answers true if the list contains the feature, else false. This method is
 133    * optimised for the condition that the list is sorted on feature start
 134    * position ascending, and will give unreliable results if this does not hold.
 135    *
 136    * @param list
 137    * @param feature
 138    * @return
 139    */
 140   public static boolean listContains(List<SequenceFeature> list,
 141           SequenceFeature feature)
 142   {
 143     if (list == null || feature == null)
 144     {
 145       return false;
 146     }
 147
 148     /*
 149      * locate the first entry in the list which does not precede the feature
 150      */
 151     int begin = feature.begin;
 152     int pos = BinarySearcher.findFirst(list, true, Compare.GE, begin);
 153     int len = list.size();
 154     while (pos < len)
 155     {
 156       SequenceFeature sf = list.get(pos);
 157       if (sf.begin > begin)
 158       {
 159         return false; // no match found
 160       }
 161       if (sf.equals(feature))
 162       {
 163         return true;
 164       }
 165       pos++;
 166     }
 167     return false;
 168   }
 169
 170   /**
 171    * A helper method to return the maximum of two floats, where a non-NaN value
 172    * is treated as 'greater than' a NaN value (unlike Math.max which does the
 173    * opposite)
 174    *
 175    * @param f1
 176    * @param f2
 177    */
 178   protected static float max(float f1, float f2)
 179   {
 180     if (Float.isNaN(f1))
 181     {
 182       return Float.isNaN(f2) ? f1 : f2;
 183     }
 184     else
 185     {
 186       return Float.isNaN(f2) ? f1 : Math.max(f1, f2);
 187     }
 188   }
 189
 190   /**
 191    * A helper method to return the minimum of two floats, where a non-NaN value
 192    * is treated as 'less than' a NaN value (unlike Math.min which does the
 193    * opposite)
 194    *
 195    * @param f1
 196    * @param f2
 197    */
 198   protected static float min(float f1, float f2)
 199   {
 200     if (Float.isNaN(f1))
 201     {
 202       return Float.isNaN(f2) ? f1 : f2;
 203     }
 204     else
 205     {
 206       return Float.isNaN(f2) ? f1 : Math.min(f1, f2);
 207     }
 208   }
 209
 210   /**
 211    * Constructor that defaults to using NCList IntervalStore
 212    */
 213   public FeatureStore()
 214   {
 215     this(IntervalStoreType.INTERVAL_STORE_NCLIST);
 216   }
 217
 218   /**
 219    * Constructor that allows an alternative IntervalStore implementation to be
 220    * chosen
 221    */
 222   public FeatureStore(IntervalStoreType intervalStoreType)
 223   {
 224     features = getIntervalStore(intervalStoreType);
 225     positionalFeatureGroups = new HashSet<>();
 226     nonPositionalFeatureGroups = new HashSet<>();
 227     positionalMinScore = Float.NaN;
 228     positionalMaxScore = Float.NaN;
 229     nonPositionalMinScore = Float.NaN;
 230     nonPositionalMaxScore = Float.NaN;
 231
 232     // only construct nonPositionalFeatures or contactFeatures if needed
 233   }
 234
 235   /**
 236    * Returns a new instance of IntervalStoreI of implementation as selected by
 237    * the type parameter
 238    *
 239    * @param type
 240    * @return
 241    */
 242   private IntervalStoreI<SequenceFeature> getIntervalStore(
 243           IntervalStoreType type)
 244   {
 245     switch (type)
 246     {
 247     default:
 248     case INTERVAL_STORE_NCLIST:
 249       return new intervalstore.impl.IntervalStore<>();
 250     case INTERVAL_STORE_NCARRAY:
 251       return new intervalstore.nonc.IntervalStore<>();
 252     case INTERVAL_STORE_LINKED_LIST:
 253       return new intervalstore.nonc.IntervalStore0<>();
 254     }
 255   }
 256
 257   /**
 258    * Add a contact feature to the lists that hold them ordered by start (first
 259    * contact) and by end (second contact) position, ensuring the lists remain
 260    * ordered, and returns true. This method allows duplicate features to be
 261    * added, so test before calling to avoid this.
 262    *
 263    * @param feature
 264    * @return
 265    */
 266   protected synchronized boolean addContactFeature(SequenceFeature feature)
 267   {
 268     if (contactFeatureStarts == null)
 269     {
 270       contactFeatureStarts = new ArrayList<>();
 271       contactFeatureEnds = new ArrayList<>();
 272     }
 273
 274     /*
 275      * insert into list sorted by start (first contact position):
 276      * binary search the sorted list to find the insertion point
 277      */
 278     int insertAt = BinarySearcher.findFirst(contactFeatureStarts, true,
 279             Compare.GE, feature.begin);
 280     contactFeatureStarts.add(insertAt, feature);
 281     /*
 282      * insert into list sorted by end (second contact position):
 283      * binary search the sorted list to find the insertion point
 284      */
 285     contactFeatureEnds.add(findFirstEnd(contactFeatureEnds, feature.end),
 286             feature);
 287
 288     return true;
 289   }
 290
 291   /**
 292    * Adds one sequence feature to the store, and returns true, unless the
 293    * feature is already contained in the store, in which case this method
 294    * returns false. Containment is determined by SequenceFeature.equals()
 295    * comparison.
 296    *
 297    * @param feature
 298    */
 299   public boolean addFeature(SequenceFeature feature)
 300   {
 301     if (feature.isContactFeature())
 302     {
 303       if (containsContactFeature(feature))
 304       {
 305         return false;
 306       }
 307       positionalFeatureGroups.add(feature.getFeatureGroup());
 308       if (feature.begin > maxContactStart)
 309       {
 310         maxContactStart = feature.begin;
 311       }
 312       addContactFeature(feature);
 313     }
 314     else if (feature.isNonPositional())
 315     {
 316       if (containsNonPositionalFeature(feature))
 317       {
 318         return false;
 319       }
 320
 321       addNonPositionalFeature(feature);
 322     }
 323     else
 324     {
 325       if (!features.add(feature, false))
 326       {
 327         return false;
 328       }
 329       positionalFeatureGroups.add(feature.getFeatureGroup());
 330       if (feature.begin > maxStart)
 331       {
 332         maxStart = feature.begin;
 333       }
 334     }
 335
 336     /*
 337      * record the total extent of positional features, to make
 338      * getTotalFeatureLength possible; we count the length of a
 339      * contact feature as 1
 340      */
 341     totalExtent += getFeatureLength(feature);
 342
 343     /*
 344      * record the minimum and maximum score for positional
 345      * and non-positional features
 346      */
 347     float score = feature.getScore();
 348     if (!Float.isNaN(score))
 349     {
 350       if (feature.isNonPositional())
 351       {
 352         nonPositionalMinScore = min(nonPositionalMinScore, score);
 353         nonPositionalMaxScore = max(nonPositionalMaxScore, score);
 354       }
 355       else
 356       {
 357         positionalMinScore = min(positionalMinScore, score);
 358         positionalMaxScore = max(positionalMaxScore, score);
 359       }
 360     }
 361
 362     return true;
 363   }
 364
 365   /**
 366    * A helper method that adds to the result list any features from the
 367    * collection provided whose feature group matches the specified group
 368    *
 369    * @param group
 370    * @param sfs
 371    * @param result
 372    */
 373   private void addFeaturesForGroup(String group,
 374           Collection<SequenceFeature> sfs, List<SequenceFeature> result)
 375   {
 376     if (sfs == null)
 377     {
 378       return;
 379     }
 380     for (SequenceFeature sf : sfs)
 381     {
 382       String featureGroup = sf.getFeatureGroup();
 383       if (group == null && featureGroup == null
 384               || group != null && group.equals(featureGroup))
 385       {
 386         result.add(sf);
 387       }
 388     }
 389   }
 390
 391   /**
 392    * Adds the feature to the list of non-positional features (with lazy
 393    * instantiation of the list if it is null), and returns true. The feature
 394    * group is added to the set of distinct feature groups for non-positional
 395    * features. This method allows duplicate features, so test before calling to
 396    * prevent this.
 397    *
 398    * @param feature
 399    */
 400   protected boolean addNonPositionalFeature(SequenceFeature feature)
 401   {
 402     if (nonPositionalFeatures == null)
 403     {
 404       nonPositionalFeatures = new ArrayList<>();
 405     }
 406
 407     nonPositionalFeatures.add(feature);
 408
 409     nonPositionalFeatureGroups.add(feature.getFeatureGroup());
 410
 411     return true;
 412   }
 413
 414   /**
 415    * Answers true if this store contains the given feature (testing by
 416    * SequenceFeature.equals), else false
 417    *
 418    * @param feature
 419    * @return
 420    */
 421   public boolean contains(SequenceFeature feature)
 422   {
 423     if (feature.isNonPositional())
 424     {
 425       return containsNonPositionalFeature(feature);
 426     }
 427
 428     if (feature.isContactFeature())
 429     {
 430       return containsContactFeature(feature);
 431     }
 432
 433     return containsPositionalFeature(feature);
 434   }
 435
 436   private boolean containsPositionalFeature(SequenceFeature feature)
 437   {
 438     return features == null || feature.begin > maxStart ? false
 439             : features.contains(feature);
 440   }
 441
 442   /**
 443    * Answers true if this store already contains a contact feature equal to the
 444    * given feature (by {@code SequenceFeature.equals()} test), else false
 445    *
 446    * @param feature
 447    * @return
 448    */
 449   private boolean containsContactFeature(SequenceFeature feature)
 450   {
 451     return contactFeatureStarts != null && feature.begin <= maxContactStart
 452             && listContains(contactFeatureStarts, feature);
 453   }
 454
 455   /**
 456    * Answers true if this store already contains a non-positional feature equal
 457    * to the given feature (by {@code SequenceFeature.equals()} test), else false
 458    *
 459    * @param feature
 460    * @return
 461    */
 462   private boolean containsNonPositionalFeature(SequenceFeature feature)
 463   {
 464     return nonPositionalFeatures == null ? false
 465             : nonPositionalFeatures.contains(feature);
 466   }
 467
 468   /**
 469    * Deletes the given feature from the store, returning true if it was found
 470    * (and deleted), else false. This method makes no assumption that the feature
 471    * is in the 'expected' place in the store, in case it has been modified since
 472    * it was added.
 473    *
 474    * @param sf
 475    */
 476   public synchronized boolean delete(SequenceFeature sf)
 477   {
 478     boolean removed = false;
 479
 480     /*
 481      * try contact positions (and if found, delete
 482      * from both lists of contact positions)
 483      */
 484     if (!removed && contactFeatureStarts != null)
 485     {
 486       removed = contactFeatureStarts.remove(sf);
 487       if (removed)
 488       {
 489         contactFeatureEnds.remove(sf);
 490       }
 491     }
 492
 493     /*
 494      * if not found, try non-positional features
 495      */
 496     if (!removed && nonPositionalFeatures != null)
 497     {
 498       removed = nonPositionalFeatures.remove(sf);
 499     }
 500
 501     /*
 502      * if not found, try nested features
 503      */
 504     if (!removed && features != null)
 505     {
 506       removed = features.remove(sf);
 507     }
 508
 509     if (removed)
 510     {
 511       rescanAfterDelete();
 512     }
 513
 514     return removed;
 515   }
 516
 517   public List<SequenceFeature> findFeatures(long start, long end)
 518   {
 519     return findFeatures(start, end, null);
 520   }
 521
 522   /**
 523    * Returns a (possibly empty) list of features whose extent overlaps the given
 524    * range. The returned list is not ordered. Contact features are included if
 525    * either of the contact points lies within the range. If the {@code result}
 526    * parameter is not null, new entries are added to this list and the (possibly
 527    * extended) list returned.
 528    *
 529    * @param start
 530    *          start position of overlap range (inclusive)
 531    * @param end
 532    *          end position of overlap range (inclusive)
 533    * @param result
 534    * @return
 535    */
 536   public List<SequenceFeature> findFeatures(long start, long end,
 537           List<SequenceFeature> result)
 538   {
 539     if (result == null)
 540     {
 541       result = new ArrayList<>();
 542     }
 543
 544     findContactFeatures(start, end, result);
 545     features.findOverlaps(start, end, result);
 546
 547     return result;
 548   }
 549
 550   /**
 551    * Returns a (possibly empty) list of stored contact features
 552    *
 553    * @return
 554    */
 555   public List<SequenceFeature> getContactFeatures()
 556   {
 557     List<SequenceFeature> result = new ArrayList<>();
 558     getContactFeatures(result);
 559     return result;
 560   }
 561
 562   /**
 563    * Adds any stored contact features to the result list
 564    *
 565    * @return
 566    */
 567   public void getContactFeatures(List<SequenceFeature> result)
 568   {
 569     if (contactFeatureStarts != null)
 570     {
 571       result.addAll(contactFeatureStarts);
 572     }
 573   }
 574
 575   /**
 576    * Answers the number of positional (or non-positional) features stored.
 577    * Contact features count as 1.
 578    *
 579    * @param positional
 580    * @return
 581    */
 582   public int getFeatureCount(boolean positional)
 583   {
 584     if (!positional)
 585     {
 586       return nonPositionalFeatures == null ? 0
 587               : nonPositionalFeatures.size();
 588     }
 589
 590     int size = 0;
 591
 592     if (contactFeatureStarts != null)
 593     {
 594       // note a contact feature (start/end) counts as one
 595       size += contactFeatureStarts.size();
 596     }
 597
 598     if (features != null)
 599     {
 600       size += features.size();
 601     }
 602     return size;
 603   }
 604
 605   /**
 606    * Answers the set of distinct feature groups stored, possibly including null,
 607    * as an unmodifiable view of the set. The parameter determines whether the
 608    * groups for positional or for non-positional features are returned.
 609    *
 610    * @param positionalFeatures
 611    * @return
 612    */
 613   public Set<String> getFeatureGroups(boolean positionalFeatures)
 614   {
 615     if (positionalFeatures)
 616     {
 617       return Collections.unmodifiableSet(positionalFeatureGroups);
 618     }
 619     else
 620     {
 621       return nonPositionalFeatureGroups == null
 622               ? Collections.<String> emptySet()
 623               : Collections.unmodifiableSet(nonPositionalFeatureGroups);
 624     }
 625   }
 626
 627   /**
 628    * Answers a list of all either positional or non-positional features whose
 629    * feature group matches the given group (which may be null)
 630    *
 631    * @param positional
 632    * @param group
 633    * @return
 634    */
 635   public List<SequenceFeature> getFeaturesForGroup(boolean positional,
 636           String group)
 637   {
 638     List<SequenceFeature> result = new ArrayList<>();
 639
 640     /*
 641      * if we know features don't include the target group, no need
 642      * to inspect them for matches
 643      */
 644     if (positional && !positionalFeatureGroups.contains(group)
 645             || !positional && !nonPositionalFeatureGroups.contains(group))
 646     {
 647       return result;
 648     }
 649
 650     if (positional)
 651     {
 652       addFeaturesForGroup(group, contactFeatureStarts, result);
 653       addFeaturesForGroup(group, features, result);
 654     }
 655     else
 656     {
 657       addFeaturesForGroup(group, nonPositionalFeatures, result);
 658     }
 659     return result;
 660   }
 661
 662   /**
 663    * Answers the maximum score held for positional or non-positional features.
 664    * This may be Float.NaN if there are no features, are none has a non-NaN
 665    * score.
 666    *
 667    * @param positional
 668    * @return
 669    */
 670   public float getMaximumScore(boolean positional)
 671   {
 672     return positional ? positionalMaxScore : nonPositionalMaxScore;
 673   }
 674
 675   /**
 676    * Answers the minimum score held for positional or non-positional features.
 677    * This may be Float.NaN if there are no features, are none has a non-NaN
 678    * score.
 679    *
 680    * @param positional
 681    * @return
 682    */
 683   public float getMinimumScore(boolean positional)
 684   {
 685     return positional ? positionalMinScore : nonPositionalMinScore;
 686   }
 687
 688   /**
 689    * Answers a (possibly empty) list of all non-positional features
 690    *
 691    * @return
 692    */
 693   public List<SequenceFeature> getNonPositionalFeatures()
 694   {
 695     List<SequenceFeature> result = new ArrayList<>();
 696     getNonPositionalFeatures(result);
 697     return result;
 698   }
 699
 700   /**
 701    * Adds any stored non-positional features to the result list
 702    *
 703    * @return
 704    */
 705   public void getNonPositionalFeatures(List<SequenceFeature> result)
 706   {
 707     if (nonPositionalFeatures != null)
 708     {
 709       result.addAll(nonPositionalFeatures);
 710     }
 711   }
 712
 713   /**
 714    * Returns a (possibly empty) list of all positional features stored
 715    *
 716    * @return
 717    */
 718   public List<SequenceFeature> getPositionalFeatures()
 719   {
 720     List<SequenceFeature> result = new ArrayList<>();
 721     getPositionalFeatures(result);
 722
 723     return result;
 724   }
 725
 726   /**
 727    * Adds all positional features stored to the result list, in no guaranteed
 728    * order, and with no check for duplicates
 729    */
 730   public void getPositionalFeatures(List<SequenceFeature> result)
 731   {
 732     /*
 733      * add any contact features - from the list by start position
 734      */
 735     if (contactFeatureStarts != null)
 736     {
 737       result.addAll(contactFeatureStarts);
 738     }
 739
 740     /*
 741      * add any nested features
 742      */
 743     if (features != null)
 744     {
 745       result.addAll(features);
 746     }
 747   }
 748
 749   /**
 750    * Answers the total length of positional features (or zero if there are
 751    * none). Contact features contribute a value of 1 to the total.
 752    *
 753    * @return
 754    */
 755   public int getTotalFeatureLength()
 756   {
 757     return totalExtent;
 758   }
 759
 760   /**
 761    * Answers true if this store has no features, else false
 762    *
 763    * @return
 764    */
 765   public boolean isEmpty()
 766   {
 767     boolean hasFeatures = (contactFeatureStarts != null
 768             && !contactFeatureStarts.isEmpty())
 769             || (nonPositionalFeatures != null
 770                     && !nonPositionalFeatures.isEmpty())
 771             || (features != null && features.size() > 0);
 772
 773     return !hasFeatures;
 774   }
 775
 776   /**
 777    * Rescan all features to recompute any cached values after an entry has been
 778    * deleted. This is expected to be an infrequent event, so performance here is
 779    * not critical.
 780    */
 781   protected synchronized void rescanAfterDelete()
 782   {
 783     positionalFeatureGroups.clear();
 784     nonPositionalFeatureGroups.clear();
 785     totalExtent = 0;
 786     positionalMinScore = Float.NaN;
 787     positionalMaxScore = Float.NaN;
 788     nonPositionalMinScore = Float.NaN;
 789     nonPositionalMaxScore = Float.NaN;
 790     /*
 791      * scan non-positional features for groups and scores
 792      */
 793     if (nonPositionalFeatures != null)
 794     {
 795       for (int i = 0, n = nonPositionalFeatures.size(); i < n; i++)
 796       {
 797         SequenceFeature sf = nonPositionalFeatures.get(i);
 798         nonPositionalFeatureGroups.add(sf.getFeatureGroup());
 799         float score = sf.getScore();
 800         nonPositionalMinScore = min(nonPositionalMinScore, score);
 801         nonPositionalMaxScore = max(nonPositionalMaxScore, score);
 802       }
 803     }
 804
 805     rescanPositional(contactFeatureStarts);
 806     rescanPositional(features);
 807   }
 808
 809   /**
 810    * Scans the given features and updates cached feature groups, minimum and
 811    * maximum feature score, and total feature extent (length) for positional
 812    * features
 813    *
 814    * @param sfs
 815    */
 816   private void rescanPositional(Collection<SequenceFeature> sfs)
 817   {
 818     if (sfs == null)
 819     {
 820       return;
 821     }
 822     for (SequenceFeature sf : sfs)
 823     {
 824       positionalFeatureGroups.add(sf.getFeatureGroup());
 825       float score = sf.getScore();
 826       positionalMinScore = min(positionalMinScore, score);
 827       positionalMaxScore = max(positionalMaxScore, score);
 828       totalExtent += getFeatureLength(sf);
 829     }
 830   }
 831
 832   /**
 833    * Adds the shift amount to the start and end of all positional features whose
 834    * start position is at or after fromPosition. Returns true if at least one
 835    * feature was shifted, else false.
 836    *
 837    * @param fromPosition
 838    * @param shiftBy
 839    * @return
 840    */
 841   public synchronized boolean shiftFeatures(int fromPosition, int shiftBy)
 842   {
 843     /*
 844      * Because begin and end are final fields (to ensure the data store's
 845      * integrity), we have to delete each feature and re-add it as amended.
 846      * (Although a simple shift of all values would preserve data integrity!)
 847      */
 848     boolean modified = false;
 849     List<SequenceFeature> list = getPositionalFeatures();
 850     for (int i = 0, n = list.size(); i < n; i++)
 851     {
 852       SequenceFeature sf = list.get(i);
 853       if (sf.getBegin() >= fromPosition)
 854       {
 855         modified = true;
 856         int newBegin = sf.getBegin() + shiftBy;
 857         int newEnd = sf.getEnd() + shiftBy;
 858
 859         /*
 860          * sanity check: don't shift left of the first residue
 861          */
 862         if (newEnd > 0)
 863         {
 864           newBegin = Math.max(1, newBegin);
 865           SequenceFeature sf2 = new SequenceFeature(sf, newBegin, newEnd,
 866                   sf.getFeatureGroup(), sf.getScore());
 867           addFeature(sf2);
 868         }
 869         delete(sf);
 870       }
 871     }
 872     return modified;
 873   }
 874
 875   /**
 876    * Answers the position (0, 1...) in the list of the first entry whose end
 877    * position is not less than {@ pos}. If no such entry is found, answers the
 878    * length of the list.
 879    *
 880    * @param list
 881    * @param pos
 882    * @return
 883    */
 884   protected int findFirstEnd(List<SequenceFeature> list, long pos)
 885   {
 886     return BinarySearcher.findFirst(list, false, Compare.GE, (int) pos);
 887   }
 888
 889   /**
 890    * Adds contact features to the result list where either the second or the
 891    * first contact position lies within the target range
 892    *
 893    * @param from
 894    * @param to
 895    * @param result
 896    */
 897   protected void findContactFeatures(long from, long to,
 898           List<SequenceFeature> result)
 899   {
 900     if (contactFeatureStarts != null)
 901     {
 902       findContactStartOverlaps(from, to, result);
 903       findContactEndOverlaps(from, to, result);
 904     }
 905   }
 906
 907   /**
 908    * Adds to the result list any contact features whose end (second contact
 909    * point), but not start (first contact point), lies in the query from-to
 910    * range
 911    *
 912    * @param from
 913    * @param to
 914    * @param result
 915    */
 916   private void findContactEndOverlaps(long from, long to,
 917           List<SequenceFeature> result)
 918   {
 919     /*
 920      * find the first contact feature (if any)
 921      * whose end point is not before the target range
 922      */
 923     int index = findFirstEnd(contactFeatureEnds, from);
 924
 925     int n = contactFeatureEnds.size();
 926     while (index < n)
 927     {
 928       SequenceFeature sf = contactFeatureEnds.get(index);
 929       if (!sf.isContactFeature())
 930       {
 931         System.err.println("Error! non-contact feature type " + sf.getType()
 932                 + " in contact features list");
 933         index++;
 934         continue;
 935       }
 936
 937       int begin = sf.getBegin();
 938       if (begin >= from && begin <= to)
 939       {
 940         /*
 941          * this feature's first contact position lies in the search range
 942          * so we don't include it in results a second time
 943          */
 944         index++;
 945         continue;
 946       }
 947
 948       if (sf.getEnd() > to)
 949       {
 950         /*
 951          * this feature (and all following) has end point after the target range
 952          */
 953         break;
 954       }
 955
 956       /*
 957        * feature has end >= from and end <= to
 958        * i.e. contact end point lies within overlap search range
 959        */
 960       result.add(sf);
 961       index++;
 962     }
 963   }
 964
 965   /**
 966    * Adds contact features whose start position lies in the from-to range to the
 967    * result list
 968    *
 969    * @param from
 970    * @param to
 971    * @param result
 972    */
 973   private void findContactStartOverlaps(long from, long to,
 974           List<SequenceFeature> result)
 975   {
 976     int index = BinarySearcher.findFirst(contactFeatureStarts, true,
 977             Compare.GE, (int) from);
 978
 979     while (index < contactFeatureStarts.size())
 980     {
 981       SequenceFeature sf = contactFeatureStarts.get(index);
 982       if (!sf.isContactFeature())
 983       {
 984         System.err.println("Error! non-contact feature " + sf.toString()
 985                 + " in contact features list");
 986         index++;
 987         continue;
 988       }
 989       if (sf.getBegin() > to)
 990       {
 991         /*
 992          * this feature's start (and all following) follows the target range
 993          */
 994         break;
 995       }
 996
 997       /*
 998        * feature has begin >= from and begin <= to
 999        * i.e. contact start point lies within overlap search range
1000        */
1001       result.add(sf);
1002       index++;
1003     }
1004   }
1005
1006 }