/*====================================================================*/
/*  FILE   :   @(#)r2btree.c	1.1  -  05/12/98 */
/*====================================================================*/
/*  PURPOSE:  Abstract Data Type implementation of a height balanced  */
/*	      binary tree.  This code was downloaded from the web and */
/*            used with permission.				      */
/*                                                                    */
/*  SYSTEM :  RECON II                                                */
/*                                                                    */
/*  USED BY:  main(), ReadTestData(), BuildCompList(), SelectComp(),  */
/*            and AnnotateSource().		                      */
/*                                                                    */
/*  HISTORY:                                                          */
/*  VER   DATE       AUTHOR        DESCRIPTION                        */
/*  1.00  20 Apr 98  A. Conwell    Added to recon
/*--------------------------------------------------------------------*/

/*
 * 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 2.6 1998/03/04 02:24:46 rushing Exp $ */

/*
 * This is a fairly straightfoward translation of a prototype
 * written in python, 'avl_tree.py'. Read that file first.
 */

#include <stdio.h>
#include <stdlib.h>

#include "r2btree.h"

avl_node *
new_avl_node (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;
    SET_BALANCE (node, 0);
    SET_RANK (node, 1);
    return node;
  }
}	     

avl_tree *
new_avl_tree (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 = new_avl_node((void *)NULL, (avl_node *) NULL);
    if (!root) {
      return NULL;
    } else {
      t->root = root;
      t->height = 0;
      t->length = 0;
      t->curr = (avl_node *)NULL;
      t->compare_fun = compare_fun;
      t->compare_arg = compare_arg;
      return t;
    }
  }
}
  
void
free_avl_tree_helper (avl_node * node, avl_free_key_fun_type free_key_fun)
{
  if (node->left) {
    free_avl_tree_helper (node->left, free_key_fun);
  }
  free_key_fun (node->key);
  if (node->right) {
    free_avl_tree_helper (node->right, free_key_fun);
  }
  free (node);
}

void
free_avl_tree (avl_tree * tree, avl_free_key_fun_type free_key_fun)
{
  if (tree->length) {
    free_avl_tree_helper (tree->root->right, free_key_fun);
  }
  if (tree->root) {
    free (tree->root);
  }
  free (tree);
}

int
insert_by_key (avl_tree * ob,
	       void * key)
{
  if (!(ob->root->right)) {
    avl_node * node = new_avl_node (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 */
	SET_RANK (p, (GET_RANK (p) + 1));
	q = p->left;
	if (!q) {
	  /* insert */
	  avl_node * q_node = new_avl_node (key, p);
	  if (!q_node) {
	    return (-1);
	  } else {
	    q = q_node;
	    p->left = q;
	    break;
	  }
	} else if (GET_BALANCE(q)) {
	  t = p;
	  s = q;
	}
	p = q;
      } else {
	/* move right */
	q = p->right;
	if (!q) {
	  /* insert */
	  avl_node * q_node = new_avl_node (key, p);
	  if (!q_node) {
	    return -1;
	  } else {
	    q = q_node;
	    p->right = q;
	    break;
	  }
	} else if (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) {
	SET_BALANCE (p, -1);
	p = p->left;
      } else {
	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 (GET_BALANCE (s) == 0) {
      SET_BALANCE (s, a);
      ob->height = ob->height + 1;
      return 0;
    } else if (GET_BALANCE (s) == -a) {
      SET_BALANCE (s, 0);
      return 0;
    } else if (GET_BALANCE(s) == a) {
      if (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;
	  SET_RANK (s, (GET_RANK (s) - GET_RANK (r)));
	} else {
	  s->right = r->left;
	  if (r->left) {
	    r->left->parent = s;
	  }
	  r->left = s;
	  s->parent = r;
	  SET_RANK (r, (GET_RANK (r) + GET_RANK (s)));
	}
	SET_BALANCE (s, 0);
	SET_BALANCE (r, 0);
      } else if (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;
	  SET_RANK (p, (GET_RANK (p) + GET_RANK (r)));
	  SET_RANK (s, (GET_RANK (s) - 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;
	  SET_RANK (r, (GET_RANK (r) - GET_RANK (p)));
	  SET_RANK (p, (GET_RANK (p) + GET_RANK (s)));
	}
	if (GET_BALANCE (p) == a) {
	  SET_BALANCE (s, -a);
	  SET_BALANCE (r, 0);
	} else if (GET_BALANCE (p) == -a) {
	  SET_BALANCE (s, 0);
	  SET_BALANCE (r, a);
	} else {
	  SET_BALANCE (s, 0);
	  SET_BALANCE (r, 0);
	}
	SET_BALANCE (p, 0);
      }
      /* finishing touch */
      if (s == t->right) {
	t->right = p;
      } else {
	t->left = p;
      }
      p->parent = t;
    }
  }
  return 0;
}

int
get_item_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 < GET_RANK(p)) {
      p = p->left;
    } else if (m > GET_RANK(p)) {
      m = m - GET_RANK(p);
      p = p->right;
    } else {
      *value_address = p->key;
      return 0;
    }
  }
}
		   
int
get_item_by_key (avl_tree * tree,
		 void * key,
		 void **value_address)
{
  avl_node * x = tree->root->right;

/*  Make sure that tree has some elements before going on. */
  if (x==NULL)
    return -1;
/*  Make sure key is something other than NULL! */
  if (key==NULL)
    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
remove_by_key (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;
  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
       */
      SET_RANK (x, (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
	 */
	SET_RANK(x, (GET_RANK (x) + 1));
	while (x != tree->root->right) {
	  if (x->parent->left == x) {
	    SET_RANK(x->parent, (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 {
	SET_RANK(x, (GET_RANK (x) + 1));
	while (x != tree->root->right) {
	  if (x->parent->left == x) {
	    SET_RANK(x->parent, (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
     */
    SET_RANK (x, (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 */
  free_key_fun (x->key);
  free (x);

  while (shorter && p->parent) {
    
    /* case 1: height unchanged */
    if (GET_BALANCE(p) == 0) {
      if (shortened_side == -1) {
	/* we removed a left child, the tree is now heavier
	 * on the right
	 */
	SET_BALANCE (p, +1);
      } else {
	/* we removed a right child, the tree is now heavier
	 * on the left
	 */
	SET_BALANCE (p, -1);
      }
      shorter = 0;
      
    } else if (GET_BALANCE (p) == shortened_side) {
      /* case 2: taller subtree shortened, height reduced */
      SET_BALANCE (p, 0);
    } else {
      /* case 3: shorter subtree shortened */
      top = p->parent;
      /* set <q> to the taller of the two subtrees of <p> */
      if (shortened_side == 1) {
	q = p->left;
      } else {
	q = p->right;
      }
      if (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;
	  SET_RANK (q, (GET_RANK (q) + 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;
	  SET_RANK (p, (GET_RANK (p) - GET_RANK (q)));
	}
	shorter = 0;
	SET_BALANCE (q, shortened_side);
	SET_BALANCE (p, (- shortened_side));
      } else if (GET_BALANCE (q) == 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;
	  SET_RANK (q, (GET_RANK (q) + 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;
	  SET_RANK (p, (GET_RANK (p) - GET_RANK (q)));
	}
	shorter = 1;
	SET_BALANCE (q, 0);
	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;
	  SET_RANK (r, (GET_RANK (r) + GET_RANK (q)));
	  SET_RANK (p, (GET_RANK (p) - 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;