X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=src%2Fjalview%2Fdatamodel%2Ffeatures%2FFeatureStore.java;h=c582e565f396113f5542a361825984abc3be1891;hb=78991c8c3216606a0e7203ec25f59fea4898126c;hp=75ec45aeaa089e9e5ae872efb8bc913479431a3e;hpb=b74cdec4b07000bee431a7cca86a948f44d3ffbe;p=jalview.git diff --git a/src/jalview/datamodel/features/FeatureStore.java b/src/jalview/datamodel/features/FeatureStore.java index 75ec45a..c582e56 100644 --- a/src/jalview/datamodel/features/FeatureStore.java +++ b/src/jalview/datamodel/features/FeatureStore.java @@ -21,7 +21,6 @@ package jalview.datamodel.features; import jalview.datamodel.SequenceFeature; -import jalview.util.Platform; import java.util.ArrayList; import java.util.Collection; @@ -31,16 +30,35 @@ import java.util.List; import java.util.Set; import intervalstore.api.IntervalStoreI; +import intervalstore.impl.BinarySearcher; +import intervalstore.impl.BinarySearcher.Compare; -public abstract class FeatureStore implements FeatureStoreI +public class FeatureStore { + public enum IntervalStoreType + { + /** + * original NCList-based IntervalStore + */ + INTERVAL_STORE_NCLIST, - /** - * track last start for quick insertion of ordered features + /** + * linked-list IntervalStore + */ + INTERVAL_STORE_LINKED_LIST, + + /** + * NCList as array buffer IntervalStore + */ + INTERVAL_STORE_NCARRAY + } + + /* + * track largest start for quick insertion of ordered features */ - protected int lastStart = -1; + protected int maxStart = -1; - protected int lastContactStart = -1; + protected int maxContactStart = -1; /* * Non-positional features have no (zero) start/end position. @@ -90,37 +108,6 @@ public abstract class FeatureStore implements FeatureStoreI float nonPositionalMaxScore; - public final static int INTERVAL_STORE_DEFAULT = -1; - - /** - * original NCList-based IntervalStore - */ - public final static int INTERVAL_STORE_NCLIST_OBJECT = 0; - - /** - * linked-list IntervalStore - */ - public final static int INTERVAL_STORE_LINKED_LIST_PRESORT = 1; - - /** - * linked-list IntervalStore - */ - public final static int INTERVAL_STORE_LINKED_LIST_NO_PRESORT = 2; - - /** - * NCList as array buffer IntervalStore - */ - public final static int INTERVAL_STORE_NCLIST_BUFFER_PRESORT = 3; - - /** - * NCList as array buffer IntervalStore - */ - public final static int INTERVAL_STORE_NCLIST_BUFFER_NO_PRESORT = 4; - - static final int intervalStoreJavaOption = INTERVAL_STORE_NCLIST_OBJECT; - - static final int intervalStoreJSOption = INTERVAL_STORE_NCLIST_BUFFER_PRESORT; - /** * Answers the 'length' of the feature, counting 0 for non-positional features * and 1 for contact features @@ -150,8 +137,7 @@ public abstract class FeatureStore implements FeatureStoreI * @param feature * @return */ - @Override - public boolean listContains(List list, + public static boolean listContains(List list, SequenceFeature feature) { if (list == null || feature == null) @@ -159,40 +145,26 @@ public abstract class FeatureStore implements FeatureStoreI return false; } - return (getEquivalentFeatureIndex(list, feature) >= 0); - } - - /** - * Binary search for the index (>= 0) of a feature in a list. - * - * @param list - * @param feature - * @return index if found; -1 if not - */ - protected int getEquivalentFeatureIndex(List list, - SequenceFeature feature) - { - /* * locate the first entry in the list which does not precede the feature */ int begin = feature.begin; - int pos = findFirstBegin(list, begin); + int pos = BinarySearcher.findFirst(list, true, Compare.GE, begin); int len = list.size(); while (pos < len) { SequenceFeature sf = list.get(pos); if (sf.begin > begin) { - return -1; // no match found + return false; // no match found } if (sf.equals(feature)) { - return pos; + return true; } pos++; } - return -1; + return false; } /** @@ -236,17 +208,18 @@ public abstract class FeatureStore implements FeatureStoreI } /** - * standard constructor + * Constructor that defaults to using NCList IntervalStore */ public FeatureStore() { - this(INTERVAL_STORE_DEFAULT); + this(IntervalStoreType.INTERVAL_STORE_NCLIST); } /** - * constructor for testing only + * Constructor that allows an alternative IntervalStore implementation to be + * chosen */ - public FeatureStore(int intervalStoreType) + public FeatureStore(IntervalStoreType intervalStoreType) { features = getIntervalStore(intervalStoreType); positionalFeatureGroups = new HashSet<>(); @@ -256,27 +229,21 @@ public abstract class FeatureStore implements FeatureStoreI nonPositionalMinScore = Float.NaN; nonPositionalMaxScore = Float.NaN; - // we only construct nonPositionalFeatures, contactFeatures if we need to + // only construct nonPositionalFeatures or contactFeatures if needed } - private IntervalStoreI getIntervalStore(int type) + private IntervalStoreI getIntervalStore( + IntervalStoreType type) { - switch (type != INTERVAL_STORE_DEFAULT ? type : // - Platform.isJS() // - ? intervalStoreJSOption - : intervalStoreJavaOption) + switch (type) { default: - case INTERVAL_STORE_NCLIST_OBJECT: + case INTERVAL_STORE_NCLIST: return new intervalstore.impl.IntervalStore<>(); - case INTERVAL_STORE_NCLIST_BUFFER_PRESORT: - return new intervalstore.nonc.IntervalStore<>(true); - case INTERVAL_STORE_NCLIST_BUFFER_NO_PRESORT: - return new intervalstore.nonc.IntervalStore<>(false); - case INTERVAL_STORE_LINKED_LIST_PRESORT: - return new intervalstore.nonc.IntervalStore0<>(true); - case INTERVAL_STORE_LINKED_LIST_NO_PRESORT: - return new intervalstore.nonc.IntervalStore0<>(false); + case INTERVAL_STORE_NCARRAY: + return new intervalstore.nonc.IntervalStore<>(); + case INTERVAL_STORE_LINKED_LIST: + return new intervalstore.nonc.IntervalStore0<>(); } } @@ -301,8 +268,9 @@ public abstract class FeatureStore implements FeatureStoreI * insert into list sorted by start (first contact position): * binary search the sorted list to find the insertion point */ - contactFeatureStarts.add( - findFirstBegin(contactFeatureStarts, feature.begin), feature); + int insertAt = BinarySearcher.findFirst(contactFeatureStarts, true, + Compare.GE, feature.begin); + contactFeatureStarts.add(insertAt, feature); /* * insert into list sorted by end (second contact position): * binary search the sorted list to find the insertion point @@ -321,23 +289,8 @@ public abstract class FeatureStore implements FeatureStoreI * * @param feature */ - - @Override public boolean addFeature(SequenceFeature feature) { - // if (contains(feature)) - // { - // return false; - // } - - // /* - // * keep a record of feature groups - // */ - // if (!feature.isNonPositional()) - // { - // positionalFeatureGroups.add(feature.getFeatureGroup()); - // } - if (feature.isContactFeature()) { if (containsContactFeature(feature)) @@ -345,15 +298,15 @@ public abstract class FeatureStore implements FeatureStoreI return false; } positionalFeatureGroups.add(feature.getFeatureGroup()); - if (feature.begin > lastContactStart) + if (feature.begin > maxContactStart) { - lastContactStart = feature.begin; + maxContactStart = feature.begin; } addContactFeature(feature); } else if (feature.isNonPositional()) { - if (containsNonPositional(feature)) + if (containsNonPositionalFeature(feature)) { return false; } @@ -362,16 +315,14 @@ public abstract class FeatureStore implements FeatureStoreI } else { - // allow for check with - if (checkContainsPositionalFeatureForAdd(feature) - || !addPositionalFeature(feature)) + if (!features.add(feature, false)) { return false; } positionalFeatureGroups.add(feature.getFeatureGroup()); - if (feature.begin > lastStart) + if (feature.begin > maxStart) { - lastStart = feature.begin; + maxStart = feature.begin; } } @@ -423,14 +374,6 @@ public abstract class FeatureStore implements FeatureStoreI } /** - * Adds one feature to the IntervalStore that can manage nested features - * (creating the IntervalStore if necessary) - * - * @return true if added -- allowing for late checking during addition - */ - abstract protected boolean addPositionalFeature(SequenceFeature feature); - - /** * Adds the feature to the list of non-positional features (with lazy * instantiation of the list if it is null), and returns true. The feature * group is added to the set of distinct feature groups for non-positional @@ -460,58 +403,53 @@ public abstract class FeatureStore implements FeatureStoreI * @param feature * @return */ - @Override public boolean contains(SequenceFeature feature) { if (feature.isNonPositional()) { - return containsNonPositional(feature); - + return containsNonPositionalFeature(feature); } if (feature.isContactFeature()) { return containsContactFeature(feature); - } return containsPositionalFeature(feature); + } + private boolean containsPositionalFeature(SequenceFeature feature) + { + return features == null || feature.begin > maxStart ? false + : features.contains(feature); } /** - * A check that can be overridden if the check is being done during the add - * operation itself. + * Answers true if this store already contains a contact feature equal to the + * given feature (by {@code SequenceFeature.equals()} test), else false * * @param feature * @return */ - protected boolean checkContainsPositionalFeatureForAdd( - SequenceFeature feature) - { - return containsPositionalFeature(feature); - } - - private boolean containsPositionalFeature(SequenceFeature feature) - { - return features == null || feature.begin > lastStart ? false - : containsFeature(feature); - } - private boolean containsContactFeature(SequenceFeature feature) { - return contactFeatureStarts != null && feature.begin <= lastContactStart + return contactFeatureStarts != null && feature.begin <= maxContactStart && listContains(contactFeatureStarts, feature); } - private boolean containsNonPositional(SequenceFeature feature) + /** + * Answers true if this store already contains a non-positional feature equal + * to the given feature (by {@code SequenceFeature.equals()} test), else false + * + * @param feature + * @return + */ + private boolean containsNonPositionalFeature(SequenceFeature feature) { return nonPositionalFeatures == null ? false : nonPositionalFeatures.contains(feature); } - abstract protected boolean containsFeature(SequenceFeature feature); - /** * Deletes the given feature from the store, returning true if it was found * (and deleted), else false. This method makes no assumption that the feature @@ -520,8 +458,6 @@ public abstract class FeatureStore implements FeatureStoreI * * @param sf */ - - @Override public synchronized boolean delete(SequenceFeature sf) { boolean removed = false; @@ -552,7 +488,7 @@ public abstract class FeatureStore implements FeatureStoreI */ if (!removed && features != null) { - removed = findAndRemoveNonContactFeature(sf); + removed = features.remove(sf); } if (removed) @@ -563,23 +499,11 @@ public abstract class FeatureStore implements FeatureStoreI return removed; } - abstract protected boolean findAndRemoveNonContactFeature(SequenceFeature sf); - - abstract protected void findContactFeatures(long from, long to, - List result); - - abstract protected int findFirstBegin(List list, - long pos); - - abstract protected int findFirstEnd(List list, long pos); - - @Override public List findOverlappingFeatures(long start, long end) { return findOverlappingFeatures(start, end, null); } - @Override public List getContactFeatures() { return getContactFeatures(new ArrayList<>()); @@ -591,8 +515,6 @@ public abstract class FeatureStore implements FeatureStoreI * * @return */ - - @Override public List getContactFeatures( List result) { @@ -610,8 +532,6 @@ public abstract class FeatureStore implements FeatureStoreI * @param positional * @return */ - - @Override public int getFeatureCount(boolean positional) { if (!positional) @@ -622,7 +542,6 @@ public abstract class FeatureStore implements FeatureStoreI return (contactFeatureStarts == null ? 0 : contactFeatureStarts.size()) + features.size(); - } /** @@ -633,8 +552,6 @@ public abstract class FeatureStore implements FeatureStoreI * @param positionalFeatures * @return */ - - @Override public Set getFeatureGroups(boolean positionalFeatures) { if (positionalFeatures) @@ -649,12 +566,6 @@ public abstract class FeatureStore implements FeatureStoreI } } - @Override - public Collection getFeatures() - { - return features; - } - /** * Answers a list of all either positional or non-positional features whose * feature group matches the given group (which may be null) @@ -663,8 +574,6 @@ public abstract class FeatureStore implements FeatureStoreI * @param group * @return */ - - @Override public List getFeaturesForGroup(boolean positional, String group) { @@ -700,8 +609,6 @@ public abstract class FeatureStore implements FeatureStoreI * @param positional * @return */ - - @Override public float getMaximumScore(boolean positional) { return positional ? positionalMaxScore : nonPositionalMaxScore; @@ -715,14 +622,11 @@ public abstract class FeatureStore implements FeatureStoreI * @param positional * @return */ - - @Override public float getMinimumScore(boolean positional) { return positional ? positionalMinScore : nonPositionalMinScore; } - @Override public List getNonPositionalFeatures() { return getNonPositionalFeatures(new ArrayList<>()); @@ -734,8 +638,6 @@ public abstract class FeatureStore implements FeatureStoreI * * @return */ - - @Override public List getNonPositionalFeatures( List result) { @@ -746,7 +648,6 @@ public abstract class FeatureStore implements FeatureStoreI return result; } - @Override public List getPositionalFeatures() { return getPositionalFeatures(new ArrayList<>()); @@ -757,8 +658,6 @@ public abstract class FeatureStore implements FeatureStoreI * * @return */ - - @Override public List getPositionalFeatures( List result) { @@ -788,8 +687,6 @@ public abstract class FeatureStore implements FeatureStoreI * * @return */ - - @Override public int getTotalFeatureLength() { return totalExtent; @@ -800,8 +697,6 @@ public abstract class FeatureStore implements FeatureStoreI * * @return */ - - @Override public boolean isEmpty() { boolean hasFeatures = (contactFeatureStarts != null @@ -832,10 +727,9 @@ public abstract class FeatureStore implements FeatureStoreI */ if (nonPositionalFeatures != null) { - List list = nonPositionalFeatures; - for (int i = 0, n = list.size(); i < n; i++) + for (int i = 0, n = nonPositionalFeatures.size(); i < n; i++) { - SequenceFeature sf = list.get(i); + SequenceFeature sf = nonPositionalFeatures.get(i); nonPositionalFeatureGroups.add(sf.getFeatureGroup()); float score = sf.getScore(); nonPositionalMinScore = min(nonPositionalMinScore, score); @@ -843,14 +737,17 @@ public abstract class FeatureStore implements FeatureStoreI } } - /* - * scan positional features for groups, scores and extents - */ - rescanPositional(contactFeatureStarts); rescanPositional(features); } + /** + * Scans the given features and updates cached feature groups, minimum and + * maximum feature score, and total feature extent (length) for positional + * features + * + * @param sfs + */ private void rescanPositional(Collection sfs) { if (sfs == null) @@ -876,8 +773,6 @@ public abstract class FeatureStore implements FeatureStoreI * @param shiftBy * @return */ - - @Override public synchronized boolean shiftFeatures(int fromPosition, int shiftBy) { /* @@ -912,4 +807,163 @@ public abstract class FeatureStore implements FeatureStoreI return modified; } + /** + * Answers the position (0, 1...) in the list of the first entry whose end + * position is not less than {@ pos}. If no such entry is found, answers the + * length of the list. + * + * @param list + * @param pos + * @return + */ + protected int findFirstEnd(List list, long pos) + { + return BinarySearcher.findFirst(list, false, Compare.GE, (int) pos); + } + + /** + * Adds contact features to the result list where either the second or the + * first contact position lies within the target range + * + * @param from + * @param to + * @param result + */ + protected void findContactFeatures(long from, long to, + List 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 = findFirstEnd(contactFeatureEnds, from); + + int n = contactFeatureEnds.size(); + while (index < n) + { + SequenceFeature sf = contactFeatureEnds.get(index); + if (!sf.isContactFeature()) + { + System.err.println("Error! non-contact feature type " + sf.getType() + + " in contact features list"); + index++; + continue; + } + + int begin = sf.getBegin(); + if (begin >= from && begin <= to) + { + /* + * this feature's first contact position lies in the search range + * so we don't include it in results a second time + */ + index++; + continue; + } + + if (sf.getEnd() > to) + { + /* + * this feature (and all following) has end point after the target range + */ + break; + } + + /* + * feature has end >= from and end <= to + * i.e. contact end point lies within overlap search range + */ + result.add(sf); + index++; + } + } + + /** + * Adds contact features whose start position lies in the from-to range to the + * result list + * + * @param from + * @param to + * @param result + */ + private void findContactStartOverlaps(long from, long to, + List result) + { + int index = BinarySearcher.findFirst(contactFeatureStarts, true, + Compare.GE, (int) from); + + while (index < contactFeatureStarts.size()) + { + SequenceFeature sf = contactFeatureStarts.get(index); + if (!sf.isContactFeature()) + { + System.err.println("Error! non-contact feature " + sf.toString() + + " in contact features list"); + index++; + continue; + } + if (sf.getBegin() > to) + { + /* + * this feature's start (and all following) follows the target range + */ + break; + } + + /* + * feature has begin >= from and begin <= to + * i.e. contact start point lies within overlap search range + */ + result.add(sf); + index++; + } + } + + /** + * Returns a (possibly empty) list of features whose extent overlaps the given + * range. The returned list is not ordered. Contact features are included if + * either of the contact points lies within the range. If the {@code result} + * parameter is not null, new entries are added to this list and the (possibly + * extended) list returned. + * + * @param start + * start position of overlap range (inclusive) + * @param end + * end position of overlap range (inclusive) + * @param result + * @return + */ + public List findOverlappingFeatures(long start, long end, + List result) + { + if (result == null) + { + result = new ArrayList<>(); + } + + findContactFeatures(start, end, result); + features.findOverlaps(start, end, result); + + return result; + } + }