X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=unused%2Fnonc%2FIntervalStore.java;fp=unused%2Fnonc%2FIntervalStore.java;h=0000000000000000000000000000000000000000;hb=4f77328104498504339216829abf5ea87e2791ec;hp=4e308b5bbea3b1306010aa081fa34f52251013be;hpb=2b8c0785318a3528e1876e8e2dd48b7d831eae69;p=jalview.git diff --git a/unused/nonc/IntervalStore.java b/unused/nonc/IntervalStore.java deleted file mode 100644 index 4e308b5..0000000 --- a/unused/nonc/IntervalStore.java +++ /dev/null @@ -1,540 +0,0 @@ -/* -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 - * any type providing getBegin() and getEnd() - */ -public class IntervalStore - extends AbstractCollection - implements intervalstore.api.IntervalStoreI -{ - private List intervals; - - private boolean isTainted; - - private IntervalI[] orderedIntervalStarts; - - /** - * Constructor - */ - public IntervalStore() - { - intervals = new ArrayList<>(); - } - - class IntervalComparator implements Comparator - { - - @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 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 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 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 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 findOverlaps(long start, long end) - { - - List 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 - * remove operation (throws - * UnsupportedOperationException if attempted). - */ - @Override - public Iterator iterator() - { - return intervals.iterator(); - - } - - private void justCheckOne(T sf, long start, long end, List 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 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 item.equals(entry). - * - * @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(); - } - -}