-
- /**
- * Since we are traversing the sorted feature array in a forward direction,
- * 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("\nFSJS found " + sf0 + "\nFS in " + sf);
- return sf;
- }
- sf = sf.containedBy;
- }
- return null;
- }
-
- /**
- * Fast find of known features already on the list; slower removal of
- * equivalent feature, not necessarily identical.
- *
- * @param feature
- * @return 0-based index for this feature in featureList
- */
- @Override
- protected int getEquivalentFeatureIndex(List<SequenceFeature> list,
- SequenceFeature feature)
- {
- int pos = feature.index1 - 1;
- if (!isTainted && pos >= 0)
- {
- return pos;
- }
- return super.getEquivalentFeatureIndex(list, feature);
- }
-
- /**
- * Find all overlaps; special case when there is only one feature. The
- * required array of start-sorted SequenceFeature is created lazily.
- *
- * @param start
- * @param end
- * @param result
- */
- private void getOverlaps(long start, long end,
- List<SequenceFeature> result)
- {
- int n = featureList.size();
- switch (n)
- {
- case 0:
- return;
- case 1:
- justCheckOne(featureList.get(0), start, end, result);
- return;
- default:
- if (isTainted)
- {
- orderedFeatureStarts = featureList
- .toArray(new SequenceFeature[featureList.size()]);
- linkFeatures(orderedFeatureStarts);
- isTainted = false;
- }
- break;
- }
-
- // (1) Find the closest feature to this position.
-
- int index = getClosestFeature(orderedFeatureStarts, start);
- SequenceFeature sf = (index < 0 ? null : orderedFeatureStarts[index]);
-
- // (2) Traverse the containedBy field, checking for overlap.
-
- while (sf != null)
- {
- if (sf.end >= start)
- {
- result.add(sf);
- }
- sf = sf.containedBy;
- }
-
- // (3) For an interval, find the last feature that starts in this interval,
- // and add all features up through that feature.
-
- if (end > start)
- {
- // fill in with all features that start within this interval, fully
- // inclusive
- int index2 = getClosestFeature(orderedFeatureStarts, end);
- while (++index <= index2)
- {
- result.add(orderedFeatureStarts[index]);
- }
-
- }
- }
-
- /**
- * Quick check when we only have one feature.
- *
- * @param sf
- * @param start
- * @param end
- * @param result
- */
- private void justCheckOne(SequenceFeature sf, long start, long end,
- List<SequenceFeature> result)
- {
- if (sf.begin <= end && sf.end >= start)
- {
- result.add(sf);
- }
- return;
- }
-
- /**
- * Run through the sorted sequence array once, building the containedBy linked
- * list references. Does a check first to make sure there is actually
- * something out there that is overlapping. A null for sf.containedBy means
- * there are no overlaps for this feature.
- *
- * @param features
- */
- private void linkFeatures(SequenceFeature[] features)
- {
- int n = features.length;
- switch (n)
- {
- case 0:
- return;
- case 1:
- features[0].index1 = 1;
- return;
- }
- int maxEnd = features[0].end;
- for (int i = 1; i < n;)
- {
- SequenceFeature sf = features[i];
- if (sf.begin <= maxEnd)
- {
- sf.containedBy = getContainedBy(features[i - 1], sf);
- }
- if (sf.end > maxEnd)
- {
- maxEnd = sf.end;
- }
- sf.index1 = ++i;
- }
- }