/* libavl - manipulates AVL trees.
   Copyright (C) 1998, 1999 Free Software Foundation, Inc.

   This program is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public License as
   published by the Free Software Foundation; either version 2 of the
   License, or (at your option) any later version.

   This program is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
   02111-1307, USA.

   The author may be contacted at <pfaffben@pilot.msu.edu> on the
   Internet, or as Ben Pfaff, 12167 Airport Rd, DeWitt MI 48820, USA
   through more mundane means. */

/* This is file avltr.c in libavl. */

#if HAVE_CONFIG_H
#include <config.h>
#endif
#if SELF_TEST 
#include <limits.h>
#include <time.h>
#endif
#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
#include <assert.h>
#include "avltr.h"

/* Tag types. */
#define PLUS +1
#define MINUS -1

#if !__GCC__ && !defined (inline)
#define inline
#endif

void
print_structure (avltr_tree *tree, avltr_node *node, int level);

#if __GNUC__ >= 2
#define unused __attribute__ ((unused))
#else
#define unused
#endif

#ifdef HAVE_XMALLOC
void *xmalloc (size_t);
#else /* !HAVE_XMALLOC */
/* Allocates SIZE bytes of space using malloc().  Aborts if out of
   memory. */
static void *
xmalloc (size_t size)
{
  void *vp;
  if (size == 0)
    return NULL;
  vp = malloc (size);
  assert (vp != NULL);
  if (vp == NULL)
    {
      fprintf (stderr, "virtual memory exhausted\n");
      exit (EXIT_FAILURE);
    }
  return vp;
}
#endif /* !HAVE_XMALLOC */

/* Creates an AVL tree in arena OWNER (which can be NULL).  The arena
   is owned by the caller, not by the AVL tree.  CMP is a order
   function for the data to be stored in the tree.  PARAM is arbitrary
   data that becomes an argument to the comparison function. */
avltr_tree *
avltr_create (avl_comparison_func cmp, void *param)
{
  avltr_tree *tree;

  assert (cmp != NULL);
  tree = (avltr_tree *) xmalloc (sizeof (avltr_tree));

  tree->root.link[0] = NULL;
  tree->root.link[1] = &tree->root;
  tree->root.rtag = PLUS;
  tree->cmp = cmp;
  tree->count = 0;
  tree->param = param;

  return tree;
}

/* Destroy tree TREE.  Function FREE_FUNC is called for every node in
   the tree as it is destroyed.  

   No effect if the tree has an arena owner and free_func is NULL.
   The caller owns the arena and must destroy it itself.

   Do not attempt to reuse the tree after it has been freed.  Create a
   new one.  */
void
avltr_destroy (avltr_tree *tree, avl_node_func free_func)
{
  assert (tree != NULL);
  
  if (tree->root.link[0] != &tree->root)
    {
      /* Uses Knuth's Algorithm 2.3.1T as modified in exercise 13
	 (postorder traversal), further modified for right-threaded
	 trees. */
      
      /* T1. */
      avltr_node *an[AVL_MAX_HEIGHT];	/* Stack A: nodes. */
      char ab[AVL_MAX_HEIGHT];		/* Stack A: bits. */
      int ap = 0;			/* Stack A: height. */
      avltr_node *p = tree->root.link[0];

      for (;;)
	{
	  /* T2. */
	  while (p != NULL)
	    {
	      /* T3. */
	      ab[ap] = 0;
	      an[ap++] = p;
	      p = p->link[0];
	    }

	  /* T4. */
	  for (;;)
	    {
	      if (ap == 0)
		goto done;

	      p = an[--ap];
	      if (ab[ap] == 0)
		{
		  ab[ap++] = 1;
		  if (p->rtag == MINUS)
		    continue;
		  p = p->link[1];
		  break;
		}
      
	      if (free_func)
	      	free_func (p->data, tree->param);
	      free (p);
	    }
	}
    }

 done:
  free (tree);
}

/* avltr_destroy() with FREE_FUNC hardcoded as free(). */
void
avltr_free (avltr_tree *tree)
{
  avltr_destroy (tree, (avl_node_func) free);
}

/* Return the number of nodes in TREE. */
int
avltr_count (const avltr_tree *tree)
{
  assert (tree != NULL);
  return tree->count;
}

/* Copy the contents of TREE to a new tree in arena OWNER.  If COPY is
   non-NULL, then each data item is passed to function COPY, and the
   return values are inserted into the new tree; otherwise, the items
   are copied verbatim from the old tree to the new tree.  Returns the
   new tree. */
avltr_tree *
avltr_copy (const avltr_tree *tree, avl_copy_func copy)
{
  /* Knuth's Algorithm 2.3.1C (copying a binary tree).  Additionally
     uses Algorithm 2.3.1I (insertion into a threaded binary tree) and
     Algorithm 2.3.1 exercise 17 (preorder successor in threaded
     binary tree).  */

  avltr_tree *new_tree;

  const avltr_node *p;
  avltr_node *q;
  
  assert (tree != NULL);
  new_tree = avltr_create (tree->cmp, tree->param);
  new_tree->count = tree->count;
  p = &tree->root;
  if (p->link[0] == p)
    return new_tree;
  q = &new_tree->root;

  for (;;)
    {
      /* C4.  This is Algorithm 2.3.1 exercise 23 for insertion to the
       left in a right-threaded binary tree. */
      if (p->link[0] != NULL)
	{
	  avltr_node *r = (avltr_node *) xmalloc (sizeof (avltr_node));

	  q->link[0] = r;
	  r->link[0] = NULL;
	  r->link[1] = q;
	  r->rtag = MINUS;
	}

      /* C5: Find preorder successors of P and Q.  This is Algorithm
         2.3.1 exercise 17 but applies its actions to Q as well as
         P. */
      if (p->link[0] != NULL)
	{
	  p = p->link[0];
	  q = q->link[0];
	}
      else
	{
	  while (p->rtag == MINUS)
	    {
	      p = p->link[1];
	      q = q->link[1];
	    }
	  p = p->link[1];
	  q = q->link[1];
	}

      /* C6. */
      if (p == &tree->root)
	{
	  assert (q == &new_tree->root);
	  return new_tree;
	}
      
      /* C2.  This is Algorithm 2.3.1 exercise 23 for insertion to the
	 right in a right-threaded binary tree. */
      if (p->rtag == PLUS)
	{
	  avltr_node *r =  (avltr_node *) xmalloc (sizeof (avltr_node));

	  r->link[1] = q->link[1];
	  r->rtag = q->rtag;
	  q->link[1] = r;
	  q->rtag = PLUS;
	  r->link[0] = NULL;
	}

      /* C3. */
      q->bal = p->bal;
      if (copy == NULL)
	q->data = p->data;
      else
	q->data = copy (p->data, tree->param);
    }
}

/* Threads the unthreaded AVL tree TREE in-place, and returns TREE cast to
   avltr_tree *. */
avltr_tree *
avltr_thread (struct avl_tree *_tree)
{
  /* Uses Knuth's Algorithm 2.3.1 exercise 30 (thread an unthreaded
     tree, with Algorithm 2.3.1T (inorder traversal) for computing
     Q$. */

  avltr_tree *tree = (avltr_tree *) _tree;

  /* Algorithm T's variables. */
  avltr_node *an[AVL_MAX_HEIGHT];	/* Stack A: nodes. */
  avltr_node **ap;			/* Stack A: stack pointer. */
  avltr_node *tp;			/* P. */

  /* Algorithm L's variables. */
  avltr_node *p, *q;

  assert (tree != NULL);

  /* T1. */
  ap = an;
  tp = tree->root.link[0];

  /* L1. */
  q = &tree->root;
  q->link[1] = q;

  for (;;)
    {
      /* L2. */
      {
	/* T2. */
	while (tp != NULL)
	  {
	    /* T3. */
	    *ap++ = tp;
	    tp = tp->link[0];
	  }
      
	/* T4.  Modified to visit HEAD after fully traversing the
           tree. */
	if (ap == an)
	  tp = &tree->root;
	else
	  tp = *--ap;

	/* T5: Visit P. */
	p = tp;
      }

      /* L3. */
      if (q->link[1] == NULL)
	{
	  q->link[1] = p;
	  q->rtag = MINUS;
	}
      else
	q->rtag = PLUS;
  
      /* L4. */
      if (p == &tree->root)
	return tree;
      q = p;

      /* T5: Next. */
      tp = tp->link[1];
    }
}

/* Unthreads the threaded tree TREE in-place, and returns TREE cast to
   avl_tree *. */
struct avl_tree *
avltr_unthread (avltr_tree *tree)
{
  /* Uses Knuth's Algorithm 2.3.1T as modified in exercise 13
     (postorder traversal). */
      
  /* T1. */
  avltr_node *an[AVL_MAX_HEIGHT];	/* Stack A: nodes. */
  char ab[AVL_MAX_HEIGHT];		/* Stack A: bits. */
  int ap = 0;				/* Stack A: height. */
  avltr_node *p;

  assert (tree != NULL);
  p = tree->root.link[0];
  if (p != NULL)
    for (;;)
      {
	/* T2. */
	for (;;)
	  {
	    /* T3. */
	    ab[ap] = 0;
	    an[ap++] = p;
	    if (p->link[0] == NULL)
	      break;
	    p = p->link[0];
	  }

	/* T4. */
	for (;;)
	  {
	    if (ap == 0)
	      goto done;

	    p = an[--ap];
	    if (ab[ap] == 0)
	      {
		ab[ap++] = 1;
		if (p->rtag == MINUS)
		  continue;
		p = p->link[1];
		break;
	      }
      
	    if (p->rtag == MINUS)
	      p->link[1] = NULL;
	  }
      }
  else
    tree->root.link[0] = NULL;

 done:
  tree->root.link[1] = NULL;
  return (struct avl_tree *) tree;
}

/* Walk tree TREE in inorder, calling WALK_FUNC at each node.  Passes
   PARAM to WALK_FUNC.  */
void
avltr_walk (const avltr_tree *tree, avl_node_func walk_func, void *param)
{
  const avltr_node *p = &tree->root;

  /* Uses Knuth's algorithm 2.3.1D (threaded inorder successor). */
  assert (tree && walk_func);
  
  for (;;)
    {
      if (p->rtag == MINUS)
	p = p->link[1];
      else
	{
	  p = p->link[1];
	  while (p->link[0] != NULL)
	    p = p->link[0];
	}

      if (p == &tree->root)
	return;

      walk_func (p->data, param);
    }
}

/* Each call to this function for a given TREE and TRAV return the
   next item in the tree in inorder.  Initialize the first element of
   TRAV (init) to 0 before calling the first time.  Returns NULL when
   out of elements.  */
void *
avltr_traverse (const avltr_tree *tree, avltr_traverser *trav)
{
  const avltr_node *p;
  
  assert (tree && trav);

  if (trav->init == 0)
    {
      p = &tree->root;
      trav->init = 1;
    }
  else
    p = trav->p;

  /* Knuth's Algorithm 2.3.1S (threaded inorder successor). */
  if (p->rtag == MINUS)
    p = p->link[1];
  else
    {
      p = p->link[1];
      while (p->link[0] != NULL)
	p = p->link[0];
    }

  if (p == &tree->root)
    {
      trav->init = 0;
      return NULL;
    }
  else
    {
      trav->p = p;
      return (void *) p->data;
    }
}

/* Given ITEM, a pointer to a data item in TREE (or NULL), returns a
   pointer to the next item in the tree in comparison order, or NULL
   if ITEM is the last item. */
void **
avltr_next (const avltr_tree *tree, void **item)
{
  const avltr_node *p;

  assert (tree != NULL);
  if (item == NULL)
    p = &tree->root;
  else
    p = (avltr_node *) (((char *) item) - offsetof (avltr_node, data));

  /* Knuth's Algorithm 2.3.1S (threaded inorder successor). */
  if (p->rtag == MINUS)
    p = p->link[1];
  else
    {
      p = p->link[1];
      while (p->link[0] != NULL)
	p = p->link[0];
    }

  if (p == &tree->root)
    return NULL;

  return (void **) &p->data;
}

/* Search TREE for an item matching ITEM.  If found, returns a pointer
   to the address of the item.  If none is found, ITEM is inserted
   into the tree, and a pointer to the address of ITEM is returned.
   In either case, the pointer returned can be changed by the caller,
   or the returned data item can be directly edited, but the key data
   in the item must not be changed. */
void **
avltr_probe (avltr_tree *tree, void *item)
{
  /* Uses Knuth's Algorithm 6.2.3A (balanced tree search and
     insertion), modified for a right-threaded binary tree.  Caches
     results of comparisons.  In empirical tests this eliminates about
     25% of the comparisons seen under random insertions.  */

  /* A1. */
  avltr_node *t;
  avltr_node *s, *p, *q, *r;

  assert (tree != NULL);
  t = &tree->root;
  s = p = t->link[0];

  if (s == NULL)
    {
      tree->count++;
      assert (tree->count == 1);
      q = t->link[0] = (avltr_node *) xmalloc (sizeof (avltr_node));
      q->data = item;
      q->link[0] = NULL;
      q->link[1] = t;
      q->rtag = MINUS;
      q->bal = 0;
      return &q->data;
    }

  for (;;)
    {
      /* A2. */
      int diff = tree->cmp (item, p->data, tree->param);

      /* A3. */
      if (diff < 0)
	{
	  p->cache = 0;
	  q = p->link[0];
	  if (q == NULL)
	    {
	      /* Algorithm 2.3.1 exercise 23 for insertion to the left
		 in a right-threaded binary tree. */
	      q = (avltr_node *) xmalloc (sizeof (avltr_node));
	      p->link[0] = q;
	      q->link[0] = NULL;
	      q->link[1] = p;
	      q->rtag = MINUS;
	      break;
	    }
	}
      /* A4. */
      else if (diff > 0)
	{
	  p->cache = 1;
	  q = p->link[1];
	  if (p->rtag == MINUS)
	    {
	      /* Algorithm 2.3.1 exercise 23 for insertion to the right
		 in a right-threaded binary tree. */
	      q = (avltr_node *) xmalloc (sizeof (avltr_node));
	      q->link[1] = p->link[1];
	      q->rtag = p->rtag;
	      p->link[1] = q;
	      p->rtag = PLUS;
	      q->link[0] = NULL;
	      break;
	    }
	  assert (q != NULL);
	}
      else
	/* A2. */
	return &p->data;

      /* A3, A4. */
      if (q->bal != 0)
	t = p, s = q;
      p = q;
    }
  
  /* A5. */
  tree->count++;
  q->data = item;
  q->bal = 0;
  
  /* A6. */
  r = p = s->link[(int) s->cache];
  while (p != q)
    {
      p->bal = p->cache * 2 - 1;
      p = p->link[(int) p->cache];
    }

  /* A7. */
  if (s->cache == 0)
    {
      /* a = -1. */
      if (s->bal == 0)
	{
	  s->bal = -1;
	  return &q->data;
	}
      else if (s->bal == +1)
	{
	  s->bal = 0;
	  return &q->data;
	}

      assert (s->bal == -1);
      if (r->bal == -1)
	{
	  /* A8. */
	  p = r;
	  if (r->rtag == MINUS)
	    {
	      s->link[0] = NULL;
	      r->link[1] = s;
	      r->rtag = PLUS;
	    }
	  else
	    {
	      s->link[0] = r->link[1];
	      r->link[1] = s;
	    }
	  s->bal = r->bal = 0;
	}
      else
	{
	  /* A9. */
	  assert (r->bal == +1);
	  p = r->link[1];
	  r->link[1] = p->link[0];
	  p->link[0] = r;
	  s->link[0] = p->link[1];
	  p->link[1] = s;
	  if (p->bal == -1)
	    s->bal = 1, r->bal = 0;
	  else if (p->bal == 0)
	    s->bal = r->bal = 0;
	  else 
	    {
	      assert (p->bal == +1);
	      s->bal = 0, r->bal = -1;
	    }
	  p->bal = 0;
	  p->rtag = PLUS;
	  if (s->link[0] == s)
	    s->link[0] = NULL;
	  if (r->link[1] == NULL)
	    {
	      r->link[1] = p;
	      r->rtag = MINUS;
	    }
	}
    }
  else
    {
      /* a == +1. */
      if (s->bal == 0)
	{
	  s->bal = 1;
	  return &q->data;
	}
      else if (s->bal == -1)
	{
	  s->bal = 0;
	  return &q->data;
	}

      assert (s->bal == +1);
      if (r->bal == +1)
	{
	  /* A8. */
	  p = r;
	  if (r->link[0] == NULL)
	    {
	      s->rtag = MINUS;
	      r->link[0] = s;
	    }
	  else
	    {
	      s->link[1] = r->link[0];
	      s->rtag = PLUS;
	      r->link[0] = s;
	    }
	  s->bal = r->bal = 0;
	}
      else
	{
	  /* A9. */
	  assert (r->bal == -1);
	  p = r->link[0];
	  r->link[0] = p->link[1];
	  p->link[1] = r;
	  s->link[1] = p->link[0];
	  p->link[0] = s;
	  if (p->bal == +1)
	    s->bal = -1, r->bal = 0;
	  else if (p->bal == 0)
	    s->bal = r->bal = 0;
	  else 
	    {
	      assert (p->bal == -1);
	      s->bal = 0, r->bal = 1;
	    }
	  p->rtag = PLUS;
	  if (s->link[1] == NULL)
	    {
	      s->link[1] = p;
	      s->rtag = MINUS;
	    }
	  if (r->link[0] == r)
	    r->link[0] = NULL;
	  p->bal = 0;
	}
    }
		
  /* A10. */
  if (t != &tree->root && s == t->link[1])
    t->link[1] = p;
  else
    t->link[0] = p;

  return &q->data;
}
  
/* Search TREE for an item matching ITEM, and return a pointer to it
   if found. */
void **
avltr_find (const avltr_tree *tree, const void *item)
{
  const avltr_node *p;

  assert (tree != NULL);
  p = tree->root.link[0];
  if (p == NULL)
    return NULL;
  for (;;)
    {
      int diff = tree->cmp (item, p->data, tree->param);

      /* A3. */
      if (diff < 0)
	{
	  p = p->link[0];
	  if (p == NULL)
	    return NULL;
	}
      else if (diff > 0)
	{
	  if (p->rtag == MINUS)
	    return NULL;
	  p = p->link[1];
	}
      else
	return (void **) &p->data;
    }
}

/* Search TREE for an item close to the value of ITEM, and return it.
   This function will return a null pointer only if TREE is empty. */
void **
avltr_find_close (const avltr_tree *tree, const void *item)
{
  const avltr_node *p;

  assert (tree != NULL);
  p = tree->root.link[0];
  if (p == NULL)
    return NULL;
  for (;;)
    {
      int diff = tree->cmp (item, p->data, tree->param);

      /* A3. */
      if (diff < 0)
	{
	  if (p->link[0])
	    p = p->link[0];
	  else
	    return (void **) &p->data;
	}
      else if (diff > 0)
	{
	  if (p->rtag == MINUS)
	    return (void **) &p->data;
	  p = p->link[1];
	}
      else
	return (void **) &p->data;
    }
}

/* Searches AVL tree TREE for an item matching ITEM.  If found, the
   item is removed from the tree and the actual item found is returned
   to the caller.  If no item matching ITEM exists in the tree,
   returns NULL. */
void *
avltr_delete (avltr_tree *tree, const void *item)
{
  /* Uses my Algorithm DTR, which can be found at
     http://www.msu.edu/user/pfaffben/avl.  Algorithm DT is based on
     Knuth's Algorithms 6.2.2D (Tree deletion), 6.2.3A (Balanced tree
     search and insertion), 2.3.1I (Insertion into a threaded binary
     trees), and the notes on pages 465-466 of Vol. 3. */

  /* D1. */
  avltr_node *pa[AVL_MAX_HEIGHT];	/* Stack P: Nodes. */
  unsigned char a[AVL_MAX_HEIGHT];	/* Stack P: Bits. */
  int k = 1;				/* Stack P: Pointer. */
  
  avltr_node *p;

  assert (tree != NULL);

  a[0] = 0;
  pa[0] = &tree->root;
  p = tree->root.link[0];
  if (p == NULL)
    return NULL;
  for (;;)
    {
      /* D2. */
      int diff = tree->cmp (item, p->data, tree->param);

      if (diff == 0)
	break;

      /* D3, D4. */
      pa[k] = p;
      if (diff < 0)
	{
	  if (p->link[0] != NULL)
	    {
	      p = p->link[0];
	      a[k] = 0;
	    }
	  else
	    return NULL;
	}
      else if (diff > 0)
	{
	  if (p->rtag == PLUS)
	    {
	      p = p->link[1];
	      a[k] = 1;
	    }
	  else
	    return NULL;
	}

      k++;
    }
  tree->count--;
  
  item = p->data;

  {
    avltr_node *t = p;
    avltr_node **q = &pa[k - 1]->link[(int) a[k - 1]];

    /* D5. */
    if (t->rtag == MINUS)
      {
	if (t->link[0] != NULL)
	  {
	    avltr_node *const x = t->link[0];

	    *q = x;
	    (*q)->bal = 0;
	    if (x->rtag == MINUS)
	      {
		if (a[k - 1] == 1)
		  x->link[1] = t->link[1];
		else
		  x->link[1] = pa[k - 1];
	      }
	  }
	else
	  {
	    *q = t->link[a[k - 1]];
	    if (a[k - 1] == 0)
	      pa[k - 1]->link[0] = NULL;
	    else
	      pa[k - 1]->rtag = MINUS;
	  }
      }
    else
      {
	/* D6. */
	avltr_node *r = t->link[1];
	if (r->link[0] == NULL)
	  {
	    r->link[0] = t->link[0];
	    r->bal = t->bal;
	    if (r->link[0] != NULL)
	      {
		avltr_node *s = r->link[0];
		while (s->rtag == PLUS)
		  s = s->link[1];
		assert (s->rtag == MINUS);
		s->link[1] = r;
	      }
	    *q = r;
	    a[k] = 1;
	    pa[k++] = r;
	  }
	else
	  {
	    /* D7. */
	    avltr_node *s = r->link[0];

	    a[k] = 1;
	    pa[k++] = t;

	    a[k] = 0;
	    pa[k++] = r;
	    
	    /* D8. */
	    while (s->link[0] != NULL)
	      {
		r = s;
		s = r->link[0];
		a[k] = 0;
		pa[k++] = r;
	      }

	    /* D9. */
	    t->data = s->data;
	    if (s->rtag == PLUS)
	      r->link[0] = s->link[1];
	    else
	      r->link[0] = NULL;
	    p = s;
	  }
      }
  }

  free (p);

  assert (k > 0);
  /* D10. */
  while (--k)
    {
      avltr_node *const s = pa[k];

      if (a[k] == 0)
	{
	  avltr_node *const r = s->link[1];
	  
	  /* D10. */
	  if (s->bal == -1)
	    {
	      s->bal = 0;
	      continue;
	    }
	  else if (s->bal == 0)
	    {
	      s->bal = +1;
	      break;
	    }

	  assert (s->bal == +1);
	  if (s->rtag == MINUS || r->bal == 0)
	    {
	      /* D11. */
	      s->link[1] = r->link[0];
	      r->link[0] = s;
	      r->bal = -1;
	      pa[k - 1]->link[(int) a[k - 1]] = r;
	      break;
	    }
	  else if (r->bal == +1)
	    {
	      /* D12. */
	      if (r->link[0] != NULL)
		{
		  s->rtag = PLUS;
		  s->link[1] = r->link[0];
		}
	      else
		s->rtag = MINUS;
	      r->link[0] = s;
	      s->bal = r->bal = 0;
	      pa[k - 1]->link[a[k - 1]] = r;
	    }
	  else 
	    {
	      /* D13. */
	      assert (r->bal == -1);
	      p = r->link[0];
	      if (p->rtag == PLUS)
		r->link[0] = p->link[1];
	      else
		r->link[0] = NULL;
	      p->link[1] = r;
	      p->rtag = PLUS;
	      if (p->link[0] == NULL)
		{
		  s->link[1] = p;
		  s->rtag = MINUS;
		}
	      else
		{
		  s->link[1] = p->link[0];
		  s->rtag = PLUS;
		}
	      p->link[0] = s;
	      if (p->bal == +1)
		s->bal = -1, r->bal = 0;
	      else if (p->bal == 0)
		s->bal = r->bal = 0;
	      else
		{
		  assert (p->bal == -1);
		  s->bal = 0, r->bal = +1;
		}
	      p->bal = 0;
	      pa[k - 1]->link[(int) a[k - 1]] = p;
	      if (a[k - 1] == 1)
		pa[k - 1]->rtag = PLUS;
	    }
	}
      else
	{
	  avltr_node *const r = s->link[0];
	  
	  /* D10. */
	  if (s->bal == +1)
	    {
	      s->bal = 0;
	      continue;
	    }
	  else if (s->bal == 0)
	    {
	      s->bal = -1;
	      break;
	    }

	  assert (s->bal == -1);
	  if (s->link[0] == NULL || r->bal == 0)
	    {
	      /* D11. */
	      s->link[0] = r->link[1];
	      r->link[1] = s;
	      r->bal = +1;
	      pa[k - 1]->link[(int) a[k - 1]] = r;
	      break;
	    }
	  else if (r->bal == -1)
	    {
	      /* D12. */
	      if (r->rtag == PLUS)
		s->link[0] = r->link[1];
	      else
		s->link[0] = NULL;
	      r->link[1] = s;
	      r->rtag = PLUS;
	      s->bal = r->bal = 0;
	      pa[k - 1]->link[a[k - 1]] = r;
	    }
	  else 
	    {
	      /* D13. */
	      assert (r->bal == +1);
	      p = r->link[1];
	      if (p->link[0] != NULL)
		{
		  r->rtag = PLUS;
		  r->link[1] = p->link[0];
		}
	      else
		r->rtag = MINUS;
	      p->link[0] = r;
	      if (p->rtag == MINUS)
		s->link[0] = NULL;
	      else
		s->link[0] = p->link[1];
	      p->link[1] = s;
	      p->rtag = PLUS;
	      if (p->bal == -1)
		s->bal = +1, r->bal = 0;
	      else if (p->bal == 0)
		s->bal = r->bal = 0;
	      else
		{
		  assert (p->bal == +1);
		  s->bal = 0, r->bal = -1;
		}
	      p->bal = 0;
	      if (a[k - 1] == 1)
		pa[k - 1]->rtag = PLUS;
	      pa[k - 1]->link[(int) a[k - 1]] = p;
	    }
	}
    }
      
  return (void *) item;
}

/* Inserts ITEM into TREE.  Returns NULL if the item was inserted,
   otherwise a pointer to the duplicate item. */
void *
avltr_insert (avltr_tree *tree, void *item)
{
  void **p;
  
  assert (tree != NULL);
  
  p = avltr_probe (tree, item);
  return (*p == item) ? NULL : *p;
}

/* If ITEM does not exist in TREE, inserts it and returns NULL.  If a
   matching item does exist, it is replaced by ITEM and the item
   replaced is returned.  The caller is responsible for freeing the
   item returned. */
void *
avltr_replace (avltr_tree *tree, void *item)
{
  void **p;

  assert (tree != NULL);
  
  p = avltr_probe (tree, item);
  if (*p == item)
    return NULL;
  else
    {
      void *r = *p;
      *p = item;
      return r;
    }
}

/* Delete ITEM from TREE when you know that ITEM must be in TREE.  For
   debugging purposes. */
void *
(avltr_force_delete) (avltr_tree *tree, void *item)
{
  void *found = avltr_delete (tree, item);
  assert (found != NULL);
  return found;
}

#if SELF_TEST

/* Size of the tree used for testing. */
#define TREE_SIZE 1024

/* Used to flag delayed aborting. */
int done = 0;

/* Count the number of nodes in TREE below and including NODE. */
int
count (avltr_tree *tree, avltr_node *node)
{
  int n = 1;
  if (node->link[0] != NULL)
    n += count (tree, node->link[0]);
  if (node->rtag == PLUS)
    n += count (tree, node->link[1]);
  return n;
}

/* Print the structure of node NODE of an avl tree, which is LEVEL
   levels from the top of the tree.  Uses different delimiters to
   visually distinguish levels. */
void
print_structure (avltr_tree *tree, avltr_node *node, int level)
{
  char lc[] = "([{<`";
  char rc[] = ")]}>'";

  if (node == NULL)
    {
      printf (" :nil");
      return;
    }
  else if (level >= 10)
    {
      printf ("Too deep, giving up.\n");
      done = 1;
      return;
    }
  else if (node == &tree->root)
    {
      printf (" root");
      return;
    }
  printf (" %c%d", lc[level % 5], (int) node->data);
  fflush (stdout);

  print_structure (tree, node->link[0], level + 1);
  fflush (stdout);

  if (node->rtag == PLUS)
    print_structure (tree, node->link[1], level + 1);
  else if (node->link[1] != &tree->root)
    printf (" :%d", (int) node->link[1]->data);
  else
    printf (" :r");
  fflush (stdout);

  printf ("%c", rc[level % 5]);
  fflush (stdout);
}

/* Compare two integers A and B and return a strcmp()-type result. */
int
compare_ints (const void *a, const void *b, void *param unused)
{
  return ((int) a) - ((int) b);
}

/* Print the value of integer A. */
void
print_int (void *a, void *param unused)
{
  printf (" %d", (int) a);
}

/* Linearly print contents of TREE. */
void
print_contents (avltr_tree *tree)
{
  avltr_walk (tree, print_int, NULL);
  printf ("\n");
}

/* Examine NODE in a avl tree.  *COUNT is increased by the number of
   nodes in the tree, including the current one.  If the node is the
   root of the tree, PARENT should be INT_MIN, otherwise it should be
   the parent node value.  DIR is the direction that the current node
   is linked from the parent: -1 for left child, +1 for right child;
   it is not used if PARENT is INT_MIN.  Returns the height of the
   tree rooted at NODE. */
int
recurse_tree (avltr_tree *tree, avltr_node *node, int *count, int parent,
	      int dir, unsigned char *nodes, unsigned char *threads)
{
  if (node != NULL && node != &tree->root) 
    {
      int d = (int) node->data;
      int nl = 0;
      int nr = 0;

      (*count)++;

      assert (d >= 0 && d < TREE_SIZE);
      if (nodes[d / 8] & (1 << (d % 8)))
	{
	  printf (" Arrived at node %d by two different paths.\n", d);
	  done = 1;
	}
      else
	nodes[d / 8] |= 1 << (d % 8);

      if (node->link[0] != NULL)
	nl = recurse_tree (tree, node->link[0], count, d, -1, nodes, threads);

      if (node->rtag == PLUS)
	{
	  if (node->link[1] == NULL)
	    {
	      printf (" Null thread link.\n");
	      done = 1;
	    }
	  nr = recurse_tree (tree, node->link[1], count, d, 1, nodes, threads);
	}
      else if (node->link[1] != &tree->root)
	{
	  int dr = (int) node->link[1]->data;
	  assert (dr >= 0 && dr < TREE_SIZE);
	  if (threads[dr / 8] & (1 << dr % 8))
	    {
	      printf (" Multiple threads to node %d.\n", d);
	      done = 1;
	    }
	  threads[dr / 8] |= 1 << (dr % 8);
	}

      if (nr - nl != node->bal)
	{
	  printf (" Node %d has incorrect balance: right height=%d, "
		  "left height=%d, difference=%d, but balance factor=%d.\n",
		  d, nr, nl, nr - nl, node->bal);
	  done = 1;
	}
      
      if (node->bal < -1 || node->bal > 1)
	{
	  printf (" Node %d has invalid balance factor %d.\n", d, node->bal);
	  done = 1;
	}
      
      if (parent != INT_MIN)
	{
	  assert (dir == -1 || dir == +1);
	  if (dir == -1 && d > parent)
	    {
	      printf (" Node %d is smaller than its left child %d.\n",
		      parent, d);
	      done = 1;
	    }
	  else if (dir == +1 && d < parent)
	    {
	      printf (" Node %d is larger than its right child %d.\n",
		      parent, d);
	      done = 1;
	    }
	}
      assert (node->bal >= -1 && node->bal <= 1);
      return 1 + (nl > nr ? nl : nr);
    }
  else return 0;
}

/* Check that everything about TREE is kosher. */
void
verify_tree (avltr_tree *tree)
{
  {
    unsigned char nodes[(TREE_SIZE + 7) / 8];
    unsigned char threads[(TREE_SIZE + 7) / 8];

    int count = 0;
    int i;
    
    memset (nodes, 0, (TREE_SIZE + 7) / 8);
    memset (threads, 0, (TREE_SIZE + 7) / 8);
  
    recurse_tree (tree, tree->root.link[0], &count, INT_MIN, 0, nodes,
		  threads);
    
    if (count != tree->count)
      {
	printf (" Tree should have %d nodes, but tree count by recursive "
		"descent is %d.\n", tree->count, count);
	done = 1;
      }

    for (i = 0; i < TREE_SIZE; i++)
      {
	int thread = threads[i / 8] & (1 << (i % 8));
	int node = nodes[i / 8] & (1 << (i % 8));

	if (thread && !node)
	  {
	    printf (" A thread leads to ``node'' %d, "
		    "which is not in the tree.", i);
	    done = 1;
	  }
      }
  }

  /* Check threads. */
  {
    int count = 0;
    int last = INT_MIN;
    void **data = NULL;
  
    while (NULL != (data = avltr_next (tree, data)))
      {
	if (((int) *data) < last)
	  {
	    printf (" Misordered right threads.\n");
	    abort ();
	  }
	else if (((int) *data) == last)
	  {
	    printf (" Loop in right threads detected on %d.\n", last);
	    abort ();
	  }
	last = (int) *data;
	count++;
      }

    if (count != tree->count)
      {
	printf (" Tree should have %d nodes, but tree count by right threads "
		"is %d.\n", tree->count, count);
	done = 1;
      }
  }

  if (done)
    abort ();
}

/* Arrange the N elements of ARRAY in random order. */
void
shuffle (int *array, int n)
{
  int i;
  
  for (i = 0; i < n; i++)
    {
      int j = i + rand () % (n - i);
      int t = array[j];
      array[j] = array[i];
      array[i] = t;
    }
}

/* Compares avl trees rooted at A and B, making sure that they are
   identical. */
void
compare_trees (avltr_node *a, avltr_node *b)
{
  int diff = 0;
  
  assert (a && b);
  
  /* Separating these conditions makes it easier to pinpoint bad data
     under a memory debugger like Checker because each test is a
     separate statement. */
  diff |= a->data != b->data;
  diff |= a->bal != b->bal;
  diff |= ((a->link[0] != NULL) ^ (b->link[0] != NULL));
  diff |= ((a->rtag == PLUS) ^ (b->rtag == PLUS));
  if (diff)
    {
      printf (" Copied nodes differ: %d b=%d a->bal=%d b->bal=%d a:",
	      (int) a->data, (int) b->data, a->bal, b->bal);
      if (a->link[0])
	printf ("l");
      if (a->link[1])
	printf ("r");
      printf (" b:");
      if (b->link[0])
	printf ("l");
      if (b->link[1])
	printf ("r");
      printf ("\n");
      abort ();
    }
  if (a->link[0] != NULL)
    compare_trees (a->link[0], b->link[0]);
  if (a->rtag == PLUS)
    compare_trees (a->link[1], b->link[1]);
}

/* Simple stress test procedure for the AVL tree routines.  Does the
   following:

   * Generate a random number seed.  By default this is generated from
   the current time.  You can also pass a seed value on the command
   line if you want to test the same case.  The seed value is
   displayed.

   * Create a tree and insert the integers from 0 up to TREE_SIZE - 1
   into it, in random order.  Verify the tree structure after each
   insertion.
   
   * Remove each integer from the tree, in a different random order.
   After each deletion, verify the tree structure; also, make a copy
   of the tree into a new tree, verify the copy and compare it to the
   original, then destroy the copy.

   * Destroy the tree, increment the random seed value, and start over.

   If you make any modifications to the avl tree routines, then you
   might want to insert some calls to print_structure() at strategic
   places in order to be able to see what's really going on.  Also,
   memory debuggers like Checker or Purify are very handy. */
#define N_ITERATIONS 16
int
main (int argc, char **argv)
{
  int array[TREE_SIZE];
  int seed;
  int iteration;
  
  if (argc == 2)
    seed = atoi (argv[1]);
  else
    seed = time (0) * 257 % 32768;

  fputs ("Testing avltr...\n", stdout);

  for (iteration = 1; iteration <= N_ITERATIONS; iteration++)
    {
      avltr_tree *tree;
      int i;
      
      printf ("Iteration %4d/%4d: seed=%5d", iteration, N_ITERATIONS, seed);
      fflush (stdout);
      
      srand (seed++);

      for (i = 0; i < TREE_SIZE; i++)
	array[i] = i;
      shuffle (array, TREE_SIZE);
      
      tree = avltr_create (compare_ints, NULL);
      for (i = 0; i < TREE_SIZE; i++)
	  avltr_force_insert (tree, (void *) (array[i]));
      verify_tree (tree);

      shuffle (array, TREE_SIZE);
      for (i = 0; i < TREE_SIZE; i++)
	{
	  avltr_tree *copy;

	  avltr_delete (tree, (void *) (array[i]));
	  verify_tree (tree);

	  copy = avltr_copy (tree, NULL);
	  verify_tree (copy);
	  if (tree->root.link[0] != NULL)
	    compare_trees (tree->root.link[0], copy->root.link[0]);
	  else if (copy->root.link[0] != NULL)
	    {
	      printf (" Empty tree results in nonempty copy.\n");
	      abort ();
	    }
	  avltr_destroy (copy, NULL);

	  if (i % 128 == 0)
	    {
	      putchar ('.');
	      fflush (stdout);
	    }
	}
      fputs (" good.\n", stdout);

      avltr_destroy (tree, NULL);
    }
  
  return 0;
}
#endif /* SELF_TEST */

/*
  Local variables:
  compile-command: "gcc -DSELF_TEST=1 -W -Wall -I. -o ./avltr-test avltr.c"
  End:
*/