X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=src%2Fjalview%2Fdatamodel%2Ffeatures%2FNCList.java;h=ae58a69768184cc87f02453eac2c02c6980d3dc8;hb=bb620cae1e4c44ae9efaf975c7bbbc63b0558db3;hp=17e08eb6ac985772c4ae8157b7ab3f7cf3c2ecfa;hpb=fdea751663ec46a587cfdf45bfae9ec667043efb;p=jalview.git

diff --git a/src/jalview/datamodel/features/NCList.java b/src/jalview/datamodel/features/NCList.java
index 17e08eb..ae58a69 100644
--- a/src/jalview/datamodel/features/NCList.java
+++ b/src/jalview/datamodel/features/NCList.java
@@ -1,8 +1,30 @@
+/*
+ * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
+ * Copyright (C) $$Year-Rel$$ The Jalview Authors
+ * 
+ * This file is part of Jalview.
+ * 
+ * Jalview is free software: you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License 
+ * as published by the Free Software Foundation, either version 3
+ * of the License, or (at your option) any later version.
+ *  
+ * Jalview is distributed in the hope that it will be useful, but 
+ * WITHOUT ANY WARRANTY; without even the implied warranty 
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR 
+ * PURPOSE.  See the GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
+ * The Jalview Authors are detailed in the 'AUTHORS' file.
+ */
 package jalview.datamodel.features;
 
+import jalview.datamodel.ContiguousI;
+import jalview.datamodel.Range;
+
 import java.util.ArrayList;
 import java.util.Collections;
-import java.util.Comparator;
 import java.util.List;
 
 /**
@@ -28,12 +50,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 +66,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 +77,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 +97,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<>(entry));
+    size = 1;
   }
 
   public NCList()
@@ -95,10 +113,15 @@ 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<>();
     
+    if (ranges.isEmpty())
+    {
+      return sublists;
+    }
+
     int listStartIndex = 0;
     long lastEndPos = Long.MAX_VALUE;
 
@@ -113,13 +136,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;
   }
 
@@ -171,7 +194,7 @@ public class NCList<T extends ContiguousI>
       /*
        * all subranges precede this one - add it on the end
        */
-      subranges.add(new NCNode<T>(entry));
+      subranges.add(new NCNode<>(entry));
       return true;
     }
 
@@ -188,16 +211,16 @@ public class NCList<T extends ContiguousI>
     {
       NCNode<T> subrange = subranges.get(j);
 
-      if (end < subrange.getStart() && !overlapping && !enclosing)
+      if (end < subrange.getBegin() && !overlapping && !enclosing)
       {
         /*
          * new entry lies between subranges j-1 j
          */
-        subranges.add(j, new NCNode<T>(entry));
+        subranges.add(j, new NCNode<>(entry));
         return true;
       }
 
-      if (subrange.getStart() <= start && subrange.getEnd() >= end)
+      if (subrange.getBegin() <= start && subrange.getEnd() >= end)
       {
         /*
          * push new entry inside this subrange as it encloses it
@@ -206,7 +229,7 @@ public class NCList<T extends ContiguousI>
         return true;
       }
       
-      if (start <= subrange.getStart())
+      if (start <= subrange.getBegin())
       {
         if (end >= subrange.getEnd())
         {
@@ -241,7 +264,7 @@ public class NCList<T extends ContiguousI>
              * entry spans two subranges but doesn't enclose any
              * so just add it 
              */
-            subranges.add(j, new NCNode<T>(entry));
+            subranges.add(j, new NCNode<>(entry));
             return true;
           }
         }
@@ -262,7 +285,7 @@ public class NCList<T extends ContiguousI>
     }
     else
     {
-      subranges.add(new NCNode<T>(entry));
+      subranges.add(new NCNode<>(entry));
     }
 
     return true;
@@ -293,7 +316,7 @@ public class NCList<T extends ContiguousI>
     for (int i = candidateIndex; i < subranges.size(); i++)
     {
       NCNode<T> candidate = subranges.get(i);
-      if (candidate.getStart() > to)
+      if (candidate.getBegin() > to)
       {
         /*
          * we are past the end of our target range
@@ -320,9 +343,9 @@ public class NCList<T extends ContiguousI>
   protected synchronized void addEnclosingRange(T entry, final int i,
           final int j)
   {
-    NCList<T> newNCList = new NCList<T>();
-    newNCList.subranges.addAll(subranges.subList(i, j + 1));
-    NCNode<T> newNode = new NCNode<T>(entry, newNCList);
+    NCList<T> newNCList = new NCList<>();
+    newNCList.addNodes(subranges.subList(i, j + 1));
+    NCNode<T> newNode = new NCNode<>(entry, newNCList);
     for (int k = j; k >= i; k--)
     {
       subranges.remove(k);
@@ -330,6 +353,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
@@ -342,7 +374,7 @@ public class NCList<T extends ContiguousI>
    */
   public List<T> findOverlaps(long from, long to)
   {
-    List<T> result = new ArrayList<T>();
+    List<T> result = new ArrayList<>();
 
     findOverlaps(from, to, result);
     
@@ -373,7 +405,7 @@ public class NCList<T extends ContiguousI>
     for (int i = candidateIndex; i < subranges.size(); i++)
     {
       NCNode<T> candidate = subranges.get(i);
-      if (candidate.getStart() > to)
+      if (candidate.getBegin() > to)
       {
         /*
          * we are past the end of our target range
@@ -396,8 +428,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)
     {
@@ -427,7 +463,7 @@ public class NCList<T extends ContiguousI>
   }
 
   /**
-   * Returns a string representation of the data where containment is shown bgy
+   * Returns a string representation of the data where containment is shown by
    * indentation on new lines
    * 
    * @return
@@ -438,6 +474,7 @@ public class NCList<T extends ContiguousI>
     int offset = 0;
     int indent = 2;
     prettyPrint(sb, offset, indent);
+    sb.append(System.lineSeparator());
     return sb.toString();
   }
 
@@ -488,7 +525,7 @@ public class NCList<T extends ContiguousI>
     int lastStart = start;
     for (NCNode<T> subrange : subranges)
     {
-      if (subrange.getStart() < lastStart)
+      if (subrange.getBegin() < lastStart)
       {
         System.err.println("error in NCList: range " + subrange.toString()
                 + " starts before " + lastStart);
@@ -500,7 +537,7 @@ public class NCList<T extends ContiguousI>
                 + " ends after " + end);
         return false;
       }
-      lastStart = subrange.getStart();
+      lastStart = subrange.getBegin();
 
       if (!subrange.isValid())
       {
@@ -517,7 +554,7 @@ public class NCList<T extends ContiguousI>
    */
   public int getStart()
   {
-    return subranges.isEmpty() ? 0 : subranges.get(0).getStart();
+    return subranges.isEmpty() ? 0 : subranges.get(0).getBegin();
   }
 
   /**
@@ -525,7 +562,7 @@ public class NCList<T extends ContiguousI>
    * 
    * @return
    */
-  public int getSize()
+  public int size()
   {
     return size;
   }
@@ -537,7 +574,7 @@ public class NCList<T extends ContiguousI>
    */
   public List<T> getEntries()
   {
-    List<T> result = new ArrayList<T>();
+    List<T> result = new ArrayList<>();
     getEntries(result);
     return result;
   }
@@ -579,12 +616,17 @@ public class NCList<T extends ContiguousI>
       {
         /*
          * if the subrange is rooted on this entry, promote its
-         * subregions (if any) to replace the subrange here 
+         * subregions (if any) to replace the subrange here;
+         * NB have to resort subranges after doing this since e.g.
+         * [10-30 [12-20 [16-18], 13-19]]
+         * after deleting 12-20, 16-18 is promoted to sibling of 13-19
+         * but should follow it in the list of subranges of 10-30 
          */
         subranges.remove(i);
         if (subRegions != null)
         {
-          subranges.addAll(i, subRegions.subranges);
+          subranges.addAll(subRegions.subranges);
+          Collections.sort(subranges, RangeComparator.BY_START_POSITION);
         }
         size--;
         return true;
@@ -594,30 +636,11 @@ public class NCList<T extends ContiguousI>
         if (subRegions != null && subRegions.delete(entry))
         {
           size--;
+          subrange.deleteSubRegionsIfEmpty();
           return true;
         }
       }
     }
     return false;
   }
-
-  /**
-   * Answers true if this contains no ranges
-   * 
-   * @return
-   */
-  public boolean isEmpty()
-  {
-    return getSize() == 0;
-  }
-
-  /**
-   * Answer the list of subranges held in this NCList
-   * 
-   * @return
-   */
-  List<NCNode<T>> getSubregions()
-  {
-    return subranges;
-  }
 }