src/jalview/util/MapList.java

   1 /*\r
   2  * Jalview - A Sequence Alignment Editor and Viewer\r
   3  * Copyright (C) 2006 AM Waterhouse, J Procter, G Barton, M Clamp, S Searle\r
   4  *\r
   5  * This program is free software; you can redistribute it and/or\r
   6  * modify it under the terms of the GNU General Public License\r
   7  * as published by the Free Software Foundation; either version 2\r
   8  * of the License, or (at your option) any later version.\r
   9  *\r
  10  * This program is distributed in the hope that it will be useful,\r
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  13  * GNU General Public License for more details.\r
  14  *\r
  15  * You should have received a copy of the GNU General Public License\r
  16  * along with this program; if not, write to the Free Software\r
  17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA\r
  18  */\r
  19 package jalview.util;\r
  20 \r
  21 import java.util.*;\r
  22 \r
  23 /**\r
  24  * MapList\r
  25  * Simple way of bijectively mapping a non-contiguous linear range to another non-contiguous linear range\r
  26  * Use at your own risk!\r
  27  * TODO: efficient implementation of private posMap method\r
  28  * TODO: test/ensure that sense of from and to ratio start position is conserved (codon start position recovery)\r
  29  * TODO: optimize to use int[][] arrays rather than vectors.\r
  30  */\r
  31 public class MapList\r
  32 {\r
  33     public Vector fromShifts;\r
  34     public Vector toShifts;\r
  35     int fromRatio; // number of steps in fromShifts to one toRatio unit\r
  36     int toRatio; // number of steps in toShifts to one fromRatio\r
  37   public MapList(int from[], int to[], int fromRatio, int toRatio)\r
  38   {\r
  39     fromShifts = new Vector();\r
  40     for (int i=0;i<from.length; i+=2)\r
  41         fromShifts.add(new int[] { from[i], from[i+1]});\r
  42     toShifts = new Vector();\r
  43     for (int i=0;i<to.length; i+=2)\r
  44         toShifts.add(new int[] { to[i], to[i+1]});\r
  45     this.fromRatio=fromRatio;\r
  46     this.toRatio=toRatio;\r
  47   }\r
  48   /**\r
  49    * get all mapped positions from 'from' to 'to'\r
  50    * @return int[][] { int[] { fromStart, fromFinish, toStart, toFinish }, int [fromFinish-fromStart+2] { toStart..toFinish mappings}}\r
  51    */\r
  52   public int[][] makeFromMap() {\r
  53       return posMap(fromShifts, fromRatio, toShifts, toRatio);\r
  54   }\r
  55   /**\r
  56    * get all mapped positions from 'to' to 'from'\r
  57    * @return int[to position]=position mapped in from\r
  58    */\r
  59   public int[][] makeToMap() {\r
  60       return posMap(toShifts,toRatio, fromShifts, fromRatio);\r
  61   }\r
  62   /**\r
  63    * construct an int map for intervals in intVals\r
  64    * @param intVals\r
  65    * @return int[] { from, to pos in range }, int[range.to-range.from+1] returning mapped position\r
  66    */\r
  67   private int[][] posMap(Vector intVals, int ratio, Vector toIntVals, int toRatio) {\r
  68       Iterator iv = intVals.iterator();\r
  69       if (!iv.hasNext())\r
  70           return null;\r
  71       int[] intv=(int[]) iv.next();\r
  72       int from=intv[0],to=intv[1];\r
  73       if (from>to) {\r
  74           from = intv[1];\r
  75           to=intv[0];\r
  76       }\r
  77       while (iv.hasNext()) {\r
  78           intv = (int[]) iv.next();\r
  79           if (intv[0]<from)\r
  80               from=intv[0];\r
  81           if (intv[1]<from)\r
  82               from=intv[1];\r
  83           if (intv[0]>to)\r
  84               to=intv[0];\r
  85           if (intv[1]>to)\r
  86               to=intv[1];\r
  87       }\r
  88       int tF=0,tT=0;\r
  89       int mp[][] = new int[to-from+2][];\r
  90       for (int i=0;i<mp.length; i++) {\r
  91           int[] m = shift(i+from,intVals,ratio,toIntVals, toRatio);\r
  92           if (m!=null) {\r
  93               if (i==0) {\r
  94                   tF=tT=m[0];\r
  95               } else {\r
  96                   if (m[0]<tF) {\r
  97                       tF=m[0];\r
  98                   }\r
  99                   if (m[0]>tT) {\r
 100                       tT=m[0];\r
 101                   }\r
 102               }\r
 103           }\r
 104           mp[i] = m;\r
 105       }\r
 106       int[][] map=new int[][] { new int[]{from, to, tF, tT}, new int[to-from+2]};\r
 107 \r
 108       map[0][2] = tF;\r
 109       map[0][3] = tT;\r
 110       \r
 111       for (int i=0;i<mp.length; i++) {\r
 112           if (mp[i]!=null) {\r
 113               map[1][i] = mp[i][0]-tF;\r
 114           } else {\r
 115               map[1][i] = -1; // indicates an out of range mapping\r
 116           }\r
 117       }\r
 118       return map;\r
 119   }\r
 120   /**\r
 121    * addShift\r
 122    * @param pos start position for shift (in original reference frame)\r
 123    * @param shift length of shift\r
 124    *\r
 125   public void addShift(int pos, int shift)\r
 126   {\r
 127     int sidx = 0;\r
 128     int[] rshift=null;\r
 129     while (sidx<shifts.size() && (rshift=(int[]) shifts.elementAt(sidx))[0]<pos)\r
 130       sidx++;\r
 131     if (sidx==shifts.size())\r
 132       shifts.insertElementAt(new int[] { pos, shift}, sidx);\r
 133     else\r
 134       rshift[1]+=shift;\r
 135   }\r
 136 */\r
 137   /**\r
 138    * shift from pos to To(pos)\r
 139    *\r
 140    * @param pos int\r
 141    * @return int shifted position in To, frameshift in From\r
 142    */\r
 143   public int[] shiftFrom(int pos)\r
 144   {\r
 145       return shift(pos, fromShifts, fromRatio, toShifts, toRatio);\r
 146   }\r
 147 \r
 148   /**\r
 149    * inverse of shiftFrom - maps pos in To to a position in From\r
 150    * @param pos (in To)\r
 151    * @return shifted position in From, frameshift in To\r
 152    */\r
 153   public int[] shiftTo(int pos) {\r
 154       return shift(pos, toShifts, toRatio, fromShifts, fromRatio);\r
 155   }\r
 156   /**\r
 157    * \r
 158    * @param fromShifts\r
 159    * @param fromRatio\r
 160    * @param toShifts\r
 161    * @param toRatio\r
 162    * @return\r
 163    */\r
 164   private int[] shift(int pos, Vector fromShifts, int fromRatio, Vector toShifts, int toRatio) {\r
 165       int[] fromCount = countPos(fromShifts.iterator(), pos);\r
 166       if (fromCount==null)\r
 167           return null;\r
 168       int fromRemainder=(fromCount[0]-1) % fromRatio;\r
 169       int toCount = 1+(((fromCount[0]-1) / fromRatio) * toRatio);\r
 170       int[] toPos = countToPos(toShifts.iterator(), toCount);\r
 171       if (toPos==null)\r
 172           return null; // throw new Error("Bad Mapping!");\r
 173       //System.out.println(fromCount[0]+" "+fromCount[1]+" "+toCount);\r
 174       return new int[] {toPos[0], fromRemainder};\r
 175   }\r
 176   /**\r
 177    * count how many positions pos is along the series of intervals.\r
 178    * @param intVals\r
 179    * @param pos\r
 180    * @return number of positions or null if pos is not within intervals\r
 181    */\r
 182   private int[] countPos(Iterator intVals, int pos) {\r
 183       int count=0,intv[];\r
 184       while (intVals.hasNext()) {\r
 185           intv = (int[])intVals.next();\r
 186           if (intv[0] <= intv[1]) {\r
 187               if (pos>=intv[0] && pos<=intv[1]) {\r
 188                   return new int[] { count+pos-intv[0]+1, +1 };\r
 189               } else {\r
 190                   count+=intv[1]-intv[0]+1;\r
 191               }\r
 192           } else {\r
 193               if (pos>=intv[1] && pos<=intv[0]) {\r
 194                   return new int[] { count+intv[0]-pos+1, -1 };\r
 195               } else {\r
 196                   count+=intv[0]-intv[1]+1;\r
 197               }\r
 198           }\r
 199       }\r
 200       return null;\r
 201   }\r
 202   /**\r
 203    * count out pos positions into a series of intervals and return the position\r
 204    * @param intVals\r
 205    * @param pos\r
 206    * @return position pos in interval set\r
 207    */\r
 208   private int[] countToPos(Iterator intVals, int pos) {\r
 209       int count=0,diff=0,intv[]={0,0};\r
 210       while (intVals.hasNext()) {\r
 211           intv = (int[])intVals.next();\r
 212           diff = intv[1]-intv[0];\r
 213           if (diff>=0) {\r
 214               if (pos<=count+1+diff) {\r
 215                   return new int[] { pos-count-1+intv[0],+1 };\r
 216               } else {\r
 217                   count+=1+diff;\r
 218               }\r
 219           } else {\r
 220               if (pos<=count+1-diff) {\r
 221                   return new int[] { intv[0]-(pos-count-1),-1 };\r
 222               } else {\r
 223                   count+=1-diff;\r
 224               }\r
 225           }\r
 226       }\r
 227       return null;//(diff<0) ? (intv[1]-1) : (intv[0]+1);\r
 228   }\r
 229   public static void testMap(MapList ml, int fromS,int fromE) {\r
 230       for (int from=1; from<=25; from++) {\r
 231           int[] too=ml.shiftFrom(from);\r
 232           System.out.print("ShiftFrom("+from+")==");\r
 233           if (too==null)\r
 234               System.out.print("NaN\n");\r
 235           else {\r
 236               System.out.print(too[0]+" % "+too[1]);\r
 237               System.out.print("\t+--+\t");\r
 238               int[] toofrom=ml.shiftTo(too[0]);\r
 239               if (toofrom!=null)\r
 240                   System.out.println("ShiftTo("+too[0]+")=="+toofrom[0]+" % "+toofrom[1]);\r
 241               else\r
 242                   System.out.println("ShiftTo("+too[0]+")=="+"NaN! - not Bijective Mapping!");\r
 243           }\r
 244       }\r
 245       int mmap[][] = ml.makeFromMap();\r
 246       System.out.println("FromMap : ("+mmap[0][0]+" "+mmap[0][1]+" "+mmap[0][2]+" "+mmap[0][3]+" ");\r
 247       for (int i=1;i<=mmap[1].length; i++) {\r
 248           if (mmap[1][i-1]==-1) {\r
 249               System.out.print(i+"=XXX");\r
 250               \r
 251           } else {\r
 252               System.out.print(i+"="+(mmap[0][2]+mmap[1][i-1]));\r
 253           }\r
 254           if (i % 20==0)\r
 255               System.out.print("\n");\r
 256           else\r
 257               System.out.print(",");\r
 258       }\r
 259       System.out.print("\n");\r
 260   }\r
 261   public static void main(String argv[]) {\r
 262       MapList ml=new MapList(new int[] { 1,5,10,15,25,20}, \r
 263               new int[] { 51,1}, 1, 3);\r
 264       MapList ml1=new MapList(new int[] { 1,3,17,4}, \r
 265               new int[] { 51,1}, 1, 3);\r
 266       \r
 267       // test internal consistency\r
 268       int to[] = new int[51];\r
 269       MapList.testMap(ml, 1, 25);\r
 270       /*\r
 271       for (int from=1; from<=51; from++) {\r
 272           int[] too=ml.shiftTo(from);\r
 273           int[] toofrom=ml.shiftFrom(too[0]);\r
 274           System.out.println("ShiftFrom("+from+")=="+too[0]+" % "+too[1]+"\t+-+\tShiftTo("+too[0]+")=="+toofrom[0]+" % "+toofrom[1]);\r
 275       }*/\r
 276       System.out.print("Success?\n"); // if we get here - something must be working!\r
 277   }\r
 278 }\r