
///////////////////////////////////////////////////////////////////////////////
//
// File   : Asura_TemplateTree.h
// Author : Andy Tate
// Date   : 25-Jun-2008
//
// Copyright (C) 2008 Rebellion, All Rights Reserved.
//
///////////////////////////////////////////////////////////////////////////////

#ifdef ASURA_USE_PRAGMA_ONCE
	#pragma once
#endif   // ifdef ASURA_USE_PRAGMA_ONCE

#ifndef __ASURA_TEMPLATETREE_H__
#define __ASURA_TEMPLATETREE_H__

////////////////////////////////////////////////////////////////////////////////
// Include files...
////////////////////////////////////////////////////////////////////////////////

#include "Debugging/Asura_Assert.h"


////////////////////////////////////////////////////////////////////////////////
// Forward class declarations...
////////////////////////////////////////////////////////////////////////////////

class Asura_Chunk_Stream;

template <class Key, class T> class Asura_TemplateTree;
template <class Key, class T> class Asura_TemplateTree_Iterator;
template <class Key, class T> class Asura_TemplateTree_ConstIterator;


////////////////////////////////////////////////////////////////////////////////
// Class declaration...
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
// Class        : Asura_TemplateTree_Node
// Author       : Andy Tate
// Date         : 25-Jun-2008
//
// Description  : Template class (taken from "Asura_TemplateTree_Node") which
//				  allows data to be stored in a tree and keyed from any data-type
//				  (not just "Asura_Hash_ID" as we've had previously).
////////////////////////////////////////////////////////////////////////////////

template <class Key, class T> class Asura_TemplateTree_Node
{
	// Friend classes...
	friend class Asura_TemplateTree<Key, T>;
	friend class Asura_TemplateTree_Iterator<Key, T>;
	friend class Asura_TemplateTree_ConstIterator<Key, T>;

public:
	// Public functions...
	Asura_TemplateTree_Node(const Key& xKey, const T& xData)
	: m_xKey(xKey)
	, m_xData(xData)
	, m_pxLower(NULL)
	, m_pxHigher(NULL)
	{
	}

	Asura_TemplateTree_Node(const Key& xKey, Asura_Chunk_Stream& xStream)
	: m_xKey(xKey)
	, m_xData(xKey, xStream)
	, m_pxLower(NULL)
	, m_pxHigher(NULL)
	{
	}

	Asura_TemplateTree_Node(const Key& xKey)
	: m_xKey(xKey)
	, m_pxLower(NULL)
	, m_pxHigher(NULL)
	{
	}

	~Asura_TemplateTree_Node()
	{
		delete(m_pxLower);
		delete(m_pxHigher);
	}


protected:
	// Protected variables...

	// Protected functions...


private:
	// Private variables...
	const Key							m_xKey;
	T									m_xData;
	Asura_TemplateTree_Node<Key, T>*	m_pxLower;
	Asura_TemplateTree_Node<Key, T>*	m_pxHigher;

	// Private functions...
	Asura_TemplateTree_Node(void);
	Asura_TemplateTree_Node(const Asura_TemplateTree_Node& xOther);

	Asura_TemplateTree_Node&	operator=(const Asura_TemplateTree_Node& xOther);

};   // End of class 'Asura_TemplateTree_Node'.



////////////////////////////////////////////////////////////////////////////////
// Class        : Asura_TemplateTree
// Author       : Andy Tate
// Date         : 25-Jun-2008
//
// Description  : Template class (taken from "Asura_TemplateTree") which
//				  allows a tree to be made keyed from any data type (not just
//				  "Asura_Hash_ID" as we've had previously).
////////////////////////////////////////////////////////////////////////////////

template <class Key, class T> class Asura_TemplateTree
{
	// Friend classes...
	friend class Asura_TemplateTree_Iterator<Key, T>;
	friend class Asura_TemplateTree_ConstIterator<Key, T>;

public:
	// Public typedefs...
	typedef int CompareFunction(const Key& xKey1, const Key& xKey2);

	// Public functions...
	Asura_TemplateTree(CompareFunction* pfnCompare)
	: m_pxFirstRoot(NULL)
	, m_iNumberOfNodes(0)
	, m_pfnCompare(pfnCompare)
	, m_uIterationCount(0)
	, m_pxDeletionList(NULL)
	, m_uNumberOfNodesToDelete(0)
	{
	}

	~Asura_TemplateTree()
	{
		FreeAll();
	}

	void Reset(void)
	{
		// (MH - 15.12.2002) should be no need to delete these in order to reset them.
		FreeAll();
		m_iNumberOfNodes	= 0;
		m_pxFirstRoot		= NULL;
	}

	T* GetData(const Key& xSearchKey)
	{
		Asura_TemplateTree_Node<Key, T>*	pxNode	= m_pxFirstRoot;

		// Check down the whole tree...
		while(pxNode != NULL)
		{
			const int	iCompare	= m_pfnCompare(xSearchKey, pxNode->m_xKey);

			if(iCompare == 0)
			{
				return(&(pxNode->m_xData));
			}
			else
			{
				pxNode	= (iCompare < 0)
						? pxNode->m_pxLower
						: pxNode->m_pxHigher;
			}
		}

		// Failed to find a match...
		return(NULL);
	}

	const T* GetData(const Key& xSearchKey) const
	{
		const Asura_TemplateTree_Node<Key, T>*	pxNode	= m_pxFirstRoot;

		// Check down the whole tree...
		while(pxNode != NULL)
		{
			const int	iCompare	= m_pfnCompare(xSearchKey, pxNode->m_xKey);

			if(iCompare == 0)
			{
				return(&(pxNode->m_xData));
			}
			else
			{
				pxNode	= (iCompare < 0)
						? pxNode->m_pxLower
						: pxNode->m_pxHigher;
			}
		}

		// Failed to find a match...
		return(NULL);
	}

	//adds node to tree , returns pointer to data if successful
	T* AddNode(const Key& xKey, const T& xData)
	{
		if(m_uIterationCount > 0)
		{
			Asura_Assert(false, "Cannot add a tree node during iteration.");
			return(NULL);
		}
		else
		{
			Asura_TemplateTree_Node<Key, T>**	ppxNode			= FindNode(xKey);
			Asura_TemplateTree_Node<Key, T>*	pxExistingNode	= *ppxNode;

			if(pxExistingNode == NULL)
			{
				Asura_TemplateTree_Node<Key, T>*	pxNewNode	= new Asura_TemplateTree_Node<Key, T> (xKey, xData);

				// Add this node to the tree...
				*ppxNode	= pxNewNode;
				m_iNumberOfNodes++;

				return(&(pxNewNode->m_xData));
			}
			else
			{
				// Already exists...
				return(NULL);
			}
		}
	}

	//adds node to tree , returns pointer to data if successful
	T* AddNode(const Key& xKey, Asura_Chunk_Stream& xStream)
	{
		if(m_uIterationCount > 0)
		{
			Asura_Assert(false, "Cannot add a tree node during iteration.");
			return(NULL);
		}
		else
		{
			Asura_TemplateTree_Node<Key, T>**	ppxNode			= FindNode(xKey);
			Asura_TemplateTree_Node<Key, T>*	pxExistingNode	= *ppxNode;
			Asura_TemplateTree_Node<Key, T>*	pxNewNode		= new Asura_TemplateTree_Node<Key, T> (xKey, xStream);

			if(pxExistingNode == NULL)
			{
				// Add this node to the tree...
				*ppxNode	= pxNewNode;
				m_iNumberOfNodes++;

				return(&(pxNewNode->m_xData));
			}
			else
			{
				// Already exists...
				delete(pxNewNode);
				return(NULL);
			}
		}
	}

	//adds node to tree , returns pointer to data if successful
	T* AddNode(const Key& xKey)
	{
		if(m_uIterationCount > 0)
		{
			Asura_Assert(false, "Cannot add a tree node during iteration.");
			return(NULL);
		}
		else
		{
			Asura_TemplateTree_Node<Key, T>**	ppxNode			= FindNode(xKey);
			Asura_TemplateTree_Node<Key, T>*	pxExistingNode	= *ppxNode;

			if(pxExistingNode == NULL)
			{
				Asura_TemplateTree_Node<Key, T>*	pxNewNode	= new Asura_TemplateTree_Node<Key, T> (xKey);

				// Add this node to the tree...
				*ppxNode	= pxNewNode;
				m_iNumberOfNodes++;

				return(&(pxNewNode->m_xData));
			}
			else
			{
				// Already exists...
				return(NULL);
			}
		}
	}

	// Delete a nodes from the tree
	bool DeleteNode(const Key& xKey)
	{
		if(m_uIterationCount > 0)
		{
			if(m_pxDeletionList == NULL)
			{
				m_pxDeletionList = new Key [m_iNumberOfNodes];
			}
			m_pxDeletionList[m_uNumberOfNodesToDelete++]	= xKey;
			return(true);
		}
		else
		{
			Asura_TemplateTree_Node<Key, T>*	pxNode	= UnlinkNode(xKey);

			if(pxNode == NULL)
			{
				return(false);
			}
			else
			{
				delete(pxNode);
				return(true);
			}
		}
	}

	inline int GetNumberOfNodes(void) const
	{
		return(m_iNumberOfNodes);
	}


protected:
	// Protected functions...
	void BeginIteration(void)
	{
		m_uIterationCount++;
	}

	void EndIteration(void)
	{
		if(m_uIterationCount == 0)
		{
			Asura_Assert(false, "Mismatch between call to \"BeginIteration()\" and \"EndIteration\".");
		}
		else
		{
			m_uIterationCount--;

			if(m_uIterationCount == 0)
			{
				FreeDeletedNodesList();
			}
		}
	}

	void FreeAll(void)
	{
		if(m_uIterationCount == 0)
		{
			delete(m_pxFirstRoot);
			delete[](m_pxDeletionList);

			m_pxFirstRoot				= NULL;
			m_pxDeletionList			= NULL;
			m_uNumberOfNodesToDelete	= 0;
		}
		else
		{
			Asura_Assert(false, "This tree is still being iterated over - data will not be freed.");
		}
	}

	Asura_TemplateTree_Node<Key, T>** FindNode(const Key& xSearchKey)
	{
		Asura_TemplateTree_Node<Key, T>**	ppxNode	= &m_pxFirstRoot;
		Asura_TemplateTree_Node<Key, T>*	pxNode	= m_pxFirstRoot;

		//find point to insert new node
		while(pxNode != NULL)
		{
			const int	iCompare	= m_pfnCompare(xSearchKey, pxNode->m_xKey);

			if(iCompare == 0)
			{
				return(ppxNode);
			}
			else
			{
				ppxNode	= (iCompare < 0)
						? &(pxNode->m_pxLower)
						: &(pxNode->m_pxHigher);
				pxNode	= *ppxNode;
			}
		}

		// No matches found - return the last node checked...
		return(ppxNode);
	}

	//Unlinks the specified node from the tree and returns it.
	//The count of the number of nodes is decreased in the process.
	//RAR 15/03/2006
	Asura_TemplateTree_Node<Key, T>* UnlinkNode(const Key& xKey)
	{
		if(m_pxFirstRoot == NULL)
		{
			return(NULL);
		}
		else
		{
			Asura_TemplateTree_Node<Key, T>**	ppxNode			= FindNode(xKey);
			Asura_TemplateTree_Node<Key, T>*	pxNodeToUnlink	= *ppxNode;

			if(pxNodeToUnlink == NULL)
			{
				return(NULL);
			}
			else
			{
				//found the node to delete , if it has children they will need to be transferred up
				if(pxNodeToUnlink->m_pxLower == NULL)
				{
					*ppxNode					= pxNodeToUnlink->m_pxHigher;
					pxNodeToUnlink->m_pxHigher	= NULL;
				}
				else if(pxNodeToUnlink->m_pxHigher == NULL)
				{
					*ppxNode					= pxNodeToUnlink->m_pxLower;
					pxNodeToUnlink->m_pxLower	= NULL;
				}
				else
				{
					Asura_TemplateTree_Node<Key, T>*	pxNodeToTransfer;

					//The deleted node has 2 children  , 1 will need to be found a place beneath the other
					//Pick semi-randomly to keep some chance of things not being unbalanced
					if(m_iNumberOfNodes % 2)
					{
						*ppxNode			= pxNodeToUnlink->m_pxLower;
						pxNodeToTransfer	= pxNodeToUnlink->m_pxHigher;
					}
					else
					{
						*ppxNode			= pxNodeToUnlink->m_pxHigher;
						pxNodeToTransfer	= pxNodeToUnlink->m_pxLower;
					}

					//The unlinked node no longer has any children
					pxNodeToUnlink->m_pxLower	= NULL;
					pxNodeToUnlink->m_pxHigher	= NULL;

					ppxNode		= FindNode(pxNodeToTransfer->m_xKey);
					*ppxNode	= pxNodeToTransfer;
				}

				// Finally, update the node-count and return the unlinked node...
				m_iNumberOfNodes--;
				return(pxNodeToUnlink);
			}
		}
	}

	void FreeDeletedNodesList(void)
	{
		if(m_pxDeletionList != NULL)
		{
			for(u_int u = 0; u < m_uNumberOfNodesToDelete; u++)
			{
				const Key&							xKey	= m_pxDeletionList[u];
				Asura_TemplateTree_Node<Key, T>*	pxNode	= UnlinkNode(xKey);

				delete(pxNode);
			}

			delete[](m_pxDeletionList);
			m_pxDeletionList			= NULL;
			m_uNumberOfNodesToDelete	= 0;
		}
	}

	// Protected variables...
	Asura_TemplateTree_Node<Key, T>*	m_pxFirstRoot;
	int									m_iNumberOfNodes;
	CompareFunction*					m_pfnCompare;

	u_int								m_uIterationCount;
	Key*								m_pxDeletionList;
	u_int								m_uNumberOfNodesToDelete;

};   // End of class 'Asura_TemplateTree'.



////////////////////////////////////////////////////////////////////////////////
// Class        : Asura_TemplateTree_Iterator
// Author       : Andy Tate
// Date         : 3-Dec-2007
//
// Description  : Templified class used to iterate through members of the
//				  "Asura_TemplateTree" class.
////////////////////////////////////////////////////////////////////////////////

template <class Key, class T> class Asura_TemplateTree_Iterator
{
public:
	// Public functions...
	Asura_TemplateTree_Iterator(Asura_TemplateTree<Key, T>& xTree)
	: m_xTree(xTree)
	, m_ppxNodes(NULL)
	, m_uNumNodes(0)
	, m_uCurrentNode(0)
	, m_bIterating( false )
	{
		Begin();
	}
	~Asura_TemplateTree_Iterator()
	{
		End();
	}

	// Function to begin iteration...
	void Begin(void)
	{
		if (!m_bIterating)
		{
			m_uCurrentNode	= 0;
			m_uNumNodes		= m_xTree.GetNumberOfNodes();

			if(m_uNumNodes == 0)
			{
				m_ppxNodes	= NULL;
			}
			else
			{
				m_xTree.BeginIteration();

				m_ppxNodes	=  new Asura_TemplateTree_Node<Key, T>* [m_uNumNodes];

				if(m_xTree.m_pxFirstRoot != NULL)
				{
					FillItemArray(m_xTree.m_pxFirstRoot);
				}

				m_uCurrentNode	= 0;
			}

			m_bIterating = true;
		}
	}

	// Query function to see whether iteration is complete...
	bool Done(void) const
	{
		return(m_ppxNodes == NULL);
	}

	// Function to step onto the next item to be iterated...
	void Next(void)
	{
		m_uCurrentNode++;

		if(m_uCurrentNode == m_uNumNodes)
		{
			End();
		}
	}

	// Function to end iterations...
	void End(void)
	{
		if( m_bIterating && (m_ppxNodes != NULL) )
		{
			delete[](m_ppxNodes);

			m_ppxNodes		= NULL;
			m_uCurrentNode	= 0;
			m_uNumNodes		= 0;

			m_xTree.EndIteration();

			m_bIterating = false;
		}
	}

	void Restart(void)
	{
		End();
		Begin();
	}

	// Accessor function to get the current entry...
	T* GetCurrent(void) const
	{
		if(m_ppxNodes == NULL)
		{
			return(NULL);
		}
		else
		{
			return(&(m_ppxNodes[m_uCurrentNode]->m_xData));
		}
	}

	const Key* GetCurrentKey(void) const
	{
		if(m_ppxNodes == NULL)
		{
			return(NULL);
		}
		else
		{
			return(&(m_ppxNodes[m_uCurrentNode]->m_xKey));
		}
	}


protected:
	// Protected variables...

	// Protected functions...

	// Recursive function used to fill the item array with data...
	void FillItemArray(Asura_TemplateTree_Node<Key, T>* pxNode)
	{
		Asura_TemplateTree_Node<Key, T>*	pxLower		= pxNode->m_pxLower;
		Asura_TemplateTree_Node<Key, T>*	pxHigher	= pxNode->m_pxHigher;

		if(pxLower != NULL)
		{
			FillItemArray(pxLower);
		}

		m_ppxNodes[m_uCurrentNode++]	= pxNode;

		if(pxHigher != NULL)
		{
			FillItemArray(pxHigher);
		}
	}


private:
	// Private variables...
	Asura_TemplateTree<Key, T>&			m_xTree;		// A reference to the tree to iterate over.
	Asura_TemplateTree_Node<Key, T>**	m_ppxNodes;		// An array of pointers to the data to be iterated over.
	u_int								m_uNumNodes;	// The number of nodes to be iterated over.
	u_int								m_uCurrentNode;	// The index of the current node during iteration.
	bool								m_bIterating;	// Flag to enforce ordering of Begin() End()

	// Private functions...
	Asura_TemplateTree_Iterator(void);
	Asura_TemplateTree_Iterator(const Asura_TemplateTree_Iterator& xOther);

	Asura_TemplateTree_Iterator&	operator=(const Asura_TemplateTree_Iterator& xOther);

};   // End of class 'Asura_TemplateTree_Iterator'.



////////////////////////////////////////////////////////////////////////////////
// Class        : Asura_TemplateTree_ConstIterator
// Author       : Andy Tate
// Date         : 3-Dec-2007
//
// Description  : Templified class used to iterate through members of the
//				  "Asura_TemplateTree" class.
////////////////////////////////////////////////////////////////////////////////

template <class Key, class T> class Asura_TemplateTree_ConstIterator
{
public:
	// Public functions...
	Asura_TemplateTree_ConstIterator(Asura_TemplateTree<Key, T> const& xTree)
	: m_xTree(const_cast<Asura_TemplateTree<Key, T>&>(xTree))
	, m_ppxNodes(NULL)
	, m_uNumNodes(0)
	, m_uCurrentNode(0)
	{
		Begin();
	}
	~Asura_TemplateTree_ConstIterator()
	{
		End();
	}

	// Function to begin iteration...
	void Begin(void)
	{
		m_uCurrentNode	= 0;
		m_uNumNodes		= m_xTree.GetNumberOfNodes();

		if(m_uNumNodes == 0)
		{
			m_ppxNodes	= NULL;
		}
		else
		{
			m_xTree.BeginIteration();

			m_ppxNodes	= new Asura_TemplateTree_Node<Key, T> const* [m_uNumNodes];

			if(m_xTree.m_pxFirstRoot != NULL)
			{
				FillItemArray(m_xTree.m_pxFirstRoot);
			}

			m_uCurrentNode	= 0;
		}
	}

	// Query function to see whether iteration is complete...
	bool Done(void) const
	{
		return(m_ppxNodes == NULL);
	}

	// Function to step onto the next item to be iterated...
	void Next(void)
	{
		m_uCurrentNode++;

		if(m_uCurrentNode == m_uNumNodes)
		{
			End();
		}
	}

	// Function to end iterations...
	void End(void)
	{
		if(m_ppxNodes != NULL)
		{
			delete[](m_ppxNodes);

			m_ppxNodes		= NULL;
			m_uCurrentNode	= 0;
			m_uNumNodes		= 0;

			m_xTree.EndIteration();
		}
	}

	// Accessor function to get the current entry...
	T const* GetCurrent(void) const
	{
		if(m_ppxNodes == NULL)
		{
			return(NULL);
		}
		else
		{
			return(&(m_ppxNodes[m_uCurrentNode]->m_xData));
		}
	}

	const Key* GetCurrentKey(void) const
	{
		if(m_ppxNodes == NULL)
		{
			return(NULL);
		}
		else
		{
			return(&(m_ppxNodes[m_uCurrentNode]->m_xKey));
		}
	}


protected:
	// Protected variables...

	// Protected functions...

	// Recursive function used to fill the item array with data...
	void FillItemArray(Asura_TemplateTree_Node<Key, T> const* pxNode)
	{
		Asura_TemplateTree_Node<Key, T> const*	pxLower		= pxNode->m_pxLower;
		Asura_TemplateTree_Node<Key, T> const*	pxHigher	= pxNode->m_pxHigher;

		if(pxLower != NULL)
		{
			FillItemArray(pxLower);
		}

		m_ppxNodes[m_uCurrentNode++]	= pxNode;

		if(pxHigher != NULL)
		{
			FillItemArray(pxHigher);
		}
	}


private:
	// Private variables...
	Asura_TemplateTree<Key, T>&				m_xTree;		// A reference to the tree to iterate over.
	Asura_TemplateTree_Node<Key, T> const**	m_ppxNodes;		// An array of pointers to the data to be iterated over.
	u_int									m_uNumNodes;	// The number of items to be iterated over.
	u_int									m_uCurrentNode;	// The index of the current item during iteration.

	// Private functions...
	Asura_TemplateTree_ConstIterator(void);
	Asura_TemplateTree_ConstIterator(const Asura_TemplateTree_ConstIterator& xOther);

	Asura_TemplateTree_ConstIterator&	operator=(const Asura_TemplateTree_ConstIterator& xOther);

};   // End of class 'Asura_TemplateTree_ConstIterator'.


#endif   // ifndef __ASURA_TEMPLATETREE_H__


/// End of file. ///
