src/jalview/datamodel/features/FeatureStore.java

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