+
+ /**
+ * Find all features containing this position.
+ * Uses isTainted field to know when to reconstruct its temporary array.
+ *
+ * @param pos
+ * @return list of SequenceFeatures
+ * @author Bob Hanson 2019.07.30
+ */
+ public void findOverlappingFeatures(int pos, List<SequenceFeature> result)
+ {
+
+ if (contactFeatureStarts != null)
+ {
+ findContacts(contactFeatureStarts, pos, result, true);
+ findContacts(contactFeatureEnds, pos, result, false);
+ }
+ if (features != null)
+ {
+ int n = features.size();
+ if (isTainted)
+ {
+ isTainted = false;
+ if (temp.length < n)
+ {
+ temp = new SequenceFeature[n << 1];
+ }
+ features.toArray(temp);
+ }
+ findOverlaps(temp, n, pos, result);
+ }
+ }
+
+ /**
+ * 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;
+ }
+ }
+ }
+
+ /**
+ * Brute force point-interval overlap test
+ *
+ * @param features
+ * @param n
+ * @param pos
+ * @param result
+ */
+ private static void findOverlaps(SequenceFeature[] features, int n,
+ int pos,
+ List<SequenceFeature> result)
+ {
+ // BH I know, brute force. We need a single-position overlap
+ // method for IntervalStore, I think.
+ for (int i = n; --i >= 0;)
+ {
+ SequenceFeature f = features[i];
+ if (f.begin <= pos && f.end >= pos)
+ {
+ result.add(f);
+ }
+ }
+ }
+