2fad332458ff5f63f5a3f7d4bdc3b28a180e6006
[jalview.git] / 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,
555           List<SequenceI> seqset)
556   {
557     if (node == null)
558     {
559       return tmp;
560     }
561
562     SequenceNode left = (SequenceNode) node.left();
563     SequenceNode right = (SequenceNode) node.right();
564
565     if ((left == null) && (right == null))
566     {
567       if (!node.isPlaceholder() && (node.element() != null))
568       {
569         if (node.element() instanceof SequenceI)
570         {
571           if (!tmp.contains(node.element())) // && (seqset==null ||
572                                              // seqset.size()==0 ||
573                                              // seqset.contains(tmp)))
574           {
575             tmp.add((SequenceI) node.element());
576           }
577         }
578       }
579
580       return tmp;
581     }
582     else
583     {
584       _sortByTree(left, tmp, seqset);
585       _sortByTree(right, tmp, seqset);
586     }
587
588     return tmp;
589   }
590
591   // Ordering Objects
592   // Alignment.sortBy(OrderObj) - sequence of sequence pointer refs in
593   // appropriate order
594   //
595
596   /**
597    * recover the order of sequences given by the safe numbering scheme introducd
598    * SeqsetUtils.uniquify.
599    */
600   public static void recoverOrder(SequenceI[] alignment)
601   {
602     float[] ids = new float[alignment.length];
603
604     for (int i = 0; i < alignment.length; i++)
605     {
606       ids[i] = (new Float(alignment[i].getName().substring(8)))
607               .floatValue();
608     }
609
610     jalview.util.QuickSort.sort(ids, alignment);
611   }
612
613   /**
614    * Sort sequence in order of increasing score attribute for annotation with a
615    * particular scoreLabel. Or reverse if same label was used previously
616    * 
617    * @param scoreLabel
618    *          exact label for sequence associated AlignmentAnnotation scores to
619    *          use for sorting.
620    * @param alignment
621    *          sequences to be sorted
622    */
623   public static void sortByAnnotationScore(String scoreLabel,
624           AlignmentI alignment)
625   {
626     SequenceI[] seqs = alignment.getSequencesArray();
627     boolean[] hasScore = new boolean[seqs.length]; // per sequence score
628     // presence
629     int hasScores = 0; // number of scores present on set
630     double[] scores = new double[seqs.length];
631     double min = 0, max = 0;
632     for (int i = 0; i < seqs.length; i++)
633     {
634       AlignmentAnnotation[] scoreAnn = seqs[i].getAnnotation(scoreLabel);
635       if (scoreAnn != null)
636       {
637         hasScores++;
638         hasScore[i] = true;
639         scores[i] = scoreAnn[0].getScore(); // take the first instance of this
640         // score.
641         if (hasScores == 1)
642         {
643           max = min = scores[i];
644         }
645         else
646         {
647           if (max < scores[i])
648           {
649             max = scores[i];
650           }
651           if (min > scores[i])
652           {
653             min = scores[i];
654           }
655         }
656       }
657       else
658       {
659         hasScore[i] = false;
660       }
661     }
662     if (hasScores == 0)
663     {
664       return; // do nothing - no scores present to sort by.
665     }
666     if (hasScores < seqs.length)
667     {
668       for (int i = 0; i < seqs.length; i++)
669       {
670         if (!hasScore[i])
671         {
672           scores[i] = (max + i + 1.0);
673         }
674       }
675     }
676
677     jalview.util.QuickSort.sort(scores, seqs);
678     if (lastSortByScore != scoreLabel)
679     {
680       lastSortByScore = scoreLabel;
681       setOrder(alignment, seqs);
682     }
683     else
684     {
685       setReverseOrder(alignment, seqs);
686     }
687   }
688
689   /**
690    * types of feature ordering: Sort by score : average score - or total score -
691    * over all features in region Sort by feature label text: (or if null -
692    * feature type text) - numerical or alphabetical Sort by feature density:
693    * based on counts - ignoring individual text or scores for each feature
694    */
695   public static String FEATURE_SCORE = "average_score";
696
697   public static String FEATURE_LABEL = "text";
698
699   public static String FEATURE_DENSITY = "density";
700
701   /**
702    * sort the alignment using the features on each sequence found between start
703    * and stop with the given featureLabel (and optional group qualifier)
704    * 
705    * @param featureLabel
706    *          (may not be null)
707    * @param groupLabel
708    *          (may be null)
709    * @param start
710    *          (-1 to include non-positional features)
711    * @param stop
712    *          (-1 to only sort on non-positional features)
713    * @param alignment
714    *          - aligned sequences containing features
715    * @param method
716    *          - one of the string constants FEATURE_SCORE, FEATURE_LABEL,
717    *          FEATURE_DENSITY
718    */
719   public static void sortByFeature(String featureLabel, String groupLabel,
720           int start, int stop, AlignmentI alignment, String method)
721   {
722     sortByFeature(featureLabel == null ? null : new String[]
723     { featureLabel }, groupLabel == null ? null : new String[]
724     { groupLabel }, start, stop, alignment, method);
725   }
726
727   private static boolean containsIgnoreCase(final String lab,
728           final String[] labs)
729   {
730     if (labs == null)
731     {
732       return true;
733     }
734     if (lab == null)
735     {
736       return false;
737     }
738     for (int q = 0; q < labs.length; q++)
739     {
740       if (labs[q] != null && lab.equalsIgnoreCase(labs[q]))
741       {
742         return true;
743       }
744     }
745     return false;
746   }
747
748   public static void sortByFeature(String[] featureLabels,
749           String[] groupLabels, int start, int stop, AlignmentI alignment,
750           String method)
751   {
752     if (method != FEATURE_SCORE && method != FEATURE_LABEL
753             && method != FEATURE_DENSITY)
754     {
755       throw new Error(MessageManager.getString("error.implementation_error_sortbyfeature"));
756     }
757     boolean ignoreScore = method != FEATURE_SCORE;
758     StringBuffer scoreLabel = new StringBuffer();
759     scoreLabel.append(start + stop + method);
760     // This doesn't quite work yet - we'd like to have a canonical ordering that
761     // can be preserved from call to call
762     for (int i = 0; featureLabels != null && i < featureLabels.length; i++)
763     {
764       scoreLabel.append(featureLabels[i] == null ? "null"
765               : featureLabels[i]);
766     }
767     for (int i = 0; groupLabels != null && i < groupLabels.length; i++)
768     {
769       scoreLabel.append(groupLabels[i] == null ? "null" : groupLabels[i]);
770     }
771     SequenceI[] seqs = alignment.getSequencesArray();
772
773     boolean[] hasScore = new boolean[seqs.length]; // per sequence score
774     // presence
775     int hasScores = 0; // number of scores present on set
776     double[] scores = new double[seqs.length];
777     int[] seqScores = new int[seqs.length];
778     Object[] feats = new Object[seqs.length];
779     double min = 0, max = 0;
780     for (int i = 0; i < seqs.length; i++)
781     {
782       SequenceFeature[] sf = seqs[i].getSequenceFeatures();
783       if (sf == null)
784       {
785         sf = new SequenceFeature[0];
786       }
787       else
788       {
789         SequenceFeature[] tmp = new SequenceFeature[sf.length];
790         for (int s = 0; s < tmp.length; s++)
791         {
792           tmp[s] = sf[s];
793         }
794         sf = tmp;
795       }
796       int sstart = (start == -1) ? start : seqs[i].findPosition(start);
797       int sstop = (stop == -1) ? stop : seqs[i].findPosition(stop);
798       seqScores[i] = 0;
799       scores[i] = 0.0;
800       int n = sf.length;
801       for (int f = 0; f < sf.length; f++)
802       {
803         // filter for selection criteria
804         if (
805         // ignore features outwith alignment start-stop positions.
806         (sf[f].end < sstart || sf[f].begin > sstop) ||
807         // or ignore based on selection criteria
808                 (featureLabels != null && !AlignmentSorter
809                         .containsIgnoreCase(sf[f].type, featureLabels))
810                 || (groupLabels != null
811                 // problem here: we cannot eliminate null feature group features
812                 && (sf[f].getFeatureGroup() != null && !AlignmentSorter
813                         .containsIgnoreCase(sf[f].getFeatureGroup(),
814                                 groupLabels))))
815         {
816           // forget about this feature
817           sf[f] = null;
818           n--;
819         }
820         else
821         {
822           // or, also take a look at the scores if necessary.
823           if (!ignoreScore && sf[f].getScore() != Float.NaN)
824           {
825             if (seqScores[i] == 0)
826             {
827               hasScores++;
828             }
829             seqScores[i]++;
830             hasScore[i] = true;
831             scores[i] += sf[f].getScore(); // take the first instance of this
832             // score.
833           }
834         }
835       }
836       SequenceFeature[] fs;
837       feats[i] = fs = new SequenceFeature[n];
838       if (n > 0)
839       {
840         n = 0;
841         for (int f = 0; f < sf.length; f++)
842         {
843           if (sf[f] != null)
844           {
845             ((SequenceFeature[]) feats[i])[n++] = sf[f];
846           }
847         }
848         if (method == FEATURE_LABEL)
849         {
850           // order the labels by alphabet
851           String[] labs = new String[fs.length];
852           for (int l = 0; l < labs.length; l++)
853           {
854             labs[l] = (fs[l].getDescription() != null ? fs[l]
855                     .getDescription() : fs[l].getType());
856           }
857           jalview.util.QuickSort.sort(labs, ((Object[]) feats[i]));
858         }
859       }
860       if (hasScore[i])
861       {
862         // compute average score
863         scores[i] /= seqScores[i];
864         // update the score bounds.
865         if (hasScores == 1)
866         {
867           max = min = scores[i];
868         }
869         else
870         {
871           if (max < scores[i])
872           {
873             max = scores[i];
874           }
875           if (min > scores[i])
876           {
877             min = scores[i];
878           }
879         }
880       }
881     }
882
883     if (method == FEATURE_SCORE)
884     {
885       if (hasScores == 0)
886       {
887         return; // do nothing - no scores present to sort by.
888       }
889       // pad score matrix
890       if (hasScores < seqs.length)
891       {
892         for (int i = 0; i < seqs.length; i++)
893         {
894           if (!hasScore[i])
895           {
896             scores[i] = (max + 1 + i);
897           }
898           else
899           {
900             int nf = (feats[i] == null) ? 0
901                     : ((SequenceFeature[]) feats[i]).length;
902             // System.err.println("Sorting on Score: seq "+seqs[i].getName()+
903             // " Feats: "+nf+" Score : "+scores[i]);
904           }
905         }
906       }
907
908       jalview.util.QuickSort.sort(scores, seqs);
909     }
910     else if (method == FEATURE_DENSITY)
911     {
912
913       // break ties between equivalent numbers for adjacent sequences by adding
914       // 1/Nseq*i on the original order
915       double fr = 0.9 / (1.0 * seqs.length);
916       for (int i = 0; i < seqs.length; i++)
917       {
918         double nf;
919         scores[i] = (0.05 + fr * i)
920                 + (nf = ((feats[i] == null) ? 0.0
921                         : 1.0 * ((SequenceFeature[]) feats[i]).length));
922         // System.err.println("Sorting on Density: seq "+seqs[i].getName()+
923         // " Feats: "+nf+" Score : "+scores[i]);
924       }
925       jalview.util.QuickSort.sort(scores, seqs);
926     }
927     else
928     {
929       if (method == FEATURE_LABEL)
930       {
931         throw new Error(MessageManager.getString("error.not_yet_implemented"));
932       }
933     }
934     if (lastSortByFeatureScore == null
935             || !scoreLabel.toString().equals(lastSortByFeatureScore))
936     {
937       sortByFeatureScoreAscending = true;
938     }
939     else
940     {
941       sortByFeatureScoreAscending = !sortByFeatureScoreAscending;
942     }
943     if (sortByFeatureScoreAscending)
944     {
945       setOrder(alignment, seqs);
946     }
947     else
948     {
949       setReverseOrder(alignment, seqs);
950     }
951     lastSortByFeatureScore = scoreLabel.toString();
952   }
953
954 }