// file rbtree.cpp
//created by alpha 2008.11.3

#include "../headers/rbtree.h"
#include "../headers/dot.h"
#include "../headers/control.h"
#include <ctime>
#include <iostream>
#include <sstream>
#include <stack>

using namespace std;

// constructor of rbtree class
rbtree::rbtree ()
{
	NIL=new rbtnode;
	NIL->color = BLACK;
	NIL->key = -1;
	NIL->lchild = NULL;
	NIL->rchild = NULL;
	NIL->father = NIL;
	NIL->size = 0;
	root = NIL;
	num = 0;
}

//init rbtree
bool rbtree::init()
{
	cout<<"Please input the size of tree : ";
	srand((int)time(0));
	int size;
	cin>>size;
	for (int i=0; i!=size; i++){
		int swap = rand();
		insert (swap);
	}

	return true;
}
//visit the rbtree "t" in inOrder
void rbtree::inOrder()
{
	inOrder(root);
	return;
}
void rbtree::inOrder(rbtnode *node) 
{
    if ( node != NIL)
    {
        if ( NIL != node->lchild )
		{
			if (node->lchild->key > node->key)
			{
                cerr<<"inorder walk false!\n";
				exit(-1);
            }
            inOrder(node->lchild);
        }
        print(node);
        if ( NIL != node->rchild )
        {
            if (node->rchild->key < node->key)
            {
                cout<<"inorder walk false\n";
				exit(-1);
            }
            inOrder(node->rchild);
        }
    }
}
void rbtree::preOrder()
{
	preOrder(root,0,0);
	return;
}
void rbtree::preOrder(rbtnode *node, int level, int flag)
{
	int n = level;
	while(n)
	{
		cout<<"    ";
		n--;	
	}
	level++;
	if (NIL != node)
	{
		cout<<"("<<node->key;
		if(RED == node->color)
			cout<<"R,\n";
		else
			cout<<"B,\n";
	}
	else
	{
		cout<<"NIL";
		if(flag)
			cout<<")\n";
		else
			cout<<",\n";
	}
	if (NULL != node->lchild)
	{
		preOrder(node->lchild,level,0);
	}
	if (NULL != node->rchild && NIL == node->rchild)
	{
		preOrder(node->rchild,level,1);
	}
	else if(NULL != node->rchild)
		preOrder(node->rchild,level,0);
	n = level;
	if(NIL != node&&NIL != node->rchild)
	{
		n = level-1;
		while(n)
		{
			cout<<"    ";
			n--;	
		}
		cout<<")\n";
	}
	level--;
}
//find key in rbtree, return a rbtnode to rbtnode
rbtnode* rbtree::find(int key)
{
    rbtnode *x;
    // find the node
    x = root;
    do
    {
        if ( key == x->key )
            break;
        if (key < x->key)
        {
            if (NIL != x->lchild)
                x = x->lchild;
            else
			{
				cout<<"There is no "<<key<<" in the tree\n";
				return NULL;
			}
        }
        else
        {
            if (NIL != x->rchild)
                x = x->rchild;
            else
			{
				cout<<"There is no "<<key<<" in the tree\n";
				return NULL;
			}
        }
    } while (NIL != x);
    return x;
}

// print the rbtree
void rbtree::print(rbtnode *node)
{
	string color[2] = { "BLACK", "RED" };
	cout<<"Key="<<node->key<<"    color="<<color[node->color];
	if (NIL != node->father)
		cout<<"    father="<<node->father->key;
    if (NIL != node->lchild)
		cout<<"    left="<<node->lchild->key;
    if (NIL != node->rchild)
		cout<<"    right="<<node->rchild->key;
    cout<<endl;
}
void rbtree::print()
{
	preOrder();
}
// insert a key
bool rbtree::insert()
{
	cout<<"Please input the key of the rbtnode you want to insert : ";
	rbtnode *z = new rbtnode;
	cin>>z->key;
	rbtnode *y = NIL;
	rbtnode *x = root;
	if (x == NIL){
		root = z;
		z->father = NIL;
		z->lchild = NIL;
		z->rchild = NIL;
		z->color = BLACK;
	}
	else
	{
		while ( x != NIL ){
			y = x;
			if ( z->key < x->key )
				x = x->lchild;
			else
				x = x->rchild;
		}
		if ( z->key < y->key )
			y->lchild = z;
		else 
			y->rchild = z;
		z->father = y;
		z->lchild = NIL;
		z->rchild = NIL;
		z->color = RED;
		insertFixup (z);
	}
	if(NIL != z)
	{
		z->size = z->lchild->size + z->rchild->size + 1;
	}
	return true;
}
bool rbtree::insert(int initkey)
{
	rbtnode *z = new rbtnode;
	z->key = initkey;
	rbtnode *y = NIL;
	rbtnode *x = root;
	if (x == NIL){
		root = z;
		z->father = NIL;
		z->lchild = NIL;
		z->rchild = NIL;
		z->color = BLACK;
	}
	else
	{
		while ( x != NIL ){
			y = x;
			if ( z->key < x->key )
				x = x->lchild;
			else
				x = x->rchild;
		}

		if ( z->key < y->key )
			y->lchild = z;
		else 
			y->rchild = z;
		z->father = y;
		z->lchild = NIL;
		z->rchild = NIL;
		z->color = RED;
		insertFixup (z);
	}
	num++;
	if(NIL != z)
	{
		z->size = z->lchild->size + z->rchild->size + 1;
	}
	if(controlInsert)
	{
		stringstream snum;
		snum<<num;
		stringstream ss;
		ss<<initkey;
		string name = "step"+snum.str()+"_insertkey_" + ss.str();
		toJpg(name);
	}
	return true;
}
// rbtree fixup
void rbtree::insertFixup(rbtnode *z)
{
    rbtnode *y;
    while (root != z && RED == z->father->color)        
    {
        if (z->father == z->father->father->lchild)        
        {
            y = z->father->father->rchild;                        
            if (NIL != y && RED == y->color)                
            {
                z->father->color = BLACK;                        
                y->color = BLACK;                                        
                z->father->father->color = BLACK;                
                z = z->father->father;                                
            }
            else                                                                        
            {
                if (z == z->father->rchild)                        
                {
                    z = z->father;
                    leftRotate ( z );
                }
                z->father->color = BLACK;                        
                z->father->father->color = RED;                
                rightRotate(z->father->father);
            }
        }
        else                                                                                
        {
            y = z->father->father->lchild;                        
            if (NIL != y && RED == y->color)                
            {
                z->father->color = BLACK;                        
                y->color = BLACK;                                        
                z->father->father->color = RED;                
                z = z->father->father;                                
            }               
            else                                                                        
            {
                if (z == z->father->lchild)                        
                {
                    z = z->father;
                    rightRotate(z);
                }
                z->father->color = BLACK;                        
                z->father->father->color = RED;                
                leftRotate(z->father->father);
            }
        }
    } 
    root->color = BLACK;
}

// left rotate
void rbtree::leftRotate(rbtnode *A) 
{       
    rbtnode *B;
    B = A->rchild;

    A->rchild  = B->lchild;
    if (NIL != B->lchild)
        B->lchild->father = A;
    B->father = A->father;
    if ( A == root )
    {
        root = B;
    }
    else if ( A == A->father->lchild)
    {
        A->father->lchild = B;
    }
    else
    {
        A->father->rchild = B;
    }
    B->lchild = A;
    A->father = B;
}

//right rotate
void rbtree::rightRotate(rbtnode *A)
{
    rbtnode *B;
    B = A->lchild;

    A->lchild = B->rchild;
    if (NIL != B->rchild)
        B->rchild->father = A;

    B->father = A->father;
    if (A == root)
    {
        root = B;
    }
    else if (A == A->father->lchild)
    {
        A->father->lchild = B;
    }
    else
    {
        A->father->rchild = B;
    }
    A->father = B;
    B->rchild  = A;
}

bool rbtree::delNode(int key)
{
    rbtnode *x, *y, *z, *x_father;    
    z = find(key);                   // find key
    if (NIL == z)
	{
		cout<<"delrbtnode fault, there is no key "<<key<<endl;
		return false;
	}
    y = z, x = NIL, x_father = NIL; 
    if (NIL == y->lchild)
    {