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