- /////////////////////// 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<SequenceFeature> findOverlappingFeatures(int pos,
- List<SequenceFeature> 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<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.
- *
- * @param l
- * @param pos
- * @param result
- * @param isStart
- *
- * @author Bob Hanson 2019.07.30
- */
- private static void findContacts(List<SequenceFeature> l, int pos,
- List<SequenceFeature> 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<SequenceFeature> features, int pos,
- List<SequenceFeature> 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<SequenceFeature> 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]);
- }
-
-