From 33a853ff07bf9fbdace2744c6c38e28786147e53 Mon Sep 17 00:00:00 2001
From: hansonr <hansonr@STO24954W.ad.stolaf.edu>
Date: Wed, 7 Aug 2019 19:33:02 -0500
Subject: [PATCH] JAL-3383 JAL-3253-applet shortcut binary search when
 position is out of range.

---
 src/jalview/datamodel/features/FeatureStore.java   |   22 +++++++++++--
 src/jalview/datamodel/features/FeatureStoreJS.java |   33 ++++++++++++++++++--
 2 files changed, 49 insertions(+), 6 deletions(-)

diff --git a/src/jalview/datamodel/features/FeatureStore.java b/src/jalview/datamodel/features/FeatureStore.java
index 8db35a3..d832f4d 100644
--- a/src/jalview/datamodel/features/FeatureStore.java
+++ b/src/jalview/datamodel/features/FeatureStore.java
@@ -33,6 +33,11 @@ public abstract class FeatureStore implements FeatureStoreI
 {
 
   /**
+   * track last start for quick insertion of ordered features
+   */
+  protected int lastStart = -1, lastContactStart = -1;
+
+  /**
    * Answers the 'length' of the feature, counting 0 for non-positional features
    * and 1 for contact features
    * 
@@ -87,12 +92,13 @@ public abstract class FeatureStore implements FeatureStoreI
     /*
      * locate the first entry in the list which does not precede the feature
      */
-    int pos = findFirstBegin(list, feature.begin);
+    int begin = feature.begin;
+    int pos = findFirstBegin(list, begin);
     int len = list.size();
     while (pos < len)
     {
       SequenceFeature sf = list.get(pos);
-      if (sf.begin > feature.begin)
+      if (sf.begin > begin)
       {
         return -1; // no match found
       }
@@ -268,6 +274,10 @@ public abstract class FeatureStore implements FeatureStoreI
 
     if (feature.isContactFeature())
     {
+      if (feature.begin > lastContactStart)
+      {
+        lastContactStart = feature.begin;
+      }
       addContactFeature(feature);
     }
     else if (feature.isNonPositional())
@@ -277,6 +287,10 @@ public abstract class FeatureStore implements FeatureStoreI
     else
     {
       addPositionalFeature(feature);
+      if (feature.begin > lastStart)
+      {
+        lastStart = feature.begin;
+      }
     }
 
     /*
@@ -374,10 +388,12 @@ public abstract class FeatureStore implements FeatureStoreI
     if (feature.isContactFeature())
     {
       return contactFeatureStarts != null
+              && feature.begin <= lastContactStart
               && listContains(contactFeatureStarts, feature);
     }
 
-    return features == null ? false : containsFeature(feature);
+    return features == null || feature.begin > lastStart ? false
+            : containsFeature(feature);
   }
 
 
diff --git a/src/jalview/datamodel/features/FeatureStoreJS.java b/src/jalview/datamodel/features/FeatureStoreJS.java
index b119aef..37f81a0 100644
--- a/src/jalview/datamodel/features/FeatureStoreJS.java
+++ b/src/jalview/datamodel/features/FeatureStoreJS.java
@@ -37,6 +37,7 @@ public class FeatureStoreJS extends FeatureStore
 {
   boolean contactsTainted = true;
 
+
   /**
    * internal reference to features as an ArrayList
    */
@@ -154,12 +155,33 @@ public class FeatureStoreJS extends FeatureStore
     getContactEndOverlaps(from, to, result);
   }
 
+  /**
+   * Locate the first feature start that is at or after this position.
+   * 
+   */
+
+  static int ntotal = 0, ncaught = 0;
+
   @Override
   protected int findFirstBegin(List<SequenceFeature> list, long pos)
   {
-    int start = 0;
-    int end = list.size() - 1;
     int matched = list.size();
+    int end = matched - 1;
+    int start = (end < 0 || list.get(end).begin < pos ? matched : 0);
+    // if (end < 0)
+    // {
+    //
+    // }
+    // else if (start > end)
+    // {
+    // ncaught++;
+    // }
+    // ntotal++;
+    //
+    // System.out.println(
+    // "FSJS " + ncaught + "/" + ntotal + " " + pos + "/"
+    // + (end < 0 ? -1 : list.get(end).begin) + " "
+    // + start + "/" + matched);
 
     while (start <= end)
     {
@@ -177,6 +199,11 @@ public class FeatureStoreJS extends FeatureStore
     return matched;
   }
 
+  /**
+   * Locate the feature start that is after or at this position.
+   * 
+   */
+
   @Override
   protected int findFirstEnd(List<SequenceFeature> list, long pos)
   {
@@ -407,7 +434,7 @@ public class FeatureStoreJS extends FeatureStore
     {
       if (begin <= sf.end)
       {
-        System.out.println("\nFS found " + sf0 + "\nFS in " + sf);
+        // System.out.println("\nFSJS found " + sf0 + "\nFS in " + sf);
         return sf;
       }
       sf = sf.containedBy;
-- 
1.7.10.2