src/jalview/util/MapList.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer (Version 2.6)
   3  * Copyright (C) 2010 J Procter, AM Waterhouse, G Barton, M Clamp, S Searle
   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  */
  18 package jalview.util;
  19
  20 import java.util.*;
  21
  22 /**
  23  * MapList Simple way of bijectively mapping a non-contiguous linear range to
  24  * another non-contiguous linear range Use at your own risk! TODO: efficient
  25  * implementation of private posMap method TODO: test/ensure that sense of from
  26  * and to ratio start position is conserved (codon start position recovery)
  27  * TODO: optimize to use int[][] arrays rather than vectors.
  28  */
  29 public class MapList
  30 {
  31   /*
  32    * (non-Javadoc)
  33    *
  34    * @see java.lang.Object#equals(java.lang.Object)
  35    */
  36   public boolean equals(MapList obj)
  37   {
  38     if (obj == this)
  39       return true;
  40     if (obj != null && obj.fromRatio == fromRatio && obj.toRatio == toRatio
  41             && obj.fromShifts != null && obj.toShifts != null)
  42     {
  43       int i, iSize = fromShifts.size(), j, jSize = obj.fromShifts.size();
  44       if (iSize != jSize)
  45         return false;
  46       for (i = 0, iSize = fromShifts.size(), j = 0, jSize = obj.fromShifts
  47               .size(); i < iSize;)
  48       {
  49         int[] mi = (int[]) fromShifts.elementAt(i++);
  50         int[] mj = (int[]) obj.fromShifts.elementAt(j++);
  51         if (mi[0] != mj[0] || mi[1] != mj[1])
  52           return false;
  53       }
  54       iSize = toShifts.size();
  55       jSize = obj.toShifts.size();
  56       if (iSize != jSize)
  57         return false;
  58       for (i = 0, j = 0; i < iSize;)
  59       {
  60         int[] mi = (int[]) toShifts.elementAt(i++);
  61         int[] mj = (int[]) obj.toShifts.elementAt(j++);
  62         if (mi[0] != mj[0] || mi[1] != mj[1])
  63           return false;
  64       }
  65       return true;
  66     }
  67     return false;
  68   }
  69
  70   public Vector fromShifts;
  71
  72   public Vector toShifts;
  73
  74   int fromRatio; // number of steps in fromShifts to one toRatio unit
  75
  76   int toRatio; // number of steps in toShifts to one fromRatio
  77
  78   /**
  79    *
  80    * @return series of intervals mapped in from
  81    */
  82   public int[] getFromRanges()
  83   {
  84     return getRanges(fromShifts);
  85   }
  86
  87   public int[] getToRanges()
  88   {
  89     return getRanges(toShifts);
  90   }
  91
  92   private int[] getRanges(Vector shifts)
  93   {
  94     int[] rnges = new int[2 * shifts.size()];
  95     Enumeration e = shifts.elements();
  96     int i = 0;
  97     while (e.hasMoreElements())
  98     {
  99       int r[] = (int[]) e.nextElement();
 100       rnges[i++] = r[0];
 101       rnges[i++] = r[1];
 102     }
 103     return rnges;
 104   }
 105
 106   /**
 107    * lowest and highest value in the from Map
 108    */
 109   int[] fromRange = null;
 110
 111   /**
 112    * lowest and highest value in the to Map
 113    */
 114   int[] toRange = null;
 115
 116   /**
 117    *
 118    * @return length of mapped phrase in from
 119    */
 120   public int getFromRatio()
 121   {
 122     return fromRatio;
 123   }
 124
 125   /**
 126    *
 127    * @return length of mapped phrase in to
 128    */
 129   public int getToRatio()
 130   {
 131     return toRatio;
 132   }
 133
 134   public int getFromLowest()
 135   {
 136     return fromRange[0];
 137   }
 138
 139   public int getFromHighest()
 140   {
 141     return fromRange[1];
 142   }
 143
 144   public int getToLowest()
 145   {
 146     return toRange[0];
 147   }
 148
 149   public int getToHighest()
 150   {
 151     return toRange[1];
 152   }
 153
 154   private void ensureRange(int[] limits, int pos)
 155   {
 156     if (limits[0] > pos)
 157       limits[0] = pos;
 158     if (limits[1] < pos)
 159       limits[1] = pos;
 160   }
 161
 162   public MapList(int from[], int to[], int fromRatio, int toRatio)
 163   {
 164     fromRange = new int[]
 165     { from[0], from[1] };
 166     toRange = new int[]
 167     { to[0], to[1] };
 168
 169     fromShifts = new Vector();
 170     for (int i = 0; i < from.length; i += 2)
 171     {
 172       ensureRange(fromRange, from[i]);
 173       ensureRange(fromRange, from[i + 1]);
 174
 175       fromShifts.addElement(new int[]
 176       { from[i], from[i + 1] });
 177     }
 178     toShifts = new Vector();
 179     for (int i = 0; i < to.length; i += 2)
 180     {
 181       ensureRange(toRange, to[i]);
 182       ensureRange(toRange, to[i + 1]);
 183       toShifts.addElement(new int[]
 184       { to[i], to[i + 1] });
 185     }
 186     this.fromRatio = fromRatio;
 187     this.toRatio = toRatio;
 188   }
 189
 190   public MapList(MapList map)
 191   {
 192     this.fromRange = new int[]
 193     { map.fromRange[0], map.fromRange[1] };
 194     this.toRange = new int[]
 195     { map.toRange[0], map.toRange[1] };
 196     this.fromRatio = map.fromRatio;
 197     this.toRatio = map.toRatio;
 198     if (map.fromShifts != null)
 199     {
 200       this.fromShifts = new Vector();
 201       Enumeration e = map.fromShifts.elements();
 202       while (e.hasMoreElements())
 203       {
 204         int[] el = (int[]) e.nextElement();
 205         fromShifts.addElement(new int[]
 206         { el[0], el[1] });
 207       }
 208     }
 209     if (map.toShifts != null)
 210     {
 211       this.toShifts = new Vector();
 212       Enumeration e = map.toShifts.elements();
 213       while (e.hasMoreElements())
 214       {
 215         int[] el = (int[]) e.nextElement();
 216         toShifts.addElement(new int[]
 217         { el[0], el[1] });
 218       }
 219     }
 220   }
 221
 222   /**
 223    * get all mapped positions from 'from' to 'to'
 224    *
 225    * @return int[][] { int[] { fromStart, fromFinish, toStart, toFinish }, int
 226    *         [fromFinish-fromStart+2] { toStart..toFinish mappings}}
 227    */
 228   public int[][] makeFromMap()
 229   {
 230     return posMap(fromShifts, fromRatio, toShifts, toRatio);
 231   }
 232
 233   /**
 234    * get all mapped positions from 'to' to 'from'
 235    *
 236    * @return int[to position]=position mapped in from
 237    */
 238   public int[][] makeToMap()
 239   {
 240     return posMap(toShifts, toRatio, fromShifts, fromRatio);
 241   }
 242
 243   /**
 244    * construct an int map for intervals in intVals
 245    *
 246    * @param intVals
 247    * @return int[] { from, to pos in range }, int[range.to-range.from+1]
 248    *         returning mapped position
 249    */
 250   private int[][] posMap(Vector intVals, int ratio, Vector toIntVals,
 251           int toRatio)
 252   {
 253     int iv = 0, ivSize = intVals.size();
 254     if (iv >= ivSize)
 255     {
 256       return null;
 257     }
 258     int[] intv = (int[]) intVals.elementAt(iv++);
 259     int from = intv[0], to = intv[1];
 260     if (from > to)
 261     {
 262       from = intv[1];
 263       to = intv[0];
 264     }
 265     while (iv < ivSize)
 266     {
 267       intv = (int[]) intVals.elementAt(iv++);
 268       if (intv[0] < from)
 269       {
 270         from = intv[0];
 271       }
 272       if (intv[1] < from)
 273       {
 274         from = intv[1];
 275       }
 276       if (intv[0] > to)
 277       {
 278         to = intv[0];
 279       }
 280       if (intv[1] > to)
 281       {
 282         to = intv[1];
 283       }
 284     }
 285     int tF = 0, tT = 0;
 286     int mp[][] = new int[to - from + 2][];
 287     for (int i = 0; i < mp.length; i++)
 288     {
 289       int[] m = shift(i + from, intVals, ratio, toIntVals, toRatio);
 290       if (m != null)
 291       {
 292         if (i == 0)
 293         {
 294           tF = tT = m[0];
 295         }
 296         else
 297         {
 298           if (m[0] < tF)
 299           {
 300             tF = m[0];
 301           }
 302           if (m[0] > tT)
 303           {
 304             tT = m[0];
 305           }
 306         }
 307       }
 308       mp[i] = m;
 309     }
 310     int[][] map = new int[][]
 311     { new int[]
 312     { from, to, tF, tT }, new int[to - from + 2] };
 313
 314     map[0][2] = tF;
 315     map[0][3] = tT;
 316
 317     for (int i = 0; i < mp.length; i++)
 318     {
 319       if (mp[i] != null)
 320       {
 321         map[1][i] = mp[i][0] - tF;
 322       }
 323       else
 324       {
 325         map[1][i] = -1; // indicates an out of range mapping
 326       }
 327     }
 328     return map;
 329   }
 330
 331   /**
 332    * addShift
 333    *
 334    * @param pos
 335    *          start position for shift (in original reference frame)
 336    * @param shift
 337    *          length of shift
 338    *
 339    *          public void addShift(int pos, int shift) { int sidx = 0; int[]
 340    *          rshift=null; while (sidx<shifts.size() && (rshift=(int[])
 341    *          shifts.elementAt(sidx))[0]<pos) sidx++; if (sidx==shifts.size())
 342    *          shifts.insertElementAt(new int[] { pos, shift}, sidx); else
 343    *          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
 977   /**
 978    * test for containment rather than equivalence to another mapping
 979    *
 980    * @param map
 981    *          to be tested for containment
 982    * @return true if local or mapped range map contains or is contained by this
 983    *         mapping
 984    */
 985   public boolean containsEither(boolean local, MapList map)
 986   {
 987     if (local)
 988     {
 989       return ((getFromLowest() >= map.getFromLowest() && getFromHighest() <= map
 990               .getFromHighest()) || (getFromLowest() <= map.getFromLowest() && getFromHighest() >= map
 991               .getFromHighest()));
 992     }
 993     else
 994     {
 995       return ((getToLowest() >= map.getToLowest() && getToHighest() <= map
 996               .getToHighest()) || (getToLowest() <= map.getToLowest() && getToHighest() >= map
 997               .getToHighest()));
 998     }
 999   }
1000 }