apparent bug in JpredFile parser where annotation was not being removed from alignmen...
[jalview.git] / 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); // needs to be inclusive of end of symbol position
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 series of from,to intervals from from first position of starting region to final position of ending region inclusive
450    */
451   private int[] getIntervals(Vector fromShifts2, int[] fromStart, int[] fromEnd, int fromRatio2)
452   {
453     int startpos,endpos;
454     startpos = fromStart[0]; // first position in fromStart 
455     endpos = fromEnd[0]+fromEnd[2]*(fromRatio2-1); // last position in fromEnd
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  * get the 'initial' position of mpos in To
541  * @param mpos position in from
542  * @return position of first word in to reference frame
543  */
544 public int getToPosition(int mpos)
545 {
546   int[] mp = shiftTo(mpos);
547   if (mp!=null)
548   {
549     return mp[0];
550   }
551   return mpos;
552 }
553 /**
554  * get range of positions in To frame for the mpos word in From
555  * @param mpos position in From
556  * @return null or int[] first position in To for mpos, last position in to for Mpos
557  */
558 public int[] getToWord(int mpos) {
559   int[] mp=shiftTo(mpos);
560   if (mp!=null) {
561       return new int[] {mp[0], mp[0]+mp[2]*(getFromRatio()-1)};
562   }
563   return null;
564 }
565 /**
566  * get From position in the associated
567  * reference frame for position pos in the
568  * associated sequence.
569  * @param pos
570  * @return
571  */
572 public int getMappedPosition(int pos) {
573   int[] mp = shiftFrom(pos);
574   if (mp!=null)
575   {
576     return mp[0];
577   }
578   return pos;
579 }
580 public int[] getMappedWord(int pos) {
581   int[] mp = shiftFrom(pos);
582   if (mp!=null)
583   {
584     return new int[] { mp[0], mp[0]+mp[2]*(getToRatio()-1)};
585   }
586   return null;
587 }
588
589   /**
590    * test routine. not incremental.
591    * @param ml
592    * @param fromS
593    * @param fromE
594    */
595   public static void testMap(MapList ml, int fromS, int fromE)
596   {
597     for (int from = 1; from <= 25; from++)
598     {
599       int[] too=ml.shiftFrom(from);
600       System.out.print("ShiftFrom("+from+")==");
601       if (too==null)
602       {
603         System.out.print("NaN\n");
604       }
605       else
606       {
607         System.out.print(too[0]+" % "+too[1]+" ("+too[2]+")");
608         System.out.print("\t+--+\t");
609         int[] toofrom=ml.shiftTo(too[0]);
610         if (toofrom != null)
611         {
612           if (toofrom[0]!=from)
613           {
614             System.err.println("Mapping not reflexive:" + from + " " + too[0] +
615                 "->" + toofrom[0]);
616           }
617           System.out.println("ShiftTo(" + too[0] + ")==" + toofrom[0] + " % " +
618               toofrom[1]+" ("+toofrom[2]+")");
619         }
620         else
621         {
622           System.out.println("ShiftTo(" + too[0] + ")==" +
623           "NaN! - not Bijective Mapping!");
624         }
625       }
626     }
627     int mmap[][] = ml.makeFromMap();
628     System.out.println("FromMap : (" + mmap[0][0] + " " + mmap[0][1] + " " +
629         mmap[0][2] + " " + mmap[0][3] + " ");
630     for (int i = 1; i <= mmap[1].length; i++)
631     {
632       if (mmap[1][i - 1] == -1)
633       {
634         System.out.print(i+"=XXX");
635
636       }
637       else
638       {
639         System.out.print(i+"="+(mmap[0][2]+mmap[1][i-1]));
640       }
641       if (i % 20==0)
642       {
643         System.out.print("\n");
644       }
645       else
646       {
647         System.out.print(",");
648       }
649     }
650     //test range function
651     System.out.print("\nTest locateInFrom\n");
652     {
653       int f=mmap[0][2],t=mmap[0][3];
654       while (f<=t) {
655         System.out.println("Range "+f+" to "+t);
656         int rng[] = ml.locateInFrom(f,t);
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         System.out.print("\nReversed\n");
668         rng = ml.locateInFrom(t,f);
669         if (rng!=null)
670         {
671           for (int i=0; i<rng.length; i++) {
672             System.out.print(rng[i]+((i%2==0) ? "," : ";"));
673           }
674         }
675         else
676         {
677           System.out.println("No range!");
678         }
679         System.out.print("\n");
680         f++;t--;
681       }
682     }
683     System.out.print("\n");
684     mmap = ml.makeToMap();
685     System.out.println("ToMap : (" + mmap[0][0] + " " + mmap[0][1] + " " +
686         mmap[0][2] + " " + mmap[0][3] + " ");
687     for (int i = 1; i <= mmap[1].length; i++)
688     {
689       if (mmap[1][i - 1] == -1)
690       {
691         System.out.print(i+"=XXX");
692
693       }
694       else
695       {
696         System.out.print(i+"="+(mmap[0][2]+mmap[1][i-1]));
697       }
698       if (i % 20==0)
699       {
700         System.out.print("\n");
701       }
702       else
703       {
704         System.out.print(",");
705       }
706     }
707     System.out.print("\n");
708     //test range function
709     System.out.print("\nTest locateInTo\n");
710     {
711       int f=mmap[0][2],t=mmap[0][3];
712       while (f<=t) {
713         System.out.println("Range "+f+" to "+t);
714         int rng[] = ml.locateInTo(f,t);
715         if (rng!=null) {
716           for (int i=0; i<rng.length; i++) {
717             System.out.print(rng[i]+((i%2==0) ? "," : ";"));
718           }
719         }
720         else
721         {
722           System.out.println("No range!");
723         }
724         System.out.print("\nReversed\n");
725         rng = ml.locateInTo(t,f);
726         if (rng!=null)
727         {
728           for (int i=0; i<rng.length; i++) {
729             System.out.print(rng[i]+((i%2==0) ? "," : ";"));
730           }
731         }
732         else
733         {
734           System.out.println("No range!");
735         }
736         f++; t--;
737         System.out.print("\n");
738       }
739     }
740
741   }
742
743   public static void main(String argv[])
744   {
745     MapList ml = new MapList(new int[]
746                                      {1, 5, 10, 15, 25, 20},
747                                      new int[]
748                                              {51, 1}, 1, 3);
749     MapList ml1 = new MapList(new int[]
750                                       {1, 3, 17, 4},
751                                       new int[]
752                                               {51, 1}, 1, 3);
753     MapList ml2 = new MapList(new int[] { 1, 60 },
754         new int[] { 1, 20 }, 3, 1);
755     // test internal consistency
756     int to[] = new int[51];
757     MapList.testMap(ml, 1, 60);
758     /*
759       for (int from=1; from<=51; from++) {
760           int[] too=ml.shiftTo(from);
761           int[] toofrom=ml.shiftFrom(too[0]);
762           System.out.println("ShiftFrom("+from+")=="+too[0]+" % "+too[1]+"\t+-+\tShiftTo("+too[0]+")=="+toofrom[0]+" % "+toofrom[1]);
763       }*/
764     System.out.print("Success?\n"); // if we get here - something must be working!
765   }
766 }