JAL-3263, JAL 3264 New Transpiler fixes FunctionalInterface issues,

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

diff --git a/srcjar/intervalstore/impl/NCListBuilder.java b/srcjar/intervalstore/impl/NCListBuilder.java
new file mode 100644 (file)
index 0000000..7d0b013
--- /dev/null
+++ b/srcjar/intervalstore/impl/NCListBuilder.java
@@ -0,0 +1,142 @@
+/*
+BSD 3-Clause License
+
+Copyright (c) 2018, Mungo Carstairs
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+* Redistributions of source code must retain the above copyright notice, this
+  list of conditions and the following disclaimer.
+
+* Redistributions in binary form must reproduce the above copyright notice,
+  this list of conditions and the following disclaimer in the documentation
+  and/or other materials provided with the distribution.
+
+* Neither the name of the copyright holder nor the names of its
+  contributors may be used to endorse or promote products derived from
+  this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+package intervalstore.impl;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.List;
+
+import intervalstore.api.IntervalI;
+
+/**
+ * A comparator that orders ranges by either start position ascending. If
+ * position matches, ordering is by length descending. This provides the
+ * canonical ordering of intervals into subranges in order to build a nested
+ * containment list.
+ * 
+ * @author gmcarstairs
+ */
+public class NCListBuilder<T extends IntervalI>
+{
+  class NCListComparator<V extends IntervalI> implements Comparator<V>
+  {
+    /**
+     * Compares two intervals in a way that will sort a list by start position
+     * ascending, then by length descending. Answers
+     * <ul>
+     * <li>a negative value if o1.begin < o2.begin</li>
+     * <li>else a positive value if o1.begin > o2.begin</li>
+     * <li>else a negative value if o1.end > o2.end</li>
+     * <li>else a positive value of o1.end < o2.end</li>
+     * <li>else zero</li
+     * </ul>
+     */
+    @Override
+    public int compare(V o1, V o2)
+    {
+      int order = Integer.compare(o1.getBegin(), o2.getBegin());
+      if (order == 0)
+      {
+        /*
+         * if tied on start position, longer length sorts to left
+         * i.e. the negation of normal ordering by length
+         */
+        order = Integer.compare(o2.getEnd(), o1.getEnd());
+      }
+      return order;
+    }
+  }
+
+  private Comparator<T> comparator = new NCListComparator<>();
+  
+  /**
+   * Default constructor
+   */
+  public NCListBuilder()
+  {
+  }
+
+  /**
+   * Answers a comparator which sorts items of type T by start position
+   * ascending, and within that by end position (length) descending)
+   * 
+   * @return
+   */
+  Comparator<T> getComparator()
+  {
+    return comparator;
+  }
+
+  /**
+   * Sorts and traverses the ranges to identify sublists, whose start intervals
+   * are overlapping or disjoint but not mutually contained. Answers a list of
+   * start-end indices of the sorted list of ranges.
+   * 
+   * @param ranges
+   * @return
+   */
+  List<IntervalI> partitionNestedSublists(List<T> ranges)
+  {
+    List<IntervalI> sublists = new ArrayList<>();
+  
+    /*
+     * sort by start ascending, length descending, so that
+     * contained intervals follow their containing interval
+     */
+    Collections.sort(ranges, comparator);
+  
+    int listStartIndex = 0;
+  
+    IntervalI lastParent = ranges.get(0);
+    boolean first = true;
+  
+    for (int i = 0; i < ranges.size(); i++)
+    {
+      IntervalI nextInterval = ranges.get(i);
+      if (!first && !lastParent.properlyContainsInterval(nextInterval))
+      {
+        /*
+         * this interval is not properly contained in the parent; 
+         * close off the last sublist
+         */
+        sublists.add(new Range(listStartIndex, i - 1));
+        listStartIndex = i;
+        lastParent = nextInterval;
+      }
+      first = false;
+    }
+  
+    sublists.add(new Range(listStartIndex, ranges.size() - 1));
+    return sublists;
+  }
+}