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

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

diff --git a/src/jalview/datamodel/features/NCList.java b/src/jalview/datamodel/features/NCList.java
index 9906884..a911666 100644 (file)
--- a/src/jalview/datamodel/features/NCList.java
+++ b/src/jalview/datamodel/features/NCList.java
@@ -2,7 +2,6 @@ package jalview.datamodel.features;
 
 import java.util.ArrayList;
 import java.util.Collections;
-import java.util.Comparator;
 import java.util.List;
 
 /**
@@ -28,12 +27,6 @@ public class NCList<T extends ContiguousI>
    */
   private List<NCNode<T>> subranges;
 
-  /*
-   * a comparator to sort intervals by start position ascending, with
-   * longer (enclosing) intervals preceding those they enclose 
-   */
-  Comparator<ContiguousI> intervalSorter = new RangeComparator(true);
-
   /**
    * Constructor given a list of things that are each located on a contiguous
    * interval. Note that the constructor may reorder the list.
@@ -50,6 +43,9 @@ public class NCList<T extends ContiguousI>
   }
 
   /**
+   * Sort and group ranges into sublists where each sublist represents a region
+   * and its contained subregions
+   * 
    * @param ranges
    */
   protected void build(List<T> ranges)
@@ -58,18 +54,18 @@ public class NCList<T extends ContiguousI>
      * sort by start ascending so that contained intervals 
      * follow their containing interval
      */
-    Collections.sort(ranges, intervalSorter);
+    Collections.sort(ranges, RangeComparator.BY_START_POSITION);
 
-    List<SubList> sublists = buildSubranges(ranges);
+    List<Range> sublists = buildSubranges(ranges);
 
     /*
      * convert each subrange to an NCNode consisting of a range and
      * (possibly) its contained NCList
      */
-    for (SubList sublist : sublists)
+    for (Range sublist : sublists)
     {
-      subranges.add(new NCNode<T>(ranges.subList(sublist.startIndex,
-              sublist.endIndex + 1)));
+      subranges.add(new NCNode<T>(ranges.subList(sublist.start,
+              sublist.end + 1)));
     }
 
     size = ranges.size();
@@ -78,9 +74,8 @@ public class NCList<T extends ContiguousI>
   public NCList(T entry)
   {
     this();
-    List<T> ranges = new ArrayList<T>();
-    ranges.add(entry);
-    build(ranges);
+    subranges.add(new NCNode<T>(entry));
+    size = 1;
   }
 
   public NCList()
@@ -95,9 +90,9 @@ public class NCList<T extends ContiguousI>
    * @param ranges
    * @return
    */
-  protected List<SubList> buildSubranges(List<T> ranges)
+  protected List<Range> buildSubranges(List<T> ranges)
   {
-    List<SubList> sublists = new ArrayList<SubList>();
+    List<Range> sublists = new ArrayList<Range>();
     
     if (ranges.isEmpty())
     {
@@ -118,13 +113,13 @@ public class NCList<T extends ContiguousI>
          * this interval is not contained in the preceding one 
          * close off the last sublist
          */
-        sublists.add(new SubList(listStartIndex, i - 1));
+        sublists.add(new Range(listStartIndex, i - 1));
         listStartIndex = i;
       }
       lastEndPos = nextEnd;
     }
 
-    sublists.add(new SubList(listStartIndex, ranges.size() - 1));
+    sublists.add(new Range(listStartIndex, ranges.size() - 1));
     return sublists;
   }
 
@@ -326,7 +321,7 @@ public class NCList<T extends ContiguousI>
           final int j)
   {
     NCList<T> newNCList = new NCList<T>();
-    newNCList.subranges.addAll(subranges.subList(i, j + 1));
+    newNCList.addNodes(subranges.subList(i, j + 1));
     NCNode<T> newNode = new NCNode<T>(entry, newNCList);
     for (int k = j; k >= i; k--)
     {
@@ -335,6 +330,15 @@ public class NCList<T extends ContiguousI>
     subranges.add(i, newNode);
   }
 
+  protected void addNodes(List<NCNode<T>> nodes)
+  {
+    for (NCNode<T> node : nodes)
+    {
+      subranges.add(node);
+      size += node.size();
+    }
+  }
+
   /**
    * Returns a (possibly empty) list of items whose extent overlaps the given
    * range
@@ -401,8 +405,12 @@ public class NCList<T extends ContiguousI>
    */
   protected int findFirstOverlap(long from)
   {
-    // TODO binary search
-    // for now quick cheat linear search
+    /*
+     * The NCList paper describes binary search for this step,
+     * but this not implemented here as (a) I haven't understood it yet
+     * and (b) it seems to imply complications for adding to an NCList
+     */
+
     int i = 0;
     if (subranges != null)
     {
@@ -531,7 +539,7 @@ public class NCList<T extends ContiguousI>
    * 
    * @return
    */
-  public int getSize()
+  public int size()
   {
     return size;
   }
@@ -594,8 +602,8 @@ public class NCList<T extends ContiguousI>
         subranges.remove(i);
         if (subRegions != null)
         {
-          subranges.addAll(i, subRegions.subranges);
-          Collections.sort(subranges, intervalSorter);
+          subranges.addAll(subRegions.subranges);
+          Collections.sort(subranges, RangeComparator.BY_START_POSITION);
         }
         size--;
         return true;
@@ -605,6 +613,7 @@ public class NCList<T extends ContiguousI>
         if (subRegions != null && subRegions.delete(entry))
         {
           size--;
+          subrange.deleteSubRegionsIfEmpty();
           return true;
         }
       }