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