avl_node.h

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

/////////////////////////////////////////////////////////////////////////////
// Name:        avl_node.h
// Version:		1.0.0
// Purpose:     AVL Node Handle Class Definition Example
// Author:      Wu Yuh Song
// Modified by:
// Created:     07/30/1999
// Copyright:   (c) Wu Yuh Song
// Licence:   	Wu Yuh Song's Library Licence, Version 1
/////////////////////////////////////////////////////////////////////////////




#ifndef ___AVL_NODE_INCLUDED___
#define ___AVL_NODE_INCLUDED___

#include "avl_debug_macros.h"




/*
/////////////////////////////////////////////////////////////////////////////
//	
//	AVL NODE HANDLE Example
//
//		Member funcions listed here must be fully defined
//		and obey their respective behavior specification
//		as stated in the documents that ship with these 
//		codes.
//
//		Functions that are enclosed by the #ifdef ___AVL_LINKLIST_SUPPORT___
//		directives are optional. You should define them according to their
//		behavioral specification in the doc file if you want the ablitiy
//		to iterate the tree as a doubly-linked list. Otherwise, you can omit
//		them, if you don't need that capability.
//
//
/////////////////////////////////////////////////////////////////////////////

class avl_node_hnd
{
public:


	bool SetToNode(avl_node_hnd& );			

	void SetParent(avl_node_hnd& );
	void SetLeftChild(avl_node_hnd&);
	void SetRightChild(avl_node_hnd&);

#ifdef ___AVL_LINKLIST_SUPPORT___
	void SetLeftSibling(avl_node_hnd&);
	void SetRightSibling(avl_node_hnd&);
#endif
	
	void SetParentNull();
	void SetLeftChildNull();
	void SetRightChildNull();
	
#ifdef ___AVL_LINKLIST_SUPPORT___
	void SetLeftSiblingNull();
	void SetRightSiblingNull();
#endif

	int Compare(avl_node_hnd& hndNode)
	
	void SetBalanceFactor(int);
	int  GetBalanceFactor();
	

	bool StepUp();				
	bool StepRight();		
	bool StepLeft();			

#ifdef ___AVL_LINKLIST_SUPPORT___
	bool StepToLeftSibling();
	bool StepToRightSibling();
#endif
};

*/


/////////////////////////////////////////////////////////////////////////////
//
//	AVL Memory Node Handle
//
//	This is a fully defined node handle class which works with
//	nearly every conditions of using the memory for data storage.
//		
//	typeKey is the 'KEY' and typeValue is the 'VALUE' which the
//	key holds.
//
//	For example, if you want to create a tree which records 
//	your classmates' exam grades, it is possibly that we use
//  a 'char*' as the key type for recording the name of each your
//  classmate, and us 'int' as the value type for recording each
//  associated grade.
//
//	The code is like :       avl_node_hnd_mem<char*,int> hndNode;
//
//	Please read the doc file for detailed information.
//
//
/////////////////////////////////////////////////////////////////////////////


template<class typeKey, class typeValue>
class avl_node_hnd_mem
{

   
protected:
	//
	// DataCore structure holds the essence of a node.
	// Precisely, each avl_node_hnd_mem is just a 'reference'.
	//
	// An avl_node_hnd_mem must have a DataCore structure attached (
	// that means m_pCurrent points to a valid DataCore structure )
	// in order to work with the avl library.
	//
	struct DataCore
	{
		DataCore *pParent, *pLeftChild, *pRightChild;
		int 	  bf;
		
		typeKey   key;
		typeValue value;


#ifdef ___AVL_LINKLIST_SUPPORT___		
		DataCore *pLeftSibling, *pRightSibling;		
#endif	

	}*m_pCurrent;
	
	
public:
	avl_node_hnd_mem() : m_pCurrent(NULL)
	{}

	bool NewNode()
	{   
		if ( m_pCurrent = new DataCore )
			return true;
	   	else
	   		return false;
	}

	bool DeleteNode()
	{
		if ( m_pCurrent ) {
	   		delete m_pCurrent;
	   		m_pCurrent = NULL;
	   		return true;   
	 	}
		else
			return false;
	 
	}


	void GetValue(typeValue& value)
	{
	   assert(m_pCurrent);
	   value = m_pCurrent->value;
	}
	
	void SetValue(typeValue& value)
	{
	   assert(m_pCurrent);
	   m_pCurrent->value = value;
	   
	}
	
	void GetKey(typeKey& key)
	{
	   assert(m_pCurrent);
	   key = m_pCurrent->key;
	}
	
	void SetKey(const typeKey& key)
	{
	   assert(m_pCurrent);
	   m_pCurrent->key = key; 
	}
	
	
public:

	void SetBalanceFactor(int nbf)
	{
		assert(m_pCurrent);
		
		m_pCurrent->bf = nbf;   
	}
	
	
	int  GetBalanceFactor()
	{
	   	assert(m_pCurrent);
	   	
		return m_pCurrent->bf;   
	}

	bool SetToNode(avl_node_hnd_mem<typeKey,typeValue>& node)
	{
	   	m_pCurrent = node.m_pCurrent;	   
	   	
		return true;		
	}

	void SetParent(avl_node_hnd_mem<typeKey,typeValue>& node)
	{
	   assert(m_pCurrent);
	   m_pCurrent->pParent = node.m_pCurrent;
	}
	
	void SetLeftChild(avl_node_hnd_mem<typeKey,typeValue>& node)
	{
	   assert(m_pCurrent);
	   m_pCurrent->pLeftChild = node.m_pCurrent;  
	}
	
	
	void SetRightChild(avl_node_hnd_mem<typeKey,typeValue>& node)
	{
		assert(m_pCurrent);
		m_pCurrent->pRightChild = node.m_pCurrent;
	}
	
	void SetParentNull()
	{
	   assert(m_pCurrent);
	   m_pCurrent->pParent = NULL;
	}
	
	void SetLeftChildNull()
	{
	   assert(m_pCurrent);
	   m_pCurrent->pLeftChild = NULL;   
	}
	
	void SetRightChildNull()
	{
	   assert(m_pCurrent);
	   m_pCurrent->pRightChild = NULL;
	}
	
	int Compare(avl_node_hnd_mem<typeKey,typeValue>& node)
	{
		if ( m_pCurrent->key > node.m_pCurrent->key)
	 	  	return 1;
		else if ( m_pCurrent->key < node.m_pCurrent->key)
			return -1;
		else
			return 0;
		  	
	}
	
	bool StepUp()
	{
	   	assert(m_pCurrent);
	   	
		if ( m_pCurrent->pParent) 
			m_pCurrent = m_pCurrent->pParent;
		else
			return false;

		return true;
	}   
	
	bool StepRight()
	{
	    assert(m_pCurrent);
	    
		if ( m_pCurrent->pRightChild)
			m_pCurrent = m_pCurrent->pRightChild;
		else
			return false;
			
		return true;
	}
	
	
	bool StepLeft()
	{
	    assert(m_pCurrent);
	    
		if ( m_pCurrent->pLeftChild)
			m_pCurrent = m_pCurrent->pLeftChild;
		else
			return false;
		
		return true;
	}


#ifdef ___AVL_LINKLIST_SUPPORT___




	void SetLeftSibling(avl_node_hnd_mem<typeKey, typeValue>& node)
	{
		assert(m_pCurrent);	   
	   	m_pCurrent->pLeftSibling = node.m_pCurrent;
	}
	
	
	void SetRightSibling(avl_node_hnd_mem<typeKey,typeValue>& node)
	{
		assert(m_pCurrent);
		m_pCurrent->pRightSibling = node.m_pCurrent;   
	}

	void SetLeftSiblingNull()
	{
		assert(m_pCurrent);
		m_pCurrent->pLeftSibling = NULL;	   
	}

	void SetRightSiblingNull()
	{
		assert(m_pCurrent);
	 	m_pCurrent->pRightSibling = NULL;  
	}

	bool StepToLeftSibling()
	{
	   	assert(m_pCurrent);
	   	
		if ( m_pCurrent->pLeftSibling)
			m_pCurrent = m_pCurrent->pLeftSibling;
		else
			return false;
		
		return true;
			
	}
	
	
	bool StepToRightSibling()
	{
	   	assert(m_pCurrent);
	   	
		if ( m_pCurrent->pRightSibling)
			m_pCurrent = m_pCurrent->pRightSibling;
		else
			return false;
		
		return true;
	}
	
#endif
};




#endif