src/jalview/util/MapList.java

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