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