2 * Jalview - A Sequence Alignment Editor and Viewer (Version 2.8.0b1)
3 * Copyright (C) 2014 The Jalview Authors
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/>.
17 * The Jalview Authors are detailed in the 'AUTHORS' file.
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[]
341 * rshift=null; while (sidx<shifts.size() && (rshift=(int[])
342 * shifts.elementAt(sidx))[0]<pos) sidx++; if (sidx==shifts.size())
343 * shifts.insertElementAt(new int[] { pos, shift}, sidx); else
344 * rshift[1]+=shift; }
347 * shift from pos to To(pos)
351 * @return int shifted position in To, frameshift in From, direction of mapped
354 public int[] shiftFrom(int pos)
356 return shift(pos, fromShifts, fromRatio, toShifts, toRatio);
360 * inverse of shiftFrom - maps pos in To to a position in From
364 * @return shifted position in From, frameshift in To, direction of mapped
367 public int[] shiftTo(int pos)
369 return shift(pos, toShifts, toRatio, fromShifts, fromRatio);
380 private int[] shift(int pos, Vector fromShifts, int fromRatio,
381 Vector toShifts, int toRatio)
383 int[] fromCount = countPos(fromShifts, pos);
384 if (fromCount == null)
388 int fromRemainder = (fromCount[0] - 1) % fromRatio;
389 int toCount = 1 + (((fromCount[0] - 1) / fromRatio) * toRatio);
390 int[] toPos = countToPos(toShifts, toCount);
393 return null; // throw new Error("Bad Mapping!");
395 // System.out.println(fromCount[0]+" "+fromCount[1]+" "+toCount);
397 { toPos[0], fromRemainder, toPos[1] };
401 * count how many positions pos is along the series of intervals.
405 * @return number of positions or null if pos is not within intervals
407 private int[] countPos(Vector intVals, int pos)
409 int count = 0, intv[], iv = 0, ivSize = intVals.size();
412 intv = (int[]) intVals.elementAt(iv++);
413 if (intv[0] <= intv[1])
415 if (pos >= intv[0] && pos <= intv[1])
418 { count + pos - intv[0] + 1, +1 };
422 count += intv[1] - intv[0] + 1;
427 if (pos >= intv[1] && pos <= intv[0])
430 { count + intv[0] - pos + 1, -1 };
434 count += intv[0] - intv[1] + 1;
442 * count out pos positions into a series of intervals and return the position
446 * @return position pos in interval set
448 private int[] countToPos(Vector intVals, int pos)
450 int count = 0, diff = 0, iv = 0, ivSize = intVals.size(), intv[] =
454 intv = (int[]) intVals.elementAt(iv++);
455 diff = intv[1] - intv[0];
458 if (pos <= count + 1 + diff)
461 { pos - count - 1 + intv[0], +1 };
470 if (pos <= count + 1 - diff)
473 { intv[0] - (pos - count - 1), -1 };
481 return null;// (diff<0) ? (intv[1]-1) : (intv[0]+1);
485 * find series of intervals mapping from start-end in the From map.
491 * @return series of ranges in from map
493 public int[] locateInFrom(int start, int end)
495 // inefficient implementation
496 int fromStart[] = shiftTo(start);
497 int fromEnd[] = shiftTo(end); // needs to be inclusive of end of symbol
499 if (fromStart == null || fromEnd == null)
501 int iv[] = getIntervals(fromShifts, fromStart, fromEnd, fromRatio);
506 * find series of intervals mapping from start-end in the to map.
509 * position in from map
511 * position in from map
512 * @return series of ranges in to map
514 public int[] locateInTo(int start, int end)
516 // inefficient implementation
517 int toStart[] = shiftFrom(start);
518 int toEnd[] = shiftFrom(end);
519 if (toStart == null || toEnd == null)
521 int iv[] = getIntervals(toShifts, toStart, toEnd, toRatio);
526 * like shift - except returns the intervals in the given vector of shifts
527 * which were spanned in traversing fromStart to fromEnd
533 * @return series of from,to intervals from from first position of starting
534 * region to final position of ending region inclusive
536 private int[] getIntervals(Vector fromShifts2, int[] fromStart,
537 int[] fromEnd, int fromRatio2)
539 int startpos, endpos;
540 startpos = fromStart[0]; // first position in fromStart
541 endpos = fromEnd[0]; // last position in fromEnd
542 int endindx = (fromRatio2 - 1); // additional positions to get to last
543 // position from endpos
544 int intv = 0, intvSize = fromShifts2.size();
545 int iv[], i = 0, fs = -1, fe_s = -1, fe = -1; // containing intervals
546 // search intervals to locate ones containing startpos and count endindx
547 // positions on from endpos
548 while (intv < intvSize && (fs == -1 || fe == -1))
550 iv = (int[]) fromShifts2.elementAt(intv++);
553 endpos = iv[0]; // start counting from beginning of interval
554 endindx--; // inclusive of endpos
558 if (fs == -1 && startpos >= iv[0] && startpos <= iv[1])
562 if (endpos >= iv[0] && endpos <= iv[1])
570 if (endpos + endindx <= iv[1])
573 endpos = endpos + endindx; // end of end token is within this
578 endindx -= iv[1] - endpos; // skip all this interval too
585 if (fs == -1 && startpos <= iv[0] && startpos >= iv[1])
589 if (endpos <= iv[0] && endpos >= iv[1])
597 if (endpos - endindx >= iv[1])
600 endpos = endpos - endindx; // end of end token is within this
605 endindx -= endpos - iv[1]; // skip all this interval too
612 if (fs == fe && fe == -1)
614 Vector ranges = new Vector();
619 // truncate initial interval
620 iv = (int[]) fromShifts2.elementAt(intv++);
622 { iv[0], iv[1] };// clone
627 ranges.addElement(iv); // add initial range
628 iv = (int[]) fromShifts2.elementAt(intv++); // get next interval
630 { iv[0], iv[1] };// clone
635 ranges.addElement(iv); // add only - or final range
639 // walk from end of interval.
640 i = fromShifts2.size() - 1;
645 iv = (int[]) fromShifts2.elementAt(i);
647 { iv[1], iv[0] };// reverse and clone
648 // truncate initial interval
654 { // fix apparent logic bug when fe==-1
655 ranges.addElement(iv); // add (truncated) reversed interval
656 iv = (int[]) fromShifts2.elementAt(i);
658 { iv[1], iv[0] }; // reverse and clone
662 // interval is already reversed
665 ranges.addElement(iv); // add only - or final range
667 // create array of start end intervals.
669 if (ranges != null && ranges.size() > 0)
671 range = new int[ranges.size() * 2];
673 intvSize = ranges.size();
675 while (intv < intvSize)
677 iv = (int[]) ranges.elementAt(intv);
680 ranges.setElementAt(null, intv++); // remove
687 * get the 'initial' position of mpos in To
691 * @return position of first word in to reference frame
693 public int getToPosition(int mpos)
695 int[] mp = shiftTo(mpos);
704 * get range of positions in To frame for the mpos word in From
708 * @return null or int[] first position in To for mpos, last position in to
711 public int[] getToWord(int mpos)
713 int[] mp = shiftTo(mpos);
717 { mp[0], mp[0] + mp[2] * (getFromRatio() - 1) };
723 * get From position in the associated reference frame for position pos in the
724 * associated sequence.
729 public int getMappedPosition(int pos)
731 int[] mp = shiftFrom(pos);
739 public int[] getMappedWord(int pos)
741 int[] mp = shiftFrom(pos);
745 { mp[0], mp[0] + mp[2] * (getToRatio() - 1) };
751 * test routine. not incremental.
757 public static void testMap(MapList ml, int fromS, int fromE)
759 for (int from = 1; from <= 25; from++)
761 int[] too = ml.shiftFrom(from);
762 System.out.print("ShiftFrom(" + from + ")==");
765 System.out.print("NaN\n");
769 System.out.print(too[0] + " % " + too[1] + " (" + too[2] + ")");
770 System.out.print("\t+--+\t");
771 int[] toofrom = ml.shiftTo(too[0]);
774 if (toofrom[0] != from)
776 System.err.println("Mapping not reflexive:" + from + " "
777 + too[0] + "->" + toofrom[0]);
779 System.out.println("ShiftTo(" + too[0] + ")==" + toofrom[0]
780 + " % " + toofrom[1] + " (" + toofrom[2] + ")");
784 System.out.println("ShiftTo(" + too[0] + ")=="
785 + "NaN! - not Bijective Mapping!");
789 int mmap[][] = ml.makeFromMap();
790 System.out.println("FromMap : (" + mmap[0][0] + " " + mmap[0][1] + " "
791 + mmap[0][2] + " " + mmap[0][3] + " ");
792 for (int i = 1; i <= mmap[1].length; i++)
794 if (mmap[1][i - 1] == -1)
796 System.out.print(i + "=XXX");
801 System.out.print(i + "=" + (mmap[0][2] + mmap[1][i - 1]));
805 System.out.print("\n");
809 System.out.print(",");
812 // test range function
813 System.out.print("\nTest locateInFrom\n");
815 int f = mmap[0][2], t = mmap[0][3];
818 System.out.println("Range " + f + " to " + t);
819 int rng[] = ml.locateInFrom(f, t);
822 for (int i = 0; i < rng.length; i++)
824 System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
829 System.out.println("No range!");
831 System.out.print("\nReversed\n");
832 rng = ml.locateInFrom(t, f);
835 for (int i = 0; i < rng.length; i++)
837 System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
842 System.out.println("No range!");
844 System.out.print("\n");
849 System.out.print("\n");
850 mmap = ml.makeToMap();
851 System.out.println("ToMap : (" + mmap[0][0] + " " + mmap[0][1] + " "
852 + mmap[0][2] + " " + mmap[0][3] + " ");
853 for (int i = 1; i <= mmap[1].length; i++)
855 if (mmap[1][i - 1] == -1)
857 System.out.print(i + "=XXX");
862 System.out.print(i + "=" + (mmap[0][2] + mmap[1][i - 1]));
866 System.out.print("\n");
870 System.out.print(",");
873 System.out.print("\n");
874 // test range function
875 System.out.print("\nTest locateInTo\n");
877 int f = mmap[0][2], t = mmap[0][3];
880 System.out.println("Range " + f + " to " + t);
881 int rng[] = ml.locateInTo(f, t);
884 for (int i = 0; i < rng.length; i++)
886 System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
891 System.out.println("No range!");
893 System.out.print("\nReversed\n");
894 rng = ml.locateInTo(t, f);
897 for (int i = 0; i < rng.length; i++)
899 System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
904 System.out.println("No range!");
908 System.out.print("\n");
914 public static void main(String argv[])
916 MapList ml = new MapList(new int[]
917 { 1, 5, 10, 15, 25, 20 }, new int[]
919 MapList ml1 = new MapList(new int[]
920 { 1, 3, 17, 4 }, new int[]
922 MapList ml2 = new MapList(new int[]
925 // test internal consistency
926 int to[] = new int[51];
927 MapList.testMap(ml, 1, 60);
928 MapList mldna = new MapList(new int[]
929 { 2, 2, 6, 8, 12, 16 }, new int[]
931 int[] frm = mldna.locateInFrom(1, 1);
932 testLocateFrom(mldna, 1, 1, new int[]
934 MapList.testMap(mldna, 1, 3);
936 * for (int from=1; from<=51; from++) { int[] too=ml.shiftTo(from); int[]
937 * toofrom=ml.shiftFrom(too[0]);
938 * System.out.println("ShiftFrom("+from+")=="+too[0]+" %
939 * "+too[1]+"\t+-+\tShiftTo("+too[0]+")=="+toofrom[0]+" % "+toofrom[1]); }
941 System.out.print("Success?\n"); // if we get here - something must be
945 private static void testLocateFrom(MapList mldna, int i, int j, int[] ks)
947 int[] frm = mldna.locateInFrom(i, j);
948 if (frm == ks || java.util.Arrays.equals(frm, ks))
950 System.out.println("Success test locate from " + i + " to " + j);
954 System.err.println("Failed test locate from " + i + " to " + j);
955 for (int c = 0; c < frm.length; c++)
957 System.err.print(frm[c] + ((c % 2 == 0) ? "," : ";"));
959 System.err.println("Expected");
960 for (int c = 0; c < ks.length; c++)
962 System.err.print(ks[c] + ((c % 2 == 0) ? "," : ";"));
969 * @return a MapList whose From range is this maplist's To Range, and vice
972 public MapList getInverse()
974 return new MapList(getToRanges(), getFromRanges(), getToRatio(),
979 * test for containment rather than equivalence to another mapping
982 * to be tested for containment
983 * @return true if local or mapped range map contains or is contained by this
986 public boolean containsEither(boolean local, MapList map)
990 return ((getFromLowest() >= map.getFromLowest() && getFromHighest() <= map
991 .getFromHighest()) || (getFromLowest() <= map.getFromLowest() && getFromHighest() >= map
996 return ((getToLowest() >= map.getToLowest() && getToHighest() <= map
997 .getToHighest()) || (getToLowest() <= map.getToLowest() && getToHighest() >= map