package second_term.tenth_chapter;

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

import java.util.*;


public class LinkedBinaryTree<T> implements BinaryTreeADT<T>, Iterable<T>
{
    public BinaryTreeNode<T> root;
    public int modCount;
    public LinkedBinaryTree<T> left,right;

    public LinkedBinaryTree() 
    {
        root = null;
    }


    public LinkedBinaryTree(T element) 
    {
        root = new BinaryTreeNode<T>(element);
    }
    

    public LinkedBinaryTree(T element, LinkedBinaryTree<T> left,
                            LinkedBinaryTree<T> right)
    {
        root = new BinaryTreeNode<T>(element);
        root.setLeft(left.root);
        root.setRight(right.root);
        this.left = left;
        this.right = left;
    }
    

    public T getRootElement() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException("tree");
        return root.element;
    }

    protected BinaryTreeNode<T> getRootNode() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException("tree");
        return root;
    }

    public LinkedBinaryTree<T> getLeft()
    {
        return left;
    }

    public LinkedBinaryTree<T> getRight()
    {
       return right;
    }

    public boolean isEmpty() 
    {
        return (root == null);
    }


    public int size() 
    {
       return root.numChildren();
//        int leftNum = 0;
//        int rightNum= 0;

//        if(node.left != null){
//            leftNum = getNumberOfNode(node.left);
//        }
//        if(node.right != null){
//            rightNum = getNumberOfNode(node.right);
//        }
//        return leftNum + rightNum + 1;
    }

     public int getHeight()
    {
       return height(root);
    }

    private int height(BinaryTreeNode<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 int CountLeaf(BinaryTreeNode tree){
        if (tree!=null){
            if (tree.getLeft()==null&&tree.getRight()==null)
                return 1;
            else
                return CountLeaf(tree.getLeft())+CountLeaf(tree.getRight());
        }
        else
            return 0;
    }
    

    public boolean contains(T targetElement) 
    {
        return findNode(targetElement,root)==null;
    }//PP10.5

    public T find(T targetElement) throws ElementNotFoundException
    {
        BinaryTreeNode<T> current = findNode(targetElement, root);
        
        if (current == null)
            throw new ElementNotFoundException("LinkedBinaryTree");
        
        return (current.getElement());
    }


    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;
    }



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

        nodes.addToRear((BinaryTreeNode<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;
    }


    public Iterator<T> iterator()
    {
        return iteratorInOrder();
    }
    

    public Iterator<T> iteratorInOrder()
    {
        UnorderedListArrayList<T> tempList = new UnorderedListArrayList<>();
        inOrder(root, tempList);
        
        return new TreeIterator(tempList.iterator());
    }


    protected void inOrder(BinaryTreeNode<T> node, 
                           UnorderedListArrayList<T> tempList)
    {
        if (node != null)
        {
//            System.out.println(node.getElement()+" ");
            inOrder(node.getLeft(), tempList);
            tempList.addToRear(node.getElement());
            inOrder(node.getRight(), tempList);
        }
    }


    public Iterator<T> iteratorPreOrder() 
    {
        UnorderedListArrayList<T> tempList = new UnorderedListArrayList<>();
        preOrder(root,tempList);
        return new TreeIterator(tempList.iterator());
    }


    protected void preOrder(BinaryTreeNode<T> node, 
                            UnorderedListArrayList<T> tempList)
    {
        if (node!=null) {
            tempList.addToRear(node.getElement());
            preOrder(node.getLeft(), tempList);
            preOrder(node.getRight(), tempList);
        }
    }


    public Iterator<T> iteratorPostOrder() 
    {
        UnorderedListArrayList<T> tempList = new UnorderedListArrayList<>();
        postOrder(root,tempList);
        return new TreeIterator(tempList.iterator());
    }


    protected void postOrder(BinaryTreeNode<T> node, 
                             UnorderedListArrayList<T> tempList)
    {
        postOrder(node.getLeft(),tempList);
        postOrder(node.getRight(),tempList);
        tempList.addToRear(node.getElement());
    }


    public Iterator<T> iteratorLevelOrder() 
    {
        UnorderedListArrayList<BinaryTreeNode<T>> nodes =
                              new UnorderedListArrayList<BinaryTreeNode<T>>();
        UnorderedListArrayList<T> tempList = new UnorderedListArrayList<T>();
        BinaryTreeNode<T> current;

        nodes.addToRear(root);
        
        while (!nodes.isEmpty()) 
        {
            current = nodes.removefirst();
            
            if (current != null)
            {
                tempList.addToRear(current.getElement());
                if (current.getLeft() != null)
                    nodes.addToRear(current.getLeft());
                if (current.getRight() != null)
                    nodes.addToRear(current.getRight());
            }
            else
                tempList.addToRear(null);
        }
        
        return new TreeIterator(tempList.iterator());
    }
    

    private class TreeIterator implements Iterator<T>
    {
        private int expectedModCount;
        private Iterator<T> iter;
        

        public TreeIterator(Iterator<T> iter)
        {
            this.iter = iter;
            expectedModCount = modCount;
        }
        

        public boolean hasNext() throws ConcurrentModificationException
        {
            if (!(modCount == expectedModCount))
                throw new ConcurrentModificationException();
            
            return (iter.hasNext());
        }
        

        public T next() throws NoSuchElementException
        {
            if (hasNext())
                return (iter.next());
            else 
                throw new NoSuchElementException();
        }

        public void remove()
        {
            throw new UnsupportedOperationException();
        }
    }
    public void removeRightSubtree(T element){//PP10.1
    BinaryTreeNode temp = findNode(element,root);
    if(temp.getRight()==null)
        System.out.println("this node is enpty");
    else
        temp.setRight(null);
}

    public void removeAllElements(){//PP10.1
        root = null;
    }

    public void NoRecursionLevelOrder(){
        int height = getHeight();
        if(root != null)
            for(int x = 1; x <= height; x++){
                levelOrder(root,x);
            }
    }
    //迭代层序遍历
    private void levelOrder(BinaryTreeNode root,int level){
        if(root == null || level < 1){
            return;
        }
        if(level == 1){
            System.out.print(root.getElement() + "\n");
            return;
        }
        levelOrder(root.getLeft(),level - 1);
        levelOrder(root.getRight(),level - 1);
    }

    //非迭代层序遍历
    public void RecursionLevelOrder(){
        UnorderedListArrayList<BinaryTreeNode<T>> list = new UnorderedListArrayList<BinaryTreeNode<T>>();
        UnorderedListArrayList<T> tempList = new UnorderedListArrayList<T>();
        BinaryTreeNode<T> current;

        list.addToRear(root);
        while(!list.isEmpty()){
            current=list.removefirst();
            System.out.println(current.getElement()+"   ");

            if (current != null)
            {
                tempList.addToRear(current.getElement());
                if (current.getLeft() != null)
                    list.addToRear(current.getLeft());
                if (current.getRight() != null)
                    list.addToRear(current.getRight());
            }
            else
                tempList.addToRear(null);
        }
    }

}