///////////////////////////////////////////////////////////////////////////////
/// @file deRedBlack.hpp
///
/// @brief templated red-black tree
///
/// @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 2003
/// @author Assassin
/// @remarks Creation
///
///////////////////////////////////////////////////////////////////////////////

#ifndef DEREDBLACK_HPP
#define DEREDBLACK_HPP

#include "deList.hpp"

// part of this code is adapted from a Java applet demo which can be found at
// http://www.ece.uc.edu/~franco/C321/html/RedBlack/redblack.html

template <class T>
class deTRedBlack
{
	class TRBNode
	{
	public:
		explicit TRBNode()
			:Left(NULL), Right(NULL), Parent(NULL), Tree(NULL), Color(Red)
		{
		}
		TRBNode(const T & ref)
			:Data(ref), Left(NULL), Right(NULL), Parent(NULL), Tree(NULL), Color(Red)
		{
		}
		TRBNode(const TRBNode & ref)
			:Data(ref.Data), Left(NULL), Right(NULL), Parent(NULL), Tree(NULL), Color(Red)
		{
		}
		~TRBNode()
			{}
		bool operator ==(const T & ref)
		{
			return Data == ref;
		}
		bool operator >(const T & ref)
		{
			return Data > ref;
		}
		bool operator <(const T & ref)
		{
			return Data < ref;
		}
		void CopyPtrs(const TRBNode * ref)
		{
			Left = ref->Left;
			Right = ref->Right;
			Parent = ref->Parent;
			Color = ref->Color;
		}
		template<class _Ty> inline
		void Swap(_Ty& _X, _Ty& _Y)
		{
			_Ty _Tmp(_X);
			_X = _Y;
			_Y = _Tmp; 
		}
		void SwapWith(TRBNode * Swapper, TRBNode* &Root)
		{
			if (Left)
				Left->Parent = Swapper;
			if (Right)
				Right->Parent = Swapper;
			if (Swapper->Left)
				Swapper->Left->Parent = this;
			if (Swapper->Right)
				Swapper->Right->Parent = this;
			if (Parent)
			{
				if (Parent->Left == this)
				{
					Parent->Left = Swapper;
				}
				else if (Parent->Right == this)
				{
					Parent->Right = Swapper;
				}
				else if (Swapper->Right == this)
				{
					Swapper->Right = Swapper;
				}
				else if (Swapper->Left == this)
				{
					Swapper->Left = Swapper;
				}
			}
			else
				Root = Swapper;
			if (Swapper->Parent)
			{
				if (Swapper->Parent->Left == Swapper)
				{
					Swapper->Parent->Left = this;
				}
				else if (Swapper->Parent->Right == Swapper)
				{
					Swapper->Parent->Right = this;
				}
				else if (Right == Swapper)
				{
					Right = this;
				}
				else if (Left == Swapper)
				{
					Left = this;
				}
			}
			else
				Root = this;
			Swap(Left, Swapper->Left);
			Swap(Right, Swapper->Right);
			Swap(Parent, Swapper->Parent);
			Swap(Color, Swapper->Color);
		}
		void Destroy()
		{
			if (Left)
				Left->Destroy();
			if (Right)
				Right->Destroy();
			delete this;
		}
		void AddDataToList(deTList <T*> &list)
		{
			list.AddElement(&Data);
			if (Left)
				Left->AddDataToList(list);
			if (Right)
				Right->AddDataToList(list);
		}

		TRBNode *Left, *Right;
		TRBNode *Parent;
		enum Color_t {Red, Black} Color;
		deTRedBlack * Tree;
		T Data;
	};

private:
	TRBNode * m_Root;
	long m_Length;

public:
	deTRedBlack()
	{
		m_Root = NULL;
		m_Length = 0;
	}
	~deTRedBlack()
	{
		EmptyTree();
	}

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

	void* FindValue(const T& Val, T* &obj) const
	{
		TRBNode *Node = m_Root;
		while (Node)
		{
			if (*Node == Val)
				break;
			if (*Node > Val)
				Node = Node->Left;
			else
				Node = Node->Right;
		}
		if (!Node)
		{
			obj = NULL;
			return NULL;
		}
		else
			obj = &(Node->Data);
		return Node;
	}
	void* FindValue(const T& Val, T & obj) const
	{
		T * objptr;
		void * ptr;
		ptr = FindValue(Val, objptr);
		if (objptr)
			obj = *objptr;
		return ptr;
	}
	void* GetRoot(T* &obj) const
	{
		TRBNode *Node = m_Root;
		obj = NULL;
		if (!Node)
		{
			return NULL;
		}
		obj = &(Node->Data);
		return Node;
	}
	void * GetLeftMost(T &obj)
	{
		T * objptr;
		void * ptr;
		ptr = GetLeftMost(objptr);
		if (objptr)
			obj = *objptr;
		return ptr;
	}
	void * GetLeftMost(T* &obj)
	{
		TRBNode *Node = m_Root;
		obj = NULL;
		if (!Node)
		{
			return NULL;
		}
		while (Node->Left)
			Node = Node->Left;
		if (Node)
		{
			obj = &(Node->Data);
		}
		return Node;
	}
	void * GetLeftMostLeaf(T* &obj)
	{
		TRBNode *Node = 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);
		}
		return Node;
	}
	void * GetNextRight(void * current, T &obj)
	{
		T * objptr;
		void * ptr;
		ptr = GetNextRight(current, objptr);
		if (objptr)
			obj = *objptr;
		return ptr;
	}
	void * GetNextRight(void * current, T* &obj)
	{
		TRBNode *Node = (TRBNode*)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)
			{
				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);
		}
		return Node;
	}
	void* AddElement(const T & data)
	{
		TRBNode *Node, *NewNode = new TRBNode(data);
		if (!NewNode)
			return NULL;

		NewNode->Tree = this;
		m_Length++;
		if (m_Root == NULL)
			m_Root = NewNode;
		else
		{
			Node = m_Root;
			while (Node != NULL)
			{
				if (*Node > data) // looks a little funky, but it's due to the operator order
				{
					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;
					}
				}
			}
		}

		RestoreRedBlack(NewNode);

		return NewNode;
	}
	static void StaticRemoveElement(void * ptr)
	{
		TRBNode * Node = (TRBNode*)ptr;
		if (Node->Tree)
			Node->Tree->RemoveElement(ptr);
	}
#pragma todo (make sure RemoveElement really works)
	deBoolean RemoveElement(void * ptr)
	{
		TRBNode * Node = (TRBNode*)ptr;
		if (Node == NULL)
			return deFALSE;
		TRBNode * DeletedNode = NULL;
		deBoolean LeftSide;

		if (Node->Left && Node->Right)
		{
			// have two children. This is the "Nasty Case"
			// but we can do a fancy trick by swapping that guarantees we have one or no children
			// we swap with one that only has one child, and "delete" that one instead
			TRBNode * Swapper = Node->Right;
			// get the smallest value that's greater than value in 'Node'
			while (Swapper->Left)
			{
				Swapper = Swapper->Left;
			}
			Swapper->SwapWith(Node, m_Root);
		}
		
		if (Node->Left || Node->Right)
		{
			// we have a single child
			if (Node->Right == NULL)
			{
				// only have a left node
				DeletedNode = Node;
				Node->Left->Parent = Node->Parent;
				if (Node->Parent)
				{
					LeftSide = (Node->Parent->Left == Node);
					if (LeftSide)
					{
						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
				DeletedNode = Node;
				Node->Right->Parent = Node->Parent;
				if (Node->Parent)
				{
					LeftSide = (Node->Parent->Left == Node);
					if (LeftSide)
					{
						Node->Parent->Left = Node->Right;
					}
					else //if (Node->Parent->Right == Node)
					{
						Node->Parent->Right = Node->Right;
					}
				}
				else
					m_Root = Node->Right;
			}
		}
		else
		{
			//no children, just point the parent at NULL
			DeletedNode = Node;
			if (Node->Parent)
			{
				LeftSide = (Node->Parent->Left == Node);
				if (LeftSide)
				{
					Node->Parent->Left = NULL;
				}
				else //if (Node->Parent->Right == Node)
				{
					Node->Parent->Right = NULL;
				}
			}
			else
				m_Root = NULL;
		}

		// deleting black affects the black-depth of the tree
		// so we need to adjust & possibly rebalance
		if (DeletedNode->Color == TRBNode::Black)
		{
			if (DeletedNode->Parent)
			{
				// if it had a child, then the child was merely moved into its place and can be re-colored to black
				if (LeftSide && DeletedNode->Parent->Left)
				{
					DeletedNode->Parent->Left->Color = TRBNode::Black;
					goto GoodRet;
				}
				else if (!LeftSide && DeletedNode->Parent->Right)
				{
					DeletedNode->Parent->Right->Color = TRBNode::Black;
					goto GoodRet;
				}
			}

			{
				// deleted node was black leaf, this is the tough one
				TRBNode RootSentinel;
				TRBNode* Sibling;
				TRBNode* Current;
				TRBNode* NodeParent;
				m_Root->Parent = &RootSentinel;
				RootSentinel.Left = m_Root;
				RootSentinel.Right = NULL;
				Current = DeletedNode;
				NodeParent = Current->Parent;
				if (NodeParent)
					Sibling = (LeftSide) ? NodeParent->Right : NodeParent->Left;
				else
					Sibling = NULL;
				// Loop until the current node is red, or until we get to the root node.
				while (NodeParent->Parent && Current->Color == TRBNode::Black)
				{
					// If the sibling is red, we are unable to reduce the number of black
					// nodes in the sibling tree, and we can't increase the number of 
					// black nodes in our tree..  Thus we must do a rotation from the 
					// sibling tree to our tree to give us some extra (red) nodes to 
					// play with. This is Case 1 from the text
					if (Sibling && Sibling->Color == TRBNode::Red)
					{
						NodeParent->Color = TRBNode::Red;
						Sibling->Color = TRBNode::Black;
						if (LeftSide)
						{
							leftRotate(NodeParent);
							Sibling = NodeParent->Right;
						}
						else
						{
							rightRotate(NodeParent);
							Sibling = NodeParent->Left;
						}
						continue;
					}
					// Sibling will be black here
					
					// If the sibling is black and has no red children, we have to
					// reduce the black node count in the sibling's tree to match ours.
					// This is Case 2a from the text.
					if (!Sibling || 
						((!Sibling->Left || Sibling->Left->Color == TRBNode::Black) &&
						 (!Sibling->Right|| Sibling->Right->Color== TRBNode::Black)))
					{
						if (Sibling)
							Sibling->Color = TRBNode::Red;
						// Now we move one level up the tree to continue fixing the other branches.
						Current = NodeParent;
						NodeParent = Current->Parent;
						LeftSide = (NodeParent->Left == Current);
						Sibling = (LeftSide) ? NodeParent->Right : NodeParent->Left;
						continue;
					}
					// Sibling will be black with 1 or 2 red children here

					// << Case 2b is handled by the while loop. >>

					// If one of the sibling's children are red, we again can't make the
					// sibling red to balance the tree at the parent, so we have to do a
					// rotation.  If the "near" nephew is red and the "far" nephew is
					// black, we need to do a "prep-slide" (aka "double rotation")
					// After doing a rotation and rearranging a few colors, the effect is
					// that we maintain the same number of black nodes per path on the 
					// far side of the parent, and we gain a black node on the current 
					// side, so we are done.
					// This is Case 4 from the text. (Case 3 is the double rotation)
					if (LeftSide)
					{
						if (Sibling->Right->Color == TRBNode::Black)
						{ // Case 3 from text
							rightSide_RightRotate(Sibling);
							Sibling = NodeParent->Right;
						}
						// now Case 4 from the text
						if (Sibling->Right->Color != TRBNode::Black ||
							Sibling->Color != NodeParent->Color ||
							NodeParent->Color != TRBNode::Black)
						{
							Sibling->Right->Color = TRBNode::Black;
							Sibling->Color = NodeParent->Color;
							NodeParent->Color = TRBNode::Black;
						}
						
						Current = NodeParent;
						NodeParent = Current->Parent;
						// I would have assigned to leftSide here,
						//   but we are exiting the function, so why bother?
						// leftSide= (Parent->Left == Current);
						if (NodeParent->Left == Current)
							leftSide_LeftRotate(Current);
						else
							rightSide_LeftRotate(Current);
						goto GoodRet;
					}
					else
					{
						if (Sibling->Left->Color == TRBNode::Black)
						{ // Case 3 from text
							leftSide_LeftRotate(Sibling);
							Sibling = NodeParent->Left;
						}
						// Case 4 from the text
						if (Sibling->Left->Color != TRBNode::Black ||
							Sibling->Color != NodeParent->Color ||
							NodeParent->Color != TRBNode::Black)
						{
							Sibling->Left->Color = TRBNode::Black;
							Sibling->Color = NodeParent->Color;
							NodeParent->Color = TRBNode::Black;
						}
						
						Current = NodeParent;
						NodeParent = Current->Parent;
						// I would have assigned to leftSide here,
						// but we are exiting the function, so why bother?
						// leftSide = (Parent->Left == Current);
						if (NodeParent->Left == Current)
							leftSide_LeftRotate(Current);
						else
							rightSide_LeftRotate(Current);
						goto GoodRet;
					}
					// Now, make the current node black (to fulfill Case 2b)
					// Case 4 will have exited directly out of the function.
					// If we stopped because we reached the top of the tree,
					//   the head is black anyway so don't worry about it.
					Current->Color = TRBNode::Black;
         		}
				m_Root = RootSentinel.Left;
				if (m_Root)
					m_Root->Parent = NULL;
			}
		}
GoodRet:
		if (m_Root)
			DE_ASSERT(m_Root->Color == TRBNode::Black);
		delete Node;
		m_Length--;
		return deTRUE;
	}
	T* GetData(void* ptr)
	{
		TRBNode * Node = (TRBNode*)ptr;
		if (Node == NULL)
			return NULL;
		return &(Node->Data);
	}
	void GetDataPList(deTList <T*> &list)
	{
		if (m_Root)
			m_Root->AddDataToList(list);
	}
	long Length() const
	{
		return m_Length;
	}
private:
	void RestoreRedBlack(TRBNode * Node)
	{
		if (!Node)
			return;
		TRBNode* Uncle;
		/* Now restore the red-black property */
		Node->Color = TRBNode::Red;
		while ( (Node != m_Root) && (Node->Parent->Color == TRBNode::Red) )
		{
			if ( Node->Parent == Node->Parent->Parent->Left )
			{
				/* If x's parent is a left, y is x's right 'uncle' */
				Uncle = Node->Parent->Parent->Right;
				if (Uncle && Uncle->Color == TRBNode::Red )
				{
					/* case 1 - change the colours */
					Node->Parent->Color = TRBNode::Black;
					Uncle->Color = TRBNode::Black;
					Node->Parent->Parent->Color = TRBNode::Red;
					/* Move x up the tree */
					Node = Node->Parent->Parent;
				}
				else
				{
					/* y is a black node */
					if ( Node == Node->Parent->Right )
					{
						/* and x is to the right */ 
						/* case 2 - move x up and rotate */
						Node = Node->Parent;
						RotateLeft( Node );
					}
					/* case 3 */
					Node->Parent->Color = TRBNode::Black;
					Node->Parent->Parent->Color = TRBNode::Red;
					RotateRight( Node->Parent->Parent );
				}
			}
			else
			{
				/* If x's parent is a right, y is x's left 'uncle' */
				Uncle = Node->Parent->Parent->Left;
				if (Uncle && Uncle->Color == TRBNode::Red )
				{
					/* case 1 - change the colours */
					Node->Parent->Color = TRBNode::Black;
					Uncle->Color = TRBNode::Black;
					Node->Parent->Parent->Color = TRBNode::Red;
					/* Move x up the tree */
					Node = Node->Parent->Parent;
				}
				else
				{
					/* y is a black node */
					if ( Node == Node->Parent->Left )
					{
						/* and x is to the right */ 
						/* case 2 - move x up and rotate */
						Node = Node->Parent;
						RotateRight( Node );
					}
					/* case 3 */
					Node->Parent->Color = TRBNode::Black;
					Node->Parent->Parent->Color = TRBNode::Red;
					RotateLeft( Node->Parent->Parent );
				}
			}  
		}
		/* Colour the root black */
		m_Root->Color = TRBNode::Black;
    }
	void RotateLeft(TRBNode * Node)
	{
		TRBNode * y;
		y = Node->Right;
		/* Turn y's left sub-tree into x's right sub-tree */
		Node->Right = y->Left;
		if ( y->Left != NULL )
			y->Left->Parent = Node;
		/* y's new parent was x's parent */
		y->Parent = Node->Parent;
		/* Set the parent to point to y instead of x */
		/* First see whether we're at the root */
		if ( Node->Parent == NULL )
			m_Root = y;
		else
		{
			if ( Node == (Node->Parent)->Left )
				/* x was on the left of its parent */
				Node->Parent->Left = y;
			else
				/* x must have been on the right */
				Node->Parent->Right = y;
		}
		/* Finally, put x on y's left */
		y->Left = Node;
		Node->Parent = y;	
	}
	void RotateRight(TRBNode * Node)
	{
		TRBNode * y;
		y = Node->Left;
		/* Turn y's right sub-tree into x's left sub-tree */
		Node->Left = y->Right;
		if ( y->Right != NULL )
			y->Right->Parent = Node;
		/* y's new parent was x's parent */
		y->Parent = Node->Parent;
		/* Set the parent to point to y instead of x */
		/* First see whether we're at the root */
		if ( Node->Parent == NULL )
			m_Root = y;
		else
		{
			if ( Node == (Node->Parent)->Right )
				/* x was on the right of its parent */
				Node->Parent->Right = y;
			else
				/* x must have been on the left */
				Node->Parent->Left = y;
		}
		/* Finally, put x on y's right */
		y->Right = Node;
		Node->Parent = y;	
	}

	void rightRotate(TRBNode* node)
	{
		if (node->Parent->Left == node)
			leftSide_RightRotate(node);
		else
			rightSide_RightRotate(node);
	}
	
	void leftRotate(TRBNode* node)
	{
		if (node->Parent->Left == node)
			leftSide_LeftRotate(node);
		else
			rightSide_LeftRotate(node);
	}
	
	void leftSide_LeftRotate(TRBNode* node)
	{
		TRBNode* temp = node->Parent; // temp is used for parent
		TRBNode* child = node->Right;
		
		temp->Left = child;
		child->Parent = temp;
		
		temp = child->Left; // temp is now used for grandchild
		node->Right = temp;
		temp->Parent = node;
		
		child->Left = node;
		node->Parent = child;
	}
	
	void leftSide_RightRotate(TRBNode* node)
	{
		TRBNode* temp = node->Parent; // temp is used for parent
		TRBNode* child = node->Left;
		
		temp->Left = child;
		child->Parent = temp;
		
		temp = child->Right; // temp is now used for grandchild
		node->Left = temp;
		temp->Parent = node;
		
		child->Right = node;
		node->Parent = child;
	}
	
	void rightSide_RightRotate(TRBNode* node)
	{
		TRBNode* temp = node->Parent; // temp is used for parent
		TRBNode* child = node->Left;
		
		temp->Right = child;
		child->Parent = temp;
		
		temp = child->Right; // temp is now used for grandchild
		node->Left = temp;
		temp->Parent = node;
		
		child->Right = node;
		node->Parent = child;
	}
	
	void rightSide_LeftRotate(TRBNode* node)
	{
		TRBNode* temp = node->Parent; // temp is used for parent
		TRBNode* child = node->Right;
		
		temp->Right = child;
		child->Parent = temp;
		
		temp = child->Left; // temp is now used for grandchild
		node->Right = temp;
		temp->Parent = node;
		
		child->Left = node;
		node->Parent = child;
	}

};

//#pragma warning (default : 4710)

#endif // DEREDBLACK_HPP
