package week9;

import week2.EmptyCollectionException;
import week5.ElementNotFoundException;
import week5.NonComparableElementException;
import week8.BinaryTreeNode;
import week8.LinkedBinaryTree;

//链式二叉查找树类
public class LinkedBinarySearchTree<T> extends LinkedBinaryTree<T> implements
        BinarySearchTreeADT<T> {

    //Creates an empty binary search tree.
    public LinkedBinarySearchTree() {
        super();
    }


    //Creates a binary search with the specified elem as its root.
    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());
        }
    }

    //公有方法，删除指定元素，并按照一定规则形成新的二叉查找树
    @Override
    public T removeElement(T targetElement) {

        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.setLeft(temp.getLeft());
                    root.setRight(temp.getRight());
                }
                modCount--;

            } else {
                parent = root;
                if (((Comparable<T>) targetElement)
                        .compareTo(root.getElement()) < 0) {
                    result = removeElement(targetElement, root.getLeft(),
                            parent);
                } else {
                    result = removeElement(targetElement, root.getRight(),
                            parent);
                }
            }
        }
        return result;
    }
    //私有方法，删除特定节点
    private T removeElement(T targetElement, BinaryTreeNode<T> node,
                            BinaryTreeNode<T> parent) {
        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);

                // 看当前应该删除的降低ian
                if (parent.getRight() == node) {
                    parent.setRight(temp);
                } else {
                    parent.setLeft(temp);;
                }

                modCount--;

            } else {
                parent = node;
                if (((Comparable<T>) targetElement)
                        .compareTo(root.getElement()) < 0) {
                    result = removeElement(targetElement, root.getLeft(),
                            parent);
                } else {
                    result = removeElement(targetElement, root.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;
    }
}