--- /dev/null
+/*
+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;
+import intervalstore.api.IntervalStoreI;
+
+
+/**
+ *
+ * A Collection class to store interval-associated data, with options for "lazy"
+ * sorting so as to speed incremental construction of the data prior to issuing
+ * a findOverlap call.
+ *
+ *
+ * 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 Bob Hanson 2019.08.06
+ *
+ * @param <T>
+ * any type providing <code>getBegin()</code>, <code>getEnd()</code>
+ * <code>getContainedBy()</code>, and <code>setContainedBy()</code>
+ */
+public class IntervalStore<T extends IntervalI>
+ extends AbstractCollection<T> implements IntervalStoreI<T>
+{
+
+ private final boolean DO_PRESORT;
+
+ private boolean isSorted;
+
+ private List<T> intervals;
+
+ private boolean isTainted;
+
+ private IntervalI[] orderedIntervalStarts;
+
+ private static Comparator<IntervalI> icompare = new IntervalComparator();
+
+ static
+ {
+ System.out.println("intervalstore.nonc.IntervalStore initialized");
+ }
+
+ // private Comparator<IntervalI> icompare = new IntervalComparator();
+
+ /**
+ * Constructor
+ */
+ public IntervalStore()
+ {
+
+ intervals = new ArrayList<>();
+ DO_PRESORT = true;
+ };
+
+ public IntervalStore(boolean presort)
+ {
+ intervals = new ArrayList<>();
+ DO_PRESORT = presort;
+ };
+
+ /**
+ * 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)
+ {
+ this(intervals, true);
+ }
+
+ /**
+ * Allows a presort option, which can speed up initial loading of individual
+ * features but will delay the first findOverlap if set to true.
+ *
+ * @param intervals
+ * @param presort
+ */
+ public IntervalStore(List<T> intervals, boolean presort)
+ {
+ this.intervals = intervals;
+ DO_PRESORT = presort;
+ if (DO_PRESORT)
+ {
+ sort();
+ }
+ isTainted = true;
+ }
+
+ /**
+ * Adds one interval to the store.
+ *
+ * @param interval
+ */
+ @Override
+ public boolean add(T interval)
+ {
+ if (interval == null)
+ {
+ return false;
+ }
+
+ synchronized (intervals)
+ {
+ if (DO_PRESORT)
+ {
+ int insertPosition = findFirstBegin(intervals, interval.getBegin());
+ intervals.add(insertPosition, interval);
+ isSorted = true;
+ }
+ else
+ {
+ intervals.add(interval);
+ isSorted = false;
+ }
+ isTainted = true;
+ return true;
+ }
+ }
+
+ @Override
+ public void clear()
+ {
+ intervals.clear();
+ orderedIntervalStarts = null;
+ isTainted = true;
+ }
+
+ @Override
+ public boolean contains(Object entry)
+ {
+ return listContains(intervals, entry);
+ }
+
+ private void ensureFinalized()
+ {
+ if (isTainted && intervals.size() >= 2)
+ {
+ if (!isSorted)
+ {
+ sort();
+ }
+ orderedIntervalStarts = intervals.toArray(new IntervalI[0]);
+ linkFeatures(orderedIntervalStarts);
+ isTainted = false;
+ }
+ }
+
+ /**
+ * Sort intervals by start (lowest first) and end (highest first).
+ */
+ private void sort()
+ {
+ Collections.sort(intervals, icompare);
+ isSorted = true;
+ }
+
+ 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)
+ {
+ return findOverlaps(start, end, null);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public List<T> findOverlaps(long start, long end, List<T> result)
+ {
+
+ if (result == null)
+ {
+ result = new ArrayList<>();
+ }
+ int n = intervals.size();
+ switch (n)
+ {
+ case 0:
+ return result;
+ case 1:
+ T sf = intervals.get(0);
+ if (sf.getBegin() <= end && sf.getEnd() >= start)
+ {
+ result.add(sf);
+ }
+ return result;
+ }
+
+ ensureFinalized();
+
+ // (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()
+ {
+ int n = intervals.size();
+ if (n < 2)
+ {
+ return n;
+ }
+ ensureFinalized();
+ int maxDepth = 1;
+ T root = null;
+ for (int i = 0; i < n; i++)
+ {
+ T element = intervals.get(i);
+ IntervalI container = element;
+ if (element.getContainedBy() == null)
+ {
+ root = element;
+ }
+ int depth = 1;
+ while ((container = container.getContainedBy()) != null)
+ {
+ if (++depth > maxDepth && container == root)
+ {
+ maxDepth = depth;
+ break;
+ }
+ }
+ }
+ return maxDepth;
+ }
+
+ @Override
+ public boolean isValid()
+ {
+ ensureFinalized();
+ 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();
+
+ }
+
+ @SuppressWarnings("unchecked")
+ private void linkFeatures(IntervalI[] features)
+ {
+ int n = features.length;
+ if (n < 2)
+ {
+ return;
+ }
+ int maxEnd = features[0].getEnd();
+ for (int i = 1; i < n; i++)
+ {
+ T sf = (T) features[i];
+ if (sf.getBegin() <= maxEnd)
+ {
+ sf.setContainedBy(getContainedBy((T) features[i - 1], 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;
+ }
+
+ if (!isSorted)
+ {
+ return intervals.contains(entry);
+ }
+
+ @SuppressWarnings("unchecked")
+ 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 synchronized boolean remove(Object o)
+ {
+ // if (o == null)
+ // {
+ // throw new NullPointerException();
+ // }
+ return (o != null && intervals.size() > 0
+ && removeInterval((IntervalI) o));
+ }
+
+ /**
+ * Uses a binary search to find the entry and removes it if found.
+ *
+ * @param entry
+ * @return
+ */
+ protected boolean removeInterval(IntervalI entry)
+ {
+ if (!isSorted)
+ {
+ return intervals.remove(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 to = entry.getEnd();
+ for (int i = startIndex, size = intervals.size(); i < size; i++)
+ {
+ T sf = intervals.get(i);
+ if (sf.getBegin() > from)
+ {
+ return false;
+ }
+ if (sf.getEnd() == to && sf.equals(entry))
+ {
+ intervals.remove(i).setContainedBy(null);
+ return (isTainted = true);
+ }
+ }
+ return false;
+ }
+
+ @Override
+ public int size()
+ {
+ return intervals.size();
+ }
+
+ @Override
+ public String toString()
+ {
+ return prettyPrint();
+ }
+
+ @Override
+ public int getWidth()
+ {
+ ensureFinalized();
+ int w = 0;
+ for (int i = intervals.size(); --i >= 0;)
+ {
+ if (intervals.get(i).getContainedBy() == null)
+ {
+ w++;
+ }
+ }
+ return w;
+ }
+
+ @Override
+ public String prettyPrint()
+ {
+ int n = intervals.size();
+ if (n == 0)
+ {
+ return "";
+ }
+ if (n == 1)
+ {
+ return intervals.get(0) + "\n";
+ }
+ ensureFinalized();
+ String sep = "\t";
+ StringBuffer sb = new StringBuffer();
+ for (int i = 0; i < n; i++)
+ {
+ IntervalI range = orderedIntervalStarts[i];
+ IntervalI container = range.getContainedBy();
+ while (container != null)
+ {
+ sb.append(sep);
+ container = container.getContainedBy();
+ }
+ sb.append(range.toString()).append('\n');
+ }
+ return sb.toString();
+ }
+
+ @Override
+ public boolean revalidate()
+ {
+ isTainted = true;
+ isSorted = true;
+ ensureFinalized();
+ return true;
+ }
+
+ @Override
+ public IntervalI get(int i)
+ {
+ ensureFinalized();
+ return (i < 0 || i >= orderedIntervalStarts.length ? null
+ : orderedIntervalStarts[i]);
+ }
+
+}
git://source.jalview.org / jalview.git / blobdiff