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
  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.Enumeration;
  24 import java.util.Vector;
  25
  26 /**
  27  * MapList Simple way of bijectively mapping a non-contiguous linear range to
  28  * another non-contiguous linear range Use at your own risk! TODO: efficient
  29  * implementation of private posMap method TODO: test/ensure that sense of from
  30  * and to ratio start position is conserved (codon start position recovery)
  31  * TODO: optimize to use int[][] arrays rather than vectors.
  32  */
  33 public class MapList
  34 {
  35   /*
  36    * (non-Javadoc)
  37    *
  38    * @see java.lang.Object#equals(java.lang.Object)
  39    */
  40   public boolean equals(MapList obj)
  41   {
  42     if (obj == this)
  43     {
  44       return true;
  45     }
  46     if (obj != null && obj.fromRatio == fromRatio && obj.toRatio == toRatio
  47             && obj.fromShifts != null && obj.toShifts != null)
  48     {
  49       int i, iSize = fromShifts.size(), j, jSize = obj.fromShifts.size();
  50       if (iSize != jSize)
  51       {
  52         return false;
  53       }
  54       for (i = 0, iSize = fromShifts.size(), j = 0, jSize = obj.fromShifts
  55               .size(); i < iSize;)
  56       {
  57         int[] mi = (int[]) fromShifts.elementAt(i++);
  58         int[] mj = (int[]) obj.fromShifts.elementAt(j++);
  59         if (mi[0] != mj[0] || mi[1] != mj[1])
  60         {
  61           return false;
  62         }
  63       }
  64       iSize = toShifts.size();
  65       jSize = obj.toShifts.size();
  66       if (iSize != jSize)
  67       {
  68         return false;
  69       }
  70       for (i = 0, j = 0; i < iSize;)
  71       {
  72         int[] mi = (int[]) toShifts.elementAt(i++);
  73         int[] mj = (int[]) obj.toShifts.elementAt(j++);
  74         if (mi[0] != mj[0] || mi[1] != mj[1])
  75         {
  76           return false;
  77         }
  78       }
  79       return true;
  80     }
  81     return false;
  82   }
  83
  84   public Vector fromShifts;
  85
  86   public Vector toShifts;
  87
  88   int fromRatio; // number of steps in fromShifts to one toRatio unit
  89
  90   int toRatio; // number of steps in toShifts to one fromRatio
  91
  92   /**
  93    *
  94    * @return series of intervals mapped in from
  95    */
  96   public int[] getFromRanges()
  97   {
  98     return getRanges(fromShifts);
  99   }
 100
 101   public int[] getToRanges()
 102   {
 103     return getRanges(toShifts);
 104   }
 105
 106   private int[] getRanges(Vector shifts)
 107   {
 108     int[] rnges = new int[2 * shifts.size()];
 109     Enumeration e = shifts.elements();
 110     int i = 0;
 111     while (e.hasMoreElements())
 112     {
 113       int r[] = (int[]) e.nextElement();
 114       rnges[i++] = r[0];
 115       rnges[i++] = r[1];
 116     }
 117     return rnges;
 118   }
 119
 120   /**
 121    * lowest and highest value in the from Map
 122    */
 123   int[] fromRange = null;
 124
 125   /**
 126    * lowest and highest value in the to Map
 127    */
 128   int[] toRange = null;
 129
 130   /**
 131    *
 132    * @return length of mapped phrase in from
 133    */
 134   public int getFromRatio()
 135   {
 136     return fromRatio;
 137   }
 138
 139   /**
 140    *
 141    * @return length of mapped phrase in to
 142    */
 143   public int getToRatio()
 144   {
 145     return toRatio;
 146   }
 147
 148   public int getFromLowest()
 149   {
 150     return fromRange[0];
 151   }
 152
 153   public int getFromHighest()
 154   {
 155     return fromRange[1];
 156   }
 157
 158   public int getToLowest()
 159   {
 160     return toRange[0];
 161   }
 162
 163   public int getToHighest()
 164   {
 165     return toRange[1];
 166   }
 167
 168   private void ensureRange(int[] limits, int pos)
 169   {
 170     if (limits[0] > pos)
 171     {
 172       limits[0] = pos;
 173     }
 174     if (limits[1] < pos)
 175     {
 176       limits[1] = pos;
 177     }
 178   }
 179
 180   public MapList(int from[], int to[], int fromRatio, int toRatio)
 181   {
 182     fromRange = new int[]
 183     { from[0], from[1] };
 184     toRange = new int[]
 185     { to[0], to[1] };
 186
 187     fromShifts = new Vector();
 188     for (int i = 0; i < from.length; i += 2)
 189     {
 190       ensureRange(fromRange, from[i]);
 191       ensureRange(fromRange, from[i + 1]);
 192
 193       fromShifts.addElement(new int[]
 194       { from[i], from[i + 1] });
 195     }
 196     toShifts = new Vector();
 197     for (int i = 0; i < to.length; i += 2)
 198     {
 199       ensureRange(toRange, to[i]);
 200       ensureRange(toRange, to[i + 1]);
 201       toShifts.addElement(new int[]
 202       { to[i], to[i + 1] });
 203     }
 204     this.fromRatio = fromRatio;
 205     this.toRatio = toRatio;
 206   }
 207
 208   public MapList(MapList map)
 209   {
 210     this.fromRange = new int[]
 211     { map.fromRange[0], map.fromRange[1] };
 212     this.toRange = new int[]
 213     { map.toRange[0], map.toRange[1] };
 214     this.fromRatio = map.fromRatio;
 215     this.toRatio = map.toRatio;
 216     if (map.fromShifts != null)
 217     {
 218       this.fromShifts = new Vector();
 219       Enumeration e = map.fromShifts.elements();
 220       while (e.hasMoreElements())
 221       {
 222         int[] el = (int[]) e.nextElement();
 223         fromShifts.addElement(new int[]
 224         { el[0], el[1] });
 225       }
 226     }
 227     if (map.toShifts != null)
 228     {
 229       this.toShifts = new Vector();
 230       Enumeration e = map.toShifts.elements();
 231       while (e.hasMoreElements())
 232       {
 233         int[] el = (int[]) e.nextElement();
 234         toShifts.addElement(new int[]
 235         { el[0], el[1] });
 236       }
 237     }
 238   }
 239
 240   /**
 241    * get all mapped positions from 'from' to 'to'
 242    *
 243    * @return int[][] { int[] { fromStart, fromFinish, toStart, toFinish }, int
 244    *         [fromFinish-fromStart+2] { toStart..toFinish mappings}}
 245    */
 246   public int[][] makeFromMap()
 247   {
 248     return posMap(fromShifts, fromRatio, toShifts, toRatio);
 249   }
 250
 251   /**
 252    * get all mapped positions from 'to' to 'from'
 253    *
 254    * @return int[to position]=position mapped in from
 255    */
 256   public int[][] makeToMap()
 257   {
 258     return posMap(toShifts, toRatio, fromShifts, fromRatio);
 259   }
 260
 261   /**
 262    * construct an int map for intervals in intVals
 263    *
 264    * @param intVals
 265    * @return int[] { from, to pos in range }, int[range.to-range.from+1]
 266    *         returning mapped position
 267    */
 268   private int[][] posMap(Vector intVals, int ratio, Vector toIntVals,
 269           int toRatio)
 270   {
 271     int iv = 0, ivSize = intVals.size();
 272     if (iv >= ivSize)
 273     {
 274       return null;
 275     }
 276     int[] intv = (int[]) intVals.elementAt(iv++);
 277     int from = intv[0], to = intv[1];
 278     if (from > to)
 279     {
 280       from = intv[1];
 281       to = intv[0];
 282     }
 283     while (iv < ivSize)
 284     {
 285       intv = (int[]) intVals.elementAt(iv++);
 286       if (intv[0] < from)
 287       {
 288         from = intv[0];
 289       }
 290       if (intv[1] < from)
 291       {
 292         from = intv[1];
 293       }
 294       if (intv[0] > to)
 295       {
 296         to = intv[0];
 297       }
 298       if (intv[1] > to)
 299       {
 300         to = intv[1];
 301       }
 302     }
 303     int tF = 0, tT = 0;
 304     int mp[][] = new int[to - from + 2][];
 305     for (int i = 0; i < mp.length; i++)
 306     {
 307       int[] m = shift(i + from, intVals, ratio, toIntVals, toRatio);
 308       if (m != null)
 309       {
 310         if (i == 0)
 311         {
 312           tF = tT = m[0];
 313         }
 314         else
 315         {
 316           if (m[0] < tF)
 317           {
 318             tF = m[0];
 319           }
 320           if (m[0] > tT)
 321           {
 322             tT = m[0];
 323           }
 324         }
 325       }
 326       mp[i] = m;
 327     }
 328     int[][] map = new int[][]
 329     { new int[]
 330     { from, to, tF, tT }, new int[to - from + 2] };
 331
 332     map[0][2] = tF;
 333     map[0][3] = tT;
 334
 335     for (int i = 0; i < mp.length; i++)
 336     {
 337       if (mp[i] != null)
 338       {
 339         map[1][i] = mp[i][0] - tF;
 340       }
 341       else
 342       {
 343         map[1][i] = -1; // indicates an out of range mapping
 344       }
 345     }
 346     return map;
 347   }
 348
 349   /**
 350    * addShift
 351    *
 352    * @param pos
 353    *          start position for shift (in original reference frame)
 354    * @param shift
 355    *          length of shift
 356    *
 357    *          public void addShift(int pos, int shift) { int sidx = 0; int[]
 358    *          rshift=null; while (sidx<shifts.size() && (rshift=(int[])
 359    *          shifts.elementAt(sidx))[0]<pos) sidx++; if (sidx==shifts.size())
 360    *          shifts.insertElementAt(new int[] { pos, shift}, sidx); else
 361    *          rshift[1]+=shift; }
 362    */
 363   /**
 364    * shift from pos to To(pos)
 365    *
 366    * @param pos
 367    *          int
 368    * @return int shifted position in To, frameshift in From, direction of mapped
 369    *         symbol in To
 370    */
 371   public int[] shiftFrom(int pos)
 372   {
 373     return shift(pos, fromShifts, fromRatio, toShifts, toRatio);
 374   }
 375
 376   /**
 377    * inverse of shiftFrom - maps pos in To to a position in From
 378    *
 379    * @param pos
 380    *          (in To)
 381    * @return shifted position in From, frameshift in To, direction of mapped
 382    *         symbol in From
 383    */
 384   public int[] shiftTo(int pos)
 385   {
 386     return shift(pos, toShifts, toRatio, fromShifts, fromRatio);
 387   }
 388
 389   /**
 390    *
 391    * @param fromShifts
 392    * @param fromRatio
 393    * @param toShifts
 394    * @param toRatio
 395    * @return
 396    */
 397   private int[] shift(int pos, Vector fromShifts, int fromRatio,
 398           Vector toShifts, int toRatio)
 399   {
 400     int[] fromCount = countPos(fromShifts, pos);
 401     if (fromCount == null)
 402     {
 403       return null;
 404     }
 405     int fromRemainder = (fromCount[0] - 1) % fromRatio;
 406     int toCount = 1 + (((fromCount[0] - 1) / fromRatio) * toRatio);
 407     int[] toPos = countToPos(toShifts, toCount);
 408     if (toPos == null)
 409     {
 410       return null; // throw new Error("Bad Mapping!");
 411     }
 412     // System.out.println(fromCount[0]+" "+fromCount[1]+" "+toCount);
 413     return new int[]
 414     { toPos[0], fromRemainder, toPos[1] };
 415   }
 416
 417   /**
 418    * count how many positions pos is along the series of intervals.
 419    *
 420    * @param intVals
 421    * @param pos
 422    * @return number of positions or null if pos is not within intervals
 423    */
 424   private int[] countPos(Vector intVals, int pos)
 425   {
 426     int count = 0, intv[], iv = 0, ivSize = intVals.size();
 427     while (iv < ivSize)
 428     {
 429       intv = (int[]) intVals.elementAt(iv++);
 430       if (intv[0] <= intv[1])
 431       {
 432         if (pos >= intv[0] && pos <= intv[1])
 433         {
 434           return new int[]
 435           { count + pos - intv[0] + 1, +1 };
 436         }
 437         else
 438         {
 439           count += intv[1] - intv[0] + 1;
 440         }
 441       }
 442       else
 443       {
 444         if (pos >= intv[1] && pos <= intv[0])
 445         {
 446           return new int[]
 447           { count + intv[0] - pos + 1, -1 };
 448         }
 449         else
 450         {
 451           count += intv[0] - intv[1] + 1;
 452         }
 453       }
 454     }
 455     return null;
 456   }
 457
 458   /**
 459    * count out pos positions into a series of intervals and return the position
 460    *
 461    * @param intVals
 462    * @param pos
 463    * @return position pos in interval set
 464    */
 465   private int[] countToPos(Vector intVals, int pos)
 466   {
 467     int count = 0, diff = 0, iv = 0, ivSize = intVals.size(), intv[] =
 468     { 0, 0 };
 469     while (iv < ivSize)
 470     {
 471       intv = (int[]) intVals.elementAt(iv++);
 472       diff = intv[1] - intv[0];
 473       if (diff >= 0)
 474       {
 475         if (pos <= count + 1 + diff)
 476         {
 477           return new int[]
 478           { pos - count - 1 + intv[0], +1 };
 479         }
 480         else
 481         {
 482           count += 1 + diff;
 483         }
 484       }
 485       else
 486       {
 487         if (pos <= count + 1 - diff)
 488         {
 489           return new int[]
 490           { intv[0] - (pos - count - 1), -1 };
 491         }
 492         else
 493         {
 494           count += 1 - diff;
 495         }
 496       }
 497     }
 498     return null;// (diff<0) ? (intv[1]-1) : (intv[0]+1);
 499   }
 500
 501   /**
 502    * find series of intervals mapping from start-end in the From map.
 503    *
 504    * @param start
 505    *          position in to map
 506    * @param end
 507    *          position in to map
 508    * @return series of ranges in from map
 509    */
 510   public int[] locateInFrom(int start, int end)
 511   {
 512     // inefficient implementation
 513     int fromStart[] = shiftTo(start);
 514     int fromEnd[] = shiftTo(end); // needs to be inclusive of end of symbol
 515     // position
 516     if (fromStart == null || fromEnd == null)
 517     {
 518       return null;
 519     }
 520     int iv[] = getIntervals(fromShifts, fromStart, fromEnd, fromRatio);
 521     return iv;
 522   }
 523
 524   /**
 525    * find series of intervals mapping from start-end in the to map.
 526    *
 527    * @param start
 528    *          position in from map
 529    * @param end
 530    *          position in from map
 531    * @return series of ranges in to map
 532    */
 533   public int[] locateInTo(int start, int end)
 534   {
 535     // inefficient implementation
 536     int toStart[] = shiftFrom(start);
 537     int toEnd[] = shiftFrom(end);
 538     if (toStart == null || toEnd == null)
 539     {
 540       return null;
 541     }
 542     int iv[] = getIntervals(toShifts, toStart, toEnd, toRatio);
 543     return iv;
 544   }
 545
 546   /**
 547    * like shift - except returns the intervals in the given vector of shifts
 548    * which were spanned in traversing fromStart to fromEnd
 549    *
 550    * @param fromShifts2
 551    * @param fromStart
 552    * @param fromEnd
 553    * @param fromRatio2
 554    * @return series of from,to intervals from from first position of starting
 555    *         region to final position of ending region inclusive
 556    */
 557   private int[] getIntervals(Vector fromShifts2, int[] fromStart,
 558           int[] fromEnd, int fromRatio2)
 559   {
 560     int startpos, endpos;
 561     startpos = fromStart[0]; // first position in fromStart
 562     endpos = fromEnd[0]; // last position in fromEnd
 563     int endindx = (fromRatio2 - 1); // additional positions to get to last
 564     // position from endpos
 565     int intv = 0, intvSize = fromShifts2.size();
 566     int iv[], i = 0, fs = -1, fe_s = -1, fe = -1; // containing intervals
 567     // search intervals to locate ones containing startpos and count endindx
 568     // positions on from endpos
 569     while (intv < intvSize && (fs == -1 || fe == -1))
 570     {
 571       iv = (int[]) fromShifts2.elementAt(intv++);
 572       if (fe_s > -1)
 573       {
 574         endpos = iv[0]; // start counting from beginning of interval
 575         endindx--; // inclusive of endpos
 576       }
 577       if (iv[0] <= iv[1])
 578       {
 579         if (fs == -1 && startpos >= iv[0] && startpos <= iv[1])
 580         {
 581           fs = i;
 582         }
 583         if (endpos >= iv[0] && endpos <= iv[1])
 584         {
 585           if (fe_s == -1)
 586           {
 587             fe_s = i;
 588           }
 589           if (fe_s != -1)
 590           {
 591             if (endpos + endindx <= iv[1])
 592             {
 593               fe = i;
 594               endpos = endpos + endindx; // end of end token is within this
 595               // interval
 596             }
 597             else
 598             {
 599               endindx -= iv[1] - endpos; // skip all this interval too
 600             }
 601           }
 602         }
 603       }
 604       else
 605       {
 606         if (fs == -1 && startpos <= iv[0] && startpos >= iv[1])
 607         {
 608           fs = i;
 609         }
 610         if (endpos <= iv[0] && endpos >= iv[1])
 611         {
 612           if (fe_s == -1)
 613           {
 614             fe_s = i;
 615           }
 616           if (fe_s != -1)
 617           {
 618             if (endpos - endindx >= iv[1])
 619             {
 620               fe = i;
 621               endpos = endpos - endindx; // end of end token is within this
 622               // interval
 623             }
 624             else
 625             {
 626               endindx -= endpos - iv[1]; // skip all this interval too
 627             }
 628           }
 629         }
 630       }
 631       i++;
 632     }
 633     if (fs == fe && fe == -1)
 634     {
 635       return null;
 636     }
 637     Vector ranges = new Vector();
 638     if (fs <= fe)
 639     {
 640       intv = fs;
 641       i = fs;
 642       // truncate initial interval
 643       iv = (int[]) fromShifts2.elementAt(intv++);
 644       iv = new int[]
 645       { iv[0], iv[1] };// clone
 646       if (i == fs)
 647       {
 648         iv[0] = startpos;
 649       }
 650       while (i != fe)
 651       {
 652         ranges.addElement(iv); // add initial range
 653         iv = (int[]) fromShifts2.elementAt(intv++); // get next interval
 654         iv = new int[]
 655         { iv[0], iv[1] };// clone
 656         i++;
 657       }
 658       if (i == fe)
 659       {
 660         iv[1] = endpos;
 661       }
 662       ranges.addElement(iv); // add only - or final range
 663     }
 664     else
 665     {
 666       // walk from end of interval.
 667       i = fromShifts2.size() - 1;
 668       while (i > fs)
 669       {
 670         i--;
 671       }
 672       iv = (int[]) fromShifts2.elementAt(i);
 673       iv = new int[]
 674       { iv[1], iv[0] };// reverse and clone
 675       // truncate initial interval
 676       if (i == fs)
 677       {
 678         iv[0] = startpos;
 679       }
 680       while (--i != fe)
 681       { // fix apparent logic bug when fe==-1
 682         ranges.addElement(iv); // add (truncated) reversed interval
 683         iv = (int[]) fromShifts2.elementAt(i);
 684         iv = new int[]
 685         { iv[1], iv[0] }; // reverse and clone
 686       }
 687       if (i == fe)
 688       {
 689         // interval is already reversed
 690         iv[1] = endpos;
 691       }
 692       ranges.addElement(iv); // add only - or final range
 693     }
 694     // create array of start end intervals.
 695     int[] range = null;
 696     if (ranges != null && ranges.size() > 0)
 697     {
 698       range = new int[ranges.size() * 2];
 699       intv = 0;
 700       intvSize = ranges.size();
 701       i = 0;
 702       while (intv < intvSize)
 703       {
 704         iv = (int[]) ranges.elementAt(intv);
 705         range[i++] = iv[0];
 706         range[i++] = iv[1];
 707         ranges.setElementAt(null, intv++); // remove
 708       }
 709     }
 710     return range;
 711   }
 712
 713   /**
 714    * get the 'initial' position of mpos in To
 715    *
 716    * @param mpos
 717    *          position in from
 718    * @return position of first word in to reference frame
 719    */
 720   public int getToPosition(int mpos)
 721   {
 722     int[] mp = shiftTo(mpos);
 723     if (mp != null)
 724     {
 725       return mp[0];
 726     }
 727     return mpos;
 728   }
 729
 730   /**
 731    * get range of positions in To frame for the mpos word in From
 732    *
 733    * @param mpos
 734    *          position in From
 735    * @return null or int[] first position in To for mpos, last position in to
 736    *         for Mpos
 737    */
 738   public int[] getToWord(int mpos)
 739   {
 740     int[] mp = shiftTo(mpos);
 741     if (mp != null)
 742     {
 743       return new int[]
 744       { mp[0], mp[0] + mp[2] * (getFromRatio() - 1) };
 745     }
 746     return null;
 747   }
 748
 749   /**
 750    * get From position in the associated reference frame for position pos in the
 751    * associated sequence.
 752    *
 753    * @param pos
 754    * @return
 755    */
 756   public int getMappedPosition(int pos)
 757   {
 758     int[] mp = shiftFrom(pos);
 759     if (mp != null)
 760     {
 761       return mp[0];
 762     }
 763     return pos;
 764   }
 765
 766   public int[] getMappedWord(int pos)
 767   {
 768     int[] mp = shiftFrom(pos);
 769     if (mp != null)
 770     {
 771       return new int[]
 772       { mp[0], mp[0] + mp[2] * (getToRatio() - 1) };
 773     }
 774     return null;
 775   }
 776
 777   /**
 778    *
 779    * @return a MapList whose From range is this maplist's To Range, and vice
 780    *         versa
 781    */
 782   public MapList getInverse()
 783   {
 784     return new MapList(getToRanges(), getFromRanges(), getToRatio(),
 785             getFromRatio());
 786   }
 787
 788   /**
 789    * test for containment rather than equivalence to another mapping
 790    *
 791    * @param map
 792    *          to be tested for containment
 793    * @return true if local or mapped range map contains or is contained by this
 794    *         mapping
 795    */
 796   public boolean containsEither(boolean local, MapList map)
 797   {
 798     if (local)
 799     {
 800       return ((getFromLowest() >= map.getFromLowest() && getFromHighest() <= map
 801               .getFromHighest()) || (getFromLowest() <= map.getFromLowest() && getFromHighest() >= map
 802               .getFromHighest()));
 803     }
 804     else
 805     {
 806       return ((getToLowest() >= map.getToLowest() && getToHighest() <= map
 807               .getToHighest()) || (getToLowest() <= map.getToLowest() && getToHighest() >= map
 808               .getToHighest()));
 809     }
 810   }
 811 }