+++ /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