2 * Jalview - A Sequence Alignment Editor and Viewer (Version 2.8.2)
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
10 * of the License, or (at your option) any later version.
12 * Jalview is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty
14 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
15 * PURPOSE. See the GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with Jalview. If not, see <http://www.gnu.org/licenses/>.
19 * The Jalview Authors are detailed in the 'AUTHORS' file.
26 * MapList Simple way of bijectively mapping a non-contiguous linear range to
27 * another non-contiguous linear range Use at your own risk! TODO: efficient
28 * implementation of private posMap method TODO: test/ensure that sense of from
29 * and to ratio start position is conserved (codon start position recovery)
30 * TODO: optimize to use int[][] arrays rather than vectors.
37 * @see java.lang.Object#equals(java.lang.Object)
39 public boolean equals(MapList obj)
43 if (obj != null && obj.fromRatio == fromRatio && obj.toRatio == toRatio
44 && obj.fromShifts != null && obj.toShifts != null)
46 int i, iSize = fromShifts.size(), j, jSize = obj.fromShifts.size();
49 for (i = 0, iSize = fromShifts.size(), j = 0, jSize = obj.fromShifts
52 int[] mi = (int[]) fromShifts.elementAt(i++);
53 int[] mj = (int[]) obj.fromShifts.elementAt(j++);
54 if (mi[0] != mj[0] || mi[1] != mj[1])
57 iSize = toShifts.size();
58 jSize = obj.toShifts.size();
61 for (i = 0, j = 0; i < iSize;)
63 int[] mi = (int[]) toShifts.elementAt(i++);
64 int[] mj = (int[]) obj.toShifts.elementAt(j++);
65 if (mi[0] != mj[0] || mi[1] != mj[1])
73 public Vector fromShifts;
75 public Vector toShifts;
77 int fromRatio; // number of steps in fromShifts to one toRatio unit
79 int toRatio; // number of steps in toShifts to one fromRatio
83 * @return series of intervals mapped in from
85 public int[] getFromRanges()
87 return getRanges(fromShifts);
90 public int[] getToRanges()
92 return getRanges(toShifts);
95 private int[] getRanges(Vector shifts)
97 int[] rnges = new int[2 * shifts.size()];
98 Enumeration e = shifts.elements();
100 while (e.hasMoreElements())
102 int r[] = (int[]) e.nextElement();
110 * lowest and highest value in the from Map
112 int[] fromRange = null;
115 * lowest and highest value in the to Map
117 int[] toRange = null;
121 * @return length of mapped phrase in from
123 public int getFromRatio()
130 * @return length of mapped phrase in to
132 public int getToRatio()
137 public int getFromLowest()
142 public int getFromHighest()
147 public int getToLowest()
152 public int getToHighest()
157 private void ensureRange(int[] limits, int pos)
165 public MapList(int from[], int to[], int fromRatio, int toRatio)
167 fromRange = new int[]
168 { from[0], from[1] };
172 fromShifts = new Vector();
173 for (int i = 0; i < from.length; i += 2)
175 ensureRange(fromRange, from[i]);
176 ensureRange(fromRange, from[i + 1]);
178 fromShifts.addElement(new int[]
179 { from[i], from[i + 1] });
181 toShifts = new Vector();
182 for (int i = 0; i < to.length; i += 2)
184 ensureRange(toRange, to[i]);
185 ensureRange(toRange, to[i + 1]);
186 toShifts.addElement(new int[]
187 { to[i], to[i + 1] });
189 this.fromRatio = fromRatio;
190 this.toRatio = toRatio;
193 public MapList(MapList map)
195 this.fromRange = new int[]
196 { map.fromRange[0], map.fromRange[1] };
197 this.toRange = new int[]
198 { map.toRange[0], map.toRange[1] };
199 this.fromRatio = map.fromRatio;
200 this.toRatio = map.toRatio;
201 if (map.fromShifts != null)
203 this.fromShifts = new Vector();
204 Enumeration e = map.fromShifts.elements();
205 while (e.hasMoreElements())
207 int[] el = (int[]) e.nextElement();
208 fromShifts.addElement(new int[]
212 if (map.toShifts != null)
214 this.toShifts = new Vector();
215 Enumeration e = map.toShifts.elements();
216 while (e.hasMoreElements())
218 int[] el = (int[]) e.nextElement();
219 toShifts.addElement(new int[]
226 * get all mapped positions from 'from' to 'to'
228 * @return int[][] { int[] { fromStart, fromFinish, toStart, toFinish }, int
229 * [fromFinish-fromStart+2] { toStart..toFinish mappings}}
231 public int[][] makeFromMap()
233 return posMap(fromShifts, fromRatio, toShifts, toRatio);
237 * get all mapped positions from 'to' to 'from'
239 * @return int[to position]=position mapped in from
241 public int[][] makeToMap()
243 return posMap(toShifts, toRatio, fromShifts, fromRatio);
247 * construct an int map for intervals in intVals
250 * @return int[] { from, to pos in range }, int[range.to-range.from+1]
251 * returning mapped position
253 private int[][] posMap(Vector intVals, int ratio, Vector toIntVals,
256 int iv = 0, ivSize = intVals.size();
261 int[] intv = (int[]) intVals.elementAt(iv++);
262 int from = intv[0], to = intv[1];
270 intv = (int[]) intVals.elementAt(iv++);
289 int mp[][] = new int[to - from + 2][];
290 for (int i = 0; i < mp.length; i++)
292 int[] m = shift(i + from, intVals, ratio, toIntVals, toRatio);
313 int[][] map = new int[][]
315 { from, to, tF, tT }, new int[to - from + 2] };
320 for (int i = 0; i < mp.length; i++)
324 map[1][i] = mp[i][0] - tF;
328 map[1][i] = -1; // indicates an out of range mapping
338 * start position for shift (in original reference frame)
342 * public void addShift(int pos, int shift) { int sidx = 0; int[]
343 * rshift=null; while (sidx<shifts.size() && (rshift=(int[])
344 * shifts.elementAt(sidx))[0]<pos) sidx++; if (sidx==shifts.size())
345 * shifts.insertElementAt(new int[] { pos, shift}, sidx); else
346 * rshift[1]+=shift; }
349 * shift from pos to To(pos)
353 * @return int shifted position in To, frameshift in From, direction of mapped
356 public int[] shiftFrom(int pos)
358 return shift(pos, fromShifts, fromRatio, toShifts, toRatio);
362 * inverse of shiftFrom - maps pos in To to a position in From
366 * @return shifted position in From, frameshift in To, direction of mapped
369 public int[] shiftTo(int pos)
371 return shift(pos, toShifts, toRatio, fromShifts, fromRatio);
382 private int[] shift(int pos, Vector fromShifts, int fromRatio,
383 Vector toShifts, int toRatio)
385 int[] fromCount = countPos(fromShifts, pos);
386 if (fromCount == null)
390 int fromRemainder = (fromCount[0] - 1) % fromRatio;
391 int toCount = 1 + (((fromCount[0] - 1) / fromRatio) * toRatio);
392 int[] toPos = countToPos(toShifts, toCount);
395 return null; // throw new Error("Bad Mapping!");
397 // System.out.println(fromCount[0]+" "+fromCount[1]+" "+toCount);
399 { toPos[0], fromRemainder, toPos[1] };
403 * count how many positions pos is along the series of intervals.
407 * @return number of positions or null if pos is not within intervals
409 private int[] countPos(Vector intVals, int pos)
411 int count = 0, intv[], iv = 0, ivSize = intVals.size();
414 intv = (int[]) intVals.elementAt(iv++);
415 if (intv[0] <= intv[1])
417 if (pos >= intv[0] && pos <= intv[1])
420 { count + pos - intv[0] + 1, +1 };
424 count += intv[1] - intv[0] + 1;
429 if (pos >= intv[1] && pos <= intv[0])
432 { count + intv[0] - pos + 1, -1 };
436 count += intv[0] - intv[1] + 1;
444 * count out pos positions into a series of intervals and return the position
448 * @return position pos in interval set
450 private int[] countToPos(Vector intVals, int pos)
452 int count = 0, diff = 0, iv = 0, ivSize = intVals.size(), intv[] =
456 intv = (int[]) intVals.elementAt(iv++);
457 diff = intv[1] - intv[0];
460 if (pos <= count + 1 + diff)
463 { pos - count - 1 + intv[0], +1 };
472 if (pos <= count + 1 - diff)
475 { intv[0] - (pos - count - 1), -1 };
483 return null;// (diff<0) ? (intv[1]-1) : (intv[0]+1);
487 * find series of intervals mapping from start-end in the From map.
493 * @return series of ranges in from map
495 public int[] locateInFrom(int start, int end)
497 // inefficient implementation
498 int fromStart[] = shiftTo(start);
499 int fromEnd[] = shiftTo(end); // needs to be inclusive of end of symbol
501 if (fromStart == null || fromEnd == null)
503 int iv[] = getIntervals(fromShifts, fromStart, fromEnd, fromRatio);
508 * find series of intervals mapping from start-end in the to map.
511 * position in from map
513 * position in from map
514 * @return series of ranges in to map
516 public int[] locateInTo(int start, int end)
518 // inefficient implementation
519 int toStart[] = shiftFrom(start);
520 int toEnd[] = shiftFrom(end);
521 if (toStart == null || toEnd == null)
523 int iv[] = getIntervals(toShifts, toStart, toEnd, toRatio);
528 * like shift - except returns the intervals in the given vector of shifts
529 * which were spanned in traversing fromStart to fromEnd
535 * @return series of from,to intervals from from first position of starting
536 * region to final position of ending region inclusive
538 private int[] getIntervals(Vector fromShifts2, int[] fromStart,
539 int[] fromEnd, int fromRatio2)
541 int startpos, endpos;
542 startpos = fromStart[0]; // first position in fromStart
543 endpos = fromEnd[0]; // last position in fromEnd
544 int endindx = (fromRatio2 - 1); // additional positions to get to last
545 // position from endpos
546 int intv = 0, intvSize = fromShifts2.size();
547 int iv[], i = 0, fs = -1, fe_s = -1, fe = -1; // containing intervals
548 // search intervals to locate ones containing startpos and count endindx
549 // positions on from endpos
550 while (intv < intvSize && (fs == -1 || fe == -1))
552 iv = (int[]) fromShifts2.elementAt(intv++);
555 endpos = iv[0]; // start counting from beginning of interval
556 endindx--; // inclusive of endpos
560 if (fs == -1 && startpos >= iv[0] && startpos <= iv[1])
564 if (endpos >= iv[0] && endpos <= iv[1])
572 if (endpos + endindx <= iv[1])
575 endpos = endpos + endindx; // end of end token is within this
580 endindx -= iv[1] - endpos; // skip all this interval too
587 if (fs == -1 && startpos <= iv[0] && startpos >= iv[1])
591 if (endpos <= iv[0] && endpos >= iv[1])
599 if (endpos - endindx >= iv[1])
602 endpos = endpos - endindx; // end of end token is within this
607 endindx -= endpos - iv[1]; // skip all this interval too
614 if (fs == fe && fe == -1)
616 Vector ranges = new Vector();
621 // truncate initial interval
622 iv = (int[]) fromShifts2.elementAt(intv++);
624 { iv[0], iv[1] };// clone
629 ranges.addElement(iv); // add initial range
630 iv = (int[]) fromShifts2.elementAt(intv++); // get next interval
632 { iv[0], iv[1] };// clone
637 ranges.addElement(iv); // add only - or final range
641 // walk from end of interval.
642 i = fromShifts2.size() - 1;
647 iv = (int[]) fromShifts2.elementAt(i);
649 { iv[1], iv[0] };// reverse and clone
650 // truncate initial interval
656 { // fix apparent logic bug when fe==-1
657 ranges.addElement(iv); // add (truncated) reversed interval
658 iv = (int[]) fromShifts2.elementAt(i);
660 { iv[1], iv[0] }; // reverse and clone
664 // interval is already reversed
667 ranges.addElement(iv); // add only - or final range
669 // create array of start end intervals.
671 if (ranges != null && ranges.size() > 0)
673 range = new int[ranges.size() * 2];
675 intvSize = ranges.size();
677 while (intv < intvSize)
679 iv = (int[]) ranges.elementAt(intv);
682 ranges.setElementAt(null, intv++); // remove
689 * get the 'initial' position of mpos in To
693 * @return position of first word in to reference frame
695 public int getToPosition(int mpos)
697 int[] mp = shiftTo(mpos);
706 * get range of positions in To frame for the mpos word in From
710 * @return null or int[] first position in To for mpos, last position in to
713 public int[] getToWord(int mpos)
715 int[] mp = shiftTo(mpos);
719 { mp[0], mp[0] + mp[2] * (getFromRatio() - 1) };
725 * get From position in the associated reference frame for position pos in the
726 * associated sequence.
731 public int getMappedPosition(int pos)
733 int[] mp = shiftFrom(pos);
741 public int[] getMappedWord(int pos)
743 int[] mp = shiftFrom(pos);
747 { mp[0], mp[0] + mp[2] * (getToRatio() - 1) };
753 * test routine. not incremental.
759 public static void testMap(MapList ml, int fromS, int fromE)
761 for (int from = 1; from <= 25; from++)
763 int[] too = ml.shiftFrom(from);
764 System.out.print("ShiftFrom(" + from + ")==");
767 System.out.print("NaN\n");
771 System.out.print(too[0] + " % " + too[1] + " (" + too[2] + ")");
772 System.out.print("\t+--+\t");
773 int[] toofrom = ml.shiftTo(too[0]);
776 if (toofrom[0] != from)
778 System.err.println("Mapping not reflexive:" + from + " "
779 + too[0] + "->" + toofrom[0]);
781 System.out.println("ShiftTo(" + too[0] + ")==" + toofrom[0]
782 + " % " + toofrom[1] + " (" + toofrom[2] + ")");
786 System.out.println("ShiftTo(" + too[0] + ")=="
787 + "NaN! - not Bijective Mapping!");
791 int mmap[][] = ml.makeFromMap();
792 System.out.println("FromMap : (" + mmap[0][0] + " " + mmap[0][1] + " "
793 + mmap[0][2] + " " + mmap[0][3] + " ");
794 for (int i = 1; i <= mmap[1].length; i++)
796 if (mmap[1][i - 1] == -1)
798 System.out.print(i + "=XXX");
803 System.out.print(i + "=" + (mmap[0][2] + mmap[1][i - 1]));
807 System.out.print("\n");
811 System.out.print(",");
814 // test range function
815 System.out.print("\nTest locateInFrom\n");
817 int f = mmap[0][2], t = mmap[0][3];
820 System.out.println("Range " + f + " to " + t);
821 int rng[] = ml.locateInFrom(f, t);
824 for (int i = 0; i < rng.length; i++)
826 System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
831 System.out.println("No range!");
833 System.out.print("\nReversed\n");
834 rng = ml.locateInFrom(t, f);
837 for (int i = 0; i < rng.length; i++)
839 System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
844 System.out.println("No range!");
846 System.out.print("\n");
851 System.out.print("\n");
852 mmap = ml.makeToMap();
853 System.out.println("ToMap : (" + mmap[0][0] + " " + mmap[0][1] + " "
854 + mmap[0][2] + " " + mmap[0][3] + " ");
855 for (int i = 1; i <= mmap[1].length; i++)
857 if (mmap[1][i - 1] == -1)
859 System.out.print(i + "=XXX");
864 System.out.print(i + "=" + (mmap[0][2] + mmap[1][i - 1]));
868 System.out.print("\n");
872 System.out.print(",");
875 System.out.print("\n");
876 // test range function
877 System.out.print("\nTest locateInTo\n");
879 int f = mmap[0][2], t = mmap[0][3];
882 System.out.println("Range " + f + " to " + t);
883 int rng[] = ml.locateInTo(f, t);
886 for (int i = 0; i < rng.length; i++)
888 System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
893 System.out.println("No range!");
895 System.out.print("\nReversed\n");
896 rng = ml.locateInTo(t, f);
899 for (int i = 0; i < rng.length; i++)
901 System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
906 System.out.println("No range!");
910 System.out.print("\n");
916 public static void main(String argv[])
918 MapList ml = new MapList(new int[]
919 { 1, 5, 10, 15, 25, 20 }, new int[]
921 MapList ml1 = new MapList(new int[]
922 { 1, 3, 17, 4 }, new int[]
924 MapList ml2 = new MapList(new int[]
927 // test internal consistency
928 int to[] = new int[51];
929 MapList.testMap(ml, 1, 60);
930 MapList mldna = new MapList(new int[]
931 { 2, 2, 6, 8, 12, 16 }, new int[]
933 int[] frm = mldna.locateInFrom(1, 1);
934 testLocateFrom(mldna, 1, 1, new int[]
936 MapList.testMap(mldna, 1, 3);
938 * for (int from=1; from<=51; from++) { int[] too=ml.shiftTo(from); int[]
939 * toofrom=ml.shiftFrom(too[0]);
940 * System.out.println("ShiftFrom("+from+")=="+too[0]+" %
941 * "+too[1]+"\t+-+\tShiftTo("+too[0]+")=="+toofrom[0]+" % "+toofrom[1]); }
943 System.out.print("Success?\n"); // if we get here - something must be
947 private static void testLocateFrom(MapList mldna, int i, int j, int[] ks)
949 int[] frm = mldna.locateInFrom(i, j);
950 if (frm == ks || java.util.Arrays.equals(frm, ks))
952 System.out.println("Success test locate from " + i + " to " + j);
956 System.err.println("Failed test locate from " + i + " to " + j);
957 for (int c = 0; c < frm.length; c++)
959 System.err.print(frm[c] + ((c % 2 == 0) ? "," : ";"));
961 System.err.println("Expected");
962 for (int c = 0; c < ks.length; c++)
964 System.err.print(ks[c] + ((c % 2 == 0) ? "," : ";"));
971 * @return a MapList whose From range is this maplist's To Range, and vice
974 public MapList getInverse()
976 return new MapList(getToRanges(), getFromRanges(), getToRatio(),
981 * test for containment rather than equivalence to another mapping
984 * to be tested for containment
985 * @return true if local or mapped range map contains or is contained by this
988 public boolean containsEither(boolean local, MapList map)
992 return ((getFromLowest() >= map.getFromLowest() && getFromHighest() <= map
993 .getFromHighest()) || (getFromLowest() <= map.getFromLowest() && getFromHighest() >= map
998 return ((getToLowest() >= map.getToLowest() && getToHighest() <= map
999 .getToHighest()) || (getToLowest() <= map.getToLowest() && getToHighest() >= map