X-Git-Url: http://source.jalview.org/gitweb/?p=jalview.git;a=blobdiff_plain;f=src%2Fjalview%2Fdatamodel%2Ffeatures%2FFeatureStore.java;fp=src%2Fjalview%2Fdatamodel%2Ffeatures%2FFeatureStore.java;h=54c0d59f90b164a1f62d890b60e32be94cfd383b;hp=951b7a5e0859b384e2b3dd9346123550506d58e5;hb=74393b51f368cb9f58589472d432a433d9c4386d;hpb=7a0d503181fe41452120a8a02ca63476392aa08c

diff --git a/src/jalview/datamodel/features/FeatureStore.java b/src/jalview/datamodel/features/FeatureStore.java
index 951b7a5..54c0d59 100644
--- a/src/jalview/datamodel/features/FeatureStore.java
+++ b/src/jalview/datamodel/features/FeatureStore.java
@@ -20,16 +20,18 @@
  */
 package jalview.datamodel.features;
 
-import jalview.datamodel.ContiguousI;
 import jalview.datamodel.SequenceFeature;
 
 import java.util.ArrayList;
 import java.util.Collections;
-import java.util.Comparator;
 import java.util.HashSet;
 import java.util.List;
 import java.util.Set;
 
+import intervalstore.api.IntervalStoreI;
+import intervalstore.impl.BinarySearcher;
+import intervalstore.impl.IntervalStore;
+
 /**
  * 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
@@ -40,80 +42,6 @@ import java.util.Set;
  */
 public class FeatureStore
 {
-  /**
-   * a class providing criteria for performing a binary search of a list
-   */
-  abstract static class SearchCriterion
-  {
-    /**
-     * Answers true if the entry passes the search criterion test
-     * 
-     * @param entry
-     * @return
-     */
-    abstract boolean compare(SequenceFeature entry);
-
-    /**
-     * serves a search condition for finding the first feature whose start
-     * position follows a given target location
-     * 
-     * @param target
-     * @return
-     */
-    static SearchCriterion byStart(final long target)
-    {
-      return new SearchCriterion() {
-
-        @Override
-        boolean compare(SequenceFeature entry)
-        {
-          return entry.getBegin() >= target;
-        }
-      };
-    }
-
-    /**
-     * serves a search condition for finding the first feature whose end
-     * position is at or follows a given target location
-     * 
-     * @param target
-     * @return
-     */
-    static SearchCriterion byEnd(final long target)
-    {
-      return new SearchCriterion()
-      {
-
-        @Override
-        boolean compare(SequenceFeature entry)
-        {
-          return entry.getEnd() >= target;
-        }
-      };
-    }
-
-    /**
-     * serves a search condition for finding the first feature which follows the
-     * given range as determined by a supplied comparator
-     * 
-     * @param target
-     * @return
-     */
-    static SearchCriterion byFeature(final ContiguousI to,
-            final Comparator<ContiguousI> rc)
-    {
-      return new SearchCriterion()
-      {
-
-        @Override
-        boolean compare(SequenceFeature entry)
-        {
-          return rc.compare(entry, to) >= 0;
-        }
-      };
-    }
-  }
-
   /*
    * Non-positional features have no (zero) start/end position.
    * Kept as a separate list in case this criterion changes in future.
@@ -121,14 +49,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;
@@ -139,13 +59,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 
@@ -178,16 +95,15 @@ public class FeatureStore
    */
   public FeatureStore()
   {
-    nonNestedFeatures = new ArrayList<SequenceFeature>();
-    positionalFeatureGroups = new HashSet<String>();
-    nonPositionalFeatureGroups = new HashSet<String>();
+    features = new IntervalStore<>();
+    positionalFeatureGroups = new HashSet<>();
+    nonPositionalFeatureGroups = new HashSet<>();
     positionalMinScore = Float.NaN;
     positionalMaxScore = Float.NaN;
     nonPositionalMinScore = Float.NaN;
     nonPositionalMaxScore = Float.NaN;
 
-    // we only construct nonPositionalFeatures, contactFeatures
-    // or the NCList if we need to
+    // we only construct nonPositionalFeatures, contactFeatures if we need to
   }
 
   /**
@@ -213,58 +129,46 @@ public class FeatureStore
       positionalFeatureGroups.add(feature.getFeatureGroup());
     }
 
-    boolean added = false;
-
     if (feature.isContactFeature())
     {
-      added = addContactFeature(feature);
+      addContactFeature(feature);
     }
     else if (feature.isNonPositional())
     {
-      added = addNonPositionalFeature(feature);
+      addNonPositionalFeature(feature);
     }
     else
     {
-      added = addNonNestedFeature(feature);
-      if (!added)
-      {
-        /*
-         * detected a nested feature - put it in the NCList structure
-         */
-        added = addNestedFeature(feature);
-      }
+      addNestedFeature(feature);
     }
 
-    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);
+    /*
+     * record the total extent of positional features, to make
+     * getTotalFeatureLength possible; we count the length of a 
+     * contact feature as 1
+     */
+    totalExtent += getFeatureLength(feature);
 
-      /*
-       * record the minimum and maximum score for positional
-       * and non-positional features
-       */
-      float score = feature.getScore();
-      if (!Float.isNaN(score))
+    /*
+     * record the minimum and maximum score for positional
+     * and non-positional features
+     */
+    float score = feature.getScore();
+    if (!Float.isNaN(score))
+    {
+      if (feature.isNonPositional())
       {
-        if (feature.isNonPositional())
-        {
-          nonPositionalMinScore = min(nonPositionalMinScore, score);
-          nonPositionalMaxScore = max(nonPositionalMaxScore, score);
-        }
-        else
-        {
-          positionalMinScore = min(positionalMinScore, score);
-          positionalMaxScore = max(positionalMaxScore, score);
-        }
+        nonPositionalMinScore = min(nonPositionalMinScore, score);
+        nonPositionalMaxScore = max(nonPositionalMaxScore, score);
+      }
+      else
+      {
+        positionalMinScore = min(positionalMinScore, score);
+        positionalMaxScore = max(positionalMaxScore, score);
       }
     }
 
-    return added;
+    return true;
   }
 
   /**
@@ -288,12 +192,7 @@ public class FeatureStore
               contactFeatureStarts, feature);
     }
 
-    if (listContains(nonNestedFeatures, feature))
-    {
-      return true;
-    }
-
-    return nestedFeatures == null ? false : nestedFeatures
+    return features == null ? false : features
             .contains(feature);
   }
 
@@ -330,7 +229,7 @@ public class FeatureStore
   {
     if (nonPositionalFeatures == null)
     {
-      nonPositionalFeatures = new ArrayList<SequenceFeature>();
+      nonPositionalFeatures = new ArrayList<>();
     }
 
     nonPositionalFeatures.add(feature);
@@ -341,91 +240,16 @@ public class FeatureStore
   }
 
   /**
-   * 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.
-   */
-  protected synchronized boolean addNestedFeature(SequenceFeature feature)
-  {
-    if (nestedFeatures == null)
-    {
-      nestedFeatures = new NCList<>(feature);
-      return true;
-    }
-    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.
-   * 
-   * @param feature
-   * @return
-   */
-  protected boolean addNonNestedFeature(SequenceFeature feature)
-  {
-    synchronized (nonNestedFeatures)
-    {
-      /*
-       * 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;
-    }
-  }
-
-  /**
-   * Answers true if range1 properly encloses range2, else false
-   * 
-   * @param range1
-   * @param range2
-   * @return
+   * Adds one feature to the IntervalStore that can manage nested features
+   * (creating the IntervalStore if necessary)
    */
-  protected boolean encloses(ContiguousI range1, ContiguousI range2)
+  protected synchronized void addNestedFeature(SequenceFeature feature)
   {
-    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)
+    if (features == null)
     {
-      return true;
+      features = new IntervalStore<>();
     }
-    return false;
+    features.add(feature);
   }
 
   /**
@@ -441,28 +265,29 @@ public class FeatureStore
   {
     if (contactFeatureStarts == null)
     {
-      contactFeatureStarts = new ArrayList<SequenceFeature>();
+      contactFeatureStarts = new ArrayList<>();
     }
     if (contactFeatureEnds == null)
     {
-      contactFeatureEnds = new ArrayList<SequenceFeature>();
+      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));
+    int insertPosition = BinarySearcher.findFirst(contactFeatureStarts,
+            f -> f.getBegin() >= feature.getBegin());
     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);
+
+    /*
+     * insert into list sorted by end (second contact position):
+     * binary search the sorted list to find the insertion point
+     */
+    insertPosition = BinarySearcher.findFirst(contactFeatureEnds,
+            f -> f.getEnd() >= feature.getEnd());
+    contactFeatureEnds.add(insertPosition, feature);
 
     return true;
   }
@@ -487,8 +312,10 @@ public class FeatureStore
     /*
      * locate the first entry in the list which does not precede the feature
      */
-    int pos = binarySearch(features,
-            SearchCriterion.byFeature(feature, RangeComparator.BY_START_POSITION));
+    // int pos = binarySearch(features,
+    // SearchCriterion.byFeature(feature, RangeComparator.BY_START_POSITION));
+    int pos = BinarySearcher.findFirst(features,
+            val -> val.getBegin() >= feature.getBegin());
     int len = features.size();
     while (pos < len)
     {
@@ -521,13 +348,11 @@ public class FeatureStore
   {
     List<SequenceFeature> result = new ArrayList<>();
 
-    findNonNestedFeatures(start, end, result);
-
     findContactFeatures(start, end, result);
 
-    if (nestedFeatures != null)
+    if (features != null)
     {
-      result.addAll(nestedFeatures.findOverlaps(start, end));
+      result.addAll(features.findOverlaps(start, end));
     }
 
     return result;
@@ -546,11 +371,11 @@ public class FeatureStore
   {
     if (contactFeatureStarts != null)
     {
-      findContactStartFeatures(from, to, result);
+      findContactStartOverlaps(from, to, result);
     }
     if (contactFeatureEnds != null)
     {
-      findContactEndFeatures(from, to, result);
+      findContactEndOverlaps(from, to, result);
     }
   }
 
@@ -563,22 +388,24 @@ public class FeatureStore
    * @param to
    * @param result
    */
-  protected void findContactEndFeatures(long from, long to,
+  protected void findContactEndOverlaps(long from, long to,
           List<SequenceFeature> result)
   {
     /*
-     * find the first contact feature (if any) that does not lie 
-     * entirely before the target range
+     * find the first contact feature (if any) 
+     * whose end point is not before the target range
      */
-    int startPosition = binarySearch(contactFeatureEnds,
-            SearchCriterion.byEnd(from));
-    for (; startPosition < contactFeatureEnds.size(); startPosition++)
+    int index = BinarySearcher.findFirst(contactFeatureEnds,
+            f -> f.getEnd() >= from);
+
+    while (index < contactFeatureEnds.size())
     {
-      SequenceFeature sf = contactFeatureEnds.get(startPosition);
+      SequenceFeature sf = contactFeatureEnds.get(index);
       if (!sf.isContactFeature())
       {
         System.err.println("Error! non-contact feature type "
                 + sf.getType() + " in contact features list");
+        index++;
         continue;
       }
 
@@ -589,54 +416,24 @@ public class FeatureStore
          * this feature's first contact position lies in the search range
          * so we don't include it in results a second time
          */
+        index++;
         continue;
       }
 
-      int end = sf.getEnd();
-      if (end >= from && end <= to)
-      {
-        result.add(sf);
-      }
-      if (end > to)
+      if (sf.getEnd() > to)
       {
+        /*
+         * this feature (and all following) has end point after the target range
+         */
         break;
       }
-    }
-  }
-
-  /**
-   * 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.
-   * 
-   * @param from
-   * @param to
-   * @param result
-   */
-  protected void findNonNestedFeatures(long from, long to,
-          List<SequenceFeature> result)
-  {
-    /*
-     * find the first feature whose end position is
-     * after the target range start
-     */
-    int startIndex = binarySearch(nonNestedFeatures,
-            SearchCriterion.byEnd(from));
 
-    final int startIndex1 = startIndex;
-    int i = startIndex1;
-    while (i < nonNestedFeatures.size())
-    {
-      SequenceFeature sf = nonNestedFeatures.get(i);
-      if (sf.getBegin() > to)
-      {
-        break;
-      }
-      if (sf.getBegin() <= to && sf.getEnd() >= from)
-      {
-        result.add(sf);
-      }
-      i++;
+      /*
+       * feature has end >= from and end <= to
+       * i.e. contact end point lies within overlap search range
+       */
+      result.add(sf);
+      index++;
     }
   }
 
@@ -648,26 +445,36 @@ public class FeatureStore
    * @param to
    * @param result
    */
-  protected void findContactStartFeatures(long from, long to,
+  protected void findContactStartOverlaps(long from, long to,
           List<SequenceFeature> result)
   {
-    int startPosition = binarySearch(contactFeatureStarts,
-            SearchCriterion.byStart(from));
+    int index = BinarySearcher.findFirst(contactFeatureStarts,
+            f -> f.getBegin() >= from);
 
-    for (; startPosition < contactFeatureStarts.size(); startPosition++)
+    while (index < contactFeatureStarts.size())
     {
-      SequenceFeature sf = contactFeatureStarts.get(startPosition);
+      SequenceFeature sf = contactFeatureStarts.get(index);
       if (!sf.isContactFeature())
       {
-        System.err.println("Error! non-contact feature type "
-                + sf.getType() + " in contact features list");
+        System.err.println("Error! non-contact feature " + sf.toString()
+                + " in contact features list");
+        index++;
         continue;
       }
-      int begin = sf.getBegin();
-      if (begin >= from && begin <= to)
+      if (sf.getBegin() > to)
       {
-        result.add(sf);
+        /*
+         * this feature's start (and all following) follows the target range
+         */
+        break;
       }
+
+      /*
+       * feature has begin >= from and begin <= to
+       * i.e. contact start point lies within overlap search range
+       */
+      result.add(sf);
+      index++;
     }
   }
 
@@ -678,11 +485,7 @@ public class FeatureStore
    */
   public List<SequenceFeature> getPositionalFeatures()
   {
-    /*
-     * add non-nested features (may be all features for many cases)
-     */
     List<SequenceFeature> result = new ArrayList<>();
-    result.addAll(nonNestedFeatures);
 
     /*
      * add any contact features - from the list by start position
@@ -695,9 +498,9 @@ public class FeatureStore
     /*
      * add any nested features
      */
-    if (nestedFeatures != null)
+    if (features != null)
     {
-      result.addAll(nestedFeatures.getEntries());
+      result.addAll(features);
     }
 
     return result;
@@ -743,13 +546,10 @@ public class FeatureStore
    */
   public synchronized boolean delete(SequenceFeature sf)
   {
-    /*
-     * try the non-nested positional features first
-     */
-    boolean removed = nonNestedFeatures.remove(sf);
+    boolean removed = false;
 
     /*
-     * if not found, try contact positions (and if found, delete
+     * try contact positions (and if found, delete
      * from both lists of contact positions)
      */
     if (!removed && contactFeatureStarts != null)
@@ -775,9 +575,9 @@ public class FeatureStore
     /*
      * if not found, try nested features
      */
-    if (!removed && nestedFeatures != null)
+    if (!removed && features != null)
     {
-      removed = nestedFeatures.delete(sf);
+      removed = features.remove(sf);
     }
 
     if (removed)
@@ -874,12 +674,12 @@ public class FeatureStore
    */
   public boolean isEmpty()
   {
-    boolean hasFeatures = !nonNestedFeatures.isEmpty()
-            || (contactFeatureStarts != null && !contactFeatureStarts
+    boolean hasFeatures = (contactFeatureStarts != null
+            && !contactFeatureStarts
                     .isEmpty())
             || (nonPositionalFeatures != null && !nonPositionalFeatures
                     .isEmpty())
-            || (nestedFeatures != null && nestedFeatures.size() > 0);
+            || (features != null && features.size() > 0);
 
     return !hasFeatures;
   }
@@ -907,41 +707,6 @@ public class FeatureStore
   }
 
   /**
-   * 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.
-   * 
-   * @param features
-   * @param sc
-   * @return
-   */
-  protected static int binarySearch(List<SequenceFeature> features,
-          SearchCriterion sc)
-  {
-    int start = 0;
-    int end = features.size() - 1;
-    int matched = features.size();
-
-    while (start <= end)
-    {
-      int mid = (start + end) / 2;
-      SequenceFeature entry = features.get(mid);
-      boolean compare = sc.compare(entry);
-      if (compare)
-      {
-        matched = mid;
-        end = mid - 1;
-      }
-      else
-      {
-        start = mid + 1;
-      }
-    }
-
-    return matched;
-  }
-
-  /**
    * Answers the number of positional (or non-positional) features stored.
    * Contact features count as 1.
    * 
@@ -956,7 +721,7 @@ public class FeatureStore
               .size();
     }
 
-    int size = nonNestedFeatures.size();
+    int size = 0;
 
     if (contactFeatureStarts != null)
     {
@@ -964,9 +729,9 @@ public class FeatureStore
       size += contactFeatureStarts.size();
     }
 
-    if (nestedFeatures != null)
+    if (features != null)
     {
-      size += nestedFeatures.size();
+      size += features.size();
     }
 
     return size;