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