// AVL.h: interface for the AVL class.
//
//////////////////////////////////////////////////////////////////////
// BinaryNode.h: interface for the BinaryNode class.
//
//////////////////////////////////////////////////////////////////////

#ifndef _BINARYTREE_
#define _BINARYTREE_

template<class T>
class AVL ;

enum TALLER { NONE , RIGHT , LEFT };

template<class T>
class BinaryNode  
{
public:
	BinaryNode(const T & d , TALLER  t = NONE , BinaryNode<T> *  L = 0 , BinaryNode<T> *  R = 0)
		:data(d),taller(t),left(L),right(R){}
private:
	friend class AVL<T>;
	T data ;
	TALLER taller ;
	BinaryNode * left ,*right ;
};

#endif 



#ifndef _AVL_
#define _AVL_
#include<stdexcept>
#include<new>
#include<queue>
#include<iostream>
template<class StdElement>
class AVL{ 
public:
	AVL(); 

	AVL(const AVL<StdElement>& t); 

	~AVL(); 

	const AVL<StdElement> & operator=(const AVL<StdElement>& t); 

	bool empty() const;

	bool isComplete();

	int size()const;

	int height()const ;

	void insert(const StdElement& data);

	void remove(const StdElement& data);

	void inorder(void(*)(const StdElement & d))const;

	void postorder(void(*)(const StdElement & d))const;

	void preorder(void(*)(const StdElement & d))const;
	
	void mirror();

	int print();

	void draw() ;
private:
	
	BinaryNode<StdElement> * root;

	void insert( BinaryNode<StdElement> * & ,const StdElement& data);

	void remove( BinaryNode<StdElement> * &,const StdElement& data);

	void copy(const BinaryNode<StdElement>  * , BinaryNode<StdElement>* & );

	void clear( BinaryNode<StdElement> * &);
	
	int size(const BinaryNode<StdElement>  * )const;

	int height(const BinaryNode<StdElement>  * )const ;

	void inorder( const BinaryNode<StdElement> *  ,void(*)(const StdElement & d))const;

	void postorder( const BinaryNode<StdElement> * ,void(*)(const StdElement & d))const;

	void preorder( const BinaryNode<StdElement> * ,void(*)(const StdElement &  d))const;

	void draw(BinaryNode<StdElement> * & ptr, int level) ;

	bool search(const BinaryNode<StdElement>*,const StdElement &)const ;

	void mirror(BinaryNode<StdElement> *&ptr) ;
	// function specialist for AVL Data Type
	void single_rotate_left_child(BinaryNode<StdElement> *&);
	void single_rotate_right_child(BinaryNode<StdElement> *&);
	void double_rotate_left_child(BinaryNode<StdElement> *&);
	void double_rotate_right_child(BinaryNode<StdElement> *&);



};

#endif 


template<class StdElement>
AVL<StdElement>::AVL()
{
	root = 0 ;
}

template<class StdElement>
AVL<StdElement>::AVL(const AVL<StdElement> & rhs)
{
	root = 0 ;
	copy(rhs.root,rhs);
}

template<class StdElement>
AVL<StdElement>::~AVL()
{
//	clear(root);
}

template<class StdElement>
void AVL<StdElement>::insert(const StdElement & element)
{
	insert(root,element);
}


template<class StdElement>
void AVL<StdElement>::mirror()
{
	mirror(root);
}


template<class StdElement>
void AVL<StdElement>::remove(const StdElement & element )
{
	if(search(root,element));
		remove(root,element);
}

template<class StdElement>
bool AVL<StdElement>::empty()const
{
	return root == 0 ? true : false ;
}
template<class StdElement>
int AVL<StdElement>::size()const
{

	return size(root);
}

template<class StdElement>
int AVL<StdElement>::height()const
{
	return height(root);
}

template<class StdElement>
void AVL<StdElement>::preorder(void (*out)(const StdElement & ))const
{
	preorder(root,out);
}

template<class StdElement>
void AVL<StdElement>::postorder(void(*out)(const StdElement & ))const
{
	postorder(root,out);
}

template<class StdElement>
void AVL<StdElement>::inorder(void(*out)(const StdElement & ))const
{
	inorder(root,out);
}

/*----------------------------------------------------------*/

template<class StdElement>
int AVL<StdElement>::size(const BinaryNode<StdElement>  * ptr)const
{
	if(ptr == 0 )
		return 0 ;
	return 1 + size(ptr->left) + size(ptr->right);
}

template<class StdElement>
int AVL<StdElement>::height(const BinaryNode<StdElement>  * ptr)const
{
	if(ptr == 0 )
		return -1 ;
	return 1 + (height(ptr->left) > height(ptr->right) ? height(ptr->left) : height(ptr->right) );
}

template<class StdElement>
void AVL<StdElement>::preorder(const BinaryNode<StdElement> * ptr,void (*out)(const StdElement & ))const
{
	if(ptr != 0 )
	{
		out(ptr->data);
		preorder(ptr->left,out);
		preorder(ptr->right,out);
	}
}

template<class StdElement>
bool AVL<StdElement>::search(const BinaryNode<StdElement>  * ptr,const StdElement & element)const
{
	if(ptr == 0 )
		return false ;
	else
	{
		if(element > ptr->data )
			return search(ptr->right,element);
		else if(element < ptr->data)
			return search(ptr->left,element);
		else
			return true ;
	}
}
template<class StdElement>
void AVL<StdElement>::postorder(const BinaryNode<StdElement> * ptr,void(*out)(const StdElement & ))const
{
	if(ptr != 0 )
	{
		postorder(ptr->left,out);
		postorder(ptr->right,out);
		out(ptr->data);
	}
}

template<class StdElement>
void AVL<StdElement>::inorder(const BinaryNode<StdElement> * ptr,void(*out)(const StdElement & ))const
{
	if(ptr != 0 )
	{
		inorder(ptr->left,out);
		out(ptr->data);
		inorder(ptr->right,out);
		
	}
}
template<class StdElement>
void AVL<StdElement>::insert( BinaryNode<StdElement> * & ptr ,const StdElement & element)
{
	if(ptr == 0 )
		ptr = new BinaryNode<StdElement>(element,NONE);
	else
	{
		if(ptr->data > element )
		{
			insert(ptr->left,element);
			if(ptr->taller == LEFT )
				if(ptr->left->data > element )
					single_rotate_left_child(ptr);
				else
					double_rotate_left_child(ptr);
		}
		else if(ptr->data < element )
		{
			insert(ptr->right,element);
			if(ptr->taller == RIGHT )
				if(ptr->right->data < element )
					single_rotate_right_child(ptr);
				else
					double_rotate_right_child(ptr);
		}
		else
			throw exception("No duplicate in Binary Search Tree");
	}
	int left_subtree = height(ptr->left) , right_subtree =  height(ptr->right) ;
	ptr->taller = ( left_subtree > right_subtree ? LEFT : (right_subtree > left_subtree ? RIGHT : NONE) ) ;
}

// function specialist for AVL Data Type
template<class StdElement>
void AVL<StdElement>::single_rotate_left_child(BinaryNode<StdElement> * & p1 )
{
	BinaryNode<StdElement> * p3 = p1->left ;
	p1->left = p3->right  ;
	p3->right = p1 ;
	p1 = p3 ;
}

template<class StdElement>
void AVL<StdElement>::single_rotate_right_child(BinaryNode<StdElement> * & p1 )
{
	BinaryNode<StdElement> * p3 = p1->right ;
	p1->right = p3->left  ;
	p3->left = p1 ;
	p1 = p3 ;
}

template<class StdElement>
void AVL<StdElement>::double_rotate_left_child(BinaryNode<StdElement> * & p1 )
{
	single_rotate_right_child(p1->left);
	single_rotate_left_child(p1);

}

template<class StdElement>
void AVL<StdElement>::double_rotate_right_child(BinaryNode<StdElement> * & p1 )
{
	single_rotate_left_child(p1->right);
	single_rotate_right_child(p1);
}

template<class StdElement>
void AVL<StdElement>::clear(BinaryNode<StdElement> * &ptr)
{
	if(ptr != 0 )
	{
		clear(ptr->left);
		clear(ptr->right);
		remove(ptr , ptr->data );
	}
}

template<class StdElement>
void AVL<StdElement>::remove(BinaryNode<StdElement> * & ptr , const StdElement & element)
{

}

template<class StdElement>
void AVL<StdElement>::draw() 
{
	draw(root,0);
}

template<class StdElement>
void AVL<StdElement>::draw(BinaryNode<StdElement> * &ptr, int level) 
{
   int k;

   if (ptr != 0)
   {
	draw(ptr->right, level + 1);
	for (k = 0; k < 3 * level; k++)
		std::cout <<" ";
	std::cout << ptr->data <<"\n";
	draw(ptr->left, level + 1);
    }
}

template<class StdElement>
void AVL<StdElement>::mirror(BinaryNode<StdElement> *&ptr)
{
	if(ptr != 0 )
	{
		mirror(ptr->left);
		mirror(ptr->right);
		BinaryNode<StdElement> *temp = ptr->left ;
		ptr->left = ptr->right ;
		ptr->right = temp ;
	}
}


template<class StdElement>
int AVL<StdElement>::print()
{
	std::queue<BinaryNode<StdElement> *> q ;

	BinaryNode<StdElement> *temp ;
	q.push(root);

	bool last = true ;
	int space = 3 * height();
	int level = 0 ;
	int Node  = 1 ;
	int counter =0 ;
	int current_node = 0 ;

	while(! q.empty() && last)
	{

		temp = q.front();
		q.pop();
		counter++;
		if(temp != 0 )
		{
			current_node++;
			for(int i=1 ; i<=space; i++)
				std::cout<<" ";
			std::cout<<temp->data;
			q.push(temp->left);
			q.push(temp->right);
		}
		else
		{
			q.push(0);
			q.push(0);
		}
		if(counter == Node )
		{
			std::cout<<"\n";
			if(current_node == 0 )
				last = false ;
			else
			{
				counter=0;
				Node*=2;
				current_node=0;
				level++;
				space-=3;
			}
		}
	}
	return level ;

}


template<class StdElement>
bool AVL<StdElement>::isComplete()
{
	std::queue<BinaryNode<StdElement> *> q ;

	BinaryNode<StdElement> *temp ;
	q.push(root);

	bool last = true ,NotNULL = false;
	int level = 0 ;
	int max  = 1 ;
	int min =0 ;
	int current = 0 ;

	while(! q.empty() && last)
	{
		temp = q.front();
		q.pop();
		min++;
		if(temp != 0 )
		{
			current++;
			if(NotNULL)
				if(temp->left || temp->right)
					return false ;
			if(temp->left == 0 || temp->right == 0)
				NotNULL = true ;
			q.push(temp->left);
			q.push(temp->right);
		}
		else
		{
			q.push(0);
			q.push(0);
		}
		if(min == max )
		{
			if(current == 0 )
				last = false ;
			else
			{
				min=0;
				max*=2;
				current=0;
				level++;
			}
		}
	}
	return true ;
}