X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=unused%2Fnonc%2FIntervalStore.java;fp=unused%2Fnonc%2FIntervalStore.java;h=4e308b5bbea3b1306010aa081fa34f52251013be;hb=0031ee4b6a42ad328e417cb65c7a840183e62e87;hp=0000000000000000000000000000000000000000;hpb=e6b6f08502b7a31b22ae18e31c4ada1dba58be54;p=jalview.git

diff --git a/unused/nonc/IntervalStore.java b/unused/nonc/IntervalStore.java
new file mode 100644
index 0000000..4e308b5
--- /dev/null
+++ b/unused/nonc/IntervalStore.java
@@ -0,0 +1,540 @@
+/*
+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.nonc;
+
+import java.util.AbstractCollection;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+
+import intervalstore.api.IntervalI;
+
+/**
+ * A collection class to store interval-associated data, with O(log N)
+ * performance for overlap queries, insertion and deletion (where N is the size
+ * of the store). Accepts duplicate entries but not null values.
+ * 
+ * @author gmcarstairs
+ *
+ * @param <T>
+ *          any type providing <code>getBegin()</code> and <code>getEnd()</code>
+ */
+public class IntervalStore<T extends IntervalI>
+        extends AbstractCollection<T>
+        implements intervalstore.api.IntervalStoreI<T>
+{
+  private List<T> intervals;
+
+  private boolean isTainted;
+
+  private IntervalI[] orderedIntervalStarts;
+
+  /**
+   * Constructor
+   */
+  public IntervalStore()
+  {
+    intervals = new ArrayList<>();
+  }
+
+  class IntervalComparator implements Comparator<T>
+  {
+
+    @Override
+    public int compare(IntervalI o1, IntervalI 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;
+
+    }
+
+  };
+  
+  /**
+   * Constructor given a list of intervals. Note that the list may get sorted as
+   * a side-effect of calling this constructor.
+   */
+  public IntervalStore(List<T> intervals)
+  {
+    Collections.sort(this.intervals = intervals,
+              new IntervalComparator());
+      isTainted = true;
+    findOverlaps(0, -1); // ensure this is ordered
+  }
+
+  /**
+   * Adds one interval to the store.
+   * 
+   * @param interval
+   */
+  @Override
+  public boolean add(T interval)
+  {
+    if (interval == null)
+    {
+      return false;
+    }
+
+    synchronized (intervals)
+    {
+      int insertPosition = findFirstBegin(intervals, interval.getBegin());
+      intervals.add(insertPosition, interval);
+      isTainted = true;
+      return true;
+    }
+  }
+
+  @Override
+  public void clear()
+  {
+    intervals.clear();
+    orderedIntervalStarts = null;
+    isTainted = true;
+  }
+
+  @Override
+  public boolean contains(Object entry)
+  {
+    return listContains(intervals, entry);
+  }
+
+  protected int findFirstBegin(List<T> list, long pos)
+  {
+    int start = 0;
+    int end = list.size() - 1;
+    int matched = list.size();
+
+    while (start <= end)
+    {
+      int mid = (start + end) / 2;
+      if (list.get(mid).getBegin() >= pos)
+      {
+        matched = mid;
+        end = mid - 1;
+      }
+      else
+      {
+        start = mid + 1;
+      }
+    }
+    return matched;
+  }
+
+  protected int findFirstEnd(List<T> list, long pos)
+  {
+    int start = 0;
+    int end = list.size() - 1;
+    int matched = list.size();
+
+    while (start <= end)
+    {
+      int mid = (start + end) / 2;
+      if (list.get(mid).getEnd() >= pos)
+      {
+        matched = mid;
+        end = mid - 1;
+      }
+      else
+      {
+        start = mid + 1;
+      }
+    }
+    return matched;
+  }
+
+  /**
+   * Adds non-nested intervals to the result list that lie within the target
+   * range
+   * 
+   * @param from
+   * @param to
+   * @param result
+   */
+  protected void findIntervalOverlaps(long from, long to,
+          List<T> result)
+  {
+
+    int startIndex = findFirstEnd(intervals, from);
+    final int startIndex1 = startIndex;
+    int i = startIndex1;
+    while (i < intervals.size())
+    {
+      T sf = intervals.get(i);
+      if (sf.getBegin() > to)
+      {
+        break;
+      }
+      if (sf.getBegin() <= to && sf.getEnd() >= from)
+      {
+        result.add(sf);
+      }
+      i++;
+    }
+  }
+
+  @Override
+  public List<T> findOverlaps(long start, long end)
+  {
+
+    List<T> result = new ArrayList<>();
+
+    int n = intervals.size();
+    switch (n)
+    {
+    case 0:
+      return result;
+    case 1:
+      justCheckOne(intervals.get(0), start, end, result);
+      return result;
+    default:
+
+      if (isTainted)
+      {
+        orderedIntervalStarts = intervals.toArray(new IntervalI[0]);
+        linkFeatures(orderedIntervalStarts);
+        isTainted = false;
+      }
+      break;
+    }
+
+    if (end < start)
+    {
+      // just ensuring not tainted -- fully loaded
+      return result;
+    }
+
+    // (1) Find the closest feature to this position.
+
+    int index = getClosestFeature(orderedIntervalStarts, start);
+    IntervalI sf = (index < 0 ? null : orderedIntervalStarts[index]);
+
+    // (2) Traverse the containedBy field, checking for overlap.
+
+    while (sf != null)
+    {
+      if (sf.getEnd() >= start)
+      {
+        result.add((T) sf);
+      }
+      sf = sf.getContainedBy();
+    }
+
+    // (3) For an interval, find the last feature that starts in this interval,
+    // and add all features up through that feature.
+
+    if (end >= start)
+    {
+      // fill in with all features that start within this interval, fully
+      // inclusive
+      int index2 = getClosestFeature(orderedIntervalStarts, end);
+      while (++index <= index2)
+      {
+        result.add((T) orderedIntervalStarts[index]);
+      }
+
+    }
+    return result;
+  }
+
+  private int getClosestFeature(IntervalI[] l, long pos)
+  {
+    int low = 0;
+    int high = l.length - 1;
+    while (low <= high)
+    {
+      int mid = (low + high) >>> 1;
+      IntervalI f = l[mid];
+      switch (Long.signum(f.getBegin() - pos))
+      {
+      case -1:
+        low = mid + 1;
+        continue;
+      case 1:
+        high = mid - 1;
+        continue;
+      case 0:
+
+        while (++mid <= high && l[mid].getBegin() == pos)
+        {
+          ;
+        }
+        return --mid;
+      }
+    }
+    return (high < 0 ? -1 : high);
+  }
+
+  @SuppressWarnings("unchecked")
+  public T getContainedBy(T sf, T sf0)
+  {
+    int begin = sf0.getBegin();
+    while (sf != null)
+    {
+      if (begin <= sf.getEnd())
+      {
+        // System.out.println("\nIS found " + sf0.getIndex1() + ":" + sf0
+        // + "\nFS in " + sf.getIndex1() + ":" + sf);
+        return sf;
+      }
+      sf = (T) sf.getContainedBy();
+    }
+    return null;
+  }
+
+  @Override
+  public int getDepth()
+  {
+    if (size() == 0)
+    {
+      return 0;
+    }
+    int maxDepth = 0;
+    for (int i = intervals.size(); --i >= 0;)
+    {
+      T element = intervals.get(i);
+      T container = element;
+      int depth = 0;
+      while ((container = (T) container.getContainedBy()) != null)
+      {
+        if (++depth > maxDepth && container == this)
+        {
+          maxDepth = depth;
+          break;
+        }
+      }
+    }
+    return maxDepth;
+  }
+
+  @Override
+  public boolean isValid()
+  {
+    for (int i = 0; i < intervals.size() - 1; i++)
+    {
+      T i1 = intervals.get(i);
+      T i2 = intervals.get(i + 1);
+
+      if (i2.getBegin() < i1.getBegin())
+      {
+        System.err.println("nonNested wrong start order : " + i1.toString()
+                + ", " + i2.toString());
+        return false;
+      }
+    }
+    return true;
+  }
+
+  /**
+   * Answers an iterator over the intervals in the store, with no particular
+   * ordering guaranteed. The iterator does not support the optional
+   * <code>remove</code> operation (throws
+   * <code>UnsupportedOperationException</code> if attempted).
+   */
+  @Override
+  public Iterator<T> iterator()
+  {
+    return intervals.iterator();
+
+  }
+
+  private void justCheckOne(T sf, long start, long end, List<T> result)
+  {
+    if (sf.getBegin() <= end && sf.getEnd() >= start)
+    {
+      result.add(sf);
+    }
+    return;
+  }
+
+  private void linkFeatures(IntervalI[] features)
+  {
+    int n = features.length;
+    switch (n)
+    {
+    case 0:
+      return;
+    case 1:
+      features[0].setIndex1(1);
+      return;
+    }
+    int maxEnd = features[0].getEnd();
+    for (int i = 1; i < n;)
+    {
+      T sf = (T) features[i];
+      sf.setIndex1(++i);
+      if (sf.getBegin() <= maxEnd)
+      {
+        sf.setContainedBy(getContainedBy((T) features[i - 2], sf));
+      }
+      if (sf.getEnd() > maxEnd)
+      {
+        maxEnd = sf.getEnd();
+      }
+    }
+
+  }
+
+  /**
+   * Answers true if the list contains the interval, else false. This method is
+   * optimised for the condition that the list is sorted on interval start
+   * position ascending, and will give unreliable results if this does not hold.
+   * 
+   * @param intervals
+   * @param entry
+   * @return
+   */
+  protected boolean listContains(List<T> intervals, Object entry)
+  {
+    if (intervals == null || entry == null)
+    {
+      return false;
+    }
+
+    T interval = (T) entry;
+
+    /*
+     * locate the first entry in the list which does not precede the interval
+     */
+    int pos = findFirstBegin(intervals, interval.getBegin());
+    int len = intervals.size();
+    while (pos < len)
+    {
+      T sf = intervals.get(pos);
+      if (sf.getBegin() > interval.getBegin())
+      {
+        return false; // no match found
+      }
+      if (sf.getEnd() == interval.getEnd() && sf.equals(interval))
+      {
+        return true;
+      }
+      pos++;
+    }
+    return false;
+  }
+
+  @Override
+  public String prettyPrint()
+  {
+    return toString();
+  }
+
+  @Override
+  public synchronized boolean remove(Object o)
+  {
+    if (o == null || !(o instanceof IntervalI))
+    {
+      return false;
+    }
+
+    T entry = (T) o;
+
+    /*
+     * try the non-nested positional intervals first
+     */
+    boolean removed = removeInterval(entry);
+    if (removed)
+    {
+      isTainted = true;
+    }
+
+    return removed;
+
+  }
+
+  /**
+   * Removes the given entry from the list of non-nested entries, returning true
+   * if found and removed, or false if not found. Specifically, removes the
+   * first item in the list for which <code>item.equals(entry)</code>.
+   * 
+   * @param entry
+   * @return
+   */
+  protected boolean removeInterval(T entry)
+  {
+    /*
+     * find the first interval that might match, i.e. whose 
+     * start position is not less than the target range start
+     * (NB inequality test ensures the first match if any is found)
+     */
+    int startIndex = findFirstBegin(intervals, entry.getBegin());
+
+    /*
+     * traverse intervals to look for a match
+     */
+    int from = entry.getBegin();
+    int i = startIndex;
+    int size = intervals.size();
+    while (i < size)
+    {
+      T sf = intervals.get(i);
+      if (sf.getBegin() > from)
+      {
+        break;
+      }
+      if (sf.equals(entry))
+      {
+        intervals.remove(i);
+        return true;
+      }
+      i++;
+    }
+    return false;
+  }
+
+  @Override
+  public int size()
+  {
+    return intervals.size();
+  }
+
+  @Override
+  public String toString()
+  {
+    ensureFinalized();
+    StringBuffer sb = new StringBuffer();
+
+    return sb.toString();
+  }
+
+}