elementAt instead of get for 1.1 compatibility
[jalview.git] / src / jalview / analysis / AlignmentSorter.java
1 /*\r
2 * Jalview - A Sequence Alignment Editor and Viewer\r
3 * Copyright (C) 2005 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.analysis;\r
20 \r
21 import jalview.datamodel.*;\r
22 \r
23 import jalview.util.*;\r
24 \r
25 import java.util.*;\r
26 \r
27 \r
28 /** Data structure to hold and manipulate a multiple sequence alignment\r
29  */\r
30 public class AlignmentSorter\r
31 {\r
32     static boolean sortIdAscending = true;\r
33     static int lastGroupHash = 0;\r
34     static boolean sortGroupAscending = true;\r
35     static AlignmentOrder lastOrder = null;\r
36     static boolean sortOrderAscending = true;\r
37     static NJTree lastTree = null;\r
38     static boolean sortTreeAscending = true;\r
39 \r
40     /**\r
41      * Sort by Percentage Identity\r
42      *\r
43      * @param align AlignmentI\r
44      * @param s SequenceI\r
45      */\r
46     public static void sortByPID(AlignmentI align, SequenceI s)\r
47     {\r
48         int nSeq = align.getHeight();\r
49 \r
50         float[] scores = new float[nSeq];\r
51         SequenceI[] seqs = new SequenceI[nSeq];\r
52 \r
53         for (int i = 0; i < nSeq; i++)\r
54         {\r
55             scores[i] = Comparison.PID(align.getSequenceAt(i).getSequence(),\r
56                                        s.getSequence());\r
57             seqs[i] = align.getSequenceAt(i);\r
58         }\r
59 \r
60         QuickSort.sort(scores, 0, scores.length - 1, seqs);\r
61 \r
62         setReverseOrder(align, seqs);\r
63     }\r
64 \r
65     /**\r
66      * Reverse the order of the sort\r
67      *\r
68      * @param align DOCUMENT ME!\r
69      * @param seqs DOCUMENT ME!\r
70      */\r
71     private static void setReverseOrder(AlignmentI align, SequenceI[] seqs)\r
72     {\r
73         int nSeq = seqs.length;\r
74 \r
75         int len = 0;\r
76 \r
77         if ((nSeq % 2) == 0)\r
78         {\r
79             len = nSeq / 2;\r
80         }\r
81         else\r
82         {\r
83             len = (nSeq + 1) / 2;\r
84         }\r
85 \r
86         // NOTE: DO NOT USE align.setSequenceAt() here - it will NOT work\r
87         for (int i = 0; i < len; i++)\r
88         {\r
89             //SequenceI tmp = seqs[i];\r
90             align.getSequences().setElementAt(seqs[nSeq - i - 1], i);\r
91             align.getSequences().setElementAt(seqs[i], nSeq - i - 1);\r
92         }\r
93     }\r
94 \r
95     /**\r
96      * Sets the Alignment object with the given sequences\r
97      *\r
98      * @param align Alignment object to be updated\r
99      * @param tmp sequences as a vector\r
100      */\r
101     private static void setOrder(AlignmentI align, Vector tmp)\r
102     {\r
103         setOrder(align, vectorSubsetToArray(tmp, align.getSequences()));\r
104     }\r
105 \r
106     /**\r
107      * Sets the Alignment object with the given sequences\r
108      *\r
109      * @param align DOCUMENT ME!\r
110      * @param seqs sequences as an array\r
111      */\r
112     private static void setOrder(AlignmentI align, SequenceI[] seqs)\r
113     {\r
114         // NOTE: DO NOT USE align.setSequenceAt() here - it will NOT work\r
115         Vector algn = align.getSequences();\r
116 \r
117         for (int i = 0; i < seqs.length; i++)\r
118         {\r
119             algn.setElementAt(seqs[i], i);\r
120         }\r
121     }\r
122 \r
123     /**\r
124      * Sorts by ID. Numbers are sorted before letters.\r
125      *\r
126      * @param align The alignment object to sort\r
127      */\r
128     public static void sortByID(AlignmentI align)\r
129     {\r
130         int nSeq = align.getHeight();\r
131 \r
132         String[] ids = new String[nSeq];\r
133         SequenceI[] seqs = new SequenceI[nSeq];\r
134 \r
135         for (int i = 0; i < nSeq; i++)\r
136         {\r
137             ids[i] = align.getSequenceAt(i).getName();\r
138             seqs[i] = align.getSequenceAt(i);\r
139         }\r
140 \r
141         QuickSort.sort(ids, seqs);\r
142 \r
143         if (sortIdAscending)\r
144         {\r
145             setReverseOrder(align, seqs);\r
146         }\r
147         else\r
148         {\r
149             setOrder(align, seqs);\r
150         }\r
151 \r
152         sortIdAscending = !sortIdAscending;\r
153     }\r
154 \r
155     /**\r
156      * Sorts the alignment by size of group.\r
157      * <br>Maintains the order of sequences in each group\r
158      * by order in given alignment object.\r
159      *\r
160      * @param align sorts the given alignment object by group\r
161      */\r
162     public static void sortByGroup(AlignmentI align)\r
163     {\r
164         //MAINTAINS ORIGNAL SEQUENCE ORDER,\r
165         //ORDERS BY GROUP SIZE\r
166         Vector groups = new Vector();\r
167 \r
168         if (groups.hashCode() != lastGroupHash)\r
169         {\r
170             sortGroupAscending = true;\r
171             lastGroupHash = groups.hashCode();\r
172         }\r
173         else\r
174         {\r
175             sortGroupAscending = !sortGroupAscending;\r
176         }\r
177 \r
178         //SORTS GROUPS BY SIZE\r
179         //////////////////////\r
180         for (int i = 0; i < align.getGroups().size(); i++)\r
181         {\r
182             SequenceGroup sg = (SequenceGroup) align.getGroups().elementAt(i);\r
183 \r
184             for (int j = 0; j < groups.size(); j++)\r
185             {\r
186                 SequenceGroup sg2 = (SequenceGroup) groups.elementAt(j);\r
187 \r
188                 if (sg.getSize(false) > sg2.getSize(false))\r
189                 {\r
190                     groups.insertElementAt(sg, j);\r
191 \r
192                     break;\r
193                 }\r
194             }\r
195 \r
196             if (!groups.contains(sg))\r
197             {\r
198                 groups.addElement(sg);\r
199             }\r
200         }\r
201 \r
202         //NOW ADD SEQUENCES MAINTAINING ALIGNMENT ORDER\r
203         ///////////////////////////////////////////////\r
204         Vector seqs = new Vector();\r
205 \r
206         for (int i = 0; i < groups.size(); i++)\r
207         {\r
208             SequenceGroup sg = (SequenceGroup) groups.elementAt(i);\r
209             SequenceI[] orderedseqs = sg.getSequencesInOrder(align);\r
210 \r
211             for (int j = 0; j < orderedseqs.length; j++)\r
212             {\r
213                 seqs.addElement(orderedseqs[j]);\r
214             }\r
215         }\r
216 \r
217         if (sortGroupAscending)\r
218         {\r
219             setOrder(align, seqs);\r
220         }\r
221         else\r
222         {\r
223             setReverseOrder(align,\r
224                 vectorSubsetToArray(seqs, align.getSequences()));\r
225         }\r
226     }\r
227 \r
228     /**\r
229      * Converts Vector to array.\r
230      * java 1.18 does not have Vector.toArray()\r
231      *\r
232      * @param tmp Vector of SequenceI objects\r
233      *\r
234      * @return array of Sequence[]\r
235      */\r
236     private static SequenceI[] vectorToArray(Vector tmp)\r
237     {\r
238         SequenceI[] seqs = new SequenceI[tmp.size()];\r
239 \r
240         for (int i = 0; i < tmp.size(); i++)\r
241         {\r
242             seqs[i] = (SequenceI) tmp.elementAt(i);\r
243         }\r
244 \r
245         return seqs;\r
246     }\r
247 \r
248     /**\r
249      * DOCUMENT ME!\r
250      *\r
251      * @param tmp DOCUMENT ME!\r
252      * @param mask DOCUMENT ME!\r
253      *\r
254      * @return DOCUMENT ME!\r
255      */\r
256     private static SequenceI[] vectorSubsetToArray(Vector tmp, Vector mask)\r
257     {\r
258         Vector seqs = new Vector();\r
259         int i;\r
260         boolean[] tmask = new boolean[mask.size()];\r
261 \r
262         for (i = 0; i < mask.size(); i++)\r
263             tmask[i] = true;\r
264 \r
265         for (i = 0; i < tmp.size(); i++)\r
266         {\r
267             Object sq = tmp.elementAt(i);\r
268 \r
269             if (mask.contains(sq) && tmask[mask.indexOf(sq)])\r
270             {\r
271                 tmask[mask.indexOf(sq)] = false;\r
272                 seqs.addElement(sq);\r
273             }\r
274         }\r
275 \r
276         for (i = 0; i < tmask.length; i++)\r
277             if (tmask[i])\r
278             {\r
279                 seqs.addElement(mask.elementAt(i));\r
280             }\r
281 \r
282         return vectorToArray(seqs);\r
283     }\r
284 \r
285     /**\r
286      * Sorts by a given AlignmentOrder object\r
287      *\r
288      * @param align Alignment to order\r
289      * @param order specified order for alignment\r
290      */\r
291     public static void sortBy(AlignmentI align, AlignmentOrder order)\r
292     {\r
293         // Get an ordered vector of sequences which may also be present in align\r
294         Vector tmp = order.getOrder();\r
295 \r
296         if (lastOrder == order)\r
297         {\r
298             sortOrderAscending = !sortOrderAscending;\r
299         }\r
300         else\r
301         {\r
302             sortOrderAscending = true;\r
303         }\r
304 \r
305         if (sortOrderAscending)\r
306         {\r
307             setOrder(align, tmp);\r
308         }\r
309         else\r
310         {\r
311             setReverseOrder(align,\r
312                 vectorSubsetToArray(tmp, align.getSequences()));\r
313         }\r
314     }\r
315 \r
316     /**\r
317      * DOCUMENT ME!\r
318      *\r
319      * @param align alignment to order\r
320      * @param tree tree which has\r
321      *\r
322      * @return DOCUMENT ME!\r
323      */\r
324     private static Vector getOrderByTree(AlignmentI align, NJTree tree)\r
325     {\r
326         int nSeq = align.getHeight();\r
327 \r
328         Vector tmp = new Vector();\r
329 \r
330         tmp = _sortByTree(tree.getTopNode(), tmp, align.getSequences());\r
331 \r
332         if (tmp.size() != nSeq)\r
333         {\r
334             // TODO: JBPNote - decide if this is always an error\r
335             // (eg. not when a tree is associated to another alignment which has more\r
336             //  sequences)\r
337             if (tmp.size() < nSeq)\r
338             {\r
339                 addStrays(align, tmp);\r
340             }\r
341 \r
342             if (tmp.size() != nSeq)\r
343             {\r
344                 System.err.println("ERROR: tmp.size()=" + tmp.size() +\r
345                     " != nseq=" + nSeq + " in getOrderByTree");\r
346             }\r
347         }\r
348 \r
349         return tmp;\r
350     }\r
351 \r
352     /**\r
353      * Sorts the alignment by a given tree\r
354      *\r
355      * @param align alignment to order\r
356      * @param tree tree which has\r
357      */\r
358     public static void sortByTree(AlignmentI align, NJTree tree)\r
359     {\r
360         Vector tmp = getOrderByTree(align, tree);\r
361 \r
362         // tmp should properly permute align with tree.\r
363         if (lastTree != tree)\r
364         {\r
365             sortTreeAscending = true;\r
366             lastTree = tree;\r
367         }\r
368         else\r
369         {\r
370             sortTreeAscending = !sortTreeAscending;\r
371         }\r
372 \r
373         if (sortTreeAscending)\r
374         {\r
375             setOrder(align, tmp);\r
376         }\r
377         else\r
378         {\r
379             setReverseOrder(align,\r
380                 vectorSubsetToArray(tmp, align.getSequences()));\r
381         }\r
382     }\r
383 \r
384     /**\r
385      * DOCUMENT ME!\r
386      *\r
387      * @param align DOCUMENT ME!\r
388      * @param seqs DOCUMENT ME!\r
389      */\r
390     private static void addStrays(AlignmentI align, Vector seqs)\r
391     {\r
392         int nSeq = align.getHeight();\r
393 \r
394         for (int i = 0; i < nSeq; i++)\r
395         {\r
396             if (!seqs.contains(align.getSequenceAt(i)))\r
397             {\r
398                 seqs.addElement(align.getSequenceAt(i));\r
399             }\r
400         }\r
401 \r
402         if (nSeq != seqs.size())\r
403         {\r
404             System.err.println(\r
405                 "ERROR: Size still not right even after addStrays");\r
406         }\r
407     }\r
408 \r
409     /**\r
410      * DOCUMENT ME!\r
411      *\r
412      * @param node DOCUMENT ME!\r
413      * @param tmp DOCUMENT ME!\r
414      * @param seqset DOCUMENT ME!\r
415      *\r
416      * @return DOCUMENT ME!\r
417      */\r
418     private static Vector _sortByTree(SequenceNode node, Vector tmp,\r
419         Vector seqset)\r
420     {\r
421         if (node == null)\r
422         {\r
423             return tmp;\r
424         }\r
425 \r
426         SequenceNode left = (SequenceNode) node.left();\r
427         SequenceNode right = (SequenceNode) node.right();\r
428 \r
429         if ((left == null) && (right == null))\r
430         {\r
431             if (!node.isPlaceholder() && (node.element() != null))\r
432             {\r
433                 if (node.element() instanceof SequenceI)\r
434                 {\r
435                     if (!tmp.contains(node.element()))\r
436                     {\r
437                         tmp.addElement((SequenceI) node.element());\r
438                     }\r
439                 }\r
440             }\r
441 \r
442             return tmp;\r
443         }\r
444         else\r
445         {\r
446             _sortByTree(left, tmp, seqset);\r
447             _sortByTree(right, tmp, seqset);\r
448         }\r
449 \r
450         return tmp;\r
451     }\r
452 \r
453     // Ordering Objects\r
454     // Alignment.sortBy(OrderObj) - sequence of sequence pointer refs in appropriate order\r
455     //\r
456 \r
457     /**\r
458      * recover the order of sequences given by the safe numbering scheme introducd\r
459      * SeqsetUtils.uniquify.\r
460      */\r
461     public static void recoverOrder(SequenceI[] alignment)\r
462     {\r
463         float[] ids = new float[alignment.length];\r
464 \r
465         for (int i = 0; i < alignment.length; i++)\r
466             ids[i] = (new Float(alignment[i].getName().substring(8))).floatValue();\r
467 \r
468         jalview.util.QuickSort.sort(ids, alignment);\r
469     }\r
470 }\r