/* as_avl - avl library for as
 * vix 14dec85 [written]
 * vix 02feb86 [added avl balancing from wirth "a+ds=p" p. 220-221]
 * vix 06feb86 [added avl_mung()]
 * vix 20jun86 [added avl_delete per wirth a+ds (mod2 v.) p. 224]
 * vix 23jun86 [added delete uar to add for replaced nodes]

   gish oct89 [renamed functions to begin with avl_ prefix]
   gish jan90 [modified avl_srch() so as to be non-recursive]
   gish aug90 [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.
 */

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

static void	sprout();
static Boolean	delete();
static void	del();
static void	balanceL();
static void	balanceR();

typedef avl_tree	PNTR (PNTR alloc_f)();
typedef void		(PNTR free_f)();

static alloc_f	local_alloc = (alloc_f)mem_malloc;
static free_f	local_free = (free_f)mem_free;

/* Establish a new memory allocating function */
alloc_f
avl_setalloc(newalloc)
	alloc_f	newalloc;
{
	alloc_f	oldalloc;

	oldalloc = local_alloc;
	local_alloc = newalloc;
	return oldalloc;
}

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

	oldfree = local_free;
	local_free = newfree;
	return oldfree;
}

void
avl_init(ppr_avl)
	CharPtr	ppr_avl;
{
	*ppr_avl = NULL;
}
	

CharPtr
avl_srch(ppr_avl, pfi_compare, pc_user)
	CharPtr	ppr_avl;
	FnPtr	pfi_compare;
	CharPtr	pc_user;
{
	register avl_tree	PNTR ppr = *(avl_tree PNTR PNTR)ppr_avl;
	register int	i_comp;
	register CharPtr	cur_avl_p;

	while (ppr) {
		i_comp = (*pfi_compare)(pc_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_avl, pfi_compare, pc_user, pfi_delete)
	CharPtr	ppr_avl;
	FnPtr	pfi_compare;
	CharPtr	pc_user;
	FnPtr	pfi_delete;
{
	void	sprout();
	Boolean	i_balance = FALSE;

	sprout((avl_tree PNTR PNTR)ppr_avl, pc_user, &i_balance,
				pfi_compare, pfi_delete);
}


static void
sprout(ppr, pc_data, pi_balance, pfi_compare, pfi_delete)
	avl_tree	PNTR PNTR ppr;
	CharPtr	pc_data;
	Boolean	PNTR pi_balance;
	FnPtr	pfi_compare;
	FnPtr	pfi_delete;
{
	avl_tree	PNTR p1, PNTR p2;
	int		cmp;

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

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

	/* if LESS, prepare to move to the left.
	 */
	if (cmp < 0) {
		sprout(&(*ppr)->avl_l, pc_data, pi_balance,
			pfi_compare, pfi_delete);
		if (*pi_balance) {	/* left branch has grown longer */
			switch ((*ppr)->avl_b) {
			case 1:	/* right branch WAS longer; balance is ok now */
				(*ppr)->avl_b = 0;
				*pi_balance = FALSE;
				break;
			case 0:	/* balance WAS okay; now left branch longer */
				(*ppr)->avl_b = -1;
				break;
			case -1:
				/* left branch was already too long. rebalnce */
				p1 = (*ppr)->avl_l;
				if (p1->avl_b == -1) {	/* LL */
					(*ppr)->avl_l = p1->avl_r;
					p1->avl_r = *ppr;
					(*ppr)->avl_b = 0;
					*ppr = p1;
				}
				else {			/* 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) {
		sprout(&(*ppr)->avl_r, pc_data, pi_balance,
			pfi_compare, pfi_delete);
		if (*pi_balance) {	/* right branch has grown longer */
			switch ((*ppr)->avl_b) {
			case -1:
				(*ppr)->avl_b = 0;
				*pi_balance = FALSE;
				break;
			case 0:
				(*ppr)->avl_b = 1;
				break;
			case 1:
				p1 = (*ppr)->avl_r;
				if (p1->avl_b == 1) {	/* RR */
					(*ppr)->avl_r = p1->avl_l;
					p1->avl_l = *ppr;
					(*ppr)->avl_b = 0;
					*ppr = p1;
				}
				else {			/* 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...  */
	*pi_balance = FALSE;
	if (pfi_delete)
		(*pfi_delete)((*ppr)->avl_p);
	(*ppr)->avl_p = pc_data;
}


Boolean
avl_delete(ppr_p, pfi_compare, pc_user, pfi_uar)
	CharPtr	ppr_p;
	FnPtr	pfi_compare;
	CharPtr	pc_user;
	FnPtr	pfi_uar;
{
	Boolean	i_balance = FALSE, i_uar_called = FALSE;

	return delete((avl_tree PNTR PNTR)ppr_p, pfi_compare, pc_user, pfi_uar,
				&i_balance, &i_uar_called);
}


static Boolean
delete(ppr_p, pfi_compare, pc_user, pfi_uar,
						pi_balance, pi_uar_called)
	avl_tree	PNTR PNTR ppr_p;
	FnPtr		pfi_compare;
	CharPtr		pc_user;
	FnPtr		pfi_uar;
	BoolPtr	pi_balance;
	BoolPtr	pi_uar_called;
{
	void	del(), balanceL(), balanceR();
	avl_tree	PNTR pr_q;
	int		i_comp;
	Boolean	i_ret;

	if (*ppr_p == NULL)
		return FALSE;

	i_comp = (*pfi_compare)(pc_user, (*ppr_p)->avl_p);
	if (i_comp < 0) {
		i_ret = delete(&(*ppr_p)->avl_l, pfi_compare, pc_user, pfi_uar,
						pi_balance, pi_uar_called);
		if (*pi_balance)
			balanceL(ppr_p, pi_balance);
	}
	else if (i_comp > 0) {
		i_ret = delete(&(*ppr_p)->avl_r, pfi_compare, pc_user, pfi_uar,
						pi_balance, pi_uar_called);
		if (*pi_balance)
			balanceR(ppr_p, pi_balance);
	}
	else {
		pr_q = *ppr_p;
		if (pr_q->avl_r == NULL) {
			*ppr_p = pr_q->avl_l;
			*pi_balance = TRUE;
		}
		else if (pr_q->avl_l == NULL) {
			*ppr_p = pr_q->avl_r;
			*pi_balance = TRUE;
		}
		else {
			del(&pr_q->avl_l, pi_balance, &pr_q, pfi_uar,
								pi_uar_called);
			if (*pi_balance)
				balanceL(ppr_p, pi_balance);
		}
		if (*pi_uar_called == 0 && *pfi_uar != NULL)
			(*pfi_uar)(pr_q->avl_p);
		(void) (*local_free)((CharPtr)pr_q); /* bug fix */
		i_ret = TRUE;
	}
	return i_ret;
}


static void
del(ppr_r, pi_balance, ppr_q, pfi_uar, pi_uar_called)
	avl_tree	PNTR PNTR ppr_r;
	BoolPtr	pi_balance;
	avl_tree	PNTR PNTR ppr_q;
	FnPtr		pfi_uar;
	BoolPtr	pi_uar_called;
{
	void	balanceR();

	if ((*ppr_r)->avl_r != NULL) {
		del(&(*ppr_r)->avl_r, pi_balance, ppr_q, pfi_uar,
								pi_uar_called);
		if (*pi_balance)
			balanceR(ppr_r, pi_balance);
	} else {
		if (pfi_uar)
			(*pfi_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;
	}
}


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

	switch ((*ppr_p)->avl_b) {
	case -1:
		(*ppr_p)->avl_b = 0;
		break;
	case 0:
		(*ppr_p)->avl_b = 1;
		*pi_balance = FALSE;
		break;
	case 1:
		p1 = (*ppr_p)->avl_r;
		b1 = p1->avl_b;
		if (b1 >= 0) {
			(*ppr_p)->avl_r = p1->avl_l;
			p1->avl_l = *ppr_p;
			if (b1 == 0) {
				(*ppr_p)->avl_b = 1;
				p1->avl_b = -1;
				*pi_balance = FALSE;
			} else {
				(*ppr_p)->avl_b = 0;
				p1->avl_b = 0;
			}
			*ppr_p = p1;
		} else {
			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;
		}
	}
}


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

	switch ((*ppr_p)->avl_b) {
	case 1:
		(*ppr_p)->avl_b = 0;
		break;
	case 0:
		(*ppr_p)->avl_b = -1;
		*pi_balance = FALSE;
		break;
	case -1:
		p1 = (*ppr_p)->avl_l;
		b1 = p1->avl_b;
		if (b1 <= 0) {
			(*ppr_p)->avl_l = p1->avl_r;
			p1->avl_r = *ppr_p;
			if (b1 == 0) {
				(*ppr_p)->avl_b = -1;
				p1->avl_b = 1;
				*pi_balance = FALSE;
			} else {
				(*ppr_p)->avl_b = 0;
				p1->avl_b = 0;
			}
			*ppr_p = p1;
		} else {
			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;
		}
	}
}


Boolean
avl_trav(ppr, pfi_uar)
	CharPtr	ppr;
	FnPtr	pfi_uar;
{
	register avl_tree	PNTR PNTR ppr_avl = (avl_tree PNTR PNTR)ppr;

	if (!*ppr_avl)
		return TRUE;

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

void
avl_mung(ppr_avl, pfi_uar)
	avl_tree	PNTR PNTR ppr_avl;
	FnPtr		pfi_uar;
{
	if (*ppr_avl) {
		avl_mung(&(**ppr_avl).avl_l, pfi_uar);
		avl_mung(&(**ppr_avl).avl_r, pfi_uar);
		if (pfi_uar)
			(*pfi_uar)((**ppr_avl).avl_p);
		(void) (*local_free)((CharPtr)*ppr_avl);
		*ppr_avl = NULL;
	}
}