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