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