/***********************************************************************
*                                                                      *
*               This software is part of the ast package               *
*          Copyright (c) 1985-2009 AT&T Intellectual Property          *
*                      and is licensed under the                       *
*                  Common Public License, Version 1.0                  *
*                    by AT&T Intellectual Property                     *
*                                                                      *
*                A copy of the License is available at                 *
*            http://www.opensource.org/licenses/cpl1.0.txt             *
*         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
*                                                                      *
*              Information and Software Systems Research               *
*                            AT&T Research                             *
*                           Florham Park NJ                            *
*                                                                      *
*                 Glenn Fowler <gsf@research.att.com>                  *
*                  David Korn <dgk@research.att.com>                   *
*                   Phong Vo <kpv@research.att.com>                    *
*                                                                      *
***********************************************************************/
#include	"dthdr.h"

/*	Ordered set/multiset
**	dt:	dictionary being searched
**	obj:	the object to look for.
**	type:	search type.
**
**      Written by Kiem-Phong Vo (5/25/96)
*/

#if __STD_C
static Void_t* dttree(Dt_t* dt, Void_t* obj, int type)
#else
static Void_t* dttree(dt,obj,type)
Dt_t*		dt;
Void_t* 	obj;
int		type;
#endif
{
	Dtlink_t	*root, *t;
	int		cmp, lk, sz, ky;
	Void_t		*o, *k, *key;
	Dtlink_t	*l, *r, *me, link;
	int		n, minp, turn[DT_MINP];
	Dtcompar_f	cmpf;
	Dtdisc_t*	disc;

	UNFLATTEN(dt);
	disc = dt->disc; _DTDSC(disc,ky,sz,lk,cmpf);
	dt->type &= ~DT_FOUND;

	root = dt->data->here;
	if(!obj)
	{	if(!root || !(type&(DT_CLEAR|DT_FIRST|DT_LAST)) )
			return NIL(Void_t*);

		if(type&DT_CLEAR) /* delete all objects */
		{	if(disc->freef || disc->link < 0)
			{	do
				{	while((t = root->left) )
						RROTATE(root,t);
					t = root->right;
					if(disc->freef)
						(*disc->freef)(dt,_DTOBJ(root,lk),disc);
					if(disc->link < 0)
						(*dt->memoryf)(dt,(Void_t*)root,0,disc);
				} while((root = t) );
			}

			dt->data->size = 0;
			dt->data->here = NIL(Dtlink_t*);
			return NIL(Void_t*);
		}
		else /* computing largest/smallest element */
		{	if(type&DT_LAST)
			{	while((t = root->right) )
					LROTATE(root,t);
			}
			else /* type&DT_FIRST */
			{	while((t = root->left) )
					RROTATE(root,t);
			}

			dt->data->here = root;
			return _DTOBJ(root,lk);
		}
	}

	/* note that link.right is LEFT tree and link.left is RIGHT tree */
	l = r = &link;

	/* allow apps to delete an object "actually" in the dictionary */
	if(dt->meth->type == DT_OBAG && (type&(DT_DELETE|DT_DETACH)) )
	{	key = _DTKEY(obj,ky,sz);
		for(o = dtsearch(dt,obj); o; o = dtnext(dt,o) )
		{	k = _DTKEY(o,ky,sz);
			if(_DTCMP(dt,key,k,disc,cmpf,sz) != 0)
				break;
			if(o == obj)
			{	root = dt->data->here;
				l->right = root->left;
				r->left  = root->right;
				goto dt_delete;
			}
		}
	}

	if(type&(DT_MATCH|DT_SEARCH|DT_INSERT|DT_ATTACH))
	{	key = (type&DT_MATCH) ? obj : _DTKEY(obj,ky,sz);
		if(root)
			goto do_search;
	}
	else if(type&DT_RENEW)
	{	me = (Dtlink_t*)obj;
		obj = _DTOBJ(me,lk);
		key = _DTKEY(obj,ky,sz);
		if(root)
			goto do_search;
	}
	else if(root && _DTOBJ(root,lk) != obj)
	{	key = _DTKEY(obj,ky,sz);
	do_search:
		if(dt->meth->type == DT_OSET &&
		   (minp = dt->data->minp) != 0 && (type&(DT_MATCH|DT_SEARCH)) )
		{	/* simple search, note that minp should be even */
			for(t = root, n = 0; n < minp; ++n)
			{	k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
				if((cmp = _DTCMP(dt,key,k,disc,cmpf,sz)) == 0)
					return _DTOBJ(t,lk);
				else
				{	turn[n] = cmp;	
					if(!(t = cmp < 0 ? t->left : t->right) )
						return NIL(Void_t*);
				}
			}

			/* exceed search length, top-down splay now */
			for(n = 0; n < minp; n += 2)
			{	if(turn[n] < 0)
				{	t = root->left;
					if(turn[n+1] < 0)
					{	rrotate(root,t);
						rlink(r,t);
						root = t->left;
					}
					else
					{	llink(l,t);
						rlink(r,root);
						root = t->right;
					}
				}
				else
				{	t = root->right;
					if(turn[n+1] > 0)
					{	lrotate(root,t);
						llink(l,t);
						root = t->right;
					}
					else
					{	rlink(r,t);
						llink(l,root);
						root = t->left;
					}
				}
			}
		}

		while(1)
		{	k = _DTOBJ(root,lk); k = _DTKEY(k,ky,sz);
			if((cmp = _DTCMP(dt,key,k,disc,cmpf,sz)) == 0)
				break;
			else if(cmp < 0)
			{	if((t = root->left) )
				{	k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
					if((cmp = _DTCMP(dt,key,k,disc,cmpf,sz)) < 0)
					{	rrotate(root,t);
						rlink(r,t);
						if(!(root = t->left) )
							break;
					}
					else if(cmp == 0)
					{	rlink(r,root);
						root = t;
						break;
					}
					else /* if(cmp > 0) */
					{	llink(l,t);
						rlink(r,root);
						if(!(root = t->right) )
							break;
					}
				}
				else
				{	rlink(r,root);
					root = NIL(Dtlink_t*);
					break;
				}
			}
			else /* if(cmp > 0) */
			{	if((t = root->right) )
				{	k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
					if((cmp = _DTCMP(dt,key,k,disc,cmpf,sz)) > 0)
					{	lrotate(root,t);
						llink(l,t);
						if(!(root = t->right) )
							break;
					}
					else if(cmp == 0)
					{	llink(l,root);
						root = t;
						break;
					}
					else /* if(cmp < 0) */
					{	rlink(r,t);
						llink(l,root);
						if(!(root = t->left) )
							break;
					}
				}
				else
				{	llink(l,root);
					root = NIL(Dtlink_t*);
					break;
				}
			}
		}
	}

	if(root)
	{	/* found it, now isolate it */
		dt->type |= DT_FOUND;
		l->right = root->left;
		r->left = root->right;

		if(type&(DT_SEARCH|DT_MATCH))
		{ has_root:
			root->left = link.right;
			root->right = link.left;
			if((dt->meth->type&DT_OBAG) && (type&(DT_SEARCH|DT_MATCH)) )
			{	key = _DTOBJ(root,lk); key = _DTKEY(key,ky,sz);
				while((t = root->left) )
				{	/* find max of left subtree */
					while((r = t->right) )
						LROTATE(t,r);
					root->left = t;

					/* now see if it's in the same group */
					k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
					if(_DTCMP(dt,key,k,disc,cmpf,sz) != 0)
						break;
					RROTATE(root,t);
				}
			}
			dt->data->here = root;
			return _DTOBJ(root,lk);
		}
		else if(type&DT_NEXT)
		{	root->left = link.right;
			root->right = NIL(Dtlink_t*);
			link.right = root;
		dt_next:
			if((root = link.left) )	
			{	while((t = root->left) )
					RROTATE(root,t);
				link.left = root->right;
				goto has_root;
			}
			else	goto no_root;
		}
		else if(type&DT_PREV)
		{	root->right = link.left;
			root->left = NIL(Dtlink_t*);
			link.left = root;
		dt_prev:
			if((root = link.right) )
			{	while((t = root->right) )
					LROTATE(root,t);
				link.right = root->left;
				goto has_root;
			}
			else	goto no_root;
		}
		else if(type&(DT_DELETE|DT_DETACH))
		{	/* taking an object out of the dictionary */
		dt_delete:
			obj = _DTOBJ(root,lk);
			if(disc->freef && (type&DT_DELETE))
				(*disc->freef)(dt,obj,disc);
			if(disc->link < 0)
				(*dt->memoryf)(dt,(Void_t*)root,0,disc);
			if((dt->data->size -= 1) < 0)
				dt->data->size = -1;
			goto no_root;
		}
		else if(type&(DT_INSERT|DT_ATTACH))
		{	if(dt->meth->type&DT_OSET)
				goto has_root;
			else
			{	root->left = NIL(Dtlink_t*);
				root->right = link.left;
				link.left = root;
				goto dt_insert;
			}
		}
		else if(type&DT_RENEW) /* a duplicate */
		{	if(dt->meth->type&DT_OSET)
			{	if(disc->freef)
					(*disc->freef)(dt,obj,disc);
				if(disc->link < 0)
					(*dt->memoryf)(dt,(Void_t*)me,0,disc);
			}
			else
			{	me->left = NIL(Dtlink_t*);
				me->right = link.left;
				link.left = me;
				dt->data->size += 1;
			}
			goto has_root;
		}
	}
	else
	{	/* not found, finish up LEFT and RIGHT trees */
		r->left = NIL(Dtlink_t*);
		l->right = NIL(Dtlink_t*);

		if(type&DT_NEXT)
			goto dt_next;
		else if(type&DT_PREV)
			goto dt_prev;
		else if(type&(DT_SEARCH|DT_MATCH))
		{ no_root:
			while((t = r->left) )
				r = t;
			r->left = link.right;
			dt->data->here = link.left;
			return (type&DT_DELETE) ? obj : NIL(Void_t*);
		}
		else if(type&(DT_INSERT|DT_ATTACH))
		{ dt_insert:
			if(disc->makef && (type&DT_INSERT))
				obj = (*disc->makef)(dt,obj,disc);
			if(obj)
			{	if(lk >= 0)
					root = _DTLNK(obj,lk);
				else
				{	root = (Dtlink_t*)(*dt->memoryf)
						(dt,NIL(Void_t*),sizeof(Dthold_t),disc);
					if(root)
						((Dthold_t*)root)->obj = obj;
					else if(disc->makef && disc->freef &&
						(type&DT_INSERT))
						(*disc->freef)(dt,obj,disc);
				}
			}
			if(root)
			{	if(dt->data->size >= 0)
					dt->data->size += 1;
				goto has_root;
			}
			else	goto no_root;
		}
		else if(type&DT_RENEW)
		{	root = me;
			dt->data->size += 1;
			goto has_root;
		}
		else /*if(type&DT_DELETE)*/
		{	obj = NIL(Void_t*);
			goto no_root;
		}
	}

	return NIL(Void_t*);
}

/* make this method available */
static Dtmethod_t	_Dtoset =  { dttree, DT_OSET };
static Dtmethod_t	_Dtobag =  { dttree, DT_OBAG };
__DEFINE__(Dtmethod_t*,Dtoset,&_Dtoset);
__DEFINE__(Dtmethod_t*,Dtobag,&_Dtobag);

#ifndef KPVDEL /* backward compatibility - delete next time around */
Dtmethod_t		_Dttree = { dttree, DT_OSET };
__DEFINE__(Dtmethod_t*,Dtorder,&_Dttree);
__DEFINE__(Dtmethod_t*,Dttree,&_Dttree);
#endif

#ifdef NoF
NoF(dttree)
#endif