import java.util.ArrayList;
import java.util.Arrays;
-import java.util.BitSet;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
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
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.
*
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<SequenceFeature>
+ {
+
+ @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.
*
}
}
- 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
{
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);
}
}
- 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<SequenceFeature> 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;
case 0:
while (++mid <= high && l[mid].begin == pos)
- {
- ;
- }
- mid--;
+ {
+ ;
+ }
+ mid--;
return l[mid];
}
}
return (high < 0 || low >= l.length ? null : l[high]);
}
- private void checkOne(SequenceFeature sf, int pos,
- List<SequenceFeature> 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<SequenceFeature>
- {
-
- 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<SequenceFeature>
- // {
- //
- // 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;
}
git://source.jalview.org / jalview.git / commitdiff