2 * Jalview - A Sequence Alignment Editor and Viewer
3 * Copyright (C) 2007 AM Waterhouse, J Procter, G Barton, M Clamp, S Searle
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License
7 * as published by the Free Software Foundation; either version 2
8 * of the License, or (at your option) any later version.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
24 * MapList Simple way of bijectively mapping a non-contiguous linear range to
25 * another non-contiguous linear range Use at your own risk! TODO: efficient
26 * implementation of private posMap method TODO: test/ensure that sense of from
27 * and to ratio start position is conserved (codon start position recovery)
28 * TODO: optimize to use int[][] arrays rather than vectors.
35 * @see java.lang.Object#equals(java.lang.Object)
37 public boolean equals(MapList obj)
41 if (obj != null && obj.fromRatio == fromRatio && obj.toRatio == toRatio
42 && obj.fromShifts != null && obj.toShifts != null)
44 int i, iSize = fromShifts.size(), j, jSize = obj.fromShifts.size();
47 for (i = 0, iSize = fromShifts.size(), j = 0, jSize = obj.fromShifts
50 int[] mi = (int[]) fromShifts.elementAt(i++);
51 int[] mj = (int[]) obj.fromShifts.elementAt(j++);
52 if (mi[0] != mj[0] || mi[1] != mj[1])
55 iSize = toShifts.size();
56 jSize = obj.toShifts.size();
59 for (i = 0, j = 0; i < iSize;)
61 int[] mi = (int[]) toShifts.elementAt(i++);
62 int[] mj = (int[]) obj.toShifts.elementAt(j++);
63 if (mi[0] != mj[0] || mi[1] != mj[1])
71 public Vector fromShifts;
73 public Vector toShifts;
75 int fromRatio; // number of steps in fromShifts to one toRatio unit
77 int toRatio; // number of steps in toShifts to one fromRatio
81 * @return series of intervals mapped in from
83 public int[] getFromRanges()
85 return getRanges(fromShifts);
88 public int[] getToRanges()
90 return getRanges(toShifts);
93 private int[] getRanges(Vector shifts)
95 int[] rnges = new int[2 * shifts.size()];
96 Enumeration e = shifts.elements();
98 while (e.hasMoreElements())
100 int r[] = (int[]) e.nextElement();
108 * lowest and highest value in the from Map
110 int[] fromRange = null;
113 * lowest and highest value in the to Map
115 int[] toRange = null;
119 * @return length of mapped phrase in from
121 public int getFromRatio()
128 * @return length of mapped phrase in to
130 public int getToRatio()
135 public int getFromLowest()
140 public int getFromHighest()
145 public int getToLowest()
150 public int getToHighest()
155 private void ensureRange(int[] limits, int pos)
163 public MapList(int from[], int to[], int fromRatio, int toRatio)
165 fromRange = new int[]
166 { from[0], from[1] };
170 fromShifts = new Vector();
171 for (int i = 0; i < from.length; i += 2)
173 ensureRange(fromRange, from[i]);
174 ensureRange(fromRange, from[i + 1]);
176 fromShifts.addElement(new int[]
177 { from[i], from[i + 1] });
179 toShifts = new Vector();
180 for (int i = 0; i < to.length; i += 2)
182 ensureRange(toRange, to[i]);
183 ensureRange(toRange, to[i + 1]);
184 toShifts.addElement(new int[]
185 { to[i], to[i + 1] });
187 this.fromRatio = fromRatio;
188 this.toRatio = toRatio;
191 public MapList(MapList map)
193 this.fromRange = new int[]
194 { map.fromRange[0], map.fromRange[1] };
195 this.toRange = new int[]
196 { map.toRange[0], map.toRange[1] };
197 this.fromRatio = map.fromRatio;
198 this.toRatio = map.toRatio;
199 if (map.fromShifts != null)
201 this.fromShifts = new Vector();
202 Enumeration e = map.fromShifts.elements();
203 while (e.hasMoreElements())
205 int[] el = (int[]) e.nextElement();
206 fromShifts.addElement(new int[]
210 if (map.toShifts != null)
212 this.toShifts = new Vector();
213 Enumeration e = map.toShifts.elements();
214 while (e.hasMoreElements())
216 int[] el = (int[]) e.nextElement();
217 toShifts.addElement(new int[]
224 * get all mapped positions from 'from' to 'to'
226 * @return int[][] { int[] { fromStart, fromFinish, toStart, toFinish }, int
227 * [fromFinish-fromStart+2] { toStart..toFinish mappings}}
229 public int[][] makeFromMap()
231 return posMap(fromShifts, fromRatio, toShifts, toRatio);
235 * get all mapped positions from 'to' to 'from'
237 * @return int[to position]=position mapped in from
239 public int[][] makeToMap()
241 return posMap(toShifts, toRatio, fromShifts, fromRatio);
245 * construct an int map for intervals in intVals
248 * @return int[] { from, to pos in range }, int[range.to-range.from+1]
249 * returning mapped position
251 private int[][] posMap(Vector intVals, int ratio, Vector toIntVals,
254 int iv = 0, ivSize = intVals.size();
259 int[] intv = (int[]) intVals.elementAt(iv++);
260 int from = intv[0], to = intv[1];
268 intv = (int[]) intVals.elementAt(iv++);
287 int mp[][] = new int[to - from + 2][];
288 for (int i = 0; i < mp.length; i++)
290 int[] m = shift(i + from, intVals, ratio, toIntVals, toRatio);
311 int[][] map = new int[][]
313 { from, to, tF, tT }, new int[to - from + 2] };
318 for (int i = 0; i < mp.length; i++)
322 map[1][i] = mp[i][0] - tF;
326 map[1][i] = -1; // indicates an out of range mapping
336 * start position for shift (in original reference frame)
340 * public void addShift(int pos, int shift) { int sidx = 0; int[] rshift=null;
341 * while (sidx<shifts.size() && (rshift=(int[]) shifts.elementAt(sidx))[0]<pos)
342 * sidx++; if (sidx==shifts.size()) shifts.insertElementAt(new int[] { pos,
343 * shift}, sidx); else 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 interval
576 endindx -= iv[1] - endpos; // skip all this interval too
583 if (fs == -1 && startpos <= iv[0] && startpos >= iv[1])
587 if (endpos <= iv[0] && endpos >= iv[1])
595 if (endpos - endindx >= iv[1])
598 endpos = endpos - endindx; // end of end token is within this interval
602 endindx -= endpos-iv[1]; // skip all this interval too
609 if (fs == fe && fe == -1)
611 Vector ranges = new Vector();
616 // truncate initial interval
617 iv = (int[]) fromShifts2.elementAt(intv++);
619 { iv[0], iv[1] };// clone
624 ranges.addElement(iv); // add initial range
625 iv = (int[]) fromShifts2.elementAt(intv++); // get next interval
627 { iv[0], iv[1] };// clone
632 ranges.addElement(iv); // add only - or final range
636 // walk from end of interval.
637 i = fromShifts2.size() - 1;
642 iv = (int[]) fromShifts2.elementAt(i);
644 { iv[1], iv[0] };// reverse and clone
645 // truncate initial interval
651 { // fix apparent logic bug when fe==-1
652 ranges.addElement(iv); // add (truncated) reversed interval
653 iv = (int[]) fromShifts2.elementAt(i);
655 { iv[1], iv[0] }; // reverse and clone
659 // interval is already reversed
662 ranges.addElement(iv); // add only - or final range
664 // create array of start end intervals.
666 if (ranges != null && ranges.size() > 0)
668 range = new int[ranges.size() * 2];
670 intvSize = ranges.size();
672 while (intv < intvSize)
674 iv = (int[]) ranges.elementAt(intv);
677 ranges.setElementAt(null, intv++); // remove
684 * get the 'initial' position of mpos in To
688 * @return position of first word in to reference frame
690 public int getToPosition(int mpos)
692 int[] mp = shiftTo(mpos);
701 * get range of positions in To frame for the mpos word in From
705 * @return null or int[] first position in To for mpos, last position in to
708 public int[] getToWord(int mpos)
710 int[] mp = shiftTo(mpos);
714 { mp[0], mp[0] + mp[2] * (getFromRatio() - 1) };
720 * get From position in the associated reference frame for position pos in the
721 * associated sequence.
726 public int getMappedPosition(int pos)
728 int[] mp = shiftFrom(pos);
736 public int[] getMappedWord(int pos)
738 int[] mp = shiftFrom(pos);
742 { mp[0], mp[0] + mp[2] * (getToRatio() - 1) };
748 * test routine. not incremental.
754 public static void testMap(MapList ml, int fromS, int fromE)
756 for (int from = 1; from <= 25; from++)
758 int[] too = ml.shiftFrom(from);
759 System.out.print("ShiftFrom(" + from + ")==");
762 System.out.print("NaN\n");
766 System.out.print(too[0] + " % " + too[1] + " (" + too[2] + ")");
767 System.out.print("\t+--+\t");
768 int[] toofrom = ml.shiftTo(too[0]);
771 if (toofrom[0] != from)
773 System.err.println("Mapping not reflexive:" + from + " "
774 + too[0] + "->" + toofrom[0]);
776 System.out.println("ShiftTo(" + too[0] + ")==" + toofrom[0]
777 + " % " + toofrom[1] + " (" + toofrom[2] + ")");
781 System.out.println("ShiftTo(" + too[0] + ")=="
782 + "NaN! - not Bijective Mapping!");
786 int mmap[][] = ml.makeFromMap();
787 System.out.println("FromMap : (" + mmap[0][0] + " " + mmap[0][1] + " "
788 + mmap[0][2] + " " + mmap[0][3] + " ");
789 for (int i = 1; i <= mmap[1].length; i++)
791 if (mmap[1][i - 1] == -1)
793 System.out.print(i + "=XXX");
798 System.out.print(i + "=" + (mmap[0][2] + mmap[1][i - 1]));
802 System.out.print("\n");
806 System.out.print(",");
809 // test range function
810 System.out.print("\nTest locateInFrom\n");
812 int f = mmap[0][2], t = mmap[0][3];
815 System.out.println("Range " + f + " to " + t);
816 int rng[] = ml.locateInFrom(f, t);
819 for (int i = 0; i < rng.length; i++)
821 System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
826 System.out.println("No range!");
828 System.out.print("\nReversed\n");
829 rng = ml.locateInFrom(t, f);
832 for (int i = 0; i < rng.length; i++)
834 System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
839 System.out.println("No range!");
841 System.out.print("\n");
846 System.out.print("\n");
847 mmap = ml.makeToMap();
848 System.out.println("ToMap : (" + mmap[0][0] + " " + mmap[0][1] + " "
849 + mmap[0][2] + " " + mmap[0][3] + " ");
850 for (int i = 1; i <= mmap[1].length; i++)
852 if (mmap[1][i - 1] == -1)
854 System.out.print(i + "=XXX");
859 System.out.print(i + "=" + (mmap[0][2] + mmap[1][i - 1]));
863 System.out.print("\n");
867 System.out.print(",");
870 System.out.print("\n");
871 // test range function
872 System.out.print("\nTest locateInTo\n");
874 int f = mmap[0][2], t = mmap[0][3];
877 System.out.println("Range " + f + " to " + t);
878 int rng[] = ml.locateInTo(f, t);
881 for (int i = 0; i < rng.length; i++)
883 System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
888 System.out.println("No range!");
890 System.out.print("\nReversed\n");
891 rng = ml.locateInTo(t, f);
894 for (int i = 0; i < rng.length; i++)
896 System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
901 System.out.println("No range!");
905 System.out.print("\n");
911 public static void main(String argv[])
913 MapList ml = new MapList(new int[]
914 { 1, 5, 10, 15, 25, 20 }, new int[]
916 MapList ml1 = new MapList(new int[]
917 { 1, 3, 17, 4 }, new int[]
919 MapList ml2 = new MapList(new int[]
922 // test internal consistency
923 int to[] = new int[51];
924 MapList.testMap(ml, 1, 60);
925 MapList mldna = new MapList(new int[] { 2,2,6,8,12,16}, new int[] { 1,3},3,1);
926 int[] frm = mldna.locateInFrom(1,1);
927 testLocateFrom(mldna, 1,1,new int[] { 2,2,6,7});
928 MapList.testMap(mldna, 1,3);
930 * for (int from=1; from<=51; from++) { int[] too=ml.shiftTo(from); int[]
931 * toofrom=ml.shiftFrom(too[0]);
932 * System.out.println("ShiftFrom("+from+")=="+too[0]+" %
933 * "+too[1]+"\t+-+\tShiftTo("+too[0]+")=="+toofrom[0]+" % "+toofrom[1]); }
935 System.out.print("Success?\n"); // if we get here - something must be
939 private static void testLocateFrom(MapList mldna, int i, int j, int[] ks)
941 int[] frm = mldna.locateInFrom(i, j);
942 if (frm==ks || java.util.Arrays.equals(frm,ks))
944 System.out.println("Success test locate from "+i+" to "+j);
946 System.err.println("Failed test locate from "+i+" to "+j);
947 for (int c = 0; c < frm.length; c++)
949 System.err.print(frm[c] + ((c % 2 == 0) ? "," : ";"));
951 System.err.println("Expected");
952 for (int c = 0; c < ks.length; c++)
954 System.err.print(ks[c] + ((c % 2 == 0) ? "," : ";"));
961 * @return a MapList whose From range is this maplist's To Range, and vice
964 public MapList getInverse()
966 return new MapList(getToRanges(), getFromRanges(), getToRatio(),