JAL-3253-applet JAL-3383 Overview speed up -- see Issue comments.

[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 54c0d59..686ac26 100644 (file)
--- a/src/jalview/datamodel/features/FeatureStore.java
+++ b/src/jalview/datamodel/features/FeatureStore.java
@@ -90,6 +90,10 @@ public class FeatureStore
 
   float nonPositionalMaxScore;
 
+  private SequenceFeature[] temp = new SequenceFeature[3];
+
+  private boolean isTainted;
+
   /**
    * Constructor
    */
@@ -250,6 +254,7 @@ public class FeatureStore
       features = new IntervalStore<>();
     }
     features.add(feature);
+    isTainted = true;
   }
 
   /**
@@ -602,7 +607,7 @@ public class FeatureStore
     positionalMaxScore = Float.NaN;
     nonPositionalMinScore = Float.NaN;
     nonPositionalMaxScore = Float.NaN;
-
+    isTainted = true;
     /*
      * scan non-positional features for groups and scores
      */
@@ -851,4 +856,107 @@ public class FeatureStore
     }
     return modified;
   }
+
+  /**
+   * Find all features containing this position.
+   * Uses isTainted field to know when to reconstruct its temporary array.
+   * 
+   * @param pos
+   * @return list of SequenceFeatures
+   * @author Bob Hanson 2019.07.30
+   */
+  public void findOverlappingFeatures(int pos, List<SequenceFeature> result)
+  {
+
+    if (contactFeatureStarts != null)
+    {
+      findContacts(contactFeatureStarts, pos, result, true);
+      findContacts(contactFeatureEnds, pos, result, false);
+    }
+    if (features != null)
+    {
+      int n = features.size();
+      if (isTainted)
+      {
+        isTainted = false;
+        if (temp.length < n)
+        {
+          temp = new SequenceFeature[n << 1];
+        }
+        features.toArray(temp);
+      }
+      findOverlaps(temp, n, pos, result);
+    }
+  }
+
+  /**
+   * Binary search for contact start or end at a given (Overview) position.
+   * 
+   * @param l
+   * @param pos
+   * @param result
+   * @param isStart
+   * 
+   * @author Bob Hanson 2019.07.30
+   */
+  private static void findContacts(List<SequenceFeature> l, int pos,
+          List<SequenceFeature> result, boolean isStart)
+  {
+    int low = 0;
+    int high = l.size() - 1;
+    while (low <= high)
+    {
+      int mid = (low + high) >>> 1;
+      SequenceFeature f = l.get(mid);
+      switch (Long.signum((isStart ? f.begin : f.end) - pos))
+      {
+      case -1:
+        low = mid + 1;
+        continue;
+      case 1:
+        high = mid - 1;
+        continue;
+      case 0:
+        int m = mid;
+        result.add(f);
+        // could be "5" in 12345556788 ?
+        while (++mid <= high && (f = l.get(mid)) != null
+                && (isStart ? f.begin : f.end) == pos)
+        {
+          result.add(f);
+        }
+        while (--m >= low && (f = l.get(m)) != null
+                && (isStart ? f.begin : f.end) == pos)
+        {
+          result.add(f);
+        }
+        return;
+      }
+    }
+  }
+
+  /**
+   * Brute force point-interval overlap test
+   * 
+   * @param features
+   * @param n
+   * @param pos
+   * @param result
+   */
+  private static void findOverlaps(SequenceFeature[] features, int n,
+          int pos,
+          List<SequenceFeature> result)
+  {
+    // BH I know, brute force. We need a single-position overlap
+    // method for IntervalStore, I think.
+    for (int i = n; --i >= 0;)
+    {
+      SequenceFeature f = features[i];
+      if (f.begin <= pos && f.end >= pos)
+      {
+        result.add(f);
+      }
+    }
+  }
+
 }