--- /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.impl;
+
+import java.util.AbstractCollection;
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+
+import intervalstore.api.IntervalI;
+import intervalstore.api.IntervalStoreI;
+
+/**
+ * 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 IntervalStoreI<T>
+{
+ /**
+ * An iterator over the intervals held in this store, with no particular
+ * ordering guaranteed. The iterator does not support the optional
+ * <code>remove</code> operation (throws
+ * <code>UnsupportedOperationException</code> if attempted).
+ *
+ * @author gmcarstairs
+ *
+ * @param <V>
+ */
+ private class IntervalIterator<V extends IntervalI> implements Iterator<V>
+ {
+ /*
+ * iterator over top level non-nested intervals
+ */
+ Iterator<? extends IntervalI> topLevelIterator;
+
+ /*
+ * iterator over NCList (if any)
+ */
+ Iterator<? extends IntervalI> nestedIterator;
+
+ /**
+ * Constructor initialises iterators over the top level list and any nested
+ * NCList
+ *
+ * @param intervalStore
+ */
+ public IntervalIterator(
+ IntervalStore<? extends IntervalI> intervalStore)
+ {
+ topLevelIterator = nonNested.iterator();
+ if (nested != null)
+ {
+ nestedIterator = nested.iterator();
+ }
+ }
+
+ @Override
+ public boolean hasNext()
+ {
+ return topLevelIterator.hasNext() ? true
+ : (nestedIterator != null && nestedIterator.hasNext());
+ }
+
+ @Override
+ public V next()
+ {
+ if (topLevelIterator.hasNext())
+ {
+ return (V) topLevelIterator.next();
+ }
+ if (nestedIterator != null)
+ {
+ return (V) nestedIterator.next();
+ }
+ throw new NoSuchElementException();
+ }
+
+ }
+
+ private List<T> nonNested;
+
+ private NCList<T> nested;
+
+ /**
+ * Constructor
+ */
+ public IntervalStore()
+ {
+ nonNested = new ArrayList<>();
+ }
+
+ /**
+ * 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();
+
+ /*
+ * partition into subranges whose root intervals
+ * have no mutual containment (if no intervals are nested,
+ * each subrange is of length 1 i.e. a single interval)
+ */
+ List<IntervalI> sublists = new NCListBuilder<T>()
+ .partitionNestedSublists(intervals);
+
+ /*
+ * add all 'subrange root intervals' (and any co-located intervals)
+ * to our top level list of 'non-nested' intervals;
+ * put aside any left over for our NCList
+ */
+ List<T> nested = new ArrayList<>();
+
+ for (IntervalI subrange : sublists)
+ {
+ int listIndex = subrange.getBegin();
+ IntervalI root = intervals.get(listIndex);
+ while (listIndex <= subrange.getEnd())
+ {
+ T t = intervals.get(listIndex);
+ if (root.equalsInterval(t))
+ {
+ nonNested.add(t);
+ }
+ else
+ {
+ nested.add(t);
+ }
+ listIndex++;
+ }
+ }
+
+ if (!nested.isEmpty())
+ {
+ this.nested = new NCList<>(nested);
+ }
+ }
+
+ /**
+ * Adds one interval to the store.
+ *
+ * @param interval
+ */
+ @Override
+ public boolean add(T interval)
+ {
+ if (interval == null)
+ {
+ return false;
+ }
+ if (!addNonNestedInterval(interval))
+ {
+ /*
+ * detected a nested interval - put it in the NCList structure
+ */
+ addNestedInterval(interval);
+ }
+ return true;
+ }
+
+ @Override
+ public boolean contains(Object entry)
+ {
+ if (listContains(nonNested, entry))
+ {
+ return true;
+ }
+
+ return nested == null ? false : nested.contains(entry);
+ }
+
+ protected boolean addNonNestedInterval(T entry)
+ {
+ synchronized (nonNested)
+ {
+ /*
+ * find the first stored interval which doesn't precede the new one
+ */
+ int insertPosition = BinarySearcher.findFirst(nonNested,
+ val -> val.getBegin() >= entry.getBegin());
+ /*
+ * fail if we detect interval enclosure
+ * - of the new interval by the one before or after it
+ * - of the next interval by the new one
+ */
+ if (insertPosition > 0)
+ {
+ if (nonNested.get(insertPosition - 1).properlyContainsInterval(entry))
+ {
+ return false;
+ }
+ }
+ if (insertPosition < nonNested.size())
+ {
+ T following = nonNested.get(insertPosition);
+ if (entry.properlyContainsInterval(following)
+ || following.properlyContainsInterval(entry))
+ {
+ return false;
+ }
+ }
+
+ /*
+ * checks passed - add the interval
+ */
+ nonNested.add(insertPosition, entry);
+
+ return true;
+ }
+ }
+
+ @Override
+ public List<T> findOverlaps(long from, long to)
+ {
+ List<T> result = new ArrayList<>();
+
+ findNonNestedOverlaps(from, to, result);
+
+ if (nested != null)
+ {
+ result.addAll(nested.findOverlaps(from, to));
+ }
+
+ return result;
+ }
+
+ @Override
+ public String prettyPrint()
+ {
+ String pp = nonNested.toString();
+ if (nested != null)
+ {
+ pp += System.lineSeparator() + nested.prettyPrint();
+ }
+ return pp;
+ }
+
+ @Override
+ public boolean isValid()
+ {
+ for (int i = 0; i < nonNested.size() - 1; i++)
+ {
+ IntervalI i1 = nonNested.get(i);
+ IntervalI i2 = nonNested.get(i + 1);
+
+ if (i2.getBegin() < i1.getBegin())
+ {
+ System.err.println("nonNested wrong start order : " + i1.toString()
+ + ", " + i2.toString());
+ return false;
+ }
+ if (i1.properlyContainsInterval(i2)
+ || i2.properlyContainsInterval(i1))
+ {
+ System.err.println("nonNested invalid containment!: "
+ + i1.toString()
+ + ", " + i2.toString());
+ return false;
+ }
+ }
+ return nested == null ? true : nested.isValid();
+ }
+
+ @Override
+ public int size()
+ {
+ int i = nonNested.size();
+ if (nested != null)
+ {
+ i += nested.size();
+ }
+ return i;
+ }
+
+ @Override
+ public synchronized boolean remove(Object o)
+ {
+ if (o == null)
+ {
+ return false;
+ }
+ try
+ {
+ @SuppressWarnings("unchecked")
+ T entry = (T) o;
+
+ /*
+ * try the non-nested positional intervals first
+ */
+ boolean removed = removeNonNested(entry);
+
+ /*
+ * if not found, try nested intervals
+ */
+ if (!removed && nested != null)
+ {
+ removed = nested.remove(entry);
+ }
+
+ return removed;
+ } catch (ClassCastException e)
+ {
+ return false;
+ }
+ }
+
+ /**
+ * 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 removeNonNested(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 = BinarySearcher.findFirst(nonNested,
+ val -> val.getBegin() >= entry.getBegin());
+
+ /*
+ * traverse intervals to look for a match
+ */
+ int from = entry.getBegin();
+ int i = startIndex;
+ int size = nonNested.size();
+ while (i < size)
+ {
+ T sf = nonNested.get(i);
+ if (sf.getBegin() > from)
+ {
+ break;
+ }
+ if (sf.equals(entry))
+ {
+ nonNested.remove(i);
+ return true;
+ }
+ i++;
+ }
+ return false;
+ }
+
+ @Override
+ public int getDepth()
+ {
+ if (size() == 0)
+ {
+ return 0;
+ }
+ return (nonNested.isEmpty() ? 0 : 1)
+ + (nested == null ? 0 : nested.getDepth());
+ }
+
+ /**
+ * Adds one interval to the NCList that can manage nested intervals (creating
+ * the NCList if necessary)
+ */
+ protected synchronized void addNestedInterval(T interval)
+ {
+ if (nested == null)
+ {
+ nested = new NCList<>();
+ }
+ nested.add(interval);
+ }
+
+ /**
+ * 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 || !(entry instanceof IntervalI))
+ {
+ return false;
+ }
+
+ IntervalI interval = (IntervalI) entry;
+
+ /*
+ * locate the first entry in the list which does not precede the interval
+ */
+ int pos = BinarySearcher.findFirst(intervals,
+ val -> val.getBegin() >= 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.equals(interval))
+ {
+ return true;
+ }
+ pos++;
+ }
+ return false;
+ }
+
+ /**
+ * 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 new IntervalIterator<>(this);
+ }
+
+ @Override
+ public void clear()
+ {
+ this.nonNested.clear();
+ this.nested = new NCList<>();
+ }
+
+ /**
+ * Adds non-nested intervals to the result list that lie within the target
+ * range
+ *
+ * @param from
+ * @param to
+ * @param result
+ */
+ protected void findNonNestedOverlaps(long from, long to,
+ List<T> result)
+ {
+ /*
+ * find the first interval whose end position is
+ * after the target range start
+ */
+ int startIndex = BinarySearcher.findFirst(nonNested,
+ val -> val.getEnd() >= from);
+
+ final int startIndex1 = startIndex;
+ int i = startIndex1;
+ while (i < nonNested.size())
+ {
+ T sf = nonNested.get(i);
+ if (sf.getBegin() > to)
+ {
+ break;
+ }
+ if (sf.getBegin() <= to && sf.getEnd() >= from)
+ {
+ result.add(sf);
+ }
+ i++;
+ }
+ }
+
+ @Override
+ public String toString()
+ {
+ String s = nonNested.toString();
+ if (nested != null)
+ {
+ s = s + System.lineSeparator() + nested.toString();
+ }
+ return s;
+ }
+}
git://source.jalview.org / jalview.git / blobdiff