// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): SUNY Stony Brook students

// This software is copyrighted by the DIMACS Center at Rutgers, The State
// University of New Jersey.  IT IS PROVIDED AS IS, AND THE AUTHORS, DIMACS, AND
// RUTGERS, THE STATE UNIVERSITY OF NEW JERSEY  DISCLAIM
// ALL LIABILITY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
// DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY
// DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.

// THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT.  THIS SOFTWARE
// IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE
// NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
// MODIFICATIONS.

// The authors hereby grant permission to use, copy, modify, distribute,
// and license this software and its documentation for any purpose, provided
// that existing copyright notices are retained in all copies and that this
// notice is included verbatim in any distributions. No written agreement,
// license, or royalty fee is required for any of the authorized uses.
// Modifications to this software may be copyrighted by their authors
// and need not follow the licensing terms described here, provided that
// the new terms are clearly indicated on the first page of each file where
// they apply.

// Last File Update: 31-Jul-1996
// 



/*****************************public routines******************************/
//
//constructor.
//
template <class Key, class Item>
RedBlackTree<Key, Item>::RedBlackTree()
{
  _count = 0;
  NIL = new RedBlackTreeNode<Key,Item>;
  _root = NIL; 
}
//
// Destructor.
//
template <class Key, class Item>
RedBlackTree<Key, Item>::~RedBlackTree()
{
  clear();
  delete NIL;
}

//
//In this routine we call treeInsert first to insert a new node
//into the tree as if it were an ordinary binary search tree, and
//then we color node to red. To gurantee that red-black properties
//are preserved, we then fix up the modified tree by recoloring 
//nodes and performing rotations. There are six cases.
//
template <class Key, class Item>
ContainerNode*
RedBlackTree<Key, Item>::insert(Key passed_key, Item passed_item)
{
   RedBlackTreeNode<Key,Item>* node;
   node = new RedBlackTreeNode<Key,Item>;
   if (!node) {
       error("RedBlackTree<Key, Item>::insert():
              free store exhausted.");
       return(0);
    }

    _count++;             // construct a new node.
    node->key = passed_key;
    node->item = passed_item;
    node->left = NIL;
    node->right= NIL;
    node->parent = NIL;
    
    treeInsert(node);    // insert as if it were an ordinary binary tree. 
    //The only red-black property that might be violated here is :
    //a red node can not be a child of a red parent. Since the 
    //new node was colored to RED , following loop fixs up this
    //violation if it happens. 
    RedBlackTreeNode<Key,Item> *x, *y;
    x = node;
    x->color = _RED;
    while ( (x != _root) && (x->parent->color == _RED) ) {
       //The goal of this loop is to move the one violation up
       //the tree while maintaining property:every simple path
       //from a node to decendant leaf contains the same number 
       //of black nodes, as an invariant. 
       //There are six cases to consider in this loop, but three
       //of them are symmetric to the other three, depending
       //on whether x's parent is a left child or a right child
       //of x's grandparent (x->parent->parent). There is an
       //important assumption that the root of the tree is
       //black, so that if x's parent is red, x's grandparent
       //is non-NIL(exits).
       if (x->parent == x->parent->parent->left) {  //cases 1-3
          y = x->parent->parent->right; //uncle of x
          if (y->color == _RED) {                    //case1
             x->parent->color = _BLACK;
             y->color = _BLACK;
             x->parent->parent->color = _RED;  
             x = x->parent->parent;
          }
          else {                                   //cases 2-3
             if (x == x->parent->right) {          //case2
                x = x->parent;
                leftRotate(x);
             }
             x->parent->color = _BLACK;            //case3
             x->parent->parent->color = _RED; 
             rightRotate(x->parent->parent);
          }
       }    //end of cases1-3.
       else {                                     //cases4-6
          y = x->parent->parent->left;  
          if (y->color == _RED) {                  //case4
             x->parent->color = _BLACK; 
             y->color = _BLACK;
             x->parent->parent->color = _RED;  
             x = x->parent->parent;
          }
          else {
             if (x == x->parent->left) {          //case5
                x = x->parent;
                rightRotate(x);
             }
             x->parent->color = _BLACK;            //case6
             x->parent->parent->color = _RED;
             leftRotate(x->parent->parent);
          }

       } //end of else : cases 4-6
   }  //end of while
    
   _root->color = _BLACK;         
}

//
//search a key in the tree.
//
template <class Key, class Item>
RedBlackTreeNode<Key,Item>*
RedBlackTree<Key,Item>::search(const Key& passed_key) const
{  
   if (_root == NIL) 
      return (0);
   if ( _root->key == passed_key) 
      return _root;
   RedBlackTreeNode<Key,Item>* x = _root;
   while ( (x != NIL) && (x->key != passed_key) ) {
      if (passed_key < x->key)
         x = x->left;
      else
         x = x->right;   
   }
   if (x == NIL) {
      warning("RedBlackTree<Key,Item>::search():
               key is not found.");
      return (0);
   }
   return x;
}

//
//search a Item in the tree. 
// 
template <class Key, class Item> 
RedBlackTreeNode<Key,Item>*
RedBlackTree<Key,Item>::searchItem(const Item& passed_item) const
{
   if (_root == NIL)
      return (0);
   if ( ElementOps<Item>::compareItems(_root->item,passed_item)==0) 
      return _root;
   RedBlackTreeNode<Key,Item>* x = treeSearchItem(_root,passed_item);
   if (!x) 
      warning("RedBlackTree<Key,Item>::searchItem:
               item is not found.");
   return x;
}

//
//Query on membership.
//
template <class Key, class Item>
Bool
RedBlackTree<Key, Item>::memberQ(const Item& e) const
{
   if (searchItem(e))
      return TRUE;  
   else  
      return FALSE;
}

//
//Find the successor for a node in the tree.
//
template <class Key, class Item> 
RedBlackTreeNode<Key,Item>*
RedBlackTree<Key,Item>::successor(RedBlackTreeNode<Key,Item>* x) const
{
   if ( (!x) || (x == NIL)) {
      error("RedBlackTree<Key,Item>::successor():
             NULL pointer.");
      return (0);
   }
 
   if (x->right != NIL) 
      return treeMinimum(x->right);
   RedBlackTreeNode<Key,Item>* y = x->parent;
   while ( (y != NIL) && (x == y->right) ) {
      x = y;
      y = y->parent;
   }
   if (y == NIL) { 
      warning("RedBlackTree<Key,Item>::successor():
               No successor is found.");   
      return (0);
   }
   return y;
}  

//
// find the predecessor for a node in the tree.
//
template <class Key, class Item>
RedBlackTreeNode<Key,Item>*
RedBlackTree<Key,Item>::predecessor(RedBlackTreeNode<Key,Item>* x) const{
   if ( (!x) || (x == NIL) ) {
      error("RedBlackTree<Key,Item>::predecessor():
             NULL pointer.");
      return (0);
   }
   if (x->left != NIL)
      return treeMaximum(x->left);
   RedBlackTreeNode<Key,Item>* y = x->parent;
   while ( (y != NIL) && (x == y->left) ) {
      x = y;
      y = y->parent;
   }
   if (y == NIL) {
      warning("RedBlackTree<Key,Item>::predecessor():
               No predecessor is found.");
      return (0);
   }
   return y;

}


//
//
//
template <class Key, class Item>
void
RedBlackTree<Key, Item>::remove(RedBlackTreeNode<Key,Item>* passed_node)
{
  if ( (!passed_node) ||(passed_node == NIL) ) {
     warning("RedBlackTree<Key,Item>::remove()
               : NULL pointer.");
     return;
  }

  RedBlackTreeNode<Key,Item> *y, *x;
  if ( (passed_node->left == NIL) || (passed_node->right == NIL) )
     y = passed_node;
  else
     y = successor(passed_node);
  if ( (y->left) && (y->left != NIL) )
     x = y->left;
  else
     x = y->right;
  x->parent = y->parent;
  if (y->parent == NIL)
     _root = x;
  else if (y == y->parent->left)
     y->parent->left = x;
  else
     y->parent->right = x;
  if (y != passed_node) {
     passed_node->key = y->key;
     passed_node->item = y->item;
  } 
  if (y->color == _BLACK)
     removeFixup(x);
  delete y;
  _count--;
}

//
// Remove an item from the tree.
//
template <class Key, class Item>
void
RedBlackTree<Key,Item>::remove(Item passed_item)
{
   RedBlackTreeNode<Key,Item> *x;
   x = searchItem(passed_item);
   remove(x);
}

//
// Remove all the node in the tree.
//
template <class Key, class Item>
void 
RedBlackTree<Key,Item>::clear()
{
  treeKill(_root);
  _root = NIL;
}

//
//Find the minimum key in the tree.
//
template <class Key, class Item> 
ContainerNode*
RedBlackTree<Key,Item>::minimum() const
{
  RedBlackTreeNode<Key,Item> *x;
  x = treeMinimum(_root);
  return (ContainerNode *) x;
}
 
//
//Find the maximum key in the tree.
//
template <class Key, class Item>
ContainerNode*
RedBlackTree<Key,Item>::maximum() const
{ 
   RedBlackTreeNode<Key,Item> *x;
   x = treeMaximum(_root);
   return (ContainerNode *) x;
}

//
//Delete the minimum key in the tree
//
template <class Key, class Item> 
Item
RedBlackTree<Key,Item>::extractMin()
{
   if (_root == NIL) {
      error("RedBlackTree<Key,Item>::extractMin():
             Empty Tree.");
      return (0);
   }
   RedBlackTreeNode<Key,Item> *x;
   x = (RedBlackTreeNode<Key,Item> *) minimum() ;
   Item item = x->item;
   remove(x);
   return item;
}
 
//
//Delete the maximum key in the tree.
//
template <class Key, class Item>
Item
RedBlackTree<Key,Item>::extractMax()
{
   if (_root == NIL) { 
      error("RedBlackTree<Key,Item>::extractMax(): 
             Empty Tree."); 
      return (0); 
   }  
   RedBlackTreeNode<Key,Item> *x;
   x = (RedBlackTreeNode<Key,Item> *) maximum();
   Item item = x->item;
   remove(x);
   return item;
}

 

//
//Print out the tree in inorderwalk.
//
template <class Key, class Item>
void 
RedBlackTree<Key,Item>::inorderWalk(ostream& os) const
{
   if (_root == NIL) { 
     os << "<Empty Red Black Tree>" << endl;
     return;
   }
   os << "<";
   inorderTreeWalk(os, _root);
   os << ">";
   os << endl; 
}
 
//
//Print out the tree in preorder 
//
template <class Key, class Item> 
void 
RedBlackTree<Key,Item>::preorderWalk(ostream& os) const
{
   if (_root == NIL) {  
     os << "<Empty Red Black Tree>" << endl;
     return;
   }
   os << "<";  
   preorderTreeWalk(os, _root); 
   os << ">";  
   os << endl; 
}
//
//print out the tree in postorder.
//
template <class Key, class Item>
void
RedBlackTree<Key,Item>::postorderWalk(ostream& os) const
{
   if (_root == NIL) {  
      os << "<Empty Red Black Tree>" << endl;
      return;
   }
   os << "<";
   postorderTreeWalk(os, _root);
   os << ">";
   os << endl;
}
 
//
//print out all the items in the tree.
//
template <class Key, class Item>
ostream&
RedBlackTree<Key,Item>::print(ostream& os)
{
   if (_root == NIL) {
      os << "(Empty Red Black Tree)" << endl;
      return os;
   }
   os << "(";
   Iterator<Item> get_next(this);
   Item i;
   while (get_next(i))
       os << i << " ";
   os << ")" <<endl ;
   return os;
}
//
// Display the tree in human-readable way.
//
template <class Key, class Item>
ostream&
RedBlackTree<Key,Item>::display(ostream& os)  const
{
   if (_root == NIL) {
      os << "<Empty Red Black Tree>" << endl;
      return os;
   }
   //char order[20];
   //os << "What kind of orders you want to use?
   //          (inorder, postorder, preorder)" << endl;
   //cin >> order;
   //if (strcmp(order, "inorder") == 0) {

      inorderWalk(os);

   //   return os;
   //}
   //else if (strcmp(order, "postorder") == 0) {
   //   postorderWalk(os);
   //   return os;
   //}
   //else if (strcmp(order, "preorder") == 0) {
   //   preorderWalk(os);
   //   return os;
   //}
   //else {
   //   display(os);
   //   return os;
   //}

   return os;
}
 
//
// Randomly permutate the all the key in the tree, then rebuild
// it, for testing.
//
template <class Key, class Item>
void
RedBlackTree<Key,Item>::scramble()
{
   if (_count <= 1)
      return;
   int i, j;
   RedBlackTreeNode<Key,Item>** tree;
   tree = new RedBlackTreeNode<Key,Item>*[_count + 1];
   if (!tree) {
      error("RedBlackTree<Key,Item>::scramble():
             free store is exhausted.");
      return; 
   }
   RedBlackTreeNode<Key,Item>* tmp;
   for (i = 1; i <= _count; i ++) {
       tree[i] = new RedBlackTreeNode<Key,Item>;
       tmp =  getNode(i);
       tree[i]->key = tmp->key;
       tree[i]->item = tmp->item;
   }
 
   int count = _count;
   clear();
 
   // generate a random permutation on tree[].
   for(i = count; i >= 1; i--) {
       j = (int)Link_randomLong() % i + 1 ; //generate a random number in [1,i)
       tmp = tree[i];
       tree[i] = tree[j]; //swap tree[i] with tree[j].
       tree[j] = tmp;
    }
    
    // rebuild the tree from the permutation
    for (i = 1; i <= count; i++) {
        insert(tree[i]->key,tree[i]->item);
        delete tree[i];
    }
    delete [] tree;
}

//
// Change a key in the tree.
//
template <class Key, class Item>
void 
RedBlackTree<Key,Item>::changeKey(RedBlackTreeNode<Key,Item>* node,
                                      Key k)
{
  if (!node) {   
    error("RedBlackTree<Key,Item>::changeKey() : NUll pointer.");
    return;   
  }
  if ( k == node->key) {
     warning("RedBlackTree<Key,Item>::changeKey() : key is not changed.");
     return;  
  }
  Key tmpk;
  Item tmpi;
  RedBlackTreeNode<Key,Item> *x, *predx, *succx;
 
  if ( k < node->key) {
     node->key = k;
     x = node;
     predx = predecessor(x);
     while ( (predx) && (predx->key > k) ) {
       tmpk = predx->key;
       tmpi = predx->item;
       predx->key = x->key;
       predx->item = x->item;
       x->key = tmpk;
       x->item = tmpi;
       x = predx;
       predx = predecessor(x);
     }  
  }     
  else {
  //if ( k > node->key) {
     node->key = k;
     x = node;
     succx = successor(x);
     while ( (succx) && (succx->key < k) ) {
       tmpk = succx->key;
       tmpi = succx->item;
       succx->key = x->key;
       succx->item = x->item;
       x->key = tmpk;
       x->item = tmpi;
       x = succx;
       succx = successor(x);
     }   
  }     
}

//
//Merge another tree into cureent tree and destory the tree merged.
//
template <class Key, class Item>
void
RedBlackTree<Key,Item>::merge(RedBlackTree<Key,Item> &T)
{
   int Tsize = T.size();
   if (!Tsize)
      return;
   RedBlackTreeNode<Key,Item> *tmp;
   for (int i = 1; i <= Tsize; i++) {
      tmp = T.getNode(i);
      insert(tmp->key, tmp->item);
   }    
   T.clear();
}
   
//
//Get ith node in the tree.
//
template <class Key, class Item>
RedBlackTreeNode<Key,Item>*
RedBlackTree<Key,Item>::getNode(int index) const
{
   RedBlackTreeNode<Key,Item> *node = 0;
   int j = index;
   treeIterate(_root, node, j);
   return node;
}

//
//Iterate the items in the tree.
//
template <class Key, class Item> 
int
RedBlackTree<Key,Item>::iterate(Iterator<Item>& iterator, Item& item) const
{
   if (_count <= 0)
       return 0;  
   if (iterator._index > _count || iterator._index < 0)
       return 0; 
   else {
       iterator._index++;
       RedBlackTreeNode<Key,Item> *node = 0;
       int index = iterator._index;
       treeIterate(_root, node, index);
       if (node) {
           item = node->item;
           return 1;
       } else
           return 0;
   }        
 
}
//
// operator = , copy a tree to another tree.
//
template <class Key, class Item>
RedBlackTree<Key,Item>&
RedBlackTree<Key,Item>::operator=(const RedBlackTree<Key, Item>& tree)
{
  if (&tree == this)
      return *this;
   clear();
   int size = tree.size();
   if (!size)
      return *this;

   RedBlackTreeNode<Key,Item> *tmp, *node;
   for (int i = 1; i <= size; i++) {
     node = new RedBlackTreeNode<Key,Item>;
     tmp = tree.getNode(i);
     insert(tmp->key, tmp->item);
   }
   return *this;

}

//
// Calculate the tree's height.
//
template <class Key, class Item>
int 
RedBlackTree<Key,Item>::height() const
{
  return treeHeight(_root); 
}

//
// Calculate the tree's black height. 
// 
template <class Key, class Item> 
int 
RedBlackTree<Key,Item>::bheight() const 
{
   return treeBHeight(_root);
}
/*****************************private routines******************************/

//
//Left rotation is a local operation in search tree that preserve
//the inorder key ordering. When we do a left rotation on a node x,
//we assume that its right child is non-NIL. Left rotation "pivot"
//around the link from x to y . It makes y the new root of the subtree,
//with x as y's left child and y's(original) left child as x's right
//child.
//
template <class Key, class Item>
void
RedBlackTree<Key, Item>::leftRotate(RedBlackTreeNode<Key,Item>* x)
{ 
   if ((!x) || (x == NIL)) {
      error("RedBlackTree<Key, Item>::leftRotate():
             NULL pointer.");
      return;
   }
   RedBlackTreeNode<Key,Item> *y  = x->right;   //set y.
   if ( (!y) ||(y == NIL) ){
      error("RedBlackTree<Key, Item>::leftRotate():
             error in left rotation.");
      return;
   }

   x->right = y->left;  //turn y's left subtree into x's right subtree.
   if ( (y->left) && (y->left != NIL) )
      y->left->parent = x;

   y->parent = x->parent; //Link x's parent to y.
   if (x->parent == NIL)
      _root = y;
   else if (x == x->parent->left)  
      x->parent->left = y;
   else 
      x->parent->right = y;


   y->left = x;    //Link x as y's left child.
   x->parent = y;
} 
    
//
//Right rotation is a local operation in search tree that preserve 
//the inorder key ordering. It is symmetric to left rotation.
//When we do a tight rotation on a node x, we assume that its left
//child is non-NIL. Right rotation "pivot" around the link from x to y .
//It makes y the new root of the subtree, with x as y's right child
//and y's(original) right child as x's left child.
//   
template <class Key, class Item>
void
RedBlackTree<Key, Item>::rightRotate(RedBlackTreeNode<Key,Item>* x)
{
   if ((!x) || (x == NIL)) { 
      error("RedBlackTree<Key, Item>::rightRotate(): 
             NULL pointer."); 
      return;
   } 
   RedBlackTreeNode<Key,Item> *y = x->left;  //set y.
   if ((!y) || (y == NIL)){ 
      error("RedBlackTree<Key, Item>::rightRotate():
             error in right rotation."); 
      return;  
   } 
   
   x->left = y->right; // turn y's right subtree into x's left subtree.
   if ( (y->right) && (y->right != NIL) )
      y->right->parent = x;

   y->parent = x->parent; //Link x's parent to y
   if (x->parent == NIL)
      _root = y;
   else if (x == x->parent->left) 
      x->parent->left = y;  
   else  
      x->parent->right = y;

   y->right = x;  //Link x as y's right child.
   x->parent = y;
}

//
//This routine is similar to insertion in BinarySearchTree. 
//We do not need to concern the red-black properties here.
//
template <class Key, class Item>
void
RedBlackTree<Key, Item>::treeInsert(RedBlackTreeNode<Key,Item>* node)
{
   if ( (!node) || (node == NIL) )
      return;
   if (_root == NIL) {
      _root = node;
      return;
   }
   RedBlackTreeNode<Key,Item> *x, *y;
   y = NIL;
   x = _root;
   while ( x != NIL ) {
      y = x;
      if ( node->key < x->key)
         x = x->left;
      else
         x = x->right;
   }
   node->parent = y;

   if (node->key < y->key)
      y->left = node;
   else
      y->right = node;
} 
//
//This routine restores the Red-Black tree properties to the tree.
//If the node y which is deleted in remove() is black, its removal 
//causes any path that previously contained node y to have one fewer
//black node, thus Red-Black property:Every simple path from a node
//to a descendant leaf contains the same number of black nodes, is
//violated by any ancestor of y in the tree. We can correct this 
//problem by thinking of node x (a child of y or leaf NIL) as having
//"extra" black. This routine just attempts to move the extra black
//up the tree until:(1) x points to a red node, in which case we color 
//the node black. (2) x points to the root, in which case the extra 
//black can be simply removed.(3) suitable rotations and colorings
//can be performed. There are eight cases considered here, but 
//four of them are symmetric to the other four, depending x is
// a left child or right child of its parent.
//
template <class Key, class Item>
void
RedBlackTree<Key, Item>::removeFixup(RedBlackTreeNode<Key,Item>* x)
{
   while ( (x != _root) && (x->color == _BLACK) ) { 
      //Within the while loop, x always points to a nonroot 
      //block node while has the extra black. We maintain a 
      //pointer w to the sibling of x. Since node x is doubly
      //black, node w can not be NIL, otherwise the number of
      //blacks on the path from x->parent to the NIL leaf w 
      //would be smaller than the number on the path from x->parent
      //to x.
      if (x == x->parent->left)  {    //cases1-4
         RedBlackTreeNode<Key,Item>* w = x->parent->right;
         if (w->color == _RED) {       //case1
            w->color = _BLACK;
            x->parent->color = _RED;
            leftRotate(x->parent);
            w = x->parent->right;
         } 
         
         if ( (w->left->color == _BLACK) 
                  && (w->right->color == _BLACK) ) {   //case2
            w->color = _RED;
            x = x->parent;
         }
         else  {                                //case3-4
            if ( w->right->color == _BLACK) {    //case3
               w->left->color = _BLACK;
               w->color = _RED;
               rightRotate(w);
               w = x->parent->right;
            }
            w->color = x->parent->color;        //case4 
            x->parent->color = _BLACK;
            w->right->color = _BLACK;
            leftRotate(x->parent);
            x = _root;
         } 
      }                  //end of if  cases1-4
 
      else  {                                 //cases5-8  
         RedBlackTreeNode<Key,Item>* w = x->parent->left;
         if (w->color == _RED) {               //case5
            w->color = _BLACK; 
            x->parent->color = _RED; 
            rightRotate(x->parent);
            w = x->parent->left;
         }
         
         if ( (w->right->color == _BLACK) 
                  && (w->left->color == _BLACK) ) {   //case6
            w->color = _RED; 
            x = x->parent; 
         }   
         else  {                                //case7-8
            if ( w->left->color == _BLACK) {    //case7 
               w->right->color = _BLACK; 
               w->color = _RED;
               leftRotate(w); 
               w = x->parent->left; 
            } 
            w->color = x->parent->color;        //case4  
            x->parent->color = _BLACK;  
            w->left->color = _BLACK; 
            rightRotate(x->parent); 
            x = _root; 
         } 
      }            //end of else    cases5-8 
   }      //end of while loop
  
   x->color = _BLACK;
}

//
//Find the minimum in the subtree rooted at x.
//
template <class Key, class Item> 
RedBlackTreeNode<Key,Item>*
RedBlackTree<Key,Item>::treeMinimum(RedBlackTreeNode<Key,Item>* y) const
{
  if (!y || (y == NIL))
     return (0); 
  RedBlackTreeNode<Key,Item> *x = y; 
  while (x->left != NIL)
     x = x->left;
  return x;
}
 
//
// Find the maximum in the subtree rooted at x.
//
template <class Key, class Item>
RedBlackTreeNode<Key,Item>* 
RedBlackTree<Key,Item>::treeMaximum(RedBlackTreeNode<Key,Item>* y) const
{
  if ( (y == NIL) || !y)
     return (0);
  RedBlackTreeNode<Key,Item> *x = y;
  while (x->right != NIL)
     x = x->right;
  return x;
}

//
//Search for a key in the subtree rooted on x. 
// 
template <class Key, class Item> 
RedBlackTreeNode<Key,Item>*  
RedBlackTree<Key,Item>::treeSearch(RedBlackTreeNode<Key,Item>* x,
                                       const Key& k) const
{
  if ( (!x) || (k == x->key) )
     return x;
  if (x == NIL)   
     return (0);
  if ( k < x->key)
     return treeSearch(x->left, k);
  else   
     return treeSearch(x->right, k);
}
 
//
// Search for an item in the subtree rooted on x.
//
template <class Key, class Item> 
RedBlackTreeNode<Key,Item>* 
RedBlackTree<Key,Item>::treeSearchItem(RedBlackTreeNode<Key,Item>* x,
                                           const Item& item) const
{                                             
  if ( (!x) || (ElementOps<Item>::compareItems(item, x->item)==0) )
     return x;
  if (x == NIL)  
     return (0);
  RedBlackTreeNode<Key,Item>* node;
  node = treeSearchItem(x->left, item);
  if (node && (node != NIL))
     return node;
  else   
     return treeSearchItem(x->right, item);
}

//
// Delete the subtree rooted at x.
//
template <class Key, class Item> 
void
RedBlackTree<Key,Item>::treeKill(RedBlackTreeNode<Key,Item>* x)
{
   if ( (!x) || (x == NIL) )
      return;
   treeKill(x->left);
   treeKill(x->right);
   delete x;
   _count--;
}

//
// print out the subtree rooted at x in inorder walk
//
template <class Key, class Item> 
void
RedBlackTree<Key,Item>::inorderTreeWalk(ostream& os,
				RedBlackTreeNode<Key,Item>* x) const
{
   if (x && (x != NIL)) {
      inorderTreeWalk(os, x->left);  
      os << "(";
      os << x->key;
      os << ",";  
      ElementOps<Item>::displayItem(os, x->item);
      os << ")";   
      inorderTreeWalk(os, x->right); 
   }
}

//
//print out the subtree rooted at x in preorder walk. 
//
template <class Key, class Item> 
void
RedBlackTree<Key,Item>::preorderTreeWalk(ostream& os,
				RedBlackTreeNode<Key,Item>* x) const
{
   if (x && (x != NIL)) { 
      os << "("; 
      os << x->key;
      os << ","; 
      ElementOps<Item>::displayItem(os, x->item);
      os << ")";
      preorderTreeWalk(os, x->left);  
      preorderTreeWalk(os, x->right);
   }
}
 
//
// print out the subtree rooted at x in postorder walk.
//
template <class Key, class Item> 
void
RedBlackTree<Key,Item>::postorderTreeWalk(ostream& os,
				RedBlackTreeNode<Key,Item>* x) const
{
   if (x && (x != NIL)) {
      postorderTreeWalk(os, x->left);
      postorderTreeWalk(os, x->right);
      os << "(";  
      os << x->key; 
      os << ",";    
      ElementOps<Item>::displayItem(os, x->item);
      os << ")";
   }
}

//
// Iterate ith node in the subtree rooted at x.
//
template <class Key, class Item>
void
RedBlackTree<Key,Item>::treeIterate(RedBlackTreeNode<Key,Item>* x,
                                    RedBlackTreeNode<Key,Item>*& node,
                                    int& index) const
{
   if ( index <= 0) 
      return;
   if (x && (x != NIL)) {
      treeIterate(x->left, node, index);
      index--;
      if (!index) {
         node = x;
         return; 
      }
      treeIterate(x->right, node, index);
   }
}

//
// Calculate the height of subtree rooted on x.
//
template <class Key, class Item>
int
RedBlackTree<Key,Item>::treeHeight(RedBlackTreeNode<Key,Item>* x) const
{
   if (x == NIL)
      return -1;
   int lefth = treeHeight(x->left);
   int righth = treeHeight(x->right); 
  
   if (lefth > righth)
      return 1 + lefth;
   else
      return 1 + righth;
}

//
// Calculate the black height of subtree rooted on x. 
// 
template <class Key, class Item> 
int 
RedBlackTree<Key,Item>::treeBHeight(RedBlackTreeNode<Key,Item>* x) const 
{
   if (x == NIL)
      return 0;
   int lefth = treeBHeight(x->left);
   int righth = treeBHeight(x->right);

   if (x->color == _RED)  {
      if (lefth > righth)
         return 1 + lefth;
      else  
         return 1 + righth;
   }
   else if ( (x->left->color == _BLACK) || (lefth > righth) )
      return 1 + lefth;
   else if ( (x->right->color == _BLACK) || (lefth < righth) ) 
      return 1 + righth;
   else if (lefth > righth)
      return lefth;
   else
      return righth;
 
}