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