JAL-3210 updated IntervalStoreJ classes in srcjar

[jalview.git] / srcjar / intervalstore / impl / BinarySearcher.java

diff --git a/srcjar/intervalstore/impl/BinarySearcher.java b/srcjar/intervalstore/impl/BinarySearcher.java
index 1086e91..22990f6 100644 (file)
--- a/srcjar/intervalstore/impl/BinarySearcher.java
+++ b/srcjar/intervalstore/impl/BinarySearcher.java
@@ -32,16 +32,26 @@ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 package intervalstore.impl;
 
 import java.util.List;
-import java.util.function.Function;
+
+import intervalstore.api.IntervalI;
 
 /**
- * Provides a method to perform binary search of an ordered list for the first
- * entry that satisfies a supplied condition
+ * Provides a method to perform binary search of an ordered list of
+ * {@code IntervalI} objects for the first entry that satisfies a supplied
+ * condition on either the begin or end value of the intervals
  * 
  * @author gmcarstairs
  */
 public final class BinarySearcher
 {
+  /*
+   * compare using <, <=, =, >=, >
+   */
+  public enum Compare
+  {
+    LT, LE, EQ, GE, GT
+  }
+
   private BinarySearcher()
   {
   }
@@ -59,23 +69,44 @@ public final class BinarySearcher
    * <code>Collections.binarySearch</code> instead.
    * 
    * @param list
+   *          the list to be searched
+   * @param compareValue
+   *          a function that extracts the value to be compared from an entry
+   * @param compareTo
+   *          the value to compare to
    * @param test
+   *          a function that compares (compareValue, compareTo) and returns
+   *          true or false
    * @return
    * @see java.util.Collections#binarySearch(List, Object)
    */
-  public static <T> int findFirst(List<? extends T> list,
-          Function<T, Boolean> test)
+  public static int findFirst(List<? extends IntervalI> list,
+          boolean compareBegin,
+          Compare comp, int compareto)
   {
     int start = 0;
-    int end = list.size() - 1;
     int matched = list.size();
+    int end = matched - 1;
   
+    /*
+     * shortcut for the case that the last entry in the list
+     * fails the test (this arises when adding non-overlapping
+     * intervals in ascending start position order) 
+     */
+    if (end > 0)
+    {
+      IntervalI last = list.get(end);
+      if (!compare(last, compareBegin, comp, compareto))
+      {
+        return matched;
+      }
+    }
+
     while (start <= end)
     {
       int mid = (start + end) / 2;
-      T entry = list.get(mid);
-      boolean itsTrue = test.apply(entry);
-      if (itsTrue)
+      IntervalI entry = list.get(mid);
+      if (compare(entry, compareBegin, comp, compareto))
       {
         matched = mid;
         end = mid - 1;
@@ -88,4 +119,42 @@ public final class BinarySearcher
   
     return matched;
   }
+
+  /**
+   * Applies the comparison specified by {@code comp} to either the
+   * {@code begin} value of {@code entry} (if {@code compareBegin} is true) or
+   * the {@code end} value, and the {@code compareTo} value, and returns the
+   * result of the comparison
+   * 
+   * @param entry
+   * @param compareBegin
+   * @param comp
+   * @param compareTo
+   * @return
+   */
+  private static boolean compare(IntervalI entry, boolean compareBegin,
+          Compare comp, int compareTo)
+  {
+    int val = compareBegin ? entry.getBegin() : entry.getEnd();
+    boolean result;
+    switch (comp)
+    {
+    case LT:
+      result = val < compareTo;
+      break;
+    case LE:
+      result = val <= compareTo;
+      break;
+    case EQ:
+      result = val == compareTo;
+      break;
+    case GE:
+      result = val >= compareTo;
+      break;
+    case GT:
+    default:
+      result = val > compareTo;
+    }
+    return result;
+  }
 }