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

// 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];
                }
        }






}