X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=src%2Fjalview%2Fdatamodel%2Ffeatures%2FFeatureStore.java;h=615b34036ee713e87b5d50a5f955c0e0d7343135;hb=f8258d012b4afd77e0dd6fd3743714fbabb59c8f;hp=8db35a3d8863e0421c3f17d4792d24fc09b8f95d;hpb=0031ee4b6a42ad328e417cb65c7a840183e62e87;p=jalview.git diff --git a/src/jalview/datamodel/features/FeatureStore.java b/src/jalview/datamodel/features/FeatureStore.java index 8db35a3..615b340 100644 --- a/src/jalview/datamodel/features/FeatureStore.java +++ b/src/jalview/datamodel/features/FeatureStore.java @@ -21,6 +21,7 @@ package jalview.datamodel.features; import jalview.datamodel.SequenceFeature; +import jalview.util.Platform; import java.util.ArrayList; import java.util.Collection; @@ -29,8 +30,94 @@ import java.util.HashSet; import java.util.List; import java.util.Set; -public abstract class FeatureStore implements FeatureStoreI +import intervalstore.api.IntervalStoreI; +import intervalstore.impl.BinarySearcher; +import intervalstore.impl.BinarySearcher.Compare; + +public class FeatureStore { + /* + * track last start for quick insertion of ordered features + */ + protected int lastStart = -1; + + protected int lastContactStart = -1; + + /* + * Non-positional features have no (zero) start/end position. + * Kept as a separate list in case this criterion changes in future. + */ + List nonPositionalFeatures; + + /* + * contact features ordered by first contact position + */ + List contactFeatureStarts; + + /* + * contact features ordered by second contact position + */ + List contactFeatureEnds; + + /* + * IntervalStore holds remaining features and provides efficient + * query for features overlapping any given interval + */ + IntervalStoreI features; + + /* + * Feature groups represented in stored positional features + * (possibly including null) + */ + Set positionalFeatureGroups; + + /* + * Feature groups represented in stored non-positional features + * (possibly including null) + */ + Set nonPositionalFeatureGroups; + + /* + * the total length of all positional features; contact features count 1 to + * the total and 1 to size(), consistent with an average 'feature length' of 1 + */ + int totalExtent; + + float positionalMinScore; + + float positionalMaxScore; + + float nonPositionalMinScore; + + 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 = 1; + + /** + * NCList as array buffer IntervalStore + */ + public final static int INTERVAL_STORE_NCARRAY = 3; + + static final int intervalStoreJavaOption = INTERVAL_STORE_NCLIST_OBJECT; + + private final static boolean isJSLinkedTest = false; + + static final int intervalStoreJSOption = (isJSLinkedTest + ? INTERVAL_STORE_LINKED_LIST + : INTERVAL_STORE_NCARRAY); + + // TODO: compare performance in real situations using + // INTERVAL_STORE_LINKED_LIST; /** * Answers the 'length' of the feature, counting 0 for non-positional features @@ -61,7 +148,6 @@ public abstract class FeatureStore implements FeatureStoreI * @param feature * @return */ - @Override public boolean listContains(List list, SequenceFeature feature) { @@ -70,39 +156,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 pos = findFirstBegin(list, feature.begin); + int begin = feature.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 > feature.begin) + 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; } /** @@ -145,59 +218,24 @@ 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. - */ - List nonPositionalFeatures; - - /* - * contact features ordered by first contact position - */ - List contactFeatureStarts; - - /* - * contact features ordered by second contact position - */ - List contactFeatureEnds; - - /* - * IntervalStore holds remaining features and provides efficient - * query for features overlapping any given interval - */ - Collection features; - - /* - * Feature groups represented in stored positional features - * (possibly including null) - */ - Set positionalFeatureGroups; - - /* - * Feature groups represented in stored non-positional features - * (possibly including null) - */ - Set nonPositionalFeatureGroups; - - /* - * the total length of all positional features; contact features count 1 to - * the total and 1 to size(), consistent with an average 'feature length' of 1 + /** + * standard constructor */ - int totalExtent; - - float positionalMinScore; - - float positionalMaxScore; - - float nonPositionalMinScore; - - float nonPositionalMaxScore; + public FeatureStore() + { + this(INTERVAL_STORE_DEFAULT); + } /** - * Constructor + * constructor for testing only */ - public FeatureStore() + public FeatureStore(int intervalStoreType) { + features = + // Platform.isJS() + // ? new intervalstore.nonc.IntervalStore<>(true) + // : new intervalstore.impl.IntervalStore<>(); + getIntervalStore(intervalStoreType); positionalFeatureGroups = new HashSet<>(); nonPositionalFeatureGroups = new HashSet<>(); positionalMinScore = Float.NaN; @@ -208,6 +246,23 @@ public abstract class FeatureStore implements FeatureStoreI // we only construct nonPositionalFeatures, contactFeatures if we need to } + private IntervalStoreI getIntervalStore(int type) + { + switch (type != INTERVAL_STORE_DEFAULT ? type : // + Platform.isJS() // + ? intervalStoreJSOption + : intervalStoreJavaOption) + { + default: + case INTERVAL_STORE_NCLIST_OBJECT: + return new intervalstore.impl.IntervalStore<>(); + case INTERVAL_STORE_NCARRAY: + return new intervalstore.nonc.IntervalStoreImpl(); + case INTERVAL_STORE_LINKED_LIST: + return new intervalstore.nonc.IntervalStore0Impl(); + } + } + /** * 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 @@ -229,8 +284,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 @@ -249,34 +305,41 @@ 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)) + { + return false; + } + positionalFeatureGroups.add(feature.getFeatureGroup()); + if (feature.begin > lastContactStart) + { + lastContactStart = feature.begin; + } addContactFeature(feature); } else if (feature.isNonPositional()) { + if (containsNonPositionalFeature(feature)) + { + return false; + } + addNonPositionalFeature(feature); } else { - addPositionalFeature(feature); + if (!features.add(feature, false)) + { + return false; + } + positionalFeatureGroups.add(feature.getFeatureGroup()); + if (feature.begin > lastStart) + { + lastStart = feature.begin; + } } /* @@ -327,12 +390,6 @@ public abstract class FeatureStore implements FeatureStoreI } /** - * Adds one feature to the IntervalStore that can manage nested features - * (creating the IntervalStore if necessary) - */ - abstract protected void 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 @@ -362,26 +419,53 @@ public abstract class FeatureStore implements FeatureStoreI * @param feature * @return */ - @Override public boolean contains(SequenceFeature feature) { if (feature.isNonPositional()) { - return nonPositionalFeatures == null ? false - : nonPositionalFeatures.contains(feature); + return containsNonPositionalFeature(feature); } if (feature.isContactFeature()) { - return contactFeatureStarts != null - && listContains(contactFeatureStarts, feature); + return containsContactFeature(feature); } - return features == null ? false : containsFeature(feature); + return containsPositionalFeature(feature); + } + private boolean containsPositionalFeature(SequenceFeature feature) + { + return features == null || feature.begin > lastStart ? false + : features.contains(feature); + } + + /** + * Answers true if this store already contains a contact feature equal to the + * given feature (by {@code SequenceFeature.equals()} test), else false + * + * @param feature + * @return + */ + private boolean containsContactFeature(SequenceFeature feature) + { + return contactFeatureStarts != null && feature.begin <= lastContactStart + && listContains(contactFeatureStarts, feature); + } - abstract protected boolean containsFeature(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); + } /** * Deletes the given feature from the store, returning true if it was found @@ -391,8 +475,6 @@ public abstract class FeatureStore implements FeatureStoreI * * @param sf */ - - @Override public synchronized boolean delete(SequenceFeature sf) { boolean removed = false; @@ -423,7 +505,7 @@ public abstract class FeatureStore implements FeatureStoreI */ if (!removed && features != null) { - removed = findAndRemoveNonContactFeature(sf); + removed = features.remove(sf); } if (removed) @@ -434,23 +516,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<>()); @@ -462,8 +532,6 @@ public abstract class FeatureStore implements FeatureStoreI * * @return */ - - @Override public List getContactFeatures( List result) { @@ -481,8 +549,6 @@ public abstract class FeatureStore implements FeatureStoreI * @param positional * @return */ - - @Override public int getFeatureCount(boolean positional) { if (!positional) @@ -493,7 +559,6 @@ public abstract class FeatureStore implements FeatureStoreI return (contactFeatureStarts == null ? 0 : contactFeatureStarts.size()) + features.size(); - } /** @@ -504,8 +569,6 @@ public abstract class FeatureStore implements FeatureStoreI * @param positionalFeatures * @return */ - - @Override public Set getFeatureGroups(boolean positionalFeatures) { if (positionalFeatures) @@ -520,7 +583,6 @@ public abstract class FeatureStore implements FeatureStoreI } } - @Override public Collection getFeatures() { return features; @@ -534,8 +596,6 @@ public abstract class FeatureStore implements FeatureStoreI * @param group * @return */ - - @Override public List getFeaturesForGroup(boolean positional, String group) { @@ -571,8 +631,6 @@ public abstract class FeatureStore implements FeatureStoreI * @param positional * @return */ - - @Override public float getMaximumScore(boolean positional) { return positional ? positionalMaxScore : nonPositionalMaxScore; @@ -586,14 +644,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<>()); @@ -605,8 +660,6 @@ public abstract class FeatureStore implements FeatureStoreI * * @return */ - - @Override public List getNonPositionalFeatures( List result) { @@ -617,7 +670,6 @@ public abstract class FeatureStore implements FeatureStoreI return result; } - @Override public List getPositionalFeatures() { return getPositionalFeatures(new ArrayList<>()); @@ -628,8 +680,6 @@ public abstract class FeatureStore implements FeatureStoreI * * @return */ - - @Override public List getPositionalFeatures( List result) { @@ -659,8 +709,6 @@ public abstract class FeatureStore implements FeatureStoreI * * @return */ - - @Override public int getTotalFeatureLength() { return totalExtent; @@ -671,8 +719,6 @@ public abstract class FeatureStore implements FeatureStoreI * * @return */ - - @Override public boolean isEmpty() { boolean hasFeatures = (contactFeatureStarts != null @@ -747,8 +793,6 @@ public abstract class FeatureStore implements FeatureStoreI * @param shiftBy * @return */ - - @Override public synchronized boolean shiftFeatures(int fromPosition, int shiftBy) { /* @@ -783,4 +827,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; + } + }