*/
public int[] locateInFrom(int start, int end)
{
+ return locateInFrom2(start, end);
+
// inefficient implementation
- int fromStart[] = shiftTo(start);
+ // int fromStart[] = shiftTo(start);
// needs to be inclusive of end of symbol position
- int fromEnd[] = shiftTo(end);
- System.out.println("locateInFrom");
- return getIntervals(fromShifts, fromStart, fromEnd, fromRatio);
+ // int fromEnd[] = shiftTo(end);
+ // return getIntervals(fromShifts, fromStart, fromEnd, fromRatio);
}
/**
*/
public int[] locateInTo(int start, int end)
{
- int toStart[] = shiftFrom(start);
- int toEnd[] = shiftFrom(end);
- return getIntervals(toShifts, toStart, toEnd, toRatio);
+ return locateInTo2(start, end);
+
+ // int toStart[] = shiftFrom(start);
+ // int toEnd[] = shiftFrom(end);
+ // return getIntervals(toShifts, toStart, toEnd, toRatio);
}
/**
List<int[]> toRanges = new ArrayList<>();
for (int[] range : getToRanges())
{
+ int fromLength = Math.abs(range[1] - range[0]) + 1;
int[] transferred = map.locateInTo(range[0], range[1]);
if (transferred == null || transferred.length % 2 != 0)
{
* convert [start1, end1, start2, end2, ...]
* to [[start1, end1], [start2, end2], ...]
*/
+ int toLength = 0;
for (int i = 0; i < transferred.length;)
{
toRanges.add(new int[] { transferred[i], transferred[i + 1] });
+ toLength += Math.abs(transferred[i + 1] - transferred[i]) + 1;
i += 2;
}
+
+ /*
+ * check we mapped the full range - if not, abort
+ */
+ if (fromLength * map.getToRatio() != toLength * map.getFromRatio())
+ {
+ return null;
+ }
}
return new MapList(getFromRanges(), toRanges, outFromRatio, outToRatio);
/**
* Returns the [start, end, start, end, ...] ranges in the 'from' range that
- * map to the given start-end in the 'to' range. Returns null if either
- * {@code start} or {@code end} is not a mapped 'to' range position.
+ * map to positions between {@code start} and {@code end} in the 'to' range.
+ * Returns null if no mapped positions are found in start-end.
*
* @param start
* @param end
List<int[]> ranges1, List<int[]> ranges2, int wordLength1,
int wordLength2)
{
+ if (end < start)
+ {
+ int tmp = end;
+ end = start;
+ start = tmp;
+ }
+
/*
* first traverse ranges1 and record count of mapped positions
* to any that overlap start-end
}
/*
- * convert positions to equivalent 'word' positions in ranges
+ * convert positions to equivalent 'word' positions in ranges2
*/
mapWords(overlaps, wordLength1, wordLength2);
List<int[]> mapped = new ArrayList<>();
final int s1 = overlaps.size();
final int s2 = ranges2.size();
- int rangeIndex = 0;
- int rangeOffset = 0;
- int mappedCount = 0;
+ int ranges2Index = 0;
- for (int i = 0 ; i < s1 ; i++)
+ /*
+ * count of mapped positions preceding ranges2[ranges2Index]
+ */
+ int traversed = 0;
+
+ /*
+ * for each [from-to] range in overlaps:
+ * - walk (what remains of) ranges2
+ * - record the values at offsets [from-to]
+ * - stop when past 'to' positions (or at end of ranges2)
+ */
+ for (int i = 0; i < s1; i++)
{
- /*
- * for each range in overlaps, walk ranges2 and record the values
- * at the offsets, advancing rangeIndex / Offset
- */
- int [] mappedRange = ranges2.get(rangeIndex);
- int [] overlap = overlaps.get(s1);
- while (mappedCount < overlap[1])
+ int[] overlap = overlaps.get(i);
+ final int toAdd = overlap[1] - overlap[0] + 1;
+ int added = 0; // how much of overlap has been 'found'
+ for (; added < toAdd && ranges2Index < s2; ranges2Index++)
{
-
+ int[] range2 = ranges2.get(ranges2Index);
+ int rangeStart = range2[0];
+ int rangeEnd = range2[1];
+ boolean reverseStrand = range2[1] < range2[0];
+ int rangeLength = Math.abs(rangeEnd - rangeStart) + 1;
+ if (traversed + rangeLength <= overlap[0])
+ {
+ /*
+ * precedes overlap - keep looking
+ */
+ traversed += rangeLength;
+ continue;
+ }
+ int overlapStart = overlap[0] - traversed;
+ int overlapEnd = Math.min(overlapStart + toAdd - added - 1,
+ rangeLength - 1);
+ int mappedFrom = range2[0] + (reverseStrand ? - overlapStart : overlapStart);
+ int mappedTo = range2[0] + (reverseStrand ? - overlapEnd : overlapEnd);
+ mapped.add(new int[] { mappedFrom, mappedTo });
+ int found = overlapEnd - overlapStart + 1;
+ added += found;
+ overlap[0] += found;
+ traversed += rangeLength;
}
}
-
+
return mapped;
}
/**
* Helper method that returns a (possibly empty) list of offsets in
- * {@code ranges} to subranges that overlap {@code start-end}. The list
- * returned holds counts of the number of positions traversed (inclusive) to
- * reach the overlapping positions, not the overlapping values. Returns null
- * if there are no overlaps.
+ * {@code ranges} to subranges that overlap {@code start-end} (where start <=
+ * end}. The list returned holds counts of the number of positions traversed
+ * (exclusive) to reach the overlapping positions, not the overlapping values.
+ * Returns null if there are no overlaps.
*
* @param ranges
* @param start
/**
* A helper method that checks whether {@code range} overlaps
- * {@code start-end}, and if so adds the positional offset of the overlap to
- * {@code positions}.
+ * {@code start-end}, and if so adds the offset of the overlap in
+ * {@code range}, plus {@code pos}, to {@code positions}.
*
* @param positions
* a list of map offsets to add to
* overlap
*/
int overlapStart = Math.max(start, range[0]);
+ int overlapStartOffset = pos + overlapStart - range[0];
int overlapEnd = Math.min(end, range[1]);
- positions
- .add(new int[]
- { 1 + overlapStart - range[0], 1 + overlapEnd - range[0] });
+ int overlapEndOffset = pos + overlapEnd - range[0];
+ int[] lastOverlap = positions.isEmpty() ? null
+ : positions.get(positions.size() - 1);
+ if (lastOverlap != null && overlapStartOffset == lastOverlap[1] + 1)
+ {
+ /*
+ * just extending the last overlap range
+ */
+ lastOverlap[1] = overlapEndOffset;
+ }
+ else
+ {
+ /*
+ * add a new (discontiguous) overlap range
+ */
+ positions.add(new int[] { overlapStartOffset, overlapEndOffset });
+ }
}
}
else
int overlapEnd = Math.min(end, range[0]);
positions
.add(new int[]
- { 1 + range[0] - overlapStart, 1 + range[0] - overlapEnd });
+ { pos + range[0] - overlapEnd,
+ pos + range[0] - overlapStart });
}
}
}