JAL-3397 final update

[jalview.git] / src / intervalstore / impl / NCList.java

diff --git a/src/intervalstore/impl/NCList.java b/src/intervalstore/impl/NCList.java
index 0bf6e1b..243192d 100644 (file)
--- a/src/intervalstore/impl/NCList.java
+++ b/src/intervalstore/impl/NCList.java
@@ -39,7 +39,6 @@ import java.util.List;
 import java.util.NoSuchElementException;
 
 import intervalstore.api.IntervalI;
-import intervalstore.impl.Range;
 
 /**
  * An adapted implementation of NCList as described in the paper
@@ -53,6 +52,9 @@ import intervalstore.impl.Range;
  */
 public class NCList<T extends IntervalI> extends AbstractCollection<T>
 {
+
+  // private static final boolean OPTION_FIND_ANY = false;
+
   /**
    * A depth-first iterator over the elements stored in the NCList
    */
@@ -200,7 +202,7 @@ public class NCList<T extends IntervalI> extends AbstractCollection<T>
      * sort by start ascending, length descending, so that
      * contained intervals follow their containing interval
      */
-    Collections.sort(ranges, new NCListBuilder<>().getComparator());
+    Collections.sort(ranges, IntervalI.COMPARATOR_BIGENDIAN);
 
     int listStartIndex = 0;
 
@@ -455,8 +457,13 @@ public class NCList<T extends IntervalI> extends AbstractCollection<T>
    * @param to
    * @param result
    */
-  protected void findOverlaps(long from, long to, List<T> result)
+  protected List<T> findOverlaps(long from, long to, List<T> result)
   {
+
+    // if (OPTION_FIND_ANY)
+    // {
+    // return findAnyOverlaps(from, to, result);
+    // }
     /*
      * find the first sublist that might overlap, i.e. 
      * the first whose end position is >= from
@@ -475,8 +482,74 @@ public class NCList<T extends IntervalI> extends AbstractCollection<T>
       }
       candidate.findOverlaps(from, to, result);
     }
-
+    return result;
   }
+  
+  // /**
+  // * Recursively searches the NCList adding any items that overlap the from-to
+  // * range to the result list
+  // *
+  // * @param from
+  // * @param to
+  // * @param result
+  // */
+  // protected List<T> findAnyOverlaps(long from, long to, List<T> result)
+  // {
+  //
+  // // BH find ANY overlap
+  //
+  // int candidateIndex = findAnyOverlap(subranges, from, to);
+  //
+  // if (candidateIndex < 0)
+  // return result;
+  // for (int i = candidateIndex, n = subranges.size(); i < n; i++)
+  // {
+  // NCNode<T> candidate = subranges.get(i);
+  // if (candidate.getBegin() > to)
+  // {
+  // /*
+  // * we are past the end of our target range
+  // */
+  // break;
+  // }
+  // candidate.findOverlaps(from, to, result);
+  // }
+  //
+  // // BH adds dual-direction check
+  //
+  // for (int i = candidateIndex; --i >= 0;)
+  // {
+  // NCNode<T> candidate = subranges.get(i);
+  // if (candidate.getEnd() < from)
+  // {
+  // break;
+  // }
+  // candidate.findOverlaps(from, to, result);
+  // }
+  // return result;
+  // }
+  //
+  // private int findAnyOverlap(List<NCNode<T>> ranges, long from, long to)
+  // {
+  // int start = 0;
+  // int end = ranges.size() - 1;
+  // while (start <= end)
+  // {
+  // int mid = (start + end) >>> 1;
+  // NCNode<T> r = ranges.get(mid);
+  // if (r.getEnd() >= from)
+  // {
+  // if (r.getBegin() <= to)
+  // return mid;
+  // end = mid - 1;
+  // }
+  // else
+  // {
+  // start = mid + 1;
+  // }
+  // }
+  // return -1;
+  // }
 
   /**
    * Search subranges for the first one whose end position is not before the
@@ -489,8 +562,8 @@ public class NCList<T extends IntervalI> extends AbstractCollection<T>
    */
   protected int findFirstOverlap(final long from)
   {
-    return BinarySearcher.findFirst(subranges,
-            val -> val.getEnd() >= from);
+    return BinarySearcher.findFirst(subranges, (int) from,
+            BinarySearcher.fend);
   }
 
   /**
@@ -517,7 +590,7 @@ public class NCList<T extends IntervalI> extends AbstractCollection<T>
     int offset = 0;
     int indent = 2;
     prettyPrint(sb, offset, indent);
-    sb.append(System.lineSeparator());
+    sb.append('\n');// System.lineSeparator());
     return sb.toString();
   }
 
@@ -533,7 +606,7 @@ public class NCList<T extends IntervalI> extends AbstractCollection<T>
     {
       if (!first)
       {
-        sb.append(System.lineSeparator());
+        sb.append('\n');// System.lineSeparator());
       }
       first = false;
       subrange.prettyPrint(sb, offset, indent);
@@ -749,4 +822,9 @@ public class NCList<T extends IntervalI> extends AbstractCollection<T>
     subranges.clear();
     size = 0;
   }
+
+  public int getWidth()
+  {
+    return subranges.size();
+  }
 }