src/jalview/util/MapList.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer (Version 2.9.0b2)
   3  * Copyright (C) 2015 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 = new ArrayList<int[]>();
  45
  46   /*
  47    * Same format as fromShifts, for the 'mapped to' sequence
  48    */
  49   private List<int[]> toShifts = new ArrayList<int[]>();
  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    * Two MapList objects are equal if they are the same object, or they both
  77    * have populated shift ranges and all values are the same.
  78    */
  79   @Override
  80   public boolean equals(Object o)
  81   {
  82     // TODO should also override hashCode to ensure equal objects have equal
  83     // hashcodes
  84     if (o == null || !(o instanceof MapList))
  85     {
  86       return false;
  87     }
  88
  89     MapList obj = (MapList) o;
  90     if (obj == this)
  91     {
  92       return true;
  93     }
  94     if (obj.fromRatio != fromRatio || obj.toRatio != toRatio
  95             || obj.fromShifts == null || obj.toShifts == null)
  96     {
  97       return false;
  98     }
  99     return Arrays
 100             .deepEquals(fromShifts.toArray(), obj.fromShifts.toArray())
 101             && Arrays
 102                     .deepEquals(toShifts.toArray(), obj.toShifts.toArray());
 103   }
 104
 105   /**
 106    * Returns the 'from' ranges as {[start1, end1], [start2, end2], ...}
 107    *
 108    * @return
 109    */
 110   public List<int[]> getFromRanges()
 111   {
 112     return fromShifts;
 113   }
 114
 115   /**
 116    * Returns the 'to' ranges as {[start1, end1], [start2, end2], ...}
 117    *
 118    * @return
 119    */
 120   public List<int[]> getToRanges()
 121   {
 122     return toShifts;
 123   }
 124
 125   /**
 126    * Flattens a list of [start, end] into a single [start1, end1, start2,
 127    * end2,...] array.
 128    *
 129    * @param shifts
 130    * @return
 131    */
 132   protected static int[] getRanges(List<int[]> shifts)
 133   {
 134     int[] rnges = new int[2 * shifts.size()];
 135     int i = 0;
 136     for (int[] r : shifts)
 137     {
 138       rnges[i++] = r[0];
 139       rnges[i++] = r[1];
 140     }
 141     return rnges;
 142   }
 143
 144   /**
 145    *
 146    * @return length of mapped phrase in from
 147    */
 148   public int getFromRatio()
 149   {
 150     return fromRatio;
 151   }
 152
 153   /**
 154    *
 155    * @return length of mapped phrase in to
 156    */
 157   public int getToRatio()
 158   {
 159     return toRatio;
 160   }
 161
 162   public int getFromLowest()
 163   {
 164     return fromLowest;
 165   }
 166
 167   public int getFromHighest()
 168   {
 169     return fromHighest;
 170   }
 171
 172   public int getToLowest()
 173   {
 174     return toLowest;
 175   }
 176
 177   public int getToHighest()
 178   {
 179     return toHighest;
 180   }
 181
 182   /**
 183    * Constructor.
 184    *
 185    * @param from
 186    *          contiguous regions as [start1, end1, start2, end2, ...]
 187    * @param to
 188    *          same format as 'from'
 189    * @param fromRatio
 190    *          phrase length in 'from' (e.g. 3 for dna)
 191    * @param toRatio
 192    *          phrase length in 'to' (e.g. 1 for protein)
 193    */
 194   public MapList(int from[], int to[], int fromRatio, int toRatio)
 195   {
 196     this.fromRatio = fromRatio;
 197     this.toRatio = toRatio;
 198     fromLowest = from[0];
 199     fromHighest = from[1];
 200     for (int i = 0; i < from.length; i += 2)
 201     {
 202       fromLowest = Math.min(fromLowest, from[i]);
 203       fromHighest = Math.max(fromHighest, from[i + 1]);
 204
 205       fromShifts.add(new int[] { from[i], from[i + 1] });
 206     }
 207
 208     toLowest = to[0];
 209     toHighest = to[1];
 210     for (int i = 0; i < to.length; i += 2)
 211     {
 212       toLowest = Math.min(toLowest, to[i]);
 213       toHighest = Math.max(toHighest, to[i + 1]);
 214       toShifts.add(new int[] { to[i], to[i + 1] });
 215     }
 216   }
 217
 218   /**
 219    * Copy constructor. Creates an identical mapping.
 220    *
 221    * @param map
 222    */
 223   public MapList(MapList map)
 224   {
 225     // TODO not used - remove?
 226     this.fromLowest = map.fromLowest;
 227     this.fromHighest = map.fromHighest;
 228     this.toLowest = map.toLowest;
 229     this.toHighest = map.toHighest;
 230
 231     this.fromRatio = map.fromRatio;
 232     this.toRatio = map.toRatio;
 233     if (map.fromShifts != null)
 234     {
 235       for (int[] r : map.fromShifts)
 236       {
 237         fromShifts.add(new int[] { r[0], r[1] });
 238       }
 239     }
 240     if (map.toShifts != null)
 241     {
 242       for (int[] r : map.toShifts)
 243       {
 244         toShifts.add(new int[] { r[0], r[1] });
 245       }
 246     }
 247   }
 248
 249   /**
 250    * Constructor given ranges as lists of [start, end] positions
 251    *
 252    * @param fromRange
 253    * @param toRange
 254    * @param fromRatio
 255    * @param toRatio
 256    */
 257   public MapList(List<int[]> fromRange, List<int[]> toRange, int fromRatio,
 258           int toRatio)
 259   {
 260     this.fromShifts = fromRange;
 261     this.toShifts = toRange;
 262     this.fromRatio = fromRatio;
 263     this.toRatio = toRatio;
 264
 265     fromLowest = Integer.MAX_VALUE;
 266     fromHighest = 0;
 267     for (int[] range : fromRange)
 268     {
 269       fromLowest = Math.min(fromLowest, range[0]);
 270       fromHighest = Math.max(fromHighest, range[1]);
 271     }
 272
 273     toLowest = Integer.MAX_VALUE;
 274     toHighest = 0;
 275     for (int[] range : toRange)
 276     {
 277       toLowest = Math.min(toLowest, range[0]);
 278       toHighest = Math.max(toHighest, range[1]);
 279     }
 280   }
 281
 282   /**
 283    * get all mapped positions from 'from' to 'to'
 284    *
 285    * @return int[][] { int[] { fromStart, fromFinish, toStart, toFinish }, int
 286    *         [fromFinish-fromStart+2] { toStart..toFinish mappings}}
 287    */
 288   protected int[][] makeFromMap()
 289   {
 290     // TODO not used - remove??
 291     return posMap(fromShifts, fromRatio, toShifts, toRatio);
 292   }
 293
 294   /**
 295    * get all mapped positions from 'to' to 'from'
 296    *
 297    * @return int[to position]=position mapped in from
 298    */
 299   protected int[][] makeToMap()
 300   {
 301     // TODO not used - remove??
 302     return posMap(toShifts, toRatio, fromShifts, fromRatio);
 303   }
 304
 305   /**
 306    * construct an int map for intervals in intVals
 307    *
 308    * @param shiftTo
 309    * @return int[] { from, to pos in range }, int[range.to-range.from+1]
 310    *         returning mapped position
 311    */
 312   private int[][] posMap(List<int[]> shiftTo, int ratio,
 313           List<int[]> shiftFrom, int toRatio)
 314   {
 315     // TODO not used - remove??
 316     int iv = 0, ivSize = shiftTo.size();
 317     if (iv >= ivSize)
 318     {
 319       return null;
 320     }
 321     int[] intv = shiftTo.get(iv++);
 322     int from = intv[0], to = intv[1];
 323     if (from > to)
 324     {
 325       from = intv[1];
 326       to = intv[0];
 327     }
 328     while (iv < ivSize)
 329     {
 330       intv = shiftTo.get(iv++);
 331       if (intv[0] < from)
 332       {
 333         from = intv[0];
 334       }
 335       if (intv[1] < from)
 336       {
 337         from = intv[1];
 338       }
 339       if (intv[0] > to)
 340       {
 341         to = intv[0];
 342       }
 343       if (intv[1] > to)
 344       {
 345         to = intv[1];
 346       }
 347     }
 348     int tF = 0, tT = 0;
 349     int mp[][] = new int[to - from + 2][];
 350     for (int i = 0; i < mp.length; i++)
 351     {
 352       int[] m = shift(i + from, shiftTo, ratio, shiftFrom, toRatio);
 353       if (m != null)
 354       {
 355         if (i == 0)
 356         {
 357           tF = tT = m[0];
 358         }
 359         else
 360         {
 361           if (m[0] < tF)
 362           {
 363             tF = m[0];
 364           }
 365           if (m[0] > tT)
 366           {
 367             tT = m[0];
 368           }
 369         }
 370       }
 371       mp[i] = m;
 372     }
 373     int[][] map = new int[][] { new int[] { from, to, tF, tT },
 374         new int[to - from + 2] };
 375
 376     map[0][2] = tF;
 377     map[0][3] = tT;
 378
 379     for (int i = 0; i < mp.length; i++)
 380     {
 381       if (mp[i] != null)
 382       {
 383         map[1][i] = mp[i][0] - tF;
 384       }
 385       else
 386       {
 387         map[1][i] = -1; // indicates an out of range mapping
 388       }
 389     }
 390     return map;
 391   }
 392
 393   /**
 394    * addShift
 395    *
 396    * @param pos
 397    *          start position for shift (in original reference frame)
 398    * @param shift
 399    *          length of shift
 400    *
 401    *          public void addShift(int pos, int shift) { int sidx = 0; int[]
 402    *          rshift=null; while (sidx<shifts.size() && (rshift=(int[])
 403    *          shifts.elementAt(sidx))[0]<pos) sidx++; if (sidx==shifts.size())
 404    *          shifts.insertElementAt(new int[] { pos, shift}, sidx); else
 405    *          rshift[1]+=shift; }
 406    */
 407
 408   /**
 409    * shift from pos to To(pos)
 410    *
 411    * @param pos
 412    *          int
 413    * @return int shifted position in To, frameshift in From, direction of mapped
 414    *         symbol in To
 415    */
 416   public int[] shiftFrom(int pos)
 417   {
 418     return shift(pos, fromShifts, fromRatio, toShifts, toRatio);
 419   }
 420
 421   /**
 422    * inverse of shiftFrom - maps pos in To to a position in From
 423    *
 424    * @param pos
 425    *          (in To)
 426    * @return shifted position in From, frameshift in To, direction of mapped
 427    *         symbol in From
 428    */
 429   public int[] shiftTo(int pos)
 430   {
 431     return shift(pos, toShifts, toRatio, fromShifts, fromRatio);
 432   }
 433
 434   /**
 435    *
 436    * @param shiftTo
 437    * @param fromRatio
 438    * @param shiftFrom
 439    * @param toRatio
 440    * @return
 441    */
 442   protected static int[] shift(int pos, List<int[]> shiftTo, int fromRatio,
 443           List<int[]> shiftFrom, int toRatio)
 444   {
 445     // TODO: javadoc; tests
 446     int[] fromCount = countPos(shiftTo, pos);
 447     if (fromCount == null)
 448     {
 449       return null;
 450     }
 451     int fromRemainder = (fromCount[0] - 1) % fromRatio;
 452     int toCount = 1 + (((fromCount[0] - 1) / fromRatio) * toRatio);
 453     int[] toPos = countToPos(shiftFrom, toCount);
 454     if (toPos == null)
 455     {
 456       return null; // throw new Error("Bad Mapping!");
 457     }
 458     // System.out.println(fromCount[0]+" "+fromCount[1]+" "+toCount);
 459     return new int[] { toPos[0], fromRemainder, toPos[1] };
 460   }
 461
 462   /**
 463    * count how many positions pos is along the series of intervals.
 464    *
 465    * @param shiftTo
 466    * @param pos
 467    * @return number of positions or null if pos is not within intervals
 468    */
 469   protected static int[] countPos(List<int[]> shiftTo, int pos)
 470   {
 471     int count = 0, intv[], iv = 0, ivSize = shiftTo.size();
 472     while (iv < ivSize)
 473     {
 474       intv = shiftTo.get(iv++);
 475       if (intv[0] <= intv[1])
 476       {
 477         if (pos >= intv[0] && pos <= intv[1])
 478         {
 479           return new int[] { count + pos - intv[0] + 1, +1 };
 480         }
 481         else
 482         {
 483           count += intv[1] - intv[0] + 1;
 484         }
 485       }
 486       else
 487       {
 488         if (pos >= intv[1] && pos <= intv[0])
 489         {
 490           return new int[] { count + intv[0] - pos + 1, -1 };
 491         }
 492         else
 493         {
 494           count += intv[0] - intv[1] + 1;
 495         }
 496       }
 497     }
 498     return null;
 499   }
 500
 501   /**
 502    * count out pos positions into a series of intervals and return the position
 503    *
 504    * @param shiftFrom
 505    * @param pos
 506    * @return position pos in interval set
 507    */
 508   protected static int[] countToPos(List<int[]> shiftFrom, int pos)
 509   {
 510     int count = 0, diff = 0, iv = 0, ivSize = shiftFrom.size();
 511     int[] intv = { 0, 0 };
 512     while (iv < ivSize)
 513     {
 514       intv = shiftFrom.get(iv++);
 515       diff = intv[1] - intv[0];
 516       if (diff >= 0)
 517       {
 518         if (pos <= count + 1 + diff)
 519         {
 520           return new int[] { pos - count - 1 + intv[0], +1 };
 521         }
 522         else
 523         {
 524           count += 1 + diff;
 525         }
 526       }
 527       else
 528       {
 529         if (pos <= count + 1 - diff)
 530         {
 531           return new int[] { intv[0] - (pos - count - 1), -1 };
 532         }
 533         else
 534         {
 535           count += 1 - diff;
 536         }
 537       }
 538     }
 539     return null;// (diff<0) ? (intv[1]-1) : (intv[0]+1);
 540   }
 541
 542   /**
 543    * find series of intervals mapping from start-end in the From map.
 544    *
 545    * @param start
 546    *          position mapped 'to'
 547    * @param end
 548    *          position mapped 'to'
 549    * @return series of [start, end] ranges in sequence mapped 'from'
 550    */
 551   public int[] locateInFrom(int start, int end)
 552   {
 553     // inefficient implementation
 554     int fromStart[] = shiftTo(start);
 555     // needs to be inclusive of end of symbol position
 556     int fromEnd[] = shiftTo(end);
 557
 558     return getIntervals(fromShifts, fromStart, fromEnd, fromRatio);
 559   }
 560
 561   /**
 562    * find series of intervals mapping from start-end in the to map.
 563    *
 564    * @param start
 565    *          position mapped 'from'
 566    * @param end
 567    *          position mapped 'from'
 568    * @return series of [start, end] ranges in sequence mapped 'to'
 569    */
 570   public int[] locateInTo(int start, int end)
 571   {
 572     int toStart[] = shiftFrom(start);
 573     int toEnd[] = shiftFrom(end);
 574     return getIntervals(toShifts, toStart, toEnd, toRatio);
 575   }
 576
 577   /**
 578    * like shift - except returns the intervals in the given vector of shifts
 579    * which were spanned in traversing fromStart to fromEnd
 580    *
 581    * @param shiftFrom
 582    * @param fromStart
 583    * @param fromEnd
 584    * @param fromRatio2
 585    * @return series of from,to intervals from from first position of starting
 586    *         region to final position of ending region inclusive
 587    */
 588   protected static int[] getIntervals(List<int[]> shiftFrom,
 589           int[] fromStart, int[] fromEnd, int fromRatio2)
 590   {
 591     if (fromStart == null || fromEnd == null)
 592     {
 593       return null;
 594     }
 595     int startpos, endpos;
 596     startpos = fromStart[0]; // first position in fromStart
 597     endpos = fromEnd[0]; // last position in fromEnd
 598     int endindx = (fromRatio2 - 1); // additional positions to get to last
 599     // position from endpos
 600     int intv = 0, intvSize = shiftFrom.size();
 601     int iv[], i = 0, fs = -1, fe_s = -1, fe = -1; // containing intervals
 602     // search intervals to locate ones containing startpos and count endindx
 603     // positions on from endpos
 604     while (intv < intvSize && (fs == -1 || fe == -1))
 605     {
 606       iv = shiftFrom.get(intv++);
 607       if (fe_s > -1)
 608       {
 609         endpos = iv[0]; // start counting from beginning of interval
 610         endindx--; // inclusive of endpos
 611       }
 612       if (iv[0] <= iv[1])
 613       {
 614         if (fs == -1 && startpos >= iv[0] && startpos <= iv[1])
 615         {
 616           fs = i;
 617         }
 618         if (endpos >= iv[0] && endpos <= iv[1])
 619         {
 620           if (fe_s == -1)
 621           {
 622             fe_s = i;
 623           }
 624           if (fe_s != -1)
 625           {
 626             if (endpos + endindx <= iv[1])
 627             {
 628               fe = i;
 629               endpos = endpos + endindx; // end of end token is within this
 630               // interval
 631             }
 632             else
 633             {
 634               endindx -= iv[1] - endpos; // skip all this interval too
 635             }
 636           }
 637         }
 638       }
 639       else
 640       {
 641         if (fs == -1 && startpos <= iv[0] && startpos >= iv[1])
 642         {
 643           fs = i;
 644         }
 645         if (endpos <= iv[0] && endpos >= iv[1])
 646         {
 647           if (fe_s == -1)
 648           {
 649             fe_s = i;
 650           }
 651           if (fe_s != -1)
 652           {
 653             if (endpos - endindx >= iv[1])
 654             {
 655               fe = i;
 656               endpos = endpos - endindx; // end of end token is within this
 657               // interval
 658             }
 659             else
 660             {
 661               endindx -= endpos - iv[1]; // skip all this interval too
 662             }
 663           }
 664         }
 665       }
 666       i++;
 667     }
 668     if (fs == fe && fe == -1)
 669     {
 670       return null;
 671     }
 672     List<int[]> ranges = new ArrayList<int[]>();
 673     if (fs <= fe)
 674     {
 675       intv = fs;
 676       i = fs;
 677       // truncate initial interval
 678       iv = shiftFrom.get(intv++);
 679       iv = new int[] { iv[0], iv[1] };// clone
 680       if (i == fs)
 681       {
 682         iv[0] = startpos;
 683       }
 684       while (i != fe)
 685       {
 686         ranges.add(iv); // add initial range
 687         iv = shiftFrom.get(intv++); // get next interval
 688         iv = new int[] { iv[0], iv[1] };// clone
 689         i++;
 690       }
 691       if (i == fe)
 692       {
 693         iv[1] = endpos;
 694       }
 695       ranges.add(iv); // add only - or final range
 696     }
 697     else
 698     {
 699       // walk from end of interval.
 700       i = shiftFrom.size() - 1;
 701       while (i > fs)
 702       {
 703         i--;
 704       }
 705       iv = shiftFrom.get(i);
 706       iv = new int[] { iv[1], iv[0] };// reverse and clone
 707       // truncate initial interval
 708       if (i == fs)
 709       {
 710         iv[0] = startpos;
 711       }
 712       while (--i != fe)
 713       { // fix apparent logic bug when fe==-1
 714         ranges.add(iv); // add (truncated) reversed interval
 715         iv = shiftFrom.get(i);
 716         iv = new int[] { iv[1], iv[0] }; // reverse and clone
 717       }
 718       if (i == fe)
 719       {
 720         // interval is already reversed
 721         iv[1] = endpos;
 722       }
 723       ranges.add(iv); // add only - or final range
 724     }
 725     // create array of start end intervals.
 726     int[] range = null;
 727     if (ranges != null && ranges.size() > 0)
 728     {
 729       range = new int[ranges.size() * 2];
 730       intv = 0;
 731       intvSize = ranges.size();
 732       i = 0;
 733       while (intv < intvSize)
 734       {
 735         iv = ranges.get(intv);
 736         range[i++] = iv[0];
 737         range[i++] = iv[1];
 738         ranges.set(intv++, null); // remove
 739       }
 740     }
 741     return range;
 742   }
 743
 744   /**
 745    * get the 'initial' position of mpos in To
 746    *
 747    * @param mpos
 748    *          position in from
 749    * @return position of first word in to reference frame
 750    */
 751   public int getToPosition(int mpos)
 752   {
 753     // TODO not used - remove??
 754     int[] mp = shiftTo(mpos);
 755     if (mp != null)
 756     {
 757       return mp[0];
 758     }
 759     return mpos;
 760   }
 761
 762   /**
 763    * get range of positions in To frame for the mpos word in From
 764    *
 765    * @param mpos
 766    *          position in From
 767    * @return null or int[] first position in To for mpos, last position in to
 768    *         for Mpos
 769    */
 770   public int[] getToWord(int mpos)
 771   {
 772     int[] mp = shiftTo(mpos);
 773     if (mp != null)
 774     {
 775       return new int[] { mp[0], mp[0] + mp[2] * (getFromRatio() - 1) };
 776     }
 777     return null;
 778   }
 779
 780   /**
 781    * get From position in the associated reference frame for position pos in the
 782    * associated sequence.
 783    *
 784    * @param pos
 785    * @return
 786    */
 787   public int getMappedPosition(int pos)
 788   {
 789     // TODO not used - remove??
 790     int[] mp = shiftFrom(pos);
 791     if (mp != null)
 792     {
 793       return mp[0];
 794     }
 795     return pos;
 796   }
 797
 798   public int[] getMappedWord(int pos)
 799   {
 800     // TODO not used - remove??
 801     int[] mp = shiftFrom(pos);
 802     if (mp != null)
 803     {
 804       return new int[] { mp[0], mp[0] + mp[2] * (getToRatio() - 1) };
 805     }
 806     return null;
 807   }
 808
 809   /**
 810    *
 811    * @return a MapList whose From range is this maplist's To Range, and vice
 812    *         versa
 813    */
 814   public MapList getInverse()
 815   {
 816     return new MapList(getToRanges(), getFromRanges(), getToRatio(),
 817             getFromRatio());
 818   }
 819
 820   /**
 821    * test for containment rather than equivalence to another mapping
 822    *
 823    * @param map
 824    *          to be tested for containment
 825    * @return true if local or mapped range map contains or is contained by this
 826    *         mapping
 827    */
 828   public boolean containsEither(boolean local, MapList map)
 829   {
 830     // TODO not used - remove?
 831     if (local)
 832     {
 833       return ((getFromLowest() >= map.getFromLowest() && getFromHighest() <= map
 834               .getFromHighest()) || (getFromLowest() <= map.getFromLowest() && getFromHighest() >= map
 835               .getFromHighest()));
 836     }
 837     else
 838     {
 839       return ((getToLowest() >= map.getToLowest() && getToHighest() <= map
 840               .getToHighest()) || (getToLowest() <= map.getToLowest() && getToHighest() >= map
 841               .getToHighest()));
 842     }
 843   }
 844
 845   /**
 846    * String representation - for debugging, not guaranteed not to change
 847    */
 848   @Override
 849   public String toString()
 850   {
 851     StringBuilder sb = new StringBuilder(64);
 852     sb.append("From (").append(fromRatio).append(":").append(toRatio)
 853             .append(") [");
 854     for (int[] shift : fromShifts)
 855     {
 856       sb.append(" ").append(Arrays.toString(shift));
 857     }
 858     sb.append(" ] To [");
 859     for (int[] shift : toShifts)
 860     {
 861       sb.append(" ").append(Arrays.toString(shift));
 862     }
 863     sb.append(" ]");
 864     return sb.toString();
 865   }
 866 }