<classpathentry kind="lib" path="lib/htsjdk-2.12.0.jar"/>
<classpathentry kind="lib" path="lib/groovy-all-2.4.12-indy.jar"/>
<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER/org.eclipse.jdt.internal.debug.ui.launcher.StandardVMType/JavaSE-1.8"/>
+ <classpathentry kind="lib" path="lib/intervalstore.jar" sourcepath="/IntervalStoreJ/binaries/intervalstore-src.jar"/>
<classpathentry kind="output" path="classes"/>
</classpath>
+++ /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;
-
-/**
- * An immutable data bean that models a start-end range
- */
-public class Range implements ContiguousI
-{
- public final int start;
-
- public final 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 obj)
- {
- if (obj instanceof Range)
- {
- Range r = (Range) obj;
- return (start == r.start && end == r.end);
- }
- return false;
- }
-}
import java.util.Vector;
import fr.orsay.lri.varna.models.rna.RNA;
+import intervalstore.api.IntervalI;
+import intervalstore.impl.Range;
/**
*
* {@inheritDoc}
*/
@Override
- public Range findPositions(int fromColumn, int toColumn)
+ public IntervalI findPositions(int fromColumn, int toColumn)
{
if (toColumn < fromColumn || fromColumn < 1)
{
import java.util.Vector;
import fr.orsay.lri.varna.models.rna.RNA;
+import intervalstore.api.IntervalI;
/**
* Methods for manipulating a sequence, its metadata and related annotation in
* @param toColumn
* @return
*/
- public Range findPositions(int fromColum, int toColumn);
+ public IntervalI findPositions(int fromColum, int toColumn);
/**
* Returns an int array where indices correspond to each residue in the
*/
package jalview.datamodel.features;
-import jalview.datamodel.ContiguousI;
+import intervalstore.api.IntervalI;
/**
- * An extension of ContiguousI that allows start/end values to be interpreted
+ * An extension of IntervalI that allows start/end values to be interpreted
* instead as two contact positions
*/
-public interface FeatureLocationI extends ContiguousI
+public interface FeatureLocationI extends IntervalI
{
boolean isContactFeature();
}
*/
package jalview.datamodel.features;
-import jalview.datamodel.ContiguousI;
import jalview.datamodel.SequenceFeature;
import java.util.ArrayList;
import java.util.Collections;
-import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
+import intervalstore.api.IntervalStoreI;
+import intervalstore.impl.BinarySearcher;
+import intervalstore.impl.IntervalStore;
+
/**
* 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
*/
public class FeatureStore
{
- /**
- * a class providing criteria for performing a binary search of a list
- */
- abstract static class SearchCriterion
- {
- /**
- * Answers true if the entry passes the search criterion test
- *
- * @param entry
- * @return
- */
- abstract boolean compare(SequenceFeature entry);
-
- /**
- * serves a search condition for finding the first feature whose start
- * position follows a given target location
- *
- * @param target
- * @return
- */
- static SearchCriterion byStart(final long target)
- {
- return new SearchCriterion() {
-
- @Override
- boolean compare(SequenceFeature entry)
- {
- return entry.getBegin() >= target;
- }
- };
- }
-
- /**
- * serves a search condition for finding the first feature whose end
- * position is at or follows a given target location
- *
- * @param target
- * @return
- */
- static SearchCriterion byEnd(final long target)
- {
- return new SearchCriterion()
- {
-
- @Override
- boolean compare(SequenceFeature entry)
- {
- return entry.getEnd() >= target;
- }
- };
- }
-
- /**
- * serves a search condition for finding the first feature which follows the
- * given range as determined by a supplied comparator
- *
- * @param target
- * @return
- */
- static SearchCriterion byFeature(final ContiguousI to,
- final Comparator<ContiguousI> rc)
- {
- return new SearchCriterion()
- {
-
- @Override
- boolean compare(SequenceFeature entry)
- {
- return rc.compare(entry, to) >= 0;
- }
- };
- }
- }
-
/*
* Non-positional features have no (zero) start/end position.
* Kept as a separate list in case this criterion changes in future.
List<SequenceFeature> nonPositionalFeatures;
/*
- * An ordered list of features, with the promise that no feature in the list
- * properly contains any other. This constraint allows bounded linear search
- * of the list for features overlapping a region.
- * Contact features are not included in this list.
- */
- List<SequenceFeature> nonNestedFeatures;
-
- /*
* contact features ordered by first contact position
*/
List<SequenceFeature> contactFeatureStarts;
List<SequenceFeature> contactFeatureEnds;
/*
- * Nested Containment List is used to hold any features that are nested
- * within (properly contained by) any other feature. This is a recursive tree
- * which supports depth-first scan for features overlapping a range.
- * It is used here as a 'catch-all' fallback for features that cannot be put
- * into a simple ordered list without invalidating the search methods.
+ * IntervalStore holds remaining features and provides efficient
+ * query for features overlapping any given interval
*/
- NCList<SequenceFeature> nestedFeatures;
+ IntervalStoreI<SequenceFeature> features;
/*
* Feature groups represented in stored positional features
*/
public FeatureStore()
{
- nonNestedFeatures = new ArrayList<SequenceFeature>();
- positionalFeatureGroups = new HashSet<String>();
- nonPositionalFeatureGroups = new HashSet<String>();
+ features = new IntervalStore<>();
+ positionalFeatureGroups = new HashSet<>();
+ nonPositionalFeatureGroups = new HashSet<>();
positionalMinScore = Float.NaN;
positionalMaxScore = Float.NaN;
nonPositionalMinScore = Float.NaN;
nonPositionalMaxScore = Float.NaN;
- // we only construct nonPositionalFeatures, contactFeatures
- // or the NCList if we need to
+ // we only construct nonPositionalFeatures, contactFeatures if we need to
}
/**
positionalFeatureGroups.add(feature.getFeatureGroup());
}
- boolean added = false;
-
if (feature.isContactFeature())
{
- added = addContactFeature(feature);
+ addContactFeature(feature);
}
else if (feature.isNonPositional())
{
- added = addNonPositionalFeature(feature);
+ addNonPositionalFeature(feature);
}
else
{
- added = addNonNestedFeature(feature);
- if (!added)
- {
- /*
- * detected a nested feature - put it in the NCList structure
- */
- added = addNestedFeature(feature);
- }
+ addNestedFeature(feature);
}
- if (added)
- {
- /*
- * record the total extent of positional features, to make
- * getTotalFeatureLength possible; we count the length of a
- * contact feature as 1
- */
- totalExtent += getFeatureLength(feature);
+ /*
+ * record the total extent of positional features, to make
+ * getTotalFeatureLength possible; we count the length of a
+ * contact feature as 1
+ */
+ totalExtent += getFeatureLength(feature);
- /*
- * record the minimum and maximum score for positional
- * and non-positional features
- */
- float score = feature.getScore();
- if (!Float.isNaN(score))
+ /*
+ * record the minimum and maximum score for positional
+ * and non-positional features
+ */
+ float score = feature.getScore();
+ if (!Float.isNaN(score))
+ {
+ if (feature.isNonPositional())
+ {
+ nonPositionalMinScore = min(nonPositionalMinScore, score);
+ nonPositionalMaxScore = max(nonPositionalMaxScore, score);
+ }
+ else
{
- if (feature.isNonPositional())
- {
- nonPositionalMinScore = min(nonPositionalMinScore, score);
- nonPositionalMaxScore = max(nonPositionalMaxScore, score);
- }
- else
- {
- positionalMinScore = min(positionalMinScore, score);
- positionalMaxScore = max(positionalMaxScore, score);
- }
+ positionalMinScore = min(positionalMinScore, score);
+ positionalMaxScore = max(positionalMaxScore, score);
}
}
- return added;
+ return true;
}
/**
contactFeatureStarts, feature);
}
- if (listContains(nonNestedFeatures, feature))
- {
- return true;
- }
-
- return nestedFeatures == null ? false : nestedFeatures
+ return features == null ? false : features
.contains(feature);
}
{
if (nonPositionalFeatures == null)
{
- nonPositionalFeatures = new ArrayList<SequenceFeature>();
+ nonPositionalFeatures = new ArrayList<>();
}
nonPositionalFeatures.add(feature);
}
/**
- * Adds one feature to the NCList that can manage nested features (creating
- * the NCList if necessary), and returns true. If the feature is already
- * stored in the NCList (by equality test), then it is not added, and this
- * method returns false.
+ * Adds one feature to the IntervalStore that can manage nested features
+ * (creating the IntervalStore if necessary)
*/
- protected synchronized boolean addNestedFeature(SequenceFeature feature)
+ protected synchronized void addNestedFeature(SequenceFeature feature)
{
- if (nestedFeatures == null)
+ if (features == null)
{
- nestedFeatures = new NCList<>(feature);
- return true;
+ features = new IntervalStore<>();
}
- return nestedFeatures.add(feature, false);
- }
-
- /**
- * Add a feature to the list of non-nested features, maintaining the ordering
- * of the list. A check is made for whether the feature is nested in (properly
- * contained by) an existing feature. If there is no nesting, the feature is
- * added to the list and the method returns true. If nesting is found, the
- * feature is not added and the method returns false.
- *
- * @param feature
- * @return
- */
- protected boolean addNonNestedFeature(SequenceFeature feature)
- {
- synchronized (nonNestedFeatures)
- {
- /*
- * find the first stored feature which doesn't precede the new one
- */
- int insertPosition = binarySearch(nonNestedFeatures,
- SearchCriterion.byFeature(feature, RangeComparator.BY_START_POSITION));
-
- /*
- * fail if we detect feature enclosure - of the new feature by
- * the one preceding it, or of the next feature by the new one
- */
- if (insertPosition > 0)
- {
- if (encloses(nonNestedFeatures.get(insertPosition - 1), feature))
- {
- return false;
- }
- }
- if (insertPosition < nonNestedFeatures.size())
- {
- if (encloses(feature, nonNestedFeatures.get(insertPosition)))
- {
- return false;
- }
- }
-
- /*
- * checks passed - add the feature
- */
- nonNestedFeatures.add(insertPosition, feature);
-
- return true;
- }
- }
-
- /**
- * Answers true if range1 properly encloses range2, else false
- *
- * @param range1
- * @param range2
- * @return
- */
- protected boolean encloses(ContiguousI range1, ContiguousI range2)
- {
- int begin1 = range1.getBegin();
- int begin2 = range2.getBegin();
- int end1 = range1.getEnd();
- int end2 = range2.getEnd();
- if (begin1 == begin2 && end1 > end2)
- {
- return true;
- }
- if (begin1 < begin2 && end1 >= end2)
- {
- return true;
- }
- return false;
+ features.add(feature);
}
/**
{
if (contactFeatureStarts == null)
{
- contactFeatureStarts = new ArrayList<SequenceFeature>();
+ contactFeatureStarts = new ArrayList<>();
}
if (contactFeatureEnds == null)
{
- contactFeatureEnds = new ArrayList<SequenceFeature>();
+ contactFeatureEnds = new ArrayList<>();
}
/*
+ * insert into list sorted by start (first contact position):
* binary search the sorted list to find the insertion point
*/
- int insertPosition = binarySearch(contactFeatureStarts,
- SearchCriterion.byFeature(feature,
- RangeComparator.BY_START_POSITION));
+ int insertPosition = BinarySearcher.findFirst(contactFeatureStarts,
+ f -> f.getBegin() >= feature.getBegin());
contactFeatureStarts.add(insertPosition, feature);
- // and resort to mak siccar...just in case insertion point not quite right
- Collections.sort(contactFeatureStarts, RangeComparator.BY_START_POSITION);
- insertPosition = binarySearch(contactFeatureStarts,
- SearchCriterion.byFeature(feature,
- RangeComparator.BY_END_POSITION));
- contactFeatureEnds.add(feature);
- Collections.sort(contactFeatureEnds, RangeComparator.BY_END_POSITION);
+
+ /*
+ * insert into list sorted by end (second contact position):
+ * binary search the sorted list to find the insertion point
+ */
+ insertPosition = BinarySearcher.findFirst(contactFeatureEnds,
+ f -> f.getEnd() >= feature.getEnd());
+ contactFeatureEnds.add(insertPosition, feature);
return true;
}
/*
* locate the first entry in the list which does not precede the feature
*/
- int pos = binarySearch(features,
- SearchCriterion.byFeature(feature, RangeComparator.BY_START_POSITION));
+ // int pos = binarySearch(features,
+ // SearchCriterion.byFeature(feature, RangeComparator.BY_START_POSITION));
+ int pos = BinarySearcher.findFirst(features,
+ val -> val.getBegin() >= feature.getBegin());
int len = features.size();
while (pos < len)
{
{
List<SequenceFeature> result = new ArrayList<>();
- findNonNestedFeatures(start, end, result);
-
findContactFeatures(start, end, result);
- if (nestedFeatures != null)
+ if (features != null)
{
- result.addAll(nestedFeatures.findOverlaps(start, end));
+ result.addAll(features.findOverlaps(start, end));
}
return result;
{
if (contactFeatureStarts != null)
{
- findContactStartFeatures(from, to, result);
+ findContactStartOverlaps(from, to, result);
}
if (contactFeatureEnds != null)
{
- findContactEndFeatures(from, to, result);
+ findContactEndOverlaps(from, to, result);
}
}
* @param to
* @param result
*/
- protected void findContactEndFeatures(long from, long to,
+ protected void findContactEndOverlaps(long from, long to,
List<SequenceFeature> result)
{
/*
- * find the first contact feature (if any) that does not lie
- * entirely before the target range
+ * find the first contact feature (if any)
+ * whose end point is not before the target range
*/
- int startPosition = binarySearch(contactFeatureEnds,
- SearchCriterion.byEnd(from));
- for (; startPosition < contactFeatureEnds.size(); startPosition++)
+ int index = BinarySearcher.findFirst(contactFeatureEnds,
+ f -> f.getEnd() >= from);
+
+ while (index < contactFeatureEnds.size())
{
- SequenceFeature sf = contactFeatureEnds.get(startPosition);
+ SequenceFeature sf = contactFeatureEnds.get(index);
if (!sf.isContactFeature())
{
System.err.println("Error! non-contact feature type "
+ sf.getType() + " in contact features list");
+ index++;
continue;
}
* this feature's first contact position lies in the search range
* so we don't include it in results a second time
*/
+ index++;
continue;
}
- int end = sf.getEnd();
- if (end >= from && end <= to)
- {
- result.add(sf);
- }
- if (end > to)
+ if (sf.getEnd() > to)
{
+ /*
+ * this feature (and all following) has end point after the target range
+ */
break;
}
- }
- }
-
- /**
- * Adds non-nested features to the result list that lie within the target
- * range. Non-positional features (start=end=0), contact features and nested
- * features are excluded.
- *
- * @param from
- * @param to
- * @param result
- */
- protected void findNonNestedFeatures(long from, long to,
- List<SequenceFeature> result)
- {
- /*
- * find the first feature whose end position is
- * after the target range start
- */
- int startIndex = binarySearch(nonNestedFeatures,
- SearchCriterion.byEnd(from));
- final int startIndex1 = startIndex;
- int i = startIndex1;
- while (i < nonNestedFeatures.size())
- {
- SequenceFeature sf = nonNestedFeatures.get(i);
- if (sf.getBegin() > to)
- {
- break;
- }
- if (sf.getBegin() <= to && sf.getEnd() >= from)
- {
- result.add(sf);
- }
- i++;
+ /*
+ * feature has end >= from and end <= to
+ * i.e. contact end point lies within overlap search range
+ */
+ result.add(sf);
+ index++;
}
}
* @param to
* @param result
*/
- protected void findContactStartFeatures(long from, long to,
+ protected void findContactStartOverlaps(long from, long to,
List<SequenceFeature> result)
{
- int startPosition = binarySearch(contactFeatureStarts,
- SearchCriterion.byStart(from));
+ int index = BinarySearcher.findFirst(contactFeatureStarts,
+ f -> f.getBegin() >= from);
- for (; startPosition < contactFeatureStarts.size(); startPosition++)
+ while (index < contactFeatureStarts.size())
{
- SequenceFeature sf = contactFeatureStarts.get(startPosition);
+ SequenceFeature sf = contactFeatureStarts.get(index);
if (!sf.isContactFeature())
{
- System.err.println("Error! non-contact feature type "
- + sf.getType() + " in contact features list");
+ System.err.println("Error! non-contact feature " + sf.toString()
+ + " in contact features list");
+ index++;
continue;
}
- int begin = sf.getBegin();
- if (begin >= from && begin <= to)
+ if (sf.getBegin() > to)
{
- result.add(sf);
+ /*
+ * 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++;
}
}
*/
public List<SequenceFeature> getPositionalFeatures()
{
- /*
- * add non-nested features (may be all features for many cases)
- */
List<SequenceFeature> result = new ArrayList<>();
- result.addAll(nonNestedFeatures);
/*
* add any contact features - from the list by start position
/*
* add any nested features
*/
- if (nestedFeatures != null)
+ if (features != null)
{
- result.addAll(nestedFeatures.getEntries());
+ result.addAll(features);
}
return result;
*/
public synchronized boolean delete(SequenceFeature sf)
{
- /*
- * try the non-nested positional features first
- */
- boolean removed = nonNestedFeatures.remove(sf);
+ boolean removed = false;
/*
- * if not found, try contact positions (and if found, delete
+ * try contact positions (and if found, delete
* from both lists of contact positions)
*/
if (!removed && contactFeatureStarts != null)
/*
* if not found, try nested features
*/
- if (!removed && nestedFeatures != null)
+ if (!removed && features != null)
{
- removed = nestedFeatures.delete(sf);
+ removed = features.remove(sf);
}
if (removed)
*/
public boolean isEmpty()
{
- boolean hasFeatures = !nonNestedFeatures.isEmpty()
- || (contactFeatureStarts != null && !contactFeatureStarts
+ boolean hasFeatures = (contactFeatureStarts != null
+ && !contactFeatureStarts
.isEmpty())
|| (nonPositionalFeatures != null && !nonPositionalFeatures
.isEmpty())
- || (nestedFeatures != null && nestedFeatures.size() > 0);
+ || (features != null && features.size() > 0);
return !hasFeatures;
}
}
/**
- * Performs a binary search of the (sorted) list to find the index of the
- * first entry which returns true for the given comparator function. Returns
- * the length of the list if there is no such entry.
- *
- * @param features
- * @param sc
- * @return
- */
- protected static int binarySearch(List<SequenceFeature> features,
- SearchCriterion sc)
- {
- int start = 0;
- int end = features.size() - 1;
- int matched = features.size();
-
- while (start <= end)
- {
- int mid = (start + end) / 2;
- SequenceFeature entry = features.get(mid);
- boolean compare = sc.compare(entry);
- if (compare)
- {
- matched = mid;
- end = mid - 1;
- }
- else
- {
- start = mid + 1;
- }
- }
-
- return matched;
- }
-
- /**
* Answers the number of positional (or non-positional) features stored.
* Contact features count as 1.
*
.size();
}
- int size = nonNestedFeatures.size();
+ int size = 0;
if (contactFeatureStarts != null)
{
size += contactFeatureStarts.size();
}
- if (nestedFeatures != null)
+ if (features != null)
{
- size += nestedFeatures.size();
+ size += features.size();
}
return size;
+++ /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.ContiguousI;
-import jalview.datamodel.Range;
-
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.List;
-
-/**
- * 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 ContiguousI>
-{
- /*
- * the number of ranges 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);
- }
-
- /**
- * Sort and group ranges into sublists where each sublist represents a region
- * and its contained subregions
- *
- * @param ranges
- */
- protected void build(List<T> ranges)
- {
- /*
- * sort by start ascending so that contained intervals
- * follow their containing interval
- */
- Collections.sort(ranges, RangeComparator.BY_START_POSITION);
-
- List<Range> sublists = buildSubranges(ranges);
-
- /*
- * convert each subrange to an NCNode consisting of a range and
- * (possibly) its contained NCList
- */
- for (Range sublist : sublists)
- {
- subranges.add(new NCNode<T>(ranges.subList(sublist.start,
- sublist.end + 1)));
- }
-
- size = ranges.size();
- }
-
- public NCList(T entry)
- {
- this();
- subranges.add(new NCNode<>(entry));
- size = 1;
- }
-
- public NCList()
- {
- subranges = new ArrayList<NCNode<T>>();
- }
-
- /**
- * Traverses the sorted ranges to identify sublists, within which each
- * interval contains the one that follows it
- *
- * @param ranges
- * @return
- */
- protected List<Range> buildSubranges(List<T> ranges)
- {
- List<Range> sublists = new ArrayList<>();
-
- if (ranges.isEmpty())
- {
- return sublists;
- }
-
- int listStartIndex = 0;
- long lastEndPos = Long.MAX_VALUE;
-
- for (int i = 0; i < ranges.size(); i++)
- {
- ContiguousI nextInterval = ranges.get(i);
- long nextStart = nextInterval.getBegin();
- long nextEnd = nextInterval.getEnd();
- if (nextStart > lastEndPos || nextEnd > lastEndPos)
- {
- /*
- * this interval is not contained in the preceding one
- * close off the last sublist
- */
- sublists.add(new Range(listStartIndex, i - 1));
- listStartIndex = i;
- }
- lastEndPos = nextEnd;
- }
-
- sublists.add(new Range(listStartIndex, ranges.size() - 1));
- return sublists;
- }
-
- /**
- * Adds one entry to the stored set (with duplicates allowed)
- *
- * @param entry
- */
- public void add(T entry)
- {
- add(entry, true);
- }
-
- /**
- * Adds one entry to the stored set, and returns true, unless allowDuplicates
- * is set to false and it is already contained (by object equality test), in
- * which case it is not added and this method returns false.
- *
- * @param entry
- * @param allowDuplicates
- * @return
- */
- public synchronized boolean add(T entry, boolean allowDuplicates)
- {
- if (!allowDuplicates && contains(entry))
- {
- return false;
- }
-
- size++;
- long start = entry.getBegin();
- long end = entry.getEnd();
-
- /*
- * cases:
- * - precedes all subranges: add as NCNode on front of list
- * - follows all subranges: add as NCNode on end of list
- * - enclosed by a subrange - add recursively to subrange
- * - encloses one or more subranges - push them inside it
- * - none of the above - add as a new node and resort nodes list (?)
- */
-
- /*
- * find the first subrange whose end does not precede entry's start
- */
- int candidateIndex = findFirstOverlap(start);
- if (candidateIndex == -1)
- {
- /*
- * all subranges precede this one - add it on the end
- */
- subranges.add(new NCNode<>(entry));
- return true;
- }
-
- /*
- * 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;
- boolean overlapping = false;
-
- for (int j = candidateIndex; j < subranges.size(); j++)
- {
- NCNode<T> subrange = subranges.get(j);
-
- if (end < subrange.getBegin() && !overlapping && !enclosing)
- {
- /*
- * new entry lies between subranges j-1 j
- */
- subranges.add(j, new NCNode<>(entry));
- return true;
- }
-
- if (subrange.getBegin() <= start && subrange.getEnd() >= end)
- {
- /*
- * push new entry inside this subrange as it encloses it
- */
- subrange.add(entry);
- return true;
- }
-
- 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
- */
- addEnclosingRange(entry, firstEnclosed, lastEnclosed);
- return true;
- }
- else
- {
- /*
- * entry spans two subranges but doesn't enclose any
- * so just add it
- */
- subranges.add(j, new NCNode<>(entry));
- return true;
- }
- }
- }
- else
- {
- overlapping = true;
- }
- }
-
- /*
- * drops through to here if new range encloses all others
- * or overlaps the last one
- */
- if (enclosing)
- {
- addEnclosingRange(entry, firstEnclosed, lastEnclosed);
- }
- else
- {
- subranges.add(new NCNode<>(entry));
- }
-
- return true;
- }
-
- /**
- * Answers true if this NCList contains the given entry (by object equality
- * test), else false
- *
- * @param entry
- * @return
- */
- public boolean contains(T entry)
- {
- /*
- * find the first sublist that might overlap, i.e.
- * the first whose end position is >= from
- */
- int candidateIndex = findFirstOverlap(entry.getBegin());
-
- if (candidateIndex == -1)
- {
- return false;
- }
-
- int to = entry.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(entry))
- {
- return true;
- }
- }
- return false;
- }
-
- /**
- * Update the tree so that the range of the new entry encloses subranges i to
- * j (inclusive). That is, replace subranges i-j (inclusive) with a new
- * subrange that contains them.
- *
- * @param entry
- * @param i
- * @param j
- */
- protected synchronized void addEnclosingRange(T entry, final int i,
- final int j)
- {
- NCList<T> newNCList = new NCList<>();
- newNCList.addNodes(subranges.subList(i, j + 1));
- NCNode<T> newNode = new NCNode<>(entry, newNCList);
- for (int k = j; k >= i; k--)
- {
- subranges.remove(k);
- }
- subranges.add(i, newNode);
- }
-
- protected void addNodes(List<NCNode<T>> nodes)
- {
- for (NCNode<T> node : nodes)
- {
- subranges.add(node);
- size += node.size();
- }
- }
-
- /**
- * 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
- */
- 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 void findOverlaps(long from, long to, List<T> result)
- {
- /*
- * find the first sublist that might overlap, i.e.
- * the first whose end position is >= from
- */
- int candidateIndex = findFirstOverlap(from);
-
- if (candidateIndex == -1)
- {
- return;
- }
-
- 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);
- }
-
- }
-
- /**
- * 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 -1 if none found.
- *
- * @param from
- * @return
- */
- protected int findFirstOverlap(long from)
- {
- /*
- * The NCList paper describes binary search for this step,
- * but this not implemented here as (a) I haven't understood it yet
- * and (b) it seems to imply complications for adding to an NCList
- */
-
- int i = 0;
- if (subranges != null)
- {
- for (NCNode<T> subrange : subranges)
- {
- if (subrange.getEnd() >= from)
- {
- return i;
- }
- i++;
- }
- }
- return -1;
- }
-
- /**
- * 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();
- }
-
- /**
- * Returns a string representation of the data where containment is shown by
- * indentation on new lines
- *
- * @return
- */
- public String prettyPrint()
- {
- StringBuilder sb = new StringBuilder(512);
- int offset = 0;
- int indent = 2;
- prettyPrint(sb, offset, indent);
- sb.append(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(System.lineSeparator());
- }
- first = false;
- subrange.prettyPrint(sb, offset, indent);
- }
- }
-
- /**
- * Answers true if the data held satisfy the rules of construction of an
- * NCList, else false.
- *
- * @return
- */
- public boolean isValid()
- {
- 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.
- * <p>
- *
- * @param start
- * @param end
- * @return
- */
- boolean isValid(final int start, final int end)
- {
- int lastStart = start;
- for (NCNode<T> subrange : subranges)
- {
- if (subrange.getBegin() < lastStart)
- {
- System.err.println("error in NCList: range " + subrange.toString()
- + " starts before " + lastStart);
- return false;
- }
- if (subrange.getEnd() > end)
- {
- System.err.println("error in NCList: range " + subrange.toString()
- + " ends after " + end);
- return false;
- }
- lastStart = subrange.getBegin();
-
- if (!subrange.isValid())
- {
- return false;
- }
- }
- return true;
- }
-
- /**
- * Answers the lowest start position enclosed by the ranges
- *
- * @return
- */
- public int getStart()
- {
- return subranges.isEmpty() ? 0 : subranges.get(0).getBegin();
- }
-
- /**
- * Returns the number of ranges held (deep count)
- *
- * @return
- */
- public int size()
- {
- return size;
- }
-
- /**
- * Returns a list of all entries stored
- *
- * @return
- */
- 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);
- }
- }
-
- /**
- * Deletes the given entry from the store, returning true if it was found (and
- * deleted), else false. This method makes no assumption that the entry is in
- * the 'expected' place in the store, in case it has been modified since it
- * was added. Only the first 'same object' match is deleted, not 'equal' or
- * multiple objects.
- *
- * @param entry
- */
- public synchronized boolean delete(T entry)
- {
- if (entry == null)
- {
- return false;
- }
- for (int i = 0; i < subranges.size(); i++)
- {
- NCNode<T> subrange = subranges.get(i);
- NCList<T> subRegions = subrange.getSubRegions();
-
- if (subrange.getRegion() == entry)
- {
- /*
- * if the subrange is rooted on this entry, promote its
- * subregions (if any) to replace the subrange here;
- * NB have to resort subranges after doing this since e.g.
- * [10-30 [12-20 [16-18], 13-19]]
- * after deleting 12-20, 16-18 is promoted to sibling of 13-19
- * but should follow it in the list of subranges of 10-30
- */
- subranges.remove(i);
- if (subRegions != null)
- {
- subranges.addAll(subRegions.subranges);
- Collections.sort(subranges, RangeComparator.BY_START_POSITION);
- }
- size--;
- return true;
- }
- else
- {
- if (subRegions != null && subRegions.delete(entry))
- {
- size--;
- subrange.deleteSubRegionsIfEmpty();
- return true;
- }
- }
- }
- return false;
- }
-}
+++ /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.ContiguousI;
-
-import java.util.ArrayList;
-import java.util.List;
-
-/**
- * Each node of the NCList tree consists of a range, and (optionally) the NCList
- * of ranges it encloses
- *
- * @param <V>
- */
-class NCNode<V extends ContiguousI> implements ContiguousI
-{
- /*
- * deep size (number of ranges included)
- */
- private int size;
-
- private V region;
-
- /*
- * null, or an object holding contained subregions of this nodes region
- */
- private NCList<V> subregions;
-
- /**
- * Constructor given a list of ranges
- *
- * @param ranges
- */
- NCNode(List<V> ranges)
- {
- build(ranges);
- }
-
- /**
- * Constructor given a single range
- *
- * @param range
- */
- NCNode(V range)
- {
- List<V> ranges = new ArrayList<>();
- ranges.add(range);
- build(ranges);
- }
-
- NCNode(V entry, NCList<V> newNCList)
- {
- region = entry;
- subregions = newNCList;
- size = 1 + newNCList.size();
- }
-
- /**
- * @param ranges
- */
- protected void build(List<V> ranges)
- {
- size = ranges.size();
-
- if (!ranges.isEmpty())
- {
- region = ranges.get(0);
- }
- if (ranges.size() > 1)
- {
- subregions = new NCList<V>(ranges.subList(1, ranges.size()));
- }
- }
-
- @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>
- */
- @Override
- public String toString() {
- StringBuilder sb = new StringBuilder(10 * size);
- sb.append(region.getBegin()).append("-").append(region.getEnd());
- 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.getBegin()).append("-").append(region.getEnd());
- if (subregions != null)
- {
- sb.append(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<V> result)
- {
- if (region.getBegin() <= to && region.getEnd() >= from)
- {
- result.add(region);
- }
- if (subregions != null)
- {
- subregions.findOverlaps(from, to, result);
- }
- }
-
- /**
- * Add one range to this subrange
- *
- * @param entry
- */
- synchronized void add(V entry)
- {
- if (entry.getBegin() < region.getBegin() || entry.getEnd() > region.getEnd()) {
- 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<V>(entry);
- }
- else
- {
- subregions.add(entry);
- }
- size++;
- }
-
- /**
- * 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;
- }
- return subregions.isValid(getBegin(), getEnd());
- }
-
- /**
- * Adds all contained entries to the given list
- *
- * @param entries
- */
- void getEntries(List<V> 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(V 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
- */
- V getRegion()
- {
- return region;
- }
-
- /**
- * Answers the (possibly null) contained regions within this object
- *
- * @return
- */
- NCList<V> getSubRegions()
- {
- return subregions;
- }
-
- /**
- * Nulls the subregion reference if it is empty (after a delete entry
- * operation)
- */
- void deleteSubRegionsIfEmpty()
- {
- if (subregions != null && subregions.size() == 0)
- {
- subregions = null;
- }
- }
-
- /**
- * Answers the (deep) size of this node i.e. the number of ranges it models
- *
- * @return
- */
- int size()
- {
- return size;
- }
-}
+++ /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.ContiguousI;
-
-import java.util.Comparator;
-
-/**
- * A comparator that orders ranges by either start position or end position
- * ascending. If the position matches, ordering is resolved by end position (or
- * start position).
- *
- * @author gmcarstairs
- *
- */
-public class RangeComparator implements Comparator<ContiguousI>
-{
- public static final Comparator<ContiguousI> BY_START_POSITION = new RangeComparator(
- true);
-
- public static final Comparator<ContiguousI> BY_END_POSITION = new RangeComparator(
- false);
-
- boolean byStart;
-
- /**
- * Constructor
- *
- * @param byStartPosition
- * if true, order based on start position, if false by end position
- */
- RangeComparator(boolean byStartPosition)
- {
- byStart = byStartPosition;
- }
-
- @Override
- public int compare(ContiguousI o1, ContiguousI o2)
- {
- int len1 = o1.getEnd() - o1.getBegin();
- int len2 = o2.getEnd() - o2.getBegin();
-
- if (byStart)
- {
- return compare(o1.getBegin(), o2.getBegin(), len1, len2);
- }
- else
- {
- return compare(o1.getEnd(), o2.getEnd(), len1, len2);
- }
- }
-
- /**
- * Compares two ranges for ordering
- *
- * @param pos1
- * first range positional ordering criterion
- * @param pos2
- * second range positional ordering criterion
- * @param len1
- * first range length ordering criterion
- * @param len2
- * second range length ordering criterion
- * @return
- */
- public int compare(long pos1, long pos2, int len1, int len2)
- {
- int order = Long.compare(pos1, pos2);
- if (order == 0)
- {
- /*
- * if tied on position order, longer length sorts to left
- * i.e. the negation of normal ordering by length
- */
- order = -Integer.compare(len1, len2);
- }
- return order;
- }
-}
*/
package jalview.datamodel.features;
-import jalview.datamodel.ContiguousI;
import jalview.datamodel.SequenceFeature;
import jalview.io.gff.SequenceOntologyFactory;
import jalview.io.gff.SequenceOntologyI;
import java.util.Set;
import java.util.TreeMap;
+import intervalstore.api.IntervalI;
+
/**
* A class that stores sequence features in a way that supports efficient
* querying by type and location (overlap). Intended for (but not limited to)
/**
* a comparator for sorting features by start position ascending
*/
- private static Comparator<ContiguousI> FORWARD_STRAND = new Comparator<ContiguousI>()
+ private static Comparator<IntervalI> FORWARD_STRAND = new Comparator<IntervalI>()
{
@Override
- public int compare(ContiguousI o1, ContiguousI o2)
+ public int compare(IntervalI o1, IntervalI o2)
{
return Integer.compare(o1.getBegin(), o2.getBegin());
}
/**
* a comparator for sorting features by end position descending
*/
- private static Comparator<ContiguousI> REVERSE_STRAND = new Comparator<ContiguousI>()
+ private static Comparator<IntervalI> REVERSE_STRAND = new Comparator<IntervalI>()
{
@Override
- public int compare(ContiguousI o1, ContiguousI o2)
+ public int compare(IntervalI o1, IntervalI o2)
{
return Integer.compare(o2.getEnd(), o1.getEnd());
}
import jalview.api.AlignViewportI;
import jalview.api.FeatureColourI;
-import jalview.datamodel.Range;
import jalview.datamodel.SequenceFeature;
import jalview.datamodel.SequenceI;
import jalview.util.Comparison;
import java.awt.Graphics2D;
import java.util.List;
+import intervalstore.api.IntervalI;
+
public class FeatureRenderer extends FeatureRendererModel
{
private static final AlphaComposite NO_TRANSPARENCY = AlphaComposite
/*
* if columns are all gapped, or sequence has no features, nothing to do
*/
- Range visiblePositions = seq.findPositions(start+1, end+1);
+ IntervalI visiblePositions = seq.findPositions(start + 1, end + 1);
if (visiblePositions == null || !seq.getFeatures().hasFeatures())
{
return null;
import org.testng.annotations.BeforeMethod;
import org.testng.annotations.Test;
+import intervalstore.impl.Range;
import junit.extensions.PA;
public class SequenceTest
{
-
@BeforeClass(alwaysRun = true)
public void setUpJvOptionPane()
{
assertTrue(overlaps.contains(sf));
}
- /**
- * Tests for the method that returns false for an attempt to add a feature
- * that would enclose, or be enclosed by, another feature
- */
- @Test(groups = "Functional")
- public void testAddNonNestedFeature()
- {
- FeatureStore fs = new FeatureStore();
-
- String type = "Domain";
- SequenceFeature sf1 = new SequenceFeature(type, type, 10, 20,
- Float.NaN, null);
- assertTrue(fs.addNonNestedFeature(sf1));
-
- // co-located feature is ok
- SequenceFeature sf2 = new SequenceFeature(type, type, 10, 20,
- Float.NaN, null);
- assertTrue(fs.addNonNestedFeature(sf2));
-
- // overlap left is ok
- SequenceFeature sf3 = new SequenceFeature(type, type, 5, 15, Float.NaN,
- null);
- assertTrue(fs.addNonNestedFeature(sf3));
-
- // overlap right is ok
- SequenceFeature sf4 = new SequenceFeature(type, type, 15, 25,
- Float.NaN, null);
- assertTrue(fs.addNonNestedFeature(sf4));
-
- // add enclosing feature is not ok
- SequenceFeature sf5 = new SequenceFeature(type, type, 10, 21,
- Float.NaN, null);
- assertFalse(fs.addNonNestedFeature(sf5));
- SequenceFeature sf6 = new SequenceFeature(type, type, 4, 15, Float.NaN,
- null);
- assertFalse(fs.addNonNestedFeature(sf6));
- SequenceFeature sf7 = new SequenceFeature(type, type, 1, 50, Float.NaN,
- null);
- assertFalse(fs.addNonNestedFeature(sf7));
-
- // add enclosed feature is not ok
- SequenceFeature sf8 = new SequenceFeature(type, type, 10, 19,
- Float.NaN, null);
- assertFalse(fs.addNonNestedFeature(sf8));
- SequenceFeature sf9 = new SequenceFeature(type, type, 16, 25,
- Float.NaN, null);
- assertFalse(fs.addNonNestedFeature(sf9));
- SequenceFeature sf10 = new SequenceFeature(type, type, 7, 7, Float.NaN,
- null);
- assertFalse(fs.addNonNestedFeature(sf10));
- }
-
@Test(groups = "Functional")
public void testGetPositionalFeatures()
{
assertEquals(fs.getFeatureCount(true), 3);
assertTrue(fs.delete(sf1));
assertEquals(fs.getFeatureCount(true), 2);
- // FeatureStore should now only contain features in the NCList
- assertTrue(fs.nonNestedFeatures.isEmpty());
- assertEquals(fs.nestedFeatures.size(), 2);
+ assertEquals(fs.features.size(), 2);
assertFalse(fs.isEmpty());
assertTrue(fs.delete(sf2));
assertEquals(fs.getFeatureCount(true), 1);
public void testListContains()
{
assertFalse(FeatureStore.listContains(null, null));
- List<SequenceFeature> features = new ArrayList<SequenceFeature>();
+ List<SequenceFeature> features = new ArrayList<>();
assertFalse(FeatureStore.listContains(features, null));
SequenceFeature sf1 = new SequenceFeature("type1", "desc1", 20, 30, 3f,
assertEquals(features.size(), 2);
assertTrue(features.contains(sf1));
assertTrue(features.contains(sf2));
- assertTrue(store.nonNestedFeatures.contains(sf1));
- assertTrue(store.nestedFeatures.contains(sf2));
+ assertTrue(store.features.contains(sf1));
+ assertTrue(store.features.contains(sf2));
/*
* delete the first feature
+++ /dev/null
-package jalview.datamodel.features;
-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 jalview.datamodel.ContiguousI;
-import jalview.datamodel.Range;
-import jalview.datamodel.SequenceFeature;
-
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.Comparator;
-import java.util.List;
-import java.util.Random;
-
-import junit.extensions.PA;
-
-import org.testng.annotations.DataProvider;
-import org.testng.annotations.Test;
-
-public class NCListTest
-{
-
- private Random random = new Random(107);
-
- private Comparator<ContiguousI> sorter = new RangeComparator(true);
-
- /**
- * A basic sanity test of the constructor
- */
- @Test(groups = "Functional")
- public void testConstructor()
- {
- List<Range> ranges = new ArrayList<Range>();
- ranges.add(new Range(20, 20));
- ranges.add(new Range(10, 20));
- ranges.add(new Range(15, 30));
- ranges.add(new Range(10, 30));
- ranges.add(new Range(11, 19));
- ranges.add(new Range(10, 20));
- ranges.add(new Range(1, 100));
-
- NCList<Range> ncl = new NCList<Range>(ranges);
- String expected = "[1-100 [10-30 [10-20 [10-20 [11-19]]]], 15-30 [20-20]]";
- assertEquals(ncl.toString(), expected);
- assertTrue(ncl.isValid());
-
- Collections.reverse(ranges);
- ncl = new NCList<Range>(ranges);
- assertEquals(ncl.toString(), expected);
- assertTrue(ncl.isValid());
- }
-
- @Test(groups = "Functional")
- public void testFindOverlaps()
- {
- List<Range> ranges = new ArrayList<Range>();
- ranges.add(new Range(20, 50));
- ranges.add(new Range(30, 70));
- ranges.add(new Range(1, 100));
- ranges.add(new Range(70, 120));
-
- NCList<Range> ncl = new NCList<Range>(ranges);
-
- List<Range> overlaps = ncl.findOverlaps(121, 122);
- assertEquals(overlaps.size(), 0);
-
- overlaps = ncl.findOverlaps(21, 22);
- assertEquals(overlaps.size(), 2);
- assertEquals(((ContiguousI) overlaps.get(0)).getBegin(), 1);
- assertEquals(((ContiguousI) overlaps.get(0)).getEnd(), 100);
- assertEquals(((ContiguousI) overlaps.get(1)).getBegin(), 20);
- assertEquals(((ContiguousI) overlaps.get(1)).getEnd(), 50);
-
- overlaps = ncl.findOverlaps(110, 110);
- assertEquals(overlaps.size(), 1);
- assertEquals(((ContiguousI) overlaps.get(0)).getBegin(), 70);
- assertEquals(((ContiguousI) overlaps.get(0)).getEnd(), 120);
- }
-
- @Test(groups = "Functional")
- public void testAdd_onTheEnd()
- {
- List<Range> ranges = new ArrayList<Range>();
- ranges.add(new Range(20, 50));
- NCList<Range> ncl = new NCList<Range>(ranges);
- assertEquals(ncl.toString(), "[20-50]");
- assertTrue(ncl.isValid());
-
- ncl.add(new Range(60, 70));
- assertEquals(ncl.toString(), "[20-50, 60-70]");
- assertTrue(ncl.isValid());
- }
-
- @Test(groups = "Functional")
- public void testAdd_inside()
- {
- List<Range> ranges = new ArrayList<Range>();
- ranges.add(new Range(20, 50));
- NCList<Range> ncl = new NCList<Range>(ranges);
- assertEquals(ncl.toString(), "[20-50]");
- assertTrue(ncl.isValid());
-
- ncl.add(new Range(30, 40));
- assertEquals(ncl.toString(), "[20-50 [30-40]]");
- }
-
- @Test(groups = "Functional")
- public void testAdd_onTheFront()
- {
- List<Range> ranges = new ArrayList<Range>();
- ranges.add(new Range(20, 50));
- NCList<Range> ncl = new NCList<Range>(ranges);
- assertEquals(ncl.toString(), "[20-50]");
- assertTrue(ncl.isValid());
-
- ncl.add(new Range(5, 15));
- assertEquals(ncl.toString(), "[5-15, 20-50]");
- assertTrue(ncl.isValid());
- }
-
- @Test(groups = "Functional")
- public void testAdd_enclosing()
- {
- List<Range> ranges = new ArrayList<Range>();
- ranges.add(new Range(20, 50));
- ranges.add(new Range(30, 60));
- NCList<Range> ncl = new NCList<Range>(ranges);
- assertEquals(ncl.toString(), "[20-50, 30-60]");
- assertTrue(ncl.isValid());
- assertEquals(ncl.getStart(), 20);
-
- ncl.add(new Range(10, 70));
- assertEquals(ncl.toString(), "[10-70 [20-50, 30-60]]");
- assertTrue(ncl.isValid());
- }
-
- @Test(groups = "Functional")
- public void testAdd_spanning()
- {
- List<Range> ranges = new ArrayList<Range>();
- ranges.add(new Range(20, 40));
- ranges.add(new Range(60, 70));
- NCList<Range> ncl = new NCList<Range>(ranges);
- assertEquals(ncl.toString(), "[20-40, 60-70]");
- assertTrue(ncl.isValid());
-
- ncl.add(new Range(30, 50));
- assertEquals(ncl.toString(), "[20-40, 30-50, 60-70]");
- assertTrue(ncl.isValid());
-
- ncl.add(new Range(40, 65));
- assertEquals(ncl.toString(), "[20-40, 30-50, 40-65, 60-70]");
- assertTrue(ncl.isValid());
- }
-
- /**
- * Provides the scales for pseudo-random NCLists i.e. the range of the maximal
- * [0-scale] interval to be stored
- *
- * @return
- */
- @DataProvider(name = "scalesOfLife")
- public Object[][] getScales()
- {
- return new Object[][] { new Integer[] { 10 }, new Integer[] { 100 } };
- }
-
- /**
- * Do a number of pseudo-random (reproducible) builds of an NCList, to
- * exercise as many methods of the class as possible while generating the
- * range of possible structure topologies
- * <ul>
- * <li>verify that add adds an entry and increments size</li>
- * <li>...except where the entry is already contained (by equals test)</li>
- * <li>verify that the structure is valid at all stages of construction</li>
- * <li>generate, run and verify a range of overlap queries</li>
- * <li>tear down the structure by deleting entries, verifying correctness at
- * each stage</li>
- * </ul>
- */
- @Test(groups = "Functional", dataProvider = "scalesOfLife")
- public void test_pseudoRandom(Integer scale)
- {
- NCList<SequenceFeature> ncl = new NCList<SequenceFeature>();
- List<SequenceFeature> features = new ArrayList<SequenceFeature>(scale);
-
- testAdd_pseudoRandom(scale, ncl, features);
-
- /*
- * sort the list of added ranges - this doesn't affect the test,
- * just makes it easier to inspect the data in the debugger
- */
- Collections.sort(features, sorter);
-
- testFindOverlaps_pseudoRandom(ncl, scale, features);
-
- testDelete_pseudoRandom(ncl, features);
- }
-
- /**
- * Pick randomly selected entries to delete in turn, checking the NCList size
- * and validity at each stage, until it is empty
- *
- * @param ncl
- * @param features
- */
- protected void testDelete_pseudoRandom(NCList<SequenceFeature> ncl,
- List<SequenceFeature> features)
- {
- int deleted = 0;
-
- while (!features.isEmpty())
- {
- assertEquals(ncl.size(), features.size());
- int toDelete = random.nextInt(features.size());
- SequenceFeature entry = features.get(toDelete);
- assertTrue(ncl.contains(entry), String.format(
- "NCList doesn't contain entry [%d] '%s'!", deleted,
- entry.toString()));
-
- ncl.delete(entry);
- assertFalse(ncl.contains(entry), String.format(
- "NCList still contains deleted entry [%d] '%s'!", deleted,
- entry.toString()));
- features.remove(toDelete);
- deleted++;
-
- assertTrue(ncl.isValid(), String.format(
- "NCList invalid after %d deletions, last deleted was '%s'",
- deleted, entry.toString()));
-
- /*
- * brute force check that deleting one entry didn't delete any others
- */
- for (int i = 0; i < features.size(); i++)
- {
- SequenceFeature sf = features.get(i);
- assertTrue(ncl.contains(sf), String.format(
- "NCList doesn't contain entry [%d] %s after deleting '%s'!",
- i, sf.toString(), entry.toString()));
- }
- }
- assertEquals(ncl.size(), 0); // all gone
- }
-
- /**
- * Randomly generate entries and add them to the NCList, checking its validity
- * and size at each stage. A few entries should be duplicates (by equals test)
- * so not get added.
- *
- * @param scale
- * @param ncl
- * @param features
- */
- protected void testAdd_pseudoRandom(Integer scale,
- NCList<SequenceFeature> ncl,
- List<SequenceFeature> features)
- {
- int count = 0;
- final int size = 50;
-
- for (int i = 0; i < size; i++)
- {
- int r1 = random.nextInt(scale + 1);
- int r2 = random.nextInt(scale + 1);
- int from = Math.min(r1, r2);
- int to = Math.max(r1, r2);
-
- /*
- * choice of two feature values means that occasionally an identical
- * feature may be generated, in which case it should not be added
- */
- float value = (float) i % 2;
- SequenceFeature feature = new SequenceFeature("Pfam", "", from, to,
- value, "group");
-
- /*
- * add to NCList - with duplicate entries (by equals) disallowed
- */
- ncl.add(feature, false);
- if (features.contains(feature))
- {
- System.out.println("Duplicate feature generated "
- + feature.toString());
- }
- else
- {
- features.add(feature);
- count++;
- }
-
- /*
- * check list format is valid at each stage of its construction
- */
- assertTrue(ncl.isValid(),
- String.format("Failed for scale = %d, i=%d", scale, i));
- assertEquals(ncl.size(), count);
- }
- // System.out.println(ncl.prettyPrint());
- }
-
- /**
- * A helper method that generates pseudo-random range queries and veries that
- * findOverlaps returns the correct matches
- *
- * @param ncl
- * the NCList to query
- * @param scale
- * ncl maximal range is [0, scale]
- * @param features
- * a list of the ranges stored in ncl
- */
- protected void testFindOverlaps_pseudoRandom(NCList<SequenceFeature> ncl,
- int scale,
- List<SequenceFeature> features)
- {
- int halfScale = scale / 2;
- int minIterations = 20;
-
- /*
- * generates ranges in [-halfScale, scale+halfScale]
- * - some should be internal to [0, scale] P = 1/4
- * - some should lie before 0 P = 1/16
- * - some should lie after scale P = 1/16
- * - some should overlap left P = 1/4
- * - some should overlap right P = 1/4
- * - some should enclose P = 1/8
- *
- * 50 iterations give a 96% probability of including the
- * unlikeliest case; keep going until we have done all!
- */
- boolean inside = false;
- boolean enclosing = false;
- boolean before = false;
- boolean after = false;
- boolean overlapLeft = false;
- boolean overlapRight = false;
- boolean allCasesCovered = false;
-
- int i = 0;
- while (i < minIterations || !allCasesCovered)
- {
- i++;
- int r1 = random.nextInt((scale + 1) * 2);
- int r2 = random.nextInt((scale + 1) * 2);
- int from = Math.min(r1, r2) - halfScale;
- int to = Math.max(r1, r2) - halfScale;
-
- /*
- * ensure all cases of interest get covered
- */
- inside |= from >= 0 && to <= scale;
- enclosing |= from <= 0 && to >= scale;
- before |= to < 0;
- after |= from > scale;
- overlapLeft |= from < 0 && to >= 0 && to <= scale;
- overlapRight |= from >= 0 && from <= scale && to > scale;
- if (!allCasesCovered)
- {
- allCasesCovered |= inside && enclosing && before && after
- && overlapLeft && overlapRight;
- if (allCasesCovered)
- {
- System.out
- .println(String
- .format("Covered all findOverlaps cases after %d iterations for scale %d",
- i, scale));
- }
- }
-
- verifyFindOverlaps(ncl, from, to, features);
- }
- }
-
- /**
- * A helper method that verifies that overlaps found by interrogating an
- * NCList correctly match those found by brute force search
- *
- * @param ncl
- * @param from
- * @param to
- * @param features
- */
- protected void verifyFindOverlaps(NCList<SequenceFeature> ncl, int from,
- int to, List<SequenceFeature> features)
- {
- List<SequenceFeature> overlaps = ncl.findOverlaps(from, to);
-
- /*
- * check returned entries do indeed overlap from-to range
- */
- for (ContiguousI sf : overlaps)
- {
- int begin = sf.getBegin();
- int end = sf.getEnd();
- assertTrue(begin <= to && end >= from, String.format(
- "[%d, %d] does not overlap query range [%d, %d]", begin, end,
- from, to));
- }
-
- /*
- * check overlapping ranges are included in the results
- * (the test above already shows non-overlapping ranges are not)
- */
- for (ContiguousI sf : features)
- {
- int begin = sf.getBegin();
- int end = sf.getEnd();
- if (begin <= to && end >= from)
- {
- boolean found = overlaps.contains(sf);
- assertTrue(found, String.format(
- "[%d, %d] missing in query range [%d, %d]", begin, end,
- from, to));
- }
- }
- }
-
- @Test(groups = "Functional")
- public void testGetEntries()
- {
- List<Range> ranges = new ArrayList<Range>();
- Range r1 = new Range(20, 20);
- Range r2 = new Range(10, 20);
- Range r3 = new Range(15, 30);
- Range r4 = new Range(10, 30);
- Range r5 = new Range(11, 19);
- Range r6 = new Range(10, 20);
- ranges.add(r1);
- ranges.add(r2);
- ranges.add(r3);
- ranges.add(r4);
- ranges.add(r5);
- ranges.add(r6);
-
- NCList<Range> ncl = new NCList<Range>(ranges);
- Range r7 = new Range(1, 100);
- ncl.add(r7);
-
- List<Range> contents = ncl.getEntries();
- assertEquals(contents.size(), 7);
- assertTrue(contents.contains(r1));
- assertTrue(contents.contains(r2));
- assertTrue(contents.contains(r3));
- assertTrue(contents.contains(r4));
- assertTrue(contents.contains(r5));
- assertTrue(contents.contains(r6));
- assertTrue(contents.contains(r7));
-
- ncl = new NCList<Range>();
- assertTrue(ncl.getEntries().isEmpty());
- }
-
- @Test(groups = "Functional")
- public void testDelete()
- {
- List<Range> ranges = new ArrayList<Range>();
- Range r1 = new Range(20, 30);
- ranges.add(r1);
- NCList<Range> ncl = new NCList<Range>(ranges);
- assertTrue(ncl.getEntries().contains(r1));
-
- Range r2 = new Range(20, 30);
- assertFalse(ncl.delete(null)); // null argument
- assertFalse(ncl.delete(r2)); // never added
- assertTrue(ncl.delete(r1)); // success
- assertTrue(ncl.getEntries().isEmpty());
-
- /*
- * tests where object.equals() == true
- */
- NCList<SequenceFeature> features = new NCList<SequenceFeature>();
- SequenceFeature sf1 = new SequenceFeature("type", "desc", 1, 10, 2f,
- "group");
- SequenceFeature sf2 = new SequenceFeature("type", "desc", 1, 10, 2f,
- "group");
- features.add(sf1);
- assertEquals(sf1, sf2); // sf1.equals(sf2)
- assertFalse(features.delete(sf2)); // equality is not enough for deletion
- assertTrue(features.getEntries().contains(sf1)); // still there!
- assertTrue(features.delete(sf1));
- assertTrue(features.getEntries().isEmpty()); // gone now
-
- /*
- * test with duplicate objects in NCList
- */
- features.add(sf1);
- features.add(sf1);
- assertEquals(features.getEntries().size(), 2);
- assertSame(features.getEntries().get(0), sf1);
- assertSame(features.getEntries().get(1), sf1);
- assertTrue(features.delete(sf1)); // first match only is deleted
- assertTrue(features.contains(sf1));
- assertEquals(features.size(), 1);
- assertTrue(features.delete(sf1));
- assertTrue(features.getEntries().isEmpty());
- }
-
- @Test(groups = "Functional")
- public void testAdd_overlapping()
- {
- List<Range> ranges = new ArrayList<Range>();
- ranges.add(new Range(40, 50));
- ranges.add(new Range(20, 30));
- NCList<Range> ncl = new NCList<Range>(ranges);
- assertEquals(ncl.toString(), "[20-30, 40-50]");
- assertTrue(ncl.isValid());
-
- /*
- * add range overlapping internally
- */
- ncl.add(new Range(25, 35));
- assertEquals(ncl.toString(), "[20-30, 25-35, 40-50]");
- assertTrue(ncl.isValid());
-
- /*
- * add range overlapping last range
- */
- ncl.add(new Range(45, 55));
- assertEquals(ncl.toString(), "[20-30, 25-35, 40-50, 45-55]");
- assertTrue(ncl.isValid());
-
- /*
- * add range overlapping first range
- */
- ncl.add(new Range(15, 25));
- assertEquals(ncl.toString(), "[15-25, 20-30, 25-35, 40-50, 45-55]");
- assertTrue(ncl.isValid());
- }
-
- /**
- * Test the contains method (which uses object equals test)
- */
- @Test(groups = "Functional")
- public void testContains()
- {
- NCList<SequenceFeature> ncl = new NCList<SequenceFeature>();
- SequenceFeature sf1 = new SequenceFeature("type", "desc", 1, 10, 2f,
- "group");
- SequenceFeature sf2 = new SequenceFeature("type", "desc", 1, 10, 2f,
- "group");
- SequenceFeature sf3 = new SequenceFeature("type", "desc", 1, 10, 2f,
- "anothergroup");
- ncl.add(sf1);
-
- assertTrue(ncl.contains(sf1));
- assertTrue(ncl.contains(sf2)); // sf1.equals(sf2)
- assertFalse(ncl.contains(sf3)); // !sf1.equals(sf3)
-
- /*
- * make some deeper structure in the NCList
- */
- SequenceFeature sf4 = new SequenceFeature("type", "desc", 2, 9, 2f,
- "group");
- ncl.add(sf4);
- assertTrue(ncl.contains(sf4));
- SequenceFeature sf5 = new SequenceFeature("type", "desc", 4, 5, 2f,
- "group");
- SequenceFeature sf6 = new SequenceFeature("type", "desc", 6, 8, 2f,
- "group");
- ncl.add(sf5);
- ncl.add(sf6);
- assertTrue(ncl.contains(sf5));
- assertTrue(ncl.contains(sf6));
- }
-
- @Test(groups = "Functional")
- public void testIsValid()
- {
- List<Range> ranges = new ArrayList<Range>();
- Range r1 = new Range(40, 50);
- ranges.add(r1);
- NCList<Range> ncl = new NCList<Range>(ranges);
- assertTrue(ncl.isValid());
-
- Range r2 = new Range(42, 44);
- ncl.add(r2);
- assertTrue(ncl.isValid());
- Range r3 = new Range(46, 48);
- ncl.add(r3);
- assertTrue(ncl.isValid());
- Range r4 = new Range(43, 43);
- ncl.add(r4);
- assertTrue(ncl.isValid());
-
- assertEquals(ncl.toString(), "[40-50 [42-44 [43-43], 46-48]]");
- assertTrue(ncl.isValid());
-
- PA.setValue(r1, "start", 43);
- assertFalse(ncl.isValid()); // r2 not inside r1
- PA.setValue(r1, "start", 40);
- assertTrue(ncl.isValid());
-
- PA.setValue(r3, "start", 41);
- assertFalse(ncl.isValid()); // r3 should precede r2
- PA.setValue(r3, "start", 46);
- assertTrue(ncl.isValid());
-
- PA.setValue(r4, "start", 41);
- assertFalse(ncl.isValid()); // r4 not inside r2
- PA.setValue(r4, "start", 43);
- assertTrue(ncl.isValid());
-
- PA.setValue(r4, "start", 44);
- assertFalse(ncl.isValid()); // r4 has reverse range
- }
-
- @Test(groups = "Functional")
- public void testPrettyPrint()
- {
- /*
- * construct NCList from a list of ranges
- * they are sorted then assembled into NCList subregions
- * notice that 42-42 end up inside 41-46
- */
- List<Range> ranges = new ArrayList<Range>();
- ranges.add(new Range(40, 50));
- ranges.add(new Range(45, 55));
- ranges.add(new Range(40, 45));
- ranges.add(new Range(41, 46));
- ranges.add(new Range(42, 42));
- ranges.add(new Range(42, 42));
- NCList<Range> ncl = new NCList<Range>(ranges);
- assertTrue(ncl.isValid());
- assertEquals(ncl.toString(),
- "[40-50 [40-45], 41-46 [42-42 [42-42]], 45-55]");
- String expected = "40-50\n 40-45\n41-46\n 42-42\n 42-42\n45-55\n";
- assertEquals(ncl.prettyPrint(), expected);
-
- /*
- * repeat but now add ranges one at a time
- * notice that 42-42 end up inside 40-50 so we get
- * a different but equal valid NCList structure
- */
- ranges.clear();
- ncl = new NCList<Range>(ranges);
- ncl.add(new Range(40, 50));
- ncl.add(new Range(45, 55));
- ncl.add(new Range(40, 45));
- ncl.add(new Range(41, 46));
- ncl.add(new Range(42, 42));
- ncl.add(new Range(42, 42));
- assertTrue(ncl.isValid());
- assertEquals(ncl.toString(),
- "[40-50 [40-45 [42-42 [42-42]], 41-46], 45-55]");
- expected = "40-50\n 40-45\n 42-42\n 42-42\n 41-46\n45-55\n";
- assertEquals(ncl.prettyPrint(), expected);
- }
-
- /**
- * A test that shows different valid trees can be constructed from the same
- * set of ranges, depending on the order of construction
- */
- @Test(groups = "Functional")
- public void testConstructor_alternativeTrees()
- {
- List<Range> ranges = new ArrayList<Range>();
- ranges.add(new Range(10, 60));
- ranges.add(new Range(20, 30));
- ranges.add(new Range(40, 50));
-
- /*
- * constructor with greedy traversal of sorted ranges to build nested
- * containment lists results in 20-30 inside 10-60, 40-50 a sibling
- */
- NCList<Range> ncl = new NCList<Range>(ranges);
- assertEquals(ncl.toString(), "[10-60 [20-30], 40-50]");
- assertTrue(ncl.isValid());
-
- /*
- * adding ranges one at a time results in 40-50
- * a sibling of 20-30 inside 10-60
- */
- ncl = new NCList<Range>(new Range(10, 60));
- ncl.add(new Range(20, 30));
- ncl.add(new Range(40, 50));
- assertEquals(ncl.toString(), "[10-60 [20-30, 40-50]]");
- assertTrue(ncl.isValid());
- }
-}
+++ /dev/null
-package jalview.datamodel.features;
-
-import static org.testng.Assert.assertEquals;
-import static org.testng.Assert.assertFalse;
-import static org.testng.Assert.assertTrue;
-
-import jalview.datamodel.Range;
-import jalview.datamodel.SequenceFeature;
-
-import java.util.ArrayList;
-import java.util.List;
-
-import junit.extensions.PA;
-
-import org.testng.annotations.Test;
-
-public class NCNodeTest
-{
- @Test(groups = "Functional")
- public void testAdd()
- {
- Range r1 = new Range(10, 20);
- NCNode<Range> node = new NCNode<Range>(r1);
- assertEquals(node.getBegin(), 10);
- Range r2 = new Range(10, 15);
- node.add(r2);
-
- List<Range> contents = new ArrayList<Range>();
- node.getEntries(contents);
- assertEquals(contents.size(), 2);
- assertTrue(contents.contains(r1));
- assertTrue(contents.contains(r2));
- }
-
- @Test(
- groups = "Functional",
- expectedExceptions = { IllegalArgumentException.class })
- public void testAdd_invalidRangeStart()
- {
- Range r1 = new Range(10, 20);
- NCNode<Range> node = new NCNode<Range>(r1);
- assertEquals(node.getBegin(), 10);
- Range r2 = new Range(9, 15);
- node.add(r2);
- }
-
- @Test(
- groups = "Functional",
- expectedExceptions = { IllegalArgumentException.class })
- public void testAdd_invalidRangeEnd()
- {
- Range r1 = new Range(10, 20);
- NCNode<Range> node = new NCNode<Range>(r1);
- assertEquals(node.getBegin(), 10);
- Range r2 = new Range(12, 21);
- node.add(r2);
- }
-
- @Test(groups = "Functional")
- public void testGetEntries()
- {
- Range r1 = new Range(10, 20);
- NCNode<Range> node = new NCNode<Range>(r1);
- List<Range> entries = new ArrayList<Range>();
-
- node.getEntries(entries);
- assertEquals(entries.size(), 1);
- assertTrue(entries.contains(r1));
-
- // clearing the returned list does not affect the NCNode
- entries.clear();
- node.getEntries(entries);
- assertEquals(entries.size(), 1);
- assertTrue(entries.contains(r1));
-
- Range r2 = new Range(15, 18);
- node.add(r2);
- entries.clear();
- node.getEntries(entries);
- assertEquals(entries.size(), 2);
- assertTrue(entries.contains(r1));
- assertTrue(entries.contains(r2));
- }
-
- /**
- * Tests for the contains method (uses entry.equals() test)
- */
- @Test(groups = "Functional")
- public void testContains()
- {
- SequenceFeature sf1 = new SequenceFeature("type", "desc", 1, 10, 2f,
- "group");
- SequenceFeature sf2 = new SequenceFeature("type", "desc", 1, 10, 2f,
- "group");
- SequenceFeature sf3 = new SequenceFeature("type", "desc", 1, 10, 2f,
- "anothergroup");
- NCNode<SequenceFeature> node = new NCNode<SequenceFeature>(sf1);
-
- assertFalse(node.contains(null));
- assertTrue(node.contains(sf1));
- assertTrue(node.contains(sf2)); // sf1.equals(sf2)
- assertFalse(node.contains(sf3)); // !sf1.equals(sf3)
- }
-
- /**
- * Test method that checks for valid structure. Valid means that all
- * subregions (if any) lie within the root range, and that all subregions have
- * valid structure.
- */
- @Test(groups = "Functional")
- public void testIsValid()
- {
- Range r1 = new Range(10, 20);
- Range r2 = new Range(14, 15);
- Range r3 = new Range(16, 17);
- NCNode<Range> node = new NCNode<Range>(r1);
- node.add(r2);
- node.add(r3);
-
- /*
- * node has root range [10-20] and contains an
- * NCList of [14-15, 16-17]
- */
- assertTrue(node.isValid());
- PA.setValue(r1, "start", 15);
- assertFalse(node.isValid()); // r2 not within r1
- PA.setValue(r1, "start", 10);
- assertTrue(node.isValid());
- PA.setValue(r1, "end", 16);
- assertFalse(node.isValid()); // r3 not within r1
- PA.setValue(r1, "end", 20);
- assertTrue(node.isValid());
- PA.setValue(r3, "start", 12);
- assertFalse(node.isValid()); // r3 should precede r2
- }
-}
+++ /dev/null
-package jalview.datamodel.features;
-
-import static org.testng.Assert.assertEquals;
-
-import jalview.datamodel.ContiguousI;
-import jalview.datamodel.Range;
-
-import java.util.Comparator;
-
-import org.testng.annotations.Test;
-
-public class RangeComparatorTest
-{
-
- @Test(groups = "Functional")
- public void testCompare()
- {
- RangeComparator comp = new RangeComparator(true);
-
- // same position, same length
- assertEquals(comp.compare(10, 10, 20, 20), 0);
- // same position, len1 > len2
- assertEquals(comp.compare(10, 10, 20, 19), -1);
- // same position, len1 < len2
- assertEquals(comp.compare(10, 10, 20, 21), 1);
- // pos1 > pos2
- assertEquals(comp.compare(11, 10, 20, 20), 1);
- // pos1 < pos2
- assertEquals(comp.compare(10, 11, 20, 10), -1);
- }
-
- @Test(groups = "Functional")
- public void testCompare_byStart()
- {
- Comparator<ContiguousI> comp = RangeComparator.BY_START_POSITION;
-
- // same start position, same length
- assertEquals(comp.compare(new Range(10, 20), new Range(10, 20)), 0);
- // same start position, len1 > len2
- assertEquals(comp.compare(new Range(10, 20), new Range(10, 19)), -1);
- // same start position, len1 < len2
- assertEquals(comp.compare(new Range(10, 18), new Range(10, 20)), 1);
- // pos1 > pos2
- assertEquals(comp.compare(new Range(11, 20), new Range(10, 20)), 1);
- // pos1 < pos2
- assertEquals(comp.compare(new Range(10, 20), new Range(11, 20)), -1);
- }
-
- @Test(groups = "Functional")
- public void testCompare_byEnd()
- {
- Comparator<ContiguousI> comp = RangeComparator.BY_END_POSITION;
-
- // same end position, same length
- assertEquals(comp.compare(new Range(10, 20), new Range(10, 20)), 0);
- // same end position, len1 > len2
- assertEquals(comp.compare(new Range(10, 20), new Range(11, 20)), -1);
- // same end position, len1 < len2
- assertEquals(comp.compare(new Range(11, 20), new Range(10, 20)), 1);
- // end1 > end2
- assertEquals(comp.compare(new Range(10, 21), new Range(10, 20)), 1);
- // end1 < end2
- assertEquals(comp.compare(new Range(10, 20), new Range(10, 21)), -1);
- }
-}
git://source.jalview.org / jalview.git / commitdiff