X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=src%2Fjalview%2Fdatamodel%2Ffeatures%2FFeatureStore.java;h=615b34036ee713e87b5d50a5f955c0e0d7343135;hb=f8258d012b4afd77e0dd6fd3743714fbabb59c8f;hp=432f62d866980931ff0e04c84f962cab30558c70;hpb=4bb1a8a4b8fc08ed5b0d51f0ea03d9a9ad7dc419;p=jalview.git

diff --git a/src/jalview/datamodel/features/FeatureStore.java b/src/jalview/datamodel/features/FeatureStore.java
index 432f62d..615b340 100644
--- a/src/jalview/datamodel/features/FeatureStore.java
+++ b/src/jalview/datamodel/features/FeatureStore.java
@@ -1,76 +1,47 @@
+/*
+ * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
+ * Copyright (C) $$Year-Rel$$ The Jalview Authors
+ * 
+ * This file is part of Jalview.
+ * 
+ * Jalview is free software: you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License 
+ * as published by the Free Software Foundation, either version 3
+ * of the License, or (at your option) any later version.
+ *  
+ * Jalview is distributed in the hope that it will be useful, but 
+ * WITHOUT ANY WARRANTY; without even the implied warranty 
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR 
+ * PURPOSE.  See the GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
+ * The Jalview Authors are detailed in the 'AUTHORS' file.
+ */
 package jalview.datamodel.features;
 
 import jalview.datamodel.SequenceFeature;
+import jalview.util.Platform;
 
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.Collections;
-import java.util.Comparator;
 import java.util.HashSet;
 import java.util.List;
 import java.util.Set;
 
-/**
- * A data store for a set of sequence features that supports efficient lookup of
- * features overlapping a given range. Intended for (but not limited to) storage
- * of features for one sequence and feature type.
- * 
- * @author gmcarstairs
- *
- */
+import intervalstore.api.IntervalStoreI;
+import intervalstore.impl.BinarySearcher;
+import intervalstore.impl.BinarySearcher.Compare;
+
 public class FeatureStore
 {
-  /**
-   * a class providing criteria for performing a binary search of a list
+  /*
+   * track last start for quick insertion of ordered features
    */
-  abstract static class SearchCriterion
-  {
-    /**
-     * Answers true if the entry passes the search criterion test
-     * 
-     * @param entry
-     * @return
-     */
-    abstract boolean compare(SequenceFeature entry);
-
-    static SearchCriterion byStart(final long target)
-    {
-      return new SearchCriterion() {
-
-        @Override
-        boolean compare(SequenceFeature entry)
-        {
-          return entry.getBegin() >= target;
-        }
-      };
-    }
-
-    static SearchCriterion byEnd(final long target)
-    {
-      return new SearchCriterion()
-      {
-
-        @Override
-        boolean compare(SequenceFeature entry)
-        {
-          return entry.getEnd() >= target;
-        }
-      };
-    }
+  protected int lastStart = -1;
 
-    static SearchCriterion byFeature(final ContiguousI to,
-            final Comparator<ContiguousI> rc)
-    {
-      return new SearchCriterion()
-      {
-
-        @Override
-        boolean compare(SequenceFeature entry)
-        {
-          return rc.compare(entry, to) >= 0;
-        }
-      };
-    }
-  }
+  protected int lastContactStart = -1;
 
   /*
    * Non-positional features have no (zero) start/end position.
@@ -79,14 +50,6 @@ public class FeatureStore
   List<SequenceFeature> nonPositionalFeatures;
 
   /*
-   * An ordered list of features, with the promise that no feature in the list 
-   * properly contains any other. This constraint allows bounded linear search
-   * of the list for features overlapping a region.
-   * Contact features are not included in this list.
-   */
-  List<SequenceFeature> nonNestedFeatures;
-
-  /*
    * contact features ordered by first contact position
    */
   List<SequenceFeature> contactFeatureStarts;
@@ -97,13 +60,10 @@ public class FeatureStore
   List<SequenceFeature> contactFeatureEnds;
 
   /*
-   * Nested Containment List is used to hold any features that are nested 
-   * within (properly contained by) any other feature. This is a recursive tree
-   * which supports depth-first scan for features overlapping a range.
-   * It is used here as a 'catch-all' fallback for features that cannot be put
-   * into a simple ordered list without invalidating the search methods.
+   * IntervalStore holds remaining features and provides efficient
+   * query for features overlapping any given interval
    */
-  NCList<SequenceFeature> nestedFeatures;
+  IntervalStoreI<SequenceFeature> features;
 
   /*
    * Feature groups represented in stored positional features 
@@ -131,97 +91,33 @@ public class FeatureStore
 
   float nonPositionalMaxScore;
 
+  public final static int INTERVAL_STORE_DEFAULT = -1;
+
   /**
-   * Constructor
+   * original NCList-based IntervalStore
    */
-  public FeatureStore()
-  {
-    nonNestedFeatures = new ArrayList<SequenceFeature>();
-    positionalFeatureGroups = new HashSet<String>();
-    nonPositionalFeatureGroups = new HashSet<String>();
-    positionalMinScore = Float.NaN;
-    positionalMaxScore = Float.NaN;
-    nonPositionalMinScore = Float.NaN;
-    nonPositionalMaxScore = Float.NaN;
-
-    // we only construct nonPositionalFeatures, contactFeatures
-    // or the NCList if we need to
-  }
+  public final static int INTERVAL_STORE_NCLIST_OBJECT = 0;
 
   /**
-   * Adds one sequence feature to the store, and returns true, unless the
-   * feature is already contained in the store, in which case this method
-   * returns false. Containment is determined by SequenceFeature.equals()
-   * comparison.
-   * 
-   * @param feature
+   * linked-list IntervalStore
    */
-  public boolean addFeature(SequenceFeature feature)
-  {
-    /*
-     * keep a record of feature groups
-     */
-    if (!feature.isNonPositional())
-    {
-      positionalFeatureGroups.add(feature.getFeatureGroup());
-    }
+  public final static int INTERVAL_STORE_LINKED_LIST = 1;
 
-    boolean added = false;
+  /**
+   * NCList as array buffer IntervalStore
+   */
+  public final static int INTERVAL_STORE_NCARRAY = 3;
 
-    if (feature.isContactFeature())
-    {
-      added = addContactFeature(feature);
-    }
-    else if (feature.isNonPositional())
-    {
-      added = addNonPositionalFeature(feature);
-    }
-    else
-    {
-      if (!contains(nonNestedFeatures, feature))
-      {
-        added = addNonNestedFeature(feature);
-        if (!added)
-        {
-          /*
-           * detected a nested feature - put it in the NCList structure
-           */
-          added = addNestedFeature(feature);
-        }
-      }
-    }
+  static final int intervalStoreJavaOption = INTERVAL_STORE_NCLIST_OBJECT;
 
-    if (added)
-    {
-      /*
-       * record the total extent of positional features, to make
-       * getTotalFeatureLength possible; we count the length of a 
-       * contact feature as 1
-       */
-      totalExtent += getFeatureLength(feature);
+  private final static boolean isJSLinkedTest = false;
 
-      /*
-       * record the minimum and maximum score for positional
-       * and non-positional features
-       */
-      float score = feature.getScore();
-      if (!Float.isNaN(score))
-      {
-        if (feature.isNonPositional())
-        {
-          nonPositionalMinScore = min(nonPositionalMinScore, score);
-          nonPositionalMaxScore = max(nonPositionalMaxScore, score);
-        }
-        else
-        {
-          positionalMinScore = min(positionalMinScore, score);
-          positionalMaxScore = max(positionalMaxScore, score);
-        }
-      }
-    }
+  static final int intervalStoreJSOption = (isJSLinkedTest
+          ? INTERVAL_STORE_LINKED_LIST
+          : INTERVAL_STORE_NCARRAY);
 
-    return added;
-  }
+  // TODO: compare performance in real situations using
+  // INTERVAL_STORE_LINKED_LIST;
 
   /**
    * Answers the 'length' of the feature, counting 0 for non-positional features
@@ -244,125 +140,134 @@ public class FeatureStore
   }
 
   /**
-   * Adds the feature to the list of non-positional features (with lazy
-   * instantiation of the list if it is null), and returns true. If the
-   * non-positional features already include the new feature (by equality test),
-   * then it is not added, and this method returns false. The feature group is
-   * added to the set of distinct feature groups for non-positional features.
+   * Answers true if the list contains the feature, else false. This method is
+   * optimised for the condition that the list is sorted on feature start
+   * position ascending, and will give unreliable results if this does not hold.
    * 
+   * @param list
    * @param feature
+   * @return
    */
-  protected boolean addNonPositionalFeature(SequenceFeature feature)
+  public boolean listContains(List<SequenceFeature> list,
+          SequenceFeature feature)
   {
-    if (nonPositionalFeatures == null)
-    {
-      nonPositionalFeatures = new ArrayList<SequenceFeature>();
-    }
-    if (nonPositionalFeatures.contains(feature))
+    if (list == null || feature == null)
     {
       return false;
     }
 
-    nonPositionalFeatures.add(feature);
-
-    nonPositionalFeatureGroups.add(feature.getFeatureGroup());
-
-    return true;
+    /*
+     * locate the first entry in the list which does not precede the feature
+     */
+    int begin = feature.begin;
+    int pos = BinarySearcher.findFirst(list, true, Compare.GE, begin);
+    int len = list.size();
+    while (pos < len)
+    {
+      SequenceFeature sf = list.get(pos);
+      if (sf.begin > begin)
+      {
+        return false; // no match found
+      }
+      if (sf.equals(feature))
+      {
+        return true;
+      }
+      pos++;
+    }
+    return false;
   }
 
   /**
-   * Adds one feature to the NCList that can manage nested features (creating
-   * the NCList if necessary), and returns true. If the feature is already
-   * stored in the NCList (by equality test), then it is not added, and this
-   * method returns false.
+   * A helper method to return the maximum of two floats, where a non-NaN value
+   * is treated as 'greater than' a NaN value (unlike Math.max which does the
+   * opposite)
+   * 
+   * @param f1
+   * @param f2
    */
-  protected synchronized boolean addNestedFeature(SequenceFeature feature)
+  protected static float max(float f1, float f2)
   {
-    if (nestedFeatures == null)
+    if (Float.isNaN(f1))
+    {
+      return Float.isNaN(f2) ? f1 : f2;
+    }
+    else
     {
-      nestedFeatures = new NCList<SequenceFeature>(feature);
-      return true;
+      return Float.isNaN(f2) ? f1 : Math.max(f1, f2);
     }
-    return nestedFeatures.add(feature, false);
   }
 
   /**
-   * Add a feature to the list of non-nested features, maintaining the ordering
-   * of the list. A check is made for whether the feature is nested in (properly
-   * contained by) an existing feature. If there is no nesting, the feature is
-   * added to the list and the method returns true. If nesting is found, the
-   * feature is not added and the method returns false.
+   * A helper method to return the minimum of two floats, where a non-NaN value
+   * is treated as 'less than' a NaN value (unlike Math.min which does the
+   * opposite)
    * 
-   * @param feature
-   * @return
+   * @param f1
+   * @param f2
    */
-  protected boolean addNonNestedFeature(SequenceFeature feature)
+  protected static float min(float f1, float f2)
   {
-    synchronized (nonNestedFeatures)
+    if (Float.isNaN(f1))
     {
-      /*
-       * find the first stored feature which doesn't precede the new one
-       */
-      int insertPosition = binarySearch(nonNestedFeatures,
-              SearchCriterion.byFeature(feature, RangeComparator.BY_START_POSITION));
-
-      /*
-       * fail if we detect feature enclosure - of the new feature by
-       * the one preceding it, or of the next feature by the new one
-       */
-      if (insertPosition > 0)
-      {
-        if (encloses(nonNestedFeatures.get(insertPosition - 1), feature))
-        {
-          return false;
-        }
-      }
-      if (insertPosition < nonNestedFeatures.size())
-      {
-        if (encloses(feature, nonNestedFeatures.get(insertPosition)))
-        {
-          return false;
-        }
-      }
-
-      /*
-       * checks passed - add the feature
-       */
-      nonNestedFeatures.add(insertPosition, feature);
-
-      return true;
+      return Float.isNaN(f2) ? f1 : f2;
+    }
+    else
+    {
+      return Float.isNaN(f2) ? f1 : Math.min(f1, f2);
     }
   }
 
   /**
-   * Answers true if range1 properly encloses range2, else false
-   * 
-   * @param range1
-   * @param range2
-   * @return
+   * standard constructor
    */
-  protected boolean encloses(ContiguousI range1, ContiguousI range2)
+  public FeatureStore()
   {
-    int begin1 = range1.getBegin();
-    int begin2 = range2.getBegin();
-    int end1 = range1.getEnd();
-    int end2 = range2.getEnd();
-    if (begin1 == begin2 && end1 > end2)
-    {
-      return true;
-    }
-    if (begin1 < begin2 && end1 >= end2)
-    {
-      return true;
+    this(INTERVAL_STORE_DEFAULT);
+  }
+
+  /**
+   * constructor for testing only
+   */
+  public FeatureStore(int intervalStoreType)
+  {
+    features =
+            // Platform.isJS()
+            // ? new intervalstore.nonc.IntervalStore<>(true)
+            // : new intervalstore.impl.IntervalStore<>();
+            getIntervalStore(intervalStoreType);
+    positionalFeatureGroups = new HashSet<>();
+    nonPositionalFeatureGroups = new HashSet<>();
+    positionalMinScore = Float.NaN;
+    positionalMaxScore = Float.NaN;
+    nonPositionalMinScore = Float.NaN;
+    nonPositionalMaxScore = Float.NaN;
+
+    // we only construct nonPositionalFeatures, contactFeatures if we need to
+  }
+
+  private IntervalStoreI<SequenceFeature> getIntervalStore(int type)
+  {
+    switch (type != INTERVAL_STORE_DEFAULT ? type : //
+            Platform.isJS() //
+                    ? intervalStoreJSOption
+                    : intervalStoreJavaOption)
+    {
+    default:
+    case INTERVAL_STORE_NCLIST_OBJECT:
+      return new intervalstore.impl.IntervalStore<>();
+    case INTERVAL_STORE_NCARRAY:
+      return new intervalstore.nonc.IntervalStoreImpl();
+    case INTERVAL_STORE_LINKED_LIST:
+      return new intervalstore.nonc.IntervalStore0Impl();
     }
-    return false;
   }
 
   /**
    * Add a contact feature to the lists that hold them ordered by start (first
    * contact) and by end (second contact) position, ensuring the lists remain
-   * ordered, and returns true. If the contact feature lists already contain the
-   * given feature (by test for equality), does not add it and returns false.
+   * ordered, and returns true. This method allows duplicate features to be
+   * added, so test before calling to avoid this.
    * 
    * @param feature
    * @return
@@ -371,302 +276,382 @@ public class FeatureStore
   {
     if (contactFeatureStarts == null)
     {
-      contactFeatureStarts = new ArrayList<SequenceFeature>();
-    }
-    if (contactFeatureEnds == null)
-    {
-      contactFeatureEnds = new ArrayList<SequenceFeature>();
-    }
-
-    if (contains(contactFeatureStarts, feature))
-    {
-      return false;
+      contactFeatureStarts = new ArrayList<>();
+      contactFeatureEnds = new ArrayList<>();
     }
 
     /*
+     * insert into list sorted by start (first contact position):
      * binary search the sorted list to find the insertion point
      */
-    int insertPosition = binarySearch(contactFeatureStarts,
-            SearchCriterion.byFeature(feature,
-                    RangeComparator.BY_START_POSITION));
-    contactFeatureStarts.add(insertPosition, feature);
-    // and resort to mak siccar...just in case insertion point not quite right
-    Collections.sort(contactFeatureStarts, RangeComparator.BY_START_POSITION);
-
-    insertPosition = binarySearch(contactFeatureStarts,
-            SearchCriterion.byFeature(feature,
-                    RangeComparator.BY_END_POSITION));
-    contactFeatureEnds.add(feature);
-    Collections.sort(contactFeatureEnds, RangeComparator.BY_END_POSITION);
+    int insertAt = BinarySearcher.findFirst(contactFeatureStarts, true,
+            Compare.GE, feature.begin);
+    contactFeatureStarts.add(insertAt, feature);
+    /*
+     * insert into list sorted by end (second contact position):
+     * binary search the sorted list to find the insertion point
+     */
+    contactFeatureEnds.add(findFirstEnd(contactFeatureEnds, feature.end),
+            feature);
 
     return true;
   }
 
   /**
-   * Answers true if the list contains the feature, else false. This method is
-   * optimised for the condition that the list is sorted on feature start
-   * position ascending, and will give unreliable results if this does not hold.
+   * Adds one sequence feature to the store, and returns true, unless the
+   * feature is already contained in the store, in which case this method
+   * returns false. Containment is determined by SequenceFeature.equals()
+   * comparison.
    * 
-   * @param features
    * @param feature
-   * @return
    */
-  protected static boolean contains(List<SequenceFeature> features,
-          SequenceFeature feature)
+  public boolean addFeature(SequenceFeature feature)
   {
-    if (features == null || feature == null)
+    if (feature.isContactFeature())
     {
-      return false;
+      if (containsContactFeature(feature))
+      {
+        return false;
+      }
+      positionalFeatureGroups.add(feature.getFeatureGroup());
+      if (feature.begin > lastContactStart)
+      {
+        lastContactStart = feature.begin;
+      }
+      addContactFeature(feature);
+    }
+    else if (feature.isNonPositional())
+    {
+      if (containsNonPositionalFeature(feature))
+      {
+        return false;
+      }
+
+      addNonPositionalFeature(feature);
+    }
+    else
+    {
+      if (!features.add(feature, false))
+      {
+        return false;
+      }
+      positionalFeatureGroups.add(feature.getFeatureGroup());
+      if (feature.begin > lastStart)
+      {
+        lastStart = feature.begin;
+      }
     }
 
     /*
-     * locate the first entry in the list which does not precede the feature
+     * record the total extent of positional features, to make
+     * getTotalFeatureLength possible; we count the length of a 
+     * contact feature as 1
      */
-    int pos = binarySearch(features,
-            SearchCriterion.byFeature(feature, RangeComparator.BY_START_POSITION));
-    int len = features.size();
-    while (pos < len)
+    totalExtent += getFeatureLength(feature);
+
+    /*
+     * record the minimum and maximum score for positional
+     * and non-positional features
+     */
+    float score = feature.getScore();
+    if (!Float.isNaN(score))
     {
-      SequenceFeature sf = features.get(pos);
-      if (sf.getBegin() > feature.getBegin())
+      if (feature.isNonPositional())
       {
-        return false; // no match found
+        nonPositionalMinScore = min(nonPositionalMinScore, score);
+        nonPositionalMaxScore = max(nonPositionalMaxScore, score);
       }
-      if (sf.equals(feature))
+      else
       {
-        return true;
+        positionalMinScore = min(positionalMinScore, score);
+        positionalMaxScore = max(positionalMaxScore, score);
       }
-      pos++;
     }
-    return false;
+
+    return true;
   }
 
-  /**
-   * Returns a (possibly empty) list of features whose extent overlaps the given
-   * range. The returned list is not ordered. Contact features are included if
-   * either of the contact points lies within the range.
-   * 
-   * @param start
-   *          start position of overlap range (inclusive)
-   * @param end
-   *          end position of overlap range (inclusive)
-   * @return
-   */
-  public List<SequenceFeature> findOverlappingFeatures(long start, long end)
+  private void addFeaturesForGroup(String group,
+          Collection<SequenceFeature> sfs, List<SequenceFeature> result)
   {
-    List<SequenceFeature> result = new ArrayList<SequenceFeature>();
-
-    findNonNestedFeatures(start, end, result);
-
-    findContactFeatures(start, end, result);
-
-    if (nestedFeatures != null)
+    if (sfs == null)
     {
-      result.addAll(nestedFeatures.findOverlaps(start, end));
+      return;
+    }
+    for (SequenceFeature sf : sfs)
+    {
+      String featureGroup = sf.getFeatureGroup();
+      if (group == null && featureGroup == null
+              || group != null && group.equals(featureGroup))
+      {
+        result.add(sf);
+      }
     }
-
-    return result;
   }
 
   /**
-   * Adds contact features to the result list where either the second or the
-   * first contact position lies within the target range
+   * Adds the feature to the list of non-positional features (with lazy
+   * instantiation of the list if it is null), and returns true. The feature
+   * group is added to the set of distinct feature groups for non-positional
+   * features. This method allows duplicate features, so test before calling to
+   * prevent this.
    * 
-   * @param from
-   * @param to
-   * @param result
+   * @param feature
    */
-  protected void findContactFeatures(long from, long to,
-          List<SequenceFeature> result)
+  protected boolean addNonPositionalFeature(SequenceFeature feature)
   {
-    if (contactFeatureStarts != null)
+    if (nonPositionalFeatures == null)
     {
-      findContactStartFeatures(from, to, result);
+      nonPositionalFeatures = new ArrayList<>();
     }
-    if (contactFeatureEnds != null)
+
+    nonPositionalFeatures.add(feature);
+
+    nonPositionalFeatureGroups.add(feature.getFeatureGroup());
+
+    return true;
+  }
+
+  /**
+   * Answers true if this store contains the given feature (testing by
+   * SequenceFeature.equals), else false
+   * 
+   * @param feature
+   * @return
+   */
+  public boolean contains(SequenceFeature feature)
+  {
+    if (feature.isNonPositional())
     {
-      findContactEndFeatures(from, to, result);
+      return containsNonPositionalFeature(feature);
     }
+
+    if (feature.isContactFeature())
+    {
+      return containsContactFeature(feature);
+    }
+
+    return containsPositionalFeature(feature);
+
+  }
+
+  private boolean containsPositionalFeature(SequenceFeature feature)
+  {
+    return features == null || feature.begin > lastStart ? false
+            : features.contains(feature);
   }
 
   /**
-   * Adds to the result list any contact features whose end (second contact
-   * point), but not start (first contact point), lies in the query from-to
-   * range
+   * Answers true if this store already contains a contact feature equal to the
+   * given feature (by {@code SequenceFeature.equals()} test), else false
    * 
-   * @param from
-   * @param to
-   * @param result
+   * @param feature
+   * @return
    */
-  protected void findContactEndFeatures(long from, long to,
-          List<SequenceFeature> result)
+  private boolean containsContactFeature(SequenceFeature feature)
   {
+    return contactFeatureStarts != null && feature.begin <= lastContactStart
+            && listContains(contactFeatureStarts, feature);
+  }
+
+  /**
+   * Answers true if this store already contains a non-positional feature equal
+   * to the given feature (by {@code SequenceFeature.equals()} test), else false
+   * 
+   * @param feature
+   * @return
+   */
+  private boolean containsNonPositionalFeature(SequenceFeature feature)
+  {
+    return nonPositionalFeatures == null ? false
+            : nonPositionalFeatures.contains(feature);
+  }
+
+  /**
+   * Deletes the given feature from the store, returning true if it was found
+   * (and deleted), else false. This method makes no assumption that the feature
+   * is in the 'expected' place in the store, in case it has been modified since
+   * it was added.
+   * 
+   * @param sf
+   */
+  public synchronized boolean delete(SequenceFeature sf)
+  {
+    boolean removed = false;
+
     /*
-     * find the first contact feature (if any) that does not lie 
-     * entirely before the target range
+     * try contact positions (and if found, delete
+     * from both lists of contact positions)
      */
-    int startPosition = binarySearch(contactFeatureEnds,
-            SearchCriterion.byEnd(from));
-    for (; startPosition < contactFeatureEnds.size(); startPosition++)
+    if (!removed && contactFeatureStarts != null)
     {
-      SequenceFeature sf = contactFeatureEnds.get(startPosition);
-      if (!sf.isContactFeature())
+      removed = contactFeatureStarts.remove(sf);
+      if (removed)
       {
-        System.err.println("Error! non-contact feature type "
-                + sf.getType() + " in contact features list");
-        continue;
+        contactFeatureEnds.remove(sf);
       }
+    }
 
-      int begin = sf.getBegin();
-      if (begin >= from && begin <= to)
-      {
-        /*
-         * this feature's first contact position lies in the search range
-         * so we don't include it in results a second time
-         */
-        continue;
-      }
+    /*
+     * if not found, try non-positional features
+     */
+    if (!removed && nonPositionalFeatures != null)
+    {
+      removed = nonPositionalFeatures.remove(sf);
+    }
 
-      int end = sf.getEnd();
-      if (end >= from && end <= to)
-      {
-        result.add(sf);
-      }
-      if (end > to)
-      {
-        break;
-      }
+    /*
+     * if not found, try nested features
+     */
+    if (!removed && features != null)
+    {
+      removed = features.remove(sf);
+    }
+
+    if (removed)
+    {
+      rescanAfterDelete();
     }
+
+    return removed;
+  }
+
+  public List<SequenceFeature> findOverlappingFeatures(long start, long end)
+  {
+    return findOverlappingFeatures(start, end, null);
+  }
+
+  public List<SequenceFeature> getContactFeatures()
+  {
+    return getContactFeatures(new ArrayList<>());
   }
 
   /**
-   * Adds non-nested features to the result list that lie within the target
-   * range. Non-positional features (start=end=0), contact features and nested
-   * features are excluded.
+   * Answers a list of all contact features. If there are none, returns an
+   * immutable empty list.
    * 
-   * @param from
-   * @param to
-   * @param result
+   * @return
    */
-  protected void findNonNestedFeatures(long from, long to,
+  public List<SequenceFeature> getContactFeatures(
           List<SequenceFeature> result)
   {
-    int startIndex = binarySearch(nonNestedFeatures,
-            SearchCriterion.byEnd(from));
-
-    findNonNestedFeatures(startIndex, from, to, result);
+    if (contactFeatureStarts != null)
+    {
+      result.addAll(contactFeatureStarts);
+    }
+    return result;
   }
 
   /**
-   * Scans the list of non-nested features, starting from startIndex, to find
-   * those that overlap the from-to range, and adds them to the result list.
-   * Returns the index of the first feature whose start position is after the
-   * target range (or the length of the whole list if none such feature exists).
+   * Answers the number of positional (or non-positional) features stored.
+   * Contact features count as 1.
    * 
-   * @param startIndex
-   * @param from
-   * @param to
-   * @param result
+   * @param positional
    * @return
    */
-  protected int findNonNestedFeatures(final int startIndex, long from,
-          long to, List<SequenceFeature> result)
+  public int getFeatureCount(boolean positional)
   {
-    int i = startIndex;
-    while (i < nonNestedFeatures.size())
+    if (!positional)
     {
-      SequenceFeature sf = nonNestedFeatures.get(i);
-      if (sf.getBegin() > to)
-      {
-        break;
-      }
-      int start = sf.getBegin();
-      int end = sf.getEnd();
-      if (start <= to && end >= from)
-      {
-        result.add(sf);
-      }
-      i++;
+      return nonPositionalFeatures == null ? 0
+              : nonPositionalFeatures.size();
     }
-    return i;
+
+    return (contactFeatureStarts == null ? 0 : contactFeatureStarts.size())
+            + features.size();
   }
 
   /**
-   * Adds contact features whose start position lies in the from-to range to the
-   * result list
+   * Answers the set of distinct feature groups stored, possibly including null,
+   * as an unmodifiable view of the set. The parameter determines whether the
+   * groups for positional or for non-positional features are returned.
    * 
-   * @param from
-   * @param to
-   * @param result
+   * @param positionalFeatures
+   * @return
    */
-  protected void findContactStartFeatures(long from, long to,
-          List<SequenceFeature> result)
+  public Set<String> getFeatureGroups(boolean positionalFeatures)
   {
-    int startPosition = binarySearch(contactFeatureStarts,
-            SearchCriterion.byStart(from));
-
-    for (; startPosition < contactFeatureStarts.size(); startPosition++)
+    if (positionalFeatures)
     {
-      SequenceFeature sf = contactFeatureStarts.get(startPosition);
-      if (!sf.isContactFeature())
-      {
-        System.err.println("Error! non-contact feature type "
-                + sf.getType() + " in contact features list");
-        continue;
-      }
-      int begin = sf.getBegin();
-      if (begin >= from && begin <= to)
-      {
-        result.add(sf);
-      }
+      return Collections.unmodifiableSet(positionalFeatureGroups);
+    }
+    else
+    {
+      return nonPositionalFeatureGroups == null
+              ? Collections.<String> emptySet()
+              : Collections.unmodifiableSet(nonPositionalFeatureGroups);
     }
   }
 
+  public Collection<SequenceFeature> getFeatures()
+  {
+    return features;
+  }
+
   /**
-   * Answers a list of all positional features stored, in no guaranteed order
+   * Answers a list of all either positional or non-positional features whose
+   * feature group matches the given group (which may be null)
    * 
+   * @param positional
+   * @param group
    * @return
    */
-  public List<SequenceFeature> getPositionalFeatures()
+  public List<SequenceFeature> getFeaturesForGroup(boolean positional,
+          String group)
   {
-    /*
-     * add non-nested features (may be all features for many cases)
-     */
-    List<SequenceFeature> result = new ArrayList<SequenceFeature>();
-    result.addAll(nonNestedFeatures);
+    List<SequenceFeature> result = new ArrayList<>();
 
     /*
-     * add any contact features - from the list by start position
+     * if we know features don't include the target group, no need
+     * to inspect them for matches
      */
-    if (contactFeatureStarts != null)
+    if (positional && !positionalFeatureGroups.contains(group)
+            || !positional && !nonPositionalFeatureGroups.contains(group))
     {
-      result.addAll(contactFeatureStarts);
+      return result;
     }
 
-    /*
-     * add any nested features
-     */
-    if (nestedFeatures != null)
+    if (positional)
     {
-      result.addAll(nestedFeatures.getEntries());
+      addFeaturesForGroup(group, contactFeatureStarts, result);
+      addFeaturesForGroup(group, features, result);
+    }
+    else
+    {
+      addFeaturesForGroup(group, nonPositionalFeatures, result);
     }
-
     return result;
   }
 
   /**
-   * Answers a list of all contact features. If there are none, returns an
-   * immutable empty list.
+   * Answers the maximum score held for positional or non-positional features.
+   * This may be Float.NaN if there are no features, are none has a non-NaN
+   * score.
    * 
+   * @param positional
    * @return
    */
-  public List<SequenceFeature> getContactFeatures()
+  public float getMaximumScore(boolean positional)
   {
-    if (contactFeatureStarts == null)
-    {
-      return Collections.emptyList();
-    }
-    return new ArrayList<SequenceFeature>(contactFeatureStarts);
+    return positional ? positionalMaxScore : nonPositionalMaxScore;
+  }
+
+  /**
+   * Answers the minimum score held for positional or non-positional features.
+   * This may be Float.NaN if there are no features, are none has a non-NaN
+   * score.
+   * 
+   * @param positional
+   * @return
+   */
+  public float getMinimumScore(boolean positional)
+  {
+    return positional ? positionalMinScore : nonPositionalMinScore;
+  }
+
+  public List<SequenceFeature> getNonPositionalFeatures()
+  {
+    return getNonPositionalFeatures(new ArrayList<>());
   }
 
   /**
@@ -675,68 +660,74 @@ public class FeatureStore
    * 
    * @return
    */
-  public List<SequenceFeature> getNonPositionalFeatures()
+  public List<SequenceFeature> getNonPositionalFeatures(
+          List<SequenceFeature> result)
   {
-    if (nonPositionalFeatures == null)
+    if (nonPositionalFeatures != null)
     {
-      return Collections.emptyList();
+      result.addAll(nonPositionalFeatures);
     }
-    return new ArrayList<SequenceFeature>(nonPositionalFeatures);
+    return result;
+  }
+
+  public List<SequenceFeature> getPositionalFeatures()
+  {
+    return getPositionalFeatures(new ArrayList<>());
   }
 
   /**
-   * Deletes the given feature from the store, returning true if it was found
-   * (and deleted), else false. This method makes no assumption that the feature
-   * is in the 'expected' place in the store, in case it has been modified since
-   * it was added.
+   * Answers a list of all positional features stored, in no guaranteed order
    * 
-   * @param sf
+   * @return
    */
-  public synchronized boolean delete(SequenceFeature sf)
+  public List<SequenceFeature> getPositionalFeatures(
+          List<SequenceFeature> result)
   {
-    /*
-     * try the non-nested positional features first
-     */
-    boolean removed = nonNestedFeatures.remove(sf);
 
     /*
-     * if not found, try contact positions (and if found, delete
-     * from both lists of contact positions)
+     * add any contact features - from the list by start position
      */
-    if (!removed && contactFeatureStarts != null)
+    if (contactFeatureStarts != null)
     {
-      removed = contactFeatureStarts.remove(sf);
-      if (removed)
-      {
-        contactFeatureEnds.remove(sf);
-      }
+      result.addAll(contactFeatureStarts);
     }
 
-    boolean removedNonPositional = false;
-
     /*
-     * if not found, try non-positional features
+     * add any nested features
      */
-    if (!removed && nonPositionalFeatures != null)
+    if (features != null)
     {
-      removedNonPositional = nonPositionalFeatures.remove(sf);
-      removed = removedNonPositional;
+      result.addAll(features);
     }
 
-    /*
-     * if not found, try nested features
-     */
-    if (!removed && nestedFeatures != null)
-    {
-      removed = nestedFeatures.delete(sf);
-    }
+    return result;
+  }
 
-    if (removed)
-    {
-      rescanAfterDelete();
-    }
+  /**
+   * Answers the total length of positional features (or zero if there are
+   * none). Contact features contribute a value of 1 to the total.
+   * 
+   * @return
+   */
+  public int getTotalFeatureLength()
+  {
+    return totalExtent;
+  }
 
-    return removed;
+  /**
+   * Answers true if this store has no features, else false
+   * 
+   * @return
+   */
+  public boolean isEmpty()
+  {
+    boolean hasFeatures = (contactFeatureStarts != null
+            && !contactFeatureStarts.isEmpty())
+            || (nonPositionalFeatures != null
+                    && !nonPositionalFeatures.isEmpty())
+            || features.size() > 0;
+
+    return !hasFeatures;
   }
 
   /**
@@ -753,231 +744,246 @@ public class FeatureStore
     positionalMaxScore = Float.NaN;
     nonPositionalMinScore = Float.NaN;
     nonPositionalMaxScore = Float.NaN;
-
     /*
      * scan non-positional features for groups and scores
      */
-    for (SequenceFeature sf : getNonPositionalFeatures())
+    if (nonPositionalFeatures != null)
     {
-      nonPositionalFeatureGroups.add(sf.getFeatureGroup());
-      float score = sf.getScore();
-      nonPositionalMinScore = min(nonPositionalMinScore, score);
-      nonPositionalMaxScore = max(nonPositionalMaxScore, score);
+      List<SequenceFeature> list = nonPositionalFeatures;
+      for (int i = 0, n = list.size(); i < n; i++)
+      {
+        SequenceFeature sf = list.get(i);
+        nonPositionalFeatureGroups.add(sf.getFeatureGroup());
+        float score = sf.getScore();
+        nonPositionalMinScore = min(nonPositionalMinScore, score);
+        nonPositionalMaxScore = max(nonPositionalMaxScore, score);
+      }
     }
 
     /*
      * scan positional features for groups, scores and extents
      */
-    for (SequenceFeature sf : getPositionalFeatures())
-    {
-      positionalFeatureGroups.add(sf.getFeatureGroup());
-      float score = sf.getScore();
-      positionalMinScore = min(positionalMinScore, score);
-      positionalMaxScore = max(positionalMaxScore, score);
-      totalExtent += getFeatureLength(sf);
-    }
-  }
 
-  /**
-   * A helper method to return the minimum of two floats, where a non-NaN value
-   * is treated as 'less than' a NaN value (unlike Math.min which does the
-   * opposite)
-   * 
-   * @param f1
-   * @param f2
-   */
-  protected static float min(float f1, float f2)
-  {
-    if (Float.isNaN(f1))
-    {
-      return Float.isNaN(f2) ? f1 : f2;
-    }
-    else
-    {
-      return Float.isNaN(f2) ? f1 : Math.min(f1, f2);
-    }
+    rescanPositional(contactFeatureStarts);
+    rescanPositional(features);
   }
 
-  /**
-   * A helper method to return the maximum of two floats, where a non-NaN value
-   * is treated as 'greater than' a NaN value (unlike Math.max which does the
-   * opposite)
-   * 
-   * @param f1
-   * @param f2
-   */
-  protected static float max(float f1, float f2)
+  private void rescanPositional(Collection<SequenceFeature> sfs)
   {
-    if (Float.isNaN(f1))
+    if (sfs == null)
     {
-      return Float.isNaN(f2) ? f1 : f2;
+      return;
     }
-    else
+    for (SequenceFeature sf : sfs)
     {
-      return Float.isNaN(f2) ? f1 : Math.max(f1, f2);
+      positionalFeatureGroups.add(sf.getFeatureGroup());
+      float score = sf.getScore();
+      positionalMinScore = min(positionalMinScore, score);
+      positionalMaxScore = max(positionalMaxScore, score);
+      totalExtent += getFeatureLength(sf);
     }
   }
 
   /**
-   * Scans all positional features to check whether the given feature group is
-   * found, and returns true if found, else false
+   * Adds the shift amount to the start and end of all positional features whose
+   * start position is at or after fromPosition. Returns true if at least one
+   * feature was shifted, else false.
    * 
-   * @param featureGroup
+   * @param fromPosition
+   * @param shiftBy
    * @return
    */
-  protected boolean findFeatureGroup(String featureGroup)
+  public synchronized boolean shiftFeatures(int fromPosition, int shiftBy)
   {
-    for (SequenceFeature sf : getPositionalFeatures())
+    /*
+     * Because begin and end are final fields (to ensure the data store's
+     * integrity), we have to delete each feature and re-add it as amended.
+     * (Although a simple shift of all values would preserve data integrity!)
+     */
+    boolean modified = false;
+    List<SequenceFeature> list = getPositionalFeatures();
+    for (int i = 0, n = list.size(); i < n; i++)
     {
-      String group = sf.getFeatureGroup();
-      if (group == featureGroup
-              || (group != null && group.equals(featureGroup)))
+      SequenceFeature sf = list.get(i);
+      if (sf.getBegin() >= fromPosition)
       {
-        return true;
+        modified = true;
+        int newBegin = sf.getBegin() + shiftBy;
+        int newEnd = sf.getEnd() + shiftBy;
+
+        /*
+         * sanity check: don't shift left of the first residue
+         */
+        if (newEnd > 0)
+        {
+          newBegin = Math.max(1, newBegin);
+          SequenceFeature sf2 = new SequenceFeature(sf, newBegin, newEnd,
+                  sf.getFeatureGroup(), sf.getScore());
+          addFeature(sf2);
+        }
+        delete(sf);
       }
     }
-    return false;
+    return modified;
   }
 
   /**
-   * Answers true if this store has no features, else false
+   * Answers the position (0, 1...) in the list of the first entry whose end
+   * position is not less than {@ pos}. If no such entry is found, answers the
+   * length of the list.
    * 
+   * @param list
+   * @param pos
    * @return
    */
-  public boolean isEmpty()
+  protected int findFirstEnd(List<SequenceFeature> list, long pos)
   {
-    boolean hasFeatures = !nonNestedFeatures.isEmpty()
-            || (contactFeatureStarts != null && !contactFeatureStarts
-                    .isEmpty())
-            || (nonPositionalFeatures != null && !nonPositionalFeatures
-                    .isEmpty())
-            || (nestedFeatures != null && nestedFeatures.size() > 0);
-
-    return !hasFeatures;
+    return BinarySearcher.findFirst(list, false, Compare.GE, (int) pos);
   }
 
   /**
-   * Answers the set of distinct feature groups stored, possibly including null,
-   * as an unmodifiable view of the set. The parameter determines whether the
-   * groups for positional or for non-positional features are returned.
+   * Adds contact features to the result list where either the second or the
+   * first contact position lies within the target range
    * 
-   * @param positionalFeatures
-   * @return
+   * @param from
+   * @param to
+   * @param result
    */
-  public Set<String> getFeatureGroups(boolean positionalFeatures)
+  protected void findContactFeatures(long from, long to,
+          List<SequenceFeature> result)
   {
-    if (positionalFeatures)
-    {
-      return Collections.unmodifiableSet(positionalFeatureGroups);
-    }
-    else
+    if (contactFeatureStarts != null)
     {
-      return nonPositionalFeatureGroups == null ? Collections
-              .<String> emptySet() : Collections
-              .unmodifiableSet(nonPositionalFeatureGroups);
+      findContactStartOverlaps(from, to, result);
+      findContactEndOverlaps(from, to, result);
     }
   }
 
   /**
-   * Performs a binary search of the (sorted) list to find the index of the
-   * first entry which returns true for the given comparator function. Returns
-   * the length of the list if there is no such entry.
+   * Adds to the result list any contact features whose end (second contact
+   * point), but not start (first contact point), lies in the query from-to
+   * range
    * 
-   * @param features
-   * @param sc
-   * @return
+   * @param from
+   * @param to
+   * @param result
    */
-  protected static int binarySearch(List<SequenceFeature> features,
-          SearchCriterion sc)
+  private void findContactEndOverlaps(long from, long to,
+          List<SequenceFeature> result)
   {
-    int start = 0;
-    int end = features.size() - 1;
-    int matched = features.size();
+    /*
+     * find the first contact feature (if any) 
+     * whose end point is not before the target range
+     */
+    int index = findFirstEnd(contactFeatureEnds, from);
 
-    while (start <= end)
+    int n = contactFeatureEnds.size();
+    while (index < n)
     {
-      int mid = (start + end) / 2;
-      SequenceFeature entry = features.get(mid);
-      boolean compare = sc.compare(entry);
-      if (compare)
+      SequenceFeature sf = contactFeatureEnds.get(index);
+      if (!sf.isContactFeature())
       {
-        matched = mid;
-        end = mid - 1;
+        System.err.println("Error! non-contact feature type " + sf.getType()
+                + " in contact features list");
+        index++;
+        continue;
       }
-      else
+
+      int begin = sf.getBegin();
+      if (begin >= from && begin <= to)
+      {
+        /*
+         * this feature's first contact position lies in the search range
+         * so we don't include it in results a second time
+         */
+        index++;
+        continue;
+      }
+
+      if (sf.getEnd() > to)
       {
-        start = mid + 1;
+        /*
+         * this feature (and all following) has end point after the target range
+         */
+        break;
       }
-    }
 
-    return matched;
+      /*
+       * feature has end >= from and end <= to
+       * i.e. contact end point lies within overlap search range
+       */
+      result.add(sf);
+      index++;
+    }
   }
 
   /**
-   * Answers the number of positional (or non-positional) features stored.
-   * Contact features count as 1.
+   * Adds contact features whose start position lies in the from-to range to the
+   * result list
    * 
-   * @param positional
-   * @return
+   * @param from
+   * @param to
+   * @param result
    */
-  public int getFeatureCount(boolean positional)
+  private void findContactStartOverlaps(long from, long to,
+          List<SequenceFeature> result)
   {
-    if (!positional)
-    {
-      return nonPositionalFeatures == null ? 0 : nonPositionalFeatures
-              .size();
-    }
-
-    int size = nonNestedFeatures.size();
+    int index = BinarySearcher.findFirst(contactFeatureStarts, true,
+            Compare.GE, (int) from);
 
-    if (contactFeatureStarts != null)
+    while (index < contactFeatureStarts.size())
     {
-      // note a contact feature (start/end) counts as one
-      size += contactFeatureStarts.size();
-    }
+      SequenceFeature sf = contactFeatureStarts.get(index);
+      if (!sf.isContactFeature())
+      {
+        System.err.println("Error! non-contact feature " + sf.toString()
+                + " in contact features list");
+        index++;
+        continue;
+      }
+      if (sf.getBegin() > to)
+      {
+        /*
+         * this feature's start (and all following) follows the target range
+         */
+        break;
+      }
 
-    if (nestedFeatures != null)
-    {
-      size += nestedFeatures.size();
+      /*
+       * feature has begin >= from and begin <= to
+       * i.e. contact start point lies within overlap search range
+       */
+      result.add(sf);
+      index++;
     }
-
-    return size;
   }
 
   /**
-   * Answers the total length of positional features (or zero if there are
-   * none). Contact features contribute a value of 1 to the total.
+   * Returns a (possibly empty) list of features whose extent overlaps the given
+   * range. The returned list is not ordered. Contact features are included if
+   * either of the contact points lies within the range. If the {@code result}
+   * parameter is not null, new entries are added to this list and the (possibly
+   * extended) list returned.
    * 
+   * @param start
+   *          start position of overlap range (inclusive)
+   * @param end
+   *          end position of overlap range (inclusive)
+   * @param result
    * @return
    */
-  public int getTotalFeatureLength()
+  public List<SequenceFeature> findOverlappingFeatures(long start, long end,
+          List<SequenceFeature> result)
   {
-    return totalExtent;
-  }
+    if (result == null)
+    {
+      result = new ArrayList<>();
+    }
 
-  /**
-   * Answers the minimum score held for positional or non-positional features.
-   * This may be Float.NaN if there are no features, are none has a non-NaN
-   * score.
-   * 
-   * @param positional
-   * @return
-   */
-  public float getMinimumScore(boolean positional)
-  {
-    return positional ? positionalMinScore : nonPositionalMinScore;
-  }
+    findContactFeatures(start, end, result);
+    features.findOverlaps(start, end, result);
 
-  /**
-   * Answers the maximum score held for positional or non-positional features.
-   * This may be Float.NaN if there are no features, are none has a non-NaN
-   * score.
-   * 
-   * @param positional
-   * @return
-   */
-  public float getMaximumScore(boolean positional)
-  {
-    return positional ? positionalMaxScore : nonPositionalMaxScore;
+    return result;
   }
+
 }