#include "def.h"
#include "macro.h"
/* AK  291288 */
typedef struct node {
	char * _key; /* dies enthaelt ein object */
	struct node * _l, * _r;
	char _rtag;
} Node;

#define KEY(p) ((p) -> _key)
#define L(p) ((p) -> _l)
#define R(p) ((p) -> _r)
#define RTAG(p) ((p) -> _rtag)


/* TSEARCH(3C) */
typedef enum {
	preorder, postorder, endorder, leaf }
VISIT;


static INT AK_twalk();
static void AK_tfree();
static char ** AK_tsearch();
static char ** AK_tfind();
static void walk();
static void freeself_bintree_action();
static void fprint_bintree_action();
static void insert_bt_bt_action();
static void copy_bintree_action();
static void t_BINTREE_LIST_action();
static void t_BINTREE_SCHUR_action();

static char *_bt_p1, *_bt_p2, *_bt_p3; /* fur twalk */
#define TWALK AK_twalk
#define TSEARCH AK_tsearch
#define TFIND AK_tfind

#ifdef BINTREETRUE
static void freeself_bintree_action(a,type) OP *a; VISIT type;
/* AK 210891 V1.3 */
{
	if ((type==postorder) ||  (type==leaf)) 	
		SYMfreeall(*a);
}
#endif /*BINTREETRUE*/

#ifdef BINTREETRUE
INT freeself_bintree(a) OP a;
/* AK 050891 V1.3 */
{
	OBJECTSELF d ;
	d = S_O_S(a);
	AK_tfree(& d.ob_charpointer,freeself_bintree_action,NULL,NULL,NULL);
	C_O_K(a,EMPTY);
	return OK; /* AK 050891 */
}
#endif /*BINTREETRUE*/


#ifdef BINTREETRUE
INT init_bintree(a) OP a;
/* AK 050891 V1.3 */
{
	OBJECTSELF d;
	C_O_K(a,BINTREE);
	d.ob_charpointer = (char *) NULL;
	C_O_S(a,d);
	return(OK);
}
#endif /*BINTREETRUE*/

#ifdef BINTREETRUE
static void fprint_bintree_action(a,type,l) OP *a;VISIT type;INT l;
/* AK 210891 V1.3 */
{
	FILE *p1 = (FILE *) _bt_p1;
	if ((type==postorder)||  (type==leaf))
	{
		fprint(p1,*a);
		fprintf(p1," ");
		if (p1==stdout) 
			{	
			zeilenposition++;
			if (zeilenposition >70L) {
				fprintf(p1,"\n");
				zeilenposition=0L; }
			}
	}
}
#endif /*BINTREETRUE*/


#ifdef BINTREETRUE
INT fprint_bintree(fp,a) FILE *fp; OP a;
/* AK 050891 V1.3 */
/* gibt einen bintree aus */
{
	void fprint_bintree_action();
	OBJECTSELF d;
	d = S_O_S(a);
	if (d.ob_charpointer == NULL)
		{
		fprintf(fp,"empty tree");
		if (fp == stdout) zeilenposition += 10L;
		}
	else
		{
		_bt_p1 = (char *) fp;
		_bt_p2 = (char *) NULL;
		_bt_p3 =(char *)  NULL;
		TWALK(d.ob_charpointer,fprint_bintree_action);
		}
	return OK;
}
#endif /*BINTREETRUE*/

#ifdef BINTREETRUE
INT insert_bintree(a,bt,eh,cf) OP a,bt; INT (*cf)(), (*eh)();
/* fuegt a in bintree bt ein */
/* cf ist die vergleichsfunktion
	   eh gibt die operation bei schon vorhandenem
	   gleichen eintrag an */
/* AK 040189 */ /* AK 210891 V1.3 */
{
	INT erg = OK;
	char ** result;

	if (S_O_K(a) == BINTREE) 
		{
		erg += insert_bt_bt(a,bt,eh,cf);
		goto endr_ende;
		}

	if (cf == NULL) cf = comp;
	/* default wert */

	result = TSEARCH(a, &((S_O_S(bt)).ob_charpointer) ,cf);
	if (*result == (char *)a) 
		return INSERTOK;
				/* d.h. das element wurde eingefuegt */
	else 			/* d.h. es wurde ein gleiches element festgestelt
				und result ist ein pointer darauf */
		{
		if (eh != NULL) 
			(*eh)(a,*result);
		SYMfreeall(a);
		return INSERTEQ;
		}
	ENDR("insert_bt");
}



INT insert_bt_bt(a,bt,eh,cf) OP a,bt; INT (*cf)(), (*eh)();
/* fuegt a was auch bintree ist in bintree bt ein */
/* cf ist die vergleichsfunktion
	   eh gibt die operation bei schon vorhandenem
	   gleichen eintrag an */
/* AK 090189 */ /* AK 210891 V1.3 */
{
	OBJECTSELF d;
	INT erg = OK;
	d = S_O_S(a);
	AK_tfree(&d.ob_charpointer,insert_bt_bt_action,bt,eh,cf);
	C_O_K(a,EMPTY); /* leer setzen */
	erg += SYMfreeall(a);
	ENDR("insert_bt_bt");
}



static void insert_bt_bt_action(a,type,bt,eh,cf)OP *a,bt; VISIT type; 
		INT (*eh)(),(*cf)();
/* AK 210891 V1.3 */
{
	INT insert_erg;

	if ((type==postorder)||  (type==leaf))
	{
		insert_erg = insert_bintree(*a,bt,eh,cf);
		/* if (insert_erg == INSERTEQ) SYMfreeall(*a); */
	}
}
#endif /*BINTREETRUE*/

#ifdef BINTREETRUE
INT copy_bintree(a,b) OP a,b;
/* AK 210891 V1.3 */
{
	OBJECTSELF d;

	init(BINTREE,b);
	d = S_O_S(a);
		_bt_p1 = (char *) b;
		_bt_p2 = (char *) NULL;
		_bt_p3 = (char *) NULL;
	TWALK(d.ob_charpointer,copy_bintree_action);
	return OK;
}
#endif /*BINTREETRUE*/

#ifdef BINTREETRUE
static void copy_bintree_action(a,type,l) OP *a; VISIT type; INT l;
/* AK 210891 V1.3 */
{
	OP bt = (OP) _bt_p1;
	if ((type==postorder)||  (type==leaf))
	{
		OP c=callocobject();
		copy(*a,c);
		insert_bintree(c,bt,NULL,NULL);
	}
}
#endif /*BINTREETRUE*/


#ifdef BINTREETRUE
OP find_bintree(a,b) OP a,b;
/* test ob a in b */
/* AK 050396 */
{
	char ** result;
	result = TFIND(a, &((S_O_S(b)).ob_charpointer) ,comp);
	if (result == NULL) return NULL;
	return (OP) *result;
	
}



static Node ** find(k,rootp,compar, parent, c) char *k; 
	register Node ** rootp; INT (*compar)(); 
	Node ** parent; INT *c;
/* AK 210891 V1.3 */
{
	*parent = (Node *) 0;
	if (rootp && *rootp)
		for (;;)
		{
			if ((*c = (*compar) (k,KEY(*rootp))) == 0L)
				break;
			*parent = *rootp;
			if( *c < 0L)
			{
				rootp = & L(*parent);
				if (! *rootp) break;
			}
			else {
				rootp = & R(*parent);
				if (RTAG(*parent)) break;
			}
		}

	return (rootp);
}


static char ** AK_tfind(k,rootp,compar) char *k; 
	register Node ** rootp;
	INT (*compar)();
{
	Node * parent;
        INT c;
	if (rootp = find(k,rootp,compar, &parent, &c))
                if (*rootp && (c == 0))
                        return (&KEY(*rootp));
	return NULL;
}

#endif /*BINTREETRUE*/
static char ** AK_tsearch(k,rootp,compar) char *k; 
	register Node ** rootp;
	INT (*compar)();
/* AK 210891 V1.3 */
{
#ifdef BINTREETRUE
	register Node *p;
	Node * parent;
	INT c;

	if (rootp = find(k,rootp,compar, &parent, &c))
		if (*rootp && c == 0)
			return (&KEY(*rootp));
		else if (p = (Node *) SYM_malloc(sizeof(Node)))
		{
			KEY(p) =k;
			L(p) = (Node *) 0;
			if (parent && c>0)
			{
				R(p) = R(parent);
				R(parent) = p, RTAG(parent)= 0;
			}
			else
			{
				R(p) = parent;
				* rootp = p;
			}
			RTAG(p) = 1;
			return (&KEY(p));
		}
	return ((char**) 0);
#endif /*BINTREETRUE*/
}


static void walk(root,action,l) register Node *root; 
	void (*action) (); 
	INT l; 
/* fuer parameter bei action */

/* AK 210891 V1.3 */
{
#ifdef BINTREETRUE
	if (! L(root) && RTAG(root))
		(*action) (&KEY(root), leaf, l);
	else
	{
		(*action) (&KEY(root), preorder, l);
		if (L(root))
			walk(L(root), action, l+1L);
		(*action) (&KEY(root), postorder, l);
		if (! RTAG(root))
			walk(R(root), action, l+1L);
		(*action) (&KEY(root), endorder, l);

	}
#endif /*BINTREETRUE*/
}

static INT AK_twalk(root,action) Node *root; 
	void (*action) (); 
/* AK 210891 V1.3 */
{
#ifdef BINTREETRUE
	if (root)
		walk(root,action,0L);
	return OK;
#endif /*BINTREETRUE*/
}


static void AK_tfree(rootp,a) Node **rootp; void (*a)();
/* AK 210891 V1.3 */
{
#ifdef BINTREETRUE
	register Node *root,*p;

	if (!rootp || ! (root = *rootp))
		return;
	* rootp = (Node *)0;
	for (;;)
	{
		while (p = L(root))
			root = p;
		if (RTAG(root))
		{
			if (a)
				(* a)(&KEY(root), leaf);
			do
			{
				p=R(root),SYM_free(root),root=p;
				if (! root)
					return;
				if (a)
					(* a)(&KEY(root),postorder);
			} while(RTAG(root));
		}
		else
		{
			if (a)
				(* a)(&KEY(root),postorder);
		}
		p=R(root),SYM_free(root),root=p;
	}
#endif /*BINTREETRUE*/
}

#ifdef BINTREETRUE
INT t_BINTREE_LIST(a,b) OP a,b;
/* wandelt einen BINTREE in ein SYMLIST object um */
/* die liste ist nach den gleichen vergleich sortiert */
/* AK 070390 V1.1 */ /* AK 050891 V1.3 */
{
	void t_BINTREE_LIST_action();
	INT erg = OK; /* AK 170392 */
	OP h, *h2;

	if (check_equal_2(a,b,t_BINTREE_LIST,&erg) == EQUAL)
                return erg;


	h = callocobject();
	erg += b_sn_l(NULL,NULL,h);

	h2 = &S_L_N(h);
		_bt_p1 = (char *)&h2;
		_bt_p2 = (char *)NULL;
		_bt_p3 = (char *)NULL;
	erg += TWALK((S_O_S(a)).ob_charpointer,t_BINTREE_LIST_action);

	if (S_L_N(h) != NULL) 
		*b = *S_L_N(h);
	else 
		erg += b_sn_l(NULL,NULL,b);

	C_O_K(S_L_N(h),EMPTY);
	SYMfreeall(S_L_N(h));
	C_L_N(h,NULL); 
	erg += SYMfreeall(h); 
	ENDR("t_BINTREE_LIST");
}
#endif /* BINTREETRUE */

#ifdef BINTREETRUE
static void t_BINTREE_LIST_action(a,type,l)OP *a;VISIT type;INT l;
/* AK 210891 V1.3 */
{
	if ((type==postorder) ||  (type==leaf))
		{
		**(OP **)_bt_p1 = callocobject();
		b_sn_l(callocobject(),NULL,**(OP **)_bt_p1);
		copy(*a,S_L_S(**(OP **)_bt_p1));
		*(OP **)_bt_p1 = & S_L_N(**(OP **)_bt_p1);
		}
}
#endif /* BINTREETRUE */

#ifdef BINTREETRUE
INT t_BINTREE_SCHUR(a,b) OP a,b;
/* wandelt einen BINTREE in ein SCHUR object um */
/* die liste ist nach den gleichen vergleich sortiert */
/* AK 070390 V1.1 */ /* AK 050891 V1.3 */
{
	void t_BINTREE_SCHUR_action();
	OP *h2,h;
	INT erg = OK;

	if (check_equal_2(a,b,t_BINTREE_SCHUR,&erg) == EQUAL)
                return erg;
		
	h = callocobject();
	erg += b_sn_l(NULL,NULL,h);
	C_O_K(h,SCHUR);

	h2 = &S_L_N(h);
		_bt_p1 = (char *)&h2;
		_bt_p2 = (char *)NULL;
		_bt_p3 = (char *)NULL;
	TWALK((S_O_S(a)).ob_charpointer,t_BINTREE_SCHUR_action);

	if (S_L_N(h) != NULL) 
		*b = *S_L_N(h);
	else 
		{
		erg += b_sn_l(NULL,NULL,b);
		C_O_K(b,SCHUR);
		}

	C_O_K(S_L_N(h),EMPTY);
	erg += SYMfreeall(S_L_N(h));
	C_L_N(h,NULL); 
	erg += SYMfreeall(h); 
	return erg;
}
#endif /* BINTREETRUE */

#ifdef BINTREETRUE
static void t_BINTREE_SCHUR_action(a,type,l)OP *a;VISIT type;INT l;
/* AK 210891 V1.3 */
{
	if ((type==postorder)||  (type==leaf))
		{
		**(OP**)_bt_p1 = callocobject();
		b_sn_l(callocobject(),NULL,**(OP**)_bt_p1);
		C_O_K(**(OP**)_bt_p1,SCHUR);
		copy(*a,S_L_S(**(OP**)_bt_p1));
		*(OP**)_bt_p1 = & S_L_N(**(OP**)_bt_p1);
		}
}
#endif /* BINTREETRUE */
#ifdef BINTREETRUE
INT test_bintree()
{
	OP a,b,c;
	a = callocobject();
	b = callocobject();
	c = callocobject();
	printeingabe("test_bintree:init(BINTREE,a) ");
	init(BINTREE,a); println(a);
	printeingabe("test_bintree:insert(5L,a) ");
	m_i_i(5L,b);insert(b,a,NULL,NULL); println(a);
	printeingabe("test_bintree:insert(7L,a) ");
	b = callocobject();
	m_i_i(7L,b);
	insert(b,a,NULL,NULL);  println(a);
	printeingabe("test_bintree:copy(a,c) ");
	copy(a,c); println(c);
	printeingabe("test_bintree:insert(9L,c) ");
	b = callocobject();
	m_i_i(9L,b);
	insert(b,c,NULL,NULL); 
	println(c);
	SYMfreeall(a);
	SYMfreeall(c);
	return OK;
}
#endif /* BINTREETRUE */
#ifdef BINTREETRUE
#endif /* BINTREETRUE */

