/*-------------------------------------------------------------------------
 *
 *
 *                                AVLTREE 1.0
 *                       (c) Werner Van Belle aug 95
 *
 * 
 * NODE AddAvlNode(NODE root, NODE who)
 *   Voegt who toe aan root, geeft als resultaat de nieuwe root weer
 *   O(log2n)
 * 
 * NODE SearchAvlNode(NODE root, SEARCH_DATA watte)
 *   Zoekt watte op in root, geeft als resultaat de bijhorende node weer
 *   O(<log2n)
 * 
 * NODE DeleteAvlNode(NODE root, SEARCH_DATA wie)
 *   Verwijdert wie uit root, geeft als resultaat de nieuwe root weer
 *   O(log2n)
 * 
 * int ValidAvlTree(NODE root)
 *   Controleert of de AVL-tree wel aan de AVL-voorwaarde voldoet. Hier 
 *   wordt niet gecontroleerd of de linkerkinderen kleiner zijn dan root 
 *   en de rechterkinderen groter zijn dan root 
 *   O(n)
 * 
 * int AvlTreeCount(NODE root)
 *   geeft weer hoeveel elementen in de tree steken. 
 *   O(n)
 * 
 * int AvlDepth(NODE root)
 *   geeft de maximum diepte van een pad doorheen de tree weer. 
 *   O(n)
 *
 * void PrintAvlTree(NODE root, int diepte)
 *   Print de avltree. Deze functie is enkel aanwezig als PRINT_NODE
 *   gedefinieerd is. Het output formaat is 
 *     .rechterkind
 *     rootzelf
 *     .linkerkind
 */

#include <assert.h>
/* #define DEBUG_NODES */
#define LEFT(WHO) WHO(Left,Right,LEFT_NODE,RIGHT_NODE,SET_LEFT_NODE,SET_RIGHT_NODE,\
	      NEGATIVE_FLAG,POSITIVE_FLAG,SET_NEGATIVE_FLAG,SET_POSITIVE_FLAG)
#define RIGHT(WHO) WHO(Right,Left,RIGHT_NODE,LEFT_NODE,SET_RIGHT_NODE,SET_LEFT_NODE,\
	      POSITIVE_FLAG,NEGATIVE_FLAG,SET_POSITIVE_FLAG,SET_NEGATIVE_FLAG)
#define CREATE_ROTATE(lname,rname,LN,RN,SLN,SRN,NF,PF,SNF,SPF)\
static NODE Rotate##lname(NODE root, int* depthchanged)\
     {\
	NODE sec;\
	assert(!ISNULLNODE(root) && depthchanged);\
	sec=RN(root);\
	assert(PF(root));\
	if (!(NF(sec)))\
	  {\
	     /* printf("single " #lname " rotation ");\
	     PRINT_NODE(root);\
	     printf("\n"); */\
	     SRN(root,LN(sec));\
	     SLN(sec,root);\
	     if (PF(sec))\
	       {\
		  SET_ZERO_FLAG(root);\
		  SET_ZERO_FLAG(sec);\
		  *depthchanged=1;\
		  return sec;\
	       }\
	     SPF(root);\
	     SNF(sec);\
	     return sec;\
	  }\
	  {\
	     NODE third=LN(sec);\
             /* printf("double " #lname " rotation ");\
	     PRINT_NODE(root);\
	     printf("\n");*/\
	     SLN(sec,RN(third));\
	     SRN(root,LN(third));\
	     SRN(third,sec);\
	     SLN(third,root);\
	     *depthchanged=1;\
	     if (NF(third))\
	       {\
		  SPF(sec);\
		  SET_ZERO_FLAG(root);\
		  SET_ZERO_FLAG(third);\
		  return third;\
	       }\
	     if (ZERO_FLAG(third))\
	       {\
		  SET_ZERO_FLAG(sec);\
		  SET_ZERO_FLAG(third);\
		  SET_ZERO_FLAG(root);\
		  return third;\
	       }\
	     SET_ZERO_FLAG(sec);\
	     SNF(root);\
	     SET_ZERO_FLAG(third);\
	     return third;\
	  }\
     }

LEFT(CREATE_ROTATE);
RIGHT(CREATE_ROTATE);


#define CREATE_HANG(lname,rname,LN,RN,SLN,SRN,NF,PF,SNF,SPF)\
     {\
	SLN(root,AddAvlNode_aux(LN(root),who,&heightchanged));\
	if (heightchanged)\
	  {\
	     if (ZERO_FLAG(root))\
	       {\
		  SNF(root);\
		  *depthchanged=1;\
		  return root;\
	       }\
	     if (PF(root))\
	       {\
		  SET_ZERO_FLAG(root);\
		  return root;\
	       }\
	     heightchanged=0;\
	     root=Rotate##rname(root,&heightchanged);\
	     /* als heightchanged verandert is; is root kleiner\
	      * geworden */\
	     if (!heightchanged) *depthchanged=1;\
	     return root;\
	  }\
	return root;\
     }

static NODE AddAvlNode_aux(NODE root, NODE who, int* depthchanged)
/* geeft de nieuwe root weer */
     {
	int CompareResult, heightchanged=0;
	assert(depthchanged);
        #ifdef DEBUG_NODES
	printf("add ");
	PRINT_NODE(who);
	printf(" to root ");
	if (ISNULLNODE(root)) printf("(null)");
	else PRINT_NODE(root);
	printf("\n");
	#endif
	if (ISNULLNODE(who)) return root;
	SET_LEFT_NODE(who,NULLNODE);
	SET_RIGHT_NODE(who,NULLNODE);
	SET_ZERO_FLAG(who);
	if (ISNULLNODE(root)) 
	  {
	     *depthchanged=1;
	     return who;
	  }
	CompareResult=COMPARE_ADD_DATA(root,who);
	/* 1. geen dubbels */
	assert(CompareResult);
	/* 2. hang links aan */
	if (CompareResult==1) LEFT(CREATE_HANG);
	/* 3. hang rechts aan */
	RIGHT(CREATE_HANG);
     }

NODE AddAvlNode(NODE root, NODE who)
/* geeft de nieuwe root weer */
     {
	int depthchanged=0;
	return AddAvlNode_aux(root,who,&depthchanged);
     }

NODE SearchAvlNode(NODE root, SEARCH_DATA watte)
/* geeft het resultaat van het zoeken weer, NULLNODE indien niet gevonden */
     {
	int CompareResult;
	while(root)
	  {
	     CompareResult=COMPARE_SEARCH_DATA(root,watte);
	     if (CompareResult==0) return root;
	     if (CompareResult==1) root=LEFT_NODE(root);
	     else root=RIGHT_NODE(root);
	  }
	return NULLNODE;
     }


#define CREATE_FREEDOM(lname,rname,LN,RN,SLN,SRN,NF,PF,SNF,SPF)\
static NODE lname##Freedom_aux(NODE cur,NODE *placetostorefreedom,int*heightchanged)\
     {\
	assert(!ISNULLNODE(cur));\
	assert(placetostorefreedom);\
	if (ISNULLNODE(RN(cur)))\
	  {\
	     if (ISNULLNODE(LN(cur)))\
	       {\
		  *placetostorefreedom=cur;\
		  *heightchanged=1;\
		  return NULLNODE;\
	       }\
	     *heightchanged=1;\
	     *placetostorefreedom=cur;\
	     return LN(cur);\
	  }\
	  {\
	     int takverkleind=0;\
	     SRN(cur,lname##Freedom_aux(RN(cur),placetostorefreedom,&takverkleind));\
	     if (takverkleind) \
	       {\
		  if (NF(cur)) return Rotate##rname(cur,heightchanged);\
		  if (PF(cur))\
		    {\
		       SET_ZERO_FLAG(cur);\
		       *heightchanged=1;\
		       return cur;\
		    }\
		  SNF(cur);\
		  return cur;\
	       }\
	     return cur;\
	  }\
     }\
\
static NODE Get##lname##Freedom(NODE root, NODE*placetostorefreedom,int *heightchanged)\
     {\
	NODE lname;\
	assert(!ISNULLNODE(root));\
	assert(!ISNULLNODE(LN(root)));\
	assert(heightchanged);\
	assert(placetostorefreedom);\
	lname=LN(root);\
	if (!ISNULLNODE(RN(lname)))\
	  return lname##Freedom_aux(lname,placetostorefreedom,heightchanged);\
	*heightchanged=1;\
	*placetostorefreedom=lname;\
	return LN(lname);\
     }

LEFT(CREATE_FREEDOM)
RIGHT(CREATE_FREEDOM)

#define CREATE_ZAK(lname,rname,LN,RN,SLN,SRN,NF,PF,SNF,SPF)\
SLN(root,DeleteAvlNode_naardelete(LN(root),wie,&takkleiner));\
if (takkleiner)\
     {\
	if (NF(root))\
	  {\
	     SET_ZERO_FLAG(root);\
	     *heightchanged=1;\
	     return root;\
	  }\
	if (ZERO_FLAG(root))\
	  {\
	     SPF(root);\
	     return root;\
	  }\
	return Rotate##lname(root,heightchanged);\
     }\
return root;

static NODE DeleteAvlNode_naardelete(NODE root, SEARCH_DATA wie, int* heightchanged)
     {
	int CompareResult,takkleiner=0;
	assert(heightchanged);
	if (ISNULLNODE(root)) return root;
	CompareResult=COMPARE_SEARCH_DATA(root,wie);
	switch (CompareResult)
	  {
	   case -1: /* root<wie */ RIGHT(CREATE_ZAK);
	   case 1: /* root>wie */ LEFT(CREATE_ZAK);
	   case 0: /* root==wie */
	     /* nu een opnderscheid maken voor welke kinderen de 
	      * root heeft */
	     if (ISNULLNODE(LEFT_NODE(root)) && ISNULLNODE(RIGHT_NODE(root)))
	       {
		  DELETE_NODE(root);
		  *heightchanged=1;
		  return NULLNODE;
	       }
	     if (ISNULLNODE(LEFT_NODE(root)))
	       {
		  NODE rechter;
		  rechter=RIGHT_NODE(root);
		  assert(POSITIVE_FLAG(root));
		  assert(!ISNULLNODE(rechter));
		  assert(ISNULLNODE(LEFT_NODE(rechter)));
		  assert(ISNULLNODE(RIGHT_NODE(rechter)));
		  *heightchanged=1;
		  DELETE_NODE(root);
		  return rechter;
	       }
	     if (ISNULLNODE(RIGHT_NODE(root)))
	       {
		  NODE linker;
		  linker=LEFT_NODE(root);
		  assert(NEGATIVE_FLAG(root));
		  assert(!ISNULLNODE(linker));
		  assert(ISNULLNODE(LEFT_NODE(linker)));
		  assert(ISNULLNODE(RIGHT_NODE(linker)));
		  DELETE_NODE(root);
		  *heightchanged=1;
		  return linker;
	       }
	     if (POSITIVE_FLAG(root))
	       {
		  NODE freedom;
		  SET_RIGHT_NODE(root,GetRightFreedom(root,&freedom,heightchanged));
		  SET_LEFT_NODE(freedom,LEFT_NODE(root));
		  SET_RIGHT_NODE(freedom,RIGHT_NODE(root));
		  if (*heightchanged) SET_ZERO_FLAG(freedom);
		  else SET_POSITIVE_FLAG(freedom);
		  DELETE_NODE(root);
		  return freedom;
	       }
	     if (NEGATIVE_FLAG(root))
	       {
		  NODE freedom;
		  SET_LEFT_NODE(root,GetLeftFreedom(root,&freedom,heightchanged));
		  SET_LEFT_NODE(freedom,LEFT_NODE(root));
		  SET_RIGHT_NODE(freedom,RIGHT_NODE(root));
		  if (*heightchanged) SET_ZERO_FLAG(freedom);
		  else SET_NEGATIVE_FLAG(freedom);
		  DELETE_NODE(root);
		  return freedom;
	       }
	     if (ZERO_FLAG(root))
	       {
		  NODE freedom;
		  int takverkleind=0;
		  SET_LEFT_NODE(root,GetLeftFreedom(root,&freedom,&takverkleind));
		  SET_LEFT_NODE(freedom,LEFT_NODE(root));
		  SET_RIGHT_NODE(freedom,RIGHT_NODE(root));
		  if (takverkleind) SET_POSITIVE_FLAG(freedom);
		  else  SET_ZERO_FLAG(freedom);
		  DELETE_NODE(root);
		  return freedom;
	       }
	   default: 
	     assert(0);
	     exit(57);
	  }
     }

NODE DeleteAvlNode(NODE root, SEARCH_DATA wie)
     {
	int heightchanged=0;
	return DeleteAvlNode_naardelete(root,wie,&heightchanged);
     }

int AvlDepth(NODE root)
     {
	int l,r;
	if (ISNULLNODE(root)) return 0;
	l=AvlDepth(LEFT_NODE(root));
	r=AvlDepth(RIGHT_NODE(root));
	if (l>r) return l+1;
	return r+1;
     }

int ValidAvlTree(NODE root)
     {
	if (ISNULLNODE(root)) return 1;
	if (!ValidAvlTree(LEFT_NODE(root))) return 0;
	if (!ValidAvlTree(RIGHT_NODE(root))) return 0;
	if (POSITIVE_FLAG(root))
	  return (AvlDepth(LEFT_NODE(root))==(AvlDepth(RIGHT_NODE(root))-1));
	if (NEGATIVE_FLAG(root))
	  return (AvlDepth(LEFT_NODE(root))==(AvlDepth(RIGHT_NODE(root))+1));
	return (AvlDepth(LEFT_NODE(root))==AvlDepth(RIGHT_NODE(root)));
     }

int AvlTreeCount(NODE root)
     {
	if (ISNULLNODE(root)) return 0;
	return 1+AvlTreeCount(LEFT_NODE(root))+AvlTreeCount(RIGHT_NODE(root));
     }

#ifdef PRINT_NODE
void PrintAvlTree(NODE root, int diepte)
     {
	int t,l,r;
	if (ISNULLNODE(root)) return;
	PrintAvlTree(RIGHT_NODE(root),diepte+1);
	for(t=diepte;t>0;t--) printf(".");
	PRINT_NODE(root);
	l=AvlDepth(LEFT_NODE(root));
	r=AvlDepth(RIGHT_NODE(root));
	printf(" left=%d, right=%d, count=%d ",l,r,AvlTreeCount(root));
	if ((abs(l-r)>1) || 
	    (l<r && !POSITIVE_FLAG(root)) ||
	    (l>r && !NEGATIVE_FLAG(root)) ||
	    (l==r && !ZERO_FLAG(root)))
	  printf("*********");
	printf("\n");
	PrintAvlTree(LEFT_NODE(root),diepte+1);
     }
#endif