// implementation of RedBlackTree
// does not allow duplicate items
// wdg 2008
#include <iostream>
using namespace std;
#include "RedBlackTree.h"

//---------------------------------------------------------------------
// constructor creates an empty tree

    RedBlackTree::RedBlackTree( ) 
    {
    }

//======================================================================
//  SPECIFIC METHODS FOR RED-BLACK TREES
// adapted from Cormen, Leiserson and Rivest
//======================================================================
// rotate methods affecting node x and its right/left child y
void RedBlackTree::leftRotate(RBNode *x) 
{   
   RBNode *y = static_cast<RBNode*> (x->right);
   cout << "Rotating " << x->element << "&" << y->element << endl;
   x->right = y->left;
   if( y->left!=NULL )
      y->left->parent = x;
   y->parent = x->parent;
   if( x->parent==NULL )
      root=y;
   else if( x== x->parent->left )
      x->parent->left=y;
   else
      x->parent->right=y;
   y->left=x;
   x->parent=y;
  }         
//----------------------------------------------------------------------
void RedBlackTree::rightRotate(RBNode *x) 
{
   RBNode *y = static_cast<RBNode*> (x->left);
   cout<< "Rotating " << x->element << "&" << y->element << endl;
   x->left = y->right;
   if( y->right!=NULL)
      y->right->parent=x;
   y->parent = x->parent;
   if( x->parent==NULL )
      root=y;
   else if( x==x->parent->left )
      x->parent->left=y;
   else 
      x->parent->right=y;
   y->right=x;
   x->parent=y;
  }  
//----------------------------------------------------------------------
// returns the grandparent of a node
RBNode *RedBlackTree::grand(RBNode *v)
{
   if( v==root || v->parent==root)
      return NULL;
   else 
      return static_cast<RBNode*> (v->parent->parent);
}
//---------------------------------------------------------------------
// returns the uncle of a node: the sibling of the parent
RBNode *RedBlackTree::uncle(RBNode *v)
{
   if( v==root || v->parent==root )
      return NULL;
   else if( isLeftChild(v->parent) )
      return static_cast<RBNode*> (grand(v)->right);
   else
      return static_cast<RBNode*> (grand(v)->left );
}
//---------------------------------------------------------------------
// returns whether the node is the left child of its parent
bool RedBlackTree::isLeftChild(BSTNode *v)
{
   return (v!=root && v==v->parent->left);
}
//---------------------------------------------------------------------
// this uses bottom-up insertion
// add the node according to binary search tree, color it red
// if parent is black then done, else have red node with red child
// if uncle of lower node is red, then recolor and so move problem up tree
// if uncle black, then use a rotation or two and some recoloring to rectify

void RedBlackTree::insertItem(ItemType it)
{      
   RBNode *x = new RBNode(it);
   if( !BinarySearchTree::insertItem(x) )
      return;
   cout << "Inserting " << it << endl;
   x->color = RED;
   while( x!=root && (static_cast<RBNode*>(x->parent))->color==RED) {
        RBNode *y = uncle(x);
        if( y!=NULL && y->color==RED) {   // move red-red problem up tree
            static_cast<RBNode*>(x->parent)->color=BLACK;
            y->color=BLACK;
            grand(x)->color=RED;
            x=grand(x);
        }
        else {     // uncle is BLACk; fix with rotation or two
           bool parentWasLeftChild = isLeftChild(x->parent); 
           bool wasLeftChild = isLeftChild(x);
           // if you zigzag from grandparent to node, need double rotation
           // this is the first rotation
           if( parentWasLeftChild && !wasLeftChild ) {
               x= static_cast<RBNode*>(x->parent);
               leftRotate(x);
           }
           else if( !parentWasLeftChild && wasLeftChild ) {
               x= static_cast<RBNode*>(x->parent);
               rightRotate(x);
           }
           // in any event you finish off with a rotation
           static_cast<RBNode*>(x->parent)->color = BLACK;
           grand(x)->color = RED;
           if( parentWasLeftChild )
              rightRotate(grand(x));
           else 
              leftRotate(grand(x));
        }//else
     }//while
    static_cast<RBNode*>(root)->color=BLACK;           
  }