#include "WimpLib:Set.h"

#include "WimpLib:mem.h"
#include "WimpLib:std.h"
#include "WimpLib:Exception.h"

static const char Err_InvalidNode[] = "Set invalid node";
static const char Err_InvalidIndex[] = "Set index out of bounds";

// #define TEST

/*
 * Sets are implemented by using red-black binary trees.
 *
 * A red-black tree is a binary search tree which has the following properties:
 * - Every node is either red or black.
 * - Every leaf (NULL) is back.
 * - If a node is red, then both its children are black.
 * - Every path from a node to a descendant contains the same number
 *   of black nodes.
 * Preserving the red-black properties ensure that the tree remains
 * more or less balanced (depth never exceeds  2*log(n+1))
 * and that insertion takes O(log n).
 *
 * The implementation uses sentinel nodes to mark black leafs.
 *
 * The nodes have also indexing information giving their relative
 * position compared to their parent. The NULL node on top
 * of the tree can be considered to have the position behind
 * the last element in the tree, allowing a fast calculation
 * of the index of a node by traversing the tree from that
 * node to the top and cummulating the relative indexes.
 */

typedef enum {Node_Red, Node_Black} Node_Colour;

struct SetNode
{
	SetNode*     pParent;
	SetNode*     pLeft;
	SetNode*     pRight;
	Node_Colour  Colour;
	const void*  pData;
	int          RelativeIndex;
};

struct Set
{
	SetNode      NilNode;
	Set_FCompare Compare;
	Set_FAlloc   Alloc;
	Set_FDelete  Delete;
	void*        pHandle;
	int          NodeCount;
};

#ifdef TEST

#include <assert.h>

static void ASSERT_NODE(const Set* This, const SetNode* pNode)
{
	const SetNode* pNil = &This->NilNode;

	if (pNode == pNil)
	{
		if ((pNil->pParent != pNil)
		||  (pNil->pRight != pNil)
		||  (pNil->Colour != Node_Black)
		||  !((This->NodeCount > 0) || (pNil->pLeft == pNil))
		||  ((pNode->pLeft != pNil)
			&& ((pNode->pLeft->pParent != pNode) || (pNode->pLeft->RelativeIndex > 0))))
			assert(false);
	}
	else
	{
		int index;

		if ((pNode->pParent != pNil)
			&& (pNode->pParent->pLeft != pNode)
			&& (pNode->pParent->pRight != pNode))
			assert(false);
		if ((pNode->pLeft != pNil)
			&& ((pNode->pLeft->pParent != pNode) || (pNode->pLeft->RelativeIndex > 0)))
			assert(false);
		if ((pNode->pRight != pNil)
			&& ((pNode->pRight->pParent != pNode) || (pNode->pRight->RelativeIndex < 0)))
			assert(false);
		index = Set_GetNodeIndex(This, pNode);
		if (pNode != Set_GetNode(This, index))
			assert(false);
	}
}

#else

#undef  assert
#define assert(x)
#define ASSERT_NODE(x, y)

#endif

/**
 * Creates a new set.
 *
 * @param  pVPtr   Pointer to the function callbacks defining the set.
 *
 * @returns        Pointer to a new Set.
 */
Set* New_Set(void* pHandle, const SetVPtr* pVPtr) throws(mem)
{
	Set* This = throw_mem_alloc(sizeof(*This));

	// Sentinel Node
	This->NilNode.pParent
		= This->NilNode.pLeft
		= This->NilNode.pRight
		= &This->NilNode;
	This->NilNode.Colour = Node_Black;
	This->NilNode.pData = NULL;
	This->NilNode.RelativeIndex = 0;

	This->pHandle = pHandle;
	This->Compare = pVPtr->FCompare;
	This->Alloc = pVPtr->FAlloc;
	This->Delete = pVPtr->FDelete;
	This->NodeCount = 0;

	return This;
}

/**
 * Deletes a set.
 * This function also deletes the elements contained in the set.
 */
void Delete_Set(Set* This)
{
	if (This)
	{
		Set_Clear(This);

		mem_free(This);
	}
}

/**
 * Returns the number of different nodes in the set.
 */
int Set_Count(const Set* This)
{
	return This->NodeCount;
}

/**
 * Returns the function used to sort elements in the set.
 */
Set_FCompare Set_GetFCompare(const Set* This)
{
	return This->Compare;
}

/**
 * Rebalances the ordered tree by pushing the node below its right child.
 * This means that child takes the place of the node, the child's left child
 * becomes the node's right child and the node becomes the child's left child.
 * This operation keeps the tree ordered.
 *
 * @param  pUpper  Pointer to the node around which the rotation takes place.
 */
static void RotateLeft(Set* This, SetNode* pUpper)
{
	const SetNode* pNil = &This->NilNode;
	SetNode* pLower = pUpper->pRight;
	SetNode* pLowerLeft = pLower->pLeft;
	SetNode* pUpperParent = pUpper->pParent;
	int URelIndex = pUpper->RelativeIndex;

	assert(pUpper != pNil);
	assert(pLower != pNil);
	ASSERT_NODE(This, pNil);
	ASSERT_NODE(This, pUpper);
	ASSERT_NODE(This, pLower);
	ASSERT_NODE(This, pLowerLeft);
	ASSERT_NODE(This, pUpperParent);

	// First update relative indexes
	if (pLowerLeft != pNil)
		pLowerLeft->RelativeIndex += pLower->RelativeIndex;
	pUpper->RelativeIndex = -pLower->RelativeIndex;
	pLower->RelativeIndex += URelIndex;

	// Update positions
	pUpper->pRight = pLowerLeft;
	if (pLowerLeft!= pNil) pLowerLeft->pParent = pUpper;

	pLower->pParent = pUpperParent;
	if (pUpper == pUpperParent->pLeft)
		pUpperParent->pLeft = pLower;
	else
		pUpperParent->pRight = pLower;

	pLower->pLeft = pUpper;
	pUpper->pParent = pLower;

	ASSERT_NODE(This, pNil);
	ASSERT_NODE(This, pUpper);
	ASSERT_NODE(This, pLower);
	ASSERT_NODE(This, pLowerLeft);
	ASSERT_NODE(This, pUpperParent);
}

/**
 * Rebalances the ordered tree by pushing the node below its left child.
 * This means that child takes the place of the node, the child's right child
 * becomes the node's left child and the node becomes the child's right child.
 * This operation keeps the tree ordered.
 *
 * @param  pUpper  Pointer to the node around which the rotation takes place.
 */
static void RotateRight(Set* This, SetNode* pUpper)
{
	const SetNode* pNil = &This->NilNode;
	SetNode* pLower = pUpper->pLeft;
	SetNode* pLowerRight = pLower->pRight;
	SetNode* pUpperParent = pUpper->pParent;
	int URelIndex = pUpper->RelativeIndex;

	assert(pUpper != pNil);
	assert(pLower != pNil);
	ASSERT_NODE(This, pNil);
	ASSERT_NODE(This, pUpper);
	ASSERT_NODE(This, pLower);
	ASSERT_NODE(This, pLowerRight);
	ASSERT_NODE(This, pUpperParent);

	// First update relative indexes
	if (pLowerRight != pNil)
		pLowerRight->RelativeIndex += pLower->RelativeIndex;
	pUpper->RelativeIndex = -pLower->RelativeIndex;
	pLower->RelativeIndex += URelIndex;

	// Update positions
	pUpper->pLeft = pLowerRight;
	if (pLowerRight != pNil) pLowerRight->pParent = pUpper;

	pLower->pParent = pUpperParent;
	if (pUpper == pUpperParent->pLeft)
		pUpperParent->pLeft = pLower;
	else
		pUpperParent->pRight = pLower;

	pLower->pRight = pUpper;
	pUpper->pParent = pLower;

	ASSERT_NODE(This, pNil);
	ASSERT_NODE(This, pUpper);
	ASSERT_NODE(This, pLower);
	ASSERT_NODE(This, pLowerRight);
	ASSERT_NODE(This, pUpperParent);
}

/**
 * Propagates relative index changes to the top from the left.
 *
 * @param  pChild  Pointer to node to detach.
 * @param  value   Value to update by, 1 for add, -1 for remove.
 */
static void Set_FixParentIndex
	( Set* This
	, SetNode* pChild
	, int value
	)
{
	const SetNode* pNil = &This->NilNode;
	SetNode* pNode = pChild->pParent;
	SetNode* pParent = pNode->pParent;

	// Update count on each change of direction
	while (pNode != pNil)
	{
		if (pChild == pNode->pLeft)
		{
			if (pNode == pParent->pRight)
				pNode->RelativeIndex += value;
		}
		else
		{
			if (pNode == pParent->pLeft)
				pNode->RelativeIndex -= value;
		}
		pChild = pNode;
		pNode = pParent;
		pParent = pParent->pParent;
	}
}

/**
 * Attaches a node in the ordered tree. The node is marked as red
 * and restoring the red-black properties of the tree rebalances the tree.
 * The relative indexes are updated from the parent node to the top one.
 *
 * @param  pParent  Pointer to the bottom node where to attach in the Set.
 * @param  val      Compare result determining left or right attachment.
 * @param  pNode    Pointer to the node to attach in the Set.
 */
static void Set_Attach(Set* This, SetNode* pParent, int val, SetNode* pNode)
{
	const SetNode* pNil = &This->NilNode;
	SetNode* pWhere = pNode;

	assert(pParent);
	assert(pNode);
	ASSERT_NODE(This, pNil);
	ASSERT_NODE(This, pParent);

	pWhere = pNode;

	pNode->pParent = pParent;
	pNode->pLeft = (SetNode*) pNil;
	pNode->pRight = (SetNode*) pNil;
	pNode->Colour = Node_Red;

	if (val < 0)
	{
		assert(pParent->pLeft == pNil);
		pParent->pLeft = pNode;
		pNode->RelativeIndex = -1;
	}
	else
	{
		assert(pParent->pRight == pNil);
		pParent->pRight = pNode;
		pNode->RelativeIndex = +1;
	}
	Set_FixParentIndex(This, pNode, +1);

	// Red-black adjustments.
	// We introduce a red node at the bottom of the tree node so that we do not
	// increase the black depth but if its parent is red we break the third rule.

	// Note: the sentinel above root is Black
	while (pParent->Colour == Node_Red)
	{
		SetNode* pGrandPa = pParent->pParent;
		SetNode* pUncle;

		// assert(pParent != pNil);
		// assert(pGrandPa->Colour == Node_Black);

		if (pGrandPa == pNil)
		{
			pParent->Colour = Node_Black;
			break;
		}

		if (pParent == pGrandPa->pLeft)
		{
			pUncle = pGrandPa->pRight;

			if (pUncle->Colour == Node_Black)
			{
				// Red parent, black uncle
				// The tree inbalance starts and depending of the configuration
				// we need to put either the node or its parent in grandpa's place
				if (pNode == pParent->pRight)
				{
					RotateLeft(This, pParent);
					pParent = pNode;
				}
				pParent->Colour = Node_Black;
				pGrandPa->Colour = Node_Red;
				RotateRight(This, pGrandPa);
				break;
			}
		}
		else
		{
			pUncle = pGrandPa->pLeft;

			if (pUncle->Colour == Node_Black)
			{
				// Red parent, black uncle
				// The tree inbalance starts and depending of the configuration
				// we need to put either the node or its parent in grandpa's place
				if (pNode == pParent->pLeft)
				{
					RotateRight(This, pParent);
					pParent = pNode;
				}
				pParent->Colour = Node_Black;
				pGrandPa->Colour = Node_Red;
				RotateLeft(This, pGrandPa);
				break;
			}
		}

		// Red parent and uncle
		// Need to fix Colours and try upper in the tree
		pParent->Colour = Node_Black;
		pUncle->Colour = Node_Black;
		pGrandPa->Colour = Node_Red;

		pNode = pGrandPa;
		pParent = pNode->pParent;
	}

	ASSERT_NODE(This, pNil);
	ASSERT_NODE(This, pParent);
	ASSERT_NODE(This, pWhere);
}

/**
 * Detaches a node from the set,
 * rebalances the red-black tree,
 * fixes the relative indexes.
 *
 * @param  pNode  Pointer to node to detach.
 */
static void Set_Detach(Set* This , SetNode* pNode)
{
	const SetNode* pNil = &This->NilNode;
	SetNode* pParent;
	SetNode* pChild;

	assert(pNode && (pNode != pNil));
	ASSERT_NODE(This, pNil);
	ASSERT_NODE(This, pNode);
	ASSERT_NODE(This, pNode->pParent);
	ASSERT_NODE(This, pNode->pLeft);
	ASSERT_NODE(This, pNode->pRight);

	if ((pNode->pLeft != pNil) && (pNode->pRight != pNil))
	{
		// Deleting a node with 2 childs is difficult so we will
		// exchange its data with its successor's node (which is last
		// node on the chain of left chain of the node's right child)
		// since this one as no left child and delete this one.
		SetNode* pNext = Set_GetSuccessor(This, pNode);
		Node_Colour Colour = pNext->Colour;

		assert(pNext && (pNext != pNil));
		assert(pNext->pLeft == pNil);

		ASSERT_NODE(This, pNext);

		// Substitution makes successor's eventual right child the node's only child.
		// Substitution and removal will move node's parent and left child as parent and
		// left child of successor.
		pChild = pNext->pRight;

		Set_FixParentIndex(This, pNext, -1);

		if (pChild != pNil)
		{
			pChild->RelativeIndex += pNext->RelativeIndex;
			if (pNode->pLeft == pChild)
			{
				if (pNext->pParent->pLeft == pNext)
					pChild->RelativeIndex++;
			}
			else
			{
				if (pNext->pParent->pRight == pNext)
					pChild->RelativeIndex--;
			}
		}

		if (pNode->pRight == pNext)
		{
			// Substitution makes successor the node's parent.
			// Substitution and removal leaves successor's right child unchanged.
			pParent = pNext;
		}
		else
		{
			// Substitution makes successor's parent the node's parent.
			pParent = pNext->pParent;
			// After removal successor's child take the place of it's parent in the tree.
			if (pParent->pLeft == pNext)
				pParent->pLeft = pChild;
			else
				pParent->pRight = pChild;
			if (pChild != pNil) pChild->pParent = pParent;

			// After removal right child of node becomes right child of successor.
			pNext->pRight = pNode->pRight;
			pNext->pRight->pParent = pNext;
		}

		// After substitition (and removal), parent and left child of node
		// become parent and left child of successor.
		pNext->pParent = pNode->pParent;
		if (pNext->pParent->pLeft == pNode)
			pNext->pParent->pLeft = pNext;
		else
			pNext->pParent->pRight = pNext;

		pNext->pLeft = pNode->pLeft;
		pNext->pLeft->pParent = pNext;

		pNext->RelativeIndex = pNode->RelativeIndex;
		pNext->Colour = pNode->Colour;
		pNode->Colour = Colour;

		ASSERT_NODE(This, pNext);
	}
	else
	{
		// Node with at most one child.
		pParent = pNode->pParent;
		pChild = (pNode->pLeft != pNil) ? pNode->pLeft : pNode->pRight;

		Set_FixParentIndex(This, pNode, -1);

		if (pChild != pNil)
		{
			pChild->RelativeIndex += pNode->RelativeIndex;
			if (pNode->pLeft == pChild)
			{
				if (pParent->pLeft == pNode)
					pChild->RelativeIndex++;
			}
			else
			{
				if (pParent->pRight == pNode)
					pChild->RelativeIndex--;
			}
		}

		// Let the child take the place of the node in the tree.
		if (pParent->pLeft == pNode)
			pParent->pLeft = pChild;
		else
			pParent->pRight = pChild;

		if (pChild != pNil) pChild->pParent = pParent;
	}

	ASSERT_NODE(This, pNil);
	ASSERT_NODE(This, pParent);
	ASSERT_NODE(This, pChild);

	// Red-black tree adjustments.
	// There is nothing to do if we remove a red node. For a black node either
	// we find (through possible rorations) a red node to turn to black
	// or the whole tree is to end reorganised and end with a decreased black height.

	if (pNode->Colour == Node_Black)
	{
		if (pChild->Colour == Node_Red)
		{
			// The only child is red, turning it black fixes our problem.
			pChild->Colour = Node_Black;
		}
        else
        {
			while(pParent != pNil)
			{
				SetNode* pSister;

				if (pChild == pParent->pLeft)
				{
					pSister = pParent->pRight;

					if (pSister->Colour == Node_Red)
					{
						// Means that parent is black and sister childs are black
						// Rotate the sister above brings us to a case below
						pSister->Colour = Node_Black;
						pParent->Colour = Node_Red;
						RotateLeft(This, pParent);
						pSister = pParent->pRight;
					}

					// Now sister is always back

					if (pSister->pRight->Colour == Node_Black)
					{
						if (pSister->pLeft->Colour == Node_Black)
						{
							if (pParent->Colour == Node_Black)
							{
								// Everything is black around us, there is nothing
								// that can be done at our level, so decrease the black count
								// on the sister side too by turning it red and reattempt
								// one level higher.
								pSister->Colour = Node_Red;

								pChild = pParent;
								pParent = pChild->pParent;

								continue;
							}
							else
							{
								// Turn parent black to restore black height
								// and turn sister red to compensate in that direction.
								pSister->Colour = Node_Red;
								pParent->Colour = Node_Black;
								break;
							}
						}
						else
						{
							// Rotate sister right and change Colours to maintain height
							pSister->pLeft->Colour = Node_Black;
							pSister->Colour = Node_Red;
							RotateRight(This, pSister);
							pSister = pParent->pRight;
							// The configuration is now the same as final case
						}
					}

					// Sister is black and has a red right child

					pSister->Colour = pParent->Colour;
					pSister->pRight->Colour = Node_Black;
					pParent->Colour = Node_Black;
					RotateLeft(This, pParent);
					break;
				}
				else
				{
					pSister = pParent->pLeft;

					if (pSister->Colour == Node_Red)
					{
						// Means that parent is black
						// Rotate the sister above brings us to a case below
						pSister->Colour = Node_Black;
						pParent->Colour = Node_Red;
						RotateRight(This, pParent);
						pSister = pParent->pLeft;
					}

					// Now sister is always back

					if (pSister->pLeft->Colour == Node_Black)
					{
						if (pSister->pRight->Colour == Node_Black)
						{
							if (pParent->Colour == Node_Black)
							{
								// Everything is black around us, there is nothing
								// that can be done at our level, so decrease the black count
								// on the sister side too by turning it red and reattempt
								// one level higher.
								pSister->Colour = Node_Red;

								pChild = pParent;
								pParent = pChild->pParent;

								continue;
							}
							else
							{
								// Turn parent black to restore black height
								// and turn sister red to compensate in that direction.
								pSister->Colour = Node_Red;
								pParent->Colour = Node_Black;
								break;
							}
						}
						else
						{
							// Rotate sister left and change Colours to maintain height
							pSister->pRight->Colour = Node_Black;
							pSister->Colour = Node_Red;
							RotateLeft(This, pSister);
							pSister = pParent->pLeft;
							// The configuration is now the same as final case
						}
					}

					// Sister is black and has a red right child

					pSister->Colour = pParent->Colour;
					pSister->pLeft->Colour = Node_Black;
					pParent->Colour = Node_Black;
					RotateRight(This, pParent);
					break;
				}
			}
		}
	}
}

/**
 * Inserts a new node in the set.
 *
 * @param  pNode  Pointer to the node to insert after.
 *                Use NULL to insert before all elements.
 * @param  pData  Pointer to the data to insert in the Set.
 *
 * @returns       Pointer to a node from the Set.
 */
SetNode* Set_InsertAfter(Set* This, SetNode* pNode, const void* pData) throws(mem)
{
	const SetNode* pNil = &This->NilNode;
	SetNode* pWhere = pNil->pLeft;
	SetNode* pParent = (SetNode*) pNil;
	int val;

	ASSERT_NODE(This, pNil);

	if (pNode == NULL)
	{
		// Insertion before first element, means at the left of first element
		pParent = (SetNode*) pNil;
		while (pParent->pLeft != pNil)
			pParent = pParent->pLeft;
		val = -1;
	}
	else
	{
		// Insertion as right child of node or as left child of sucessor.
		if (pNode->pRight != pNil)
		{
			pParent = pNode->pRight;
			while (pParent->pLeft != pNil)
				pParent = pParent->pLeft;
			val = -1;
		}
		else
		{
			pParent = pNode;
			val = 1;
		}
	}

	// Reached the bottom of the tree.
	// Add the new entry as child of the last node.
	pWhere = throw_mem_alloc(sizeof(*pWhere));
	pWhere->pData = This->Alloc ? This->Alloc(This->pHandle, pData) : pData;

	This->NodeCount++;

	Set_Attach(This, pParent, val, pWhere);

	return pWhere;
}

/**
 * Inserts a new node in the set.
 *
 * @param  pNode  Pointer to the node to insert after.
 *                Use NULL to insert after all elements.
 * @param  pData  Pointer to the data to insert in the Set.
 *
 * @returns       Pointer to a node from the Set.
 */
SetNode* Set_InsertBefore(Set* This, SetNode* pNode, const void* pData) throws(mem)
{
	const SetNode* pNil = &This->NilNode;
	SetNode* pWhere = pNil->pLeft;
	SetNode* pParent = (SetNode*) pNil;
	int val;

	ASSERT_NODE(This, pNil);

	// Insertion after last element means before nil node
	if (pNode == NULL)
		pNode = (SetNode*) pNil;

	// Insertion as left child of node or as right child of predecessor.
	if (pNode->pLeft != pNil)
	{
		pParent = pNode->pLeft;
		while (pParent->pRight != pNil)
			pParent = pParent->pRight;
		val = 1;
	}
	else
	{
		pParent = pNode;
		val = -1;
	}

	// Reached the bottom of the tree.
	// Add the new entry as child of the last node.
	pWhere = throw_mem_alloc(sizeof(*pWhere));
	pWhere->pData = This->Alloc ? This->Alloc(This->pHandle, pData) : pData;

	This->NodeCount++;

	Set_Attach(This, pParent, val, pWhere);

	return pWhere;
}

/**
 * Sets the data associated to a given node.
 *
 * @param  pNode  Pointer to the node.
 * @param  pData  Pointer to the data to associate to the node.
 */
void Set_SetNodeData(Set* This, SetNode* pNode, const void* pData) throws(null)
{
	const SetNode* pNil = &This->NilNode;

	if ((pNode == pNil)
	||  (pNode == NULL))
		throw_runtime(Err_InvalidNode);

	pNode->pData = pData;
}

/**
 * Removes the node from the set and deletes the associated data.
 *
 * @param  pNode  Pointer to node to remove.
 *                NULL is ignored.
 */
void Set_RemoveNode(Set* This, SetNode* pNode)
{
	const SetNode* pNil = &This->NilNode;

	if (!pNode
	||  (pNode == pNil))
		return;

	Set_Detach(This, pNode);

	// Delete the node.
	if (This->Delete) This->Delete(This->pHandle, (void*) pNode->pData);
	mem_free(pNode);
	This->NodeCount--;
}

/**
 * Inserts a new node in the set.
 *
 * @param  index  Index of the node to insert before.
 *                Use -1 to insert after all elements.
 * @param  pData  Pointer to the data to insert in the Set.
 *
 * @returns       Pointer to a node from the Set.
 */
SetNode* Set_Insert(Set* This, int index, const void* pData) throws(mem index)
{
	SetNode* pNode;

	if ((index < -1) || (index > This->NodeCount))
		throw_runtime(Err_InvalidIndex);

	if ((index == -1) || (index == This->NodeCount))
	{
		pNode = NULL;
		index = This->NodeCount;
	}
	else
		pNode = Set_GetNode(This, index);

	pNode = Set_InsertBefore(This, pNode, pData);

	return pNode;
}

/**
 * Sets the data associated to a given node.
 *
 * @param  index  Index of the node.
 * @param  pData  Pointer to the data to associate to the node.
 */
void Set_SetData(Set* This, int index, const void* pData) throws(index)
{
	SetNode* pNode = Set_GetNode(This, index);

	pNode->pData = pData;
}

/**
 * Removes the node from the set and deletes the associated data.
 *
 * @param  index  Index of the node to remove.
 *                Index must be a valid one or -1 which is ignored.
 */
void Set_Remove(Set* This, int index) throws(index)
{
	if (index == -1)
		return;

	Set_RemoveNode(This, Set_GetNode(This, index));
}

/**
 * Recursively deletes all the nodes.
 * This function also delete the data associated to the node.
 */
void Set_Clear(Set* This)
{
	SetNode* pNode = This->NilNode.pLeft;
	SetNode* pNil = &This->NilNode;
	SetNode* pDelNode;

	while(pNode != pNil)
	{
		// goto leftmost child
		while (pNode->pLeft != pNil)
			pNode = pNode->pLeft;

		// a right child might have a left child
		if (pNode->pRight != pNil)
		{
			pNode = pNode->pRight;
			continue;
		}

		// has no child we may delete it
		pDelNode = pNode;
		pNode = pNode->pParent;
		if (pNode->pLeft != pNil)
			pNode->pLeft = pNil;
		else
			pNode->pRight = pNil;

		if (This->Delete) This->Delete(This->pHandle, (void*) pDelNode->pData);
		mem_free(pDelNode);
	}

	This->NodeCount = 0;
	ASSERT_NODE(This, pNil);
}

/**
 * Returns the order of a node in the set, index starts at 0 for the lowest node.
 *
 * @param  pNode  Pointer to the node.
 *
 * @returns       Index.
 */
int Set_GetNodeIndex(const Set* This, const SetNode* pNode) throws(null)
{
	const SetNode* pNil = &This->NilNode;
	int index;

	ASSERT_NODE(This, pNil);

	if ((pNode == pNil)
	||  (pNode == NULL))
		throw_runtime(Err_InvalidNode);

	index = This->NodeCount;

	while (pNode != pNil)
	{
		index += pNode->RelativeIndex;
		pNode = pNode->pParent;
	}

	return index;
}

/**
 * Returns the data associated to a given node.
 *
 * @param  pNode  Pointer to the node.
 *
 * @returns       Pointer to the data associated to the node.
 */
void* Set_GetNodeData(const Set* This, const SetNode* pNode) throws(null)
{
	const SetNode* pNil = &This->NilNode;

	ASSERT_NODE(This, pNil);

	if ((pNode == pNil)
	||  (pNode == NULL))
		throw_runtime(Err_InvalidNode);

	return (void*) pNode->pData;
}

/**
 * Returns the next node in order (>=) to a given node.
 *
 * @param  pNode  Pointer to the node or NULL to get the first (lowest) node.
 *
 * @returns       Pointer to the next node or NULL if none.
 */
SetNode* Set_GetSuccessor(const Set* This, const SetNode* pNode)
{
	const SetNode* pNil = &This->NilNode;

	ASSERT_NODE(This, pNil);

	if (!pNode)
	{
		// Find the leftmost child
		pNode = pNil;

		while (pNode->pLeft != pNil)
			pNode = pNode->pLeft;
	}
	else if (pNode->pRight != pNil)
	{
		// Find the leftmost child of right child
		pNode = pNode->pRight;

		while (pNode->pLeft != pNil)
			pNode = pNode->pLeft;
	}
	else
	{
		// Find this first parent in the chain for which we are at the left side
		const SetNode* pParent = pNode->pParent;

		while ((pParent != pNil) && (pNode == pParent->pRight))
		{
			pNode = pParent;
			pParent = pNode->pParent;
		}

		pNode = pParent;
	}

	return (pNode == pNil) ? NULL : (SetNode*) pNode;
}

/**
 * Returns the previous node in order (<=) to a given node.
 *
 * @param  pNode  Pointer to the node or NULL to get the last (highest) node.
 *
 * @returns       Pointer to the previous node or NULL if none.
 */
SetNode* Set_GetPredeccessor(const Set* This, const SetNode* pNode)
{
	const SetNode* pNil = &This->NilNode;

	ASSERT_NODE(This, pNil);

	if (!pNode)
	{
		// Find the rightmost child
		pNode = pNil;

		while (pNode->pRight != pNil)
			pNode = pNode->pRight;
	}
	else if (pNode->pLeft != pNil)
	{
		// Find the rightmost child of left child
		pNode = pNode->pLeft;

		while (pNode->pRight != pNil)
			pNode = pNode->pRight;
	}
	else
	{
		// Find this first parent in the chain for which we are at the right side
		const SetNode* pParent = pNode->pParent;

		while ((pParent != pNil) && (pNode == pParent->pLeft))
		{
			pNode = pParent;
			pParent = pNode->pParent;
		}

		pNode = pParent;
	}

	return (pNode == pNil) ? NULL : (SetNode*) pNode;
}

/**
 * Attempts to locate data in a set.
 *
 * @param  pNode  Pointer to the node to start from or NULL to start from the beginning.
 * @param  pData  Pointer to data to locate.
 *
 * @returns       Pointer to the set's node containing the data or NULL if not found.
 */
SetNode* Set_FindNode(const Set* This, const SetNode* pNode, const void* pData)
{
	int val;

	if (!pNode) pNode = Set_GetSuccessor(This, NULL);

	while (pNode != NULL)
	{
		val = This->Compare(pData, pNode->pData);

		if (!val) return (SetNode*) pNode;

		pNode = Set_GetSuccessor(This, pNode);
	}

	return NULL;
}

/**
 * Returns the node with the given index.
 *
 * @param  index  Index of the node to locate.
 *
 * @returns       Pointer to the node.
 */
SetNode* Set_GetNode(const Set* This, int index) throws(index)
{
	const SetNode* pNil = &This->NilNode;
	SetNode* pNode = pNil->pLeft;

	ASSERT_NODE(This, pNil);

	index = This->NodeCount - index;

	while (pNode != pNil)
	{
		index += pNode->RelativeIndex;
		if (!index) return pNode;

		if (index > 0)
			pNode = pNode->pLeft;
		else
			pNode = pNode->pRight;
	}

	throw_runtime(Err_InvalidIndex);

	return NULL;
}

/**
 * Returns the data associated to a the node with the given index.
 *
 * @param  index  Index of the node to locate.
 *
 * @returns       Pointer to the data associated to the node.
 */
void* Set_GetData(const Set* This, int index) throws(index)
{
	SetNode* pNode = Set_GetNode(This, index);

	return (void*) pNode->pData;
}

/**
 * Attempts to locate data in a set.
 *
 * @param  index  Index to start from.
 * @param  pData  Pointer to data to locate.
 *
 * @returns       Index of the node containing the data or -1 if not found.
 */
int Set_Find(const Set* This, int index, const void* pData) throws(index)
{
	if (index != This->NodeCount)
	{
		SetNode* pNode = Set_GetNode(This, index);

		pNode = Set_FindNode(This, pNode, pData);

		if (pNode) return Set_GetNodeIndex(This, pNode);
	}

	return -1;
}
