import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;

// ------------------------------------------------------------------------------
/**
 * AVLTree_Recursive is a recursive implementation of a self-balancing
 * node-based AVL binary search tree. The data elements contained in the tree
 * must be mutually comparable.
 * 
 * @author Michael D. Naper, Jr. <MichaelNaper.com>
 * @version 2010.07.08
 * 
 * @param <E>
 *            The generic type for data elements contained in the tree.
 */
public class AVLTree_Recursive<E extends Comparable<? super E>> implements
        Iterable<E> {

    // ~ Nested Classes ........................................................

    // -------------------------------------------------------------------------
    /**
     * TreeNode is an implementation of a binary search tree node, which stores
     * a data element, references to each of its child nodes, and its height in
     * the tree.
     */
    private class TreeNode {

        // ~ Instance Variables ................................................

        /**
         * The data element stored in this node.
         */
        private E element;

        /**
         * The reference to the left child node, if present.
         */
        private TreeNode leftChild;

        /**
         * The reference to the right child node, if present.
         */
        private TreeNode rightChild;

        /**
         * The height of the node in the tree.
         */
        private int height;

        // ~ Constructors ......................................................

        // ---------------------------------------------------------------------
        /**
         * Constructs a new instance of TreeNode with the specified data element
         * and child node references.
         * 
         * @param element
         *            The element to be stored in the node.
         * @param leftChild
         *            The left child of the node.
         * @param rightChild
         *            The right child of the node.
         */
        public TreeNode(E element, TreeNode leftChild, TreeNode rightChild) {

            this.element = element;

            this.leftChild = leftChild;
            this.rightChild = rightChild;

            height = 0;
        }

        // ---------------------------------------------------------------------
        /**
         * Constructs a new instance of TreeNode with the specified data element
         * and no child node references.
         * 
         * @param element
         *            The element to be stored in the node.
         */
        public TreeNode(E element) {

            this(element, null, null);
        }
    }

    // -------------------------------------------------------------------------
    /**
     * TreeIterator is an iterator over the AVLTree.
     */
    private class TreeIterator implements Iterator<E> {

        // ~ Instance Variables ................................................

        /**
         * The LinkedList that stores the nodes of the tree in order.
         */
        private LinkedList<E> elementList;

        // ~ Constructors ......................................................

        // ---------------------------------------------------------------------
        /**
         * Constructs a new instance of TreeIterator.
         */
        public TreeIterator() {

            elementList = toList(root);
        }

        // ~ Methods ...........................................................

        // ---------------------------------------------------------------------
        /**
         * Returns true if the iterator has more data elements.
         * 
         * @return True if the iterator has more elements.
         */
        @Override
        public boolean hasNext() {

            return !elementList.isEmpty();
        }

        // ---------------------------------------------------------------------
        /**
         * Returns the next data element in the iteration.
         * 
         * @return The next element in the iteration.
         */
        @Override
        public E next() {

            return elementList.pop();
        }

        // ---------------------------------------------------------------------
        /**
         * The removal method is unsupported by this implementation of Iterator.
         */
        @Override
        public void remove() {

            throw new UnsupportedOperationException();
        }
    }

    // ~ Instance Variables ....................................................

    /**
     * The reference to the root node of the tree, if present.
     */
    private TreeNode root;

    /**
     * The size of the tree.
     */
    private int size;

    // ~ Constructors ..........................................................

    // -------------------------------------------------------------------------
    /**
     * Constructs a new, empty instance of AVLTree.
     */
    public AVLTree_Recursive() {

        root = null;

        size = 0;
    }

    // ~ Methods ...............................................................

    // -------------------------------------------------------------------------
    /**
     * Inserts the specified data element into this AVLTree, if the element is
     * not already present.
     * 
     * @param element
     *            The element to be inserted.
     * @return True if insertion is performed.
     */
    public boolean insert(E element) {

        if (element == null) {
            return false;
        }

        try {
            root = insert(root, element);
        } catch (IllegalArgumentException e) {
            return false;
        }

        return true;
    }

    // -------------------------------------------------------------------------
    /**
     * Helper recursive method for inserting the specified data element into the
     * specified subtree, if the element is not already present.
     * 
     * @param sRoot
     *            The root of the subtree for which to insert the element.
     * @param element
     *            The element to be inserted.
     * @return The new root of the specified subtree.
     */
    private TreeNode insert(TreeNode sRoot, E element) {

        if (sRoot == null) {
            size++;

            return new TreeNode(element);
        }

        int cmp = element.compareTo(sRoot.element);

        if (cmp < 0) {
            sRoot.leftChild = insert(sRoot.leftChild, element);

            if (height(sRoot.leftChild) - height(sRoot.rightChild) == 2) {
                if (height(sRoot.leftChild.leftChild) >= height(sRoot.leftChild.rightChild)) {
                    sRoot = rotateWithLeftChild(sRoot);
                } else {
                    sRoot = doubleRotateWithLeftChild(sRoot);
                }
            }
        } else if (cmp > 0) {
            sRoot.rightChild = insert(sRoot.rightChild, element);

            if (height(sRoot.rightChild) - height(sRoot.leftChild) == 2) {
                if (height(sRoot.rightChild.rightChild) >= height(sRoot.rightChild.leftChild)) {
                    sRoot = rotateWithRightChild(sRoot);
                } else {
                    sRoot = doubleRotateWithRightChild(sRoot);
                }
            }
        } else {
            throw new IllegalArgumentException("Element " + element
                    + " is already present.");
        }

        sRoot.height = Math.max(height(sRoot.leftChild),
                height(sRoot.rightChild)) + 1;

        return sRoot;
    }

    // -------------------------------------------------------------------------
    /**
     * Inserts all the data elements in the specified Collection into this
     * AVLTree, if the element is not already present.
     * 
     * @param elements
     *            The collection of elements to be inserted.
     * @return True if insertion is performed at least once.
     */
    public boolean insertAll(Collection<? extends E> elements) {

        if (elements == null) {
            return false;
        }

        boolean hasInsertion = false;

        for (E element : elements) {
            hasInsertion = insert(element) || hasInsertion;
        }

        return hasInsertion;
    }

    // -------------------------------------------------------------------------
    /**
     * Returns true if this AVLTree contains the specified data element.
     * 
     * @param element
     *            The element whose presence is to be tested.
     * @return True if this AVLTree contains the specified element.
     */
    public boolean contains(E element) {

        if (element == null) {
            return false;
        }

        return find(element) != null;
    }

    // -------------------------------------------------------------------------
    /**
     * Returns true if this AVLTree contains all the data elements in the
     * specified Collection.
     * 
     * @param elements
     *            The collection of elements to be checked for containment.
     * @return True if this AVLTree contains all the elements in the specified
     *         collection.
     */
    public boolean containsAll(Collection<? extends E> elements) {

        if (elements == null) {
            return false;
        }

        for (E element : elements) {
            if (!contains(element)) {
                return false;
            }
        }

        return true;
    }

    // -------------------------------------------------------------------------
    /**
     * Returns a reference to the specified data element in this AVLTree, or
     * null if the element is not present.
     * 
     * @param element
     *            The element to be found.
     * @return The reference to the specified element in the tree, or null if
     *         the element is not present.
     */
    public E find(E element) {

        if (element == null) {
            return null;
        }

        TreeNode foundNode = find(root, element);

        return (foundNode == null) ? null : foundNode.element;
    }

    // -------------------------------------------------------------------------
    /**
     * Helper recursive method for returning a reference to the node with the
     * specified data element in the specified subtree, or null if the element
     * is not present.
     * 
     * @param sRoot
     *            The root of the subtree for which to find the element.
     * @param element
     *            The element to be found.
     * @return The reference to the node with the specified element in the
     *         specified subtree, or null if the element is not present.
     */
    private TreeNode find(TreeNode sRoot, E element) {

        if (sRoot == null) {
            return null;
        }

        int cmp = element.compareTo(sRoot.element);

        if (cmp < 0) {
            return find(sRoot.leftChild, element);
        } else if (cmp > 0) {
            return find(sRoot.rightChild, element);
        } else {
            return sRoot;
        }
    }

    // -------------------------------------------------------------------------
    /**
     * Returns a reference to the data element from this AVLTree with the
     * smallest key, if the element is present.
     * 
     * @return The reference to the element with the smallest key, or null if
     *         the tree is empty.
     */
    public E findMin() {

        TreeNode minNode = findMin(root);

        return (minNode == null) ? null : minNode.element;
    }

    // -------------------------------------------------------------------------
    /**
     * Helper recursive method for returning a reference to the node with the
     * smallest key in the specified subtree, or null if the tree is empty.
     * 
     * @param sRoot
     *            The root of the subtree for which to find the node with the
     *            smallest key.
     * @return The reference to the node with the smallest key in the specified
     *         subtree, or null if the tree is empty.
     */
    private TreeNode findMin(TreeNode sRoot) {

        if (sRoot.leftChild == null) {
            return sRoot;
        }

        return findMin(sRoot.leftChild);
    }

    // -------------------------------------------------------------------------
    /**
     * Returns a reference to the data element from this AVLTree with the
     * largest key, if the element is present.
     * 
     * @return The reference to the element with the largest key, or null if the
     *         tree is empty.
     */
    public E findMax() {

        TreeNode maxNode = findMax(root);

        return (maxNode == null) ? null : maxNode.element;
    }

    // -------------------------------------------------------------------------
    /**
     * Helper recursive method for returning a reference to the node with the
     * largest key in the specified subtree, or null if the tree is empty.
     * 
     * @param sRoot
     *            The root of the subtree for which to find the node with the
     *            largest key.
     * @return The reference to the node with the largest key in the subtree, or
     *         null if the tree is empty.
     */
    private TreeNode findMax(TreeNode sRoot) {

        if (sRoot.rightChild == null) {
            return sRoot;
        }

        return findMax(sRoot.rightChild);
    }

    // -------------------------------------------------------------------------
    /**
     * Removes the specified data element from this AVLTree, if the element is
     * present.
     * 
     * @param element
     *            The element to be removed.
     * @return True if removal is performed.
     */
    public boolean remove(E element) {

        if (element == null) {
            return false;
        }

        try {
            root = remove(root, element);
        } catch (IllegalArgumentException e) {
            return false;
        }

        return true;
    }

    // -------------------------------------------------------------------------
    /**
     * Helper recursive method for removing the specified data element from the
     * specified subtree, if the element is present.
     * 
     * @param sRoot
     *            The root of the subtree for which to remove the element.
     * @param element
     *            The element to be removed.
     * @return The new root of the specified subtree.
     */
    private TreeNode remove(TreeNode sRoot, E element) {

        if (sRoot == null) {
            throw new IllegalArgumentException("Element " + element
                    + "is not present.");
        }

        int cmp = element.compareTo(sRoot.element);

        if (cmp < 0) {
            sRoot.leftChild = remove(sRoot.leftChild, element);

            if (height(sRoot.rightChild) - height(sRoot.leftChild) == 2) {
                if (height(sRoot.rightChild.rightChild) >= height(sRoot.rightChild.leftChild)) {
                    sRoot = rotateWithRightChild(sRoot);
                } else {
                    sRoot = doubleRotateWithRightChild(sRoot);
                }
            }
        } else if (cmp > 0) {
            sRoot.rightChild = remove(sRoot.rightChild, element);

            if (height(sRoot.leftChild) - height(sRoot.rightChild) == 2) {
                if (height(sRoot.leftChild.leftChild) >= height(sRoot.leftChild.rightChild)) {
                    sRoot = rotateWithLeftChild(sRoot);
                } else {
                    sRoot = doubleRotateWithLeftChild(sRoot);
                }
            }
        } else {
            return removeNode(sRoot);
        }

        sRoot.height = Math.max(height(sRoot.leftChild),
                height(sRoot.rightChild)) + 1;

        return sRoot;
    }

    // -------------------------------------------------------------------------
    /**
     * Removes the specified node from the AVLTree, returning an appropriate
     * replacement node.
     * 
     * @param removalNode
     *            The node to be removed from the tree.
     * @return The node to replace the removed node.
     */
    private TreeNode removeNode(TreeNode removalNode) {

        TreeNode replacementNode;

        if (removalNode.leftChild != null && removalNode.rightChild != null) {
            replacementNode = findMin(removalNode.rightChild);

            removalNode.rightChild = removeMin(removalNode.rightChild);

            replacementNode.leftChild = removalNode.leftChild;
            replacementNode.rightChild = removalNode.rightChild;

            if (height(replacementNode.leftChild)
                    - height(replacementNode.rightChild) == 2) {
                if (height(replacementNode.leftChild.leftChild) >= height(replacementNode.leftChild.rightChild)) {
                    replacementNode = rotateWithLeftChild(replacementNode);
                } else {
                    replacementNode = doubleRotateWithLeftChild(replacementNode);
                }
            }

            replacementNode.height = Math.max(
                    height(replacementNode.leftChild),
                    height(replacementNode.rightChild)) + 1;
        } else {
            replacementNode = (removalNode.leftChild != null) ? removalNode.leftChild
                    : removalNode.rightChild;

            size--;
        }

        removalNode.leftChild = null;
        removalNode.rightChild = null;

        return replacementNode;
    }

    // -------------------------------------------------------------------------
    /**
     * Removes all the data elements in the specified Collection from this
     * AVLTree, if the element is present.
     * 
     * @param elements
     *            The collection of elements to be removed.
     * @return True if removal is performed at least once.
     */
    public boolean removeAll(Collection<? extends E> elements) {

        if (elements == null) {
            return false;
        }

        boolean hasRemoval = false;

        for (E element : elements) {
            hasRemoval = remove(element) || hasRemoval;
        }

        return hasRemoval;
    }

    // -------------------------------------------------------------------------
    /**
     * Removes and returns the data element from this AVLTree with the smallest
     * key, if the element is present.
     */
    public void removeMin() {

        root = removeMin(root);
    }

    // -------------------------------------------------------------------------
    /**
     * Helper recursive method for removing the node with the smallest key from
     * the specified subtree, if the element is present.
     * 
     * @param sRoot
     *            The root of the subtree for which to remove the node with the
     *            smallest key.
     * @return The new root of the specified subtree.
     */
    private TreeNode removeMin(TreeNode sRoot) {

        if (sRoot == null) {
            return null;
        }

        if (sRoot.leftChild == null) {
            size--;

            return sRoot.rightChild;
        }

        sRoot.leftChild = removeMin(sRoot.leftChild);

        if (height(sRoot.rightChild) - height(sRoot.leftChild) == 2) {
            if (height(sRoot.rightChild.rightChild) >= height(sRoot.rightChild.leftChild)) {
                sRoot = rotateWithRightChild(sRoot);
            } else {
                sRoot = doubleRotateWithRightChild(sRoot);
            }
        }

        sRoot.height = Math.max(height(sRoot.leftChild),
                height(sRoot.rightChild)) + 1;

        return sRoot;
    }

    // -------------------------------------------------------------------------
    /**
     * Removes and returns the data element from this AVLTree with the largest
     * key, if the element is present.
     */
    public void removeMax() {

        root = removeMax(root);
    }

    // -------------------------------------------------------------------------
    /**
     * Helper recursive method for removing the node with the largest key from
     * the specified subtree, if the element is present.
     * 
     * @param sRoot
     *            The root of the subtree for which to remove the node with the
     *            largest key.
     * @return The new root of the specified subtree.
     */
    private TreeNode removeMax(TreeNode sRoot) {

        if (sRoot == null) {
            return null;
        }

        if (sRoot.rightChild == null) {
            size--;

            return sRoot.leftChild;
        }

        sRoot.rightChild = removeMax(sRoot.rightChild);

        if (height(sRoot.leftChild) - height(sRoot.rightChild) == 2) {
            if (height(sRoot.leftChild.leftChild) >= height(sRoot.leftChild.rightChild)) {
                sRoot = rotateWithLeftChild(sRoot);
            } else {
                sRoot = doubleRotateWithLeftChild(sRoot);
            }
        }

        sRoot.height = Math.max(height(sRoot.leftChild),
                height(sRoot.rightChild)) + 1;

        return sRoot;
    }

    // -------------------------------------------------------------------------
    /**
     * Returns the height of the specified node in the tree or -1 if the node is
     * null.
     * 
     * @param node
     *            The node of which to get the height.
     * @return The height of the node in the tree or -1 if the node is null.
     */
    private int height(TreeNode node) {

        return (node == null) ? -1 : node.height;
    }

    // -------------------------------------------------------------------------
    /**
     * Rotates a node with its left child.
     * 
     * @param sRoot
     *            The root of the subtree with which to rotate the node's left
     *            child.
     * @return The node that is the new root of the specified root's subtree.
     */
    private TreeNode rotateWithLeftChild(TreeNode sRoot) {

        TreeNode newRoot = sRoot.leftChild;

        sRoot.leftChild = newRoot.rightChild;
        newRoot.rightChild = sRoot;

        sRoot.height = Math.max(height(sRoot.leftChild),
                height(sRoot.rightChild)) + 1;
        newRoot.height = Math.max(height(newRoot.leftChild), sRoot.height) + 1;

        return newRoot;
    }

    // -------------------------------------------------------------------------
    /**
     * Rotates a node with its right child.
     * 
     * @param sRoot
     *            The root of the subtree with which to rotate the node's right
     *            child.
     * @return The node that is the new root of the specified root's subtree.
     */
    private TreeNode rotateWithRightChild(TreeNode sRoot) {

        TreeNode newRoot = sRoot.rightChild;

        sRoot.rightChild = newRoot.leftChild;
        newRoot.leftChild = sRoot;

        sRoot.height = Math.max(height(sRoot.leftChild),
                height(sRoot.rightChild)) + 1;
        newRoot.height = Math.max(sRoot.height, height(newRoot.rightChild)) + 1;

        return newRoot;
    }

    // -------------------------------------------------------------------------
    /**
     * Double rotates a node with its left child.
     * 
     * @param sRoot
     *            The root of the subtree with which to double rotate the node's
     *            left child.
     * @return The node that is the new root of the specified root's subtree.
     */
    private TreeNode doubleRotateWithLeftChild(TreeNode sRoot) {

        sRoot.leftChild = rotateWithRightChild(sRoot.leftChild);

        return rotateWithLeftChild(sRoot);
    }

    // -------------------------------------------------------------------------
    /**
     * Double rotates a node with its right child.
     * 
     * @param sRoot
     *            The root of the subtree with which to double rotate the node's
     *            right child.
     * @return The node that is the new root of the specified root's subtree.
     */
    private TreeNode doubleRotateWithRightChild(TreeNode sRoot) {

        sRoot.rightChild = rotateWithLeftChild(sRoot.rightChild);

        return rotateWithRightChild(sRoot);
    }

    // -------------------------------------------------------------------------
    /**
     * Removes all the data elements from this AVLTree. The AVLTree will be
     * empty after this method returns.
     */
    public void clear() {

        root = null;

        size = 0;
    }

    // -------------------------------------------------------------------------
    /**
     * Returns true if this AVLTree contains no data elements. In other words,
     * returns true if the size of this AVLTree is zero.
     * 
     * @return True if this AVLTree contains no elements.
     */
    public boolean isEmpty() {

        return root == null;
    }

    // -------------------------------------------------------------------------
    /**
     * Returns the number of data elements in this AVLTree.
     * 
     * @return The number of elements in this AVLTree.
     */
    public int size() {

        return size;
    }

    // -------------------------------------------------------------------------
    /**
     * Returns an iterator over the data elements in this AVLTree in order.
     * 
     * @return An Iterator over the elements in this AVLTree.
     */
    public Iterator<E> iterator() {

        return new TreeIterator();
    }

    // -------------------------------------------------------------------------
    /**
     * Returns an array containing all the data elements in this AVLTree in
     * order.
     * 
     * @return An array containing all the elements in this AVLTree.
     */
    @SuppressWarnings("rawtypes")
    public Comparable[] toArray() {

        Comparable[] elementList = new Comparable[size];

        if (root == null) {
            return elementList;
        }

        return toList(root).toArray(elementList);
    }

    // -------------------------------------------------------------------------
    /**
     * Helper recursive method for returning an array containing all the data
     * elements in the specified subtree in order.
     * 
     * @param sRoot
     *            The root of the subtree for which to return an ArrayList
     *            containing all the elements.
     * @return An ArrayList containing all the elements in the specified
     *         subtree.
     */
    public LinkedList<E> toList(TreeNode sRoot) {

        LinkedList<E> elementList = new LinkedList<E>();

        if (sRoot == null) {
            return elementList;
        }

        elementList.addAll(toList(sRoot.leftChild));

        elementList.add(sRoot.element);

        elementList.addAll(toList(sRoot.rightChild));

        return elementList;
    }

    // -------------------------------------------------------------------------
    /**
     * Returns a string representation of this AVLTree. The returned string is a
     * sideways tree diagram representing the organization of the data elements
     * in the tree.
     * 
     * @return A string representation of this AVLTree.
     */
    @Override
    public String toString() {

        if (root == null) {
            return new String();
        }

        return toString(root, 0);
    }

    // -------------------------------------------------------------------------
    /**
     * Helper recursive method for returning a string representation of the
     * specified subtree. The returned string is a sideways tree diagram
     * representing the organization of the data elements in the subtree.
     * 
     * @param sRoot
     *            The node that roots the subtree.
     * @param depth
     *            The depth of the root node in the initial subtree.
     * @return A string representation of the specified subtree.
     */
    private String toString(TreeNode sRoot, int depth) {

        StringBuilder nodeString = new StringBuilder();

        if (sRoot == null) {
            return nodeString.toString();
        }

        nodeString.append(toString(sRoot.leftChild, depth + 1));

        for (int i = 0; i < depth; i++) {
            nodeString.append("---");
        }

        if (depth > 0) {
            nodeString.append(" ");
        }

        nodeString.append(sRoot.element + "\n");

        nodeString.append(toString(sRoot.rightChild, depth + 1));

        return nodeString.toString();
    }
}