2 * Jalview - A Sequence Alignment Editor and Viewer (Version 2.7)
3 * Copyright (C) 2011 J Procter, AM Waterhouse, J Engelhardt, LM Lui, G Barton, M Clamp, S Searle
5 * This file is part of Jalview.
7 * Jalview is free software: you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
11 * Jalview is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty
13 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
14 * PURPOSE. See the GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License along with Jalview. If not, see <http://www.gnu.org/licenses/>.
23 * MapList Simple way of bijectively mapping a non-contiguous linear range to
24 * another non-contiguous linear range Use at your own risk! TODO: efficient
25 * implementation of private posMap method TODO: test/ensure that sense of from
26 * and to ratio start position is conserved (codon start position recovery)
27 * TODO: optimize to use int[][] arrays rather than vectors.
34 * @see java.lang.Object#equals(java.lang.Object)
36 public boolean equals(MapList obj)
40 if (obj != null && obj.fromRatio == fromRatio && obj.toRatio == toRatio
41 && obj.fromShifts != null && obj.toShifts != null)
43 int i, iSize = fromShifts.size(), j, jSize = obj.fromShifts.size();
46 for (i = 0, iSize = fromShifts.size(), j = 0, jSize = obj.fromShifts
49 int[] mi = (int[]) fromShifts.elementAt(i++);
50 int[] mj = (int[]) obj.fromShifts.elementAt(j++);
51 if (mi[0] != mj[0] || mi[1] != mj[1])
54 iSize = toShifts.size();
55 jSize = obj.toShifts.size();
58 for (i = 0, j = 0; i < iSize;)
60 int[] mi = (int[]) toShifts.elementAt(i++);
61 int[] mj = (int[]) obj.toShifts.elementAt(j++);
62 if (mi[0] != mj[0] || mi[1] != mj[1])
70 public Vector fromShifts;
72 public Vector toShifts;
74 int fromRatio; // number of steps in fromShifts to one toRatio unit
76 int toRatio; // number of steps in toShifts to one fromRatio
80 * @return series of intervals mapped in from
82 public int[] getFromRanges()
84 return getRanges(fromShifts);
87 public int[] getToRanges()
89 return getRanges(toShifts);
92 private int[] getRanges(Vector shifts)
94 int[] rnges = new int[2 * shifts.size()];
95 Enumeration e = shifts.elements();
97 while (e.hasMoreElements())
99 int r[] = (int[]) e.nextElement();
107 * lowest and highest value in the from Map
109 int[] fromRange = null;
112 * lowest and highest value in the to Map
114 int[] toRange = null;
118 * @return length of mapped phrase in from
120 public int getFromRatio()
127 * @return length of mapped phrase in to
129 public int getToRatio()
134 public int getFromLowest()
139 public int getFromHighest()
144 public int getToLowest()
149 public int getToHighest()
154 private void ensureRange(int[] limits, int pos)
162 public MapList(int from[], int to[], int fromRatio, int toRatio)
164 fromRange = new int[]
165 { from[0], from[1] };
169 fromShifts = new Vector();
170 for (int i = 0; i < from.length; i += 2)
172 ensureRange(fromRange, from[i]);
173 ensureRange(fromRange, from[i + 1]);
175 fromShifts.addElement(new int[]
176 { from[i], from[i + 1] });
178 toShifts = new Vector();
179 for (int i = 0; i < to.length; i += 2)
181 ensureRange(toRange, to[i]);
182 ensureRange(toRange, to[i + 1]);
183 toShifts.addElement(new int[]
184 { to[i], to[i + 1] });
186 this.fromRatio = fromRatio;
187 this.toRatio = toRatio;
190 public MapList(MapList map)
192 this.fromRange = new int[]
193 { map.fromRange[0], map.fromRange[1] };
194 this.toRange = new int[]
195 { map.toRange[0], map.toRange[1] };
196 this.fromRatio = map.fromRatio;
197 this.toRatio = map.toRatio;
198 if (map.fromShifts != null)
200 this.fromShifts = new Vector();
201 Enumeration e = map.fromShifts.elements();
202 while (e.hasMoreElements())
204 int[] el = (int[]) e.nextElement();
205 fromShifts.addElement(new int[]
209 if (map.toShifts != null)
211 this.toShifts = new Vector();
212 Enumeration e = map.toShifts.elements();
213 while (e.hasMoreElements())
215 int[] el = (int[]) e.nextElement();
216 toShifts.addElement(new int[]
223 * get all mapped positions from 'from' to 'to'
225 * @return int[][] { int[] { fromStart, fromFinish, toStart, toFinish }, int
226 * [fromFinish-fromStart+2] { toStart..toFinish mappings}}
228 public int[][] makeFromMap()
230 return posMap(fromShifts, fromRatio, toShifts, toRatio);
234 * get all mapped positions from 'to' to 'from'
236 * @return int[to position]=position mapped in from
238 public int[][] makeToMap()
240 return posMap(toShifts, toRatio, fromShifts, fromRatio);
244 * construct an int map for intervals in intVals
247 * @return int[] { from, to pos in range }, int[range.to-range.from+1]
248 * returning mapped position
250 private int[][] posMap(Vector intVals, int ratio, Vector toIntVals,
253 int iv = 0, ivSize = intVals.size();
258 int[] intv = (int[]) intVals.elementAt(iv++);
259 int from = intv[0], to = intv[1];
267 intv = (int[]) intVals.elementAt(iv++);
286 int mp[][] = new int[to - from + 2][];
287 for (int i = 0; i < mp.length; i++)
289 int[] m = shift(i + from, intVals, ratio, toIntVals, toRatio);
310 int[][] map = new int[][]
312 { from, to, tF, tT }, new int[to - from + 2] };
317 for (int i = 0; i < mp.length; i++)
321 map[1][i] = mp[i][0] - tF;
325 map[1][i] = -1; // indicates an out of range mapping
335 * start position for shift (in original reference frame)
339 * public void addShift(int pos, int shift) { int sidx = 0; int[]
340 * rshift=null; while (sidx<shifts.size() && (rshift=(int[])
341 * shifts.elementAt(sidx))[0]<pos) sidx++; if (sidx==shifts.size())
342 * shifts.insertElementAt(new int[] { pos, shift}, sidx); else
343 * rshift[1]+=shift; }
346 * shift from pos to To(pos)
350 * @return int shifted position in To, frameshift in From, direction of mapped
353 public int[] shiftFrom(int pos)
355 return shift(pos, fromShifts, fromRatio, toShifts, toRatio);
359 * inverse of shiftFrom - maps pos in To to a position in From
363 * @return shifted position in From, frameshift in To, direction of mapped
366 public int[] shiftTo(int pos)
368 return shift(pos, toShifts, toRatio, fromShifts, fromRatio);
379 private int[] shift(int pos, Vector fromShifts, int fromRatio,
380 Vector toShifts, int toRatio)
382 int[] fromCount = countPos(fromShifts, pos);
383 if (fromCount == null)
387 int fromRemainder = (fromCount[0] - 1) % fromRatio;
388 int toCount = 1 + (((fromCount[0] - 1) / fromRatio) * toRatio);
389 int[] toPos = countToPos(toShifts, toCount);
392 return null; // throw new Error("Bad Mapping!");
394 // System.out.println(fromCount[0]+" "+fromCount[1]+" "+toCount);
396 { toPos[0], fromRemainder, toPos[1] };
400 * count how many positions pos is along the series of intervals.
404 * @return number of positions or null if pos is not within intervals
406 private int[] countPos(Vector intVals, int pos)
408 int count = 0, intv[], iv = 0, ivSize = intVals.size();
411 intv = (int[]) intVals.elementAt(iv++);
412 if (intv[0] <= intv[1])
414 if (pos >= intv[0] && pos <= intv[1])
417 { count + pos - intv[0] + 1, +1 };
421 count += intv[1] - intv[0] + 1;
426 if (pos >= intv[1] && pos <= intv[0])
429 { count + intv[0] - pos + 1, -1 };
433 count += intv[0] - intv[1] + 1;
441 * count out pos positions into a series of intervals and return the position
445 * @return position pos in interval set
447 private int[] countToPos(Vector intVals, int pos)
449 int count = 0, diff = 0, iv = 0, ivSize = intVals.size(), intv[] =
453 intv = (int[]) intVals.elementAt(iv++);
454 diff = intv[1] - intv[0];
457 if (pos <= count + 1 + diff)
460 { pos - count - 1 + intv[0], +1 };
469 if (pos <= count + 1 - diff)
472 { intv[0] - (pos - count - 1), -1 };
480 return null;// (diff<0) ? (intv[1]-1) : (intv[0]+1);
484 * find series of intervals mapping from start-end in the From map.
490 * @return series of ranges in from map
492 public int[] locateInFrom(int start, int end)
494 // inefficient implementation
495 int fromStart[] = shiftTo(start);
496 int fromEnd[] = shiftTo(end); // needs to be inclusive of end of symbol
498 if (fromStart == null || fromEnd == null)
500 int iv[] = getIntervals(fromShifts, fromStart, fromEnd, fromRatio);
505 * find series of intervals mapping from start-end in the to map.
508 * position in from map
510 * position in from map
511 * @return series of ranges in to map
513 public int[] locateInTo(int start, int end)
515 // inefficient implementation
516 int toStart[] = shiftFrom(start);
517 int toEnd[] = shiftFrom(end);
518 if (toStart == null || toEnd == null)
520 int iv[] = getIntervals(toShifts, toStart, toEnd, toRatio);
525 * like shift - except returns the intervals in the given vector of shifts
526 * which were spanned in traversing fromStart to fromEnd
532 * @return series of from,to intervals from from first position of starting
533 * region to final position of ending region inclusive
535 private int[] getIntervals(Vector fromShifts2, int[] fromStart,
536 int[] fromEnd, int fromRatio2)
538 int startpos, endpos;
539 startpos = fromStart[0]; // first position in fromStart
540 endpos = fromEnd[0]; // last position in fromEnd
541 int endindx = (fromRatio2 - 1); // additional positions to get to last
542 // position from endpos
543 int intv = 0, intvSize = fromShifts2.size();
544 int iv[], i = 0, fs = -1, fe_s = -1, fe = -1; // containing intervals
545 // search intervals to locate ones containing startpos and count endindx
546 // positions on from endpos
547 while (intv < intvSize && (fs == -1 || fe == -1))
549 iv = (int[]) fromShifts2.elementAt(intv++);
552 endpos = iv[0]; // start counting from beginning of interval
553 endindx--; // inclusive of endpos
557 if (fs == -1 && startpos >= iv[0] && startpos <= iv[1])
561 if (endpos >= iv[0] && endpos <= iv[1])
569 if (endpos + endindx <= iv[1])
572 endpos = endpos + endindx; // end of end token is within this
577 endindx -= iv[1] - endpos; // skip all this interval too
584 if (fs == -1 && startpos <= iv[0] && startpos >= iv[1])
588 if (endpos <= iv[0] && endpos >= iv[1])
596 if (endpos - endindx >= iv[1])
599 endpos = endpos - endindx; // end of end token is within this
604 endindx -= endpos - iv[1]; // skip all this interval too
611 if (fs == fe && fe == -1)
613 Vector ranges = new Vector();
618 // truncate initial interval
619 iv = (int[]) fromShifts2.elementAt(intv++);
621 { iv[0], iv[1] };// clone
626 ranges.addElement(iv); // add initial range
627 iv = (int[]) fromShifts2.elementAt(intv++); // get next interval
629 { iv[0], iv[1] };// clone
634 ranges.addElement(iv); // add only - or final range
638 // walk from end of interval.
639 i = fromShifts2.size() - 1;
644 iv = (int[]) fromShifts2.elementAt(i);
646 { iv[1], iv[0] };// reverse and clone
647 // truncate initial interval
653 { // fix apparent logic bug when fe==-1
654 ranges.addElement(iv); // add (truncated) reversed interval
655 iv = (int[]) fromShifts2.elementAt(i);
657 { iv[1], iv[0] }; // reverse and clone
661 // interval is already reversed
664 ranges.addElement(iv); // add only - or final range
666 // create array of start end intervals.
668 if (ranges != null && ranges.size() > 0)
670 range = new int[ranges.size() * 2];
672 intvSize = ranges.size();
674 while (intv < intvSize)
676 iv = (int[]) ranges.elementAt(intv);
679 ranges.setElementAt(null, intv++); // remove
686 * get the 'initial' position of mpos in To
690 * @return position of first word in to reference frame
692 public int getToPosition(int mpos)
694 int[] mp = shiftTo(mpos);
703 * get range of positions in To frame for the mpos word in From
707 * @return null or int[] first position in To for mpos, last position in to
710 public int[] getToWord(int mpos)
712 int[] mp = shiftTo(mpos);
716 { mp[0], mp[0] + mp[2] * (getFromRatio() - 1) };
722 * get From position in the associated reference frame for position pos in the
723 * associated sequence.
728 public int getMappedPosition(int pos)
730 int[] mp = shiftFrom(pos);
738 public int[] getMappedWord(int pos)
740 int[] mp = shiftFrom(pos);
744 { mp[0], mp[0] + mp[2] * (getToRatio() - 1) };
750 * test routine. not incremental.
756 public static void testMap(MapList ml, int fromS, int fromE)
758 for (int from = 1; from <= 25; from++)
760 int[] too = ml.shiftFrom(from);
761 System.out.print("ShiftFrom(" + from + ")==");
764 System.out.print("NaN\n");
768 System.out.print(too[0] + " % " + too[1] + " (" + too[2] + ")");
769 System.out.print("\t+--+\t");
770 int[] toofrom = ml.shiftTo(too[0]);
773 if (toofrom[0] != from)
775 System.err.println("Mapping not reflexive:" + from + " "
776 + too[0] + "->" + toofrom[0]);
778 System.out.println("ShiftTo(" + too[0] + ")==" + toofrom[0]
779 + " % " + toofrom[1] + " (" + toofrom[2] + ")");
783 System.out.println("ShiftTo(" + too[0] + ")=="
784 + "NaN! - not Bijective Mapping!");
788 int mmap[][] = ml.makeFromMap();
789 System.out.println("FromMap : (" + mmap[0][0] + " " + mmap[0][1] + " "
790 + mmap[0][2] + " " + mmap[0][3] + " ");
791 for (int i = 1; i <= mmap[1].length; i++)
793 if (mmap[1][i - 1] == -1)
795 System.out.print(i + "=XXX");
800 System.out.print(i + "=" + (mmap[0][2] + mmap[1][i - 1]));
804 System.out.print("\n");
808 System.out.print(",");
811 // test range function
812 System.out.print("\nTest locateInFrom\n");
814 int f = mmap[0][2], t = mmap[0][3];
817 System.out.println("Range " + f + " to " + t);
818 int rng[] = ml.locateInFrom(f, t);
821 for (int i = 0; i < rng.length; i++)
823 System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
828 System.out.println("No range!");
830 System.out.print("\nReversed\n");
831 rng = ml.locateInFrom(t, f);
834 for (int i = 0; i < rng.length; i++)
836 System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
841 System.out.println("No range!");
843 System.out.print("\n");
848 System.out.print("\n");
849 mmap = ml.makeToMap();
850 System.out.println("ToMap : (" + mmap[0][0] + " " + mmap[0][1] + " "
851 + mmap[0][2] + " " + mmap[0][3] + " ");
852 for (int i = 1; i <= mmap[1].length; i++)
854 if (mmap[1][i - 1] == -1)
856 System.out.print(i + "=XXX");
861 System.out.print(i + "=" + (mmap[0][2] + mmap[1][i - 1]));
865 System.out.print("\n");
869 System.out.print(",");
872 System.out.print("\n");
873 // test range function
874 System.out.print("\nTest locateInTo\n");
876 int f = mmap[0][2], t = mmap[0][3];
879 System.out.println("Range " + f + " to " + t);
880 int rng[] = ml.locateInTo(f, t);
883 for (int i = 0; i < rng.length; i++)
885 System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
890 System.out.println("No range!");
892 System.out.print("\nReversed\n");
893 rng = ml.locateInTo(t, f);
896 for (int i = 0; i < rng.length; i++)
898 System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
903 System.out.println("No range!");
907 System.out.print("\n");
913 public static void main(String argv[])
915 MapList ml = new MapList(new int[]
916 { 1, 5, 10, 15, 25, 20 }, new int[]
918 MapList ml1 = new MapList(new int[]
919 { 1, 3, 17, 4 }, new int[]
921 MapList ml2 = new MapList(new int[]
924 // test internal consistency
925 int to[] = new int[51];
926 MapList.testMap(ml, 1, 60);
927 MapList mldna = new MapList(new int[]
928 { 2, 2, 6, 8, 12, 16 }, new int[]
930 int[] frm = mldna.locateInFrom(1, 1);
931 testLocateFrom(mldna, 1, 1, new int[]
933 MapList.testMap(mldna, 1, 3);
935 * for (int from=1; from<=51; from++) { int[] too=ml.shiftTo(from); int[]
936 * toofrom=ml.shiftFrom(too[0]);
937 * System.out.println("ShiftFrom("+from+")=="+too[0]+" %
938 * "+too[1]+"\t+-+\tShiftTo("+too[0]+")=="+toofrom[0]+" % "+toofrom[1]); }
940 System.out.print("Success?\n"); // if we get here - something must be
944 private static void testLocateFrom(MapList mldna, int i, int j, int[] ks)
946 int[] frm = mldna.locateInFrom(i, j);
947 if (frm == ks || java.util.Arrays.equals(frm, ks))
949 System.out.println("Success test locate from " + i + " to " + j);
953 System.err.println("Failed test locate from " + i + " to " + j);
954 for (int c = 0; c < frm.length; c++)
956 System.err.print(frm[c] + ((c % 2 == 0) ? "," : ";"));
958 System.err.println("Expected");
959 for (int c = 0; c < ks.length; c++)
961 System.err.print(ks[c] + ((c % 2 == 0) ? "," : ";"));
968 * @return a MapList whose From range is this maplist's To Range, and vice
971 public MapList getInverse()
973 return new MapList(getToRanges(), getFromRanges(), getToRatio(),
978 * test for containment rather than equivalence to another mapping
981 * to be tested for containment
982 * @return true if local or mapped range map contains or is contained by this
985 public boolean containsEither(boolean local, MapList map)
989 return ((getFromLowest() >= map.getFromLowest() && getFromHighest() <= map
990 .getFromHighest()) || (getFromLowest() <= map.getFromLowest() && getFromHighest() >= map
995 return ((getToLowest() >= map.getToLowest() && getToHighest() <= map
996 .getToHighest()) || (getToLowest() <= map.getToLowest() && getToHighest() >= map