///////////////////////////////////////////////////////////////////
//
//	avl.h
//
//	Started by Jeff Ondich on 4/13/98.
//	Last modified 4/13/98.
//
//	AVL tree template.  Assumes operator< and operator==
//	are defined for T operands.
//
//	The code for AVLTree::AddItem is loosely based on
//	the Insert function on p. 562 of "Fundamentals of
//	Data Structures in C++" by Horowitz, Sahni, and Mehta,
//	Computer Science Press, 1995.
//
///////////////////////////////////////////////////////////////////


template <class T>
struct AVLNode
{
	T					mData;
	int					mBalanceFactor;
	AVLNode<T>			*mLeft, *mRight, *mParent;

						AVLNode( const T& theData );
	virtual				~AVLNode( void );
	int					GetHeight( void ) const;
};

template <class T>
class AVLIterator
{
private:
	AVLNode<T>*		mCurrentNode;

public:
					AVLIterator() : mCurrentNode(0) {}
					AVLIterator( AVLNode<T>* p ) : mCurrentNode(p) {}

	T*				operator->() const
						{ return( &(mCurrentNode->mData) ); }

	T&				operator*() const
						{ return( mCurrentNode->mData ); }

	AVLIterator&	operator++();

	AVLIterator		operator++(int)
						{
							AVLIterator<T>	tmp = *this;
							++(*this);
							return( tmp );
						}

	bool			operator==( const AVLIterator& x ) const
						{ return ( mCurrentNode == x.mCurrentNode ); }

	bool			operator!=( const AVLIterator& x ) const
						{ return ( mCurrentNode != x.mCurrentNode ); }
};


template <class T>
class AVLTree
{
private:
	AVLNode<T>				*mRoot;
	

public:
	typedef	AVLIterator<T>	iterator;

							AVLTree( void );
	virtual					~AVLTree( void );

	T*						AddItem( const T& theData );
	const AVLNode<T>*		GetRoot() const { return mRoot; }
	iterator				begin();
	iterator				end() { return( iterator(0) ); }
};


///////////////////////////////////////////////////////////////////
//	AVLNode
///////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////
//	AVLNode::AVLNode
///////////////////////////////////////////////////////////////////

template <class T>
AVLNode<T>::AVLNode( const T& theData )
{
	mData = theData;
	mBalanceFactor = 0;
	mLeft = 0;
	mRight = 0;
	mParent = 0;
}


///////////////////////////////////////////////////////////////////
//
//	AVLNode::~AVLNode
//
//	Recursively deletes subtrees--first left, then right.
//
///////////////////////////////////////////////////////////////////

template <class T>
AVLNode<T>::~AVLNode( void )
{
	if( mLeft != 0 )
		delete mLeft;

	if( mRight != 0 )
		delete mRight;
}


///////////////////////////////////////////////////////////////////
//	AVLIterator
///////////////////////////////////////////////////////////////////

template<class T>
AVLIterator<T>&	AVLIterator<T>::operator++()
{
	if( mCurrentNode == 0 )
		return( *this );

	if( mCurrentNode->mRight != 0 )
	{
		mCurrentNode = mCurrentNode->mRight;
		while( mCurrentNode->mLeft != 0 )
			mCurrentNode = mCurrentNode->mLeft;
	}
	else
	{
		AVLNode<T>	*p = mCurrentNode->mParent;
		AVLNode<T>	*q = mCurrentNode;
		while( p != 0  &&  p->mRight == q )
		{
			q = p;
			p = p->mParent;
		}
		mCurrentNode = p;
	}

	return( *this );
}


///////////////////////////////////////////////////////////////////
//	AVLTree
///////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////
//
//	AVLTree::AVLTree
//
///////////////////////////////////////////////////////////////////

template <class T>
AVLTree<T>::AVLTree( void )
{
	mRoot = 0;
}


///////////////////////////////////////////////////////////////////
//
//	AVLTree::~AVLTree
//
//	Exploits the recursive deletion of AVLNodes to delete
//	the whole tree by deleting the root.
//
///////////////////////////////////////////////////////////////////

template <class T>
AVLTree<T>::~AVLTree( void )
{
	if( mRoot != 0 )
		delete mRoot;
}


///////////////////////////////////////////////////////////////////
//
//	AVLTree::AddItem
//
//	Adds a node containing the given data to the AVL tree.
//	If the data is already in the tree (determined by using
//	operator==( const T&, const T& )), AddItem returns
//	a pointer to the matched data.  Otherwise, AddItem
//	returns a pointer to the data in the new node if the addition
//	succeeds, and 0 if not.  (Failure can only occur if
//	new fails to return a non-null pointer.)
//
///////////////////////////////////////////////////////////////////

template <class T>
T*	AVLTree<T>::AddItem( const T& theData )
{
	/////////////////////////////////////////////////////
	// Adding to an empty tree.  Note that if the
	// memory allocation fails, mRoot will be 0,
	// and so the return value will be correct.
	/////////////////////////////////////////////////////

	if( mRoot == 0 )
	{
		mRoot = new AVLNode<T>( theData );
		if( mRoot != 0 )
			return( &(mRoot->mData) );
		else
			return( 0 );
	}


	/////////////////////////////////////////////////////
	// Find the insertion point for the new node.
	// Lots of pointers following each other down the
	// tree to prepare for rotation, if necessary.
	/////////////////////////////////////////////////////
	
	AVLNode<T>		*current = mRoot; // p
	AVLNode<T>		*unevenAncestor = mRoot; //a
	AVLNode<T>		*uaParent = 0; //f
	AVLNode<T>		*parent = 0; //q

	while( current != 0 )
	{
		if( current->mBalanceFactor != 0 )
		{
			unevenAncestor = current;
			uaParent = parent;
		}
		
		if( theData < current->mData )
		{
			parent = current;
			current = current->mLeft;
		}
		else if( theData == current->mData )
		{
			return( &(current->mData) );
		}
		else
		{
			parent = current;
			current = current->mRight;
		}
	}


	/////////////////////////////////////////////////////
	// Add the new node to the tree and rebalance,
	// if necessary.
	/////////////////////////////////////////////////////
	
	AVLNode<T> *newNode = new AVLNode<T>( theData );
	if( newNode == 0 )
	{
//		cerr << "Memory allocation error." << endl;
		exit(1);
	}
	
	newNode->mParent = parent;
	if( parent->mData < theData )
		parent->mRight = newNode;
	else
		parent->mLeft = newNode;


	/////////////////////////////////////////////////////
	// Adjust balance factors.
	/////////////////////////////////////////////////////

	AVLNode<T>		*b = 0; //b
	AVLNode<T>		*c = 0; //c
	int				balanceChange; // d

	if( unevenAncestor->mData < theData )
	{
		current = b = unevenAncestor->mRight;
		balanceChange = -1;
	}
	else
	{
		current = b = unevenAncestor->mLeft;
		balanceChange = 1;
	}

	while( current != newNode )
	{
		if( current->mData < theData )
		{
			current->mBalanceFactor = -1;
			current = current->mRight;
		}
		else
		{
			current->mBalanceFactor = 1;
			current = current->mLeft;
		}
	}
	
	
	/////////////////////////////////////////////////////
	// If the tree's unbalanced, fix it.
	/////////////////////////////////////////////////////
	
	bool unbalanced = true;

	if( unevenAncestor->mBalanceFactor == 0 
		||  unevenAncestor->mBalanceFactor + balanceChange == 0 )
	{
		unevenAncestor->mBalanceFactor += balanceChange;
		unbalanced = false;
	}
	
	if( unbalanced )
	{
		if( balanceChange == 1 )
		{
			if( b->mBalanceFactor == 1 ) // LL Rotation
			{
				unevenAncestor->mBalanceFactor = 0;
				b->mBalanceFactor = 0;

				unevenAncestor->mLeft = b->mRight;
				if( unevenAncestor->mLeft != 0 )
					unevenAncestor->mLeft->mParent = unevenAncestor;

				b->mRight = unevenAncestor;
				b->mParent = unevenAncestor->mParent;

				unevenAncestor->mParent = b;
			}
			else // LR Rotation
			{
				c = b->mRight;
				c->mParent = unevenAncestor->mParent;

				b->mRight = c->mLeft;
				if( b->mRight != 0 )
					b->mRight->mParent = b;

				unevenAncestor->mLeft = c->mRight;
				if( unevenAncestor->mLeft != 0 )
					unevenAncestor->mLeft->mParent = unevenAncestor;

				c->mLeft = b;
				b->mParent = c;

				c->mRight = unevenAncestor;
				unevenAncestor->mParent = c;

				switch( c->mBalanceFactor )
				{
				case 1:
					unevenAncestor->mBalanceFactor = -1;
					b->mBalanceFactor = 0;
					break;
				
				case -1:
					unevenAncestor->mBalanceFactor = 0;
					b->mBalanceFactor = 1;
					break;
				
				case 0:
					unevenAncestor->mBalanceFactor = 0;
					b->mBalanceFactor = 0;
					break;
				}
				c->mBalanceFactor = 0;
				b = c;
			}
		} // Left imbalance
		
		else
		{
			if( b->mBalanceFactor == -1 ) // RR Rotation
			{
				unevenAncestor->mBalanceFactor = 0;
				b->mBalanceFactor = 0;

				unevenAncestor->mRight = b->mLeft;
				if( unevenAncestor->mRight != 0 )
					unevenAncestor->mRight->mParent = unevenAncestor;

				b->mLeft = unevenAncestor;
				b->mParent = unevenAncestor->mParent;

				unevenAncestor->mParent = b;
			}
			else // RL Rotation
			{
				c = b->mLeft;
				c->mParent = unevenAncestor->mParent;

				b->mLeft = c->mRight;
				if( b->mLeft != 0 )
					b->mLeft->mParent = b;

				unevenAncestor->mRight = c->mLeft;
				if( unevenAncestor->mRight != 0 )
					unevenAncestor->mRight->mParent = unevenAncestor;

				c->mRight = b;
				b->mParent = c;

				c->mLeft = unevenAncestor;
				unevenAncestor->mParent = c;

				switch( c->mBalanceFactor )
				{
				case 1:
					unevenAncestor->mBalanceFactor = 0;
					b->mBalanceFactor = -1;
					break;
				
				case -1:
					unevenAncestor->mBalanceFactor = 1;
					b->mBalanceFactor = 0;
					break;
				
				case 0:
					unevenAncestor->mBalanceFactor = 0;
					b->mBalanceFactor = 0;
					break;
				}
				c->mBalanceFactor = 0;
				b = c;
			}
		} // Right imbalance
		
		if( uaParent == 0 )
			mRoot = b;
		
		else if( unevenAncestor == uaParent->mLeft )
			uaParent->mLeft = b;
		
		else if( unevenAncestor == uaParent->mRight )
			uaParent->mRight = b;
	}

	return( &(newNode->mData) );
}


///////////////////////////////////////////////////////////////////
//
//	AVLTree::begin
//
///////////////////////////////////////////////////////////////////

template <class T>
AVLTree<T>::iterator	AVLTree<T>::begin()
{
	AVLNode<T>	*p = mRoot;
	if( p != 0 )
	{
		while( p->mLeft != 0 )
			p = p->mLeft;
	}
	return( AVLTree<T>::iterator(p) );
}



///////////////////////////////////////////////////////////////////
//
//	AVLNode::GetHeight
//
///////////////////////////////////////////////////////////////////

template <class T>
int AVLNode<T>::GetHeight( void ) const
{
	int	left = 0, right = 0;
	
	if( mLeft != 0 )
		left = mLeft->GetHeight();
	
	if( mRight != 0 )
		right = mRight->GetHeight();
	
	if( left > right )
		return( 1 + left );
	else
		return( 1 + right );
}