package week6;



import week4.ArrayUnorderedList;
import week4.ElementNotFoundException;
import week2.EmptyCollectionException;


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


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

    protected BinaryTreeNode<T> root;
    protected int modCount;

    /**
     * 无参构造方法
     */
    public LinkedBinaryTree() {
        root = null;
    }

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

    public LinkedBinaryTree(BinaryTreeNode<T> ltn) {
        this.root = ltn;
    }

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

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

    //删除全部元素
    public String removeAllElements() throws EmptyCollectionException {
        if (root == null)
            throw new EmptyCollectionException("tree is empty");
        while (root.getLeft() != null){
            root.setRight(null);
            root = root.left;
        }
        root = null;
        return super.toString();
    }

    @Override
    public boolean contains(T targetElement) {
        BinaryTreeNode<T> current = findAgain(targetElement, root);
        return current.getElement() == targetElement;
    }

    // 获取当前元素
    @Override
    public T find(T targetElement) {
        BinaryTreeNode<T> current = findAgain(targetElement, root);

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

        return (current.getElement());
    }

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

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

    /**
     * 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 new LinkedBinaryTree(this.root.getLeft());
    }

    /**
     * Returns the right subtree of the root of this tree.
     *
     * @return a link to the right subtree of the tree
     */
    public LinkedBinaryTree<T> getRight() {
        return new LinkedBinaryTree(this.root.getRight());
    }

    public int getHeight() {
        return 0;
    }

    private int height(BinaryTreeNode<T> node) {
        return 0;
    }

    @Override
    public T getRootElement() throws EmptyCollectionException {
        if (root.getElement().equals(null)) {
            throw new EmptyCollectionException("BinaryTreeNode ");
        }
        return root.getElement();
    }

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

    /**
     * 返回的是当前结点孩子结点的个数
     */
    @Override
    public int size() {

        int size = 0;
        if(root.getLeft()!=null){
            size+=1;
        }
        if(root.getRight()!=null){
            size+=1;
        }

        return size;
    }
    /**
     * 中序遍历
     */
    @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);
        }
    }

    /**
     * 前序遍历
     */
    public Iterator<T> iteratorPreOrder() {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        preOrder(root, tempList);
        return new TreeIterator(tempList.iterator());
    }

    /**
     * Performs a recursive preorder traversal.
     *
     * @param node
     *            the node to be used as the root for this traversal
     * @param tempList
     *            the temporary list for use in this traversal
     */
    private void preOrder(BinaryTreeNode<T> node, ArrayUnorderedList<T> tempList) {
        if (node != null) {
            tempList.addToRear(node.getElement());
            inOrder(node.getLeft(), tempList);

            inOrder(node.getRight(), tempList);
        }

    }

    /**
     * 后序遍历
     */
    @Override
    public Iterator<T> iteratorPostOrder() {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        postOrder(root, tempList);
        return new TreeIterator(tempList.iterator());
    }

    private void postOrder(BinaryTreeNode<T> node,
                           ArrayUnorderedList<T> tempList) {

        if (node != null) {
            tempList.addToRear(node.getElement());
            inOrder(node.getLeft(), tempList);

            inOrder(node.getRight(), tempList);
        }

    }

    /**
     * 层序遍历
     */
    @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());
    }

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

    public void oString() {
        string(root);
    }
    private void string(BinaryTreeNode temp){
        if(temp != null){
            string(temp.getRight());
            System.out.println(temp.getElement() + " ");
            string(temp.getLeft());
        }
    }

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