package week6.jsjf;

import weeek3.jsjf.LinkedQueue;
import week4.jsjf.ArrayUnorderedList;
import week4.jsjf.UnorderedListADT;
import week6.jsjf.exceptions.ElementNotFoundException;
import week6.jsjf.exceptions.EmptyCollectionException;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * LinkedBinaryTree实现了BinaryTreeADT接口
 * 
 * @author Lewis and Chase
 * @version 4.0
 */
public class LinkedBinaryTree<T> implements BinaryTreeADT<T>, Iterable<T>
{
    public BinaryTreeNode<T> root;
    protected int modCount;
    LinkedBinaryTree left,right;

    /**
     * 创建一个空的二叉树
     */
    public LinkedBinaryTree() 
    {
        root = null;
    }

    /**
     * 创建以指定元素为根的二叉树
     *
     * @param element 成为二叉树的根的元素
     */
    public LinkedBinaryTree(T element)
    {
        root = new BinaryTreeNode<T>(element);
    }
    
    /**
     * 创建以指定元素为根的元素并将给定的树作为他的左孩子和右孩子
     *
     * @param element 将成为二叉树根的元素
     * @param left 树的左子树
     * @param right 数的右子树
     */
    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=right;
       }
       public void removeAllelement(){
        root.setLeft(null);
        root.setRight(null);
        root=null;
       }
       public void removeLeftsubtree(){
        root.setLeft(null);
       }
       public void removeRightsubtree(){
        root.setRight(null);
       }

    
    /**
     * 返回根元素的引用
     *
     * @return 指定元素的引用
     * @throws EmptyCollectionException 如果树为空
     */
    @Override
    public T getRootElement() throws EmptyCollectionException
    {

        if (root.getElement()==null) {
            throw new EmptyCollectionException("BinaryTreeNode ");
        }
        return root.getElement();
    }

    
    /**
     * 返回根节点的引用
     *
     * @return 指定结点的引用
     * @throws EmptyCollectionException i如果树为空
     */
    public BinaryTreeNode<T> getRootNode() throws EmptyCollectionException
    {
        if (root==null)
            throw new EmptyCollectionException("LinkedBinaryTree");

        return root;
    }
    
    /**
     * 返回树的根的左子树
     *
     * @return 树的左子树的一个链接
     */
    public LinkedBinaryTree<T> getLeft()
    {
        return left;
    }

    /**
     * 返回树的根的右子树
     *
     * @return 树的右子树的链接
     */
    public LinkedBinaryTree<T> getRight()
    {
        return right;
    }
    
    /**
     *如果此二叉树为空，则返回true，否则返回false。
     * @return 如果这个二叉树为空，则为真，否则为假
     */
    @Override
    public boolean isEmpty()
    {
        return (root == null);
    }

    /**
     * 返回树的元素总数的整数型
     *
     * @return 数的整数型大小
     */
    @Override
    public int size()
    {
        return root.numChildren()+1;
    }
    
    /**
     * Returns the height of this tree.
     *
     * @return the height of the tree
     */
     public int getHeight()
    {
        return height(root);
    }
    
    /**
     * 返回指定节点的高度。
     *
     * @param node 开始计算高度的结点
     * @return 树的高度
     */
    public  int height(BinaryTreeNode<T> node)
    {
       if (node==null)
           return 0;

       int leftlength=height(node.getLeft());
       int rightlength=height(node.getRight());

       return  leftlength> rightlength ? leftlength + 1 : rightlength + 1;

    }
    
    /**
     * 如果该树包含一个元素，则返回true指定目标元素，否则为false。
     * @param targetElement 在树中被搜寻的元素
     * @return 如果元素在树中返回真否则返回假
     */
    @Override
    public boolean contains(T targetElement)
    {
      if (findAgain(targetElement,root)==null)
          return false;
      else
          return true;
    }
    public void preorder(BinaryTreeNode node) {
                 if (node != null) {
                         System.out.print(node.getElement());
                         preorder(node.getLeft());
                         preorder(node.getRight());
                     }
             }//先序遍历
    public void Inorder(BinaryTreeNode node) {
               if (node != null) {
                         Inorder(node.getLeft());
                         System.out.print(node.getElement());
                         Inorder(node.getRight());
                     }
             }//中序遍历
    public void postorder(BinaryTreeNode node) {
              if (node != null) {
                         postorder(node.left);
                         postorder(node.right);
                         System.out.print(node.getElement());
                     }
             }//后序遍历
    LinkedQueue<BinaryTreeNode> B=new LinkedQueue<>();
    public void unrecursionlevelOreder(BinaryTreeNode node) throws InterruptedException {
        B.enqueue(node);
        while(B.size()!=0)
        { BinaryTreeNode a;
            a=B.first();
            System.out.print(a.getElement());
            if (B.first().getLeft()!=null)
                B.enqueue(B.first().getLeft());
            if(B.first().getRight()!=null)
                B.enqueue(B.first().getRight());
            B.dequeue(); } }//非递归实现层序遍历


    /**
     * 返回对指定目标元素的引用在这个二叉树中发现。抛出一个ElementNotFoundException 如果在二叉树中没有找到指定的目标元素。
     *
     * @param targetElement 在树中被搜寻的元素
     * @return 指定元素的引用
     * @throws ElementNotFoundException 如果元素不在树中
     */
    @Override
    public T find(T targetElement) throws ElementNotFoundException
    {
        BinaryTreeNode<T> current = findAgain(targetElement, root);
        
        if (current == null)
            throw new ElementNotFoundException("LinkedBinaryTree");
        
        return (current.getElement());
    }

    /**
     * 返回一个指定元素的引用如果它在树中
     *
     * @param targetElement 在树中被查找的元素
     * @param next 开始进行搜索的元素
     */
    private BinaryTreeNode<T> findAgain(T targetElement,BinaryTreeNode<T> next)
    {
        if (next == null)
            return null;
        
        if (next.getElement().equals(targetElement))
            return next;
        
        BinaryTreeNode<T> temp = findAgain(targetElement, next.getLeft());
        
        if (temp == null)
            temp = findAgain(targetElement, next.getRight());
        
        return temp;
    }
    
    /**
     *返回显示的二叉树的字符串表示形式以有序的方式显示节点。
     *
     * @return 二叉树的字符串表示
     */

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


    /**
     * 返回一个迭代器包括树中的元素使用iteratorInOrder 方法
     *
     * @return 顺序迭代二叉树
     */
    @Override
    public Iterator<T> iterator()
    {
        return iteratorInOrder();
    }
    
    /**
     * Performs an inorder traversal on this binary tree by calling an
     * overloaded, recursive inorder method that starts with
     * the root.
     *
     * @return an in order iterator over this binary tree
     */
    @Override
    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);
        }
    }


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


    @Override
    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());
        }
    }


    @Override
    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());
    }
    
    /**
     * Inner class to represent an iterator over the elements of this tree
     */
    private class TreeIterator implements Iterator<T>
    {
        private int expectedModCount;
        private Iterator<T> iter;
        
        /**
         * Sets up this iterator using the specified iterator.
         *
         * @param iter the list iterator created by a tree traversal
         */
        public TreeIterator(Iterator<T> iter)
        {
            this.iter = iter;
            expectedModCount = modCount;
        }
        
        /**
         * Returns true if this iterator has at least one more element
         * to deliver in the iteration.
         *
         * @return  true if this iterator has at least one more element to deliver
         *          in the iteration
         * @throws  ConcurrentModificationException if the collection has changed
         *          while the iterator is in use
         */
        @Override
        public boolean hasNext() throws ConcurrentModificationException
        {
            if (!(modCount == expectedModCount))
                throw new ConcurrentModificationException();
            
            return (iter.hasNext());
        }
        
        /**
         * Returns the next element in the iteration. If there are no
         * more elements in this iteration, a NoSuchElementException is
         * thrown.
         *
         * @return the next element in the iteration
         * @throws NoSuchElementException if the iterator is empty
         */
        @Override
        public T next() throws NoSuchElementException
        {
            if (hasNext())
                return (iter.next());
            else 
                throw new NoSuchElementException();
        }
        
        /**
         * The remove operation is not supported.
         * 
         * @throws UnsupportedOperationException if the remove operation is called
         */
        @Override
        public void remove()
        {
            throw new UnsupportedOperationException();
        }
    }
}