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