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