formatting
[jalview.git] / src / jalview / analysis / AlignmentSorter.java
1 /*
2  * Jalview - A Sequence Alignment Editor and Viewer (Version 2.7)
3  * Copyright (C) 2011 J Procter, AM Waterhouse, J Engelhardt, LM Lui, G Barton, M Clamp, S Searle
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 of the License, or (at your option) any later version.
10  * 
11  * Jalview is distributed in the hope that it will be useful, but 
12  * WITHOUT ANY WARRANTY; without even the implied warranty 
13  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR 
14  * PURPOSE.  See the GNU General Public License for more details.
15  * 
16  * You should have received a copy of the GNU General Public License along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
17  */
18 package jalview.analysis;
19
20 import java.util.*;
21
22 import jalview.datamodel.*;
23 import jalview.util.*;
24
25 /**
26  * Routines for manipulating the order of a multiple sequence alignment TODO:
27  * this class retains some global states concerning sort-order which should be
28  * made attributes for the caller's alignment visualization. TODO: refactor to
29  * allow a subset of selected sequences to be sorted within the context of a
30  * whole alignment. Sort method template is: SequenceI[] tobesorted, [ input
31  * data mapping to each tobesorted element to use ], Alignment context of
32  * tobesorted that are to be re-ordered, boolean sortinplace, [special data - ie
33  * seuqence to be sorted w.r.t.]) sortinplace implies that the sorted vector
34  * resulting from applying the operation to tobesorted should be mapped back to
35  * the original positions in alignment. Otherwise, normal behaviour is to re
36  * order alignment so that tobesorted is sorted and grouped together starting
37  * from the first tobesorted position in the alignment. e.g. (a,tb2,b,tb1,c,tb3
38  * becomes a,tb1,tb2,tb3,b,c)
39  */
40 public class AlignmentSorter
41 {
42   /**
43    * todo: refactor searches to follow a basic pattern: (search property, last
44    * search state, current sort direction)
45    */
46   static boolean sortIdAscending = true;
47
48   static int lastGroupHash = 0;
49
50   static boolean sortGroupAscending = true;
51
52   static AlignmentOrder lastOrder = null;
53
54   static boolean sortOrderAscending = true;
55
56   static NJTree lastTree = null;
57
58   static boolean sortTreeAscending = true;
59
60   /**
61    * last Annotation Label used by sortByScore
62    */
63   private static String lastSortByScore;
64
65   private static boolean sortByScoreAscending = true;
66
67   /**
68    * compact representation of last arguments to SortByFeatureScore
69    */
70   private static String lastSortByFeatureScore;
71
72   private static boolean sortByFeatureScoreAscending = true;
73
74   private static boolean sortLengthAscending;
75
76   /**
77    * Sort by Percentage Identity w.r.t. s
78    * 
79    * @param align
80    *          AlignmentI
81    * @param s
82    *          SequenceI
83    * @param tosort
84    *          sequences from align that are to be sorted.
85    */
86   public static void sortByPID(AlignmentI align, SequenceI s,
87           SequenceI[] tosort)
88   {
89     sortByPID(align, s, tosort, 0, -1);
90   }
91
92   /**
93    * Sort by Percentage Identity w.r.t. s
94    * 
95    * @param align
96    *          AlignmentI
97    * @param s
98    *          SequenceI
99    * @param tosort
100    *          sequences from align that are to be sorted.
101    * @param start
102    *          start column (0 for beginning
103    * @param end
104    */
105   public static void sortByPID(AlignmentI align, SequenceI s,
106           SequenceI[] tosort, int start, int end)
107   {
108     int nSeq = align.getHeight();
109
110     float[] scores = new float[nSeq];
111     SequenceI[] seqs = new SequenceI[nSeq];
112
113     for (int i = 0; i < nSeq; i++)
114     {
115       scores[i] = Comparison.PID(align.getSequenceAt(i)
116               .getSequenceAsString(), s.getSequenceAsString());
117       seqs[i] = align.getSequenceAt(i);
118     }
119
120     QuickSort.sort(scores, 0, scores.length - 1, seqs);
121
122     setReverseOrder(align, seqs);
123   }
124
125   /**
126    * Reverse the order of the sort
127    * 
128    * @param align
129    *          DOCUMENT ME!
130    * @param seqs
131    *          DOCUMENT ME!
132    */
133   private static void setReverseOrder(AlignmentI align, SequenceI[] seqs)
134   {
135     int nSeq = seqs.length;
136
137     int len = 0;
138
139     if ((nSeq % 2) == 0)
140     {
141       len = nSeq / 2;
142     }
143     else
144     {
145       len = (nSeq + 1) / 2;
146     }
147
148     // NOTE: DO NOT USE align.setSequenceAt() here - it will NOT work
149     for (int i = 0; i < len; i++)
150     {
151       // SequenceI tmp = seqs[i];
152       align.getSequences().setElementAt(seqs[nSeq - i - 1], i);
153       align.getSequences().setElementAt(seqs[i], nSeq - i - 1);
154     }
155   }
156
157   /**
158    * Sets the Alignment object with the given sequences
159    * 
160    * @param align
161    *          Alignment object to be updated
162    * @param tmp
163    *          sequences as a vector
164    */
165   private static void setOrder(AlignmentI align, Vector tmp)
166   {
167     setOrder(align, vectorSubsetToArray(tmp, align.getSequences()));
168   }
169
170   /**
171    * Sets the Alignment object with the given sequences
172    * 
173    * @param align
174    *          DOCUMENT ME!
175    * @param seqs
176    *          sequences as an array
177    */
178   public static void setOrder(AlignmentI align, SequenceI[] seqs)
179   {
180     // NOTE: DO NOT USE align.setSequenceAt() here - it will NOT work
181     Vector algn = align.getSequences();
182     Vector tmp = new Vector();
183
184     for (int i = 0; i < seqs.length; i++)
185     {
186       if (algn.contains(seqs[i]))
187       {
188         tmp.addElement(seqs[i]);
189       }
190     }
191
192     algn.removeAllElements();
193     // User may have hidden seqs, then clicked undo or redo
194     for (int i = 0; i < tmp.size(); i++)
195     {
196       algn.addElement(tmp.elementAt(i));
197     }
198
199   }
200
201   /**
202    * Sorts by ID. Numbers are sorted before letters.
203    * 
204    * @param align
205    *          The alignment object to sort
206    */
207   public static void sortByID(AlignmentI align)
208   {
209     int nSeq = align.getHeight();
210
211     String[] ids = new String[nSeq];
212     SequenceI[] seqs = new SequenceI[nSeq];
213
214     for (int i = 0; i < nSeq; i++)
215     {
216       ids[i] = align.getSequenceAt(i).getName();
217       seqs[i] = align.getSequenceAt(i);
218     }
219
220     QuickSort.sort(ids, seqs);
221
222     if (sortIdAscending)
223     {
224       setReverseOrder(align, seqs);
225     }
226     else
227     {
228       setOrder(align, seqs);
229     }
230
231     sortIdAscending = !sortIdAscending;
232   }
233
234   /**
235    * Sorts by sequence length
236    * 
237    * @param align
238    *          The alignment object to sort
239    */
240   public static void sortByLength(AlignmentI align)
241   {
242     int nSeq = align.getHeight();
243
244     float[] length = new float[nSeq];
245     SequenceI[] seqs = new SequenceI[nSeq];
246
247     for (int i = 0; i < nSeq; i++)
248     {
249       seqs[i] = align.getSequenceAt(i);
250       length[i] = (float) (seqs[i].getEnd() - seqs[i].getStart());
251     }
252
253     QuickSort.sort(length, seqs);
254
255     if (sortLengthAscending)
256     {
257       setReverseOrder(align, seqs);
258     }
259     else
260     {
261       setOrder(align, seqs);
262     }
263
264     sortLengthAscending = !sortLengthAscending;
265   }
266
267   /**
268    * Sorts the alignment by size of group. <br>
269    * Maintains the order of sequences in each group by order in given alignment
270    * object.
271    * 
272    * @param align
273    *          sorts the given alignment object by group
274    */
275   public static void sortByGroup(AlignmentI align)
276   {
277     // MAINTAINS ORIGNAL SEQUENCE ORDER,
278     // ORDERS BY GROUP SIZE
279     Vector groups = new Vector();
280
281     if (groups.hashCode() != lastGroupHash)
282     {
283       sortGroupAscending = true;
284       lastGroupHash = groups.hashCode();
285     }
286     else
287     {
288       sortGroupAscending = !sortGroupAscending;
289     }
290
291     // SORTS GROUPS BY SIZE
292     // ////////////////////
293     for (int i = 0; i < align.getGroups().size(); i++)
294     {
295       SequenceGroup sg = (SequenceGroup) align.getGroups().elementAt(i);
296
297       for (int j = 0; j < groups.size(); j++)
298       {
299         SequenceGroup sg2 = (SequenceGroup) groups.elementAt(j);
300
301         if (sg.getSize() > sg2.getSize())
302         {
303           groups.insertElementAt(sg, j);
304
305           break;
306         }
307       }
308
309       if (!groups.contains(sg))
310       {
311         groups.addElement(sg);
312       }
313     }
314
315     // NOW ADD SEQUENCES MAINTAINING ALIGNMENT ORDER
316     // /////////////////////////////////////////////
317     Vector seqs = new Vector();
318
319     for (int i = 0; i < groups.size(); i++)
320     {
321       SequenceGroup sg = (SequenceGroup) groups.elementAt(i);
322       SequenceI[] orderedseqs = sg.getSequencesInOrder(align);
323
324       for (int j = 0; j < orderedseqs.length; j++)
325       {
326         seqs.addElement(orderedseqs[j]);
327       }
328     }
329
330     if (sortGroupAscending)
331     {
332       setOrder(align, seqs);
333     }
334     else
335     {
336       setReverseOrder(align,
337               vectorSubsetToArray(seqs, align.getSequences()));
338     }
339   }
340
341   /**
342    * Converts Vector to array. java 1.18 does not have Vector.toArray()
343    * 
344    * @param tmp
345    *          Vector of SequenceI objects
346    * 
347    * @return array of Sequence[]
348    */
349   private static SequenceI[] vectorToArray(Vector tmp)
350   {
351     SequenceI[] seqs = new SequenceI[tmp.size()];
352
353     for (int i = 0; i < tmp.size(); i++)
354     {
355       seqs[i] = (SequenceI) tmp.elementAt(i);
356     }
357
358     return seqs;
359   }
360
361   /**
362    * DOCUMENT ME!
363    * 
364    * @param tmp
365    *          DOCUMENT ME!
366    * @param mask
367    *          DOCUMENT ME!
368    * 
369    * @return DOCUMENT ME!
370    */
371   private static SequenceI[] vectorSubsetToArray(Vector tmp, Vector mask)
372   {
373     Vector seqs = new Vector();
374     int i, idx;
375     boolean[] tmask = new boolean[mask.size()];
376
377     for (i = 0; i < mask.size(); i++)
378     {
379       tmask[i] = true;
380     }
381
382     for (i = 0; i < tmp.size(); i++)
383     {
384       Object sq = tmp.elementAt(i);
385       idx = mask.indexOf(sq);
386       if (idx > -1 && tmask[idx])
387       {
388         tmask[idx] = false;
389         seqs.addElement(sq);
390       }
391     }
392
393     for (i = 0; i < tmask.length; i++)
394     {
395       if (tmask[i])
396       {
397         seqs.addElement(mask.elementAt(i));
398       }
399     }
400
401     return vectorToArray(seqs);
402   }
403
404   /**
405    * Sorts by a given AlignmentOrder object
406    * 
407    * @param align
408    *          Alignment to order
409    * @param order
410    *          specified order for alignment
411    */
412   public static void sortBy(AlignmentI align, AlignmentOrder order)
413   {
414     // Get an ordered vector of sequences which may also be present in align
415     Vector tmp = order.getOrder();
416
417     if (lastOrder == order)
418     {
419       sortOrderAscending = !sortOrderAscending;
420     }
421     else
422     {
423       sortOrderAscending = true;
424     }
425
426     if (sortOrderAscending)
427     {
428       setOrder(align, tmp);
429     }
430     else
431     {
432       setReverseOrder(align, vectorSubsetToArray(tmp, align.getSequences()));
433     }
434   }
435
436   /**
437    * DOCUMENT ME!
438    * 
439    * @param align
440    *          alignment to order
441    * @param tree
442    *          tree which has
443    * 
444    * @return DOCUMENT ME!
445    */
446   private static Vector getOrderByTree(AlignmentI align, NJTree tree)
447   {
448     int nSeq = align.getHeight();
449
450     Vector tmp = new Vector();
451
452     tmp = _sortByTree(tree.getTopNode(), tmp, align.getSequences());
453
454     if (tmp.size() != nSeq)
455     {
456       // TODO: JBPNote - decide if this is always an error
457       // (eg. not when a tree is associated to another alignment which has more
458       // sequences)
459       if (tmp.size() != nSeq)
460       {
461         addStrays(align, tmp);
462       }
463
464       if (tmp.size() != nSeq)
465       {
466         System.err.println("WARNING: tmp.size()=" + tmp.size() + " != nseq="
467                 + nSeq + " in getOrderByTree - tree contains sequences not in alignment");
468       }
469     }
470
471     return tmp;
472   }
473
474   /**
475    * Sorts the alignment by a given tree
476    * 
477    * @param align
478    *          alignment to order
479    * @param tree
480    *          tree which has
481    */
482   public static void sortByTree(AlignmentI align, NJTree tree)
483   {
484     Vector tmp = getOrderByTree(align, tree);
485
486     // tmp should properly permute align with tree.
487     if (lastTree != tree)
488     {
489       sortTreeAscending = true;
490       lastTree = tree;
491     }
492     else
493     {
494       sortTreeAscending = !sortTreeAscending;
495     }
496
497     if (sortTreeAscending)
498     {
499       setOrder(align, tmp);
500     }
501     else
502     {
503       setReverseOrder(align, vectorSubsetToArray(tmp, align.getSequences()));
504     }
505   }
506
507   /**
508    * DOCUMENT ME!
509    * 
510    * @param align
511    *          DOCUMENT ME!
512    * @param seqs
513    *          DOCUMENT ME!
514    */
515   private static void addStrays(AlignmentI align, Vector seqs)
516   {
517     int nSeq = align.getHeight();
518
519     for (int i = 0; i < nSeq; i++)
520     {
521       if (!seqs.contains(align.getSequenceAt(i)))
522       {
523         seqs.addElement(align.getSequenceAt(i));
524       }
525     }
526
527     if (nSeq != seqs.size())
528     {
529       System.err
530               .println("ERROR: Size still not right even after addStrays");
531     }
532   }
533
534   /**
535    * DOCUMENT ME!
536    * 
537    * @param node
538    *          DOCUMENT ME!
539    * @param tmp
540    *          DOCUMENT ME!
541    * @param seqset
542    *          DOCUMENT ME!
543    * 
544    * @return DOCUMENT ME!
545    */
546   private static Vector _sortByTree(SequenceNode node, Vector tmp,
547           Vector seqset)
548   {
549     if (node == null)
550     {
551       return tmp;
552     }
553
554     SequenceNode left = (SequenceNode) node.left();
555     SequenceNode right = (SequenceNode) node.right();
556
557     if ((left == null) && (right == null))
558     {
559       if (!node.isPlaceholder() && (node.element() != null))
560       {
561         if (node.element() instanceof SequenceI)
562         {
563           if (!tmp.contains(node.element())) //  && (seqset==null || seqset.size()==0 || seqset.contains(tmp)))
564           {
565             tmp.addElement((SequenceI) node.element());
566           }
567         }
568       }
569
570       return tmp;
571     }
572     else
573     {
574       _sortByTree(left, tmp, seqset);
575       _sortByTree(right, tmp, seqset);
576     }
577
578     return tmp;
579   }
580
581   // Ordering Objects
582   // Alignment.sortBy(OrderObj) - sequence of sequence pointer refs in
583   // appropriate order
584   //
585
586   /**
587    * recover the order of sequences given by the safe numbering scheme introducd
588    * SeqsetUtils.uniquify.
589    */
590   public static void recoverOrder(SequenceI[] alignment)
591   {
592     float[] ids = new float[alignment.length];
593
594     for (int i = 0; i < alignment.length; i++)
595     {
596       ids[i] = (new Float(alignment[i].getName().substring(8)))
597               .floatValue();
598     }
599
600     jalview.util.QuickSort.sort(ids, alignment);
601   }
602
603   /**
604    * Sort sequence in order of increasing score attribute for annotation with a
605    * particular scoreLabel. Or reverse if same label was used previously
606    * 
607    * @param scoreLabel
608    *          exact label for sequence associated AlignmentAnnotation scores to
609    *          use for sorting.
610    * @param alignment
611    *          sequences to be sorted
612    */
613   public static void sortByAnnotationScore(String scoreLabel,
614           AlignmentI alignment)
615   {
616     SequenceI[] seqs = alignment.getSequencesArray();
617     boolean[] hasScore = new boolean[seqs.length]; // per sequence score
618     // presence
619     int hasScores = 0; // number of scores present on set
620     double[] scores = new double[seqs.length];
621     double min = 0, max = 0;
622     for (int i = 0; i < seqs.length; i++)
623     {
624       AlignmentAnnotation[] scoreAnn = seqs[i].getAnnotation(scoreLabel);
625       if (scoreAnn != null)
626       {
627         hasScores++;
628         hasScore[i] = true;
629         scores[i] = scoreAnn[0].getScore(); // take the first instance of this
630         // score.
631         if (hasScores == 1)
632         {
633           max = min = scores[i];
634         }
635         else
636         {
637           if (max < scores[i])
638           {
639             max = scores[i];
640           }
641           if (min > scores[i])
642           {
643             min = scores[i];
644           }
645         }
646       }
647       else
648       {
649         hasScore[i] = false;
650       }
651     }
652     if (hasScores == 0)
653     {
654       return; // do nothing - no scores present to sort by.
655     }
656     if (hasScores < seqs.length)
657     {
658       for (int i = 0; i < seqs.length; i++)
659       {
660         if (!hasScore[i])
661         {
662           scores[i] = (max + i + 1.0);
663         }
664       }
665     }
666
667     jalview.util.QuickSort.sort(scores, seqs);
668     if (lastSortByScore != scoreLabel)
669     {
670       lastSortByScore = scoreLabel;
671       setOrder(alignment, seqs);
672     }
673     else
674     {
675       setReverseOrder(alignment, seqs);
676     }
677   }
678
679   /**
680    * types of feature ordering: Sort by score : average score - or total score -
681    * over all features in region Sort by feature label text: (or if null -
682    * feature type text) - numerical or alphabetical Sort by feature density:
683    * based on counts - ignoring individual text or scores for each feature
684    */
685   public static String FEATURE_SCORE = "average_score";
686
687   public static String FEATURE_LABEL = "text";
688
689   public static String FEATURE_DENSITY = "density";
690
691   /**
692    * sort the alignment using the features on each sequence found between start
693    * and stop with the given featureLabel (and optional group qualifier)
694    * 
695    * @param featureLabel
696    *          (may not be null)
697    * @param groupLabel
698    *          (may be null)
699    * @param start
700    *          (-1 to include non-positional features)
701    * @param stop
702    *          (-1 to only sort on non-positional features)
703    * @param alignment
704    *          - aligned sequences containing features
705    * @param method
706    *          - one of the string constants FEATURE_SCORE, FEATURE_LABEL,
707    *          FEATURE_DENSITY
708    */
709   public static void sortByFeature(String featureLabel, String groupLabel,
710           int start, int stop, AlignmentI alignment, String method)
711   {
712     sortByFeature(featureLabel == null ? null : new String[]
713     { featureLabel }, groupLabel == null ? null : new String[]
714     { groupLabel }, start, stop, alignment, method);
715   }
716
717   private static boolean containsIgnoreCase(final String lab,
718           final String[] labs)
719   {
720     if (labs == null)
721     {
722       return true;
723     }
724     if (lab == null)
725     {
726       return false;
727     }
728     for (int q = 0; q < labs.length; q++)
729     {
730       if (labs[q] != null && lab.equalsIgnoreCase(labs[q]))
731       {
732         return true;
733       }
734     }
735     return false;
736   }
737
738   public static void sortByFeature(String[] featureLabels,
739           String[] groupLabels, int start, int stop, AlignmentI alignment,
740           String method)
741   {
742     if (method != FEATURE_SCORE && method != FEATURE_LABEL
743             && method != FEATURE_DENSITY)
744     {
745       throw new Error(
746               "Implementation Error - sortByFeature method must be one of FEATURE_SCORE, FEATURE_LABEL or FEATURE_DENSITY.");
747     }
748     boolean ignoreScore = method != FEATURE_SCORE;
749     StringBuffer scoreLabel = new StringBuffer();
750     scoreLabel.append(start + stop + method);
751     // This doesn't quite work yet - we'd like to have a canonical ordering that
752     // can be preserved from call to call
753     for (int i = 0; featureLabels != null && i < featureLabels.length; i++)
754     {
755       scoreLabel.append(featureLabels[i] == null ? "null"
756               : featureLabels[i]);
757     }
758     for (int i = 0; groupLabels != null && i < groupLabels.length; i++)
759     {
760       scoreLabel.append(groupLabels[i] == null ? "null" : groupLabels[i]);
761     }
762     SequenceI[] seqs = alignment.getSequencesArray();
763
764     boolean[] hasScore = new boolean[seqs.length]; // per sequence score
765     // presence
766     int hasScores = 0; // number of scores present on set
767     double[] scores = new double[seqs.length];
768     int[] seqScores = new int[seqs.length];
769     Object[] feats = new Object[seqs.length];
770     double min = 0, max = 0;
771     for (int i = 0; i < seqs.length; i++)
772     {
773       SequenceFeature[] sf = seqs[i].getSequenceFeatures();
774       if (sf == null && seqs[i].getDatasetSequence() != null)
775       {
776         sf = seqs[i].getDatasetSequence().getSequenceFeatures();
777       }
778       if (sf == null)
779       {
780         sf = new SequenceFeature[0];
781       }
782       else
783       {
784         SequenceFeature[] tmp = new SequenceFeature[sf.length];
785         for (int s = 0; s < tmp.length; s++)
786         {
787           tmp[s] = sf[s];
788         }
789         sf = tmp;
790       }
791       int sstart = (start == -1) ? start : seqs[i].findPosition(start);
792       int sstop = (stop == -1) ? stop : seqs[i].findPosition(stop);
793       seqScores[i] = 0;
794       scores[i] = 0.0;
795       int n = sf.length;
796       for (int f = 0; f < sf.length; f++)
797       {
798         // filter for selection criteria
799         if (
800         // ignore features outwith alignment start-stop positions.
801         (sf[f].end < sstart || sf[f].begin > sstop) ||
802         // or ignore based on selection criteria
803                 (featureLabels != null && !AlignmentSorter
804                         .containsIgnoreCase(sf[f].type, featureLabels))
805                 || (groupLabels != null
806                 // problem here: we cannot eliminate null feature group features
807                 && (sf[f].getFeatureGroup() != null && !AlignmentSorter
808                         .containsIgnoreCase(sf[f].getFeatureGroup(),
809                                 groupLabels))))
810         {
811           // forget about this feature
812           sf[f] = null;
813           n--;
814         }
815         else
816         {
817           // or, also take a look at the scores if necessary.
818           if (!ignoreScore && sf[f].getScore() != Float.NaN)
819           {
820             if (seqScores[i] == 0)
821             {
822               hasScores++;
823             }
824             seqScores[i]++;
825             hasScore[i] = true;
826             scores[i] += sf[f].getScore(); // take the first instance of this
827             // score.
828           }
829         }
830       }
831       SequenceFeature[] fs;
832       feats[i] = fs = new SequenceFeature[n];
833       if (n > 0)
834       {
835         n = 0;
836         for (int f = 0; f < sf.length; f++)
837         {
838           if (sf[f] != null)
839           {
840             ((SequenceFeature[]) feats[i])[n++] = sf[f];
841           }
842         }
843         if (method == FEATURE_LABEL)
844         {
845           // order the labels by alphabet
846           String[] labs = new String[fs.length];
847           for (int l = 0; l < labs.length; l++)
848           {
849             labs[l] = (fs[l].getDescription() != null ? fs[l]
850                     .getDescription() : fs[l].getType());
851           }
852           jalview.util.QuickSort.sort(labs, ((Object[]) feats[i]));
853         }
854       }
855       if (hasScore[i])
856       {
857         // compute average score
858         scores[i] /= seqScores[i];
859         // update the score bounds.
860         if (hasScores == 1)
861         {
862           max = min = scores[i];
863         }
864         else
865         {
866           if (max < scores[i])
867           {
868             max = scores[i];
869           }
870           if (min > scores[i])
871           {
872             min = scores[i];
873           }
874         }
875       }
876     }
877
878     if (method == FEATURE_SCORE)
879     {
880       if (hasScores == 0)
881       {
882         return; // do nothing - no scores present to sort by.
883       }
884       // pad score matrix
885       if (hasScores < seqs.length)
886       {
887         for (int i = 0; i < seqs.length; i++)
888         {
889           if (!hasScore[i])
890           {
891             scores[i] = (max + 1 + i);
892           }
893           else
894           {
895             int nf = (feats[i] == null) ? 0
896                     : ((SequenceFeature[]) feats[i]).length;
897             // System.err.println("Sorting on Score: seq "+seqs[i].getName()+
898             // " Feats: "+nf+" Score : "+scores[i]);
899           }
900         }
901       }
902
903       jalview.util.QuickSort.sort(scores, seqs);
904     }
905     else if (method == FEATURE_DENSITY)
906     {
907
908       // break ties between equivalent numbers for adjacent sequences by adding
909       // 1/Nseq*i on the original order
910       double fr = 0.9 / (1.0 * seqs.length);
911       for (int i = 0; i < seqs.length; i++)
912       {
913         double nf;
914         scores[i] = (0.05 + fr * i)
915                 + (nf = ((feats[i] == null) ? 0.0
916                         : 1.0 * ((SequenceFeature[]) feats[i]).length));
917         // System.err.println("Sorting on Density: seq "+seqs[i].getName()+
918         // " Feats: "+nf+" Score : "+scores[i]);
919       }
920       jalview.util.QuickSort.sort(scores, seqs);
921     }
922     else
923     {
924       if (method == FEATURE_LABEL)
925       {
926         throw new Error("Not yet implemented.");
927       }
928     }
929     if (lastSortByFeatureScore == null
930             || !scoreLabel.toString().equals(lastSortByFeatureScore))
931     {
932       sortByFeatureScoreAscending = true;
933     }
934     else
935     {
936       sortByFeatureScoreAscending = !sortByFeatureScoreAscending;
937     }
938     if (sortByFeatureScoreAscending)
939     {
940       setOrder(alignment, seqs);
941     }
942     else
943     {
944       setReverseOrder(alignment, seqs);
945     }
946     lastSortByFeatureScore = scoreLabel.toString();
947   }
948
949 }