X-Git-Url: http://source.jalview.org/gitweb/?p=jalview.git;a=blobdiff_plain;f=src%2Fjalview%2Futil%2FMapList.java;h=c5654fbee62fd697f85c53ebb55e44302eb28b29;hp=26416599e95984a587291851a08c814200afe1d6;hb=c17981672620e0b780a2338bd0c74e55cf9ddec2;hpb=be32c14cd8e48fe0a207cd7030cb9cd46f894678 diff --git a/src/jalview/util/MapList.java b/src/jalview/util/MapList.java index 2641659..c5654fb 100644 --- a/src/jalview/util/MapList.java +++ b/src/jalview/util/MapList.java @@ -24,6 +24,8 @@ import java.util.ArrayList; import java.util.Arrays; import java.util.List; +import jalview.bin.Cache; + /** * A simple way of bijectively mapping a non-contiguous linear range to another * non-contiguous linear range. @@ -41,12 +43,12 @@ public class MapList /* * Subregions (base 1) described as { [start1, end1], [start2, end2], ...} */ - private List fromShifts = new ArrayList(); + private List fromShifts; /* * Same format as fromShifts, for the 'mapped to' sequence */ - private List toShifts = new ArrayList(); + private List toShifts; /* * number of steps in fromShifts to one toRatio unit @@ -73,14 +75,21 @@ public class MapList private int toHighest; /** + * Constructor + */ + public MapList() + { + fromShifts = new ArrayList<>(); + toShifts = new ArrayList<>(); + } + + /** * Two MapList objects are equal if they are the same object, or they both * have populated shift ranges and all values are the same. */ @Override public boolean equals(Object o) { - // TODO should also override hashCode to ensure equal objects have equal - // hashcodes if (o == null || !(o instanceof MapList)) { return false; @@ -96,10 +105,31 @@ public class MapList { return false; } - return Arrays - .deepEquals(fromShifts.toArray(), obj.fromShifts.toArray()) - && Arrays - .deepEquals(toShifts.toArray(), obj.toShifts.toArray()); + return Arrays.deepEquals(fromShifts.toArray(), obj.fromShifts.toArray()) + && Arrays.deepEquals(toShifts.toArray(), + obj.toShifts.toArray()); + } + + /** + * Returns a hashcode made from the fromRatio, toRatio, and from/to ranges + */ + @Override + public int hashCode() + { + int hashCode = 31 * fromRatio; + hashCode = 31 * hashCode + toRatio; + for (int[] shift : fromShifts) + { + hashCode = 31 * hashCode + shift[0]; + hashCode = 31 * hashCode + shift[1]; + } + for (int[] shift : toShifts) + { + hashCode = 31 * hashCode + shift[0]; + hashCode = 31 * hashCode + shift[1]; + } + + return hashCode; } /** @@ -180,7 +210,8 @@ public class MapList } /** - * Constructor. + * Constructor given from and to ranges as [start1, end1, start2, end2,...]. + * There is no validation check that the ranges do not overlap each other. * * @param from * contiguous regions as [start1, end1, start2, end2, ...] @@ -193,27 +224,30 @@ public class MapList */ public MapList(int from[], int to[], int fromRatio, int toRatio) { + this(); this.fromRatio = fromRatio; this.toRatio = toRatio; - fromLowest = from[0]; - fromHighest = from[1]; + fromLowest = Integer.MAX_VALUE; + fromHighest = Integer.MIN_VALUE; + for (int i = 0; i < from.length; i += 2) { - fromLowest = Math.min(fromLowest, from[i]); - fromHighest = Math.max(fromHighest, from[i + 1]); - - fromShifts.add(new int[] - { from[i], from[i + 1] }); + /* + * note lowest and highest values - bearing in mind the + * direction may be reversed + */ + fromLowest = Math.min(fromLowest, Math.min(from[i], from[i + 1])); + fromHighest = Math.max(fromHighest, Math.max(from[i], from[i + 1])); + fromShifts.add(new int[] { from[i], from[i + 1] }); } - toLowest = to[0]; - toHighest = to[1]; + toLowest = Integer.MAX_VALUE; + toHighest = Integer.MIN_VALUE; for (int i = 0; i < to.length; i += 2) { - toLowest = Math.min(toLowest, to[i]); - toHighest = Math.max(toHighest, to[i + 1]); - toShifts.add(new int[] - { to[i], to[i + 1] }); + toLowest = Math.min(toLowest, Math.min(to[i], to[i + 1])); + toHighest = Math.max(toHighest, Math.max(to[i], to[i + 1])); + toShifts.add(new int[] { to[i], to[i + 1] }); } } @@ -224,6 +258,7 @@ public class MapList */ public MapList(MapList map) { + this(); // TODO not used - remove? this.fromLowest = map.fromLowest; this.fromHighest = map.fromHighest; @@ -236,53 +271,135 @@ public class MapList { for (int[] r : map.fromShifts) { - fromShifts.add(new int[] - { r[0], r[1] }); + fromShifts.add(new int[] { r[0], r[1] }); } } if (map.toShifts != null) { for (int[] r : map.toShifts) { - toShifts.add(new int[] - { r[0], r[1] }); + toShifts.add(new int[] { r[0], r[1] }); } } } /** - * Constructor given ranges as lists of [start, end] positions + * Constructor given ranges as lists of [start, end] positions. There is no + * validation check that the ranges do not overlap each other. * * @param fromRange * @param toRange * @param fromRatio * @param toRatio */ - public MapList(List fromRange, List toRange, - int fromRatio, int toRatio) + public MapList(List fromRange, List toRange, int fromRatio, + int toRatio) { + this(); + fromRange = coalesceRanges(fromRange); + toRange = coalesceRanges(toRange); this.fromShifts = fromRange; this.toShifts = toRange; this.fromRatio = fromRatio; this.toRatio = toRatio; fromLowest = Integer.MAX_VALUE; - fromHighest = 0; - for (int[] range : fromRange) { - fromLowest = Math.min(fromLowest, range[0]); - fromHighest = Math.max(fromHighest, range[1]); + fromHighest = Integer.MIN_VALUE; + for (int[] range : fromRange) + { + if (range.length != 2) + { + // throw new IllegalArgumentException(range); + Cache.log.error("Invalid format for fromRange " + + Arrays.toString(range) + " may cause errors"); + } + fromLowest = Math.min(fromLowest, Math.min(range[0], range[1])); + fromHighest = Math.max(fromHighest, Math.max(range[0], range[1])); } toLowest = Integer.MAX_VALUE; - toHighest = 0; + toHighest = Integer.MIN_VALUE; for (int[] range : toRange) { - toLowest = Math.min(toLowest, range[0]); - toHighest = Math.max(toHighest, range[1]); + if (range.length != 2) + { + // throw new IllegalArgumentException(range); + Cache.log.error("Invalid format for toRange " + + Arrays.toString(range) + " may cause errors"); + } + toLowest = Math.min(toLowest, Math.min(range[0], range[1])); + toHighest = Math.max(toHighest, Math.max(range[0], range[1])); } } /** + * Consolidates a list of ranges so that any contiguous ranges are merged. + * This assumes the ranges are already in start order (does not sort them). + *

+ * The main use case for this method is when mapping cDNA sequence to its + * protein product, based on CDS feature ranges which derive from spliced + * exons, but are contiguous on the cDNA sequence. For example + * 

+   *   CDS 1-20  // from exon1
+   *   CDS 21-35 // from exon2
+   *   CDS 36-71 // from exon3
+   * 'coalesce' to range 1-71
+   *
+ * + * @param ranges + * @return the same list (if unchanged), else a new merged list, leaving the + * input list unchanged + */ + public static List coalesceRanges(final List ranges) + { + if (ranges == null || ranges.size() < 2) + { + return ranges; + } + + boolean changed = false; + List merged = new ArrayList<>(); + int[] lastRange = ranges.get(0); + int lastDirection = lastRange[1] >= lastRange[0] ? 1 : -1; + lastRange = new int[] { lastRange[0], lastRange[1] }; + merged.add(lastRange); + boolean first = true; + + for (final int[] range : ranges) + { + if (first) + { + first = false; + continue; + } + + int direction = range[1] >= range[0] ? 1 : -1; + + /* + * if next range is in the same direction as last and contiguous, + * just update the end position of the last range + */ + boolean sameDirection = range[1] == range[0] + || direction == lastDirection; + boolean extending = range[0] == lastRange[1] + lastDirection; + if (sameDirection && extending) + { + lastRange[1] = range[1]; + changed = true; + } + else + { + lastRange = new int[] { range[0], range[1] }; + merged.add(lastRange); + // careful: merging [5, 5] after [7, 6] should keep negative direction + lastDirection = (range[1] == range[0]) ? lastDirection : direction; + } + } + + return changed ? merged : ranges; + } + + /** * get all mapped positions from 'from' to 'to' * * @return int[][] { int[] { fromStart, fromFinish, toStart, toFinish }, int @@ -313,8 +430,7 @@ public class MapList * returning mapped position */ private int[][] posMap(List shiftTo, int ratio, - List shiftFrom, - int toRatio) + List shiftFrom, int toRatio) { // TODO not used - remove?? int iv = 0, ivSize = shiftTo.size(); @@ -374,9 +490,8 @@ public class MapList } mp[i] = m; } - int[][] map = new int[][] - { new int[] - { from, to, tF, tT }, new int[to - from + 2] }; + int[][] map = new int[][] { new int[] { from, to, tF, tT }, + new int[to - from + 2] }; map[0][2] = tF; map[0][3] = tT; @@ -461,8 +576,7 @@ public class MapList return null; // throw new Error("Bad Mapping!"); } // System.out.println(fromCount[0]+" "+fromCount[1]+" "+toCount); - return new int[] - { toPos[0], fromRemainder, toPos[1] }; + return new int[] { toPos[0], fromRemainder, toPos[1] }; } /** @@ -482,8 +596,7 @@ public class MapList { if (pos >= intv[0] && pos <= intv[1]) { - return new int[] - { count + pos - intv[0] + 1, +1 }; + return new int[] { count + pos - intv[0] + 1, +1 }; } else { @@ -494,8 +607,7 @@ public class MapList { if (pos >= intv[1] && pos <= intv[0]) { - return new int[] - { count + intv[0] - pos + 1, -1 }; + return new int[] { count + intv[0] - pos + 1, -1 }; } else { @@ -516,8 +628,7 @@ public class MapList protected static int[] countToPos(List shiftFrom, int pos) { int count = 0, diff = 0, iv = 0, ivSize = shiftFrom.size(); - int[] intv = - { 0, 0 }; + int[] intv = { 0, 0 }; while (iv < ivSize) { intv = shiftFrom.get(iv++); @@ -526,8 +637,7 @@ public class MapList { if (pos <= count + 1 + diff) { - return new int[] - { pos - count - 1 + intv[0], +1 }; + return new int[] { pos - count - 1 + intv[0], +1 }; } else { @@ -538,8 +648,7 @@ public class MapList { if (pos <= count + 1 - diff) { - return new int[] - { intv[0] - (pos - count - 1), -1 }; + return new int[] { intv[0] - (pos - count - 1), -1 }; } else { @@ -597,8 +706,7 @@ public class MapList * region to final position of ending region inclusive */ protected static int[] getIntervals(List shiftFrom, - int[] fromStart, - int[] fromEnd, int fromRatio2) + int[] fromStart, int[] fromEnd, int fromRatio2) { if (fromStart == null || fromEnd == null) { @@ -681,15 +789,14 @@ public class MapList { return null; } - List ranges = new ArrayList(); + List ranges = new ArrayList<>(); if (fs <= fe) { intv = fs; i = fs; // truncate initial interval iv = shiftFrom.get(intv++); - iv = new int[] - { iv[0], iv[1] };// clone + iv = new int[] { iv[0], iv[1] };// clone if (i == fs) { iv[0] = startpos; @@ -698,8 +805,7 @@ public class MapList { ranges.add(iv); // add initial range iv = shiftFrom.get(intv++); // get next interval - iv = new int[] - { iv[0], iv[1] };// clone + iv = new int[] { iv[0], iv[1] };// clone i++; } if (i == fe) @@ -717,8 +823,7 @@ public class MapList i--; } iv = shiftFrom.get(i); - iv = new int[] - { iv[1], iv[0] };// reverse and clone + iv = new int[] { iv[1], iv[0] };// reverse and clone // truncate initial interval if (i == fs) { @@ -728,8 +833,7 @@ public class MapList { // fix apparent logic bug when fe==-1 ranges.add(iv); // add (truncated) reversed interval iv = shiftFrom.get(i); - iv = new int[] - { iv[1], iv[0] }; // reverse and clone + iv = new int[] { iv[1], iv[0] }; // reverse and clone } if (i == fe) { @@ -788,8 +892,7 @@ public class MapList int[] mp = shiftTo(mpos); if (mp != null) { - return new int[] - { mp[0], mp[0] + mp[2] * (getFromRatio() - 1) }; + return new int[] { mp[0], mp[0] + mp[2] * (getFromRatio() - 1) }; } return null; } @@ -818,8 +921,7 @@ public class MapList int[] mp = shiftFrom(pos); if (mp != null) { - return new int[] - { mp[0], mp[0] + mp[2] * (getToRatio() - 1) }; + return new int[] { mp[0], mp[0] + mp[2] * (getToRatio() - 1) }; } return null; } @@ -848,15 +950,295 @@ public class MapList // TODO not used - remove? if (local) { - return ((getFromLowest() >= map.getFromLowest() && getFromHighest() <= map - .getFromHighest()) || (getFromLowest() <= map.getFromLowest() && getFromHighest() >= map - .getFromHighest())); + return ((getFromLowest() >= map.getFromLowest() + && getFromHighest() <= map.getFromHighest()) + || (getFromLowest() <= map.getFromLowest() + && getFromHighest() >= map.getFromHighest())); } else { - return ((getToLowest() >= map.getToLowest() && getToHighest() <= map - .getToHighest()) || (getToLowest() <= map.getToLowest() && getToHighest() >= map - .getToHighest())); + return ((getToLowest() >= map.getToLowest() + && getToHighest() <= map.getToHighest()) + || (getToLowest() <= map.getToLowest() + && getToHighest() >= map.getToHighest())); + } + } + + /** + * String representation - for debugging, not guaranteed not to change + */ + @Override + public String toString() + { + StringBuilder sb = new StringBuilder(64); + sb.append("["); + for (int[] shift : fromShifts) + { + sb.append(" ").append(Arrays.toString(shift)); + } + sb.append(" ] "); + sb.append(fromRatio).append(":").append(toRatio); + sb.append(" to ["); + for (int[] shift : toShifts) + { + sb.append(" ").append(Arrays.toString(shift)); + } + sb.append(" ]"); + return sb.toString(); + } + + /** + * Extend this map list by adding the given map's ranges. There is no + * validation check that the ranges do not overlap existing ranges (or each + * other), but contiguous ranges are merged. + * + * @param map + */ + public void addMapList(MapList map) + { + if (this.equals(map)) + { + return; + } + this.fromLowest = Math.min(fromLowest, map.fromLowest); + this.toLowest = Math.min(toLowest, map.toLowest); + this.fromHighest = Math.max(fromHighest, map.fromHighest); + this.toHighest = Math.max(toHighest, map.toHighest); + + for (int[] range : map.getFromRanges()) + { + addRange(range, fromShifts); + } + for (int[] range : map.getToRanges()) + { + addRange(range, toShifts); + } + } + + /** + * Adds the given range to a list of ranges. If the new range just extends + * existing ranges, the current endpoint is updated instead. + * + * @param range + * @param addTo + */ + static void addRange(int[] range, List addTo) + { + /* + * list is empty - add to it! + */ + if (addTo.size() == 0) + { + addTo.add(range); + return; + } + + int[] last = addTo.get(addTo.size() - 1); + boolean lastForward = last[1] >= last[0]; + boolean newForward = range[1] >= range[0]; + + /* + * contiguous range in the same direction - just update endpoint + */ + if (lastForward == newForward && last[1] == range[0]) + { + last[1] = range[1]; + return; } + + /* + * next range starts at +1 in forward sense - update endpoint + */ + if (lastForward && newForward && range[0] == last[1] + 1) + { + last[1] = range[1]; + return; + } + + /* + * next range starts at -1 in reverse sense - update endpoint + */ + if (!lastForward && !newForward && range[0] == last[1] - 1) + { + last[1] = range[1]; + return; + } + + /* + * just add the new range + */ + addTo.add(range); + } + + /** + * Returns true if mapping is from forward strand, false if from reverse + * strand. Result is just based on the first 'from' range that is not a single + * position. Default is true unless proven to be false. Behaviour is not well + * defined if the mapping has a mixture of forward and reverse ranges. + * + * @return + */ + public boolean isFromForwardStrand() + { + return isForwardStrand(getFromRanges()); + } + + /** + * Returns true if mapping is to forward strand, false if to reverse strand. + * Result is just based on the first 'to' range that is not a single position. + * Default is true unless proven to be false. Behaviour is not well defined if + * the mapping has a mixture of forward and reverse ranges. + * + * @return + */ + public boolean isToForwardStrand() + { + return isForwardStrand(getToRanges()); + } + + /** + * A helper method that returns true unless at least one range has start > + * end. Behaviour is undefined for a mixture of forward and reverse ranges. + * + * @param ranges + * @return + */ + private boolean isForwardStrand(List ranges) + { + boolean forwardStrand = true; + for (int[] range : ranges) + { + if (range[1] > range[0]) + { + break; // forward strand confirmed + } + else if (range[1] < range[0]) + { + forwardStrand = false; + break; // reverse strand confirmed + } + } + return forwardStrand; + } + + /** + * + * @return true if from, or to is a three to 1 mapping + */ + public boolean isTripletMap() + { + return (toRatio == 3 && fromRatio == 1) + || (fromRatio == 3 && toRatio == 1); + } + + /** + * Returns a map which is the composite of this one and the input map. That + * is, the output map has the fromRanges of this map, and its toRanges are the + * toRanges of this map as transformed by the input map. + *

+ * Returns null if the mappings cannot be traversed (not all toRanges of this + * map correspond to fromRanges of the input), or if this.toRatio does not + * match map.fromRatio. + * + * 

+   * Example 1:
+   *    this:   from [1-100] to [501-600]
+   *    input:  from [10-40] to [60-90]
+   *    output: from [10-40] to [560-590]
+   * Example 2 ('reverse strand exons'):
+   *    this:   from [1-100] to [2000-1951], [1000-951] // transcript to loci
+   *    input:  from [1-50]  to [41-90] // CDS to transcript
+   *    output: from [10-40] to [1960-1951], [1000-971] // CDS to gene loci
+   *
+ * + * @param map + * @return + */ + public MapList traverse(MapList map) + { + if (map == null) + { + return null; + } + + /* + * compound the ratios by this rule: + * A:B with M:N gives A*M:B*N + * reduced by greatest common divisor + * so 1:3 with 3:3 is 3:9 or 1:3 + * 1:3 with 3:1 is 3:3 or 1:1 + * 1:3 with 1:3 is 1:9 + * 2:5 with 3:7 is 6:35 + */ + int outFromRatio = getFromRatio() * map.getFromRatio(); + int outToRatio = getToRatio() * map.getToRatio(); + int gcd = MathUtils.gcd(outFromRatio, outToRatio); + outFromRatio /= gcd; + outToRatio /= gcd; + + List toRanges = new ArrayList<>(); + for (int[] range : getToRanges()) + { + int[] transferred = map.locateInTo(range[0], range[1]); + if (transferred == null || transferred.length % 2 != 0) + { + return null; + } + + /* + * convert [start1, end1, start2, end2, ...] + * to [[start1, end1], [start2, end2], ...] + */ + for (int i = 0; i < transferred.length;) + { + toRanges.add(new int[] { transferred[i], transferred[i + 1] }); + i += 2; + } + } + + return new MapList(getFromRanges(), toRanges, outFromRatio, outToRatio); + } + + /** + * Answers true if the mapping is from one contiguous range to another, else + * false + * + * @return + */ + public boolean isContiguous() + { + return fromShifts.size() == 1 && toShifts.size() == 1; + } + + /** + * 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]); } }