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