avl.h

Although there has been a lot of AVL tree libraries available now, nearly all of them are meant to w

/////////////////////////////////////////////////////////////////////////////
// Name:        avl.h
// Version:		1.0.0
// Purpose:     AVL Library Core
// Author:      Wu Yuh Song
// Modified by:
// Created:     07/30/1999
// Copyright:   (c) Wu Yuh Song
// Licence:   	Wu Yuh Song's Library Licence, Version 1
/////////////////////////////////////////////////////////////////////////////


/////////////////////////////////////////////////////////////////////////////
//
//
//	Technical Notes :  Lines followed by the 'range cautious' comment
//					   are codes which inherently limit the maximum
//					   capacity of this tree. Replace it with a wider	
//					   data type could enlarge the capacity.
//
//
/////////////////////////////////////////////////////////////////////////////

#ifndef ___AVL_INCLUDED___
#define ___AVL_INCLUDED___

#include <time.h>
#include <string.h>
#include <math.h>

#include "avl_debug_macros.h"
#include "avl_errors.h"


template<class hndNode>
class AVL
{
public:

	struct TreeInfo
	{
		hndNode			nhndRoot;
#ifdef ___AVL_LINKLIST_SUPPORT___
		hndNode			nhndListHead;
		hndNode			nhndListTail;
#endif
		unsigned int	nNodeNumber;	//(range cautious: 0 to 4,294,967,295)
		int				nHeight;
	};


	struct SearchResult
	{
		hndNode		nhndSearch;
		int			nImbalanceIdx;
		hndNode		nhndImbalance;
		int			nEndIdx;

		bool		bFound;

	};

protected:
   
	hndNode* 	m_pRoot;

#ifdef ___AVL_LINKLIST_SUPPORT___	
	hndNode		m_nodeListHead;
	hndNode		m_nodeListTail;
#endif
	
	unsigned int m_nNodeNumber;  //(range cautious: 0 to 4,294,967,295)
	int		 	m_nHeight;
	double		m_dSearchPath_alloc_factor;
	int			m_sizeSearchPath;
	bool*		m_bSearchPath;	//true  => right
								//false => left

	time_t		m_timeLastSearchPathReAlloc;
	double		m_dReAllocInterval;

protected:
	inline bool ReAllocSearchPath();

	inline void LL(hndNode& nhndNode, hndNode* pnhndParent, bool bLocation, bool bInvert);
	inline void LR(hndNode& nhndNode, hndNode* pnhndParent, bool bLocation, bool bInvert);

	void Connect_Left(hndNode& nhndParent, hndNode& nhndChild)
	{
		nhndParent.SetLeftChild(nhndChild);
		nhndChild.SetParent(nhndParent);
	}
	
	void Connect_Right(hndNode& nhndParent, hndNode& nhndChild)
	{
	    nhndParent.SetRightChild(nhndChild);
	    nhndChild.SetParent(nhndParent);
	}	

#ifdef ___AVL_LINKLIST_SUPPORT___	
	void InsertToList(hndNode* pnhndLeft, hndNode& nhndInsert, hndNode* pnhndRight)
	{
	   	
	   	if ( pnhndLeft) {
	   	   	nhndInsert.SetLeftSibling(*pnhndLeft);
	   	   	pnhndLeft->SetRightSibling(nhndInsert);
	   	}
	 	else {
	 	    nhndInsert.SetLeftSiblingNull();
			m_nodeListHead.SetToNode(nhndInsert);						
	 	}

		if ( pnhndRight) {
		   	nhndInsert.SetRightSibling(*pnhndRight);
		   	pnhndRight->SetLeftSibling(nhndInsert);		   	
		}
		else {
		   	nhndInsert.SetRightSiblingNull();
		   	m_nodeListTail.SetToNode(nhndInsert);
		}
		
	}
	
	void RemoveFromList(hndNode& nhndRemove)
	{
		hndNode nodeLeft, nodeRight;

		
		verify( nodeLeft.SetToNode(nhndRemove) );
		verify( nodeRight.SetToNode(nhndRemove) );
		
		if (nodeLeft.StepToLeftSibling() ) {
			if( nodeRight.StepToRightSibling() ) {
				nodeLeft.SetRightSibling(nodeRight);
				nodeRight.SetLeftSibling(nodeLeft);
			}
			else {
				nodeLeft.SetRightSiblingNull();
				m_nodeListTail.SetToNode( nodeLeft);
			}		
		}
		else if ( nodeRight.StepToRightSibling() ) {
			nodeRight.SetLeftSiblingNull();
			m_nodeListHead.SetToNode( nodeRight);
		}		
	}	
#endif


	
public:
		
	AVL()
	{
	   	m_pRoot = NULL;
	   
	   	m_bSearchPath = NULL;
	   	m_nHeight = 0;
		m_nNodeNumber = 0;
	   	m_sizeSearchPath = 0;
	 	m_dSearchPath_alloc_factor = 1.5;
	
		m_dReAllocInterval = 10*60;	//600 second(s)
		time(&m_timeLastSearchPathReAlloc);
		ReAllocSearchPath();
	}		

	~AVL()
	{
	   	if ( m_pRoot)
	   		delete m_pRoot;
	   	if ( m_bSearchPath)
	   		delete[] m_bSearchPath;
	}

	
	bool GetRoot( hndNode& nhndNode);
#ifdef ___AVL_LINKLIST_SUPPORT___
	bool GetListHead(hndNode& nhndNode);
	bool GetListTail(hndNode& nhndnode);
#endif
	unsigned int GetNodeNumber();
	int	 GetHeight();

	bool Search( hndNode& nhndNode, int* pnImbalanceIdx = NULL, hndNode* pImbalance = NULL, int* pnEndIdx = NULL);
		//	'node' will point to the end point of the search
	 	//  when it is unable to find the exactly fit point.
	 	//
		//	*pnImbalanceIdx = -1 when there's no imbalanced 
		//   points in the search path.
		//	Else, it will record the index of m_bSearchPath[]
		//  in which the nearest imbalanced point is.
	inline bool Search ( SearchResult& sr);
	
 	bool Insert( hndNode& nhndInsert, SearchResult* pSR = NULL, hndNode* pnhndDup = NULL, bool bReplace = true);
 	bool Delete( hndNode& nhndDelete, SearchResult* pSR = NULL);
 		// nhndDelete will be redirect to the exact node for delete

	void Attach( TreeInfo& info);
	bool GetInfo( TreeInfo& info);

//// Error reports functions and their associated variables
protected:	
	int	 m_nLastError;	//record the last error

protected:
	inline void SetLastError(int nErr = AVL_Errors::NO_INFO);
public:
	int  GetLastError();
	void GetErrorMessage(int nErr, char* pBuf, int sizeBuf);

//// Diagnostic functions and their associated variables
public:
	
	unsigned int m_ndgCount;	//(range cautious: 0 to 4,294,967,295)
	int	m_ndgLLCount;
	int m_ndgRRCount;
	int	m_ndgLRCount;
	int	m_ndgRLCount;
	
public:
 	bool CheckIntegrity();
protected:
	
	int  Ping(hndNode nhndNode);



};

template<class hndNode>
void AVL<hndNode>::SetLastError(int nErr)
{
	m_nLastError = nErr;
}

template<class hndNode>
int AVL<hndNode>::GetLastError()
{
	return m_nLastError;
}

template<class hndNode>
void AVL<hndNode>::GetErrorMessage(int nErr, char* pBuf, int sizeBuf)
{
	if ( nErr < AVL_Errors::MAX_ERR_NO ) {
		strncpy(pBuf, AVL_Errors::szErrorMessages[nErr], sizeBuf);
		pBuf[sizeBuf-1] = NULL;
	}
	else
		pBuf[0] = NULL;
	
}

template<class hndNode>
void AVL<hndNode>::Attach( TreeInfo& info)
{
	if ( !m_pRoot)
		m_pRoot = new hndNode;

	m_pRoot->SetToNode(info.nhndRoot);
#ifdef ___AVL_LINKLIST_SUPPORT___
	m_nodeListHead.SetToNode(info.nhndListHead);
	m_nodeListTail.SetToNode(info.nhndListTail);
#endif
	m_nNodeNumber = info.nNodeNumber;
	m_nHeight = info.nHeight;

	ReAllocSearchPath();	
}

template<class hndNode>
bool AVL<hndNode>::GetInfo( TreeInfo& info)
{
	SetLastError();

	if ( m_pRoot) {
		info.nhndRoot.SetToNode(*m_pRoot);
#ifdef ___AVL_LINKLIST_SUPPORT___
		verify( GetListHead(info.nhndListHead) );
		verify( GetListTail(info.nhndListTail) );
#endif
		info.nNodeNumber = GetNodeNumber();
		info.nHeight = GetHeight();
		return true;
	}
	else {
		SetLastError( AVL_Errors::E_EMPTYTREE);
		return false;	//tree is empty
	}
}


template<class hndNode>
bool AVL<hndNode>::CheckIntegrity()
{
	hndNode nodeTmp, nodeTmp1;
	unsigned int k; //(range cautious: 0 to 4,294,967,295);
	
	SetLastError();
	
	///Check if the tree is empty
	if ( !GetRoot(nodeTmp) ) {
		SetLastError(AVL_Errors::E_EMPTYTREE);
		return true;
	}

	

#ifdef ___AVL_LINKLIST_SUPPORT___	

	///check validity of m_nodeListHead and m_nodeListTail

	GetRoot(nodeTmp);
	while(nodeTmp.StepLeft());
	if ( nodeTmp.Compare(m_nodeListHead) ) {
		SetLastError(AVL_Errors::E_INVALIDLISTHEAD);
		assert(false);
		return false;
	}
	
	GetRoot(nodeTmp);
	while(nodeTmp.StepRight());
	if ( nodeTmp.Compare(m_nodeListTail)) {
		SetLastError(AVL_Errors::E_INVALIDLISTTAIL);
		assert(false);
		return false;
	}

	//Right iteration over the tree	
	GetListHead(nodeTmp);
	nodeTmp1.SetToNode(nodeTmp);
	k = 0;
	do {
		//Check uniqueness of nodes
		if(k) {
			if( !nodeTmp1.Compare(nodeTmp) ) {
				SetLastError(AVL_Errors::E_KEYCOLLISION);
				assert(false);
				return false;
			}
			nodeTmp1.SetToNode(nodeTmp);
		}
		k++;
	}while(nodeTmp.StepToRightSibling() );
	
	if ( k != m_nNodeNumber) {
		SetLastError (AVL_Errors::E_NODENUMBERUNMATCHED);
		assert(false);
		return false;
	}

	//Left iteration over the tree	

	GetListTail(nodeTmp);
	nodeTmp1.SetToNode(nodeTmp);	
	k = 0;
	do {
		//Check uniqueness of nodes
		if(k) {
			if( !nodeTmp1.Compare(nodeTmp) ) {
				SetLastError(AVL_Errors::E_KEYCOLLISION);
				assert(false);
				return false;
			}
			nodeTmp1.SetToNode(nodeTmp);
		}

		k++;
	}while(nodeTmp.StepToLeftSibling() );
	
	if ( k != m_nNodeNumber) {
		SetLastError (AVL_Errors::E_NODENUMBERUNMATCHED);
		assert(false);
		return false;
	}
	
#endif

	//traverse the tree
	m_ndgCount = 0;
	if ( !(Ping(*m_pRoot) == m_nHeight) ) {
		SetLastError( AVL_Errors::E_HEIGHTUNMATCHED);
		assert(false);
		return false;
	}

	if ( k != m_nNodeNumber) {
		SetLastError (AVL_Errors::E_NODENUMBERUNMATCHED);
		assert(false);
		return false;
	}
	
/*	printf ( "\t\t Tree traversing ok... %lu nodes exist in the tree\n", m_ndgCount);


	printf ( "\t\t Height : %d\n", m_nHeight);
	float perfectness = 0;
	if ( m_nHeight) {
		float tmp;
		tmp = 1.4404*(log(m_ndgCount+2)/log(2))-0.328;
		perfectness = (float)((m_nHeight-tmp)*100/(log(m_ndgCount+1)/log(2)-tmp));
		
	}
	printf ( "\t\t Perfectness : %.2f %%\n", perfectness);
*/
	return true;
}

template<class hndNode>
int AVL<hndNode>::Ping(hndNode nhndNode)
{
	hndNode nodeLeft, nodeRight;
	int hl, hr;
	
	nodeLeft.SetToNode(nhndNode);
	nodeRight.SetToNode(nhndNode);

	if ( nodeLeft.StepLeft() )
		hl = Ping(nodeLeft)+1;
	else
		hl = 1;
		
	if ( nodeRight.StepRight())
		hr = Ping(nodeRight)+1;
	else
		hr = 1;
	
	if ( hr-hl != nhndNode.GetBalanceFactor() )
		assert(false);	
	
	m_ndgCount++;		
	
	return hr > hl ? hr : hl;
}




template<class hndNode>
bool AVL<hndNode>::GetRoot( hndNode& nhndNode)
{
	if ( m_pRoot) {
		return nhndNode.SetToNode(*m_pRoot);
	}
	else
		return false;
}

#ifdef ___AVL_LINKLIST_SUPPORT___

template<class hndNode>
bool AVL<hndNode>::GetListHead(hndNode& nhndNode)
{
	if ( m_pRoot)
		return nhndNode.SetToNode(m_nodeListHead);
	else
		return false;
}


template<class hndNode>
bool AVL<hndNode>::GetListTail(hndNode& nhndNode)
{
	if ( m_pRoot)
		return nhndNode.SetToNode(m_nodeListTail);
	else
		return false;
}

#endif

template<class hndNode>
unsigned int AVL<hndNode>::GetNodeNumber()
{
	return m_nNodeNumber; //(range cautious: 0 to 4,294,967,295)
}

template<class hndNode>
int	AVL<hndNode>::GetHeight()
{
	return m_nHeight;
}


template<class hndNode>
bool AVL<hndNode>::ReAllocSearchPath()
{

	if ( m_nHeight >= m_sizeSearchPath) {
		if ( m_bSearchPath)
		  	delete[] m_bSearchPath;
#ifdef _DEBUG
	int tmp = m_sizeSearchPath;
#endif
		m_sizeSearchPath = (int)((m_nHeight+1)*m_dSearchPath_alloc_factor);
#ifdef _DEBUG		
	TRACE( "\t\t\tInflate m_bSearchPath from %d to %d (m_nHeight : %d)\n",tmp, m_sizeSearchPath, m_nHeight);
#endif
		time(&m_timeLastSearchPathReAlloc);

#ifdef _MSC_VER
	#pragma warning( disable : 4800 )
#endif		

		return ( m_bSearchPath = new bool[m_sizeSearchPath] );

#ifdef _MSC_VER
	#pragma warning( default : 4800 )
#endif

	}
	else {
		time_t timeNow;
		
		time(&timeNow);
		
		if ( difftime(timeNow, m_timeLastSearchPathReAlloc) >= m_dReAllocInterval  &&
			 (int)((m_nHeight+1)*m_dSearchPath_alloc_factor*1.3) < m_sizeSearchPath ) {
	
#ifdef _DEBUG
	int tmp = m_sizeSearchPath;
#endif			
			m_sizeSearchPath = (int)((m_nHeight+1)*m_dSearchPath_alloc_factor);
#ifdef _DEBUG																						
	TRACE( "\t\t\tReduce  m_bSearchPath from %d to %d (m_nHeight : %d , Time elapsed : %.3Lf sec)\n"
			,tmp
			, m_sizeSearchPath
			, m_nHeight
			,difftime(timeNow, m_timeLastSearchPathReAlloc));
#endif

			time(&m_timeLastSearchPathReAlloc);
		
			if ( m_bSearchPath)
			  	delete[] m_bSearchPath;

#ifdef _MSC_VER
	#pragma warning( disable : 4800 )
#endif		

			return ( m_bSearchPath = new bool[m_sizeSearchPath] );

#ifdef _MSC_VER
	#pragma warning( default : 4800 )
#endif		

		}
	}

	return false;	
}


template<class hndNode>
bool AVL<hndNode>::Search ( SearchResult& sr)
{
	sr.bFound = Search(sr.nhndSearch, &sr.nImbalanceIdx, &sr.nhndImbalance, &sr.nEndIdx);

	return sr.bFound;
}

template<class hndNode>
bool AVL<hndNode>::Search( hndNode& nhndNode, int* pnImbalanceIdx, hndNode* pnhndImbalance, int* pnEndIdx)
{
	SetLastError();

   	if (!m_pRoot) {
		SetLastError(AVL_Errors::E_EMPTYTREE);
   		return false;
	}
	

	if (pnImbalanceIdx)		
		*pnImbalanceIdx = -1;
	if ( pnEndIdx)
		*pnEndIdx = -1;
		
   	if ( m_pRoot) {
   	   	hndNode nodeTmp;
   	   	int 	k, nLevel;
   	   	bool 	b;
		   
  	   	b = nodeTmp.SetToNode(*m_pRoot);
		nLevel = 0;
		
	
   	   	while(b && (k = nhndNode.Compare(nodeTmp)) ) {

   	   		
			if ( (pnImbalanceIdx || pnhndImbalance) && 
				 nodeTmp.GetBalanceFactor()) 
			{
				if ( pnhndImbalance)
					pnhndImbalance->SetToNode(nodeTmp);
				if ( pnImbalanceIdx)
					*pnImbalanceIdx = nLevel;
			}
			

   	   	   
   	   		if ( k == 1) {
   	   		   	m_bSearchPath[nLevel] = true;
   	   			b = nodeTmp.StepRight();
   	   		}
   	   		else {
   	   		   	m_bSearchPath[nLevel] = false;
   	   			b = nodeTmp.StepLeft();
			}

			nLevel++;
   	   	}

		
		if ( pnEndIdx) {
		   	if ( b)
		   		*pnEndIdx = nLevel;
		   	else
				*pnEndIdx = nLevel-1;
		}
   	 
   	 	if ( b) 
   	 	   	return nhndNode.SetToNode(nodeTmp);
		else
			nhndNode.SetToNode(nodeTmp);	//set to the end of the search
   	}
	
	SetLastError(AVL_Errors::E_NOTFOUND);

	return false;   
}


template<class hndNode>
void AVL<hndNode>::LL(hndNode& nhndNode, hndNode* pnhndParent, bool bLocation, bool bInvert)