mapped = getPositionsForOffsets(toShifts, offsets);
+
+ return mapped.isEmpty() ? null : MappingUtils.rangeListToArray(mapped);
+ }
+
+ /**
+ * 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 ranges
+ * @param wordLengthFrom
+ * @param wordLengthTo
+ * @return
+ */
+ protected final static BitSet getMappedOffsetsForPositions(int start,
+ int end, List ranges, int wordLengthFrom, int wordLengthTo)
+ {
+ BitSet overlaps = new BitSet();
+ int offset = 0;
+ final int s1 = ranges.size();
+ for (int i = 0; i < s1; i++)
+ {
+ int[] range = ranges.get(i);
+ final int offset1 = offset;
+ int overlapStartOffset = -1;
+ int overlapEndOffset = -1;
+
+ if (range[1] >= range[0])
{
- System.out.print("\n");
+ /*
+ * 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.out.print(",");
- }
- }
- System.out.print("\n");
- //test range function
- System.out.print("\nTest locateInTo\n");
- {
- int f=mmap[0][2],t=mmap[0][3];
- while (f<=t) {
- System.out.println("Range "+f+" to "+t);
- int rng[] = ml.locateInTo(f,t);
- if (rng!=null) {
- for (int i=0; i= range[1])
{
- for (int i=0; i -1)
+ {
+ /*
+ * found an overlap
+ */
+ if (wordLengthFrom != wordLengthTo)
{
- System.out.println("No range!");
+ /*
+ * 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 % wordLengthFrom;
+ overlapStartOffset = overlapStartOffset / wordLengthFrom
+ * wordLengthTo;
+
+ /*
+ * similar calculation for range end, adding
+ * (wordLength2 - 1) for end of mapped word
+ */
+ overlapEndOffset -= overlapEndOffset % wordLengthFrom;
+ overlapEndOffset = overlapEndOffset / wordLengthFrom
+ * wordLengthTo;
+ overlapEndOffset += wordLengthTo - 1;
}
- f++; t--;
- System.out.print("\n");
+ overlaps.set(overlapStartOffset, overlapEndOffset + 1);
}
+ offset += 1 + Math.abs(range[1] - range[0]);
}
-
+ return overlaps;
}
- public static void main(String argv[])
+ /**
+ * Returns a (possibly empty) list of the [start-end] values (positions) at
+ * offsets in the {@code ranges} list that are marked by 'on' bits in the
+ * {@code offsets} bitset.
+ *
+ * @param ranges
+ * @param offsets
+ * @return
+ */
+ protected final static List getPositionsForOffsets(
+ List ranges, BitSet offsets)
{
- MapList ml = new MapList(new int[]
- {1, 5, 10, 15, 25, 20},
- new int[]
- {51, 1}, 1, 3);
- MapList ml1 = new MapList(new int[]
- {1, 3, 17, 4},
- new int[]
- {51, 1}, 1, 3);
- MapList ml2 = new MapList(new int[] { 1, 60 },
- new int[] { 1, 20 }, 3, 1);
- // test internal consistency
- int to[] = new int[51];
- MapList.testMap(ml, 1, 60);
+ List mapped = new ArrayList<>();
+ if (offsets.isEmpty())
+ {
+ return mapped;
+ }
+
+ /*
+ * count of positions preceding ranges[i]
+ */
+ int traversed = 0;
+
/*
- for (int from=1; from<=51; from++) {
- int[] too=ml.shiftTo(from);
- int[] toofrom=ml.shiftFrom(too[0]);
- System.out.println("ShiftFrom("+from+")=="+too[0]+" % "+too[1]+"\t+-+\tShiftTo("+too[0]+")=="+toofrom[0]+" % "+toofrom[1]);
- }*/
- System.out.print("Success?\n"); // if we get here - something must be working!
+ * 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 = ranges.size();
+ for (int i = 0; added < toAdd && i < s2; i++)
+ {
+ int[] range = ranges.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 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;
}
}