<classpathentry kind="lib" path="lib/jetty-http-9.2.10.v20150310.jar"/>
<classpathentry kind="lib" path="lib/jetty-io-9.2.10.v20150310.jar"/>
<classpathentry kind="lib" path="lib/java-json.jar"/>
- <classpathentry kind="con" path="org.testng.TESTNG_CONTAINER"/>
<classpathentry kind="lib" path="lib/biojava-core-4.1.0.jar"/>
<classpathentry kind="lib" path="lib/biojava-ontology-4.1.0.jar"/>
<classpathentry kind="lib" path="lib/htsjdk-2.12.0.jar"/>
<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER/org.eclipse.jdt.internal.debug.ui.launcher.StandardVMType/JavaSE-1.8"/>
<classpathentry exported="true" kind="con" path="GROOVY_DSL_SUPPORT"/>
<classpathentry kind="lib" path="lib/Jmol-14.29.17.jar"/>
- <classpathentry kind="lib" path="lib/intervalstore-v1.0.jar"/>
+ <classpathentry kind="lib" path="utils/testnglibs/bsh-2.0b4.jar"/>
+ <classpathentry kind="lib" path="utils/testnglibs/guava-base-r03.jar"/>
+ <classpathentry kind="lib" path="utils/testnglibs/guava-collections-r03.jar"/>
+ <classpathentry kind="lib" path="utils/testnglibs/jcommander.jar"/>
+ <classpathentry kind="lib" path="utils/testnglibs/junit-4.12.jar"/>
+ <classpathentry kind="lib" path="utils/testnglibs/snakeyaml.jar"/>
+ <classpathentry kind="lib" path="utils/testnglibs/testng-sources.jar"/>
+ <classpathentry kind="lib" path="utils/testnglibs/testng.jar"/>
+ <classpathentry kind="lib" path="lib/intervalstore-v1.1.jar"/>
<classpathentry kind="output" path="classes"/>
</classpath>
+++ /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.api;
-
-import java.util.Collections;
-import java.util.Comparator;
-import java.util.List;
-
-public interface IntervalI
-{
-
- /**
- * Compare intervals by start position ascending and end position descending.
- *
- * BIGENDIAN sorts 10-100 ahead of 10-80 (original IntervalStoreJ method
- *
- */
- static Comparator<? super IntervalI> COMPARATOR_BIGENDIAN = new Comparator<IntervalI>()
- {
- @Override
- public int compare(IntervalI o1, IntervalI o2)
- {
- int ret = Integer.signum(o1.getBegin() - o2.getBegin());
- return (ret == 0 ? Integer.signum(o2.getEnd() - o1.getEnd()) : ret);
- }
- };
-
- /**
- * Compare intervals by start position ascending and end position descending.
- *
- * LITTLEENDIAN sorts 10-100 after 10-80
- *
- */
- static Comparator<? super IntervalI> COMPARATOR_LITTLEENDIAN = new Comparator<IntervalI>()
- {
- @Override
- public int compare(IntervalI o1, IntervalI o2)
- {
- int ret = Integer.signum(o1.getBegin() - o2.getBegin());
- return (ret == 0 ? Integer.signum(o1.getEnd() - o2.getEnd()) : ret);
- }
- };
-
- /**
- * a comparator for sorting intervals by start position ascending
- */
- static Comparator<? super IntervalI> FORWARD_STRAND = new Comparator<IntervalI>()
- {
- @Override
- public int compare(IntervalI o1, IntervalI o2)
- {
- return Integer.signum(o1.getBegin() - o2.getBegin());
- }
- };
-
- /**
- * a comparator for sorting intervals by end position descending
- */
- static Comparator<? super IntervalI> REVERSE_STRAND = new Comparator<IntervalI>()
- {
- @Override
- public int compare(IntervalI o1, IntervalI o2)
- {
- return Integer.signum(o2.getEnd() - o1.getEnd());
- }
- };
-
- static int NOT_CONTAINED = Integer.MIN_VALUE;
- static int CONTAINMENT_UNKNOWN = 0;
-
- int getBegin();
- int getEnd();
-
- /**
- * Answers true if this interval contains (or matches) the given interval
- * based solely on start and end.
- *
- * @param i
- * @return
- */
- default boolean containsInterval(IntervalI i)
- {
- return i != null && i.getBegin() >= getBegin()
- && i.getEnd() <= getEnd();
- }
-
-
- /**
- * Answers true if this interval properly contains the given interval, that
- * is, it contains it and is larger than it
- *
- * @param i
- * @return
- */
- default boolean properlyContainsInterval(IntervalI i)
- {
- return containsInterval(i)
- && (i.getBegin() > getBegin() || i.getEnd() < getEnd());
- }
-
- /**
- * Slower than equalsInterval; also includes type.
- *
- * Ensure that subclasses override equals(Object). For example:
- *
- * public boolean equals(Object o) { return o != null && o instanceof XXX &&
- * equalsInterval((XXX) i); }
- *
- *
- * equalsInterval also must be overridden.
- *
- * public boolean equalsInterval(IntervalI i) {return ((SimpleFeature)i).start
- * == start && ((SimpleFeature)i).end == end && ((SimpleFeature)i).description
- * == this.description; }
- *
- *
- * @param o
- * @return true if equal, including a type check
- */
- @Override
- abstract boolean equals(Object o);
-
-
-
- /**
- * Check that two intervals are equal, in terms of end points, descriptions,
- * or any other distinguishing features.
- *
- * Used in IntervalStore in searches, since it is faster than equals(), as at
- * that point we know that we have the correct type.
- *
- * @param i
- * may be null
- * @return true if equal; null value must return false, not throw
- * NullPointerException
- */
- abstract boolean equalsInterval(IntervalI i);
-
- default boolean overlapsInterval(IntervalI i)
- {
- if (i == null)
- {
- return false;
- }
- if (i.getBegin() < getBegin())
- {
- return i.getEnd() >= getBegin();
- }
- if (i.getEnd() > getEnd())
- {
- return i.getBegin() <= getEnd();
- }
- return true; // i internal to this
- }
-
- /**
- * Sorts the list by start position ascending (if forwardString==true), or by
- * end position descending
- *
- * @param intervals
- * @param forwardStrand
- */
- static void sortIntervals(List<? extends IntervalI> intervals,
- final boolean forwardStrand)
- {
- Collections.sort(intervals,
- forwardStrand ? FORWARD_STRAND : REVERSE_STRAND);
- }
-
-
-}
+++ /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.api;
-
-import java.util.Collection;
-import java.util.List;
-
-import intervalstore.impl.NCList;
-
-public interface IntervalStoreI<T extends IntervalI> extends Collection<T>
-{
-
- /**
- * Returns a (possibly empty) list of items whose extent overlaps the given
- * range
- *
- * @param from
- * start of overlap range (inclusive)
- * @param to
- * end of overlap range (inclusive)
- * @return
- */
- List<T> findOverlaps(long from, long to);
-
- /**
- * Ensures that the IntervalStore is ready for findOverlap.
- *
- * @return true iff the data held satisfy the rules of construction of an
- * IntervalStore.
- *
- */
- boolean isValid();
-
- /**
- * Answers the level of nesting of intervals in the store, as
- * <ul>
- * <li>0 if the store is empty</li>
- * <li>1 if all intervals are 'top level' (non nested)</li>
- * <li>else 1 plus the depth of the enclosed NCList</li>
- * </ul>
- *
- * @return
- * @see NCList#getDepth()
- */
- int getDepth();
-
- /**
- * Return the number of top-level (not-contained) intervals.
- *
- * @return
- */
- int getWidth();
-
- List<T> findOverlaps(long start, long end, List<T> result);
-
- String prettyPrint();
-
- /**
- * Resort and rebuild links.
- *
- * @return
- */
- boolean revalidate();
-
- /**
- * Get the i-th interval, whatever that means to this store.
- *
- * @param i
- * @return
- */
- IntervalI get(int i);
-
- /**
- * Check to see if this store can check for duplicates while adding.
- *
- * @return
- */
- boolean canCheckForDuplicates();
-
- /**
- * Add with a check for duplicates, if possible.
- *
- * @param interval
- * @param checkForDuplicate
- * @return false only if addition was unsuccessful because there was an
- * identical interval already in the store or because the store cannot
- * check for duplicates
- */
- boolean add(T interval, boolean checkForDuplicate);
-
-}
\ No newline at end of file
+++ /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.List;
-import java.util.function.ToIntFunction;
-
-import intervalstore.api.IntervalI;
-
-/**
- * Provides a method to perform binary search of an ordered list for the first
- * entry that satisfies a supplied condition
- *
- * @author gmcarstairs
- */
-public final class BinarySearcher
-{
-
- public static ToIntFunction<IntervalI> fbegin = new ToIntFunction<IntervalI>()
- {
-
- @Override
- public int applyAsInt(IntervalI value)
- {
- return value.getBegin();
- }
-
- };
-
- public static ToIntFunction<IntervalI> fend = new ToIntFunction<IntervalI>()
- {
-
- @Override
- public int applyAsInt(IntervalI value)
- {
- return value.getEnd();
- }
-
- };
-
- private BinarySearcher()
- {
- }
-
- /**
- * Performs a binary search of the list to find the index of the first entry
- * for which the test returns true. Answers the length of the list if there is
- * no such entry.
- * <p>
- * For correct behaviour, the provided list must be ordered consistent with
- * the test, that is, any entries returning false must precede any entries
- * returning true. Note that this means that this method is <em>not</em>
- * usable to search for equality (to find a specific entry), as all unequal
- * entries will answer false to the test. To do that, use
- * <code>Collections.binarySearch</code> instead.
- *
- * @param list
- * @param test
- * @return
- * @see java.util.Collections#binarySearch(List, Object)
- */
- public static <T> int findFirst(List<? extends T> list, int pos,
- ToIntFunction<T> test)
- {
- int start = 0;
- int end = list.size() - 1;
- int matched = list.size();
-
- while (start <= end)
- {
- int mid = (start + end) / 2;
- T entry = list.get(mid);
- boolean itsTrue = test.applyAsInt(entry) >= pos;
- if (itsTrue)
- {
- matched = mid;
- end = mid - 1;
- }
- else
- {
- start = mid + 1;
- }
- }
-
- return matched;
- }
-}
+++ /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());
- }
-
- @SuppressWarnings("unchecked")
- @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,
- entry.getBegin(),
- BinarySearcher.fbegin);
- /*
- * 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)
- {
- nested.findOverlaps(from, to, result);
- }
-
- return result;
- }
-
- @Override
- public String prettyPrint()
- {
- String pp = nonNested.toString();
- if (nested != null)
- {
- pp += '\n' + 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 from = entry.getBegin();
- int startIndex = BinarySearcher.findFirst(nonNested, from,
- BinarySearcher.fbegin);
-
- /*
- * traverse intervals to look for a match
- */
-
- 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 from = interval.getBegin();
- int pos = BinarySearcher.findFirst(intervals, from,
- BinarySearcher.fbegin);
- int len = intervals.size();
- while (pos < len)
- {
- T sf = intervals.get(pos);
- if (sf.getBegin() > from)
- {
- 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, (int) from,
- BinarySearcher.fend);
- for (int i = startIndex, n = nonNested.size(); i < n; i++)
- {
- T sf = nonNested.get(i);
- if (sf.getBegin() > to)
- {
- break;
- }
- if (sf.getEnd() >= from)
- {
- result.add(sf);
- }
- }
- }
-
- @Override
- public String toString()
- {
- String s = nonNested.toString();
- if (nested != null)
- {
- s = s + '\n'// + System.lineSeparator()
- + nested.toString();
- }
- return s;
- }
-
- @Override
- public int getWidth()
- {
- return (nonNested == null ? 0 : nonNested.size())
- + (nested == null ? 0 : nested.size());
- }
-
- @Override
- public List<T> findOverlaps(long start, long end, List<T> result)
- {
- return findOverlaps(start, end);
- }
-
- @Override
- public boolean revalidate()
- {
- // not applicable
- return true;
- }
-
- @Override
- public IntervalI get(int i)
- {
- // not supported (but could be)
- return null;
- }
-
- @Override
- public boolean canCheckForDuplicates()
- {
- return false;
- }
-
- @Override
- public boolean add(T interval, boolean checkForDuplicate)
- {
- return add(interval);
- }
-}
+++ /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.Collections;
-import java.util.Iterator;
-import java.util.List;
-import java.util.NoSuchElementException;
-
-import intervalstore.api.IntervalI;
-
-/**
- * An adapted implementation of NCList as described in the paper
- *
- * <pre>
- * Nested Containment List (NCList): a new algorithm for accelerating
- * interval query of genome alignment and interval databases
- * - Alexander V. Alekseyenko, Christopher J. Lee
- * https://doi.org/10.1093/bioinformatics/btl647
- * </pre>
- */
-public class NCList<T extends IntervalI> extends AbstractCollection<T>
-{
-
- // private static final boolean OPTION_FIND_ANY = false;
-
- /**
- * A depth-first iterator over the elements stored in the NCList
- */
- private class NCListIterator implements Iterator<T>
- {
- int subrangeIndex;
-
- Iterator<T> nodeIterator;
-
- /**
- * Constructor bootstraps a pointer to an iterator over the first subrange
- * (if any)
- */
- NCListIterator()
- {
- subrangeIndex = nextSubrange(-1);
- }
-
- /**
- * Moves the subrange iterator to the next subrange, and answers its index
- * in the list of subranges. If there are no more, sets the iterator to null
- * and answers -1.
- *
- * @return
- */
- private int nextSubrange(int after)
- {
- int nextIndex = after + 1;
- if (nextIndex < subranges.size())
- {
- nodeIterator = subranges.get(nextIndex).iterator();
- return nextIndex;
- }
- nodeIterator = null;
- return -1;
- }
-
- @Override
- public boolean hasNext()
- {
- return nodeIterator != null && nodeIterator.hasNext();
- }
-
- /**
- * Answers the next element returned by the current NCNode's iterator, and
- * advances the iterator (to the next NCNode if necessary)
- */
- @Override
- public T next()
- {
- if (nodeIterator == null || !nodeIterator.hasNext())
- {
- throw new NoSuchElementException();
- }
- T result = nodeIterator.next();
-
- if (!nodeIterator.hasNext())
- {
- subrangeIndex = nextSubrange(subrangeIndex);
- }
- return result;
- }
-
- }
-
- /*
- * the number of interval instances represented
- */
- private int size;
-
- /*
- * a list, in start position order, of sublists of ranges ordered so
- * that each contains (or is the same as) the one that follows it
- */
- private List<NCNode<T>> subranges;
-
- /**
- * Constructor given a list of things that are each located on a contiguous
- * interval. Note that the constructor may reorder the list.
- * <p>
- * We assume here that for each range, start <= end. Behaviour for reverse
- * ordered ranges is undefined.
- *
- * @param ranges
- */
- public NCList(List<T> ranges)
- {
- this();
- build(ranges);
- }
-
- /**
- * Sorts and groups ranges into sublists where each sublist represents an
- * interval and its contained subintervals
- *
- * @param ranges
- */
- protected void build(List<T> ranges)
- {
- /*
- * sort and partition into subranges
- * which have no mutual containment
- */
- List<IntervalI> sublists = partitionNestedSublists(ranges);
-
- /*
- * convert each subrange to an NCNode consisting of a range and
- * (possibly) its contained NCList
- */
- for (IntervalI sublist : sublists)
- {
- subranges.add(new NCNode<>(
- ranges.subList(sublist.getBegin(), sublist.getEnd() + 1)));
- }
-
- size = ranges.size();
- }
-
- /**
- * Default constructor
- */
- public NCList()
- {
- subranges = new ArrayList<>();
- }
-
- /**
- * Sorts and traverses the ranges to identify sublists, whose start intervals
- * are overlapping or disjoint but not mutually contained. Answers a list of
- * start-end indices of the sorted list of ranges.
- *
- * @param ranges
- * @return
- */
- protected List<IntervalI> partitionNestedSublists(List<T> ranges)
- {
- List<IntervalI> sublists = new ArrayList<>();
-
- if (ranges.isEmpty())
- {
- return sublists;
- }
-
- /*
- * sort by start ascending, length descending, so that
- * contained intervals follow their containing interval
- */
- Collections.sort(ranges, IntervalI.COMPARATOR_BIGENDIAN);
-
- int listStartIndex = 0;
-
- IntervalI lastParent = ranges.get(0);
- boolean first = true;
-
- for (int i = 0; i < ranges.size(); i++)
- {
- IntervalI nextInterval = ranges.get(i);
- if (!first && !lastParent.properlyContainsInterval(nextInterval))
- {
- /*
- * this interval is not properly contained in the parent;
- * close off the last sublist
- */
- sublists.add(new Range(listStartIndex, i - 1));
- listStartIndex = i;
- lastParent = nextInterval;
- }
- first = false;
- }
-
- sublists.add(new Range(listStartIndex, ranges.size() - 1));
- return sublists;
- }
-
- /**
- * Adds one entry to the stored set
- *
- * @param entry
- */
- @Override
- public synchronized boolean add(final T entry)
- {
- final NCNode<T> newNode = new NCNode<>(entry);
- addNode(newNode);
- return true;
- }
-
- /**
- * Adds one NCNode to this NCList
- * <p>
- * This method does not update the <code>size</code> (interval count) of this
- * NCList, as it may be used to rearrange nodes without changing their count.
- * Callers should increment the count if needed.
- *
- * @param newNode
- */
- protected void addNode(final NCNode<T> newNode)
- {
- final long start = newNode.getBegin();
- final long end = newNode.getEnd();
- size += newNode.size();
-
- /*
- * cases:
- * 1) precedes all subranges - add as NCNode on front of list
- * 2) follows all subranges - add as NCNode on end of list
- * 3) matches a subrange - add as a sibling in the list
- * 4) properly enclosed by a subrange - add recursively to subrange
- * 5) properly encloses one or more subranges - push them inside it
- * 6) spans two subranges - insert between them
- */
-
- /*
- * find the first subrange whose end does not precede entry's start
- */
- int candidateIndex = findFirstOverlap(start);
-
- /*
- * search for maximal span of subranges i-k that the new entry
- * encloses; or a subrange that encloses the new entry
- */
- boolean enclosing = false;
- int firstEnclosed = 0;
- int lastEnclosed = 0;
-
- for (int j = candidateIndex; j < subranges.size(); j++)
- {
- NCNode<T> subrange = subranges.get(j);
-
- if (subrange.equalsInterval(newNode))
- {
- /*
- * matching interval - insert adjacent
- */
- subranges.add(j, newNode);
- return;
- }
-
- if (end < subrange.getBegin() && !enclosing)
- {
- /*
- * new entry lies between subranges j-1 j
- */
- subranges.add(j, newNode);
- return;
- }
-
- if (subrange.properlyContainsInterval(newNode))
- {
- /*
- * push new entry inside this subrange as it encloses it
- */
- subrange.addNode(newNode);
- return;
- }
-
- if (start <= subrange.getBegin())
- {
- if (end >= subrange.getEnd())
- {
- /*
- * new entry encloses this subrange (and possibly preceding ones);
- * continue to find the maximal list it encloses
- */
- if (!enclosing)
- {
- firstEnclosed = j;
- }
- lastEnclosed = j;
- enclosing = true;
- continue;
- }
- else
- {
- /*
- * entry spans from before this subrange to inside it
- */
- if (enclosing)
- {
- /*
- * entry encloses one or more preceding subranges
- */
- push(newNode, firstEnclosed, lastEnclosed);
- }
- else
- {
- /*
- * entry overlaps two subranges but doesn't enclose either
- * so just add it
- */
- subranges.add(j, newNode);
- }
- return;
- }
- }
- }
-
- /*
- * drops through to here if new range encloses all others
- * or overlaps the last one
- */
- if (enclosing)
- {
- push(newNode, firstEnclosed, lastEnclosed);
- }
- else
- {
- subranges.add(newNode);
- }
- }
-
- @Override
- public boolean contains(Object entry)
- {
- if (!(entry instanceof IntervalI))
- {
- return false;
- }
- IntervalI interval = (IntervalI) entry;
-
- /*
- * find the first sublist that might overlap, i.e.
- * the first whose end position is >= from
- */
- int candidateIndex = findFirstOverlap(interval.getBegin());
-
- int to = interval.getEnd();
-
- for (int i = candidateIndex; i < subranges.size(); i++)
- {
- NCNode<T> candidate = subranges.get(i);
- if (candidate.getBegin() > to)
- {
- /*
- * we are past the end of our target range
- */
- break;
- }
- if (candidate.contains(interval))
- {
- return true;
- }
- }
- return false;
- }
-
- /**
- * Update the tree so that the new node encloses current subranges i to j
- * (inclusive). That is, replace subranges i-j (inclusive) with a new subrange
- * that contains them.
- *
- * @param node
- * @param i
- * @param j
- * @throws IllegalArgumentException
- * if any of the subranges is not contained by the node's start-end
- * range
- */
- protected synchronized void push(NCNode<T> node, final int i,
- final int j)
- {
- for (int k = i; k <= j; k++)
- {
- NCNode<T> n = subranges.get(k);
- if (!node.containsInterval(n)) {
- throw new IllegalArgumentException("Can't push " + n.toString()
- + " inside " + node.toString());
- }
- node.addNode(n);
- }
-
- for (int k = j; k >= i; k--)
- {
- subranges.remove(k);
- }
- subranges.add(i, node);
- }
-
- /**
- * Answers a list of contained intervals that overlap the given range
- *
- * @param from
- * @param to
- * @return
- */
- public List<T> findOverlaps(long from, long to)
- {
- List<T> result = new ArrayList<>();
-
- findOverlaps(from, to, result);
-
- return result;
- }
-
- /**
- * Recursively searches the NCList adding any items that overlap the from-to
- * range to the result list
- *
- * @param from
- * @param to
- * @param result
- */
- protected List<T> findOverlaps(long from, long to, List<T> result)
- {
-
- // if (OPTION_FIND_ANY)
- // {
- // return findAnyOverlaps(from, to, result);
- // }
- /*
- * find the first sublist that might overlap, i.e.
- * the first whose end position is >= from
- */
- int candidateIndex = findFirstOverlap(from);
-
- for (int i = candidateIndex; i < subranges.size(); i++)
- {
- NCNode<T> candidate = subranges.get(i);
- if (candidate.getBegin() > to)
- {
- /*
- * we are past the end of our target range
- */
- break;
- }
- candidate.findOverlaps(from, to, result);
- }
- return result;
- }
-
- // /**
- // * Recursively searches the NCList adding any items that overlap the from-to
- // * range to the result list
- // *
- // * @param from
- // * @param to
- // * @param result
- // */
- // protected List<T> findAnyOverlaps(long from, long to, List<T> result)
- // {
- //
- // // BH find ANY overlap
- //
- // int candidateIndex = findAnyOverlap(subranges, from, to);
- //
- // if (candidateIndex < 0)
- // return result;
- // for (int i = candidateIndex, n = subranges.size(); i < n; i++)
- // {
- // NCNode<T> candidate = subranges.get(i);
- // if (candidate.getBegin() > to)
- // {
- // /*
- // * we are past the end of our target range
- // */
- // break;
- // }
- // candidate.findOverlaps(from, to, result);
- // }
- //
- // // BH adds dual-direction check
- //
- // for (int i = candidateIndex; --i >= 0;)
- // {
- // NCNode<T> candidate = subranges.get(i);
- // if (candidate.getEnd() < from)
- // {
- // break;
- // }
- // candidate.findOverlaps(from, to, result);
- // }
- // return result;
- // }
- //
- // private int findAnyOverlap(List<NCNode<T>> ranges, long from, long to)
- // {
- // int start = 0;
- // int end = ranges.size() - 1;
- // while (start <= end)
- // {
- // int mid = (start + end) >>> 1;
- // NCNode<T> r = ranges.get(mid);
- // if (r.getEnd() >= from)
- // {
- // if (r.getBegin() <= to)
- // return mid;
- // end = mid - 1;
- // }
- // else
- // {
- // start = mid + 1;
- // }
- // }
- // return -1;
- // }
-
- /**
- * Search subranges for the first one whose end position is not before the
- * target range's start position, i.e. the first one that may overlap the
- * target range. Returns the index in the list of the first such range found,
- * or the length of the list if none found.
- *
- * @param from
- * @return
- */
- protected int findFirstOverlap(final long from)
- {
- return BinarySearcher.findFirst(subranges, (int) from,
- BinarySearcher.fend);
- }
-
- /**
- * Formats the tree as a bracketed list e.g.
- *
- * <pre>
- * [1-100 [10-30 [10-20]], 15-30 [20-20]]
- * </pre>
- */
- @Override
- public String toString()
- {
- return subranges.toString();
- }
-
- /**
- * Answers the NCList as an indented list
- *
- * @return
- */
- public String prettyPrint()
- {
- StringBuilder sb = new StringBuilder(512);
- int offset = 0;
- int indent = 2;
- prettyPrint(sb, offset, indent);
- sb.append('\n');// System.lineSeparator());
- return sb.toString();
- }
-
- /**
- * @param sb
- * @param offset
- * @param indent
- */
- void prettyPrint(StringBuilder sb, int offset, int indent)
- {
- boolean first = true;
- for (NCNode<T> subrange : subranges)
- {
- if (!first)
- {
- sb.append('\n');// System.lineSeparator());
- }
- first = false;
- subrange.prettyPrint(sb, offset, indent);
- }
- }
-
- /**
- * Answers true if the store's structure is valid (nesting containment rules
- * are obeyed), else false. For use in testing and debugging.
- *
- * @return
- */
- public boolean isValid()
- {
- int count = 0;
- for (NCNode<T> subrange : subranges)
- {
- count += subrange.size();
- }
- if (count != size)
- {
- return false;
- }
- return isValid(Integer.MIN_VALUE, Integer.MAX_VALUE);
- }
-
- /**
- * Answers true if the data held satisfy the rules of construction of an
- * NCList bounded within the given start-end range, else false.
- * <p>
- * Each subrange must lie within start-end (inclusive). Subranges must be
- * ordered by start position ascending, and within that by end position
- * descending.
- * <p>
- *
- * @param start
- * @param end
- * @return
- */
- boolean isValid(final int start, final int end)
- {
- NCNode<T> lastRange = null;
-
- for (NCNode<T> subrange : subranges)
- {
- if (subrange.getBegin() < start)
- {
- System.err.println("error in NCList: range " + subrange.toString()
- + " starts before " + end);
- return false;
- }
- if (subrange.getEnd() > end)
- {
- System.err.println("error in NCList: range " + subrange.toString()
- + " ends after " + end);
- return false;
- }
-
- if (lastRange != null)
- {
- if (subrange.getBegin() < lastRange.getBegin())
- {
- System.err.println("error in NCList: range " + subrange.toString()
- + " starts before " + lastRange.toString());
- return false;
- }
- if (subrange.properlyContainsInterval(lastRange))
- {
- System.err.println("error in NCList: range " + subrange.toString()
- + " encloses preceding: " + lastRange.toString());
- return false;
- }
- if (lastRange.properlyContainsInterval(subrange))
- {
- System.err.println("error in NCList: range " + subrange.toString()
- + " enclosed by preceding: " + lastRange.toString());
- return false;
- }
- }
- lastRange = subrange;
-
- if (!subrange.isValid())
- {
- return false;
- }
- }
- return true;
- }
-
- /**
- * Answers the number of intervals stored
- *
- * @return
- */
- @Override
- public int size()
- {
- return size;
- }
-
- /**
- * Answers a list of all entries stored, in no guaranteed order. This method
- * is not synchronized, so is not thread-safe.
- */
- public List<T> getEntries()
- {
- List<T> result = new ArrayList<>();
- getEntries(result);
- return result;
- }
-
- /**
- * Adds all contained entries to the given list
- *
- * @param result
- */
- void getEntries(List<T> result)
- {
- for (NCNode<T> subrange : subranges)
- {
- subrange.getEntries(result);
- }
- }
-
- /**
- * Removes the first interval <code>I</code>found that is equal to T
- * (<code>I.equals(T)</code>). Answers true if an interval is removed, false
- * if no match is found. This method is synchronized so thread-safe.
- *
- * @param entry
- * @return
- */
- public synchronized boolean remove(T entry)
- {
- if (entry == null)
- {
- return false;
- }
- int i = findFirstOverlap(entry.getBegin());
-
- for (; i < subranges.size(); i++)
- {
- NCNode<T> subrange = subranges.get(i);
- if (subrange.getBegin() > entry.getBegin())
- {
- /*
- * not found
- */
- return false;
- }
- NCList<T> subRegions = subrange.getSubRegions();
-
- if (subrange.getRegion().equals(entry))
- {
- /*
- * if the subrange is rooted on this entry, remove it,
- * and remove and promote its subregions (if any)
- */
- subranges.remove(i);
- size -= subrange.size();
- if (subRegions != null)
- {
- for (NCNode<T> r : subRegions.subranges)
- {
- addNode(r);
- }
- }
- return true;
- }
- else
- {
- if (subrange.remove(entry))
- {
- size--;
- return true;
- }
- }
- }
- return false;
- }
-
- /**
- * Answers the depth of interval nesting of this object, where 1 means there
- * are no nested sub-intervals
- *
- * @return
- */
- public int getDepth()
- {
- int subDepth = 0;
- for (NCNode<T> subrange : subranges)
- {
- subDepth = Math.max(subDepth, subrange.getDepth());
- }
-
- return subDepth;
- }
-
- /**
- * Answers an iterator over the contained intervals, with no particular order
- * 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 NCListIterator();
- }
-
- @Override
- public synchronized void clear()
- {
- subranges.clear();
- size = 0;
- }
-
- public int getWidth()
- {
- return subranges.size();
- }
-}
+++ /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.ArrayList;
-import java.util.Collections;
-import java.util.Comparator;
-import java.util.List;
-
-import intervalstore.api.IntervalI;
-
-/**
- * A comparator that orders ranges by either start position ascending. If
- * position matches, ordering is by length descending. This provides the
- * canonical ordering of intervals into subranges in order to build a nested
- * containment list.
- *
- * @author gmcarstairs
- */
-public class NCListBuilder<T extends IntervalI>
-{
- // class NCListComparator<V extends IntervalI> implements Comparator<V>
- // {
- // /**
- // * Compares two intervals in a way that will sort a list by start position
- // * ascending, then by length descending. Answers
- // * <ul>
- // * <li>a negative value if o1.begin < o2.begin</li>
- // * <li>else a positive value if o1.begin > o2.begin</li>
- // * <li>else a negative value if o1.end > o2.end</li>
- // * <li>else a positive value of o1.end < o2.end</li>
- // * <li>else zero</li
- // * </ul>
- // */
- // @Override
- // public int compare(V o1, V 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;
- // }
- // }
-
- private Comparator<? super IntervalI> comparator = IntervalI.COMPARATOR_BIGENDIAN;// new
- // NCListComparator<>();
-
- /**
- * Default constructor
- */
- public NCListBuilder()
- {
- }
-
- /**
- * Answers a comparator which sorts items of type T by start position
- * ascending, and within that by end position (length) descending)
- *
- * @return
- */
- Comparator<? super IntervalI> getComparator()
- {
- return comparator;
- }
-
- /**
- * Sorts and traverses the ranges to identify sublists, whose start intervals
- * are overlapping or disjoint but not mutually contained. Answers a list of
- * start-end indices of the sorted list of ranges.
- *
- * @param ranges
- * @return
- */
- List<IntervalI> partitionNestedSublists(List<T> ranges)
- {
- List<IntervalI> sublists = new ArrayList<>();
-
- /*
- * sort by start ascending, length descending, so that
- * contained intervals follow their containing interval
- */
- Collections.sort(ranges, comparator);
-
- int listStartIndex = 0;
-
- IntervalI lastParent = ranges.get(0);
- boolean first = true;
-
- for (int i = 0, n = ranges.size(); i < n; i++)
- {
- IntervalI nextInterval = ranges.get(i);
- if (!first && !lastParent.properlyContainsInterval(nextInterval))
- {
- /*
- * this interval is not properly contained in the parent;
- * close off the last sublist
- */
- sublists.add(new Range(listStartIndex, i - 1));
- listStartIndex = i;
- lastParent = nextInterval;
- }
- first = false;
- }
-
- sublists.add(new Range(listStartIndex, ranges.size() - 1));
- return sublists;
- }
-}
+++ /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.Iterator;
-import java.util.List;
-import java.util.NoSuchElementException;
-
-import intervalstore.api.IntervalI;
-
-/**
- * Each node of the NCList tree consists of a range, and (optionally) the NCList
- * of ranges it encloses
- *
- * @param <T>
- */
-class NCNode<T extends IntervalI> implements IntervalI
-{
- /**
- * A depth-first iterator over the intervals stored in the NCNode. The
- * optional <code>remove</code> operation is not supported.
- *
- * @author gmcarstairs
- *
- */
- private class NCNodeIterator implements Iterator<T>
- {
- boolean first = true;
- Iterator<T> subregionIterator;
-
- @Override
- public boolean hasNext()
- {
- return first
- || (subregionIterator != null && subregionIterator.hasNext());
- }
-
- /**
- * Answers the next interval - initially the top level interval for this
- * node, thereafter the intervals returned by the NCList's iterator
- */
- @Override
- public T next()
- {
- if (first)
- {
- subregionIterator = subregions == null ? null
- : subregions.iterator();
- first = false;
- return region;
- }
- if (subregionIterator == null || !subregionIterator.hasNext())
- {
- throw new NoSuchElementException();
- }
- return subregionIterator.next();
- }
- }
-
- private T region;
-
- /*
- * null, or an object holding contained subregions of this nodes region
- */
- private NCList<T> subregions;
-
- /**
- * Constructor given a list of ranges. The list not be empty, and should be
- * ordered so that the first range contains all the others. If not, behaviour
- * will likely be invalid.
- *
- * @param ranges
- * @throws IllegalArgumentException
- * if the list is empty
- */
- NCNode(List<T> ranges)
- {
- if (ranges.isEmpty())
- {
- throw new IllegalArgumentException("List may not be empty");
- }
- region = ranges.get(0);
-
- if (ranges.size() > 1)
- {
- subregions = new NCList<>(ranges.subList(1, ranges.size()));
- }
- }
-
- /**
- * Constructor given a single range
- *
- * @param range
- */
- NCNode(T range)
- {
- region = range;
- }
-
- @Override
- public int getBegin()
- {
- return region.getBegin();
- }
-
- @Override
- public int getEnd()
- {
- return region.getEnd();
- }
-
- /**
- * Formats the node as a bracketed list e.g.
- *
- * <pre>
- * [1-100 [10-30 [10-20]], 15-30 [20-20]]
- * </pre>
- *
- * where the format for each interval is as given by <code>T.toString()</code>
- */
- @Override
- public String toString()
- {
- StringBuilder sb = new StringBuilder(10 * size());
- sb.append(region.toString());
- if (subregions != null)
- {
- sb.append(" ").append(subregions.toString());
- }
- return sb.toString();
- }
-
- void prettyPrint(StringBuilder sb, int offset, int indent)
- {
- for (int i = 0; i < offset; i++)
- {
- sb.append(" ");
- }
- sb.append(region.toString());
- if (subregions != null)
- {
- sb.append('\n');// System.lineSeparator());
- subregions.prettyPrint(sb, offset + 2, indent);
- }
- }
-
- /**
- * Add any ranges that overlap the from-to range to the result list
- *
- * @param from
- * @param to
- * @param result
- */
- void findOverlaps(long from, long to, List<T> result)
- {
- if (region.getBegin() <= to && region.getEnd() >= from)
- {
- result.add(region);
- if (subregions != null)
- {
- subregions.findOverlaps(from, to, result);
- }
- }
- }
-
- /**
- * Add one node to this node's subregions.
- *
- * @param entry
- * @throws IllegalArgumentException
- * if the added node is not contained by the node's start-end range
- */
- synchronized void addNode(NCNode<T> entry)
- {
- if (!region.containsInterval(entry))
- {
- throw new IllegalArgumentException(
- String.format("adding improper subrange %d-%d to range %d-%d",
- entry.getBegin(), entry.getEnd(), region.getBegin(),
- region.getEnd()));
- }
- if (subregions == null)
- {
- subregions = new NCList<>();
- }
-
- subregions.addNode(entry);
- }
-
- /**
- * Answers true if the data held satisfy the rules of construction of an
- * NCList, else false
- *
- * @return
- */
- boolean isValid()
- {
- /*
- * we don't handle reverse ranges
- */
- if (region != null && region.getBegin() > region.getEnd())
- {
- return false;
- }
- if (subregions == null)
- {
- return true;
- }
- if (subregions.isEmpty())
- {
- /*
- * we expect empty subregions to be nulled
- */
- return false;
- }
- return subregions.isValid(getBegin(), getEnd());
- }
-
- /**
- * Adds all contained entries to the given list
- *
- * @param entries
- */
- void getEntries(List<T> entries)
- {
- entries.add(region);
- if (subregions != null)
- {
- subregions.getEntries(entries);
- }
- }
-
- /**
- * Answers true if this object contains the given entry (by object equals
- * test), else false
- *
- * @param entry
- * @return
- */
- boolean contains(IntervalI entry)
- {
- if (entry == null)
- {
- return false;
- }
- if (entry.equals(region))
- {
- return true;
- }
- return subregions == null ? false : subregions.contains(entry);
- }
-
- /**
- * Answers the 'root' region modelled by this object
- *
- * @return
- */
- T getRegion()
- {
- return region;
- }
-
- /**
- * Answers the (possibly null) contained regions within this object
- *
- * @return
- */
- NCList<T> getSubRegions()
- {
- return subregions;
- }
-
- /**
- * Answers the (deep) size of this node i.e. the number of intervals it models
- *
- * @return
- */
- int size()
- {
- return subregions == null ? 1 : 1 + subregions.size();
- }
-
- /**
- * Answers the depth of NCNode / NCList nesting in the data tree
- *
- * @return
- */
- int getDepth()
- {
- return subregions == null ? 1 : 1 + subregions.getDepth();
- }
-
- /**
- * Answers an iterator over the intervals stored in this node. The iterator
- * does not support the optional <code>remove</code> operation (throws
- * <code>UnsupportedOperationException</code> if attempted).
- *
- * @return
- */
- public Iterator<T> iterator()
- {
- return new NCNodeIterator();
- }
-
- /**
- * Removes the first interval found equal to the given entry. Answers true if
- * a matching interval is found and removed, else false.
- *
- * @param entry
- * @return
- */
- boolean remove(T entry)
- {
- if (region.equals(entry))
- {
- /*
- * this case must be handled by NCList, to allow any
- * children of a deleted interval to be promoted
- */
- throw new IllegalArgumentException("NCNode can't remove self");
- }
- if (subregions == null)
- {
- return false;
- }
- if (subregions.remove(entry))
- {
- if (subregions.isEmpty())
- {
- subregions = null;
- }
- return true;
- }
- return false;
- }
-
- @SuppressWarnings("unchecked")
- @Override
- public boolean equals(Object o)
- {
- return o != null && o instanceof NCNode
- && equalsInterval((NCNode<T>) o);
- }
-
- @Override
- public boolean equalsInterval(IntervalI i)
- {
- return i != null && getBegin() == i.getBegin()
- && getEnd() == i.getEnd();
-
- }
-
-}
+++ /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 intervalstore.api.IntervalI;
-
-/**
- * An immutable data bean that models a start-end range
- */
-public class Range implements IntervalI
-{
-
- // no need for final here; these can be fully mutable as long as
- // store.revalidate() is run afterwords
-
- public int start;
-
- public int end;
-
-
- @Override
- public int getBegin()
- {
- return start;
- }
-
- @Override
- public int getEnd()
- {
- return end;
- }
-
- public Range(int i, int j)
- {
- start = i;
- end = j;
- }
-
- @Override
- public String toString()
- {
- return String.valueOf(start) + "-" + String.valueOf(end);
- }
-
- @Override
- public int hashCode()
- {
- return start * 31 + end;
- }
-
- @Override
- public boolean equals(Object o)
- {
- return (o != null && o instanceof Range && equalsInterval((Range) o));
- }
-
- @Override
- public boolean equalsInterval(IntervalI obj)
- {
-
- // override equalsInterval, not equals
- return (obj != null && start == ((Range) obj).start
- && end == ((Range) obj).end);
-
- }
-
- public void setStart(int pos)
- {
- start = pos;
- }
-
- public void setEnd(int pos)
- {
- end = pos;
- }
-
-
-}
+++ /dev/null
-/*
- * Copyright (c) 2009, 2013, Oracle and/or its affiliates. All rights reserved.
- * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
- *
- * This code is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License version 2 only, as
- * published by the Free Software Foundation. Oracle designates this
- * particular file as subject to the "Classpath" exception as provided
- * by Oracle in the LICENSE file that accompanied this code.
- *
- * This code is distributed in the hope that it will be useful, but WITHOUT
- * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
- * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
- * version 2 for more details (a copy is included in the LICENSE file that
- * accompanied this code).
- *
- * You should have received a copy of the GNU General Public License version
- * 2 along with this work; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
- *
- * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
- * or visit www.oracle.com if you need additional information or have any
- * questions.
- */
-
-package intervalstore.nonc;
-
-import intervalstore.api.IntervalI;
-
-/**
- * A dual pivot quicksort for int[] where the int is a pointer to something for
- * which the value needs to be checked. This class is not used; it was just an
- * idea I was trying. But it is sort of cool, so I am keeping it in the package
- * for possible future use.
- *
- * Adapted from Java 7 java.util.DualPivotQuicksort -- int[] only. The only
- * difference is that wherever an a[] value is compared, we use val(a[i])
- * instead of a[i] itself. Pretty straightforward. Could be adapted for general
- * use. Why didn't they do this in Java?
- *
- * val(i) is just a hack here, of course. A more general implementation might
- * use a Function call.
- *
- * Just thought it was cool that you can do this.
- *
- * @author Bob Hanson 2019.09.02
- *
- */
-
-class IntervalEndSorter
-{
-
- private IntervalI[] intervals;
-
- private int val(int i)
- {
- return intervals[i].getEnd();
- }
-
- /*
- * Tuning parameters.
- */
-
- /**
- * The maximum number of runs in merge sort.
- */
- private static final int MAX_RUN_COUNT = 67;
-
- /**
- * The maximum length of run in merge sort.
- */
- private static final int MAX_RUN_LENGTH = 33;
-
- /**
- * If the length of an array to be sorted is less than this constant,
- * Quicksort is used in preference to merge sort.
- */
- private static final int QUICKSORT_THRESHOLD = 286;
-
- /**
- * If the length of an array to be sorted is less than this constant,
- * insertion sort is used in preference to Quicksort.
- */
- private static final int INSERTION_SORT_THRESHOLD = 47;
-
- /*
- * Sorting methods for seven primitive types.
- */
-
- /**
- * Sorts the specified range of the array using the given workspace array
- * slice if possible for merging
- *
- * @param a
- * the array to be sorted
- * @param left
- * the index of the first element, inclusive, to be sorted
- * @param right
- * the index of the last element, inclusive, to be sorted
- * @param work
- * a workspace array (slice)
- * @param workBase
- * origin of usable space in work array
- * @param workLen
- * usable size of work array
- */
- void sort(int[] a, IntervalI[] intervals, int len)
- {
- this.intervals = intervals;
-
- int left = 0, right = len - 1;
- // Use Quicksort on small arrays
- if (right - left < QUICKSORT_THRESHOLD)
- {
- sort(a, left, right, true);
- return;
- }
-
- /*
- * Index run[i] is the start of i-th run
- * (ascending or descending sequence).
- */
- int[] run = new int[MAX_RUN_COUNT + 1];
- int count = 0;
- run[0] = left;
-
- // Check if the array is nearly sorted
- for (int k = left; k < right; run[count] = k)
- {
- switch (Integer.signum(val(a[k + 1]) - val(a[k])))
- {
- case 1:
- // ascending
- while (++k <= right && val(a[k - 1]) <= val(a[k]))
- ;
- break;
- case -1:
- // descending
- while (++k <= right && val(a[k - 1]) >= val(a[k]))
- ;
- for (int lo = run[count] - 1, hi = k; ++lo < --hi;)
- {
- int t = a[lo];
- a[lo] = a[hi];
- a[hi] = t;
- }
- break;
- default:
- // equal
- for (int m = MAX_RUN_LENGTH; ++k <= right
- && val(a[k - 1]) == val(a[k]);)
- {
- if (--m == 0)
- {
- sort(a, left, right, true);
- return;
- }
- }
- }
-
- /*
- * The array is not highly structured,
- * use Quicksort instead of merge sort.
- */
- if (++count == MAX_RUN_COUNT)
- {
- sort(a, left, right, true);
- return;
- }
- }
-
- // Check special cases
- // Implementation note: variable "right" is increased by 1.
- if (run[count] == right++)
- { // The last run contains one element
- run[++count] = right;
- }
- else if (count == 1)
- { // The array is already sorted
- return;
- }
-
- // Determine alternation base for merge
- byte odd = 0;
- for (int n = 1; (n <<= 1) < count; odd ^= 1)
- ;
-
- // Use or create temporary array b for merging
- int[] b; // temp array; alternates with a
- int ao, bo; // array offsets from 'left'
- int blen = right - left; // space needed for b
- int[] work = new int[blen];
- int workBase = 0;
- if (odd == 0)
- {
- System.arraycopy(a, left, work, workBase, blen);
- b = a;
- bo = 0;
- a = work;
- ao = workBase - left;
- }
- else
- {
- b = work;
- ao = 0;
- bo = workBase - left;
- }
-
- // Merging
- for (int last; count > 1; count = last)
- {
- for (int k = (last = 0) + 2; k <= count; k += 2)
- {
- int hi = run[k], mi = run[k - 1];
- for (int i = run[k - 2], p = i, q = mi; i < hi; ++i)
- {
- if (q >= hi || p < mi && val(a[p + ao]) <= val(a[q + ao]))
- {
- b[i + bo] = a[p++ + ao];
- }
- else
- {
- b[i + bo] = a[q++ + ao];
- }
- }
- run[++last] = hi;
- }
- if ((count & 1) != 0)
- {
- for (int i = right, lo = run[count - 1]; --i >= lo; b[i + bo] = a[i
- + ao])
- ;
- run[++last] = right;
- }
- int[] t = a;
- a = b;
- b = t;
- int o = ao;
- ao = bo;
- bo = o;
- }
- }
-
- /**
- * Sorts the specified range of the array by Dual-Pivot Quicksort.
- *
- * @param a
- * the array to be sorted
- * @param left
- * the index of the first element, inclusive, to be sorted
- * @param right
- * the index of the last element, inclusive, to be sorted
- * @param leftmost
- * indicates if this part is the leftmost in the range
- */
- private void sort(int[] a, int left, int right, boolean leftmost)
- {
- int length = right - left + 1;
-
- // Use insertion sort on tiny arrays
- if (length < INSERTION_SORT_THRESHOLD)
- {
- if (leftmost)
- {
- /*
- * Traditional (without sentinel) insertion sort,
- * optimized for server VM, is used in case of
- * the leftmost part.
- */
- for (int i = left, j = i; i < right; j = ++i)
- {
- int ai = a[i + 1];
- while (val(ai) < val(a[j]))
- {
- a[j + 1] = a[j];
- if (j-- == left)
- {
- break;
- }
- }
- a[j + 1] = ai;
- }
- }
- else
- {
- /*
- * Skip the longest ascending sequence.
- */
- do
- {
- if (left >= right)
- {
- return;
- }
- } while (val(a[++left]) >= val(a[left - 1]));
-
- /*
- * Every element from adjoining part plays the role
- * of sentinel, therefore this allows us to avoid the
- * left range check on each iteration. Moreover, we use
- * the more optimized algorithm, so called pair insertion
- * sort, which is faster (in the context of Quicksort)
- * than traditional implementation of insertion sort.
- */
- for (int k = left; ++left <= right; k = ++left)
- {
- int a1 = a[k], a2 = a[left];
-
- if (val(a1) < val(a2))
- {
- a2 = a1;
- a1 = a[left];
- }
- while (val(a1) < val(a[--k]))
- {
- a[k + 2] = a[k];
- }
- a[++k + 1] = a1;
-
- while (val(a2) < val(a[--k]))
- {
- a[k + 1] = a[k];
- }
- a[k + 1] = a2;
- }
- int last = a[right];
-
- while (val(last) < val(a[--right]))
- {
- a[right + 1] = a[right];
- }
- a[right + 1] = last;
- }
- return;
- }
-
- // Inexpensive approximation of length / 7
- int seventh = (length >> 3) + (length >> 6) + 1;
-
- /*
- * Sort five evenly spaced elements around (and including) the
- * center element in the range. These elements will be used for
- * pivot selection as described below. The choice for spacing
- * these elements was empirically determined to work well on
- * a wide variety of inputs.
- */
- int e3 = (left + right) >>> 1; // The midpoint
- int e2 = e3 - seventh;
- int e1 = e2 - seventh;
- int e4 = e3 + seventh;
- int e5 = e4 + seventh;
-
- // Sort these elements using insertion sort
- if (val(a[e2]) < val(a[e1]))
- {
- int t = a[e2];
- a[e2] = a[e1];
- a[e1] = t;
- }
-
- if (val(a[e3]) < val(a[e2]))
- {
- int t = a[e3];
- a[e3] = a[e2];
- a[e2] = t;
- if (val(t) < val(a[e1]))
- {
- a[e2] = a[e1];
- a[e1] = t;
- }
- }
- if (val(a[e4]) < val(a[e3]))
- {
- int t = a[e4];
- a[e4] = a[e3];
- a[e3] = t;
- int vt = val(t);
- if (vt < val(a[e2]))
- {
- a[e3] = a[e2];
- a[e2] = t;
- if (vt < val(a[e1]))
- {
- a[e2] = a[e1];
- a[e1] = t;
- }
- }
- }
- if (val(a[e5]) < val(a[e4]))
- {
- int t = a[e5];
- a[e5] = a[e4];
- a[e4] = t;
- int vt = val(t);
- if (vt < val(a[e3]))
- {
- a[e4] = a[e3];
- a[e3] = t;
- if (vt < val(a[e2]))
- {
- a[e3] = a[e2];
- a[e2] = t;
- if (vt < val(a[e1]))
- {
- a[e2] = a[e1];
- a[e1] = t;
- }
- }
- }
- }
-
- // Pointers
- int less = left; // The index of the first element of center part
- int great = right; // The index before the first element of right part
-
- if (val(a[e1]) != val(a[e2]) && val(a[e2]) != val(a[e3])
- && val(a[e3]) != val(a[e4]) && val(a[e4]) != val(a[e5]))
- {
- /*
- * Use the second and fourth of the five sorted elements as pivots.
- * These values are inexpensive approximations of the first and
- * second terciles of the array. Note that pivot1 <= pivot2.
- */
- int pivot1 = val(a[e2]);
- int pivot2 = val(a[e4]);
- int pivot1k = a[e2];
- int pivot2k = a[e4];
-
- /*
- * The first and the last elements to be sorted are moved to the
- * locations formerly occupied by the pivots. When partitioning
- * is complete, the pivots are swapped back into their final
- * positions, and excluded from subsequent sorting.
- */
- a[e2] = a[left];
- a[e4] = a[right];
-
- /*
- * Skip elements, which are less or greater than pivot values.
- */
- while (val(a[++less]) < pivot1)
- ;
- while (val(a[--great]) > pivot2)
- ;
-
- /*
- * Partitioning:
- *
- * left part center part right part
- * +--------------------------------------------------------------+
- * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
- * +--------------------------------------------------------------+
- * ^ ^ ^
- * | | |
- * less k great
- *
- * Invariants:
- *
- * all in (left, less) < pivot1
- * pivot1 <= all in [less, k) <= pivot2
- * all in (great, right) > pivot2
- *
- * Pointer k is the first index of ?-part.
- */
- outer: for (int k = less - 1; ++k <= great;)
- {
- int ak = a[k];
- if (val(ak) < pivot1)
- { // Move a[k] to left part
- a[k] = a[less];
- /*
- * Here and below we use "a[i] = b; i++;" instead
- * of "a[i++] = b;" due to performance issue.
- */
- a[less] = ak;
- ++less;
- }
- else if (val(ak) > pivot2)
- { // Move a[k] to right part
- while (val(a[great]) > pivot2)
- {
- if (great-- == k)
- {
- break outer;
- }
- }
- if (val(a[great]) < pivot1)
- { // a[great] <= pivot2
- a[k] = a[less];
- a[less] = a[great];
- ++less;
- }
- else
- { // pivot1 <= a[great] <= pivot2
- a[k] = a[great];
- }
- /*
- * Here and below we use "a[i] = b; i--;" instead
- * of "a[i--] = b;" due to performance issue.
- */
- a[great] = ak;
- --great;
- }
- }
-
- // Swap pivots into their final positions
- a[left] = a[less - 1];
- a[less - 1] = pivot1k;
- a[right] = a[great + 1];
- a[great + 1] = pivot2k;
-
- // Sort left and right parts recursively, excluding known pivots
- sort(a, left, less - 2, leftmost);
- sort(a, great + 2, right, false);
-
- /*
- * If center part is too large (comprises > 4/7 of the array),
- * swap internal pivot values to ends.
- */
- if (less < e1 && e5 < great)
- {
- /*
- * Skip elements, which are equal to pivot values.
- */
- while (val(a[less]) == pivot1)
- {
- ++less;
- }
-
- while (val(a[great]) == pivot2)
- {
- --great;
- }
-
- /*
- * Partitioning:
- *
- * left part center part right part
- * +----------------------------------------------------------+
- * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
- * +----------------------------------------------------------+
- * ^ ^ ^
- * | | |
- * less k great
- *
- * Invariants:
- *
- * all in (*, less) == pivot1
- * pivot1 < all in [less, k) < pivot2
- * all in (great, *) == pivot2
- *
- * Pointer k is the first index of ?-part.
- */
- outer: for (int k = less - 1; ++k <= great;)
- {
- int ak = a[k];
- if (val(ak) == pivot1)
- { // Move a[k] to left part
- a[k] = a[less];
- a[less] = ak;
- ++less;
- }
- else if (val(ak) == pivot2)
- { // Move a[k] to right part
- while (val(a[great]) == pivot2)
- {
- if (great-- == k)
- {
- break outer;
- }
- }
- if (val(a[great]) == pivot1)
- { // a[great] < pivot2
- a[k] = a[less];
- /*
- * Even though a[great] equals to pivot1, the
- * assignment a[less] = pivot1 may be incorrect,
- * if a[great] and pivot1 are floating-point zeros
- * of different signs. Therefore in float and
- * double sorting methods we have to use more
- * accurate assignment a[less] = a[great].
- */
- a[less] = pivot1k;
- ++less;
- }
- else
- { // pivot1 < a[great] < pivot2
- a[k] = a[great];
- }
- a[great] = ak;
- --great;
- }
- }
- }
-
- // Sort center part recursively
- sort(a, less, great, false);
-
- }
- else
- { // Partitioning with one pivot
- /*
- * Use the third of the five sorted elements as pivot.
- * This value is inexpensive approximation of the median.
- */
- int pivot = val(a[e3]);
-
- /*
- * Partitioning degenerates to the traditional 3-way
- * (or "Dutch National Flag") schema:
- *
- * left part center part right part
- * +-------------------------------------------------+
- * | < pivot | == pivot | ? | > pivot |
- * +-------------------------------------------------+
- * ^ ^ ^
- * | | |
- * less k great
- *
- * Invariants:
- *
- * all in (left, less) < pivot
- * all in [less, k) == pivot
- * all in (great, right) > pivot
- *
- * Pointer k is the first index of ?-part.
- */
- for (int k = less; k <= great; ++k)
- {
- if (val(a[k]) == pivot)
- {
- continue;
- }
- int ak = a[k];
- if (val(ak) < pivot)
- { // Move a[k] to left part
- a[k] = a[less];
- a[less] = ak;
- ++less;
- }
- else
- { // a[k] > pivot - Move a[k] to right part
- while (val(a[great]) > pivot)
- {
- --great;
- }
- if (val(a[great]) < pivot)
- { // a[great] <= pivot
- a[k] = a[less];
- a[less] = a[great];
- ++less;
- }
- else
- { // a[great] == pivot
- /*
- * Even though a[great] equals to pivot, the
- * assignment a[k] = pivot may be incorrect,
- * if a[great] and pivot are floating-point
- * zeros of different signs. Therefore in float
- * and double sorting methods we have to use
- * more accurate assignment a[k] = a[great].
- */
- // So, guess what?
- //
- // Actually, we do need a[great] for IntervalStore,
- // because here, two, the numbers are not necessarily the same item
- //
- // a[k] = pivot;
- a[k] = a[great];
- }
- a[great] = ak;
- --great;
- }
- }
-
- /*
- * Sort left and right parts recursively.
- * All elements from center part are equal
- * and, therefore, already sorted.
- */
- sort(a, left, less - 1, leftmost);
- sort(a, great + 1, right, false);
- }
- }
-
-}
Comparator<? super IntervalI> comparator, boolean bigendian)
{
icompare = (comparator != null ? comparator
- : bigendian ? IntervalI.COMPARATOR_BIGENDIAN
- : IntervalI.COMPARATOR_LITTLEENDIAN);
+ : bigendian ? IntervalI.COMPARE_BEGIN_ASC_END_DESC
+ : IntervalI.COMPARE_BEGIN_ASC_END_ASC);
this.bigendian = bigendian;
if (intervals != null)
}
/**
- * Adds one interval to the store, allowing duplicates.
+ * Adds one interval to the store, allowing duplicates
*
* @param interval
*/
else
{
index = findInterval(interval);
- // System.out.println("index = " + index + " for " + interval + "\n"
- // + Arrays.toString(intervals) + "\n"
- // + Arrays.toString(offsets));
if (!allowDuplicates && index >= 0)
{
return false;
int pt0 = pt;
while (--pt >= 0 && offsets[pt] == 0)
{
- ;
+
}
if (pt < 0)
{
case 0:
IntervalI iv = intervals[mid];
if ((bsIgnore == null || !bsIgnore.get(mid))
- && iv.equalsInterval(interval))
+ && sameInterval(interval, iv))
{
return mid;
// found one; just scan up and down now, first checking the range, but
break;
}
if ((bsIgnore == null || !bsIgnore.get(i))
- && iv.equalsInterval(interval))
+ && sameInterval(interval, iv))
{
return i;
}
return -1 - ++i;
}
if ((bsIgnore == null || !bsIgnore.get(i))
- && iv.equalsInterval(interval))
+ && sameInterval(interval, iv))
{
return i;
}
return -1 - start;
}
- @Override
- public boolean canCheckForDuplicates()
+ /**
+ * Answers true if the two intervals are equal (as determined by
+ * {@code i1.equals(i2)}, else false
+ *
+ * @param i1
+ * @param i2
+ * @return
+ */
+ static boolean sameInterval(IntervalI i1, IntervalI i2)
{
- return true;
+ /*
+ * for speed, do the fast check for begin/end equality before
+ * the equals check which includes type checking
+ */
+ return i1.equalsInterval(i2) && i1.equals(i2);
}
/**
}
/**
- * return the i-th interval in the designated order (bigendian or
- * littleendian)
- */
- @Override
- public IntervalI get(int i)
- {
- if (i < 0 || i >= intervalCount + added)
- {
- return null;
- }
- ensureFinalized();
- return intervals[i];
- }
-
- /**
* Return the deepest level of nesting.
*
*/
}
/**
- * Get the number of root-level nests.
- *
- */
- @Override
- public int getWidth()
- {
- ensureFinalized();
- // System.out.println(
- // "ISList w[0]=" + nestCounts[0] + " w[1]=" + nestCounts[1]);
- return nestCounts[0] + (createUnnested ? nestCounts[1] : 0);
- }
-
- @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
{
sb.append(sep).append(nests[pt + i].toString());
if (nestCounts[pt + i] > 0)
+ {
dump(pt + i, sb, sep + " ");
+ }
}
}
@Override
public synchronized boolean remove(Object o)
{
- // if (o == null)
- // {
- // throw new NullPointerException();
- // }
return (o != null && intervalCount > 0
&& removeInterval((IntervalI) o));
}
case -1:
break;
case 0:
- if (iv.equalsInterval(interval))
+ if (sameInterval(interval, iv))
{
return pt;
}
else
{
int i = intervalCount;
- while (--i >= 0 && !intervals[i].equalsInterval(interval))
+ while (--i >= 0 && !sameInterval(intervals[i], interval))
{
- ;
+
}
return i;
}
* Recreate the key nest arrays.
*
*/
- @Override
public boolean revalidate()
{
isTainted = true;
int beginLast2 = beginLast;
// Phase One: Get the temporary container array myContainer.
-
for (int i = 1; i < intervalCount; i++)
{
int pt = i - 1;
public class IntervalStore0<T extends IntervalI>
extends AbstractCollection<T> implements IntervalStoreI<T>
{
+ private static int NOT_CONTAINED = Integer.MIN_VALUE;
/**
* Search for the last interval that starts before or at the specified from/to
}
DO_PRESORT = presort;
icompare = (comparator != null ? comparator
- : bigendian ? IntervalI.COMPARATOR_BIGENDIAN
- : IntervalI.COMPARATOR_LITTLEENDIAN);
+ : bigendian ? IntervalI.COMPARE_BEGIN_ASC_END_DESC
+ : IntervalI.COMPARE_BEGIN_ASC_END_ASC);
this.bigendian = bigendian;
if (DO_PRESORT && intervalCount > 1)
@Override
public boolean add(T interval)
{
- return add(interval, true);
+ return add(interval, false);
}
/**
int pt0 = pt;
while (--pt >= 0 && offsets[pt] == 0)
{
- ;
+
}
if (pt < 0)
{
case 0:
IntervalI iv = intervals[mid];
if ((bsIgnore == null || !bsIgnore.get(mid))
- && iv.equalsInterval(interval))
+ && sameInterval(interval, iv))
{
return mid;
// found one; just scan up and down now, first checking the range, but
break;
}
if ((bsIgnore == null || !bsIgnore.get(i))
- && iv.equalsInterval(interval))
+ && sameInterval(interval, iv))
{
return i;
}
return -1 - ++i;
}
if ((bsIgnore == null || !bsIgnore.get(i))
- && iv.equalsInterval(interval))
+ && sameInterval(interval, iv))
{
return i;
}
return -1 - start;
}
- // private int binaryInsertionSearch(long from, long to)
- // {
- // int matched = intervalCount;
- // int end = matched - 1;
- // int start = matched;
- // if (end < 0 || from > intervals[end].getEnd()
- // || from < intervals[start = 0].getBegin())
- // return start;
- // while (start <= end)
- // {
- // int mid = (start + end) >>> 1;
- // switch (compareRange(intervals[mid], from, to))
- // {
- // case 0:
- // return mid;
- // case 1:
- // matched = mid;
- // end = mid - 1;
- // continue;
- // case -1:
- // start = mid + 1;
- // continue;
- // }
- //
- // }
- // return matched;
- // }
+ boolean sameInterval(IntervalI i1, IntervalI i2)
+ {
+ /*
+ * do the quick test of begin/end first for speed
+ */
+ return i1.equalsInterval(i2) && i1.equals(i2);
+ }
@Override
public void clear()
return result;
}
- @Override
- public IntervalI get(int i)
- {
- if (i < 0 || i >= intervalCount + added)
- {
- return null;
- }
- ensureFinalized();
- return intervals[i];
- }
-
private int getContainedBy(int index, int begin)
{
while (index >= 0)
}
index -= Math.abs(offsets[index]);
}
- return IntervalI.NOT_CONTAINED;
+ return NOT_CONTAINED;
}
@Override
for (int i = 0; i < intervalCount; i++)
{
IntervalI element = intervals[i];
- if (offsets[i] == IntervalI.NOT_CONTAINED)
+ if (offsets[i] == NOT_CONTAINED)
{
root = element;
}
return maxDepth;
}
- @Override
- public int getWidth()
- {
- ensureFinalized();
- int w = 0;
- for (int i = offsets.length; --i >= 0;)
- {
- if (offsets[i] > 0)
- {
- w++;
- }
- }
- return w;
- }
-
- @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
return;
}
maxEnd = intervals[0].getEnd();
- offsets[0] = IntervalI.NOT_CONTAINED;
+ offsets[0] = NOT_CONTAINED;
if (intervalCount == 1)
{
return;
// System.out.println(sf + " is contained by "
// + (index < 0 ? null : starts[index]));
- offsets[i] = (index < 0 ? IntervalI.NOT_CONTAINED
+ offsets[i] = (index < 0 ? NOT_CONTAINED
: isMonotonic ? index - i : i - index);
isMonotonic = (sf.getEnd() > maxEnd);
if (isMonotonic)
case -1:
break;
case 0:
- if (iv.equalsInterval(interval))
+ if (sameInterval(interval, iv))
{
return pt;
}
else
{
int i = intervalCount;
- while (--i >= 0 && !intervals[i].equalsInterval(interval))
+ while (--i >= 0 && !sameInterval(intervals[i], interval))
{
- ;
+
}
return i;
}
}
@Override
- public boolean revalidate()
- {
- isTainted = true;
- isSorted = false;
- ensureFinalized();
- return true;
- }
-
- @Override
public int size()
{
return intervalCount + added - deleted;
{
return prettyPrint();
}
-
- @Override
- public boolean canCheckForDuplicates()
- {
- return true;
- }
-
}
public boolean hasHidden();
/**
- * Get the visible-column bitset, possibly containing hidden columns (which
- * may or may not be hidden in the overview).
+ * Get the bitset where a set bit indicates a column to be shown
*
* @return a BitSet
*/
- public BitSet getOverviewBitSet();
+ public BitSet getShownBitSet();
/**
* Get the hidden-column bitset, (which may or may not be hidden in the
private boolean nucleotide = true;
+ private List<AlignedCodonFrame> codonFrameList;
+
+ private static final SequenceGroup[] noGroups = new SequenceGroup[0];
+
+ /*
+ * persistent object to hold result of findAllGroups(SequenceI)
+ */
+ private List<SequenceGroup> groupsForSequence = new ArrayList<>();
+
public boolean hasRNAStructure = false;
public AlignmentAnnotation[] annotations;
public Hashtable alignmentProperties;
- private List<AlignedCodonFrame> codonFrameList;
-
private void initAlignment(SequenceI[] seqs)
{
groups = Collections.synchronizedList(new ArrayList<SequenceGroup>());
return null;
}
- private static final SequenceGroup[] noGroups = new SequenceGroup[0];
-
- private ArrayList<SequenceGroup> temp = new ArrayList<>();
-
/*
* (non-Javadoc)
*
@Override
public SequenceGroup[] findAllGroups(SequenceI s)
{
-
synchronized (groups)
{
int gSize = groups.size();
{
return noGroups;
}
- temp.clear();
+ groupsForSequence.clear();
for (int i = 0; i < gSize; i++)
{
SequenceGroup sg = groups.get(i);
if (sg.getSequences().contains(s))
{
- temp.add(sg);
+ groupsForSequence.add(sg);
}
}
}
- SequenceGroup[] ret = new SequenceGroup[temp.size()];
- return temp.toArray(ret);
+ SequenceGroup[] ret = new SequenceGroup[groupsForSequence.size()];
+ return groupsForSequence.toArray(ret);
}
/** */
}
/**
- * return ALL columns, not just the truly visible ones
+ * Returns all columns, including any hidden in the alignment
*/
@Override
- public BitSet getOverviewBitSet()
+ public BitSet getShownBitSet()
{
if (bsVisible == null)
{
*/
private int changeCount;
+ /*
+ * cached rgb colours for each position of the aligned sequence (column)
+ */
+ private int[] argb;
+
/**
* Creates a new Sequence object.
*
return sequenceFeatureStore.add(sf);
}
- /**
- * @param sf
- * A known feature of this featureStore
- */
@Override
public void deleteFeature(SequenceFeature sf)
{
_isNa = Comparison.isNucleotide(this);
}
return !_isNa;
- };
+ }
/*
* (non-Javadoc)
List<SequenceFeature> result = getFeatures().findFeatures(startPos,
endPos, types);
- // if (datasetSequence != null)
- // {
- // result = datasetSequence.getFeatures().findFeatures(startPos, endPos,
- // types);
- // }
- // else
- // {
- // result = sequenceFeatureStore.findFeatures(startPos, endPos, types);
- // }
/*
* if end column is gapped, endPos may be to the right,
return 0;
}
- private int[] argb;
-
@Override
public int getColor(int i)
{
}
/**
- * @author Bob Hanson 2019.07.30
- *
- * allows passing the result ArrayList as a parameter to avoid
- * unnecessary construction
- * @return result (JavaScript) or new ArrayList (Java -- see FeatureRender)
- *
+ * Answers a (possibly empty) list of features of the specified type that
+ * overlap the specified column position. If parameter {@code result} is not
+ * null, features are appended to it and the (possibly extended) list is
+ * returned.
*/
@Override
public List<SequenceFeature> findFeatures(int column, String type,
result);
}
- /**
- * allows early intervention for renderer if this returns false
- */
@Override
public boolean hasFeatures(String type)
{
import java.util.TreeMap;
import java.util.Vector;
-import intervalstore.api.IntervalI;
-
/**
* A class that models a single contiguous feature on a sequence. If flag
* 'contactFeature' is true, the start and end positions are interpreted instead
public boolean equals(Object o)
{
return (o != null && (o instanceof SequenceFeature)
- && equalsInterval((SequenceFeature) o));
+ && equals(((SequenceFeature) o), false));
}
/**
- * Having determined that this is in fact a SequenceFeature, now check it for
- * equivalence. Overridden in CrossRef; used by IntervalStore (possibly).
- */
- @Override
- public boolean equalsInterval(IntervalI sf)
- {
- return sf != null && equals((SequenceFeature) sf, false);
- }
- /**
* Overloaded method allows the equality test to optionally ignore the
* 'Parent' attribute of a feature. This supports avoiding adding many
* superficially duplicate 'exon' or CDS features to genomic or protein
*/
public boolean addSequenceFeature(SequenceFeature sf);
+ /**
+ * Deletes the feature from the sequence (if found). To be precise, deletes
+ * the first feature {@code f} found where {@code f.equals(sf)}.
+ *
+ * @param sf
+ */
public void deleteFeature(SequenceFeature sf);
public void setDatasetSequence(SequenceI seq);
public void resetColors();
/**
- * allows passing the result ArrayList as a parameter to avoid unnecessary
- * construction
- *
- * @author Bob Hanson 2019.07.30
- *
- *
+ * Answers a (possibly empty) list of features of the specified type that
+ * overlap the specified column position. If parameter {@code result} is not
+ * null, features are appended to it and the (possibly extended) list is
+ * returned.
*/
List<SequenceFeature> findFeatures(int column, String type,
List<SequenceFeature> result);
/**
- * allows early intervention for renderer if false
- *
- * @author Bob Hanson 2019.07.30
+ * Answers true if this store contains at least one feature, else false
*
+ * @return
*/
public boolean hasFeatures(String type);
* Only the visible columns.
*/
@Override
- public BitSet getOverviewBitSet()
+ public BitSet getShownBitSet()
{
if (bsVisible == null)
{
import java.util.Set;
import intervalstore.api.IntervalStoreI;
+import intervalstore.impl.BinarySearcher;
+import intervalstore.impl.BinarySearcher.Compare;
-public abstract class FeatureStore implements FeatureStoreI
+public class FeatureStore
{
-
- /**
+ /*
* track last start for quick insertion of ordered features
*/
protected int lastStart = -1;
* @param feature
* @return
*/
- @Override
public boolean listContains(List<SequenceFeature> list,
SequenceFeature feature)
{
return false;
}
- return (getEquivalentFeatureIndex(list, feature) >= 0);
- }
-
- /**
- * Binary search for the index (>= 0) of a feature in a list.
- *
- * @param list
- * @param feature
- * @return index if found; -1 if not
- */
- protected int getEquivalentFeatureIndex(List<SequenceFeature> list,
- SequenceFeature feature)
- {
-
/*
* locate the first entry in the list which does not precede the feature
*/
int begin = feature.begin;
- int pos = findFirstBegin(list, begin);
+ int pos = BinarySearcher.findFirst(list, true, Compare.GE, begin);
int len = list.size();
while (pos < len)
{
SequenceFeature sf = list.get(pos);
if (sf.begin > begin)
{
- return -1; // no match found
+ return false; // no match found
}
if (sf.equals(feature))
{
- return pos;
+ return true;
}
pos++;
}
- return -1;
+ return false;
}
/**
*/
public FeatureStore(int intervalStoreType)
{
- features = getIntervalStore(intervalStoreType);
+ features =
+ // Platform.isJS()
+ // ? new intervalstore.nonc.IntervalStore<>(true)
+ // : new intervalstore.impl.IntervalStore<>();
+ getIntervalStore(intervalStoreType);
positionalFeatureGroups = new HashSet<>();
nonPositionalFeatureGroups = new HashSet<>();
positionalMinScore = Float.NaN;
private IntervalStoreI<SequenceFeature> getIntervalStore(int type)
{
switch (type != INTERVAL_STORE_DEFAULT ? type : //
- Platform.isJS() //
- ? intervalStoreJSOption
- : intervalStoreJavaOption)
+ Platform.isJS() //
+ ? intervalStoreJSOption
+ : intervalStoreJavaOption)
{
default:
case INTERVAL_STORE_NCLIST_OBJECT:
* insert into list sorted by start (first contact position):
* binary search the sorted list to find the insertion point
*/
- contactFeatureStarts.add(
- findFirstBegin(contactFeatureStarts, feature.begin), feature);
+ int insertAt = BinarySearcher.findFirst(contactFeatureStarts, true,
+ Compare.GE, feature.begin);
+ contactFeatureStarts.add(insertAt, feature);
/*
* insert into list sorted by end (second contact position):
* binary search the sorted list to find the insertion point
*
* @param feature
*/
-
- @Override
public boolean addFeature(SequenceFeature feature)
{
- // if (contains(feature))
- // {
- // return false;
- // }
-
- // /*
- // * keep a record of feature groups
- // */
- // if (!feature.isNonPositional())
- // {
- // positionalFeatureGroups.add(feature.getFeatureGroup());
- // }
-
if (feature.isContactFeature())
{
if (containsContactFeature(feature))
}
else if (feature.isNonPositional())
{
- if (containsNonPositional(feature))
+ if (containsNonPositionalFeature(feature))
{
return false;
}
}
else
{
- // allow for check with
- if (checkContainsPositionalFeatureForAdd(feature)
- || !addPositionalFeature(feature))
+ if (!features.add(feature, false))
{
return false;
}
}
/**
- * Adds one feature to the IntervalStore that can manage nested features
- * (creating the IntervalStore if necessary)
- *
- * @return true if added -- allowing for late checking during addition
- */
- abstract protected boolean addPositionalFeature(SequenceFeature feature);
-
- /**
* Adds the feature to the list of non-positional features (with lazy
* instantiation of the list if it is null), and returns true. The feature
* group is added to the set of distinct feature groups for non-positional
* @param feature
* @return
*/
- @Override
public boolean contains(SequenceFeature feature)
{
if (feature.isNonPositional())
{
- return containsNonPositional(feature);
-
+ return containsNonPositionalFeature(feature);
}
if (feature.isContactFeature())
{
return containsContactFeature(feature);
-
}
return containsPositionalFeature(feature);
}
- /**
- * A check that can be overridden if the check is being done during the add
- * operation itself.
- *
- * @param feature
- * @return
- */
- protected boolean checkContainsPositionalFeatureForAdd(
- SequenceFeature feature)
- {
- return containsPositionalFeature(feature);
- }
-
private boolean containsPositionalFeature(SequenceFeature feature)
{
return features == null || feature.begin > lastStart ? false
- : containsFeature(feature);
+ : features.contains(feature);
}
+ /**
+ * Answers true if this store already contains a contact feature equal to the
+ * given feature (by {@code SequenceFeature.equals()} test), else false
+ *
+ * @param feature
+ * @return
+ */
private boolean containsContactFeature(SequenceFeature feature)
{
return contactFeatureStarts != null && feature.begin <= lastContactStart
&& listContains(contactFeatureStarts, feature);
}
- private boolean containsNonPositional(SequenceFeature feature)
+ /**
+ * Answers true if this store already contains a non-positional feature equal
+ * to the given feature (by {@code SequenceFeature.equals()} test), else false
+ *
+ * @param feature
+ * @return
+ */
+ private boolean containsNonPositionalFeature(SequenceFeature feature)
{
return nonPositionalFeatures == null ? false
: nonPositionalFeatures.contains(feature);
}
- abstract protected boolean containsFeature(SequenceFeature feature);
-
/**
* Deletes the given feature from the store, returning true if it was found
* (and deleted), else false. This method makes no assumption that the feature
*
* @param sf
*/
-
- @Override
public synchronized boolean delete(SequenceFeature sf)
{
boolean removed = false;
*/
if (!removed && features != null)
{
- removed = findAndRemoveNonContactFeature(sf);
+ removed = features.remove(sf);
}
if (removed)
return removed;
}
- abstract protected boolean findAndRemoveNonContactFeature(SequenceFeature sf);
-
- abstract protected void findContactFeatures(long from, long to,
- List<SequenceFeature> result);
-
- abstract protected int findFirstBegin(List<SequenceFeature> list,
- long pos);
-
- abstract protected int findFirstEnd(List<SequenceFeature> list, long pos);
-
- @Override
public List<SequenceFeature> findOverlappingFeatures(long start, long end)
{
return findOverlappingFeatures(start, end, null);
}
- @Override
public List<SequenceFeature> getContactFeatures()
{
return getContactFeatures(new ArrayList<>());
*
* @return
*/
-
- @Override
public List<SequenceFeature> getContactFeatures(
List<SequenceFeature> result)
{
* @param positional
* @return
*/
-
- @Override
public int getFeatureCount(boolean positional)
{
if (!positional)
return (contactFeatureStarts == null ? 0 : contactFeatureStarts.size())
+ features.size();
-
}
/**
* @param positionalFeatures
* @return
*/
-
- @Override
public Set<String> getFeatureGroups(boolean positionalFeatures)
{
if (positionalFeatures)
}
}
- @Override
public Collection<SequenceFeature> getFeatures()
{
return features;
* @param group
* @return
*/
-
- @Override
public List<SequenceFeature> getFeaturesForGroup(boolean positional,
String group)
{
* @param positional
* @return
*/
-
- @Override
public float getMaximumScore(boolean positional)
{
return positional ? positionalMaxScore : nonPositionalMaxScore;
* @param positional
* @return
*/
-
- @Override
public float getMinimumScore(boolean positional)
{
return positional ? positionalMinScore : nonPositionalMinScore;
}
- @Override
public List<SequenceFeature> getNonPositionalFeatures()
{
return getNonPositionalFeatures(new ArrayList<>());
*
* @return
*/
-
- @Override
public List<SequenceFeature> getNonPositionalFeatures(
List<SequenceFeature> result)
{
return result;
}
- @Override
public List<SequenceFeature> getPositionalFeatures()
{
return getPositionalFeatures(new ArrayList<>());
*
* @return
*/
-
- @Override
public List<SequenceFeature> getPositionalFeatures(
List<SequenceFeature> result)
{
*
* @return
*/
-
- @Override
public int getTotalFeatureLength()
{
return totalExtent;
*
* @return
*/
-
- @Override
public boolean isEmpty()
{
boolean hasFeatures = (contactFeatureStarts != null
* @param shiftBy
* @return
*/
-
- @Override
public synchronized boolean shiftFeatures(int fromPosition, int shiftBy)
{
/*
return modified;
}
+ /**
+ * Answers the position (0, 1...) in the list of the first entry whose end
+ * position is not less than {@ pos}. If no such entry is found, answers the
+ * length of the list.
+ *
+ * @param list
+ * @param pos
+ * @return
+ */
+ protected int findFirstEnd(List<SequenceFeature> list, long pos)
+ {
+ return BinarySearcher.findFirst(list, false, Compare.GE, (int) pos);
+ }
+
+ /**
+ * Adds contact features to the result list where either the second or the
+ * first contact position lies within the target range
+ *
+ * @param from
+ * @param to
+ * @param result
+ */
+ protected void findContactFeatures(long from, long to,
+ List<SequenceFeature> result)
+ {
+ if (contactFeatureStarts != null)
+ {
+ findContactStartOverlaps(from, to, result);
+ findContactEndOverlaps(from, to, result);
+ }
+ }
+
+ /**
+ * Adds to the result list any contact features whose end (second contact
+ * point), but not start (first contact point), lies in the query from-to
+ * range
+ *
+ * @param from
+ * @param to
+ * @param result
+ */
+ private void findContactEndOverlaps(long from, long to,
+ List<SequenceFeature> result)
+ {
+ /*
+ * find the first contact feature (if any)
+ * whose end point is not before the target range
+ */
+ int index = findFirstEnd(contactFeatureEnds, from);
+
+ int n = contactFeatureEnds.size();
+ while (index < n)
+ {
+ SequenceFeature sf = contactFeatureEnds.get(index);
+ if (!sf.isContactFeature())
+ {
+ System.err.println("Error! non-contact feature type " + sf.getType()
+ + " in contact features list");
+ index++;
+ continue;
+ }
+
+ int begin = sf.getBegin();
+ if (begin >= from && begin <= to)
+ {
+ /*
+ * this feature's first contact position lies in the search range
+ * so we don't include it in results a second time
+ */
+ index++;
+ continue;
+ }
+
+ if (sf.getEnd() > to)
+ {
+ /*
+ * this feature (and all following) has end point after the target range
+ */
+ break;
+ }
+
+ /*
+ * feature has end >= from and end <= to
+ * i.e. contact end point lies within overlap search range
+ */
+ result.add(sf);
+ index++;
+ }
+ }
+
+ /**
+ * Adds contact features whose start position lies in the from-to range to the
+ * result list
+ *
+ * @param from
+ * @param to
+ * @param result
+ */
+ private void findContactStartOverlaps(long from, long to,
+ List<SequenceFeature> result)
+ {
+ int index = BinarySearcher.findFirst(contactFeatureStarts, true,
+ Compare.GE, (int) from);
+
+ while (index < contactFeatureStarts.size())
+ {
+ SequenceFeature sf = contactFeatureStarts.get(index);
+ if (!sf.isContactFeature())
+ {
+ System.err.println("Error! non-contact feature " + sf.toString()
+ + " in contact features list");
+ index++;
+ continue;
+ }
+ if (sf.getBegin() > to)
+ {
+ /*
+ * this feature's start (and all following) follows the target range
+ */
+ break;
+ }
+
+ /*
+ * feature has begin >= from and begin <= to
+ * i.e. contact start point lies within overlap search range
+ */
+ result.add(sf);
+ index++;
+ }
+ }
+
+ /**
+ * Returns a (possibly empty) list of features whose extent overlaps the given
+ * range. The returned list is not ordered. Contact features are included if
+ * either of the contact points lies within the range. If the {@code result}
+ * parameter is not null, new entries are added to this list and the (possibly
+ * extended) list returned.
+ *
+ * @param start
+ * start position of overlap range (inclusive)
+ * @param end
+ * end position of overlap range (inclusive)
+ * @param result
+ * @return
+ */
+ public List<SequenceFeature> findOverlappingFeatures(long start, long end,
+ List<SequenceFeature> result)
+ {
+ if (result == null)
+ {
+ result = new ArrayList<>();
+ }
+
+ findContactFeatures(start, end, result);
+ features.findOverlaps(start, end, result);
+
+ return result;
+ }
+
}
+++ /dev/null
-package jalview.datamodel.features;
-
-import jalview.datamodel.SequenceFeature;
-
-import java.util.Collection;
-import java.util.List;
-import java.util.Set;
-
-public interface FeatureStoreI
-{
-
- boolean addFeature(SequenceFeature feature);
-
- boolean contains(SequenceFeature feature);
-
- boolean delete(SequenceFeature sf);
-
- List<SequenceFeature> findOverlappingFeatures(long start, long end);
-
- List<SequenceFeature> findOverlappingFeatures(long start, long end,
- List<SequenceFeature> result);
-
- List<SequenceFeature> getContactFeatures();
-
- List<SequenceFeature> getContactFeatures(List<SequenceFeature> result);
-
- int getFeatureCount(boolean positional);
-
- Set<String> getFeatureGroups(boolean positionalFeatures);
-
- Collection<SequenceFeature> getFeatures();
-
- List<SequenceFeature> getFeaturesForGroup(boolean positional,
- String group);
-
- float getMaximumScore(boolean positional);
-
- float getMinimumScore(boolean positional);
-
- List<SequenceFeature> getNonPositionalFeatures();
-
- List<SequenceFeature> getNonPositionalFeatures(
- List<SequenceFeature> result);
-
- List<SequenceFeature> getPositionalFeatures();
-
- List<SequenceFeature> getPositionalFeatures(List<SequenceFeature> result);
-
- int getTotalFeatureLength();
-
- boolean isEmpty();
-
- boolean shiftFeatures(int fromPosition, int shiftBy);
-
- boolean listContains(List<SequenceFeature> features,
- SequenceFeature feature);
-
-}
+++ /dev/null
-/*
- * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
- * Copyright (C) $$Year-Rel$$ The Jalview Authors
- *
- * This file is part of Jalview.
- *
- * Jalview is free software: you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation, either version 3
- * of the License, or (at your option) any later version.
- *
- * Jalview is distributed in the hope that it will be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty
- * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
- * PURPOSE. See the GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with Jalview. If not, see <http://www.gnu.org/licenses/>.
- * The Jalview Authors are detailed in the 'AUTHORS' file.
- */
-package jalview.datamodel.features;
-
-import jalview.datamodel.SequenceFeature;
-
-import java.util.ArrayList;
-import java.util.List;
-
-import intervalstore.impl.BinarySearcher;
-
-/**
- * A data store for a set of sequence features that supports efficient lookup of
- * features overlapping a given range. Intended for (but not limited to) storage
- * of features for one sequence and feature type.
- *
- * @author gmcarstairs
- *
- */
-public class FeatureStoreImpl extends FeatureStore
-{
-
- public FeatureStoreImpl()
- {
- super();
- }
-
- public FeatureStoreImpl(int option)
- {
- super(option);
- }
-
- /**
- * Add a contact feature to the lists that hold them ordered by start (first
- * contact) and by end (second contact) position, ensuring the lists remain
- * ordered, and returns true. This method allows duplicate features to be
- * added, so test before calling to avoid this.
- *
- * @param feature
- * @return
- */
- @Override
- protected synchronized boolean addContactFeature(SequenceFeature feature)
- {
- if (contactFeatureStarts == null)
- {
- contactFeatureStarts = new ArrayList<>();
- contactFeatureEnds = new ArrayList<>();
- }
-
- /*
- * insert into list sorted by start (first contact position):
- * binary search the sorted list to find the insertion point
- */
- int insertPosition = findFirstBegin(contactFeatureStarts,
- feature.getBegin());
- contactFeatureStarts.add(insertPosition, feature);
-
- /*
- * insert into list sorted by end (second contact position):
- * binary search the sorted list to find the insertion point
- */
- insertPosition = findFirstEnd(contactFeatureEnds,
- feature.getEnd());
- contactFeatureEnds.add(insertPosition, feature);
-
- return true;
- }
-
- /**
- * Adds one feature to the IntervalStore that can manage nested features
- * (creating the IntervalStore if necessary)
- */
- @Override
- protected synchronized boolean addPositionalFeature(
- SequenceFeature feature)
- {
- return features.add(feature);
- }
-
- /**
- * Adds contact features to the result list where either the second or the
- * first contact position lies within the target range
- *
- * @param from
- * @param to
- * @param result
- */
- @Override
- protected void findContactFeatures(long from, long to,
- List<SequenceFeature> result)
- {
- if (contactFeatureStarts != null)
- {
- findContactStartOverlaps(from, to, result);
- findContactEndOverlaps(from, to, result);
- }
- }
-
- @Override
- protected boolean containsFeature(SequenceFeature feature)
- {
- return features.contains(feature);
- }
-
- /**
- * Adds to the result list any contact features whose end (second contact
- * point), but not start (first contact point), lies in the query from-to
- * range
- *
- * @param from
- * @param to
- * @param result
- */
-
- private void findContactEndOverlaps(long from, long to,
- List<SequenceFeature> result)
- {
- /*
- * find the first contact feature (if any)
- * whose end point is not before the target range
- */
- int index = findFirstEnd(contactFeatureEnds, from);
-
- int n = contactFeatureEnds.size();
- while (index < n)
- {
- SequenceFeature sf = contactFeatureEnds.get(index);
- if (!sf.isContactFeature())
- {
- System.err.println("Error! non-contact feature type " + sf.getType()
- + " in contact features list");
- index++;
- continue;
- }
-
- int begin = sf.getBegin();
- if (begin >= from && begin <= to)
- {
- /*
- * this feature's first contact position lies in the search range
- * so we don't include it in results a second time
- */
- index++;
- continue;
- }
-
- if (sf.getEnd() > to)
- {
- /*
- * this feature (and all following) has end point after the target range
- */
- break;
- }
-
- /*
- * feature has end >= from and end <= to
- * i.e. contact end point lies within overlap search range
- */
- result.add(sf);
- index++;
- }
- }
-
- /**
- * Adds contact features whose start position lies in the from-to range to the
- * result list
- *
- * @param from
- * @param to
- * @param result
- */
-
- private void findContactStartOverlaps(long from, long to,
- List<SequenceFeature> result)
- {
- int index = findFirstBegin(contactFeatureStarts, from);
-
- while (index < contactFeatureStarts.size())
- {
- SequenceFeature sf = contactFeatureStarts.get(index);
- if (!sf.isContactFeature())
- {
- System.err.println("Error! non-contact feature " + sf.toString()
- + " in contact features list");
- index++;
- continue;
- }
- if (sf.getBegin() > to)
- {
- /*
- * this feature's start (and all following) follows the target range
- */
- break;
- }
-
- /*
- * feature has begin >= from and begin <= to
- * i.e. contact start point lies within overlap search range
- */
- result.add(sf);
- index++;
- }
- }
-
- /**
- * Returns a (possibly empty) list of features whose extent overlaps the given
- * range. The returned list is not ordered. Contact features are included if
- * either of the contact points lies within the range.
- *
- * @param start
- * start position of overlap range (inclusive)
- * @param end
- * end position of overlap range (inclusive)
- * @param result
- * ignored
- * @return
- */
-
- @Override
- public List<SequenceFeature> findOverlappingFeatures(long start, long end,
- List<SequenceFeature> result)
- {
- result = new ArrayList<>();
- findContactFeatures(start, end, result);
- findOverlaps(start, end, result);
- return result;
- }
-
- private void findOverlaps(long start, long end,
- List<SequenceFeature> result)
- {
- result.addAll(features
- .findOverlaps(start, end));
- }
-
- @Override
- protected int findFirstBegin(List<SequenceFeature> list, long pos)
- {
- return BinarySearcher.findFirst(list, (int) pos,
- BinarySearcher.fbegin);
- }
-
- @Override
- protected int findFirstEnd(List<SequenceFeature> list, long pos)
- {
- return BinarySearcher.findFirst(list, (int) pos, BinarySearcher.fend);
- }
-
- @Override
- protected boolean findAndRemoveNonContactFeature(SequenceFeature sf)
- {
- return features.remove(sf);
- }
-
-}
+++ /dev/null
-/*
- * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
- * Copyright (C) $$Year-Rel$$ The Jalview Authors
- *
- * This file is part of Jalview.
- *
- * Jalview is free software: you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation, either version 3
- * of the License, or (at your option) any later version.
- *
- * Jalview is distributed in the hope that it will be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty
- * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
- * PURPOSE. See the GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with Jalview. If not, see <http://www.gnu.org/licenses/>.
- * The Jalview Authors are detailed in the 'AUTHORS' file.
- */
-package jalview.datamodel.features;
-
-import jalview.datamodel.SequenceFeature;
-
-import java.util.ArrayList;
-import java.util.List;
-
-/**
- * An adaption of FeatureStore that is efficient and lightweight, accelerating
- * processing speed in JavaScript.
- *
- * It could be used in Java as well, with significant acceleration, but all this
- * is so fast anyway that it probably will not be noticed in Java to speed it up
- * by a factor of two or three. So for now, at least, this implementation is
- * just in JavaScript. The flag for this is in SequenceFeatures.
- *
- * This implementation uses the IntervalStore developed by Bob Hanson, found at
- * https://github.com/BobHanson/IntervalStoreJ, forked from the one developed by
- * Mungo Carstairs at https://github.com/bartongroup/IntervalStoreJ.
- *
- * See the discussion folder at https://github.com/BobHanson/IntervalStoreJ for
- * details.
- *
- * @author gmcarstairs
- * @author Bob Hanson 2019.08.03-2019.08.16
- *
- */
-public class FeatureStoreJS extends FeatureStore
-{
-
-
- public FeatureStoreJS()
- {
- super();
- }
-
- public FeatureStoreJS(int option)
- {
- super(option);
- }
-
- /**
- * Add a contact feature to the lists that hold them ordered by start (first
- * contact) and by end (second contact) position, ensuring the lists remain
- * ordered. This method allows duplicate features to be added, so test before
- * calling to avoid this.
- *
- * @param feature
- * @return true
- */
- @Override
- protected synchronized boolean addContactFeature(SequenceFeature feature)
- {
- if (contactFeatureStarts == null)
- {
- contactFeatureStarts = new ArrayList<>();
- contactFeatureEnds = new ArrayList<>();
- }
- contactFeatureStarts.add(
- findFirstBegin(contactFeatureStarts, feature.begin), feature);
- contactFeatureEnds.add(findFirstEnd(contactFeatureEnds, feature.end),
- feature);
- return true;
- }
-
- /**
- * Add a feature to the IntervalStore, not allowing for duplicates.
- *
- *
- * @return false if could not add it (late check for duplicate)
- */
- @Override
- protected synchronized boolean addPositionalFeature(
- SequenceFeature feature)
- {
- return features.add(feature, false);
- }
-
- /**
- * Initial check in FeatureStore.add(feature) that in other implementations
- * does a containment check, but in this implementation just returns false to
- * indicate that we should continue. This implementation will do this check as
- * part of the add() method for greater efficiency (one binary search instead
- * of two).
- *
- * @return false -- meaning "maybe not contained; continue adding"
- */
- @Override
- protected boolean checkContainsPositionalFeatureForAdd(
- SequenceFeature feature)
- {
- return false;
- }
-
- /**
- * Check to see if a feature (or its equivalent based on
- * IntervalI.equalsInterval) is already in this store. This method should be
- * avoided except when necessary, as it involves a binary search with identity
- * check.
- *
- * @return true if this feature or its equivalent (based on equalsInterval) is
- * present already in the collection.
- */
- @Override
- protected boolean containsFeature(SequenceFeature feature)
- {
- return features.contains(feature);
- }
-
- @Override
- protected boolean findAndRemoveNonContactFeature(SequenceFeature sf)
- {
- return features.remove(sf);
- }
-
- /**
- * Add contact features to the result list where either the second or the
- * first contact position lies within the target range, inclusively.
- *
- * @param from
- * @param to
- * @param result
- */
- @Override
- protected void findContactFeatures(long from, long to,
- List<SequenceFeature> result)
- {
- getContactStartOverlaps(from, to, result);
- getContactEndOverlaps(from, to, result);
- }
-
- /**
- * Locate the first feature start in a standard ArrayList that is at or after
- * this position.
- *
- */
-
- @Override
- protected int findFirstBegin(List<SequenceFeature> list, long pos)
- {
- int matched = list.size();
- int end = matched - 1;
- int start = (end < 0 || list.get(end).begin < pos ? matched : 0);
- while (start <= end)
- {
- int mid = (start + end) / 2;
- if (list.get(mid).begin >= pos)
- {
- matched = mid;
- end = mid - 1;
- }
- else
- {
- start = mid + 1;
- }
- }
- return matched;
- }
-
- /**
- * Locate the feature end in a standard ArrayList that is after or at this
- * position.
- *
- */
-
- @Override
- protected int findFirstEnd(List<SequenceFeature> list, long pos)
- {
- int matched = list.size();
- int end = matched - 1;
- int start = 0;
- while (start <= end)
- {
- int mid = (start + end) / 2;
- if (list.get(mid).end >= pos)
- {
- matched = mid;
- end = mid - 1;
- }
- else
- {
- start = mid + 1;
- }
- }
- return matched;
- }
-
- /**
- * Returns a (possibly empty) list of features whose extent overlaps the given
- * range. The returned list is ordered as follows:
- *
- * (1) ContactFeature starts
- *
- * (2) ContactFeature ends (that are not also starts)
- *
- * (3) noncontact SequenceFeatures, in reverse start order
- *
- * (This last reverse order is for efficiency in processing only.)
- *
- *
- *
- * @param start
- * start position of overlap range (inclusive)
- * @param end
- * end position of overlap range (inclusive)
- *
- * @param result
- * optional result list; for highest efficiency, provide this
- * parameter
- * @return result same as result parameter, or a new ArrayList if that is null
- */
-
- @Override
- public List<SequenceFeature> findOverlappingFeatures(long start, long end,
- List<SequenceFeature> result)
- {
- if (result == null)
- {
- result = new ArrayList<>();
- }
- if (contactFeatureStarts != null)
- {
- if (start == end)
- {
- getContactPointStarts(contactFeatureStarts, start, result);
- getContactPointEnds(contactFeatureEnds, end, result);
- }
- else
- {
- findContactFeatures(start, end, result);
- }
- }
- if (features.size() > 0)
- {
- features.findOverlaps(start, end, result);
- }
- return result;
- }
-
- /**
- * Adds to the result list any contact features having end (second contact
- * point), but not start (first contact point), in the query from-to range
- *
- * @param from
- * @param to
- * @param result
- */
-
- private void getContactEndOverlaps(long from, long to,
- List<SequenceFeature> result)
- {
- // find the first contact feature (if any)
- // with end point not before the target range
-
- for (int i = findFirstEnd(contactFeatureEnds,
- from), n = contactFeatureEnds.size(); i < n; i++)
- {
- SequenceFeature sf = contactFeatureEnds.get(i);
- if (sf.begin >= from && sf.begin <= to)
- {
- // this feature's first contact position lies in the search range
- // so we don't include it in results a second time
- continue;
- }
-
- if (sf.end > to)
- {
- // this feature (and all following) has end point after the target range
- break;
- }
-
- // feature has end >= from and end <= to
- // i.e. contact end point lies within overlap search range
- result.add(sf);
- }
- }
-
- /**
- * Binary search for contact start or end matching a specific position. This
- * efficient search was designed specifically for rapid return for the
- * OverviewPanel. It's implementation sped processing of that panel by 2300%.
- *
- * @param l
- * @param pos
- * @param result
- * @param isStart
- *
- * @author Bob Hanson 2019.07.30
- */
- private void getContactPointStarts(List<SequenceFeature> l, long pos,
- List<SequenceFeature> result)
- {
- int low = 0;
- int high = l.size() - 1;
- while (low <= high)
- {
- int mid = (low + high) >>> 1;
- SequenceFeature f = l.get(mid);
- switch (Long.signum(f.begin - pos))
- {
- case -1:
- low = mid + 1;
- continue;
- case 1:
- high = mid - 1;
- continue;
- case 0:
- int m = mid;
- result.add(f);
- // could be "5" in 12345556788 ?
- while (++mid <= high && (f = l.get(mid)) != null && f.begin == pos)
- {
- result.add(f);
- }
- while (--m >= low && (f = l.get(m)) != null && f.begin == pos)
- {
- result.add(f);
- }
- return;
- }
- }
- }
-
- private void getContactPointEnds(List<SequenceFeature> l, long pos,
- List<SequenceFeature> result)
- {
- int low = 0;
- int high = l.size() - 1;
- while (low <= high)
- {
- int mid = (low + high) >>> 1;
- SequenceFeature f = l.get(mid);
- switch (Long.signum(f.end - pos))
- {
- case -1:
- low = mid + 1;
- continue;
- case 1:
- high = mid - 1;
- continue;
- case 0:
- int m = mid;
- if (f.begin != f.end)
- {
- result.add(f);
- }
- // could be "5" in 12345556788 ?
- while (++mid <= high && (f = l.get(mid)) != null
- && f.end == pos)
- {
- if (f.begin != f.end)
- {
- result.add(f);
- }
- }
- while (--m >= low && (f = l.get(m)) != null
- && f.end == pos)
- {
- if (f.begin != f.end)
- {
- result.add(f);
- }
- }
- return;
- }
- }
- }
-
- /**
- * Adds contact features whose start position lies in the from-to range to the
- * result list
- *
- * @param from
- * @param to
- * @param result
- */
-
- private void getContactStartOverlaps(long from, long to,
- List<SequenceFeature> result)
- {
- for (int i = findFirstBegin(contactFeatureStarts,
- from), n = contactFeatureStarts.size(); i < n; i++)
- {
- SequenceFeature sf = contactFeatureStarts.get(i);
- if (sf.begin > to)
- {
- break;
- }
- result.add(sf);
- }
- }
-}
import jalview.datamodel.SequenceFeature;
import jalview.io.gff.SequenceOntologyFactory;
import jalview.io.gff.SequenceOntologyI;
-import jalview.util.Platform;
import java.util.ArrayList;
import java.util.Arrays;
+import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
*/
public class SequenceFeatures implements SequenceFeaturesI
{
-
/*
* map from feature type to structured store of features for that type
* null types are permitted (but not a good idea!)
*/
- private Map<String, FeatureStoreI> featureStore;
+ private Map<String, FeatureStore> featureStore;
/**
* Constructor
* ? wrap as a synchronized map for add and delete operations
*/
// featureStore = Collections
- // .synchronizedSortedMap(new TreeMap<String, FeatureStoreI>());
+ // .synchronizedSortedMap(new TreeMap<String, FeatureStore>());
featureStore = new TreeMap<>();
}
if (featureStore.get(type) == null)
{
- featureStore.put(type, newFeatureStore());
+ featureStore.put(type, new FeatureStore());
}
return featureStore.get(type).addFeature(sf);
}
- private FeatureStoreI newFeatureStore()
- {
- return (//
- Platform.isJS()//
- ? new FeatureStoreJS()
- : new FeatureStoreImpl());
- }
-
/**
* {@inheritDoc}
*/
String... type)
{
List<SequenceFeature> result = new ArrayList<>();
- for (FeatureStoreI featureSet : varargToTypes(type))
+ for (FeatureStore featureSet : varargToTypes(type))
{
- // System.err.println("SF findFeature " + System.currentTimeMillis()
- // + " " + from + " " + to + " "
- // + featureSet.getPositionalFeatures().get(0).type);
- //
- result.addAll(featureSet.findOverlappingFeatures(from, to, null));
+ featureSet.findOverlappingFeatures(from, to, result);
}
return result;
}
{
int result = 0;
- for (FeatureStoreI featureSet : varargToTypes(type))
+ for (FeatureStore featureSet : varargToTypes(type))
{
result += featureSet.getFeatureCount(positional);
}
{
int result = 0;
- for (FeatureStoreI featureSet : varargToTypes(type))
+ for (FeatureStore featureSet : varargToTypes(type))
{
result += featureSet.getTotalFeatureLength();
}
{
List<SequenceFeature> result = new ArrayList<>();
- for (FeatureStoreI featureSet : varargToTypes(type))
+ for (FeatureStore featureSet : varargToTypes(type))
{
featureSet.getPositionalFeatures(result);
}
* @param type
* @return
*/
- protected Iterable<FeatureStoreI> varargToTypes(String... type)
+ protected Iterable<FeatureStore> varargToTypes(String... type)
{
if (type == null || type.length == 0)
{
return featureStore.values();
}
- List<FeatureStoreI> types = new ArrayList<>();
+ List<FeatureStore> types = new ArrayList<>();
List<String> args = Arrays.asList(type);
- for (Entry<String, FeatureStoreI> featureType : featureStore.entrySet())
+ for (Entry<String, FeatureStore> featureType : featureStore.entrySet())
{
if (args.contains(featureType.getKey()))
{
{
List<SequenceFeature> result = new ArrayList<>();
- for (FeatureStoreI featureSet : varargToTypes(type))
+ for (FeatureStore featureSet : varargToTypes(type))
{
featureSet.getContactFeatures(result);
}
{
List<SequenceFeature> result = new ArrayList<>();
- for (FeatureStoreI featureSet : varargToTypes(type))
+ for (FeatureStore featureSet : varargToTypes(type))
{
featureSet.getNonPositionalFeatures(result);
}
@Override
public boolean delete(SequenceFeature sf)
{
- for (FeatureStoreI featureSet : featureStore.values())
+ for (FeatureStore featureSet : featureStore.values())
{
if (featureSet.delete(sf))
{
@Override
public boolean hasFeatures()
{
- for (FeatureStoreI featureSet : featureStore.values())
+ for (FeatureStore featureSet : featureStore.values())
{
if (!featureSet.isEmpty())
{
{
Set<String> groups = new HashSet<>();
- for (FeatureStoreI featureSet : varargToTypes(type))
+ for (FeatureStore featureSet : varargToTypes(type))
{
groups.addAll(featureSet.getFeatureGroups(positionalFeatures));
}
{
Set<String> result = new HashSet<>();
- for (Entry<String, FeatureStoreI> featureType : featureStore.entrySet())
+ for (Entry<String, FeatureStore> featureType : featureStore.entrySet())
{
Set<String> featureGroups = featureType.getValue()
.getFeatureGroups(positionalFeatures);
public Set<String> getFeatureTypes(String... soTerm)
{
Set<String> types = new HashSet<>();
- for (Entry<String, FeatureStoreI> entry : featureStore.entrySet())
+ for (Entry<String, FeatureStore> entry : featureStore.entrySet())
{
String type = entry.getKey();
if (!entry.getValue().isEmpty() && isOntologyTerm(type, soTerm))
public static void sortFeatures(List<? extends IntervalI> features,
final boolean forwardStrand)
{
- IntervalI.sortIntervals(features, forwardStrand);
+ Collections.sort(features,
+ forwardStrand ? IntervalI.COMPARE_BEGIN_ASC
+ : IntervalI.COMPARE_END_DESC);
}
/**
String group, String... type)
{
List<SequenceFeature> result = new ArrayList<>();
- for (FeatureStoreI featureSet : varargToTypes(type))
+ for (FeatureStore featureSet : varargToTypes(type))
{
if (featureSet.getFeatureGroups(positional).contains(group))
{
public boolean shiftFeatures(int fromPosition, int shiftBy)
{
boolean modified = false;
- for (FeatureStoreI fs : featureStore.values())
+ for (FeatureStore fs : featureStore.values())
{
modified |= fs.shiftFeatures(fromPosition, shiftBy);
}
featureStore.clear();
}
- /**
- * Simplified find for features associated with a given position.
- *
- * JavaScript set to not use IntervalI, but easily testable by setting false
- * to true in javadoc
- *
- * FeatureRenderer has checked already that featureStore does contain type.
- *
- * @author Bob Hanson 2019.07.30
- */
@Override
public List<SequenceFeature> findFeatures(int pos, String type,
List<SequenceFeature> list)
{
- FeatureStoreI fs = featureStore.get(type);
+ FeatureStore fs = featureStore.get(type);
return fs.findOverlappingFeatures(pos, pos, list);
}
- // Chrome; developer console closed
-
- // BH 2019.08.01 useIntervalStore true, redraw false:
- // Platform: timer mark 13.848 0.367 overviewrender 16000 pixels row:14
- // Platform: timer mark 15.391 0.39 overviewrender 16000 pixels row:14
- // Platform: timer mark 16.498 0.39 overviewrender 16000 pixels row:14
- // Platform: timer mark 17.596 0.401 overviewrender 16000 pixels row:14
- // Platform: timer mark 18.738 0.363 overviewrender 16000 pixels row:14
- // Platform: timer mark 19.659 0.358 overviewrender 16000 pixels row:14
- // Platform: timer mark 20.737 0.359 overviewrender 16000 pixels row:14
- // Platform: timer mark 21.797 0.391 overviewrender 16000 pixels row:14
- // Platform: timer mark 22.851 0.361 overviewrender 16000 pixels row:14
- // Platform: timer mark 24.019 0.395 overviewrender 16000 pixels row:14
-
- // BH 2019.08.01 useIntervalStore false, redraw false:
- // Platform: timer mark 19.011 0.181 overviewrender 16000 pixels row:14
- // Platform: timer mark 20.311 0.183 overviewrender 16000 pixels row:14
- // Platform: timer mark 21.368 0.175 overviewrender 16000 pixels row:14
- // Platform: timer mark 22.347 0.178 overviewrender 16000 pixels row:14
- // Platform: timer mark 23.605 0.216 overviewrender 16000 pixels row:14
- // Platform: timer mark 24.836 0.191 overviewrender 16000 pixels row:14
- // Platform: timer mark 26.016 0.181 overviewrender 16000 pixels row:14
- // Platform: timer mark 27.278 0.178 overviewrender 16000 pixels row:14
- // Platform: timer mark 28.158 0.181 overviewrender 16000 pixels row:14
- // Platform: timer mark 29.227 0.196 overviewrender 16000 pixels row:14
- // Platform: timer mark 30.1 0.171 overviewrender 16000 pixels row:14
- // Platform: timer mark 31.684 0.196 overviewrender 16000 pixels row:14
- // Platform: timer mark 32.779 0.18 overviewrender 16000 pixels row:14
- // Platform: timer mark 52.355 0.185 overviewrender 16000 pixels row:14
- // Platform: timer mark 53.829 0.186 overviewrender 16000 pixels row:14
-
- /**
- * @author Bob Hanson 2019.08.01
- */
@Override
public boolean hasFeatures(String type)
{
void deleteAll();
/**
- * Point-specific parameter return for JavaScript
+ * Answers a (possibly empty) list of features of the specified type that
+ * overlap the specified column position. If parameter {@code result} is not
+ * null, features are appended to it and the (possibly extended) list is
+ * returned.
*
* @param pos
* @param type
* @param result
- * @return result (JavaScript) or new ArrayList (Java -- see FeatureRender)
- * @author Bob Hanson 2019.07.30
+ * @return
*/
List<SequenceFeature> findFeatures(int pos, String type, List<SequenceFeature> result);
/**
- * @author Bob Hanson 2019.08.01
- *
- * @param type
- * @return true if this type is in featureStore
+ * Answers true if there are any features of the given type, else false
*/
boolean hasFeatures(String type);
}
import jalview.datamodel.SequenceI;
import jalview.io.gff.SequenceOntologyI;
import jalview.util.JSONUtils;
-import jalview.util.Platform;
-import java.io.BufferedReader;
import java.io.IOException;
import java.net.MalformedURLException;
import java.net.URL;
List<String> queries = new ArrayList<>();
queries.add(query);
SequenceI seq = parseFeaturesJson(queries);
- if (seq == null)
- return null;
return new Alignment(new SequenceI[] { seq });
-
}
/**
WritableRaster raster = miniMe.getRaster();
DataBufferInt db = (DataBufferInt) raster.getDataBuffer();
pixels = db.getBankData()[0];
- bscol = cols.getOverviewBitSet();
+ bscol = cols.getShownBitSet();
if (skippingColumns)
{
columnsToShow = calcColumnsToShow();
public class OverviewResColourFinder extends ResidueColourFinder
{
+ public static final Color OVERVIEW_DEFAULT_GAP = Color.lightGray;
+
+ public static final Color OVERVIEW_DEFAULT_LEGACY_GAP = Color.white;
+
+ public static final Color OVERVIEW_DEFAULT_HIDDEN = Color.darkGray
+ .darker();
+
final int GAP_COLOUR; // default colour to use at gaps
final int RESIDUE_COLOUR; // default colour to use at residues
boolean useLegacy = false;
- public static final Color OVERVIEW_DEFAULT_GAP = Color.lightGray;
-
- public static final Color OVERVIEW_DEFAULT_LEGACY_GAP = Color.white;
-
- public static final Color OVERVIEW_DEFAULT_HIDDEN = Color.darkGray
- .darker();
-
/**
* Constructor without colour settings (used by applet)
*/
// if there's a FeatureColourFinder we might override the residue colour
// here with feature colouring
- return seq.setColor(i,
- finder == null || finder.noFeaturesDisplayed() ? col
- : finder.findFeatureColourInt(col, seq, i));
+ col = finder == null || finder.noFeaturesDisplayed() ? col
+ : finder.findFeatureColourInt(col, seq, i);
+ return seq.setColor(i, col);
}
/**
public int findFeatureColourInt(int defaultColour, SequenceI seq,
int column)
{
- // if (noFeaturesDisplayed())
- // {
- // return defaultColour;
- // }
-
Graphics g = null;
/*
private static final AlphaComposite NO_TRANSPARENCY = AlphaComposite
.getInstance(AlphaComposite.SRC_OVER, 1.0f);
+ /*
+ * persistent list used by JalviewJS; not threadsafe for Java
+ */
+ private List<SequenceFeature> overlaps = (Platform.isJS()
+ ? new ArrayList<>()
+ : null);
+
/**
* Constructor given a viewport
*
@Override
public Color findFeatureColour(SequenceI seq, int column, Graphics g)
{
- // BH 2019.08.01
- // this is already checked in FeatureColorFinder
- // if (!av.isShowSequenceFeatures())
- // {
- // return null;
- // }
-
// column is 'base 1' but getCharAt is an array index (ie from 0)
if (Comparison.isGap(seq.getCharAt(column - 1)))
{
* applies), or null if no feature is drawn in the range given.
*
* @param g
- * the graphics context to draw on (may be null only if t == 1 from
- * colourOnly==true)
+ * the graphics context to draw on (null if no transparency applies)
* @param seq
* @param start
* start column
final SequenceI seq, int start, int end, int y1,
boolean colourOnly)
{
- // from SeqCanvas and OverviewRender
/*
* if columns are all gapped, or sequence has no features, nothing to do
*/
updateFeatures();
- if (transparency != 1f) // g cannot be null here if trans == 1f - BH // && g
- // != null)
+ if (transparency != 1f)
{
((Graphics2D) g).setComposite(
AlphaComposite.getInstance(AlphaComposite.SRC_OVER,
findAllFeatures();
}
- private List<SequenceFeature> overlaps = (Platform.isJS()
- ? new ArrayList<>()
- : null);
-
/**
* Returns the sequence feature colour rendered at the given column position,
* or null if none found. The feature of highest render order (i.e. on top) is
* colour for features enclosing a gapped column. Check for gap before calling
* if different behaviour is wanted.
*
- * BH 2019.07.30
- *
- * Adds a result ArrayList to parameters in order to avoid an unnecessary
- * construction of that for every pixel checked.
- *
- *
* @param seq
* @param column
* (1..)
continue;
}
+ /*
+ * field overlaps is used by JalviewJS to avoid object creation;
+ * not thread-safe for Java (Javascript is single-threaded)
+ */
if (overlaps != null)
{
overlaps.clear();
--- /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 static org.testng.Assert.assertEquals;
+import static org.testng.Assert.assertFalse;
+import static org.testng.Assert.assertSame;
+import static org.testng.Assert.assertTrue;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.testng.annotations.Test;
+
+public class IntervalStoreTest
+{
+ @Test(groups = "Functional")
+ public void testFindOverlaps_nonNested()
+ {
+ IntervalStore<SimpleFeature> store = new IntervalStore<>();
+ SimpleFeature sf1 = add(store, 10, 20);
+ // same range different description
+ SimpleFeature sf2 = new SimpleFeature(10, 20, "desc");
+ store.add(sf2);
+ SimpleFeature sf3 = add(store, 15, 25);
+ SimpleFeature sf4 = add(store, 20, 35);
+
+ assertEquals(store.size(), 4);
+ List<SimpleFeature> overlaps = store.findOverlaps(1, 9);
+ assertTrue(overlaps.isEmpty());
+
+ overlaps = store.findOverlaps(8, 10);
+ assertEquals(overlaps.size(), 2);
+ assertTrue(overlaps.contains(sf1));
+ assertTrue(overlaps.contains(sf2));
+
+ overlaps = store.findOverlaps(12, 16);
+ assertEquals(overlaps.size(), 3);
+ assertTrue(overlaps.contains(sf1));
+ assertTrue(overlaps.contains(sf2));
+ assertTrue(overlaps.contains(sf3));
+
+ overlaps = store.findOverlaps(33, 33);
+ assertEquals(overlaps.size(), 1);
+ assertTrue(overlaps.contains(sf4));
+
+ /*
+ * ensure edge cases are covered
+ */
+ overlaps = store.findOverlaps(35, 40);
+ assertEquals(overlaps.size(), 1);
+ assertTrue(overlaps.contains(sf4));
+ assertTrue(store.findOverlaps(36, 100).isEmpty());
+ assertTrue(store.findOverlaps(1, 9).isEmpty());
+ }
+
+ @Test(groups = "Functional")
+ public void testFindOverlaps_nested()
+ {
+ IntervalStore<SimpleFeature> store = new IntervalStore<>();
+ SimpleFeature sf1 = add(store, 10, 50);
+ SimpleFeature sf2 = add(store, 10, 40);
+ SimpleFeature sf3 = add(store, 20, 30);
+ // feature at same location but different description
+ SimpleFeature sf4 = new SimpleFeature(20, 30, "different desc");
+ store.add(sf4);
+ SimpleFeature sf5 = add(store, 35, 36);
+
+ List<SimpleFeature> overlaps = store.findOverlaps(1, 9);
+ assertTrue(overlaps.isEmpty());
+
+ overlaps = store.findOverlaps(10, 15);
+ assertEquals(overlaps.size(), 2);
+ assertTrue(overlaps.contains(sf1));
+ assertTrue(overlaps.contains(sf2));
+
+ overlaps = store.findOverlaps(45, 60);
+ assertEquals(overlaps.size(), 1);
+ assertTrue(overlaps.contains(sf1));
+
+ overlaps = store.findOverlaps(32, 38);
+ assertEquals(overlaps.size(), 3);
+ assertTrue(overlaps.contains(sf1));
+ assertTrue(overlaps.contains(sf2));
+ assertTrue(overlaps.contains(sf5));
+
+ overlaps = store.findOverlaps(15, 25);
+ assertEquals(overlaps.size(), 4);
+ assertTrue(overlaps.contains(sf1));
+ assertTrue(overlaps.contains(sf2));
+ assertTrue(overlaps.contains(sf3));
+ assertTrue(overlaps.contains(sf4));
+ }
+
+ @Test(groups = "Functional")
+ public void testFindOverlaps_mixed()
+ {
+ IntervalStore<SimpleFeature> store = new IntervalStore<>();
+ SimpleFeature sf1 = add(store, 10, 50);
+ SimpleFeature sf2 = add(store, 1, 15);
+ SimpleFeature sf3 = add(store, 20, 30);
+ SimpleFeature sf4 = add(store, 40, 100);
+ SimpleFeature sf5 = add(store, 60, 100);
+ SimpleFeature sf6 = add(store, 70, 70);
+
+ List<SimpleFeature> overlaps = store.findOverlaps(200, 200);
+ assertTrue(overlaps.isEmpty());
+
+ overlaps = store.findOverlaps(1, 9);
+ assertEquals(overlaps.size(), 1);
+ assertTrue(overlaps.contains(sf2));
+
+ overlaps = store.findOverlaps(5, 18);
+ assertEquals(overlaps.size(), 2);
+ assertTrue(overlaps.contains(sf1));
+ assertTrue(overlaps.contains(sf2));
+
+ overlaps = store.findOverlaps(30, 40);
+ assertEquals(overlaps.size(), 3);
+ assertTrue(overlaps.contains(sf1));
+ assertTrue(overlaps.contains(sf3));
+ assertTrue(overlaps.contains(sf4));
+
+ overlaps = store.findOverlaps(80, 90);
+ assertEquals(overlaps.size(), 2);
+ assertTrue(overlaps.contains(sf4));
+ assertTrue(overlaps.contains(sf5));
+
+ overlaps = store.findOverlaps(68, 70);
+ assertEquals(overlaps.size(), 3);
+ assertTrue(overlaps.contains(sf4));
+ assertTrue(overlaps.contains(sf5));
+ assertTrue(overlaps.contains(sf6));
+ }
+
+ /**
+ * Helper method to add a feature with type "desc"
+ *
+ * @param store
+ * @param from
+ * @param to
+ * @return
+ */
+ SimpleFeature add(IntervalStore<SimpleFeature> store, int from,
+ int to)
+ {
+ SimpleFeature sf1 = new SimpleFeature(from, to, "desc");
+ store.add(sf1);
+ return sf1;
+ }
+
+ @Test(groups = "Functional")
+ public void testRemove()
+ {
+ IntervalStore<SimpleFeature> store = new IntervalStore<>();
+ SimpleFeature sf1 = add(store, 10, 20);
+ assertTrue(store.contains(sf1));
+
+ try
+ {
+ store.remove("what is this?");
+ } catch (ClassCastException e)
+ {
+ // expected;
+ }
+ assertFalse(store.remove(null));
+
+ /*
+ * simple deletion
+ */
+ assertTrue(store.remove(sf1));
+ assertTrue(store.isEmpty());
+
+ SimpleFeature sf2 = add(store, 0, 0);
+ SimpleFeature sf2a = add(store, 30, 40);
+ assertTrue(store.contains(sf2));
+ assertFalse(store.remove(sf1));
+ assertTrue(store.remove(sf2));
+ assertTrue(store.remove(sf2a));
+ assertTrue(store.isEmpty());
+
+ /*
+ * nested feature deletion
+ */
+ SimpleFeature sf4 = add(store, 20, 30);
+ SimpleFeature sf5 = add(store, 22, 26); // to NCList
+ SimpleFeature sf6 = add(store, 23, 24); // child of sf5
+ SimpleFeature sf7 = add(store, 25, 25); // sibling of sf6
+ SimpleFeature sf8 = add(store, 24, 24); // child of sf6
+ SimpleFeature sf9 = add(store, 23, 23); // child of sf6
+ assertEquals(store.size(), 6);
+
+ // delete a node with children - they take its place
+ assertTrue(store.remove(sf6)); // sf8, sf9 should become children of sf5
+ assertEquals(store.size(), 5);
+ assertFalse(store.contains(sf6));
+
+ // delete a node with no children
+ assertTrue(store.remove(sf7));
+ assertEquals(store.size(), 4);
+ assertFalse(store.contains(sf7));
+
+ // delete root of NCList
+ assertTrue(store.remove(sf5));
+ assertEquals(store.size(), 3);
+ assertFalse(store.contains(sf5));
+
+ // continue the killing fields
+ assertTrue(store.remove(sf4));
+ assertEquals(store.size(), 2);
+ assertFalse(store.contains(sf4));
+
+ assertTrue(store.remove(sf9));
+ assertEquals(store.size(), 1);
+ assertFalse(store.contains(sf9));
+
+ assertTrue(store.remove(sf8));
+ assertTrue(store.isEmpty());
+ }
+
+ /**
+ * A helper method to test whether a list contains a specific object (by
+ * object identity, not equality test as used by List.contains())
+ *
+ * @param list
+ * @param o
+ * @return
+ */
+ private static boolean containsObject(List<? extends Object> list,
+ Object o)
+ {
+ for (Object i : list)
+ {
+ if (i == o)
+ {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ @Test(groups = "Functional")
+ public void testAdd()
+ {
+ IntervalStore<SimpleFeature> store = new IntervalStore<>();
+
+ assertFalse(store.add(null));
+
+ SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath");
+ SimpleFeature sf2 = new SimpleFeature(10, 20, "Cath");
+
+ assertTrue(store.add(sf1));
+ assertEquals(store.size(), 1);
+
+ /*
+ * contains should return true for the same or an identical feature
+ */
+ assertTrue(store.contains(sf1));
+ assertTrue(store.contains(sf2));
+
+ /*
+ * duplicates are accepted
+ */
+ assertTrue(store.add(sf2));
+ assertEquals(store.size(), 2);
+
+ SimpleFeature sf3 = new SimpleFeature(0, 0, "Cath");
+ assertTrue(store.add(sf3));
+ assertEquals(store.size(), 3);
+ }
+
+ @Test(groups = "Functional")
+ public void testAdd_noDuplicates()
+ {
+ IntervalStore<SimpleFeature> store = new IntervalStore<>();
+
+ SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath");
+ SimpleFeature sf2 = new SimpleFeature(10, 20, "Cath");
+ assertTrue(sf1.equals(sf2));
+ assertTrue(store.add(sf1));
+ assertEquals(store.size(), 1);
+ assertFalse(store.add(sf2, false));
+ assertEquals(store.size(), 1);
+ assertTrue(store.contains(sf1));
+ assertTrue(store.contains(sf2)); // because sf1.equals(sf2) !
+ }
+
+ @Test(groups = "Functional")
+ public void testIsEmpty()
+ {
+ IntervalStore<SimpleFeature> store = new IntervalStore<>();
+ assertTrue(store.isEmpty());
+ assertEquals(store.size(), 0);
+
+ /*
+ * non-nested feature
+ */
+ SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath");
+ store.add(sf1);
+ assertFalse(store.isEmpty());
+ assertEquals(store.size(), 1);
+ store.remove(sf1);
+ assertTrue(store.isEmpty());
+ assertEquals(store.size(), 0);
+
+ sf1 = new SimpleFeature(0, 0, "Cath");
+ store.add(sf1);
+ assertFalse(store.isEmpty());
+ assertEquals(store.size(), 1);
+ store.remove(sf1);
+ assertTrue(store.isEmpty());
+ assertEquals(store.size(), 0);
+
+ /*
+ * sf2, sf3 added as nested features
+ */
+ sf1 = new SimpleFeature(19, 49, "Cath");
+ SimpleFeature sf2 = new SimpleFeature(20, 40, "Cath");
+ SimpleFeature sf3 = new SimpleFeature(25, 35, "Cath");
+ store.add(sf1);
+ assertEquals(store.size(), 1);
+ store.add(sf2);
+ assertEquals(store.size(), 2);
+ store.add(sf3);
+ assertEquals(store.size(), 3);
+ assertTrue(store.remove(sf1));
+ assertEquals(store.size(), 2);
+
+ assertFalse(store.isEmpty());
+ assertTrue(store.remove(sf2));
+ assertEquals(store.size(), 1);
+ assertFalse(store.isEmpty());
+ assertTrue(store.remove(sf3));
+ assertEquals(store.size(), 0);
+ assertTrue(store.isEmpty()); // all gone
+ }
+
+ @Test(groups = "Functional")
+ public void testRemove_readd()
+ {
+ /*
+ * add a feature and a nested feature
+ */
+ IntervalStore<SimpleFeature> store = new IntervalStore<>();
+ SimpleFeature sf1 = add(store, 10, 20);
+ // sf2 is nested in sf1 so will be stored in nestedFeatures
+ SimpleFeature sf2 = add(store, 12, 14);
+ assertEquals(store.size(), 2);
+ assertTrue(store.contains(sf1));
+ assertTrue(store.contains(sf2));
+
+ /*
+ * delete the first feature
+ */
+ assertTrue(store.remove(sf1));
+ assertFalse(store.contains(sf1));
+ assertTrue(store.contains(sf2));
+
+ /*
+ * re-add the 'nested' feature; it is now duplicated
+ */
+ store.add(sf2);
+ assertEquals(store.size(), 2);
+ assertTrue(store.contains(sf2));
+ }
+
+ @Test(groups = "Functional")
+ public void testContains()
+ {
+ IntervalStore<SimpleFeature> store = new IntervalStore<>();
+ SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath");
+ SimpleFeature sf2 = new SimpleFeature(10, 20, "Pfam");
+
+ store.add(sf1);
+ assertTrue(store.contains(sf1));
+ assertTrue(store.contains(new SimpleFeature(sf1))); // identical feature
+ assertFalse(store.contains(sf2)); // different description
+
+ /*
+ * add a nested feature
+ */
+ SimpleFeature sf3 = new SimpleFeature(12, 16, "Cath");
+ store.add(sf3);
+ assertTrue(store.contains(sf3));
+ assertTrue(store.contains(new SimpleFeature(sf3)));
+
+ /*
+ * delete the outer (enclosing, non-nested) feature
+ */
+ store.remove(sf1);
+ assertFalse(store.contains(sf1));
+ assertTrue(store.contains(sf3));
+
+ assertFalse(store.contains(null));
+ try
+ {
+ assertFalse(store.contains("junk"));
+ } catch (ClassCastException e)
+ {
+ // expected;
+ }
+ }
+
+ @Test(groups = "Functional")
+ public void testFindOverlaps_resultsArg_mixed()
+ {
+ IntervalStore<SimpleFeature> store = new IntervalStore<>();
+ SimpleFeature sf1 = add(store, 10, 50);
+ SimpleFeature sf2 = add(store, 1, 15);
+ SimpleFeature sf3 = add(store, 20, 30);
+ SimpleFeature sf4 = add(store, 40, 100);
+ SimpleFeature sf5 = add(store, 60, 100);
+ SimpleFeature sf6 = add(store, 70, 70);
+
+ List<SimpleFeature> overlaps = new ArrayList<>();
+ List<SimpleFeature> overlaps2 = store.findOverlaps(200, 200, overlaps);
+ assertSame(overlaps, overlaps2);
+ assertTrue(overlaps.isEmpty());
+
+ overlaps.clear();
+ store.findOverlaps(1, 9, overlaps);
+ assertEquals(overlaps.size(), 1);
+ assertTrue(overlaps.contains(sf2));
+
+ overlaps.clear();
+ store.findOverlaps(5, 18, overlaps);
+ assertEquals(overlaps.size(), 2);
+ assertTrue(overlaps.contains(sf1));
+ assertTrue(overlaps.contains(sf2));
+
+ overlaps.clear();
+ store.findOverlaps(30, 40, overlaps);
+ assertEquals(overlaps.size(), 3);
+ assertTrue(overlaps.contains(sf1));
+ assertTrue(overlaps.contains(sf3));
+ assertTrue(overlaps.contains(sf4));
+
+ overlaps.clear();
+ store.findOverlaps(80, 90, overlaps);
+ assertEquals(overlaps.size(), 2);
+ assertTrue(overlaps.contains(sf4));
+ assertTrue(overlaps.contains(sf5));
+
+ overlaps.clear();
+ store.findOverlaps(68, 70, overlaps);
+ assertEquals(overlaps.size(), 3);
+ assertTrue(overlaps.contains(sf4));
+ assertTrue(overlaps.contains(sf5));
+ assertTrue(overlaps.contains(sf6));
+
+ /*
+ * and without clearing the list first
+ * note that sf4 is included twice, as an
+ * overlap of 68-70 and also of 30-40
+ */
+ store.findOverlaps(30, 40, overlaps);
+ assertEquals(overlaps.size(), 6);
+ assertTrue(overlaps.contains(sf1));
+ assertTrue(overlaps.contains(sf3));
+ assertTrue(overlaps.contains(sf4));
+ assertTrue(overlaps.contains(sf5));
+ assertTrue(overlaps.contains(sf6));
+ assertSame(sf4, overlaps.get(0));
+ assertSame(sf4, overlaps.get(4));
+ }
+
+ @Test(groups = "Functional")
+ public void testFindOverlaps_resultsArg_nested()
+ {
+ IntervalStore<SimpleFeature> store = new IntervalStore<>();
+ SimpleFeature sf1 = add(store, 10, 50);
+ SimpleFeature sf2 = add(store, 10, 40);
+ SimpleFeature sf3 = add(store, 20, 30);
+ // feature at same location but different description
+ SimpleFeature sf4 = new SimpleFeature(20, 30, "different desc");
+ store.add(sf4);
+ SimpleFeature sf5 = add(store, 35, 36);
+
+ List<SimpleFeature> overlaps = new ArrayList<>();
+ store.findOverlaps(1, 9, overlaps);
+ assertTrue(overlaps.isEmpty());
+
+ store.findOverlaps(10, 15, overlaps);
+ assertEquals(overlaps.size(), 2);
+ assertTrue(overlaps.contains(sf1));
+ assertTrue(overlaps.contains(sf2));
+
+ overlaps.clear();
+ store.findOverlaps(45, 60, overlaps);
+ assertEquals(overlaps.size(), 1);
+ assertTrue(overlaps.contains(sf1));
+
+ overlaps.clear();
+ store.findOverlaps(32, 38, overlaps);
+ assertEquals(overlaps.size(), 3);
+ assertTrue(overlaps.contains(sf1));
+ assertTrue(overlaps.contains(sf2));
+ assertTrue(overlaps.contains(sf5));
+
+ overlaps.clear();
+ store.findOverlaps(15, 25, overlaps);
+ assertEquals(overlaps.size(), 4);
+ assertTrue(overlaps.contains(sf1));
+ assertTrue(overlaps.contains(sf2));
+ assertTrue(overlaps.contains(sf3));
+ assertTrue(overlaps.contains(sf4));
+ }
+
+ @Test(groups = "Functional")
+ public void testFindOverlaps_resultsArg_nonNested()
+ {
+ IntervalStore<SimpleFeature> store = new IntervalStore<>();
+ SimpleFeature sf1 = add(store, 10, 20);
+ // same range different description
+ SimpleFeature sf2 = new SimpleFeature(10, 20, "desc");
+ store.add(sf2);
+ SimpleFeature sf3 = add(store, 15, 25);
+ SimpleFeature sf4 = add(store, 20, 35);
+
+ assertEquals(store.size(), 4);
+ List<SimpleFeature> overlaps = new ArrayList<>();
+ store.findOverlaps(1, 9, overlaps);
+ assertTrue(overlaps.isEmpty());
+
+ store.findOverlaps(8, 10, overlaps);
+ assertEquals(overlaps.size(), 2);
+ assertTrue(overlaps.contains(sf1));
+ assertTrue(overlaps.contains(sf2));
+
+ overlaps.clear();
+ store.findOverlaps(12, 16, overlaps);
+ assertEquals(overlaps.size(), 3);
+ assertTrue(overlaps.contains(sf1));
+ assertTrue(overlaps.contains(sf2));
+ assertTrue(overlaps.contains(sf3));
+
+ overlaps.clear();
+ store.findOverlaps(33, 33, overlaps);
+ assertEquals(overlaps.size(), 1);
+ assertTrue(overlaps.contains(sf4));
+
+ /*
+ * ensure edge cases are covered
+ */
+ overlaps.clear();
+ store.findOverlaps(35, 40, overlaps);
+ assertEquals(overlaps.size(), 1);
+ assertTrue(overlaps.contains(sf4));
+
+ overlaps.clear();
+ assertTrue(store.findOverlaps(36, 100, overlaps).isEmpty());
+ assertTrue(store.findOverlaps(1, 9, overlaps).isEmpty());
+ }
+}
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;
+package intervalstore.nonc;
import intervalstore.api.IntervalI;
/**
* A simplified feature instance sufficient for unit test purposes
*/
-public class SimpleFeature extends Range
+public class SimpleFeature implements IntervalI
{
+ final private int begin;
- private String description;
+ final private int end;
+ private String description;
/**
* Constructor
*/
public SimpleFeature(int from, int to, String desc)
{
- super(from, to);
+ begin = from;
+ end = to;
description = desc;
}
*/
public SimpleFeature(SimpleFeature sf1)
{
- this(sf1.start, sf1.end, sf1.description);
+ this(sf1.begin, sf1.end, sf1.description);
}
- public String getDescription()
+ @Override
+ public int getBegin()
{
- return description;
+ return begin;
}
@Override
- public int hashCode()
+ public int getEnd()
{
- return start + 37 * end
- + (description == null ? 0 : description.hashCode());
+ return end;
+ }
+
+ public String getDescription()
+ {
+ return description;
}
@Override
- public boolean equals(Object o)
+ public int hashCode()
{
- return (o != null && o instanceof SimpleFeature
- && equalsInterval((SimpleFeature) o));
+ return begin + 37 * end
+ + (description == null ? 0 : description.hashCode());
}
/**
* Equals method that requires two instances to have the same description, as
- * well as start and end position. Does not do a test for null
+ * well as start and end position.
*/
@Override
- public boolean equalsInterval(IntervalI o)
+ public boolean equals(Object obj)
{
- // must override equalsInterval, not equals
- return (o != null && start == ((SimpleFeature) o).start
- && end == ((SimpleFeature) o).end)
- && (description == null
- ? ((SimpleFeature) o).description == null
- : description.equals(((SimpleFeature) o).description));
+ if (obj != null && obj instanceof SimpleFeature)
+ {
+ SimpleFeature o = (SimpleFeature) obj;
+ if (this.begin == o.begin && this.end == o.end)
+ {
+ if (this.description == null)
+ {
+ return o.description == null;
+ }
+ return this.description.equals(o.description);
+ }
+ }
+ return false;
}
@Override
public String toString()
{
- return start + ":" + end + ":" + description;
+ return begin + ":" + end + ":" + description;
}
-
}
@Test(groups = "Functional")
public void testFindFeatures_nonNested()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
fs.addFeature(new SequenceFeature("", "", 10, 20, Float.NaN,
null));
// same range different description
assertEquals(overlaps.get(0).getEnd(), 35);
}
- private FeatureStoreI newFeatureStore()
+ private FeatureStore newFeatureStore()
{
- return new FeatureStoreJS(intervalStoreOption);
+ return new FeatureStore(intervalStoreOption);
}
@Test(groups = "Functional")
public void testFindFeatures_nested()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
SequenceFeature sf1 = addFeature(fs, 10, 50);
SequenceFeature sf2 = addFeature(fs, 10, 40);
SequenceFeature sf3 = addFeature(fs, 20, 30);
private void testFind()
{
- FeatureStoreI fs1 = newFeatureStore();
+ FeatureStore fs1 = newFeatureStore();
SequenceFeature sf = addFeature(fs1, 1, 3000);
{
testFind();
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
SequenceFeature sf1 = addFeature(fs, 10, 50);
SequenceFeature sf2 = addFeature(fs, 1, 15);
SequenceFeature sf3 = addFeature(fs, 20, 30);
* @param to
* @return
*/
- SequenceFeature addFeature(FeatureStoreI fs, int from, int to)
+ SequenceFeature addFeature(FeatureStore fs, int from, int to)
{
SequenceFeature sf1 = new SequenceFeature("", "", from, to, Float.NaN,
null);
@Test(groups = "Functional")
public void testFindFeatures_contactFeatures()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
SequenceFeature sf = new SequenceFeature("disulphide bond", "bond", 10,
20, Float.NaN, null);
@Test(groups = "Functional")
public void testGetPositionalFeatures()
{
- FeatureStoreI store = newFeatureStore();
+ FeatureStore store = newFeatureStore();
SequenceFeature sf1 = new SequenceFeature("Metal", "desc", 10, 20,
Float.NaN, null);
store.addFeature(sf1);
@Test(groups = "Functional")
public void testDelete()
{
- FeatureStoreI store = newFeatureStore();
+ FeatureStore store = newFeatureStore();
SequenceFeature sf1 = addFeature(store, 10, 20);
assertTrue(store.getPositionalFeatures().contains(sf1));
@Test(groups = "Functional")
public void testAddFeature()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
SequenceFeature sf1 = new SequenceFeature("Cath", "", 10, 20,
Float.NaN, null);
@Test(groups = "Functional")
public void testIsEmpty()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
assertTrue(fs.isEmpty());
assertEquals(fs.getFeatureCount(true), 0);
@Test(groups = "Functional")
public void testGetFeatureGroups()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
assertTrue(fs.getFeatureGroups(true).isEmpty());
assertTrue(fs.getFeatureGroups(false).isEmpty());
@Test(groups = "Functional")
public void testGetTotalFeatureLength()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
assertEquals(fs.getTotalFeatureLength(), 0);
addFeature(fs, 10, 20); // 11
@Test(groups = "Functional")
public void testGetMinimumScore_getMaximumScore()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
assertEquals(fs.getMinimumScore(true), Float.NaN); // positional
assertEquals(fs.getMaximumScore(true), Float.NaN);
assertEquals(fs.getMinimumScore(false), Float.NaN); // non-positional
@Test(groups = "Functional")
public void testListContains()
{
- FeatureStoreI featureStore = newFeatureStore();
+ FeatureStore featureStore = newFeatureStore();
assertFalse(featureStore.listContains(null, null));
List<SequenceFeature> features = new ArrayList<>();
assertFalse(featureStore.listContains(features, null));
@Test(groups = "Functional")
public void testGetFeaturesForGroup()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
/*
* with no features
@Test(groups = "Functional")
public void testShiftFeatures()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
assertFalse(fs.shiftFeatures(0, 1)); // nothing to do
SequenceFeature sf1 = new SequenceFeature("Cath", "", 2, 5, 0f, null);
/*
* add a feature and a nested feature
*/
- FeatureStoreI store = newFeatureStore();
+ FeatureStore store = newFeatureStore();
SequenceFeature sf1 = addFeature(store, 10, 20);
// sf2 is nested in sf1 so will be stored in nestedFeatures
SequenceFeature sf2 = addFeature(store, 12, 14);
@Test(groups = "Functional")
public void testContains()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
SequenceFeature sf1 = new SequenceFeature("Cath", "", 10, 20,
Float.NaN, "group1");
SequenceFeature sf2 = new SequenceFeature("Cath", "", 10, 20,
public class FeatureStoreJavaTest
{
-
- private int intervalStoreOption = FeatureStore.intervalStoreJavaOption;
-
- private FeatureStoreI newFeatureStore()
+ private FeatureStore newFeatureStore()
{
- return new FeatureStoreImpl(intervalStoreOption);
+ return new FeatureStore();
}
@Test(groups = "Functional")
public void testFindFeatures_nonNested()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
fs.addFeature(new SequenceFeature("", "", 10, 20, Float.NaN,
null));
// same range different description
@Test(groups = "Functional")
public void testFindFeatures_nested()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
SequenceFeature sf1 = addFeature(fs, 10, 50);
SequenceFeature sf2 = addFeature(fs, 10, 40);
SequenceFeature sf3 = addFeature(fs, 20, 30);
@Test(groups = "Functional")
public void testFindFeatures_mixed()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
SequenceFeature sf1 = addFeature(fs, 10, 50);
SequenceFeature sf2 = addFeature(fs, 1, 15);
SequenceFeature sf3 = addFeature(fs, 20, 30);
* @param to
* @return
*/
- SequenceFeature addFeature(FeatureStoreI fs, int from, int to)
+ SequenceFeature addFeature(FeatureStore fs, int from, int to)
{
SequenceFeature sf1 = new SequenceFeature("", "", from, to, Float.NaN,
null);
@Test(groups = "Functional")
public void testFindFeatures_contactFeatures()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
SequenceFeature sf = new SequenceFeature("disulphide bond", "bond", 10,
20, Float.NaN, null);
@Test(groups = "Functional")
public void testGetPositionalFeatures()
{
- FeatureStoreI store = newFeatureStore();
+ FeatureStore store = newFeatureStore();
SequenceFeature sf1 = new SequenceFeature("Metal", "desc", 10, 20,
Float.NaN, null);
store.addFeature(sf1);
@Test(groups = "Functional")
public void testDelete()
{
- FeatureStoreI store = newFeatureStore();
+ FeatureStore store = newFeatureStore();
SequenceFeature sf1 = addFeature(store, 10, 20);
assertTrue(store.getPositionalFeatures().contains(sf1));
@Test(groups = "Functional")
public void testAddFeature()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
SequenceFeature sf1 = new SequenceFeature("Cath", "", 10, 20,
Float.NaN, null);
@Test(groups = "Functional")
public void testIsEmpty()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
assertTrue(fs.isEmpty());
assertEquals(fs.getFeatureCount(true), 0);
@Test(groups = "Functional")
public void testGetFeatureGroups()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
assertTrue(fs.getFeatureGroups(true).isEmpty());
assertTrue(fs.getFeatureGroups(false).isEmpty());
@Test(groups = "Functional")
public void testGetTotalFeatureLength()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
assertEquals(fs.getTotalFeatureLength(), 0);
addFeature(fs, 10, 20); // 11
@Test(groups = "Functional")
public void testGetMinimumScore_getMaximumScore()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
assertEquals(fs.getMinimumScore(true), Float.NaN); // positional
assertEquals(fs.getMaximumScore(true), Float.NaN);
assertEquals(fs.getMinimumScore(false), Float.NaN); // non-positional
@Test(groups = "Functional")
public void testListContains()
{
- FeatureStoreI featureStore = newFeatureStore();
+ FeatureStore featureStore = newFeatureStore();
assertFalse(featureStore.listContains(null, null));
List<SequenceFeature> features = new ArrayList<>();
assertFalse(featureStore.listContains(features, null));
@Test(groups = "Functional")
public void testGetFeaturesForGroup()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
/*
* with no features
@Test(groups = "Functional")
public void testShiftFeatures()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
assertFalse(fs.shiftFeatures(0, 1)); // nothing to do
SequenceFeature sf1 = new SequenceFeature("Cath", "", 2, 5, 0f, null);
/*
* add a feature and a nested feature
*/
- FeatureStoreI store = newFeatureStore();
+ FeatureStore store = newFeatureStore();
SequenceFeature sf1 = addFeature(store, 10, 20);
// sf2 is nested in sf1 so will be stored in nestedFeatures
SequenceFeature sf2 = addFeature(store, 12, 14);
@Test(groups = "Functional")
public void testContains()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
SequenceFeature sf1 = new SequenceFeature("Cath", "", 10, 20,
Float.NaN, "group1");
SequenceFeature sf2 = new SequenceFeature("Cath", "", 10, 20,
public class FeatureStoreLinkedTest
{
- private FeatureStoreI newFeatureStore()
+ private FeatureStore newFeatureStore()
{
- return new FeatureStoreImpl(
+ return new FeatureStore(
FeatureStore.INTERVAL_STORE_LINKED_LIST_PRESORT);
}
@Test(groups = "Functional")
public void testFindFeatures_nonNested()
{
- FeatureStoreI fs = newFeatureStore();
- fs.addFeature(new SequenceFeature("", "", 10, 20, Float.NaN,
- null));
+ FeatureStore fs = newFeatureStore();
+ SequenceFeature sf0 = new SequenceFeature("", "", 10, 20, Float.NaN,
+ null);
+ fs.addFeature(sf0);
// same range different description
- fs.addFeature(new SequenceFeature("", "desc", 10, 20, Float.NaN, null));
- fs.addFeature(new SequenceFeature("", "", 15, 25, Float.NaN, null));
- fs.addFeature(new SequenceFeature("", "", 20, 35, Float.NaN, null));
+ SequenceFeature sf1 = new SequenceFeature("", "desc", 10, 20, Float.NaN, null);
+ fs.addFeature(sf1);
+ SequenceFeature sf2 = new SequenceFeature("", "", 15, 25, Float.NaN, null);
+ fs.addFeature(sf2);
+ SequenceFeature sf3 = new SequenceFeature("", "", 20, 35, Float.NaN, null);
+ fs.addFeature(sf3);
List<SequenceFeature> overlaps = fs.findOverlappingFeatures(1, 9);
assertTrue(overlaps.isEmpty());
overlaps = fs.findOverlappingFeatures(8, 10);
assertEquals(overlaps.size(), 2);
- assertEquals(overlaps.get(0).getEnd(), 20);
- assertEquals(overlaps.get(1).getEnd(), 20);
+ assertTrue(overlaps.contains(sf0));
+ assertTrue(overlaps.contains(sf1));
overlaps = fs.findOverlappingFeatures(12, 16);
assertEquals(overlaps.size(), 3);
- assertEquals(overlaps.get(0).getEnd(), 20);
- assertEquals(overlaps.get(1).getEnd(), 20);
- assertEquals(overlaps.get(2).getEnd(), 25);
+ assertTrue(overlaps.contains(sf0));
+ assertTrue(overlaps.contains(sf1));
+ assertTrue(overlaps.contains(sf2));
overlaps = fs.findOverlappingFeatures(33, 33);
assertEquals(overlaps.size(), 1);
- assertEquals(overlaps.get(0).getEnd(), 35);
+ assertTrue(overlaps.contains(sf3));
}
@Test(groups = "Functional")
public void testFindFeatures_nested()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
SequenceFeature sf1 = addFeature(fs, 10, 50);
SequenceFeature sf2 = addFeature(fs, 10, 40);
SequenceFeature sf3 = addFeature(fs, 20, 30);
@Test(groups = "Functional")
public void testFindFeatures_mixed()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
SequenceFeature sf1 = addFeature(fs, 10, 50);
SequenceFeature sf2 = addFeature(fs, 1, 15);
SequenceFeature sf3 = addFeature(fs, 20, 30);
* @param to
* @return
*/
- SequenceFeature addFeature(FeatureStoreI fs, int from, int to)
+ SequenceFeature addFeature(FeatureStore fs, int from, int to)
{
SequenceFeature sf1 = new SequenceFeature("", "", from, to, Float.NaN,
null);
@Test(groups = "Functional")
public void testFindFeatures_contactFeatures()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
SequenceFeature sf = new SequenceFeature("disulphide bond", "bond", 10,
20, Float.NaN, null);
@Test(groups = "Functional")
public void testGetPositionalFeatures()
{
- FeatureStoreI store = newFeatureStore();
+ FeatureStore store = newFeatureStore();
SequenceFeature sf1 = new SequenceFeature("Metal", "desc", 10, 20,
Float.NaN, null);
store.addFeature(sf1);
@Test(groups = "Functional")
public void testDelete()
{
- FeatureStoreI store = newFeatureStore();
+ FeatureStore store = newFeatureStore();
SequenceFeature sf1 = addFeature(store, 10, 20);
assertTrue(store.getPositionalFeatures().contains(sf1));
@Test(groups = "Functional")
public void testAddFeature()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
SequenceFeature sf1 = new SequenceFeature("Cath", "", 10, 20,
Float.NaN, null);
@Test(groups = "Functional")
public void testIsEmpty()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
assertTrue(fs.isEmpty());
assertEquals(fs.getFeatureCount(true), 0);
@Test(groups = "Functional")
public void testGetFeatureGroups()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
assertTrue(fs.getFeatureGroups(true).isEmpty());
assertTrue(fs.getFeatureGroups(false).isEmpty());
@Test(groups = "Functional")
public void testGetTotalFeatureLength()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
assertEquals(fs.getTotalFeatureLength(), 0);
addFeature(fs, 10, 20); // 11
@Test(groups = "Functional")
public void testGetMinimumScore_getMaximumScore()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
assertEquals(fs.getMinimumScore(true), Float.NaN); // positional
assertEquals(fs.getMaximumScore(true), Float.NaN);
assertEquals(fs.getMinimumScore(false), Float.NaN); // non-positional
@Test(groups = "Functional")
public void testListContains()
{
- FeatureStoreI featureStore = newFeatureStore();
+ FeatureStore featureStore = newFeatureStore();
assertFalse(featureStore.listContains(null, null));
List<SequenceFeature> features = new ArrayList<>();
assertFalse(featureStore.listContains(features, null));
@Test(groups = "Functional")
public void testGetFeaturesForGroup()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
/*
* with no features
@Test(groups = "Functional")
public void testShiftFeatures()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
assertFalse(fs.shiftFeatures(0, 1)); // nothing to do
SequenceFeature sf1 = new SequenceFeature("Cath", "", 2, 5, 0f, null);
/*
* add a feature and a nested feature
*/
- FeatureStoreI store = newFeatureStore();
+ FeatureStore store = newFeatureStore();
SequenceFeature sf1 = addFeature(store, 10, 20);
// sf2 is nested in sf1 so will be stored in nestedFeatures
SequenceFeature sf2 = addFeature(store, 12, 14);
@Test(groups = "Functional")
public void testContains()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
SequenceFeature sf1 = new SequenceFeature("Cath", "", 10, 20,
Float.NaN, "group1");
SequenceFeature sf2 = new SequenceFeature("Cath", "", 10, 20,
public class FeatureStoreNCListBufferTest
{
- private FeatureStoreI newFeatureStore()
+ private FeatureStore newFeatureStore()
{
- return new FeatureStoreImpl(
+ return new FeatureStore(
FeatureStore.INTERVAL_STORE_NCLIST_BUFFER_PRESORT);
}
@Test(groups = "Functional")
public void testFindFeatures_nonNested()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
fs.addFeature(new SequenceFeature("", "", 10, 20, Float.NaN,
null));
// same range different description
@Test(groups = "Functional")
public void testFindFeatures_nested()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
SequenceFeature sf1 = addFeature(fs, 10, 50);
SequenceFeature sf2 = addFeature(fs, 10, 40);
SequenceFeature sf3 = addFeature(fs, 20, 30);
@Test(groups = "Functional")
public void testFindFeatures_mixed()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
SequenceFeature sf1 = addFeature(fs, 10, 50);
SequenceFeature sf2 = addFeature(fs, 1, 15);
SequenceFeature sf3 = addFeature(fs, 20, 30);
* @param to
* @return
*/
- SequenceFeature addFeature(FeatureStoreI fs, int from, int to)
+ SequenceFeature addFeature(FeatureStore fs, int from, int to)
{
SequenceFeature sf1 = new SequenceFeature("", "", from, to, Float.NaN,
null);
@Test(groups = "Functional")
public void testFindFeatures_contactFeatures()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
SequenceFeature sf = new SequenceFeature("disulphide bond", "bond", 10,
20, Float.NaN, null);
@Test(groups = "Functional")
public void testGetPositionalFeatures()
{
- FeatureStoreI store = newFeatureStore();
+ FeatureStore store = newFeatureStore();
SequenceFeature sf1 = new SequenceFeature("Metal", "desc", 10, 20,
Float.NaN, null);
store.addFeature(sf1);
@Test(groups = "Functional")
public void testDelete()
{
- FeatureStoreI store = newFeatureStore();
+ FeatureStore store = newFeatureStore();
SequenceFeature sf1 = addFeature(store, 10, 20);
assertTrue(store.getPositionalFeatures().contains(sf1));
@Test(groups = "Functional")
public void testAddFeature()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
SequenceFeature sf1 = new SequenceFeature("Cath", "", 10, 20,
Float.NaN, null);
@Test(groups = "Functional")
public void testIsEmpty()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
assertTrue(fs.isEmpty());
assertEquals(fs.getFeatureCount(true), 0);
@Test(groups = "Functional")
public void testGetFeatureGroups()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
assertTrue(fs.getFeatureGroups(true).isEmpty());
assertTrue(fs.getFeatureGroups(false).isEmpty());
@Test(groups = "Functional")
public void testGetTotalFeatureLength()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
assertEquals(fs.getTotalFeatureLength(), 0);
addFeature(fs, 10, 20); // 11
@Test(groups = "Functional")
public void testGetMinimumScore_getMaximumScore()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
assertEquals(fs.getMinimumScore(true), Float.NaN); // positional
assertEquals(fs.getMaximumScore(true), Float.NaN);
assertEquals(fs.getMinimumScore(false), Float.NaN); // non-positional
@Test(groups = "Functional")
public void testListContains()
{
- FeatureStoreI featureStore = newFeatureStore();
+ FeatureStore featureStore = newFeatureStore();
assertFalse(featureStore.listContains(null, null));
List<SequenceFeature> features = new ArrayList<>();
assertFalse(featureStore.listContains(features, null));
@Test(groups = "Functional")
public void testGetFeaturesForGroup()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
/*
* with no features
@Test(groups = "Functional")
public void testShiftFeatures()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
assertFalse(fs.shiftFeatures(0, 1)); // nothing to do
SequenceFeature sf1 = new SequenceFeature("Cath", "", 2, 5, 0f, null);
/*
* add a feature and a nested feature
*/
- FeatureStoreI store = newFeatureStore();
+ FeatureStore store = newFeatureStore();
SequenceFeature sf1 = addFeature(store, 10, 20);
// sf2 is nested in sf1 so will be stored in nestedFeatures
SequenceFeature sf2 = addFeature(store, 12, 14);
@Test(groups = "Functional")
public void testContains()
{
- FeatureStoreI fs = newFeatureStore();
+ FeatureStore fs = newFeatureStore();
SequenceFeature sf1 = new SequenceFeature("Cath", "", 10, 20,
Float.NaN, "group1");
SequenceFeature sf2 = new SequenceFeature("Cath", "", 10, 20,
* no type specified - get all types stored
* they are returned in keyset (alphabetical) order
*/
- Map<String, FeatureStoreI> featureStores = (Map<String, FeatureStoreI>) PA
+ Map<String, FeatureStore> featureStores = (Map<String, FeatureStore>) PA
.getValue(sf, "featureStore");
- Iterable<FeatureStoreI> types = sf.varargToTypes();
- Iterator<FeatureStoreI> iterator = types.iterator();
+ Iterable<FeatureStore> types = sf.varargToTypes();
+ Iterator<FeatureStore> iterator = types.iterator();
assertTrue(iterator.hasNext());
assertSame(iterator.next(), featureStores.get("Cath"));
assertTrue(iterator.hasNext());
git://source.jalview.org / jalview.git / commitdiff