source: branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/SimpleTree.java @ 1573

// 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 java.io.PrintWriter;
import java.io.Serializable;
import java.io.StringWriter;
import java.util.Hashtable;

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



/**
 * 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;

        /** attributes attached to this tree. */
        private Hashtable[] attributes = null;



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

        /** clone constructor */
        public SimpleTree(Tree tree)
        {
                root = new FengDoolittleNode(tree.getRoot());
                createNodeList();
        }

        /** clone constructor */
        public SimpleTree(Tree tree, boolean keepIdentifiers)
        {
                root = new FengDoolittleNode(tree.getRoot(), keepIdentifiers);
                createNodeList();
        }
        /**
         * clone constructor
         * @param lm - a label mapping use for translating the original label names into something else
         */
        public SimpleTree(Tree tree, LabelMapping lm)
        {
                root = new FengDoolittleNode(tree.getRoot(), lm);
                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];
                }
        }

        private int getIndex(Node node) {
                if (node.isLeaf()) return node.getNumber();
                return getExternalNodeCount() + node.getNumber();
        }

        /**
         * Sets an named attribute for a given node.
         * @param node the node whose attribute is being set.
         * @param name the name of the attribute.
         * @param value the new value of the attribute.
         */
        public void setAttribute(Node node, String name, Object value) {
                if (node instanceof AttributeNode) {
                        ((AttributeNode)node).setAttribute(name, value);
                } else {
                        int index = getIndex(node);
                        if (attributes == null) {
                                attributes = new Hashtable[getExternalNodeCount() + getInternalNodeCount()];
                        }
                        if (attributes[index] == null) {
                                attributes[index] = new Hashtable();
                        }
                        attributes[index].put(name, value);
                }
        }

        public String toString() {
                StringWriter sw = new StringWriter();
                NodeUtils.printNH(new PrintWriter(sw), getRoot(), false, true, 0, true);
                sw.write(";");
                return sw.toString();
        }

        /**
         * @return an object representing the named attributed for the numbered node.
         * @param node the node being interrogated.
         * @param name the name of the attribute of interest.
         */
        public Object getAttribute(Node node, String name) {
                if (node instanceof AttributeNode) {
                        return ((AttributeNode)node).getAttribute(name);
                } else {
                        int index = getIndex(node);
                        if (attributes == null || attributes[index] == null) {
                                return null;
                        }
                        return attributes[index].get(name);
                }
        }





}