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<>();
  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    * There is no validation check that the ranges do not overlap each other.
 213    *
 214    * @param from
 215    *          contiguous regions as [start1, end1, start2, end2, ...]
 216    * @param to
 217    *          same format as 'from'
 218    * @param fromRatio
 219    *          phrase length in 'from' (e.g. 3 for dna)
 220    * @param toRatio
 221    *          phrase length in 'to' (e.g. 1 for protein)
 222    */
 223   public MapList(int from[], int to[], int fromRatio, int toRatio)
 224   {
 225     this();
 226     this.fromRatio = fromRatio;
 227     this.toRatio = toRatio;
 228     fromLowest = Integer.MAX_VALUE;
 229     fromHighest = Integer.MIN_VALUE;
 230
 231     for (int i = 0; i < from.length; i += 2)
 232     {
 233       /*
 234        * note lowest and highest values - bearing in mind the
 235        * direction may be reversed
 236        */
 237       fromLowest = Math.min(fromLowest, Math.min(from[i], from[i + 1]));
 238       fromHighest = Math.max(fromHighest, Math.max(from[i], from[i + 1]));
 239       fromShifts.add(new int[] { from[i], from[i + 1] });
 240     }
 241
 242     toLowest = Integer.MAX_VALUE;
 243     toHighest = Integer.MIN_VALUE;
 244     for (int i = 0; i < to.length; i += 2)
 245     {
 246       toLowest = Math.min(toLowest, Math.min(to[i], to[i + 1]));
 247       toHighest = Math.max(toHighest, Math.max(to[i], to[i + 1]));
 248       toShifts.add(new int[] { to[i], to[i + 1] });
 249     }
 250   }
 251
 252   /**
 253    * Copy constructor. Creates an identical mapping.
 254    *
 255    * @param map
 256    */
 257   public MapList(MapList map)
 258   {
 259     this();
 260     // TODO not used - remove?
 261     this.fromLowest = map.fromLowest;
 262     this.fromHighest = map.fromHighest;
 263     this.toLowest = map.toLowest;
 264     this.toHighest = map.toHighest;
 265
 266     this.fromRatio = map.fromRatio;
 267     this.toRatio = map.toRatio;
 268     if (map.fromShifts != null)
 269     {
 270       for (int[] r : map.fromShifts)
 271       {
 272         fromShifts.add(new int[] { r[0], r[1] });
 273       }
 274     }
 275     if (map.toShifts != null)
 276     {
 277       for (int[] r : map.toShifts)
 278       {
 279         toShifts.add(new int[] { r[0], r[1] });
 280       }
 281     }
 282   }
 283
 284   /**
 285    * Constructor given ranges as lists of [start, end] positions. There is no
 286    * validation check that the ranges do not overlap each other.
 287    *
 288    * @param fromRange
 289    * @param toRange
 290    * @param fromRatio
 291    * @param toRatio
 292    */
 293   public MapList(List<int[]> fromRange, List<int[]> toRange, int fromRatio,
 294           int toRatio)
 295   {
 296     this();
 297     fromRange = coalesceRanges(fromRange);
 298     toRange = coalesceRanges(toRange);
 299     this.fromShifts = fromRange;
 300     this.toShifts = toRange;
 301     this.fromRatio = fromRatio;
 302     this.toRatio = toRatio;
 303
 304     fromLowest = Integer.MAX_VALUE;
 305     fromHighest = Integer.MIN_VALUE;
 306     for (int[] range : fromRange)
 307     {
 308       if (range.length != 2)
 309       {
 310         // throw new IllegalArgumentException(range);
 311         System.err.println("Invalid format for fromRange "
 312                 + Arrays.toString(range) + " may cause errors");
 313       }
 314       fromLowest = Math.min(fromLowest, Math.min(range[0], range[1]));
 315       fromHighest = Math.max(fromHighest, Math.max(range[0], range[1]));
 316     }
 317
 318     toLowest = Integer.MAX_VALUE;
 319     toHighest = Integer.MIN_VALUE;
 320     for (int[] range : toRange)
 321     {
 322       if (range.length != 2)
 323       {
 324         // throw new IllegalArgumentException(range);
 325         System.err.println("Invalid format for toRange "
 326                 + Arrays.toString(range) + " may cause errors");
 327       }
 328       toLowest = Math.min(toLowest, Math.min(range[0], range[1]));
 329       toHighest = Math.max(toHighest, Math.max(range[0], range[1]));
 330     }
 331   }
 332
 333   /**
 334    * Consolidates a list of ranges so that any contiguous ranges are merged.
 335    * This assumes the ranges are already in start order (does not sort them).
 336    * <p>
 337    * The main use case for this method is when mapping cDNA sequence to its
 338    * protein product, based on CDS feature ranges which derive from spliced
 339    * exons, but are contiguous on the cDNA sequence. For example
 340    * <pre>
 341    *   CDS 1-20  // from exon1
 342    *   CDS 21-35 // from exon2
 343    *   CDS 36-71 // from exon3
 344    * 'coalesce' to range 1-71
 345    * </pre>
 346    *
 347    * @param ranges
 348    * @return the same list (if unchanged), else a new merged list, leaving the
 349    *         input list unchanged
 350    */
 351   public static List<int[]> coalesceRanges(final List<int[]> ranges)
 352   {
 353     if (ranges == null || ranges.size() < 2)
 354     {
 355       return ranges;
 356     }
 357
 358     boolean changed = false;
 359     List<int[]> merged = new ArrayList<>();
 360     int[] lastRange = ranges.get(0);
 361     int lastDirection = lastRange[1] >= lastRange[0] ? 1 : -1;
 362     lastRange = new int[] { lastRange[0], lastRange[1] };
 363     merged.add(lastRange);
 364     boolean first = true;
 365
 366     for (final int[] range : ranges)
 367     {
 368       if (first)
 369       {
 370         first = false;
 371         continue;
 372       }
 373
 374       int direction = range[1] >= range[0] ? 1 : -1;
 375
 376       /*
 377        * if next range is in the same direction as last and contiguous,
 378        * just update the end position of the last range
 379        */
 380       boolean sameDirection = range[1] == range[0]
 381               || direction == lastDirection;
 382       boolean extending = range[0] == lastRange[1] + lastDirection;
 383       if (sameDirection && 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<>();
 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()
 952               && getFromHighest() <= map.getFromHighest())
 953               || (getFromLowest() <= map.getFromLowest()
 954                       && getFromHighest() >= map.getFromHighest()));
 955     }
 956     else
 957     {
 958       return ((getToLowest() >= map.getToLowest()
 959               && getToHighest() <= map.getToHighest())
 960               || (getToLowest() <= map.getToLowest()
 961                       && getToHighest() >= map.getToHighest()));
 962     }
 963   }
 964
 965   /**
 966    * String representation - for debugging, not guaranteed not to change
 967    */
 968   @Override
 969   public String toString()
 970   {
 971     StringBuilder sb = new StringBuilder(64);
 972     sb.append("[");
 973     for (int[] shift : fromShifts)
 974     {
 975       sb.append(" ").append(Arrays.toString(shift));
 976     }
 977     sb.append(" ] ");
 978     sb.append(fromRatio).append(":").append(toRatio);
 979     sb.append(" to [");
 980     for (int[] shift : toShifts)
 981     {
 982       sb.append(" ").append(Arrays.toString(shift));
 983     }
 984     sb.append(" ]");
 985     return sb.toString();
 986   }
 987
 988   /**
 989    * Extend this map list by adding the given map's ranges. There is no
 990    * validation check that the ranges do not overlap existing ranges (or each
 991    * other), but contiguous ranges are merged.
 992    *
 993    * @param map
 994    */
 995   public void addMapList(MapList map)
 996   {
 997     if (this.equals(map))
 998     {
 999       return;
1000     }
1001     this.fromLowest = Math.min(fromLowest, map.fromLowest);
1002     this.toLowest = Math.min(toLowest, map.toLowest);
1003     this.fromHighest = Math.max(fromHighest, map.fromHighest);
1004     this.toHighest = Math.max(toHighest, map.toHighest);
1005
1006     for (int[] range : map.getFromRanges())
1007     {
1008       addRange(range, fromShifts);
1009     }
1010     for (int[] range : map.getToRanges())
1011     {
1012       addRange(range, toShifts);
1013     }
1014   }
1015
1016   /**
1017    * Adds the given range to a list of ranges. If the new range just extends
1018    * existing ranges, the current endpoint is updated instead.
1019    *
1020    * @param range
1021    * @param addTo
1022    */
1023   static void addRange(int[] range, List<int[]> addTo)
1024   {
1025     /*
1026      * list is empty - add to it!
1027      */
1028     if (addTo.size() == 0)
1029     {
1030       addTo.add(range);
1031       return;
1032     }
1033
1034     int[] last = addTo.get(addTo.size() - 1);
1035     boolean lastForward = last[1] >= last[0];
1036     boolean newForward = range[1] >= range[0];
1037
1038     /*
1039      * contiguous range in the same direction - just update endpoint
1040      */
1041     if (lastForward == newForward && last[1] == range[0])
1042     {
1043       last[1] = range[1];
1044       return;
1045     }
1046
1047     /*
1048      * next range starts at +1 in forward sense - update endpoint
1049      */
1050     if (lastForward && newForward && range[0] == last[1] + 1)
1051     {
1052       last[1] = range[1];
1053       return;
1054     }
1055
1056     /*
1057      * next range starts at -1 in reverse sense - update endpoint
1058      */
1059     if (!lastForward && !newForward && range[0] == last[1] - 1)
1060     {
1061       last[1] = range[1];
1062       return;
1063     }
1064
1065     /*
1066      * just add the new range
1067      */
1068     addTo.add(range);
1069   }
1070
1071   /**
1072    * Returns true if mapping is from forward strand, false if from reverse
1073    * strand. Result is just based on the first 'from' range that is not a single
1074    * position. Default is true unless proven to be false. Behaviour is not well
1075    * defined if the mapping has a mixture of forward and reverse ranges.
1076    *
1077    * @return
1078    */
1079   public boolean isFromForwardStrand()
1080   {
1081     return isForwardStrand(getFromRanges());
1082   }
1083
1084   /**
1085    * Returns true if mapping is to forward strand, false if to reverse strand.
1086    * Result is just based on the first 'to' range that is not a single position.
1087    * Default is true unless proven to be false. Behaviour is not well defined if
1088    * the mapping has a mixture of forward and reverse ranges.
1089    *
1090    * @return
1091    */
1092   public boolean isToForwardStrand()
1093   {
1094     return isForwardStrand(getToRanges());
1095   }
1096
1097   /**
1098    * A helper method that returns true unless at least one range has start >
1099    * end. Behaviour is undefined for a mixture of forward and reverse ranges.
1100    *
1101    * @param ranges
1102    * @return
1103    */
1104   private boolean isForwardStrand(List<int[]> ranges)
1105   {
1106     boolean forwardStrand = true;
1107     for (int[] range : ranges)
1108     {
1109       if (range[1] > range[0])
1110       {
1111         break; // forward strand confirmed
1112       }
1113       else if (range[1] < range[0])
1114       {
1115         forwardStrand = false;
1116         break; // reverse strand confirmed
1117       }
1118     }
1119     return forwardStrand;
1120   }
1121
1122   /**
1123    *
1124    * @return true if from, or to is a three to 1 mapping
1125    */
1126   public boolean isTripletMap()
1127   {
1128     return (toRatio == 3 && fromRatio == 1)
1129             || (fromRatio == 3 && toRatio == 1);
1130   }
1131
1132   /**
1133    * Returns a map which is the composite of this one and the input map. That
1134    * is, the output map has the fromRanges of this map, and its toRanges are the
1135    * toRanges of this map as transformed by the input map.
1136    * <p>
1137    * Returns null if the mappings cannot be traversed (not all toRanges of this
1138    * map correspond to fromRanges of the input), or if this.toRatio does not
1139    * match map.fromRatio.
1140    *
1141    * <pre>
1142    * Example 1:
1143    *    this:   from [1-100] to [501-600]
1144    *    input:  from [10-40] to [60-90]
1145    *    output: from [10-40] to [560-590]
1146    * Example 2 ('reverse strand exons'):
1147    *    this:   from [1-100] to [2000-1951], [1000-951] // transcript to loci
1148    *    input:  from [1-50]  to [41-90] // CDS to transcript
1149    *    output: from [10-40] to [1960-1951], [1000-971] // CDS to gene loci
1150    * </pre>
1151    *
1152    * @param map
1153    * @return
1154    */
1155   public MapList traverse(MapList map)
1156   {
1157     if (map == null)
1158     {
1159       return null;
1160     }
1161
1162     /*
1163      * compound the ratios by this rule:
1164      * A:B with M:N gives A*M:B*N
1165      * reduced by greatest common divisor
1166      * so 1:3 with 3:3 is 3:9 or 1:3
1167      * 1:3 with 3:1 is 3:3 or 1:1
1168      * 1:3 with 1:3 is 1:9
1169      * 2:5 with 3:7 is 6:35
1170      */
1171     int outFromRatio = getFromRatio() * map.getFromRatio();
1172     int outToRatio = getToRatio() * map.getToRatio();
1173     int gcd = MathUtils.gcd(outFromRatio, outToRatio);
1174     outFromRatio /= gcd;
1175     outToRatio /= gcd;
1176
1177     List<int[]> toRanges = new ArrayList<>();
1178     for (int[] range : getToRanges())
1179     {
1180       int[] transferred = map.locateInTo(range[0], range[1]);
1181       if (transferred == null || transferred.length % 2 != 0)
1182       {
1183         return null;
1184       }
1185
1186       /*
1187        *  convert [start1, end1, start2, end2, ...]
1188        *  to [[start1, end1], [start2, end2], ...]
1189        */
1190       for (int i = 0; i < transferred.length;)
1191       {
1192         toRanges.add(new int[] { transferred[i], transferred[i + 1] });
1193         i += 2;
1194       }
1195     }
1196
1197     return new MapList(getFromRanges(), toRanges, outFromRatio, outToRatio);
1198   }
1199
1200   /**
1201    * Answers true if the mapping is from one contiguous range to another, else
1202    * false
1203    *
1204    * @return
1205    */
1206   public boolean isContiguous()
1207   {
1208     return fromShifts.size() == 1 && toShifts.size() == 1;
1209   }
1210 }