/*
 * Jalview - A Sequence Alignment Editor and Viewer (Version 2.8)
 * Copyright (C) 2012 J Procter, AM Waterhouse, LM Lui, J Engelhardt, G Barton, M Clamp, S Searle
 * 
 * This file is part of Jalview.
 * 
 * Jalview is free software: you can redistribute it and/or
 * modify it under the terms of the GNU General Public License 
 * as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
 *  
 * Jalview is distributed in the hope that it will be useful, but 
 * WITHOUT ANY WARRANTY; without even the implied warranty 
 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR 
 * PURPOSE.  See the GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
 */
package jalview.analysis;

import java.util.*;

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

/**
 * DOCUMENT ME!
 * 
 * @author $author$
 * @version $Revision$
 */
public class NJTree
{
  Vector cluster;

  SequenceI[] sequence;

  // SequenceData is a string representation of what the user
  // sees. The display may contain hidden columns.
  public AlignmentView seqData = null;

  int[] done;

  int noseqs;

  int noClus;

  float[][] distance;

  int mini;

  int minj;

  float ri;

  float rj;

  Vector groups = new Vector();

  SequenceNode maxdist;

  SequenceNode top;

  float maxDistValue;

  float maxheight;

  int ycount;

  Vector node;

  String type;

  String pwtype;

  Object found = null;

  Object leaves = null;

  boolean hasDistances = true; // normal case for jalview trees

  boolean hasBootstrap = false; // normal case for jalview trees

  private boolean hasRootDistance = true;

  /**
   * Create a new NJTree object with leaves associated with sequences in seqs,
   * and original alignment data represented by Cigar strings.
   * 
   * @param seqs
   *          SequenceI[]
   * @param odata
   *          Cigar[]
   * @param treefile
   *          NewickFile
   */
  public NJTree(SequenceI[] seqs, AlignmentView odata, NewickFile treefile)
  {
    this(seqs, treefile);
    if (odata != null)
    {
      seqData = odata;
    }
    /*
     * sequenceString = new String[odata.length]; char gapChar =
     * jalview.util.Comparison.GapChars.charAt(0); for (int i = 0; i <
     * odata.length; i++) { SequenceI oseq_aligned = odata[i].getSeq(gapChar);
     * sequenceString[i] = oseq_aligned.getSequence(); }
     */
  }

  /**
   * Creates a new NJTree object from a tree from an external source
   * 
   * @param seqs
   *          SequenceI which should be associated with leafs of treefile
   * @param treefile
   *          A parsed tree
   */
  public NJTree(SequenceI[] seqs, NewickFile treefile)
  {
    this.sequence = seqs;
    top = treefile.getTree();

    /**
     * There is no dependent alignment to be recovered from an imported tree.
     * 
     * if (sequenceString == null) { sequenceString = new String[seqs.length];
     * for (int i = 0; i < seqs.length; i++) { sequenceString[i] =
     * seqs[i].getSequence(); } }
     */

    hasDistances = treefile.HasDistances();
    hasBootstrap = treefile.HasBootstrap();
    hasRootDistance = treefile.HasRootDistance();

    maxheight = findHeight(top);

    SequenceIdMatcher algnIds = new SequenceIdMatcher(seqs);

    Vector leaves = new Vector();
    findLeaves(top, leaves);

    int i = 0;
    int namesleft = seqs.length;

    SequenceNode j;
    SequenceI nam;
    String realnam;
    Vector one2many = new Vector();
    int countOne2Many = 0;
    while (i < leaves.size())
    {
      j = (SequenceNode) leaves.elementAt(i++);
      realnam = j.getName();
      nam = null;

      if (namesleft > -1)
      {
        nam = algnIds.findIdMatch(realnam);
      }

      if (nam != null)
      {
        j.setElement(nam);
        if (one2many.contains(nam))
        {
          countOne2Many++;
          // if (jalview.bin.Cache.log.isDebugEnabled())
          // jalview.bin.Cache.log.debug("One 2 many relationship for
          // "+nam.getName());
        }
        else
        {
          one2many.addElement(nam);
          namesleft--;
        }
      }
      else
      {
        j.setElement(new Sequence(realnam, "THISISAPLACEHLDER"));
        j.setPlaceholder(true);
      }
    }
    // if (jalview.bin.Cache.log.isDebugEnabled() && countOne2Many>0) {
    // jalview.bin.Cache.log.debug("There were "+countOne2Many+" alignment
    // sequence ids (out of "+one2many.size()+" unique ids) linked to two or
    // more leaves.");
    // }
    // one2many.clear();
  }

  /**
   * Creates a new NJTree object.
   * 
   * @param sequence
   *          DOCUMENT ME!
   * @param type
   *          DOCUMENT ME!
   * @param pwtype
   *          DOCUMENT ME!
   * @param start
   *          DOCUMENT ME!
   * @param end
   *          DOCUMENT ME!
   */
  public NJTree(SequenceI[] sequence, AlignmentView seqData, String type,
          String pwtype, int start, int end)
  {
    this.sequence = sequence;
    this.node = new Vector();
    this.type = type;
    this.pwtype = pwtype;
    if (seqData != null)
    {
      this.seqData = seqData;
    }
    else
    {
      SeqCigar[] seqs = new SeqCigar[sequence.length];
      for (int i = 0; i < sequence.length; i++)
      {
        seqs[i] = new SeqCigar(sequence[i], start, end);
      }
      CigarArray sdata = new CigarArray(seqs);
      sdata.addOperation(CigarArray.M, end - start + 1);
      this.seqData = new AlignmentView(sdata, start);
    }
    // System.err.println("Made seqData");// dbg
    if (!(type.equals("NJ")))
    {
      type = "AV";
    }

    if (!(pwtype.equals("PID")))
    {
      if (ResidueProperties.getScoreMatrix(pwtype) == null)
      {
        pwtype = "BLOSUM62";
      }
    }

    int i = 0;

    done = new int[sequence.length];

    while ((i < sequence.length) && (sequence[i] != null))
    {
      done[i] = 0;
      i++;
    }

    noseqs = i++;

    distance = findDistances(this.seqData
            .getSequenceStrings(Comparison.GapChars.charAt(0)));
    // System.err.println("Made distances");// dbg
    makeLeaves();
    // System.err.println("Made leaves");// dbg

    noClus = cluster.size();

    cluster();
    // System.err.println("Made clusters");// dbg

  }

  /**
   * Generate a string representation of the Tree
   * 
   * @return Newick File with all tree data available
   */
  public String toString()
  {
    jalview.io.NewickFile fout = new jalview.io.NewickFile(getTopNode());

    return fout.print(isHasBootstrap(), isHasDistances(),
            isHasRootDistance()); // output all data available for tree
  }

  /**
   * 
   * used when the alignment associated to a tree has changed.
   * 
   * @param list
   *          Sequence set to be associated with tree nodes
   */
  public void UpdatePlaceHolders(List<SequenceI> list)
  {
    Vector leaves = new Vector();
    findLeaves(top, leaves);

    int sz = leaves.size();
    SequenceIdMatcher seqmatcher = null;
    int i = 0;

    while (i < sz)
    {
      SequenceNode leaf = (SequenceNode) leaves.elementAt(i++);

      if (list.contains(leaf.element()))
      {
        leaf.setPlaceholder(false);
      }
      else
      {
        if (seqmatcher == null)
        {
          // Only create this the first time we need it
          SequenceI[] seqs = new SequenceI[list.size()];

          for (int j = 0; j < seqs.length; j++)
          {
            seqs[j] = (SequenceI) list.get(j);
          }

          seqmatcher = new SequenceIdMatcher(seqs);
        }

        SequenceI nam = seqmatcher.findIdMatch(leaf.getName());

        if (nam != null)
        {
          if (!leaf.isPlaceholder())
          {
            // remapping the node to a new sequenceI - should remove any refs to
            // old one.
            // TODO - make many sequenceI to one leaf mappings possible!
            // (JBPNote)
          }
          leaf.setPlaceholder(false);
          leaf.setElement(nam);
        }
        else
        {
          if (!leaf.isPlaceholder())
          {
            // Construct a new placeholder sequence object for this leaf
            leaf.setElement(new Sequence(leaf.getName(),
                    "THISISAPLACEHLDER"));
          }
          leaf.setPlaceholder(true);

        }
      }
    }
  }

  /**
   * rename any nodes according to their associated sequence. This will modify
   * the tree's metadata! (ie the original NewickFile or newly generated
   * BinaryTree's label data)
   */
  public void renameAssociatedNodes()
  {
    applyToNodes(new NodeTransformI()
    {

      @Override
      public void transform(BinaryNode node)
      {
        Object el = node.element();
        if (el != null && el instanceof SequenceI)
        {
          node.setName(((SequenceI) el).getName());
        }
      }
    });
  }

  /**
   * DOCUMENT ME!
   */
  public void cluster()
  {
    while (noClus > 2)
    {
      if (type.equals("NJ"))
      {
        findMinNJDistance();
      }
      else
      {
        findMinDistance();
      }

      Cluster c = joinClusters(mini, minj);

      done[minj] = 1;

      cluster.setElementAt(null, minj);
      cluster.setElementAt(c, mini);

      noClus--;
    }

    boolean onefound = false;

    int one = -1;
    int two = -1;

    for (int i = 0; i < noseqs; i++)
    {
      if (done[i] != 1)
      {
        if (onefound == false)
        {
          two = i;
          onefound = true;
        }
        else
        {
          one = i;
        }
      }
    }

    joinClusters(one, two);
    top = (SequenceNode) (node.elementAt(one));

    reCount(top);
    findHeight(top);
    findMaxDist(top);
  }

  /**
   * DOCUMENT ME!
   * 
   * @param i
   *          DOCUMENT ME!
   * @param j
   *          DOCUMENT ME!
   * 
   * @return DOCUMENT ME!
   */
  public Cluster joinClusters(int i, int j)
  {
    float dist = distance[i][j];

    int noi = ((Cluster) cluster.elementAt(i)).value.length;
    int noj = ((Cluster) cluster.elementAt(j)).value.length;

    int[] value = new int[noi + noj];

    for (int ii = 0; ii < noi; ii++)
    {
      value[ii] = ((Cluster) cluster.elementAt(i)).value[ii];
    }

    for (int ii = noi; ii < (noi + noj); ii++)
    {
      value[ii] = ((Cluster) cluster.elementAt(j)).value[ii - noi];
    }

    Cluster c = new Cluster(value);

    ri = findr(i, j);
    rj = findr(j, i);

    if (type.equals("NJ"))
    {
      findClusterNJDistance(i, j);
    }
    else
    {
      findClusterDistance(i, j);
    }

    SequenceNode sn = new SequenceNode();

    sn.setLeft((SequenceNode) (node.elementAt(i)));
    sn.setRight((SequenceNode) (node.elementAt(j)));

    SequenceNode tmpi = (SequenceNode) (node.elementAt(i));
    SequenceNode tmpj = (SequenceNode) (node.elementAt(j));

    if (type.equals("NJ"))
    {
      findNewNJDistances(tmpi, tmpj, dist);
    }
    else
    {
      findNewDistances(tmpi, tmpj, dist);
    }

    tmpi.setParent(sn);
    tmpj.setParent(sn);

    node.setElementAt(sn, i);

    return c;
  }

  /**
   * DOCUMENT ME!
   * 
   * @param tmpi
   *          DOCUMENT ME!
   * @param tmpj
   *          DOCUMENT ME!
   * @param dist
   *          DOCUMENT ME!
   */
  public void findNewNJDistances(SequenceNode tmpi, SequenceNode tmpj,
          float dist)
  {

    tmpi.dist = ((dist + ri) - rj) / 2;
    tmpj.dist = (dist - tmpi.dist);

    if (tmpi.dist < 0)
    {
      tmpi.dist = 0;
    }

    if (tmpj.dist < 0)
    {
      tmpj.dist = 0;
    }
  }

  /**
   * DOCUMENT ME!
   * 
   * @param tmpi
   *          DOCUMENT ME!
   * @param tmpj
   *          DOCUMENT ME!
   * @param dist
   *          DOCUMENT ME!
   */
  public void findNewDistances(SequenceNode tmpi, SequenceNode tmpj,
          float dist)
  {
    float ih = 0;
    float jh = 0;

    SequenceNode sni = tmpi;
    SequenceNode snj = tmpj;

    while (sni != null)
    {
      ih = ih + sni.dist;
      sni = (SequenceNode) sni.left();
    }

    while (snj != null)
    {
      jh = jh + snj.dist;
      snj = (SequenceNode) snj.left();
    }

    tmpi.dist = ((dist / 2) - ih);
    tmpj.dist = ((dist / 2) - jh);
  }

  /**
   * DOCUMENT ME!
   * 
   * @param i
   *          DOCUMENT ME!
   * @param j
   *          DOCUMENT ME!
   */
  public void findClusterDistance(int i, int j)
  {
    int noi = ((Cluster) cluster.elementAt(i)).value.length;
    int noj = ((Cluster) cluster.elementAt(j)).value.length;

    // New distances from cluster to others
    float[] newdist = new float[noseqs];

    for (int l = 0; l < noseqs; l++)
    {
      if ((l != i) && (l != j))
      {
        newdist[l] = ((distance[i][l] * noi) + (distance[j][l] * noj))
                / (noi + noj);
      }
      else
      {
        newdist[l] = 0;
      }
    }

    for (int ii = 0; ii < noseqs; ii++)
    {
      distance[i][ii] = newdist[ii];
      distance[ii][i] = newdist[ii];
    }
  }

  /**
   * DOCUMENT ME!
   * 
   * @param i
   *          DOCUMENT ME!
   * @param j
   *          DOCUMENT ME!
   */
  public void findClusterNJDistance(int i, int j)
  {

    // New distances from cluster to others
    float[] newdist = new float[noseqs];

    for (int l = 0; l < noseqs; l++)
    {
      if ((l != i) && (l != j))
      {
        newdist[l] = ((distance[i][l] + distance[j][l]) - distance[i][j]) / 2;
      }
      else
      {
        newdist[l] = 0;
      }
    }

    for (int ii = 0; ii < noseqs; ii++)
    {
      distance[i][ii] = newdist[ii];
      distance[ii][i] = newdist[ii];
    }
  }

  /**
   * DOCUMENT ME!
   * 
   * @param i
   *          DOCUMENT ME!
   * @param j
   *          DOCUMENT ME!
   * 
   * @return DOCUMENT ME!
   */
  public float findr(int i, int j)
  {
    float tmp = 1;

    for (int k = 0; k < noseqs; k++)
    {
      if ((k != i) && (k != j) && (done[k] != 1))
      {
        tmp = tmp + distance[i][k];
      }
    }

    if (noClus > 2)
    {
      tmp = tmp / (noClus - 2);
    }

    return tmp;
  }

  /**
   * DOCUMENT ME!
   * 
   * @return DOCUMENT ME!
   */
  public float findMinNJDistance()
  {
    float min = 100000;

    for (int i = 0; i < (noseqs - 1); i++)
    {
      for (int j = i + 1; j < noseqs; j++)
      {
        if ((done[i] != 1) && (done[j] != 1))
        {
          float tmp = distance[i][j] - (findr(i, j) + findr(j, i));

          if (tmp < min)
          {
            mini = i;
            minj = j;

            min = tmp;
          }
        }
      }
    }

    return min;
  }

  /**
   * DOCUMENT ME!
   * 
   * @return DOCUMENT ME!
   */
  public float findMinDistance()
  {
    float min = 100000;

    for (int i = 0; i < (noseqs - 1); i++)
    {
      for (int j = i + 1; j < noseqs; j++)
      {
        if ((done[i] != 1) && (done[j] != 1))
        {
          if (distance[i][j] < min)
          {
            mini = i;
            minj = j;

            min = distance[i][j];
          }
        }
      }
    }

    return min;
  }

  /**
   * DOCUMENT ME!
   * 
   * @return DOCUMENT ME!
   */
  public float[][] findDistances(String[] sequenceString)
  {
    float[][] distance = new float[noseqs][noseqs];

    if (pwtype.equals("PID"))
    {
      for (int i = 0; i < (noseqs - 1); i++)
      {
        for (int j = i; j < noseqs; j++)
        {
          if (j == i)
          {
            distance[i][i] = 0;
          }
          else
          {
            distance[i][j] = 100 - Comparison.PID(sequenceString[i],
                    sequenceString[j]);

            distance[j][i] = distance[i][j];
          }
        }
      }
    }
    else
    {
      // Pairwise substitution score (with no gap penalties)
      ScoreMatrix pwmatrix = ResidueProperties.getScoreMatrix(pwtype);
      if (pwmatrix == null)
      {
        pwmatrix = ResidueProperties.getScoreMatrix("BLOSUM62");
      }
      int maxscore = 0;
      int end = sequenceString[0].length();
      for (int i = 0; i < (noseqs - 1); i++)
      {
        for (int j = i; j < noseqs; j++)
        {
          int score = 0;

          for (int k = 0; k < end; k++)
          {
            try
            {
              score += pwmatrix.getPairwiseScore(
                      sequenceString[i].charAt(k),
                      sequenceString[j].charAt(k));
            } catch (Exception ex)
            {
              System.err.println("err creating BLOSUM62 tree");
              ex.printStackTrace();
            }
          }

          distance[i][j] = (float) score;

          if (score > maxscore)
          {
            maxscore = score;
          }
        }
      }

      for (int i = 0; i < (noseqs - 1); i++)
      {
        for (int j = i; j < noseqs; j++)
        {
          distance[i][j] = (float) maxscore - distance[i][j];
          distance[j][i] = distance[i][j];
        }
      }

    }
    return distance;

    // else
    /*
     * else if (pwtype.equals("SW")) { float max = -1;
     * 
     * for (int i = 0; i < (noseqs - 1); i++) { for (int j = i; j < noseqs; j++)
     * { AlignSeq as = new AlignSeq(sequence[i], sequence[j], "pep");
     * as.calcScoreMatrix(); as.traceAlignment(); as.printAlignment(System.out);
     * distance[i][j] = (float) as.maxscore;
     * 
     * if (max < distance[i][j]) { max = distance[i][j]; } } }
     * 
     * for (int i = 0; i < (noseqs - 1); i++) { for (int j = i; j < noseqs; j++)
     * { distance[i][j] = max - distance[i][j]; distance[j][i] = distance[i][j];
     * } } }/
     */
  }

  /**
   * DOCUMENT ME!
   */
  public void makeLeaves()
  {
    cluster = new Vector();

    for (int i = 0; i < noseqs; i++)
    {
      SequenceNode sn = new SequenceNode();

      sn.setElement(sequence[i]);
      sn.setName(sequence[i].getName());
      node.addElement(sn);

      int[] value = new int[1];
      value[0] = i;

      Cluster c = new Cluster(value);
      cluster.addElement(c);
    }
  }

  /**
   * Search for leaf nodes.
   * 
   * @param node
   *          root node to search from
   * @param leaves
   *          Vector of leaves to add leaf node objects too.
   * 
   * @return Vector of leaf nodes on binary tree
   */
  public Vector findLeaves(SequenceNode node, Vector leaves)
  {
    if (node == null)
    {
      return leaves;
    }

    if ((node.left() == null) && (node.right() == null)) // Interior node
    // detection
    {
      leaves.addElement(node);

      return leaves;
    }
    else
    {
      /*
       * TODO: Identify internal nodes... if (node.isSequenceLabel()) {
       * leaves.addElement(node); }
       */
      findLeaves((SequenceNode) node.left(), leaves);
      findLeaves((SequenceNode) node.right(), leaves);
    }

    return leaves;
  }

  /**
   * Find the leaf node with a particular ycount
   * 
   * @param node
   *          initial point on tree to search from
   * @param count
   *          value to search for
   * 
   * @return null or the node with ycound=count
   */
  public Object findLeaf(SequenceNode node, int count)
  {
    found = _findLeaf(node, count);

    return found;
  }

  /*
   * #see findLeaf(SequenceNode node, count)
   */
  public Object _findLeaf(SequenceNode node, int count)
  {
    if (node == null)
    {
      return null;
    }

    if (node.ycount == count)
    {
      found = node.element();

      return found;
    }
    else
    {
      _findLeaf((SequenceNode) node.left(), count);
      _findLeaf((SequenceNode) node.right(), count);
    }

    return found;
  }

  /**
   * printNode is mainly for debugging purposes.
   * 
   * @param node
   *          SequenceNode
   */
  public void printNode(SequenceNode node)
  {
    if (node == null)
    {
      return;
    }

    if ((node.left() == null) && (node.right() == null))
    {
      System.out
              .println("Leaf = " + ((SequenceI) node.element()).getName());
      System.out.println("Dist " + ((SequenceNode) node).dist);
      System.out.println("Boot " + node.getBootstrap());
    }
    else
    {
      System.out.println("Dist " + ((SequenceNode) node).dist);
      printNode((SequenceNode) node.left());
      printNode((SequenceNode) node.right());
    }
  }

  /**
   * DOCUMENT ME!
   * 
   * @param node
   *          DOCUMENT ME!
   */
  public void findMaxDist(SequenceNode node)
  {
    if (node == null)
    {
      return;
    }

    if ((node.left() == null) && (node.right() == null))
    {
      float dist = ((SequenceNode) node).dist;

      if (dist > maxDistValue)
      {
        maxdist = (SequenceNode) node;
        maxDistValue = dist;
      }
    }
    else
    {
      findMaxDist((SequenceNode) node.left());
      findMaxDist((SequenceNode) node.right());
    }
  }

  /**
   * DOCUMENT ME!
   * 
   * @return DOCUMENT ME!
   */
  public Vector getGroups()
  {
    return groups;
  }

  /**
   * DOCUMENT ME!
   * 
   * @return DOCUMENT ME!
   */
  public float getMaxHeight()
  {
    return maxheight;
  }

  /**
   * DOCUMENT ME!
   * 
   * @param node
   *          DOCUMENT ME!
   * @param threshold
   *          DOCUMENT ME!
   */
  public void groupNodes(SequenceNode node, float threshold)
  {
    if (node == null)
    {
      return;
    }

    if ((node.height / maxheight) > threshold)
    {
      groups.addElement(node);
    }
    else
    {
      groupNodes((SequenceNode) node.left(), threshold);
      groupNodes((SequenceNode) node.right(), threshold);
    }
  }

  /**
   * DOCUMENT ME!
   * 
   * @param node
   *          DOCUMENT ME!
   * 
   * @return DOCUMENT ME!
   */
  public float findHeight(SequenceNode node)
  {
    if (node == null)
    {
      return maxheight;
    }

    if ((node.left() == null) && (node.right() == null))
    {
      node.height = ((SequenceNode) node.parent()).height + node.dist;

      if (node.height > maxheight)
      {
        return node.height;
      }
      else
      {
        return maxheight;
      }
    }
    else
    {
      if (node.parent() != null)
      {
        node.height = ((SequenceNode) node.parent()).height + node.dist;
      }
      else
      {
        maxheight = 0;
        node.height = (float) 0.0;
      }

      maxheight = findHeight((SequenceNode) (node.left()));
      maxheight = findHeight((SequenceNode) (node.right()));
    }

    return maxheight;
  }

  /**
   * DOCUMENT ME!
   * 
   * @return DOCUMENT ME!
   */
  public SequenceNode reRoot()
  {
    if (maxdist != null)
    {
      ycount = 0;

      float tmpdist = maxdist.dist;

      // New top
      SequenceNode sn = new SequenceNode();
      sn.setParent(null);

      // New right hand of top
      SequenceNode snr = (SequenceNode) maxdist.parent();
      changeDirection(snr, maxdist);
      System.out.println("Printing reversed tree");
      printN(snr);
      snr.dist = tmpdist / 2;
      maxdist.dist = tmpdist / 2;

      snr.setParent(sn);
      maxdist.setParent(sn);

      sn.setRight(snr);
      sn.setLeft(maxdist);

      top = sn;

      ycount = 0;
      reCount(top);
      findHeight(top);
    }

    return top;
  }

  /**
   * 
   * @return true if original sequence data can be recovered
   */
  public boolean hasOriginalSequenceData()
  {
    return seqData != null;
  }

  /**
   * Returns original alignment data used for calculation - or null where not
   * available.
   * 
   * @return null or cut'n'pasteable alignment
   */
  public String printOriginalSequenceData(char gapChar)
  {
    if (seqData == null)
    {
      return null;
    }

    StringBuffer sb = new StringBuffer();
    String[] seqdatas = seqData.getSequenceStrings(gapChar);
    for (int i = 0; i < seqdatas.length; i++)
    {
      sb.append(new jalview.util.Format("%-" + 15 + "s").form(sequence[i]
              .getName()));
      sb.append(" " + seqdatas[i] + "\n");
    }
    return sb.toString();
  }

  /**
   * DOCUMENT ME!
   * 
   * @param node
   *          DOCUMENT ME!
   */
  public void printN(SequenceNode node)
  {
    if (node == null)
    {
      return;
    }

    if ((node.left() != null) && (node.right() != null))
    {
      printN((SequenceNode) node.left());
      printN((SequenceNode) node.right());
    }
    else
    {
      System.out.println(" name = "
              + ((SequenceI) node.element()).getName());
    }

    System.out.println(" dist = " + ((SequenceNode) node).dist + " "
            + ((SequenceNode) node).count + " "
            + ((SequenceNode) node).height);
  }

  /**
   * DOCUMENT ME!
   * 
   * @param node
   *          DOCUMENT ME!
   */
  public void reCount(SequenceNode node)
  {
    ycount = 0;
    _lycount = 0;
    // _lylimit = this.node.size();
    _reCount(node);
  }

  private long _lycount = 0, _lylimit = 0;

  /**
   * DOCUMENT ME!
   * 
   * @param node
   *          DOCUMENT ME!
   */
  public void _reCount(SequenceNode node)
  {
    // if (_lycount<_lylimit)
    // {
    // System.err.println("Warning: depth of _recount greater than number of nodes.");
    // }
    if (node == null)
    {
      return;
    }
    _lycount++;

    if ((node.left() != null) && (node.right() != null))
    {

      _reCount((SequenceNode) node.left());
      _reCount((SequenceNode) node.right());

      SequenceNode l = (SequenceNode) node.left();
      SequenceNode r = (SequenceNode) node.right();

      ((SequenceNode) node).count = l.count + r.count;
      ((SequenceNode) node).ycount = (l.ycount + r.ycount) / 2;
    }
    else
    {
      ((SequenceNode) node).count = 1;
      ((SequenceNode) node).ycount = ycount++;
    }
    _lycount--;
  }

  /**
   * DOCUMENT ME!
   * 
   * @param node
   *          DOCUMENT ME!
   */
  public void swapNodes(SequenceNode node)
  {
    if (node == null)
    {
      return;
    }

    SequenceNode tmp = (SequenceNode) node.left();

    node.setLeft(node.right());
    node.setRight(tmp);
  }

  /**
   * DOCUMENT ME!
   * 
   * @param node
   *          DOCUMENT ME!
   * @param dir
   *          DOCUMENT ME!
   */
  public void changeDirection(SequenceNode node, SequenceNode dir)
  {
    if (node == null)
    {
      return;
    }

    if (node.parent() != top)
    {
      changeDirection((SequenceNode) node.parent(), node);

      SequenceNode tmp = (SequenceNode) node.parent();

      if (dir == node.left())
      {
        node.setParent(dir);
        node.setLeft(tmp);
      }
      else if (dir == node.right())
      {
        node.setParent(dir);
        node.setRight(tmp);
      }
    }
    else
    {
      if (dir == node.left())
      {
        node.setParent(node.left());

        if (top.left() == node)
        {
          node.setRight(top.right());
        }
        else
        {
          node.setRight(top.left());
        }
      }
      else
      {
        node.setParent(node.right());

        if (top.left() == node)
        {
          node.setLeft(top.right());
        }
        else
        {
          node.setLeft(top.left());
        }
      }
    }
  }

  /**
   * DOCUMENT ME!
   * 
   * @return DOCUMENT ME!
   */
  public SequenceNode getMaxDist()
  {
    return maxdist;
  }

  /**
   * DOCUMENT ME!
   * 
   * @return DOCUMENT ME!
   */
  public SequenceNode getTopNode()
  {
    return top;
  }

  /**
   * 
   * @return true if tree has real distances
   */
  public boolean isHasDistances()
  {
    return hasDistances;
  }

  /**
   * 
   * @return true if tree has real bootstrap values
   */
  public boolean isHasBootstrap()
  {
    return hasBootstrap;
  }

  public boolean isHasRootDistance()
  {
    return hasRootDistance;
  }

  /**
   * apply the given transform to all the nodes in the tree.
   * 
   * @param nodeTransformI
   */
  public void applyToNodes(NodeTransformI nodeTransformI)
  {
    for (Enumeration nodes = node.elements(); nodes.hasMoreElements(); nodeTransformI
            .transform((BinaryNode) nodes.nextElement()))
      ;
  }
}

/**
 * DOCUMENT ME!
 * 
 * @author $author$
 * @version $Revision$
 */
class Cluster
{
  int[] value;

  /**
   * Creates a new Cluster object.
   * 
   * @param value
   *          DOCUMENT ME!
   */
  public Cluster(int[] value)
  {
    this.value = value;
  }
}