src/jalview/util/MapList.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer
   3  * Copyright (C) 2007 AM Waterhouse, J Procter, G Barton, M Clamp, S Searle
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License
   7  * as published by the Free Software Foundation; either version 2
   8  * of the License, or (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
  18  */
  19 package jalview.util;
  20
  21 import java.util.*;
  22
  23 /**
  24  * MapList
  25  * Simple way of bijectively mapping a non-contiguous linear range to another non-contiguous linear range
  26  * Use at your own risk!
  27  * TODO: efficient implementation of private posMap method
  28  * TODO: test/ensure that sense of from and to ratio start position is conserved (codon start position recovery)
  29  * TODO: optimize to use int[][] arrays rather than vectors.
  30  */
  31 public class MapList
  32 {
  33   /* (non-Javadoc)
  34    * @see java.lang.Object#equals(java.lang.Object)
  35    */
  36   public boolean equals(MapList obj) {
  37     if (obj==this)
  38       return true;
  39     if (obj!=null && obj.fromRatio==fromRatio && obj.toRatio==toRatio
  40         && obj.fromShifts!=null && obj.toShifts!=null) {
  41       int i,iSize=fromShifts.size(),j,jSize=obj.fromShifts.size();
  42       if (iSize!=jSize)
  43         return false;
  44       for (i=0,iSize=fromShifts.size(),j=0, jSize=obj.fromShifts.size(); i<iSize;) {
  45         int[] mi=(int[]) fromShifts.elementAt(i++);
  46         int[] mj=(int[]) obj.fromShifts.elementAt(j++);
  47         if (mi[0]!=mj[0] || mi[1]!=mj[1])
  48           return false;
  49       }
  50       iSize=toShifts.size();
  51       jSize=obj.toShifts.size();
  52       if (iSize!=jSize)
  53         return false;
  54       for (i=0,j=0; i<iSize;) {
  55         int[] mi=(int[]) toShifts.elementAt(i++);
  56         int[] mj=(int[]) obj.toShifts.elementAt(j++);
  57         if (mi[0]!=mj[0] || mi[1]!=mj[1])
  58           return false;
  59       }
  60       return true;
  61     }
  62     return false;
  63   }
  64   public Vector fromShifts;
  65   public Vector toShifts;
  66   int fromRatio; // number of steps in fromShifts to one toRatio unit
  67   int toRatio; // number of steps in toShifts to one fromRatio
  68   /**
  69    * lowest and highest value in the from Map
  70    */
  71   int[] fromRange=null;
  72   /**
  73    * lowest and highest value in the to Map
  74    */
  75   int[] toRange=null;
  76   public int getFromRatio()
  77   {
  78     return fromRatio;
  79   }
  80   public int getToRatio()
  81   {
  82     return toRatio;
  83   }
  84   public int getFromLowest() {
  85     return fromRange[0];
  86   }
  87   public int getFromHighest() {
  88     return fromRange[1];
  89   }
  90   public int getToLowest() {
  91     return toRange[0];
  92   }
  93   public int getToHighest() {
  94     return toRange[1];
  95   }
  96   private void ensureRange(int[] limits, int pos) {
  97     if (limits[0]>pos)
  98       limits[0]=pos;
  99     if (limits[1]<pos)
 100       limits[1]=pos;
 101   }
 102   public MapList(int from[], int to[], int fromRatio, int toRatio)
 103   {
 104     fromRange=new int[] { from[0],from[1] };
 105     toRange=new int[] { to[0],to[1] };
 106
 107     fromShifts = new Vector();
 108     for (int i=0;i<from.length; i+=2)
 109     {
 110       ensureRange(fromRange, from[i]);
 111       ensureRange(fromRange, from[i+1]);
 112
 113       fromShifts.addElement(new int[]
 114                              {from[i], from[i + 1]});
 115     }
 116     toShifts = new Vector();
 117     for (int i=0;i<to.length; i+=2)
 118     {
 119       ensureRange(toRange, to[i]);
 120       ensureRange(toRange, to[i+1]);
 121       toShifts.addElement(new int[]
 122                            {to[i], to[i + 1]});
 123     }
 124     this.fromRatio=fromRatio;
 125     this.toRatio=toRatio;
 126   }
 127   public MapList(MapList map)
 128   {
 129     this.fromRange = new int[]
 130     { map.fromRange[0], map.fromRange[1] };
 131     this.toRange = new int[]
 132     { map.toRange[0], map.toRange[1] };
 133     this.fromRatio = map.fromRatio;
 134     this.toRatio = map.toRatio;
 135     if (map.fromShifts != null)
 136     {
 137       this.fromShifts = new Vector();
 138       Enumeration e = map.fromShifts.elements();
 139       while (e.hasMoreElements())
 140       {
 141         int[] el = (int[]) e.nextElement();
 142         fromShifts.addElement(new int[]
 143         { el[0], el[1] });
 144       }
 145     }
 146     if (map.toShifts != null)
 147     {
 148       this.toShifts = new Vector();
 149       Enumeration e = map.toShifts.elements();
 150       while (e.hasMoreElements())
 151       {
 152         int[] el = (int[]) e.nextElement();
 153         toShifts.addElement(new int[]
 154         { el[0], el[1] });
 155       }
 156     }
 157   }
 158   /**
 159    * get all mapped positions from 'from' to 'to'
 160    * @return int[][] { int[] { fromStart, fromFinish, toStart, toFinish }, int [fromFinish-fromStart+2] { toStart..toFinish mappings}}
 161    */
 162   public int[][] makeFromMap()
 163   {
 164     return posMap(fromShifts, fromRatio, toShifts, toRatio);
 165   }
 166   /**
 167    * get all mapped positions from 'to' to 'from'
 168    * @return int[to position]=position mapped in from
 169    */
 170   public int[][] makeToMap()
 171   {
 172     return posMap(toShifts,toRatio, fromShifts, fromRatio);
 173   }
 174   /**
 175    * construct an int map for intervals in intVals
 176    * @param intVals
 177    * @return int[] { from, to pos in range }, int[range.to-range.from+1] returning mapped position
 178    */
 179   private int[][] posMap(Vector intVals, int ratio, Vector toIntVals,
 180       int toRatio)
 181   {
 182     int iv=0,ivSize = intVals.size();
 183     if (iv>=ivSize)
 184     {
 185       return null;
 186     }
 187     int[] intv=(int[]) intVals.elementAt(iv++);
 188     int from=intv[0],to=intv[1];
 189     if (from > to)
 190     {
 191       from = intv[1];
 192       to=intv[0];
 193     }
 194     while (iv<ivSize)
 195     {
 196       intv = (int[]) intVals.elementAt(iv++);
 197       if (intv[0]<from)
 198       {
 199         from=intv[0];
 200       }
 201       if (intv[1]<from)
 202       {
 203         from=intv[1];
 204       }
 205       if (intv[0]>to)
 206       {
 207         to=intv[0];
 208       }
 209       if (intv[1]>to)
 210       {
 211         to=intv[1];
 212       }
 213     }
 214     int tF=0,tT=0;
 215     int mp[][] = new int[to-from+2][];
 216     for (int i = 0; i < mp.length; i++)
 217     {
 218       int[] m = shift(i+from,intVals,ratio,toIntVals, toRatio);
 219       if (m != null)
 220       {
 221         if (i == 0)
 222         {
 223           tF=tT=m[0];
 224         }
 225         else
 226         {
 227           if (m[0] < tF)
 228           {
 229             tF=m[0];
 230           }
 231           if (m[0] > tT)
 232           {
 233             tT=m[0];
 234           }
 235         }
 236       }
 237       mp[i] = m;
 238     }
 239     int[][] map = new int[][]
 240                             {
 241         new int[]
 242                 {
 243             from, to, tF, tT}, new int[to - from + 2]};
 244
 245     map[0][2] = tF;
 246     map[0][3] = tT;
 247
 248     for (int i = 0; i < mp.length; i++)
 249     {
 250       if (mp[i] != null)
 251       {
 252         map[1][i] = mp[i][0]-tF;
 253       }
 254       else
 255       {
 256         map[1][i] = -1; // indicates an out of range mapping
 257       }
 258     }
 259     return map;
 260   }
 261   /**
 262    * addShift
 263    * @param pos start position for shift (in original reference frame)
 264    * @param shift length of shift
 265    *
 266   public void addShift(int pos, int shift)
 267   {
 268     int sidx = 0;
 269     int[] rshift=null;
 270     while (sidx<shifts.size() && (rshift=(int[]) shifts.elementAt(sidx))[0]<pos)
 271       sidx++;
 272     if (sidx==shifts.size())
 273       shifts.insertElementAt(new int[] { pos, shift}, sidx);
 274     else
 275       rshift[1]+=shift;
 276   }
 277    */
 278   /**
 279    * shift from pos to To(pos)
 280    *
 281    * @param pos int
 282    * @return int shifted position in To, frameshift in From, direction of mapped symbol in To
 283    */
 284   public int[] shiftFrom(int pos)
 285   {
 286     return shift(pos, fromShifts, fromRatio, toShifts, toRatio);
 287   }
 288
 289   /**
 290    * inverse of shiftFrom - maps pos in To to a position in From
 291    * @param pos (in To)
 292    * @return shifted position in From, frameshift in To, direction of mapped symbol in From
 293    */
 294   public int[] shiftTo(int pos)
 295   {
 296     return shift(pos, toShifts, toRatio, fromShifts, fromRatio);
 297   }
 298   /**
 299    *
 300    * @param fromShifts
 301    * @param fromRatio
 302    * @param toShifts
 303    * @param toRatio
 304    * @return
 305    */
 306   private int[] shift(int pos, Vector fromShifts, int fromRatio,
 307       Vector toShifts, int toRatio)
 308   {
 309     int[] fromCount = countPos(fromShifts, pos);
 310     if (fromCount==null)
 311     {
 312       return null;
 313     }
 314     int fromRemainder=(fromCount[0]-1) % fromRatio;
 315     int toCount = 1+(((fromCount[0]-1) / fromRatio) * toRatio);
 316     int[] toPos = countToPos(toShifts, toCount);
 317     if (toPos==null)
 318     {
 319       return null; // throw new Error("Bad Mapping!");
 320     }
 321     //System.out.println(fromCount[0]+" "+fromCount[1]+" "+toCount);
 322     return new int[]
 323                    {
 324         toPos[0], fromRemainder, toPos[1]};
 325   }
 326   /**
 327    * count how many positions pos is along the series of intervals.
 328    * @param intVals
 329    * @param pos
 330    * @return number of positions or null if pos is not within intervals
 331    */
 332   private int[] countPos(Vector intVals, int pos)
 333   {
 334     int count=0,intv[],iv=0,ivSize=intVals.size();
 335     while (iv<ivSize)
 336     {
 337       intv = (int[])intVals.elementAt(iv++);
 338       if (intv[0] <= intv[1])
 339       {
 340         if (pos >= intv[0] && pos <= intv[1])
 341         {
 342           return new int[]
 343                          {
 344               count + pos - intv[0] + 1, +1};
 345         }
 346         else
 347         {
 348           count+=intv[1]-intv[0]+1;
 349         }
 350       }
 351       else
 352       {
 353         if (pos >= intv[1] && pos <= intv[0])
 354         {
 355           return new int[]
 356                          {
 357               count + intv[0] - pos + 1, -1};
 358         }
 359         else
 360         {
 361           count+=intv[0]-intv[1]+1;
 362         }
 363       }
 364     }
 365     return null;
 366   }
 367   /**
 368    * count out pos positions into a series of intervals and return the position
 369    * @param intVals
 370    * @param pos
 371    * @return position pos in interval set
 372    */
 373   private int[] countToPos(Vector intVals, int pos)
 374   {
 375     int count = 0, diff = 0, iv=0,ivSize=intVals.size(), intv[] =
 376     {
 377         0, 0};
 378     while (iv<ivSize)
 379     {
 380       intv = (int[])intVals.elementAt(iv++);
 381       diff = intv[1]-intv[0];
 382       if (diff >= 0)
 383       {
 384         if (pos <= count + 1 + diff)
 385         {
 386           return new int[]
 387                          {
 388               pos - count - 1 + intv[0], +1};
 389         }
 390         else
 391         {
 392           count+=1+diff;
 393         }
 394       }
 395       else
 396       {
 397         if (pos <= count + 1 - diff)
 398         {
 399           return new int[]
 400                          {
 401               intv[0] - (pos - count - 1), -1};
 402         }
 403         else
 404         {
 405           count+=1-diff;
 406         }
 407       }
 408     }
 409     return null;//(diff<0) ? (intv[1]-1) : (intv[0]+1);
 410   }
 411   /**
 412    * find series of intervals mapping from start-end in the From map.
 413    * @param start position in to map
 414    * @param end position in to map
 415    * @return series of ranges in from map
 416    */
 417   public int[] locateInFrom(int start, int end) {
 418     // inefficient implementation
 419     int fromStart[] = shiftTo(start);
 420     int fromEnd[] = shiftTo(end);
 421     if (fromStart==null || fromEnd==null)
 422       return null;
 423     int iv[] = getIntervals(fromShifts, fromStart, fromEnd,fromRatio);
 424     return iv;
 425   }
 426
 427   /**
 428    * find series of intervals mapping from start-end in the to map.
 429    * @param start position in from map
 430    * @param end position in from map
 431    * @return series of ranges in to map
 432    */
 433   public int[] locateInTo(int start, int end) {
 434     // inefficient implementation
 435     int toStart[] = shiftFrom(start);
 436     int toEnd[] = shiftFrom(end);
 437     if (toStart==null || toEnd==null)
 438       return null;
 439     int iv[] = getIntervals(toShifts, toStart, toEnd, toRatio);
 440     return iv;
 441   }
 442   /**
 443    * like shift - except returns the intervals in the given vector of shifts which were spanned
 444    * in traversing fromStart to fromEnd
 445    * @param fromShifts2
 446    * @param fromStart
 447    * @param fromEnd
 448    * @param fromRatio2
 449    * @return
 450    */
 451   private int[] getIntervals(Vector fromShifts2, int[] fromStart, int[] fromEnd, int fromRatio2)
 452   {
 453     // correct for word direction for start and end
 454     int startpos = fromStart[0]+fromStart[2]*(fromRatio2-1);
 455     int endpos = fromEnd[0]+fromEnd[2]*(fromRatio2-1);
 456     int intv=0,intvSize= fromShifts2.size();
 457     int iv[],i=0,fs=-1,fe=-1; // containing intervals
 458     while (intv<intvSize && (fs==-1 || fe==-1)) {
 459       iv = (int[]) fromShifts2.elementAt(intv++);
 460       if (iv[0]<=iv[1]) {
 461         if (fs==-1 && startpos>=iv[0] && startpos<=iv[1]) {
 462           fs = i;
 463         }
 464         if (fe==-1 && endpos>=iv[0] && endpos<=iv[1]) {
 465           fe = i;
 466         }
 467       } else {
 468         if (fs==-1 && startpos<=iv[0] && startpos>=iv[1]) {
 469           fs = i;
 470         }
 471         if (fe==-1 && endpos<=iv[0] && endpos>=iv[1]) {
 472           fe = i;
 473         }
 474       }
 475       i++;
 476     }
 477     if (fs==fe && fe==-1)
 478       return null;
 479     Vector ranges=new Vector();
 480     if (fs<=fe) {
 481       intv = fs;
 482       i=fs;
 483       // truncate initial interval
 484       iv = (int[]) fromShifts2.elementAt(intv++);
 485       iv = new int[] { iv[0], iv[1]};// clone
 486       if (i==fs)
 487         iv[0] = startpos;
 488       while (i!=fe) {
 489         ranges.addElement(iv); // add initial range
 490         iv = (int[]) fromShifts2.elementAt(intv++); // get next interval
 491         iv = new int[] { iv[0], iv[1]};// clone
 492         i++;
 493       }
 494       if (i==fe)
 495         iv[1] = endpos;
 496       ranges.addElement(iv); // add only - or final range
 497     } else {
 498       // walk from end of interval.
 499       i=fromShifts2.size()-1;
 500       while (i>fs) {
 501         i--;
 502       }
 503       iv = (int[]) fromShifts2.elementAt(i);
 504       iv = new int[] { iv[1], iv[0]};//  reverse and clone
 505       // truncate initial interval
 506       if (i==fs)
 507       {
 508         iv[0] = startpos;
 509       }
 510       while (i!=fe) {
 511         ranges.addElement(iv); // add (truncated) reversed interval
 512         iv = (int[]) fromShifts2.elementAt(--i);
 513         iv = new int[] { iv[1], iv[0] }; // reverse and clone
 514       }
 515       if (i==fe) {
 516         // interval is already reversed
 517         iv[1] = endpos;
 518       }
 519       ranges.addElement(iv); // add only - or final range
 520     }
 521     // create array of start end intervals.
 522     int[] range = null;
 523     if (ranges!=null && ranges.size()>0)
 524     {
 525       range = new int[ranges.size()*2];
 526       intv = 0;
 527       intvSize=ranges.size();
 528       i=0;
 529       while (intv<intvSize)
 530       {
 531         iv = (int[]) ranges.elementAt(intv);
 532         range[i++] = iv[0];
 533         range[i++] = iv[1];
 534         ranges.setElementAt(null, intv++); // remove
 535       }
 536     }
 537     return range;
 538   }
 539   /**
 540    * test routine. not incremental.
 541    * @param ml
 542    * @param fromS
 543    * @param fromE
 544    */
 545   public static void testMap(MapList ml, int fromS, int fromE)
 546   {
 547     for (int from = 1; from <= 25; from++)
 548     {
 549       int[] too=ml.shiftFrom(from);
 550       System.out.print("ShiftFrom("+from+")==");
 551       if (too==null)
 552       {
 553         System.out.print("NaN\n");
 554       }
 555       else
 556       {
 557         System.out.print(too[0]+" % "+too[1]+" ("+too[2]+")");
 558         System.out.print("\t+--+\t");
 559         int[] toofrom=ml.shiftTo(too[0]);
 560         if (toofrom != null)
 561         {
 562           if (toofrom[0]!=from)
 563           {
 564             System.err.println("Mapping not reflexive:" + from + " " + too[0] +
 565                 "->" + toofrom[0]);
 566           }
 567           System.out.println("ShiftTo(" + too[0] + ")==" + toofrom[0] + " % " +
 568               toofrom[1]+" ("+toofrom[2]+")");
 569         }
 570         else
 571         {
 572           System.out.println("ShiftTo(" + too[0] + ")==" +
 573           "NaN! - not Bijective Mapping!");
 574         }
 575       }
 576     }
 577     int mmap[][] = ml.makeFromMap();
 578     System.out.println("FromMap : (" + mmap[0][0] + " " + mmap[0][1] + " " +
 579         mmap[0][2] + " " + mmap[0][3] + " ");
 580     for (int i = 1; i <= mmap[1].length; i++)
 581     {
 582       if (mmap[1][i - 1] == -1)
 583       {
 584         System.out.print(i+"=XXX");
 585
 586       }
 587       else
 588       {
 589         System.out.print(i+"="+(mmap[0][2]+mmap[1][i-1]));
 590       }
 591       if (i % 20==0)
 592       {
 593         System.out.print("\n");
 594       }
 595       else
 596       {
 597         System.out.print(",");
 598       }
 599     }
 600     //test range function
 601     System.out.print("\nTest locateInFrom\n");
 602     {
 603       int f=mmap[0][2],t=mmap[0][3];
 604       while (f<t) {
 605         System.out.println("Range "+f+" to "+t);
 606         int rng[] = ml.locateInFrom(f,t);
 607         if (rng!=null)
 608         {
 609           for (int i=0; i<rng.length; i++) {
 610             System.out.print(rng[i]+((i%2==0) ? "," : ";"));
 611           }
 612         }
 613         else
 614         {
 615           System.out.println("No range!");
 616         }
 617         System.out.print("\nReversed\n");
 618         rng = ml.locateInFrom(t,f);
 619         if (rng!=null)
 620         {
 621           for (int i=0; i<rng.length; i++) {
 622             System.out.print(rng[i]+((i%2==0) ? "," : ";"));
 623           }
 624         }
 625         else
 626         {
 627           System.out.println("No range!");
 628         }
 629         System.out.print("\n");
 630         f++;t--;
 631       }
 632     }
 633     System.out.print("\n");
 634     mmap = ml.makeToMap();
 635     System.out.println("ToMap : (" + mmap[0][0] + " " + mmap[0][1] + " " +
 636         mmap[0][2] + " " + mmap[0][3] + " ");
 637     for (int i = 1; i <= mmap[1].length; i++)
 638     {
 639       if (mmap[1][i - 1] == -1)
 640       {
 641         System.out.print(i+"=XXX");
 642
 643       }
 644       else
 645       {
 646         System.out.print(i+"="+(mmap[0][2]+mmap[1][i-1]));
 647       }
 648       if (i % 20==0)
 649       {
 650         System.out.print("\n");
 651       }
 652       else
 653       {
 654         System.out.print(",");
 655       }
 656     }
 657     System.out.print("\n");
 658     //test range function
 659     System.out.print("\nTest locateInTo\n");
 660     {
 661       int f=mmap[0][2],t=mmap[0][3];
 662       while (f<t) {
 663         System.out.println("Range "+f+" to "+t);
 664         int rng[] = ml.locateInTo(f,t);
 665         if (rng!=null) {
 666           for (int i=0; i<rng.length; i++) {
 667             System.out.print(rng[i]+((i%2==0) ? "," : ";"));
 668           }
 669         }
 670         else
 671         {
 672           System.out.println("No range!");
 673         }
 674         System.out.print("\nReversed\n");
 675         rng = ml.locateInTo(t,f);
 676         if (rng!=null)
 677         {
 678           for (int i=0; i<rng.length; i++) {
 679             System.out.print(rng[i]+((i%2==0) ? "," : ";"));
 680           }
 681         }
 682         else
 683         {
 684           System.out.println("No range!");
 685         }
 686         f++; t--;
 687         System.out.print("\n");
 688       }
 689     }
 690
 691   }
 692
 693   public static void main(String argv[])
 694   {
 695     MapList ml = new MapList(new int[]
 696                                      {1, 5, 10, 15, 25, 20},
 697                                      new int[]
 698                                              {51, 1}, 1, 3);
 699     MapList ml1 = new MapList(new int[]
 700                                       {1, 3, 17, 4},
 701                                       new int[]
 702                                               {51, 1}, 1, 3);
 703     MapList ml2 = new MapList(new int[] { 1, 60 },
 704         new int[] { 1, 20 }, 3, 1);
 705     // test internal consistency
 706     int to[] = new int[51];
 707     MapList.testMap(ml, 1, 60);
 708     /*
 709       for (int from=1; from<=51; from++) {
 710           int[] too=ml.shiftTo(from);
 711           int[] toofrom=ml.shiftFrom(too[0]);
 712           System.out.println("ShiftFrom("+from+")=="+too[0]+" % "+too[1]+"\t+-+\tShiftTo("+too[0]+")=="+toofrom[0]+" % "+toofrom[1]);
 713       }*/
 714     System.out.print("Success?\n"); // if we get here - something must be working!
 715   }
 716 }