X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=src%2Fjalview%2Futil%2FMapList.java;h=986b18cf270c855a00a7369d2c2aa060d4a6beab;hb=6398c0217546a4d6943f63f670c2684c7c7274be;hp=bf66b91b2496fb0d36c17fed9b797d90e1649da3;hpb=2ad6ae4687351167ea0f706a2fe8574f7460104c;p=jalview.git diff --git a/src/jalview/util/MapList.java b/src/jalview/util/MapList.java index bf66b91..986b18c 100644 --- a/src/jalview/util/MapList.java +++ b/src/jalview/util/MapList.java @@ -77,8 +77,8 @@ public class MapList */ public MapList() { - fromShifts = new ArrayList(); - toShifts = new ArrayList(); + fromShifts = new ArrayList<>(); + toShifts = new ArrayList<>(); } /** @@ -88,8 +88,6 @@ public class MapList @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; @@ -105,10 +103,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; } /** @@ -215,7 +234,7 @@ public class MapList { /* * note lowest and highest values - bearing in mind the - * direction may be revesed + * 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])); @@ -308,6 +327,13 @@ public class MapList fromHighest = Integer.MIN_VALUE; for (int[] range : fromRange) { + if (range.length != 2) + { + // throw new IllegalArgumentException(range); + System.err.println( + "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])); } @@ -316,57 +342,97 @@ public class MapList toHighest = Integer.MIN_VALUE; for (int[] range : toRange) { + if (range.length != 2) + { + // throw new IllegalArgumentException(range); + System.err.println("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 + * 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). * * @param ranges - * @return + * @return the same list (if unchanged), else a new merged list, leaving the + * input list unchanged */ - public static List coalesceRanges(List ranges) + public static List coalesceRanges(final List ranges) { - if (ranges == null || ranges.size() < 2) { + if (ranges == null || ranges.size() < 2) + { return ranges; } boolean changed = false; - List merged = new ArrayList(); + 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); - - for (int[] range : ranges) + boolean first = true; + + for (final int[] range : ranges) { - if (range == lastRange) + if (first) { + first = false; continue; } + if (range[0] == lastRange[0] && range[1] == lastRange[1]) + { + // drop duplicate range + changed = true; + continue; + } + + /* + * drop this range if it lies within the last range + */ + if ((lastDirection == 1 && range[0] >= lastRange[0] + && range[0] <= lastRange[1] && range[1] >= lastRange[0] + && range[1] <= lastRange[1]) + || (lastDirection == -1 && range[0] <= lastRange[0] + && range[0] >= lastRange[1] + && range[1] <= lastRange[0] + && range[1] >= lastRange[1])) + { + changed = true; + 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 */ - if ((range[1] == range[0] || direction == lastDirection) - && (range[0] == lastRange[1] || range[0] == lastRange[1] - + lastDirection)) + boolean sameDirection = range[1] == range[0] + || direction == lastDirection; + boolean extending = range[0] == lastRange[1] + lastDirection; + boolean overlapping = (lastDirection == 1 && range[0] >= lastRange[0] + && range[0] <= lastRange[1]) + || (lastDirection == -1 && range[0] <= lastRange[0] + && range[0] >= lastRange[1]); + if (sameDirection && (overlapping || extending)) { lastRange[1] = range[1]; changed = true; } else { - merged.add(range); - lastRange = range; + 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; } @@ -760,7 +826,7 @@ public class MapList { return null; } - List ranges = new ArrayList(); + List ranges = new ArrayList<>(); if (fs <= fe) { intv = fs; @@ -921,15 +987,17 @@ 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())); } } @@ -945,7 +1013,9 @@ public class MapList { sb.append(" ").append(Arrays.toString(shift)); } - sb.append(" ] To ["); + sb.append(" ] "); + sb.append(fromRatio).append(":").append(toRatio); + sb.append(" to ["); for (int[] shift : toShifts) { sb.append(" ").append(Arrays.toString(shift)); @@ -963,6 +1033,10 @@ public class MapList */ 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); @@ -970,62 +1044,14 @@ public class MapList for (int[] range : map.getFromRanges()) { - addRange(range, fromShifts); + MappingUtils.addRange(range, fromShifts); } for (int[] range : map.getToRanges()) { - addRange(range, toShifts); + MappingUtils.addRange(range, toShifts); } } - public 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 @@ -1036,8 +1062,33 @@ public class MapList */ 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 : getFromRanges()) + for (int[] range : ranges) { if (range[1] > range[0]) { @@ -1051,4 +1102,93 @@ public class MapList } 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; + } }