package jalview.analysis;

import jalview.datamodel.*;
import jalview.util.*;
import jalview.io.*;

import java.util.*;

/** Data structure to hold and manipulate a multiple sequence alignment
 */
public class AlignmentSorter {

  private AlignmentSorter() {
    try
    {
      jbInit();
    }
    catch (Exception ex)
    {
      ex.printStackTrace();
    }
  }

  public static void sortGroups(AlignmentI align) {
    Vector groups = align.getGroups();
    int    nGroup = groups.size();

    float[]  arr = new float [nGroup];
    Object[] s   = new Object[nGroup];

    for (int i=0; i < nGroup; i++) {
      arr[i] = ((SequenceGroup)groups.elementAt(i)).getSize();
      s[i]   = groups.elementAt(i);
    }

    QuickSort.sort(arr,s);

    Vector newg = new Vector(nGroup);

    for (int i=nGroup-1; i >= 0; i--) {
      newg.addElement(s[i]);
    }

    //    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();

    float     scores[] = new float[nSeq];
    SequenceI seqs[]   = new SequenceI[nSeq];

    for (int i = 0; i < nSeq; i++) {
      scores[i] = Comparison.PID(align.getSequenceAt(i),s);
      seqs[i]   = align.getSequenceAt(i);
    }

    QuickSort.sort(scores,0,scores.length-1,seqs);

   setReverseOrder(align,seqs);
  }

  private static void setReverseOrder(AlignmentI align, SequenceI [] seqs) {
    int nSeq = seqs.length;

    int len = 0;
    if (nSeq%2 == 0) {
      len = nSeq/2;
    } else {
      len = (nSeq+1)/2;
    }

// NOTE: DO NOT USE align.setSequenceAt() here - it will NOT work
    for (int i = 0; i < len; i++) {
      //SequenceI tmp = seqs[i];
      align.getSequences().setElementAt(seqs[nSeq-i-1],i);
      align.getSequences().setElementAt(seqs[i],nSeq-i-1);
    }
  }

  private static void setOrder(AlignmentI align, Vector 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

      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) {
    int nSeq = align.getHeight();

    String    ids[]   = new String[nSeq];
    SequenceI seqs[]  = new SequenceI[nSeq];

    for (int i = 0; i < nSeq; i++) {
      ids[i]  = align.getSequenceAt(i).getName();
      seqs[i] = align.getSequenceAt(i);
    }

    QuickSort.sort(ids,seqs);

    if(sortIdAscending)
      setReverseOrder(align,seqs);
    else
      setOrder(align, seqs);

    sortIdAscending = !sortIdAscending;
  }
  static int lastGroupHash = 0;
  static boolean sortGroupAscending = true;

  public static void sortByGroup(AlignmentI align) {
    int    nSeq = align.getHeight();
    Vector groups = align.getGroups();
    if (groups.hashCode()!=lastGroupHash) {
      sortGroupAscending=true;
      lastGroupHash = groups.hashCode();
    } else
      sortGroupAscending = ! sortGroupAscending;

    Vector seqs = new Vector();

    for (int i=0; i < groups.size(); i++) {
      SequenceGroup sg = (SequenceGroup)groups.elementAt(i);

      for (int j = 0; j < sg.getSize(); j++) {
        seqs.addElement(sg.getSequenceAt(j));
      }
    }

    // Deletions can happen so this check may fail
    /*
     if (seqs.size() != nSeq) {
      System.err.println("ERROR: tmp.size() != nseq in sortByGroups");
      if (seqs.size() < nSeq) {
        addStrays(align,seqs);
      }
    }
*/
    if(sortGroupAscending)
      setOrder(align,seqs);
    else
      setReverseOrder( align, vectorSubsetToArray(seqs, align.getSequences()));

  }

  private static SequenceI [] vectorToArray(Vector tmp) {
    SequenceI[] seqs = new SequenceI[tmp.size()];

    for (int i=0; i < tmp.size(); i++) {
      seqs[i] = (SequenceI)tmp.elementAt(i);
    }
    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);
  }

  static AlignmentOrder lastOrder = null;
  static boolean sortOrderAscending = true;

  public static void sortBy(AlignmentI align, AlignmentOrder order) {
    // Get an ordered vector of sequences which may also be present in align
    Vector tmp = order.getOrder();
//    if (tmp.size()<align.getHeight())
//      addStrays(align, tmp);
    if (lastOrder==order)
      sortOrderAscending=!sortOrderAscending;
    else
      sortOrderAscending=true;

    if (sortOrderAscending)
      setOrder(align, tmp);
    else
      setReverseOrder(align, vectorSubsetToArray(tmp, align.getSequences()));
  }
  static NJTree lastTree = null;
  static boolean sortTreeAscending = true;

  public static Vector getOrderByTree(AlignmentI align, NJTree tree) {
    int nSeq = align.getHeight();

    Vector tmp = new Vector();

    tmp = _sortByTree(tree.getTopNode(), tmp, align.getSequences());

    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(lastTree!=tree) {
      sortTreeAscending = true;
      lastTree = tree;
    } else {
      sortTreeAscending = !sortTreeAscending;
    }
    if(sortTreeAscending)
      setOrder(align,tmp);
    else
      setReverseOrder(align, vectorSubsetToArray(tmp, align.getSequences()));
  }

  private static void addStrays(AlignmentI align, Vector seqs) {
    int    nSeq = align.getHeight();
    for (int i=0;i<nSeq;i++) {
      if (!seqs.contains(align.getSequenceAt(i))) {
        seqs.addElement(align.getSequenceAt(i));
      }
    }
    if (nSeq != seqs.size()) {
      System.err.println("ERROR: Size still not right even after addStrays");
    }
  }

  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.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, 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);
  }

  private void jbInit()
      throws Exception
  {
  }

}