2 * This code was originated from
3 * Jalview - A Sequence Alignment Editor and Viewer
4 * Copyright (C) 2007 AM Waterhouse, J Procter, G Barton, M Clamp, S Searle
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version 2
9 * of the License, or (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
20 package uk.ac.vamsas.objects.utils;
26 * Simple way of bijectively mapping a non-contiguous linear range to another non-contiguous linear range
27 * Use at your own risk!
28 * TODO: efficient implementation of private posMap method
29 * TODO: test/ensure that sense of from and to ratio start position is conserved (codon start position recovery)
30 * TODO: optimize to use int[][] arrays rather than vectors.
35 * @see java.lang.Object#equals(java.lang.Object)
37 public boolean equals(MapList obj) {
40 if (obj!=null && obj.fromRatio==fromRatio && obj.toRatio==toRatio
41 && obj.fromShifts!=null && obj.toShifts!=null) {
42 int i,iSize=fromShifts.size(),j,jSize=obj.fromShifts.size();
45 for (i=0,iSize=fromShifts.size(),j=0, jSize=obj.fromShifts.size(); i<iSize;) {
46 int[] mi=(int[]) fromShifts.elementAt(i++);
47 int[] mj=(int[]) obj.fromShifts.elementAt(j++);
48 if (mi[0]!=mj[0] || mi[1]!=mj[1])
51 iSize=toShifts.size();
52 jSize=obj.toShifts.size();
55 for (i=0,j=0; i<iSize;) {
56 int[] mi=(int[]) toShifts.elementAt(i++);
57 int[] mj=(int[]) obj.toShifts.elementAt(j++);
58 if (mi[0]!=mj[0] || mi[1]!=mj[1])
65 public Vector fromShifts;
66 public Vector toShifts;
67 int fromRatio; // number of steps in fromShifts to one toRatio unit
68 int toRatio; // number of steps in toShifts to one fromRatio
72 * @return series of intervals mapped in from
74 public int[] getFromRanges()
76 return getRanges(fromShifts);
78 public int[] getToRanges()
80 return getRanges(toShifts);
83 private int[] getRanges(Vector shifts)
85 int[] rnges = new int[2*shifts.size()];
86 Enumeration e = shifts.elements();
88 while (e.hasMoreElements())
90 int r[] = (int[]) e.nextElement();
97 * lowest and highest value in the from Map
101 * lowest and highest value in the to Map
106 * @return length of mapped phrase in from
108 public int getFromRatio()
114 * @return length of mapped phrase in to
116 public int getToRatio()
120 public int getFromLowest() {
123 public int getFromHighest() {
126 public int getToLowest() {
129 public int getToHighest() {
132 private void ensureRange(int[] limits, int pos) {
138 public MapList(int from[], int to[], int fromRatio, int toRatio)
140 fromRange=new int[] { from[0],from[1] };
141 toRange=new int[] { to[0],to[1] };
143 fromShifts = new Vector();
144 for (int i=0;i<from.length; i+=2)
146 ensureRange(fromRange, from[i]);
147 ensureRange(fromRange, from[i+1]);
149 fromShifts.addElement(new int[]
150 {from[i], from[i + 1]});
152 toShifts = new Vector();
153 for (int i=0;i<to.length; i+=2)
155 ensureRange(toRange, to[i]);
156 ensureRange(toRange, to[i+1]);
157 toShifts.addElement(new int[]
160 this.fromRatio=fromRatio;
161 this.toRatio=toRatio;
163 public MapList(MapList map)
165 this.fromRange = new int[]
166 { map.fromRange[0], map.fromRange[1] };
167 this.toRange = new int[]
168 { map.toRange[0], map.toRange[1] };
169 this.fromRatio = map.fromRatio;
170 this.toRatio = map.toRatio;
171 if (map.fromShifts != null)
173 this.fromShifts = new Vector();
174 Enumeration e = map.fromShifts.elements();
175 while (e.hasMoreElements())
177 int[] el = (int[]) e.nextElement();
178 fromShifts.addElement(new int[]
182 if (map.toShifts != null)
184 this.toShifts = new Vector();
185 Enumeration e = map.toShifts.elements();
186 while (e.hasMoreElements())
188 int[] el = (int[]) e.nextElement();
189 toShifts.addElement(new int[]
195 * get all mapped positions from 'from' to 'to'
196 * @return int[][] { int[] { fromStart, fromFinish, toStart, toFinish }, int [fromFinish-fromStart+2] { toStart..toFinish mappings}}
198 public int[][] makeFromMap()
200 return posMap(fromShifts, fromRatio, toShifts, toRatio);
203 * get all mapped positions from 'to' to 'from'
204 * @return int[to position]=position mapped in from
206 public int[][] makeToMap()
208 return posMap(toShifts,toRatio, fromShifts, fromRatio);
211 * construct an int map for intervals in intVals
213 * @return int[] { from, to pos in range }, int[range.to-range.from+1] returning mapped position
215 private int[][] posMap(Vector intVals, int ratio, Vector toIntVals,
218 int iv=0,ivSize = intVals.size();
223 int[] intv=(int[]) intVals.elementAt(iv++);
224 int from=intv[0],to=intv[1];
232 intv = (int[]) intVals.elementAt(iv++);
251 int mp[][] = new int[to-from+2][];
252 for (int i = 0; i < mp.length; i++)
254 int[] m = shift(i+from,intVals,ratio,toIntVals, toRatio);
275 int[][] map = new int[][]
279 from, to, tF, tT}, new int[to - from + 2]};
284 for (int i = 0; i < mp.length; i++)
288 map[1][i] = mp[i][0]-tF;
292 map[1][i] = -1; // indicates an out of range mapping
299 * @param pos start position for shift (in original reference frame)
300 * @param shift length of shift
302 public void addShift(int pos, int shift)
306 while (sidx<shifts.size() && (rshift=(int[]) shifts.elementAt(sidx))[0]<pos)
308 if (sidx==shifts.size())
309 shifts.insertElementAt(new int[] { pos, shift}, sidx);
315 * shift from pos to To(pos)
318 * @return int shifted position in To, frameshift in From, direction of mapped symbol in To
320 public int[] shiftFrom(int pos)
322 return shift(pos, fromShifts, fromRatio, toShifts, toRatio);
326 * inverse of shiftFrom - maps pos in To to a position in From
328 * @return shifted position in From, frameshift in To, direction of mapped symbol in From
330 public int[] shiftTo(int pos)
332 return shift(pos, toShifts, toRatio, fromShifts, fromRatio);
342 private int[] shift(int pos, Vector fromShifts, int fromRatio,
343 Vector toShifts, int toRatio)
345 int[] fromCount = countPos(fromShifts, pos);
350 int fromRemainder=(fromCount[0]-1) % fromRatio;
351 int toCount = 1+(((fromCount[0]-1) / fromRatio) * toRatio);
352 int[] toPos = countToPos(toShifts, toCount);
355 return null; // throw new Error("Bad Mapping!");
357 //System.out.println(fromCount[0]+" "+fromCount[1]+" "+toCount);
360 toPos[0], fromRemainder, toPos[1]};
363 * count how many positions pos is along the series of intervals.
366 * @return number of positions or null if pos is not within intervals
368 private int[] countPos(Vector intVals, int pos)
370 int count=0,intv[],iv=0,ivSize=intVals.size();
373 intv = (int[])intVals.elementAt(iv++);
374 if (intv[0] <= intv[1])
376 if (pos >= intv[0] && pos <= intv[1])
380 count + pos - intv[0] + 1, +1};
384 count+=intv[1]-intv[0]+1;
389 if (pos >= intv[1] && pos <= intv[0])
393 count + intv[0] - pos + 1, -1};
397 count+=intv[0]-intv[1]+1;
404 * count out pos positions into a series of intervals and return the position
407 * @return position pos in interval set
409 private int[] countToPos(Vector intVals, int pos)
411 int count = 0, diff = 0, iv=0,ivSize=intVals.size(), intv[] =
416 intv = (int[])intVals.elementAt(iv++);
417 diff = intv[1]-intv[0];
420 if (pos <= count + 1 + diff)
424 pos - count - 1 + intv[0], +1};
433 if (pos <= count + 1 - diff)
437 intv[0] - (pos - count - 1), -1};
445 return null;//(diff<0) ? (intv[1]-1) : (intv[0]+1);
448 * find series of intervals mapping from start-end in the From map.
449 * @param start position in to map
450 * @param end position in to map
451 * @return series of ranges in from map
453 public int[] locateInFrom(int start, int end) {
454 // inefficient implementation
455 int fromStart[] = shiftTo(start);
456 int fromEnd[] = shiftTo(end); // needs to be inclusive of end of symbol position
457 if (fromStart==null || fromEnd==null)
459 int iv[] = getIntervals(fromShifts, fromStart, fromEnd,fromRatio);
464 * find series of intervals mapping from start-end in the to map.
465 * @param start position in from map
466 * @param end position in from map
467 * @return series of ranges in to map
469 public int[] locateInTo(int start, int end) {
470 // inefficient implementation
471 int toStart[] = shiftFrom(start);
472 int toEnd[] = shiftFrom(end);
473 if (toStart==null || toEnd==null)
475 int iv[] = getIntervals(toShifts, toStart, toEnd, toRatio);
479 * like shift - except returns the intervals in the given vector of shifts which were spanned
480 * in traversing fromStart to fromEnd
485 * @return series of from,to intervals from from first position of starting region to final position of ending region inclusive
487 private int[] getIntervals(Vector fromShifts2, int[] fromStart, int[] fromEnd, int fromRatio2)
490 startpos = fromStart[0]; // first position in fromStart
491 endpos = fromEnd[0]+fromEnd[2]*(fromRatio2-1); // last position in fromEnd
492 int intv=0,intvSize= fromShifts2.size();
493 int iv[],i=0,fs=-1,fe=-1; // containing intervals
494 while (intv<intvSize && (fs==-1 || fe==-1)) {
495 iv = (int[]) fromShifts2.elementAt(intv++);
497 if (fs==-1 && startpos>=iv[0] && startpos<=iv[1]) {
500 if (fe==-1 && endpos>=iv[0] && endpos<=iv[1]) {
504 if (fs==-1 && startpos<=iv[0] && startpos>=iv[1]) {
507 if (fe==-1 && endpos<=iv[0] && endpos>=iv[1]) {
513 if (fs==fe && fe==-1)
515 Vector ranges=new Vector();
519 // truncate initial interval
520 iv = (int[]) fromShifts2.elementAt(intv++);
521 iv = new int[] { iv[0], iv[1]};// clone
525 ranges.addElement(iv); // add initial range
526 iv = (int[]) fromShifts2.elementAt(intv++); // get next interval
527 iv = new int[] { iv[0], iv[1]};// clone
532 ranges.addElement(iv); // add only - or final range
534 // walk from end of interval.
535 i=fromShifts2.size()-1;
539 iv = (int[]) fromShifts2.elementAt(i);
540 iv = new int[] { iv[1], iv[0]};// reverse and clone
541 // truncate initial interval
546 while (--i!=fe) { // fix apparent logic bug when fe==-1
547 ranges.addElement(iv); // add (truncated) reversed interval
548 iv = (int[]) fromShifts2.elementAt(i);
549 iv = new int[] { iv[1], iv[0] }; // reverse and clone
552 // interval is already reversed
555 ranges.addElement(iv); // add only - or final range
557 // create array of start end intervals.
559 if (ranges!=null && ranges.size()>0)
561 range = new int[ranges.size()*2];
563 intvSize=ranges.size();
565 while (intv<intvSize)
567 iv = (int[]) ranges.elementAt(intv);
570 ranges.setElementAt(null, intv++); // remove
576 * get the 'initial' position of mpos in To
577 * @param mpos position in from
578 * @return position of first word in to reference frame
580 public int getToPosition(int mpos)
582 int[] mp = shiftTo(mpos);
590 * get range of positions in To frame for the mpos word in From
591 * @param mpos position in From
592 * @return null or int[] first position in To for mpos, last position in to for Mpos
594 public int[] getToWord(int mpos) {
595 int[] mp=shiftTo(mpos);
597 return new int[] {mp[0], mp[0]+mp[2]*(getFromRatio()-1)};
602 * get From position in the associated
603 * reference frame for position pos in the
604 * associated sequence.
608 public int getMappedPosition(int pos) {
609 int[] mp = shiftFrom(pos);
616 public int[] getMappedWord(int pos) {
617 int[] mp = shiftFrom(pos);
620 return new int[] { mp[0], mp[0]+mp[2]*(getToRatio()-1)};
626 * test routine. not incremental.
631 public static void testMap(MapList ml, int fromS, int fromE)
633 for (int from = 1; from <= 25; from++)
635 int[] too=ml.shiftFrom(from);
636 System.out.print("ShiftFrom("+from+")==");
639 System.out.print("NaN\n");
643 System.out.print(too[0]+" % "+too[1]+" ("+too[2]+")");
644 System.out.print("\t+--+\t");
645 int[] toofrom=ml.shiftTo(too[0]);
648 if (toofrom[0]!=from)
650 System.err.println("Mapping not reflexive:" + from + " " + too[0] +
653 System.out.println("ShiftTo(" + too[0] + ")==" + toofrom[0] + " % " +
654 toofrom[1]+" ("+toofrom[2]+")");
658 System.out.println("ShiftTo(" + too[0] + ")==" +
659 "NaN! - not Bijective Mapping!");
663 int mmap[][] = ml.makeFromMap();
664 System.out.println("FromMap : (" + mmap[0][0] + " " + mmap[0][1] + " " +
665 mmap[0][2] + " " + mmap[0][3] + " ");
666 for (int i = 1; i <= mmap[1].length; i++)
668 if (mmap[1][i - 1] == -1)
670 System.out.print(i+"=XXX");
675 System.out.print(i+"="+(mmap[0][2]+mmap[1][i-1]));
679 System.out.print("\n");
683 System.out.print(",");
686 //test range function
687 System.out.print("\nTest locateInFrom\n");
689 int f=mmap[0][2],t=mmap[0][3];
691 System.out.println("Range "+f+" to "+t);
692 int rng[] = ml.locateInFrom(f,t);
695 for (int i=0; i<rng.length; i++) {
696 System.out.print(rng[i]+((i%2==0) ? "," : ";"));
701 System.out.println("No range!");
703 System.out.print("\nReversed\n");
704 rng = ml.locateInFrom(t,f);
707 for (int i=0; i<rng.length; i++) {
708 System.out.print(rng[i]+((i%2==0) ? "," : ";"));
713 System.out.println("No range!");
715 System.out.print("\n");
719 System.out.print("\n");
720 mmap = ml.makeToMap();
721 System.out.println("ToMap : (" + mmap[0][0] + " " + mmap[0][1] + " " +
722 mmap[0][2] + " " + mmap[0][3] + " ");
723 for (int i = 1; i <= mmap[1].length; i++)
725 if (mmap[1][i - 1] == -1)
727 System.out.print(i+"=XXX");
732 System.out.print(i+"="+(mmap[0][2]+mmap[1][i-1]));
736 System.out.print("\n");
740 System.out.print(",");
743 System.out.print("\n");
744 //test range function
745 System.out.print("\nTest locateInTo\n");
747 int f=mmap[0][2],t=mmap[0][3];
749 System.out.println("Range "+f+" to "+t);
750 int rng[] = ml.locateInTo(f,t);
752 for (int i=0; i<rng.length; i++) {
753 System.out.print(rng[i]+((i%2==0) ? "," : ";"));
758 System.out.println("No range!");
760 System.out.print("\nReversed\n");
761 rng = ml.locateInTo(t,f);
764 for (int i=0; i<rng.length; i++) {
765 System.out.print(rng[i]+((i%2==0) ? "," : ";"));
770 System.out.println("No range!");
773 System.out.print("\n");
779 public static void main(String argv[])
781 MapList ml = new MapList(new int[]
782 {1, 5, 10, 15, 25, 20},
785 MapList ml1 = new MapList(new int[]
789 MapList ml2 = new MapList(new int[] { 1, 60 },
790 new int[] { 1, 20 }, 3, 1);
791 // test internal consistency
792 int to[] = new int[51];
793 MapList.testMap(ml, 1, 60);
795 for (int from=1; from<=51; from++) {
796 int[] too=ml.shiftTo(from);
797 int[] toofrom=ml.shiftFrom(too[0]);
798 System.out.println("ShiftFrom("+from+")=="+too[0]+" % "+too[1]+"\t+-+\tShiftTo("+too[0]+")=="+toofrom[0]+" % "+toofrom[1]);
800 System.out.print("Success?\n"); // if we get here - something must be working!
804 * @return a MapList whose From range is this maplist's To Range, and vice versa
806 public MapList getInverse()
808 return new MapList(getToRanges(), getFromRanges(), getToRatio(), getFromRatio());