package chap12;

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

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




/** 
 * @author LbZhang
 * @version 创建时间：2015年11月30日 上午10:44:08 
 * @description 类说明
 */
public class ArrayBinaryTree<T> implements BinaryTreeADT<T>, Iterable<T> {

	private static final int DEFAULT_CAPACITY = 50;
	
	protected int count;
	protected T[] tree;//持有数组用于实现堆
	protected int modCount;
	public BTNode<T> root;
	public ArrayBinaryTree(){
		count = 0;
		tree = (T[])new Object[DEFAULT_CAPACITY];
	}
	
	public ArrayBinaryTree(T element){
		count = 1;
		tree = (T[])new Object[DEFAULT_CAPACITY];
		tree[0] = element;
	}
	
	protected void expandCapacity(){
		tree=Arrays.copyOf(tree, tree.length*2);
	}
	
	@Override
	public T getRootElement() throws EmptyCollectionException{
		if(isEmpty()){
			throw new EmptyCollectionException("ArrayBinaryTree");
		}
		return tree[0];
	}

	@Override
	public boolean isEmpty() {
		return count==0;
	}

	@Override
	public int size() {
		return count;
	}

	@Override
	public boolean contains(T targetElement) {
		T temp;
		boolean found = false;
		
		try{
			temp = find(targetElement);
			found = true;
		}catch(Exception ElementNotFoundException){
			found = false;
		}
		
		return found;
	}

	@Override
	public T find(T targetElement) throws ElementNotFoundException {
	
		T temp = null;
		boolean found = false;
		
		for(int i=0;i<tree.length;i++){
			if(tree[i]!=null){
				if(targetElement.equals(tree[i])){
					found = true;
					temp=tree[i];
				}
				
			}
		}
		
		if(!found){
			throw new ElementNotFoundException("ArrayBinaryTree");
		}
		
		return temp;
	}
	
	@Override
	public String toString() {
		ArrayList<T> tempList = new ArrayList<T>();
		///用于临时存储连理获取的对象的引用的队列
		inOrder(0,tempList);
		return tempList.toString();
	}

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

	@Override
	public Iterator<T> iteratorInOrder() {
		ArrayList<T> tempList = new ArrayList<>();
		inOrder(0, tempList);
		return new TreeIterator(tempList.iterator());
	}
	
	protected void inOrder(int root,ArrayList<T> tempList){
		if(root<tree.length){
			if(tree[root]!=null){
				inOrder(root*2+1, tempList);
				tempList.add(tree[root]);
				inOrder(root*2+2, tempList);
			}
		}
	}

	@Override
	public Iterator<T> iteratorPreOrder() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Iterator<T> iteratorPostOrder() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Iterator<T> iteratorLevelOrder() {
		// TODO Auto-generated method stub
		return null;
	}
	

	/**
	 * 自定义一个TreeIterator类
	 * @author MrLBZ
	 *
	 */
	private class TreeIterator implements Iterator<T>
	{
		private int expectedModCount;
		private Iterator<T> iter;
	
		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();
		}
	}

}