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