X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=src%2Fjalview%2Fdatamodel%2Ffeatures%2FFeatureStore.java;h=e60aec5c3d22a6fd3acaabfdfa22a80d6152e6ca;hb=67e1902bea1290962c53ba11affe3ad52c199608;hp=13472139cb1534d5f7515f44014db3ff4aaf7b68;hpb=81d2ea57ab71c0806a036833f73711bc4ad5c76d;p=jalview.git diff --git a/src/jalview/datamodel/features/FeatureStore.java b/src/jalview/datamodel/features/FeatureStore.java index 1347213..e60aec5 100644 --- a/src/jalview/datamodel/features/FeatureStore.java +++ b/src/jalview/datamodel/features/FeatureStore.java @@ -23,7 +23,9 @@ package jalview.datamodel.features; import jalview.datamodel.SequenceFeature; import java.util.ArrayList; +import java.util.Arrays; import java.util.Collections; +import java.util.Comparator; import java.util.HashSet; import java.util.List; import java.util.Set; @@ -90,12 +92,15 @@ 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; @@ -114,6 +119,7 @@ public class FeatureStore * * @param feature */ + public boolean addFeature(SequenceFeature feature) { if (contains(feature)) @@ -182,18 +188,17 @@ public class FeatureStore { if (feature.isNonPositional()) { - return nonPositionalFeatures == null ? false : nonPositionalFeatures - .contains(feature); + return nonPositionalFeatures == null ? false + : nonPositionalFeatures.contains(feature); } if (feature.isContactFeature()) { - return contactFeatureStarts == null ? false : listContains( - contactFeatureStarts, feature); + return contactFeatureStarts == null ? false + : listContains(contactFeatureStarts, feature); } - return features == null ? false : features - .contains(feature); + return features == null ? false : features.contains(feature); } /** @@ -250,6 +255,7 @@ public class FeatureStore features = new IntervalStore<>(); } features.add(feature); + featuresList.add(feature); } /** @@ -280,7 +286,6 @@ public class FeatureStore f -> f.getBegin() >= feature.getBegin()); contactFeatureStarts.add(insertPosition, feature); - /* * insert into list sorted by end (second contact position): * binary search the sorted list to find the insertion point @@ -344,6 +349,7 @@ public class FeatureStore * end position of overlap range (inclusive) * @return */ + public List findOverlappingFeatures(long start, long end) { List result = new ArrayList<>(); @@ -403,8 +409,8 @@ public class FeatureStore 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; } @@ -483,6 +489,7 @@ public class FeatureStore * * @return */ + public List getPositionalFeatures() { List result = new ArrayList<>(); @@ -512,6 +519,7 @@ public class FeatureStore * * @return */ + public List getContactFeatures() { if (contactFeatureStarts == null) @@ -527,6 +535,7 @@ public class FeatureStore * * @return */ + public List getNonPositionalFeatures() { if (nonPositionalFeatures == null) @@ -544,6 +553,7 @@ public class FeatureStore * * @param sf */ + public synchronized boolean delete(SequenceFeature sf) { boolean removed = false; @@ -578,6 +588,7 @@ public class FeatureStore if (!removed && features != null) { removed = features.remove(sf); + featuresList.remove(sf); } if (removed) @@ -602,7 +613,6 @@ public class FeatureStore positionalMaxScore = Float.NaN; nonPositionalMinScore = Float.NaN; nonPositionalMaxScore = Float.NaN; - /* * scan non-positional features for groups and scores */ @@ -672,13 +682,13 @@ public class FeatureStore * * @return */ + public boolean isEmpty() { boolean hasFeatures = (contactFeatureStarts != null - && !contactFeatureStarts - .isEmpty()) - || (nonPositionalFeatures != null && !nonPositionalFeatures - .isEmpty()) + && !contactFeatureStarts.isEmpty()) + || (nonPositionalFeatures != null + && !nonPositionalFeatures.isEmpty()) || (features != null && features.size() > 0); return !hasFeatures; @@ -692,6 +702,7 @@ public class FeatureStore * @param positionalFeatures * @return */ + public Set getFeatureGroups(boolean positionalFeatures) { if (positionalFeatures) @@ -700,9 +711,9 @@ public class FeatureStore } else { - return nonPositionalFeatureGroups == null ? Collections - . emptySet() : Collections - .unmodifiableSet(nonPositionalFeatureGroups); + return nonPositionalFeatureGroups == null + ? Collections. emptySet() + : Collections.unmodifiableSet(nonPositionalFeatureGroups); } } @@ -713,12 +724,13 @@ public class FeatureStore * @param positional * @return */ + public int getFeatureCount(boolean positional) { if (!positional) { - return nonPositionalFeatures == null ? 0 : nonPositionalFeatures - .size(); + return nonPositionalFeatures == null ? 0 + : nonPositionalFeatures.size(); } int size = 0; @@ -743,6 +755,7 @@ public class FeatureStore * * @return */ + public int getTotalFeatureLength() { return totalExtent; @@ -756,6 +769,7 @@ public class FeatureStore * @param positional * @return */ + public float getMinimumScore(boolean positional) { return positional ? positionalMinScore : nonPositionalMinScore; @@ -769,6 +783,7 @@ public class FeatureStore * @param positional * @return */ + public float getMaximumScore(boolean positional) { return positional ? positionalMaxScore : nonPositionalMaxScore; @@ -782,6 +797,7 @@ public class FeatureStore * @param group * @return */ + public List getFeaturesForGroup(boolean positional, String group) { @@ -802,8 +818,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); } @@ -812,13 +828,16 @@ 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 @@ -828,22 +847,316 @@ 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(), sf.getScore()); - 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; } + + /////////////////////// 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); + } + + } + + /** + * + * @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 ithis = intervals[i]; + if (ithis.begin <= maxEnd) + { + ithis.containedBy = getContainedBy(intervals[i - 1], ithis); + } + if (ithis.end > maxEnd) + { + maxEnd = ithis.end; + } + } + } + + /** + * Since we are traversing the sorted feature array, 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; + } + + // Searching for overlapping features at a given position: + + /** + * 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) + { + 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(List features, int pos, + List result) + { + 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; + } + } + + /** + * Quick check when we only have one feature. + * + * @param sf + * @param pos + * @param result + */ + private void checkOne(SequenceFeature sf, int pos, + List result) + { + if (sf.begin <= pos && sf.end >= pos) + { + result.add(sf); + } + return; + } + + /** + * A binary search identical to the one used for contact start/end, but here + * we return the feature itself. + * + * @param l + * @param pos + * @return + */ + private SequenceFeature findClosestFeature(SequenceFeature[] l, int 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) + { + ; + } + mid--; + return l[mid]; + } + } + // -1 here? + return (high < 0 || low >= l.length ? null : l[high]); + } + + }