JAL-2480 more efficient contains check on add; tidied comparators

[jalview.git] / src / jalview / datamodel / features / FeatureStore.java

diff --git a/src/jalview/datamodel/features/FeatureStore.java b/src/jalview/datamodel/features/FeatureStore.java
index 75e99c7..432f62d 100644 (file)
--- a/src/jalview/datamodel/features/FeatureStore.java
+++ b/src/jalview/datamodel/features/FeatureStore.java
@@ -72,10 +72,6 @@ public class FeatureStore
     }
   }
 
-  Comparator<ContiguousI> startOrdering = new RangeComparator(true);
-
-  Comparator<ContiguousI> endOrdering = new RangeComparator(false);
-
   /*
    * Non-positional features have no (zero) start/end position.
    * Kept as a separate list in case this criterion changes in future.
@@ -182,7 +178,7 @@ public class FeatureStore
     }
     else
     {
-      if (!nonNestedFeatures.contains(feature))
+      if (!contains(nonNestedFeatures, feature))
       {
         added = addNonNestedFeature(feature);
         if (!added)
@@ -308,7 +304,7 @@ public class FeatureStore
        * find the first stored feature which doesn't precede the new one
        */
       int insertPosition = binarySearch(nonNestedFeatures,
-              SearchCriterion.byFeature(feature, startOrdering));
+              SearchCriterion.byFeature(feature, RangeComparator.BY_START_POSITION));
 
       /*
        * fail if we detect feature enclosure - of the new feature by
@@ -382,21 +378,70 @@ public class FeatureStore
       contactFeatureEnds = new ArrayList<SequenceFeature>();
     }
 
-    // TODO binary search for insertion points!
-    if (contactFeatureStarts.contains(feature))
+    if (contains(contactFeatureStarts, feature))
     {
       return false;
     }
 
-    contactFeatureStarts.add(feature);
-    Collections.sort(contactFeatureStarts, startOrdering);
+    /*
+     * 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, endOrdering);
+    Collections.sort(contactFeatureEnds, RangeComparator.BY_END_POSITION);
 
     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.
+   * 
+   * @param features
+   * @param feature
+   * @return
+   */
+  protected static boolean contains(List<SequenceFeature> features,
+          SequenceFeature feature)
+  {
+    if (features == null || feature == null)
+    {
+      return false;
+    }
+
+    /*
+     * 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 len = features.size();
+    while (pos < len)
+    {
+      SequenceFeature sf = features.get(pos);
+      if (sf.getBegin() > feature.getBegin())
+      {
+        return false; // no match found
+      }
+      if (sf.equals(feature))
+      {
+        return true;
+      }
+      pos++;
+    }
+    return false;
+  }
+
+  /**
    * 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.
@@ -842,7 +887,7 @@ public class FeatureStore
    * @param sc
    * @return
    */
-  protected int binarySearch(List<SequenceFeature> features,
+  protected static int binarySearch(List<SequenceFeature> features,
           SearchCriterion sc)
   {
     int start = 0;