From 3d451fd5cf0a9d719457846257ab0ac24bf7ef2d Mon Sep 17 00:00:00 2001
From: jprocter <Jim Procter>
Date: Fri, 20 May 2005 15:17:00 +0000
Subject: [PATCH] Various sort methods added and bugs fixed (coping with
 associated trees and alignment orders from web services)

---
 src/jalview/analysis/AlignmentSorter.java |  110 +++++++++++++++++++++++------
 1 file changed, 88 insertions(+), 22 deletions(-)

diff --git a/src/jalview/analysis/AlignmentSorter.java b/src/jalview/analysis/AlignmentSorter.java
index 64682c1..48e771e 100755
--- a/src/jalview/analysis/AlignmentSorter.java
+++ b/src/jalview/analysis/AlignmentSorter.java
@@ -36,7 +36,12 @@ public class AlignmentSorter {
     //    align.setGroups(newg);
   }
 
-  /**    */
+  /**
+   * Sort by Percentage Identity
+   *
+   * @param align AlignmentI
+   * @param s SequenceI
+   */
   public static void sortByPID(AlignmentI align, SequenceI s) {
     int nSeq = align.getHeight();
 
@@ -72,16 +77,17 @@ public class AlignmentSorter {
   }
 
   private static void setOrder(AlignmentI align, Vector tmp) {
-    setOrder(align,vectorToArray(tmp));
+    setOrder(align,vectorSubsetToArray(tmp, align.getSequences()));
   }
 
   private static void setOrder(AlignmentI align, SequenceI [] seqs) {
-// NOTE: DO NOT USE align.setSequenceAt() here - it will NOT work
-    for (int i = 0; i < seqs.length; i++) {
-      align.getSequences().setElementAt(seqs[i],i);
-    }
-  }
+      // NOTE: DO NOT USE align.setSequenceAt() here - it will NOT work
 
+      Vector algn = align.getSequences();
+
+      for (int i = 0, p = 0; i < seqs.length; i++)
+        algn.setElementAt(seqs[i], p++);
+  }
   /**    */
   static boolean sortIdAscending = true;
   public static void sortByID(AlignmentI align) {
@@ -144,27 +150,70 @@ public class AlignmentSorter {
     return seqs;
   }
 
+  private static SequenceI [] vectorSubsetToArray(Vector tmp, Vector mask) {
+    Vector seqs = new Vector();
+    int i,m, p;
+    boolean[] tmask = new boolean[m=mask.size()];
+    for (i=0; i<m; i++)
+      tmask[i] = true;
+    for (i=0; i < tmp.size(); i++) {
+      Object sq;
+      if (mask.contains(sq=tmp.elementAt(i))) {
+        tmask[mask.indexOf(sq)] = false;
+        seqs.addElement(sq);
+        m--;
+      }
+    }
+    for (i=0; i<tmask.length; i++)
+      if (tmask[i])
+        seqs.addElement(mask.elementAt(i));
+    return vectorToArray(seqs);
+  }
+
+
+  public static void sortBy(AlignmentI align, AlignmentOrder order) {
+    // Get an order vector that is a proper permutation of the positions in align
+    Vector tmp = order.getOrder();
+    if (tmp.size()<align.getHeight())
+      addStrays(align, tmp);
+    setOrder(align, tmp);
+  }
+
   static boolean sortTreeAscending = true;
-  public static void sortByTree(AlignmentI align, NJTree tree) {
-    int    nSeq = align.getHeight();
+
+  public static Vector getOrderByTree(AlignmentI align, NJTree tree) {
+    int nSeq = align.getHeight();
 
     Vector tmp = new Vector();
 
-    tmp = _sortByTree(tree.getTopNode(),tmp);
+    tmp = _sortByTree(tree.getTopNode(), tmp, align.getSequences());
 
-    if (tmp.size() != nSeq) {
-      System.err.println("ERROR: tmp.size() != nseq in sortByTree");
-      if (tmp.size() < nSeq) {
-        addStrays(align,tmp);
+    if (tmp.size() != nSeq)
+    {
+      // TODO: JBPNote - decide if this is always an error
+      // (eg. not when a tree is associated to another alignment which has more
+      //  sequences)
+
+      if (tmp.size() < nSeq)
+      {
+        addStrays(align, tmp);
       }
+      if (tmp.size() != nSeq)
+        System.err.println("ERROR: tmp.size()="+tmp.size()+" != nseq="+nSeq+" in getOrderByTree");
+
     }
+    return tmp;
+  }
 
+  public static void sortByTree(AlignmentI align, NJTree tree) {
+    Vector tmp = getOrderByTree(align, tree);
+    // tmp should properly permute align with tree.
     if(sortTreeAscending)
       setOrder(align,tmp);
     else
-      setReverseOrder(align, vectorToArray(tmp));
+      setReverseOrder(align, vectorSubsetToArray(tmp, align.getSequences()));
 
-      sortTreeAscending = !sortTreeAscending;
+      sortTreeAscending = !sortTreeAscending; // JBPNote: this is totally random - have to keep last tree sort ref ...
   }
 
   private static void addStrays(AlignmentI align, Vector seqs) {
@@ -179,21 +228,38 @@ public class AlignmentSorter {
     }
   }
 
-  public static Vector _sortByTree(SequenceNode node, Vector tmp) {
+  public static Vector _sortByTree(SequenceNode node, Vector tmp, Vector seqset) {
     if (node == null) {return tmp;}
 
     SequenceNode left = (SequenceNode)node.left();
     SequenceNode right = (SequenceNode)node.right();
 
     if (left == null && right == null) {
-      if (node.element() instanceof SequenceI) {
-        tmp.addElement((SequenceI)node.element());
+      if (!node.isPlaceholder() && node.element()!=null)
+        if (node.element() instanceof SequenceI)
+          if (!tmp.contains(node.element()))
+              tmp.addElement((SequenceI)node.element());
         return tmp;
-      }
+
     } else {
-      _sortByTree(left,tmp);
-      _sortByTree(right,tmp);
+      _sortByTree(left,tmp, seqset);
+      _sortByTree(right,tmp, seqset);
     }
     return tmp;
   }
+  // Ordering Objects
+  // Alignment.sortBy(OrderObj) - sequence of sequence pointer refs in appropriate order
+  //
+
+  /**
+   * recover the order of sequences given by the safe numbering scheme introducd
+   * SeqsetUtils.uniquify.
+   */
+  public static void recoverOrder(SequenceI[] alignment) {
+    float[] ids = new float[alignment.length];
+    for (int i=0; i<alignment.length; i++)
+      ids[i] = (new Float(alignment[i].getName().substring(8))).floatValue();
+    jalview.util.QuickSort.sort(ids, alignment);
+  }
+
 }
-- 
1.7.10.2