package Week07;

import Week04.Array.ArrayUnorderedList;
import Week04.ElementNotFoundException;
import Week04.jsjf.UnorderedListADT;
import jsjf.EmptyCollectionException;

import java.util.*;

/**
 * @author 20172323
 */
public class LinkedBinaryTree<T> implements Iterable<T>, BinaryTreeADT<T> {

	protected BinaryTreeNode<T> root;
	protected int modCount;
	private LinkedBinaryTree<T> left, right;

	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);
		this.left = left;
		this.right = right;
	}

	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);
//            try{
//                return (current.getElement());
//            }
//            catch (ElementNotFoundException n){
//                System.out.println();
//            }
//            catch (NullPointerException m){
//                System.out.println("txdashazi");
//            }
            if (current == null)
                return (T) new ElementNotFoundException("binary tree");
//               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;
	}

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

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

	public int getHeight() {
		BinaryTreeNode cur = root;
		int height = 0;
		if (root != null){
			height++;
		}
		cur = cur.left;
		while (cur.judge() != true){
			height++;
			cur = cur.left;
		}
		height++;
		return height;

	}

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

	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 String toString() {
		UnorderedListADT<BinaryTreeNode<T>> nodes = new ArrayUnorderedList<BinaryTreeNode<T>>();
		UnorderedListADT<Integer> levelList = new ArrayUnorderedList<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);
				nodes.addToRear(null);
				levelList.addToRear(currentLevel + 1);
				result = result + " ";
			}
		}

		return result;
	}

	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 toPreString(){
		preOrder(root);
	}
	private void preOrder(BinaryTreeNode root){
		if(null!= root){
			System.out.print(root.getElement() + "\t");
			preOrder(root.getLeft());
			preOrder(root.getRight());
		}
	}

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

	public void toInString(){
		inOrder(root);
	}
	private void inOrder(BinaryTreeNode root) {
		if (null != root) {
			inOrder(root.getLeft());
			System.out.print(root.getElement() + "\t");
			inOrder(root.getRight());
		}
	}

	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);
	}
	//层序输出非递归
	public void toLevelString2(){
		BinaryTreeNode temp;
		Queue<BinaryTreeNode> queue=new LinkedList<BinaryTreeNode>();
		queue.offer(root);
		while(!queue.isEmpty()){
			temp=queue.poll();
			System.out.print(temp.getElement()+"\n");
			if(null!=temp.getLeft())
				queue.offer(temp.getLeft());
			if(null!=temp.getRight()){
				queue.offer(temp.getRight());
			}
		}
	}

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