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