package chap12;

import chap10.ArrayUnorderedList;
import chap3.EmptyCollectionException;
import chap6.ElementNotFoundException;

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



/**
 * @author LbZhang
 * @version 创建时间：2015年11月22日 上午11:04:36
 * @description 二叉树的构建
 */
public class LinkedBinaryTree<T> implements Iterable<T>, BinaryTreeADT<T> {

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

	// protected int sizeOfLTree;

	/**
	 * 无参构造方法
	 */
	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);
	}

	/**
	 * 获取根节点
	 * 
	 * @return
	 */
	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());
		// To be completed as a Programming Project
	}

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

	/**
	 * Returns the height of this tree.
	 * 
	 * @return the height of the tree
	 */
	public int getHeight() {
		return 0;
		// To be completed as a Programming Project
	}

	/**
	 * Returns the height of the specified node.
	 * 
	 * @param node
	 *            the node from which to calculate the height
	 * @return the height of the tree
	 */
	private int height(BinaryTreeNode<T> node) {
		return 0;
		// To be completed as a Programming Project
	}

	@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 boolean contains(T targetElement) {
		return false;
	}

	@Override
	public T find(T targetElement) {
		// 获取当前元素
		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;
	}

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

	/**
	 * Performs a recursive inorder traversal. 中根遍历
	 * 
	 * @param node
	 *            the node to be used as the root for this traversal
	 * @param tempList
	 *            the temporary list for use in this traversal
	 */
	protected void inOrder(BinaryTreeNode<T> node,
			ArrayUnorderedList<T> tempList) {
		if (node != null) {
			inOrder(node.getLeft(), tempList);
			tempList.addToRear(node.getElement());
			inOrder(node.getRight(), tempList);
		}
	}

	/**
	 * Performs an preorder traversal on this binary tree by calling an
	 * overloaded, recursive preorder method that starts with the root.
	 * 
	 * @return a pre order iterator over this tree
	 */
	@Override
	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);
		}

	}

	/**
	 * Performs an postorder traversal on this binary tree by calling an
	 * overloaded, recursive postorder method that starts with the root.
	 * 
	 * @return a post order iterator over this tree
	 */
	@Override
	public Iterator<T> iteratorPostOrder() {
		ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
		postOrder(root, tempList);
		return new TreeIterator(tempList.iterator());
	}

	/**
	 * Performs a recursive postorder 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 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();
	}

	@Override
	public String toString() {
		// TODO Auto-generated method stub
		return super.toString();
	}

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