src/jalview/datamodel/features/FeatureStore.java

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