src/jalview/util/MapList.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer (Version 2.8.2)
   3  * Copyright (C) 2014 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 of the License, or (at your option) any later version.
  10  *
  11  * Jalview is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty
  13  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  14  * PURPOSE.  See the GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
  17  * The Jalview Authors are detailed in the 'AUTHORS' file.
  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[]
 341    *          rshift=null; while (sidx<shifts.size() && (rshift=(int[])
 342    *          shifts.elementAt(sidx))[0]<pos) sidx++; if (sidx==shifts.size())
 343    *          shifts.insertElementAt(new int[] { pos, shift}, sidx); else
 344    *          rshift[1]+=shift; }
 345    */
 346   /**
 347    * shift from pos to To(pos)
 348    *
 349    * @param pos
 350    *          int
 351    * @return int shifted position in To, frameshift in From, direction of mapped
 352    *         symbol in To
 353    */
 354   public int[] shiftFrom(int pos)
 355   {
 356     return shift(pos, fromShifts, fromRatio, toShifts, toRatio);
 357   }
 358
 359   /**
 360    * inverse of shiftFrom - maps pos in To to a position in From
 361    *
 362    * @param pos
 363    *          (in To)
 364    * @return shifted position in From, frameshift in To, direction of mapped
 365    *         symbol in From
 366    */
 367   public int[] shiftTo(int pos)
 368   {
 369     return shift(pos, toShifts, toRatio, fromShifts, fromRatio);
 370   }
 371
 372   /**
 373    *
 374    * @param fromShifts
 375    * @param fromRatio
 376    * @param toShifts
 377    * @param toRatio
 378    * @return
 379    */
 380   private int[] shift(int pos, Vector fromShifts, int fromRatio,
 381           Vector toShifts, int toRatio)
 382   {
 383     int[] fromCount = countPos(fromShifts, pos);
 384     if (fromCount == null)
 385     {
 386       return null;
 387     }
 388     int fromRemainder = (fromCount[0] - 1) % fromRatio;
 389     int toCount = 1 + (((fromCount[0] - 1) / fromRatio) * toRatio);
 390     int[] toPos = countToPos(toShifts, toCount);
 391     if (toPos == null)
 392     {
 393       return null; // throw new Error("Bad Mapping!");
 394     }
 395     // System.out.println(fromCount[0]+" "+fromCount[1]+" "+toCount);
 396     return new int[]
 397     { toPos[0], fromRemainder, toPos[1] };
 398   }
 399
 400   /**
 401    * count how many positions pos is along the series of intervals.
 402    *
 403    * @param intVals
 404    * @param pos
 405    * @return number of positions or null if pos is not within intervals
 406    */
 407   private int[] countPos(Vector intVals, int pos)
 408   {
 409     int count = 0, intv[], iv = 0, ivSize = intVals.size();
 410     while (iv < ivSize)
 411     {
 412       intv = (int[]) intVals.elementAt(iv++);
 413       if (intv[0] <= intv[1])
 414       {
 415         if (pos >= intv[0] && pos <= intv[1])
 416         {
 417           return new int[]
 418           { count + pos - intv[0] + 1, +1 };
 419         }
 420         else
 421         {
 422           count += intv[1] - intv[0] + 1;
 423         }
 424       }
 425       else
 426       {
 427         if (pos >= intv[1] && pos <= intv[0])
 428         {
 429           return new int[]
 430           { count + intv[0] - pos + 1, -1 };
 431         }
 432         else
 433         {
 434           count += intv[0] - intv[1] + 1;
 435         }
 436       }
 437     }
 438     return null;
 439   }
 440
 441   /**
 442    * count out pos positions into a series of intervals and return the position
 443    *
 444    * @param intVals
 445    * @param pos
 446    * @return position pos in interval set
 447    */
 448   private int[] countToPos(Vector intVals, int pos)
 449   {
 450     int count = 0, diff = 0, iv = 0, ivSize = intVals.size(), intv[] =
 451     { 0, 0 };
 452     while (iv < ivSize)
 453     {
 454       intv = (int[]) intVals.elementAt(iv++);
 455       diff = intv[1] - intv[0];
 456       if (diff >= 0)
 457       {
 458         if (pos <= count + 1 + diff)
 459         {
 460           return new int[]
 461           { pos - count - 1 + intv[0], +1 };
 462         }
 463         else
 464         {
 465           count += 1 + diff;
 466         }
 467       }
 468       else
 469       {
 470         if (pos <= count + 1 - diff)
 471         {
 472           return new int[]
 473           { intv[0] - (pos - count - 1), -1 };
 474         }
 475         else
 476         {
 477           count += 1 - diff;
 478         }
 479       }
 480     }
 481     return null;// (diff<0) ? (intv[1]-1) : (intv[0]+1);
 482   }
 483
 484   /**
 485    * find series of intervals mapping from start-end in the From map.
 486    *
 487    * @param start
 488    *          position in to map
 489    * @param end
 490    *          position in to map
 491    * @return series of ranges in from map
 492    */
 493   public int[] locateInFrom(int start, int end)
 494   {
 495     // inefficient implementation
 496     int fromStart[] = shiftTo(start);
 497     int fromEnd[] = shiftTo(end); // needs to be inclusive of end of symbol
 498     // position
 499     if (fromStart == null || fromEnd == null)
 500       return null;
 501     int iv[] = getIntervals(fromShifts, fromStart, fromEnd, fromRatio);
 502     return iv;
 503   }
 504
 505   /**
 506    * find series of intervals mapping from start-end in the to map.
 507    *
 508    * @param start
 509    *          position in from map
 510    * @param end
 511    *          position in from map
 512    * @return series of ranges in to map
 513    */
 514   public int[] locateInTo(int start, int end)
 515   {
 516     // inefficient implementation
 517     int toStart[] = shiftFrom(start);
 518     int toEnd[] = shiftFrom(end);
 519     if (toStart == null || toEnd == null)
 520       return null;
 521     int iv[] = getIntervals(toShifts, toStart, toEnd, toRatio);
 522     return iv;
 523   }
 524
 525   /**
 526    * like shift - except returns the intervals in the given vector of shifts
 527    * which were spanned in traversing fromStart to fromEnd
 528    *
 529    * @param fromShifts2
 530    * @param fromStart
 531    * @param fromEnd
 532    * @param fromRatio2
 533    * @return series of from,to intervals from from first position of starting
 534    *         region to final position of ending region inclusive
 535    */
 536   private int[] getIntervals(Vector fromShifts2, int[] fromStart,
 537           int[] fromEnd, int fromRatio2)
 538   {
 539     int startpos, endpos;
 540     startpos = fromStart[0]; // first position in fromStart
 541     endpos = fromEnd[0]; // last position in fromEnd
 542     int endindx = (fromRatio2 - 1); // additional positions to get to last
 543     // position from endpos
 544     int intv = 0, intvSize = fromShifts2.size();
 545     int iv[], i = 0, fs = -1, fe_s = -1, fe = -1; // containing intervals
 546     // search intervals to locate ones containing startpos and count endindx
 547     // positions on from endpos
 548     while (intv < intvSize && (fs == -1 || fe == -1))
 549     {
 550       iv = (int[]) fromShifts2.elementAt(intv++);
 551       if (fe_s > -1)
 552       {
 553         endpos = iv[0]; // start counting from beginning of interval
 554         endindx--; // inclusive of endpos
 555       }
 556       if (iv[0] <= iv[1])
 557       {
 558         if (fs == -1 && startpos >= iv[0] && startpos <= iv[1])
 559         {
 560           fs = i;
 561         }
 562         if (endpos >= iv[0] && endpos <= iv[1])
 563         {
 564           if (fe_s == -1)
 565           {
 566             fe_s = i;
 567           }
 568           if (fe_s != -1)
 569           {
 570             if (endpos + endindx <= iv[1])
 571             {
 572               fe = i;
 573               endpos = endpos + endindx; // end of end token is within this
 574               // interval
 575             }
 576             else
 577             {
 578               endindx -= iv[1] - endpos; // skip all this interval too
 579             }
 580           }
 581         }
 582       }
 583       else
 584       {
 585         if (fs == -1 && startpos <= iv[0] && startpos >= iv[1])
 586         {
 587           fs = i;
 588         }
 589         if (endpos <= iv[0] && endpos >= iv[1])
 590         {
 591           if (fe_s == -1)
 592           {
 593             fe_s = i;
 594           }
 595           if (fe_s != -1)
 596           {
 597             if (endpos - endindx >= iv[1])
 598             {
 599               fe = i;
 600               endpos = endpos - endindx; // end of end token is within this
 601               // interval
 602             }
 603             else
 604             {
 605               endindx -= endpos - iv[1]; // skip all this interval too
 606             }
 607           }
 608         }
 609       }
 610       i++;
 611     }
 612     if (fs == fe && fe == -1)
 613       return null;
 614     Vector ranges = new Vector();
 615     if (fs <= fe)
 616     {
 617       intv = fs;
 618       i = fs;
 619       // truncate initial interval
 620       iv = (int[]) fromShifts2.elementAt(intv++);
 621       iv = new int[]
 622       { iv[0], iv[1] };// clone
 623       if (i == fs)
 624         iv[0] = startpos;
 625       while (i != fe)
 626       {
 627         ranges.addElement(iv); // add initial range
 628         iv = (int[]) fromShifts2.elementAt(intv++); // get next interval
 629         iv = new int[]
 630         { iv[0], iv[1] };// clone
 631         i++;
 632       }
 633       if (i == fe)
 634         iv[1] = endpos;
 635       ranges.addElement(iv); // add only - or final range
 636     }
 637     else
 638     {
 639       // walk from end of interval.
 640       i = fromShifts2.size() - 1;
 641       while (i > fs)
 642       {
 643         i--;
 644       }
 645       iv = (int[]) fromShifts2.elementAt(i);
 646       iv = new int[]
 647       { iv[1], iv[0] };// reverse and clone
 648       // truncate initial interval
 649       if (i == fs)
 650       {
 651         iv[0] = startpos;
 652       }
 653       while (--i != fe)
 654       { // fix apparent logic bug when fe==-1
 655         ranges.addElement(iv); // add (truncated) reversed interval
 656         iv = (int[]) fromShifts2.elementAt(i);
 657         iv = new int[]
 658         { iv[1], iv[0] }; // reverse and clone
 659       }
 660       if (i == fe)
 661       {
 662         // interval is already reversed
 663         iv[1] = endpos;
 664       }
 665       ranges.addElement(iv); // add only - or final range
 666     }
 667     // create array of start end intervals.
 668     int[] range = null;
 669     if (ranges != null && ranges.size() > 0)
 670     {
 671       range = new int[ranges.size() * 2];
 672       intv = 0;
 673       intvSize = ranges.size();
 674       i = 0;
 675       while (intv < intvSize)
 676       {
 677         iv = (int[]) ranges.elementAt(intv);
 678         range[i++] = iv[0];
 679         range[i++] = iv[1];
 680         ranges.setElementAt(null, intv++); // remove
 681       }
 682     }
 683     return range;
 684   }
 685
 686   /**
 687    * get the 'initial' position of mpos in To
 688    *
 689    * @param mpos
 690    *          position in from
 691    * @return position of first word in to reference frame
 692    */
 693   public int getToPosition(int mpos)
 694   {
 695     int[] mp = shiftTo(mpos);
 696     if (mp != null)
 697     {
 698       return mp[0];
 699     }
 700     return mpos;
 701   }
 702
 703   /**
 704    * get range of positions in To frame for the mpos word in From
 705    *
 706    * @param mpos
 707    *          position in From
 708    * @return null or int[] first position in To for mpos, last position in to
 709    *         for Mpos
 710    */
 711   public int[] getToWord(int mpos)
 712   {
 713     int[] mp = shiftTo(mpos);
 714     if (mp != null)
 715     {
 716       return new int[]
 717       { mp[0], mp[0] + mp[2] * (getFromRatio() - 1) };
 718     }
 719     return null;
 720   }
 721
 722   /**
 723    * get From position in the associated reference frame for position pos in the
 724    * associated sequence.
 725    *
 726    * @param pos
 727    * @return
 728    */
 729   public int getMappedPosition(int pos)
 730   {
 731     int[] mp = shiftFrom(pos);
 732     if (mp != null)
 733     {
 734       return mp[0];
 735     }
 736     return pos;
 737   }
 738
 739   public int[] getMappedWord(int pos)
 740   {
 741     int[] mp = shiftFrom(pos);
 742     if (mp != null)
 743     {
 744       return new int[]
 745       { mp[0], mp[0] + mp[2] * (getToRatio() - 1) };
 746     }
 747     return null;
 748   }
 749
 750   /**
 751    * test routine. not incremental.
 752    *
 753    * @param ml
 754    * @param fromS
 755    * @param fromE
 756    */
 757   public static void testMap(MapList ml, int fromS, int fromE)
 758   {
 759     for (int from = 1; from <= 25; from++)
 760     {
 761       int[] too = ml.shiftFrom(from);
 762       System.out.print("ShiftFrom(" + from + ")==");
 763       if (too == null)
 764       {
 765         System.out.print("NaN\n");
 766       }
 767       else
 768       {
 769         System.out.print(too[0] + " % " + too[1] + " (" + too[2] + ")");
 770         System.out.print("\t+--+\t");
 771         int[] toofrom = ml.shiftTo(too[0]);
 772         if (toofrom != null)
 773         {
 774           if (toofrom[0] != from)
 775           {
 776             System.err.println("Mapping not reflexive:" + from + " "
 777                     + too[0] + "->" + toofrom[0]);
 778           }
 779           System.out.println("ShiftTo(" + too[0] + ")==" + toofrom[0]
 780                   + " % " + toofrom[1] + " (" + toofrom[2] + ")");
 781         }
 782         else
 783         {
 784           System.out.println("ShiftTo(" + too[0] + ")=="
 785                   + "NaN! - not Bijective Mapping!");
 786         }
 787       }
 788     }
 789     int mmap[][] = ml.makeFromMap();
 790     System.out.println("FromMap : (" + mmap[0][0] + " " + mmap[0][1] + " "
 791             + mmap[0][2] + " " + mmap[0][3] + " ");
 792     for (int i = 1; i <= mmap[1].length; i++)
 793     {
 794       if (mmap[1][i - 1] == -1)
 795       {
 796         System.out.print(i + "=XXX");
 797
 798       }
 799       else
 800       {
 801         System.out.print(i + "=" + (mmap[0][2] + mmap[1][i - 1]));
 802       }
 803       if (i % 20 == 0)
 804       {
 805         System.out.print("\n");
 806       }
 807       else
 808       {
 809         System.out.print(",");
 810       }
 811     }
 812     // test range function
 813     System.out.print("\nTest locateInFrom\n");
 814     {
 815       int f = mmap[0][2], t = mmap[0][3];
 816       while (f <= t)
 817       {
 818         System.out.println("Range " + f + " to " + t);
 819         int rng[] = ml.locateInFrom(f, t);
 820         if (rng != null)
 821         {
 822           for (int i = 0; i < rng.length; i++)
 823           {
 824             System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
 825           }
 826         }
 827         else
 828         {
 829           System.out.println("No range!");
 830         }
 831         System.out.print("\nReversed\n");
 832         rng = ml.locateInFrom(t, f);
 833         if (rng != null)
 834         {
 835           for (int i = 0; i < rng.length; i++)
 836           {
 837             System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
 838           }
 839         }
 840         else
 841         {
 842           System.out.println("No range!");
 843         }
 844         System.out.print("\n");
 845         f++;
 846         t--;
 847       }
 848     }
 849     System.out.print("\n");
 850     mmap = ml.makeToMap();
 851     System.out.println("ToMap : (" + mmap[0][0] + " " + mmap[0][1] + " "
 852             + mmap[0][2] + " " + mmap[0][3] + " ");
 853     for (int i = 1; i <= mmap[1].length; i++)
 854     {
 855       if (mmap[1][i - 1] == -1)
 856       {
 857         System.out.print(i + "=XXX");
 858
 859       }
 860       else
 861       {
 862         System.out.print(i + "=" + (mmap[0][2] + mmap[1][i - 1]));
 863       }
 864       if (i % 20 == 0)
 865       {
 866         System.out.print("\n");
 867       }
 868       else
 869       {
 870         System.out.print(",");
 871       }
 872     }
 873     System.out.print("\n");
 874     // test range function
 875     System.out.print("\nTest locateInTo\n");
 876     {
 877       int f = mmap[0][2], t = mmap[0][3];
 878       while (f <= t)
 879       {
 880         System.out.println("Range " + f + " to " + t);
 881         int rng[] = ml.locateInTo(f, t);
 882         if (rng != null)
 883         {
 884           for (int i = 0; i < rng.length; i++)
 885           {
 886             System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
 887           }
 888         }
 889         else
 890         {
 891           System.out.println("No range!");
 892         }
 893         System.out.print("\nReversed\n");
 894         rng = ml.locateInTo(t, f);
 895         if (rng != null)
 896         {
 897           for (int i = 0; i < rng.length; i++)
 898           {
 899             System.out.print(rng[i] + ((i % 2 == 0) ? "," : ";"));
 900           }
 901         }
 902         else
 903         {
 904           System.out.println("No range!");
 905         }
 906         f++;
 907         t--;
 908         System.out.print("\n");
 909       }
 910     }
 911
 912   }
 913
 914   public static void main(String argv[])
 915   {
 916     MapList ml = new MapList(new int[]
 917     { 1, 5, 10, 15, 25, 20 }, new int[]
 918     { 51, 1 }, 1, 3);
 919     MapList ml1 = new MapList(new int[]
 920     { 1, 3, 17, 4 }, new int[]
 921     { 51, 1 }, 1, 3);
 922     MapList ml2 = new MapList(new int[]
 923     { 1, 60 }, new int[]
 924     { 1, 20 }, 3, 1);
 925     // test internal consistency
 926     int to[] = new int[51];
 927     MapList.testMap(ml, 1, 60);
 928     MapList mldna = new MapList(new int[]
 929     { 2, 2, 6, 8, 12, 16 }, new int[]
 930     { 1, 3 }, 3, 1);
 931     int[] frm = mldna.locateInFrom(1, 1);
 932     testLocateFrom(mldna, 1, 1, new int[]
 933     { 2, 2, 6, 7 });
 934     MapList.testMap(mldna, 1, 3);
 935     /*
 936      * for (int from=1; from<=51; from++) { int[] too=ml.shiftTo(from); int[]
 937      * toofrom=ml.shiftFrom(too[0]);
 938      * System.out.println("ShiftFrom("+from+")=="+too[0]+" %
 939      * "+too[1]+"\t+-+\tShiftTo("+too[0]+")=="+toofrom[0]+" % "+toofrom[1]); }
 940      */
 941     System.out.print("Success?\n"); // if we get here - something must be
 942     // working!
 943   }
 944
 945   private static void testLocateFrom(MapList mldna, int i, int j, int[] ks)
 946   {
 947     int[] frm = mldna.locateInFrom(i, j);
 948     if (frm == ks || java.util.Arrays.equals(frm, ks))
 949     {
 950       System.out.println("Success test locate from " + i + " to " + j);
 951     }
 952     else
 953     {
 954       System.err.println("Failed test locate from " + i + " to " + j);
 955       for (int c = 0; c < frm.length; c++)
 956       {
 957         System.err.print(frm[c] + ((c % 2 == 0) ? "," : ";"));
 958       }
 959       System.err.println("Expected");
 960       for (int c = 0; c < ks.length; c++)
 961       {
 962         System.err.print(ks[c] + ((c % 2 == 0) ? "," : ";"));
 963       }
 964     }
 965   }
 966
 967   /**
 968    *
 969    * @return a MapList whose From range is this maplist's To Range, and vice
 970    *         versa
 971    */
 972   public MapList getInverse()
 973   {
 974     return new MapList(getToRanges(), getFromRanges(), getToRatio(),
 975             getFromRatio());
 976   }
 977
 978   /**
 979    * test for containment rather than equivalence to another mapping
 980    *
 981    * @param map
 982    *          to be tested for containment
 983    * @return true if local or mapped range map contains or is contained by this
 984    *         mapping
 985    */
 986   public boolean containsEither(boolean local, MapList map)
 987   {
 988     if (local)
 989     {
 990       return ((getFromLowest() >= map.getFromLowest() && getFromHighest() <= map
 991               .getFromHighest()) || (getFromLowest() <= map.getFromLowest() && getFromHighest() >= map
 992               .getFromHighest()));
 993     }
 994     else
 995     {
 996       return ((getToLowest() >= map.getToLowest() && getToHighest() <= map
 997               .getToHighest()) || (getToLowest() <= map.getToLowest() && getToHighest() >= map
 998               .getToHighest()));
 999     }
1000   }
1001 }