src/jalview/util/MapList.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer (Version 2.4)
   3  * Copyright (C) 2008 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
 573                                           // interval
 574             }
 575             else
 576             {
 577               endindx -= iv[1] - endpos; // skip all this interval too
 578             }
 579           }
 580         }
 581       }
 582       else
 583       {
 584         if (fs == -1 && startpos <= iv[0] && startpos >= iv[1])
 585         {
 586           fs = i;
 587         }
 588         if (endpos <= iv[0] && endpos >= iv[1])
 589         {
 590           if (fe_s == -1)
 591           {
 592             fe_s = i;
 593           }
 594           if (fe_s != -1)
 595           {
 596             if (endpos - endindx >= iv[1])
 597             {
 598               fe = i;
 599               endpos = endpos - endindx; // end of end token is within this
 600                                           // interval
 601             }
 602             else
 603             {
 604               endindx -= endpos - iv[1]; // skip all this interval too
 605             }
 606           }
 607         }
 608       }
 609       i++;
 610     }
 611     if (fs == fe && fe == -1)
 612       return null;
 613     Vector ranges = new Vector();
 614     if (fs <= fe)
 615     {
 616       intv = fs;
 617       i = fs;
 618       // truncate initial interval
 619       iv = (int[]) fromShifts2.elementAt(intv++);
 620       iv = new int[]
 621       { iv[0], iv[1] };// clone
 622       if (i == fs)
 623         iv[0] = startpos;
 624       while (i != fe)
 625       {
 626         ranges.addElement(iv); // add initial range
 627         iv = (int[]) fromShifts2.elementAt(intv++); // get next interval
 628         iv = new int[]
 629         { iv[0], iv[1] };// clone
 630         i++;
 631       }
 632       if (i == fe)
 633         iv[1] = endpos;
 634       ranges.addElement(iv); // add only - or final range
 635     }
 636     else
 637     {
 638       // walk from end of interval.
 639       i = fromShifts2.size() - 1;
 640       while (i > fs)
 641       {
 642         i--;
 643       }
 644       iv = (int[]) fromShifts2.elementAt(i);
 645       iv = new int[]
 646       { iv[1], iv[0] };// reverse and clone
 647       // truncate initial interval
 648       if (i == fs)
 649       {
 650         iv[0] = startpos;
 651       }
 652       while (--i != fe)
 653       { // fix apparent logic bug when fe==-1
 654         ranges.addElement(iv); // add (truncated) reversed interval
 655         iv = (int[]) fromShifts2.elementAt(i);
 656         iv = new int[]
 657         { iv[1], iv[0] }; // reverse and clone
 658       }
 659       if (i == fe)
 660       {
 661         // interval is already reversed
 662         iv[1] = endpos;
 663       }
 664       ranges.addElement(iv); // add only - or final range
 665     }
 666     // create array of start end intervals.
 667     int[] range = null;
 668     if (ranges != null && ranges.size() > 0)
 669     {
 670       range = new int[ranges.size() * 2];
 671       intv = 0;
 672       intvSize = ranges.size();
 673       i = 0;
 674       while (intv < intvSize)
 675       {
 676         iv = (int[]) ranges.elementAt(intv);
 677         range[i++] = iv[0];
 678         range[i++] = iv[1];
 679         ranges.setElementAt(null, intv++); // remove
 680       }
 681     }
 682     return range;
 683   }
 684
 685   /**
 686    * get the 'initial' position of mpos in To
 687    *
 688    * @param mpos
 689    *                position in from
 690    * @return position of first word in to reference frame
 691    */
 692   public int getToPosition(int mpos)
 693   {
 694     int[] mp = shiftTo(mpos);
 695     if (mp != null)
 696     {
 697       return mp[0];
 698     }
 699     return mpos;
 700   }
 701
 702   /**
 703    * get range of positions in To frame for the mpos word in From
 704    *
 705    * @param mpos
 706    *                position in From
 707    * @return null or int[] first position in To for mpos, last position in to
 708    *         for Mpos
 709    */
 710   public int[] getToWord(int mpos)
 711   {
 712     int[] mp = shiftTo(mpos);
 713     if (mp != null)
 714     {
 715       return new int[]
 716       { mp[0], mp[0] + mp[2] * (getFromRatio() - 1) };
 717     }
 718     return null;
 719   }
 720
 721   /**
 722    * get From position in the associated reference frame for position pos in the
 723    * associated sequence.
 724    *
 725    * @param pos
 726    * @return
 727    */
 728   public int getMappedPosition(int pos)
 729   {
 730     int[] mp = shiftFrom(pos);
 731     if (mp != null)
 732     {
 733       return mp[0];
 734     }
 735     return pos;
 736   }
 737
 738   public int[] getMappedWord(int pos)
 739   {
 740     int[] mp = shiftFrom(pos);
 741     if (mp != null)
 742     {
 743       return new int[]
 744       { mp[0], mp[0] + mp[2] * (getToRatio() - 1) };
 745     }
 746     return null;
 747   }
 748
 749   /**
 750    * test routine. not incremental.
 751    *
 752    * @param ml
 753    * @param fromS
 754    * @param fromE
 755    */
 756   public static void testMap(MapList ml, int fromS, int fromE)
 757   {
 758     for (int from = 1; from <= 25; from++)
 759     {
 760       int[] too = ml.shiftFrom(from);
 761       System.out.print("ShiftFrom(" + from + ")==");
 762       if (too == null)
 763       {
 764         System.out.print("NaN\n");
 765       }
 766       else
 767       {
 768         System.out.print(too[0] + " % " + too[1] + " (" + too[2] + ")");
 769         System.out.print("\t+--+\t");
 770         int[] toofrom = ml.shiftTo(too[0]);
 771         if (toofrom != null)
 772         {
 773           if (toofrom[0] != from)
 774           {
 775             System.err.println("Mapping not reflexive:" + from + " "
 776                     + too[0] + "->" + toofrom[0]);
 777           }
 778           System.out.println("ShiftTo(" + too[0] + ")==" + toofrom[0]
 779                   + " % " + toofrom[1] + " (" + toofrom[2] + ")");
 780         }
 781         else
 782         {
 783           System.out.println("ShiftTo(" + too[0] + ")=="
 784                   + "NaN! - not Bijective Mapping!");
 785         }
 786       }
 787     }
 788     int mmap[][] = ml.makeFromMap();
 789     System.out.println("FromMap : (" + mmap[0][0] + " " + mmap[0][1] + " "
 790             + mmap[0][2] + " " + mmap[0][3] + " ");
 791     for (int i = 1; i <= mmap[1].length; i++)
 792     {
 793       if (mmap[1][i - 1] == -1)
 794       {
 795         System.out.print(i + "=XXX");
 796
 797       }
 798       else
 799       {
 800         System.out.print(i + "=" + (mmap[0][2] + mmap[1][i - 1]));
 801       }
 802       if (i % 20 == 0)
 803       {
 804         System.out.print("\n");
 805       }
 806       else
 807       {
 808         System.out.print(",");
 809       }
 810     }
 811     // test range function
 812     System.out.print("\nTest locateInFrom\n");
 813     {
 814       int f = mmap[0][2], t = mmap[0][3];
 815       while (f <= t)
 816       {
 817         System.out.println("Range " + f + " to " + t);
 818         int rng[] = ml.locateInFrom(f, t);
 819         if (rng != null)
 820         {
 821           for (int i = 0; i < rng.length; i++)
 822           {
 823             System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
 824           }
 825         }
 826         else
 827         {
 828           System.out.println("No range!");
 829         }
 830         System.out.print("\nReversed\n");
 831         rng = ml.locateInFrom(t, f);
 832         if (rng != null)
 833         {
 834           for (int i = 0; i < rng.length; i++)
 835           {
 836             System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
 837           }
 838         }
 839         else
 840         {
 841           System.out.println("No range!");
 842         }
 843         System.out.print("\n");
 844         f++;
 845         t--;
 846       }
 847     }
 848     System.out.print("\n");
 849     mmap = ml.makeToMap();
 850     System.out.println("ToMap : (" + mmap[0][0] + " " + mmap[0][1] + " "
 851             + mmap[0][2] + " " + mmap[0][3] + " ");
 852     for (int i = 1; i <= mmap[1].length; i++)
 853     {
 854       if (mmap[1][i - 1] == -1)
 855       {
 856         System.out.print(i + "=XXX");
 857
 858       }
 859       else
 860       {
 861         System.out.print(i + "=" + (mmap[0][2] + mmap[1][i - 1]));
 862       }
 863       if (i % 20 == 0)
 864       {
 865         System.out.print("\n");
 866       }
 867       else
 868       {
 869         System.out.print(",");
 870       }
 871     }
 872     System.out.print("\n");
 873     // test range function
 874     System.out.print("\nTest locateInTo\n");
 875     {
 876       int f = mmap[0][2], t = mmap[0][3];
 877       while (f <= t)
 878       {
 879         System.out.println("Range " + f + " to " + t);
 880         int rng[] = ml.locateInTo(f, t);
 881         if (rng != null)
 882         {
 883           for (int i = 0; i < rng.length; i++)
 884           {
 885             System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
 886           }
 887         }
 888         else
 889         {
 890           System.out.println("No range!");
 891         }
 892         System.out.print("\nReversed\n");
 893         rng = ml.locateInTo(t, f);
 894         if (rng != null)
 895         {
 896           for (int i = 0; i < rng.length; i++)
 897           {
 898             System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
 899           }
 900         }
 901         else
 902         {
 903           System.out.println("No range!");
 904         }
 905         f++;
 906         t--;
 907         System.out.print("\n");
 908       }
 909     }
 910
 911   }
 912
 913   public static void main(String argv[])
 914   {
 915     MapList ml = new MapList(new int[]
 916     { 1, 5, 10, 15, 25, 20 }, new int[]
 917     { 51, 1 }, 1, 3);
 918     MapList ml1 = new MapList(new int[]
 919     { 1, 3, 17, 4 }, new int[]
 920     { 51, 1 }, 1, 3);
 921     MapList ml2 = new MapList(new int[]
 922     { 1, 60 }, new int[]
 923     { 1, 20 }, 3, 1);
 924     // test internal consistency
 925     int to[] = new int[51];
 926     MapList.testMap(ml, 1, 60);
 927     MapList mldna = new MapList(new int[]
 928     { 2, 2, 6, 8, 12, 16 }, new int[]
 929     { 1, 3 }, 3, 1);
 930     int[] frm = mldna.locateInFrom(1, 1);
 931     testLocateFrom(mldna, 1, 1, new int[]
 932     { 2, 2, 6, 7 });
 933     MapList.testMap(mldna, 1, 3);
 934     /*
 935      * for (int from=1; from<=51; from++) { int[] too=ml.shiftTo(from); int[]
 936      * toofrom=ml.shiftFrom(too[0]);
 937      * System.out.println("ShiftFrom("+from+")=="+too[0]+" %
 938      * "+too[1]+"\t+-+\tShiftTo("+too[0]+")=="+toofrom[0]+" % "+toofrom[1]); }
 939      */
 940     System.out.print("Success?\n"); // if we get here - something must be
 941     // working!
 942   }
 943
 944   private static void testLocateFrom(MapList mldna, int i, int j, int[] ks)
 945   {
 946     int[] frm = mldna.locateInFrom(i, j);
 947     if (frm == ks || java.util.Arrays.equals(frm, ks))
 948     {
 949       System.out.println("Success test locate from " + i + " to " + j);
 950     }
 951     else
 952     {
 953       System.err.println("Failed test locate from " + i + " to " + j);
 954       for (int c = 0; c < frm.length; c++)
 955       {
 956         System.err.print(frm[c] + ((c % 2 == 0) ? "," : ";"));
 957       }
 958       System.err.println("Expected");
 959       for (int c = 0; c < ks.length; c++)
 960       {
 961         System.err.print(ks[c] + ((c % 2 == 0) ? "," : ";"));
 962       }
 963     }
 964   }
 965
 966   /**
 967    *
 968    * @return a MapList whose From range is this maplist's To Range, and vice
 969    *         versa
 970    */
 971   public MapList getInverse()
 972   {
 973     return new MapList(getToRanges(), getFromRanges(), getToRatio(),
 974             getFromRatio());
 975   }
 976 }