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<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       return ranges;
 347     }
 348
 349     boolean changed = false;
 350     List<int[]> merged = new ArrayList<int[]>();
 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] && range[1] <= lastRange[1])
 376               || (lastDirection == -1 && range[0] <= lastRange[0]
 377                       && range[0] >= lastRange[1]
 378                       && range[1] <= lastRange[0] && range[1] >= lastRange[1]))
 379       {
 380         changed = true;
 381         continue;
 382       }
 383
 384       int direction = range[1] >= range[0] ? 1 : -1;
 385
 386       /*
 387        * if next range is in the same direction as last and contiguous,
 388        * just update the end position of the last range
 389        */
 390       boolean sameDirection = range[1] == range[0] || direction == lastDirection;
 391       boolean extending = range[0] == lastRange[1] + lastDirection;
 392       boolean overlapping = (lastDirection == 1 && range[0] >= lastRange[0] && range[0] <= lastRange[1])
 393               || (lastDirection == -1 && range[0] <= lastRange[0] && range[0] >= lastRange[1]);
 394       if (sameDirection && (overlapping || extending))
 395       {
 396         lastRange[1] = range[1];
 397         changed = true;
 398       }
 399       else
 400       {
 401         lastRange = new int[] { range[0], range[1] };
 402         merged.add(lastRange);
 403         // careful: merging [5, 5] after [7, 6] should keep negative direction
 404         lastDirection = (range[1] == range[0]) ? lastDirection : direction;
 405       }
 406     }
 407
 408     return changed ? merged : ranges;
 409   }
 410
 411   /**
 412    * get all mapped positions from 'from' to 'to'
 413    *
 414    * @return int[][] { int[] { fromStart, fromFinish, toStart, toFinish }, int
 415    *         [fromFinish-fromStart+2] { toStart..toFinish mappings}}
 416    */
 417   protected int[][] makeFromMap()
 418   {
 419     // TODO not used - remove??
 420     return posMap(fromShifts, fromRatio, toShifts, toRatio);
 421   }
 422
 423   /**
 424    * get all mapped positions from 'to' to 'from'
 425    *
 426    * @return int[to position]=position mapped in from
 427    */
 428   protected int[][] makeToMap()
 429   {
 430     // TODO not used - remove??
 431     return posMap(toShifts, toRatio, fromShifts, fromRatio);
 432   }
 433
 434   /**
 435    * construct an int map for intervals in intVals
 436    *
 437    * @param shiftTo
 438    * @return int[] { from, to pos in range }, int[range.to-range.from+1]
 439    *         returning mapped position
 440    */
 441   private int[][] posMap(List<int[]> shiftTo, int ratio,
 442           List<int[]> shiftFrom, int toRatio)
 443   {
 444     // TODO not used - remove??
 445     int iv = 0, ivSize = shiftTo.size();
 446     if (iv >= ivSize)
 447     {
 448       return null;
 449     }
 450     int[] intv = shiftTo.get(iv++);
 451     int from = intv[0], to = intv[1];
 452     if (from > to)
 453     {
 454       from = intv[1];
 455       to = intv[0];
 456     }
 457     while (iv < ivSize)
 458     {
 459       intv = shiftTo.get(iv++);
 460       if (intv[0] < from)
 461       {
 462         from = intv[0];
 463       }
 464       if (intv[1] < from)
 465       {
 466         from = intv[1];
 467       }
 468       if (intv[0] > to)
 469       {
 470         to = intv[0];
 471       }
 472       if (intv[1] > to)
 473       {
 474         to = intv[1];
 475       }
 476     }
 477     int tF = 0, tT = 0;
 478     int mp[][] = new int[to - from + 2][];
 479     for (int i = 0; i < mp.length; i++)
 480     {
 481       int[] m = shift(i + from, shiftTo, ratio, shiftFrom, toRatio);
 482       if (m != null)
 483       {
 484         if (i == 0)
 485         {
 486           tF = tT = m[0];
 487         }
 488         else
 489         {
 490           if (m[0] < tF)
 491           {
 492             tF = m[0];
 493           }
 494           if (m[0] > tT)
 495           {
 496             tT = m[0];
 497           }
 498         }
 499       }
 500       mp[i] = m;
 501     }
 502     int[][] map = new int[][] { new int[] { from, to, tF, tT },
 503         new int[to - from + 2] };
 504
 505     map[0][2] = tF;
 506     map[0][3] = tT;
 507
 508     for (int i = 0; i < mp.length; i++)
 509     {
 510       if (mp[i] != null)
 511       {
 512         map[1][i] = mp[i][0] - tF;
 513       }
 514       else
 515       {
 516         map[1][i] = -1; // indicates an out of range mapping
 517       }
 518     }
 519     return map;
 520   }
 521
 522   /**
 523    * addShift
 524    *
 525    * @param pos
 526    *          start position for shift (in original reference frame)
 527    * @param shift
 528    *          length of shift
 529    *
 530    *          public void addShift(int pos, int shift) { int sidx = 0; int[]
 531    *          rshift=null; while (sidx<shifts.size() && (rshift=(int[])
 532    *          shifts.elementAt(sidx))[0]<pos) sidx++; if (sidx==shifts.size())
 533    *          shifts.insertElementAt(new int[] { pos, shift}, sidx); else
 534    *          rshift[1]+=shift; }
 535    */
 536
 537   /**
 538    * shift from pos to To(pos)
 539    *
 540    * @param pos
 541    *          int
 542    * @return int shifted position in To, frameshift in From, direction of mapped
 543    *         symbol in To
 544    */
 545   public int[] shiftFrom(int pos)
 546   {
 547     return shift(pos, fromShifts, fromRatio, toShifts, toRatio);
 548   }
 549
 550   /**
 551    * inverse of shiftFrom - maps pos in To to a position in From
 552    *
 553    * @param pos
 554    *          (in To)
 555    * @return shifted position in From, frameshift in To, direction of mapped
 556    *         symbol in From
 557    */
 558   public int[] shiftTo(int pos)
 559   {
 560     return shift(pos, toShifts, toRatio, fromShifts, fromRatio);
 561   }
 562
 563   /**
 564    *
 565    * @param shiftTo
 566    * @param fromRatio
 567    * @param shiftFrom
 568    * @param toRatio
 569    * @return
 570    */
 571   protected static int[] shift(int pos, List<int[]> shiftTo, int fromRatio,
 572           List<int[]> shiftFrom, int toRatio)
 573   {
 574     // TODO: javadoc; tests
 575     int[] fromCount = countPos(shiftTo, pos);
 576     if (fromCount == null)
 577     {
 578       return null;
 579     }
 580     int fromRemainder = (fromCount[0] - 1) % fromRatio;
 581     int toCount = 1 + (((fromCount[0] - 1) / fromRatio) * toRatio);
 582     int[] toPos = countToPos(shiftFrom, toCount);
 583     if (toPos == null)
 584     {
 585       return null; // throw new Error("Bad Mapping!");
 586     }
 587     // System.out.println(fromCount[0]+" "+fromCount[1]+" "+toCount);
 588     return new int[] { toPos[0], fromRemainder, toPos[1] };
 589   }
 590
 591   /**
 592    * count how many positions pos is along the series of intervals.
 593    *
 594    * @param shiftTo
 595    * @param pos
 596    * @return number of positions or null if pos is not within intervals
 597    */
 598   protected static int[] countPos(List<int[]> shiftTo, int pos)
 599   {
 600     int count = 0, intv[], iv = 0, ivSize = shiftTo.size();
 601     while (iv < ivSize)
 602     {
 603       intv = shiftTo.get(iv++);
 604       if (intv[0] <= intv[1])
 605       {
 606         if (pos >= intv[0] && pos <= intv[1])
 607         {
 608           return new int[] { count + pos - intv[0] + 1, +1 };
 609         }
 610         else
 611         {
 612           count += intv[1] - intv[0] + 1;
 613         }
 614       }
 615       else
 616       {
 617         if (pos >= intv[1] && pos <= intv[0])
 618         {
 619           return new int[] { count + intv[0] - pos + 1, -1 };
 620         }
 621         else
 622         {
 623           count += intv[0] - intv[1] + 1;
 624         }
 625       }
 626     }
 627     return null;
 628   }
 629
 630   /**
 631    * count out pos positions into a series of intervals and return the position
 632    *
 633    * @param shiftFrom
 634    * @param pos
 635    * @return position pos in interval set
 636    */
 637   protected static int[] countToPos(List<int[]> shiftFrom, int pos)
 638   {
 639     int count = 0, diff = 0, iv = 0, ivSize = shiftFrom.size();
 640     int[] intv = { 0, 0 };
 641     while (iv < ivSize)
 642     {
 643       intv = shiftFrom.get(iv++);
 644       diff = intv[1] - intv[0];
 645       if (diff >= 0)
 646       {
 647         if (pos <= count + 1 + diff)
 648         {
 649           return new int[] { pos - count - 1 + intv[0], +1 };
 650         }
 651         else
 652         {
 653           count += 1 + diff;
 654         }
 655       }
 656       else
 657       {
 658         if (pos <= count + 1 - diff)
 659         {
 660           return new int[] { intv[0] - (pos - count - 1), -1 };
 661         }
 662         else
 663         {
 664           count += 1 - diff;
 665         }
 666       }
 667     }
 668     return null;// (diff<0) ? (intv[1]-1) : (intv[0]+1);
 669   }
 670
 671   /**
 672    * find series of intervals mapping from start-end in the From map.
 673    *
 674    * @param start
 675    *          position mapped 'to'
 676    * @param end
 677    *          position mapped 'to'
 678    * @return series of [start, end] ranges in sequence mapped 'from'
 679    */
 680   public int[] locateInFrom(int start, int end)
 681   {
 682     // inefficient implementation
 683     int fromStart[] = shiftTo(start);
 684     // needs to be inclusive of end of symbol position
 685     int fromEnd[] = shiftTo(end);
 686
 687     return getIntervals(fromShifts, fromStart, fromEnd, fromRatio);
 688   }
 689
 690   /**
 691    * find series of intervals mapping from start-end in the to map.
 692    *
 693    * @param start
 694    *          position mapped 'from'
 695    * @param end
 696    *          position mapped 'from'
 697    * @return series of [start, end] ranges in sequence mapped 'to'
 698    */
 699   public int[] locateInTo(int start, int end)
 700   {
 701     int toStart[] = shiftFrom(start);
 702     int toEnd[] = shiftFrom(end);
 703     return getIntervals(toShifts, toStart, toEnd, toRatio);
 704   }
 705
 706   /**
 707    * like shift - except returns the intervals in the given vector of shifts
 708    * which were spanned in traversing fromStart to fromEnd
 709    *
 710    * @param shiftFrom
 711    * @param fromStart
 712    * @param fromEnd
 713    * @param fromRatio2
 714    * @return series of from,to intervals from from first position of starting
 715    *         region to final position of ending region inclusive
 716    */
 717   protected static int[] getIntervals(List<int[]> shiftFrom,
 718           int[] fromStart, int[] fromEnd, int fromRatio2)
 719   {
 720     if (fromStart == null || fromEnd == null)
 721     {
 722       return null;
 723     }
 724     int startpos, endpos;
 725     startpos = fromStart[0]; // first position in fromStart
 726     endpos = fromEnd[0]; // last position in fromEnd
 727     int endindx = (fromRatio2 - 1); // additional positions to get to last
 728     // position from endpos
 729     int intv = 0, intvSize = shiftFrom.size();
 730     int iv[], i = 0, fs = -1, fe_s = -1, fe = -1; // containing intervals
 731     // search intervals to locate ones containing startpos and count endindx
 732     // positions on from endpos
 733     while (intv < intvSize && (fs == -1 || fe == -1))
 734     {
 735       iv = shiftFrom.get(intv++);
 736       if (fe_s > -1)
 737       {
 738         endpos = iv[0]; // start counting from beginning of interval
 739         endindx--; // inclusive of endpos
 740       }
 741       if (iv[0] <= iv[1])
 742       {
 743         if (fs == -1 && startpos >= iv[0] && startpos <= iv[1])
 744         {
 745           fs = i;
 746         }
 747         if (endpos >= iv[0] && endpos <= iv[1])
 748         {
 749           if (fe_s == -1)
 750           {
 751             fe_s = i;
 752           }
 753           if (fe_s != -1)
 754           {
 755             if (endpos + endindx <= iv[1])
 756             {
 757               fe = i;
 758               endpos = endpos + endindx; // end of end token is within this
 759               // interval
 760             }
 761             else
 762             {
 763               endindx -= iv[1] - endpos; // skip all this interval too
 764             }
 765           }
 766         }
 767       }
 768       else
 769       {
 770         if (fs == -1 && startpos <= iv[0] && startpos >= iv[1])
 771         {
 772           fs = i;
 773         }
 774         if (endpos <= iv[0] && endpos >= iv[1])
 775         {
 776           if (fe_s == -1)
 777           {
 778             fe_s = i;
 779           }
 780           if (fe_s != -1)
 781           {
 782             if (endpos - endindx >= iv[1])
 783             {
 784               fe = i;
 785               endpos = endpos - endindx; // end of end token is within this
 786               // interval
 787             }
 788             else
 789             {
 790               endindx -= endpos - iv[1]; // skip all this interval too
 791             }
 792           }
 793         }
 794       }
 795       i++;
 796     }
 797     if (fs == fe && fe == -1)
 798     {
 799       return null;
 800     }
 801     List<int[]> ranges = new ArrayList<int[]>();
 802     if (fs <= fe)
 803     {
 804       intv = fs;
 805       i = fs;
 806       // truncate initial interval
 807       iv = shiftFrom.get(intv++);
 808       iv = new int[] { iv[0], iv[1] };// clone
 809       if (i == fs)
 810       {
 811         iv[0] = startpos;
 812       }
 813       while (i != fe)
 814       {
 815         ranges.add(iv); // add initial range
 816         iv = shiftFrom.get(intv++); // get next interval
 817         iv = new int[] { iv[0], iv[1] };// clone
 818         i++;
 819       }
 820       if (i == fe)
 821       {
 822         iv[1] = endpos;
 823       }
 824       ranges.add(iv); // add only - or final range
 825     }
 826     else
 827     {
 828       // walk from end of interval.
 829       i = shiftFrom.size() - 1;
 830       while (i > fs)
 831       {
 832         i--;
 833       }
 834       iv = shiftFrom.get(i);
 835       iv = new int[] { iv[1], iv[0] };// reverse and clone
 836       // truncate initial interval
 837       if (i == fs)
 838       {
 839         iv[0] = startpos;
 840       }
 841       while (--i != fe)
 842       { // fix apparent logic bug when fe==-1
 843         ranges.add(iv); // add (truncated) reversed interval
 844         iv = shiftFrom.get(i);
 845         iv = new int[] { iv[1], iv[0] }; // reverse and clone
 846       }
 847       if (i == fe)
 848       {
 849         // interval is already reversed
 850         iv[1] = endpos;
 851       }
 852       ranges.add(iv); // add only - or final range
 853     }
 854     // create array of start end intervals.
 855     int[] range = null;
 856     if (ranges != null && ranges.size() > 0)
 857     {
 858       range = new int[ranges.size() * 2];
 859       intv = 0;
 860       intvSize = ranges.size();
 861       i = 0;
 862       while (intv < intvSize)
 863       {
 864         iv = ranges.get(intv);
 865         range[i++] = iv[0];
 866         range[i++] = iv[1];
 867         ranges.set(intv++, null); // remove
 868       }
 869     }
 870     return range;
 871   }
 872
 873   /**
 874    * get the 'initial' position of mpos in To
 875    *
 876    * @param mpos
 877    *          position in from
 878    * @return position of first word in to reference frame
 879    */
 880   public int getToPosition(int mpos)
 881   {
 882     // TODO not used - remove??
 883     int[] mp = shiftTo(mpos);
 884     if (mp != null)
 885     {
 886       return mp[0];
 887     }
 888     return mpos;
 889   }
 890
 891   /**
 892    * get range of positions in To frame for the mpos word in From
 893    *
 894    * @param mpos
 895    *          position in From
 896    * @return null or int[] first position in To for mpos, last position in to
 897    *         for Mpos
 898    */
 899   public int[] getToWord(int mpos)
 900   {
 901     int[] mp = shiftTo(mpos);
 902     if (mp != null)
 903     {
 904       return new int[] { mp[0], mp[0] + mp[2] * (getFromRatio() - 1) };
 905     }
 906     return null;
 907   }
 908
 909   /**
 910    * get From position in the associated reference frame for position pos in the
 911    * associated sequence.
 912    *
 913    * @param pos
 914    * @return
 915    */
 916   public int getMappedPosition(int pos)
 917   {
 918     // TODO not used - remove??
 919     int[] mp = shiftFrom(pos);
 920     if (mp != null)
 921     {
 922       return mp[0];
 923     }
 924     return pos;
 925   }
 926
 927   public int[] getMappedWord(int pos)
 928   {
 929     // TODO not used - remove??
 930     int[] mp = shiftFrom(pos);
 931     if (mp != null)
 932     {
 933       return new int[] { mp[0], mp[0] + mp[2] * (getToRatio() - 1) };
 934     }
 935     return null;
 936   }
 937
 938   /**
 939    *
 940    * @return a MapList whose From range is this maplist's To Range, and vice
 941    *         versa
 942    */
 943   public MapList getInverse()
 944   {
 945     return new MapList(getToRanges(), getFromRanges(), getToRatio(),
 946             getFromRatio());
 947   }
 948
 949   /**
 950    * test for containment rather than equivalence to another mapping
 951    *
 952    * @param map
 953    *          to be tested for containment
 954    * @return true if local or mapped range map contains or is contained by this
 955    *         mapping
 956    */
 957   public boolean containsEither(boolean local, MapList map)
 958   {
 959     // TODO not used - remove?
 960     if (local)
 961     {
 962       return ((getFromLowest() >= map.getFromLowest() && getFromHighest() <= map
 963               .getFromHighest()) || (getFromLowest() <= map.getFromLowest() && getFromHighest() >= map
 964               .getFromHighest()));
 965     }
 966     else
 967     {
 968       return ((getToLowest() >= map.getToLowest() && getToHighest() <= map
 969               .getToHighest()) || (getToLowest() <= map.getToLowest() && getToHighest() >= map
 970               .getToHighest()));
 971     }
 972   }
 973
 974   /**
 975    * String representation - for debugging, not guaranteed not to change
 976    */
 977   @Override
 978   public String toString()
 979   {
 980     StringBuilder sb = new StringBuilder(64);
 981     sb.append("[");
 982     for (int[] shift : fromShifts)
 983     {
 984       sb.append(" ").append(Arrays.toString(shift));
 985     }
 986     sb.append(" ] ");
 987     sb.append(fromRatio).append(":").append(toRatio);
 988     sb.append(" to [");
 989     for (int[] shift : toShifts)
 990     {
 991       sb.append(" ").append(Arrays.toString(shift));
 992     }
 993     sb.append(" ]");
 994     return sb.toString();
 995   }
 996
 997   /**
 998    * Extend this map list by adding the given map's ranges. There is no
 999    * validation check that the ranges do not overlap existing ranges (or each
1000    * other), but contiguous ranges are merged.
1001    *
1002    * @param map
1003    */
1004   public void addMapList(MapList map)
1005   {
1006     if (this.equals(map))
1007     {
1008       return;
1009     }
1010     this.fromLowest = Math.min(fromLowest, map.fromLowest);
1011     this.toLowest = Math.min(toLowest, map.toLowest);
1012     this.fromHighest = Math.max(fromHighest, map.fromHighest);
1013     this.toHighest = Math.max(toHighest, map.toHighest);
1014
1015     for (int[] range : map.getFromRanges())
1016     {
1017       addRange(range, fromShifts);
1018     }
1019     for (int[] range : map.getToRanges())
1020     {
1021       addRange(range, toShifts);
1022     }
1023   }
1024
1025   /**
1026    * Adds the given range to a list of ranges. If the new range just extends
1027    * existing ranges, the current endpoint is updated instead.
1028    *
1029    * @param range
1030    * @param addTo
1031    */
1032   static void addRange(int[] range, List<int[]> addTo)
1033   {
1034     /*
1035      * list is empty - add to it!
1036      */
1037     if (addTo.size() == 0)
1038     {
1039       addTo.add(range);
1040       return;
1041     }
1042
1043     int[] last = addTo.get(addTo.size() - 1);
1044     boolean lastForward = last[1] >= last[0];
1045     boolean newForward = range[1] >= range[0];
1046
1047     /*
1048      * contiguous range in the same direction - just update endpoint
1049      */
1050     if (lastForward == newForward && last[1] == range[0])
1051     {
1052       last[1] = range[1];
1053       return;
1054     }
1055
1056     /*
1057      * next range starts at +1 in forward sense - update endpoint
1058      */
1059     if (lastForward && newForward && range[0] == last[1] + 1)
1060     {
1061       last[1] = range[1];
1062       return;
1063     }
1064
1065     /*
1066      * next range starts at -1 in reverse sense - update endpoint
1067      */
1068     if (!lastForward && !newForward && range[0] == last[1] - 1)
1069     {
1070       last[1] = range[1];
1071       return;
1072     }
1073
1074     /*
1075      * just add the new range
1076      */
1077     addTo.add(range);
1078   }
1079
1080   /**
1081    * Returns true if mapping is from forward strand, false if from reverse
1082    * strand. Result is just based on the first 'from' range that is not a single
1083    * position. Default is true unless proven to be false. Behaviour is not well
1084    * defined if the mapping has a mixture of forward and reverse ranges.
1085    *
1086    * @return
1087    */
1088   public boolean isFromForwardStrand()
1089   {
1090     boolean forwardStrand = true;
1091     for (int[] range : getFromRanges())
1092     {
1093       if (range[1] > range[0])
1094       {
1095         break; // forward strand confirmed
1096       }
1097       else if (range[1] < range[0])
1098       {
1099         forwardStrand = false;
1100         break; // reverse strand confirmed
1101       }
1102     }
1103     return forwardStrand;
1104   }
1105
1106   /**
1107    *
1108    * @return true if from, or to is a three to 1 mapping
1109    */
1110   public boolean isTripletMap()
1111   {
1112     return (toRatio == 3 && fromRatio == 1)
1113             || (fromRatio == 3 && toRatio == 1);
1114   }
1115
1116 }