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

/**
 * LinkedBinaryTree class implements the BinaryTree interface by means
 * of a linked structure consisting of nodes.
 *
 * @version    1.6    June 26, 2001
 * @author     Franck van Breugel
 * @see BinaryTree
 * @see BTNode
 */
public class LinkedBinaryTree implements BinaryTree 
{
    private BTNode root;  // pointer to the root of this binary tree
    private int size;   // size of this binary tree

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

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

    /**
     * Constructs a binary tree consisting of a root which stores
     * the specified element, which has the first specified binary tree as its
     * left subtree and the second specified binary tree as its right subtree.
     *
     * @param element The element stored in the root.
     * @param left The left subtree of the root.
     * @param right The right subtree of the root.
     */
    public LinkedBinaryTree(Object element, BinaryTree left, BinaryTree right) 
    {
        BTNode leftRoot = (BTNode) left.root();
        BTNode rightRoot = (BTNode) right.root();
        root = new BTNode(element, leftRoot, rightRoot, null);
        leftRoot.setParent(root);
        rightRoot.setParent(root);
        size = left.size() + right.size() + 1;
    }

    /** 
     * 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.");
        }
        BTNode node = (BTNode) 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)
    {
        BTNode node = (BTNode) position;
        Vector vector = new Vector();
        if (isInternal(node)) 
	{
            vector.addElement(node.getLeft());
            vector.addElement(node.getRight());
        }
        return vector.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)
    {
        BTNode node = (BTNode) position;
        return (node.getLeft() != null || node.getRight() != null);
    }

    /**
     * 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)
    {
        BTNode node = (BTNode) 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(BTNode node, Vector vector) 
    {
        if (node == null) 
        {
            return;
        } 
        else 
        {
            vector.addElement(node.element());
            preorderElements(node.getLeft(), vector);
            preorderElements(node.getRight(), 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(BTNode node, Vector vector) 
    {
        if (node == null) 
        {
            return;
        } 
        else 
        {
            vector.addElement(node);
            preorderPositions(node.getLeft(), vector);
            preorderPositions(node.getRight(), 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) 
    {
        BTNode firstNode = (BTNode) first;
        BTNode secondNode = (BTNode) 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)
    {
        BTNode node = (BTNode) position;
        Object temp = node.element();
        node.setElement(element);
        return temp;
    }

    /**
     * Returns the left child of the specified position.
     * Throws an InvalidPositionException if the specified position 
     * does not have a left child.
     *
     * @param position The position of which the left child is to be returned.
     * @return The left child of the specified position.
     * @exception InvalidPositionException if the specified position 
     * does not have a left child.
     */
    public Position leftChild(Position position) throws InvalidPositionException 
    {
        BTNode node = (BTNode) position;
        if (node.getLeft() == null) 
        {
            throw new InvalidPositionException("Node has no left child.");
        }
        return node.getLeft();
    }

    /**
     * Returns the right child of the specified position.
     * Throws an InvalidPositionException if the specified position 
     * does not have a right child.
     *
     * @param position The position of which the right child is to be returned.
     * @return The right child of the specified position.
     * @exception InvalidPositionException if the specified position 
     * does not have a right child.
     */
    public Position rightChild(Position position) throws InvalidPositionException 
    {
        BTNode node = (BTNode) position;
        if (node.getRight() == null) 
        {
            throw new InvalidPositionException("Node has no right child.");
        }
        return node.getRight();
    }

    /**
     * Returns the sibling of the specified position.
     * Throws a InvalidPositionException if the specified position does not have
     * a sibling.
     *
     * @param position The position of which the sibling is to be returned.
     * @exception InvalidPositionException if the specified position does not
     * have a sibling.
     */
    public Position sibling(Position position) throws InvalidPositionException
    {
        Position parent = parent(position);
        return (position == leftChild(parent)) ? rightChild(parent) : leftChild(parent);
    }

    /**
     * Adds a left and a right child to the specified position.
     * Both positions contain no element.
     * Throws an InvalidPositionException if the specified position is internal.
     *
     * @param position The position to which the left and right child are added.
     * @exception InvalidPositionException if the specified position is internal.
     */
    public void expandExternal(Position position) throws InvalidPositionException 
    {
        if (isInternal(position)) 
        {
            throw new InvalidPositionException("Invalid position.");
        }
        BTNode node = (BTNode) position;
        BTNode leftChild = new BTNode(null, null, null, node);
        BTNode rightChild = new BTNode(null, null, null, node);
        node.setLeft(leftChild);
        node.setRight(rightChild);
        size += 2;
    }

    /**
     * Removes the specified position together with its parent,
     * replaces the parent with the sibling of the specified position,
     * and returns the element stored in the parent.
     * Throws an InvalidPositionException if the specified position is 
     * internal or if it is the root.
     *
     * @param position The position to be removed.
     * @return The element stored in the parent of the specified position.
     * @exception InvalidPositionException if the specified position is
     * internal or if it is the root.
     */
    public Object removeAboveExternal(Position position) throws InvalidPositionException 
    {
        if (isInternal(position) || isRoot(position)) 
        {
            throw new InvalidPositionException("Invalid position.");
        }
        BTNode parent = (BTNode) parent(position);
        BTNode sibling = (BTNode) sibling(position);
        if (isRoot(parent)) 
        {
            root = sibling;
            sibling.setParent(null);
        } 
        else 
        {
            BTNode grandparent = (BTNode) parent(parent);
            if (grandparent.getLeft() == parent) 
            {
                grandparent.setLeft(sibling);
            } 
            else 
            {
                grandparent.setRight(sibling);
            }
            sibling.setParent(grandparent);
        }
        size -= 2;
        return parent.element();
    }

    /**
     * Returns a string representation of the subtree of this binary
     * tree rooted at the specified node.
     *
     * @param node The root of the subtree.
     * @return A string representation of the subtree of this binary
     * tree rooted at the specified node.
     */
    private String preorderPrint(BTNode node) 
    {
        String string;
        if (node == null) 
        {
            return " ";
        } 
        else 
        {
            return (node.element().toString() + "(" + preorderPrint(node.getLeft()) + "," + preorderPrint(node.getRight()) + ")");
        }
    }

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