Send gapChar to print original Data
[jalview.git] / src / jalview / datamodel / CigarBase.java
1 package jalview.datamodel;
2
3 public abstract class CigarBase
4 {
5   /**
6    * Base class for compact idiosyncratic representation of gaps and aligned residues
7    * Regards to Tom Oldfield for his DynamicArray class.
8    * 17th July 2006
9    * Not thread safe.
10    */
11   public CigarBase()
12   {
13     // nothing to be done (probably)
14   }
15
16   protected int length = 0;
17   protected int _inc_length = 10; // extension range for addition of new operations
18   protected char[] operation = null;
19   protected int[] range = null;
20   /**
21    * Range of Hidden residues in seq (translated as deleted in seq)
22    */
23   public static final char D = 'D'; /**
24   * Range of insertions to seq
25   */
26  public static final char I = 'I'; /**
27   * Range of aligned residues
28   */
29  public static final char M = 'M';
30   static protected final char _case_shift = 'a' - 'A';
31   /**
32    * Ugly function to get edited sequence string, start and end symbol positions and the deletion regions as an array of int pairs
33    * May return null for an empty cigar string.
34    * May return null for deletion ranges if there are none.
35    * @param reference - the symbol sequence to apply the cigar operations to (or null if no sequence)
36    * @param GapChar - the symbol to use for Insert operations
37    * @return Object[] { String, int[] {start, startcol, end, endcol}, int[][3] {start, end, col} or null} the gapped sequence, first and last residue index, and the deletion ranges on the reference sequence
38    */
39   public Object[] getSequenceAndDeletions(String reference, char GapChar)
40   {
41     int rlength=0;
42     int[][] deletions = new int[length][];
43     int[][] trunc_deletions = null;
44     StringBuffer sq = new StringBuffer();
45     int cursor = 0, alcursor=0,start = 0, startpos=0, end = 0, endpos=0, delcount = -1;
46     boolean consecutive_del = false;
47     if (length == 0)
48     {
49       return null;
50     }
51     if (reference!=null)
52       rlength=reference.length();
53     boolean modstart = true;
54     for (int i = 0; i < length; i++)
55     {
56       switch (operation[i])
57       {
58         case D:
59           if (!consecutive_del)
60           {
61             deletions[++delcount] = new int[]
62                 {
63                 cursor, 0, alcursor};
64           }
65           cursor += range[i];
66           deletions[delcount][1] = cursor - 1;
67           consecutive_del = true;
68           break;
69         case I:
70           consecutive_del = false;
71           for (int r = 0; r < range[i]; r++)
72           {
73             sq.append(GapChar);
74             alcursor++;
75           }
76           break;
77         case M:
78           consecutive_del = false;
79           if (modstart)
80           {
81             start = cursor;
82             startpos=alcursor;
83             modstart = false;
84           }
85           if (reference!=null) {
86             int sbend = cursor+range[i];
87             if (sbend>=rlength) {
88               sq.append(reference.substring(cursor, rlength));
89               while (sbend-- >= rlength)
90               {
91                 sq.append(GapChar);
92               }
93             } else {
94               sq.append(reference.substring(cursor, sbend));
95             }
96           }
97           alcursor+=range[i];
98           cursor += range[i];
99           end = cursor - 1;
100           endpos = alcursor;
101           break;
102         default:
103           throw new Error("Unknown SeqCigar operation '" + operation[i] + "'");
104       }
105     }
106     if (++delcount > 0)
107     {
108       trunc_deletions = new int[delcount][];
109       System.arraycopy(deletions, 0, trunc_deletions, 0, delcount);
110     }
111     deletions = null;
112     return new Object[]
113         {
114         ((reference!=null) ? sq.toString() : null),
115         new int[] {
116         start, startpos, end, endpos}, trunc_deletions};
117   }
118
119   /**
120    * turn a cigar string into a series of operation range pairs
121    * @param cigarString String
122    * @return object[] {char[] operation, int[] range}
123    * @throws java.lang.Exception for improperly formated cigar strings or ones with unknown operations
124    */
125   public static Object[] parseCigarString(String cigarString)
126       throws Exception
127   {
128     int ops = 0;
129     for (int i = 0, l = cigarString.length(); i < l; i++)
130     {
131       char c = cigarString.charAt(i);
132       if (c == M || c == (M - _case_shift) || c == I || c == (I - _case_shift) ||
133           c == D || c == (D - _case_shift))
134       {
135         ops++;
136       }
137     }
138     char[] operation = new char[ops];
139     int[] range = new int[ops];
140     int op = 0;
141     int i = 0, l = cigarString.length();
142     while (i < l)
143     {
144       char c;
145       int j = i;
146       do
147       {
148         c = cigarString.charAt(j++);
149       }
150       while (c >= '0' && c <= '9' && j < l);
151       if (j >= l && c >= '0' && c <= '9')
152       {
153         throw new Exception("Unterminated cigar string.");
154       }
155       try
156       {
157         String rangeint = cigarString.substring(i, j - 1);
158         range[op] = Integer.parseInt(rangeint);
159         i = j;
160       }
161       catch (Exception e)
162       {
163         throw new Error("Implementation bug in parseCigarString");
164       }
165       if (c >= 'a' && c <= 'z')
166       {
167         c -= _case_shift;
168       }
169       if ( (c == M || c == I || c == D))
170       {
171         operation[op++] = c;
172       }
173       else
174       {
175         throw new Exception("Unexpected operation '" + c +
176                             "' in cigar string (position " + i + " in '" +
177                             cigarString + "'");
178       }
179     }
180     return new Object[]
181         {
182         operation, range};
183   }
184
185   /**
186    * inefficient add one operation to cigar string
187    * @param op char
188    * @param range int
189    */
190   public void addOperation(char op, int range)
191   {
192     if (op >= 'a' && op <= 'z')
193     {
194       op -= _case_shift;
195     }
196     if (op != M && op != D && op != I)
197     {
198       throw new Error("Implementation error. Invalid operation string.");
199     }
200     if (range<=0)
201       throw new Error("Invalid range string (must be non-zero positive number)");
202     int lngth = 0;
203     if (operation == null)
204     {
205       this.operation = new char[_inc_length];
206       this.range = new int[_inc_length];
207     }
208     if (length + 1 == operation.length)
209     {
210       char[] ops = this.operation;
211       this.operation = new char[length + 1 + _inc_length];
212       System.arraycopy(ops, 0, this.operation, 0, length);
213       ops = null;
214       int[] rng = this.range;
215       this.range = new int[length + 1 + _inc_length];
216       System.arraycopy(rng, 0, this.range, 0, length);
217       rng = null;
218     }
219     if ((length>0) && (operation[length-1]==op))
220       length--; // modify existing operation.
221     else
222       this.range[length]=0; // reset range
223     this.operation[length] = op;
224     this.range[length++] += range;
225   }
226
227   /**
228    * semi-efficient insert an operation on the current cigar string set at column pos (from 1)
229    * NOTE: Insertion operations simply extend width of cigar result - affecting registration of alignment
230    * Deletion ops will shorten length of result - and affect registration of alignment
231    * Match ops will also affect length of result - affecting registration of alignment
232    * (ie "10M".insert(4,I,3)->"4M3I3M")
233    * (ie "10M".insert(4,D,3)->"4M3D3M")
234    * (ie "5I5M".insert(4,I,3)->"8I5M")
235    * (ie "5I5M".insert(4,D,3)->"4I3M")
236    * if pos is beyond width - I operations are added before the operation
237    * (ie "10M".insert(4,M,3)->"13M")
238    * (ie "5I5M".insert(4,M,3)->"4I8M") - effectively shifts sequence left by 1 residue and extends it by 3
239    * @param pos int
240    * @param op char
241    * @param range int
242    */
243   public void addOperationAt(int pos, char op, int range)
244   {
245
246   }
247
248   /**
249    * sum of ranges in cigar string
250    * @return int number of residues hidden, matched, or gaps inserted into sequence
251    */
252   public int getFullWidth()
253   {
254     int w = 0;
255     if (range != null)
256     {
257       for (int i = 0; i < length; i++)
258       {
259         w += range[i];
260       }
261     }
262     return w;
263   }
264
265   /**
266    * Visible length of aligned sequence
267    * @return int length of including gaps and less hidden regions
268    */
269   public int getWidth()
270   {
271     int w = 0;
272     if (range != null)
273     {
274       for (int i = 0; i < length; i++)
275       {
276         if (operation[i] == M || operation[i] == I)
277         {
278           w += range[i];
279         }
280       }
281     }
282     return w;
283   }
284   /**
285    * mark a range of inserted residues
286    * @param range int
287    */
288   public void addInsertion(int range)
289   {
290     this.addOperation(I, range);
291   }
292
293   /**
294    * mark the next range residues as hidden (not aligned) or deleted
295    * @param range int
296    */
297   public void addDeleted(int range)
298   {
299     this.addOperation(D, range);
300   }
301
302   /**
303    * Modifies operation list to delete columns from start to end (inclusive)
304    * editing will remove insertion operations, and convert matches to deletions
305    * @param start alignment column
306    * @param end alignment column
307    * @return boolean true if residues were marked as deleted.
308    */
309   public boolean deleteRange(int start, int end)
310   {
311     boolean deleted = false;
312     int op = 0, prevop = -1, firstm = -1,
313         lastm = -1, postop = -1;
314     int width = 0; // zero'th column
315     if (length > 0)
316     {
317       // find operation bracketing start of the range
318       do
319       {
320         if (operation[op] != D)
321         {
322           width += range[prevop = op];
323         }
324         op++;
325       }
326       while (op < length && width < start);
327     }
328     if (width < start)
329     {
330       // run off end - add more operations up to deletion.
331       addInsertion(start - width);
332     }
333     else
334     {
335       // edit existing operations.
336       op = prevop;
337       width -= range[prevop];
338       int[] oldrange = range;
339       char[] oldops = operation;
340       range = new int[oldrange.length];
341       operation = new char[oldops.length];
342       if (op < length)
343       {
344         do
345         {
346           if (operation[op] != D)
347           {
348             width += range[postop = op];
349           }
350           op++;
351         }
352         while (op < length && width <= end);
353       }
354     }
355     if (deleted == true)
356     {
357       addDeleted(end - start + 1);
358     }
359     return deleted;
360   }
361
362   /**
363    * Return an ENSEMBL style cigar string where D may indicates excluded parts of seq
364    * @return String of form ([0-9]+[IMD])+
365    */
366   public String getCigarstring()
367   {
368     StringBuffer cigarString = new StringBuffer();
369     for (int i = 0; i < length; i++)
370     {
371       cigarString.append("" + range[i]);
372       cigarString.append(operation[i]);
373     }
374     return cigarString.toString();
375   }
376 }