text: #include "red_black_tree.h"
  #include <assert.h>
  
  /***********************************************************************/
  /*  FUNCTION:  RBTreeCreate */
  /**/
  /*  INPUTS:  All the inputs are names of functions.  CompFunc takes two */
  /*  void pointers to keys and returns 1 if the first arguement is */
  /*  "greater than" the second.   DestFunc takes a pointer to a key and */
  /*  destroys it in the appropriate manner when the node containing that */
  /*  key is deleted.  InfoDestFunc is similiar to DestFunc except it */
  /*  recieves a pointer to the info of a node and destroys it. */
  /*  PrintFunc recieves a pointer to the key of a node and prints it. */
  /*  PrintInfo recieves a pointer to the info of a node and prints it. */
  /*  If RBTreePrint is never called the print functions don't have to be */
  /*  defined and NullFunction can be used.  */
  /**/
  /*  OUTPUT:  This function returns a pointer to the newly created */
  /*  red-black tree. */
  /**/
  /*  Modifies Input: none */
  /***********************************************************************/
  
  rb_red_blk_tree* RBTreeCreate( int (*CompFunc) (const void*,const void*),
  			      void (*DestFunc) (void*),
  			      void (*InfoDestFunc) (void*),
  			      void (*PrintFunc) (const void*),
  			      void (*PrintInfo)(void*)) {
    rb_red_blk_tree* newTree;
    rb_red_blk_node* temp;
  
    newTree=(rb_red_blk_tree*) SafeMalloc(sizeof(rb_red_blk_tree));
    newTree->Compare=  CompFunc;
    newTree->DestroyKey= DestFunc;
    newTree->PrintKey= PrintFunc;
    newTree->PrintInfo= PrintInfo;
    newTree->DestroyInfo= InfoDestFunc;
  
    /*  see the comment in the rb_red_blk_tree structure in red_black_tree.h */
    /*  for information on nil and root */
    temp=newTree->nil= (rb_red_blk_node*) SafeMalloc(sizeof(rb_red_blk_node));
    temp->parent=temp->left=temp->right=temp;
    temp->red=0;
    temp->key=0;
    temp=newTree->root= (rb_red_blk_node*) SafeMalloc(sizeof(rb_red_blk_node));
    temp->parent=temp->left=temp->right=newTree->nil;
    temp->key=0;
    temp->red=0;
    return(newTree);
  }
  
  /***********************************************************************/
  /*  FUNCTION:  LeftRotate */
  /**/
  /*  INPUTS:  This takes a tree so that it can access the appropriate */
  /*           root and nil pointers, and the node to rotate on. */
  /**/
  /*  OUTPUT:  None */
  /**/
  /*  Modifies Input: tree, x */
  /**/
  /*  EFFECTS:  Rotates as described in _Introduction_To_Algorithms by */
  /*            Cormen, Leiserson, Rivest (Chapter 14).  Basically this */
  /*            makes the parent of x be to the left of x, x the parent of */
  /*            its parent before the rotation and fixes other pointers */
  /*            accordingly. */
  /***********************************************************************/
  
  void LeftRotate(rb_red_blk_tree* tree, rb_red_blk_node* x) {
    rb_red_blk_node* y;
    rb_red_blk_node* nil=tree->nil;
  
    /*  I originally wrote this function to use the sentinel for */
    /*  nil to avoid checking for nil.  However this introduces a */
    /*  very subtle bug because sometimes this function modifies */
    /*  the parent pointer of nil.  This can be a problem if a */
    /*  function which calls LeftRotate also uses the nil sentinel */
    /*  and expects the nil sentinel's parent pointer to be unchanged */
    /*  after calling this function.  For example, when RBDeleteFixUP */
    /*  calls LeftRotate it expects the parent pointer of nil to be */
    /*  unchanged. */
  
    y=x->right;
    x->right=y->left;
  
    if (y->left != nil) y->left->parent=x; /* used to use sentinel here */
    /* and do an unconditional assignment instead of testing for nil */
    
    y->parent=x->parent;   
  
    /* instead of checking if x->parent is the root as in the book, we */
    /* count on the root sentinel to implicitly take care of this case */
    if( x == x->parent->left) {
      x->parent->left=y;
    } else {
      x->parent->right=y;
    }
    y->left=x;
    x->parent=y;
  
  #ifdef DEBUG_ASSERT
    Assert(!tree->nil->red,"nil not red in LeftRotate");
  #endif
  }
  
  
  /***********************************************************************/
  /*  FUNCTION:  RightRotate */
  /**/
  /*  INPUTS:  This takes a tree so that it can access the appropriate */
  /*           root and nil pointers, and the node to rotate on. */
  /**/
  /*  OUTPUT:  None */
  /**/
  /*  Modifies Input?: tree, y */
  /**/
  /*  EFFECTS:  Rotates as described in _Introduction_To_Algorithms by */
  /*            Cormen, Leiserson, Rivest (Chapter 14).  Basically this */
  /*            makes the parent of x be to the left of x, x the parent of */
  /*            its parent before the rotation and fixes other pointers */
  /*            accordingly. */
  /***********************************************************************/
  
  void RightRotate(rb_red_blk_tree* tree, rb_red_blk_node* y) {
    rb_red_blk_node* x;
    rb_red_blk_node* nil=tree->nil;
  
    /*  I originally wrote this function to use the sentinel for */
    /*  nil to avoid checking for nil.  However this introduces a */
    /*  very subtle bug because sometimes this function modifies */
    /*  the parent pointer of nil.  This can be a problem if a */
    /*  function which calls LeftRotate also uses the nil sentinel */
    /*  and expects the nil sentinel's parent pointer to be unchanged */
    /*  after calling this function.  For example, when RBDeleteFixUP */
    /*  calls LeftRotate it expects the parent pointer of nil to be */
    /*  unchanged. */
  
    x=y->left;
    y->left=x->right;
  
    if (nil != x->right)  x->right->parent=y; /*used to use sentinel here */
    /* and do an unconditional assignment instead of testing for nil */
  
    /* instead of checking if x->parent is the root as in the book, we */
    /* count on the root sentinel to implicitly take care of this case */
    x->parent=y->parent;
    if( y == y->parent->left) {
      y->parent->left=x;
    } else {
      y->parent->right=x;
    }
    x->right=y;
    y->parent=x;
  
  #ifdef DEBUG_ASSERT
    Assert(!tree->nil->red,"nil not red in RightRotate");
  #endif
  }
  
  /***********************************************************************/
  /*  FUNCTION:  TreeInsertHelp  */
  /**/
  /*  INPUTS:  tree is the tree to insert into and z is the node to insert */
  /**/
  /*  OUTPUT:  none */
  /**/
  /*  Modifies Input:  tree, z */
  /**/
  /*  EFFECTS:  Inserts z into the tree as if it were a regular binary tree */
  /*            using the algorithm described in _Introduction_To_Algorithms_ */
  /*            by Cormen et al.  This funciton is only intended to be called */
  /*            by the RBTreeInsert function and not by the user */
  /***********************************************************************/
  
  void TreeInsertHelp(rb_red_blk_tree* tree, rb_red_blk_node* z) {
    /*  This function should only be called by InsertRBTree (see above) */
    rb_red_blk_node* x;
    rb_red_blk_node* y;
    rb_red_blk_node* nil=tree->nil;
    
    z->left=z->right=nil;
    y=tree->root;
    x=tree->root->left;
    while( x != nil) {
      y=x;
      if (1 == tree->Compare(x->key,z->key)) { /* x.key > z.key */
        x=x->left;
      } else { /* x,key <= z.key */
        x=x->right;
      }
    }
    z->parent=y;
    if ( (y == tree->root) ||
         (1 == tree->Compare(y->key,z->key))) { /* y.key > z.key */
      y->left=z;
    } else {
      y->right=z;
    }
  
  #ifdef DEBUG_ASSERT
    Assert(!tree->nil->red,"nil not red in TreeInsertHelp");
  #endif
  }
  
  /*  Before calling Insert RBTree the node x should have its key set */
  
  /***********************************************************************/
  /*  FUNCTION:  RBTreeInsert */
  /**/
  /*  INPUTS:  tree is the red-black tree to insert a node which has a key */
  /*           pointed to by key and info pointed to by info.  */
  /**/
  /*  OUTPUT:  This function returns a pointer to the newly inserted node */
  /*           which is guarunteed to be valid until this node is deleted. */
  /*           What this means is if another data structure stores this */
  /*           pointer then the tree does not need to be searched when this */
  /*           is to be deleted. */
  /**/
  /*  Modifies Input: tree */
  /**/
  /*  EFFECTS:  Creates a node node which contains the appropriate key and */
  /*            info pointers and inserts it into the tree. */
  /***********************************************************************/
  
  rb_red_blk_node * RBTreeInsert(rb_red_blk_tree* tree, void* key, void* info) {
    rb_red_blk_node * y;
    rb_red_blk_node * x;
    rb_red_blk_node * newNode;
  
    x=(rb_red_blk_node*) SafeMalloc(sizeof(rb_red_blk_node));
    x->key=key;
    x->info=info;
  
    TreeInsertHelp(tree,x);
    newNode=x;
    x->red=1;
    while(x->parent->red) { /* use sentinel instead of checking for root */
      if (x->parent == x->parent->parent->left) {
        y=x->parent->parent->right;
        if (y->red) {
  	x->parent->red=0;
  	y->red=0;
  	x->parent->parent->red=1;
  	x=x->parent->parent;
        } else {
  	if (x == x->parent->right) {
  	  x=x->parent;
  	  LeftRotate(tree,x);
  	}
  	x->parent->red=0;
  	x->parent->parent->red=1;
  	RightRotate(tree,x->parent->parent);
        } 
      } else { /* case for x->parent == x->parent->parent->right */
        y=x->parent->parent->left;
        if (y->red) {
  	x->parent->red=0;
  	y->red=0;
  	x->parent->parent->red=1;
  	x=x->parent->parent;
        } else {
  	if (x == x->parent->left) {
  	  x=x->parent;
  	  RightRotate(tree,x);
  	}
  	x->parent->red=0;
  	x->parent->parent->red=1;
  	LeftRotate(tree,x->parent->parent);
        } 
      }
    }
    tree->root->left->red=0;
    return(newNode);
  
  #ifdef DEBUG_ASSERT
    Assert(!tree->nil->red,"nil not red in RBTreeInsert");
    Assert(!tree->root->red,"root not red in RBTreeInsert");
  #endif
  }
  
  /***********************************************************************/
  /*  FUNCTION:  TreeSuccessor  */
  /**/
  /*    INPUTS:  tree is the tree in question, and x is the node we want the */
  /*             the successor of. */
  /**/
  /*    OUTPUT:  This function returns the successor of x or NULL if no */
  /*             successor exists. */
  /**/
  /*    Modifies Input: none */
  /**/
  /*    Note:  uses the algorithm in _Introduction_To_Algorithms_ */
  /***********************************************************************/
    
  rb_red_blk_node* TreeSuccessor(rb_red_blk_tree* tree,rb_red_blk_node* x) { 
    rb_red_blk_node* y;
    rb_red_blk_node* nil=tree->nil;
    rb_red_blk_node* root=tree->root;
  
    if (nil != (y = x->right)) { /* assignment to y is intentional */
      while(y->left != nil) { /* returns the minium of the right subtree of x */
        y=y->left;
      }
      return(y);
    } else {
      y=x->parent;
      while(x == y->right) { /* sentinel used instead of checking for nil */
        x=y;
        y=y->parent;
      }
      if (y == root) return(nil);
      return(y);
    }
  }
  
  /***********************************************************************/
  /*  FUNCTION:  Treepredecessor  */
  /**/
  /*    INPUTS:  tree is the tree in question, and x is the node we want the */
  /*             the predecessor of. */
  /**/
  /*    OUTPUT:  This function returns the predecessor of x or NULL if no */
  /*             predecessor exists. */
  /**/
  /*    Modifies Input: none */
  /**/
  /*    Note:  uses the algorithm in _Introduction_To_Algorithms_ */
  /***********************************************************************/
  
  rb_red_blk_node* TreePredecessor(rb_red_blk_tree* tree, rb_red_blk_node* x) {
    rb_red_blk_node* y;
    rb_red_blk_node* nil=tree->nil;
    rb_red_blk_node* root=tree->root;
  
    if (nil != (y = x->left)) { /* assignment to y is intentional */
      while(y->right != nil) { /* returns the maximum of the left subtree of x */
        y=y->right;
      }
      return(y);
    } else {
      y=x->parent;
      while(x == y->left) { 
        if (y == root) return(nil); 
        x=y;
        y=y->parent;
      }
      return(y);
    }
  }
  
  /***********************************************************************/
  /*  FUNCTION:  InorderTreePrint */
  /**/
  /*    INPUTS:  tree is the tree to print and x is the current inorder node */
  /**/
  /*    OUTPUT:  none  */
  /**/
  /*    EFFECTS:  This function recursively prints the nodes of the tree */
  /*              inorder using the PrintKey and PrintInfo functions. */
  /**/
  /*    Modifies Input: none */
  /**/
  /*    Note:    This function should only be called from RBTreePrint */
  /***********************************************************************/
  
  void InorderTreePrint(rb_red_blk_tree* tree, rb_red_blk_node* x) {
    rb_red_blk_node* nil=tree->nil;
    rb_red_blk_node* root=tree->root;
    if (x != tree->nil) {
      InorderTreePrint(tree,x->left);
      printf("info=");
      tree->PrintInfo(x->info);
      printf("  key="); 
      tree->PrintKey(x->key);
      printf("  l->key=");
      if( x->left == nil) printf("NULL"); else tree->PrintKey(x->left->key);
      printf("  r->key=");
      if( x->right == nil) printf("NULL"); else tree->PrintKey(x->right->key);
      printf("  p->key=");
      if( x->parent == root) printf("NULL"); else tree->PrintKey(x->parent->key);
      printf("  red=%i\n",x->red);
      InorderTreePrint(tree,x->right);
    }
  }
  
  
  /***********************************************************************/
  /*  FUNCTION:  TreeDestHelper */
  /**/
  /*    INPUTS:  tree is the tree to destroy and x is the current node */
  /**/
  /*    OUTPUT:  none  */
  /**/
  /*    EFFECTS:  This function recursively destroys the nodes of the tree */
  /*              postorder using the DestroyKey and DestroyInfo functions. */
  /**/
  /*    Modifies Input: tree, x */
  /**/
  /*    Note:    This function should only be called by RBTreeDestroy */
  /***********************************************************************/
  
  void TreeDestHelper(rb_red_blk_tree* tree, rb_red_blk_node* x) {
    rb_red_blk_node* nil=tree->nil;
    if (x != nil) {
      TreeDestHelper(tree,x->left);
      TreeDestHelper(tree,x->right);
      tree->DestroyKey(x->key);
      tree->DestroyInfo(x->info);
      free(x);
    }
  }
  
  
  /***********************************************************************/
  /*  FUNCTION:  RBTreeDestroy */
  /**/
  /*    INPUTS:  tree is the tree to destroy */
  /**/
  /*    OUTPUT:  none */
  /**/
  /*    EFFECT:  Destroys the key and frees memory */
  /**/
  /*    Modifies Input: tree */
  /**/
  /***********************************************************************/
  
  void RBTreeDestroy(rb_red_blk_tree* tree) {
    TreeDestHelper(tree,tree->root->left);
    free(tree->root);
    free(tree->nil);
    free(tree);
  }
  
  
  /***********************************************************************/
  /*  FUNCTION:  RBTreePrint */
  /**/
  /*    INPUTS:  tree is the tree to print */
  /**/
  /*    OUTPUT:  none */
  /**/
  /*    EFFECT:  This function recursively prints the nodes of the tree */
  /*             inorder using the PrintKey and PrintInfo functions. */
  /**/
  /*    Modifies Input: none */
  /**/
  /***********************************************************************/
  
  void RBTreePrint(rb_red_blk_tree* tree) {
    InorderTreePrint(tree,tree->root->left);
  }
  
  
  /***********************************************************************/
  /*  FUNCTION:  RBExactQuery */
  /**/
  /*    INPUTS:  tree is the tree to print and q is a pointer to the key */
  /*             we are searching for */
  /**/
  /*    OUTPUT:  returns the a node with key equal to q.  If there are */
  /*             multiple nodes with key equal to q this function returns */
  /*             the one highest in the tree */
  /**/
  /*    Modifies Input: none */
  /**/
  /***********************************************************************/
    
  rb_red_blk_node- RBExactQuery(rb_red_blk_tree* tree, void* q) {
    rb_red_blk_node* x=tree->root->left;
    rb_red_blk_node* nil=tree->nil;
    int compVal;
    if (x == nil) return(0);
    compVal=tree->Compare(x->key,(int*) q);
    while(0 != compVal) {/*assignemnt*/
      if (1 == compVal) { /* x->key > q */
        x=x->left;
      } else {
        x=x->right;
      }
      if ( x == nil) return(0);
      compVal=tree->Compare(x->key,(int*) q);
    }
    return(x);
  }
  
  
  /***********************************************************************/
  /*  FUNCTION:  RBDeleteFixUp */
  /**/
  /*    INPUTS:  tree is the tree to fix and x is the child of the spliced */
  /*             out node in RBTreeDelete. */
  /**/
  /*    OUTPUT:  none */
  /**/
  /*    EFFECT:  Performs rotations and changes colors to restore red-black */
  /*             properties after a node is deleted */
  /**/
  /*    Modifies Input: tree, x */
  /**/
  /*    The algorithm from this function is from _Introduction_To_Algorithms_ */
  /***********************************************************************/
  
  void RBDeleteFixUp(rb_red_blk_tree* tree, rb_red_blk_node* x) {
    rb_red_blk_node* root=tree->root->left;
    rb_red_blk_node* w;
  
    while( (!x->red) && (root != x)) {
      if (x == x->parent->left) {
        w=x->parent->right;
        if (w->red) {
  	w->red=0;
  	x->parent->red=1;
  	LeftRotate(tree,x->parent);
  	w=x->parent->right;
        }
        if ( (!w->right->red) && (!w->left->red) ) { 
  	w->red=1;
  	x=x->parent;
        } else {
  	if (!w->right->red) {
  	  w->left->red=0;
  	  w->red=1;
  	  RightRotate(tree,w);
  	  w=x->parent->right;
  	}
  	w->red=x->parent->red;
  	x->parent->red=0;
  	w->right->red=0;
  	LeftRotate(tree,x->parent);
  	x=root; /* this is to exit while loop */
        }
      } else { /* the code below is has left and right switched from above */
        w=x->parent->left;
        if (w->red) {
  	w->red=0;
  	x->parent->red=1;
  	RightRotate(tree,x->parent);
  	w=x->parent->left;
        }
        if ( (!w->right->red) && (!w->left->red) ) { 
  	w->red=1;
  	x=x->parent;
        } else {
  	if (!w->left->red) {
  	  w->right->red=0;
  	  w->red=1;
  	  LeftRotate(tree,w);
  	  w=x->parent->left;
  	}
  	w->red=x->parent->red;
  	x->parent->red=0;
  	w->left->red=0;
  	RightRotate(tree,x->parent);
  	x=root; /* this is to exit while loop */
        }
      }
    }
    x->red=0;
  
  #ifdef DEBUG_ASSERT
    Assert(!tree->nil->red,"nil not black in RBDeleteFixUp");
  #endif
  }
  
  
  /***********************************************************************/
  /*  FUNCTION:  RBDelete */
  /**/
  /*    INPUTS:  tree is the tree to delete node z from */
  /**/
  /*    OUTPUT:  none */
  /**/
  /*    EFFECT:  Deletes z from tree and frees the key and info of z */
  /*             using DestoryKey and DestoryInfo.  Then calls */
  /*             RBDeleteFixUp to restore red-black properties */
  /**/
  /*    Modifies Input: tree, z */
  /**/
  /*    The algorithm from this function is from _Introduction_To_Algorithms_ */
  /***********************************************************************/
  
  void RBDelete(rb_red_blk_tree* tree, rb_red_blk_node* z){
    rb_red_blk_node* y;
    rb_red_blk_node* x;
    rb_red_blk_node* nil=tree->nil;
    rb_red_blk_node* root=tree->root;
  
    y= ((z->left == nil) || (z->right == nil)) ? z : TreeSuccessor(tree,z);
    x= (y->left == nil) ? y->right : y->left;
    if (root == (x->parent = y->parent)) { /* assignment of y->p to x->p is intentional */
      root->left=x;
    } else {
      if (y == y->parent->left) {
        y->parent->left=x;
      } else {
        y->parent->right=x;
      }
    }
    if (y != z) { /* y should not be nil in this case */
  
  #ifdef DEBUG_ASSERT
      Assert( (y!=tree->nil),"y is nil in RBDelete\n");
  #endif
      /* y is the node to splice out and x is its child */
  
      if (!(y->red)) RBDeleteFixUp(tree,x);
    
      tree->DestroyKey(z->key);
      tree->DestroyInfo(z->info);
      y->left=z->left;
      y->right=z->right;
      y->parent=z->parent;
      y->red=z->red;
      z->left->parent=z->right->parent=y;
      if (z == z->parent->left) {
        z->parent->left=y; 
      } else {
        z->parent->right=y;
      }
      free(z); 
    } else {
      tree->DestroyKey(y->key);
      tree->DestroyInfo(y->info);
      if (!(y->red)) RBDeleteFixUp(tree,x);
      free(y);
    }
    
  #ifdef DEBUG_ASSERT
    Assert(!tree->nil->red,"nil not black in RBDelete");
  #endif
  }
  
  
  /***********************************************************************/
  /*  FUNCTION:  RBEnumerate */
  /**/
  /*    INPUTS:  tree is the tree to look for keys >= low */
  /*             and <= high with respect to the Compare function */
  /**/
  /*    OUTPUT:  stack containing pointers to the nodes between [low,high] */
  /**/
  /*    Modifies Input: none */
  /***********************************************************************/
  
  stk_stack* RBEnumerate(rb_red_blk_tree* tree, void* low, void* high) {
    stk_stack* enumResultStack;
    rb_red_blk_node* nil=tree->nil;
    rb_red_blk_node* x=tree->root->left;
    rb_red_blk_node* lastBest=nil;
  
    enumResultStack=StackCreate();
    while(nil != x) {
      if ( 1 == (tree->Compare(x->key,high)) ) { /* x->key > high */
        x=x->left;
      } else {
        lastBest=x;
        x=x->right;
      }
    }
    while ( (lastBest != nil) && (1 != tree->Compare(low,lastBest->key))) {
      StackPush(enumResultStack,lastBest);
      lastBest=TreePredecessor(tree,lastBest);
    }
    return(enumResultStack);
  }
  
  
  int checkRepHelper (rb_red_blk_node *node, rb_red_blk_tree *t)
  {
    int left_black_cnt, right_black_cnt;
  
    /* by convention sentinel nodes point to nil instead of null */
    assert (node);
    if (node == t->nil) return 0;
    
    /* the tree order must be respected */
    /* parents and children must point to each other */
    if (node->left != t->nil) {
      int tmp = t->Compare (node->key, node->left->key);
      assert (tmp==0 || tmp==1);
      assert (node->left->parent == node);
    }
    if (node->right != t->nil) { 
      int tmp = t->Compare (node->key, node->right->key);
      assert (tmp==0 || tmp==-1);
      assert (node->right->parent == node);
    }
    if (node->left != t->nil && node->right != t->nil) {
      int tmp = t->Compare (node->left->key, node->right->key);
      assert (tmp==0 || tmp==-1);
    }
    
    /* both children of a red node are black */
    if (node->red) {
      assert (!node->left->red);
      assert (!node->right->red);
    }
  
    /* every root->leaf path has the same number of black nodes */
    left_black_cnt = checkRepHelper (node->left, t);
    right_black_cnt = checkRepHelper (node->right, t);
    assert (left_black_cnt == right_black_cnt);
    return left_black_cnt + (node->red ? 0 : 1);
  }
  
  void checkRep (rb_red_blk_tree *tree)
  {
    /* root is black by convention */
    assert (!tree->root->left->red);
    checkRepHelper (tree->root->left, tree);
  }
  
  