+ return overlaps;
+ }
+
+ /**
+ * Returns a (possibly empty) list of the [start-end] values (positions) at
+ * offsets in the {@code targetRange} list that are marked by 'on' bits in the
+ * {@code offsets} bitset.
+ *
+ * @param targetRange
+ * @param offsets
+ * @return
+ */
+ protected final static List<int[]> getPositionsForOffsets(
+ List<int[]> targetRange, BitSet offsets)
+ {
+ List<int[]> mapped = new ArrayList<>();
+ if (offsets.isEmpty())
+ {
+ return mapped;
+ }
+
+ /*
+ * count of positions preceding ranges[i]
+ */
+ int traversed = 0;
+
+ /*
+ * for each [from-to] range in ranges:
+ * - find subranges (if any) at marked offsets
+ * - add the start-end values at the marked positions
+ */
+ final int toAdd = offsets.cardinality();
+ int added = 0;
+ final int s2 = targetRange.size();
+ for (int i = 0; added < toAdd && i < s2; i++)
+ {
+ int[] range = targetRange.get(i);
+ added += addOffsetPositions(mapped, traversed, range, offsets);
+ traversed += Math.abs(range[1] - range[0]) + 1;
+ }
+ return mapped;
+ }
+
+ /**
+ * Helper method that adds any start-end subranges of {@code range} that are
+ * at offsets in {@code range} marked by set bits in overlaps.
+ * {@code mapOffset} is added to {@code range} offset positions. Returns the
+ * count of positions added.
+ *
+ * @param mapped
+ * @param mapOffset
+ * @param range
+ * @param overlaps
+ * @return
+ */
+ final static int addOffsetPositions(List<int[]> mapped,
+ final int mapOffset, final int[] range, final BitSet overlaps)
+ {
+ final int rangeLength = 1 + Math.abs(range[1] - range[0]);
+ final int step = range[1] < range[0] ? -1 : 1;
+ int offsetStart = 0; // offset into range
+ int added = 0;
+
+ while (offsetStart < rangeLength)
+ {
+ /*
+ * find the start of the next marked overlap offset;
+ * if there is none, or it is beyond range, then finished
+ */
+ int overlapStart = overlaps.nextSetBit(mapOffset + offsetStart);
+ if (overlapStart == -1 || overlapStart - mapOffset >= rangeLength)
+ {
+ /*
+ * no more overlaps, or no more within range[]
+ */
+ return added;
+ }
+ overlapStart -= mapOffset;
+
+ /*
+ * end of the overlap range is just before the next clear bit;
+ * restrict it to end of range if necessary;
+ * note we may add a reverse strand range here (end < start)
+ */
+ int overlapEnd = overlaps.nextClearBit(mapOffset + overlapStart + 1);
+ overlapEnd = (overlapEnd == -1) ? rangeLength - 1
+ : Math.min(rangeLength - 1, overlapEnd - mapOffset - 1);
+ int startPosition = range[0] + step * overlapStart;
+ int endPosition = range[0] + step * overlapEnd;
+ mapped.add(new int[] { startPosition, endPosition });
+ offsetStart = overlapEnd + 1;
+ added += Math.abs(endPosition - startPosition) + 1;
+ }
+
+ return added;
+ }
+
+ /*
+ * Returns the [start, end...] positions in the range mapped from, that are
+ * mapped to by part or all of the given begin-end of the range mapped to.
+ * Returns null if begin-end does not overlap any position mapped to.
+ *
+ * @param begin
+ * @param end
+ * @return
+ */
+ public int[] getOverlapsInFrom(final int begin, final int end)
+ {
+ int[] overlaps = MappingUtils.findOverlap(toShifts, begin, end);
+
+ return overlaps == null ? null : locateInFrom(overlaps[0], overlaps[1]);
+ }
+
+ /**
+ * Returns the [start, end...] positions in the range mapped to, that are
+ * mapped to by part or all of the given begin-end of the range mapped from.
+ * Returns null if begin-end does not overlap any position mapped from.
+ *
+ * @param begin
+ * @param end
+ * @return
+ */
+ public int[] getOverlapsInTo(final int begin, final int end)
+ {
+ int[] overlaps = MappingUtils.findOverlap(fromShifts, begin, end);
+
+ return overlaps == null ? null : locateInTo(overlaps[0], overlaps[1]);