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