/***********************************************************************
*                                                                      *
*               This software is part of the ast package               *
*          Copyright (c) 1985-2011 AT&T Intellectual Property          *
*                      and is licensed under the                       *
*                 Eclipse Public License, Version 1.0                  *
*                    by AT&T Intellectual Property                     *
*                                                                      *
*                A copy of the License is available at                 *
*          http://www.eclipse.org/org/documents/epl-v10.html           *
*         (with md5 checksum b35adb5213ca9657e911e9befb180842)         *
*                                                                      *
*              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"

/*	Set a view path from dict to view.
**
**	Written by Kiem-Phong Vo (5/25/96)
*/

/* these operations must be done without viewpathing */
#define DT_NOVIEWPATH	(DT_INSERT|DT_APPEND|DT_DELETE|\
			 DT_ATTACH|DT_DETACH|DT_RELINK|DT_CLEAR| \
			 DT_FLATTEN|DT_EXTRACT|DT_RESTORE|DT_STAT)

#if __STD_C
static Void_t* dtvsearch(Dt_t* dt, reg Void_t* obj, reg int type)
#else
static Void_t* dtvsearch(dt,obj,type)
Dt_t*		dt;
reg Void_t*	obj;
reg int		type;
#endif
{
	int		cmp;
	Dt_t		*d, *p;
	Void_t		*o, *n, *oky, *nky;

	if(type&DT_NOVIEWPATH)
		return (*(dt->meth->searchf))(dt,obj,type);

	o = NIL(Void_t*);

	/* these ops look for the first appearance of an object of the right type */
	if((type & (DT_MATCH|DT_SEARCH)) ||
	   ((type & (DT_FIRST|DT_LAST|DT_ATLEAST|DT_ATMOST)) && !(dt->meth->type&DT_ORDERED) ) )
	{	for(d = dt; d; d = d->view)
			if((o = (*(d->meth->searchf))(d,obj,type)) )
				break;
		dt->walk = d;
		return o;
	}

	if(dt->meth->type & DT_ORDERED) /* ordered sets/bags */
	{	if(!(type & (DT_FIRST|DT_LAST|DT_NEXT|DT_PREV|DT_ATLEAST|DT_ATMOST)) )
			return NIL(Void_t*);

		/* find the min/max element that satisfies the op requirement */
		n = nky = NIL(Void_t*); p = NIL(Dt_t*);
		for(d = dt; d; d = d->view)
		{	if(!(o = (*d->meth->searchf)(d, obj, type)) )
				continue;
			oky = _DTKEY(d->disc,o);

			if(n) /* get the right one among all dictionaries */
			{	cmp = _DTCMP(d,oky,nky,d->disc);
				if(((type & (DT_NEXT|DT_FIRST|DT_ATLEAST)) && cmp < 0) ||
				   ((type & (DT_PREV|DT_LAST|DT_ATMOST)) && cmp > 0) )
					goto b_est;
			}
			else
			{ b_est: /* current best element to fit op requirement */
				p  = d;
				n  = o;
				nky = oky;
			}
		}

		dt->walk = p;
		return n;
	}

	/* unordered collections */
	if(!(type&(DT_NEXT|DT_PREV)) )
		return NIL(Void_t*);

	if(!dt->walk )
	{	for(d = dt; d; d = d->view)
			if((o = (*(d->meth->searchf))(d, obj, DT_SEARCH)) )
				break;
		dt->walk = d;
		if(!(obj = o) )
			return NIL(Void_t*);
	}

	for(d = dt->walk, obj = (*d->meth->searchf)(d, obj, type);; )
	{	while(obj) /* keep moving until finding an uncovered object */
		{	for(p = dt; ; p = p->view)
			{	if(p == d) /* adjacent object is uncovered */	
					return obj;
				if((*(p->meth->searchf))(p, obj, DT_SEARCH) )
					break;
			}
			obj = (*d->meth->searchf)(d, obj, type);
		}

		if(!(d = dt->walk = d->view) ) /* move on to next dictionary */
			return NIL(Void_t*);
		else if(type&DT_NEXT)
			obj = (*(d->meth->searchf))(d,NIL(Void_t*),DT_FIRST);
		else	obj = (*(d->meth->searchf))(d,NIL(Void_t*),DT_LAST);
	}
}

#if __STD_C
Dt_t* dtview(reg Dt_t* dt, reg Dt_t* view)
#else
Dt_t* dtview(dt,view)
reg Dt_t*	dt;
reg Dt_t*	view;
#endif
{
	reg Dt_t*	d;

	if(view && view->meth != dt->meth) /* must use the same method */
		return NIL(Dt_t*);

	/* make sure there won't be a cycle */
	for(d = view; d; d = d->view)
		if(d == dt)
			return NIL(Dt_t*);

	/* no more viewing lower dictionary */
	if((d = dt->view) )
		d->nview -= 1;
	dt->view = dt->walk = NIL(Dt_t*);

	if(!view)
	{	dt->searchf = dt->meth->searchf;
		return d;
	}

	/* ok */
	dt->view = view;
	dt->searchf = dtvsearch;
	view->nview += 1;

	return view;
}