/*
 * @(#)AVLTree.java
 */

package org.eda1.actividad03.AVLTree;

import java.util.NoSuchElementException;
import java.lang.IllegalStateException;
import java.util.ConcurrentModificationException;

import org.eda.estructurasdatos.ALStack;
import org.eda.estructurasdatos.BinarySearchTree;
import org.eda.estructurasdatos.Collection;
import org.eda.estructurasdatos.Iterable;
import org.eda.estructurasdatos.Iterator;

/**
 * This class is a balanced binary tree that implements the Collection interface AVL
 * tree single and double rotation methods.
 * @see     RBTree
 */

public class AVLTree<T> implements Collection<T>, Iterable<T>, BinarySearchTree<T>{
   // reference to tree root
   private AVLNode<T> root;

   // number of elements in the tree
   private int treeSize;

   // increases whenever the tree changes. used by an iterator
   // to verify that it is in a consistent state
   private int modCount;

    // ...


    /**
     * Restores balance to the tree given the specified node traversal path and
     * whether insertion or removal was performed.
     *
     * @param nodePath
     *            The Stack which contains the nodes in the order that they were
     *            traversed.
     * @param isInsertion
     *            Indicates whether insertion or removal was performed.
     */
    private void rebalanceAVLTree(ALStack<AVLNode<T>> nodePath, boolean isInsertion) {

        AVLNode<T> current;

        while (!nodePath.isEmpty()) {
            current = nodePath.pop();

            // Check for an imbalance at the current node:
            if (height(current.left) - height(current.right) == 2) {
                // Compare heights of subtrees of left child node of
                // imbalanced node (check for single or double rotation case):
                if (height(current.left.left) >= height(current.left.right)) {
                    // Check if imbalance is internal or at the tree root:
                    if (!nodePath.isEmpty()) {
                        // Compare current element with element of parent
                        // node (check which child reference to update for the
                        // parent node):
                        int cmp = ((Comparable<T>)current.nodeValue).compareTo((nodePath.peek()).nodeValue);
                        if (cmp < 0) {
                            nodePath.peek().left = singleRotateRight(current);
                        } else {
                            nodePath.peek().right = singleRotateRight(current);
                        }
                    } else {
                        root = singleRotateRight(current);
                    }
                } else {
                    if (!nodePath.isEmpty()) {
                        int cmp = ((Comparable<T>)current.nodeValue).compareTo((nodePath.peek()).nodeValue);
                        if (cmp < 0) {
                            nodePath.peek().left = doubleRotateRight(current);
                        } else {
                            nodePath.peek().right = doubleRotateRight(current);
                        }
                    } else {
                        root = doubleRotateRight(current);
                    }
                }

                current.height = Math.max(height(current.left),
                        height(current.right)) + 1;

                if (isInsertion) {
                    break;
                }
            } else if (height(current.right) - height(current.left) == 2) {
                if (height(current.right.right) >= height(current.right.left)) {
                    if (!nodePath.isEmpty()) {
                        int cmp = ((Comparable<T>)current.nodeValue).compareTo((nodePath.peek()).nodeValue);
                        if (cmp < 0) {
                            nodePath.peek().left = singleRotateLeft(current);
                        } else {
                            nodePath.peek().right = singleRotateLeft(current);
                        }
                    } else {
                        root = singleRotateLeft(current);
                    }
                } else {
                    if (!nodePath.isEmpty()) {
                        int cmp = ((Comparable<T>)current.nodeValue).compareTo((nodePath.peek()).nodeValue);
                        if (cmp < 0) {
                            nodePath.peek().left = doubleRotateLeft(current);
                        } else {
                            nodePath.peek().right = doubleRotateLeft(current);
                        }
                    } else {
                        root = doubleRotateLeft(current);
                    }
                }

                current.height = Math.max(height(current.left),
                        height(current.right)) + 1;

                if (isInsertion) {
                    break;
                }
            } else {
                current.height = Math.max(height(current.left),
                        height(current.right)) + 1;
            }
        }
    }

    // ...

    /**
     * Adds the specified item to this tree if it is not already present.
     *
     * @param item element to be added to this tree.
     * @return <tt>true</tt> if the tree did not already contain the specified
     *         element.
     */
    public boolean add(T item)
    {
        try
        {
            root = addNode(root, item);
        }

        catch (IllegalStateException ise)
        { return false; }

        // increment the tree size and modCount
        treeSize++;
        modCount++;

        // test
        //testBalanceFactor(root);
        //testHeight(root);

        // we added a node to the tree
        return true;
    }

    private AVLNode<T> addNode(AVLNode<T> t, T item)
    {
        if( t == null )
            t = new AVLNode<T>(item);
        else if (((Comparable<T>)item).compareTo(t.nodeValue) < 0)
        {
            t.left = addNode( t.left, item);

            if (height(t.left) - height(t.right) == 2 )
                if (((Comparable<T>)item).compareTo
                            (t.left.nodeValue) < 0)
                    t = singleRotateRight(t);
                else
                    t = doubleRotateRight(t);
        }
        else if (((Comparable<T>)item).compareTo
                            (t.nodeValue) > 0 )
        {
            t.right = addNode(t.right, item );

            if (height(t.left) - height(t.right) == -2)
                if (((Comparable<T>)item).compareTo
                            (t.right.nodeValue) > 0)
                    t = singleRotateLeft(t);
                else
                    t = doubleRotateLeft(t);
        }
        else
            // duplicate; throw IllegalStateException
            throw new IllegalStateException();

        t.height = max( height(t.left), height(t.right) ) + 1;

        return t;
    }

    /**
     * Adds (iterative) the specified data item into this AVLTree, if the item is
     * not already present.
     *
     * @param item
     *            The item to be inserted.
     * @return True if insertion is performed.
     */
    public boolean addIterative(T item) {

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

        ALStack<AVLNode<T>> nodePath = new ALStack<AVLNode<T>>();

        AVLNode<T> current = root;

        while (current != null) {
            nodePath.push(current);

            int cmp = ((Comparable<T>)item).compareTo(current.nodeValue);

            if (cmp < 0) {
                if (current.left == null) {
                    current.left = new AVLNode<T>(item);

                    treeSize++;

                    rebalanceAVLTree(nodePath, true);

                    return true;
                }

                current = current.left;
            } else if (cmp > 0) {
                if (current.right == null) {
                    current.right = new AVLNode<T>(item);

                    treeSize++;

                    rebalanceAVLTree(nodePath, true);

                    return true;
                }

                current = current.right;
            } else {
                return false; // Element is already stored in tree
            }
        }

        // Tree is empty:
        root = new AVLNode<T>(item);

        treeSize++;

        return true;
    }

    public boolean remove(Object item) {

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

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

        return true;
    }

    private AVLNode<T> remove(AVLNode<T> t, T item) {

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

        int cmp = ((Comparable<T>)item).compareTo(t.nodeValue);

        if (cmp < 0) {
            t.left = remove(t.left, item);

            if (height(t.right) - height(t.left) == 2) {
                if (height(t.right.right) >= height(t.right.left)) {
                    t = singleRotateLeft(t);
                } else {
                    t = doubleRotateLeft(t);
                }
            }
        } else if (cmp > 0) {
            t.right = remove(t.right, item);

            if (height(t.left) - height(t.right) == 2) {
                if (height(t.left.left) >= height(t.left.right)) {
                    t = singleRotateRight(t);
                } else {
                    t = doubleRotateRight(t);
                }
            }
        } else {
            return removeNode(t);
        }

        t.height = Math.max(height(t.left), height(t.right)) + 1;

        return t;
    }

    private AVLNode<T> removeNode(AVLNode<T> removalNode) {

        AVLNode<T> replacementNode;

        if (removalNode.left != null && removalNode.right != null) {
            replacementNode = findMin(removalNode.right);

            removalNode.right = removeMin(removalNode.right);

            replacementNode.left = removalNode.left;
            replacementNode.right = removalNode.right;

            if (height(replacementNode.left) - height(replacementNode.right) == 2) {
                if (height(replacementNode.left.left) >= height(replacementNode.left.right)) {
                    replacementNode = singleRotateRight(replacementNode);
                } else {
                    replacementNode = doubleRotateRight(replacementNode);
                }
            }

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

            treeSize--;
        }

        removalNode.left = null;
        removalNode.right = null;

        return replacementNode;
    }

    private AVLNode<T> removeMin(AVLNode<T> t) {

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

        if (t.left == null) {
            treeSize--;

            return t.right;
        }

        t.left = removeMin(t.left);

        if (height(t.right) - height(t.left) == 2) {
            if (height(t.right.right) >= height(t.right.left)) {
                t = singleRotateLeft(t);
            } else {
                t = doubleRotateLeft(t);
            }
        }

        t.height = Math.max(height(t.left), height(t.right)) + 1;

        return t;
    }

    private AVLNode<T> findMin(AVLNode<T> t) {

        if (t.left == null) {
            return t;
        }

        return findMin(t.left);
    }

    /**
     * Removes (iterative) the specified data item from this AVLTree, if the item is
     * present.
     *
     * @param item
     *            The item to be removed.
     * @return True if removal is performed.
     */
    public boolean removeIterative(T item) {

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

        ALStack<AVLNode<T>> nodePath = new ALStack<AVLNode<T>>();

        AVLNode<T> current = root;

        while (current != null) {
            nodePath.push(current);

            int cmp = ((Comparable<T>)item).compareTo(current.nodeValue);

            if (cmp < 0) {
                if ((current.left != null) && (item.equals(current.left.nodeValue))) {
                    current.left = removeNodeIterative(current.left);

                    treeSize--;

                    rebalanceAVLTree(nodePath, false);

                    return true;
                }

                current = current.left;
            } else if (cmp > 0) {
                if ((current.right != null) && (item.equals(current.right.nodeValue))) {
                    current.right = removeNodeIterative(current.right);

                    treeSize--;

                    rebalanceAVLTree(nodePath, false);

                    return true;
                }

                current = current.right;
            } else {
                root = removeNodeIterative(current); // Root is to be removed

                treeSize--;

                rebalanceAVLTree(nodePath, false);

                return true;
            }
        }

        return false;
    }

    /**
     * Removes (iterative) 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 AVLNode<T> removeNodeIterative(AVLNode<T> removalNode) {

        AVLNode<T> replacementNode;

        if ((removalNode.left != null) && (removalNode.right != null)) {
            replacementNode = fetchSuccessor(removalNode);

            replacementNode.left = removalNode.left;
            replacementNode.right = removalNode.right;

            if (height(replacementNode.left)
                    - height(replacementNode.right) == 2) {
                if (height(replacementNode.left.left) >= height(replacementNode.left.right)) {
                    replacementNode = singleRotateRight(replacementNode);
                } else {
                    replacementNode = doubleRotateRight(replacementNode);
                }
            }

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

        removalNode.left = null;
        removalNode.right = null;

        return replacementNode;
    }

    /**
     * Removes and returns the node that is the logical in-order successor of
     * the specified subtree root node.
     *
     * @param sRoot
     *            The root of the subtree of which to fetch the logical
     *            successor node.
     * @return The successor node of the specified subtree root node.
     */
    private AVLNode<T> fetchSuccessor(AVLNode<T> sRoot) {

        if ((sRoot == null) || (sRoot.right == null)) {
            return null;
        }

        AVLNode<T> successorNode = sRoot.right;

        if (sRoot.right.left == null) {
            sRoot.right = successorNode.right;

            return successorNode;
        } else {
            ALStack<AVLNode<T>> nodePath = new ALStack<AVLNode<T>>();

            nodePath.push(sRoot);

            AVLNode<T> current = sRoot.right;

            while (current.left.left != null) {
                nodePath.push(current);

                current = current.left;
            }

            nodePath.push(current);

            successorNode = current.left;

            current.left = current.left.right;

            rebalanceTreeAfterFetchSuccessor(nodePath);

            return successorNode;
        }
    }

    /**
     * Restores balance to the tree after a node successor has been fetched
     * given the specified node traversal path.
     *
     * @param nodePath
     *            The Stack which contains the nodes in the order that they were
     *            traversed.
     */
    private void rebalanceTreeAfterFetchSuccessor(ALStack<AVLNode<T>> nodePath) {

        AVLNode<T> current;

        while (nodePath.size() > 2) {
            current = nodePath.pop();

            if (height(current.right) - height(current.left) == 2) {
                if (height(current.right.right) >= height(current.right.left)) {
                    nodePath.peek().left = singleRotateLeft(current);
                } else {
                    nodePath.peek().left = doubleRotateLeft(current);
                }
            }

            current.height = Math.max(height(current.left),
                    height(current.right)) + 1;
        }

        // Current node is root of right subtree of removal node:
        current = nodePath.pop();

        if (height(current.right) - height(current.left) == 2) {
            if (height(current.right.right) >= height(current.right.left)) {
                nodePath.peek().right = singleRotateLeft(current);
            } else {
                nodePath.peek().right = doubleRotateLeft(current);
            }
        }

        current.height = Math.max(height(current.left),
                height(current.right)) + 1;
    }

    // ...

    // declares a binary search tree node object
    private static class AVLNode<T>
    {
        // node data
        public T nodeValue;

        // child links and link to the node's parent
        public AVLNode<T> left, right;

        // public int height;
        public int height;

        // constructor that initializes the value, balance factor
        // and parent fields and sets the link fields left and
        // right to null
        public AVLNode(T item)
        {
            nodeValue = item;
            left = null;
            right = null;
            height = 0;
        }
    }
}