/* 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]
 */


/* 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.
 */

/*#define		DEBUG	"tree"*/


#include <stdio.h>
#include <stdlib.h>
#include "vixie.h"
#include "tree.h"
#ifdef DEBUG
#undef DEBUG
#endif
#include "debug.h"

#ifdef __STDC__
#define __P(x) x
#else
#define	__P(x) ()
#endif

static void sprout __P((tree **, tree_t, int *, int (*)(), void (*)()));
static int delete __P((tree **, int (*)(), tree_t, void (*)(), int *,

	int *));
static void del __P((tree **, int *, tree **, void (*)(), int *));
static void bal_L __P((tree **, int *));
static void bal_R __P((tree **, int *));

#undef __P


void tree_init(tree ** ppr_tree)
{
    ENTER("tree_init");
    *ppr_tree = NULL;
    EXITV;
}


tree_t tree_srch(tree ** ppr_tree, int (*pfi_compare) ( /* ??? */ ),
    tree_t p_user)
{
    register int i_comp;

    ENTER("tree_srch");

    if (*ppr_tree) {
	i_comp = (*pfi_compare) (p_user, (**ppr_tree).tree_p);
	if (i_comp > 0)
	    EXIT(tree_srch(&(**ppr_tree).tree_r, pfi_compare, p_user));
	if (i_comp < 0)
	    EXIT(tree_srch(&(**ppr_tree).tree_l, pfi_compare, p_user));

	/* not higher, not lower... this must be the one.
	 */
	EXIT((**ppr_tree).tree_p);
    }

    /* grounded. NOT found.
     */
    EXIT(NULL);
}


void tree_add(tree ** ppr_tree, int (*pfi_compare) ( /* ??? */ ),
    tree_t p_user, void (*pfv_uar) ( /* ??? */ ))
{
    int i_balance = FALSE;

    ENTER("tree_add");
    sprout(ppr_tree, p_user, &i_balance, pfi_compare, pfv_uar);
    EXITV;
}


int tree_delete(tree ** ppr_p, int (*pfi_compare) ( /* ??? */ ),
    tree_t p_user, void (*pfv_uar) ( /* ??? */ ))
{
    int i_balance = FALSE, i_uar_called = FALSE;

    ENTER("tree_delete");
    EXIT(delete(ppr_p, pfi_compare, p_user, pfv_uar, &i_balance,
	    &i_uar_called));
} int tree_trav(tree ** ppr_tree, int (*pfi_uar) ( /* ??? */ ))
{
    ENTER("tree_trav");

    if (!*ppr_tree)
	EXIT(TRUE);

    if (!tree_trav(&(**ppr_tree).tree_l, pfi_uar))
	EXIT(FALSE);
    if (!(*pfi_uar) ((**ppr_tree).tree_p))
	EXIT(FALSE);
    if (!tree_trav(&(**ppr_tree).tree_r, pfi_uar))
	EXIT(FALSE);
    EXIT(TRUE);
}
void tree_mung(tree ** ppr_tree, void (*pfv_uar) ( /* ??? */ ))
{
    ENTER("tree_mung");
    if (*ppr_tree) {
	tree_mung(&(**ppr_tree).tree_l, pfv_uar);
	tree_mung(&(**ppr_tree).tree_r, pfv_uar);
	if (pfv_uar)
	    (*pfv_uar) ((**ppr_tree).tree_p);
	free(*ppr_tree);
	*ppr_tree = NULL;
    }
    EXITV;
}


static void sprout(tree ** ppr, tree_t p_data, int *pi_balance,
    int (*pfi_compare) ( /* ??? */ ),
    void (*pfv_delete) ( /* ??? */ ))
{
    tree *p1, *p2;
    int cmp;

    ENTER("sprout");

    /* are we grounded?  if so, add the node "here" and set the rebalance
     * flag, then exit.
     */ if (!*ppr) {
	dprintk("grounded. adding new node, setting h=true");
	*ppr = (tree *) malloc(sizeof(tree));
	(*ppr)->tree_l = NULL;
	(*ppr)->tree_r = NULL;
	(*ppr)->tree_b = 0;
	(*ppr)->tree_p = p_data;
	*pi_balance = TRUE;
	EXITV;
    }

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

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

		    p2 = p1->tree_r;
		    p1->tree_r = p2->tree_l;
		    p2->tree_l = p1;

		    (*ppr)->tree_l = p2->tree_r;
		    p2->tree_r = *ppr;

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

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

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

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

		    p2 = p1->tree_l;
		    p1->tree_l = p2->tree_r;
		    p2->tree_r = p1;

		    (*ppr)->tree_r = p2->tree_l;
		    p2->tree_l = *ppr;

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

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

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

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


static int delete(tree ** ppr_p, int (*pfi_compare) ( /* ??? */ ),
    tree_t p_user, void (*pfv_uar) ( /* ??? */ ),
    int *pi_balance, int *pi_uar_called)
{
    tree *pr_q;
    int i_comp, i_ret;

    ENTER("delete");

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

    i_comp = (*pfi_compare) ((*ppr_p)->tree_p, p_user);

    if (i_comp > 0) {
	dprintk("too high - scan left");
	i_ret =
	    delete(&(*ppr_p)->tree_l, pfi_compare, p_user, pfv_uar,
	    pi_balance, pi_uar_called);
	if (*pi_balance)
	    bal_L(ppr_p, pi_balance);
    } else if (i_comp < 0) {
	dprintk("too low - scan right");
	i_ret =
	    delete(&(*ppr_p)->tree_r, pfi_compare, p_user, pfv_uar,
	    pi_balance, pi_uar_called);
	if (*pi_balance)
	    bal_R(ppr_p, pi_balance);
    } else {
	dprintk("equal");
	pr_q = *ppr_p;
	if (pr_q->tree_r == NULL) {
	    dprintk("right subtree null");
	    *ppr_p = pr_q->tree_l;
	    *pi_balance = TRUE;
	} else if (pr_q->tree_l == NULL) {
	    dprintk("right subtree non-null, left subtree null");
	    *ppr_p = pr_q->tree_r;
	    *pi_balance = TRUE;
	} else {
	    dprintk("neither subtree null");
	    del(&pr_q->tree_l, pi_balance, &pr_q, pfv_uar, pi_uar_called);
	    if (*pi_balance)
		bal_L(ppr_p, pi_balance);
	}
	if (!*pi_uar_called && *pfv_uar)
	    (*pfv_uar) (pr_q->tree_p);
	free(pr_q);		/* thanks to wuth@castrov.cuc.ab.ca */
	i_ret = TRUE;
    }
    EXIT(i_ret);
}


static void del(tree ** ppr_r, int *pi_balance, tree ** ppr_q,
    void (*pfv_uar) ( /* ??? */ ), int *pi_uar_called)
{
    ENTER("del");

    if ((*ppr_r)->tree_r != NULL) {
	del(&(*ppr_r)->tree_r, pi_balance, ppr_q, pfv_uar, pi_uar_called);
	if (*pi_balance)
	    bal_R(ppr_r, pi_balance);
    } else {
	if (pfv_uar)
	    (*pfv_uar) ((*ppr_q)->tree_p);
	*pi_uar_called = TRUE;
	(*ppr_q)->tree_p = (*ppr_r)->tree_p;
	*ppr_q = *ppr_r;
	*ppr_r = (*ppr_r)->tree_l;
	*pi_balance = TRUE;
    }

    EXITV;
}


static void bal_L(tree ** ppr_p, int *pi_balance)
{
    tree *p1, *p2;
    int b1, b2;

    ENTER("bal_L");
    dprintk("left branch has shrunk");

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


static void bal_R(tree ** ppr_p, int *pi_balance)
{
    tree *p1, *p2;
    int b1, b2;

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