package week7.jsjf;

import week4.jsjf.ArrayUnorderedList;
import week4.jsjf.UnorderedListADT;
import week6.jsjf.BinaryTreeNode;
import week6.jsjf.LinkedBinaryTree;
import week7.jsjf.exceptions.ElementNotFoundException;
import week7.jsjf.exceptions.EmptyCollectionException;
import week7.jsjf.exceptions.NonComparableElementException;

/**
 * LinkedBinarySearchTree implements the BinarySearchTreeADT interface 
 * with links
 * 
 * @author Lewis and Chase
 * @version 4.0
 */
 public class LinkedBinarySearchTree<T> extends LinkedBinaryTree<T> implements BinarySearchTreeADT<T>
{

    //创建一个空的二叉搜索树
    LinkedBinarySearchTree left,right;
    public LinkedBinarySearchTree()

    {
        super();
    }


    /**
     *创建以指定元素为根元素的二进制搜索
     * @param element 成为新二叉树根元素的元素
     */
    public LinkedBinarySearchTree(T element) 
    {
        super(element);
        
        if (!(element instanceof Comparable))
            throw new NonComparableElementException("LinkedBinarySearchTree");
    }
    
    /**
     * 根据二叉树的自然规则在存放位置插入指定结点 相等的元素放在结点的右边
     *
     * @param element 被放入二叉树的元素
     * */
    @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++;
    }
    
    /**
     * 将指定的对象添加到根据自然顺序选择合适的位置。请注意将相等的元素放入右子树。
     * @param element 被加入二叉树的元素
     */
    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());
        }
    }
        
        
    /**
     * 删除第一个与指定元素匹配的二叉树中的元素并且返回他的引用。抛出一个ElementNotFoundException如果指定元素没有在二叉树中找到
     *
     * @param targetElement 在二叉树中被查找的元素
     * @throws ElementNotFoundException 如果指定元素没有被找到
     */
    @Override
    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.element)) 
            {
                result =  root.element;
                BinaryTreeNode<T> temp = replacement(root);
                if (temp == null)
                    root = null;
                else 
                {
                    root.element = temp.element;
                    root.setRight(temp.right);
                    root.setLeft(temp.left);
                }

                modCount--;
            }
            else 
            {                
                parent = root;
                if (((Comparable)targetElement).compareTo(root.element) < 0)
                    result = removeElement(targetElement, root.getLeft(), parent);
                else
                    result = removeElement(targetElement, root.getRight(), parent);
            }
        }
        
        return result;
    }
                
    /**
     * 删除与指定目标匹配的第一个元素来自二叉搜索树的元素，并返回一个引用如果指定目标没有被找到，抛出ElementNotFoundException元素没有在二叉搜索树中找到。
     *
     * @param targetElement 在二叉树中被搜索的元素
     * @param node 来自被搜索结点的结点
     * @param parent 被搜索的结点的parent
     * @throws ElementNotFoundException 如果目标元素没有被找到
     */
    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.element)) 
            {
                result =  node.element;
                BinaryTreeNode<T> temp = replacement(node);
                if (parent.right == node)
                    parent.right = temp;
                else 
                    parent.left = temp;

                modCount--;
            }
            else 
            {                
                parent = node;
                if (((Comparable)targetElement).compareTo(node.element) < 0)
                    result = removeElement(targetElement, node.getLeft(), parent);
                else
                    result = removeElement(targetElement, node.getRight(), parent);
            }
        }
        
        return result;
    }
    
    /**
     * 返回将代替被移动的指定元素的结点的引用如果有该结点有两个孩子的情况 中序后继者充当替代者.
     *
     * @param node 被删除的结点
     * @return 被替代结点的引用
     */
    private BinaryTreeNode<T> replacement(BinaryTreeNode<T> node) 
    {
        BinaryTreeNode<T> result = null;
        
        if ((node.left == null) && (node.right == null))
            result = null;
        
        else if ((node.left != null) && (node.right == null))
            result = node.left;
        
        else if ((node.left == null) && (node.right != null))
            result = node.right;
        
        else
        {
            BinaryTreeNode<T> current = node.right;
            BinaryTreeNode<T> parent = node;
            
            while (current.left != null)
            {
                parent = current;
                current = current.left;
            }
            
            current.left = node.left;
            if (node.right != current)
            {
                parent.left = current.right;
                current.right = node.right;
            }
            
            result = current;
        }
        
        return result;
    }
    
    /**
     *  删除二叉树中与指定目标元素匹配的元素抛出一个ElementNotFoundException如果指定元素没有在树中被找到
     *
     * @param targetElement 二叉树中被找到的元素
     * @throws ElementNotFoundException 如果指定元素没有被找到
     */
    @Override
    public void removeAllOccurrences(T targetElement)
                   throws ElementNotFoundException 
    {
        removeElement(targetElement);
        
        try
        {
            while (contains((T)targetElement))
                removeElement(targetElement);
        }
        
        catch (Exception ElementNotFoundException)
        {
        }
    }

    /**
     * 删除二叉树中最小值的结点返回该元素的结点的引用抛出一个EmptyCollectionException.如果树为空
     *
     * @return 最小值结点的引用
     * @throws EmptyCollectionException 如果树为空
     */
    @Override
    public T removeMin() throws EmptyCollectionException
    {
        T result = null;

        if (isEmpty())
            throw new EmptyCollectionException("LinkedBinarySearchTree");
        else 
        {
            if (root.left == null) 
            {
                result = root.element;
                root = root.right;
            }
            else 
            {
                BinaryTreeNode<T> parent = root;
                BinaryTreeNode<T> current = root.left;
                while (current.left != null) 
                {
                    parent = current;
                    current = current.left;
                }
                result =  current.element;
                parent.left = current.right;
            }

            modCount--;
        }
 
        return result;
    }

    /**
     * 删除二叉搜索树中有最高元素的结点并返回被删除结点的元素的引用抛出EmptyCollectionException如果树为空
     *
     * @return 含有最高元素的结点的引用
     * @throws EmptyCollectionException 如果树为空
     */
    @Override
    public T removeMax() throws EmptyCollectionException
    {
        T result=null;

        if (isEmpty())
            throw new EmptyCollectionException("LinkedBinarySearchTree");
        else
        {
            if (root.right == null)
            {
                result = root.element;
                root = root.left;
            }
            else
            {
                BinaryTreeNode<T> parent = root;
                BinaryTreeNode<T> current = root.right;
                while (current.right != null)
                {
                    parent = current;
                    current = current.right;
                }
                result =  current.element;
                parent.right = current.left;
            }

            modCount--;
        }

        return result;
    }

    /**
     * 返回二叉树中最小的元素。不从该二叉树中删除该结点.
     * 抛出一个EmptyCollectionException如果该树为空.
     *
     * @return 最小的元素
     * @throws EmptyCollectionException 如果树为空
     * */
    @Override
    public T findMin() throws EmptyCollectionException
    {
        T result=null;

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

        }
    }
    return result;
    }

    /**
     * 返回二叉树中值最高的结点.并且不从二叉树中删除结点抛出一个 EmptyCollectionException 如果树为空
     *
     * @return 最高值的元素
     * @throws EmptyCollectionException 如果树为空
     */
    @Override
    public T findMax() throws EmptyCollectionException
    {
        T result=null;

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

            }
        }
        return result;
    }

    /**
     * 返回指定元素的引用如果他在二叉树中被找到抛出NoSuchElementException如果指定元素在树中没有被找到
     *
     * @param targetElement 二叉树中被搜索的元素
     * @throws ElementNotFoundException 如果目标元素没有被找到
     */
    @Override
    public T find(T targetElement) throws ElementNotFoundException
    {
        BinaryTreeNode<T> current = findNode(targetElement, root);

        if (current == null)
            throw new ElementNotFoundException("LinkedBinaryTree");

        return (current.getElement());
    }


    @Override
    public String toString()
    {
        UnorderedListADT<BinaryTreeNode> nodes = new ArrayUnorderedList<BinaryTreeNode>();
        UnorderedListADT<Integer> levelList = new ArrayUnorderedList<Integer>();
        BinaryTreeNode current;
        String result = "";
        int printDepth = this.getHeight();
        int possibleNodes = (int)Math.pow(2, printDepth + 1);
        int countNodes = 0;

        nodes.addToRear(root);
        Integer currentLevel = 0;
        Integer previousLevel = -1;
        levelList.addToRear(currentLevel);

        while (countNodes < possibleNodes)
        {
            countNodes = countNodes + 1;
            current = nodes.removeFirst();
            currentLevel = levelList.removeFirst();
            if (currentLevel > previousLevel)
            {
                result = result + "\n\n";
                previousLevel = currentLevel;
                for (int j = 0; j < ((Math.pow(2, (printDepth - currentLevel))) - 1); j++)
                    result = result + " ";
            }
            else
            {
                for (int i = 0; i < ((Math.pow(2, (printDepth - currentLevel + 1)) - 1)) ; i++)
                {
                    result = result + " ";
                }
            }
            if (current != null)
            {
                result = result + (current.getElement()).toString();
                nodes.addToRear(current.getLeft());
                levelList.addToRear(currentLevel + 1);
                nodes.addToRear(current.getRight());
                levelList.addToRear(currentLevel + 1);
            }
            else {
                nodes.addToRear(null);
                levelList.addToRear(currentLevel + 1);
                nodes.addToRear(null);
                levelList.addToRear(currentLevel + 1);
                result = result + " ";
            }
        }
        return result;
    }

    /**
     * 返回树的根结点的左子树.
     *
     * @return 树的左子树的链接
     */
    @Override
    public LinkedBinarySearchTree<T> getLeft()
    {
        return left;
    }
    
    /**
     * 返回树的根结点的右子树
     *
     * @return 树的右子树的链接
     */
    @Override
    public LinkedBinarySearchTree<T> getRight()
    {
        return right;
    }
    
    /**
     * 如果一个元素在树中被找到则返回他的引用
     *
     * @param targetElement 在树中被查找的元素
     * @param next 开始被查找的树的结点
     */
    private BinaryTreeNode<T> findNode(T targetElement, BinaryTreeNode<T> next) 
    {

            if (next == null)
                return null;

            if (next.getElement().equals(targetElement))
                return next;

            BinaryTreeNode<T> temp = findNode(targetElement, next.getLeft());

            if (temp == null)
                temp = findNode(targetElement, next.getRight());

            return temp;

    }
}