#include<iostream>
#include<time.h>
#include<string>

using namespace std;

#define RED 0
#define BLACK 1
//#define MAX 101000
#define MAX 100
#define SIZE 10
#define NILVALUE -1

typedef struct RB
{
	int key;
	int color;
	struct RB *ptParent;
	struct RB *ptLeft;
	struct RB *ptRight;
}RBT;

void leftRotate(RBT* *root, RBT *pX);
void rightRotate(RBT* *root, RBT *pX);
void rbInsert(RBT* *root, RBT *pZ);
void rbInsertFixup(RBT* *root, RBT *pZ);
void rbDelete(RBT* *root, RBT *pZ);
void rbDeleteFixup(RBT* *root, RBT *pX);
void rbPrintNode(RBT *pX);
void rbPrintTree(RBT* *root);
void Random(int *A, int max, int length);
RBT * treeMinimum(RBT *pX);
RBT * treeSuccessor(RBT *pX);
RBT * treeSearch(RBT **root, int key);
bool isNil(RBT * pX);
//RBT * getNil();

bool isNil(RBT * pX)
{
	if(pX->color == BLACK && pX->key == NILVALUE )
		return true;
	else 
		return false;
}
void setNil(RBT * pX)
{
	pX->color = BLACK;
	pX->key = NILVALUE;
}
RBT * treeSearch(RBT **root, int key)
{
	RBT * pX = * root;
	while(pX != NULL && pX->key != NILVALUE)
	{
		if( pX->key == key)
			return pX;
		else if(pX->key < key)
			pX = pX->ptRight;
		else
			pX = pX->ptLeft;
	}
	return NULL;
}
RBT * treeMinimum(RBT *pX)
{
	while( !isNil(pX->ptLeft))
		pX = pX->ptLeft;
	return pX;
}
RBT * treeSuccessor(RBT *pX)
{
	if(!isNil(pX->ptRight))
		return treeMinimum(pX->ptRight);
	RBT *pY = pX->ptParent;
	while( !isNil(pY) && pX==pY->ptRight)
	{
		pX=pY;
		pY=pY->ptParent;
	}
	return pY;
}
void Random(int *A,const int max, int length)
{
	int *B = new int[max];
	for( int i = 0; i < max; i ++)
		B[i] = i;

	srand(time(NULL));
	
	for(int i = 0; i < max; i ++)
	{
		int r = rand() % (max);
		int tmp;

		tmp = B[i];
		B[i] = B[r];
		B[r] = tmp;
	}
	for( int i = 0 ; i < length ; i++)
	{
		A[i] = B[i];
	}
}
void leftRotate(RBT ** root, RBT * pX)
{
	RBT * pY = pX->ptRight;
	pX->ptRight = pY->ptLeft;

	pY->ptLeft->ptParent = pX;

	pY->ptParent = pX->ptParent;

	if(isNil(pX->ptParent))
		*root = pY;

	else if(pX == pX->ptParent->ptLeft)
			pX->ptParent->ptLeft = pY;
		else
			pX->ptParent->ptRight = pY;

	pY->ptLeft = pX;
	pX->ptParent = pY;

}
void rightRotate(RBT ** root, RBT * pY)
{
	RBT *pX = pY->ptLeft;
	pY->ptLeft = pX->ptRight;
	
	pX->ptRight->ptParent = pY;

	pX->ptParent = pY->ptParent;

	if(isNil(pY->ptParent))
		*root = pX;
	else if( pY == pY->ptParent->ptRight)
			pY->ptParent->ptRight = pX;
		else
			pY->ptParent->ptLeft = pX;

	pX->ptRight = pY;
	pY->ptParent = pX;
}
void rbInsert(RBT ** root, RBT *pZ)
{
	RBT *pY = new RBT();
	setNil(pY);
	RBT	*pX = * root;

	while(!isNil(pX))
	{
		pY = pX;
		if(pZ->key < pX->key)
			pX = pX->ptLeft;
		else
			pX = pX->ptRight;
	}

	pZ->ptParent = pY;

	if(isNil(pY))
		*root = pZ;
	else if(pZ->key < pY->key)
			pY->ptLeft = pZ;
		else
			pY->ptRight = pZ;

	pZ->ptLeft = new RBT();
	setNil(pZ->ptLeft);
	pZ->ptRight = new RBT();
	setNil(pZ->ptRight);
	pZ->color = RED;
	rbInsertFixup(root, pZ);
}
void rbInsertFixup(RBT **root, RBT * pZ)
{
		RBT * pY;
		while(pZ->ptParent->color == RED)
		{
			if(pZ->ptParent->ptParent->ptLeft == pZ->ptParent)
			{
				pY = pZ->ptParent->ptParent->ptRight;

				if(pY->color == RED)
				{//case1
					pZ->ptParent->color = BLACK;
					pY->color = BLACK;
					pZ->ptParent->ptParent->color = RED;
					pZ = pZ->ptParent->ptParent;
		
				}
				else {if(pZ == pZ->ptParent->ptRight)
					{//case2
						pZ = pZ->ptParent;
						leftRotate(root, pZ);
					}

					//case3
					pZ->ptParent->color=BLACK;
					pZ->ptParent->ptParent->color=RED;
					rightRotate(root,pZ->ptParent->ptParent);
					}	
			}
			else
			{
				pY = pZ->ptParent->ptParent->ptLeft;

				if(pY->color == RED)
				{//case1
					pZ->ptParent->color = BLACK;
					pY->color = BLACK;
					pZ->ptParent->ptParent->color = RED;
					pZ = pZ->ptParent->ptParent;
				}
				else{ if(pZ == pZ->ptParent->ptLeft)
					{//case2
						pZ = pZ->ptParent;
						rightRotate(root, pZ);
					}
					//case3
					pZ->ptParent->color = BLACK;
					pZ->ptParent->ptParent->color = RED;
					leftRotate(root, pZ->ptParent->ptParent);
					}
			}		
			
		}
		(*root)->color = BLACK;
}
void rbPrintNode(RBT *pX)
{
	if( pX != NULL)
	{
		cout << "Key: " << pX->key << "\t";

		if(pX->color == RED)
			cout << "Color: RED\t";
		else
			cout << "Color: BLACK\t";

		if(pX->ptLeft != NULL)
			cout << "Left: " << pX->ptLeft->key << "\t";
		else
			cout << "Left: NIL\t";

		if(pX->ptRight != NULL)
			cout << "Right: " << pX->ptLeft->key << "\t";
		else
			cout << "Right: NIL\t";

		if(pX->ptParent != NULL)
			cout << "Parent: " << pX->ptLeft->key << "\t";
		else
			cout << "Parent: NIL\t";
	}
	else
	{
		cout << "EMPTY";
	}
	cout << endl;
}
void rbPrintTree(RBT **root)
{
	if(!isNil(*root))
	{
		cout << "Color: " << (*root)->color << " Key: " << (*root)->key << endl;
		cout << "Node: " << (*root)->key << " Left: ";
		rbPrintTree(&((*root)->ptLeft));
		cout << "Node: " << (*root)->key << " Right: ";
		rbPrintTree(&((*root)->ptRight));
	}
	else if(isNil(*root))
	{
		cout << "NIL" << endl;
	}
	else
	{
		cout << "EMPTY" << endl;
	}

} 
void rbDelete(RBT* *root, RBT *pZ)
{
	RBT *pX;
	RBT *pY;

	if( isNil(pZ->ptLeft) || isNil(pZ->ptRight))
		pY = pZ;
	else
	{
		pY = treeSuccessor(pZ);
	}

	if(!isNil(pY->ptLeft))
		pX = pY->ptLeft;
	else
		pX = pY->ptRight;

	pX->ptParent = pY->ptParent;

	if(isNil(pY->ptParent))
		*root = pX;
	else if(pY == pY->ptParent->ptLeft)
	{
		pY->ptParent->ptLeft = pX;
	}
	else
		pY->ptParent->ptRight = pX;

	if(pY != pZ)
	{
		pZ->key = pY->key;
	}
	if(pY->color==BLACK)
		rbDeleteFixup(root,pX);
	delete pY;
}
void rbDeleteFixup(RBT* *root, RBT *pX)
{
	RBT *father,*brother,*node;
	node=pX;
	father=node->ptParent;
	
	while( node != (*root) && node->color == BLACK)
	{
		if(node == father->ptLeft)
		{
			brother = father->ptRight;
			if(brother->color == RED)
			{//case1
				brother->color = BLACK;
				father->color = RED;
				leftRotate(root,father);
				brother = father->ptRight;
			}
			if((isNil(brother)||brother->ptLeft->color == BLACK) &&(isNil(brother)|| brother->ptRight->color == BLACK))
			{//case2
				brother->color = RED;
				node= father;
				father=node->ptParent;
			}
			else {if(isNil(brother) || brother->ptRight->color == BLACK)
			{//case3
				
				brother->ptLeft->color = BLACK;
				brother->color = RED;
				rightRotate(root,brother);
				brother = father->ptRight;
			}
			//case4
			brother->color = father->color;
			father->color = BLACK;
			brother->ptRight->color = BLACK;
			leftRotate(root,father);
			node = *root;
			}}
		else
		{
			brother=father->ptLeft;
			if(brother->color==RED)
			{//case1
				brother->color=BLACK;
				father->color=RED;
				rightRotate(root,father);
				brother=father->ptLeft;
			}
			if((isNil(brother)||brother->ptRight->color==BLACK) && (isNil(brother)|| brother->ptLeft->color == BLACK))
			{//case2
				brother->color=RED;
				node=father;
				father=node->ptParent;
			}
			else{ if(isNil(brother) || brother->ptLeft->color==BLACK)
			{//case3
				
				brother->ptRight->color=BLACK;
				brother->color=RED;
				leftRotate(root,brother);
				brother=father->ptLeft;
			}
			//case4
			brother->color=father->color;
			father->color=BLACK;
			brother->ptLeft->color=BLACK;
			rightRotate(root,father);
			node=*root;
			}}
		
	}node->color=BLACK;
}

void insertRBNode(RBT ** root, int key)
{
	RBT * pZ = new RBT;
	pZ->key=key;
	rbInsert(root, pZ);
}
void deleteRBNode(RBT ** root, int key)
{
	RBT * pZ = treeSearch(root, key);
	rbDelete(root, pZ);
}
int main()
{

	int *A = new int[sizeof(int)*SIZE];
	RBT ** root = new RBT*[1];
	* root = new RBT();
	setNil(*root);

	//Random(A, MAX, SIZE);
	A[0]=1; A[1]=11; A[2]=12; A[3]=69; A[4]=4; 
	A[5]=14; A[6]=82; A[7]=50; A[8]=77; A[9]=3;

	for( int i = 0; i < SIZE; i ++)
	{
		cout << A[i] << " ";
	}
	cout << endl;


	for( int i = 0; i < SIZE; i ++)
	{
		RBT * pZ = new RBT;
		cout << endl << "Insert the element: " << A[i] << endl;
		pZ->key=A[i];
		rbInsert(root, pZ);
		rbPrintTree(root);
		//system("pause");
	}
	rbPrintTree(root);
	//system("pause");

	for( int i = 0 ; i < SIZE; i ++)
	{
	cout << "Delete: " << A[i] << endl;
	RBT * pZ = treeSearch(root, A[i]);
	rbDelete(root, pZ);
	rbPrintTree(root);
	//system("pause");
	}
	rbPrintTree(root);
	system("pause");


	/*int SIZE = 1000, STEP = 1000, LOOP = 100;
	int maxSIZE = SIZE + LOOP*STEP;

	while(SIZE < maxSIZE)
	{
		RBT ** root = new RBT*[1];
		int *A = new int[sizeof(int)*SIZE];
		* root = new RBT();
		setNil(*root);
		Random(A, MAX, SIZE);
	
		cout << SIZE << '\t';

		clock_t start, finish;
		start = clock();
		for( int i = 0 ; i < SIZE; i ++)
			insertRBNode(root, A[i]);
		finish = clock();
		cout << (finish - start) << '\t';
		start = clock();
		for( int i = 0 ; i < SIZE; i ++)
			deleteRBNode(root, A[i]);
		finish = clock();
		cout << (finish - start) << endl;
		SIZE += STEP;
	}
	system("pause");*/


}