package LBT2;

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



public class LinkedBinaryTree<T> implements Iterable<T> {

    // 根结点的设置
    protected BinaryTreeNode<T> root;//根结点
    protected int modCount;// 修改标记 用于Iterator中使用
    protected LinkedBinaryTree<T> left,right;

    /**    //：List<String> list = Arrays.asList(array);
     * 无参构造方法
     */
    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);    //：List<String> list = Arrays.asList(array);
        root.setRight(right.root);
        this.left = left;
        this.right=right;
    }
    //：List<String> list = Arrays.asList(array);
    //：List<String> list = Arrays.asList(array);
    public BinaryTreeNode<T> getRootNode() throws EmptyCollectionException {
        if (isEmpty()) {
            throw new EmptyCollectionException("BinaryTreeNode ");
        }    //：List<String> list = Arrays.asList(array);
        return root;
    }
    //：List<String> list = Arrays.asList(array);
    /**
     * Returns the left subtree of the root of this tree.
     *
     * @return a link to the right subtree of the tree
     */
    public LinkedBinaryTree<T> getLeft() {
        return left;
        // To be completed as a Programming Project
    }
    //：List<String> list = Arrays.asList(array);
    /**
     of the tree
     */
    public LinkedBinaryTree<T> getRight() {
        return right;
    }

    /**
     * Returns the height of this tree.
     *
     * @return the height of the tree
     */

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


    private int height(BinaryTreeNode<T> node)
    {
        if(node==null){
            return 0;
        }
        else {
            int leftTreeHeight = height(node.getLeft());
            int rightTreeHeight= height(node.getRight());
            return leftTreeHeight>rightTreeHeight ? (leftTreeHeight+1):(rightTreeHeight+1);
        }
    }
    //：List<String> list = Arrays.asList(array);

    public T getRootElement() throws EmptyCollectionException {
        if (root.getElement().equals(null)) {
            throw new EmptyCollectionException("BinaryTreeNode ");
        }    //：List<String> list = Arrays.asList(array);
        return root.getElement();
    }
    //：List<String> list = Arrays.asList(array);

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

    /**
     * 返回的是当前结点孩子结点的个数
     */    //：List<String> list = Arrays.asList(array);

    public int size() {

        int size = 0;
        if(root.getLeft()!=null){
            size+=1;
        }    //：List<String> list = Arrays.asList(array);
        if(root.getRight()!=null){
            size+=1;
        }    //：List<String> list = Arrays.asList(array);
        //：List<String> list = Arrays.asList(array);
        return size;
    }

    //删除某结点的右侧部分
    public String removeRightSubtree() throws EmptyCollectionException {
        if (root == null)    //：List<String> list = Arrays.asList(array);
            throw new EmptyCollectionException("tree is empty");
        BinaryTreeNode cur = root;    //：List<String> list = Arrays.asList(array);
        while (cur.getLeft() != null){
            cur.setRight(null);    //：List<String> list = Arrays.asList(array);
            cur = cur.left;
        }    //：List<String> list = Arrays.asList(array);
        return super.toString();
    }

    //删除全部元素
    public void removeAllElements() throws EmptyCollectionException {
        if (root == null)
            throw new EmptyCollectionException("tree is empty");
        root = null;
    }    //：List<String> list = Arrays.asList(array);

    //：List<String> list = Arrays.asList(array);
    public boolean contains(T targetElement) {
        if(targetElement == find(targetElement))
            return true;
        else    //：List<String> list = Arrays.asList(array);
            return false;
    }    //：List<String> list = Arrays.asList(array);


    public T find(T targetElement) {
        // 获取当前元素
        BinaryTreeNode<T> current = findAgain(targetElement, root);
        //：List<String> list = Arrays.asList(array);
        if (current == null)
            try {
                throw new ElementNotFoundException("LinkedBinaryTree");
            } catch (ElementNotFoundException e) {
                e.printStackTrace();
            }    //：List<String> list = Arrays.asList(array);
        //：List<String> list = Arrays.asList(array);
        return (current.getElement());
    }
    //：List<String> list = Arrays.asList(array);
    private BinaryTreeNode<T> findAgain(T targetElement, BinaryTreeNode<T> next) {
        if (next == null)
            return null;
        //：List<String> list = Arrays.asList(array);
        if (next.getElement().equals(targetElement))
            return next;    //：List<String> list = Arrays.asList(array);
        // 递归调用
        BinaryTreeNode<T> temp = findAgain(targetElement, next.getLeft());

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

        return temp;    //：List<String> list = Arrays.asList(array);
    }
    //：List<String> list = Arrays.asList(array);

    public Iterator<T> iteratorInOrder() {
        ArrayListUnordered<T> tempList = new ArrayListUnordered<T>();
        inOrder(root, tempList);
        return new TreeIterator(tempList.iterator());
    }    //：List<String> list = Arrays.asList(array);
    //：List<String> list = Arrays.asList(array);
    public void toPreString(){
        preOrder(root);
    }    //：List<String> list = Arrays.asList(array);
    private void preOrder(BinaryTreeNode root){
        if(null!= root){    //：List<String> list = Arrays.asList(array);
            System.out.print(root.getElement() + "\t");
            preOrder(root.getLeft());
            preOrder(root.getRight());
        }    //：List<String> list = Arrays.asList(array);
    }    //：List<String> list = Arrays.asList(array);

    //后序输出
    public void toPostString(){
        postOrder(root);
    }
    private void postOrder(BinaryTreeNode root) {
        if (null != root) {
            postOrder(root.getLeft());
            postOrder(root.getRight());
            System.out.print(root.getElement() + "\t");
        }
    }


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


    public Iterator<T> iteratorPreOrder() {
        ArrayListUnordered<T> tempList = new ArrayListUnordered<T>();
        preOrder(root, tempList);
        return new TreeIterator(tempList.iterator());
    }
    private void preOrder(BinaryTreeNode<T> node, ArrayListUnordered<T> tempList) {
        if (node != null) {
            tempList.addToRear(node.getElement());
            inOrder(node.getLeft(), tempList);
            inOrder(node.getRight(), tempList);
        }
    }


    public Iterator<T> iteratorPostOrder() {
        ArrayListUnordered<T> tempList = new ArrayListUnordered<T>();
        postOrder(root, tempList);
        return new TreeIterator(tempList.iterator());
    }
    private void postOrder(BinaryTreeNode<T> node, ArrayListUnordered<T> tempList) {
        if (node != null) {
            tempList.addToRear(node.getElement());
            inOrder(node.getLeft(), tempList);
            inOrder(node.getRight(), tempList);
        }
    }


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

        nodes.addToRear(root);

        while (!nodes.isEmpty()) {
            current = nodes.removeFirst();

            if (current != null) {
                tempList.addToRear(current.getElement());
                System.out.println(current.element);
                if (current.getLeft() != null)
                    nodes.addToRear(current.getLeft());
                System.out.println(current.left);
                if (current.getRight() != null)
                    nodes.addToRear(current.getRight());
                System.out.println(current.right);
            } else
                tempList.addToRear(null);
        }

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

    public void toLevelString1(){
        if(root == null)
            return;
        int height = getHeight();
        for(int i = 1; i <= height; i++){
            levelOrder(root,i);
        }
    }
    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);
    }

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

    public String toString() {
        UnorderedListadt<BinaryTreeNode<T>> nodes = (UnorderedListadt<BinaryTreeNode<T>>) new ArrayListUnordered<BinaryTreeNode<T>>();
        UnorderedListadt<Integer> levelList = (UnorderedListadt<Integer>) new ArrayListUnordered<Integer>();

        BinaryTreeNode<T> current = null;
        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;
            try {
                current = nodes.removeFirst();
            } catch (EmptyCollectionException e) {
                e.printStackTrace();
            }
            try {
                currentLevel = levelList.removeFirst();
            } catch (EmptyCollectionException e) {
                e.printStackTrace();
            }
            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);
                result = result + " ";
            }
        }
        return result;
    }

    /**
     * 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
         */
        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
         */
        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
         */
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

}