/* Copyright (C) 1996 Bjoern Beutel. */
/* Description. =============================================================*/
/* This module manages AVL trees. */
/* Includes. ================================================================*/
#include <setjmp.h>
#include <glib.h>
#include "basic.h"
#include "avl_trees.h"
/* Functions. ===============================================================*/
static bool_t
balance_left( avl_node_t **tree )
/* Balance TREE when the left subtree has shrunk.
* Return TRUE iff balanced TREE has shrunk. */
{
avl_node_t *root;
root = *tree;
root->balance++;
if (root->balance <= +1)
return (root->balance == 0);
/* Tree is in disorder, rebalance it. */
if (root->right->balance >= 0)
{
(*tree) = root->right;
root->right = (*tree)->left;
(*tree)->left = root;
if ((*tree)->balance == 0)
{
(*tree)->balance = -1;
(*tree)->left->balance = +1;
return FALSE;
}
else
{
(*tree)->balance = 0;
(*tree)->left->balance = 0;
return TRUE;
}
}
else
{
(*tree) = root->right->left;
root->right->left = (*tree)->right;
(*tree)->right = root->right;
root->right = (*tree)->left;
(*tree)->left = root;
if ((*tree)->balance == +1)
(*tree)->left->balance = -1;
else
(*tree)->left->balance = 0;
if ((*tree)->balance == -1)
(*tree)->right->balance = +1;
else
(*tree)->right->balance = 0;
(*tree)->balance = 0;
return TRUE;
}
}
/*---------------------------------------------------------------------------*/
static bool_t
balance_right( avl_node_t **tree )
/* Balance TREE when the right subtree has shrunk.
* Return TRUE iff balanced TREE has shrunk. */
{
avl_node_t *root;
root = *tree;
root->balance--;
if (root->balance >= -1)
return (root->balance == 0);
/* Tree is in disorder, rebalance it. */
if (root->left->balance <= 0)
{
(*tree) = root->left;
root->left = (*tree)->right;
(*tree)->right = root;
if ((*tree)->balance == 0)
{
(*tree)->balance = +1;
(*tree)->right->balance = -1;
return FALSE;
}
else
{
(*tree)->balance = 0;
(*tree)->right->balance = 0;
return TRUE;
}
}
else
{
(*tree) = root->left->right;
root->left->right = (*tree)->left;
(*tree)->left = root->left;
root->left = (*tree)->right;
(*tree)->right = root;
if ((*tree)->balance == -1)
(*tree)->right->balance = +1;
else
(*tree)->right->balance = 0;
if ((*tree)->balance == +1)
(*tree)->left->balance = -1;
else
(*tree)->left->balance = 0;
(*tree)->balance = 0;
return TRUE;
}
}
/*---------------------------------------------------------------------------*/
static bool_t
remove_largest( avl_node_t **tree, avl_node_t **result )
/* Find the largest element in TREE, remove it and return it in *RESULT.
* Return TRUE iff TREE has shrunk. */
{
avl_node_t *root;
bool_t shrunk;
root = *tree;
if (root->right != NULL)
{
shrunk = remove_largest( &root->right, result );
if (shrunk)
return balance_right( tree );
else
return FALSE;
}
else /* root->right == NULL ===> root is largest. */
{
*result = root;
*tree = root->left;
return TRUE;
}
}
/*---------------------------------------------------------------------------*/
bool_t
remove_avl_node( avl_node_t *node,
avl_node_t **tree,
int_t (*compare)( avl_node_t *, avl_node_t * ) )
/* Remove NODE from TREE. Return TRUE iff TREE has shrunk. */
{
int_t comp;
bool_t shrunk;
avl_node_t *root;
root = *tree;
comp = compare( node, root );
if (comp < 0)
{
shrunk = remove_avl_node( node, &root->left, compare );
if (shrunk)
return balance_left( tree );
else
return FALSE;
}
else if (comp > 0)
{
shrunk = remove_avl_node( node, &root->right, compare );
if (shrunk)
return balance_right( tree );
else
return FALSE;
}
else /* comp == 0 */
{
if (root->right == NULL)
(*tree) = root->left;
else if (root->left == NULL)
(*tree) = root->right;
else
{
shrunk = remove_largest( &root->left, tree );
(*tree)->balance = root->balance;
(*tree)->left = root->left;
(*tree)->right = root->right;
if (shrunk)
return balance_left( tree );
else
return FALSE;
}
return TRUE;
}
}
/*---------------------------------------------------------------------------*/
bool_t
insert_avl_node( avl_node_t *node,
avl_node_t **tree,
int_t (*compare)( avl_node_t *, avl_node_t * ) )
/* Find the right place to put NODE into TREE.
* Return TRUE iff TREE has grown. */
{
avl_node_t *root;
int_t comp;
bool_t grown;
if ((*tree) == NULL)
{
*tree = node;
return TRUE;
}
comp = compare( node, *tree );
if (comp < 0)
{
grown = insert_avl_node( node, &(*tree)->left, compare );
if (grown)
{
root = *tree;
root->balance--;
if (root->balance >= -1)
return (root->balance == -1);
/* Tree is in disorder, rebalance it. */
if (root->left->balance == -1)
{
(*tree) = root->left;
root->left = (*tree)->right;
(*tree)->right = root;
(*tree)->right->balance = 0;
}
else
{
(*tree) = root->left->right;
root->left->right = (*tree)->left;
(*tree)->left = root->left;
root->left = (*tree)->right;
(*tree)->right = root;
if ((*tree)->balance == -1)
(*tree)->right->balance = +1;
else
(*tree)->right->balance = 0;
if ((*tree)->balance == +1)
(*tree)->left->balance = -1;
else
(*tree)->left->balance = 0;
}
(*tree)->balance = 0;
}
return FALSE;
}
else if (comp > 0)
{
grown = insert_avl_node( node, &(*tree)->right, compare );
if (grown)
{
root = *tree;
root->balance++;
if (root->balance <= +1)
return (root->balance == +1);
/* Tree is in disorder, rebalance it. */
if (root->right->balance == +1)
{
(*tree) = root->right;
root->right = (*tree)->left;
(*tree)->left = root;
(*tree)->left->balance = 0;
}
else
{
(*tree) = root->right->left;
root->right->left = (*tree)->right;
(*tree)->right = root->right;
root->right = (*tree)->left;
(*tree)->left = root;
if ((*tree)->balance == +1)
(*tree)->left->balance = -1;
else
(*tree)->left->balance = 0;
if ((*tree)->balance == -1)
(*tree)->right->balance = +1;
else
(*tree)->right->balance = 0;
}
(*tree)->balance = 0;
}
return FALSE;
}
complain( "Internal error." );
}
/*---------------------------------------------------------------------------*/
static int_t
compare_avln_nodes( avl_node_t *node1, avl_node_t *node2 )
/* Compare NODE1 and NODE2 case-insensitively by their names. */
{
return strcmp_no_case( ((avln_node_t *) node1)->name,
((avln_node_t *) node2)->name ) ;
}
/*---------------------------------------------------------------------------*/
void
remove_avln_node( avln_node_t *node, avln_node_t **tree )
/* Remove NODE from TREE. */
{
remove_avl_node( (avl_node_t *) node, (avl_node_t **) tree,
compare_avln_nodes );
}
/*---------------------------------------------------------------------------*/
void
insert_avln_node( avln_node_t *node, avln_node_t **tree )
/* Put NODE into TREE. */
{
insert_avl_node( (avl_node_t *) node, (avl_node_t **) tree,
compare_avln_nodes );
}
/*---------------------------------------------------------------------------*/
avln_node_t *
find_avln_node( string_t name, avln_node_t *tree )
/* Find and return the name node with NAME in TREE.
* If no such node exists, return NULL. */
{
int_t result;
while (tree != NULL)
{
result = strcmp_no_case( name, tree->name );
if (result < 0)
tree = tree->left;
else if (result > 0)
tree = tree->right;
else
return tree;
}
return NULL;
}
/* End of file. =============================================================*/