From 5fa443fd521570a00ce85a627761582adad2bfd4 Mon Sep 17 00:00:00 2001 From: hansonr Date: Sat, 3 Aug 2019 22:34:38 -0500 Subject: [PATCH] JAL-3383 JAL-3253-applet -- Adds FileStoreI interface -- Makes FileStore.java abstract superclass for FileStoreImpl (for Java) and FileStoreJS (for JavaScript) -- Passing all FeatureStoreJSTest TestNG tests -- Passing all SequenceFeatureTest TestNG tests -- About 10% faster for Java on TestNG tests. -- full rendering in < 250 ms for JavaScript -- this is approximately 15 times faster than before I started this experiment. Platform: timer mark 13.396 0.209 overviewrender 16000 pixels row:14 redraw:false Platform: timer mark 14.884 0.186 overviewrender 16000 pixels row:14 redraw:false Platform: timer mark 15.989 0.185 overviewrender 16000 pixels row:14 redraw:false Platform: timer mark 17.216 0.229 overviewrender 16000 pixels row:14 redraw:false Platform: timer mark 18.148 0.239 overviewrender 16000 pixels row:14 redraw:false Platform: timer mark 18.924 0.198 overviewrender 16000 pixels row:14 redraw:false Platform: timer mark 21.827 0.233 overviewrender 16000 pixels row:14 redraw:false --- src/jalview/datamodel/features/FeatureStore.java | 657 +++------------ src/jalview/datamodel/features/FeatureStoreI.java | 55 ++ .../datamodel/features/FeatureStoreImpl.java | 202 +++++ src/jalview/datamodel/features/FeatureStoreJS.java | 499 +++++++++++ .../datamodel/features/SequenceFeatures.java | 64 +- .../datamodel/features/FeatureStoreJSTest.java | 890 ++++++++++++++++++++ .../datamodel/features/FeatureStoreTest.java | 44 +- .../datamodel/features/SequenceFeaturesTest.java | 6 +- 8 files changed, 1839 insertions(+), 578 deletions(-) create mode 100644 src/jalview/datamodel/features/FeatureStoreI.java create mode 100644 src/jalview/datamodel/features/FeatureStoreImpl.java create mode 100644 src/jalview/datamodel/features/FeatureStoreJS.java create mode 100644 test/jalview/datamodel/features/FeatureStoreJSTest.java diff --git a/src/jalview/datamodel/features/FeatureStore.java b/src/jalview/datamodel/features/FeatureStore.java index 716eb04..2cdbeb2 100644 --- a/src/jalview/datamodel/features/FeatureStore.java +++ b/src/jalview/datamodel/features/FeatureStore.java @@ -23,27 +23,17 @@ package jalview.datamodel.features; import jalview.datamodel.SequenceFeature; import java.util.ArrayList; -import java.util.Arrays; +import java.util.Collection; 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 - * of features for one sequence and feature type. - * - * @author gmcarstairs - * - */ -public class FeatureStore +public abstract class FeatureStore implements FeatureStoreI { + /* * Non-positional features have no (zero) start/end position. * Kept as a separate list in case this criterion changes in future. @@ -64,7 +54,13 @@ public class FeatureStore * IntervalStore holds remaining features and provides efficient * query for features overlapping any given interval */ - IntervalStoreI features; + Collection features; + + @Override + public Collection getFeatures() + { + return features; + } /* * Feature groups represented in stored positional features @@ -92,15 +88,11 @@ public class FeatureStore float nonPositionalMaxScore; - private ArrayList featuresList; - /** * Constructor */ public FeatureStore() { - features = new IntervalStore<>(); - featuresList = new ArrayList<>(); positionalFeatureGroups = new HashSet<>(); nonPositionalFeatureGroups = new HashSet<>(); positionalMinScore = Float.NaN; @@ -120,6 +112,7 @@ public class FeatureStore * @param feature */ + @Override public boolean addFeature(SequenceFeature feature) { if (contains(feature)) @@ -184,6 +177,7 @@ public class FeatureStore * @param feature * @return */ + @Override public boolean contains(SequenceFeature feature) { if (feature.isNonPositional()) @@ -194,8 +188,8 @@ public class FeatureStore if (feature.isContactFeature()) { - return contactFeatureStarts == null ? false - : listContains(contactFeatureStarts, feature); + return contactFeatureStarts != null + && listContains(contactFeatureStarts, feature); } return features == null ? false : features.contains(feature); @@ -250,14 +244,8 @@ public class FeatureStore */ protected synchronized void addNestedFeature(SequenceFeature feature) { - if (features == null) - { - features = new IntervalStore<>(); - } features.add(feature); - featuresList.add(feature); } - /** * Add a contact feature to the lists that hold them ordered by start (first * contact) and by end (second contact) position, ensuring the lists remain @@ -272,9 +260,6 @@ public class FeatureStore if (contactFeatureStarts == null) { contactFeatureStarts = new ArrayList<>(); - } - if (contactFeatureEnds == null) - { contactFeatureEnds = new ArrayList<>(); } @@ -338,151 +323,8 @@ public class FeatureStore return false; } - /** - * Returns a (possibly empty) list of features whose extent overlaps the given - * range. The returned list is not ordered. Contact features are included if - * either of the contact points lies within the range. - * - * @param start - * start position of overlap range (inclusive) - * @param end - * end position of overlap range (inclusive) - * @return - */ - - public List findOverlappingFeatures(long start, long end) - { - List result = new ArrayList<>(); - - findContactFeatures(start, end, result); - - if (features != null) - { - result.addAll(features.findOverlaps(start, end)); - } - - return result; - } - - /** - * Adds contact features to the result list where either the second or the - * first contact position lies within the target range - * - * @param from - * @param to - * @param result - */ - protected void findContactFeatures(long from, long to, - List result) - { - if (contactFeatureStarts != null) - { - findContactStartOverlaps(from, to, result); - } - if (contactFeatureEnds != null) - { - findContactEndOverlaps(from, to, result); - } - } - - /** - * Adds to the result list any contact features whose end (second contact - * point), but not start (first contact point), lies in the query from-to - * range - * - * @param from - * @param to - * @param result - */ - protected void findContactEndOverlaps(long from, long to, - List result) - { - /* - * find the first contact feature (if any) - * whose end point is not before the target range - */ - int index = BinarySearcher.findFirst(contactFeatureEnds, - f -> f.getEnd() >= from); - - while (index < contactFeatureEnds.size()) - { - SequenceFeature sf = contactFeatureEnds.get(index); - if (!sf.isContactFeature()) - { - System.err.println("Error! non-contact feature type " + sf.getType() - + " in contact features list"); - index++; - continue; - } - - int begin = sf.getBegin(); - if (begin >= from && begin <= to) - { - /* - * this feature's first contact position lies in the search range - * so we don't include it in results a second time - */ - index++; - continue; - } - - if (sf.getEnd() > to) - { - /* - * this feature (and all following) has end point after the target range - */ - break; - } - - /* - * feature has end >= from and end <= to - * i.e. contact end point lies within overlap search range - */ - result.add(sf); - index++; - } - } - - /** - * Adds contact features whose start position lies in the from-to range to the - * result list - * - * @param from - * @param to - * @param result - */ - protected void findContactStartOverlaps(long from, long to, - List result) - { - int index = BinarySearcher.findFirst(contactFeatureStarts, - f -> f.getBegin() >= from); - - while (index < contactFeatureStarts.size()) - { - SequenceFeature sf = contactFeatureStarts.get(index); - if (!sf.isContactFeature()) - { - System.err.println("Error! non-contact feature " + sf.toString() - + " in contact features list"); - index++; - continue; - } - if (sf.getBegin() > to) - { - /* - * this feature's start (and all following) follows the target range - */ - break; - } - - /* - * feature has begin >= from and begin <= to - * i.e. contact start point lies within overlap search range - */ - result.add(sf); - index++; - } - } + abstract protected void findContactFeatures(long from, long to, + List result); /** * Answers a list of all positional features stored, in no guaranteed order @@ -490,9 +332,10 @@ public class FeatureStore * @return */ - public List getPositionalFeatures() + @Override + public List getPositionalFeatures( + List result) { - List result = new ArrayList<>(); /* * add any contact features - from the list by start position @@ -520,13 +363,15 @@ public class FeatureStore * @return */ - public List getContactFeatures() + @Override + public List getContactFeatures( + List result) { - if (contactFeatureStarts == null) + if (contactFeatureStarts != null) { - return Collections.emptyList(); + result.addAll(contactFeatureStarts); } - return new ArrayList<>(contactFeatureStarts); + return result; } /** @@ -536,13 +381,15 @@ public class FeatureStore * @return */ - public List getNonPositionalFeatures() + @Override + public List getNonPositionalFeatures( + List result) { - if (nonPositionalFeatures == null) + if (nonPositionalFeatures != null) { - return Collections.emptyList(); + result.addAll(nonPositionalFeatures); } - return new ArrayList<>(nonPositionalFeatures); + return result; } /** @@ -554,6 +401,7 @@ public class FeatureStore * @param sf */ + @Override public synchronized boolean delete(SequenceFeature sf) { boolean removed = false; @@ -588,7 +436,6 @@ public class FeatureStore if (!removed && features != null) { removed = features.remove(sf); - featuresList.remove(sf); } if (removed) @@ -616,18 +463,32 @@ public class FeatureStore /* * scan non-positional features for groups and scores */ - for (SequenceFeature sf : getNonPositionalFeatures()) + if (nonPositionalFeatures != null) { - nonPositionalFeatureGroups.add(sf.getFeatureGroup()); - float score = sf.getScore(); - nonPositionalMinScore = min(nonPositionalMinScore, score); - nonPositionalMaxScore = max(nonPositionalMaxScore, score); + for (SequenceFeature sf : nonPositionalFeatures) + { + nonPositionalFeatureGroups.add(sf.getFeatureGroup()); + float score = sf.getScore(); + nonPositionalMinScore = min(nonPositionalMinScore, score); + nonPositionalMaxScore = max(nonPositionalMaxScore, score); + } } /* * scan positional features for groups, scores and extents */ - for (SequenceFeature sf : getPositionalFeatures()) + + rescanPositional(contactFeatureStarts); + rescanPositional(features); + } + + private void rescanPositional(Collection sfs) + { + if (sfs == null) + { + return; + } + for (SequenceFeature sf : sfs) { positionalFeatureGroups.add(sf.getFeatureGroup()); float score = sf.getScore(); @@ -677,19 +538,21 @@ public class FeatureStore } } + /** * Answers true if this store has no features, else false * * @return */ + @Override public boolean isEmpty() { boolean hasFeatures = (contactFeatureStarts != null && !contactFeatureStarts.isEmpty()) || (nonPositionalFeatures != null && !nonPositionalFeatures.isEmpty()) - || (features != null && features.size() > 0); + || features.size() > 0; return !hasFeatures; } @@ -703,6 +566,7 @@ public class FeatureStore * @return */ + @Override public Set getFeatureGroups(boolean positionalFeatures) { if (positionalFeatures) @@ -718,37 +582,83 @@ public class FeatureStore } /** - * Answers the number of positional (or non-positional) features stored. - * Contact features count as 1. + * Answers a list of all either positional or non-positional features whose + * feature group matches the given group (which may be null) * * @param positional + * @param group * @return */ - public int getFeatureCount(boolean positional) + @Override + public List getFeaturesForGroup(boolean positional, + String group) { - if (!positional) + List result = new ArrayList<>(); + + /* + * if we know features don't include the target group, no need + * to inspect them for matches + */ + if (positional && !positionalFeatureGroups.contains(group) + || !positional && !nonPositionalFeatureGroups.contains(group)) { - return nonPositionalFeatures == null ? 0 - : nonPositionalFeatures.size(); + return result; } - int size = 0; + if (positional) + { + addFeaturesForGroup(group, contactFeatureStarts, result); + addFeaturesForGroup(group, features, result); + } + else + { + addFeaturesForGroup(group, nonPositionalFeatures, result); + } + return result; + } - if (contactFeatureStarts != null) + private void addFeaturesForGroup(String group, + Collection sfs, List result) + { + if (sfs == null) + { + return; + } + for (SequenceFeature sf : sfs) { - // note a contact feature (start/end) counts as one - size += contactFeatureStarts.size(); + String featureGroup = sf.getFeatureGroup(); + if (group == null && featureGroup == null + || group != null && group.equals(featureGroup)) + { + result.add(sf); + } } + } - if (features != null) + /** + * Answers the number of positional (or non-positional) features stored. + * Contact features count as 1. + * + * @param positional + * @return + */ + + @Override + public int getFeatureCount(boolean positional) + { + if (!positional) { - size += features.size(); + return nonPositionalFeatures == null ? 0 + : nonPositionalFeatures.size(); } - return size; + return (contactFeatureStarts == null ? 0 : contactFeatureStarts.size()) + + features.size(); + } + /** * Answers the total length of positional features (or zero if there are * none). Contact features contribute a value of 1 to the total. @@ -756,6 +666,7 @@ public class FeatureStore * @return */ + @Override public int getTotalFeatureLength() { return totalExtent; @@ -770,6 +681,7 @@ public class FeatureStore * @return */ + @Override public float getMinimumScore(boolean positional) { return positional ? positionalMinScore : nonPositionalMinScore; @@ -784,48 +696,12 @@ public class FeatureStore * @return */ + @Override public float getMaximumScore(boolean positional) { return positional ? positionalMaxScore : nonPositionalMaxScore; } - /** - * Answers a list of all either positional or non-positional features whose - * feature group matches the given group (which may be null) - * - * @param positional - * @param group - * @return - */ - - public List getFeaturesForGroup(boolean positional, - String group) - { - List result = new ArrayList<>(); - - /* - * if we know features don't include the target group, no need - * to inspect them for matches - */ - if (positional && !positionalFeatureGroups.contains(group) - || !positional && !nonPositionalFeatureGroups.contains(group)) - { - return result; - } - - List sfs = positional ? getPositionalFeatures() - : getNonPositionalFeatures(); - for (SequenceFeature sf : sfs) - { - String featureGroup = sf.getFeatureGroup(); - if (group == null && featureGroup == null - || group != null && group.equals(featureGroup)) - { - result.add(sf); - } - } - return result; - } /** * Adds the shift amount to the start and end of all positional features whose @@ -837,6 +713,7 @@ public class FeatureStore * @return */ + @Override public synchronized boolean shiftFeatures(int fromPosition, int shiftBy) { /* @@ -869,301 +746,29 @@ public class FeatureStore return modified; } - /////////////////////// added by Bob Hanson /////////////////////// - - // The following methods use a linked list of containment in features - // rather than IntervalStore. Implemented only for OverviewPanel, because - // only that makes calls for start == end in feature overlap requests. - // - // - // There are two parts --- initialization, and overlap searching. - // - // Initialization involves two steps: - // - // (1) sorting of features by start position using a standard Array.sort with - // Comparator. - // (2) linking of features, effectively nesting them. - // - // Searching also involves two steps: - // - // (1) binary search for a position within the sorted features array. - // (2) traversing the linked lists with an end check to read out the - // overlapped features at this position. - // - // All of this is done with very simple standard methods. - - // single public method: - - /** - * Find all features containing this position. - * - * @param pos - * @return list of SequenceFeatures - * @author Bob Hanson 2019.07.30 - */ - - public List findOverlappingFeatures(int pos, - List result) - { - if (result == null) - { - result = new ArrayList<>(); - } - - if (contactFeatureStarts != null) - { - findContacts(contactFeatureStarts, pos, result, true); - findContacts(contactFeatureEnds, pos, result, false); - } - if (featuresList != null) - { - findOverlaps(featuresList, pos, result); - } - return result; - } - - // Initialization - - /* - * contact features ordered by first contact position - */ - private SequenceFeature[] orderedFeatureStarts; - - private void rebuildArrays(int n) - { - if (startComp == null) - { - startComp = new StartComparator(); - } - orderedFeatureStarts = new SequenceFeature[n]; - for (int i = n; --i >= 0;) - { - SequenceFeature sf = featuresList.get(i); - sf.index = i; // for debugging only - orderedFeatureStarts[i] = sf; - } - Arrays.sort(orderedFeatureStarts, startComp); - linkFeatures(orderedFeatureStarts); - } - - /** - * just a standard Comparator - */ - private static StartComparator startComp; - - class StartComparator implements Comparator - { - - @Override - public int compare(SequenceFeature o1, SequenceFeature o2) - { - int p1 = o1.begin; - int p2 = o2.begin; - return (p1 < p2 ? -1 : p1 > p2 ? 1 : 0); - } - - } - - /** - * Run through the sorted sequence array once, building the containedBy linked - * list references. Does a check first to make sure there is actually - * something out there that is overlapping. A null for sf.containedBy means - * there are no overlaps for this feature. - * - * @param intervals - */ - private void linkFeatures(SequenceFeature[] intervals) - { - if (intervals.length < 2) - { - return; - } - int maxEnd = intervals[0].end; - for (int i = 1, n = intervals.length; i < n; i++) - { - SequenceFeature sf = intervals[i]; - if (sf.begin <= maxEnd) - { - sf.containedBy = getContainedBy(intervals[i - 1], sf); - } - if (sf.end > maxEnd) - { - maxEnd = sf.end; - } - } - } - - /** - * Since we are traversing the sorted feature array in a forward direction, - * all elements prior to the one we are working on have been fully linked. All - * we are doing is following those links until we find the first array feature - * with a containedBy element that has an end >= our begin point. It is - * generally a very short list -- maybe one or two depths. But it might be - * more than that. - * - * @param sf - * @param sf0 - * @return - */ - private SequenceFeature getContainedBy(SequenceFeature sf, - SequenceFeature sf0) - { - int begin = sf0.begin; - while (sf != null) - { - if (begin <= sf.end) - { - System.out.println("\nFS found " + sf0.index + ":" + sf0 - + "\nFS in " + sf.index + ":" + sf); - return sf; - } - sf = sf.containedBy; - } - return null; - } - - // search-stage methods - /** - * Binary search for contact start or end at a given (Overview) position. - * - * @param l - * @param pos - * @param result - * @param isStart - * - * @author Bob Hanson 2019.07.30 - */ - private static void findContacts(List l, int pos, - List result, boolean isStart) + @Override + public List findOverlappingFeatures(long start, long end) { - int low = 0; - int high = l.size() - 1; - while (low <= high) - { - int mid = (low + high) >>> 1; - SequenceFeature f = l.get(mid); - switch (Long.signum((isStart ? f.begin : f.end) - pos)) - { - case -1: - low = mid + 1; - continue; - case 1: - high = mid - 1; - continue; - case 0: - int m = mid; - result.add(f); - // could be "5" in 12345556788 ? - while (++mid <= high && (f = l.get(mid)) != null - && (isStart ? f.begin : f.end) == pos) - { - result.add(f); - } - while (--m >= low && (f = l.get(m)) != null - && (isStart ? f.begin : f.end) == pos) - { - result.add(f); - } - return; - } - } + return findOverlappingFeatures(start, end, null); } - /** - * Find all overlaps; special case when there is only one feature. The - * required array of start-sorted SequenceFeature is created lazily. - * - * @param features - * @param pos - * @param result - */ - private void findOverlaps(List features, int pos, - List result) + @Override + public List getPositionalFeatures() { - int n = featuresList.size(); - if (n == 1) - { - checkOne(featuresList.get(0), pos, result); - return; - } - if (orderedFeatureStarts == null) - { - rebuildArrays(n); - } - - // (1) Find the closest feature to this position. - - SequenceFeature sf = findClosestFeature(orderedFeatureStarts, pos); - - // (2) Traverse the containedBy field, checking for overlap. - - while (sf != null) - { - if (sf.end >= pos) - { - result.add(sf); - } - sf = sf.containedBy; - } + return getPositionalFeatures(new ArrayList<>()); } - /** - * Quick check when we only have one feature. - * - * @param sf - * @param pos - * @param result - */ - private void checkOne(SequenceFeature sf, int pos, - List result) + @Override + public List getContactFeatures() { - if (sf.begin <= pos && sf.end >= pos) - { - result.add(sf); - } - return; + return getContactFeatures(new ArrayList<>()); } - /** - * A binary search identical to the one used for contact start/end, but here - * we return the feature itself. Unlike Collection.BinarySearch, all we have - * to be is close, not exact, and we make sure if there is a string of - * identical starts, then we slide to the end so that we can check all of - * them. - * - * @param l - * @param pos - * @return - */ - private SequenceFeature findClosestFeature(SequenceFeature[] l, int pos) + @Override + public List getNonPositionalFeatures() { - int low = 0; - int high = l.length - 1; - while (low <= high) - { - int mid = (low + high) >>> 1; - SequenceFeature f = l[mid]; - switch (Long.signum(f.begin - pos)) - { - case -1: - low = mid + 1; - continue; - case 1: - high = mid - 1; - continue; - case 0: - - while (++mid <= high && l[mid].begin == pos) - { - ; - } - return l[--mid]; - } - } - // -1 here? - return (high < 0 || low >= l.length ? null : l[high]); + return getNonPositionalFeatures(new ArrayList<>()); } - } diff --git a/src/jalview/datamodel/features/FeatureStoreI.java b/src/jalview/datamodel/features/FeatureStoreI.java new file mode 100644 index 0000000..873d53c --- /dev/null +++ b/src/jalview/datamodel/features/FeatureStoreI.java @@ -0,0 +1,55 @@ +package jalview.datamodel.features; + +import jalview.datamodel.SequenceFeature; + +import java.util.Collection; +import java.util.List; +import java.util.Set; + +public interface FeatureStoreI +{ + + boolean addFeature(SequenceFeature feature); + + boolean contains(SequenceFeature feature); + + boolean delete(SequenceFeature sf); + + List findOverlappingFeatures(long start, long end); + + List findOverlappingFeatures(long start, long end, + List result); + + List getContactFeatures(); + + List getContactFeatures(List result); + + int getFeatureCount(boolean positional); + + Set getFeatureGroups(boolean positionalFeatures); + + Collection getFeatures(); + + List getFeaturesForGroup(boolean positional, + String group); + + float getMaximumScore(boolean positional); + + float getMinimumScore(boolean positional); + + List getNonPositionalFeatures(); + + List getNonPositionalFeatures( + List result); + + List getPositionalFeatures(); + + List getPositionalFeatures(List result); + + int getTotalFeatureLength(); + + boolean isEmpty(); + + boolean shiftFeatures(int fromPosition, int shiftBy); + +} diff --git a/src/jalview/datamodel/features/FeatureStoreImpl.java b/src/jalview/datamodel/features/FeatureStoreImpl.java new file mode 100644 index 0000000..62832d7 --- /dev/null +++ b/src/jalview/datamodel/features/FeatureStoreImpl.java @@ -0,0 +1,202 @@ +/* + * 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.SequenceFeature; + +import java.util.ArrayList; +import java.util.List; + +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 + * of features for one sequence and feature type. + * + * @author gmcarstairs + * + */ +public class FeatureStoreImpl extends FeatureStore +{ + + public FeatureStoreImpl() + { + features = new IntervalStore<>(); + } + + /** + * Adds contact features to the result list where either the second or the + * first contact position lies within the target range + * + * @param from + * @param to + * @param result + */ + @Override + protected void findContactFeatures(long from, long to, + List result) + { + if (contactFeatureStarts != null) + { + findContactStartOverlaps(from, to, result); + findContactEndOverlaps(from, to, result); + } + } + + /** + * Adds to the result list any contact features whose end (second contact + * point), but not start (first contact point), lies in the query from-to + * range + * + * @param from + * @param to + * @param result + */ + + private void findContactEndOverlaps(long from, long to, + List result) + { + /* + * find the first contact feature (if any) + * whose end point is not before the target range + */ + int index = BinarySearcher.findFirst(contactFeatureEnds, + f -> f.getEnd() >= from); + + int n = contactFeatureEnds.size(); + while (index < n) + { + SequenceFeature sf = contactFeatureEnds.get(index); + if (!sf.isContactFeature()) + { + System.err.println("Error! non-contact feature type " + sf.getType() + + " in contact features list"); + index++; + continue; + } + + int begin = sf.getBegin(); + if (begin >= from && begin <= to) + { + /* + * this feature's first contact position lies in the search range + * so we don't include it in results a second time + */ + index++; + continue; + } + + if (sf.getEnd() > to) + { + /* + * this feature (and all following) has end point after the target range + */ + break; + } + + /* + * feature has end >= from and end <= to + * i.e. contact end point lies within overlap search range + */ + result.add(sf); + index++; + } + } + + /** + * Adds contact features whose start position lies in the from-to range to the + * result list + * + * @param from + * @param to + * @param result + */ + + private void findContactStartOverlaps(long from, long to, + List result) + { + int index = BinarySearcher.findFirst(contactFeatureStarts, + f -> f.getBegin() >= from); + + while (index < contactFeatureStarts.size()) + { + SequenceFeature sf = contactFeatureStarts.get(index); + if (!sf.isContactFeature()) + { + System.err.println("Error! non-contact feature " + sf.toString() + + " in contact features list"); + index++; + continue; + } + if (sf.getBegin() > to) + { + /* + * this feature's start (and all following) follows the target range + */ + break; + } + + /* + * feature has begin >= from and begin <= to + * i.e. contact start point lies within overlap search range + */ + result.add(sf); + index++; + } + } + + /** + * Returns a (possibly empty) list of features whose extent overlaps the given + * range. The returned list is not ordered. Contact features are included if + * either of the contact points lies within the range. + * + * @param start + * start position of overlap range (inclusive) + * @param end + * end position of overlap range (inclusive) + * @param result + * ignored + * @return + */ + + @Override + public List findOverlappingFeatures(long start, long end, + List result) + { + result = new ArrayList<>(); + findContactFeatures(start, end, result); + findOverlaps(start, end, result); + return result; + } + + private void findOverlaps(long start, long end, + List result) + { + result.addAll(((IntervalStoreI) features) + .findOverlaps(start, end)); + // TODO Auto-generated method stub + + } + +} diff --git a/src/jalview/datamodel/features/FeatureStoreJS.java b/src/jalview/datamodel/features/FeatureStoreJS.java new file mode 100644 index 0000000..295d7a0 --- /dev/null +++ b/src/jalview/datamodel/features/FeatureStoreJS.java @@ -0,0 +1,499 @@ +/* + * 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.SequenceFeature; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Comparator; +import java.util.List; + +/** + * An adaption of FeatureStore that is efficient and lightweight, accelerating + * processing speed in JavaScript. + * + * @author gmcarstairs + * @author Bob Hanson 2019.08.03 + * + */ +public class FeatureStoreJS extends FeatureStore +{ + boolean contactsTainted = true; + + /** + * Constructor + */ + public FeatureStoreJS() + { + features = new ArrayList<>(); + } + + /** + * Returns a (possibly empty) list of features whose extent overlaps the given + * range. The returned list is not ordered. Contact features are included if + * either of the contact points lies within the range. + * + * @param start + * start position of overlap range (inclusive) + * @param end + * end position of overlap range (inclusive) + * @return + */ + + @Override + public List findOverlappingFeatures(long start, long end, + List result) + { + if (result == null) + { + result = new ArrayList<>(); + } + if (contactFeatureStarts != null) + { + if (start == end) + { + findContactPoints(contactFeatureStarts, start, result, true); + findContactPoints(contactFeatureEnds, start, result, false); + } + else + { + findContactFeatures(start, end, result); + } + } + if (features.size() > 0) + { + findOverlaps(start, end, result); + } + return result; + } + + // The following methods use a linked list of containment in SequenceFeature + // rather than IntervalStore. + // + // There are two parts --- initialization, and overlap searching. + // + // Initialization involves two steps: + // + // (1) sorting of features by start position using a standard Array.sort with + // Comparator. + // (2) linking of features, effectively nesting them. + // + // Searching involves three steps: + // + // (1) binary search for a starting point within the sorted features array. + // (2) traverse the linked lists with an end check to read out the + // overlapped features at this position. + // (3) For an interval, find the last feature that starts in this interval, + // and add all features up through that feature. + // + // All of this is done with very simple standard methods. + + // Initialization + + /* + * contact features ordered by first contact position + */ + private SequenceFeature[] orderedFeatureStarts; + + private void rebuildArrays(int n) + { + if (startComp == null) + { + startComp = new StartComparator(); + } + orderedFeatureStarts = new SequenceFeature[n]; + for (int i = n; --i >= 0;) + { + SequenceFeature sf = ((ArrayList) features).get(i); + sf.index = i; // for debugging only + orderedFeatureStarts[i] = sf; + } + Arrays.sort(orderedFeatureStarts, startComp); + linkFeatures(orderedFeatureStarts); + } + + /** + * just a standard Comparator + */ + private static StartComparator startComp; + + class StartComparator implements Comparator + { + + @Override + public int compare(SequenceFeature o1, SequenceFeature o2) + { + int p1 = o1.begin; + int p2 = o2.begin; + return (p1 < p2 ? -1 : p1 > p2 ? 1 : 0); + } + + } + + /** + * Run through the sorted sequence array once, building the containedBy linked + * list references. Does a check first to make sure there is actually + * something out there that is overlapping. A null for sf.containedBy means + * there are no overlaps for this feature. + * + * @param intervals + */ + private void linkFeatures(SequenceFeature[] intervals) + { + if (intervals.length < 2) + { + return; + } + int maxEnd = intervals[0].end; + for (int i = 1, n = intervals.length; i < n; i++) + { + SequenceFeature sf = intervals[i]; + if (sf.begin <= maxEnd) + { + sf.containedBy = getContainedBy(intervals[i - 1], sf); + } + if (sf.end > maxEnd) + { + maxEnd = sf.end; + } + } + } + + /** + * Since we are traversing the sorted feature array in a forward direction, + * all elements prior to the one we are working on have been fully linked. All + * we are doing is following those links until we find the first array feature + * with a containedBy element that has an end >= our begin point. It is + * generally a very short list -- maybe one or two depths. But it might be + * more than that. + * + * @param sf + * @param sf0 + * @return + */ + private SequenceFeature getContainedBy(SequenceFeature sf, + SequenceFeature sf0) + { + int begin = sf0.begin; + while (sf != null) + { + if (begin <= sf.end) + { + // System.out.println("\nFS found " + sf0.index + ":" + sf0 + // + "\nFS in " + sf.index + ":" + sf); + return sf; + } + sf = sf.containedBy; + } + return null; + } + + // search-stage methods + + /** + * Binary search for contact start or end at a given (Overview) position. + * + * @param l + * @param pos + * @param result + * @param isStart + * + * @author Bob Hanson 2019.07.30 + */ + private static void findContactPoints(List l, long pos, + List result, boolean isStart) + { + int low = 0; + int high = l.size() - 1; + while (low <= high) + { + int mid = (low + high) >>> 1; + SequenceFeature f = l.get(mid); + switch (Long.signum((isStart ? f.begin : f.end) - pos)) + { + case -1: + low = mid + 1; + continue; + case 1: + high = mid - 1; + continue; + case 0: + int m = mid; + result.add(f); + // could be "5" in 12345556788 ? + while (++mid <= high && (f = l.get(mid)) != null + && (isStart ? f.begin : f.end) == pos) + { + result.add(f); + } + while (--m >= low && (f = l.get(m)) != null + && (isStart ? f.begin : f.end) == pos) + { + result.add(f); + } + return; + } + } + } + + /** + * Find all overlaps; special case when there is only one feature. The + * required array of start-sorted SequenceFeature is created lazily. + * + * @param features + * @param pos + * @param result + */ + private void findOverlaps(long start, long end, + List result) + { + int n = features.size(); + switch (n) + { + case 0: + return; + case 1: + checkOne(((ArrayList) features).get(0), start, end, + result); + return; + default: + if (orderedFeatureStarts == null) + { + rebuildArrays(n); + } + break; + } + + // (1) Find the closest feature to this position. + + int index = findClosestFeature(orderedFeatureStarts, start); + SequenceFeature sf = (index < 0 ? null : orderedFeatureStarts[index]); + + // (2) Traverse the containedBy field, checking for overlap. + + while (sf != null) + { + if (sf.end >= start) + { + result.add(sf); + } + sf = sf.containedBy; + } + + // (3) For an interval, find the last feature that starts in this interval, + // and add all features up through that feature. + + if (end > start) + { + // fill in with all features that start within this interval, fully + // inclusive + int index2 = findClosestFeature(orderedFeatureStarts, end); + while (++index <= index2) + { + result.add(orderedFeatureStarts[index]); + } + + } + } + + /** + * Quick check when we only have one feature. + * + * @param sf + * @param start + * @param end + * @param result + */ + private void checkOne(SequenceFeature sf, long start, long end, + List result) + { + if (sf.begin <= end && sf.end >= start) + { + result.add(sf); + } + return; + } + + /** + * A binary search identical to the one used for contact start/end, but here + * we return the feature itself. Unlike Collection.BinarySearch, all we have + * to be is close, not exact, and we make sure if there is a string of + * identical starts, then we slide to the end so that we can check all of + * them. + * + * @param l + * @param pos + * @return + */ + private int findClosestFeature(SequenceFeature[] l, long pos) + { + int low = 0; + int high = l.length - 1; + while (low <= high) + { + int mid = (low + high) >>> 1; + SequenceFeature f = l[mid]; + switch (Long.signum(f.begin - pos)) + { + case -1: + low = mid + 1; + continue; + case 1: + high = mid - 1; + continue; + case 0: + + while (++mid <= high && l[mid].begin == pos) + { + ; + } + return --mid; + } + } + return (high < 0 ? -1 : high); + } + + /** + * Adds contact features to the result list where either the second or the + * first contact position lies within the target range + * + * @param from + * @param to + * @param result + */ + @Override + protected void findContactFeatures(long from, long to, + List result) + { + findContactStartOverlaps(from, to, result); + findContactEndOverlaps(from, to, result); + } + + /** + * Adds to the result list any contact features whose end (second contact + * point), but not start (first contact point), lies in the query from-to + * range + * + * @param from + * @param to + * @param result + */ + + private void findContactEndOverlaps(long from, long to, + List result) + { + // find the first contact feature (if any) + // with end point not before the target range + + for (int i = findFirstEnd(contactFeatureEnds, + from), n = contactFeatureEnds.size(); i < n; i++) + { + SequenceFeature sf = contactFeatureEnds.get(i); + if (sf.begin >= from && sf.begin <= to) + { + // this feature's first contact position lies in the search range + // so we don't include it in results a second time + continue; + } + + if (sf.end > to) + { + // this feature (and all following) has end point after the target range + break; + } + + // feature has end >= from and end <= to + // i.e. contact end point lies within overlap search range + result.add(sf); + } + } + + /** + * Adds contact features whose start position lies in the from-to range to the + * result list + * + * @param from + * @param to + * @param result + */ + + private void findContactStartOverlaps(long from, long to, + List result) + { + for (int i = findFirstBegin(contactFeatureStarts, + from), n = contactFeatureStarts.size(); i < n; i++) + { + SequenceFeature sf = contactFeatureStarts.get(i); + if (sf.begin > to) + { + break; + } + result.add(sf); + } + } + + public static int findFirstBegin(List list, long pos) + { + int start = 0; + int end = list.size() - 1; + int matched = list.size(); + + while (start <= end) + { + int mid = (start + end) / 2; + if (list.get(mid).begin >= pos) + { + matched = mid; + end = mid - 1; + } + else + { + start = mid + 1; + } + } + return matched; + } + + public static int findFirstEnd(List list, long pos) + { + int start = 0; + int end = list.size() - 1; + int matched = list.size(); + + while (start <= end) + { + int mid = (start + end) / 2; + if (list.get(mid).end >= pos) + { + matched = mid; + end = mid - 1; + } + else + { + start = mid + 1; + } + } + return matched; + } + + +} diff --git a/src/jalview/datamodel/features/SequenceFeatures.java b/src/jalview/datamodel/features/SequenceFeatures.java index 0d29184..54102ce 100644 --- a/src/jalview/datamodel/features/SequenceFeatures.java +++ b/src/jalview/datamodel/features/SequenceFeatures.java @@ -23,6 +23,7 @@ package jalview.datamodel.features; import jalview.datamodel.SequenceFeature; import jalview.io.gff.SequenceOntologyFactory; import jalview.io.gff.SequenceOntologyI; +import jalview.util.Platform; import java.util.ArrayList; import java.util.Arrays; @@ -50,7 +51,9 @@ public class SequenceFeatures implements SequenceFeaturesI * map from feature type to structured store of features for that type * null types are permitted (but not a good idea!) */ - private Map featureStore; + private Map featureStore; + + private static boolean useIntervalStore = !Platform.isJS(); /** * Constructor @@ -62,7 +65,7 @@ public class SequenceFeatures implements SequenceFeaturesI * ? wrap as a synchronized map for add and delete operations */ // featureStore = Collections - // .synchronizedSortedMap(new TreeMap()); + // .synchronizedSortedMap(new TreeMap()); featureStore = new TreeMap<>(); } @@ -96,11 +99,17 @@ public class SequenceFeatures implements SequenceFeaturesI if (featureStore.get(type) == null) { - featureStore.put(type, new FeatureStore()); + featureStore.put(type, newFeatureStore()); } return featureStore.get(type).addFeature(sf); } + private FeatureStoreI newFeatureStore() + { + // TODO Auto-generated method stub + return (useIntervalStore ? new FeatureStoreImpl() : new FeatureStoreJS()); + } + /** * {@inheritDoc} */ @@ -109,9 +118,9 @@ public class SequenceFeatures implements SequenceFeaturesI String... type) { List result = new ArrayList<>(); - for (FeatureStore featureSet : varargToTypes(type)) + for (FeatureStoreI featureSet : varargToTypes(type)) { - result.addAll(featureSet.findOverlappingFeatures(from, to)); + result.addAll(featureSet.findOverlappingFeatures(from, to, null)); } return result; } @@ -163,7 +172,7 @@ public class SequenceFeatures implements SequenceFeaturesI { int result = 0; - for (FeatureStore featureSet : varargToTypes(type)) + for (FeatureStoreI featureSet : varargToTypes(type)) { result += featureSet.getFeatureCount(positional); } @@ -178,7 +187,7 @@ public class SequenceFeatures implements SequenceFeaturesI { int result = 0; - for (FeatureStore featureSet : varargToTypes(type)) + for (FeatureStoreI featureSet : varargToTypes(type)) { result += featureSet.getTotalFeatureLength(); } @@ -193,9 +202,9 @@ public class SequenceFeatures implements SequenceFeaturesI { List result = new ArrayList<>(); - for (FeatureStore featureSet : varargToTypes(type)) + for (FeatureStoreI featureSet : varargToTypes(type)) { - result.addAll(featureSet.getPositionalFeatures()); + featureSet.getPositionalFeatures(result); } return result; } @@ -207,7 +216,7 @@ public class SequenceFeatures implements SequenceFeaturesI * @param type * @return */ - protected Iterable varargToTypes(String... type) + protected Iterable varargToTypes(String... type) { if (type == null || type.length == 0) { @@ -218,9 +227,9 @@ public class SequenceFeatures implements SequenceFeaturesI } - List types = new ArrayList<>(); + List types = new ArrayList<>(); List args = Arrays.asList(type); - for (Entry featureType : featureStore.entrySet()) + for (Entry featureType : featureStore.entrySet()) { if (args.contains(featureType.getKey())) { @@ -238,9 +247,9 @@ public class SequenceFeatures implements SequenceFeaturesI { List result = new ArrayList<>(); - for (FeatureStore featureSet : varargToTypes(type)) + for (FeatureStoreI featureSet : varargToTypes(type)) { - result.addAll(featureSet.getContactFeatures()); + featureSet.getContactFeatures(result); } return result; } @@ -253,9 +262,9 @@ public class SequenceFeatures implements SequenceFeaturesI { List result = new ArrayList<>(); - for (FeatureStore featureSet : varargToTypes(type)) + for (FeatureStoreI featureSet : varargToTypes(type)) { - result.addAll(featureSet.getNonPositionalFeatures()); + featureSet.getNonPositionalFeatures(result); } return result; } @@ -266,7 +275,7 @@ public class SequenceFeatures implements SequenceFeaturesI @Override public boolean delete(SequenceFeature sf) { - for (FeatureStore featureSet : featureStore.values()) + for (FeatureStoreI featureSet : featureStore.values()) { if (featureSet.delete(sf)) { @@ -282,7 +291,7 @@ public class SequenceFeatures implements SequenceFeaturesI @Override public boolean hasFeatures() { - for (FeatureStore featureSet : featureStore.values()) + for (FeatureStoreI featureSet : featureStore.values()) { if (!featureSet.isEmpty()) { @@ -301,7 +310,7 @@ public class SequenceFeatures implements SequenceFeaturesI { Set groups = new HashSet<>(); - for (FeatureStore featureSet : varargToTypes(type)) + for (FeatureStoreI featureSet : varargToTypes(type)) { groups.addAll(featureSet.getFeatureGroups(positionalFeatures)); } @@ -318,7 +327,7 @@ public class SequenceFeatures implements SequenceFeaturesI { Set result = new HashSet<>(); - for (Entry featureType : featureStore.entrySet()) + for (Entry featureType : featureStore.entrySet()) { Set featureGroups = featureType.getValue().getFeatureGroups( positionalFeatures); @@ -345,7 +354,7 @@ public class SequenceFeatures implements SequenceFeaturesI public Set getFeatureTypes(String... soTerm) { Set types = new HashSet<>(); - for (Entry entry : featureStore.entrySet()) + for (Entry entry : featureStore.entrySet()) { String type = entry.getKey(); if (!entry.getValue().isEmpty() && isOntologyTerm(type, soTerm)) @@ -432,7 +441,7 @@ public class SequenceFeatures implements SequenceFeaturesI String group, String... type) { List result = new ArrayList<>(); - for (FeatureStore featureSet : varargToTypes(type)) + for (FeatureStoreI featureSet : varargToTypes(type)) { if (featureSet.getFeatureGroups(positional).contains(group)) { @@ -449,7 +458,7 @@ public class SequenceFeatures implements SequenceFeaturesI public boolean shiftFeatures(int fromPosition, int shiftBy) { boolean modified = false; - for (FeatureStore fs : featureStore.values()) + for (FeatureStoreI fs : featureStore.values()) { modified |= fs.shiftFeatures(fromPosition, shiftBy); } @@ -479,13 +488,8 @@ public class SequenceFeatures implements SequenceFeaturesI public List findFeatures(int pos, String type, List list) { - FeatureStore fs = featureStore.get(type); - boolean useIntervalStore = /** - * @j2sNative false && - */ - true; - return (useIntervalStore ? fs.findOverlappingFeatures(pos, pos) - : fs.findOverlappingFeatures(pos, list)); + FeatureStoreI fs = featureStore.get(type); + return fs.findOverlappingFeatures(pos, pos, list); } // Chrome; developer console closed diff --git a/test/jalview/datamodel/features/FeatureStoreJSTest.java b/test/jalview/datamodel/features/FeatureStoreJSTest.java new file mode 100644 index 0000000..221d7a4 --- /dev/null +++ b/test/jalview/datamodel/features/FeatureStoreJSTest.java @@ -0,0 +1,890 @@ +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.SequenceFeature; + +import java.util.ArrayList; +import java.util.List; +import java.util.Set; + +import org.testng.annotations.Test; + +public class FeatureStoreJSTest +{ + + @Test(groups = "Functional") + public void testFindFeatures_nonNested() + { + FeatureStoreI fs = newFeatureStore(); + fs.addFeature(new SequenceFeature("", "", 10, 20, Float.NaN, + null)); + // same range different description + fs.addFeature(new SequenceFeature("", "desc", 10, 20, Float.NaN, null)); + fs.addFeature(new SequenceFeature("", "", 15, 25, Float.NaN, null)); + fs.addFeature(new SequenceFeature("", "", 20, 35, Float.NaN, null)); + + List overlaps = fs.findOverlappingFeatures(1, 9); + assertTrue(overlaps.isEmpty()); + + overlaps = fs.findOverlappingFeatures(8, 10); + assertEquals(overlaps.size(), 2); + assertEquals(overlaps.get(0).getEnd(), 20); + assertEquals(overlaps.get(1).getEnd(), 20); + + overlaps = fs.findOverlappingFeatures(12, 16); + assertEquals(overlaps.size(), 3); + assertEquals(overlaps.get(0).getEnd(), 20); + assertEquals(overlaps.get(1).getEnd(), 20); + assertEquals(overlaps.get(2).getEnd(), 25); + + overlaps = fs.findOverlappingFeatures(33, 33); + assertEquals(overlaps.size(), 1); + assertEquals(overlaps.get(0).getEnd(), 35); + } + + private FeatureStoreI newFeatureStore() + { + return new FeatureStoreJS(); + // return new FeatureStoreImpl(); + } + + @Test(groups = "Functional") + public void testFindFeatures_nested() + { + FeatureStoreI fs = newFeatureStore(); + SequenceFeature sf1 = addFeature(fs, 10, 50); + SequenceFeature sf2 = addFeature(fs, 10, 40); + SequenceFeature sf3 = addFeature(fs, 20, 30); + // fudge feature at same location but different group (so is added) + SequenceFeature sf4 = new SequenceFeature("", "", 20, 30, Float.NaN, + "different group"); + fs.addFeature(sf4); + SequenceFeature sf5 = addFeature(fs, 35, 36); + + List overlaps = fs.findOverlappingFeatures(1, 9); + assertTrue(overlaps.isEmpty()); + + overlaps = fs.findOverlappingFeatures(10, 15); + assertEquals(overlaps.size(), 2); + assertTrue(overlaps.contains(sf1)); + assertTrue(overlaps.contains(sf2)); + + overlaps = fs.findOverlappingFeatures(45, 60); + assertEquals(overlaps.size(), 1); + assertTrue(overlaps.contains(sf1)); + + overlaps = fs.findOverlappingFeatures(32, 38); + assertEquals(overlaps.size(), 3); + assertTrue(overlaps.contains(sf1)); + assertTrue(overlaps.contains(sf2)); + assertTrue(overlaps.contains(sf5)); + + overlaps = fs.findOverlappingFeatures(15, 25); + assertEquals(overlaps.size(), 4); + assertTrue(overlaps.contains(sf1)); + assertTrue(overlaps.contains(sf2)); + assertTrue(overlaps.contains(sf3)); + assertTrue(overlaps.contains(sf4)); + } + + @Test(groups = "Functional") + public void testFindFeatures_mixed() + { + FeatureStoreI fs = newFeatureStore(); + SequenceFeature sf1 = addFeature(fs, 10, 50); + SequenceFeature sf2 = addFeature(fs, 1, 15); + SequenceFeature sf3 = addFeature(fs, 20, 30); + SequenceFeature sf4 = addFeature(fs, 40, 100); + SequenceFeature sf5 = addFeature(fs, 60, 100); + SequenceFeature sf6 = addFeature(fs, 70, 70); + + List overlaps = fs.findOverlappingFeatures(200, 200); + assertTrue(overlaps.isEmpty()); + + overlaps = fs.findOverlappingFeatures(1, 9); + assertEquals(overlaps.size(), 1); + assertTrue(overlaps.contains(sf2)); + + overlaps = fs.findOverlappingFeatures(5, 18); + assertEquals(overlaps.size(), 2); + assertTrue(overlaps.contains(sf1)); + assertTrue(overlaps.contains(sf2)); + + overlaps = fs.findOverlappingFeatures(30, 40); + assertEquals(overlaps.size(), 3); + assertTrue(overlaps.contains(sf1)); + assertTrue(overlaps.contains(sf3)); + assertTrue(overlaps.contains(sf4)); + + overlaps = fs.findOverlappingFeatures(80, 90); + assertEquals(overlaps.size(), 2); + assertTrue(overlaps.contains(sf4)); + assertTrue(overlaps.contains(sf5)); + + overlaps = fs.findOverlappingFeatures(68, 70); + assertEquals(overlaps.size(), 3); + assertTrue(overlaps.contains(sf4)); + assertTrue(overlaps.contains(sf5)); + assertTrue(overlaps.contains(sf6)); + } + + /** + * Helper method to add a feature of no particular type + * + * @param fs + * @param from + * @param to + * @return + */ + SequenceFeature addFeature(FeatureStoreI fs, int from, int to) + { + SequenceFeature sf1 = new SequenceFeature("", "", from, to, Float.NaN, + null); + fs.addFeature(sf1); + return sf1; + } + + @Test(groups = "Functional") + public void testFindFeatures_contactFeatures() + { + FeatureStoreI fs = newFeatureStore(); + + SequenceFeature sf = new SequenceFeature("disulphide bond", "bond", 10, + 20, Float.NaN, null); + fs.addFeature(sf); + + /* + * neither contact point in range + */ + List overlaps = fs.findOverlappingFeatures(1, 9); + assertTrue(overlaps.isEmpty()); + + /* + * neither contact point in range + */ + overlaps = fs.findOverlappingFeatures(11, 19); + assertTrue(overlaps.isEmpty()); + + /* + * first contact point in range + */ + overlaps = fs.findOverlappingFeatures(5, 15); + assertEquals(overlaps.size(), 1); + assertTrue(overlaps.contains(sf)); + + /* + * second contact point in range + */ + overlaps = fs.findOverlappingFeatures(15, 25); + assertEquals(overlaps.size(), 1); + assertTrue(overlaps.contains(sf)); + + /* + * both contact points in range + */ + overlaps = fs.findOverlappingFeatures(5, 25); + assertEquals(overlaps.size(), 1); + assertTrue(overlaps.contains(sf)); + } + + @Test(groups = "Functional") + public void testGetPositionalFeatures() + { + FeatureStoreI store = newFeatureStore(); + SequenceFeature sf1 = new SequenceFeature("Metal", "desc", 10, 20, + Float.NaN, null); + store.addFeature(sf1); + // same range, different description + SequenceFeature sf2 = new SequenceFeature("Metal", "desc2", 10, 20, + Float.NaN, null); + store.addFeature(sf2); + // discontiguous range + SequenceFeature sf3 = new SequenceFeature("Metal", "desc", 30, 40, + Float.NaN, null); + store.addFeature(sf3); + // overlapping range + SequenceFeature sf4 = new SequenceFeature("Metal", "desc", 15, 35, + Float.NaN, null); + store.addFeature(sf4); + // enclosing range + SequenceFeature sf5 = new SequenceFeature("Metal", "desc", 5, 50, + Float.NaN, null); + store.addFeature(sf5); + // non-positional feature + SequenceFeature sf6 = new SequenceFeature("Metal", "desc", 0, 0, + Float.NaN, null); + store.addFeature(sf6); + // contact feature + SequenceFeature sf7 = new SequenceFeature("Disulphide bond", "desc", + 18, 45, Float.NaN, null); + store.addFeature(sf7); + + List features = store.getPositionalFeatures(); + assertEquals(features.size(), 6); + assertTrue(features.contains(sf1)); + assertTrue(features.contains(sf2)); + assertTrue(features.contains(sf3)); + assertTrue(features.contains(sf4)); + assertTrue(features.contains(sf5)); + assertFalse(features.contains(sf6)); + assertTrue(features.contains(sf7)); + + features = store.getNonPositionalFeatures(); + assertEquals(features.size(), 1); + assertTrue(features.contains(sf6)); + } + + @Test(groups = "Functional") + public void testDelete() + { + FeatureStoreI store = newFeatureStore(); + SequenceFeature sf1 = addFeature(store, 10, 20); + assertTrue(store.getPositionalFeatures().contains(sf1)); + + /* + * simple deletion + */ + assertTrue(store.delete(sf1)); + assertTrue(store.getPositionalFeatures().isEmpty()); + + /* + * non-positional feature deletion + */ + SequenceFeature sf2 = addFeature(store, 0, 0); + assertFalse(store.getPositionalFeatures().contains(sf2)); + assertTrue(store.getNonPositionalFeatures().contains(sf2)); + assertTrue(store.delete(sf2)); + assertTrue(store.getNonPositionalFeatures().isEmpty()); + + /* + * contact feature deletion + */ + SequenceFeature sf3 = new SequenceFeature("", "Disulphide Bond", 11, + 23, Float.NaN, null); + store.addFeature(sf3); + assertEquals(store.getPositionalFeatures().size(), 1); + assertTrue(store.getPositionalFeatures().contains(sf3)); + assertTrue(store.delete(sf3)); + assertTrue(store.getPositionalFeatures().isEmpty()); + + /* + * nested feature deletion + */ + SequenceFeature sf4 = addFeature(store, 20, 30); + SequenceFeature sf5 = addFeature(store, 22, 26); // to NCList + SequenceFeature sf6 = addFeature(store, 23, 24); // child of sf5 + SequenceFeature sf7 = addFeature(store, 25, 25); // sibling of sf6 + SequenceFeature sf8 = addFeature(store, 24, 24); // child of sf6 + SequenceFeature sf9 = addFeature(store, 23, 23); // child of sf6 + assertEquals(store.getPositionalFeatures().size(), 6); + + // delete a node with children - they take its place + assertTrue(store.delete(sf6)); // sf8, sf9 should become children of sf5 + assertEquals(store.getPositionalFeatures().size(), 5); + assertFalse(store.getPositionalFeatures().contains(sf6)); + + // delete a node with no children + assertTrue(store.delete(sf7)); + assertEquals(store.getPositionalFeatures().size(), 4); + assertFalse(store.getPositionalFeatures().contains(sf7)); + + // delete root of NCList + assertTrue(store.delete(sf5)); + assertEquals(store.getPositionalFeatures().size(), 3); + assertFalse(store.getPositionalFeatures().contains(sf5)); + + // continue the killing fields + assertTrue(store.delete(sf4)); + assertEquals(store.getPositionalFeatures().size(), 2); + assertFalse(store.getPositionalFeatures().contains(sf4)); + + assertTrue(store.delete(sf9)); + assertEquals(store.getPositionalFeatures().size(), 1); + assertFalse(store.getPositionalFeatures().contains(sf9)); + + assertTrue(store.delete(sf8)); + assertTrue(store.getPositionalFeatures().isEmpty()); + } + + @Test(groups = "Functional") + public void testAddFeature() + { + FeatureStoreI fs = newFeatureStore(); + + SequenceFeature sf1 = new SequenceFeature("Cath", "", 10, 20, + Float.NaN, null); + SequenceFeature sf2 = new SequenceFeature("Cath", "", 10, 20, + Float.NaN, null); + + assertTrue(fs.addFeature(sf1)); + assertEquals(fs.getFeatureCount(true), 1); // positional + assertEquals(fs.getFeatureCount(false), 0); // non-positional + + /* + * re-adding the same or an identical feature should fail + */ + assertFalse(fs.addFeature(sf1)); + assertEquals(fs.getFeatureCount(true), 1); + assertFalse(fs.addFeature(sf2)); + assertEquals(fs.getFeatureCount(true), 1); + + /* + * add non-positional + */ + SequenceFeature sf3 = new SequenceFeature("Cath", "", 0, 0, Float.NaN, + null); + assertTrue(fs.addFeature(sf3)); + assertEquals(fs.getFeatureCount(true), 1); // positional + assertEquals(fs.getFeatureCount(false), 1); // non-positional + SequenceFeature sf4 = new SequenceFeature("Cath", "", 0, 0, Float.NaN, + null); + assertFalse(fs.addFeature(sf4)); // already stored + assertEquals(fs.getFeatureCount(true), 1); // positional + assertEquals(fs.getFeatureCount(false), 1); // non-positional + + /* + * add contact + */ + SequenceFeature sf5 = new SequenceFeature("Disulfide bond", "", 10, 20, + Float.NaN, null); + assertTrue(fs.addFeature(sf5)); + assertEquals(fs.getFeatureCount(true), 2); // positional - add 1 for contact + assertEquals(fs.getFeatureCount(false), 1); // non-positional + SequenceFeature sf6 = new SequenceFeature("Disulfide bond", "", 10, 20, + Float.NaN, null); + assertFalse(fs.addFeature(sf6)); // already stored + assertEquals(fs.getFeatureCount(true), 2); // no change + assertEquals(fs.getFeatureCount(false), 1); // no change + } + + @Test(groups = "Functional") + public void testIsEmpty() + { + FeatureStoreI fs = newFeatureStore(); + assertTrue(fs.isEmpty()); + assertEquals(fs.getFeatureCount(true), 0); + + /* + * non-nested feature + */ + SequenceFeature sf1 = new SequenceFeature("Cath", "", 10, 20, + Float.NaN, null); + fs.addFeature(sf1); + assertFalse(fs.isEmpty()); + assertEquals(fs.getFeatureCount(true), 1); + fs.delete(sf1); + assertTrue(fs.isEmpty()); + assertEquals(fs.getFeatureCount(true), 0); + + /* + * non-positional feature + */ + sf1 = new SequenceFeature("Cath", "", 0, 0, Float.NaN, null); + fs.addFeature(sf1); + assertFalse(fs.isEmpty()); + assertEquals(fs.getFeatureCount(false), 1); // non-positional + assertEquals(fs.getFeatureCount(true), 0); // positional + fs.delete(sf1); + assertTrue(fs.isEmpty()); + assertEquals(fs.getFeatureCount(false), 0); + + /* + * contact feature + */ + sf1 = new SequenceFeature("Disulfide bond", "", 19, 49, Float.NaN, null); + fs.addFeature(sf1); + assertFalse(fs.isEmpty()); + assertEquals(fs.getFeatureCount(true), 1); + fs.delete(sf1); + assertTrue(fs.isEmpty()); + assertEquals(fs.getFeatureCount(true), 0); + + /* + * sf2, sf3 added as nested features + */ + sf1 = new SequenceFeature("Cath", "", 19, 49, Float.NaN, null); + SequenceFeature sf2 = new SequenceFeature("Cath", "", 20, 40, + Float.NaN, null); + SequenceFeature sf3 = new SequenceFeature("Cath", "", 25, 35, + Float.NaN, null); + fs.addFeature(sf1); + fs.addFeature(sf2); + fs.addFeature(sf3); + assertEquals(fs.getFeatureCount(true), 3); + assertTrue(fs.delete(sf1)); + assertEquals(fs.getFeatureCount(true), 2); + assertEquals(fs.getFeatures().size(), 2); + assertFalse(fs.isEmpty()); + assertTrue(fs.delete(sf2)); + assertEquals(fs.getFeatureCount(true), 1); + assertFalse(fs.isEmpty()); + assertTrue(fs.delete(sf3)); + assertEquals(fs.getFeatureCount(true), 0); + assertTrue(fs.isEmpty()); // all gone + } + + @Test(groups = "Functional") + public void testGetFeatureGroups() + { + FeatureStoreI fs = newFeatureStore(); + assertTrue(fs.getFeatureGroups(true).isEmpty()); + assertTrue(fs.getFeatureGroups(false).isEmpty()); + + SequenceFeature sf1 = new SequenceFeature("Cath", "desc", 10, 20, 1f, "group1"); + fs.addFeature(sf1); + Set groups = fs.getFeatureGroups(true); + assertEquals(groups.size(), 1); + assertTrue(groups.contains("group1")); + + /* + * add another feature of the same group, delete one, delete both + */ + SequenceFeature sf2 = new SequenceFeature("Cath", "desc", 20, 30, 1f, "group1"); + fs.addFeature(sf2); + groups = fs.getFeatureGroups(true); + assertEquals(groups.size(), 1); + assertTrue(groups.contains("group1")); + fs.delete(sf2); + groups = fs.getFeatureGroups(true); + assertEquals(groups.size(), 1); + assertTrue(groups.contains("group1")); + fs.delete(sf1); + groups = fs.getFeatureGroups(true); + assertTrue(fs.getFeatureGroups(true).isEmpty()); + + SequenceFeature sf3 = new SequenceFeature("Cath", "desc", 20, 30, 1f, "group2"); + fs.addFeature(sf3); + SequenceFeature sf4 = new SequenceFeature("Cath", "desc", 20, 30, 1f, "Group2"); + fs.addFeature(sf4); + SequenceFeature sf5 = new SequenceFeature("Cath", "desc", 20, 30, 1f, null); + fs.addFeature(sf5); + groups = fs.getFeatureGroups(true); + assertEquals(groups.size(), 3); + assertTrue(groups.contains("group2")); + assertTrue(groups.contains("Group2")); // case sensitive + assertTrue(groups.contains(null)); // null allowed + assertTrue(fs.getFeatureGroups(false).isEmpty()); // non-positional + + fs.delete(sf3); + groups = fs.getFeatureGroups(true); + assertEquals(groups.size(), 2); + assertFalse(groups.contains("group2")); + fs.delete(sf4); + groups = fs.getFeatureGroups(true); + assertEquals(groups.size(), 1); + assertFalse(groups.contains("Group2")); + fs.delete(sf5); + groups = fs.getFeatureGroups(true); + assertTrue(groups.isEmpty()); + + /* + * add non-positional feature + */ + SequenceFeature sf6 = new SequenceFeature("Cath", "desc", 0, 0, 1f, + "CathGroup"); + fs.addFeature(sf6); + groups = fs.getFeatureGroups(false); + assertEquals(groups.size(), 1); + assertTrue(groups.contains("CathGroup")); + assertTrue(fs.delete(sf6)); + assertTrue(fs.getFeatureGroups(false).isEmpty()); + } + + @Test(groups = "Functional") + public void testGetTotalFeatureLength() + { + FeatureStoreI fs = newFeatureStore(); + assertEquals(fs.getTotalFeatureLength(), 0); + + addFeature(fs, 10, 20); // 11 + assertEquals(fs.getTotalFeatureLength(), 11); + addFeature(fs, 17, 37); // 21 + SequenceFeature sf1 = addFeature(fs, 14, 74); // 61 + assertEquals(fs.getTotalFeatureLength(), 93); + + // non-positional features don't count + SequenceFeature sf2 = new SequenceFeature("Cath", "desc", 0, 0, 1f, + "group1"); + fs.addFeature(sf2); + assertEquals(fs.getTotalFeatureLength(), 93); + + // contact features count 1 + SequenceFeature sf3 = new SequenceFeature("disulphide bond", "desc", + 15, 35, 1f, "group1"); + fs.addFeature(sf3); + assertEquals(fs.getTotalFeatureLength(), 94); + + assertTrue(fs.delete(sf1)); + assertEquals(fs.getTotalFeatureLength(), 33); + assertFalse(fs.delete(sf1)); + assertEquals(fs.getTotalFeatureLength(), 33); + assertTrue(fs.delete(sf2)); + assertEquals(fs.getTotalFeatureLength(), 33); + assertTrue(fs.delete(sf3)); + assertEquals(fs.getTotalFeatureLength(), 32); + } + + @Test(groups = "Functional") + public void testGetFeatureLength() + { + /* + * positional feature + */ + SequenceFeature sf1 = new SequenceFeature("Cath", "desc", 10, 20, 1f, "group1"); + assertEquals(FeatureStore.getFeatureLength(sf1), 11); + + /* + * non-positional feature + */ + SequenceFeature sf2 = new SequenceFeature("Cath", "desc", 0, 0, 1f, + "CathGroup"); + assertEquals(FeatureStore.getFeatureLength(sf2), 0); + + /* + * contact feature counts 1 + */ + SequenceFeature sf3 = new SequenceFeature("Disulphide Bond", "desc", + 14, 28, 1f, "AGroup"); + assertEquals(FeatureStore.getFeatureLength(sf3), 1); + } + + @Test(groups = "Functional") + public void testMin() + { + assertEquals(FeatureStore.min(Float.NaN, Float.NaN), Float.NaN); + assertEquals(FeatureStore.min(Float.NaN, 2f), 2f); + assertEquals(FeatureStore.min(-2f, Float.NaN), -2f); + assertEquals(FeatureStore.min(2f, -3f), -3f); + } + + @Test(groups = "Functional") + public void testMax() + { + assertEquals(FeatureStore.max(Float.NaN, Float.NaN), Float.NaN); + assertEquals(FeatureStore.max(Float.NaN, 2f), 2f); + assertEquals(FeatureStore.max(-2f, Float.NaN), -2f); + assertEquals(FeatureStore.max(2f, -3f), 2f); + } + + @Test(groups = "Functional") + public void testGetMinimumScore_getMaximumScore() + { + FeatureStoreI fs = newFeatureStore(); + assertEquals(fs.getMinimumScore(true), Float.NaN); // positional + assertEquals(fs.getMaximumScore(true), Float.NaN); + assertEquals(fs.getMinimumScore(false), Float.NaN); // non-positional + assertEquals(fs.getMaximumScore(false), Float.NaN); + + // add features with no score + SequenceFeature sf1 = new SequenceFeature("type", "desc", 0, 0, + Float.NaN, "group"); + fs.addFeature(sf1); + SequenceFeature sf2 = new SequenceFeature("type", "desc", 10, 20, + Float.NaN, "group"); + fs.addFeature(sf2); + assertEquals(fs.getMinimumScore(true), Float.NaN); + assertEquals(fs.getMaximumScore(true), Float.NaN); + assertEquals(fs.getMinimumScore(false), Float.NaN); + assertEquals(fs.getMaximumScore(false), Float.NaN); + + // add positional features with score + SequenceFeature sf3 = new SequenceFeature("type", "desc", 10, 20, 1f, + "group"); + fs.addFeature(sf3); + SequenceFeature sf4 = new SequenceFeature("type", "desc", 12, 16, 4f, + "group"); + fs.addFeature(sf4); + assertEquals(fs.getMinimumScore(true), 1f); + assertEquals(fs.getMaximumScore(true), 4f); + assertEquals(fs.getMinimumScore(false), Float.NaN); + assertEquals(fs.getMaximumScore(false), Float.NaN); + + // add non-positional features with score + SequenceFeature sf5 = new SequenceFeature("type", "desc", 0, 0, 11f, + "group"); + fs.addFeature(sf5); + SequenceFeature sf6 = new SequenceFeature("type", "desc", 0, 0, -7f, + "group"); + fs.addFeature(sf6); + assertEquals(fs.getMinimumScore(true), 1f); + assertEquals(fs.getMaximumScore(true), 4f); + assertEquals(fs.getMinimumScore(false), -7f); + assertEquals(fs.getMaximumScore(false), 11f); + + // delete one positional and one non-positional + // min-max should be recomputed + assertTrue(fs.delete(sf6)); + assertTrue(fs.delete(sf3)); + assertEquals(fs.getMinimumScore(true), 4f); + assertEquals(fs.getMaximumScore(true), 4f); + assertEquals(fs.getMinimumScore(false), 11f); + assertEquals(fs.getMaximumScore(false), 11f); + + // delete remaining features with score + assertTrue(fs.delete(sf4)); + assertTrue(fs.delete(sf5)); + assertEquals(fs.getMinimumScore(true), Float.NaN); + assertEquals(fs.getMaximumScore(true), Float.NaN); + assertEquals(fs.getMinimumScore(false), Float.NaN); + assertEquals(fs.getMaximumScore(false), Float.NaN); + + // delete all features + assertTrue(fs.delete(sf1)); + assertTrue(fs.delete(sf2)); + assertTrue(fs.isEmpty()); + assertEquals(fs.getMinimumScore(true), Float.NaN); + assertEquals(fs.getMaximumScore(true), Float.NaN); + assertEquals(fs.getMinimumScore(false), Float.NaN); + assertEquals(fs.getMaximumScore(false), Float.NaN); + } + + @Test(groups = "Functional") + public void testListContains() + { + assertFalse(FeatureStore.listContains(null, null)); + List features = new ArrayList<>(); + assertFalse(FeatureStore.listContains(features, null)); + + SequenceFeature sf1 = new SequenceFeature("type1", "desc1", 20, 30, 3f, + "group1"); + assertFalse(FeatureStore.listContains(null, sf1)); + assertFalse(FeatureStore.listContains(features, sf1)); + + features.add(sf1); + SequenceFeature sf2 = new SequenceFeature("type1", "desc1", 20, 30, 3f, + "group1"); + SequenceFeature sf3 = new SequenceFeature("type1", "desc1", 20, 40, 3f, + "group1"); + + // sf2.equals(sf1) so contains should return true + assertTrue(FeatureStore.listContains(features, sf2)); + assertFalse(FeatureStore.listContains(features, sf3)); + } + + @Test(groups = "Functional") + public void testGetFeaturesForGroup() + { + FeatureStoreI fs = newFeatureStore(); + + /* + * with no features + */ + assertTrue(fs.getFeaturesForGroup(true, null).isEmpty()); + assertTrue(fs.getFeaturesForGroup(false, null).isEmpty()); + assertTrue(fs.getFeaturesForGroup(true, "uniprot").isEmpty()); + assertTrue(fs.getFeaturesForGroup(false, "uniprot").isEmpty()); + + /* + * sf1: positional feature in the null group + */ + SequenceFeature sf1 = new SequenceFeature("Pfam", "desc", 4, 10, 0f, + null); + fs.addFeature(sf1); + assertTrue(fs.getFeaturesForGroup(true, "uniprot").isEmpty()); + assertTrue(fs.getFeaturesForGroup(false, "uniprot").isEmpty()); + assertTrue(fs.getFeaturesForGroup(false, null).isEmpty()); + List features = fs.getFeaturesForGroup(true, null); + assertEquals(features.size(), 1); + assertTrue(features.contains(sf1)); + + /* + * sf2: non-positional feature in the null group + * sf3: positional feature in a non-null group + * sf4: non-positional feature in a non-null group + */ + SequenceFeature sf2 = new SequenceFeature("Pfam", "desc", 0, 0, 0f, + null); + SequenceFeature sf3 = new SequenceFeature("Pfam", "desc", 4, 10, 0f, + "Uniprot"); + SequenceFeature sf4 = new SequenceFeature("Pfam", "desc", 0, 0, 0f, + "Rfam"); + fs.addFeature(sf2); + fs.addFeature(sf3); + fs.addFeature(sf4); + + features = fs.getFeaturesForGroup(true, null); + assertEquals(features.size(), 1); + assertTrue(features.contains(sf1)); + + features = fs.getFeaturesForGroup(false, null); + assertEquals(features.size(), 1); + assertTrue(features.contains(sf2)); + + features = fs.getFeaturesForGroup(true, "Uniprot"); + assertEquals(features.size(), 1); + assertTrue(features.contains(sf3)); + + features = fs.getFeaturesForGroup(false, "Rfam"); + assertEquals(features.size(), 1); + assertTrue(features.contains(sf4)); + } + + @Test(groups = "Functional") + public void testShiftFeatures() + { + FeatureStoreI fs = newFeatureStore(); + assertFalse(fs.shiftFeatures(0, 1)); // nothing to do + + SequenceFeature sf1 = new SequenceFeature("Cath", "", 2, 5, 0f, null); + fs.addFeature(sf1); + // nested feature: + SequenceFeature sf2 = new SequenceFeature("Cath", "", 8, 14, 0f, null); + fs.addFeature(sf2); + // contact feature: + SequenceFeature sf3 = new SequenceFeature("Disulfide bond", "", 23, 32, + 0f, null); + fs.addFeature(sf3); + // non-positional feature: + SequenceFeature sf4 = new SequenceFeature("Cath", "", 0, 0, 0f, null); + fs.addFeature(sf4); + + /* + * shift all features right by 5 + */ + assertTrue(fs.shiftFeatures(0, 5)); + + // non-positional features untouched: + List nonPos = fs.getNonPositionalFeatures(); + assertEquals(nonPos.size(), 1); + assertTrue(nonPos.contains(sf4)); + + // positional features are replaced + List pos = fs.getPositionalFeatures(); + assertEquals(pos.size(), 3); + assertFalse(pos.contains(sf1)); + assertFalse(pos.contains(sf2)); + assertFalse(pos.contains(sf3)); + SequenceFeatures.sortFeatures(pos, true); // ascending start pos + assertEquals(pos.get(0).getBegin(), 7); + assertEquals(pos.get(0).getEnd(), 10); + assertEquals(pos.get(1).getBegin(), 13); + assertEquals(pos.get(1).getEnd(), 19); + assertEquals(pos.get(2).getBegin(), 28); + assertEquals(pos.get(2).getEnd(), 37); + + /* + * now shift left by 15 + * feature at [7-10] should be removed + * feature at [13-19] should become [1-4] + */ + assertTrue(fs.shiftFeatures(0, -15)); + pos = fs.getPositionalFeatures(); + assertEquals(pos.size(), 2); + SequenceFeatures.sortFeatures(pos, true); + assertEquals(pos.get(0).getBegin(), 1); + assertEquals(pos.get(0).getEnd(), 4); + assertEquals(pos.get(1).getBegin(), 13); + assertEquals(pos.get(1).getEnd(), 22); + + /* + * shift right by 4 from position 2 onwards + * feature at [1-4] unchanged, feature at [13-22] shifts + */ + assertTrue(fs.shiftFeatures(2, 4)); + pos = fs.getPositionalFeatures(); + assertEquals(pos.size(), 2); + SequenceFeatures.sortFeatures(pos, true); + assertEquals(pos.get(0).getBegin(), 1); + assertEquals(pos.get(0).getEnd(), 4); + assertEquals(pos.get(1).getBegin(), 17); + assertEquals(pos.get(1).getEnd(), 26); + + /* + * shift right by 4 from position 18 onwards + * should be no change + */ + SequenceFeature f1 = pos.get(0); + SequenceFeature f2 = pos.get(1); + assertFalse(fs.shiftFeatures(18, 4)); // no update + pos = fs.getPositionalFeatures(); + assertEquals(pos.size(), 2); + SequenceFeatures.sortFeatures(pos, true); + assertSame(pos.get(0), f1); + assertSame(pos.get(1), f2); + } + + @Test(groups = "Functional") + public void testDelete_readd() + { + /* + * add a feature and a nested feature + */ + FeatureStoreI store = newFeatureStore(); + SequenceFeature sf1 = addFeature(store, 10, 20); + // sf2 is nested in sf1 so will be stored in nestedFeatures + SequenceFeature sf2 = addFeature(store, 12, 14); + List features = store.getPositionalFeatures(); + assertEquals(features.size(), 2); + assertTrue(features.contains(sf1)); + assertTrue(features.contains(sf2)); + assertTrue(store.getFeatures().contains(sf1)); + assertTrue(store.getFeatures().contains(sf2)); + + /* + * delete the first feature + */ + assertTrue(store.delete(sf1)); + features = store.getPositionalFeatures(); + assertFalse(features.contains(sf1)); + assertTrue(features.contains(sf2)); + + /* + * re-add the 'nested' feature; is it now duplicated? + */ + store.addFeature(sf2); + features = store.getPositionalFeatures(); + assertEquals(features.size(), 1); + assertTrue(features.contains(sf2)); + } + + @Test(groups = "Functional") + public void testContains() + { + FeatureStoreI fs = newFeatureStore(); + SequenceFeature sf1 = new SequenceFeature("Cath", "", 10, 20, + Float.NaN, "group1"); + SequenceFeature sf2 = new SequenceFeature("Cath", "", 10, 20, + Float.NaN, "group2"); + SequenceFeature sf3 = new SequenceFeature("Cath", "", 0, 0, Float.NaN, + "group1"); + SequenceFeature sf4 = new SequenceFeature("Cath", "", 0, 0, 0f, + "group1"); + SequenceFeature sf5 = new SequenceFeature("Disulphide Bond", "", 5, 15, + Float.NaN, "group1"); + SequenceFeature sf6 = new SequenceFeature("Disulphide Bond", "", 5, 15, + Float.NaN, "group2"); + + fs.addFeature(sf1); + fs.addFeature(sf3); + fs.addFeature(sf5); + assertTrue(fs.contains(sf1)); // positional feature + assertTrue(fs.contains(new SequenceFeature(sf1))); // identical feature + assertFalse(fs.contains(sf2)); // different group + assertTrue(fs.contains(sf3)); // non-positional + assertTrue(fs.contains(new SequenceFeature(sf3))); + assertFalse(fs.contains(sf4)); // different score + assertTrue(fs.contains(sf5)); // contact feature + assertTrue(fs.contains(new SequenceFeature(sf5))); + assertFalse(fs.contains(sf6)); // different group + + /* + * add a nested feature + */ + SequenceFeature sf7 = new SequenceFeature("Cath", "", 12, 16, + Float.NaN, "group1"); + fs.addFeature(sf7); + assertTrue(fs.contains(sf7)); + assertTrue(fs.contains(new SequenceFeature(sf7))); + + /* + * delete the outer (enclosing, non-nested) feature + */ + fs.delete(sf1); + assertFalse(fs.contains(sf1)); + assertTrue(fs.contains(sf7)); + } +} diff --git a/test/jalview/datamodel/features/FeatureStoreTest.java b/test/jalview/datamodel/features/FeatureStoreTest.java index c38cb1e..7fe94d0 100644 --- a/test/jalview/datamodel/features/FeatureStoreTest.java +++ b/test/jalview/datamodel/features/FeatureStoreTest.java @@ -19,7 +19,7 @@ public class FeatureStoreTest @Test(groups = "Functional") public void testFindFeatures_nonNested() { - FeatureStore fs = new FeatureStore(); + FeatureStoreI fs = newFeatureStore(); fs.addFeature(new SequenceFeature("", "", 10, 20, Float.NaN, null)); // same range different description @@ -46,10 +46,16 @@ public class FeatureStoreTest assertEquals(overlaps.get(0).getEnd(), 35); } + private FeatureStoreI newFeatureStore() + { + // return new FeatureStoreJS(); + return new FeatureStoreImpl(); + } + @Test(groups = "Functional") public void testFindFeatures_nested() { - FeatureStore fs = new FeatureStore(); + FeatureStoreI fs = newFeatureStore(); SequenceFeature sf1 = addFeature(fs, 10, 50); SequenceFeature sf2 = addFeature(fs, 10, 40); SequenceFeature sf3 = addFeature(fs, 20, 30); @@ -88,7 +94,7 @@ public class FeatureStoreTest @Test(groups = "Functional") public void testFindFeatures_mixed() { - FeatureStore fs = new FeatureStore(); + FeatureStoreI fs = newFeatureStore(); SequenceFeature sf1 = addFeature(fs, 10, 50); SequenceFeature sf2 = addFeature(fs, 1, 15); SequenceFeature sf3 = addFeature(fs, 20, 30); @@ -134,7 +140,7 @@ public class FeatureStoreTest * @param to * @return */ - SequenceFeature addFeature(FeatureStore fs, int from, int to) + SequenceFeature addFeature(FeatureStoreI fs, int from, int to) { SequenceFeature sf1 = new SequenceFeature("", "", from, to, Float.NaN, null); @@ -145,7 +151,7 @@ public class FeatureStoreTest @Test(groups = "Functional") public void testFindFeatures_contactFeatures() { - FeatureStore fs = new FeatureStore(); + FeatureStoreI fs = newFeatureStore(); SequenceFeature sf = new SequenceFeature("disulphide bond", "bond", 10, 20, Float.NaN, null); @@ -188,7 +194,7 @@ public class FeatureStoreTest @Test(groups = "Functional") public void testGetPositionalFeatures() { - FeatureStore store = new FeatureStore(); + FeatureStoreI store = newFeatureStore(); SequenceFeature sf1 = new SequenceFeature("Metal", "desc", 10, 20, Float.NaN, null); store.addFeature(sf1); @@ -235,7 +241,7 @@ public class FeatureStoreTest @Test(groups = "Functional") public void testDelete() { - FeatureStore store = new FeatureStore(); + FeatureStoreI store = newFeatureStore(); SequenceFeature sf1 = addFeature(store, 10, 20); assertTrue(store.getPositionalFeatures().contains(sf1)); @@ -307,7 +313,7 @@ public class FeatureStoreTest @Test(groups = "Functional") public void testAddFeature() { - FeatureStore fs = new FeatureStore(); + FeatureStoreI fs = newFeatureStore(); SequenceFeature sf1 = new SequenceFeature("Cath", "", 10, 20, Float.NaN, null); @@ -358,7 +364,7 @@ public class FeatureStoreTest @Test(groups = "Functional") public void testIsEmpty() { - FeatureStore fs = new FeatureStore(); + FeatureStoreI fs = newFeatureStore(); assertTrue(fs.isEmpty()); assertEquals(fs.getFeatureCount(true), 0); @@ -411,7 +417,7 @@ public class FeatureStoreTest assertEquals(fs.getFeatureCount(true), 3); assertTrue(fs.delete(sf1)); assertEquals(fs.getFeatureCount(true), 2); - assertEquals(fs.features.size(), 2); + assertEquals(fs.getFeatures().size(), 2); assertFalse(fs.isEmpty()); assertTrue(fs.delete(sf2)); assertEquals(fs.getFeatureCount(true), 1); @@ -424,7 +430,7 @@ public class FeatureStoreTest @Test(groups = "Functional") public void testGetFeatureGroups() { - FeatureStore fs = new FeatureStore(); + FeatureStoreI fs = newFeatureStore(); assertTrue(fs.getFeatureGroups(true).isEmpty()); assertTrue(fs.getFeatureGroups(false).isEmpty()); @@ -491,7 +497,7 @@ public class FeatureStoreTest @Test(groups = "Functional") public void testGetTotalFeatureLength() { - FeatureStore fs = new FeatureStore(); + FeatureStoreI fs = newFeatureStore(); assertEquals(fs.getTotalFeatureLength(), 0); addFeature(fs, 10, 20); // 11 @@ -567,7 +573,7 @@ public class FeatureStoreTest @Test(groups = "Functional") public void testGetMinimumScore_getMaximumScore() { - FeatureStore fs = new FeatureStore(); + FeatureStoreI fs = newFeatureStore(); assertEquals(fs.getMinimumScore(true), Float.NaN); // positional assertEquals(fs.getMaximumScore(true), Float.NaN); assertEquals(fs.getMinimumScore(false), Float.NaN); // non-positional @@ -662,7 +668,7 @@ public class FeatureStoreTest @Test(groups = "Functional") public void testGetFeaturesForGroup() { - FeatureStore fs = new FeatureStore(); + FeatureStoreI fs = newFeatureStore(); /* * with no features @@ -720,7 +726,7 @@ public class FeatureStoreTest @Test(groups = "Functional") public void testShiftFeatures() { - FeatureStore fs = new FeatureStore(); + FeatureStoreI fs = newFeatureStore(); assertFalse(fs.shiftFeatures(0, 1)); // nothing to do SequenceFeature sf1 = new SequenceFeature("Cath", "", 2, 5, 0f, null); @@ -807,7 +813,7 @@ public class FeatureStoreTest /* * add a feature and a nested feature */ - FeatureStore store = new FeatureStore(); + FeatureStoreI store = newFeatureStore(); SequenceFeature sf1 = addFeature(store, 10, 20); // sf2 is nested in sf1 so will be stored in nestedFeatures SequenceFeature sf2 = addFeature(store, 12, 14); @@ -815,8 +821,8 @@ public class FeatureStoreTest assertEquals(features.size(), 2); assertTrue(features.contains(sf1)); assertTrue(features.contains(sf2)); - assertTrue(store.features.contains(sf1)); - assertTrue(store.features.contains(sf2)); + assertTrue(store.getFeatures().contains(sf1)); + assertTrue(store.getFeatures().contains(sf2)); /* * delete the first feature @@ -838,7 +844,7 @@ public class FeatureStoreTest @Test(groups = "Functional") public void testContains() { - FeatureStore fs = new FeatureStore(); + FeatureStoreI fs = newFeatureStore(); SequenceFeature sf1 = new SequenceFeature("Cath", "", 10, 20, Float.NaN, "group1"); SequenceFeature sf2 = new SequenceFeature("Cath", "", 10, 20, diff --git a/test/jalview/datamodel/features/SequenceFeaturesTest.java b/test/jalview/datamodel/features/SequenceFeaturesTest.java index 29e76bb..30b1402 100644 --- a/test/jalview/datamodel/features/SequenceFeaturesTest.java +++ b/test/jalview/datamodel/features/SequenceFeaturesTest.java @@ -889,11 +889,11 @@ public class SequenceFeaturesTest * no type specified - get all types stored * they are returned in keyset (alphabetical) order */ - Map featureStores = (Map) PA + Map featureStores = (Map) PA .getValue(sf, "featureStore"); - Iterable types = sf.varargToTypes(); - Iterator iterator = types.iterator(); + Iterable types = sf.varargToTypes(); + Iterator iterator = types.iterator(); assertTrue(iterator.hasNext()); assertSame(iterator.next(), featureStores.get("Cath")); assertTrue(iterator.hasNext()); -- 1.7.10.2