/* as_tree - tree library for as
 * vix 14dec85 [written]
 * vix 02feb86 [added tree balancing from wirth "a+ds=p" p. 220-221]
 * vix 06feb86 [added tree_mung()]
 * vix 20jun86 [added tree_delete per wirth a+ds (mod2 v.) p. 224]
 * vix 23jun86 [added delete uar to add for replaced nodes]
 * vix 22jan93 [revisited; uses RCS, ANSI, POSIX; has bug fixes]

 gish dec93 [renamed functions to begin with avl_ prefix]
 gish dec93 [modified avl_srch() so as to be non-recursive (faster)]
 gish dec93 [added memory allocation function pointers]
 */


/* This program text was created by Paul Vixie using examples from the book:
 * "Algorithms & Data Structures," Niklaus Wirth, Prentice-Hall, 1986, ISBN
 * 0-13-022005-1.  This code and associated documentation is hereby placed
 * in the public domain.
 */

#ifdef MSG
#undef MSG
#endif
#define MSG(X)

#include <ncbi.h>
#include <gishlib.h>

static void	sprout PROTO((avl_tree **, VoidPtr, int *, FnPtr, void (*)()));
static int	delete PROTO((avl_tree **, FnPtr, VoidPtr, void (*)(), int *, int *));
static void	del PROTO((avl_tree **, int *, avl_tree **, void (*)(), int *));
static void	balanceL PROTO((avl_tree **, int *));
static void	balanceR PROTO((avl_tree **, int *));


static VoidPtr	(*local_alloc)() = (VoidPtr (*)())mem_malloc;
static void		(*local_free)() = (void (*)())mem_free;

/* Establish a new memory allocation function */
VoidPtr (*
avl_setalloc(newalloc))()
	VoidPtr	(*newalloc)();
{
	VoidPtr	(*oldalloc)();

	oldalloc = local_alloc;
	if (newalloc != NULL)
		local_alloc = newalloc;
	return oldalloc;
}

/* Establish a new memory free function */
void (*
avl_setfree(newfree))()
	void	(*newfree)();
{
	void	(*oldfree)();

	oldfree = local_free;
	if (newfree != NULL)
		local_free = newfree;
	return oldfree;
}

void
avl_init(ppr_tree)
	avl_tree	**ppr_tree;
{
	*ppr_tree = NULL;
	return;
}
	

VoidPtr
avl_srch(ppr_tree, pfi_compare, p_user)
	avl_tree	**ppr_tree;
	FnPtr	pfi_compare;
	VoidPtr	p_user;

{
	register avl_tree	*ppr = *ppr_tree;
	register int	i_comp;
	register VoidPtr	cur_avl_p;

	while (ppr) {
		i_comp = (*pfi_compare)(p_user, cur_avl_p = ppr->avl_p);
		if (i_comp > 0) {
			ppr = ppr->avl_r;
			continue;
		}
		if (i_comp < 0) {
			ppr = ppr->avl_l;
			continue;
		}

		/* not higher, not lower... this must be the one  */
		return cur_avl_p;
	}

	/* grounded. NOT found.  */
	return NULL;
}

void
avl_add(ppr_tree, pfi_compare, p_user, pfv_uar)
	avl_tree	**ppr_tree;
	FnPtr	pfi_compare;
	VoidPtr	p_user;
	void	(*pfv_uar)();
{
	int	i_balance = FALSE;

	sprout(ppr_tree, p_user, &i_balance, pfi_compare, pfv_uar);
	return;
}


int
avl_delete(ppr_p, pfi_compare, p_user, pfv_uar)
	avl_tree	**ppr_p;
	FnPtr	pfi_compare;
	VoidPtr	p_user;
	void	(*pfv_uar)();
{
	int	i_balance = FALSE,
		i_uar_called = FALSE;

	return delete(ppr_p, pfi_compare, p_user, pfv_uar, &i_balance, &i_uar_called);
}


int
avl_trav(ppr_tree, pfi_uar)
	avl_tree	**ppr_tree;
	FnPtr	pfi_uar;
{
	if (!*ppr_tree)
		return TRUE;

	if (!avl_trav(&(**ppr_tree).avl_l, pfi_uar))
		return FALSE;
	if (!(*pfi_uar)((**ppr_tree).avl_p))
		return FALSE;
	if (!avl_trav(&(**ppr_tree).avl_r, pfi_uar))
		return FALSE;
	return TRUE;
}


void
avl_mung(ppr_tree, pfv_uar)
	avl_tree	**ppr_tree;
	void	(*pfv_uar)();
{
	if (*ppr_tree)
	{
		avl_mung(&(**ppr_tree).avl_l, pfv_uar);
		avl_mung(&(**ppr_tree).avl_r, pfv_uar);
		if (pfv_uar)
			(*pfv_uar)((**ppr_tree).avl_p);
		(*local_free)(*ppr_tree);
		*ppr_tree = NULL;
	}
	return;
}


static void
sprout(ppr, p_data, pi_balance, pfi_compare, pfv_delete)
	avl_tree	**ppr;
	VoidPtr	p_data;
	int	*pi_balance;
	FnPtr	pfi_compare;
	void	(*pfv_delete)();
{
	register avl_tree	*p1, *p2;
	int	cmp;

	/* are we grounded?  if so, add the node "here" and set the rebalance
	 * flag, then exit.
	 */
	if (!*ppr) {
		MSG("grounded. adding new node, setting h=true")
		*ppr = (avl_tree *) (*local_alloc)(sizeof(avl_tree));
		(*ppr)->avl_l = NULL;
		(*ppr)->avl_r = NULL;
		(*ppr)->avl_b = 0;
		(*ppr)->avl_p = p_data;
		*pi_balance = TRUE;
		return;
	}

	/* compare the data using routine passed by caller.
	 */
	cmp = (*pfi_compare)(p_data, (*ppr)->avl_p);

	/* if LESS, prepare to move to the left.
	 */
	if (cmp < 0) {
		MSG("LESS. sprouting left.")
		sprout(&(*ppr)->avl_l, p_data, pi_balance,
			pfi_compare, pfv_delete);
		if (*pi_balance) {	/* left branch has grown longer */
			MSG("LESS: left branch has grown")
			switch ((*ppr)->avl_b)
			{
			case 1:	/* right branch WAS longer; balance is ok now */
				MSG("LESS: case 1.. balnce restored implicitly")
				(*ppr)->avl_b = 0;
				*pi_balance = FALSE;
				break;
			case 0:	/* balance WAS okay; now left branch longer */
				MSG("LESS: case 0.. balnce bad but still ok")
				(*ppr)->avl_b = -1;
				break;
			case -1:
				/* left branch was already too long. rebalnce */
				MSG("LESS: case -1: rebalancing")
				p1 = (*ppr)->avl_l;
				if (p1->avl_b == -1) {	/* LL */
					MSG("LESS: single LL")
					(*ppr)->avl_l = p1->avl_r;
					p1->avl_r = *ppr;
					(*ppr)->avl_b = 0;
					*ppr = p1;
				}
				else {			/* double LR */
					MSG("LESS: double LR")

					p2 = p1->avl_r;
					p1->avl_r = p2->avl_l;
					p2->avl_l = p1;

					(*ppr)->avl_l = p2->avl_r;
					p2->avl_r = *ppr;

					if (p2->avl_b == -1)
						(*ppr)->avl_b = 1;
					else
						(*ppr)->avl_b = 0;

					if (p2->avl_b == 1)
						p1->avl_b = -1;
					else
						p1->avl_b = 0;
					*ppr = p2;
				} /*else*/
				(*ppr)->avl_b = 0;
				*pi_balance = FALSE;
			} /*switch*/
		} /*if*/
		return;
	} /*if*/

	/* if MORE, prepare to move to the right.
	 */
	if (cmp > 0) {
		MSG("MORE: sprouting to the right")
		sprout(&(*ppr)->avl_r, p_data, pi_balance,
			pfi_compare, pfv_delete);
		if (*pi_balance) {	/* right branch has grown longer */
			MSG("MORE: right branch has grown")

			switch ((*ppr)->avl_b)
			{
			case -1:MSG("MORE: balance was off, fixed implicitly")
				(*ppr)->avl_b = 0;
				*pi_balance = FALSE;
				break;
			case 0:	MSG("MORE: balance was okay, now off but ok")
				(*ppr)->avl_b = 1;
				break;
			case 1:	MSG("MORE: balance was off, need to rebalance")
				p1 = (*ppr)->avl_r;
				if (p1->avl_b == 1) {	/* RR */
					MSG("MORE: single RR")
					(*ppr)->avl_r = p1->avl_l;
					p1->avl_l = *ppr;
					(*ppr)->avl_b = 0;
					*ppr = p1;
				}
				else {			/* double RL */
					MSG("MORE: double RL")

					p2 = p1->avl_l;
					p1->avl_l = p2->avl_r;
					p2->avl_r = p1;

					(*ppr)->avl_r = p2->avl_l;
					p2->avl_l = *ppr;

					if (p2->avl_b == 1)
						(*ppr)->avl_b = -1;
					else
						(*ppr)->avl_b = 0;

					if (p2->avl_b == -1)
						p1->avl_b = 1;
					else
						p1->avl_b = 0;

					*ppr = p2;
				} /*else*/
				(*ppr)->avl_b = 0;
				*pi_balance = FALSE;
			} /*switch*/
		} /*if*/
		return;
	} /*if*/

	/* not less, not more: this is the same key!  replace...
	 */
	MSG("I found it!  Replacing data value")
	*pi_balance = FALSE;
	if (pfv_delete)
		(*pfv_delete)((*ppr)->avl_p);
	(*ppr)->avl_p = p_data;
	return;
}


static int
delete(ppr_p, pfi_compare, p_user, pfv_uar, pi_balance, pi_uar_called)
	avl_tree	**ppr_p;
	FnPtr	pfi_compare;
	VoidPtr	p_user;
	void	(*pfv_uar)();
	int	*pi_balance;
	int	*pi_uar_called;
{
	avl_tree	*pr_q;
	int	i_comp, i_ret;

	if (*ppr_p == NULL) {
		MSG("key not in tree")
		return FALSE;
	}

	i_comp = (*pfi_compare)((*ppr_p)->avl_p, p_user);
	if (i_comp > 0) {
		MSG("too high - scan left")
		i_ret = delete(&(*ppr_p)->avl_l, pfi_compare, p_user, pfv_uar,
						pi_balance, pi_uar_called);
		if (*pi_balance)
			balanceL(ppr_p, pi_balance);
	}
	else if (i_comp < 0) {
		MSG("too low - scan right")
		i_ret = delete(&(*ppr_p)->avl_r, pfi_compare, p_user, pfv_uar,
						pi_balance, pi_uar_called);
		if (*pi_balance)
			balanceR(ppr_p, pi_balance);
	}
	else {
		MSG("equal")
		pr_q = *ppr_p;
		if (pr_q->avl_r == NULL) {
			MSG("right subtree null")
			*ppr_p = pr_q->avl_l;
			*pi_balance = TRUE;
		}
		else if (pr_q->avl_l == NULL) {
			MSG("right subtree non-null, left subtree null")
			*ppr_p = pr_q->avl_r;
			*pi_balance = TRUE;
		}
		else {
			MSG("neither subtree null")
			del(&pr_q->avl_l, pi_balance, &pr_q, pfv_uar,
								pi_uar_called);
			if (*pi_balance)
				balanceL(ppr_p, pi_balance);
		}
		if (!*pi_uar_called && pfv_uar)
			(*pfv_uar)(pr_q->avl_p);
		(*local_free)(pr_q);	/* thanks to wuth@castrov.cuc.ab.ca */
		i_ret = TRUE;
	}
	return i_ret;
}


static void
del(ppr_r, pi_balance, ppr_q, pfv_uar, pi_uar_called)
	avl_tree	**ppr_r;
	int	*pi_balance;
	avl_tree	**ppr_q;
	void	(*pfv_uar)();
	int	*pi_uar_called;
{
	if ((*ppr_r)->avl_r != NULL) {
		del(&(*ppr_r)->avl_r, pi_balance, ppr_q,
		    pfv_uar, pi_uar_called);
		if (*pi_balance)
			balanceR(ppr_r, pi_balance);
	} else {
		if (pfv_uar)
			(*pfv_uar)((*ppr_q)->avl_p);
		*pi_uar_called = TRUE;
		(*ppr_q)->avl_p = (*ppr_r)->avl_p;
		*ppr_q = *ppr_r;
		*ppr_r = (*ppr_r)->avl_l;
		*pi_balance = TRUE;
	}

	return;
}


static void
balanceL(ppr_p, pi_balance)
	avl_tree	**ppr_p;
	int	*pi_balance;
{
	register avl_tree	*p1, *p2;
	int	b1, b2;

	MSG("left branch has shrunk")

	switch ((*ppr_p)->avl_b)
	{
	case -1: MSG("was imbalanced, fixed implicitly")
		(*ppr_p)->avl_b = 0;
		break;
	case 0:	MSG("was okay, is now one off")
		(*ppr_p)->avl_b = 1;
		*pi_balance = FALSE;
		break;
	case 1:	MSG("was already off, this is too much")
		p1 = (*ppr_p)->avl_r;
		b1 = p1->avl_b;
		if (b1 >= 0) {
			MSG("single RR")
			(*ppr_p)->avl_r = p1->avl_l;
			p1->avl_l = *ppr_p;
			if (b1 == 0) {
				MSG("b1 == 0")
				(*ppr_p)->avl_b = 1;
				p1->avl_b = -1;
				*pi_balance = FALSE;
			} else {
				MSG("b1 != 0")
				(*ppr_p)->avl_b = 0;
				p1->avl_b = 0;
			}
			*ppr_p = p1;
		} else {
			MSG("double RL")
			p2 = p1->avl_l;
			b2 = p2->avl_b;
			p1->avl_l = p2->avl_r;
			p2->avl_r = p1;
			(*ppr_p)->avl_r = p2->avl_l;
			p2->avl_l = *ppr_p;
			if (b2 == 1)
				(*ppr_p)->avl_b = -1;
			else
				(*ppr_p)->avl_b = 0;
			if (b2 == -1)
				p1->avl_b = 1;
			else
				p1->avl_b = 0;
			*ppr_p = p2;
			p2->avl_b = 0;
		}
	}
	return;
}


static void
balanceR(ppr_p, pi_balance)
	avl_tree	**ppr_p;
	int	*pi_balance;
{
	register avl_tree	*p1, *p2;
	register int	b1, b2;

	MSG("right branch has shrunk")
	switch ((*ppr_p)->avl_b)
	{
	case 1:	MSG("was imbalanced, fixed implicitly")
		(*ppr_p)->avl_b = 0;
		break;
	case 0:	MSG("was okay, is now one off")
		(*ppr_p)->avl_b = -1;
		*pi_balance = FALSE;
		break;
	case -1: MSG("was already off, this is too much")
		p1 = (*ppr_p)->avl_l;
		b1 = p1->avl_b;
		if (b1 <= 0) {
			MSG("single LL")
			(*ppr_p)->avl_l = p1->avl_r;
			p1->avl_r = *ppr_p;
			if (b1 == 0) {
				MSG("b1 == 0")
				(*ppr_p)->avl_b = -1;
				p1->avl_b = 1;
				*pi_balance = FALSE;
			} else {
				MSG("b1 != 0")
				(*ppr_p)->avl_b = 0;
				p1->avl_b = 0;
			}
			*ppr_p = p1;
		} else {
			MSG("double LR")
			p2 = p1->avl_r;
			b2 = p2->avl_b;
			p1->avl_r = p2->avl_l;
			p2->avl_l = p1;
			(*ppr_p)->avl_l = p2->avl_r;
			p2->avl_r = *ppr_p;
			if (b2 == -1)
				(*ppr_p)->avl_b = 1;
			else
				(*ppr_p)->avl_b = 0;
			if (b2 == 1)
				p1->avl_b = -1;
			else
				p1->avl_b = 0;
			*ppr_p = p2;
			p2->avl_b = 0;
		}
	}
	return;
}