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