package week8;

import java.util.*;

import jsjf.BinaryTreeADT;
import jsjf.exceptions.*;
import week4.ArrayUnorderedList;

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 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);   
    }
    
    // 返回树的根元素。
    public T getRootElement() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException("ArrayBinaryTree");

        return tree[0];
    }

    // 如果此二叉树为空，则返回true，否则返回false。
    public boolean isEmpty() 
    {
        return (count == 0);
    }

    // 返回这个二叉树的整数大小。
    public int size() 
    {
        return count;
    }
    
    // 如果该树包含与指定目标元素匹配的元素，则返回true，否则返回false。
    public boolean contains(T targetElement) 
    {
        T temp;
        boolean found = false;
        
        try 
        {
            temp = find(targetElement);
            found = true;
        }
        catch (Exception ElementNotFoundException) 
        {
            found = false;
        }
        
        return found;
    }

    // 如果在此二叉树中找到指定目标元素，则返回对该元素的引用。
    // 如果在二叉树中没有找到指定的目标元素，则抛出ElementNotFoundException。
    public T find(T targetElement) throws ElementNotFoundException 
    {
        T temp = null;
        boolean found = false;
        
        for (int i = 0; i < tree.length && !found; i++)
            if (tree[i] != null)
                if (targetElement.equals(tree[i]))
                {
	                found = true;
                    temp = tree[i];
                }

        if (!found)
            throw new ElementNotFoundException("ArrayBinaryTree");

        return temp;
    }


    // 返回这个二叉树的字符串表示形式，以中序的方式显示节点。
    public String toString() 
    {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        inOrder(0, tempList);

        return tempList.toString();
    }

    // 使用iteratorInOrder方法在这个二叉树的元素上返回一个迭代器
    public Iterator<T> iterator() 
    {
        return this.iteratorInOrder();
    }
    
	// 通过调用从根开始的重载递归inorder方法，对这个二叉树执行inorder遍历。
    public Iterator<T> iteratorInOrder() 
    {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        inOrder(0, tempList);

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

    // 执行递归的中序遍历。
    protected void inOrder(int node, ArrayUnorderedList<T> tempList) 
    {
        if (node < tree.length)
            if (tree[node] != null)
            {
                inOrder(node * 2 + 1, tempList);
                tempList.addToRear(tree[node]);
                inOrder((node + 1) * 2, tempList);
            }
    }

    // 通过调用从根开始的重载递归先序方法，对这个二叉树执行先序遍历。
    public Iterator<T> iteratorPreOrder() 
    {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        preOrder(0, tempList);

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

    // 执行递归预序遍历。
    protected void preOrder(int node, ArrayUnorderedList<T> tempList) 
    {
        if (node < tree.length)
            if (tree[node] != null) 
 	        { 
                tempList.addToRear(tree[node]);
                preOrder(node * 2 + 1, tempList);
                preOrder((node + 1) * 2, tempList);
            }
    }

    // 通过调用从根开始的重载递归后序方法，在二叉树上执行一个后序遍历。
    public Iterator<T> iteratorPostOrder() 
    {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        postOrder(0, tempList);

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

    // 执行递归后序遍历
    protected void postOrder(int node, ArrayUnorderedList<T> tempList) 
    {
        if (node < tree.length)
            if (tree[node] != null) 
 	        {
                postOrder(node * 2 + 1, tempList); 
                postOrder((node + 1) * 2, tempList);
                tempList.addToRear(tree[node]);  
            }
    }

    // 使用tempList对这个二叉树执行层序遍历。
    public Iterator<T> iteratorLevelOrder() 
    {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        int ct = 0; // current number of elements added to list
        int i = 0; // current position in array
        
        while (ct < count)
        {
            if (tree[i] != null)
            {
                tempList.addToRear(tree[i]);
                ct++;
            }
            i++;
        }
        
        return new TreeIterator(tempList.iterator());
    }

	private class TreeIterator implements Iterator<T>
	{
		private int expectedModCount;
		private Iterator<T> iter;

		public TreeIterator(Iterator<T> iter)
		{
			this.iter = iter;
			expectedModCount = modCount;
		}
		
		// 如果迭代器在迭代中至少有一个元素要交付，则返回true。
		public boolean hasNext() throws ConcurrentModificationException
		{
			if (!(modCount == expectedModCount))
				throw new ConcurrentModificationException();
				
			return (iter.hasNext());
		}
		
		// 返回迭代中的下一个元素。如果这个迭代中没有更多的元素，就会抛出NoSuchElementException。
		public T next() throws NoSuchElementException
		{
			if (hasNext())
				return (iter.next());
			else 
				throw new NoSuchElementException();
		}

		public void remove()
		{
			throw new UnsupportedOperationException();
		}
	}
}