58abdc3926c1bf1badddf8e83e4b0724c06b30da
[jalview.git] / MapList.java
1 /*
2  * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
3  * Copyright (C) $$Year-Rel$$ The Jalview Authors
4  * 
5  * This file is part of Jalview.
6  * 
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.
11  *  
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.
16  * 
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.
20  */
21 package jalview.util;
22
23 import java.util.ArrayList;
24 import java.util.Arrays;
25 import java.util.List;
26
27 /**
28  * A simple way of bijectively mapping a non-contiguous linear range to another
29  * non-contiguous linear range.
30  * 
31  * Use at your own risk!
32  * 
33  * TODO: efficient implementation of private posMap method
34  * 
35  * TODO: test/ensure that sense of from and to ratio start position is conserved
36  * (codon start position recovery)
37  */
38 public class MapList
39 {
40
41   /*
42    * Subregions (base 1) described as { [start1, end1], [start2, end2], ...}
43    */
44   private List<int[]> fromShifts;
45
46   /*
47    * Same format as fromShifts, for the 'mapped to' sequence
48    */
49   private List<int[]> toShifts;
50
51   /*
52    * number of steps in fromShifts to one toRatio unit
53    */
54   private int fromRatio;
55
56   /*
57    * number of steps in toShifts to one fromRatio
58    */
59   private int toRatio;
60
61   /*
62    * lowest and highest value in the from Map
63    */
64   private int fromLowest;
65
66   private int fromHighest;
67
68   /*
69    * lowest and highest value in the to Map
70    */
71   private int toLowest;
72
73   private int toHighest;
74
75   /**
76    * Constructor
77    */
78   public MapList()
79   {
80     fromShifts = new ArrayList<int[]>();
81     toShifts = new ArrayList<int[]>();
82   }
83
84   /**
85    * Two MapList objects are equal if they are the same object, or they both
86    * have populated shift ranges and all values are the same.
87    */
88   @Override
89   public boolean equals(Object o)
90   {
91     if (o == null || !(o instanceof MapList))
92     {
93       return false;
94     }
95
96     MapList obj = (MapList) o;
97     if (obj == this)
98     {
99       return true;
100     }
101     if (obj.fromRatio != fromRatio || obj.toRatio != toRatio
102             || obj.fromShifts == null || obj.toShifts == null)
103     {
104       return false;
105     }
106     return Arrays
107             .deepEquals(fromShifts.toArray(), obj.fromShifts.toArray())
108             && Arrays
109                     .deepEquals(toShifts.toArray(), obj.toShifts.toArray());
110   }
111
112   /**
113    * Returns a hashcode made from the fromRatio, toRatio, and from/to ranges
114    */
115   @Override
116   public int hashCode()
117   {
118     int hashCode = 31 * fromRatio;
119     hashCode = 31 * hashCode + toRatio;
120     hashCode = 31 * hashCode + fromShifts.toArray().hashCode();
121     hashCode = 31 * hashCode + toShifts.toArray().hashCode();
122     return hashCode;
123   }
124
125   /**
126    * Returns the 'from' ranges as {[start1, end1], [start2, end2], ...}
127    * 
128    * @return
129    */
130   public List<int[]> getFromRanges()
131   {
132     return fromShifts;
133   }
134
135   /**
136    * Returns the 'to' ranges as {[start1, end1], [start2, end2], ...}
137    * 
138    * @return
139    */
140   public List<int[]> getToRanges()
141   {
142     return toShifts;
143   }
144
145   /**
146    * Flattens a list of [start, end] into a single [start1, end1, start2,
147    * end2,...] array.
148    * 
149    * @param shifts
150    * @return
151    */
152   protected static int[] getRanges(List<int[]> shifts)
153   {
154     int[] rnges = new int[2 * shifts.size()];
155     int i = 0;
156     for (int[] r : shifts)
157     {
158       rnges[i++] = r[0];
159       rnges[i++] = r[1];
160     }
161     return rnges;
162   }
163
164   /**
165    * 
166    * @return length of mapped phrase in from
167    */
168   public int getFromRatio()
169   {
170     return fromRatio;
171   }
172
173   /**
174    * 
175    * @return length of mapped phrase in to
176    */
177   public int getToRatio()
178   {
179     return toRatio;
180   }
181
182   public int getFromLowest()
183   {
184     return fromLowest;
185   }
186
187   public int getFromHighest()
188   {
189     return fromHighest;
190   }
191
192   public int getToLowest()
193   {
194     return toLowest;
195   }
196
197   public int getToHighest()
198   {
199     return toHighest;
200   }
201
202   /**
203    * Constructor given from and to ranges as [start1, end1, start2, end2,...].
204    * If any end is equal to the next start, the ranges will be merged. There is
205    * no validation check that the ranges do not overlap each other.
206    * 
207    * @param from
208    *          contiguous regions as [start1, end1, start2, end2, ...]
209    * @param to
210    *          same format as 'from'
211    * @param fromRatio
212    *          phrase length in 'from' (e.g. 3 for dna)
213    * @param toRatio
214    *          phrase length in 'to' (e.g. 1 for protein)
215    */
216   public MapList(int from[], int to[], int fromRatio, int toRatio)
217   {
218     this();
219     this.fromRatio = fromRatio;
220     this.toRatio = toRatio;
221     fromLowest = Integer.MAX_VALUE;
222     fromHighest = Integer.MIN_VALUE;
223     int added = 0;
224
225     for (int i = 0; i < from.length; i += 2)
226     {
227       /*
228        * note lowest and highest values - bearing in mind the
229        * direction may be reversed
230        */
231       fromLowest = Math.min(fromLowest, Math.min(from[i], from[i + 1]));
232       fromHighest = Math.max(fromHighest, Math.max(from[i], from[i + 1]));
233       if (added > 0 && from[i] == fromShifts.get(added - 1)[1])
234       {
235         /*
236          * this range starts where the last ended - just extend it
237          */
238         fromShifts.get(added - 1)[1] = from[i + 1];
239       }
240       else
241       {
242         fromShifts.add(new int[] { from[i], from[i + 1] });
243         added++;
244       }
245     }
246
247     toLowest = Integer.MAX_VALUE;
248     toHighest = Integer.MIN_VALUE;
249     added = 0;
250     for (int i = 0; i < to.length; i += 2)
251     {
252       toLowest = Math.min(toLowest, Math.min(to[i], to[i + 1]));
253       toHighest = Math.max(toHighest, Math.max(to[i], to[i + 1]));
254       if (added > 0 && to[i] == toShifts.get(added - 1)[1])
255       {
256         toShifts.get(added - 1)[1] = to[i + 1];
257       }
258       else
259       {
260         toShifts.add(new int[] { to[i], to[i + 1] });
261         added++;
262       }
263     }
264   }
265
266   /**
267    * Copy constructor. Creates an identical mapping.
268    * 
269    * @param map
270    */
271   public MapList(MapList map)
272   {
273     this();
274     // TODO not used - remove?
275     this.fromLowest = map.fromLowest;
276     this.fromHighest = map.fromHighest;
277     this.toLowest = map.toLowest;
278     this.toHighest = map.toHighest;
279
280     this.fromRatio = map.fromRatio;
281     this.toRatio = map.toRatio;
282     if (map.fromShifts != null)
283     {
284       for (int[] r : map.fromShifts)
285       {
286         fromShifts.add(new int[] { r[0], r[1] });
287       }
288     }
289     if (map.toShifts != null)
290     {
291       for (int[] r : map.toShifts)
292       {
293         toShifts.add(new int[] { r[0], r[1] });
294       }
295     }
296   }
297
298   /**
299    * Constructor given ranges as lists of [start, end] positions. There is no
300    * validation check that the ranges do not overlap each other.
301    * 
302    * @param fromRange
303    * @param toRange
304    * @param fromRatio
305    * @param toRatio
306    */
307   public MapList(List<int[]> fromRange, List<int[]> toRange, int fromRatio,
308           int toRatio)
309   {
310     this();
311     fromRange = coalesceRanges(fromRange);
312     toRange = coalesceRanges(toRange);
313     this.fromShifts = fromRange;
314     this.toShifts = toRange;
315     this.fromRatio = fromRatio;
316     this.toRatio = toRatio;
317
318     fromLowest = Integer.MAX_VALUE;
319     fromHighest = Integer.MIN_VALUE;
320     for (int[] range : fromRange)
321     {
322       fromLowest = Math.min(fromLowest, Math.min(range[0], range[1]));
323       fromHighest = Math.max(fromHighest, Math.max(range[0], range[1]));
324     }
325
326     toLowest = Integer.MAX_VALUE;
327     toHighest = Integer.MIN_VALUE;
328     for (int[] range : toRange)
329     {
330       toLowest = Math.min(toLowest, Math.min(range[0], range[1]));
331       toHighest = Math.max(toHighest, Math.max(range[0], range[1]));
332     }
333   }
334
335   /**
336    * Consolidates a list of ranges so that any contiguous ranges are merged.
337    * This assumes the ranges are already in start order (does not sort them).
338    * 
339    * @param ranges
340    * @return the same list (if unchanged), else a new merged list, leaving the
341    *         input list unchanged
342    */
343   public static List<int[]> coalesceRanges(final List<int[]> ranges)
344   {
345     if (ranges == null || ranges.size() < 2)
346     {
347       return ranges;
348     }
349
350     boolean changed = false;
351     List<int[]> merged = new ArrayList<int[]>();
352     int[] lastRange = ranges.get(0);
353     int lastDirection = lastRange[1] >= lastRange[0] ? 1 : -1;
354     lastRange = new int[] { lastRange[0], lastRange[1] };
355     merged.add(lastRange);
356     boolean first = true;
357
358     for (final int[] range : ranges)
359     {
360       if (first)
361       {
362         first = false;
363         continue;
364       }
365       if (range[0] == lastRange[0] && range[1] == lastRange[1])
366       {
367         // drop duplicate range
368         changed = true;
369         continue;
370       }
371
372       /*
373        * drop this range if it lies within the last range
374        */
375       if ((lastDirection == 1 && range[0] >= lastRange[0]
376               && range[0] <= lastRange[1] && range[1] >= lastRange[0] && range[1] <= lastRange[1])
377               || (lastDirection == -1 && range[0] <= lastRange[0]
378                       && range[0] >= lastRange[1]
379                       && range[1] <= lastRange[0] && range[1] >= lastRange[1]))
380       {
381         changed = true;
382         continue;
383       }
384
385       int direction = range[1] >= range[0] ? 1 : -1;
386
387       /*
388        * if next range is in the same direction as last and contiguous,
389        * just update the end position of the last range
390        */
391       boolean sameDirection = range[1] == range[0]
392               || direction == lastDirection;
393       boolean extending = range[0] == lastRange[1] + lastDirection;
394       boolean overlapping = (lastDirection == 1 && range[0] >= lastRange[0] && range[0] <= lastRange[1])
395               || (lastDirection == -1 && range[0] <= lastRange[0] && range[0] >= lastRange[1]);
396       if (sameDirection && (overlapping || extending))
397       {
398         lastRange[1] = range[1];
399         changed = true;
400       }
401       else
402       {
403         lastRange = new int[] { range[0], range[1] };
404         merged.add(lastRange);
405         // careful: merging [5, 5] after [7, 6] should keep negative direction
406         lastDirection = (range[1] == range[0]) ? lastDirection : direction;
407       }
408     }
409
410     return changed ? merged : ranges;
411   }
412
413   /**
414    * get all mapped positions from 'from' to 'to'
415    * 
416    * @return int[][] { int[] { fromStart, fromFinish, toStart, toFinish }, int
417    *         [fromFinish-fromStart+2] { toStart..toFinish mappings}}
418    */
419   protected int[][] makeFromMap()
420   {
421     // TODO not used - remove??
422     return posMap(fromShifts, fromRatio, toShifts, toRatio);
423   }
424
425   /**
426    * get all mapped positions from 'to' to 'from'
427    * 
428    * @return int[to position]=position mapped in from
429    */
430   protected int[][] makeToMap()
431   {
432     // TODO not used - remove??
433     return posMap(toShifts, toRatio, fromShifts, fromRatio);
434   }
435
436   /**
437    * construct an int map for intervals in intVals
438    * 
439    * @param shiftTo
440    * @return int[] { from, to pos in range }, int[range.to-range.from+1]
441    *         returning mapped position
442    */
443   private int[][] posMap(List<int[]> shiftTo, int ratio,
444           List<int[]> shiftFrom, int toRatio)
445   {
446     // TODO not used - remove??
447     int iv = 0, ivSize = shiftTo.size();
448     if (iv >= ivSize)
449     {
450       return null;
451     }
452     int[] intv = shiftTo.get(iv++);
453     int from = intv[0], to = intv[1];
454     if (from > to)
455     {
456       from = intv[1];
457       to = intv[0];
458     }
459     while (iv < ivSize)
460     {
461       intv = shiftTo.get(iv++);
462       if (intv[0] < from)
463       {
464         from = intv[0];
465       }
466       if (intv[1] < from)
467       {
468         from = intv[1];
469       }
470       if (intv[0] > to)
471       {
472         to = intv[0];
473       }
474       if (intv[1] > to)
475       {
476         to = intv[1];
477       }
478     }
479     int tF = 0, tT = 0;
480     int mp[][] = new int[to - from + 2][];
481     for (int i = 0; i < mp.length; i++)
482     {
483       int[] m = shift(i + from, shiftTo, ratio, shiftFrom, toRatio);
484       if (m != null)
485       {
486         if (i == 0)
487         {
488           tF = tT = m[0];
489         }
490         else
491         {
492           if (m[0] < tF)
493           {
494             tF = m[0];
495           }
496           if (m[0] > tT)
497           {
498             tT = m[0];
499           }
500         }
501       }
502       mp[i] = m;
503     }
504     int[][] map = new int[][] { new int[] { from, to, tF, tT },
505         new int[to - from + 2] };
506
507     map[0][2] = tF;
508     map[0][3] = tT;
509
510     for (int i = 0; i < mp.length; i++)
511     {
512       if (mp[i] != null)
513       {
514         map[1][i] = mp[i][0] - tF;
515       }
516       else
517       {
518         map[1][i] = -1; // indicates an out of range mapping
519       }
520     }
521     return map;
522   }
523
524   /**
525    * addShift
526    * 
527    * @param pos
528    *          start position for shift (in original reference frame)
529    * @param shift
530    *          length of shift
531    * 
532    *          public void addShift(int pos, int shift) { int sidx = 0; int[]
533    *          rshift=null; while (sidx<shifts.size() && (rshift=(int[])
534    *          shifts.elementAt(sidx))[0]<pos) sidx++; if (sidx==shifts.size())
535    *          shifts.insertElementAt(new int[] { pos, shift}, sidx); else
536    *          rshift[1]+=shift; }
537    */
538
539   /**
540    * shift from pos to To(pos)
541    * 
542    * @param pos
543    *          int
544    * @return int shifted position in To, frameshift in From, direction of mapped
545    *         symbol in To
546    */
547   public int[] shiftFrom(int pos)
548   {
549     return shift(pos, fromShifts, fromRatio, toShifts, toRatio);
550   }
551
552   /**
553    * inverse of shiftFrom - maps pos in To to a position in From
554    * 
555    * @param pos
556    *          (in To)
557    * @return shifted position in From, frameshift in To, direction of mapped
558    *         symbol in From
559    */
560   public int[] shiftTo(int pos)
561   {
562     return shift(pos, toShifts, toRatio, fromShifts, fromRatio);
563   }
564
565   /**
566    * 
567    * @param shiftTo
568    * @param fromRatio
569    * @param shiftFrom
570    * @param toRatio
571    * @return
572    */
573   protected static int[] shift(int pos, List<int[]> shiftTo, int fromRatio,
574           List<int[]> shiftFrom, int toRatio)
575   {
576     // TODO: javadoc; tests
577     int[] fromCount = countPos(shiftTo, pos);
578     if (fromCount == null)
579     {
580       return null;
581     }
582     int fromRemainder = (fromCount[0] - 1) % fromRatio;
583     int toCount = 1 + (((fromCount[0] - 1) / fromRatio) * toRatio);
584     int[] toPos = countToPos(shiftFrom, toCount);
585     if (toPos == null)
586     {
587       return null; // throw new Error("Bad Mapping!");
588     }
589     // System.out.println(fromCount[0]+" "+fromCount[1]+" "+toCount);
590     return new int[] { toPos[0], fromRemainder, toPos[1] };
591   }
592
593   /**
594    * count how many positions pos is along the series of intervals.
595    * 
596    * @param shiftTo
597    * @param pos
598    * @return number of positions or null if pos is not within intervals
599    */
600   protected static int[] countPos(List<int[]> shiftTo, int pos)
601   {
602     int count = 0, intv[], iv = 0, ivSize = shiftTo.size();
603     while (iv < ivSize)
604     {
605       intv = shiftTo.get(iv++);
606       if (intv[0] <= intv[1])
607       {
608         if (pos >= intv[0] && pos <= intv[1])
609         {
610           return new int[] { count + pos - intv[0] + 1, +1 };
611         }
612         else
613         {
614           count += intv[1] - intv[0] + 1;
615         }
616       }
617       else
618       {
619         if (pos >= intv[1] && pos <= intv[0])
620         {
621           return new int[] { count + intv[0] - pos + 1, -1 };
622         }
623         else
624         {
625           count += intv[0] - intv[1] + 1;
626         }
627       }
628     }
629     return null;
630   }
631
632   /**
633    * count out pos positions into a series of intervals and return the position
634    * 
635    * @param shiftFrom
636    * @param pos
637    * @return position pos in interval set
638    */
639   protected static int[] countToPos(List<int[]> shiftFrom, int pos)
640   {
641     int count = 0, diff = 0, iv = 0, ivSize = shiftFrom.size();
642     int[] intv = { 0, 0 };
643     while (iv < ivSize)
644     {
645       intv = shiftFrom.get(iv++);
646       diff = intv[1] - intv[0];
647       if (diff >= 0)
648       {
649         if (pos <= count + 1 + diff)
650         {
651           return new int[] { pos - count - 1 + intv[0], +1 };
652         }
653         else
654         {
655           count += 1 + diff;
656         }
657       }
658       else
659       {
660         if (pos <= count + 1 - diff)
661         {
662           return new int[] { intv[0] - (pos - count - 1), -1 };
663         }
664         else
665         {
666           count += 1 - diff;
667         }
668       }
669     }
670     return null;// (diff<0) ? (intv[1]-1) : (intv[0]+1);
671   }
672
673   /**
674    * find series of intervals mapping from start-end in the From map.
675    * 
676    * @param start
677    *          position mapped 'to'
678    * @param end
679    *          position mapped 'to'
680    * @return series of [start, end] ranges in sequence mapped 'from'
681    */
682   public int[] locateInFrom(int start, int end)
683   {
684     // inefficient implementation
685     int fromStart[] = shiftTo(start);
686     // needs to be inclusive of end of symbol position
687     int fromEnd[] = shiftTo(end);
688
689     return getIntervals(fromShifts, fromStart, fromEnd, fromRatio);
690   }
691
692   /**
693    * find series of intervals mapping from start-end in the to map.
694    * 
695    * @param start
696    *          position mapped 'from'
697    * @param end
698    *          position mapped 'from'
699    * @return series of [start, end] ranges in sequence mapped 'to'
700    */
701   public int[] locateInTo(int start, int end)
702   {
703     int toStart[] = shiftFrom(start);
704     int toEnd[] = shiftFrom(end);
705     return getIntervals(toShifts, toStart, toEnd, toRatio);
706   }
707
708   /**
709    * like shift - except returns the intervals in the given vector of shifts
710    * which were spanned in traversing fromStart to fromEnd
711    * 
712    * @param shiftFrom
713    * @param fromStart
714    * @param fromEnd
715    * @param fromRatio2
716    * @return series of from,to intervals from from first position of starting
717    *         region to final position of ending region inclusive
718    */
719   protected static int[] getIntervals(List<int[]> shiftFrom,
720           int[] fromStart, int[] fromEnd, int fromRatio2)
721   {
722     if (fromStart == null || fromEnd == null)
723     {
724       return null;
725     }
726     int startpos, endpos;
727     startpos = fromStart[0]; // first position in fromStart
728     endpos = fromEnd[0]; // last position in fromEnd
729     int endindx = (fromRatio2 - 1); // additional positions to get to last
730     // position from endpos
731     int intv = 0, intvSize = shiftFrom.size();
732     int iv[], i = 0, fs = -1, fe_s = -1, fe = -1; // containing intervals
733     // search intervals to locate ones containing startpos and count endindx
734     // positions on from endpos
735     while (intv < intvSize && (fs == -1 || fe == -1))
736     {
737       iv = shiftFrom.get(intv++);
738       if (fe_s > -1)
739       {
740         endpos = iv[0]; // start counting from beginning of interval
741         endindx--; // inclusive of endpos
742       }
743       if (iv[0] <= iv[1])
744       {
745         if (fs == -1 && startpos >= iv[0] && startpos <= iv[1])
746         {
747           fs = i;
748         }
749         if (endpos >= iv[0] && endpos <= iv[1])
750         {
751           if (fe_s == -1)
752           {
753             fe_s = i;
754           }
755           if (fe_s != -1)
756           {
757             if (endpos + endindx <= iv[1])
758             {
759               fe = i;
760               endpos = endpos + endindx; // end of end token is within this
761               // interval
762             }
763             else
764             {
765               endindx -= iv[1] - endpos; // skip all this interval too
766             }
767           }
768         }
769       }
770       else
771       {
772         if (fs == -1 && startpos <= iv[0] && startpos >= iv[1])
773         {
774           fs = i;
775         }
776         if (endpos <= iv[0] && endpos >= iv[1])
777         {
778           if (fe_s == -1)
779           {
780             fe_s = i;
781           }
782           if (fe_s != -1)
783           {
784             if (endpos - endindx >= iv[1])
785             {
786               fe = i;
787               endpos = endpos - endindx; // end of end token is within this
788               // interval
789             }
790             else
791             {
792               endindx -= endpos - iv[1]; // skip all this interval too
793             }
794           }
795         }
796       }
797       i++;
798     }
799     if (fs == fe && fe == -1)
800     {
801       return null;
802     }
803     List<int[]> ranges = new ArrayList<int[]>();
804     if (fs <= fe)
805     {
806       intv = fs;
807       i = fs;
808       // truncate initial interval
809       iv = shiftFrom.get(intv++);
810       iv = new int[] { iv[0], iv[1] };// clone
811       if (i == fs)
812       {
813         iv[0] = startpos;
814       }
815       while (i != fe)
816       {
817         ranges.add(iv); // add initial range
818         iv = shiftFrom.get(intv++); // get next interval
819         iv = new int[] { iv[0], iv[1] };// clone
820         i++;
821       }
822       if (i == fe)
823       {
824         iv[1] = endpos;
825       }
826       ranges.add(iv); // add only - or final range
827     }
828     else
829     {
830       // walk from end of interval.
831       i = shiftFrom.size() - 1;
832       while (i > fs)
833       {
834         i--;
835       }
836       iv = shiftFrom.get(i);
837       iv = new int[] { iv[1], iv[0] };// reverse and clone
838       // truncate initial interval
839       if (i == fs)
840       {
841         iv[0] = startpos;
842       }
843       while (--i != fe)
844       { // fix apparent logic bug when fe==-1
845         ranges.add(iv); // add (truncated) reversed interval
846         iv = shiftFrom.get(i);
847         iv = new int[] { iv[1], iv[0] }; // reverse and clone
848       }
849       if (i == fe)
850       {
851         // interval is already reversed
852         iv[1] = endpos;
853       }
854       ranges.add(iv); // add only - or final range
855     }
856     // create array of start end intervals.
857     int[] range = null;
858     if (ranges != null && ranges.size() > 0)
859     {
860       range = new int[ranges.size() * 2];
861       intv = 0;
862       intvSize = ranges.size();
863       i = 0;
864       while (intv < intvSize)
865       {
866         iv = ranges.get(intv);
867         range[i++] = iv[0];
868         range[i++] = iv[1];
869         ranges.set(intv++, null); // remove
870       }
871     }
872     return range;
873   }
874
875   /**
876    * get the 'initial' position of mpos in To
877    * 
878    * @param mpos
879    *          position in from
880    * @return position of first word in to reference frame
881    */
882   public int getToPosition(int mpos)
883   {
884     // TODO not used - remove??
885     int[] mp = shiftTo(mpos);
886     if (mp != null)
887     {
888       return mp[0];
889     }
890     return mpos;
891   }
892
893   /**
894    * get range of positions in To frame for the mpos word in From
895    * 
896    * @param mpos
897    *          position in From
898    * @return null or int[] first position in To for mpos, last position in to
899    *         for Mpos
900    */
901   public int[] getToWord(int mpos)
902   {
903     int[] mp = shiftTo(mpos);
904     if (mp != null)
905     {
906       return new int[] { mp[0], mp[0] + mp[2] * (getFromRatio() - 1) };
907     }
908     return null;
909   }
910
911   /**
912    * get From position in the associated reference frame for position pos in the
913    * associated sequence.
914    * 
915    * @param pos
916    * @return
917    */
918   public int getMappedPosition(int pos)
919   {
920     // TODO not used - remove??
921     int[] mp = shiftFrom(pos);
922     if (mp != null)
923     {
924       return mp[0];
925     }
926     return pos;
927   }
928
929   public int[] getMappedWord(int pos)
930   {
931     // TODO not used - remove??
932     int[] mp = shiftFrom(pos);
933     if (mp != null)
934     {
935       return new int[] { mp[0], mp[0] + mp[2] * (getToRatio() - 1) };
936     }
937     return null;
938   }
939
940   /**
941    * 
942    * @return a MapList whose From range is this maplist's To Range, and vice
943    *         versa
944    */
945   public MapList getInverse()
946   {
947     return new MapList(getToRanges(), getFromRanges(), getToRatio(),
948             getFromRatio());
949   }
950
951   /**
952    * test for containment rather than equivalence to another mapping
953    * 
954    * @param map
955    *          to be tested for containment
956    * @return true if local or mapped range map contains or is contained by this
957    *         mapping
958    */
959   public boolean containsEither(boolean local, MapList map)
960   {
961     // TODO not used - remove?
962     if (local)
963     {
964       return ((getFromLowest() >= map.getFromLowest() && getFromHighest() <= map
965               .getFromHighest()) || (getFromLowest() <= map.getFromLowest() && getFromHighest() >= map
966               .getFromHighest()));
967     }
968     else
969     {
970       return ((getToLowest() >= map.getToLowest() && getToHighest() <= map
971               .getToHighest()) || (getToLowest() <= map.getToLowest() && getToHighest() >= map
972               .getToHighest()));
973     }
974   }
975
976   /**
977    * String representation - for debugging, not guaranteed not to change
978    */
979   @Override
980   public String toString()
981   {
982     StringBuilder sb = new StringBuilder(64);
983     sb.append("[");
984     for (int[] shift : fromShifts)
985     {
986       sb.append(" ").append(Arrays.toString(shift));
987     }
988     sb.append(" ] ");
989     sb.append(fromRatio).append(":").append(toRatio);
990     sb.append(" to [");
991     for (int[] shift : toShifts)
992     {
993       sb.append(" ").append(Arrays.toString(shift));
994     }
995     sb.append(" ]");
996     return sb.toString();
997   }
998
999   /**
1000    * Extend this map list by adding the given map's ranges. There is no
1001    * validation check that the ranges do not overlap existing ranges (or each
1002    * other), but contiguous ranges are merged.
1003    * 
1004    * @param map
1005    */
1006   public void addMapList(MapList map)
1007   {
1008     if (this.equals(map))
1009     {
1010       return;
1011     }
1012     this.fromLowest = Math.min(fromLowest, map.fromLowest);
1013     this.toLowest = Math.min(toLowest, map.toLowest);
1014     this.fromHighest = Math.max(fromHighest, map.fromHighest);
1015     this.toHighest = Math.max(toHighest, map.toHighest);
1016
1017     for (int[] range : map.getFromRanges())
1018     {
1019       addRange(range, fromShifts);
1020     }
1021     for (int[] range : map.getToRanges())
1022     {
1023       addRange(range, toShifts);
1024     }
1025   }
1026
1027   /**
1028    * Adds the given range to a list of ranges. If the new range just extends
1029    * existing ranges, the current endpoint is updated instead.
1030    * 
1031    * @param range
1032    * @param addTo
1033    */
1034   static void addRange(int[] range, List<int[]> addTo)
1035   {
1036     /*
1037      * list is empty - add to it!
1038      */
1039     if (addTo.size() == 0)
1040     {
1041       addTo.add(range);
1042       return;
1043     }
1044
1045     int[] last = addTo.get(addTo.size() - 1);
1046     boolean lastForward = last[1] >= last[0];
1047     boolean newForward = range[1] >= range[0];
1048
1049     /*
1050      * contiguous range in the same direction - just update endpoint
1051      */
1052     if (lastForward == newForward && last[1] == range[0])
1053     {
1054       last[1] = range[1];
1055       return;
1056     }
1057
1058     /*
1059      * next range starts at +1 in forward sense - update endpoint
1060      */
1061     if (lastForward && newForward && range[0] == last[1] + 1)
1062     {
1063       last[1] = range[1];
1064       return;
1065     }
1066
1067     /*
1068      * next range starts at -1 in reverse sense - update endpoint
1069      */
1070     if (!lastForward && !newForward && range[0] == last[1] - 1)
1071     {
1072       last[1] = range[1];
1073       return;
1074     }
1075
1076     /*
1077      * just add the new range
1078      */
1079     addTo.add(range);
1080   }
1081
1082   /**
1083    * Returns true if mapping is from forward strand, false if from reverse
1084    * strand. Result is just based on the first 'from' range that is not a single
1085    * position. Default is true unless proven to be false. Behaviour is not well
1086    * defined if the mapping has a mixture of forward and reverse ranges.
1087    * 
1088    * @return
1089    */
1090   public boolean isFromForwardStrand()
1091   {
1092     boolean forwardStrand = true;
1093     for (int[] range : getFromRanges())
1094     {
1095       if (range[1] > range[0])
1096       {
1097         break; // forward strand confirmed
1098       }
1099       else if (range[1] < range[0])
1100       {
1101         forwardStrand = false;
1102         break; // reverse strand confirmed
1103       }
1104     }
1105     return forwardStrand;
1106   }
1107
1108   /**
1109    * 
1110    * @return true if from, or to is a three to 1 mapping
1111    */
1112   public boolean isTripletMap()
1113   {
1114     return (toRatio == 3 && fromRatio == 1)
1115             || (fromRatio == 3 && toRatio == 1);
1116   }
1117
1118 }