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