#ifndef BINARYTREE_H
#define BINARYTREE_H

#include <iostream>
#include <iomanip>
#include <stack>
#include <queue>
using namespace std;

template <class T> class inorderIterator;
template <class T> class postorderIterator;
template <class T> class preorderIterator;
template <class T> class levelorderIterator;
template <class T> class binaryTree;
template <class T>
class binaryTreeNode
{
	friend class inorderIterator<T>;
	friend class postorderIterator<T>;
	friend class preorderIterator<T>;
	friend class levelorderIterator<T>;
	friend class binaryTree<T>;
public:
	binaryTreeNode();
	binaryTreeNode(const T& d, binaryTreeNode<T>* l, binaryTreeNode<T>* r)
	{
		data = d;
		leftChild = l;
		rightChild = r;
	};

private:
	binaryTreeNode* leftChild;
	binaryTreeNode* rightChild;
	T data;
};
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

template <class T> class inorderIterator;
template <class T> class postorderIterator;
template <class T> class preorderIterator;
template <class T> class levelorderIterator;
template <class T>
class binaryTree
{
	friend class inorderIterator<T>;
	friend class postorderIterator<T>;
	friend class preorderIterator<T>;
	friend class levelorderIterator<T>;
public:
	binaryTree()	{	root = NULL;};

	//Create a full binary tree of 7 nodes for testing, 
	//and data in the nodes are all integers and increase by level order
	void createTesting();
	void printInFourOrders();
private:
	binaryTreeNode<T>* root;

};

template <class T>
void binaryTree<T>::createTesting()
{
	binaryTreeNode<int>* temp7 = new binaryTreeNode<int>(7, NULL, NULL);
	binaryTreeNode<int>* temp6 = new binaryTreeNode<int>(6, NULL, NULL);
	binaryTreeNode<int>* temp5 = new binaryTreeNode<int>(5, NULL, NULL);
	binaryTreeNode<int>* temp4 = new binaryTreeNode<int>(4, NULL, NULL);
	binaryTreeNode<int>* temp3 = new binaryTreeNode<int>(3, temp6, temp7);
	binaryTreeNode<int>* temp2 = new binaryTreeNode<int>(2, temp4, temp5);
	binaryTreeNode<int>* temp1 = new binaryTreeNode<int>(1, temp2, temp3);
	root = temp1;
}

template <class T>
void binaryTree<T>::printInFourOrders()
{
	T* i = NULL;
	cout<<"inorder display:"<<endl;
	inorderIterator<T> inorderIt(*this);
	while ( (i=inorderIt.next()) != NULL )
		cout<<setw(4)<<*i;
	cout<<endl;

	cout<<"postorder display:"<<endl;
	postorderIterator<T> postorderIt(*this);
	while ( (i=postorderIt.next()) != NULL )
		cout<<setw(4)<<*i;
	cout<<endl;

	cout<<"preorder display:"<<endl;
	preorderIterator<T> preorderIt(*this);
	while ( (i=preorderIt.next()) != NULL )
		cout<<setw(4)<<*i;
	cout<<endl;

	cout<<"levelorder display:"<<endl;
	levelorderIterator<T> levelorderIt(*this);
	while ( (i=levelorderIt.next()) != NULL )
		cout<<setw(4)<<*i;
	cout<<endl;
	
}
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

template <class T>
class inorderIterator
{
public:
	inorderIterator(binaryTree<T> tree)	{	t.root = current = tree.root;};
	T* next();
private:
	binaryTree<T> t;
	stack<binaryTreeNode<T>*> s;
	binaryTreeNode<T>* current;
};

template <class T>
T* inorderIterator<T>::next()
{
	while ( current!=NULL )
	{
		s.push(current);
		current = current->leftChild;
	}
	
	if ( !s.empty() )
	{
		current = s.top();
		s.pop();
		T* temp = &current->data;
		current = current->rightChild;
		return temp;
	}
	else
		return NULL;
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

template <class T>
struct nodePointerWithTag
{
	binaryTreeNode<T>* p;
	bool rightChildVistited;
};

template <class T>
class postorderIterator
{
public:
	postorderIterator(binaryTree<T> tree)	{	t.root = current = tree.root;};
	T* next();
private:
	binaryTree<T> t;
	stack< nodePointerWithTag<T> > s;
	binaryTreeNode<T>* current;
};

template <class T>
T* postorderIterator<T>::next()
{
	nodePointerWithTag<T> npwt;
	while (1)
	{
		while ( current!=NULL )
		{
			npwt.p = current;
			npwt.rightChildVistited = false;
			s.push(npwt);
			current = current->leftChild;
		}
		
		if ( !s.empty() )
		{
			npwt = s.top();
			current = npwt.p;
			s.pop();
			if ( !npwt.rightChildVistited )
			{
				npwt.rightChildVistited = true;
				s.push(npwt);
				current = current->rightChild;
			}
			else
			{
				T* temp = &current->data;
				current = NULL;
				return temp;
			}
		}
		else
			return NULL;
	}
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

template <class T>
class preorderIterator
{
public:
	preorderIterator(binaryTree<T> tree)	{	t.root = current = tree.root;};
	T* next();
private:
	binaryTree<T> t;
	stack<binaryTreeNode<T>*> s;
	binaryTreeNode<T>* current;
};

template <class T>
T* preorderIterator<T>::next()
{
	while(1)
	{
		if ( current!=NULL )
		{
			s.push(current);
			T* temp = &current->data;
			current = current->leftChild;
			return temp;
		}
		else if ( !s.empty() )
		{
			current = s.top()->rightChild;
			s.pop();
		}
		else
			return NULL;
	}
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

template <class T>
class levelorderIterator
{
public:
	levelorderIterator(binaryTree<T> tree)	{	t.root = current = tree.root;};
	T* next();
private:
	binaryTree<T> t;
	queue<binaryTreeNode<T>*> q;
	binaryTreeNode<T>* current;
};

template <class T>
T* levelorderIterator<T>::next()
{
	T* temp = NULL;
	if ( current!=NULL )
	{
		temp = &current->data;
		if (current->leftChild!=NULL)
			q.push(current->leftChild);
		if (current->rightChild!=NULL)
			q.push(current->rightChild);
	}
	if (!q.empty())
	{
		current = q.front();
		q.pop();
	}
	else
		current = NULL;
	return temp;
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

#endif