src/jalview/util/MapList.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer
   3  * Copyright (C) 2007 AM Waterhouse, J Procter, G Barton, M Clamp, S Searle
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License
   7  * as published by the Free Software Foundation; either version 2
   8  * of the License, or (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
  18  */
  19 package jalview.util;
  20
  21 import java.util.*;
  22
  23 /**
  24  * MapList Simple way of bijectively mapping a non-contiguous linear range to
  25  * another non-contiguous linear range Use at your own risk! TODO: efficient
  26  * implementation of private posMap method TODO: test/ensure that sense of from
  27  * and to ratio start position is conserved (codon start position recovery)
  28  * TODO: optimize to use int[][] arrays rather than vectors.
  29  */
  30 public class MapList
  31 {
  32   /*
  33    * (non-Javadoc)
  34    *
  35    * @see java.lang.Object#equals(java.lang.Object)
  36    */
  37   public boolean equals(MapList obj)
  38   {
  39     if (obj == this)
  40       return true;
  41     if (obj != null && obj.fromRatio == fromRatio && obj.toRatio == toRatio
  42             && obj.fromShifts != null && obj.toShifts != null)
  43     {
  44       int i, iSize = fromShifts.size(), j, jSize = obj.fromShifts.size();
  45       if (iSize != jSize)
  46         return false;
  47       for (i = 0, iSize = fromShifts.size(), j = 0, jSize = obj.fromShifts
  48               .size(); i < iSize;)
  49       {
  50         int[] mi = (int[]) fromShifts.elementAt(i++);
  51         int[] mj = (int[]) obj.fromShifts.elementAt(j++);
  52         if (mi[0] != mj[0] || mi[1] != mj[1])
  53           return false;
  54       }
  55       iSize = toShifts.size();
  56       jSize = obj.toShifts.size();
  57       if (iSize != jSize)
  58         return false;
  59       for (i = 0, j = 0; i < iSize;)
  60       {
  61         int[] mi = (int[]) toShifts.elementAt(i++);
  62         int[] mj = (int[]) obj.toShifts.elementAt(j++);
  63         if (mi[0] != mj[0] || mi[1] != mj[1])
  64           return false;
  65       }
  66       return true;
  67     }
  68     return false;
  69   }
  70
  71   public Vector fromShifts;
  72
  73   public Vector toShifts;
  74
  75   int fromRatio; // number of steps in fromShifts to one toRatio unit
  76
  77   int toRatio; // number of steps in toShifts to one fromRatio
  78
  79   /**
  80    *
  81    * @return series of intervals mapped in from
  82    */
  83   public int[] getFromRanges()
  84   {
  85     return getRanges(fromShifts);
  86   }
  87
  88   public int[] getToRanges()
  89   {
  90     return getRanges(toShifts);
  91   }
  92
  93   private int[] getRanges(Vector shifts)
  94   {
  95     int[] rnges = new int[2 * shifts.size()];
  96     Enumeration e = shifts.elements();
  97     int i = 0;
  98     while (e.hasMoreElements())
  99     {
 100       int r[] = (int[]) e.nextElement();
 101       rnges[i++] = r[0];
 102       rnges[i++] = r[1];
 103     }
 104     return rnges;
 105   }
 106
 107   /**
 108    * lowest and highest value in the from Map
 109    */
 110   int[] fromRange = null;
 111
 112   /**
 113    * lowest and highest value in the to Map
 114    */
 115   int[] toRange = null;
 116
 117   /**
 118    *
 119    * @return length of mapped phrase in from
 120    */
 121   public int getFromRatio()
 122   {
 123     return fromRatio;
 124   }
 125
 126   /**
 127    *
 128    * @return length of mapped phrase in to
 129    */
 130   public int getToRatio()
 131   {
 132     return toRatio;
 133   }
 134
 135   public int getFromLowest()
 136   {
 137     return fromRange[0];
 138   }
 139
 140   public int getFromHighest()
 141   {
 142     return fromRange[1];
 143   }
 144
 145   public int getToLowest()
 146   {
 147     return toRange[0];
 148   }
 149
 150   public int getToHighest()
 151   {
 152     return toRange[1];
 153   }
 154
 155   private void ensureRange(int[] limits, int pos)
 156   {
 157     if (limits[0] > pos)
 158       limits[0] = pos;
 159     if (limits[1] < pos)
 160       limits[1] = pos;
 161   }
 162
 163   public MapList(int from[], int to[], int fromRatio, int toRatio)
 164   {
 165     fromRange = new int[]
 166     { from[0], from[1] };
 167     toRange = new int[]
 168     { to[0], to[1] };
 169
 170     fromShifts = new Vector();
 171     for (int i = 0; i < from.length; i += 2)
 172     {
 173       ensureRange(fromRange, from[i]);
 174       ensureRange(fromRange, from[i + 1]);
 175
 176       fromShifts.addElement(new int[]
 177       { from[i], from[i + 1] });
 178     }
 179     toShifts = new Vector();
 180     for (int i = 0; i < to.length; i += 2)
 181     {
 182       ensureRange(toRange, to[i]);
 183       ensureRange(toRange, to[i + 1]);
 184       toShifts.addElement(new int[]
 185       { to[i], to[i + 1] });
 186     }
 187     this.fromRatio = fromRatio;
 188     this.toRatio = toRatio;
 189   }
 190
 191   public MapList(MapList map)
 192   {
 193     this.fromRange = new int[]
 194     { map.fromRange[0], map.fromRange[1] };
 195     this.toRange = new int[]
 196     { map.toRange[0], map.toRange[1] };
 197     this.fromRatio = map.fromRatio;
 198     this.toRatio = map.toRatio;
 199     if (map.fromShifts != null)
 200     {
 201       this.fromShifts = new Vector();
 202       Enumeration e = map.fromShifts.elements();
 203       while (e.hasMoreElements())
 204       {
 205         int[] el = (int[]) e.nextElement();
 206         fromShifts.addElement(new int[]
 207         { el[0], el[1] });
 208       }
 209     }
 210     if (map.toShifts != null)
 211     {
 212       this.toShifts = new Vector();
 213       Enumeration e = map.toShifts.elements();
 214       while (e.hasMoreElements())
 215       {
 216         int[] el = (int[]) e.nextElement();
 217         toShifts.addElement(new int[]
 218         { el[0], el[1] });
 219       }
 220     }
 221   }
 222
 223   /**
 224    * get all mapped positions from 'from' to 'to'
 225    *
 226    * @return int[][] { int[] { fromStart, fromFinish, toStart, toFinish }, int
 227    *         [fromFinish-fromStart+2] { toStart..toFinish mappings}}
 228    */
 229   public int[][] makeFromMap()
 230   {
 231     return posMap(fromShifts, fromRatio, toShifts, toRatio);
 232   }
 233
 234   /**
 235    * get all mapped positions from 'to' to 'from'
 236    *
 237    * @return int[to position]=position mapped in from
 238    */
 239   public int[][] makeToMap()
 240   {
 241     return posMap(toShifts, toRatio, fromShifts, fromRatio);
 242   }
 243
 244   /**
 245    * construct an int map for intervals in intVals
 246    *
 247    * @param intVals
 248    * @return int[] { from, to pos in range }, int[range.to-range.from+1]
 249    *         returning mapped position
 250    */
 251   private int[][] posMap(Vector intVals, int ratio, Vector toIntVals,
 252           int toRatio)
 253   {
 254     int iv = 0, ivSize = intVals.size();
 255     if (iv >= ivSize)
 256     {
 257       return null;
 258     }
 259     int[] intv = (int[]) intVals.elementAt(iv++);
 260     int from = intv[0], to = intv[1];
 261     if (from > to)
 262     {
 263       from = intv[1];
 264       to = intv[0];
 265     }
 266     while (iv < ivSize)
 267     {
 268       intv = (int[]) intVals.elementAt(iv++);
 269       if (intv[0] < from)
 270       {
 271         from = intv[0];
 272       }
 273       if (intv[1] < from)
 274       {
 275         from = intv[1];
 276       }
 277       if (intv[0] > to)
 278       {
 279         to = intv[0];
 280       }
 281       if (intv[1] > to)
 282       {
 283         to = intv[1];
 284       }
 285     }
 286     int tF = 0, tT = 0;
 287     int mp[][] = new int[to - from + 2][];
 288     for (int i = 0; i < mp.length; i++)
 289     {
 290       int[] m = shift(i + from, intVals, ratio, toIntVals, toRatio);
 291       if (m != null)
 292       {
 293         if (i == 0)
 294         {
 295           tF = tT = m[0];
 296         }
 297         else
 298         {
 299           if (m[0] < tF)
 300           {
 301             tF = m[0];
 302           }
 303           if (m[0] > tT)
 304           {
 305             tT = m[0];
 306           }
 307         }
 308       }
 309       mp[i] = m;
 310     }
 311     int[][] map = new int[][]
 312     { new int[]
 313     { from, to, tF, tT }, new int[to - from + 2] };
 314
 315     map[0][2] = tF;
 316     map[0][3] = tT;
 317
 318     for (int i = 0; i < mp.length; i++)
 319     {
 320       if (mp[i] != null)
 321       {
 322         map[1][i] = mp[i][0] - tF;
 323       }
 324       else
 325       {
 326         map[1][i] = -1; // indicates an out of range mapping
 327       }
 328     }
 329     return map;
 330   }
 331
 332   /**
 333    * addShift
 334    *
 335    * @param pos
 336    *                start position for shift (in original reference frame)
 337    * @param shift
 338    *                length of shift
 339    *
 340    * public void addShift(int pos, int shift) { int sidx = 0; int[] rshift=null;
 341    * while (sidx<shifts.size() && (rshift=(int[]) shifts.elementAt(sidx))[0]<pos)
 342    * sidx++; if (sidx==shifts.size()) shifts.insertElementAt(new int[] { pos,
 343    * shift}, sidx); else rshift[1]+=shift; }
 344    */
 345   /**
 346    * shift from pos to To(pos)
 347    *
 348    * @param pos
 349    *                int
 350    * @return int shifted position in To, frameshift in From, direction of mapped
 351    *         symbol in To
 352    */
 353   public int[] shiftFrom(int pos)
 354   {
 355     return shift(pos, fromShifts, fromRatio, toShifts, toRatio);
 356   }
 357
 358   /**
 359    * inverse of shiftFrom - maps pos in To to a position in From
 360    *
 361    * @param pos
 362    *                (in To)
 363    * @return shifted position in From, frameshift in To, direction of mapped
 364    *         symbol in From
 365    */
 366   public int[] shiftTo(int pos)
 367   {
 368     return shift(pos, toShifts, toRatio, fromShifts, fromRatio);
 369   }
 370
 371   /**
 372    *
 373    * @param fromShifts
 374    * @param fromRatio
 375    * @param toShifts
 376    * @param toRatio
 377    * @return
 378    */
 379   private int[] shift(int pos, Vector fromShifts, int fromRatio,
 380           Vector toShifts, int toRatio)
 381   {
 382     int[] fromCount = countPos(fromShifts, pos);
 383     if (fromCount == null)
 384     {
 385       return null;
 386     }
 387     int fromRemainder = (fromCount[0] - 1) % fromRatio;
 388     int toCount = 1 + (((fromCount[0] - 1) / fromRatio) * toRatio);
 389     int[] toPos = countToPos(toShifts, toCount);
 390     if (toPos == null)
 391     {
 392       return null; // throw new Error("Bad Mapping!");
 393     }
 394     // System.out.println(fromCount[0]+" "+fromCount[1]+" "+toCount);
 395     return new int[]
 396     { toPos[0], fromRemainder, toPos[1] };
 397   }
 398
 399   /**
 400    * count how many positions pos is along the series of intervals.
 401    *
 402    * @param intVals
 403    * @param pos
 404    * @return number of positions or null if pos is not within intervals
 405    */
 406   private int[] countPos(Vector intVals, int pos)
 407   {
 408     int count = 0, intv[], iv = 0, ivSize = intVals.size();
 409     while (iv < ivSize)
 410     {
 411       intv = (int[]) intVals.elementAt(iv++);
 412       if (intv[0] <= intv[1])
 413       {
 414         if (pos >= intv[0] && pos <= intv[1])
 415         {
 416           return new int[]
 417           { count + pos - intv[0] + 1, +1 };
 418         }
 419         else
 420         {
 421           count += intv[1] - intv[0] + 1;
 422         }
 423       }
 424       else
 425       {
 426         if (pos >= intv[1] && pos <= intv[0])
 427         {
 428           return new int[]
 429           { count + intv[0] - pos + 1, -1 };
 430         }
 431         else
 432         {
 433           count += intv[0] - intv[1] + 1;
 434         }
 435       }
 436     }
 437     return null;
 438   }
 439
 440   /**
 441    * count out pos positions into a series of intervals and return the position
 442    *
 443    * @param intVals
 444    * @param pos
 445    * @return position pos in interval set
 446    */
 447   private int[] countToPos(Vector intVals, int pos)
 448   {
 449     int count = 0, diff = 0, iv = 0, ivSize = intVals.size(), intv[] =
 450     { 0, 0 };
 451     while (iv < ivSize)
 452     {
 453       intv = (int[]) intVals.elementAt(iv++);
 454       diff = intv[1] - intv[0];
 455       if (diff >= 0)
 456       {
 457         if (pos <= count + 1 + diff)
 458         {
 459           return new int[]
 460           { pos - count - 1 + intv[0], +1 };
 461         }
 462         else
 463         {
 464           count += 1 + diff;
 465         }
 466       }
 467       else
 468       {
 469         if (pos <= count + 1 - diff)
 470         {
 471           return new int[]
 472           { intv[0] - (pos - count - 1), -1 };
 473         }
 474         else
 475         {
 476           count += 1 - diff;
 477         }
 478       }
 479     }
 480     return null;// (diff<0) ? (intv[1]-1) : (intv[0]+1);
 481   }
 482
 483   /**
 484    * find series of intervals mapping from start-end in the From map.
 485    *
 486    * @param start
 487    *                position in to map
 488    * @param end
 489    *                position in to map
 490    * @return series of ranges in from map
 491    */
 492   public int[] locateInFrom(int start, int end)
 493   {
 494     // inefficient implementation
 495     int fromStart[] = shiftTo(start);
 496     int fromEnd[] = shiftTo(end); // needs to be inclusive of end of symbol
 497                                   // position
 498     if (fromStart == null || fromEnd == null)
 499       return null;
 500     int iv[] = getIntervals(fromShifts, fromStart, fromEnd, fromRatio);
 501     return iv;
 502   }
 503
 504   /**
 505    * find series of intervals mapping from start-end in the to map.
 506    *
 507    * @param start
 508    *                position in from map
 509    * @param end
 510    *                position in from map
 511    * @return series of ranges in to map
 512    */
 513   public int[] locateInTo(int start, int end)
 514   {
 515     // inefficient implementation
 516     int toStart[] = shiftFrom(start);
 517     int toEnd[] = shiftFrom(end);
 518     if (toStart == null || toEnd == null)
 519       return null;
 520     int iv[] = getIntervals(toShifts, toStart, toEnd, toRatio);
 521     return iv;
 522   }
 523
 524   /**
 525    * like shift - except returns the intervals in the given vector of shifts
 526    * which were spanned in traversing fromStart to fromEnd
 527    *
 528    * @param fromShifts2
 529    * @param fromStart
 530    * @param fromEnd
 531    * @param fromRatio2
 532    * @return series of from,to intervals from from first position of starting
 533    *         region to final position of ending region inclusive
 534    */
 535   private int[] getIntervals(Vector fromShifts2, int[] fromStart,
 536           int[] fromEnd, int fromRatio2)
 537   {
 538     int startpos, endpos;
 539     startpos = fromStart[0]; // first position in fromStart
 540     endpos = fromEnd[0]; // last position in fromEnd
 541     int endindx = (fromRatio2 - 1); // additional positions to get to last
 542                                     // position from endpos
 543     int intv = 0, intvSize = fromShifts2.size();
 544     int iv[], i = 0, fs = -1, fe_s = -1, fe = -1; // containing intervals
 545     // search intervals to locate ones containing startpos and count endindx
 546     // positions on from endpos
 547     while (intv < intvSize && ( fs == -1 || fe == -1))
 548     {
 549       iv = (int[]) fromShifts2.elementAt(intv++);
 550       if (fe_s>-1)
 551       {
 552         endpos = iv[0]; // start counting from beginning of interval
 553         endindx--; // inclusive of endpos
 554       }
 555       if (iv[0] <= iv[1])
 556       {
 557         if (fs == -1 && startpos >= iv[0] && startpos <= iv[1])
 558         {
 559           fs = i;
 560         }
 561         if (endpos >= iv[0] && endpos <= iv[1])
 562         {
 563           if (fe_s == -1)
 564           {
 565             fe_s = i;
 566           }
 567           if (fe_s != -1)
 568           {
 569             if (endpos + endindx <= iv[1])
 570             {
 571               fe = i;
 572               endpos = endpos + endindx; // end of end token is within this interval
 573             }
 574             else
 575             {
 576               endindx -= iv[1] - endpos;  // skip all this interval too
 577             }
 578           }
 579         }
 580       }
 581       else
 582       {
 583         if (fs == -1 && startpos <= iv[0] && startpos >= iv[1])
 584         {
 585           fs = i;
 586         }
 587         if (endpos <= iv[0] && endpos >= iv[1])
 588         {
 589           if (fe_s == -1)
 590           {
 591             fe_s = i;
 592           }
 593           if (fe_s != -1)
 594           {
 595             if (endpos - endindx >= iv[1])
 596             {
 597               fe = i;
 598               endpos = endpos - endindx; // end of end token is within this interval
 599             }
 600             else
 601             {
 602               endindx -= endpos-iv[1]; // skip all this interval too
 603             }
 604           }
 605         }
 606       }
 607       i++;
 608     }
 609     if (fs == fe && fe == -1)
 610       return null;
 611     Vector ranges = new Vector();
 612     if (fs <= fe)
 613     {
 614       intv = fs;
 615       i = fs;
 616       // truncate initial interval
 617       iv = (int[]) fromShifts2.elementAt(intv++);
 618       iv = new int[]
 619       { iv[0], iv[1] };// clone
 620       if (i == fs)
 621         iv[0] = startpos;
 622       while (i != fe)
 623       {
 624         ranges.addElement(iv); // add initial range
 625         iv = (int[]) fromShifts2.elementAt(intv++); // get next interval
 626         iv = new int[]
 627         { iv[0], iv[1] };// clone
 628         i++;
 629       }
 630       if (i == fe)
 631         iv[1] = endpos;
 632       ranges.addElement(iv); // add only - or final range
 633     }
 634     else
 635     {
 636       // walk from end of interval.
 637       i = fromShifts2.size() - 1;
 638       while (i > fs)
 639       {
 640         i--;
 641       }
 642       iv = (int[]) fromShifts2.elementAt(i);
 643       iv = new int[]
 644       { iv[1], iv[0] };// reverse and clone
 645       // truncate initial interval
 646       if (i == fs)
 647       {
 648         iv[0] = startpos;
 649       }
 650       while (--i != fe)
 651       { // fix apparent logic bug when fe==-1
 652         ranges.addElement(iv); // add (truncated) reversed interval
 653         iv = (int[]) fromShifts2.elementAt(i);
 654         iv = new int[]
 655         { iv[1], iv[0] }; // reverse and clone
 656       }
 657       if (i == fe)
 658       {
 659         // interval is already reversed
 660         iv[1] = endpos;
 661       }
 662       ranges.addElement(iv); // add only - or final range
 663     }
 664     // create array of start end intervals.
 665     int[] range = null;
 666     if (ranges != null && ranges.size() > 0)
 667     {
 668       range = new int[ranges.size() * 2];
 669       intv = 0;
 670       intvSize = ranges.size();
 671       i = 0;
 672       while (intv < intvSize)
 673       {
 674         iv = (int[]) ranges.elementAt(intv);
 675         range[i++] = iv[0];
 676         range[i++] = iv[1];
 677         ranges.setElementAt(null, intv++); // remove
 678       }
 679     }
 680     return range;
 681   }
 682
 683   /**
 684    * get the 'initial' position of mpos in To
 685    *
 686    * @param mpos
 687    *                position in from
 688    * @return position of first word in to reference frame
 689    */
 690   public int getToPosition(int mpos)
 691   {
 692     int[] mp = shiftTo(mpos);
 693     if (mp != null)
 694     {
 695       return mp[0];
 696     }
 697     return mpos;
 698   }
 699
 700   /**
 701    * get range of positions in To frame for the mpos word in From
 702    *
 703    * @param mpos
 704    *                position in From
 705    * @return null or int[] first position in To for mpos, last position in to
 706    *         for Mpos
 707    */
 708   public int[] getToWord(int mpos)
 709   {
 710     int[] mp = shiftTo(mpos);
 711     if (mp != null)
 712     {
 713       return new int[]
 714       { mp[0], mp[0] + mp[2] * (getFromRatio() - 1) };
 715     }
 716     return null;
 717   }
 718
 719   /**
 720    * get From position in the associated reference frame for position pos in the
 721    * associated sequence.
 722    *
 723    * @param pos
 724    * @return
 725    */
 726   public int getMappedPosition(int pos)
 727   {
 728     int[] mp = shiftFrom(pos);
 729     if (mp != null)
 730     {
 731       return mp[0];
 732     }
 733     return pos;
 734   }
 735
 736   public int[] getMappedWord(int pos)
 737   {
 738     int[] mp = shiftFrom(pos);
 739     if (mp != null)
 740     {
 741       return new int[]
 742       { mp[0], mp[0] + mp[2] * (getToRatio() - 1) };
 743     }
 744     return null;
 745   }
 746
 747   /**
 748    * test routine. not incremental.
 749    *
 750    * @param ml
 751    * @param fromS
 752    * @param fromE
 753    */
 754   public static void testMap(MapList ml, int fromS, int fromE)
 755   {
 756     for (int from = 1; from <= 25; from++)
 757     {
 758       int[] too = ml.shiftFrom(from);
 759       System.out.print("ShiftFrom(" + from + ")==");
 760       if (too == null)
 761       {
 762         System.out.print("NaN\n");
 763       }
 764       else
 765       {
 766         System.out.print(too[0] + " % " + too[1] + " (" + too[2] + ")");
 767         System.out.print("\t+--+\t");
 768         int[] toofrom = ml.shiftTo(too[0]);
 769         if (toofrom != null)
 770         {
 771           if (toofrom[0] != from)
 772           {
 773             System.err.println("Mapping not reflexive:" + from + " "
 774                     + too[0] + "->" + toofrom[0]);
 775           }
 776           System.out.println("ShiftTo(" + too[0] + ")==" + toofrom[0]
 777                   + " % " + toofrom[1] + " (" + toofrom[2] + ")");
 778         }
 779         else
 780         {
 781           System.out.println("ShiftTo(" + too[0] + ")=="
 782                   + "NaN! - not Bijective Mapping!");
 783         }
 784       }
 785     }
 786     int mmap[][] = ml.makeFromMap();
 787     System.out.println("FromMap : (" + mmap[0][0] + " " + mmap[0][1] + " "
 788             + mmap[0][2] + " " + mmap[0][3] + " ");
 789     for (int i = 1; i <= mmap[1].length; i++)
 790     {
 791       if (mmap[1][i - 1] == -1)
 792       {
 793         System.out.print(i + "=XXX");
 794
 795       }
 796       else
 797       {
 798         System.out.print(i + "=" + (mmap[0][2] + mmap[1][i - 1]));
 799       }
 800       if (i % 20 == 0)
 801       {
 802         System.out.print("\n");
 803       }
 804       else
 805       {
 806         System.out.print(",");
 807       }
 808     }
 809     // test range function
 810     System.out.print("\nTest locateInFrom\n");
 811     {
 812       int f = mmap[0][2], t = mmap[0][3];
 813       while (f <= t)
 814       {
 815         System.out.println("Range " + f + " to " + t);
 816         int rng[] = ml.locateInFrom(f, t);
 817         if (rng != null)
 818         {
 819           for (int i = 0; i < rng.length; i++)
 820           {
 821             System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
 822           }
 823         }
 824         else
 825         {
 826           System.out.println("No range!");
 827         }
 828         System.out.print("\nReversed\n");
 829         rng = ml.locateInFrom(t, f);
 830         if (rng != null)
 831         {
 832           for (int i = 0; i < rng.length; i++)
 833           {
 834             System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
 835           }
 836         }
 837         else
 838         {
 839           System.out.println("No range!");
 840         }
 841         System.out.print("\n");
 842         f++;
 843         t--;
 844       }
 845     }
 846     System.out.print("\n");
 847     mmap = ml.makeToMap();
 848     System.out.println("ToMap : (" + mmap[0][0] + " " + mmap[0][1] + " "
 849             + mmap[0][2] + " " + mmap[0][3] + " ");
 850     for (int i = 1; i <= mmap[1].length; i++)
 851     {
 852       if (mmap[1][i - 1] == -1)
 853       {
 854         System.out.print(i + "=XXX");
 855
 856       }
 857       else
 858       {
 859         System.out.print(i + "=" + (mmap[0][2] + mmap[1][i - 1]));
 860       }
 861       if (i % 20 == 0)
 862       {
 863         System.out.print("\n");
 864       }
 865       else
 866       {
 867         System.out.print(",");
 868       }
 869     }
 870     System.out.print("\n");
 871     // test range function
 872     System.out.print("\nTest locateInTo\n");
 873     {
 874       int f = mmap[0][2], t = mmap[0][3];
 875       while (f <= t)
 876       {
 877         System.out.println("Range " + f + " to " + t);
 878         int rng[] = ml.locateInTo(f, t);
 879         if (rng != null)
 880         {
 881           for (int i = 0; i < rng.length; i++)
 882           {
 883             System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
 884           }
 885         }
 886         else
 887         {
 888           System.out.println("No range!");
 889         }
 890         System.out.print("\nReversed\n");
 891         rng = ml.locateInTo(t, f);
 892         if (rng != null)
 893         {
 894           for (int i = 0; i < rng.length; i++)
 895           {
 896             System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
 897           }
 898         }
 899         else
 900         {
 901           System.out.println("No range!");
 902         }
 903         f++;
 904         t--;
 905         System.out.print("\n");
 906       }
 907     }
 908
 909   }
 910
 911   public static void main(String argv[])
 912   {
 913     MapList ml = new MapList(new int[]
 914     { 1, 5, 10, 15, 25, 20 }, new int[]
 915     { 51, 1 }, 1, 3);
 916     MapList ml1 = new MapList(new int[]
 917     { 1, 3, 17, 4 }, new int[]
 918     { 51, 1 }, 1, 3);
 919     MapList ml2 = new MapList(new int[]
 920     { 1, 60 }, new int[]
 921     { 1, 20 }, 3, 1);
 922     // test internal consistency
 923     int to[] = new int[51];
 924     MapList.testMap(ml, 1, 60);
 925     MapList mldna = new MapList(new int[] { 2,2,6,8,12,16}, new int[] { 1,3},3,1);
 926     int[] frm = mldna.locateInFrom(1,1);
 927     testLocateFrom(mldna, 1,1,new int[] { 2,2,6,7});
 928     MapList.testMap(mldna, 1,3);
 929     /*
 930      * for (int from=1; from<=51; from++) { int[] too=ml.shiftTo(from); int[]
 931      * toofrom=ml.shiftFrom(too[0]);
 932      * System.out.println("ShiftFrom("+from+")=="+too[0]+" %
 933      * "+too[1]+"\t+-+\tShiftTo("+too[0]+")=="+toofrom[0]+" % "+toofrom[1]); }
 934      */
 935     System.out.print("Success?\n"); // if we get here - something must be
 936                                     // working!
 937   }
 938
 939   private static void testLocateFrom(MapList mldna, int i, int j, int[] ks)
 940   {
 941     int[] frm = mldna.locateInFrom(i, j);
 942     if (frm==ks || java.util.Arrays.equals(frm,ks))
 943     {
 944       System.out.println("Success test locate from "+i+" to "+j);
 945     } else {
 946       System.err.println("Failed test locate from "+i+" to "+j);
 947       for (int c = 0; c < frm.length; c++)
 948       {
 949         System.err.print(frm[c] + ((c % 2 == 0) ? "," : ";"));
 950       }
 951       System.err.println("Expected");
 952       for (int c = 0; c < ks.length; c++)
 953       {
 954         System.err.print(ks[c] + ((c % 2 == 0) ? "," : ";"));
 955       }
 956     }
 957   }
 958
 959   /**
 960    *
 961    * @return a MapList whose From range is this maplist's To Range, and vice
 962    *         versa
 963    */
 964   public MapList getInverse()
 965   {
 966     return new MapList(getToRanges(), getFromRanges(), getToRatio(),
 967             getFromRatio());
 968   }
 969 }