--- /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;
+
+/**
+ * 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();
+ }
+
+}
git://source.jalview.org / jalview.git / blobdiff