/*-------------------------------------------------------------------------
 * 
 * 
 *                                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 */
static NODE RotateLeft(NODE root, int* depthchanged)
     {
	NODE sec;
	assert(!ISNULLNODE(root));
	assert(depthchanged);
	sec=RIGHT_NODE(root);
	assert(POSITIVE_FLAG(root));
	if (!(NEGATIVE_FLAG(sec)))
	  {
             #ifdef DEBUG_NODES
	     printf("single left rotation ");
	     PRINT_NODE(root);
	     printf("\n");
             #endif
	     SET_RIGHT_NODE(root,LEFT_NODE(sec));
	     SET_LEFT_NODE(sec,root);
	     if (POSITIVE_FLAG(sec))
	       {
		  SET_ZERO_FLAG(root);
		  SET_ZERO_FLAG(sec);
		  *depthchanged=1;
		  return sec;
	       }
	     SET_POSITIVE_FLAG(root);
	     SET_NEGATIVE_FLAG(sec);
	     return sec;
	  }
	  {
	     NODE third=LEFT_NODE(sec);
             #ifdef DEBUG_NODES
	     printf("double left rotation ");
	     PRINT_NODE(root);
	     printf("\n");
             #endif
	     SET_LEFT_NODE(sec,RIGHT_NODE(third));
	     SET_RIGHT_NODE(root,LEFT_NODE(third));
	     SET_RIGHT_NODE(third,sec);
	     SET_LEFT_NODE(third,root);
	     *depthchanged=1;
	     if (NEGATIVE_FLAG(third))
	       {
		  SET_POSITIVE_FLAG(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);
	     SET_NEGATIVE_FLAG(root);
	     SET_ZERO_FLAG(third);
	     return third;
	  }
     }

static NODE RotateRight(NODE root, int* depthchanged)
     {
	NODE sec;
	assert(!ISNULLNODE(root));
	assert(depthchanged);
	sec=LEFT_NODE(root);
	assert(NEGATIVE_FLAG(root));
	if (!(POSITIVE_FLAG(sec)))
	  {
             #ifdef DEBUG_NODES
	     printf("single right rotation ");
	     PRINT_NODE(root);
	     printf("\n");
             #endif
	     SET_LEFT_NODE(root,RIGHT_NODE(sec));
	     SET_RIGHT_NODE(sec,root);
	     if (NEGATIVE_FLAG(sec))
	       {
		  SET_ZERO_FLAG(root);
		  SET_ZERO_FLAG(sec);
		  *depthchanged=1;
		  return sec;
	       }
	     SET_NEGATIVE_FLAG(root);
	     SET_POSITIVE_FLAG(sec);
	     return sec;
	  }
        #ifdef DEBUG_NODES
	printf("double right rotation ");
	PRINT_NODE(root);
	printf("\n");
        #endif
	  {
	     NODE third=RIGHT_NODE(sec);
	     SET_RIGHT_NODE(sec,LEFT_NODE(third));
	     SET_LEFT_NODE(root,RIGHT_NODE(third));
	     SET_LEFT_NODE(third,sec);
	     SET_RIGHT_NODE(third,root);
	     *depthchanged=1;
	     if (NEGATIVE_FLAG(third))
	       {
		  SET_ZERO_FLAG(sec);
		  SET_POSITIVE_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_NEGATIVE_FLAG(sec);
	     SET_ZERO_FLAG(third);
	     SET_ZERO_FLAG(root);
	     return third;
	  }
     }


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)
	  {
	     SET_LEFT_NODE(root,AddAvlNode_aux(LEFT_NODE(root),who,&heightchanged));
	     if (heightchanged) 
	       {
		  if (ZERO_FLAG(root))
		    {
		       SET_NEGATIVE_FLAG(root);
		       *depthchanged=1;
		       return root;
		    }
		  if (POSITIVE_FLAG(root))
		    {
		       SET_ZERO_FLAG(root);
		       return root;
		    }
		  heightchanged=0;
		  root=RotateRight(root,&heightchanged); 
		  /* als heightchanged verandert is; is root kleiner 
		   * geworden */
		  if (!heightchanged) *depthchanged=1;
		  return root;
	       }
	     return root;
	  }
	/* 3. hang rechts aan */
	SET_RIGHT_NODE(root,AddAvlNode_aux(RIGHT_NODE(root),who,&heightchanged));
	if (heightchanged) 
	  {
	     if (ZERO_FLAG(root))
	       {
		  SET_POSITIVE_FLAG(root);
		  *depthchanged=1;
		  return root;
	       }
	     if (NEGATIVE_FLAG(root))
	       {
		  SET_ZERO_FLAG(root);
		  return root;
	       }
	     heightchanged=0;
	     root=RotateLeft(root,&heightchanged);
	     if (!heightchanged) *depthchanged=1;
	  }
	return root;
     }

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;
     }

static NODE LeftFreedom_aux(NODE cur,NODE *placetostorefreedom,int*heightchanged)
     {
	assert(!ISNULLNODE(cur));
	assert(placetostorefreedom);
	if (ISNULLNODE(RIGHT_NODE(cur)))
	  {
	     if (ISNULLNODE(LEFT_NODE(cur)))
	       {
		  *placetostorefreedom=cur;
		  *heightchanged=1;
		  return NULLNODE;
	       }
	     *heightchanged=1;
	     *placetostorefreedom=cur;
	     return LEFT_NODE(cur);
	  }
	  {
	     int takverkleind=0;
	     SET_RIGHT_NODE(cur,LeftFreedom_aux(RIGHT_NODE(cur),placetostorefreedom,&takverkleind));
	     if (takverkleind) 
	       {
		  if (NEGATIVE_FLAG(cur)) return RotateRight(cur,heightchanged);
		  if (POSITIVE_FLAG(cur))
		    {
		       SET_ZERO_FLAG(cur);
		       *heightchanged=1;
		       return cur;
		    }
		  SET_NEGATIVE_FLAG(cur);
		  return cur;
	       }
	     return cur;
	  }
     }

static NODE GetLeftFreedom(NODE root, NODE*placetostorefreedom,int *heightchanged)
     {
	NODE left;
	assert(!ISNULLNODE(root));
	assert(!ISNULLNODE(LEFT_NODE(root)));
	assert(heightchanged);
	assert(placetostorefreedom);
	left=LEFT_NODE(root);
	if (!ISNULLNODE(RIGHT_NODE(left)))
	  return LeftFreedom_aux(left,placetostorefreedom,heightchanged);
	*heightchanged=1;
	*placetostorefreedom=left;
	return LEFT_NODE(left);
     }

static NODE RightFreedom_aux(NODE cur,NODE *placetostorefreedom,int*heightchanged)
     {
	assert(!ISNULLNODE(cur));
	assert(placetostorefreedom);
	if (ISNULLNODE(LEFT_NODE(cur)))
	  {
	     if (ISNULLNODE(RIGHT_NODE(cur)))
	       {
		  *placetostorefreedom=cur;
		  *heightchanged=1;
		  return NULLNODE;
	       }
	     *heightchanged=1;
	     *placetostorefreedom=cur;
	     return RIGHT_NODE(cur);
	  }
	  {
	     int takverkleind=0;
	     SET_LEFT_NODE(cur,RightFreedom_aux(LEFT_NODE(cur),placetostorefreedom,&takverkleind));
	     if (takverkleind) 
	       {
		  if (POSITIVE_FLAG(cur)) return RotateLeft(cur,heightchanged);
		  if (NEGATIVE_FLAG(cur))
		    {
		       SET_ZERO_FLAG(cur);
		       *heightchanged=1;
		       return cur;
		    }
		  SET_POSITIVE_FLAG(cur);
		  return cur;
	       }
	     return cur;
	  }
     }

static NODE GetRightFreedom(NODE root, NODE*placetostorefreedom,int *heightchanged)
     {
	NODE right;
	assert(!ISNULLNODE(root));
	assert(!ISNULLNODE(RIGHT_NODE(root)));
	assert(heightchanged);
	assert(placetostorefreedom);
	right=RIGHT_NODE(root);
	if (!ISNULLNODE(LEFT_NODE(right))) 
	  return RightFreedom_aux(right,placetostorefreedom,heightchanged);
	*heightchanged=1;
	*placetostorefreedom=right;
	return RIGHT_NODE(right);
     }

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 */
	     SET_RIGHT_NODE(root,DeleteAvlNode_naardelete(RIGHT_NODE(root),wie,&takkleiner));
	     if (takkleiner)
	       {
		  if (POSITIVE_FLAG(root))
		    {
		       SET_ZERO_FLAG(root);
		       *heightchanged=1;
		       return root;
		    }
		  if (ZERO_FLAG(root))
		    {
		       SET_NEGATIVE_FLAG(root);
		       return root;
		    }
		  return RotateRight(root,heightchanged);
	       }
	     return root;
	   case 1: /* root>wie */
	     SET_LEFT_NODE(root,DeleteAvlNode_naardelete(LEFT_NODE(root),wie,&takkleiner));
	     if (takkleiner)
	       {
		  if (NEGATIVE_FLAG(root))
		    {
		       SET_ZERO_FLAG(root);
		       *heightchanged=1;
		       return root;
		    }
		  if (ZERO_FLAG(root))
		    {
		       SET_POSITIVE_FLAG(root);
		       return root;
		    }
		  return RotateLeft(root,heightchanged);
	       }
	     return root;
	   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: 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