From: gmungoc Date: Thu, 29 Nov 2018 09:42:43 +0000 (+0000) Subject: JAL-3140 NCList now via IntervalStore library X-Git-Tag: Release_2_11_0~17^2~91^2^2~5 X-Git-Url: http://source.jalview.org/gitweb/?p=jalview.git;a=commitdiff_plain;h=81d2ea57ab71c0806a036833f73711bc4ad5c76d JAL-3140 NCList now via IntervalStore library --- diff --git a/.classpath b/.classpath index 0da91bb..f964086 100644 --- a/.classpath +++ b/.classpath @@ -70,5 +70,6 @@ + diff --git a/src/jalview/datamodel/Range.java b/src/jalview/datamodel/Range.java deleted file mode 100644 index 8b6f617..0000000 --- a/src/jalview/datamodel/Range.java +++ /dev/null @@ -1,72 +0,0 @@ -/* - * 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 . - * 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; - } -} diff --git a/src/jalview/datamodel/Sequence.java b/src/jalview/datamodel/Sequence.java index 33de452..674fabe 100755 --- a/src/jalview/datamodel/Sequence.java +++ b/src/jalview/datamodel/Sequence.java @@ -40,6 +40,8 @@ import java.util.ListIterator; import java.util.Vector; import fr.orsay.lri.varna.models.rna.RNA; +import intervalstore.api.IntervalI; +import intervalstore.impl.Range; /** * @@ -1069,7 +1071,7 @@ public class Sequence extends ASequence implements SequenceI * {@inheritDoc} */ @Override - public Range findPositions(int fromColumn, int toColumn) + public IntervalI findPositions(int fromColumn, int toColumn) { if (toColumn < fromColumn || fromColumn < 1) { diff --git a/src/jalview/datamodel/SequenceI.java b/src/jalview/datamodel/SequenceI.java index 8dce31e..ed8e8e4 100755 --- a/src/jalview/datamodel/SequenceI.java +++ b/src/jalview/datamodel/SequenceI.java @@ -29,6 +29,7 @@ import java.util.List; 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 @@ -213,7 +214,7 @@ public interface SequenceI extends ASequenceI * @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 diff --git a/src/jalview/datamodel/features/FeatureLocationI.java b/src/jalview/datamodel/features/FeatureLocationI.java index 378b8db..535346c 100644 --- a/src/jalview/datamodel/features/FeatureLocationI.java +++ b/src/jalview/datamodel/features/FeatureLocationI.java @@ -20,13 +20,13 @@ */ 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(); } diff --git a/src/jalview/datamodel/features/FeatureStore.java b/src/jalview/datamodel/features/FeatureStore.java index 02ce1c5..1347213 100644 --- a/src/jalview/datamodel/features/FeatureStore.java +++ b/src/jalview/datamodel/features/FeatureStore.java @@ -20,16 +20,18 @@ */ 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 @@ -40,80 +42,6 @@ import java.util.Set; */ 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 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. @@ -121,14 +49,6 @@ public class FeatureStore List 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 nonNestedFeatures; - - /* * contact features ordered by first contact position */ List contactFeatureStarts; @@ -139,13 +59,10 @@ public class FeatureStore List 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 nestedFeatures; + IntervalStoreI features; /* * Feature groups represented in stored positional features @@ -178,16 +95,15 @@ public class FeatureStore */ public FeatureStore() { - nonNestedFeatures = new ArrayList(); - positionalFeatureGroups = new HashSet(); - nonPositionalFeatureGroups = new HashSet(); + 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 } /** @@ -213,58 +129,46 @@ public class FeatureStore 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; } /** @@ -288,12 +192,7 @@ public class FeatureStore contactFeatureStarts, feature); } - if (listContains(nonNestedFeatures, feature)) - { - return true; - } - - return nestedFeatures == null ? false : nestedFeatures + return features == null ? false : features .contains(feature); } @@ -330,7 +229,7 @@ public class FeatureStore { if (nonPositionalFeatures == null) { - nonPositionalFeatures = new ArrayList(); + nonPositionalFeatures = new ArrayList<>(); } nonPositionalFeatures.add(feature); @@ -341,91 +240,16 @@ public class FeatureStore } /** - * 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); } /** @@ -441,28 +265,29 @@ public class FeatureStore { if (contactFeatureStarts == null) { - contactFeatureStarts = new ArrayList(); + contactFeatureStarts = new ArrayList<>(); } if (contactFeatureEnds == null) { - contactFeatureEnds = 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 = 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; } @@ -487,8 +312,10 @@ public class FeatureStore /* * 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) { @@ -521,13 +348,11 @@ public class FeatureStore { List 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; @@ -546,11 +371,11 @@ public class FeatureStore { if (contactFeatureStarts != null) { - findContactStartFeatures(from, to, result); + findContactStartOverlaps(from, to, result); } if (contactFeatureEnds != null) { - findContactEndFeatures(from, to, result); + findContactEndOverlaps(from, to, result); } } @@ -563,22 +388,24 @@ public class FeatureStore * @param to * @param result */ - protected void findContactEndFeatures(long from, long to, + protected void findContactEndOverlaps(long from, long to, List 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; } @@ -589,54 +416,24 @@ public class FeatureStore * 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 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++; } } @@ -648,26 +445,36 @@ public class FeatureStore * @param to * @param result */ - protected void findContactStartFeatures(long from, long to, + protected void findContactStartOverlaps(long from, long to, List 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++; } } @@ -678,11 +485,7 @@ public class FeatureStore */ public List getPositionalFeatures() { - /* - * add non-nested features (may be all features for many cases) - */ List result = new ArrayList<>(); - result.addAll(nonNestedFeatures); /* * add any contact features - from the list by start position @@ -695,9 +498,9 @@ public class FeatureStore /* * add any nested features */ - if (nestedFeatures != null) + if (features != null) { - result.addAll(nestedFeatures.getEntries()); + result.addAll(features); } return result; @@ -743,13 +546,10 @@ public class FeatureStore */ 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) @@ -775,9 +575,9 @@ public class FeatureStore /* * if not found, try nested features */ - if (!removed && nestedFeatures != null) + if (!removed && features != null) { - removed = nestedFeatures.delete(sf); + removed = features.remove(sf); } if (removed) @@ -874,12 +674,12 @@ public class FeatureStore */ 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; } @@ -907,41 +707,6 @@ public class FeatureStore } /** - * 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 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. * @@ -956,7 +721,7 @@ public class FeatureStore .size(); } - int size = nonNestedFeatures.size(); + int size = 0; if (contactFeatureStarts != null) { @@ -964,9 +729,9 @@ public class FeatureStore size += contactFeatureStarts.size(); } - if (nestedFeatures != null) + if (features != null) { - size += nestedFeatures.size(); + size += features.size(); } return size; diff --git a/src/jalview/datamodel/features/NCList.java b/src/jalview/datamodel/features/NCList.java deleted file mode 100644 index ae58a69..0000000 --- a/src/jalview/datamodel/features/NCList.java +++ /dev/null @@ -1,646 +0,0 @@ -/* - * 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 . - * 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 - * - * 
- * 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
- *
- */ -public class NCList -{ - /* - * 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> subranges; - - /** - * Constructor given a list of things that are each located on a contiguous - * interval. Note that the constructor may reorder the list. - *

- * We assume here that for each range, start <= end. Behaviour for reverse - * ordered ranges is undefined. - * - * @param ranges - */ - public NCList(List 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 ranges) - { - /* - * sort by start ascending so that contained intervals - * follow their containing interval - */ - Collections.sort(ranges, RangeComparator.BY_START_POSITION); - - List 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(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>(); - } - - /** - * Traverses the sorted ranges to identify sublists, within which each - * interval contains the one that follows it - * - * @param ranges - * @return - */ - protected List buildSubranges(List ranges) - { - List 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 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 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 newNCList = new NCList<>(); - newNCList.addNodes(subranges.subList(i, j + 1)); - NCNode newNode = new NCNode<>(entry, newNCList); - for (int k = j; k >= i; k--) - { - subranges.remove(k); - } - subranges.add(i, newNode); - } - - protected void addNodes(List> nodes) - { - for (NCNode 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 findOverlaps(long from, long to) - { - List 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 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 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 subrange : subranges) - { - if (subrange.getEnd() >= from) - { - return i; - } - i++; - } - } - return -1; - } - - /** - * Formats the tree as a bracketed list e.g. - * - * 

-   * [1-100 [10-30 [10-20]], 15-30 [20-20]]
-   *
- */ - @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 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. - *

- * Each subrange must lie within start-end (inclusive). Subranges must be - * ordered by start position ascending. - *

- * - * @param start - * @param end - * @return - */ - boolean isValid(final int start, final int end) - { - int lastStart = start; - for (NCNode 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 getEntries() - { - List result = new ArrayList<>(); - getEntries(result); - return result; - } - - /** - * Adds all contained entries to the given list - * - * @param result - */ - void getEntries(List result) - { - for (NCNode 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 subrange = subranges.get(i); - NCList 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; - } -} diff --git a/src/jalview/datamodel/features/NCNode.java b/src/jalview/datamodel/features/NCNode.java deleted file mode 100644 index b991750..0000000 --- a/src/jalview/datamodel/features/NCNode.java +++ /dev/null @@ -1,275 +0,0 @@ -/* - * 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 . - * 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 - */ -class NCNode 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 subregions; - - /** - * Constructor given a list of ranges - * - * @param ranges - */ - NCNode(List ranges) - { - build(ranges); - } - - /** - * Constructor given a single range - * - * @param range - */ - NCNode(V range) - { - List ranges = new ArrayList<>(); - ranges.add(range); - build(ranges); - } - - NCNode(V entry, NCList newNCList) - { - region = entry; - subregions = newNCList; - size = 1 + newNCList.size(); - } - - /** - * @param ranges - */ - protected void build(List ranges) - { - size = ranges.size(); - - if (!ranges.isEmpty()) - { - region = ranges.get(0); - } - if (ranges.size() > 1) - { - subregions = new NCList(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. - * - * 

-   * [1-100 [10-30 [10-20]], 15-30 [20-20]]
-   *
- */ - @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 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(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 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 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; - } -} diff --git a/src/jalview/datamodel/features/RangeComparator.java b/src/jalview/datamodel/features/RangeComparator.java deleted file mode 100644 index b7d702d..0000000 --- a/src/jalview/datamodel/features/RangeComparator.java +++ /dev/null @@ -1,98 +0,0 @@ -/* - * 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 . - * 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 -{ - public static final Comparator BY_START_POSITION = new RangeComparator( - true); - - public static final Comparator 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; - } -} diff --git a/src/jalview/datamodel/features/SequenceFeatures.java b/src/jalview/datamodel/features/SequenceFeatures.java index 727d3ef..bd102f6 100644 --- a/src/jalview/datamodel/features/SequenceFeatures.java +++ b/src/jalview/datamodel/features/SequenceFeatures.java @@ -20,7 +20,6 @@ */ package jalview.datamodel.features; -import jalview.datamodel.ContiguousI; import jalview.datamodel.SequenceFeature; import jalview.io.gff.SequenceOntologyFactory; import jalview.io.gff.SequenceOntologyI; @@ -36,6 +35,8 @@ import java.util.Map.Entry; 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) @@ -49,10 +50,10 @@ public class SequenceFeatures implements SequenceFeaturesI /** * a comparator for sorting features by start position ascending */ - private static Comparator FORWARD_STRAND = new Comparator() + private static Comparator FORWARD_STRAND = new Comparator() { @Override - public int compare(ContiguousI o1, ContiguousI o2) + public int compare(IntervalI o1, IntervalI o2) { return Integer.compare(o1.getBegin(), o2.getBegin()); } @@ -61,10 +62,10 @@ public class SequenceFeatures implements SequenceFeaturesI /** * a comparator for sorting features by end position descending */ - private static Comparator REVERSE_STRAND = new Comparator() + private static Comparator REVERSE_STRAND = new Comparator() { @Override - public int compare(ContiguousI o1, ContiguousI o2) + public int compare(IntervalI o1, IntervalI o2) { return Integer.compare(o2.getEnd(), o1.getEnd()); } diff --git a/src/jalview/renderer/seqfeatures/FeatureRenderer.java b/src/jalview/renderer/seqfeatures/FeatureRenderer.java index 795cd36..9db55d3 100644 --- a/src/jalview/renderer/seqfeatures/FeatureRenderer.java +++ b/src/jalview/renderer/seqfeatures/FeatureRenderer.java @@ -22,7 +22,6 @@ package jalview.renderer.seqfeatures; import jalview.api.AlignViewportI; import jalview.api.FeatureColourI; -import jalview.datamodel.Range; import jalview.datamodel.SequenceFeature; import jalview.datamodel.SequenceI; import jalview.util.Comparison; @@ -35,6 +34,8 @@ import java.awt.Graphics; import java.awt.Graphics2D; import java.util.List; +import intervalstore.api.IntervalI; + public class FeatureRenderer extends FeatureRendererModel { private static final AlphaComposite NO_TRANSPARENCY = AlphaComposite @@ -272,7 +273,7 @@ public class FeatureRenderer extends FeatureRendererModel /* * 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; diff --git a/test/jalview/datamodel/SequenceTest.java b/test/jalview/datamodel/SequenceTest.java index 79bb2bb..787179b 100644 --- a/test/jalview/datamodel/SequenceTest.java +++ b/test/jalview/datamodel/SequenceTest.java @@ -48,11 +48,11 @@ import org.testng.annotations.BeforeClass; 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() { diff --git a/test/jalview/datamodel/features/FeatureStoreTest.java b/test/jalview/datamodel/features/FeatureStoreTest.java index db21c2f..2972192 100644 --- a/test/jalview/datamodel/features/FeatureStoreTest.java +++ b/test/jalview/datamodel/features/FeatureStoreTest.java @@ -184,58 +184,6 @@ public class FeatureStoreTest 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() { @@ -462,9 +410,7 @@ public class FeatureStoreTest 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); @@ -693,7 +639,7 @@ public class FeatureStoreTest public void testListContains() { assertFalse(FeatureStore.listContains(null, null)); - List features = new ArrayList(); + List features = new ArrayList<>(); assertFalse(FeatureStore.listContains(features, null)); SequenceFeature sf1 = new SequenceFeature("type1", "desc1", 20, 30, 3f, @@ -842,8 +788,8 @@ public class FeatureStoreTest 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 diff --git a/test/jalview/datamodel/features/NCListTest.java b/test/jalview/datamodel/features/NCListTest.java deleted file mode 100644 index 2c7f752..0000000 --- a/test/jalview/datamodel/features/NCListTest.java +++ /dev/null @@ -1,682 +0,0 @@ -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 sorter = new RangeComparator(true); - - /** - * A basic sanity test of the constructor - */ - @Test(groups = "Functional") - public void testConstructor() - { - List ranges = new ArrayList(); - 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 ncl = new NCList(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(ranges); - assertEquals(ncl.toString(), expected); - assertTrue(ncl.isValid()); - } - - @Test(groups = "Functional") - public void testFindOverlaps() - { - List ranges = new ArrayList(); - 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 ncl = new NCList(ranges); - - List 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 ranges = new ArrayList(); - ranges.add(new Range(20, 50)); - NCList ncl = new NCList(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 ranges = new ArrayList(); - ranges.add(new Range(20, 50)); - NCList ncl = new NCList(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 ranges = new ArrayList(); - ranges.add(new Range(20, 50)); - NCList ncl = new NCList(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 ranges = new ArrayList(); - ranges.add(new Range(20, 50)); - ranges.add(new Range(30, 60)); - NCList ncl = new NCList(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 ranges = new ArrayList(); - ranges.add(new Range(20, 40)); - ranges.add(new Range(60, 70)); - NCList ncl = new NCList(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 - *
    - *
  • verify that add adds an entry and increments size
    • - *
  • ...except where the entry is already contained (by equals test)
    • - *
  • verify that the structure is valid at all stages of construction
    • - *
  • generate, run and verify a range of overlap queries
    • - *
  • tear down the structure by deleting entries, verifying correctness at - * each stage
    • - *
- */ - @Test(groups = "Functional", dataProvider = "scalesOfLife") - public void test_pseudoRandom(Integer scale) - { - NCList ncl = new NCList(); - List features = new ArrayList(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 ncl, - List 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 ncl, - List 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 ncl, - int scale, - List 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 ncl, int from, - int to, List features) - { - List 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 ranges = new ArrayList(); - 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 ncl = new NCList(ranges); - Range r7 = new Range(1, 100); - ncl.add(r7); - - List 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(); - assertTrue(ncl.getEntries().isEmpty()); - } - - @Test(groups = "Functional") - public void testDelete() - { - List ranges = new ArrayList(); - Range r1 = new Range(20, 30); - ranges.add(r1); - NCList ncl = new NCList(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 features = new NCList(); - 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 ranges = new ArrayList(); - ranges.add(new Range(40, 50)); - ranges.add(new Range(20, 30)); - NCList ncl = new NCList(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 ncl = new NCList(); - 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 ranges = new ArrayList(); - Range r1 = new Range(40, 50); - ranges.add(r1); - NCList ncl = new NCList(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 ranges = new ArrayList(); - 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 ncl = new NCList(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(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 ranges = new ArrayList(); - 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 ncl = new NCList(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(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()); - } -} diff --git a/test/jalview/datamodel/features/NCNodeTest.java b/test/jalview/datamodel/features/NCNodeTest.java deleted file mode 100644 index 4713084..0000000 --- a/test/jalview/datamodel/features/NCNodeTest.java +++ /dev/null @@ -1,136 +0,0 @@ -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 node = new NCNode(r1); - assertEquals(node.getBegin(), 10); - Range r2 = new Range(10, 15); - node.add(r2); - - List contents = new ArrayList(); - 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 node = new NCNode(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 node = new NCNode(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 node = new NCNode(r1); - List entries = new ArrayList(); - - 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 node = new NCNode(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 node = new NCNode(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 - } -} diff --git a/test/jalview/datamodel/features/RangeComparatorTest.java b/test/jalview/datamodel/features/RangeComparatorTest.java deleted file mode 100644 index 4849b38..0000000 --- a/test/jalview/datamodel/features/RangeComparatorTest.java +++ /dev/null @@ -1,65 +0,0 @@ -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 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 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); - } -}