From 67e1902bea1290962c53ba11affe3ad52c199608 Mon Sep 17 00:00:00 2001 From: hansonr Date: Fri, 2 Aug 2019 23:57:55 -0500 Subject: [PATCH] adds comments JAL-3383 --- src/jalview/datamodel/features/FeatureStore.java | 267 +++++++++++++--------- 1 file changed, 156 insertions(+), 111 deletions(-) diff --git a/src/jalview/datamodel/features/FeatureStore.java b/src/jalview/datamodel/features/FeatureStore.java index bd6bd1e..e60aec5 100644 --- a/src/jalview/datamodel/features/FeatureStore.java +++ b/src/jalview/datamodel/features/FeatureStore.java @@ -24,7 +24,6 @@ import jalview.datamodel.SequenceFeature; import java.util.ArrayList; import java.util.Arrays; -import java.util.BitSet; import java.util.Collections; import java.util.Comparator; import java.util.HashSet; @@ -35,7 +34,6 @@ 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 @@ -871,6 +869,31 @@ 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. * @@ -899,6 +922,103 @@ public class FeatureStore 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. * @@ -945,11 +1065,9 @@ public class FeatureStore } } - BitSet bs = new BitSet(); - /** - * Double binary sort with bitset correlation - * + * 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 @@ -968,8 +1086,15 @@ public class FeatureStore { rebuildArrays(n); } + + // (1) Find the closest feature to this position. + SequenceFeature sf = findClosestFeature(orderedFeatureStarts, pos); - while (sf != null) { + + // (2) Traverse the containedBy field, checking for overlap. + + while (sf != null) + { if (sf.end >= pos) { result.add(sf); @@ -978,44 +1103,31 @@ public class FeatureStore } } - 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; - } - } - } - - private SequenceFeature getContainedBy(SequenceFeature sf, - SequenceFeature sf0) + /** + * Quick check when we only have one feature. + * + * @param sf + * @param pos + * @param result + */ + private void checkOne(SequenceFeature sf, int pos, + List result) { - int begin = sf0.begin; - while (sf != null) + if (sf.begin <= pos && sf.end >= pos) { - if (begin <= sf.end) - { - System.out.println("\nFS found " + sf0.index + ":" + sf0 - + "\nFS in " + sf.index + ":" + sf); - return sf; - } - sf = sf.containedBy; + result.add(sf); } - return null; + 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; @@ -1035,10 +1147,10 @@ public class FeatureStore case 0: while (++mid <= high && l[mid].begin == pos) - { - ; - } - mid--; + { + ; + } + mid--; return l[mid]; } } @@ -1046,72 +1158,5 @@ public class FeatureStore return (high < 0 || low >= l.length ? null : l[high]); } - private void checkOne(SequenceFeature sf, int pos, - List result) - { - if (sf.begin <= pos && sf.end >= pos) - { - result.add(sf); - } - return; - } - - /* - * 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; - orderedFeatureStarts[i] = sf; - } - Arrays.sort(orderedFeatureStarts, startComp); - linkFeatures(orderedFeatureStarts); - } - - class StartComparator implements Comparator - { - - int pos; - - @Override - public int compare(SequenceFeature o1, SequenceFeature o2) - { - int p1 = o1.begin; - int p2 = o2.begin; - return (p1 < p2 ? -1 : p1 > p2 ? 1 : 0); - } - - } - - static StartComparator startComp; - - // class EndComparator implements Comparator - // { - // - // int pos; - // - // @Override - // public int compare(SequenceFeature o1, SequenceFeature o2) - // { - // int p1 = o1.end; - // int p2 = o2.end; - // int val = (p1 < p2 ? 1 : p1 > p2 ? -1 : 0); - // return val; - // } - // - // } - // - // static EndComparator endComp; } -- 1.7.10.2