package srcNo16.TextbookCode.jsjf;

import java.util.*;

import srcNo14.TextbookCode.UnorderedListADT;
import srcNo14.pp6_8.ArrayUnorderedList;
import srcNo16.HashPractice.LinearNode;
import srcNo16.TextbookCode.jsjf.exceptions.ElementNotFoundException;
import srcNo16.TextbookCode.jsjf.exceptions.EmptyCollectionException;


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

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

    public T getRootElement() throws EmptyCollectionException
    {
        return root.getElement();
    }
    

    protected BinaryTreeNode<T> getRootNode() throws EmptyCollectionException
    {
        return root;
    }
    

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


        LinkedBinaryTree<T> result = new LinkedBinaryTree<>();
        result.root = root.getLeft();
        return result;


    }


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

        LinkedBinaryTree<T> result = new LinkedBinaryTree<>();
        result.root = root.getRight();
        return result;

    }
    

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


    public int size()
    {
        int result = 0;

        if(root != null)
            result = root.count();

        return result;

    }


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



    private int height(BinaryTreeNode<T> node) {
        if (node == null) {
            return 0;
        } else {
            int l = height(node.left);
            int r = height(node.right);
            return (l > r) ? (l + 1) : (r + 1);
        }
    }

    public int num = 0;

    public int CountLeaf (LinkedBinaryTree T) {
        LinkedBinaryTree<T> temp = T;
        if(temp.root.getLeft()==null&&temp.root.getRight()==null) {
            num++;
        }


        if(temp.root.getLeft()!=null){
            CountLeaf(temp.getLeft());
        }

        if(temp.root.getRight()!=null) {
            CountLeaf(temp.getRight());
        }


        return num ;
    }



    public boolean contains(T targetElement)
    {

        if(findNode(targetElement,root) != null)
            return true;
        else
            return false;
    }
    

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



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

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


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


    public Iterator<T> iteratorPreOrder()
    {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        preOrder(root, tempList);

        return new TreeIterator(tempList.iterator());
    }


    protected void preOrder(BinaryTreeNode<T> node,
                            ArrayUnorderedList<T> tempList)
    {

        if (node != null)
        {
            tempList.addToRear(node.getElement());
            preOrder(node.getLeft(), tempList);
            preOrder(node.getRight(), tempList);
        }

    }


    public Iterator<T> iteratorPostOrder()
    {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        postOrder(root, tempList);

        return new TreeIterator(tempList.iterator());
    }


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

        }
    }


    public Iterator<T> iteratorLevelOrder() 
    {
        ArrayUnorderedList<BinaryTreeNode<T>> nodes = 
                              new ArrayUnorderedList<BinaryTreeNode<T>>();
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<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());
    }

    public Iterator<T> levelOrder2(){
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        int depth = getHeight();

        for (int i = 1; i <= depth; i++) {
            iteratorLevelOrder2(root,tempList, i);
        }
        return new TreeIterator(tempList.iterator());
    }

    public void iteratorLevelOrder2(BinaryTreeNode<T> node,ArrayUnorderedList<T> tempList,int ht){
        if (node == null || ht < 1) {
            return;
        }

        if (ht == 1) {
            tempList.addToRear(node.getElement());
            return;
        }

        iteratorLevelOrder2(node.left, tempList,ht - 1);

        iteratorLevelOrder2(node.right, tempList,ht - 1);
    }


    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){
        BinaryTreeNode temp = findNode(element,root);
        if(temp.getRight()==null)
            System.out.println("this node is enpty");
        else
            temp.setRight(null);
    }

    public void removeAllElements(){
        root = null;
    }
}