///////////////////////////////////////////////////////////////////////////////
/// @file deBST.hpp
///
/// @brief Templated Binary Search Tree with chaining
///
/// @author Assassin
///
/// This file is the intellectual property of Novus Delta, LLC.. Usage of the
/// contents of this file is subject to the Destiny3D Member License which
/// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
///
/// This file is distributed "AS IS" without warranty of any kind.  Novus
/// Delta, LLC. does not guarantee the fitness of the contents of this file
/// for any particular purpose.
///
/// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
///
/// <hr>
///                                 Change History
/// <hr>
///
/// @date Apr 2002
/// @author Assassin
/// @remarks Creation
///
///////////////////////////////////////////////////////////////////////////////

#ifndef DEBST_HPP
#define DEBST_HPP

#include "deList.hpp"

#pragma warning (disable : 4710)

/// templated binary tree storage class
template <class T, long N>
class deTBST
{
private:
	class TBSTNode
	{
	public:
		TBSTNode(const T & ref, const DWORD Val[N])
			:Data(ref), Left(NULL), Right(NULL), Parent(NULL), Chain(NULL), BST(NULL)
		{
			memcpy(Value, Val, sizeof(DWORD)*N);
		}
		TBSTNode(const TBSTNode & ref)
			:Data(ref.Data), Left(NULL), Right(NULL), Parent(NULL), Chain(NULL), BST(NULL)
		{
			memcpy(Value, ref.Value, sizeof(DWORD)*N);
		}
		~TBSTNode()
			{}
		bool operator ==(const DWORD Val[N])
		{
			for (int i = 0; i < N; i++)
			{
				if (Value[i] != Val[i])
					return false;
			}
			return true;
		}
		bool operator >(const DWORD Val[N])
		{
			for (int i = 0; i < N; i++)
			{
				if (Value[i] <= Val[i])
					return false;
			}
			return true;
		}
		bool operator <(const DWORD Val[N])
		{
			for (int i = 0; i < N; i++)
			{
				if (Value[i] >= Val[i])
					return false;
			}
			return true;
		}
		void Destroy()
		{
			if (Left)
				Left->Destroy();
			if (Right)
				Right->Destroy();
			if (Chain)
				Chain->Destroy();
			delete this;
		}
		void AddDataToList(deTList <T*> &list)
		{
			list.AddElement(&Data);
			if (Chain)
				Chain->AddDataToList(list);
			if (Left)
				Left->AddDataToList(list);
			if (Right)
				Right->AddDataToList(list);
		}
		void AddValueToList(deTList <DWORD> &list)
		{
			list.AddElement(Value);
			if (Left)
				Left->AddValueToList(list);
			if (Right)
				Right->AddValueToList(list);
		}

		TBSTNode *Left, *Right;
		TBSTNode *Parent, *Chain;
		deTBST * BST;
		T Data;
		DWORD Value[N];
/*		//Temp fix for the crash when deleting
		void *operator new (size_t Size)
		{
			return malloc(Size);
		}
		void operator delete (void *p)
		{
			free(p);
			return;
		}
*/	};

public:
	class iterator
	{
	private:
		friend class deTBST<T,N>;
		TBSTNode* m_Node;
	protected:
		iterator(TBSTNode* node) : m_Node(node) {}
	public:
		iterator() : m_Node(NULL) {}
		~iterator() {}
		T& operator*() const
		{
			DE_ASSERT (m_Node != 0);
			return m_Node->Data;
		}
		T* operator->() const { return &operator*(); }
		void operator++()
		{
			TBSTNode *Node = m_Node;
			if (Node->Chain)
			{
				Node = Node->Chain;
			}
			else
			{
				while (Node->Parent && Node->Parent->Chain == Node)
					Node = Node->Parent;
				if (Node->Right)
				{
					Node = Node->Right;
					while (Node->Left)
						Node = Node->Left;
				}
				else if (Node->Parent)
				{
					while (Node && Node->Parent && Node == Node->Parent->Chain)
						Node = Node->Parent;
					while (Node && Node->Parent)
					{
						if (Node->Parent->Left == Node)
						{
							Node = Node->Parent;
							break;
						}
						else
						{
							Node = Node->Parent;
							if (!Node->Parent)
								Node = NULL;
						}
					}
				}
				else
					Node = NULL;
			}
			m_Node = Node;
		}
		//void operator--() { m_Node = m_Node->Prev; }
		bool operator==(const iterator & other) const
		{ return m_Node == other.m_Node; }
		bool operator!=(const iterator & other) const
		{ return m_Node != other.m_Node; }
	};

private:
	TBSTNode * m_Root;
	long m_Length;

public:
	deTBST()
	{
		m_Root = NULL;
		m_Length = 0;
	}
	deTBST(const deTBST <T, N> & ref)
	{
		m_Root = NULL;
		m_Length = 0;

		TBSTNode * Node = ref.m_Root;
		while(Node)
		{
			AddElement(Node->Data, Node->Value);
			Node = Node->Left;
		}
	}
	const deTBST <T, N> & operator=(const deTBST <T, N> & ref)
	{
		// not implemented
		throw;

		EmptyBST();
		
		return *this;
	}
	~deTBST()
	{
		EmptyBST();
	}

	void EmptyBST()
	{
		if (m_Root)
			m_Root->Destroy();
		m_Root = 0;
		m_Length = 0;
	}

	void* GetRoot(T* &obj, DWORD value[N]) const
	{
		TBSTNode *Node = m_Root;
		obj = NULL;
		if (!Node)
		{
			return NULL;
		}
		obj = &(Node->Data);
		if (value)
			memcpy(value, Node->Value, N);
		return Node;
	}
	void* FindValue(const DWORD Val[N], T* &obj) const
	{
		TBSTNode *Node = m_Root;
		while (Node)
		{
			if (*Node == Val)
				break;
			if (*Node > Val)
				Node = Node->Left;
			else
				Node = Node->Right;
		}
		obj = NULL;
		if (!Node)
		{
			return NULL;
		}
		if (Node)
			obj = &(Node->Data);
		return Node;
	}
	void* FindValue(const DWORD Val[N], T & obj) const
	{
		T * objptr;
		void * ptr;
		ptr = FindValue(Val, objptr);
		if (objptr)
			obj = *objptr;
		return ptr;
	}
	void * GetLeftMost(T* &obj, DWORD value[N])
	{
		TBSTNode *Node = (TBSTNode*)m_Root;
		obj = NULL;
		if (!Node)
		{
			return NULL;
		}
		while (Node->Left)
			Node = Node->Left;
		if (Node)
		{
			obj = &(Node->Data);
			if (value)
				memcpy(value, Node->Value, N);
		}
		return Node;
	}
	void * GetLeftMostLeaf(T* &obj, DWORD value[N])
	{
		TBSTNode *Node = (TBSTNode*)m_Root;
		obj = NULL;
		if (!Node)
		{
			return NULL;
		}
		while (Node->Left || Node->Right)
		{
			if (Node->Left)
				Node = Node->Left;
			Node = Node->Right;
		}
		if (Node)
		{
			obj = &(Node->Data);
			if (value)
				memcpy(value, Node->Value, N);
		}
		return Node;
	}
	void * GetLeftMost(T &obj, DWORD value[N])
	{
		T * objptr;
		void * ptr;
		ptr = GetLeftMost(objptr, value);
		if (objptr)
			obj = *objptr;
		return ptr;
	}
	void * GetNextRight(void * current, T* &obj, DWORD value[N])
	{
		TBSTNode *Node = (TBSTNode*)current;
		obj = NULL;
		if (!Node)
		{
			return NULL;
		}
		if (Node->Right)
		{
			Node = Node->Right;
			while (Node->Left)
				Node = Node->Left;
		}
		else if (Node->Parent)
		{
			while (Node && Node->Parent && Node == Node->Parent->Chain)
				Node = Node->Parent;
			while (Node && Node->Parent)
			{
				if (Node->Parent->Left == Node)
				{
					Node = Node->Parent;
					break;
				}
				else
				{
					Node = Node->Parent;
					if (!Node->Parent)
						Node = NULL;
				}
			}
		}
		else
			Node = NULL;
		if (Node)
		{
			obj = &(Node->Data);
			if (value)
				memcpy(value, Node->Value, N);
		}
		return Node;
	}
	void * GetNextRight(void * current, T &obj, DWORD value[N])
	{
		T * objptr;
		void * ptr;
		ptr = GetNextRight(current, objptr, value);
		if (objptr)
			obj = *objptr;
		return ptr;
	}
	void* GetNextChain(void* current, T* &obj) const
	{
		TBSTNode *Node = (TBSTNode*)current;
		obj = NULL;
		if (!Node || !Node->Chain)
		{
			return NULL;
		}
		Node = Node->Chain;
		if (Node)
			obj = &(Node->Data);
		return Node;
	}
	void* GetNextChain(void* current, T & obj) const
	{
		T * objptr;
		void * ptr;
		ptr = GetNextChain(current, objptr);
		if (objptr)
			obj = *objptr;
		return ptr;
	}
	void* AddElement(const T & data, const DWORD Val[N])
	{
		TBSTNode *Node, *NewNode = new TBSTNode(data, Val);
		if (!NewNode)
			return NULL;

		NewNode->BST = this;
		m_Length++;
		if (m_Root == NULL)
			m_Root = NewNode;
		else
		{
			Node = m_Root;
			while (Node != NULL)
			{
				if (*Node == Val)
				{
					while (Node->Chain != NULL)
						Node = Node->Chain;
					Node->Chain = NewNode;
					NewNode->Parent = Node;
					break;
				}
				else
				if (*Node > Val)
				{
					if (Node->Left)
					{
						Node = Node->Left;
					}
					else
					{
						Node->Left = NewNode;
						NewNode->Parent = Node;
						break;
					}
				}
				else
				{
					if (Node->Right)
					{
						Node = Node->Right;
					}
					else
					{
						Node->Right = NewNode;
						NewNode->Parent = Node;
						break;
					}
				}
			}
		}

		return NewNode;
	}
	static void StaticRemoveElement(void * ptr)
	{
		TBSTNode * Node = (TBSTNode*)ptr;
		if (Node->BST)
			Node->BST->RemoveElement(ptr);
	}
//#pragma todo (make sure RemoveElement really works) // I think it does
	deBoolean RemoveElement(void * ptr)
	{
		TBSTNode * Node = (TBSTNode*)ptr;
		if (Node == NULL)
			return deFALSE;

		// if we have a chain, can just shift the next link up into this node's spot
		if (Node->Chain)
		{
			// point the chain at our left child and the child at the chain
			if (Node->Left)
			{
				Node->Chain->Left = Node->Left;
				Node->Left->Parent = Node->Chain;
			}
			// point the chain at our right child and the child at the chain
			if (Node->Right)
			{
				Node->Chain->Right = Node->Right;
				Node->Right->Parent = Node->Chain;
			}
			// if we aren't the root, then the parent needs to update its linkage
			if (Node->Parent)
			{
				Node->Chain->Parent = Node->Parent;
				if (Node->Parent->Chain == Node)
				{
					Node->Parent->Chain = Node->Chain;
				}
				else if (Node->Parent->Left == Node)
				{
					Node->Parent->Left = Node->Chain;
				}
				else if (Node->Parent->Right == Node)
				{
					Node->Parent->Right = Node->Chain;
				}
			}
			else
				m_Root = Node->Chain;
		}
		else if (Node->Left || Node->Right)
		{
			// we have children
			if (Node->Right == NULL)
			{
				// only have a left node
				Node->Left->Parent = Node->Parent;
				if (Node->Parent)
				{
					if (Node->Parent->Chain == Node)
					{
						Node->Parent->Chain = Node->Left;
					}
					else if (Node->Parent->Left == Node)
					{
						Node->Parent->Left = Node->Left;
					}
					else if (Node->Parent->Right == Node)
					{
						Node->Parent->Right = Node->Left;
					}
				}
				else
					m_Root = Node->Left;
			}
			else if (Node->Left == NULL)
			{
				// only have a right node
				Node->Right->Parent = Node->Parent;
				if (Node->Parent)
				{
					if (Node->Parent->Chain == Node)
					{
						Node->Parent->Chain = Node->Right;
					}
					else if (Node->Parent->Left == Node)
					{
						Node->Parent->Left = Node->Right;
					}
					else if (Node->Parent->Right == Node)
					{
						Node->Parent->Right = Node->Right;
					}
				}
				else
					m_Root = Node->Right;
			}
			else
			{
				// have two children. This is the "Nasty Case"
				TBSTNode * tempNode = Node->Right;
				while (tempNode->Left)
				{
					tempNode = tempNode->Left;
				}
				// now we have the smallest value that's greater than value in 'Node'
				{
					// first move its right child into place
					if (tempNode->Right)
						tempNode->Right->Parent = tempNode->Parent;
					if (Node->Parent)
					{
						if (tempNode->Parent->Chain == tempNode)
						{
							tempNode->Parent->Chain = tempNode->Right;
						}
						else if (tempNode->Parent->Left == tempNode)
						{
							tempNode->Parent->Left = tempNode->Right;
						}
						else if (tempNode->Parent->Right == tempNode)
						{
							tempNode->Parent->Right = tempNode->Right;
						}
					}
					else
						m_Root = tempNode;
				}
				// now swap it out
				tempNode->Right = Node->Right;
				tempNode->Left = Node->Left;
				tempNode->Parent = Node->Parent;
				if (Node->Left)
					Node->Left->Parent = tempNode;
				if (Node->Right)
					Node->Right->Parent = tempNode;
			}
		}
		else
		{
			//no children, just point the parent at NULL
			if (Node->Parent)
			{
				if (Node->Parent->Chain == Node)
				{
					Node->Parent->Chain = NULL;
				}
				else if (Node->Parent->Left == Node)
				{
					Node->Parent->Left = NULL;
				}
				else if (Node->Parent->Right == Node)
				{
					Node->Parent->Right = NULL;
				}
			}
			else
				m_Root = NULL;
		}

		delete Node;
		m_Length--;
		return deTRUE;
	}
	T* GetData(void* ptr)
	{
		TBSTNode * Node = (TBSTNode*)ptr;
		if (Node == NULL)
			return NULL;
		return &(Node->Data);
	}
	void GetDataPList(deTList <T*> &list)
	{
		if (m_Root)
			m_Root->AddDataToList(list);
	}
	void GetValueList(deTList <DWORD> &list)
	{
		if (m_Root)
			m_Root->AddValueToList(list);
	}
	long Length() const
	{
		return m_Length;
	}
	long size() const { return m_Length; }
	
	// iterator stuff
	inline iterator begin() {
		TBSTNode *Node = (TBSTNode*)m_Root;
		while (Node && Node->Left)
			Node = Node->Left;
		return iterator(Node);
	}
	inline iterator end()   { return iterator(0); }
	
	iterator insert(const T & data, const DWORD Val[N])
	{
		TBSTNode * Node = (TBSTNode*)AddElement(data, Val);
		return iterator(Node);
	}

	inline iterator erase(iterator& it)
	{
		iterator next = it;
		++next;
		RemoveElement(it.m_Node);
		return next;
	}
};

//#pragma warning (default : 4710)

#endif
