X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=src%2Fjalview%2Futil%2FMapList.java;h=58abdc3926c1bf1badddf8e83e4b0724c06b30da;hb=37de9310bec3501cbc6381e0c3dcb282fcaad812;hp=c566c84e2578c7b06c87edc4ea77fedcdab069de;hpb=ad15cff29620f960119f80176f1fd443da9f6763;p=jalview.git diff --git a/src/jalview/util/MapList.java b/src/jalview/util/MapList.java index c566c84..58abdc3 100644 --- a/src/jalview/util/MapList.java +++ b/src/jalview/util/MapList.java @@ -20,86 +20,141 @@ */ package jalview.util; -import java.util.*; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.List; /** - * MapList Simple way of bijectively mapping a non-contiguous linear range to - * another non-contiguous linear range Use at your own risk! TODO: efficient - * implementation of private posMap method TODO: test/ensure that sense of from - * and to ratio start position is conserved (codon start position recovery) - * TODO: optimize to use int[][] arrays rather than vectors. + * A simple way of bijectively mapping a non-contiguous linear range to another + * non-contiguous linear range. + * + * Use at your own risk! + * + * TODO: efficient implementation of private posMap method + * + * TODO: test/ensure that sense of from and to ratio start position is conserved + * (codon start position recovery) */ public class MapList { + /* - * (non-Javadoc) - * - * @see java.lang.Object#equals(java.lang.Object) + * Subregions (base 1) described as { [start1, end1], [start2, end2], ...} + */ + private List fromShifts; + + /* + * Same format as fromShifts, for the 'mapped to' sequence + */ + private List toShifts; + + /* + * number of steps in fromShifts to one toRatio unit + */ + private int fromRatio; + + /* + * number of steps in toShifts to one fromRatio + */ + private int toRatio; + + /* + * lowest and highest value in the from Map + */ + private int fromLowest; + + private int fromHighest; + + /* + * lowest and highest value in the to Map + */ + private int toLowest; + + 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. */ - public boolean equals(MapList obj) + @Override + public boolean equals(Object o) { + if (o == null || !(o instanceof MapList)) + { + return false; + } + + MapList obj = (MapList) o; if (obj == this) + { return true; - if (obj != null && obj.fromRatio == fromRatio && obj.toRatio == toRatio - && obj.fromShifts != null && obj.toShifts != null) - { - int i, iSize = fromShifts.size(), j, jSize = obj.fromShifts.size(); - if (iSize != jSize) - return false; - for (i = 0, iSize = fromShifts.size(), j = 0, jSize = obj.fromShifts - .size(); i < iSize;) - { - int[] mi = (int[]) fromShifts.elementAt(i++); - int[] mj = (int[]) obj.fromShifts.elementAt(j++); - if (mi[0] != mj[0] || mi[1] != mj[1]) - return false; - } - iSize = toShifts.size(); - jSize = obj.toShifts.size(); - if (iSize != jSize) - return false; - for (i = 0, j = 0; i < iSize;) - { - int[] mi = (int[]) toShifts.elementAt(i++); - int[] mj = (int[]) obj.toShifts.elementAt(j++); - if (mi[0] != mj[0] || mi[1] != mj[1]) - return false; - } - return true; } - return false; + if (obj.fromRatio != fromRatio || obj.toRatio != toRatio + || obj.fromShifts == null || obj.toShifts == null) + { + return false; + } + return Arrays + .deepEquals(fromShifts.toArray(), obj.fromShifts.toArray()) + && Arrays + .deepEquals(toShifts.toArray(), obj.toShifts.toArray()); } - public Vector fromShifts; - - public Vector toShifts; - - int fromRatio; // number of steps in fromShifts to one toRatio unit - - int toRatio; // number of steps in toShifts to one fromRatio + /** + * Returns a hashcode made from the fromRatio, toRatio, and from/to ranges + */ + @Override + public int hashCode() + { + int hashCode = 31 * fromRatio; + hashCode = 31 * hashCode + toRatio; + hashCode = 31 * hashCode + fromShifts.toArray().hashCode(); + hashCode = 31 * hashCode + toShifts.toArray().hashCode(); + return hashCode; + } /** + * Returns the 'from' ranges as {[start1, end1], [start2, end2], ...} * - * @return series of intervals mapped in from + * @return */ - public int[] getFromRanges() + public List getFromRanges() { - return getRanges(fromShifts); + return fromShifts; } - public int[] getToRanges() + /** + * Returns the 'to' ranges as {[start1, end1], [start2, end2], ...} + * + * @return + */ + public List getToRanges() { - return getRanges(toShifts); + return toShifts; } - private int[] getRanges(Vector shifts) + /** + * Flattens a list of [start, end] into a single [start1, end1, start2, + * end2,...] array. + * + * @param shifts + * @return + */ + protected static int[] getRanges(List shifts) { int[] rnges = new int[2 * shifts.size()]; - Enumeration e = shifts.elements(); int i = 0; - while (e.hasMoreElements()) + for (int[] r : shifts) { - int r[] = (int[]) e.nextElement(); rnges[i++] = r[0]; rnges[i++] = r[1]; } @@ -107,16 +162,6 @@ public class MapList } /** - * lowest and highest value in the from Map - */ - int[] fromRange = null; - - /** - * lowest and highest value in the to Map - */ - int[] toRange = null; - - /** * * @return length of mapped phrase in from */ @@ -136,100 +181,244 @@ public class MapList public int getFromLowest() { - return fromRange[0]; + return fromLowest; } public int getFromHighest() { - return fromRange[1]; + return fromHighest; } public int getToLowest() { - return toRange[0]; + return toLowest; } public int getToHighest() { - return toRange[1]; - } - - private void ensureRange(int[] limits, int pos) - { - if (limits[0] > pos) - limits[0] = pos; - if (limits[1] < pos) - limits[1] = pos; + return toHighest; } + /** + * Constructor given from and to ranges as [start1, end1, start2, end2,...]. + * If any end is equal to the next start, the ranges will be merged. There is + * no validation check that the ranges do not overlap each other. + * + * @param from + * contiguous regions as [start1, end1, start2, end2, ...] + * @param to + * same format as 'from' + * @param fromRatio + * phrase length in 'from' (e.g. 3 for dna) + * @param toRatio + * phrase length in 'to' (e.g. 1 for protein) + */ public MapList(int from[], int to[], int fromRatio, int toRatio) { - fromRange = new int[] - { from[0], from[1] }; - toRange = new int[] - { to[0], to[1] }; + this(); + this.fromRatio = fromRatio; + this.toRatio = toRatio; + fromLowest = Integer.MAX_VALUE; + fromHighest = Integer.MIN_VALUE; + int added = 0; - fromShifts = new Vector(); for (int i = 0; i < from.length; i += 2) { - ensureRange(fromRange, from[i]); - ensureRange(fromRange, from[i + 1]); - - fromShifts.addElement(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])); + if (added > 0 && from[i] == fromShifts.get(added - 1)[1]) + { + /* + * this range starts where the last ended - just extend it + */ + fromShifts.get(added - 1)[1] = from[i + 1]; + } + else + { + fromShifts.add(new int[] { from[i], from[i + 1] }); + added++; + } } - toShifts = new Vector(); + + toLowest = Integer.MAX_VALUE; + toHighest = Integer.MIN_VALUE; + added = 0; for (int i = 0; i < to.length; i += 2) { - ensureRange(toRange, to[i]); - ensureRange(toRange, to[i + 1]); - toShifts.addElement(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])); + if (added > 0 && to[i] == toShifts.get(added - 1)[1]) + { + toShifts.get(added - 1)[1] = to[i + 1]; + } + else + { + toShifts.add(new int[] { to[i], to[i + 1] }); + added++; + } } - this.fromRatio = fromRatio; - this.toRatio = toRatio; } + /** + * Copy constructor. Creates an identical mapping. + * + * @param map + */ public MapList(MapList map) { - this.fromRange = new int[] - { map.fromRange[0], map.fromRange[1] }; - this.toRange = new int[] - { map.toRange[0], map.toRange[1] }; + this(); + // TODO not used - remove? + this.fromLowest = map.fromLowest; + this.fromHighest = map.fromHighest; + this.toLowest = map.toLowest; + this.toHighest = map.toHighest; + this.fromRatio = map.fromRatio; this.toRatio = map.toRatio; if (map.fromShifts != null) { - this.fromShifts = new Vector(); - Enumeration e = map.fromShifts.elements(); - while (e.hasMoreElements()) + for (int[] r : map.fromShifts) { - int[] el = (int[]) e.nextElement(); - fromShifts.addElement(new int[] - { el[0], el[1] }); + fromShifts.add(new int[] { r[0], r[1] }); } } if (map.toShifts != null) { - this.toShifts = new Vector(); - Enumeration e = map.toShifts.elements(); - while (e.hasMoreElements()) + for (int[] r : map.toShifts) { - int[] el = (int[]) e.nextElement(); - toShifts.addElement(new int[] - { el[0], el[1] }); + toShifts.add(new int[] { r[0], r[1] }); } } } /** + * 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) + { + this(); + fromRange = coalesceRanges(fromRange); + toRange = coalesceRanges(toRange); + this.fromShifts = fromRange; + this.toShifts = toRange; + this.fromRatio = fromRatio; + this.toRatio = toRatio; + + fromLowest = Integer.MAX_VALUE; + fromHighest = Integer.MIN_VALUE; + for (int[] range : fromRange) + { + 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 = Integer.MIN_VALUE; + for (int[] range : toRange) + { + 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). + * + * @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; + } + 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 + */ + 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 + { + 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 * [fromFinish-fromStart+2] { toStart..toFinish mappings}} */ - public int[][] makeFromMap() + protected int[][] makeFromMap() { + // TODO not used - remove?? return posMap(fromShifts, fromRatio, toShifts, toRatio); } @@ -238,27 +427,29 @@ public class MapList * * @return int[to position]=position mapped in from */ - public int[][] makeToMap() + protected int[][] makeToMap() { + // TODO not used - remove?? return posMap(toShifts, toRatio, fromShifts, fromRatio); } /** * construct an int map for intervals in intVals * - * @param intVals + * @param shiftTo * @return int[] { from, to pos in range }, int[range.to-range.from+1] * returning mapped position */ - private int[][] posMap(Vector intVals, int ratio, Vector toIntVals, - int toRatio) + private int[][] posMap(List shiftTo, int ratio, + List shiftFrom, int toRatio) { - int iv = 0, ivSize = intVals.size(); + // TODO not used - remove?? + int iv = 0, ivSize = shiftTo.size(); if (iv >= ivSize) { return null; } - int[] intv = (int[]) intVals.elementAt(iv++); + int[] intv = shiftTo.get(iv++); int from = intv[0], to = intv[1]; if (from > to) { @@ -267,7 +458,7 @@ public class MapList } while (iv < ivSize) { - intv = (int[]) intVals.elementAt(iv++); + intv = shiftTo.get(iv++); if (intv[0] < from) { from = intv[0]; @@ -289,7 +480,7 @@ public class MapList int mp[][] = new int[to - from + 2][]; for (int i = 0; i < mp.length; i++) { - int[] m = shift(i + from, intVals, ratio, toIntVals, toRatio); + int[] m = shift(i + from, shiftTo, ratio, shiftFrom, toRatio); if (m != null) { if (i == 0) @@ -310,9 +501,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; @@ -345,6 +535,7 @@ public class MapList * shifts.insertElementAt(new int[] { pos, shift}, sidx); else * rshift[1]+=shift; } */ + /** * shift from pos to To(pos) * @@ -373,51 +564,50 @@ public class MapList /** * - * @param fromShifts + * @param shiftTo * @param fromRatio - * @param toShifts + * @param shiftFrom * @param toRatio * @return */ - private int[] shift(int pos, Vector fromShifts, int fromRatio, - Vector toShifts, int toRatio) + protected static int[] shift(int pos, List shiftTo, int fromRatio, + List shiftFrom, int toRatio) { - int[] fromCount = countPos(fromShifts, pos); + // TODO: javadoc; tests + int[] fromCount = countPos(shiftTo, pos); if (fromCount == null) { return null; } int fromRemainder = (fromCount[0] - 1) % fromRatio; int toCount = 1 + (((fromCount[0] - 1) / fromRatio) * toRatio); - int[] toPos = countToPos(toShifts, toCount); + int[] toPos = countToPos(shiftFrom, toCount); if (toPos == null) { 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] }; } /** * count how many positions pos is along the series of intervals. * - * @param intVals + * @param shiftTo * @param pos * @return number of positions or null if pos is not within intervals */ - private int[] countPos(Vector intVals, int pos) + protected static int[] countPos(List shiftTo, int pos) { - int count = 0, intv[], iv = 0, ivSize = intVals.size(); + int count = 0, intv[], iv = 0, ivSize = shiftTo.size(); while (iv < ivSize) { - intv = (int[]) intVals.elementAt(iv++); + intv = shiftTo.get(iv++); if (intv[0] <= intv[1]) { 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 { @@ -428,8 +618,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 { @@ -443,24 +632,23 @@ public class MapList /** * count out pos positions into a series of intervals and return the position * - * @param intVals + * @param shiftFrom * @param pos * @return position pos in interval set */ - private int[] countToPos(Vector intVals, int pos) + protected static int[] countToPos(List shiftFrom, int pos) { - int count = 0, diff = 0, iv = 0, ivSize = intVals.size(), intv[] = - { 0, 0 }; + int count = 0, diff = 0, iv = 0, ivSize = shiftFrom.size(); + int[] intv = { 0, 0 }; while (iv < ivSize) { - intv = (int[]) intVals.elementAt(iv++); + intv = shiftFrom.get(iv++); diff = intv[1] - intv[0]; if (diff >= 0) { if (pos <= count + 1 + diff) { - return new int[] - { pos - count - 1 + intv[0], +1 }; + return new int[] { pos - count - 1 + intv[0], +1 }; } else { @@ -471,8 +659,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 { @@ -487,69 +674,67 @@ public class MapList * find series of intervals mapping from start-end in the From map. * * @param start - * position in to map + * position mapped 'to' * @param end - * position in to map - * @return series of ranges in from map + * position mapped 'to' + * @return series of [start, end] ranges in sequence mapped 'from' */ public int[] locateInFrom(int start, int end) { // inefficient implementation int fromStart[] = shiftTo(start); - int fromEnd[] = shiftTo(end); // needs to be inclusive of end of symbol - // position - if (fromStart == null || fromEnd == null) - return null; - int iv[] = getIntervals(fromShifts, fromStart, fromEnd, fromRatio); - return iv; + // needs to be inclusive of end of symbol position + int fromEnd[] = shiftTo(end); + + return getIntervals(fromShifts, fromStart, fromEnd, fromRatio); } /** * find series of intervals mapping from start-end in the to map. * * @param start - * position in from map + * position mapped 'from' * @param end - * position in from map - * @return series of ranges in to map + * position mapped 'from' + * @return series of [start, end] ranges in sequence mapped 'to' */ public int[] locateInTo(int start, int end) { - // inefficient implementation int toStart[] = shiftFrom(start); int toEnd[] = shiftFrom(end); - if (toStart == null || toEnd == null) - return null; - int iv[] = getIntervals(toShifts, toStart, toEnd, toRatio); - return iv; + return getIntervals(toShifts, toStart, toEnd, toRatio); } /** * like shift - except returns the intervals in the given vector of shifts * which were spanned in traversing fromStart to fromEnd * - * @param fromShifts2 + * @param shiftFrom * @param fromStart * @param fromEnd * @param fromRatio2 * @return series of from,to intervals from from first position of starting * region to final position of ending region inclusive */ - private int[] getIntervals(Vector fromShifts2, int[] fromStart, - int[] fromEnd, int fromRatio2) + protected static int[] getIntervals(List shiftFrom, + int[] fromStart, int[] fromEnd, int fromRatio2) { + if (fromStart == null || fromEnd == null) + { + return null; + } int startpos, endpos; startpos = fromStart[0]; // first position in fromStart endpos = fromEnd[0]; // last position in fromEnd int endindx = (fromRatio2 - 1); // additional positions to get to last // position from endpos - int intv = 0, intvSize = fromShifts2.size(); + int intv = 0, intvSize = shiftFrom.size(); int iv[], i = 0, fs = -1, fe_s = -1, fe = -1; // containing intervals // search intervals to locate ones containing startpos and count endindx // positions on from endpos while (intv < intvSize && (fs == -1 || fe == -1)) { - iv = (int[]) fromShifts2.elementAt(intv++); + iv = shiftFrom.get(intv++); if (fe_s > -1) { endpos = iv[0]; // start counting from beginning of interval @@ -612,41 +797,44 @@ public class MapList i++; } if (fs == fe && fe == -1) + { return null; - Vector ranges = new Vector(); + } + List ranges = new ArrayList(); if (fs <= fe) { intv = fs; i = fs; // truncate initial interval - iv = (int[]) fromShifts2.elementAt(intv++); - iv = new int[] - { iv[0], iv[1] };// clone + iv = shiftFrom.get(intv++); + iv = new int[] { iv[0], iv[1] };// clone if (i == fs) + { iv[0] = startpos; + } while (i != fe) { - ranges.addElement(iv); // add initial range - iv = (int[]) fromShifts2.elementAt(intv++); // get next interval - iv = new int[] - { iv[0], iv[1] };// clone + ranges.add(iv); // add initial range + iv = shiftFrom.get(intv++); // get next interval + iv = new int[] { iv[0], iv[1] };// clone i++; } if (i == fe) + { iv[1] = endpos; - ranges.addElement(iv); // add only - or final range + } + ranges.add(iv); // add only - or final range } else { // walk from end of interval. - i = fromShifts2.size() - 1; + i = shiftFrom.size() - 1; while (i > fs) { i--; } - iv = (int[]) fromShifts2.elementAt(i); - iv = new int[] - { iv[1], iv[0] };// reverse and clone + iv = shiftFrom.get(i); + iv = new int[] { iv[1], iv[0] };// reverse and clone // truncate initial interval if (i == fs) { @@ -654,17 +842,16 @@ public class MapList } while (--i != fe) { // fix apparent logic bug when fe==-1 - ranges.addElement(iv); // add (truncated) reversed interval - iv = (int[]) fromShifts2.elementAt(i); - iv = new int[] - { iv[1], iv[0] }; // reverse and clone + ranges.add(iv); // add (truncated) reversed interval + iv = shiftFrom.get(i); + iv = new int[] { iv[1], iv[0] }; // reverse and clone } if (i == fe) { // interval is already reversed iv[1] = endpos; } - ranges.addElement(iv); // add only - or final range + ranges.add(iv); // add only - or final range } // create array of start end intervals. int[] range = null; @@ -676,10 +863,10 @@ public class MapList i = 0; while (intv < intvSize) { - iv = (int[]) ranges.elementAt(intv); + iv = ranges.get(intv); range[i++] = iv[0]; range[i++] = iv[1]; - ranges.setElementAt(null, intv++); // remove + ranges.set(intv++, null); // remove } } return range; @@ -694,6 +881,7 @@ public class MapList */ public int getToPosition(int mpos) { + // TODO not used - remove?? int[] mp = shiftTo(mpos); if (mp != null) { @@ -715,8 +903,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; } @@ -730,6 +917,7 @@ public class MapList */ public int getMappedPosition(int pos) { + // TODO not used - remove?? int[] mp = shiftFrom(pos); if (mp != null) { @@ -740,264 +928,191 @@ public class MapList public int[] getMappedWord(int pos) { + // TODO not used - remove?? 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; } /** - * test routine. not incremental. * - * @param ml - * @param fromS - * @param fromE + * @return a MapList whose From range is this maplist's To Range, and vice + * versa + */ + public MapList getInverse() + { + return new MapList(getToRanges(), getFromRanges(), getToRatio(), + getFromRatio()); + } + + /** + * test for containment rather than equivalence to another mapping + * + * @param map + * to be tested for containment + * @return true if local or mapped range map contains or is contained by this + * mapping */ - public static void testMap(MapList ml, int fromS, int fromE) + public boolean containsEither(boolean local, MapList map) { - for (int from = 1; from <= 25; from++) + // TODO not used - remove? + if (local) { - int[] too = ml.shiftFrom(from); - System.out.print("ShiftFrom(" + from + ")=="); - if (too == null) - { - System.out.print("NaN\n"); - } - else - { - System.out.print(too[0] + " % " + too[1] + " (" + too[2] + ")"); - System.out.print("\t+--+\t"); - int[] toofrom = ml.shiftTo(too[0]); - if (toofrom != null) - { - if (toofrom[0] != from) - { - System.err.println("Mapping not reflexive:" + from + " " - + too[0] + "->" + toofrom[0]); - } - System.out.println("ShiftTo(" + too[0] + ")==" + toofrom[0] - + " % " + toofrom[1] + " (" + toofrom[2] + ")"); - } - else - { - System.out.println("ShiftTo(" + too[0] + ")==" - + "NaN! - not Bijective Mapping!"); - } - } + return ((getFromLowest() >= map.getFromLowest() && getFromHighest() <= map + .getFromHighest()) || (getFromLowest() <= map.getFromLowest() && getFromHighest() >= map + .getFromHighest())); } - int mmap[][] = ml.makeFromMap(); - System.out.println("FromMap : (" + mmap[0][0] + " " + mmap[0][1] + " " - + mmap[0][2] + " " + mmap[0][3] + " "); - for (int i = 1; i <= mmap[1].length; i++) + else { - if (mmap[1][i - 1] == -1) - { - System.out.print(i + "=XXX"); + return ((getToLowest() >= map.getToLowest() && getToHighest() <= map + .getToHighest()) || (getToLowest() <= map.getToLowest() && getToHighest() >= map + .getToHighest())); + } + } - } - else - { - System.out.print(i + "=" + (mmap[0][2] + mmap[1][i - 1])); - } - if (i % 20 == 0) - { - System.out.print("\n"); - } - else - { - System.out.print(","); - } + /** + * 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)); } - // test range function - System.out.print("\nTest locateInFrom\n"); + sb.append(" ] "); + sb.append(fromRatio).append(":").append(toRatio); + sb.append(" to ["); + for (int[] shift : toShifts) { - int f = mmap[0][2], t = mmap[0][3]; - while (f <= t) - { - System.out.println("Range " + f + " to " + t); - int rng[] = ml.locateInFrom(f, t); - if (rng != null) - { - for (int i = 0; i < rng.length; i++) - { - System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";")); - } - } - else - { - System.out.println("No range!"); - } - System.out.print("\nReversed\n"); - rng = ml.locateInFrom(t, f); - if (rng != null) - { - for (int i = 0; i < rng.length; i++) - { - System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";")); - } - } - else - { - System.out.println("No range!"); - } - System.out.print("\n"); - f++; - t--; - } + sb.append(" ").append(Arrays.toString(shift)); } - System.out.print("\n"); - mmap = ml.makeToMap(); - System.out.println("ToMap : (" + mmap[0][0] + " " + mmap[0][1] + " " - + mmap[0][2] + " " + mmap[0][3] + " "); - for (int i = 1; i <= mmap[1].length; i++) + 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)) { - if (mmap[1][i - 1] == -1) - { - System.out.print(i + "=XXX"); + 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); - } - else - { - System.out.print(i + "=" + (mmap[0][2] + mmap[1][i - 1])); - } - if (i % 20 == 0) - { - System.out.print("\n"); - } - else - { - System.out.print(","); - } + for (int[] range : map.getFromRanges()) + { + addRange(range, fromShifts); } - System.out.print("\n"); - // test range function - System.out.print("\nTest locateInTo\n"); + for (int[] range : map.getToRanges()) { - 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 < rng.length; i++) - { - System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";")); - } - } - else - { - System.out.println("No range!"); - } - System.out.print("\nReversed\n"); - rng = ml.locateInTo(t, f); - if (rng != null) - { - for (int i = 0; i < rng.length; i++) - { - System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";")); - } - } - else - { - System.out.println("No range!"); - } - f++; - t--; - System.out.print("\n"); - } - } - - } - - public static void main(String argv[]) - { - 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); - MapList mldna = new MapList(new int[] - { 2, 2, 6, 8, 12, 16 }, new int[] - { 1, 3 }, 3, 1); - int[] frm = mldna.locateInFrom(1, 1); - testLocateFrom(mldna, 1, 1, new int[] - { 2, 2, 6, 7 }); - MapList.testMap(mldna, 1, 3); - /* - * 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! + addRange(range, toShifts); + } } - private static void testLocateFrom(MapList mldna, int i, int j, int[] ks) + /** + * 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) { - int[] frm = mldna.locateInFrom(i, j); - if (frm == ks || java.util.Arrays.equals(frm, ks)) + /* + * list is empty - add to it! + */ + if (addTo.size() == 0) { - System.out.println("Success test locate from " + i + " to " + j); + addTo.add(range); + return; } - else + + 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]) { - System.err.println("Failed test locate from " + i + " to " + j); - for (int c = 0; c < frm.length; c++) - { - System.err.print(frm[c] + ((c % 2 == 0) ? "," : ";")); - } - System.err.println("Expected"); - for (int c = 0; c < ks.length; c++) - { - System.err.print(ks[c] + ((c % 2 == 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 a MapList whose From range is this maplist's To Range, and vice - * versa + * @return */ - public MapList getInverse() + public boolean isFromForwardStrand() { - return new MapList(getToRanges(), getFromRanges(), getToRatio(), - getFromRatio()); + boolean forwardStrand = true; + for (int[] range : getFromRanges()) + { + if (range[1] > range[0]) + { + break; // forward strand confirmed + } + else if (range[1] < range[0]) + { + forwardStrand = false; + break; // reverse strand confirmed + } + } + return forwardStrand; } /** - * test for containment rather than equivalence to another mapping * - * @param map - * to be tested for containment - * @return true if local or mapped range map contains or is contained by this - * mapping + * @return true if from, or to is a three to 1 mapping */ - public boolean containsEither(boolean local, MapList map) + public boolean isTripletMap() { - if (local) - { - 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 (toRatio == 3 && fromRatio == 1) + || (fromRatio == 3 && toRatio == 1); } + }