/*

 * Copyright (C) 1995-1997 by Sam Rushing <rushing@nightmare.com>

 * 

 *                         All Rights Reserved

 * 

 * Permission to use, copy, modify, and distribute this software and

 * its documentation for any purpose and without fee is hereby

 * granted, provided that the above copyright notice appear in all

 * copies and that both that copyright notice and this permission

 * notice appear in supporting documentation, and that the name of Sam

 * Rushing not be used in advertising or publicity pertaining to

 * distribution of the software without specific, written prior

 * permission.

 * 

 * SAM RUSHING DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,

 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN

 * NO EVENT SHALL SAM RUSHING BE LIABLE FOR ANY SPECIAL, INDIRECT OR

 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS

 * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,

 * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN

 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

 *

 */

/* $Id: avl.c,v 1.11 2004/01/27 02:16:25 karl Exp $ */

/*

 * This is a fairly straightfoward translation of a prototype

 * written in python, 'avl_tree.py'. Read that file first.

 */

#ifdef HAVE_CONFIG_H

 #include <config.h>

#endif

#include <stdio.h>

#include <stdlib.h>

#include "avl.h"

avl_node *

avl_node_new (void *        key,

          avl_node *    parent)

{

  avl_node * node = (avl_node *) malloc (sizeof (avl_node));

  if (!node) {

    return NULL;

  } else {

    node->parent = parent;

    node->key = key;

    node->left = NULL;

    node->right = NULL;

    node->rank_and_balance = 0;

    AVL_SET_BALANCE (node, 0);

    AVL_SET_RANK (node, 1);

    thread_rwlock_create(&node->rwlock);

    return node;

  }

}         

avl_tree *

avl_tree_new (avl_key_compare_fun_type compare_fun,

          void * compare_arg)

{

  avl_tree * t = (avl_tree *) malloc (sizeof (avl_tree));

  if (!t) {

    return NULL;

  } else {

    avl_node * root = avl_node_new((void *)NULL, (avl_node *) NULL);

    if (!root) {

      free (t);

      return NULL;

    } else {

      t->root = root;

      t->height = 0;

      t->length = 0;

      t->compare_fun = compare_fun;

      t->compare_arg = compare_arg;

      thread_rwlock_create(&t->rwlock);

      return t;

    }

  }

}

static void

avl_tree_free_helper (avl_node * node, avl_free_key_fun_type free_key_fun)

{

  if (node->left) {

    avl_tree_free_helper (node->left, free_key_fun);

  }

  if (free_key_fun)

      free_key_fun (node->key);

  if (node->right) {

    avl_tree_free_helper (node->right, free_key_fun);

  }

  thread_rwlock_destroy (&node->rwlock);

  free (node);

}

void

avl_tree_free (avl_tree * tree, avl_free_key_fun_type free_key_fun)

{

  if (tree->length) {

    avl_tree_free_helper (tree->root->right, free_key_fun);

  }

  if (tree->root) {

    thread_rwlock_destroy(&tree->root->rwlock);

    free (tree->root);

  }

  thread_rwlock_destroy(&tree->rwlock);

  free (tree);

}

int

avl_insert (avl_tree * ob,

           void * key)

{

  if (!(ob->root->right)) {

    avl_node * node = avl_node_new (key, ob->root);

    if (!node) {

      return -1;

    } else {

      ob->root->right = node;

      ob->length = ob->length + 1;

      return 0;

    }

  } else { /* not self.right == None */

    avl_node *t, *p, *s, *q, *r;

    int a;

    t = ob->root;

    s = p = t->right;

    while (1) {

      if (ob->compare_fun (ob->compare_arg, key, p->key) < 1) {

    /* move left */

    AVL_SET_RANK (p, (AVL_GET_RANK (p) + 1));

    q = p->left;

    if (!q) {

      /* insert */

      avl_node * q_node = avl_node_new (key, p);

      if (!q_node) {

        return (-1);

      } else {

        q = q_node;

        p->left = q;

        break;

      }

    } else if (AVL_GET_BALANCE(q)) {

      t = p;

      s = q;

    }

    p = q;

      } else {

    /* move right */

    q = p->right;

    if (!q) {

      /* insert */

      avl_node * q_node = avl_node_new (key, p);

      if (!q_node) {

        return -1;

      } else {

        q = q_node;

        p->right = q;

        break;

      }

    } else if (AVL_GET_BALANCE(q)) {

      t = p;

      s = q;

    }

    p = q;

      }

    }

    ob->length = ob->length + 1;

    /* adjust balance factors */

    if (ob->compare_fun (ob->compare_arg, key, s->key) < 1) {

      r = p = s->left;

    } else {

      r = p = s->right;

    }

    while (p != q) {

      if (ob->compare_fun (ob->compare_arg, key, p->key) < 1) {

    AVL_SET_BALANCE (p, -1);

    p = p->left;

      } else {

    AVL_SET_BALANCE (p, +1);

    p = p->right;

      }

    }

    /* balancing act */

    if (ob->compare_fun (ob->compare_arg, key, s->key) < 1) {

      a = -1;

    } else {

      a = +1;

    }

    if (AVL_GET_BALANCE (s) == 0) {

      AVL_SET_BALANCE (s, a);

      ob->height = ob->height + 1;

      return 0;

    } else if (AVL_GET_BALANCE (s) == -a) {

      AVL_SET_BALANCE (s, 0);

      return 0;

    } else if (AVL_GET_BALANCE(s) == a) {

      if (AVL_GET_BALANCE (r) == a) {

    /* single rotation */

    p = r;

    if (a == -1) {

      s->left = r->right;

      if (r->right) {

        r->right->parent = s;

      }

      r->right = s;

      s->parent = r;

      AVL_SET_RANK (s, (AVL_GET_RANK (s) - AVL_GET_RANK (r)));

    } else {

      s->right = r->left;

      if (r->left) {

        r->left->parent = s;

      }

      r->left = s;

      s->parent = r;

      AVL_SET_RANK (r, (AVL_GET_RANK (r) + AVL_GET_RANK (s)));

    }

    AVL_SET_BALANCE (s, 0);

    AVL_SET_BALANCE (r, 0);

      } else if (AVL_GET_BALANCE (r) == -a) {

    /* double rotation */

    if (a == -1) {

      p = r->right;

      r->right = p->left;

      if (p->left) {

        p->left->parent = r;

      }

      p->left = r;

      r->parent = p;

      s->left = p->right;

      if (p->right) {

        p->right->parent = s;

      }

      p->right = s;

      s->parent = p;

      AVL_SET_RANK (p, (AVL_GET_RANK (p) + AVL_GET_RANK (r)));

      AVL_SET_RANK (s, (AVL_GET_RANK (s) - AVL_GET_RANK (p)));

    } else {

      p = r->left;

      r->left = p->right;

      if (p->right) {

        p->right->parent = r;

      }

      p->right = r;

      r->parent = p;

      s->right = p->left;

      if (p->left) {

        p->left->parent = s;

      }

      p->left = s;

      s->parent = p;

      AVL_SET_RANK (r, (AVL_GET_RANK (r) - AVL_GET_RANK (p)));

      AVL_SET_RANK (p, (AVL_GET_RANK (p) + AVL_GET_RANK (s)));

    }

    if (AVL_GET_BALANCE (p) == a) {

      AVL_SET_BALANCE (s, -a);

      AVL_SET_BALANCE (r, 0);

    } else if (AVL_GET_BALANCE (p) == -a) {

      AVL_SET_BALANCE (s, 0);

      AVL_SET_BALANCE (r, a);

    } else {

      AVL_SET_BALANCE (s, 0);

      AVL_SET_BALANCE (r, 0);

    }

    AVL_SET_BALANCE (p, 0);

      }

      /* finishing touch */

      if (s == t->right) {

    t->right = p;

      } else {

    t->left = p;

      }

      p->parent = t;

    }

  }

  return 0;

}

int

avl_get_by_index (avl_tree * tree,

           unsigned long index,

           void ** value_address)

{

  avl_node * p = tree->root->right;

  unsigned long m = index + 1;

  while (1) {

    if (!p) {

      return -1;

    }

    if (m < AVL_GET_RANK(p)) {

      p = p->left;

    } else if (m > AVL_GET_RANK(p)) {

      m = m - AVL_GET_RANK(p);

      p = p->right;

    } else {

      *value_address = p->key;

      return 0;

    }

  }

}

int

avl_get_by_key (avl_tree * tree,

         void * key,

         void **value_address)

{

  avl_node * x = tree->root->right;

  if (!x) {

    return -1;

  }

  while (1) {

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

    if (compare_result < 0) {

      if (x->left) {

    x = x->left;

      } else {

    return -1;

      }

    } else if (compare_result > 0) {

      if (x->right) {

    x = x->right;

      } else {

    return -1;

      }

    } else {

      *value_address = x->key;

      return 0;

    }

  }

}

int avl_delete(avl_tree *tree, void *key, avl_free_key_fun_type free_key_fun)

{

  avl_node *x, *y, *p, *q, *r, *top, *x_child;

  int shortened_side, shorter;

  x = tree->root->right;

  if (!x) {

    return -1;

  }

  while (1) {

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

    if (compare_result < 0) {

      /* move left

       * We will be deleting from the left, adjust this node's

       * rank accordingly

       */

      AVL_SET_RANK (x, (AVL_GET_RANK(x) - 1));

      if (x->left) {

    x = x->left;

      } else {

    /* Oops! now we have to undo the rank changes

     * all the way up the tree

     */

    AVL_SET_RANK(x, (AVL_GET_RANK (x) + 1));

    while (x != tree->root->right) {

      if (x->parent->left == x) {

        AVL_SET_RANK(x->parent, (AVL_GET_RANK (x->parent) + 1));

      }

      x = x->parent;

    }

    return -1;        /* key not in tree */

      }

    } else if (compare_result > 0) {

      /* move right */

      if (x->right) {

    x = x->right;

      } else {

    AVL_SET_RANK(x, (AVL_GET_RANK (x) + 1));

    while (x != tree->root->right) {

      if (x->parent->left == x) {

        AVL_SET_RANK(x->parent, (AVL_GET_RANK (x->parent) + 1));

      }

      x = x->parent;

    }

    return -1;        /* key not in tree */

      }

    } else {

      break;

    }

  }

  if (x->left && x->right) {

    void * temp_key;

    /* The complicated case.

     * reduce this to the simple case where we are deleting

     * a node with at most one child.

     */

    /* find the immediate predecessor <y> */

    y = x->left;

    while (y->right) {

      y = y->right;

    }

    /* swap <x> with <y> */

    temp_key = x->key;

    x->key = y->key;

    y->key = temp_key;

    /* we know <x>'s left subtree lost a node because that's

     * where we took it from

     */

    AVL_SET_RANK (x, (AVL_GET_RANK (x) - 1));

    x = y;

  }

  /* now <x> has at most one child

   * scoot this child into the place of <x>

   */

  if (x->left) {

    x_child = x->left;

    x_child->parent = x->parent;

  } else if (x->right) {

    x_child = x->right;

    x_child->parent = x->parent;

  } else {

    x_child = NULL;

  }

  /* now tell <x>'s parent that a grandchild became a child */

  if (x == x->parent->left) {

    x->parent->left = x_child;

    shortened_side = -1;

  } else {

    x->parent->right = x_child;

    shortened_side = +1;

  }

  /*

   * the height of the subtree <x>

   * has now been shortened.  climb back up

   * the tree, rotating when necessary to adjust

   * for the change.

   */

  shorter = 1;

  p = x->parent;

  /* return the key and node to storage */

  if (free_key_fun)

      free_key_fun (x->key);

  thread_rwlock_destroy (&x->rwlock);

  free (x);

  while (shorter && p->parent) {

    /* case 1: height unchanged */

    if (AVL_GET_BALANCE(p) == 0) {

      if (shortened_side == -1) {

    /* we removed a left child, the tree is now heavier

     * on the right

     */

    AVL_SET_BALANCE (p, +1);

      } else {

    /* we removed a right child, the tree is now heavier

     * on the left

     */

    AVL_SET_BALANCE (p, -1);

      }

      shorter = 0;

    } else if (AVL_GET_BALANCE (p) == shortened_side) {

      /* case 2: taller subtree shortened, height reduced */

      AVL_SET_BALANCE (p, 0);

    } else {

      /* case 3: shorter subtree shortened */

      top = p->parent;

      /* set <q> to the taller of the two subtrees of 
 */

      if (shortened_side == 1) {

    q = p->left;

      } else {

    q = p->right;

      }

      if (AVL_GET_BALANCE (q) == 0) {

    /* case 3a: height unchanged */

    if (shortened_side == -1) {

      /* single rotate left */

      q->parent = p->parent;

      p->right = q->left;

      if (q->left) {

        q->left->parent = p;

      }

      q->left = p;

      p->parent = q;

      AVL_SET_RANK (q, (AVL_GET_RANK (q) + AVL_GET_RANK (p)));

    } else {

      /* single rotate right */

      q->parent = p->parent;

      p->left = q->right;

      if (q->right) {

        q->right->parent = p;

      }

      q->right = p;

      p->parent = q;

      AVL_SET_RANK (p, (AVL_GET_RANK (p) - AVL_GET_RANK (q)));

    }

    shorter = 0;

    AVL_SET_BALANCE (q, shortened_side);

    AVL_SET_BALANCE (p, (- shortened_side));

      } else if (AVL_GET_BALANCE (q) == AVL_GET_BALANCE (p)) {

    /* case 3b: height reduced */

    if (shortened_side == -1) {

      /* single rotate left */

      q->parent = p->parent;

      p->right = q->left;

      if (q->left) {

        q->left->parent = p;

      }

      q->left = p;

      p->parent = q;

      AVL_SET_RANK (q, (AVL_GET_RANK (q) + AVL_GET_RANK (p)));

    } else {

      /* single rotate right */

      q->parent = p->parent;

      p->left = q->right;

      if (q->right) {

        q->right->parent = p;

      }

      q->right = p;

      p->parent = q;

      AVL_SET_RANK (p, (AVL_GET_RANK (p) - AVL_GET_RANK (q)));

    }

    shorter = 1;

    AVL_SET_BALANCE (q, 0);

    AVL_SET_BALANCE (p, 0);

      } else {

    /* case 3c: height reduced, balance factors opposite */

    if (shortened_side == 1) {

      /* double rotate right */

      /* first, a left rotation around q */

      r = q->right;

      r->parent = p->parent;

      q->right = r->left;

      if (r->left) {

        r->left->parent = q;

      }

      r->left = q;

      q->parent = r;

      /* now, a right rotation around p */

      p->left = r->right;

      if (r->right) {

        r->right->parent = p;

      }

      r->right = p;

      p->parent = r;

      AVL_SET_RANK (r, (AVL_GET_RANK (r) + AVL_GET_RANK (q)));

      AVL_SET_RANK (p, (AVL_GET_RANK (p) - AVL_GET_RANK (r)));

    } else {

      /* double rotate left */

      /* first, a right rotation around q */

      r = q->left;

      r->parent = p->parent;

      q->left = r->right;

      if (r->right) {

        r->right->parent = q;

      }

      r->right = q;

      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;

      AVL_SET_RANK (q, (AVL_GET_RANK (q) - AVL_GET_RANK (r)));

      AVL_SET_RANK (r, (AVL_GET_RANK (r) + AVL_GET_RANK (p)));        

    }

    if (AVL_GET_BALANCE (r) == shortened_side) {

      AVL_SET_BALANCE (q, (- shortened_side));

      AVL_SET_BALANCE (p, 0);

    } else if (AVL_GET_BALANCE (r) == (- shortened_side)) {

      AVL_SET_BALANCE (q, 0);

      AVL_SET_BALANCE (p, shortened_side);

    } else {

      AVL_SET_BALANCE (q, 0);

      AVL_SET_BALANCE (p, 0);

    }

    AVL_SET_BALANCE (r, 0);

    q = r;

      }

      /* a rotation has caused <q> (or <r> in case 3c) to become

       * the root.  let 
'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);

}

static int

avl_iterate_inorder_helper (avl_node * node,

            avl_iter_fun_type iter_fun,

            void * iter_arg)

{

  int result;

  if (node->left) {

    result = avl_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 = avl_iterate_inorder_helper (node->right, iter_fun, iter_arg);

    if (result != 0) {

      return result;

    }

  }

  return 0;

}

int

avl_iterate_inorder (avl_tree * tree,

         avl_iter_fun_type iter_fun,

         void * iter_arg)

{

  int result;

  if (tree->length) {

    result = avl_iterate_inorder_helper (tree->root->right, iter_fun, iter_arg);

    return (result);

  } else {

    return 0;

  }

}

avl_node *avl_get_first(avl_tree *tree)

{

    avl_node *node;

    node = tree->root->right;

    if (node == NULL || node->key == NULL) return NULL;

    while (node->left)

        node = node->left;

    return node;

}

avl_node *avl_get_prev(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->parent->key) {

            node = node->parent;

            if (child == node->right) {

                return node;

            }

            child = node;

        }

        return NULL;

    }

}

avl_node *avl_get_next(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->parent->key) {

            node = node->parent;

            if (child == node->left) {

                return node;

            }

            child = node;

        }

        return NULL;

    }

}

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

int

avl_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 < AVL_GET_RANK (node)) {

      node = node->left;

    } else if (m > AVL_GET_RANK (node)) {

      m = m - AVL_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 = avl_get_prev (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.

 */

static avl_node *

avl_get_index_by_key (avl_tree * tree,

          void * key,

          unsigned long * index)

{

  avl_node * x = tree->root->right;

  unsigned long m;

  if (!x) {

    return NULL;

  }

  m = AVL_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 - AVL_GET_RANK(x);

    x = x->left;

    m = m + AVL_GET_RANK(x);

      } else {

    *index = m - 2;

    return NULL;

      }

    } else if (compare_result > 0) {

      if (x->right) {

    x = x->right;

    m = m + AVL_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

avl_get_span_by_key (avl_tree * tree,

         void * key,

         unsigned long * low,

         unsigned long * high)

{

  unsigned long m, i, j;

  avl_node * node;

  node = avl_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 = avl_get_prev (node);

    i = m;

    while ((i > 0) && (tree->compare_fun (tree->compare_arg, key, left->key) == 0)) {

      left = avl_get_prev (left);

      i = i - 1;

    }

    /* search right */

    right = avl_get_next (node);

    j = m;

    while ((j <= tree->length) && (tree->compare_fun (tree->compare_arg, key, right->key) == 0)) {

      right = avl_get_next (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

avl_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 = avl_get_index_by_key (tree, low_key, &i);

  high_node = avl_get_index_by_key (tree, high_key, &j);

  if (low_node) {

    avl_node * left;

    /* search left */

    left = avl_get_prev (low_node);

    while ((i > 0) && (tree->compare_fun (tree->compare_arg, low_key, left->key) == 0)) {

      left = avl_get_prev (left);

      i = i - 1;

    }

  } else {

    i = i + 1;

  }