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