import java.util.Vector;
import java.util.Iterator;

/**
 * LinkedTree class implements the Tree interface by means
 * of a linked structure consisting of nodes.
 *
 * @version    1.2    June 22, 2001
 * @author     Franck van Breugel
 * @see Tree
 * @see TNode
 */
public class LinkedTree implements Tree 
{
    private TNode root;  // pointer to the root of this tree
    private int size;    // size of this tree

    /** Constructs a tree with an empty node. **/
    public LinkedTree() 
    {
        root = new TNode();
        size = 1;
    }

    /**
     * Constructs a tree consisting of a single node storing the
     * specified element.
     * @param element The element stored in the root.
     */
    public LinkedTree(Object element) 
    {
        root = new TNode(element, null, new Vector());
        size = 1;
    }

    /**
     * Constructs a tree consisting of a root storing the
     * specified element and the specified subtrees.
     *
     * @param element The element stored in the root.
     * @param subtrees The collection of subtrees.
     */
    public LinkedTree(Object element, Vector subtrees)
    {
        Vector children = new Vector();
        root = new TNode(element, null, children);
        size = 1;
        for (int i = 0; i < subtrees.size(); i++)
	{
            LinkedTree subtree = (LinkedTree) subtrees.elementAt(i);
            TNode node = (TNode) subtree.root();
            node.setParent(root);
            children.add(node);
            size += subtree.size();            
        }
    }

    /** 
     * Returns the size of this tree.
     *
     * @return The size of this tree.
     */
    public int size() 
    {
        return size;
    }

    /** 
     * Tests if this tree is empty. 
     *
     * @return true if this tree is empty, false otherwise.
     */
    public boolean isEmpty() 
    {
        return (size == 0);
    }

    /**
     * Returns the root of this tree.
     *
     * @return The root of this tree.
     */
    public Position root()
    {
        return root;
    }

    /**
     * Returns the parent of the specified position.
     * Throws an InvalidPositionException if the specified position is 
     * the root of the tree.
     *
     * @param position The position the parent of which is to be returned.
     * @return The parent of the specified position.
     * @exception InvalidPositionException if the specified position is 
     * the root of the tree.
     */
    public Position parent(Position position) throws InvalidPositionException 
    {
        if (isRoot(position)) 
        {
            throw new InvalidPositionException("Root has no parent.");
        }
        TNode node = (TNode) position;
        return node.getParent();
    }

    /**
     * Returns a collection of the children of the specified position.
     *
     * @param position The position a collection of the children of which 
     * is to be returned.
     * @return A collection of the children of the specified position.
     */
    public Iterator children(Position position)
    {
        TNode node = (TNode) position;
        return node.getChildren().iterator();
    }

    /**
     * Tests if the specified position is internal.
     *
     * @param position The position to be tested to be internal.
     * @return true if the specified position is internal, false otherwise.
     */
    public boolean isInternal(Position position)
    {
        TNode node = (TNode) position;
        return !node.getChildren().isEmpty();
    }

    /**
     * Tests if the specified position is external.
     *
     * @param position The position to be tested to be external.
     * @return true if the specified position is external, false otherwise.
     */
    public boolean isExternal(Position position)
    {
        return !isInternal(position);
    }

    /**
     * Tests if the specified position is the root of this tree.
     *
     * @param position The position to be tested to be the root of this tree.
     * @return true if the specified position is the root, false otherwise.
     */
    public boolean isRoot(Position position)
    {
        TNode node = (TNode) position;
        return (node == root);
    }

    /**
     * Adds the elements stored in the subtree rooted at the specified
     * node to the specified vector. 
     * A preorder traversal is used to visit the nodes of the subtree.
     *
     * @param node Root of the subtree the elements of which are added
     * to the specified verctor.
     * @param vector The vector to which the elements are added.
     */
    private void preorderElements(Position node, Vector vector) 
    {
        vector.addElement(node.element());
        Iterator children = children(node);
        while (children.hasNext())
        {
            preorderElements((Position) children.next(), vector);
        }
    }

    /**
     * Returns the collection of all the elements stored at the positions
     * of this tree.
     *
     * @return The collection of all the elements stored at the positions
     * of this tree.
     */
    public Iterator elements() 
    {
        Vector vector = new Vector();
        preorderElements(root, vector);
        return vector.iterator();
    }

    /**
     * Adds the positions in the subtree rooted at the specified
     * node to the specified vector. 
     * A preorder traversal is used to visit the nodes of the subtree.
     *
     * @param node Root of the subtree the positions of which are added
     * to the specified verctor.
     * @param vector The vector to which the positions are added.
     */
    private void preorderPositions(Position node, Vector vector) 
    {
        vector.addElement(node);
        Iterator children = children(node);
        while (children.hasNext())
        {
	    preorderPositions((Position) children.next(), vector);
	}
    }

    /**
     * Returns the collection of all the positions of this tree.
     *
     * @return the collection of all the positions of this tree.
     */
    public Iterator positions() 
    {
        Vector vector = new Vector();
        preorderPositions(root, vector);
        return vector.iterator();
    }

    /**
     * Swaps the elements of the specified positions in this tree.
     *
     * @param first The position the element of which is to be swapped.
     * @param second The position the element of which is to be swapped.
     */
    public void swapElements(Position first, Position second) 
    {
        TNode firstNode = (TNode) first;
        TNode secondNode = (TNode) second;
        Object firstElement = firstNode.element();
        Object secondElement = secondNode.element();
        firstNode.setElement(secondElement);
        secondNode.setElement(firstElement);
    }

    /**
     * Replaces the element at the specified position in this tree
     * with the specified element and returns the replaced element.
     *
     * @param position The position the element of which is to be replaced.
     * @param element The replacement element.
     * @result The replaced element.
     */
    public Object replaceElement(Position position, Object element)
    {
        TNode node = (TNode) position;
        Object temp = node.element();
        node.setElement(element);
        return temp;
    }

    /**
     * Returns a string representation of the subtree of this
     * tree rooted at the specified node.
     *
     * @param node The root of the subtree.
     * @return A string representation of the subtree of this
     * tree rooted at the specified node.
     */
    private String preorderPrint(Position node) 
    {
        String rep = (node.element() == null) ? "" : node.element().toString();
        rep += "(";
        Iterator children = children(node);
        while (children.hasNext())
        {
	    rep += preorderPrint((Position) children.next());
	}
        rep += ")";
        return rep;
    }

    /**
     * Returns a string representation of this tree.
     *
     * @returns A string representation of this tree.
     */
    public String toString() 
    {
        return preorderPrint(root);
    } 
}