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