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 is at or 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     /*
 600      * find the first feature whose end position is
 601      * after the target range start
 602      */
 603     int startIndex = binarySearch(nonNestedFeatures,
 604             SearchCriterion.byEnd(from));
 605
 606     final int startIndex1 = startIndex;
 607     int i = startIndex1;
 608     while (i < nonNestedFeatures.size())
 609     {
 610       SequenceFeature sf = nonNestedFeatures.get(i);
 611       if (sf.getBegin() > to)
 612       {
 613         break;
 614       }
 615       if (sf.getBegin() <= to && sf.getEnd() >= from)
 616       {
 617         result.add(sf);
 618       }
 619       i++;
 620     }
 621   }
 622
 623   /**
 624    * Adds contact features whose start position lies in the from-to range to the
 625    * result list
 626    *
 627    * @param from
 628    * @param to
 629    * @param result
 630    */
 631   protected void findContactStartFeatures(long from, long to,
 632           List<SequenceFeature> result)
 633   {
 634     int startPosition = binarySearch(contactFeatureStarts,
 635             SearchCriterion.byStart(from));
 636
 637     for (; startPosition < contactFeatureStarts.size(); startPosition++)
 638     {
 639       SequenceFeature sf = contactFeatureStarts.get(startPosition);
 640       if (!sf.isContactFeature())
 641       {
 642         System.err.println("Error! non-contact feature type "
 643                 + sf.getType() + " in contact features list");
 644         continue;
 645       }
 646       int begin = sf.getBegin();
 647       if (begin >= from && begin <= to)
 648       {
 649         result.add(sf);
 650       }
 651     }
 652   }
 653
 654   /**
 655    * Answers a list of all positional features stored, in no guaranteed order
 656    *
 657    * @return
 658    */
 659   public List<SequenceFeature> getPositionalFeatures()
 660   {
 661     /*
 662      * add non-nested features (may be all features for many cases)
 663      */
 664     List<SequenceFeature> result = new ArrayList<>();
 665     result.addAll(nonNestedFeatures);
 666
 667     /*
 668      * add any contact features - from the list by start position
 669      */
 670     if (contactFeatureStarts != null)
 671     {
 672       result.addAll(contactFeatureStarts);
 673     }
 674
 675     /*
 676      * add any nested features
 677      */
 678     if (nestedFeatures != null)
 679     {
 680       result.addAll(nestedFeatures.getEntries());
 681     }
 682
 683     return result;
 684   }
 685
 686   /**
 687    * Answers a list of all contact features. If there are none, returns an
 688    * immutable empty list.
 689    *
 690    * @return
 691    */
 692   public List<SequenceFeature> getContactFeatures()
 693   {
 694     if (contactFeatureStarts == null)
 695     {
 696       return Collections.emptyList();
 697     }
 698     return new ArrayList<>(contactFeatureStarts);
 699   }
 700
 701   /**
 702    * Answers a list of all non-positional features. If there are none, returns
 703    * an immutable empty list.
 704    *
 705    * @return
 706    */
 707   public List<SequenceFeature> getNonPositionalFeatures()
 708   {
 709     if (nonPositionalFeatures == null)
 710     {
 711       return Collections.emptyList();
 712     }
 713     return new ArrayList<>(nonPositionalFeatures);
 714   }
 715
 716   /**
 717    * Deletes the given feature from the store, returning true if it was found
 718    * (and deleted), else false. This method makes no assumption that the feature
 719    * is in the 'expected' place in the store, in case it has been modified since
 720    * it was added.
 721    *
 722    * @param sf
 723    */
 724   public synchronized boolean delete(SequenceFeature sf)
 725   {
 726     /*
 727      * try the non-nested positional features first
 728      */
 729     boolean removed = nonNestedFeatures.remove(sf);
 730
 731     /*
 732      * if not found, try contact positions (and if found, delete
 733      * from both lists of contact positions)
 734      */
 735     if (!removed && contactFeatureStarts != null)
 736     {
 737       removed = contactFeatureStarts.remove(sf);
 738       if (removed)
 739       {
 740         contactFeatureEnds.remove(sf);
 741       }
 742     }
 743
 744     boolean removedNonPositional = false;
 745
 746     /*
 747      * if not found, try non-positional features
 748      */
 749     if (!removed && nonPositionalFeatures != null)
 750     {
 751       removedNonPositional = nonPositionalFeatures.remove(sf);
 752       removed = removedNonPositional;
 753     }
 754
 755     /*
 756      * if not found, try nested features
 757      */
 758     if (!removed && nestedFeatures != null)
 759     {
 760       removed = nestedFeatures.delete(sf);
 761     }
 762
 763     if (removed)
 764     {
 765       rescanAfterDelete();
 766     }
 767
 768     return removed;
 769   }
 770
 771   /**
 772    * Rescan all features to recompute any cached values after an entry has been
 773    * deleted. This is expected to be an infrequent event, so performance here is
 774    * not critical.
 775    */
 776   protected synchronized void rescanAfterDelete()
 777   {
 778     positionalFeatureGroups.clear();
 779     nonPositionalFeatureGroups.clear();
 780     totalExtent = 0;
 781     positionalMinScore = Float.NaN;
 782     positionalMaxScore = Float.NaN;
 783     nonPositionalMinScore = Float.NaN;
 784     nonPositionalMaxScore = Float.NaN;
 785
 786     /*
 787      * scan non-positional features for groups and scores
 788      */
 789     for (SequenceFeature sf : getNonPositionalFeatures())
 790     {
 791       nonPositionalFeatureGroups.add(sf.getFeatureGroup());
 792       float score = sf.getScore();
 793       nonPositionalMinScore = min(nonPositionalMinScore, score);
 794       nonPositionalMaxScore = max(nonPositionalMaxScore, score);
 795     }
 796
 797     /*
 798      * scan positional features for groups, scores and extents
 799      */
 800     for (SequenceFeature sf : getPositionalFeatures())
 801     {
 802       positionalFeatureGroups.add(sf.getFeatureGroup());
 803       float score = sf.getScore();
 804       positionalMinScore = min(positionalMinScore, score);
 805       positionalMaxScore = max(positionalMaxScore, score);
 806       totalExtent += getFeatureLength(sf);
 807     }
 808   }
 809
 810   /**
 811    * A helper method to return the minimum of two floats, where a non-NaN value
 812    * is treated as 'less than' a NaN value (unlike Math.min which does the
 813    * opposite)
 814    *
 815    * @param f1
 816    * @param f2
 817    */
 818   protected static float min(float f1, float f2)
 819   {
 820     if (Float.isNaN(f1))
 821     {
 822       return Float.isNaN(f2) ? f1 : f2;
 823     }
 824     else
 825     {
 826       return Float.isNaN(f2) ? f1 : Math.min(f1, f2);
 827     }
 828   }
 829
 830   /**
 831    * A helper method to return the maximum of two floats, where a non-NaN value
 832    * is treated as 'greater than' a NaN value (unlike Math.max which does the
 833    * opposite)
 834    *
 835    * @param f1
 836    * @param f2
 837    */
 838   protected static float max(float f1, float f2)
 839   {
 840     if (Float.isNaN(f1))
 841     {
 842       return Float.isNaN(f2) ? f1 : f2;
 843     }
 844     else
 845     {
 846       return Float.isNaN(f2) ? f1 : Math.max(f1, f2);
 847     }
 848   }
 849
 850   /**
 851    * Answers true if this store has no features, else false
 852    *
 853    * @return
 854    */
 855   public boolean isEmpty()
 856   {
 857     boolean hasFeatures = !nonNestedFeatures.isEmpty()
 858             || (contactFeatureStarts != null && !contactFeatureStarts
 859                     .isEmpty())
 860             || (nonPositionalFeatures != null && !nonPositionalFeatures
 861                     .isEmpty())
 862             || (nestedFeatures != null && nestedFeatures.size() > 0);
 863
 864     return !hasFeatures;
 865   }
 866
 867   /**
 868    * Answers the set of distinct feature groups stored, possibly including null,
 869    * as an unmodifiable view of the set. The parameter determines whether the
 870    * groups for positional or for non-positional features are returned.
 871    *
 872    * @param positionalFeatures
 873    * @return
 874    */
 875   public Set<String> getFeatureGroups(boolean positionalFeatures)
 876   {
 877     if (positionalFeatures)
 878     {
 879       return Collections.unmodifiableSet(positionalFeatureGroups);
 880     }
 881     else
 882     {
 883       return nonPositionalFeatureGroups == null ? Collections
 884               .<String> emptySet() : Collections
 885               .unmodifiableSet(nonPositionalFeatureGroups);
 886     }
 887   }
 888
 889   /**
 890    * Performs a binary search of the (sorted) list to find the index of the
 891    * first entry which returns true for the given comparator function. Returns
 892    * the length of the list if there is no such entry.
 893    *
 894    * @param features
 895    * @param sc
 896    * @return
 897    */
 898   protected static int binarySearch(List<SequenceFeature> features,
 899           SearchCriterion sc)
 900   {
 901     int start = 0;
 902     int end = features.size() - 1;
 903     int matched = features.size();
 904
 905     while (start <= end)
 906     {
 907       int mid = (start + end) / 2;
 908       SequenceFeature entry = features.get(mid);
 909       boolean compare = sc.compare(entry);
 910       if (compare)
 911       {
 912         matched = mid;
 913         end = mid - 1;
 914       }
 915       else
 916       {
 917         start = mid + 1;
 918       }
 919     }
 920
 921     return matched;
 922   }
 923
 924   /**
 925    * Answers the number of positional (or non-positional) features stored.
 926    * Contact features count as 1.
 927    *
 928    * @param positional
 929    * @return
 930    */
 931   public int getFeatureCount(boolean positional)
 932   {
 933     if (!positional)
 934     {
 935       return nonPositionalFeatures == null ? 0 : nonPositionalFeatures
 936               .size();
 937     }
 938
 939     int size = nonNestedFeatures.size();
 940
 941     if (contactFeatureStarts != null)
 942     {
 943       // note a contact feature (start/end) counts as one
 944       size += contactFeatureStarts.size();
 945     }
 946
 947     if (nestedFeatures != null)
 948     {
 949       size += nestedFeatures.size();
 950     }
 951
 952     return size;
 953   }
 954
 955   /**
 956    * Answers the total length of positional features (or zero if there are
 957    * none). Contact features contribute a value of 1 to the total.
 958    *
 959    * @return
 960    */
 961   public int getTotalFeatureLength()
 962   {
 963     return totalExtent;
 964   }
 965
 966   /**
 967    * Answers the minimum score held for positional or non-positional features.
 968    * This may be Float.NaN if there are no features, are none has a non-NaN
 969    * score.
 970    *
 971    * @param positional
 972    * @return
 973    */
 974   public float getMinimumScore(boolean positional)
 975   {
 976     return positional ? positionalMinScore : nonPositionalMinScore;
 977   }
 978
 979   /**
 980    * Answers the maximum score held for positional or non-positional features.
 981    * This may be Float.NaN if there are no features, are none has a non-NaN
 982    * score.
 983    *
 984    * @param positional
 985    * @return
 986    */
 987   public float getMaximumScore(boolean positional)
 988   {
 989     return positional ? positionalMaxScore : nonPositionalMaxScore;
 990   }
 991
 992   /**
 993    * Answers a list of all either positional or non-positional features whose
 994    * feature group matches the given group (which may be null)
 995    *
 996    * @param positional
 997    * @param group
 998    * @return
 999    */
1000   public List<SequenceFeature> getFeaturesForGroup(boolean positional,
1001           String group)
1002   {
1003     List<SequenceFeature> result = new ArrayList<>();
1004
1005     /*
1006      * if we know features don't include the target group, no need
1007      * to inspect them for matches
1008      */
1009     if (positional && !positionalFeatureGroups.contains(group)
1010             || !positional && !nonPositionalFeatureGroups.contains(group))
1011     {
1012       return result;
1013     }
1014
1015     List<SequenceFeature> sfs = positional ? getPositionalFeatures()
1016             : getNonPositionalFeatures();
1017     for (SequenceFeature sf : sfs)
1018     {
1019       String featureGroup = sf.getFeatureGroup();
1020       if (group == null && featureGroup == null || group != null
1021               && group.equals(featureGroup))
1022       {
1023         result.add(sf);
1024       }
1025     }
1026     return result;
1027   }
1028
1029   /**
1030    * Adds the shift value to the start and end of all positional features.
1031    * Returns true if at least one feature was updated, else false.
1032    *
1033    * @param shift
1034    * @return
1035    */
1036   public synchronized boolean shiftFeatures(int shift)
1037   {
1038     /*
1039      * Because begin and end are final fields (to ensure the data store's
1040      * integrity), we have to delete each feature and re-add it as amended.
1041      * (Although a simple shift of all values would preserve data integrity!)
1042      */
1043     boolean modified = false;
1044     for (SequenceFeature sf : getPositionalFeatures())
1045     {
1046       modified = true;
1047       int newBegin = sf.getBegin() + shift;
1048       int newEnd = sf.getEnd() + shift;
1049
1050       /*
1051        * sanity check: don't shift left of the first residue
1052        */
1053       if (newEnd > 0)
1054       {
1055         newBegin = Math.max(1, newBegin);
1056         SequenceFeature sf2 = new SequenceFeature(sf, newBegin, newEnd,
1057                 sf.getFeatureGroup(), sf.getScore());
1058         addFeature(sf2);
1059       }
1060       delete(sf);
1061     }
1062     return modified;
1063   }
1064 }