/*
 * MS-DOS SHELL - TSEARCH functions
 *
 * MS-DOS SHELL - Copyright (c) 1990,4 Data Logic Limited
 *
 * This code is subject to the following copyright restrictions.  The
 * code for the extended (non BASIC) tsearch.3 functions is based on code
 * written by Peter Valkenburg & Michiel Huisjes.  The following copyright
 * conditions apply:
 *
 * 1.  Redistribution and use in source and binary forms are permitted
 *     provided that the above copyright notice is duplicated in the
 *     source form and the copyright notice in file sh6.c is displayed
 *     on entry to the program.
 *
 * 2.  The sources (or parts thereof) or objects generated from the sources
 *     (or parts of sources) cannot be sold under any circumstances.
 *
 *    $Header: /cvsroot/device/DEVL/UTILS/SH/Sh12.c,v 1.1 2002/08/02 06:49:33 adamy Exp $
 *
 *    $Log: Sh12.c,v $
 *    Revision 1.1  2002/08/02 06:49:33  adamy
 *    imported (reference only)
 *
 *    Revision 1.1  2001/07/20 05:55:44  ayoung
 *    WIN32 support
 *
 *    Revision 1.1.1.1  1999/12/02 01:11:12  gordonh
 *    UTIL
 *
 * Revision 2.7  1994/08/25  20:49:11  istewart
 * MS Shell 2.3 Release
 *
 * Revision 2.6  1994/02/01  10:25:20  istewart
 * Release 2.3 Beta 2, including first NT port
 *
 * Revision 2.5  1993/08/25  16:03:57  istewart
 * Beta 225 - see Notes file
 *
 * Revision 2.4  1993/07/02  10:21:35  istewart
 * 224 Beta fixes
 *
 * Revision 2.3  1993/06/02  09:52:35  istewart
 * Beta 223 Updates - see Notes file
 *
 * Revision 2.2  1993/02/16  16:03:15  istewart
 * Beta 2.22 Release
 *
 * Revision 2.1  1993/01/26  18:35:09  istewart
 * Release 2.2 beta 0
 *
 * Revision 2.0  1992/07/10  10:52:48  istewart
 * 211 Beta updates
 *
 *
 * Start of original notes for the non-BASIC tsearch functions.
 *
 * "tsearch.c", Peter Valkenburg & Michiel Huisjes, november '89.
 *
 * Standard tsearch(3) compatible implementation of AVL height balanced trees.
 * Performance is slightly better than SUN OS tsearch(3) for average case
 * delete/add operations, but worst case behaviour (i.e. when ordinary trees
 * get unbalanced) is much better.  Tsearch/tdelete/tfind run in O(2log(n)),
 * twalk in O(n), where n is the size of binary tree.
 *
 * Entry points:
 *
 *	_ts_NODE_t *tsearch((void *)key, (_ts_NODE_t **)rootp, int (*compar)());
 *	_ts_NODE_t *tdelete((void *)key, (_ts_NODE_t **)rootp, int (*compar)());
 *	_ts_NODE_t *tfind((void *)key, (_ts_NODE_t **)rootp, int (*compar)());
 *	void twalk((_ts_NODE_t *root), void (*action)());
 *
 * Here key is a pointer to any datum (to be) held in the tree rooted by *rootp
 * or root.  Keys are compared by calling compar, which gets two key arguments
 * and should return a value < 0, 0, or > 0, if the first parameter is to be
 * considered less than , equal to, or greater than the second, respectively.
 * Users can declare type (_ts_NODE_t *) as (char *) and (_ts_NODE_t **) as
 * (char **).  The return values of tsearch/tdelete/tfind can be used as
 * pointers to the key pointers of their _ts_NODE_t, by casting them to
 * (char **).
 *
 * See manual page tsearch(3) for more extensive user documentation.
 */

#include <sys/types.h>
#include <sys/stat.h>
#include <stdio.h>
#include <string.h>
#include <setjmp.h>
#include <unistd.h>
#include <limits.h>
#include "sh.h"

/*
 * Type for doubly linked AVL tree.
 */

#ifndef BASIC
typedef struct node_s {
    void		*key;		/* ptr to datum			*/
    struct node_s	*parent;	/* ptr to parent ancestor	*/
    struct node_s	*sibls[2];	/* ptrs to L/R siblings		*/
    int			balance;	/* balance value (-1, 0 or +1)	*/
} _ts_NODE_t;

typedef int		_SibIndex_t;	/* type for indexing siblings	*/
#define	L		((_SibIndex_t) 0)
#define	R		((_SibIndex_t) 1)

#define	LEFT		sibls[L]/* left sibling pointer _ts_NODE_t field */
#define	RIGHT		sibls[R]/* right sibling pointer _ts_NODE_t field */

/*
 * Direction gives direction in which child _ts_NODE_t c is under parent
 * _ts_NODE_t p.
 */

#define	direction(p, c)	((_SibIndex_t) ((p)->RIGHT == (c)))

/*
 * Cmp_dir gives direction corresponding with compare value v (R iff v > 0).
 */

#define	cmp_dir(v)	((_SibIndex_t) ((v) > 0))

/*
 * Siblingp yields ptr to left (d == L) or right (d == R) child of _ts_NODE_t n.
 */

#define	siblingp(n, d)	((n)->sibls + (d))

/*
 * Parentp yields ptr to parent's ptr to _ts_NODE_t n, or root ptr r if n is 0.
 */

#define	parentp(r, n)	((n)->parent == (_ts_NODE_t *)NULL ? (r) : \
			     siblingp((n)->parent, direction((n)->parent, (n))))

/*
 * Dir_bal yields balance value corresponding to _SibIndex_t d.
 */

#define	dir_bal(d)	((d) == L ? -1 : 1)

static _ts_NODE_t	*balance (_ts_NODE_t **, _ts_NODE_t *, int);
static _ts_NODE_t	*single_rotation (_ts_NODE_t **, _ts_NODE_t *,
					  _ts_NODE_t *, _SibIndex_t);
static _ts_NODE_t	*double_rotation (_ts_NODE_t **, _ts_NODE_t *,
					  _ts_NODE_t *, _SibIndex_t);

/*
 * Tsearch adds node key to tree rooted by *rootp, using compar for
 * comparing elements.  It returns the pointer to the _ts_NODE_t in which
 * the (possibly already existing) key pointer resides.
 */

void *
tsearch(void *key, void **root, int (*compar)(const void *, const void *) )
{
    register _ts_NODE_t		*parent, *child;
    _ts_NODE_t			*nnode;
    register _SibIndex_t	d;
    register int		cmp = 0;
    register _ts_NODE_t		**rootp = (_ts_NODE_t **)root;

    if (rootp == (_ts_NODE_t **)NULL)
	return (_ts_NODE_t *)NULL;

    /* find place where key should go */

    parent = (_ts_NODE_t *)NULL;
    child = *rootp;

    while (child != (_ts_NODE_t *)NULL)
    {
	if ((cmp = compar (key, child->key)) == 0)
	    return child;

	parent = child;
	child = *siblingp (child, cmp_dir (cmp));
    }

    /* create new node and set its parent's sibling pointer */

    nnode = (_ts_NODE_t *) GetAllocatedSpace (sizeof (_ts_NODE_t));

    if (nnode == (_ts_NODE_t *)NULL)
	return (_ts_NODE_t *)NULL;

    SetMemoryAreaNumber ((void *) nnode, 0);
    nnode->key = key;
    nnode->balance = 0;
    nnode->parent = parent;
    nnode->LEFT = nnode->RIGHT = (_ts_NODE_t *)NULL;

    if (parent == (_ts_NODE_t *)NULL)
    {
	*rootp = nnode;
	return nnode;			/* just created tree */
    }

    *siblingp (parent, cmp_dir(cmp)) = nnode;
    child = nnode;

/*
 * Back up until tree is balanced.  This is achieved when either
 * the tree is balanced by rotation or a node's balance becomes 0.
 */

    do
    {
	d = direction (parent, child);

	if (parent->balance == dir_bal(d))
	{
	    (void) balance (rootp, parent, d);
	    return nnode;
	}

	else if ((parent->balance += dir_bal(d)) == 0)
	    return nnode;

	child = parent;
	parent = parent->parent;

    } while (parent != (_ts_NODE_t *)NULL);

    return nnode;
}

/*
 * Tdelete removes key from the tree rooted by *rootp, using compar for
 * comparing elements.  It returns the pointer to the _ts_NODE_t that was the
 * parent of the _ts_NODE_t that contained the key pointer, 0 if it did not exist.
 */

void *
tdelete (void *key, void **root, int (*compar)(const void *, const void *))
{
    register _ts_NODE_t		*parent, *child;
    _ts_NODE_t			*dnode, *dparent;
    register _SibIndex_t	d;
    register int		cont_bal;
    register int		cmp;
    register _ts_NODE_t		**rootp = (_ts_NODE_t **)root;

    if (rootp == (_ts_NODE_t **)NULL)
	return (void *)NULL;

/* find node to delete */

    child = *rootp;

    while (child != (_ts_NODE_t *)NULL)
    {
	if ((cmp = compar (key, child->key)) == 0)
	    break;

	child = *siblingp (child, cmp_dir (cmp));
    }

    if (child == (_ts_NODE_t *)NULL)
	return (void *)NULL;		/* key not in tree */

/* the node was found; get its successor (if any) to replace it */

    dnode = child;
    dparent = dnode->parent;
    child = child->RIGHT;

    if (child == (_ts_NODE_t *)NULL)		/* no successor for key */
    {
	if ((child = dnode->LEFT) != (_ts_NODE_t *)NULL)
	    child->parent = dparent;	/* set new parent */

	if (dparent == (_ts_NODE_t *)NULL)
	{
	    ReleaseMemoryCell ((void *) dnode);
	    *rootp = child;
	    return (void *)NULL;	/* just deleted the root */
	}

	d = direction (dparent, dnode);	/* for back up */
	*siblingp(dparent, d) = child;	/* replace by left child */
	ReleaseMemoryCell ((void *) dnode);
	parent = dparent;
    }

    else				/* key's successor exists */
    {
	while (child->LEFT != (_ts_NODE_t *)NULL)
	    child = child->LEFT;

	parent = child->parent;
	d = direction(parent, child);		/* for back up */
	*siblingp(parent, d) = child->RIGHT;

	if (child->RIGHT != (_ts_NODE_t *)NULL)
	    child->RIGHT->parent = parent;	/* set new parent */

	dnode->key = child->key;	/* successor replaces key */
	ReleaseMemoryCell ((void *) child);
    }

/*
 * Back up until tree is balanced.  This is achieved when either the tree is
 * balanced by rotation but not made shorter, or a node's balance was 0 before
 * deletion.
 */

    do
    {
	if (parent->balance == dir_bal(!d))
	{
	    cont_bal = ((*siblingp(parent, !d))->balance != 0);
	    parent = balance(rootp, parent, !d);
	}

	else
	{
	    cont_bal = (parent->balance != 0);
	    parent->balance += dir_bal(!d);
	}

	child = parent;

	if ((parent = parent->parent) == (_ts_NODE_t *)NULL)
	    return dparent;		/* we reached the root */

	d = direction(parent, child);

    } while (cont_bal);

    return dparent;
}

/*
 * Balance the subtree rooted at sb that has become to heavy on side d.
 * Also adjusts sibling pointer of the parent of sb, or *rootp if sb is
 * the top of the entire tree.
 */

static _ts_NODE_t *
balance(_ts_NODE_t **rootp, _ts_NODE_t *sb, _SibIndex_t	d)
{
    _ts_NODE_t	*sb_next = *siblingp (sb, d);

    if (sb_next->balance == -dir_bal(d))
	return double_rotation (rootp, sb, sb_next, d);

    else
	return single_rotation (rootp, sb, sb_next, d);
}

/*
 * Balance the subtree rooted at sb that has become to heavy on side d
 * by single rotation of sb and sb_next.
 * Also adjusts sibling pointer of the parent of sb, or *rootp if sb is
 * the top of the entire tree.
 *
 *		sb		sb_next		Single rotation: Adding x or
 *	       /  \	       /       \	deleting under 3 caused
 *	sb_next	   3	      1		sb	rotation.  Same holds for mirror
 *     /       \	      |	       /  \	image.  Single_rotation returns
 *    1	        2	==>   x       2    3	top of new balanced tree.
 *    |		|		      |
 *    x		y		      y
 */

static _ts_NODE_t *
single_rotation ( 
    _ts_NODE_t **rootp,
    register _ts_NODE_t *sb, register _ts_NODE_t *sb_next, 
    register _SibIndex_t d )
{
    *siblingp (sb, d)       = *siblingp(sb_next, !d);
    *siblingp (sb_next, !d) = sb;
    sb->balance             -= sb_next->balance;
    sb_next->balance        = -sb->balance;
    *parentp (rootp, sb)    = sb_next;
    sb_next->parent         = sb->parent;
    sb->parent              = sb_next;

    if (*siblingp (sb, d) != (_ts_NODE_t *)NULL)
	(*siblingp (sb, d))->parent = sb;

    return sb_next;
}

/*
 * Balance the subtree rooted at sb that has become to heavy on side d
 * by double rotation of sb and sb_next.
 * Also adjusts sibling pointer of the parent of sb, or *rootp if sb is
 * the top of the entire tree.
 *
 *		sb		    sb_next2	   Double rotation: Adding x or
 *	       /  \	           /	    \	   x', or deleting under 4
 *	sb_next    \		sb_next	     sb    caused rotation. Same holds
 *     /       \    \	       /       \    /  \   for the mirror image.
 *    1   sb_next2   4	 ==>  1		2  3    4  Double_rotation returns top
 *       /        \			|  |	   of new balanced tree.
 *      2          3			x  x'
 *      |  	   |
 *      x	   x'
 */

static _ts_NODE_t *
double_rotation (
    _ts_NODE_t	**rootp,
    register _ts_NODE_t	*sb, register _ts_NODE_t *sb_next,
    register _SibIndex_t d )
{
    register _ts_NODE_t *sb_next2 = *siblingp(sb_next, !d);

    *siblingp (sb_next, !d)  = *siblingp (sb_next2, d);
    *siblingp (sb, d)        = *siblingp (sb_next2, !d);
    *siblingp (sb_next2, d)  = sb_next;
    *siblingp (sb_next2, !d) = sb;

    if (sb_next2->balance == sb_next->balance)
	sb_next->balance = -sb_next->balance;

    else
	sb_next->balance = 0;

    if (sb_next2->balance == sb->balance)
	sb->balance = -sb->balance;

    else
	sb->balance = 0;

    sb_next2->balance    = 0;
    *parentp (rootp, sb) = sb_next2;
    sb_next2->parent     = sb->parent;
    sb->parent           = sb_next->parent = sb_next2;

    if (*siblingp (sb_next, !d) != (_ts_NODE_t *)NULL)
	(*siblingp (sb_next, !d))->parent = sb_next;

    if (*siblingp (sb, d) != (_ts_NODE_t *)NULL)
	(*siblingp (sb, d))->parent = sb;

    return sb_next2;
}

/*
 * Tfind searches node key in the tree rooted by *rootp, using compar for
 * comparing elements.  It returns the pointer to the _ts_NODE_t in which
 * the key pointer resides, or 0 if key is not present.
 */

void	*
tfind(void *key, void **root, int (*compar)(const void *, const void *))
{
    register _ts_NODE_t	*node;
    _ts_NODE_t		**rootp = (_ts_NODE_t **)root;
    register int	cmp;

    if (rootp == (_ts_NODE_t **)NULL)
	return (void *)NULL;

    node = *rootp;
    while (node != (_ts_NODE_t *)NULL)
    {
	if ((cmp = compar (key, node->key)) == 0)
	    return node;

	node = *siblingp (node, cmp_dir (cmp));
    }

    return (void *)NULL;
}

/*
 * Twalk walks the tree rooted by node, from top to bottom and left to right,
 * calling action with the _ts_NODE_t pointer, visit order, and level in the tree
 * (0 is root).  Leafs are visited only once and action is then called with
 * `leaf' as the second parameter.  For nodes with children action is called
 * three times with visit order parameter `preorder' before, `postorder' in
 * between, and `endorder' after visiting the nodes children.
 */

void		
twalk (const void *start, register void	(*action)(const void *, VISIT, int))
{
    register VISIT	visit;
    register int	level;
    register _ts_NODE_t	*node = (_ts_NODE_t *)start;

    if ((node == (_ts_NODE_t *)NULL) || (action == 0))
	return;

/* run down tree from top to bottom, left to right */

    visit = preorder;
    level = 0;

    while (node != (_ts_NODE_t *)NULL)
    {
	if ((visit == preorder) &&
	    (node->LEFT == (_ts_NODE_t *)NULL) &&
	    (node->RIGHT == (_ts_NODE_t *)NULL))
	    visit = leaf;		/* node turns out to be leaf */

	action (node, visit, level);

	switch (visit)
	{
	    case preorder:			/* before visiting left child */
		if (node->LEFT != (_ts_NODE_t *)NULL)
		{
		    node = node->LEFT;
		    level++;
		}

		else
		    visit = postorder;

		break;

	    case postorder:		/* between visiting children */
		if (node->RIGHT != (_ts_NODE_t *)NULL)
		{
		    node = node->RIGHT;
		    visit = preorder;
		    level++;
		}

		else
		    visit = endorder;

		break;

	    case endorder:		/* after visiting children */
	    case leaf:			/* node has no children */
		if (node->parent != (_ts_NODE_t *)NULL)
		{
		    if (direction (node->parent, node) == L)
			visit = postorder;

		    else
			visit = endorder;
		}

		node = node->parent;
		level--;

		break;
	}
    }
}
#else

/*
 * Definition for t.... functions
 */

typedef struct _t_node {
    char		*key;
    struct _t_node	*llink;
    struct _t_node	*rlink;
} _t_NODE;

static void		_twalk (_t_NODE *,
				void (*)(const void *, VISIT, int), int);
/*
 * Basic Tree Processing Functions
 */

/*
 * Delete node with key
 */

void	*tdelete (key, rootcp, compar)
void	*key;
void	**rootcp;
int	(*compar)(const void *, const void *);
{
    _t_NODE		*p;		/* Parent of node to be deleted */
    register _t_NODE	*q;		/* Successor node		*/
    register _t_NODE	*r;		/* Right son node		*/
    int			ans;		/* Result of comparison		*/
    register _t_NODE	**rootp = (_t_NODE **)rootcp;

    if ((rootp == (_t_NODE **)NULL) || ((p = *rootp) == (_t_NODE *)NULL))
	return (void *)NULL;

    while ((ans = (*compar)(key, (*rootp)->key)) != 0)
    {
	p = *rootp;
	rootp = (ans < 0) ? &(*rootp)->llink : &(*rootp)->rlink;

	if (*rootp == (_t_NODE *)NULL)
	    return (void *)NULL;
    }

    r = (*rootp)->rlink;

    if ((q = (*rootp)->llink) == (_t_NODE *)NULL)
	    q = r;

    else if (r != (_t_NODE *)NULL)
    {
	if (r->llink == (_t_NODE *)NULL)
	{
	    r->llink = q;
	    q = r;
	}

	else
	{
	    for (q = r->llink; q->llink != (_t_NODE *)NULL; q = r->llink)
		r = q;

	    r->llink = q->rlink;
	    q->llink = (*rootp)->llink;
	    q->rlink = (*rootp)->rlink;
	}
    }

    ReleaseMemoryCell ((char *) *rootp);
    *rootp = q;
    return (void *)p;
}

/*
 * Find node with key
 */

void	*tfind (key, rootcp, compar)
void	*key;			/* Key to be located			*/
void	**rootcp;		/* Address of the root of the tree	*/
int	(*compar)(const void *, const void *);
{
    register _t_NODE	**rootp = (_t_NODE **)rootcp;

    if (rootp == (_t_NODE **)NULL)
	return (void *)NULL;

    while (*rootp != (_t_NODE *)NULL)
    {
	int	r = (*compar)(key, (*rootp)->key);

	if (r == 0)
	    return (void *)*rootp;

	rootp = (r < 0) ? &(*rootp)->llink : &(*rootp)->rlink;
    }

    return (void *)NULL;
}

/*
 * Search for a node with key key and add it if appropriate
 */

void	*tsearch (key, rootcp, compar)
void	*key;			/* Key to be located			*/
void	**rootcp;		/* Address of the root of the tree	*/
int	(*compar)(const void *, const void *);
{
    register _t_NODE	**rootp = (_t_NODE **)rootcp;
    register _t_NODE	*q;	/* New node if key not found */

    if (rootp == (_t_NODE **)NULL)
	return (void *)NULL;

    while (*rootp != (_t_NODE *)NULL)
    {
	int	r = (*compar)(key, (*rootp)->key);

	if (r == 0)
	    return (void *)*rootp;

	rootp = (r < 0) ? &(*rootp)->llink : &(*rootp)->rlink;
    }

    q = (_t_NODE *) GetAllocatedSpace (sizeof (_t_NODE));

    if (q != (_t_NODE *)NULL)
    {
        SetMemoryAreaNumber ((void *)q, 0);
	*rootp = q;
	q->key = key;
	q->llink = q->rlink = (_t_NODE *)NULL;
    }

    return (void *)q;
}


/* Walk the nodes of a tree */

void		twalk (root, action)
const void	*root;			/* Root of the tree to be walked */
void		(*action)(const void *, VISIT, int);
{
    if ((root != (char *)NULL) && (action != NULL))
	_twalk (root, action, 0);
}

static void		_twalk (root, action, level)
register _t_NODE	*root;
register void		(*action)(const void *, VISIT, int);
register int		level;
{
    if (root->llink == (_t_NODE *)NULL && root->rlink == NULL)
	(*action)(root, leaf, level);

    else
    {
	(*action)(root, preorder, level);

	if (root->llink != (_t_NODE *)NULL)
	    _twalk (root->llink, action, level + 1);

	(*action)(root, postorder, level);

	if (root->rlink != (_t_NODE *)NULL)
	    _twalk (root->rlink, action, level + 1);

	(*action)(root, endorder, level);
    }
}
#endif