mapped = getPositionsForOffsets(targetRange, offsets);
+
+ // TODO: or just return the List and adjust calling code to match
+ return mapped.isEmpty() ? null : MappingUtils.rangeListToArray(mapped);
}
- private static void testLocateFrom(MapList mldna, int i, int j, int[] ks)
+ /**
+ * Scans the list of {@code ranges} for any values (positions) that lie
+ * between start and end (inclusive), and records the offsets from
+ * the start of the list as a BitSet. The offset positions are converted to
+ * corresponding words in blocks of {@code wordLength2}.
+ *
+ *
+ * For example:
+ * 1:1 (e.g. gene to CDS):
+ * ranges { [10-20], [31-40] }, wordLengthFrom = wordLength 2 = 1
+ * for start = 1, end = 9, returns a BitSet with no bits set
+ * for start = 1, end = 11, returns a BitSet with bits 0-1 set
+ * for start = 15, end = 35, returns a BitSet with bits 5-15 set
+ * 1:3 (peptide to codon):
+ * ranges { [1-200] }, wordLengthFrom = 1, wordLength 2 = 3
+ * for start = 9, end = 9, returns a BitSet with bits 24-26 set
+ * 3:1 (codon to peptide):
+ * ranges { [101-150], [171-180] }, wordLengthFrom = 3, wordLength 2 = 1
+ * for start = 101, end = 102 (partial first codon), returns a BitSet with bit 0 set
+ * for start = 150, end = 171 (partial 17th codon), returns a BitSet with bit 16 set
+ * 3:1 (circular DNA to peptide):
+ * ranges { [101-150], [21-30] }, wordLengthFrom = 3, wordLength 2 = 1
+ * for start = 24, end = 40 (spans codons 18-20), returns a BitSet with bits 17-19 set
+ *
+ *
+ * @param start
+ * @param end
+ * @param sourceRange
+ * @param sourceWordLength
+ * @param targetWordLength
+ * @return
+ */
+ protected final static BitSet getMappedOffsetsForPositions(int start,
+ int end, List sourceRange, int sourceWordLength, int targetWordLength)
{
- int[] frm = mldna.locateInFrom(i, j);
- if (frm == ks || java.util.Arrays.equals(frm, ks))
+ BitSet overlaps = new BitSet();
+ int offset = 0;
+ final int s1 = sourceRange.size();
+ for (int i = 0; i < s1; i++)
{
- System.out.println("Success test locate from " + i + " to " + j);
- }
- else
- {
- System.err.println("Failed test locate from " + i + " to " + j);
- for (int c = 0; c < frm.length; c++)
+ int[] range = sourceRange.get(i);
+ final int offset1 = offset;
+ int overlapStartOffset = -1;
+ int overlapEndOffset = -1;
+
+ if (range[1] >= range[0])
+ {
+ /*
+ * forward direction range
+ */
+ if (start <= range[1] && end >= range[0])
+ {
+ /*
+ * overlap
+ */
+ int overlapStart = Math.max(start, range[0]);
+ overlapStartOffset = offset1 + overlapStart - range[0];
+ int overlapEnd = Math.min(end, range[1]);
+ overlapEndOffset = offset1 + overlapEnd - range[0];
+ }
+ }
+ else
{
- System.err.print(frm[c] + ((c % 2 == 0) ? "," : ";"));
+ /*
+ * reverse direction range
+ */
+ if (start <= range[0] && end >= range[1])
+ {
+ /*
+ * overlap
+ */
+ int overlapStart = Math.max(start, range[1]);
+ int overlapEnd = Math.min(end, range[0]);
+ overlapStartOffset = offset1 + range[0] - overlapEnd;
+ overlapEndOffset = offset1 + range[0] - overlapStart;
+ }
}
- System.err.println("Expected");
- for (int c = 0; c < ks.length; c++)
+
+ if (overlapStartOffset > -1)
{
- System.err.print(ks[c] + ((c % 2 == 0) ? "," : ";"));
+ /*
+ * found an overlap
+ */
+ if (sourceWordLength != targetWordLength)
+ {
+ /*
+ * convert any overlap found to whole words in the target range
+ * (e.g. treat any partial codon overlap as if the whole codon)
+ */
+ overlapStartOffset -= overlapStartOffset % sourceWordLength;
+ overlapStartOffset = overlapStartOffset / sourceWordLength
+ * targetWordLength;
+
+ /*
+ * similar calculation for range end, adding
+ * (wordLength2 - 1) for end of mapped word
+ */
+ overlapEndOffset -= overlapEndOffset % sourceWordLength;
+ overlapEndOffset = overlapEndOffset / sourceWordLength
+ * targetWordLength;
+ overlapEndOffset += targetWordLength - 1;
+ }
+ overlaps.set(overlapStartOffset, overlapEndOffset + 1);
}
+ offset += 1 + Math.abs(range[1] - range[0]);
}
+ 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.
*
- * @return a MapList whose From range is this maplist's To Range, and vice
- * versa
+ * @param targetRange
+ * @param offsets
+ * @return
*/
- public MapList getInverse()
+ protected final static List getPositionsForOffsets(
+ List targetRange, BitSet offsets)
{
- return new MapList(getToRanges(), getFromRanges(), getToRatio(),
- getFromRatio());
+ List 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;
}
/**
- * test for containment rather than equivalence to another mapping
+ * 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 map
- * to be tested for containment
- * @return true if local or mapped range map contains or is contained by this
- * mapping
+ * @param mapped
+ * @param mapOffset
+ * @param range
+ * @param overlaps
+ * @return
*/
- public boolean containsEither(boolean local, MapList map)
+ final static int addOffsetPositions(List mapped,
+ final int mapOffset, final int[] range, final BitSet overlaps)
{
- if (local)
- {
- return ((getFromLowest() >= map.getFromLowest() && getFromHighest() <= map
- .getFromHighest()) || (getFromLowest() <= map.getFromLowest() && getFromHighest() >= map
- .getFromHighest()));
- }
- else
+ 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)
{
- return ((getToLowest() >= map.getToLowest() && getToHighest() <= map
- .getToHighest()) || (getToLowest() <= map.getToLowest() && getToHighest() >= map
- .getToHighest()));
+ /*
+ * 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;
}
}