src/jalview/datamodel/features/FeatureStore.java

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