///////////////////////////////////////////////////////////////////////////////
/// @file RedBlackTree.cpp
///
/// @brief Destiny3D Red/Black Tree Manager for Memory Manager
///
/// @author Lightning
///
/// 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 Oct 2002
/// @author Lightning
/// @remarks Creation
///
///////////////////////////////////////////////////////////////////////////////

#include "RedBlackTree.hpp"
#include "Internal.hpp"

RedBlackNode RedBlackNULLNode = {REDBLACKNODE_ALLOC | REDBLACKNODE_BLACK, &RedBlackNULLNode, &RedBlackNULLNode, &RedBlackNULLNode, &RedBlackNULLNode, &RedBlackNULLNode};

//internal red/black tree functions

//functions for rotating the tree
void RotateRedBlackTreeLeft(RedBlackNode **Root, RedBlackNode *Node);
void RotateRedBlackTreeRight(RedBlackNode **Root, RedBlackNode *Node);

//functions used to rebalance the tree on insert and delete
void RebalanceRedBlackTreeInsert(RedBlackNode **Root, RedBlackNode *NewNode);
void RebalanceRedBlackTreeDelete(RedBlackNode **Root, RedBlackNode *NewNode);

deBoolean InsertRedBlackTreeNodeAlloc(RedBlackNode **Root, RedBlackNode *AllocNode)
{
	RedBlackNode *CurNode;
	RedBlackNode *PrevNode;

	//insert a node based on the pointer value

	//find where in the tree to insert
	CurNode = *Root;
	PrevNode = &RedBlackNULLNode;
	while(CurNode != &RedBlackNULLNode)
	{
		//if we found an existing entry, fail
		if(CurNode->Ptr == AllocNode->Ptr)
			return deFALSE;

		//save the previous node
		PrevNode = CurNode;

		//see if we go left or right
		if(AllocNode->Ptr < CurNode->Ptr)
			CurNode = CurNode->Left;	//alloc ptr is smaller, go left
		else
			CurNode = CurNode->Right;	//must be larger, go right
	}

	//got to the end of the tree where we insert the node

	//modify the alloc node for the color, type, left, and right
	SetNodeAlloc(AllocNode);
	AllocNode->Left = &RedBlackNULLNode;
	AllocNode->Right = &RedBlackNULLNode;
	AllocNode->Parent = PrevNode;

	//modify the parent entry for left or right
	if(PrevNode != &RedBlackNULLNode)
	{
		//set it's color
		SetNodeRed(AllocNode);

		//modify the parent entry
		if(AllocNode->Ptr < PrevNode->Ptr)
			PrevNode->Left = AllocNode; //alloc is smaller, set the left
		else
			PrevNode->Right = AllocNode; //alloc is larger, set the right
	}
	else
	{
		//it is the root entry, set it as such
		SetNodeBlack(AllocNode);
		*Root = AllocNode;
	}


	//rebalance the tree
	RebalanceRedBlackTreeInsert(Root, AllocNode);

	//end the insert
	return deTRUE;
}

deBoolean InsertRedBlackTreeNodeFree(RedBlackNode **Root, RedBlackNode *FreeNode)
{
	RedBlackNode *CurNode;
	RedBlackNode *PrevNode;

	//insert a free block into the tree. Combine with any other free blocks if possible

	//make sure it is a free node
	SetNodeFree(FreeNode);

	//see if we can combine with any other nodes

	//first, get the left node in the linked list
	CurNode = FreeNode->LinkedLeft;
	if(IsNodeFree(CurNode))	//curnode could be RedBlackNULLNode but that is always Alloc
	{
		//node on the left of us is a free node, combine with it
		DeleteRedBlackTreeNode(Root, CurNode);

		//change it's size
		CurNode->Size = CurNode->Size + FreeNode->Size;

		//change the linkedleft/right entries
		CurNode->LinkedRight = FreeNode->LinkedRight;
		if(FreeNode->LinkedRight != &RedBlackNULLNode)
			FreeNode->LinkedRight->LinkedLeft = CurNode;

		//free the freenode pointer
		InternalFree(FreeNode, sizeof(*FreeNode));

		//change the pointer to the node we combined with
		FreeNode = CurNode;
	}

	//go to the right entry and see if it can combine
	CurNode = FreeNode->LinkedRight;
	if(IsNodeFree(CurNode))	//curnode could be RedBlackNULLNode but that is always Alloc
	{
		//node on the left of us is a free node, combine with it
		DeleteRedBlackTreeNode(Root, CurNode);

		//change it's size
		FreeNode->Size = FreeNode->Size + CurNode->Size;

		//change the linkedleft/right entries
		FreeNode->LinkedRight = CurNode->LinkedRight;
		if(CurNode->LinkedRight != &RedBlackNULLNode)
			CurNode->LinkedRight->LinkedLeft = FreeNode;

		//free the curnode pointer
		InternalFree(CurNode, sizeof(*CurNode));
	}

	
	//we have combined with any possible free entries, now insert into the tree
	
	//find where in the tree to insert
	CurNode = *Root;
	PrevNode = &RedBlackNULLNode;
	while(CurNode != &RedBlackNULLNode)
	{
		//if we found an existing entry, insert as brother and exit
		if(CurNode->Size == FreeNode->Size)
		{
			//set free node as a brother
			FreeNode->Parent = NULL;

			//set the left and right of the free node to the brothers
			FreeNode->Right = CurNode->Brother;
			FreeNode->Left = CurNode;

			//if a brother on the right, point to us
			if(FreeNode->Right)
				FreeNode->Right->Left = FreeNode;

			//modify the current node so it points to us
			CurNode->Brother = FreeNode;

			//done
			return deTRUE;
		}

		//save the previous node
		PrevNode = CurNode;

		//see if we go left or right
		if(FreeNode->Size < CurNode->Size)
			CurNode = CurNode->Left;	//alloc ptr is smaller, go left
		else
			CurNode = CurNode->Right;	//must be larger, go right
	}

	//got to the end of the tree where we insert the node

	//modify the alloc node for the color, type, left, and right
	FreeNode->Left = &RedBlackNULLNode;
	FreeNode->Right = &RedBlackNULLNode;
	FreeNode->Parent = PrevNode;
		
	//modify the parent entry for left or right
	if(PrevNode != &RedBlackNULLNode)
	{
		//set it's color
		SetNodeRed(FreeNode);

		//modify the parent entry
		if(FreeNode->Size < PrevNode->Size)
			PrevNode->Left = FreeNode; //free is smaller, set the left
		else
			PrevNode->Right = FreeNode; //free is larger, set the right
	}
	else
	{
		//it is the root entry, set it as such
		SetNodeBlack(FreeNode);
		*Root = FreeNode;
	}

	//rebalance the tree
	RebalanceRedBlackTreeInsert(Root, FreeNode);

	//end the insert
	return deTRUE;
}

void DeleteRedBlackTreeNode(RedBlackNode **Root, RedBlackNode *Node)
{
	RedBlackNode *ReplacementNode;
	RedBlackNode *ParentRepNode;
	RedBlackNode *x, *z;

	//delete a node from the tree

	//if we are removing a free node entry, see if we can swap with a brother
	if(IsNodeFree(Node))
	{
		//check for brothers
		if(!Node->Parent)
		{
			//no parent pointer, we are a brother
			
			//set the brother on the left and right to point to each other

			//see if we need to change the brother pointer or not
			ParentRepNode = Node->Left;
			if(ParentRepNode->Parent)
				ParentRepNode->Brother = Node->Right;
			else
				ParentRepNode->Right = Node->Right;

			//change the right, if any
			if(Node->Right)
				Node->Right->Left = Node->Left;

			//wipe out any brother entry
			Node->Brother = NULL;

			//done changing the pointers, exit
			return;
		}
		else if(Node->Brother)
		{
			//Have a node parent and we have a brother. Must be the first
			//link in the brother chain

			//get the pointer to the brother that will replace us
			ReplacementNode = Node->Brother;

			//change the brother node so it can be the parent
			ReplacementNode->Brother = ReplacementNode->Right;

			//copy the pointers over from the current node and the color
			ReplacementNode->Left = Node->Left;
			ReplacementNode->Right = Node->Right;
			ReplacementNode->Parent = Node->Parent;
			ReplacementNode->Type = Node->Type;
			
			//change the parent node to point to the right one
			if(Node != *Root)
			{
				//see if we are on the left or right side of the parent
				ParentRepNode = Node->Parent;
				if(Node == ParentRepNode->Left)
					ParentRepNode->Left = ReplacementNode;
				else
					ParentRepNode->Right = ReplacementNode;
			}
			else
			{
				//swapping the root node, do so
				*Root = ReplacementNode;
			}

			//change the siblings, if any
			if(Node->Left != &RedBlackNULLNode)
				Node->Left->Parent = ReplacementNode;
			if(Node->Right != &RedBlackNULLNode)
				Node->Right->Parent = ReplacementNode;

			//now wipe out any brother and parent entry so they are set
			//by someone else
			Node->Parent = NULL;
			Node->Brother = NULL;
			
			//all done replacing, exit
			return;
		}
	}
	
	//either free node and no brother entries to put in place, or alloc node
	
	//if no left or no right, then the replacement node is the node
	if(Node->Left == &RedBlackNULLNode || Node->Right == &RedBlackNULLNode)
		ReplacementNode = Node;
	else
	{
		//take the right side of the node
		ReplacementNode = Node->Right;
		if(ReplacementNode != &RedBlackNULLNode)
		{
			//right side is not null, keep going left on the right until we
			//find the end
			while(ReplacementNode->Left != &RedBlackNULLNode)
				ReplacementNode = ReplacementNode->Left;
		}
		else
		{
			//right side is null, go up a parent entry and then go right
			//until we find that we are no longer on the right side
			z = Node;
			ReplacementNode = Node->Parent;
			while(z == ReplacementNode->Right)
			{
				z = ReplacementNode;
				ReplacementNode = ReplacementNode->Parent;
			}

			//did not find anything to replace with, set replacement as the null node
			if(ReplacementNode == *Root)
				ReplacementNode = &RedBlackNULLNode;
		}
	}

	//if the replacement node does not have anything on the left, get the right
	if(ReplacementNode->Left == &RedBlackNULLNode)
		x = ReplacementNode->Right;
	else
		x = ReplacementNode->Left;

	//set the parent
	x->Parent = ReplacementNode->Parent;

	//if the replacement node is root, then set the left
	if(*Root == x->Parent)
		(*Root)->Left = x;
	else
	{
		//modify the parent for the child entry being put in place
		if(ReplacementNode == ReplacementNode->Parent->Left)
			ReplacementNode->Parent->Left = x;
		else
			ReplacementNode->Parent->Right = x;
	}

	//if we foudn a replacement node, then replace the node entry with it
	if(ReplacementNode != Node)
	{
		//if the replacement node is black, need to do a bit of rebalancing
		if(IsNodeBlack(ReplacementNode))
			RebalanceRedBlackTreeDelete(Root, x);

		//copy of the tree data that is needed
		ReplacementNode->Left = Node->Left;
		ReplacementNode->Right = Node->Right;
		ReplacementNode->Parent = Node->Parent;
		ReplacementNode->Type = Node->Type;

		//update the child entries with the replacement node entry
		if(Node->Left != &RedBlackNULLNode)
			Node->Left->Parent = ReplacementNode;
		if(Node->Right != &RedBlackNULLNode)
			Node->Right->Parent = ReplacementNode;
	}
	else
	{
		//could not find a node to replace with us, may be root or at end of tree
		if(IsNodeBlack(ReplacementNode))
			RebalanceRedBlackTreeDelete(Root, x);
	}

	//verify any stored data on the node is removed as there shouldnt be any
	Node->ExtraData = NULL;

	return;
}

void RotateRedBlackTreeLeft(RedBlackNode **Root, RedBlackNode *Node)
{
	RedBlackNode *RightNode;

	//rotate a red/black tree to the left

	//get the right side of the node
	RightNode = Node->Right;

	//set the right side of the node to the left entry of the right
	Node->Right = RightNode->Left;

	//if the left entry of the right node does have an entry, change it's parent
	if(RightNode->Left != &RedBlackNULLNode)
		RightNode->Left->Parent = Node;

	//now change the right node's parent
	if(RightNode != &RedBlackNULLNode)
		RightNode->Parent = Node->Parent;

	//if a parent exists, update the left or right side entry
	if(Node->Parent != &RedBlackNULLNode)
	{
		//if the left entry, change the left, otherwise change right
		if(Node == Node->Parent->Left)
			Node->Parent->Left = RightNode;
		else
			Node->Parent->Right = RightNode;
	}
	else
	{
		//no parent, change the root entry
		*Root = RightNode;
	}

	//set the left of the right node to the node
	if(RightNode != &RedBlackNULLNode)
		RightNode->Left = Node;

	//if the node isnt the null node, set the parent
	if(Node != &RedBlackNULLNode)
		Node->Parent = RightNode;
}

void RotateRedBlackTreeRight(RedBlackNode **Root, RedBlackNode *Node)
{
	RedBlackNode	*LeftNode;

	//rotate a red/black tree to the right

	//get the left side of the node
	LeftNode = Node->Left;

	//set the left side of the node to the right entry of the left
	Node->Left = LeftNode->Right;

	//if the right entry of the left node does have an entry, change it's parent
	if(LeftNode->Right != &RedBlackNULLNode)
		LeftNode->Right->Parent = Node;

	//now change the left node's parent
	if(LeftNode != &RedBlackNULLNode)
		LeftNode->Parent = Node->Parent;

	//if a parent exists, update the left or right side entry
	if(Node->Parent != &RedBlackNULLNode)
	{
		//if the left entry, change the left, otherwise change right
		if(Node == Node->Parent->Left)
			Node->Parent->Left = LeftNode;
		else
			Node->Parent->Right = LeftNode;
	}
	else
	{
		//no parent, change the root entry
		*Root = LeftNode;
	}

	//set the right of the left node to the node
	if(LeftNode != &RedBlackNULLNode)
		LeftNode->Right = Node;

	//if the node isnt the null node, set the parent
	if(Node != &RedBlackNULLNode)
		Node->Parent = LeftNode;
}

void RebalanceRedBlackTreeInsert(RedBlackNode **Root, RedBlackNode *NewNode)
{
	//rebalance the tree upon inserting a free block

	//while our parent is red and we havent hit the root entry, keep rotating
	while(IsNodeRed(NewNode->Parent))
	{
		//our parent shouldnt be red as we are red, fix it
		
		//see if our parent is on it's parent's left side
		if(NewNode->Parent == NewNode->Parent->Parent->Left)
		{
			//our parent entry is on the left of it's parent, may need to rotate right

			//see if the parent's parent's right side is red
			if(IsNodeRed(NewNode->Parent->Parent->Right))
			{
				//it is red, make our parent black
				SetNodeBlack(NewNode->Parent);

				//set us to the parent's parent entry
				NewNode = NewNode->Parent->Parent;

				//make sure it is red and it's right side is black
				SetNodeBlack(NewNode->Right);
				SetNodeRed(NewNode);
			}
			else
			{
				//the parent's parent's right side is black, rotate as needed
				
				//if we are on the right side of our parent, we need to rotate left
				if(NewNode == NewNode->Parent->Right)
				{
					//rotate it
					NewNode = NewNode->Parent;
					RotateRedBlackTreeLeft(Root, NewNode);
				}

				//change the colors of the parent and the parent's parent
				SetNodeBlack(NewNode->Parent);
				SetNodeRed(NewNode->Parent->Parent);

				//rotate the parent's parent to the right
				RotateRedBlackTreeRight(Root, NewNode->Parent->Parent);
			}
		}
		else
		{
			//our parent's entry is on the right, may need to rotate left

			//see if the parent's parent's left side is red
			if(IsNodeRed(NewNode->Parent->Parent->Left))
			{
				//it is red, make our parent black
				SetNodeBlack(NewNode->Parent);

				//set us to the parent's parent entry
				NewNode = NewNode->Parent->Parent;

				//make sure it is red and it's right side is black
				SetNodeBlack(NewNode->Left);
				SetNodeRed(NewNode);
			}
			else
			{
				//the parent's parent's left side is black, rotate as needed
				
				//if we are on the left side of our parent, we need to rotate right
				if(NewNode == NewNode->Parent->Left)
				{
					//rotate it
					NewNode = NewNode->Parent;
					RotateRedBlackTreeRight(Root, NewNode);
				}

				//change the colors of the parent and the parent's parent
				SetNodeBlack(NewNode->Parent);
				SetNodeRed(NewNode->Parent->Parent);

				//rotate the parent's parent to the right
				RotateRedBlackTreeLeft(Root, NewNode->Parent->Parent);
			}
		}
	}

	//make sure the root is black
	SetNodeBlack((*Root));
}

void RebalanceRedBlackTreeDelete(RedBlackNode **Root, RedBlackNode *NewNode)
{
	RedBlackNode *OtherNode;

	//go up the tree, changing and rebalancing as needed

	//go thru as long as we have black nodes and we arent at the top
	while(NewNode != *Root && IsNodeBlack(NewNode))
	{
		//see if we are on the left or right of the parent
		if(NewNode == NewNode->Parent->Left)
		{
			//on the left

			//get the node on the right
			OtherNode = NewNode->Parent->Right;

			//if the one on the right is red, we need to do a rotate of the tree
			if(IsNodeRed(OtherNode))
			{
				//change the node's color and the node's parent's color
				SetNodeBlack(OtherNode);
				SetNodeRed(NewNode->Parent);
				
				//rotate it
				RotateRedBlackTreeLeft(Root, NewNode->Parent);
				
				//reset the right node pointer. It was rotated left so grab
				//it's parent as it should be equal to NewNode->Parent->Right
				OtherNode = NewNode->Parent->Right;
			}

			//see if the left and right nodes of the right entry are black
			if(IsNodeBlack(OtherNode->Left) && IsNodeBlack(OtherNode->Right))
			{
				//yep, both black, the right entry should be red then if it is not
				//the null node
				if(OtherNode != &RedBlackNULLNode)
					SetNodeRed(OtherNode);

				//go up the tree now
				NewNode = NewNode->Parent;
			}
			else
			{
				//one of them is red, we have a problem

				//if the left color is red, do a rotate right
				if(IsNodeBlack(OtherNode->Right))
				{
					//change the left color, change our color, and do a rotate
					SetNodeBlack(OtherNode->Left);
					SetNodeRed(OtherNode);

					//rotate it
					RotateRedBlackTreeRight(Root, OtherNode);
					
					//reset the right node pointer. It was rotated right so grab
					//NewNode->Parent->Right for the new right node
					OtherNode = NewNode->Parent->Right;
				}

				//set other's color to its' parent's color
				OtherNode->Type = NewNode->Parent->Type;
				
				//make sure the parent and othernode's right entry are black
				SetNodeBlack(NewNode->Parent);
				SetNodeBlack(OtherNode->Right);
				
				//do a rotate left
				RotateRedBlackTreeLeft(Root, NewNode->Parent);
				
				//set us as the root entry
				NewNode = *Root;

				//the above will result in the loop exiting so break to skip the checks
				break;
			}
		}
		else
		{
			//on the right, just a mirror of the above

			//get the node on the right
			OtherNode = NewNode->Parent->Left;

			//if the one on the right is red, we need to do a rotate of the tree
			if(IsNodeRed(OtherNode))
			{
				//change the node's color and the node's parent's color
				SetNodeBlack(OtherNode);
				SetNodeRed(NewNode->Parent);
				
				//rotate it
				RotateRedBlackTreeRight(Root, NewNode->Parent);
				
				//reset the left node pointer. It was rotated right so grab
				//NewNode->Parent->Left for the new left node
				OtherNode = NewNode->Parent->Left;
			}

			//see if the left and right nodes of the right entry are black
			if(IsNodeBlack(OtherNode->Left) && IsNodeBlack(OtherNode->Right))
			{
				//yep, both black, the right entry should be red then if it is not
				//the null node
				if(OtherNode != &RedBlackNULLNode)
					SetNodeRed(OtherNode);

				//go up the tree now
				NewNode = NewNode->Parent;
			}
			else
			{
				//one of them is red, we have a problem

				//if the right color is red, do a Left right
				if(IsNodeBlack(OtherNode->Left))
				{
					//change the left color, change our color, and do a rotate
					SetNodeBlack(OtherNode->Right);
					SetNodeRed(OtherNode);

					//rotate it
					RotateRedBlackTreeLeft(Root, OtherNode);
					
					//reset the right node pointer. It was rotated left so grab
					//NewNode->Parent->Left as it should be the new left node
					OtherNode = NewNode->Parent->Left;
				}

				//set other's color to its' parent's color
				OtherNode->Type = NewNode->Parent->Type;
				
				//make sure the parent and othernode's left entry are black
				SetNodeBlack(NewNode->Parent);
				SetNodeBlack(OtherNode->Left);
				
				//do a rotate right
				RotateRedBlackTreeRight(Root, NewNode->Parent);
				
				//set us as the root entry
				NewNode = *Root;

				//the above will result in the loop exiting so break to skip the checks
				break;
			}
		}
	}

	//all done, set the current node to black
	SetNodeBlack(NewNode);

	//exit from the rebalance
	return;
}

RedBlackNode *FindRedBlackTreeNodeAlloc(RedBlackNode *Root, void *Ptr)
{
	RedBlackNode *CurNode;

	//find a tree node based on the pointer
	CurNode = Root;
	while(CurNode != &RedBlackNULLNode)
	{
		//dig down the tree until we find a node that would work well

		//if the node pointer matches, return it
		if(CurNode->Ptr == Ptr)
			return CurNode;
		else
		{
			//if the pointer we are looking for is smaller than the current entry, head left
			if(Ptr < CurNode->Ptr)
				CurNode = CurNode->Left;
			else
				CurNode = CurNode->Right;
		}
	}

	//never found it, fail
	return &RedBlackNULLNode;
}

RedBlackNode *FindClosestRedBlackTreeNodePtr(RedBlackNode *Root, void *Ptr)
{
	RedBlackNode *CurNode;
	RedBlackNode *PrevNode;

	//find a tree node based on the pointer that is closest the the provided pointer
	CurNode = Root;
	PrevNode = &RedBlackNULLNode;
	while(CurNode != &RedBlackNULLNode)
	{
		//dig down the tree until we find a node that would work well

		//if the pointer we are looking for is smaller than the current entry, head left
		PrevNode = CurNode;
		if(Ptr < CurNode->Ptr)
			CurNode = CurNode->Left;
		else
			CurNode = CurNode->Right;
	}

	//return the last node we were on, if any
	return PrevNode;
}

RedBlackNode *FindRedBlackTreeNodeFree(RedBlackNode *Root, DWORD Size)
{
	RedBlackNode *CurNode;
	RedBlackNode *PrevNode;

	//find a tree node based on the size
	CurNode = Root;
	PrevNode = &RedBlackNULLNode;
	while(CurNode != &RedBlackNULLNode)
	{
		//dig down the tree until we find a node that would work well

		//if the node size matches, return it or one of the brothers
		if(CurNode->Size == Size)
		{
			//if we have a brother entry, return the brother so the tree doesnt
			//have to be rebalanced, otherwise return the one found
			if(CurNode->Brother)
				return CurNode->Brother;
			else
				return CurNode;
		}
		else
		{
			//store the last node we were at
			PrevNode = CurNode;

			//if the size we are looking for is smaller than the current entry, head left
			if(Size < CurNode->Size)
				CurNode = CurNode->Left;
			else
				CurNode = CurNode->Right;
		}
	}
		
	//we hit the end of the list, walk back up the chain until we find a node that works
	//or we hit the top of the tree
	while(PrevNode != &RedBlackNULLNode)
	{
		//if the current node's size is larger, then return it
		if(PrevNode->Size > Size)
			return PrevNode;

		//walk up the parent
		PrevNode = PrevNode->Parent;
	}

	//never found it, fail
	return &RedBlackNULLNode;	
}
