X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=src%2Fjalview%2Fdatamodel%2Ffeatures%2FFeatureStore.java;h=eb5688c6b9ef303e19b3344b73ae858c1b7e55ef;hb=57738a1f3c19b1c3a00bd3ac5108f8cd0af32f99;hp=7218b380cc4d07a36ff2d79650974fb341e292e9;hpb=b44349fe3a5f2d70b74a1b110018a753a1036aca;p=jalview.git diff --git a/src/jalview/datamodel/features/FeatureStore.java b/src/jalview/datamodel/features/FeatureStore.java index 7218b38..eb5688c 100644 --- a/src/jalview/datamodel/features/FeatureStore.java +++ b/src/jalview/datamodel/features/FeatureStore.java @@ -1,14 +1,37 @@ +/* + * 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.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.BinarySearcher.Compare; +import intervalstore.impl.IntervalStore; +import jalview.datamodel.SequenceFeature; + /** * 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 @@ -19,59 +42,6 @@ import java.util.Set; */ public class FeatureStore { - /** - * a class providing criteria for performing a binary search of a list - */ - abstract static class SearchCriterion - { - /** - * Answers true if the entry passes the search criterion test - * - * @param entry - * @return - */ - abstract boolean compare(SequenceFeature entry); - - static SearchCriterion byStart(final long target) - { - return new SearchCriterion() { - - @Override - boolean compare(SequenceFeature entry) - { - return entry.getBegin() >= target; - } - }; - } - - static SearchCriterion byEnd(final long target) - { - return new SearchCriterion() - { - - @Override - boolean compare(SequenceFeature entry) - { - return entry.getEnd() >= target; - } - }; - } - - static SearchCriterion byFeature(final ContiguousI to, - final Comparator rc) - { - return new SearchCriterion() - { - - @Override - boolean compare(SequenceFeature entry) - { - return rc.compare(entry, to) >= 0; - } - }; - } - } - /* * Non-positional features have no (zero) start/end position. * Kept as a separate list in case this criterion changes in future. @@ -79,14 +49,6 @@ public class FeatureStore List nonPositionalFeatures; /* - * An ordered list of features, with the promise that no feature in the list - * properly contains any other. This constraint allows bounded linear search - * of the list for features overlapping a region. - * Contact features are not included in this list. - */ - List nonNestedFeatures; - - /* * contact features ordered by first contact position */ List contactFeatureStarts; @@ -97,13 +59,10 @@ public class FeatureStore List contactFeatureEnds; /* - * Nested Containment List is used to hold any features that are nested - * within (properly contained by) any other feature. This is a recursive tree - * which supports depth-first scan for features overlapping a range. - * It is used here as a 'catch-all' fallback for features that cannot be put - * into a simple ordered list without invalidating the search methods. + * IntervalStore holds remaining features and provides efficient + * query for features overlapping any given interval */ - NCList nestedFeatures; + IntervalStoreI features; /* * Feature groups represented in stored positional features @@ -136,16 +95,15 @@ public class FeatureStore */ public FeatureStore() { - nonNestedFeatures = new ArrayList(); - positionalFeatureGroups = new HashSet(); - nonPositionalFeatureGroups = new HashSet(); + features = new IntervalStore<>(); + positionalFeatureGroups = new HashSet<>(); + nonPositionalFeatureGroups = new HashSet<>(); positionalMinScore = Float.NaN; positionalMaxScore = Float.NaN; nonPositionalMinScore = Float.NaN; nonPositionalMaxScore = Float.NaN; - // we only construct nonPositionalFeatures, contactFeatures - // or the NCList if we need to + // we only construct nonPositionalFeatures, contactFeatures if we need to } /** @@ -158,6 +116,11 @@ public class FeatureStore */ public boolean addFeature(SequenceFeature feature) { + if (contains(feature)) + { + return false; + } + /* * keep a record of feature groups */ @@ -166,61 +129,70 @@ public class FeatureStore positionalFeatureGroups.add(feature.getFeatureGroup()); } - boolean added = false; - if (feature.isContactFeature()) { - added = addContactFeature(feature); + addContactFeature(feature); } else if (feature.isNonPositional()) { - added = addNonPositionalFeature(feature); + addNonPositionalFeature(feature); } else { - if (!contains(nonNestedFeatures, feature)) + addNestedFeature(feature); + } + + /* + * record the total extent of positional features, to make + * getTotalFeatureLength possible; we count the length of a + * contact feature as 1 + */ + totalExtent += getFeatureLength(feature); + + /* + * record the minimum and maximum score for positional + * and non-positional features + */ + float score = feature.getScore(); + if (!Float.isNaN(score)) + { + if (feature.isNonPositional()) { - added = addNonNestedFeature(feature); - if (!added) - { - /* - * detected a nested feature - put it in the NCList structure - */ - added = addNestedFeature(feature); - } + nonPositionalMinScore = min(nonPositionalMinScore, score); + nonPositionalMaxScore = max(nonPositionalMaxScore, score); + } + else + { + positionalMinScore = min(positionalMinScore, score); + positionalMaxScore = max(positionalMaxScore, score); } } - if (added) + return true; + } + + /** + * Answers true if this store contains the given feature (testing by + * SequenceFeature.equals), else false + * + * @param feature + * @return + */ + public boolean contains(SequenceFeature feature) + { + if (feature.isNonPositional()) { - /* - * record the total extent of positional features, to make - * getTotalFeatureLength possible; we count the length of a - * contact feature as 1 - */ - totalExtent += getFeatureLength(feature); + return nonPositionalFeatures == null ? false + : nonPositionalFeatures.contains(feature); + } - /* - * record the minimum and maximum score for positional - * and non-positional features - */ - float score = feature.getScore(); - if (!Float.isNaN(score)) - { - if (feature.isNonPositional()) - { - nonPositionalMinScore = min(nonPositionalMinScore, score); - nonPositionalMaxScore = max(nonPositionalMaxScore, score); - } - else - { - positionalMinScore = min(positionalMinScore, score); - positionalMaxScore = max(positionalMaxScore, score); - } - } + if (feature.isContactFeature()) + { + return contactFeatureStarts == null ? false + : listContains(contactFeatureStarts, feature); } - return added; + return features == null ? false : features.contains(feature); } /** @@ -245,10 +217,10 @@ public class FeatureStore /** * Adds the feature to the list of non-positional features (with lazy - * instantiation of the list if it is null), and returns true. If the - * non-positional features already include the new feature (by equality test), - * then it is not added, and this method returns false. The feature group is - * added to the set of distinct feature groups for non-positional features. + * 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 + * features. This method allows duplicate features, so test before calling to + * prevent this. * * @param feature */ @@ -256,11 +228,7 @@ public class FeatureStore { if (nonPositionalFeatures == null) { - nonPositionalFeatures = new ArrayList(); - } - if (nonPositionalFeatures.contains(feature)) - { - return false; + nonPositionalFeatures = new ArrayList<>(); } nonPositionalFeatures.add(feature); @@ -271,98 +239,23 @@ public class FeatureStore } /** - * Adds one feature to the NCList that can manage nested features (creating - * the NCList if necessary), and returns true. If the feature is already - * stored in the NCList (by equality test), then it is not added, and this - * method returns false. - */ - protected synchronized boolean addNestedFeature(SequenceFeature feature) - { - if (nestedFeatures == null) - { - nestedFeatures = new NCList(feature); - return true; - } - return nestedFeatures.add(feature, false); - } - - /** - * Add a feature to the list of non-nested features, maintaining the ordering - * of the list. A check is made for whether the feature is nested in (properly - * contained by) an existing feature. If there is no nesting, the feature is - * added to the list and the method returns true. If nesting is found, the - * feature is not added and the method returns false. - * - * @param feature - * @return - */ - protected boolean addNonNestedFeature(SequenceFeature feature) - { - synchronized (nonNestedFeatures) - { - /* - * find the first stored feature which doesn't precede the new one - */ - int insertPosition = binarySearch(nonNestedFeatures, - SearchCriterion.byFeature(feature, RangeComparator.BY_START_POSITION)); - - /* - * fail if we detect feature enclosure - of the new feature by - * the one preceding it, or of the next feature by the new one - */ - if (insertPosition > 0) - { - if (encloses(nonNestedFeatures.get(insertPosition - 1), feature)) - { - return false; - } - } - if (insertPosition < nonNestedFeatures.size()) - { - if (encloses(feature, nonNestedFeatures.get(insertPosition))) - { - return false; - } - } - - /* - * checks passed - add the feature - */ - nonNestedFeatures.add(insertPosition, feature); - - return true; - } - } - - /** - * Answers true if range1 properly encloses range2, else false - * - * @param range1 - * @param range2 - * @return + * Adds one feature to the IntervalStore that can manage nested features + * (creating the IntervalStore if necessary) */ - protected boolean encloses(ContiguousI range1, ContiguousI range2) + protected synchronized void addNestedFeature(SequenceFeature feature) { - int begin1 = range1.getBegin(); - int begin2 = range2.getBegin(); - int end1 = range1.getEnd(); - int end2 = range2.getEnd(); - if (begin1 == begin2 && end1 > end2) - { - return true; - } - if (begin1 < begin2 && end1 >= end2) + if (features == null) { - return true; + features = new IntervalStore<>(); } - return false; + features.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 - * ordered, and returns true. If the contact feature lists already contain the - * given feature (by test for equality), does not add it and returns false. + * ordered, and returns true. This method allows duplicate features to be + * added, so test before calling to avoid this. * * @param feature * @return @@ -371,33 +264,28 @@ public class FeatureStore { if (contactFeatureStarts == null) { - contactFeatureStarts = new ArrayList(); + contactFeatureStarts = new ArrayList<>(); } if (contactFeatureEnds == null) { - contactFeatureEnds = new ArrayList(); - } - - if (contains(contactFeatureStarts, feature)) - { - return false; + contactFeatureEnds = new ArrayList<>(); } /* + * insert into list sorted by start (first contact position): * binary search the sorted list to find the insertion point */ - int insertPosition = binarySearch(contactFeatureStarts, - SearchCriterion.byFeature(feature, - RangeComparator.BY_START_POSITION)); + int insertPosition = BinarySearcher.findFirst(contactFeatureStarts, + true, Compare.GE, feature.getBegin()); contactFeatureStarts.add(insertPosition, feature); - // and resort to mak siccar...just in case insertion point not quite right - Collections.sort(contactFeatureStarts, RangeComparator.BY_START_POSITION); - insertPosition = binarySearch(contactFeatureStarts, - SearchCriterion.byFeature(feature, - RangeComparator.BY_END_POSITION)); - contactFeatureEnds.add(feature); - Collections.sort(contactFeatureEnds, RangeComparator.BY_END_POSITION); + /* + * insert into list sorted by end (second contact position): + * binary search the sorted list to find the insertion point + */ + insertPosition = BinarySearcher.findFirst(contactFeatureEnds, false, + Compare.GE, feature.getEnd()); + contactFeatureEnds.add(insertPosition, feature); return true; } @@ -411,7 +299,7 @@ public class FeatureStore * @param feature * @return */ - protected static boolean contains(List features, + protected static boolean listContains(List features, SequenceFeature feature) { if (features == null || feature == null) @@ -422,8 +310,10 @@ public class FeatureStore /* * locate the first entry in the list which does not precede the feature */ - int pos = binarySearch(features, - SearchCriterion.byFeature(feature, RangeComparator.BY_START_POSITION)); + // int pos = binarySearch(features, + // SearchCriterion.byFeature(feature, RangeComparator.BY_START_POSITION)); + int pos = BinarySearcher.findFirst(features, true, Compare.GE, + feature.getBegin()); int len = features.size(); while (pos < len) { @@ -454,15 +344,13 @@ public class FeatureStore */ public List findOverlappingFeatures(long start, long end) { - List result = new ArrayList(); - - findNonNestedFeatures(start, end, result); + List result = new ArrayList<>(); findContactFeatures(start, end, result); - if (nestedFeatures != null) + if (features != null) { - result.addAll(nestedFeatures.findOverlaps(start, end)); + result.addAll(features.findOverlaps(start, end)); } return result; @@ -481,11 +369,11 @@ public class FeatureStore { if (contactFeatureStarts != null) { - findContactStartFeatures(from, to, result); + findContactStartOverlaps(from, to, result); } if (contactFeatureEnds != null) { - findContactEndFeatures(from, to, result); + findContactEndOverlaps(from, to, result); } } @@ -498,22 +386,24 @@ public class FeatureStore * @param to * @param result */ - protected void findContactEndFeatures(long from, long to, + protected void findContactEndOverlaps(long from, long to, List result) { /* - * find the first contact feature (if any) that does not lie - * entirely before the target range + * find the first contact feature (if any) + * whose end point is not before the target range */ - int startPosition = binarySearch(contactFeatureEnds, - SearchCriterion.byEnd(from)); - for (; startPosition < contactFeatureEnds.size(); startPosition++) + int index = BinarySearcher.findFirst(contactFeatureEnds, false, + Compare.GE, (int) from); + + while (index < contactFeatureEnds.size()) { - SequenceFeature sf = contactFeatureEnds.get(startPosition); + SequenceFeature sf = contactFeatureEnds.get(index); if (!sf.isContactFeature()) { - System.err.println("Error! non-contact feature type " - + sf.getType() + " in contact features list"); + System.err.println("Error! non-contact feature type " + sf.getType() + + " in contact features list"); + index++; continue; } @@ -524,71 +414,25 @@ public class FeatureStore * this feature's first contact position lies in the search range * so we don't include it in results a second time */ + index++; continue; } - int end = sf.getEnd(); - if (end >= from && end <= to) - { - result.add(sf); - } - if (end > to) + if (sf.getEnd() > to) { + /* + * this feature (and all following) has end point after the target range + */ break; } - } - } - /** - * Adds non-nested features to the result list that lie within the target - * range. Non-positional features (start=end=0), contact features and nested - * features are excluded. - * - * @param from - * @param to - * @param result - */ - protected void findNonNestedFeatures(long from, long to, - List result) - { - int startIndex = binarySearch(nonNestedFeatures, - SearchCriterion.byEnd(from)); - - findNonNestedFeatures(startIndex, from, to, result); - } - - /** - * Scans the list of non-nested features, starting from startIndex, to find - * those that overlap the from-to range, and adds them to the result list. - * Returns the index of the first feature whose start position is after the - * target range (or the length of the whole list if none such feature exists). - * - * @param startIndex - * @param from - * @param to - * @param result - * @return - */ - protected int findNonNestedFeatures(final int startIndex, long from, - long to, List result) - { - int i = startIndex; - while (i < nonNestedFeatures.size()) - { - SequenceFeature sf = nonNestedFeatures.get(i); - if (sf.getBegin() > to) - { - break; - } - int start = sf.getBegin(); - int end = sf.getEnd(); - if (start <= to && end >= from) - { - result.add(sf); - } - i++; + /* + * feature has end >= from and end <= to + * i.e. contact end point lies within overlap search range + */ + result.add(sf); + index++; } - return i; } /** @@ -599,26 +443,36 @@ public class FeatureStore * @param to * @param result */ - protected void findContactStartFeatures(long from, long to, + protected void findContactStartOverlaps(long from, long to, List result) { - int startPosition = binarySearch(contactFeatureStarts, - SearchCriterion.byStart(from)); + int index = BinarySearcher.findFirst(contactFeatureStarts, true, + Compare.GE, (int) from); - for (; startPosition < contactFeatureStarts.size(); startPosition++) + while (index < contactFeatureStarts.size()) { - SequenceFeature sf = contactFeatureStarts.get(startPosition); + SequenceFeature sf = contactFeatureStarts.get(index); if (!sf.isContactFeature()) { - System.err.println("Error! non-contact feature type " - + sf.getType() + " in contact features list"); + System.err.println("Error! non-contact feature " + sf.toString() + + " in contact features list"); + index++; continue; } - int begin = sf.getBegin(); - if (begin >= from && begin <= to) + if (sf.getBegin() > to) { - result.add(sf); + /* + * this feature's start (and all following) follows the target range + */ + break; } + + /* + * feature has begin >= from and begin <= to + * i.e. contact start point lies within overlap search range + */ + result.add(sf); + index++; } } @@ -629,11 +483,7 @@ public class FeatureStore */ public List getPositionalFeatures() { - /* - * add non-nested features (may be all features for many cases) - */ - List result = new ArrayList(); - result.addAll(nonNestedFeatures); + List result = new ArrayList<>(); /* * add any contact features - from the list by start position @@ -646,9 +496,9 @@ public class FeatureStore /* * add any nested features */ - if (nestedFeatures != null) + if (features != null) { - result.addAll(nestedFeatures.getEntries()); + result.addAll(features); } return result; @@ -666,7 +516,7 @@ public class FeatureStore { return Collections.emptyList(); } - return new ArrayList(contactFeatureStarts); + return new ArrayList<>(contactFeatureStarts); } /** @@ -681,7 +531,7 @@ public class FeatureStore { return Collections.emptyList(); } - return new ArrayList(nonPositionalFeatures); + return new ArrayList<>(nonPositionalFeatures); } /** @@ -694,13 +544,10 @@ public class FeatureStore */ public synchronized boolean delete(SequenceFeature sf) { - /* - * try the non-nested positional features first - */ - boolean removed = nonNestedFeatures.remove(sf); + boolean removed = false; /* - * if not found, try contact positions (and if found, delete + * try contact positions (and if found, delete * from both lists of contact positions) */ if (!removed && contactFeatureStarts != null) @@ -726,9 +573,9 @@ public class FeatureStore /* * if not found, try nested features */ - if (!removed && nestedFeatures != null) + if (!removed && features != null) { - removed = nestedFeatures.delete(sf); + removed = features.remove(sf); } if (removed) @@ -819,39 +666,17 @@ public class FeatureStore } /** - * Scans all positional features to check whether the given feature group is - * found, and returns true if found, else false - * - * @param featureGroup - * @return - */ - protected boolean findFeatureGroup(String featureGroup) - { - for (SequenceFeature sf : getPositionalFeatures()) - { - String group = sf.getFeatureGroup(); - if (group == featureGroup - || (group != null && group.equals(featureGroup))) - { - return true; - } - } - return false; - } - - /** * Answers true if this store has no features, else false * * @return */ public boolean isEmpty() { - boolean hasFeatures = !nonNestedFeatures.isEmpty() - || (contactFeatureStarts != null && !contactFeatureStarts - .isEmpty()) - || (nonPositionalFeatures != null && !nonPositionalFeatures - .isEmpty()) - || (nestedFeatures != null && nestedFeatures.size() > 0); + boolean hasFeatures = (contactFeatureStarts != null + && !contactFeatureStarts.isEmpty()) + || (nonPositionalFeatures != null + && !nonPositionalFeatures.isEmpty()) + || (features != null && features.size() > 0); return !hasFeatures; } @@ -872,48 +697,13 @@ public class FeatureStore } else { - return nonPositionalFeatureGroups == null ? Collections - . emptySet() : Collections - .unmodifiableSet(nonPositionalFeatureGroups); + return nonPositionalFeatureGroups == null + ? Collections. emptySet() + : Collections.unmodifiableSet(nonPositionalFeatureGroups); } } /** - * Performs a binary search of the (sorted) list to find the index of the - * first entry which returns true for the given comparator function. Returns - * the length of the list if there is no such entry. - * - * @param features - * @param sc - * @return - */ - protected static int binarySearch(List features, - SearchCriterion sc) - { - int start = 0; - int end = features.size() - 1; - int matched = features.size(); - - while (start <= end) - { - int mid = (start + end) / 2; - SequenceFeature entry = features.get(mid); - boolean compare = sc.compare(entry); - if (compare) - { - matched = mid; - end = mid - 1; - } - else - { - start = mid + 1; - } - } - - return matched; - } - - /** * Answers the number of positional (or non-positional) features stored. * Contact features count as 1. * @@ -924,11 +714,11 @@ public class FeatureStore { if (!positional) { - return nonPositionalFeatures == null ? 0 : nonPositionalFeatures - .size(); + return nonPositionalFeatures == null ? 0 + : nonPositionalFeatures.size(); } - int size = nonNestedFeatures.size(); + int size = 0; if (contactFeatureStarts != null) { @@ -936,9 +726,9 @@ public class FeatureStore size += contactFeatureStarts.size(); } - if (nestedFeatures != null) + if (features != null) { - size += nestedFeatures.size(); + size += features.size(); } return size; @@ -992,7 +782,7 @@ public class FeatureStore public List getFeaturesForGroup(boolean positional, String group) { - List result = new ArrayList(); + List result = new ArrayList<>(); /* * if we know features don't include the target group, no need @@ -1009,8 +799,8 @@ public class FeatureStore for (SequenceFeature sf : sfs) { String featureGroup = sf.getFeatureGroup(); - if (group == null && featureGroup == null || group != null - && group.equals(featureGroup)) + if (group == null && featureGroup == null + || group != null && group.equals(featureGroup)) { result.add(sf); } @@ -1019,13 +809,15 @@ public class FeatureStore } /** - * Adds the shift value to the start and end of all positional features. - * Returns true if at least one feature was updated, else false. + * Adds the shift amount to the start and end of all positional features whose + * start position is at or after fromPosition. Returns true if at least one + * feature was shifted, else false. * - * @param shift + * @param fromPosition + * @param shiftBy * @return */ - public synchronized boolean shiftFeatures(int shift) + public synchronized boolean shiftFeatures(int fromPosition, int shiftBy) { /* * Because begin and end are final fields (to ensure the data store's @@ -1035,21 +827,24 @@ public class FeatureStore boolean modified = false; for (SequenceFeature sf : getPositionalFeatures()) { - modified = true; - int newBegin = sf.getBegin() + shift; - int newEnd = sf.getEnd() + shift; - - /* - * sanity check: don't shift left of the first residue - */ - if (newEnd > 0) + if (sf.getBegin() >= fromPosition) { - newBegin = Math.max(1, newBegin); - SequenceFeature sf2 = new SequenceFeature(sf, newBegin, newEnd, - sf.getFeatureGroup()); - addFeature(sf2); + modified = true; + int newBegin = sf.getBegin() + shiftBy; + int newEnd = sf.getEnd() + shiftBy; + + /* + * sanity check: don't shift left of the first residue + */ + if (newEnd > 0) + { + newBegin = Math.max(1, newBegin); + SequenceFeature sf2 = new SequenceFeature(sf, newBegin, newEnd, + sf.getFeatureGroup(), sf.getScore()); + addFeature(sf2); + } + delete(sf); } - delete(sf); } return modified; }