Merge branch 'JAL-3878_ws-overhaul-3' into with_ws_overhaul-3
[jalview.git] / src / jalview / datamodel / CigarArray.java
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.datamodel;
22
23 import java.util.Iterator;
24
25 public class CigarArray extends CigarBase
26 {
27   /**
28    * Do CIGAR operations on a set of sequences from many other cigars BAD THINGS
29    * WILL HAPPEN IF A CIGARARRAY IS PASSED TO A CIGARARRAY or a CIGARCIGAR is
30    * given a CIGARARRAY to insert gaps into.
31    */
32   /**
33    * array of subject cigars
34    */
35   public CigarSimple refCigars[] = null;
36
37   private boolean seqcigararray = false;
38
39   private CigarArray()
40   {
41     super();
42   }
43
44   /**
45    * isSeqCigarArray()
46    * 
47    * @return boolean true if all refCigars resolve to a SeqCigar or a CigarCigar
48    */
49   public boolean isSeqCigarArray()
50   {
51     return seqcigararray;
52   }
53
54   /**
55    * Apply CIGAR operations to several cigars in parallel will throw an error if
56    * any of cigar are actually CigarArrays.
57    * 
58    * @param cigar
59    *          Cigar[]
60    */
61   public CigarArray(CigarSimple[] cigars)
62   {
63     super();
64     seqcigararray = true;
65     if (cigars != null && cigars.length > 0)
66     {
67       refCigars = new CigarSimple[cigars.length];
68       for (int c = 0; c < cigars.length; c++)
69       {
70         refCigars[c] = cigars[c];
71         if (!((cigars[c] instanceof SeqCigar)
72                 || cigars[c] instanceof CigarCigar))
73         {
74           seqcigararray = false;
75         }
76       }
77     }
78   }
79
80   /**
81    * construct a cigar array from the current alignment, or just the subset of
82    * the current alignment specified by selectionGroup. Any columns marked as
83    * hidden in columnSelection will be marked as deleted in the array.
84    * 
85    * @param alignment
86    * @param columnSelection
87    * @param selectionGroup
88    */
89   public CigarArray(AlignmentI alignment, HiddenColumns hidden,
90           SequenceGroup selectionGroup)
91   {
92     this(constructSeqCigarArray(alignment, selectionGroup));
93     constructFromAlignment(alignment, hidden, selectionGroup);
94   }
95
96   private static int[] _calcStartEndBounds(AlignmentI alignment,
97           SequenceGroup selectionGroup)
98   {
99     int[] startend = new int[] { 0, 0, 0 };
100     if (selectionGroup != null)
101     {
102       startend[0] = selectionGroup.getSize();
103       startend[1] = selectionGroup.getStartRes();
104       startend[2] = selectionGroup.getEndRes(); // inclusive for start and end
105                                                 // in
106       // SeqCigar constructor
107     }
108     else
109     {
110       startend[0] = alignment.getHeight();
111       startend[2] = alignment.getWidth() - 1;
112     }
113     return startend;
114   }
115
116   public static SeqCigar[] constructSeqCigarArray(AlignmentI alignment,
117           SequenceGroup selectionGroup)
118   {
119     SequenceI[] seqs = null;
120     int i, iSize;
121     int _startend[] = _calcStartEndBounds(alignment, selectionGroup);
122     int start = _startend[1], end = _startend[2];
123     if (selectionGroup != null)
124     {
125       iSize = selectionGroup.getSize();
126       seqs = selectionGroup.getSequencesInOrder(alignment);
127       start = selectionGroup.getStartRes();
128       end = selectionGroup.getEndRes(); // inclusive for start and end in
129       // SeqCigar constructor
130     }
131     else
132     {
133       iSize = alignment.getHeight();
134       seqs = alignment.getSequencesArray();
135       end = alignment.getWidth() - 1;
136     }
137     SeqCigar[] selseqs = new SeqCigar[iSize];
138     for (i = 0; i < iSize; i++)
139     {
140       selseqs[i] = new SeqCigar(seqs[i], start, end);
141     }
142     return selseqs;
143   }
144
145   /**
146    * internal constructor function - called by CigarArray(AlignmentI, ...);
147    * 
148    * @param alignment
149    * @param list
150    *          - vector of visible regions as returned from
151    *          columnSelection.getHiddenColumns()
152    * @param selectionGroup
153    */
154   private void constructFromAlignment(AlignmentI alignment,
155           HiddenColumns hidden, SequenceGroup selectionGroup)
156   {
157     int[] _startend = _calcStartEndBounds(alignment, selectionGroup);
158     int start = _startend[1];
159     int end = _startend[2];
160     // now construct the CigarArray operations
161     if (hidden != null)
162     {
163       int[] region;
164       int hideStart;
165       int hideEnd;
166       int last = start;
167
168       Iterator<int[]> regions = hidden.getBoundedIterator(start, end);
169       while (regions.hasNext())
170       {
171         region = regions.next();
172         hideStart = region[0];
173         hideEnd = region[1];
174
175         // truncate region at start if last falls in region
176         if ((hideStart < last) && (hideEnd >= last))
177         {
178           hideStart = last;
179         }
180
181         // truncate region at end if end falls in region
182         if (hideEnd > end) // already checked that hideStart<=end
183         {
184           hideEnd = end;
185         }
186
187         /**
188          * form operations...
189          */
190         if (last < hideStart)
191         {
192           addOperation(CigarArray.M, hideStart - last);
193         }
194         addOperation(CigarArray.D, 1 + hideEnd - hideStart);
195         last = hideEnd + 1;
196       }
197
198       // Final match if necessary.
199       if (last <= end)
200       {
201         addOperation(CigarArray.M, end - last + 1);
202       }
203     }
204     else
205     {
206       addOperation(CigarArray.M, end - start + 1);
207     }
208   }
209
210   /**
211    * @see CigarBase.getSequenceAndDeletions
212    * @param GapChar
213    *          char
214    * @return Object[][]
215    */
216   protected Object[][] getArrayofSequenceAndDeletions(char GapChar)
217   {
218     if (refCigars == null || refCigars.length == 0 || length == 0)
219     {
220       return null;
221     }
222     Object[][] sqanddels = new Object[refCigars.length][];
223     for (int c = 0; c < refCigars.length; c++)
224     {
225       String refString = refCigars[c].getSequenceString(GapChar);
226       if (refString != null)
227       {
228         sqanddels[c] = getSequenceAndDeletions(refString, GapChar);
229       }
230       else
231       {
232         sqanddels[c] = null;
233       }
234     }
235     return sqanddels;
236   }
237
238   /**
239    * NOTE: this is an improper sequence string function
240    * 
241    * @return String formed by newline concatenated results of applying CIGAR
242    *         operations to each reference object in turn.
243    * @param GapChar
244    *          char
245    * @return '\n' separated strings (empty results included as \n\n)
246    */
247   public String getSequenceString(char GapChar)
248   {
249     if (length == 0 || refCigars == null)
250     {
251       return "";
252     }
253     StringBuffer seqStrings = new StringBuffer();
254     Object[][] sqanddels = getArrayofSequenceAndDeletions(GapChar);
255     for (int c = 0; c < refCigars.length; c++)
256     {
257       if (sqanddels[c] != null)
258       {
259         seqStrings.append((String) sqanddels[c][0]);
260         sqanddels[c][0] = null;
261       }
262       seqStrings.append('\n');
263     }
264     return seqStrings.toString();
265   }
266
267   /**
268    * return string results of applying cigar string to all reference cigars
269    * 
270    * @param GapChar
271    *          char
272    * @return String[]
273    */
274   public String[] getSequenceStrings(char GapChar)
275   {
276
277     if (length == 0 || refCigars == null || refCigars.length == 0)
278     {
279       return null;
280     }
281     Object[][] sqanddels = getArrayofSequenceAndDeletions(GapChar);
282     String[] seqs = new String[sqanddels.length];
283     for (int c = 0; c < refCigars.length; c++)
284     {
285       seqs[c] = (String) sqanddels[c][0];
286     }
287     return seqs;
288   }
289
290   /**
291    * Combines the CigarArray cigar operations with the operations in each
292    * reference cigar - creating a new reference cigar
293    * 
294    * @return Cigar[]
295    * 
296    *         public CigarBase[] getEditedCigars() {
297    * 
298    *         return new CigarBase[] {}; }
299    */
300   /**
301    * applyDeletions edits underlying refCigars to propagate deleted regions, and
302    * removes deletion operations from CigarArray operation list.
303    * 
304    * @return int[] position after deletion occured and range of deletion in
305    *         cigarArray or null if none occured
306    */
307   public int[] applyDeletions()
308   {
309     java.util.Vector delpos = null;
310     if (length == 0)
311     {
312       return null;
313     }
314     int cursor = 0; // range counter for deletions
315     int vcursor = 0; // visible column index
316     int offset = 0; // shift in visible column index as deletions are made
317     int i = 0;
318     while (i < length)
319     {
320       if (operation[i] != D)
321       {
322         if (operation[i] == M)
323         {
324           cursor += range[i];
325         }
326         vcursor += range[i++];
327       }
328       else
329       {
330         if (delpos == null)
331         {
332           delpos = new java.util.Vector();
333         }
334         int delstart = cursor, delend = cursor + range[i] - 1; // inclusive
335         delpos.addElement(new int[] { vcursor + offset, range[i] }); // index of
336                                                                      // right
337                                                                      // hand
338                                                                      // column
339                                                                      // after
340         // hidden region boundary
341         offset += range[i] - 1; // shift in visible column coordinates
342         System.arraycopy(operation, i + 1, operation, i, length - i);
343         System.arraycopy(range, i + 1, range, i, length - i);
344         length--;
345         /*
346          * int dmax=0; for (int s=0; s<refCigars.length; s++) { int d =
347          * refCigars[s].deleteRange(delstart, delend); if (d>dmax) dmax=d; }
348          * offset+=dmax; // shift in visible column coordinates
349          */
350         for (int s = 0; s < refCigars.length; s++)
351         {
352           int d = refCigars[s].deleteRange(delstart, delend);
353         }
354
355       }
356     }
357     if (delpos != null)
358     {
359       int[] pos = new int[delpos.size() * 2];
360       for (int k = 0, l = delpos.size(); k < l; k++)
361       {
362         int[] dr = ((int[]) delpos.elementAt(k));
363         pos[k * 2] = dr[0];
364         pos[k * 2 + 1] = dr[1];
365         delpos.setElementAt(null, k);
366       }
367       delpos = null;
368       return pos;
369     }
370     return null;
371   }
372
373   /**
374    * 
375    * @return SeqCigar[] or null if CigarArray is not a SeqCigarArray (ie it does
376    *         not resolve to set of seqCigars)
377    */
378   public SeqCigar[] getSeqCigarArray()
379   {
380     if (!isSeqCigarArray())
381     {
382       return null;
383     }
384     SeqCigar[] sa = new SeqCigar[refCigars.length];
385     for (int i = 0; i < refCigars.length; i++)
386     {
387       sa[i] = (SeqCigar) refCigars[i];
388     }
389     return sa;
390   }
391 }