package second_term.eleventh_chapter;

import second_term.first_week.EmptyCollectionException;
import second_term.sixth_chapter.ElementNotFoundException;
import second_term.sixth_chapter.NonComparableElementException;
import second_term.sixth_chapter.UnorderedListADT;
import second_term.sixth_chapter.UnorderedListArrayList;

import java.util.Comparator;

public class LinkedBinarySearchTree<T> extends LinkedBinaryTree2<T>
                                        implements BinarySearchTreeADT<T>
{
    private Comparator<? super T> cmp;

    public LinkedBinarySearchTree() 
    {
        super();
    }
    

    public LinkedBinarySearchTree(T element) 
    {
        super(element);
        
        if (!(element instanceof Comparable))
            throw new NonComparableElementException("LinkedBinarySearchTree");
    }

    private int myCompare(T lhs, T rhs){
        if(cmp != null)
            return cmp.compare(lhs, rhs);
        else
            return ((Comparable)lhs).compareTo(rhs);
    }

    private int height(BinaryTreeNode2<T> node){
        int h1, h2;
        if (node == null) {
            return 0;
        } else {
            h1 = height(node.left);
            h2 = height(node.right);
            return (h1 < h2) ? h2 + 1 : h1 + 1;
        }
    }

    public BinaryTreeNode2<T> leftRotate(BinaryTreeNode2<T> temp){
        BinaryTreeNode2<T> temp1 = temp.right;
        temp.right = temp1.left;
        temp1.left = temp;
        temp.height = Math.max(height(temp.left),height(temp.right))+1;
        temp1.height = Math.max(height(temp1.left),height(temp1.right))+1;
        return temp1;
    }
    public BinaryTreeNode2<T> rightRotate(BinaryTreeNode2<T> temp){
        BinaryTreeNode2<T> temp1 = temp.left;
        temp.left = temp1.right;
        temp1.right = temp;
        temp.height = Math.max(height(temp.left),height(temp.right))+1;
        temp1.height = Math.max(height(temp1.left),height(temp1.right))+1;
        return temp1;
    }
    public BinaryTreeNode2<T> leftRightRotate(BinaryTreeNode2<T> temp){
        temp.left = leftRotate(temp.left);
        return rightRotate(temp);
    }
    public BinaryTreeNode2<T> rightLeftRotate(BinaryTreeNode2<T> temp){
        temp.right = rightRotate(temp.right);
        return leftRotate(temp);
    }



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

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

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

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

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

//    private BinaryTreeNode2<T> add(T element,BinaryTreeNode2<T> root)
//
//    {
//       if (root==null) {
//           return new BinaryTreeNode2<T>(element);
//       }
//       int difference = cmp.compare(element,root.element);
//       if (difference<0){
//           root.left = add(element,root.left);
//           if (height(root.left)-height(root.right)==2){
//               if (myCompare(element,root.left.element)<0)
//                   root = rightRotate(root);//右
//               else
//                   root = leftRightRotate(root);//左右
//           }
//       }
//       else{
//           if (difference>0){
//               root.right = add(element,root.right);
//               if (height(root.right)-height(root.left)==2){
//                   if (myCompare(element,root.right.element)<0)
//                       root=rightLeftRotate(root);//右左
//                   else
//                       root = leftRotate(root);//左
//               }
//           }
//       }
//
//       root.height = Math.max(height(root.left),height(root.right))+1;
//       return root;
//    }
    public T removeElement(T data) {
        if (data == null) {
            throw new RuntimeException("data can\'t not be null ");
        }
        this.root = remove(data,root);
        return data;
    }

    private BinaryTreeNode2<T> remove(T data, BinaryTreeNode2<T> z) {
        if (data == null || z == null)
            throw  new ElementNotFoundException("AVLTree");
        int difference = cmp.compare(data,z.element);
        if (difference<0){
            if (height(z.right)-height(z.left)==2){
                BinaryTreeNode2<T> temp = z.right;
                if (height(temp.left)>height(temp.right))
                    z = rightLeftRotate(z);//右左
                else
                    z= leftRotate(z);//左
            }
        }
        else{
            if (difference>0){
                if (height(z.left)-height(z.right)==2){
                    BinaryTreeNode2<T>  temp = z.left;
                    if (height(temp.left)>height(temp.right))
                        z = rightRotate(z);//右
                    else
                        z = leftRightRotate(z);//左右
                }
            }
            else{
                if (z.left!=null&&z.right!=null){
                    if (height(z.left)>height(z.right)){
                        BinaryTreeNode2<T> max = findmax(z.left);
                        z.element =max.element;
                        z.left = remove(max.element,z.left);
                    }
                    else{
                        BinaryTreeNode2<T> min = findmin(z.right);
                        z.element =min.element;
                        z.right = remove(min.element,z.right);
                    }
                }
                else {
                    BinaryTreeNode2<T> temp = z;
                    z = (z.left != null)? z.left:z.right;
                    temp =null;
                }

            }
        }

        return z;

    }

    private BinaryTreeNode2<T> replacement(BinaryTreeNode2<T> node)
    {
        BinaryTreeNode2<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
        {
            BinaryTreeNode2<T> current = node.right;
            BinaryTreeNode2<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;
    }

    public void removeAllOccurrences(T targetElement)
                   throws ElementNotFoundException 
    {
        removeElement(targetElement);
        
        try
        {
            while (contains((T)targetElement))
                removeElement(targetElement);
        }
        
        catch (Exception ElementNotFoundException)
        {
        }
    }

    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 
            {
                BinaryTreeNode2<T> parent = root;
                BinaryTreeNode2<T> current = root.left;
                while (current.left != null) 
                {
                    parent = current;
                    current = current.left;
                }
                result =  current.element;
                parent.left = current.right;
            }

            modCount--;
        }
 
        return result;
    }
    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{
                BinaryTreeNode2<T> parent = root;
                BinaryTreeNode2<T> current = root.right;
                while(current.right != null){
                    parent = current;
                    current = current.right;
                }
                result = current.element;
                parent.right = current.left;
            }
            modCount--;
        }

        return result;
    }
    public T findMax() throws EmptyCollectionException {
        if (isEmpty())
            System.out.println("BinarySearchTree is empty!");

        return findmax(root).element;
    }

    private BinaryTreeNode2<T> findmax(BinaryTreeNode2<T> p) {

        if (p == null)//结束条件
            return null;
        else if (p.right == null)
            return p;
        return findmax(p.right);
    }

    public T findMin() throws EmptyCollectionException {
        if (isEmpty())
            System.out.println("BinarySearchTree is empty!");

        return findmin(root).element;
    }

    private BinaryTreeNode2<T> findmin(BinaryTreeNode2<T> p) {
        if (p == null)//结束条件
            return null;
        else if (p.left == null)//如果没有左结点,那么t就是最小的
            return p;
        return findmin(p.left);
    }

    public T findMax(BinaryTreeNode2<T> root) throws EmptyCollectionException
    {
        T result= null;

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

        return result;
    }

    public T find(T targetElement) throws ElementNotFoundException 
    {
        BinaryTreeNode2<T> current = findNode(targetElement, root);

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

        return (current.getElement());
    }
    private BinaryTreeNode2<T> findNode(T targetElement, BinaryTreeNode2<T> next)
    {
        if (next == null )
            return null;
        if (!(targetElement instanceof Comparable))
            throw new NonComparableElementException("LinkedBinarySearchTree");
        if (next.getElement().equals(targetElement))
            return next;
        BinaryTreeNode2<T> temp=null;

        Comparable<T> comparebleElement = (Comparable<T>)targetElement;
        if (comparebleElement.compareTo(next.getElement())<0)
             temp = findNode(targetElement, next.getLeft());
        else
            temp = findNode(targetElement,next.getRight());

        return temp;

    }

    public LinkedBinarySearchTree<T> getLeft()
    {
        if(root == null)
            throw new EmptyCollectionException("Get left operation failed. The tree is empty.");


        LinkedBinaryTree2<T> result = new LinkedBinaryTree2<>();
        result.root = root.getLeft();
        return (LinkedBinarySearchTree<T>) result;
    }

    public LinkedBinarySearchTree<T> getRight()
    {
        if(root == null)
            throw new EmptyCollectionException("Get right operation failed. The tree is empty.");

        LinkedBinaryTree2<T> result = new LinkedBinaryTree2<>();
        result.root = root.getRight();
        return (LinkedBinarySearchTree<T>) result;
    }

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

        nodes.addToRear((BinaryTreeNode2<T>) 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;
    }

}