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   public Vector fromShifts;
  34   public Vector toShifts;
  35   int fromRatio; // number of steps in fromShifts to one toRatio unit
  36   int toRatio; // number of steps in toShifts to one fromRatio
  37   public MapList(int from[], int to[], int fromRatio, int toRatio)
  38   {
  39     fromShifts = new Vector();
  40     for (int i = 0; i < from.length; i += 2)
  41     {
  42       fromShifts.add(new int[]
  43                      {from[i], from[i + 1]});
  44     }
  45     toShifts = new Vector();
  46     for (int i = 0; i < to.length; i += 2)
  47     {
  48       toShifts.add(new int[]
  49                    {to[i], to[i + 1]});
  50     }
  51     this.fromRatio = fromRatio;
  52     this.toRatio = toRatio;
  53   }
  54
  55   /**
  56    * get all mapped positions from 'from' to 'to'
  57    * @return int[][] { int[] { fromStart, fromFinish, toStart, toFinish }, int [fromFinish-fromStart+2] { toStart..toFinish mappings}}
  58    */
  59   public int[][] makeFromMap()
  60   {
  61     return posMap(fromShifts, fromRatio, toShifts, toRatio);
  62   }
  63
  64   /**
  65    * get all mapped positions from 'to' to 'from'
  66    * @return int[to position]=position mapped in from
  67    */
  68   public int[][] makeToMap()
  69   {
  70     return posMap(toShifts, toRatio, fromShifts, fromRatio);
  71   }
  72
  73   /**
  74    * construct an int map for intervals in intVals
  75    * @param intVals
  76    * @return int[] { from, to pos in range }, int[range.to-range.from+1] returning mapped position
  77    */
  78   private int[][] posMap(Vector intVals, int ratio, Vector toIntVals,
  79                          int toRatio)
  80   {
  81     Iterator iv = intVals.iterator();
  82     if (!iv.hasNext())
  83     {
  84       return null;
  85     }
  86     int[] intv = (int[]) iv.next();
  87     int from = intv[0], to = intv[1];
  88     if (from > to)
  89     {
  90       from = intv[1];
  91       to = intv[0];
  92     }
  93     while (iv.hasNext())
  94     {
  95       intv = (int[]) iv.next();
  96       if (intv[0] < from)
  97       {
  98         from = intv[0];
  99       }
 100       if (intv[1] < from)
 101       {
 102         from = intv[1];
 103       }
 104       if (intv[0] > to)
 105       {
 106         to = intv[0];
 107       }
 108       if (intv[1] > to)
 109       {
 110         to = intv[1];
 111       }
 112     }
 113     int tF = 0, tT = 0;
 114     int mp[][] = new int[to - from + 2][];
 115     for (int i = 0; i < mp.length; i++)
 116     {
 117       int[] m = shift(i + from, intVals, ratio, toIntVals, toRatio);
 118       if (m != null)
 119       {
 120         if (i == 0)
 121         {
 122           tF = tT = m[0];
 123         }
 124         else
 125         {
 126           if (m[0] < tF)
 127           {
 128             tF = m[0];
 129           }
 130           if (m[0] > tT)
 131           {
 132             tT = m[0];
 133           }
 134         }
 135       }
 136       mp[i] = m;
 137     }
 138     int[][] map = new int[][]
 139         {
 140         new int[]
 141         {
 142         from, to, tF, tT}, new int[to - from + 2]};
 143
 144     map[0][2] = tF;
 145     map[0][3] = tT;
 146
 147     for (int i = 0; i < mp.length; i++)
 148     {
 149       if (mp[i] != null)
 150       {
 151         map[1][i] = mp[i][0] - tF;
 152       }
 153       else
 154       {
 155         map[1][i] = -1; // indicates an out of range mapping
 156       }
 157     }
 158     return map;
 159   }
 160
 161   /**
 162    * addShift
 163    * @param pos start position for shift (in original reference frame)
 164    * @param shift length of shift
 165    *
 166      public void addShift(int pos, int shift)
 167      {
 168     int sidx = 0;
 169     int[] rshift=null;
 170    while (sidx<shifts.size() && (rshift=(int[]) shifts.elementAt(sidx))[0]<pos)
 171       sidx++;
 172     if (sidx==shifts.size())
 173       shifts.insertElementAt(new int[] { pos, shift}, sidx);
 174     else
 175       rshift[1]+=shift;
 176      }
 177    */
 178   /**
 179    * shift from pos to To(pos)
 180    *
 181    * @param pos int
 182    * @return int shifted position in To, frameshift in From
 183    */
 184   public int[] shiftFrom(int pos)
 185   {
 186     return shift(pos, fromShifts, fromRatio, toShifts, toRatio);
 187   }
 188
 189   /**
 190    * inverse of shiftFrom - maps pos in To to a position in From
 191    * @param pos (in To)
 192    * @return shifted position in From, frameshift in To
 193    */
 194   public int[] shiftTo(int pos)
 195   {
 196     return shift(pos, toShifts, toRatio, fromShifts, fromRatio);
 197   }
 198
 199   /**
 200    *
 201    * @param fromShifts
 202    * @param fromRatio
 203    * @param toShifts
 204    * @param toRatio
 205    * @return
 206    */
 207   private int[] shift(int pos, Vector fromShifts, int fromRatio,
 208                       Vector toShifts, int toRatio)
 209   {
 210     int[] fromCount = countPos(fromShifts.iterator(), pos);
 211     if (fromCount == null)
 212     {
 213       return null;
 214     }
 215     int fromRemainder = (fromCount[0] - 1) % fromRatio;
 216     int toCount = 1 + ( ( (fromCount[0] - 1) / fromRatio) * toRatio);
 217     int[] toPos = countToPos(toShifts.iterator(), toCount);
 218     if (toPos == null)
 219     {
 220       return null; // throw new Error("Bad Mapping!");
 221     }
 222     //System.out.println(fromCount[0]+" "+fromCount[1]+" "+toCount);
 223     return new int[]
 224         {
 225         toPos[0], fromRemainder};
 226   }
 227
 228   /**
 229    * count how many positions pos is along the series of intervals.
 230    * @param intVals
 231    * @param pos
 232    * @return number of positions or null if pos is not within intervals
 233    */
 234   private int[] countPos(Iterator intVals, int pos)
 235   {
 236     int count = 0, intv[];
 237     while (intVals.hasNext())
 238     {
 239       intv = (int[]) intVals.next();
 240       if (intv[0] <= intv[1])
 241       {
 242         if (pos >= intv[0] && pos <= intv[1])
 243         {
 244           return new int[]
 245               {
 246               count + pos - intv[0] + 1, +1};
 247         }
 248         else
 249         {
 250           count += intv[1] - intv[0] + 1;
 251         }
 252       }
 253       else
 254       {
 255         if (pos >= intv[1] && pos <= intv[0])
 256         {
 257           return new int[]
 258               {
 259               count + intv[0] - pos + 1, -1};
 260         }
 261         else
 262         {
 263           count += intv[0] - intv[1] + 1;
 264         }
 265       }
 266     }
 267     return null;
 268   }
 269
 270   /**
 271    * count out pos positions into a series of intervals and return the position
 272    * @param intVals
 273    * @param pos
 274    * @return position pos in interval set
 275    */
 276   private int[] countToPos(Iterator intVals, int pos)
 277   {
 278     int count = 0, diff = 0, intv[] =
 279         {
 280         0, 0};
 281     while (intVals.hasNext())
 282     {
 283       intv = (int[]) intVals.next();
 284       diff = intv[1] - intv[0];
 285       if (diff >= 0)
 286       {
 287         if (pos <= count + 1 + diff)
 288         {
 289           return new int[]
 290               {
 291               pos - count - 1 + intv[0], +1};
 292         }
 293         else
 294         {
 295           count += 1 + diff;
 296         }
 297       }
 298       else
 299       {
 300         if (pos <= count + 1 - diff)
 301         {
 302           return new int[]
 303               {
 304               intv[0] - (pos - count - 1), -1};
 305         }
 306         else
 307         {
 308           count += 1 - diff;
 309         }
 310       }
 311     }
 312     return null; //(diff<0) ? (intv[1]-1) : (intv[0]+1);
 313   }
 314
 315   public static void testMap(MapList ml, int fromS, int fromE)
 316   {
 317     for (int from = 1; from <= 25; from++)
 318     {
 319       int[] too = ml.shiftFrom(from);
 320       System.out.print("ShiftFrom(" + from + ")==");
 321       if (too == null)
 322       {
 323         System.out.print("NaN\n");
 324       }
 325       else
 326       {
 327         System.out.print(too[0] + " % " + too[1]);
 328         System.out.print("\t+--+\t");
 329         int[] toofrom = ml.shiftTo(too[0]);
 330         if (toofrom != null)
 331         {
 332           if (toofrom[0] != from)
 333           {
 334             System.err.println("Mapping not reflexive:" + from + " " + too[0] +
 335                                "->" + toofrom[0]);
 336           }
 337           System.out.println("ShiftTo(" + too[0] + ")==" + toofrom[0] + " % " +
 338                              toofrom[1]);
 339         }
 340         else
 341         {
 342           System.out.println("ShiftTo(" + too[0] + ")==" +
 343                              "NaN! - not Bijective Mapping!");
 344         }
 345       }
 346     }
 347     int mmap[][] = ml.makeFromMap();
 348     System.out.println("FromMap : (" + mmap[0][0] + " " + mmap[0][1] + " " +
 349                        mmap[0][2] + " " + mmap[0][3] + " ");
 350     for (int i = 1; i <= mmap[1].length; i++)
 351     {
 352       if (mmap[1][i - 1] == -1)
 353       {
 354         System.out.print(i + "=XXX");
 355
 356       }
 357       else
 358       {
 359         System.out.print(i + "=" + (mmap[0][2] + mmap[1][i - 1]));
 360       }
 361       if (i % 20 == 0)
 362       {
 363         System.out.print("\n");
 364       }
 365       else
 366       {
 367         System.out.print(",");
 368       }
 369     }
 370     System.out.print("\n");
 371   }
 372
 373   public static void main(String argv[])
 374   {
 375     MapList ml = new MapList(new int[]
 376                              {1, 5, 10, 15, 25, 20},
 377                              new int[]
 378                              {51, 1}, 1, 3);
 379     MapList ml1 = new MapList(new int[]
 380                               {1, 3, 17, 4},
 381                               new int[]
 382                               {51, 1}, 1, 3);
 383
 384     // test internal consistency
 385     int to[] = new int[51];
 386     MapList.testMap(ml, 1, 25);
 387     /*
 388            for (int from=1; from<=51; from++) {
 389         int[] too=ml.shiftTo(from);
 390         int[] toofrom=ml.shiftFrom(too[0]);
 391         System.out.println("ShiftFrom("+from+")=="+too[0]+" % "+too[1]+"\t+-+\tShiftTo("+too[0]+")=="+toofrom[0]+" % "+toofrom[1]);
 392            }*/
 393     System.out.print("Success?\n"); // if we get here - something must be working!
 394   }
 395 }