src/jalview/analysis/AlignmentSorter.java

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