/* Copyright (c) <2003-2011> <Julio Jerez, Newton Game Dynamics>
 *
 * This software is provided 'as-is', without any express or implied
 * warranty. In no event will the authors be held liable for any damages
 * arising from the use of this software.
 *
 * Permission is granted to anyone to use this software for any purpose,
 * including commercial applications, and to alter it and redistribute it
 * freely, subject to the following restrictions:
 *
 * 1. The origin of this software must not be misrepresented; you must not
 * claim that you wrote the original software. If you use this software
 * in a product, an acknowledgment in the product documentation would be
 * appreciated but is not required.
 *
 * 2. Altered source versions must be plainly marked as such, and must not be
 * misrepresented as being the original software.
 *
 * 3. This notice may not be removed or altered from any source distribution.
 */

#include "dgStdafx.h"
#include "dgTree.h"

const dgRedBackNode *dgRedBackNode::Minimum() const {
	const dgRedBackNode *ptr = this;
	for (; ptr->m_left; ptr = ptr->m_left) {
	}
	return ptr;
}

const dgRedBackNode *dgRedBackNode::Maximum() const {
	const dgRedBackNode *ptr = this;
	for (; ptr->m_right; ptr = ptr->m_right) {
	}
	return ptr;
}

const dgRedBackNode *dgRedBackNode::Prev() const {
	if (m_left) {
		return m_left->Maximum();
	}

	const dgRedBackNode *node = this;
	dgRedBackNode *ptr = m_parent;
	for (; ptr && node == ptr->m_left; ptr = ptr->m_parent) {
		node = ptr;
	}
	return ptr;

}

const dgRedBackNode *dgRedBackNode::Next() const {

	if (m_right) {
		return m_right->Minimum();
	}

	const dgRedBackNode *node = this;
	dgRedBackNode *ptr = m_parent;
	for (; ptr && node == ptr->m_right; ptr = ptr->m_parent) {
		node = ptr;
	}
	return ptr;
}

dgRedBackNode *dgRedBackNode::Minimum() {
	dgRedBackNode *ptr = this;
	for (; ptr->m_left; ptr = ptr->m_left) {
	}
	return ptr;
}

dgRedBackNode *dgRedBackNode::Maximum() {
	dgRedBackNode *ptr = this;
	for (; ptr->m_right; ptr = ptr->m_right) {
	}
	return ptr;
}

dgRedBackNode *dgRedBackNode::Prev() {
	if (m_left) {
		return m_left->Maximum();
	}

	dgRedBackNode *node = this;
	dgRedBackNode *ptr = m_parent;
	for (; ptr && node == ptr->m_left; ptr = ptr->m_parent) {
		node = ptr;
	}
	return ptr;

}

dgRedBackNode *dgRedBackNode::Next() {

	if (m_right) {
		return m_right->Minimum();
	}

	dgRedBackNode *node = this;
	dgRedBackNode *ptr = m_parent;
	for (; ptr && node == ptr->m_right; ptr = ptr->m_parent) {
		node = ptr;
	}
	return ptr;
}

// rotate node me to left
void dgRedBackNode::RotateLeft(dgRedBackNode **const head) {
	dgRedBackNode *const me = this;
	dgRedBackNode *const child = me->m_right;

	//establish me->m_right link
	me->m_right = child->m_left;
	if (child->m_left != NULL) {
		child->m_left->m_parent = me;
	}

	// establish child->m_parent link
	if (child != NULL) {
		child->m_parent = me->m_parent;
	}
	if (me->m_parent) {
		if (me == me->m_parent->m_left) {
			me->m_parent->m_left = child;
		} else {
			me->m_parent->m_right = child;
		}
	} else {
		*head = child;
	}

	// link child and me
	child->m_left = me;
	if (me != NULL) {
		me->m_parent = child;
	}
}

// rotate node me to right  *
void dgRedBackNode::RotateRight(dgRedBackNode **const head) {
	dgRedBackNode *const me = this;
	dgRedBackNode *const child = me->m_left;

	// establish me->m_left link
	me->m_left = child->m_right;
	if (child->m_right != NULL) {
		child->m_right->m_parent = me;
	}

	// establish child->m_parent link
	if (child != NULL) {
		child->m_parent = me->m_parent;
	}
	if (me->m_parent) {
		if (me == me->m_parent->m_right) {
			me->m_parent->m_right = child;
		} else {
			me->m_parent->m_left = child;
		}
	} else {
		*head = child;
	}

	// link me and child
	child->m_right = me;
	if (me != NULL) {
		me->m_parent = child;
	}
}

// maintain Red-Black tree balance after inserting node ptr
void dgRedBackNode::InsertFixup(dgRedBackNode **const head) {
	dgRedBackNode *ptr = this;
	// check Red-Black properties
	while ((ptr != *head) && (ptr->m_parent->GetColor() == RED)) {
		// we have a violation
		if (ptr->m_parent == ptr->m_parent->m_parent->m_left) {
			dgRedBackNode *const tmp = ptr->m_parent->m_parent->m_right;
			if (tmp && (tmp->GetColor() == RED)) {
				// uncle is RED
				ptr->m_parent->SetColor(BLACK);
				tmp->SetColor(BLACK);
				ptr->m_parent->m_parent->SetColor(RED);
				ptr = ptr->m_parent->m_parent;
			} else {
				// uncle is BLACK
				if (ptr == ptr->m_parent->m_right) {
					// make ptr a left child
					ptr = ptr->m_parent;
					ptr->RotateLeft(head);
				}

				ptr->m_parent->SetColor(BLACK);
				if (ptr->m_parent->m_parent) {
					ptr->m_parent->m_parent->SetColor(RED);
					ptr->m_parent->m_parent->RotateRight(head);
				}
			}
		} else {
			NEWTON_ASSERT(ptr->m_parent == ptr->m_parent->m_parent->m_right);
			// mirror image of above code
			dgRedBackNode *const tmp = ptr->m_parent->m_parent->m_left;
			if (tmp && (tmp->GetColor() == RED)) {
				//uncle is RED
				ptr->m_parent->SetColor(BLACK);
				tmp->SetColor(BLACK);
				ptr->m_parent->m_parent->SetColor(RED);
				ptr = ptr->m_parent->m_parent;
			} else {
				// uncle is BLACK
				if (ptr == ptr->m_parent->m_left) {
					ptr = ptr->m_parent;
					ptr->RotateRight(head);
				}
				ptr->m_parent->SetColor(BLACK);
				if (ptr->m_parent->m_parent->GetColor() == BLACK) {
					ptr->m_parent->m_parent->SetColor(RED);
					ptr->m_parent->m_parent->RotateLeft(head);
				}
			}
		}
	}
	(*head)->SetColor(BLACK);
}

//maintain Red-Black tree balance after deleting node x
void dgRedBackNode::RemoveFixup(dgRedBackNode *const thisNode,
                                dgRedBackNode **const head) {
	dgRedBackNode *ptr = this;
	dgRedBackNode *node = thisNode;
	while ((node != *head) && (!node || node->GetColor() == BLACK)) {
		if (node == ptr->m_left) {
			if (!ptr) {
				return;
			}
			dgRedBackNode *tmp = ptr->m_right;
			if (!tmp) {
				return;
			}
			if (tmp->GetColor() == RED) {
				tmp->SetColor(BLACK);
				ptr->SetColor(RED);
				ptr->RotateLeft(head);
				tmp = ptr->m_right;
				if (!ptr || !tmp) {
					return;
				}
			}
			if ((!tmp->m_left || (tmp->m_left->GetColor() == BLACK))
			        && (!tmp->m_right || (tmp->m_right->GetColor() == BLACK))) {
				tmp->SetColor(RED);
				node = ptr;
				ptr = ptr->m_parent;
				continue;
			} else if (!tmp->m_right || (tmp->m_right->GetColor() == BLACK)) {
				tmp->m_left->SetColor(BLACK);
				tmp->SetColor(RED);
				tmp->RotateRight(head);
				tmp = ptr->m_right;
				if (!ptr || !tmp) {
					return;
				}
			}
			tmp->SetColor(ptr->GetColor());
			if (tmp->m_right) {
				tmp->m_right->SetColor(BLACK);
			}
			if (ptr) {
				ptr->SetColor(BLACK);
				ptr->RotateLeft(head);
			}
			node = *head;

		} else {
			if (!ptr) {
				return;
			}
			dgRedBackNode *tmp = ptr->m_left;
			if (!tmp) {
				return;
			}
			if (tmp->GetColor() == RED) {
				tmp->SetColor(BLACK);
				ptr->SetColor(RED);
				ptr->RotateRight(head);
				tmp = ptr->m_left;
				if (!ptr || !tmp) {
					return;
				}
			}

			if ((!tmp->m_right || (tmp->m_right->GetColor() == BLACK))
			        && (!tmp->m_left || (tmp->m_left->GetColor() == BLACK))) {
				tmp->SetColor(RED);
				node = ptr;
				ptr = ptr->m_parent;
				continue;
			} else if (!tmp->m_left || (tmp->m_left->GetColor() == BLACK)) {
				tmp->m_right->SetColor(BLACK);
				tmp->SetColor(RED);
				tmp->RotateLeft(head);
				tmp = ptr->m_left;
				if (!ptr || !tmp) {
					return;
				}
			}
			tmp->SetColor(ptr->GetColor());
			if (tmp->m_left) {
				tmp->m_left->SetColor(BLACK);
			}
			if (ptr) {
				ptr->SetColor(BLACK);
				ptr->RotateRight(head);
			}
			node = *head;
		}
	}
	if (node) {
		node->SetColor(BLACK);
	}
}

void dgRedBackNode::Unlink(dgRedBackNode **const head) {
//	dgRedBackNode *child;
//	dgRedBackNode *endNode;
//	dgRedBackNode *endNodeParent;
//	dgRedBackNode::REDBLACK_COLOR oldColor;

	dgRedBackNode *const node = this;
//	node->Kill();
	node->SetInTreeFlag(false);

	if (!node->m_left || !node->m_right) {
		// y has a NULL node as a child
		dgRedBackNode *const endNode = node;

		// x is y's only child
		dgRedBackNode *child = endNode->m_right;
		if (endNode->m_left) {
			child = endNode->m_left;
		}

		// remove y from the parent chain
		if (child) {
			child->m_parent = endNode->m_parent;
		}

		if (endNode->m_parent) {
			if (endNode == endNode->m_parent->m_left) {
				endNode->m_parent->m_left = child;
			} else {
				endNode->m_parent->m_right = child;
			}
		} else {
			*head = child;
		}

		if (endNode->GetColor() == BLACK) {
			if (endNode->m_parent)
				endNode->m_parent->RemoveFixup(child, head);
			else if (*head)
				(*head)->SetColor(BLACK);
		}
//		endNode->Release();
//		delete endNode;

	} else {

		// find tree successor with a NULL node as a child
		dgRedBackNode *endNode = node->m_right;
		while (endNode->m_left != NULL) {
			endNode = endNode->m_left;
		}

		NEWTON_ASSERT(endNode);
		NEWTON_ASSERT(endNode->m_parent);
		NEWTON_ASSERT(!endNode->m_left);

		// x is y's only child
		dgRedBackNode *const child = endNode->m_right;

		NEWTON_ASSERT(
		    (endNode != node->m_right) || !child || (child->m_parent == endNode));

		endNode->m_left = node->m_left;
		node->m_left->m_parent = endNode;

		dgRedBackNode *endNodeParent = endNode;
		if (endNode != node->m_right) {
			if (child) {
				child->m_parent = endNode->m_parent;
			}
			endNode->m_parent->m_left = child;
			endNode->m_right = node->m_right;
			node->m_right->m_parent = endNode;
			endNodeParent = endNode->m_parent;
		}

		if (node == *head) {
			*head = endNode;
		} else if (node == node->m_parent->m_left) {
			node->m_parent->m_left = endNode;
		} else {
			node->m_parent->m_right = endNode;
		}
		endNode->m_parent = node->m_parent;

		dgRedBackNode::REDBLACK_COLOR oldColor = endNode->GetColor();
		endNode->SetColor(node->GetColor());
		node->SetColor(oldColor);

		if (oldColor == BLACK) {
			endNodeParent->RemoveFixup(child, head);
		}
//		node->Release();
//		delete node;
	}
}

void dgRedBackNode::Remove(dgRedBackNode **const head) {
	Unlink(head);
	delete this;
}

void dgRedBackNode::RemoveAllLow() {
	if (m_left) {
		m_left->RemoveAllLow();
	}
	if (m_right) {
		m_right->RemoveAllLow();
	}
	SetInTreeFlag(false);
//	Kill();
//	Release();
	delete this;
}

void dgRedBackNode::RemoveAll() {
	dgRedBackNode *root = this;
	for (; root->m_parent; root = root->m_parent)
		;
	root->RemoveAllLow();
}