+ // 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:
+