// SimpleTree.java
//
// (c) 1999-2001 PAL Development Core Team
//
// This package may be distributed under the
// terms of the Lesser GNU General Public License (LGPL)


package de.ugoe.cs.autoquest.tasktrees.alignment.pal.tree;

import de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc.Identifier;




/**
 * data structure for a binary/non-binary rooted/unrooted trees
 *
 * @version $Id: SimpleTree.java,v 1.19 2002/01/13 23:13:24 matt Exp $
 *
 * @author Alexei Drummond
 * @author Korbinian Strimmer
 *
 */
public class SimpleTree implements Tree
{
	//
	// This class has explicit serialization code so if you alter any fields please alter
	// the serialization code too (make sure you use a new version number - see readObject/writeObject
	// Thanks, Matthew

	//
	// Public stuff
	//

	//
	// Private stuff
	/** root node */
	private Node root;

	/** list of internal nodes (including root) */
	private Node[] internalNode = null;

	/** number of internal nodes (including root) */
	private int numInternalNodes;

	/** list of external nodes */
	private Node[] externalNode = null;

	/** number of external nodes */
	private int numExternalNodes;

	/** constructor tree consisting solely of root node */
	public SimpleTree() {

		// Default configuration
		root = new FengDoolittleNode();
		root.setIdentifier(new Identifier("ROOT"));
		root.setBranchLength(0.0);
		root.setBranchLengthSE(0.0);
	}

	/** constructor taking a root node */
	public SimpleTree(Node r) {

		root = r;
		createNodeList();
	}


	/**
	 * Returns the number of external nodes.
	 */
	public final int getExternalNodeCount() {
		if(externalNode==null) {
			createNodeList();
		}
		return numExternalNodes;
	}

	/**
	 * Returns the ith external node.
	 */
	public final Node getExternalNode(int i) {
		if(externalNode==null) {
			createNodeList();
		}
		return externalNode[i];
	}

	/**
	 * Returns the number of internal nodes.
	 */
	public final int getInternalNodeCount() {
		if(internalNode==null) {
			createNodeList();
		}
		return numInternalNodes;
	}

	/**
	 * Returns the ith internal node.
	 */
	public final Node getInternalNode(int i) {
		if(internalNode==null) {
			createNodeList();
		}
		return internalNode[i];
	}

	/**
	 * Returns the root node of this tree.
	 */
	public final Node getRoot() {
		return root;
	}

	/**
	 * Set a new node as root node.
	 */
	public final void setRoot(Node r) {
		root = r;
		createNodeList();
	}

	/** count and list external and internal nodes and
		compute heights of each node */
	public void createNodeList()
	{
		numInternalNodes = 0;
		numExternalNodes = 0;
		Node node = root;
		do
		{
			node = NodeUtils.postorderSuccessor(node);
			if (node.isLeaf())
			{
				node.setNumber(numExternalNodes);
				numExternalNodes++;
			}
			else
			{
				node.setNumber(numInternalNodes);
				numInternalNodes++;
			}
		}
		while(node != root);

		internalNode = new Node[numInternalNodes];
		externalNode = new Node[numExternalNodes];
		node = root;
		do
		{
			node = NodeUtils.postorderSuccessor(node);
			if (node.isLeaf())
			{
				externalNode[node.getNumber()] = node;
			}
			else
			{
				internalNode[node.getNumber()] = node;
			}
		}
		while(node != root);

		// compute heights if it seems necessary
		if (root.getNodeHeight() == 0.0) {
			NodeUtils.lengths2Heights(root);
		}
	}

	/**
	 * return node with number num (as displayed in ASCII tree)
	 *
	 * @param num number of node
	 *
	 * @return node
	 */
	public Node findNode(int num)
	{
		createNodeList();

		if (num <= numExternalNodes)
		{
			return externalNode[num-1];
		}
		else
		{
			return internalNode[num-1-numExternalNodes];
		}
	}






}