package eighthweek;

import seventhweek.BinaryTreeNode;
import seventhweek.LinkedBinaryTree;

public class LinkedBinarySearchTree<T> extends LinkedBinaryTree<T> implements
        BinarySearchTreeADT<T> {

    public LinkedBinarySearchTree() {
        super();
    }

    public LinkedBinarySearchTree(T element) {
        super(element);

        if (!(element instanceof Comparable))
            throw new NonComparableElementException("LinkedBinarySearchTree");
    }

    public LinkedBinarySearchTree(BinaryTreeNode<T> temp){
        root = temp;
    }

    @Override
    public void addElement(T element) {
        if (!(element instanceof Comparable)) {
            throw new NonComparableElementException("LinkedBinarySearchTree");
        }

        Comparable<T> comparableElement = (Comparable<T>) element;

        if (isEmpty()) {
            root = new BinaryTreeNode<T>(element);
        } else {
            if (comparableElement.compareTo(root.getElement()) < 0) {
                if (root.getLeft() == null) {
                    this.getRootNode().setLeft(new BinaryTreeNode<T>(element));
                } else {
                    addElement(element, root.getLeft());
                }
            } else {
                if (root.getRight() == null) {
                    this.getRootNode().setRight(new BinaryTreeNode<T>(element));
                } else {
                    addElement(element, root.getRight());
                }
            }
        }
        modCount++;
    }

    private void addElement(T element, BinaryTreeNode<T> node) {
        Comparable<T> comparableElement = (Comparable<T>) element;

        if (comparableElement.compareTo(node.getElement()) < 0) {
            if (node.getLeft() == null)
                node.setLeft(new BinaryTreeNode<T>(element));
            else
                addElement(element, node.getLeft());
        } else {
            if (node.getRight() == null)
                node.setRight(new BinaryTreeNode<T>(element));
            else
                addElement(element, node.getRight());
        }
    }


    public BinaryTreeNode<T> addElementt(T element, BinaryTreeNode<T> node){
    if(node == null)
        return new BinaryTreeNode<T>(element);
    int compareResult = ((Comparable)element).compareTo(node.getElement());
    if(compareResult >= 0)
        node.setRight(addElementt(element, node.getRight()));
    else if(compareResult < 0)
        node.setLeft(addElementt(element, node.getLeft()));
    return node;
}

    public T removeElement(T targetElement)
            throws ElementNotFoundException
    {
        T result = null;

        if (isEmpty())
            throw new ElementNotFoundException("LinkedBinarySearchTree");
        else
        {
            BinaryTreeNode<T> parent = null;
            if (((Comparable<T>)targetElement).equals(root.getElement()))
            {
                result =  root.getElement();
                BinaryTreeNode<T> temp = replacement(root);
                if (temp == null)
                    root = null;
                else
                {
                    root.setElement(temp.getElement());
                    root.setRight(temp.getRight());
                    root.setLeft(temp.getLeft());
                }

                modCount--;
            }
            else
            {
                parent = root;
                if (((Comparable)targetElement).compareTo(root.getElement()) < 0)
                    result = removeElement(targetElement, root.getLeft(), parent);
                else
                    result = removeElement(targetElement, root.getRight(), parent);
            }
        }

        return result;
    }

    /**
     * Removes the first element that matches the specified target
     * element from the binary search tree and returns a reference to
     * it.  Throws a ElementNotFoundException if the specified target
     * element is not found in the binary search tree.
     *
     * @param targetElement the element being sought in the binary search tree
     * @param node the node from which to search
     * @param parent the parent of the node from which to search
     * @throws ElementNotFoundException if the target element is not found
     */
    private T removeElement(T targetElement, BinaryTreeNode<T> node, BinaryTreeNode<T> parent)
            throws ElementNotFoundException
    {
        T result = null;

        if (node == null)
            throw new ElementNotFoundException("LinkedBinarySearchTree");
        else
        {
            if (((Comparable<T>)targetElement).equals(node.getElement()))
            {
                result =  node.getElement();
                BinaryTreeNode<T> temp = replacement(node);
                if (parent.getRight() == node)
                    parent.setRight(temp);
                else
                    parent.setLeft(temp);

                modCount--;
            }
            else
            {
                parent = node;
                if (((Comparable)targetElement).compareTo(node.getElement()) < 0)
                    result = removeElement(targetElement, node.getLeft(), parent);
                else
                    result = removeElement(targetElement, node.getRight(), parent);
            }
        }

        return result;
    }


    private BinaryTreeNode<T> replacement(BinaryTreeNode<T> node) {
        BinaryTreeNode<T> result = null;
        if ((node.getLeft() == null) && (node.getRight() == null)) {
            result = null;
        } else if ((node.getLeft() != null) && (node.getRight() == null)) {
            result = node.getLeft();

        } else if ((node.getLeft() == null) && (node.getRight() != null)) {
            result = node.getRight();
        } else {
            BinaryTreeNode<T> current = node.getRight();// 初始化右侧第一个结点
            BinaryTreeNode<T> parent = node;

            // 获取右边子树的最左边的结点
            while (current.getLeft() != null) {
                parent = current;
                current = current.getLeft();
            }

            current.setLeft(node.getLeft());

            // 如果当前待查询的结点
            if (node.getRight() != current) {
                parent.setLeft(current.getRight());// 整体的树结构移动就可以了
                current.setRight(node.getRight());
            }

            result = current;
        }
        return result;
    }

    @Override
    public void removeAllOccurrences(T targetElement) {
        removeElement(targetElement);

        try {
            while (contains((T) targetElement))
                removeElement(targetElement);
        }

        catch (Exception ElementNotFoundException) {
        }

    }

    @Override
    public T removeMin() {
        T result = null;

        if (isEmpty())
            throw new EmptyCollectionException("LinkedBinarySearchTree");
        else {
            if (root.getLeft() == null) {
                result = root.getElement();
                root = root.getRight();
            } else {
                BinaryTreeNode<T> parent = root;
                BinaryTreeNode<T> current = root.getLeft();
                while (current.getLeft() != null) {
                    parent = current;
                    current = current.getLeft();
                }
                result = current.getElement();
                parent.setLeft(current.getRight());
            }

            modCount--;
        }
        return result;
    }

    @Override
    public T removeMax() {
        T result = null;

        if (isEmpty())
            throw new EmptyCollectionException("LinkedBinarySearchTree");
        else {
            if (root.getRight() == null) {
                result = root.getElement();
                root = root.getLeft();
            } else {
                BinaryTreeNode<T> parent = root;
                BinaryTreeNode<T> current = root.getRight();
                while (current.getRight() != null) {
                    parent = current;
                    current = current.getRight();
                }
                result = current.getElement();
                parent.setRight(current.getLeft());
            }
            modCount--;
        }
        return result;
    }

    @Override
    public T findMin() {
        T result = null;

        if (isEmpty())
            throw new EmptyCollectionException("LinkedBinarySearchTree");
        else {
            if (root.getLeft() == null) {
                result = root.getElement();
            } else {
                BinaryTreeNode<T> current = root.getLeft();
                while (current.getLeft() != null) {
                    current = current.getLeft();
                }
                result = current.getElement();
            }
        }
        return result;
    }

    @Override
    public T findMax() {
        T result = null;

        if (isEmpty())
            throw new EmptyCollectionException("LinkedBinarySearchTree");
        else {
            if (root.getRight() == null) {
                result = root.getElement();
            } else {
                BinaryTreeNode<T> current = root.getRight();
                while (current.getRight() != null) {
                    current = current.getRight();
                }
                result = current.getElement();
            }
        }
        return result;
    }

}