/*--------------------------------------------------------------*/
/*  Matt Michie                                                 */
/*  CS 372 - Extra Credit                                       */
/*  mmichie@cs.nmsu.edu                                         */
/*  November 15, 2001                                           */
/*                                                              */
/*  Filename: redblack.c                                        */
/*                                                              */
/*  Can be compiled as such:                                    */
/*  gcc -c redblack.c                                           */
/*  gcc -c mmichie.c                                            */
/*  gcc -o mmichie redblack.o mmichie.o                         */
/*--------------------------------------------------------------*/

#include <stdio.h>
#include "redblack.h"

void RightRotate(RedBlackTree * x)
{
	RedBlackTree *y = x->left;

	x->left = y->right;
	if (y->right != NIL)
		y->right->parent = x;

	if (y != NIL)
		y->parent = x->parent;
	if (x->parent) {
		if (x == x->parent->right)
			x->parent->right = y;
		else
			x->parent->left = y;
	} else {
		root = y;
	}

	y->right = x;
	if (x != NIL)
		x->parent = y;
}

void LeftRotate(RedBlackTree * x)
{
	RedBlackTree *y = x->right;

	x->right = y->left;
	if (y->left != NIL)
		y->left->parent = x;

	if (y != NIL)
		y->parent = x->parent;
	if (x->parent) {
		if (x == x->parent->left)
			x->parent->left = y;
		else
			x->parent->right = y;
	} else {
		root = y;
	}

	y->left = x;
	if (x != NIL)
		x->parent = y;
}

RedBlackTree *Insert(int key)
{
	RedBlackTree *current, *parent, *x;

	current = root;
	parent = 0;
	while (current != NIL) {
		if (key == current->key)
			return (current);
		parent = current;
		if (key < current->key)
			current = current->left;
		else
			current = current->right;
	}

	x = (RedBlackTree *) malloc(sizeof(*x));

	x->key = key;
	x->parent = parent;
	x->left = NIL;
	x->right = NIL;
	x->color = red;

	if (parent) {
		if (key < parent->key)
			parent->left = x;
		else
			parent->right = x;
	} else {
		root = x;
	}

	/* Start fixing the RB Properties if needed */
	while (x != root && x->parent->color == red) {
		if (x->parent == x->parent->parent->left) {
			RedBlackTree *y = x->parent->parent->right;
			if (y->color == red) {
				x->parent->color = black;
				y->color = black;
				x->parent->parent->color = red;
				x = x->parent->parent;
			} else {
				if (x == x->parent->right) {
					x = x->parent;
					LeftRotate(x);
				}
				x->parent->color = black;
				x->parent->parent->color = red;
				RightRotate(x->parent->parent);
			}
		} else {
			RedBlackTree *y = x->parent->parent->left;
			if (y->color == red) {
				x->parent->color = black;
				y->color = black;
				x->parent->parent->color = red;
				x = x->parent->parent;
			} else {
				if (x == x->parent->left) {
					x = x->parent;
					RightRotate(x);
				}
				x->parent->color = black;
				x->parent->parent->color = red;
				LeftRotate(x->parent->parent);
			}
		}
	}
	root->color = black;
	return (x);
}

void DeleteFix(RedBlackTree * x)
{
	while (x != root && x->color == black) {
		if (x == x->parent->left) {
			RedBlackTree *w = x->parent->right;
			if (w->color == red) {
				w->color = black;
				x->parent->color = red;
				LeftRotate(x->parent);
				w = x->parent->right;
			}
			if (w->left->color == black
			    && w->right->color == black) {
				w->color = red;
				x = x->parent;
			} else {
				if (w->right->color == black) {
					w->left->color = black;
					w->color = red;
					RightRotate(w);
					w = x->parent->right;
				}
				w->color = x->parent->color;
				x->parent->color = black;
				w->right->color = black;
				LeftRotate(x->parent);
				x = root;
			}
		} else {
			RedBlackTree *w = x->parent->left;
			if (w->color == red) {
				w->color = black;
				x->parent->color = red;
				RightRotate(x->parent);
				w = x->parent->left;
			}
			if (w->right->color == black
			    && w->left->color == black) {
				w->color = red;
				x = x->parent;
			} else {
				if (w->left->color == black) {
					w->right->color = black;
					w->color = red;
					LeftRotate(w);
					w = x->parent->left;
				}
				w->color = x->parent->color;
				x->parent->color = black;
				w->left->color = black;
				RightRotate(x->parent);
				x = root;
			}
		}
	}
	x->color = black;
}


RedBlackTree *FindKey(int key)
{
	RedBlackTree *Holder = root;
	while (Holder != NIL) {
		if (key == Holder->key)
			return (Holder);
		else if (key < Holder->key)
			Holder = Holder->left;
		else
			Holder = Holder->right;
	}
}


void DeleteNode(RedBlackTree * z)
{
	RedBlackTree *x, *y;

	if (!z || z == NIL)
		return;

	if (z->left == NIL || z->right == NIL) {
		y = z;
	} else {
		y = z->right;
		while (y->left != NIL)
			y = y->left;
	}

	if (y->left != NIL)
		x = y->left;
	else
		x = y->right;

	x->parent = y->parent;
	if (y->parent)
		if (y == y->parent->left)
			y->parent->left = x;
		else
			y->parent->right = x;
	else
		root = x;

	if (y != z)
		z->key = y->key;

	if (y->color == black)
		DeleteFix(x);

	free(y);
}

void Output(int Element)
{
	printf("%d", Element);
}

void PrintTree(RedBlackTree * T)
{
	if ((T != NIL)) {
		printf("(");
		PrintTree(T->left);
		Output(T->key);
		//printf("%d_%c", T->data, T->color == red ? 'r' : 'b');
		PrintTree(T->right);
		printf(")");
	}
}

void NewTree(void)
{
	root = NIL;
	sentinel.left = NIL;
	sentinel.right = NIL;
	sentinel.parent = NIL;
	sentinel.key = 666;
	sentinel.color = black;
}

/*--------------------------------------------------------------*/
/*  Insert a node into the tree, structure, then print out      */
/*  the tree, starting at the root.                             */
/*--------------------------------------------------------------*/
void Ins(int i)
{
	Insert(i);
	//printf("Root is: %d\n", root->key);
	PrintTree(root);
	printf("\n");

}

/*--------------------------------------------------------------*/
/*  Delete a node from the tree structure.                      */
/*--------------------------------------------------------------*/
void Del(int i)
{
	RedBlackTree *Node;
	Node = FindKey(i);
	DeleteNode(Node);
	PrintTree(root);
	printf("\n");
}