q->parent = r;
	  /* now a left rotation around p */
	  p->right = r->left;
	  if (r->left) {
	    r->left->parent = p;
	  }
	  r->left = p;
	  p->parent = r;
	  SET_RANK (q, (GET_RANK (q) - GET_RANK (r)));
	  SET_RANK (r, (GET_RANK (r) + GET_RANK (p)));	    
	}
	if (GET_BALANCE (r) == shortened_side) {
	  SET_BALANCE (q, (- shortened_side));
	  SET_BALANCE (p, 0);
	} else if (GET_BALANCE (r) == (- shortened_side)) {
	  SET_BALANCE (q, 0);
	  SET_BALANCE (p, shortened_side);
	} else {
	  SET_BALANCE (q, 0);
	  SET_BALANCE (p, 0);
	}
	SET_BALANCE (r, 0);
	q = r;
      }
      /* a rotation has caused <q> (or <r> in case 3c) to become
       * the root.  let <p>'s former parent know this.
       */
      if (top->left == p) {
	top->left = q;
      } else {
	top->right = q;
      }
      /* end case 3 */
      p = q;
    }
    x = p;
    p = x->parent;
    /* shortened_side tells us which side we came up from */
    if (x == p->left) {
      shortened_side = -1;
    } else {
      shortened_side = +1;
    }
  } /* end while(shorter) */
  /* when we're all done, we're one shorter */
  tree->length = tree->length - 1;
  return (0);
}

int
iterate_inorder_helper (avl_node * node,
			avl_iter_fun_type iter_fun,
			void * iter_arg)
{
  int result;
  if (node->left) {
    result = iterate_inorder_helper (node->left, iter_fun, iter_arg);
    if (result != 0) {
      return result;
    }
  }
  result = (iter_fun (node->key, iter_arg));
  if (result != 0) {
    return result;
  }
  if (node->right) {
    result = iterate_inorder_helper (node->right, iter_fun, iter_arg);
    if (result != 0) {
      return result;
    }
  }
  return 0;
}

int
iterate_inorder (avl_tree * tree,
		 avl_iter_fun_type iter_fun,
		 void * iter_arg)
{
  int result;

  if (tree->length) {
    result = iterate_inorder_helper (tree->root->right, iter_fun, iter_arg);
    return (result);
  } else {
    return 0;
  }
}

avl_node *
get_predecessor (avl_node * node)
{
  if (node->left) {
    node = node->left;
    while (node->right) {
      node = node->right;
    }
    return node;
  } else {
    avl_node * child = node;
    while (node->parent) {
      node = node->parent;
      if (child == node->right) {
	return node;
      }
      child = node;
    }
    return node;
  }
}

avl_node *
get_successor (avl_node * node)
{
  if (node->right) {
    node = node->right;
    while (node->left) {
      node = node->left;
    }
    return node;
  } else {
    avl_node * child = node;
    while (node->parent) {
      node = node->parent;
      if (child == node->left) {
	return node;
      }
      child = node;
    }
    return node;
  }
}

avl_node *
get_first_node(avl_tree *tree)
{
  avl_node *ptr=tree->root->right;

  if (ptr==NULL)
    return (avl_node *)NULL;

  while (ptr->left!=NULL)
    ptr=ptr->left;

  return ptr;
}

/* iterate a function over a range of indices, using get_predecessor */

int
iterate_index_range (avl_tree * tree,
		     avl_iter_index_fun_type iter_fun,
		     unsigned long low,
		     unsigned long high,
		     void * iter_arg)
{
  unsigned long m;
  unsigned long num_left;
  avl_node * node;

  if (high > tree->length) {
    return -1;
  }
  num_left = (high - low);
  /* find the <high-1>th node */
  m = high;
  node = tree->root->right;
  while (1) {
    if (m < GET_RANK (node)) {
      node = node->left;
    } else if (m > GET_RANK (node)) {
      m = m - GET_RANK (node);
      node = node->right;
    } else {
      break;
    }
  }
  /* call <iter_fun> on <node>, <get_pred(node)>, ... */
  while (num_left) {
    num_left = num_left - 1;
    if (iter_fun (num_left, node->key, iter_arg) != 0) {
      return -1;
    }
    node = get_predecessor (node);
  }
  return 0;
}

/* If <key> is present in the tree, return that key's node, and set <*index>
 * appropriately.  If not, return NULL, and set <*index> to the position
 * representing the closest preceding value.
 */

avl_node *
get_index_by_key (avl_tree * tree,
		  void * key,
		  unsigned long * index)
{
  avl_node * x = tree->root->right;
  unsigned long m = GET_RANK (x);

  while (1) {
    int compare_result = tree->compare_fun (tree->compare_arg, key, x->key);
    if (compare_result < 0) {
      if (x->left) {
	m = m - GET_RANK(x);
	x = x->left;
	m = m + GET_RANK(x);
      } else {
	*index = m - 2;
	return NULL;
      }
    } else if (compare_result > 0) {
      if (x->right) {
	x = x->right;
	m = m + GET_RANK(x);
      } else {
	*index = m - 1;
	return NULL;
      }
    } else {
      *index = m - 1;
      return x;
    }
  }
}

/* return the (low index, high index) pair that spans the given key */

int
get_span_by_key (avl_tree * tree,
		 void * key,
		 unsigned long * low,
		 unsigned long * high)
{
  unsigned long m, i, j;
  avl_node * node;

  node = get_index_by_key (tree, key, &m);

  /* did we find an exact match?
   * if so, we have to search left and right
   * to find the span, since we know nothing about
   * the arrangement of like keys.
   */
  if (node) {
    avl_node * left, * right;
    /* search left */
    left = get_predecessor (node);
    i = m;
    while ((i > 0) && (tree->compare_fun (tree->compare_arg, key, left->key) == 0)) {
      left = get_predecessor (left);
      i = i - 1;
    }
    /* search right */
    right = get_successor (node);
    j = m;
    while ((j <= tree->length) && (tree->compare_fun (tree->compare_arg, key, right->key) == 0)) {
      right = get_successor (right);
      j = j + 1;
    }
    *low = i;
    *high = j + 1;
    return 0;
  } else {
    *low = *high = m;
  }
  return 0;
}

/* return the (low index, high index) pair that spans the given key */

int
get_span_by_two_keys (avl_tree * tree,
		      void * low_key,
		      void * high_key,
		      unsigned long * low,
		      unsigned long * high)
{
  unsigned long i, j;
  avl_node * low_node, * high_node;
  int order;

  /* we may need to swap them */
  order = tree->compare_fun (tree->compare_arg, low_key, high_key);
  if (order > 0) {
    void * temp = low_key;
    low_key = high_key;
    high_key = temp;
  }

  low_node = get_index_by_key (tree, low_key, &i);
  high_node = get_index_by_key (tree, high_key, &j);

  if (low_node) {
    avl_node * left;
    /* search left */
    left = get_predecessor (low_node);
    while ((i > 0) && (tree->compare_fun (tree->compare_arg, low_key, left->key) == 0)) {
      left = get_predecessor (left);
      i = i - 1;
    }
  } else {
    i = i + 1;
  }
  if (high_node) {
    avl_node * right;
    /* search right */
    right = get_successor (high_node);
    while ((j <= tree->length) && (tree->compare_fun (tree->compare_arg, high_key, right->key) == 0)) {
      right = get_successor (right);
      j = j + 1;
    }
  } else {
    j = j + 1;
  }

  *low = i;
  *high = j;
  return 0;
}

		   
int
get_item_by_key_most (avl_tree * tree,
		      void * key,
		      void **value_address)
{
  avl_node * x = tree->root->right;
  *value_address = NULL;

  while (1) {
    int compare_result = tree->compare_fun (tree->compare_arg, key, x->key);

    if (compare_result == 0) {
      *value_address = x->key;
      return 0;
    } else if (compare_result < 0) {
      /* the given key is less than the current key */
      if (x->left) {
	x = x->left;
      } else {
	if (*value_address) 
	  return 0;
	else
	  return -1;
      }
    } else {
      /* the given key is more than the current key */
      /* save this value, it might end up being the right one! */
      *value_address = x->key;
      if (x->right) {
	/* there is a bigger entry */
	x = x->right;
      } else {
	if (*value_address) 
	  return 0;
	else
	  return -1;
      }
    }
  }
}

int
get_item_by_key_least (avl_tree * tree,
		       void * key,
		       void **value_address)
{
  avl_node * x = tree->root->right;
  *value_address = NULL;

  while (1) {
    int compare_result = tree->compare_fun (tree->compare_arg, key, x->key);
    if (compare_result == 0) {
      *value_address = x->key;
      return 0;  /* exact match */
    } else if (compare_result < 0) {
      /* the given key is less than the current key */
      /* save this value, it might end up being the right one! */
      *value_address = x->key;
      if (x->left) {
	x = x->left;
      } else {
	if (*value_address)  /* we have found a valid entry */
	  return 0; 
	else
	  return -1;
      }
    } else {
      if (x->right) {
	/* there is a bigger entry */
	x = x->right;
      } else {
	if (*value_address)  /* we have found a valid entry */
	  return 0; 
	else
	  return -1;
      }
    }
  }
}

#define MAX(X, Y)  ((X) > (Y) ? (X) : (Y))

long
verify_balance (avl_node * node)
{
  if (!node) {
    return 0;
  } else {
    long lh = verify_balance (node->left);
    long rh = verify_balance (node->right);
    if ((rh - lh) != GET_BALANCE(node)) {
      fprintf (stderr, "invalid balance at node %d\n", (int) node->key);
    }
    if (((lh - rh) > 1) || ((lh - rh) < -1)) {
      fprintf (stderr, "unbalanced at node %d\n", (int) node->key);
    }
    return (1 + MAX (lh, rh));
  }
}

void
verify_parent (avl_node * node, avl_node * parent)
{
  if (node->parent != parent) {
    fprintf (stderr, "invalid parent at node %d\n", (int) node->key);
  }
  if (node->left) {
    verify_parent (node->left, node);
  }
  if (node->right) {
    verify_parent (node->right, node);
  }
}

long
verify_rank (avl_node * node)
{
  if (!node) {
    return 0;
  } else {
    unsigned long num_left=0, num_right=0;
    if (node->left) {
      num_left = verify_rank (node->left);
    }
    if (node->right) {
      num_right = verify_rank (node->right);
    }
    if (GET_RANK (node) != num_left + 1) {
      fprintf (stderr, "invalid rank at node %d\n", (int) node->key);
    }
    return (num_left + num_right + 1);
  }
}

/* sanity-check the tree */

int
verify (avl_tree * tree)
{
  if (tree->length) {
    verify_balance (tree->root->right);
    verify_parent  (tree->root->right, tree->root);
    verify_rank    (tree->root->right);
  }
  return (0);
}

/*
 * These structures are accumulated on the stack during print_tree
 * and are used to keep track of the width and direction of each
 * branch in the history of a particular line <node>.
 */ 

typedef struct _link_node {
  struct _link_node	* parent;
  char			direction;
  int			width;
} link_node;  

char balance_chars[3] = {'\\', '-', '/'};

int
default_key_printer (char * buffer, void * key)
{
  return sprintf (buffer, "%p", key);
}  

/*
 * When traveling the family tree, a change in direction
 * indicates when to print a connector.  This is kinda crazy,
 * we use the stack to build a linked list, and then travel
 * it backwards using recursion.
 */

void
print_connectors (link_node * link)
{
  if (link->parent) {
    print_connectors (link->parent);
  }
  if (link->parent && (link->parent->direction != link->direction) && (link->parent->parent)) {
    int i;
    fprintf (stdout, "|");
    for (i=0; i < (link->width - 1); i++) {
      fprintf (stdout, " ");
    }
  } else {
    int i;
    for (i=0; i < (link->width); i++) {
      fprintf (stdout, " ");
    }
  }
}

/*
 * The <key_printer> function writes a representation of the
 * key into <buffer> (which is conveniently fixed in size to add
 * the spice of danger).  It should return the size of the
 * representation.
 */

void
print_node (avl_key_printer_fun_type key_printer,
	    avl_node * node,
	    link_node * link)
{
  char buffer[256];
  unsigned int width;
  link_node *here;
  width = key_printer (buffer, node->key);

  if (node->right) {
    /* link_node here = {link, 1, width+11}; */
    here=(link_node *)malloc(sizeof(link_node));
    here->parent=link;
    here->direction=1;
    here->width=width+11;
    print_node (key_printer, node->right, here);
  }
  print_connectors (link);
  fprintf (stdout, "+-[%c %s %03d]",
	   balance_chars[GET_BALANCE(node)+1],
	   buffer,
	   (int)GET_RANK(node));
  if (node->left || node->right) {
    fprintf (stdout, "-|\n");
  } else {
    fprintf (stdout, "\n");
  }
  if (node->left) {
    /* link_node here = {link, -1, width+11}; */
    here=(link_node *)malloc(sizeof(link_node));
    here->parent=link;
    here->direction=-1;
    here->width=width+11;
    print_node (key_printer, node->left, here);
  } 
}  

void
print_tree (avl_tree * tree, avl_key_printer_fun_type key_printer)
{
  link_node top = {NULL, 0, 0};
  if (!key_printer) {
    key_printer = default_key_printer;
  }
  if (tree->length) {
    print_node (key_printer, tree->root->right, &top);
  } else {
    fprintf (stdout, "<empty tree>\n");
  }  
}