Clover icon

jalviewX

  1. Project Clover database Wed Oct 31 2018 15:13:58 GMT
  2. Package jalview.util

File MapList.java

 

Coverage histogram

../../img/srcFileCovDistChart9.png
12% of files have more coverage

Code metrics

168
364
41
1
1,239
771
163
0.45
8.88
41
3.98

Classes

Class Line # Actions
MapList 38 364 163 76
0.8673647686.7%
 

Contributing tests

This file is covered by 147 tests. .

Source view

1    /*
2    * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
3    * Copyright (C) $$Year-Rel$$ The Jalview Authors
4    *
5    * This file is part of Jalview.
6    *
7    * Jalview is free software: you can redistribute it and/or
8    * modify it under the terms of the GNU General Public License
9    * as published by the Free Software Foundation, either version 3
10    * of the License, or (at your option) any later version.
11    *
12    * Jalview is distributed in the hope that it will be useful, but
13    * WITHOUT ANY WARRANTY; without even the implied warranty
14    * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
15    * PURPOSE. See the GNU General Public License for more details.
16    *
17    * You should have received a copy of the GNU General Public License
18    * along with Jalview. If not, see <http://www.gnu.org/licenses/>.
19    * The Jalview Authors are detailed in the 'AUTHORS' file.
20    */
21    package jalview.util;
22   
23    import java.util.ArrayList;
24    import java.util.Arrays;
25    import java.util.List;
26   
27    /**
28    * A simple way of bijectively mapping a non-contiguous linear range to another
29    * non-contiguous linear range.
30    *
31    * Use at your own risk!
32    *
33    * TODO: efficient implementation of private posMap method
34    *
35    * TODO: test/ensure that sense of from and to ratio start position is conserved
36    * (codon start position recovery)
37    */
 
38    public class MapList
39    {
40   
41    /*
42    * Subregions (base 1) described as { [start1, end1], [start2, end2], ...}
43    */
44    private List<int[]> fromShifts;
45   
46    /*
47    * Same format as fromShifts, for the 'mapped to' sequence
48    */
49    private List<int[]> toShifts;
50   
51    /*
52    * number of steps in fromShifts to one toRatio unit
53    */
54    private int fromRatio;
55   
56    /*
57    * number of steps in toShifts to one fromRatio
58    */
59    private int toRatio;
60   
61    /*
62    * lowest and highest value in the from Map
63    */
64    private int fromLowest;
65   
66    private int fromHighest;
67   
68    /*
69    * lowest and highest value in the to Map
70    */
71    private int toLowest;
72   
73    private int toHighest;
74   
75    /**
76    * Constructor
77    */
 
78  742 toggle public MapList()
79    {
80  742 fromShifts = new ArrayList<>();
81  742 toShifts = new ArrayList<>();
82    }
83   
84    /**
85    * Two MapList objects are equal if they are the same object, or they both
86    * have populated shift ranges and all values are the same.
87    */
 
88  52 toggle @Override
89    public boolean equals(Object o)
90    {
91  52 if (o == null || !(o instanceof MapList))
92    {
93  2 return false;
94    }
95   
96  50 MapList obj = (MapList) o;
97  50 if (obj == this)
98    {
99  5 return true;
100    }
101  45 if (obj.fromRatio != fromRatio || obj.toRatio != toRatio
102    || obj.fromShifts == null || obj.toShifts == null)
103    {
104  3 return false;
105    }
106  42 return Arrays.deepEquals(fromShifts.toArray(), obj.fromShifts.toArray())
107    && Arrays.deepEquals(toShifts.toArray(),
108    obj.toShifts.toArray());
109    }
110   
111    /**
112    * Returns a hashcode made from the fromRatio, toRatio, and from/to ranges
113    */
 
114  6 toggle @Override
115    public int hashCode()
116    {
117  6 int hashCode = 31 * fromRatio;
118  6 hashCode = 31 * hashCode + toRatio;
119  6 for (int[] shift : fromShifts)
120    {
121  26 hashCode = 31 * hashCode + shift[0];
122  26 hashCode = 31 * hashCode + shift[1];
123    }
124  6 for (int[] shift : toShifts)
125    {
126  6 hashCode = 31 * hashCode + shift[0];
127  6 hashCode = 31 * hashCode + shift[1];
128    }
129   
130  6 return hashCode;
131    }
132   
133    /**
134    * Returns the 'from' ranges as {[start1, end1], [start2, end2], ...}
135    *
136    * @return
137    */
 
138  248 toggle public List<int[]> getFromRanges()
139    {
140  248 return fromShifts;
141    }
142   
143    /**
144    * Returns the 'to' ranges as {[start1, end1], [start2, end2], ...}
145    *
146    * @return
147    */
 
148  274 toggle public List<int[]> getToRanges()
149    {
150  274 return toShifts;
151    }
152   
153    /**
154    * Flattens a list of [start, end] into a single [start1, end1, start2,
155    * end2,...] array.
156    *
157    * @param shifts
158    * @return
159    */
 
160  1 toggle protected static int[] getRanges(List<int[]> shifts)
161    {
162  1 int[] rnges = new int[2 * shifts.size()];
163  1 int i = 0;
164  1 for (int[] r : shifts)
165    {
166  2 rnges[i++] = r[0];
167  2 rnges[i++] = r[1];
168    }
169  1 return rnges;
170    }
171   
172    /**
173    *
174    * @return length of mapped phrase in from
175    */
 
176  396 toggle public int getFromRatio()
177    {
178  396 return fromRatio;
179    }
180   
181    /**
182    *
183    * @return length of mapped phrase in to
184    */
 
185  249 toggle public int getToRatio()
186    {
187  249 return toRatio;
188    }
189   
 
190  73 toggle public int getFromLowest()
191    {
192  73 return fromLowest;
193    }
194   
 
195  68 toggle public int getFromHighest()
196    {
197  68 return fromHighest;
198    }
199   
 
200  29 toggle public int getToLowest()
201    {
202  29 return toLowest;
203    }
204   
 
205  30 toggle public int getToHighest()
206    {
207  30 return toHighest;
208    }
209   
210    /**
211    * Constructor given from and to ranges as [start1, end1, start2, end2,...].
212    * If any end is equal to the next start, the ranges will be merged. There is
213    * no validation check that the ranges do not overlap each other.
214    *
215    * @param from
216    * contiguous regions as [start1, end1, start2, end2, ...]
217    * @param to
218    * same format as 'from'
219    * @param fromRatio
220    * phrase length in 'from' (e.g. 3 for dna)
221    * @param toRatio
222    * phrase length in 'to' (e.g. 1 for protein)
223    */
 
224  653 toggle public MapList(int from[], int to[], int fromRatio, int toRatio)
225    {
226  653 this();
227  653 this.fromRatio = fromRatio;
228  653 this.toRatio = toRatio;
229  653 fromLowest = Integer.MAX_VALUE;
230  653 fromHighest = Integer.MIN_VALUE;
231  653 int added = 0;
232   
233  1538 for (int i = 0; i < from.length; i += 2)
234    {
235    /*
236    * note lowest and highest values - bearing in mind the
237    * direction may be reversed
238    */
239  886 fromLowest = Math.min(fromLowest, Math.min(from[i], from[i + 1]));
240  886 fromHighest = Math.max(fromHighest, Math.max(from[i], from[i + 1]));
241  886 if (added > 0 && from[i] == fromShifts.get(added - 1)[1])
242    {
243    /*
244    * this range starts where the last ended - just extend it
245    */
246  1 fromShifts.get(added - 1)[1] = from[i + 1];
247    }
248    else
249    {
250  885 fromShifts.add(new int[] { from[i], from[i + 1] });
251  885 added++;
252    }
253    }
254   
255  652 toLowest = Integer.MAX_VALUE;
256  652 toHighest = Integer.MIN_VALUE;
257  652 added = 0;
258  1413 for (int i = 0; i < to.length; i += 2)
259    {
260  762 toLowest = Math.min(toLowest, Math.min(to[i], to[i + 1]));
261  762 toHighest = Math.max(toHighest, Math.max(to[i], to[i + 1]));
262  762 if (added > 0 && to[i] == toShifts.get(added - 1)[1])
263    {
264  1 toShifts.get(added - 1)[1] = to[i + 1];
265    }
266    else
267    {
268  761 toShifts.add(new int[] { to[i], to[i + 1] });
269  761 added++;
270    }
271    }
272    }
273   
274    /**
275    * Copy constructor. Creates an identical mapping.
276    *
277    * @param map
278    */
 
279  17 toggle public MapList(MapList map)
280    {
281  17 this();
282    // TODO not used - remove?
283  17 this.fromLowest = map.fromLowest;
284  17 this.fromHighest = map.fromHighest;
285  17 this.toLowest = map.toLowest;
286  17 this.toHighest = map.toHighest;
287   
288  17 this.fromRatio = map.fromRatio;
289  17 this.toRatio = map.toRatio;
290  17 if (map.fromShifts != null)
291    {
292  17 for (int[] r : map.fromShifts)
293    {
294  29 fromShifts.add(new int[] { r[0], r[1] });
295    }
296    }
297  17 if (map.toShifts != null)
298    {
299  17 for (int[] r : map.toShifts)
300    {
301  22 toShifts.add(new int[] { r[0], r[1] });
302    }
303    }
304    }
305   
306    /**
307    * Constructor given ranges as lists of [start, end] positions. There is no
308    * validation check that the ranges do not overlap each other.
309    *
310    * @param fromRange
311    * @param toRange
312    * @param fromRatio
313    * @param toRatio
314    */
 
315  72 toggle public MapList(List<int[]> fromRange, List<int[]> toRange, int fromRatio,
316    int toRatio)
317    {
318  72 this();
319  72 fromRange = coalesceRanges(fromRange);
320  72 toRange = coalesceRanges(toRange);
321  72 this.fromShifts = fromRange;
322  72 this.toShifts = toRange;
323  72 this.fromRatio = fromRatio;
324  72 this.toRatio = toRatio;
325   
326  72 fromLowest = Integer.MAX_VALUE;
327  72 fromHighest = Integer.MIN_VALUE;
328  72 for (int[] range : fromRange)
329    {
330  97 if (range.length != 2)
331    {
332    // throw new IllegalArgumentException(range);
333  0 System.err.println(
334    "Invalid format for fromRange " + Arrays.toString(range)
335    + " may cause errors");
336    }
337  97 fromLowest = Math.min(fromLowest, Math.min(range[0], range[1]));
338  97 fromHighest = Math.max(fromHighest, Math.max(range[0], range[1]));
339    }
340   
341  72 toLowest = Integer.MAX_VALUE;
342  72 toHighest = Integer.MIN_VALUE;
343  72 for (int[] range : toRange)
344    {
345  101 if (range.length != 2)
346    {
347    // throw new IllegalArgumentException(range);
348  0 System.err.println("Invalid format for toRange "
349    + Arrays.toString(range)
350    + " may cause errors");
351    }
352  101 toLowest = Math.min(toLowest, Math.min(range[0], range[1]));
353  101 toHighest = Math.max(toHighest, Math.max(range[0], range[1]));
354    }
355    }
356   
357    /**
358    * Consolidates a list of ranges so that any contiguous ranges are merged.
359    * This assumes the ranges are already in start order (does not sort them).
360    *
361    * @param ranges
362    * @return the same list (if unchanged), else a new merged list, leaving the
363    * input list unchanged
364    */
 
365  157 toggle public static List<int[]> coalesceRanges(final List<int[]> ranges)
366    {
367  157 if (ranges == null || ranges.size() < 2)
368    {
369  107 return ranges;
370    }
371   
372  50 boolean changed = false;
373  50 List<int[]> merged = new ArrayList<>();
374  50 int[] lastRange = ranges.get(0);
375  50 int lastDirection = lastRange[1] >= lastRange[0] ? 1 : -1;
376  50 lastRange = new int[] { lastRange[0], lastRange[1] };
377  50 merged.add(lastRange);
378  50 boolean first = true;
379   
380  50 for (final int[] range : ranges)
381    {
382  128 if (first)
383    {
384  50 first = false;
385  50 continue;
386    }
387  78 if (range[0] == lastRange[0] && range[1] == lastRange[1])
388    {
389    // drop duplicate range
390  1 changed = true;
391  1 continue;
392    }
393   
394    /*
395    * drop this range if it lies within the last range
396    */
397  77 if ((lastDirection == 1 && range[0] >= lastRange[0]
398    && range[0] <= lastRange[1] && range[1] >= lastRange[0]
399    && range[1] <= lastRange[1])
400    || (lastDirection == -1 && range[0] <= lastRange[0]
401    && range[0] >= lastRange[1]
402    && range[1] <= lastRange[0]
403    && range[1] >= lastRange[1]))
404    {
405  5 changed = true;
406  5 continue;
407    }
408   
409  72 int direction = range[1] >= range[0] ? 1 : -1;
410   
411    /*
412    * if next range is in the same direction as last and contiguous,
413    * just update the end position of the last range
414    */
415  72 boolean sameDirection = range[1] == range[0]
416    || direction == lastDirection;
417  72 boolean extending = range[0] == lastRange[1] + lastDirection;
418  72 boolean overlapping = (lastDirection == 1 && range[0] >= lastRange[0]
419    && range[0] <= lastRange[1])
420    || (lastDirection == -1 && range[0] <= lastRange[0]
421    && range[0] >= lastRange[1]);
422  72 if (sameDirection && (overlapping || extending))
423    {
424  14 lastRange[1] = range[1];
425  14 changed = true;
426    }
427    else
428    {
429  58 lastRange = new int[] { range[0], range[1] };
430  58 merged.add(lastRange);
431    // careful: merging [5, 5] after [7, 6] should keep negative direction
432  58 lastDirection = (range[1] == range[0]) ? lastDirection : direction;
433    }
434    }
435   
436  50 return changed ? merged : ranges;
437    }
438   
439    /**
440    * get all mapped positions from 'from' to 'to'
441    *
442    * @return int[][] { int[] { fromStart, fromFinish, toStart, toFinish }, int
443    * [fromFinish-fromStart+2] { toStart..toFinish mappings}}
444    */
 
445  2 toggle protected int[][] makeFromMap()
446    {
447    // TODO not used - remove??
448  2 return posMap(fromShifts, fromRatio, toShifts, toRatio);
449    }
450   
451    /**
452    * get all mapped positions from 'to' to 'from'
453    *
454    * @return int[to position]=position mapped in from
455    */
 
456  2 toggle protected int[][] makeToMap()
457    {
458    // TODO not used - remove??
459  2 return posMap(toShifts, toRatio, fromShifts, fromRatio);
460    }
461   
462    /**
463    * construct an int map for intervals in intVals
464    *
465    * @param shiftTo
466    * @return int[] { from, to pos in range }, int[range.to-range.from+1]
467    * returning mapped position
468    */
 
469  4 toggle private int[][] posMap(List<int[]> shiftTo, int ratio,
470    List<int[]> shiftFrom, int toRatio)
471    {
472    // TODO not used - remove??
473  4 int iv = 0, ivSize = shiftTo.size();
474  4 if (iv >= ivSize)
475    {
476  0 return null;
477    }
478  4 int[] intv = shiftTo.get(iv++);
479  4 int from = intv[0], to = intv[1];
480  4 if (from > to)
481    {
482  1 from = intv[1];
483  1 to = intv[0];
484    }
485  8 while (iv < ivSize)
486    {
487  4 intv = shiftTo.get(iv++);
488  4 if (intv[0] < from)
489    {
490  0 from = intv[0];
491    }
492  4 if (intv[1] < from)
493    {
494  0 from = intv[1];
495    }
496  4 if (intv[0] > to)
497    {
498  4 to = intv[0];
499    }
500  4 if (intv[1] > to)
501    {
502  3 to = intv[1];
503    }
504    }
505  4 int tF = 0, tT = 0;
506  4 int mp[][] = new int[to - from + 2][];
507  102 for (int i = 0; i < mp.length; i++)
508    {
509  98 int[] m = shift(i + from, shiftTo, ratio, shiftFrom, toRatio);
510  98 if (m != null)
511    {
512  80 if (i == 0)
513    {
514  4 tF = tT = m[0];
515    }
516    else
517    {
518  76 if (m[0] < tF)
519    {
520  22 tF = m[0];
521    }
522  76 if (m[0] > tT)
523    {
524  9 tT = m[0];
525    }
526    }
527    }
528  98 mp[i] = m;
529    }
530  4 int[][] map = new int[][] { new int[] { from, to, tF, tT },
531    new int[to - from + 2] };
532   
533  4 map[0][2] = tF;
534  4 map[0][3] = tT;
535   
536  102 for (int i = 0; i < mp.length; i++)
537    {
538  98 if (mp[i] != null)
539    {
540  80 map[1][i] = mp[i][0] - tF;
541    }
542    else
543    {
544  18 map[1][i] = -1; // indicates an out of range mapping
545    }
546    }
547  4 return map;
548    }
549   
550    /**
551    * addShift
552    *
553    * @param pos
554    * start position for shift (in original reference frame)
555    * @param shift
556    * length of shift
557    *
558    * public void addShift(int pos, int shift) { int sidx = 0; int[]
559    * rshift=null; while (sidx<shifts.size() && (rshift=(int[])
560    * shifts.elementAt(sidx))[0]<pos) sidx++; if (sidx==shifts.size())
561    * shifts.insertElementAt(new int[] { pos, shift}, sidx); else
562    * rshift[1]+=shift; }
563    */
564   
565    /**
566    * shift from pos to To(pos)
567    *
568    * @param pos
569    * int
570    * @return int shifted position in To, frameshift in From, direction of mapped
571    * symbol in To
572    */
 
573  677 toggle public int[] shiftFrom(int pos)
574    {
575  677 return shift(pos, fromShifts, fromRatio, toShifts, toRatio);
576    }
577   
578    /**
579    * inverse of shiftFrom - maps pos in To to a position in From
580    *
581    * @param pos
582    * (in To)
583    * @return shifted position in From, frameshift in To, direction of mapped
584    * symbol in From
585    */
 
586  8453 toggle public int[] shiftTo(int pos)
587    {
588  8453 return shift(pos, toShifts, toRatio, fromShifts, fromRatio);
589    }
590   
591    /**
592    *
593    * @param shiftTo
594    * @param fromRatio
595    * @param shiftFrom
596    * @param toRatio
597    * @return
598    */
 
599  9228 toggle protected static int[] shift(int pos, List<int[]> shiftTo, int fromRatio,
600    List<int[]> shiftFrom, int toRatio)
601    {
602    // TODO: javadoc; tests
603  9228 int[] fromCount = countPos(shiftTo, pos);
604  9228 if (fromCount == null)
605    {
606  374 return null;
607    }
608  8854 int fromRemainder = (fromCount[0] - 1) % fromRatio;
609  8854 int toCount = 1 + (((fromCount[0] - 1) / fromRatio) * toRatio);
610  8854 int[] toPos = countToPos(shiftFrom, toCount);
611  8854 if (toPos == null)
612    {
613  1 return null; // throw new Error("Bad Mapping!");
614    }
615    // System.out.println(fromCount[0]+" "+fromCount[1]+" "+toCount);
616  8853 return new int[] { toPos[0], fromRemainder, toPos[1] };
617    }
618   
619    /**
620    * count how many positions pos is along the series of intervals.
621    *
622    * @param shiftTo
623    * @param pos
624    * @return number of positions or null if pos is not within intervals
625    */
 
626  9228 toggle protected static int[] countPos(List<int[]> shiftTo, int pos)
627    {
628  9228 int count = 0, intv[], iv = 0, ivSize = shiftTo.size();
629  10152 while (iv < ivSize)
630    {
631  9778 intv = shiftTo.get(iv++);
632  9778 if (intv[0] <= intv[1])
633    {
634  9348 if (pos >= intv[0] && pos <= intv[1])
635    {
636  8624 return new int[] { count + pos - intv[0] + 1, +1 };
637    }
638    else
639    {
640  724 count += intv[1] - intv[0] + 1;
641    }
642    }
643    else
644    {
645  430 if (pos >= intv[1] && pos <= intv[0])
646    {
647  230 return new int[] { count + intv[0] - pos + 1, -1 };
648    }
649    else
650    {
651  200 count += intv[0] - intv[1] + 1;
652    }
653    }
654    }
655  374 return null;
656    }
657   
658    /**
659    * count out pos positions into a series of intervals and return the position
660    *
661    * @param shiftFrom
662    * @param pos
663    * @return position pos in interval set
664    */
 
665  8854 toggle protected static int[] countToPos(List<int[]> shiftFrom, int pos)
666    {
667  8854 int count = 0, diff = 0, iv = 0, ivSize = shiftFrom.size();
668  8854 int[] intv = { 0, 0 };
669  9246 while (iv < ivSize)
670    {
671  9245 intv = shiftFrom.get(iv++);
672  9245 diff = intv[1] - intv[0];
673  9245 if (diff >= 0)
674    {
675  9104 if (pos <= count + 1 + diff)
676    {
677  8713 return new int[] { pos - count - 1 + intv[0], +1 };
678    }
679    else
680    {
681  391 count += 1 + diff;
682    }
683    }
684    else
685    {
686  141 if (pos <= count + 1 - diff)
687    {
688  140 return new int[] { intv[0] - (pos - count - 1), -1 };
689    }
690    else
691    {
692  1 count += 1 - diff;
693    }
694    }
695    }
696  1 return null;// (diff<0) ? (intv[1]-1) : (intv[0]+1);
697    }
698   
699    /**
700    * find series of intervals mapping from start-end in the From map.
701    *
702    * @param start
703    * position mapped 'to'
704    * @param end
705    * position mapped 'to'
706    * @return series of [start, end] ranges in sequence mapped 'from'
707    */
 
708  1821 toggle public int[] locateInFrom(int start, int end)
709    {
710    // inefficient implementation
711  1821 int fromStart[] = shiftTo(start);
712    // needs to be inclusive of end of symbol position
713  1821 int fromEnd[] = shiftTo(end);
714   
715  1821 return getIntervals(fromShifts, fromStart, fromEnd, fromRatio);
716    }
717   
718    /**
719    * find series of intervals mapping from start-end in the to map.
720    *
721    * @param start
722    * position mapped 'from'
723    * @param end
724    * position mapped 'from'
725    * @return series of [start, end] ranges in sequence mapped 'to'
726    */
 
727  309 toggle public int[] locateInTo(int start, int end)
728    {
729  309 int toStart[] = shiftFrom(start);
730  309 int toEnd[] = shiftFrom(end);
731  309 return getIntervals(toShifts, toStart, toEnd, toRatio);
732    }
733   
734    /**
735    * like shift - except returns the intervals in the given vector of shifts
736    * which were spanned in traversing fromStart to fromEnd
737    *
738    * @param shiftFrom
739    * @param fromStart
740    * @param fromEnd
741    * @param fromRatio2
742    * @return series of from,to intervals from from first position of starting
743    * region to final position of ending region inclusive
744    */
 
745  2130 toggle protected static int[] getIntervals(List<int[]> shiftFrom,
746    int[] fromStart, int[] fromEnd, int fromRatio2)
747    {
748  2130 if (fromStart == null || fromEnd == null)
749    {
750  168 return null;
751    }
752  1962 int startpos, endpos;
753  1962 startpos = fromStart[0]; // first position in fromStart
754  1962 endpos = fromEnd[0]; // last position in fromEnd
755  1962 int endindx = (fromRatio2 - 1); // additional positions to get to last
756    // position from endpos
757  1962 int intv = 0, intvSize = shiftFrom.size();
758  1962 int iv[], i = 0, fs = -1, fe_s = -1, fe = -1; // containing intervals
759    // search intervals to locate ones containing startpos and count endindx
760    // positions on from endpos
761  4098 while (intv < intvSize && (fs == -1 || fe == -1))
762    {
763  2136 iv = shiftFrom.get(intv++);
764  2136 if (fe_s > -1)
765    {
766  63 endpos = iv[0]; // start counting from beginning of interval
767  63 endindx--; // inclusive of endpos
768    }
769  2136 if (iv[0] <= iv[1])
770    {
771  2080 if (fs == -1 && startpos >= iv[0] && startpos <= iv[1])
772    {
773  1923 fs = i;
774    }
775  2080 if (endpos >= iv[0] && endpos <= iv[1])
776    {
777  1970 if (fe_s == -1)
778    {
779  1923 fe_s = i;
780    }
781  1970 if (fe_s != -1)
782    {
783  1970 if (endpos + endindx <= iv[1])
784    {
785  1939 fe = i;
786  1939 endpos = endpos + endindx; // end of end token is within this
787    // interval
788    }
789    else
790    {
791  31 endindx -= iv[1] - endpos; // skip all this interval too
792    }
793    }
794    }
795    }
796    else
797    {
798  56 if (fs == -1 && startpos <= iv[0] && startpos >= iv[1])
799    {
800  39 fs = i;
801    }
802  56 if (endpos <= iv[0] && endpos >= iv[1])
803    {
804  55 if (fe_s == -1)
805    {
806  39 fe_s = i;
807    }
808  55 if (fe_s != -1)
809    {
810  55 if (endpos - endindx >= iv[1])
811    {
812  55 fe = i;
813  55 endpos = endpos - endindx; // end of end token is within this
814    // interval
815    }
816    else
817    {
818  0 endindx -= endpos - iv[1]; // skip all this interval too
819    }
820    }
821    }
822    }
823  2136 i++;
824    }
825  1962 if (fs == fe && fe == -1)
826    {
827  0 return null;
828    }
829  1962 List<int[]> ranges = new ArrayList<>();
830  1962 if (fs <= fe)
831    {
832  1962 intv = fs;
833  1962 i = fs;
834    // truncate initial interval
835  1962 iv = shiftFrom.get(intv++);
836  1962 iv = new int[] { iv[0], iv[1] };// clone
837  1962 if (i == fs)
838    {
839  1962 iv[0] = startpos;
840    }
841  2038 while (i != fe)
842    {
843  76 ranges.add(iv); // add initial range
844  76 iv = shiftFrom.get(intv++); // get next interval
845  76 iv = new int[] { iv[0], iv[1] };// clone
846  76 i++;
847    }
848  1962 if (i == fe)
849    {
850  1962 iv[1] = endpos;
851    }
852  1962 ranges.add(iv); // add only - or final range
853    }
854    else
855    {
856    // walk from end of interval.
857  0 i = shiftFrom.size() - 1;
858  0 while (i > fs)
859    {
860  0 i--;
861    }
862  0 iv = shiftFrom.get(i);
863  0 iv = new int[] { iv[1], iv[0] };// reverse and clone
864    // truncate initial interval
865  0 if (i == fs)
866    {
867  0 iv[0] = startpos;
868    }
869  0 while (--i != fe)
870    { // fix apparent logic bug when fe==-1
871  0 ranges.add(iv); // add (truncated) reversed interval
872  0 iv = shiftFrom.get(i);
873  0 iv = new int[] { iv[1], iv[0] }; // reverse and clone
874    }
875  0 if (i == fe)
876    {
877    // interval is already reversed
878  0 iv[1] = endpos;
879    }
880  0 ranges.add(iv); // add only - or final range
881    }
882    // create array of start end intervals.
883  1962 int[] range = null;
884  1962 if (ranges != null && ranges.size() > 0)
885    {
886  1962 range = new int[ranges.size() * 2];
887  1962 intv = 0;
888  1962 intvSize = ranges.size();
889  1962 i = 0;
890  4000 while (intv < intvSize)
891    {
892  2038 iv = ranges.get(intv);
893  2038 range[i++] = iv[0];
894  2038 range[i++] = iv[1];
895  2038 ranges.set(intv++, null); // remove
896    }
897    }
898  1962 return range;
899    }
900   
901    /**
902    * get the 'initial' position of mpos in To
903    *
904    * @param mpos
905    * position in from
906    * @return position of first word in to reference frame
907    */
 
908  3 toggle public int getToPosition(int mpos)
909    {
910    // TODO not used - remove??
911  3 int[] mp = shiftTo(mpos);
912  3 if (mp != null)
913    {
914  3 return mp[0];
915    }
916  0 return mpos;
917    }
918   
919    /**
920    * get range of positions in To frame for the mpos word in From
921    *
922    * @param mpos
923    * position in From
924    * @return null or int[] first position in To for mpos, last position in to
925    * for Mpos
926    */
 
927  0 toggle public int[] getToWord(int mpos)
928    {
929  0 int[] mp = shiftTo(mpos);
930  0 if (mp != null)
931    {
932  0 return new int[] { mp[0], mp[0] + mp[2] * (getFromRatio() - 1) };
933    }
934  0 return null;
935    }
936   
937    /**
938    * get From position in the associated reference frame for position pos in the
939    * associated sequence.
940    *
941    * @param pos
942    * @return
943    */
 
944  0 toggle public int getMappedPosition(int pos)
945    {
946    // TODO not used - remove??
947  0 int[] mp = shiftFrom(pos);
948  0 if (mp != null)
949    {
950  0 return mp[0];
951    }
952  0 return pos;
953    }
954   
 
955  0 toggle public int[] getMappedWord(int pos)
956    {
957    // TODO not used - remove??
958  0 int[] mp = shiftFrom(pos);
959  0 if (mp != null)
960    {
961  0 return new int[] { mp[0], mp[0] + mp[2] * (getToRatio() - 1) };
962    }
963  0 return null;
964    }
965   
966    /**
967    *
968    * @return a MapList whose From range is this maplist's To Range, and vice
969    * versa
970    */
 
971  32 toggle public MapList getInverse()
972    {
973  32 return new MapList(getToRanges(), getFromRanges(), getToRatio(),
974    getFromRatio());
975    }
976   
977    /**
978    * test for containment rather than equivalence to another mapping
979    *
980    * @param map
981    * to be tested for containment
982    * @return true if local or mapped range map contains or is contained by this
983    * mapping
984    */
 
985  0 toggle public boolean containsEither(boolean local, MapList map)
986    {
987    // TODO not used - remove?
988  0 if (local)
989    {
990  0 return ((getFromLowest() >= map.getFromLowest()
991    && getFromHighest() <= map.getFromHighest())
992    || (getFromLowest() <= map.getFromLowest()
993    && getFromHighest() >= map.getFromHighest()));
994    }
995    else
996    {
997  0 return ((getToLowest() >= map.getToLowest()
998    && getToHighest() <= map.getToHighest())
999    || (getToLowest() <= map.getToLowest()
1000    && getToHighest() >= map.getToHighest()));
1001    }
1002    }
1003   
1004    /**
1005    * String representation - for debugging, not guaranteed not to change
1006    */
 
1007  11 toggle @Override
1008    public String toString()
1009    {
1010  11 StringBuilder sb = new StringBuilder(64);
1011  11 sb.append("[");
1012  11 for (int[] shift : fromShifts)
1013    {
1014  25 sb.append(" ").append(Arrays.toString(shift));
1015    }
1016  11 sb.append(" ] ");
1017  11 sb.append(fromRatio).append(":").append(toRatio);
1018  11 sb.append(" to [");
1019  11 for (int[] shift : toShifts)
1020    {
1021  16 sb.append(" ").append(Arrays.toString(shift));
1022    }
1023  11 sb.append(" ]");
1024  11 return sb.toString();
1025    }
1026   
1027    /**
1028    * Extend this map list by adding the given map's ranges. There is no
1029    * validation check that the ranges do not overlap existing ranges (or each
1030    * other), but contiguous ranges are merged.
1031    *
1032    * @param map
1033    */
 
1034  12 toggle public void addMapList(MapList map)
1035    {
1036  12 if (this.equals(map))
1037    {
1038  3 return;
1039    }
1040  9 this.fromLowest = Math.min(fromLowest, map.fromLowest);
1041  9 this.toLowest = Math.min(toLowest, map.toLowest);
1042  9 this.fromHighest = Math.max(fromHighest, map.fromHighest);
1043  9 this.toHighest = Math.max(toHighest, map.toHighest);
1044   
1045  9 for (int[] range : map.getFromRanges())
1046    {
1047  10 addRange(range, fromShifts);
1048    }
1049  9 for (int[] range : map.getToRanges())
1050    {
1051  11 addRange(range, toShifts);
1052    }
1053    }
1054   
1055    /**
1056    * Adds the given range to a list of ranges. If the new range just extends
1057    * existing ranges, the current endpoint is updated instead.
1058    *
1059    * @param range
1060    * @param addTo
1061    */
 
1062  29 toggle static void addRange(int[] range, List<int[]> addTo)
1063    {
1064    /*
1065    * list is empty - add to it!
1066    */
1067  29 if (addTo.size() == 0)
1068    {
1069  1 addTo.add(range);
1070  1 return;
1071    }
1072   
1073  28 int[] last = addTo.get(addTo.size() - 1);
1074  28 boolean lastForward = last[1] >= last[0];
1075  28 boolean newForward = range[1] >= range[0];
1076   
1077    /*
1078    * contiguous range in the same direction - just update endpoint
1079    */
1080  28 if (lastForward == newForward && last[1] == range[0])
1081    {
1082  4 last[1] = range[1];
1083  4 return;
1084    }
1085   
1086    /*
1087    * next range starts at +1 in forward sense - update endpoint
1088    */
1089  24 if (lastForward && newForward && range[0] == last[1] + 1)
1090    {
1091  3 last[1] = range[1];
1092  3 return;
1093    }
1094   
1095    /*
1096    * next range starts at -1 in reverse sense - update endpoint
1097    */
1098  21 if (!lastForward && !newForward && range[0] == last[1] - 1)
1099    {
1100  4 last[1] = range[1];
1101  4 return;
1102    }
1103   
1104    /*
1105    * just add the new range
1106    */
1107  17 addTo.add(range);
1108    }
1109   
1110    /**
1111    * Returns true if mapping is from forward strand, false if from reverse
1112    * strand. Result is just based on the first 'from' range that is not a single
1113    * position. Default is true unless proven to be false. Behaviour is not well
1114    * defined if the mapping has a mixture of forward and reverse ranges.
1115    *
1116    * @return
1117    */
 
1118  3 toggle public boolean isFromForwardStrand()
1119    {
1120  3 return isForwardStrand(getFromRanges());
1121    }
1122   
1123    /**
1124    * Returns true if mapping is to forward strand, false if to reverse strand.
1125    * Result is just based on the first 'to' range that is not a single position.
1126    * Default is true unless proven to be false. Behaviour is not well defined if
1127    * the mapping has a mixture of forward and reverse ranges.
1128    *
1129    * @return
1130    */
 
1131  27 toggle public boolean isToForwardStrand()
1132    {
1133  27 return isForwardStrand(getToRanges());
1134    }
1135   
1136    /**
1137    * A helper method that returns true unless at least one range has start > end.
1138    * Behaviour is undefined for a mixture of forward and reverse ranges.
1139    *
1140    * @param ranges
1141    * @return
1142    */
 
1143  30 toggle private boolean isForwardStrand(List<int[]> ranges)
1144    {
1145  30 boolean forwardStrand = true;
1146  30 for (int[] range : ranges)
1147    {
1148  38 if (range[1] > range[0])
1149    {
1150  20 break; // forward strand confirmed
1151    }
1152  18 else if (range[1] < range[0])
1153    {
1154  8 forwardStrand = false;
1155  8 break; // reverse strand confirmed
1156    }
1157    }
1158  30 return forwardStrand;
1159    }
1160   
1161    /**
1162    *
1163    * @return true if from, or to is a three to 1 mapping
1164    */
 
1165  6 toggle public boolean isTripletMap()
1166    {
1167  6 return (toRatio == 3 && fromRatio == 1)
1168    || (fromRatio == 3 && toRatio == 1);
1169    }
1170   
1171    /**
1172    * Returns a map which is the composite of this one and the input map. That
1173    * is, the output map has the fromRanges of this map, and its toRanges are the
1174    * toRanges of this map as transformed by the input map.
1175    * <p>
1176    * Returns null if the mappings cannot be traversed (not all toRanges of this
1177    * map correspond to fromRanges of the input), or if this.toRatio does not
1178    * match map.fromRatio.
1179    *
1180    * <pre>
1181    * Example 1:
1182    * this: from [1-100] to [501-600]
1183    * input: from [10-40] to [60-90]
1184    * output: from [10-40] to [560-590]
1185    * Example 2 ('reverse strand exons'):
1186    * this: from [1-100] to [2000-1951], [1000-951] // transcript to loci
1187    * input: from [1-50] to [41-90] // CDS to transcript
1188    * output: from [10-40] to [1960-1951], [1000-971] // CDS to gene loci
1189    * </pre>
1190    *
1191    * @param map
1192    * @return
1193    */
 
1194  8 toggle public MapList traverse(MapList map)
1195    {
1196  8 if (map == null)
1197    {
1198  0 return null;
1199    }
1200   
1201    /*
1202    * compound the ratios by this rule:
1203    * A:B with M:N gives A*M:B*N
1204    * reduced by greatest common divisor
1205    * so 1:3 with 3:3 is 3:9 or 1:3
1206    * 1:3 with 3:1 is 3:3 or 1:1
1207    * 1:3 with 1:3 is 1:9
1208    * 2:5 with 3:7 is 6:35
1209    */
1210  8 int outFromRatio = getFromRatio() * map.getFromRatio();
1211  8 int outToRatio = getToRatio() * map.getToRatio();
1212  8 int gcd = MathUtils.gcd(outFromRatio, outToRatio);
1213  8 outFromRatio /= gcd;
1214  8 outToRatio /= gcd;
1215   
1216  8 List<int[]> toRanges = new ArrayList<>();
1217  8 for (int[] range : getToRanges())
1218    {
1219  9 int[] transferred = map.locateInTo(range[0], range[1]);
1220  9 if (transferred == null || transferred.length % 2 != 0)
1221    {
1222  1 return null;
1223    }
1224   
1225    /*
1226    * convert [start1, end1, start2, end2, ...]
1227    * to [[start1, end1], [start2, end2], ...]
1228    */
1229  24 for (int i = 0; i < transferred.length;)
1230    {
1231  16 toRanges.add(new int[] { transferred[i], transferred[i + 1] });
1232  16 i += 2;
1233    }
1234    }
1235   
1236  7 return new MapList(getFromRanges(), toRanges, outFromRatio, outToRatio);
1237    }
1238   
1239    }
  • Report generated by OpenClover v 4.2.1 on Wed Oct 31 2018 15:15:54 GMT using coverage data from Wed Oct 31 2018 15:15:47 GMT.
  • Clover free edition.