/**************************************************************************

This software is copyrighted by PHILIP SMOLEN.
The following terms apply to all files associated with the software unless 
explicitly disclaimed in individual files.

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.

IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY PARTY
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.

GOVERNMENT USE: If you are acquiring this software on behalf of the
U.S. government, the Government shall have only "Restricted Rights"
in the software and related documentation as defined in the Federal 
Acquisition Regulations (FARs) in Clause 52.227.19 (c) (2).  If you
are acquiring the software on behalf of the Department of Defense, the
software shall be classified as "Commercial Computer Software" and the
Government shall have only "Restricted Rights" as defined in Clause
252.227-7013 (c) (1) of DFARs.  Notwithstanding the foregoing, the
authors grant the U.S. Government and others acting in its behalf
permission to use and distribute the software in accordance with the
terms specified in this license. 

**************************************************************************/


//*************************************************************************
// WAY OUT OF DATE.  BUT YOU GET THE IDEA.
// rbtree.c - code for a simple red-black tree.
//
// rbtreeType<X> is a red-black tree with elements of type X.  If X is
// a simple type, like int, then rbtreeType<X> forms a set with elements
// of type <X>.  If X is any ordered pair type, and only the first item
// in the pair is used in the comparison, then rbtreeType forms a lookup
// table.  All operations are O(log(n)), where n is the number of elements
// in the three, except as noted below.
//
// The type X must have a < and == operator.  If two items are == then only
// one of them may be in the tree at once.  If A < B, A will come before A
// when iterating with the next() function.
//
// The assumption is that < and == form a consistent ordering on type X.
// However, even if these operators give bogus results, the code will
// never dump core or run in an infinite loop.  In fact, the algorithms
// will still be O(log(n)), even in the worst case.  However, the size
// of the tree may be larger if the == operation always returns false.
// Iterating through the tree will still return all elements of the tree.
//
// < and == may safely throw exceptions.  These exceptions will not cause
// any memory leaks or damage to the tree.  All comparisons are done
// before any modifications, so an exception will cause the requested
// operation to abort without modifying the tree.
//
// The copies of the items, not pointers to the items, are stored in the
// tree.  If X is a class, is needs to have a valid copy constructor,
// assignment operator, and destructor.  References are used as much as
// possible to minimize the number of copies.
//
// The tree defines an iterator type.  The iterator is a constant
// pointer to a node.  A constant reference to the data is available 
// from here.  Overriding the const is perfectly acceptable as long as
// the new value == the original value.  (Note that the const on the
// iterator is more a consequence of some nasty implementation details
// than it is a suggestion of how to use the iterator.)  A NULL iterator
// indicates the end of the tree, or a non-existent element.  All 
// iterators are valid only as long as the tree does not changes; any
// additions or deletions invalidates all iterators for the given tree.
//
// Define UNIT_TEST to run tests on a simple instantiation of this
// datatype.  Also, the UNIT_TEST code provides a simple sample of how
// to use this tree.  Define RBTREE_WITH_DEBUG to compile methods which
// are used in development and debugging, but are not needed in a working
// system.  RBTREE_WITH_DEBUG requires console output, so the code is
// not applicable for all systems.
//
// The algorithms below were adapted from _Introduction_to_Algorithms_
// by Cormen, Leiserson, and Rivest, 1990.  This book is an excellent
// source for information on this data structure.
//
// All code below was written by Philip Smolen.
// Contact info:  http://www.trade-ideas.com/home/phil/RBTree/

#include "rbtree.h"

#ifdef UNIT_TEST
#define RBTREE_WITH_DEBUG
#endif

#include <assert.h>
#include <stdlib.h>

#ifdef RBTREE_WITH_DEBUG
#include <stdio.h>
#endif



#define isNull(tree, node) ((node) == &tree->null)

static void deleteNode(struct rbTreeType *tree, struct rbNodeType *node)
{
  if (tree->freeData) 
    {
      tree->freeData(&node->data);
    }
  free(node);
}

static void clearNode(struct rbTreeType *tree, struct rbNodeType *node)
{
  if (!isNull(tree, node))
    {
      clearNode(tree, node->left);
      clearNode(tree, node->right);
      deleteNode(tree, node);
    }
}

void rbClear(struct rbTreeType *tree)
{
  clearNode(tree, tree->root);
  tree->root = &tree->null;
}

int rbEmpty(const struct rbTreeType *tree)
{
  return isNull(tree, tree->root);
}

static unsigned int rbCountHelper(const struct rbNodeType *node, 
				  const struct rbNodeType *null)
{
  if (node == null)
    {
      return 0;
    }
  else
    {
      return 1 + 
	rbCountHelper(node->left, null) + rbCountHelper(node->right, null);
    }
}

unsigned int rbCount(const struct rbTreeType *tree)
{
  return rbCountHelper(tree->root, &tree->null);
}

struct rbTreeType *rbNewTree(void)
{
  struct rbTreeType *newTree 
    = (struct rbTreeType *)malloc(sizeof(struct rbTreeType));
  assert(newTree);
  newTree->null.black = 1;
  newTree->null.left = &newTree->null;
  newTree->null.right = &newTree->null;
  newTree->null.parent = &newTree->null;
  newTree->root = &newTree->null;
  newTree->freeData = NULL;
  newTree->dupData = NULL;
  newTree->compareKeys = NULL;
  newTree->compareData = NULL;
  return newTree;
}

void rbDeleteTree(struct rbTreeType *tree)
{
  rbClear(tree);
  free(tree);
}

static struct rbNodeType *newNode(struct rbTreeType *tree, 
				  const struct rbDataType *data)
{
  struct rbNodeType *node 
    = (struct rbNodeType *)malloc(sizeof(struct rbNodeType));
  assert(node);
  if (tree->dupData)
    {
      tree->dupData(&node->data, data);
    }
  else
    {
      node->data = *data;
    }
  node->left = node->right = node->parent = &tree->null;
  return node;
}

static struct rbNodeType *deepCopyNode(struct rbTreeType *destTree,
				       struct rbNodeType *parent,
				       const struct rbTreeType *srcTree,
				       const struct rbNodeType *src)
{
  if (isNull(srcTree, src))
    {
      return &destTree->null;
    }
  else
    {
      struct rbNodeType *node = newNode(destTree, &src->data);
      node->black = src->black;
      node->parent = parent;
      node->left = deepCopyNode(destTree, node, srcTree, src->left);
      node->right = deepCopyNode(destTree, node, srcTree, src->right);
      return node;
    }
}

struct rbTreeType *rbCopy(const struct rbTreeType *tree)
{
  struct rbTreeType *newTree = rbNewTree();
  newTree->freeData = tree->freeData;
  newTree->dupData = tree->dupData;
  newTree->compareKeys = tree->compareKeys;
  newTree->compareData = tree->compareData;
  newTree->root = deepCopyNode(newTree, &newTree->null, tree, tree->root);
  return newTree;
}

static void leftRotate(struct rbTreeType *tree, struct rbNodeType *node)
{
  //assert(!(isNull(tree, node)||isNull(tree, node->right)));
  struct rbNodeType *x = node;
  struct rbNodeType *y = x->right;
  x->right = y->left;
  if (!isNull(tree, y->left))
    {
      y->left->parent = x;
    }
  y->parent = x->parent;
  if (isNull(tree, x->parent))
    {
      tree->root = y;
    }
  else
    {
      if (x == x->parent->left)
	{
	  x->parent->left = y;
	}
      else
	{
	  x->parent->right = y;
	}
    }
  y->left = x;
  x->parent = y;
}

static void rightRotate(struct rbTreeType *tree, struct rbNodeType *node)
{
  //assert(!(isNull(tree, node)||isNull(tree, node->left)));
  struct rbNodeType *x = node;
  struct rbNodeType *y = x->left;
  x->left = y->right;
  if (!isNull(tree, y->right))
    {
      y->right->parent = x;
    }
  y->parent = x->parent;
  if (isNull(tree, x->parent))
    {
      tree->root = y;
    }
  else
    {
      if (x == x->parent->right)
	{
	  x->parent->right = y;
	}
      else
	{
	  x->parent->left = y;
	}
    }
  y->right = x;
  x->parent = y;
}

static void assign(struct rbTreeType *tree, 
		   struct rbDataType *dest, 
		   const struct rbDataType *src)
{
  if (tree->freeData)
    {
      tree->freeData(dest);
    }
  if (tree->dupData)
    {
      tree->dupData(dest, src);
    }
  else
    {
      *dest = *src;
    }
}

enum rbResultType rbAdd(struct rbTreeType *tree, 
			struct rbDataType *data, 
			int allowOverwrite)
{
  if (isNull(tree, tree->root))
    {
      tree->root = newNode(tree, data);
    }
  else
    {
      struct rbNodeType *parent = &tree->null;
      struct rbNodeType *current = tree->root;

      // The assignment is to satisfy the compiler.  We know this value will
      // be overwritten because we already checked for root == null above.
      enum rbCompareType comparison = RBC_ERROR;

      while (!isNull(tree, current))
	{
	  comparison = tree->compareKeys(data->key, current->data.key, tree->compareData);
	  if (comparison == RBC_EQUAL)
	    { // The data is already in the tree.  (Or different data with the
	      // same key value.)
	      if (allowOverwrite)
		{
		  assign(tree, &current->data, data);
		  return RBR_SUCCEED;
		}
	      else
		{
		  return RBR_OTHER_FAIL;
		}
	    }
	  
	  if (comparison == RBC_ERROR)
	    {
	      return RBR_OTHER_FAIL;
	    }

	  parent = current;
	  if (comparison == RBC_LESS) 
	    {
	      current = current->left;
	    }
	  else
	    {
	      current = current->right;
	    }
	}
      
      // The data is not in the tree.  Parent points to a node with a null
      // pointer where we need to be inserted.  Now that we have safely made
      // the last comparison, we can safely start allocating memory and
      // modifying the tree.
      current = newNode(tree, data);
      current->black = 0;
      current->parent = parent;
      if (comparison == RBC_LESS) 
	{
	  assert(isNull(tree, parent->left));
	  parent->left = current;
	}
      else
	{
	  assert(isNull(tree, parent->right));
	  parent->right = current;
	}
  
      // We have added the new node to the binary search tree, but it may not
      // be a proper rbtree any more.  Now we need to force the tree back into
      // balance.
      while ((current != tree->root) && (!current->parent->black)) 
	{
	  // This should never fail because the root is always black.
	  assert (!isNull(tree, current->parent->parent));  
	  if (current->parent == current->parent->parent->left)
	    {
	      struct rbNodeType *uncle = current->parent->parent->right;
	      if (!uncle->black)
		{
		  current->parent->black = 1;
		  uncle->black = 1;
		  current->parent->parent->black = 0;
		  current = current->parent->parent;
		}
	      else 
		{
		  if (current == current->parent->right) 
		    {
		      current = current->parent;
		      leftRotate(tree, current);
		    }
		  current->parent->black = 1;
		  current->parent->parent->black = 0;
		  rightRotate(tree, current->parent->parent);
		}
	    }
	  else
	    {
	      struct rbNodeType *uncle = current->parent->parent->left;
	      if (!uncle->black)
		{
		  current->parent->black = 1;
		  uncle->black = 1;
		  current->parent->parent->black = 0;
		  current = current->parent->parent;
		}
	      else
		{
		  if (current == current->parent->left) 
		    {
		      current = current->parent;
		      rightRotate(tree, current);
		    }
		  current->parent->black = 1;
		  current->parent->parent->black = 0;
		  leftRotate(tree, current->parent->parent);
		}
	    }
	}
    }

  // The tree was successfully modified.
  tree->root->black = 1;
  return RBR_SUCCEED;
}

// export is a keyword for some compilers!  The xport (export) function
// converts the null sentinal, an implementation detail, into a standard
// NULL for use by the outside world.
#define xport(tree, node) (isNull(tree, node)?NULL:(struct rbNodeType *)node)

struct rbNodeType *rbFirst(const struct rbTreeType *tree)
{
  const struct rbNodeType *parent = &tree->null;
  struct rbNodeType *current = tree->root;
  while (!isNull(tree, current))
    {
      parent = current;
      current = current->left;
    }
  return xport(tree, parent);
}  

struct rbNodeType *rbLast(const struct rbTreeType *tree)
{
  const struct rbNodeType *parent = &tree->null;
  struct rbNodeType *current = tree->root;
  while (!isNull(tree, current))
    {
      parent = current;
      current = current->right;
    }
  return xport(tree, parent);
}

struct rbNodeType *rbNext(const struct rbTreeType *tree, 
			  const struct rbNodeType *node)
{
  if (!node)
    { // Wrap around.
      return rbFirst(tree);
    }
  else if (!isNull(tree, node->right))
    {
      struct rbNodeType *current = node->right;
      while (!isNull(tree, current->left))
	{
	  current = current->left;
	}
      return current;
    }
  else
    {
      struct rbNodeType *parent = node->parent;
      while ((!isNull(tree, parent)) && (node == parent->right))
	{
	  node = parent;
	  parent = node->parent;
	}
      return xport(tree, parent);
    }
}

struct rbNodeType *rbPrev(const struct rbTreeType *tree, 
			  const struct rbNodeType *node)
{
  if (!node)
    { // Wrap around.
      return rbLast(tree);
    }
  else if (!isNull(tree, node->left))
    {
      struct rbNodeType *current = node->left;
      while (!isNull(tree, current->right))
	{
	  current = current->right;
	}
      return current;
    }
  else
    {
      struct rbNodeType *parent = node->parent;
      while ((!isNull(tree, parent)) && (node == parent->left))
	{
	  node = parent;
	  parent = node->parent;
	}
      return xport(tree, parent);
    }
}

extern enum rbResultType rbFind(const struct rbTreeType *tree,
				const rbKeyType key,
				enum rbDirectionType direction,
				struct rbNodeType **found)
{
  // A good default.
  *found = NULL;

  if (isNull(tree, tree->root))
    { // This will have to be a special case sooner or later.  Might as
      // well deal with it now.
      return RBR_OTHER_FAIL;
    }
  else
    {
      // The assignment is to satisfy the compiler.  We know this value will
      // be overwritten because we already checked for root == null above.
      enum rbCompareType comparison = RBC_ERROR;

      // We never return the null, so it is okay to override the const.
      struct rbNodeType *parent = (struct rbNodeType *)&tree->null;
      struct rbNodeType *node = tree->root;

      while (!isNull(tree, node)) 
	{
	  comparison = tree->compareKeys(key, 
					 node->data.key, 
					 tree->compareData);
	  switch (comparison)
	    {
	    case RBC_EQUAL:
	      *found = node;
	      return RBR_SUCCEED;
	    case RBC_LESS:
	      parent = node;
	      node = node->left;
	      break;
	    case RBC_MORE:
	      parent = node;
	      node = node->right;
	      break;
	    default:
	      return RBR_COMPARE_FAIL;
	    }
	}
      
      // No exact match could be found. 
      assert(!isNull(tree, parent));
      switch (direction)
	{
	case RBD_EXACT:
	  return RBR_OTHER_FAIL;
	case RBD_BEFORE:
	  if (comparison == RBC_MORE)
	    {
	      *found = parent;
	      return RBR_SUCCEED;
	    }
	  else
	    { 
	      *found = rbPrev(tree, parent);
	      return found?RBR_SUCCEED:RBR_OTHER_FAIL;
	    }
	case RBD_AFTER:
	  if (comparison == RBC_LESS)
	    {
	      *found = parent;
	      return RBR_SUCCEED;
	    }
	  else
	    {
	      *found = rbNext(tree, parent);
	      return (*found)?RBR_SUCCEED:RBR_OTHER_FAIL;
	    }
	}
    }

  // Can't get here, but the compiler is still complaining!
  assert(0);
  return RBR_OTHER_FAIL;
}

void rbRemoveNode(struct rbTreeType *tree, struct rbNodeType *node)
{
  struct rbNodeType *reallyRemove;
  struct rbNodeType *soleChild;  // This may become the sentinal null, if there
                                 // are no children.

  if (!node) { return; }

  if (isNull(tree, node->left) || isNull(tree, node->right))
    {
      reallyRemove = node;
    }
  else
    { // It would be nice to have a const and non const version of rbNext.
      reallyRemove = (struct rbNodeType *)rbNext(tree, node);
    }

  if (isNull(tree, reallyRemove->left))
    {
      soleChild = reallyRemove->right;
    }
  else
    {
      soleChild = reallyRemove->left;
    }

  soleChild->parent = reallyRemove->parent;
  if (isNull(tree, reallyRemove->parent))
    {
      tree->root = soleChild;
    }
  else if (reallyRemove->parent->left == reallyRemove) 
    {
      reallyRemove->parent->left = soleChild;
    }
  else
    {
      reallyRemove->parent->right = soleChild;
    }
  if (reallyRemove != node)
    { // This copy is not as effecient as it could be.  We don't worry too
      // much because the target client is just going to use an extra reference
      // count increment then decrement.  Could be worse for a real copy.
      assign(tree, &node->data, &reallyRemove->data);
    }

  // The data in the specified node has been removed from the tree.
  // The node reallyRemove has been removed from the tree.  Now the
  // tree may be out of balance, and not a valid red-black tree.
  if (reallyRemove->black)
    {
      struct rbNodeType *extraBlack = soleChild;
      while ((extraBlack != tree->root) && extraBlack->black)
	{
	  if (extraBlack == extraBlack->parent->left)
	    {
	      struct rbNodeType *sibling = extraBlack->parent->right;
	      if (!sibling->black)
		{
		  sibling->black = 1;
		  extraBlack->parent->black = 0;
		  leftRotate(tree, extraBlack->parent);
		  sibling = extraBlack->parent->right;
		}
	      if (sibling->left->black && sibling->right->black)
		{
		  sibling->black = 0;
		  extraBlack = extraBlack->parent;
		}
	      else
		{
		  if (sibling->right->black)
		    {
		      sibling->left->black = 1;
		      sibling->black = 0;
		      rightRotate(tree, sibling);
		      sibling = extraBlack->parent->right;
		    }
		  sibling->black = extraBlack->parent->black;
		  extraBlack->parent->black = 1;
		  sibling->right->black = 1;
		  leftRotate(tree, extraBlack->parent);
		  extraBlack = tree->root;
		}
	    }
	  else
	    {
	      struct rbNodeType *sibling = extraBlack->parent->left;
	      if (!sibling->black)
		{
		  sibling->black = 1;
		  extraBlack->parent->black = 0;
		  rightRotate(tree, extraBlack->parent);
		  sibling = extraBlack->parent->left;
		}
	      if (sibling->left->black && sibling->right->black)
		{
		  sibling->black = 0;
		  extraBlack = extraBlack->parent;
		}
	      else
		{
		  if (sibling->left->black)
		    {
		      sibling->right->black = 1;
		      sibling->black = 0;
		      leftRotate(tree, sibling);
		      sibling = extraBlack->parent->left;
		    }
		  sibling->black = extraBlack->parent->black;
		  extraBlack->parent->black = 1;
		  sibling->left->black = 1;
		  rightRotate(tree, extraBlack->parent);
		  extraBlack = tree->root;
		}
	    }
	}
      extraBlack->black = 1;
    }

  // Now that we are done, we can free up the node.
  deleteNode(tree, reallyRemove);
}

enum rbResultType rbRemove(struct rbTreeType *tree, const rbKeyType key)
{
  struct rbNodeType *node = tree->root;
  while (1)
    {
      if (isNull(tree, node))
	{ // The data we want to delete is not in the tree.
	  return RBR_OTHER_FAIL;
	}
      else
	{
	  enum rbCompareType comparison = 
	    tree->compareKeys(key, node->data.key, tree->compareData);
	  if (comparison == RBC_ERROR)
	    {
	      return RBR_COMPARE_FAIL;
	    }
	  if (comparison == RBC_EQUAL)
	    { // This is the node we want to delete.
	      rbRemoveNode(tree, node);
	      return RBR_SUCCEED;
	    }
	  if (comparison == RBC_LESS)
	    {
	      node = node->left;
	    }
	  else
	    {
	      node = node->right;
	    }
	}
    }
}

enum rbResultType rbExists(const struct rbTreeType *tree,
			   const rbKeyType key)
{
  struct rbNodeType *node = tree->root;
  while (!isNull(tree, node)) 
    {
      switch (tree->compareKeys(key, node->data.key, tree->compareData))
	{
	case RBC_EQUAL:
	  return RBR_SUCCEED;
	case RBC_LESS:
	  node = node->left;
	  break;
	case RBC_MORE:
	  node = node->right;
	  break;
	default:
	  return RBR_COMPARE_FAIL;
	}
    }
  return RBR_OTHER_FAIL;
}


#ifdef RBTREE_WITH_DEBUG
static void dumpNode(struct rbTreeType *tree, struct rbNodeType *node)
{
  if (!isNull(tree, node)) 
    {
      putchar('(');
      dumpNode(tree, node->left);
      printf(" %d%c ", node->data.key, node->black?'B':'r');
      dumpNode(tree, node->right);
      putchar(')');
    }
}

static void dump(struct rbTreeType *tree)
{
  dumpNode(tree, tree->root);
}

static void assertNodeInvariants(struct rbTreeType *tree,
				 struct rbNodeType *toCheck, 
				 struct rbNodeType *parent, 
				 int *blackHeight, 
				 int *problemFound)
{
  int bhL, bhR;
  int pfL, pfR;

  *blackHeight = toCheck->black?1:0;
  *problemFound = 0;

  if (isNull(tree, toCheck))
    {
      return;
    }

  if (toCheck->parent != parent)
    {
      fprintf(stderr, "Invalid link to parent in node %d\n", toCheck->data.key);
      *problemFound = 1;
    }

  assertNodeInvariants(tree, toCheck->left, toCheck, &bhL, &pfL);
  assertNodeInvariants(tree, toCheck->right, toCheck, &bhR, &pfR);

  *problemFound = *problemFound || pfL || pfR;

  if ((bhL == -1) || (bhR == -1))
    {
      *blackHeight = -1;
    }
  else if (bhL != bhR) 
    {
      fprintf(stderr, "Tree unbalanced at node %d, left = %d, right = %d\n",
	      toCheck->data.key, bhL, bhR);
      *blackHeight = -1;
      *problemFound = 1;
    }
  else 
    {
      *blackHeight += bhL;
    }
}

static void assertInvariants(struct rbTreeType *tree)
{
  int blackHeight;
  int otherProblem;

  int error = 0;
  if (!tree->root->black)
    {
      fputs("!tree->root->black\n", stderr);
      error = 1;
    }
  if (!tree->null.black)
    {
      fputs("!tree->null.black\n", stderr);
      error = 1;
    }
  assertNodeInvariants(tree, tree->root, &tree->null, 
		       &blackHeight, &otherProblem);
  error = error || otherProblem;
  if (error)
    {
      dump(tree);
      assert(0);
    }
}

#endif







#ifdef UNIT_TEST
////////////////////////////////////////////////////////////////////////////
//  Unit test code.
////////////////////////////////////////////////////////////////////////////

enum rbCompareType intCompareKeys(const rbKeyType a, 
				  const rbKeyType b, 
				  void *unused)
{
  if ((int)a == (int)b)
    {
      return RBC_EQUAL;
    }
  if ((int)a < (int)b)
    {
      return RBC_LESS;
    }
  return RBC_MORE;
}

typedef const struct rbNodeType *iteratorType;


int getKey(const struct rbNodeType *n)
{
  if (n)
    {
      return (int)n->data.key;
    }
  else
    {
      return -999999;
    }
}

struct rbTreeType *tree;

void doAdd(int value)
{
  struct rbDataType data;
  printf("Add %d:  ", value);
  data.key = (void *)value;
  rbAdd(tree, &data, 1);
  assertInvariants(tree);
  dump(tree);
  putchar('\n');
}

void doRemove(int value)
{
  printf("Remove %d:  ", value);
  rbRemove(tree, (void *)value);
  assertInvariants(tree);
  dump(tree);
  putchar('\n');
}

int main() 
{
  iteratorType i;
  int j;

  assert(1);
  assert((puts("Assertions enabled."),1));

  tree = rbNewTree();
  tree->compareKeys = intCompareKeys;

  assertInvariants(tree);

  puts("\nEmpty tree:");
  printf("rbFirst(tree) = %d\n", getKey(rbFirst(tree)));
  printf("rbLast(tree) = %d\n", getKey(rbLast(tree)));

  putchar('\n');
  doAdd(5);
  doAdd(7);
  doAdd(9);
  doAdd(1);
  doAdd(8);
  doAdd(4);
  printf("Forward:  ");
  for (i = rbFirst(tree); i; i = rbNext(tree, i))
    {
      printf("%d, ", getKey(i));
    }
  printf("%d\n", getKey(i));
  printf("And back:  ");
  do
    {
      printf("%d, ", getKey(i));
      i = rbPrev(tree, i);
    }
  while (i);
  printf("%d\n", getKey(i));

  putchar('\n');
  doAdd(1);
  doAdd(2);
  doAdd(3);
  doAdd(11);
  printf("Forward:  ");
  for (i = rbFirst(tree); i; i = rbNext(tree, i))
    {
      printf("%d, ", getKey(i));
    }
  printf("%d\n", getKey(i));

  for (j=0; j<13; j++)
    {
      printf("%d is %spresent\n", j, (rbExists(tree, (void *)j)==RBR_SUCCEED)?"":"not ");
    }

  printf("\nfind:\n");
  for (j=0; j<13; j++)
    {
      const struct rbNodeType *b, *e, *a;
      rbFind(tree, (void *)j, RBD_BEFORE, &b); 
      rbFind(tree, (void *)j, RBD_EXACT, &e); 
      rbFind(tree, (void *)j, RBD_AFTER, &a); 
      printf("%d:\tRBD_BEFORE:  %d,\tRBD_EXACT:  %d,\tRBD_AFTER:  %d\n",
	     j, getKey(b), getKey(e), getKey(a));
    }

  putchar('\n');
  doRemove(3);
  doRemove(5);
  doRemove(6);
  doRemove(7);
  printf("Forward:  ");
  for (i = rbFirst(tree); i; i = rbNext(tree, i))
    {
      printf("%d, ", getKey(i));
    }
  printf("%d\n", getKey(i));

  putchar('\n');
  for (j = 0; j < 1000; j++)
    {
      int k = rand()+j;
      putchar('.');
      if (j%2)
	{
	  struct rbDataType data;
	  data.key = (void *)k;
	  rbAdd(tree, &data, 1);
	  assert(rbExists(tree, (void *)k)==RBR_SUCCEED);
	}
      else
	{
	  rbRemove(tree, (void *)k);
	  assert(rbExists(tree, (void *)k)==RBR_OTHER_FAIL);
	}
      assertInvariants(tree);
    }
  putchar('\n');
  dump(tree);

  return 0;
}
#endif