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