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