src/jalview/util/MapList.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
   3  * Copyright (C) $$Year-Rel$$ 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;
  45
  46   /*
  47    * Same format as fromShifts, for the 'mapped to' sequence
  48    */
  49   private List<int[]> toShifts;
  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    * Constructor
  77    */
  78   public MapList()
  79   {
  80     fromShifts = new ArrayList<int[]>();
  81     toShifts = new ArrayList<int[]>();
  82   }
  83
  84   /**
  85    * Two MapList objects are equal if they are the same object, or they both
  86    * have populated shift ranges and all values are the same.
  87    */
  88   @Override
  89   public boolean equals(Object o)
  90   {
  91     // TODO should also override hashCode to ensure equal objects have equal
  92     // hashcodes
  93     if (o == null || !(o instanceof MapList))
  94     {
  95       return false;
  96     }
  97
  98     MapList obj = (MapList) o;
  99     if (obj == this)
 100     {
 101       return true;
 102     }
 103     if (obj.fromRatio != fromRatio || obj.toRatio != toRatio
 104             || obj.fromShifts == null || obj.toShifts == null)
 105     {
 106       return false;
 107     }
 108     return Arrays
 109             .deepEquals(fromShifts.toArray(), obj.fromShifts.toArray())
 110             && Arrays
 111                     .deepEquals(toShifts.toArray(), obj.toShifts.toArray());
 112   }
 113
 114   /**
 115    * Returns the 'from' ranges as {[start1, end1], [start2, end2], ...}
 116    *
 117    * @return
 118    */
 119   public List<int[]> getFromRanges()
 120   {
 121     return fromShifts;
 122   }
 123
 124   /**
 125    * Returns the 'to' ranges as {[start1, end1], [start2, end2], ...}
 126    *
 127    * @return
 128    */
 129   public List<int[]> getToRanges()
 130   {
 131     return toShifts;
 132   }
 133
 134   /**
 135    * Flattens a list of [start, end] into a single [start1, end1, start2,
 136    * end2,...] array.
 137    *
 138    * @param shifts
 139    * @return
 140    */
 141   protected static int[] getRanges(List<int[]> shifts)
 142   {
 143     int[] rnges = new int[2 * shifts.size()];
 144     int i = 0;
 145     for (int[] r : shifts)
 146     {
 147       rnges[i++] = r[0];
 148       rnges[i++] = r[1];
 149     }
 150     return rnges;
 151   }
 152
 153   /**
 154    *
 155    * @return length of mapped phrase in from
 156    */
 157   public int getFromRatio()
 158   {
 159     return fromRatio;
 160   }
 161
 162   /**
 163    *
 164    * @return length of mapped phrase in to
 165    */
 166   public int getToRatio()
 167   {
 168     return toRatio;
 169   }
 170
 171   public int getFromLowest()
 172   {
 173     return fromLowest;
 174   }
 175
 176   public int getFromHighest()
 177   {
 178     return fromHighest;
 179   }
 180
 181   public int getToLowest()
 182   {
 183     return toLowest;
 184   }
 185
 186   public int getToHighest()
 187   {
 188     return toHighest;
 189   }
 190
 191   /**
 192    * Constructor given from and to ranges as [start1, end1, start2, end2,...].
 193    * If any end is equal to the next start, the ranges will be merged. There is
 194    * no validation check that the ranges do not overlap each other.
 195    *
 196    * @param from
 197    *          contiguous regions as [start1, end1, start2, end2, ...]
 198    * @param to
 199    *          same format as 'from'
 200    * @param fromRatio
 201    *          phrase length in 'from' (e.g. 3 for dna)
 202    * @param toRatio
 203    *          phrase length in 'to' (e.g. 1 for protein)
 204    */
 205   public MapList(int from[], int to[], int fromRatio, int toRatio)
 206   {
 207     this();
 208     this.fromRatio = fromRatio;
 209     this.toRatio = toRatio;
 210     fromLowest = Integer.MAX_VALUE;
 211     fromHighest = Integer.MIN_VALUE;
 212     int added = 0;
 213
 214     for (int i = 0; i < from.length; i += 2)
 215     {
 216       /*
 217        * note lowest and highest values - bearing in mind the
 218        * direction may be revesed
 219        */
 220       fromLowest = Math.min(fromLowest, Math.min(from[i], from[i + 1]));
 221       fromHighest = Math.max(fromHighest, Math.max(from[i], from[i + 1]));
 222       if (added > 0 && from[i] == fromShifts.get(added - 1)[1])
 223       {
 224         /*
 225          * this range starts where the last ended - just extend it
 226          */
 227         fromShifts.get(added - 1)[1] = from[i + 1];
 228       }
 229       else
 230       {
 231         fromShifts.add(new int[] { from[i], from[i + 1] });
 232         added++;
 233       }
 234     }
 235
 236     toLowest = Integer.MAX_VALUE;
 237     toHighest = Integer.MIN_VALUE;
 238     added = 0;
 239     for (int i = 0; i < to.length; i += 2)
 240     {
 241       toLowest = Math.min(toLowest, Math.min(to[i], to[i + 1]));
 242       toHighest = Math.max(toHighest, Math.max(to[i], to[i + 1]));
 243       if (added > 0 && to[i] == toShifts.get(added - 1)[1])
 244       {
 245         toShifts.get(added - 1)[1] = to[i + 1];
 246       }
 247       else
 248       {
 249         toShifts.add(new int[] { to[i], to[i + 1] });
 250         added++;
 251       }
 252     }
 253   }
 254
 255   /**
 256    * Copy constructor. Creates an identical mapping.
 257    *
 258    * @param map
 259    */
 260   public MapList(MapList map)
 261   {
 262     this();
 263     // TODO not used - remove?
 264     this.fromLowest = map.fromLowest;
 265     this.fromHighest = map.fromHighest;
 266     this.toLowest = map.toLowest;
 267     this.toHighest = map.toHighest;
 268
 269     this.fromRatio = map.fromRatio;
 270     this.toRatio = map.toRatio;
 271     if (map.fromShifts != null)
 272     {
 273       for (int[] r : map.fromShifts)
 274       {
 275         fromShifts.add(new int[] { r[0], r[1] });
 276       }
 277     }
 278     if (map.toShifts != null)
 279     {
 280       for (int[] r : map.toShifts)
 281       {
 282         toShifts.add(new int[] { r[0], r[1] });
 283       }
 284     }
 285   }
 286
 287   /**
 288    * Constructor given ranges as lists of [start, end] positions. There is no
 289    * validation check that the ranges do not overlap each other.
 290    *
 291    * @param fromRange
 292    * @param toRange
 293    * @param fromRatio
 294    * @param toRatio
 295    */
 296   public MapList(List<int[]> fromRange, List<int[]> toRange, int fromRatio,
 297           int toRatio)
 298   {
 299     this();
 300     this.fromShifts = fromRange;
 301     this.toShifts = toRange;
 302     this.fromRatio = fromRatio;
 303     this.toRatio = toRatio;
 304
 305     fromLowest = Integer.MAX_VALUE;
 306     fromHighest = Integer.MIN_VALUE;
 307     for (int[] range : fromRange)
 308     {
 309       fromLowest = Math.min(fromLowest, Math.min(range[0], range[1]));
 310       fromHighest = Math.max(fromHighest, Math.max(range[0], range[1]));
 311     }
 312
 313     toLowest = Integer.MAX_VALUE;
 314     toHighest = Integer.MIN_VALUE;
 315     for (int[] range : toRange)
 316     {
 317       toLowest = Math.min(toLowest, Math.min(range[0], range[1]));
 318       toHighest = Math.max(toHighest, Math.max(range[0], range[1]));
 319     }
 320   }
 321
 322   /**
 323    * get all mapped positions from 'from' to 'to'
 324    *
 325    * @return int[][] { int[] { fromStart, fromFinish, toStart, toFinish }, int
 326    *         [fromFinish-fromStart+2] { toStart..toFinish mappings}}
 327    */
 328   protected int[][] makeFromMap()
 329   {
 330     // TODO not used - remove??
 331     return posMap(fromShifts, fromRatio, toShifts, toRatio);
 332   }
 333
 334   /**
 335    * get all mapped positions from 'to' to 'from'
 336    *
 337    * @return int[to position]=position mapped in from
 338    */
 339   protected int[][] makeToMap()
 340   {
 341     // TODO not used - remove??
 342     return posMap(toShifts, toRatio, fromShifts, fromRatio);
 343   }
 344
 345   /**
 346    * construct an int map for intervals in intVals
 347    *
 348    * @param shiftTo
 349    * @return int[] { from, to pos in range }, int[range.to-range.from+1]
 350    *         returning mapped position
 351    */
 352   private int[][] posMap(List<int[]> shiftTo, int ratio,
 353           List<int[]> shiftFrom, int toRatio)
 354   {
 355     // TODO not used - remove??
 356     int iv = 0, ivSize = shiftTo.size();
 357     if (iv >= ivSize)
 358     {
 359       return null;
 360     }
 361     int[] intv = shiftTo.get(iv++);
 362     int from = intv[0], to = intv[1];
 363     if (from > to)
 364     {
 365       from = intv[1];
 366       to = intv[0];
 367     }
 368     while (iv < ivSize)
 369     {
 370       intv = shiftTo.get(iv++);
 371       if (intv[0] < from)
 372       {
 373         from = intv[0];
 374       }
 375       if (intv[1] < from)
 376       {
 377         from = intv[1];
 378       }
 379       if (intv[0] > to)
 380       {
 381         to = intv[0];
 382       }
 383       if (intv[1] > to)
 384       {
 385         to = intv[1];
 386       }
 387     }
 388     int tF = 0, tT = 0;
 389     int mp[][] = new int[to - from + 2][];
 390     for (int i = 0; i < mp.length; i++)
 391     {
 392       int[] m = shift(i + from, shiftTo, ratio, shiftFrom, toRatio);
 393       if (m != null)
 394       {
 395         if (i == 0)
 396         {
 397           tF = tT = m[0];
 398         }
 399         else
 400         {
 401           if (m[0] < tF)
 402           {
 403             tF = m[0];
 404           }
 405           if (m[0] > tT)
 406           {
 407             tT = m[0];
 408           }
 409         }
 410       }
 411       mp[i] = m;
 412     }
 413     int[][] map = new int[][] { new int[] { from, to, tF, tT },
 414         new int[to - from + 2] };
 415
 416     map[0][2] = tF;
 417     map[0][3] = tT;
 418
 419     for (int i = 0; i < mp.length; i++)
 420     {
 421       if (mp[i] != null)
 422       {
 423         map[1][i] = mp[i][0] - tF;
 424       }
 425       else
 426       {
 427         map[1][i] = -1; // indicates an out of range mapping
 428       }
 429     }
 430     return map;
 431   }
 432
 433   /**
 434    * addShift
 435    *
 436    * @param pos
 437    *          start position for shift (in original reference frame)
 438    * @param shift
 439    *          length of shift
 440    *
 441    *          public void addShift(int pos, int shift) { int sidx = 0; int[]
 442    *          rshift=null; while (sidx<shifts.size() && (rshift=(int[])
 443    *          shifts.elementAt(sidx))[0]<pos) sidx++; if (sidx==shifts.size())
 444    *          shifts.insertElementAt(new int[] { pos, shift}, sidx); else
 445    *          rshift[1]+=shift; }
 446    */
 447
 448   /**
 449    * shift from pos to To(pos)
 450    *
 451    * @param pos
 452    *          int
 453    * @return int shifted position in To, frameshift in From, direction of mapped
 454    *         symbol in To
 455    */
 456   public int[] shiftFrom(int pos)
 457   {
 458     return shift(pos, fromShifts, fromRatio, toShifts, toRatio);
 459   }
 460
 461   /**
 462    * inverse of shiftFrom - maps pos in To to a position in From
 463    *
 464    * @param pos
 465    *          (in To)
 466    * @return shifted position in From, frameshift in To, direction of mapped
 467    *         symbol in From
 468    */
 469   public int[] shiftTo(int pos)
 470   {
 471     return shift(pos, toShifts, toRatio, fromShifts, fromRatio);
 472   }
 473
 474   /**
 475    *
 476    * @param shiftTo
 477    * @param fromRatio
 478    * @param shiftFrom
 479    * @param toRatio
 480    * @return
 481    */
 482   protected static int[] shift(int pos, List<int[]> shiftTo, int fromRatio,
 483           List<int[]> shiftFrom, int toRatio)
 484   {
 485     // TODO: javadoc; tests
 486     int[] fromCount = countPos(shiftTo, pos);
 487     if (fromCount == null)
 488     {
 489       return null;
 490     }
 491     int fromRemainder = (fromCount[0] - 1) % fromRatio;
 492     int toCount = 1 + (((fromCount[0] - 1) / fromRatio) * toRatio);
 493     int[] toPos = countToPos(shiftFrom, toCount);
 494     if (toPos == null)
 495     {
 496       return null; // throw new Error("Bad Mapping!");
 497     }
 498     // System.out.println(fromCount[0]+" "+fromCount[1]+" "+toCount);
 499     return new int[] { toPos[0], fromRemainder, toPos[1] };
 500   }
 501
 502   /**
 503    * count how many positions pos is along the series of intervals.
 504    *
 505    * @param shiftTo
 506    * @param pos
 507    * @return number of positions or null if pos is not within intervals
 508    */
 509   protected static int[] countPos(List<int[]> shiftTo, int pos)
 510   {
 511     int count = 0, intv[], iv = 0, ivSize = shiftTo.size();
 512     while (iv < ivSize)
 513     {
 514       intv = shiftTo.get(iv++);
 515       if (intv[0] <= intv[1])
 516       {
 517         if (pos >= intv[0] && pos <= intv[1])
 518         {
 519           return new int[] { count + pos - intv[0] + 1, +1 };
 520         }
 521         else
 522         {
 523           count += intv[1] - intv[0] + 1;
 524         }
 525       }
 526       else
 527       {
 528         if (pos >= intv[1] && pos <= intv[0])
 529         {
 530           return new int[] { count + intv[0] - pos + 1, -1 };
 531         }
 532         else
 533         {
 534           count += intv[0] - intv[1] + 1;
 535         }
 536       }
 537     }
 538     return null;
 539   }
 540
 541   /**
 542    * count out pos positions into a series of intervals and return the position
 543    *
 544    * @param shiftFrom
 545    * @param pos
 546    * @return position pos in interval set
 547    */
 548   protected static int[] countToPos(List<int[]> shiftFrom, int pos)
 549   {
 550     int count = 0, diff = 0, iv = 0, ivSize = shiftFrom.size();
 551     int[] intv = { 0, 0 };
 552     while (iv < ivSize)
 553     {
 554       intv = shiftFrom.get(iv++);
 555       diff = intv[1] - intv[0];
 556       if (diff >= 0)
 557       {
 558         if (pos <= count + 1 + diff)
 559         {
 560           return new int[] { pos - count - 1 + intv[0], +1 };
 561         }
 562         else
 563         {
 564           count += 1 + diff;
 565         }
 566       }
 567       else
 568       {
 569         if (pos <= count + 1 - diff)
 570         {
 571           return new int[] { intv[0] - (pos - count - 1), -1 };
 572         }
 573         else
 574         {
 575           count += 1 - diff;
 576         }
 577       }
 578     }
 579     return null;// (diff<0) ? (intv[1]-1) : (intv[0]+1);
 580   }
 581
 582   /**
 583    * find series of intervals mapping from start-end in the From map.
 584    *
 585    * @param start
 586    *          position mapped 'to'
 587    * @param end
 588    *          position mapped 'to'
 589    * @return series of [start, end] ranges in sequence mapped 'from'
 590    */
 591   public int[] locateInFrom(int start, int end)
 592   {
 593     // inefficient implementation
 594     int fromStart[] = shiftTo(start);
 595     // needs to be inclusive of end of symbol position
 596     int fromEnd[] = shiftTo(end);
 597
 598     return getIntervals(fromShifts, fromStart, fromEnd, fromRatio);
 599   }
 600
 601   /**
 602    * find series of intervals mapping from start-end in the to map.
 603    *
 604    * @param start
 605    *          position mapped 'from'
 606    * @param end
 607    *          position mapped 'from'
 608    * @return series of [start, end] ranges in sequence mapped 'to'
 609    */
 610   public int[] locateInTo(int start, int end)
 611   {
 612     int toStart[] = shiftFrom(start);
 613     int toEnd[] = shiftFrom(end);
 614     return getIntervals(toShifts, toStart, toEnd, toRatio);
 615   }
 616
 617   /**
 618    * like shift - except returns the intervals in the given vector of shifts
 619    * which were spanned in traversing fromStart to fromEnd
 620    *
 621    * @param shiftFrom
 622    * @param fromStart
 623    * @param fromEnd
 624    * @param fromRatio2
 625    * @return series of from,to intervals from from first position of starting
 626    *         region to final position of ending region inclusive
 627    */
 628   protected static int[] getIntervals(List<int[]> shiftFrom,
 629           int[] fromStart, int[] fromEnd, int fromRatio2)
 630   {
 631     if (fromStart == null || fromEnd == null)
 632     {
 633       return null;
 634     }
 635     int startpos, endpos;
 636     startpos = fromStart[0]; // first position in fromStart
 637     endpos = fromEnd[0]; // last position in fromEnd
 638     int endindx = (fromRatio2 - 1); // additional positions to get to last
 639     // position from endpos
 640     int intv = 0, intvSize = shiftFrom.size();
 641     int iv[], i = 0, fs = -1, fe_s = -1, fe = -1; // containing intervals
 642     // search intervals to locate ones containing startpos and count endindx
 643     // positions on from endpos
 644     while (intv < intvSize && (fs == -1 || fe == -1))
 645     {
 646       iv = shiftFrom.get(intv++);
 647       if (fe_s > -1)
 648       {
 649         endpos = iv[0]; // start counting from beginning of interval
 650         endindx--; // inclusive of endpos
 651       }
 652       if (iv[0] <= iv[1])
 653       {
 654         if (fs == -1 && startpos >= iv[0] && startpos <= iv[1])
 655         {
 656           fs = i;
 657         }
 658         if (endpos >= iv[0] && endpos <= iv[1])
 659         {
 660           if (fe_s == -1)
 661           {
 662             fe_s = i;
 663           }
 664           if (fe_s != -1)
 665           {
 666             if (endpos + endindx <= iv[1])
 667             {
 668               fe = i;
 669               endpos = endpos + endindx; // end of end token is within this
 670               // interval
 671             }
 672             else
 673             {
 674               endindx -= iv[1] - endpos; // skip all this interval too
 675             }
 676           }
 677         }
 678       }
 679       else
 680       {
 681         if (fs == -1 && startpos <= iv[0] && startpos >= iv[1])
 682         {
 683           fs = i;
 684         }
 685         if (endpos <= iv[0] && endpos >= iv[1])
 686         {
 687           if (fe_s == -1)
 688           {
 689             fe_s = i;
 690           }
 691           if (fe_s != -1)
 692           {
 693             if (endpos - endindx >= iv[1])
 694             {
 695               fe = i;
 696               endpos = endpos - endindx; // end of end token is within this
 697               // interval
 698             }
 699             else
 700             {
 701               endindx -= endpos - iv[1]; // skip all this interval too
 702             }
 703           }
 704         }
 705       }
 706       i++;
 707     }
 708     if (fs == fe && fe == -1)
 709     {
 710       return null;
 711     }
 712     List<int[]> ranges = new ArrayList<int[]>();
 713     if (fs <= fe)
 714     {
 715       intv = fs;
 716       i = fs;
 717       // truncate initial interval
 718       iv = shiftFrom.get(intv++);
 719       iv = new int[] { iv[0], iv[1] };// clone
 720       if (i == fs)
 721       {
 722         iv[0] = startpos;
 723       }
 724       while (i != fe)
 725       {
 726         ranges.add(iv); // add initial range
 727         iv = shiftFrom.get(intv++); // get next interval
 728         iv = new int[] { iv[0], iv[1] };// clone
 729         i++;
 730       }
 731       if (i == fe)
 732       {
 733         iv[1] = endpos;
 734       }
 735       ranges.add(iv); // add only - or final range
 736     }
 737     else
 738     {
 739       // walk from end of interval.
 740       i = shiftFrom.size() - 1;
 741       while (i > fs)
 742       {
 743         i--;
 744       }
 745       iv = shiftFrom.get(i);
 746       iv = new int[] { iv[1], iv[0] };// reverse and clone
 747       // truncate initial interval
 748       if (i == fs)
 749       {
 750         iv[0] = startpos;
 751       }
 752       while (--i != fe)
 753       { // fix apparent logic bug when fe==-1
 754         ranges.add(iv); // add (truncated) reversed interval
 755         iv = shiftFrom.get(i);
 756         iv = new int[] { iv[1], iv[0] }; // reverse and clone
 757       }
 758       if (i == fe)
 759       {
 760         // interval is already reversed
 761         iv[1] = endpos;
 762       }
 763       ranges.add(iv); // add only - or final range
 764     }
 765     // create array of start end intervals.
 766     int[] range = null;
 767     if (ranges != null && ranges.size() > 0)
 768     {
 769       range = new int[ranges.size() * 2];
 770       intv = 0;
 771       intvSize = ranges.size();
 772       i = 0;
 773       while (intv < intvSize)
 774       {
 775         iv = ranges.get(intv);
 776         range[i++] = iv[0];
 777         range[i++] = iv[1];
 778         ranges.set(intv++, null); // remove
 779       }
 780     }
 781     return range;
 782   }
 783
 784   /**
 785    * get the 'initial' position of mpos in To
 786    *
 787    * @param mpos
 788    *          position in from
 789    * @return position of first word in to reference frame
 790    */
 791   public int getToPosition(int mpos)
 792   {
 793     // TODO not used - remove??
 794     int[] mp = shiftTo(mpos);
 795     if (mp != null)
 796     {
 797       return mp[0];
 798     }
 799     return mpos;
 800   }
 801
 802   /**
 803    * get range of positions in To frame for the mpos word in From
 804    *
 805    * @param mpos
 806    *          position in From
 807    * @return null or int[] first position in To for mpos, last position in to
 808    *         for Mpos
 809    */
 810   public int[] getToWord(int mpos)
 811   {
 812     int[] mp = shiftTo(mpos);
 813     if (mp != null)
 814     {
 815       return new int[] { mp[0], mp[0] + mp[2] * (getFromRatio() - 1) };
 816     }
 817     return null;
 818   }
 819
 820   /**
 821    * get From position in the associated reference frame for position pos in the
 822    * associated sequence.
 823    *
 824    * @param pos
 825    * @return
 826    */
 827   public int getMappedPosition(int pos)
 828   {
 829     // TODO not used - remove??
 830     int[] mp = shiftFrom(pos);
 831     if (mp != null)
 832     {
 833       return mp[0];
 834     }
 835     return pos;
 836   }
 837
 838   public int[] getMappedWord(int pos)
 839   {
 840     // TODO not used - remove??
 841     int[] mp = shiftFrom(pos);
 842     if (mp != null)
 843     {
 844       return new int[] { mp[0], mp[0] + mp[2] * (getToRatio() - 1) };
 845     }
 846     return null;
 847   }
 848
 849   /**
 850    *
 851    * @return a MapList whose From range is this maplist's To Range, and vice
 852    *         versa
 853    */
 854   public MapList getInverse()
 855   {
 856     return new MapList(getToRanges(), getFromRanges(), getToRatio(),
 857             getFromRatio());
 858   }
 859
 860   /**
 861    * test for containment rather than equivalence to another mapping
 862    *
 863    * @param map
 864    *          to be tested for containment
 865    * @return true if local or mapped range map contains or is contained by this
 866    *         mapping
 867    */
 868   public boolean containsEither(boolean local, MapList map)
 869   {
 870     // TODO not used - remove?
 871     if (local)
 872     {
 873       return ((getFromLowest() >= map.getFromLowest() && getFromHighest() <= map
 874               .getFromHighest()) || (getFromLowest() <= map.getFromLowest() && getFromHighest() >= map
 875               .getFromHighest()));
 876     }
 877     else
 878     {
 879       return ((getToLowest() >= map.getToLowest() && getToHighest() <= map
 880               .getToHighest()) || (getToLowest() <= map.getToLowest() && getToHighest() >= map
 881               .getToHighest()));
 882     }
 883   }
 884
 885   /**
 886    * String representation - for debugging, not guaranteed not to change
 887    */
 888   @Override
 889   public String toString()
 890   {
 891     StringBuilder sb = new StringBuilder(64);
 892     sb.append("[");
 893     for (int[] shift : fromShifts)
 894     {
 895       sb.append(" ").append(Arrays.toString(shift));
 896     }
 897     sb.append(" ] To [");
 898     for (int[] shift : toShifts)
 899     {
 900       sb.append(" ").append(Arrays.toString(shift));
 901     }
 902     sb.append(" ]");
 903     return sb.toString();
 904   }
 905
 906   /**
 907    * Extend this map list by adding the given map's ranges. There is no
 908    * validation check that the ranges do not overlap existing ranges (or each
 909    * other), but contiguous ranges are merged.
 910    *
 911    * @param map
 912    */
 913   public void addMapList(MapList map)
 914   {
 915     this.fromLowest = Math.min(fromLowest, map.fromLowest);
 916     this.toLowest = Math.min(toLowest, map.toLowest);
 917     this.fromHighest = Math.max(fromHighest, map.fromHighest);
 918     this.toHighest = Math.max(toHighest, map.toHighest);
 919
 920     for (int[] range : map.getFromRanges())
 921     {
 922       addRange(range, fromShifts);
 923     }
 924     for (int[] range : map.getToRanges())
 925     {
 926       addRange(range, toShifts);
 927     }
 928   }
 929
 930   public static void addRange(int[] range, List<int[]> addTo)
 931   {
 932     /*
 933      * list is empty - add to it!
 934      */
 935     if (addTo.size() == 0)
 936     {
 937       addTo.add(range);
 938       return;
 939     }
 940
 941     int[] last = addTo.get(addTo.size() - 1);
 942     boolean lastForward = last[1] >= last[0];
 943     boolean newForward = range[1] >= range[0];
 944
 945     /*
 946      * contiguous range in the same direction - just update endpoint
 947      */
 948     if (lastForward == newForward && last[1] == range[0])
 949     {
 950       last[1] = range[1];
 951       return;
 952     }
 953
 954     /*
 955      * next range starts at +1 in forward sense - update endpoint
 956      */
 957     if (lastForward && newForward && range[0] == last[1] + 1)
 958     {
 959       last[1] = range[1];
 960       return;
 961     }
 962
 963     /*
 964      * next range starts at -1 in reverse sense - update endpoint
 965      */
 966     if (!lastForward && !newForward && range[0] == last[1] - 1)
 967     {
 968       last[1] = range[1];
 969       return;
 970     }
 971
 972     /*
 973      * just add the new range
 974      */
 975     addTo.add(range);
 976   }
 977
 978   /**
 979    * Returns true if mapping is from forward strand, false if from reverse
 980    * strand. Result is just based on the first 'from' range that is not a single
 981    * position. Default is true unless proven to be false. Behaviour is not well
 982    * defined if the mapping has a mixture of forward and reverse ranges.
 983    *
 984    * @return
 985    */
 986   public boolean isFromForwardStrand()
 987   {
 988     boolean forwardStrand = true;
 989     for (int[] range : getFromRanges())
 990     {
 991       if (range[1] > range[0])
 992       {
 993         break; // forward strand confirmed
 994       }
 995       else if (range[1] < range[0])
 996       {
 997         forwardStrand = false;
 998         break; // reverse strand confirmed
 999       }
1000     }
1001     return forwardStrand;
1002   }
1003 }