#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define FALSE  0
#define TRUE 1
#define SWAP(x,y,t) ((t) = (x), (x) = (y), (y) = (t))
typedef struct {
		  int key; } element;

typedef struct TwoThree *TwoThreePtr;
	struct TwoThree {
			  element dataL, dataR;
			  TwoThreePtr LeftChild, MiddleChild,
				      RightChild ; };
typedef struct stack *StackPtr;
	struct stack {
		       TwoThreePtr data;
		       StackPtr    link; };

StackPtr top = NULL;

int compare(element, TwoThreePtr);
TwoThreePtr search23(TwoThreePtr, element);
void NewRoot(TwoThreePtr *, element, TwoThreePtr);
TwoThreePtr pop(void);
void push(TwoThreePtr);
TwoThreePtr FindNode(TwoThreePtr, element);
void InsertionError(void);
void PutIn(TwoThreePtr *, element, TwoThreePtr);
void split(TwoThreePtr, element *, TwoThreePtr *);
void order(element[]);
void PrintTree(TwoThreePtr, int);
void EmptyStack(void);
void insert23(TwoThreePtr *, element);
TwoThreePtr FindDelNode(TwoThreePtr, element x);
void DeletionError(void);
void RotateRoot(TwoThreePtr *, TwoThreePtr *);
void Rotate(TwoThreePtr*, TwoThreePtr*, TwoThreePtr*, int);
void combine(TwoThreePtr *, TwoThreePtr *, TwoThreePtr, int, int*);
void delete23(TwoThreePtr *, element x)


int main()
{
   TwoThreePtr root = NULL, node;
   int choice;
   element x;
   top = NULL;
   printf("1. Insert, 2. Delete 3. Search, 0. Quit: ");
   scanf("%d",&choice);
   while (choice) {
      switch(choice) {
	 case 1: printf("Enter your number: ");
		 scanf("%d",&x.key);
		 insert23(&root,x);
		 PrintTree(root,0);
		 break;
	 case 2: printf("Enter your number: ");
		 scanf("%d",&x.key);
		 delete23(&root,x);
		 PrintTree(root,0);
		 break;
	 case 3: printf("Enter your number: ");
		 scanf("%d", &x.key);
		 if (search23(root,x) == NULL)
		    printf("The key is not in the tree\n");
		 else
		    printf("The pointer to the tree was returned\n");
       }
       if (top) EmptyStack();
       printf("1.Insert, 2.Delete, 3. Search, 0. QUit: ");
       scanf("%d",&choice);
    }
}


int compare(element x, TwoThreePtr node)
{
/* send back an integer to indicate the correct child pointer
for element x */
   if (x.key < node->dataL.key)
      return 1;
   else if ((x.key > node->dataL.key) && (x.key < node->dataR.key))
      return 2;
   else if (x.key > node->dataR.key)
      return 3;
   else
      return 4;
}

TwoThreePtr search23(TwoThreePtr root, element x)
{
/* search the 2-3 tree for an element that matches x.key.  If
the key is found a pointer to its node is returned, otherwise a
NULL pointer is returned */
  int done = FALSE;
  TwoThreePtr node = root;
  while (node && !done)
     switch(compare(x,node)) {
       case 1: node = node->LeftChild;
	       break;
       case 2: node = node->MiddleChild;
	       break;
       case 3: node = node->RightChild;
	       break;
       case 4: done = TRUE;
     }
   return node;
}

void NewRoot(TwoThreePtr *NewKid, element x, TwoThreePtr MiddleKid)
{
/* create a new root the old root is placed as the left child,
and MiddleKid is placed in the middle position.  The root is
returned in NewKid */
  TwoThreePtr temp;
  temp = (TwoThreePtr)malloc(sizeof(struct TwoThree));
  temp->dataL = x;
  temp->dataR.key =  INT_MAX;
  temp->LeftChild = *NewKid;
  temp->MiddleChild = MiddleKid;
  temp->RightChild = NULL;
  *NewKid = temp;
}

TwoThreePtr pop(void)
{
/* pop a node from the global stack */
   TwoThreePtr tempval;
   StackPtr    temp;
   if (top) {
      tempval = top->data;
      temp = top;
      top = top->link;
      free(temp);
      return tempval;
   }
}

TwoThreePtr FindNode(TwoThreePtr node, element x)
{
/* modified search procedure to determine the correct leaf node.  This
node is returned in FindNode.  The stack contains the node's ancestors */
  StackPtr    temp;
  int done = FALSE;
  top = NULL;
  while (node && !done) {
      push(node);
      switch(compare(x,node)) {  
	   case 1: node = node->LeftChild;
		 break;
	  case 2: node = node->MiddleChild;
		 break;
	  case 3: node = node->RightChild;
		 break;
	 case 4: done = TRUE;
       }
   }
   if (done)
     return NULL;
   else
     return pop();
}

void InsertionError(void)
{
   printf("The key is already in the tree\n");
}


void PutIn(TwoThreePtr *node, element y, TwoThreePtr a)
{
/* node has room for another element, so add it */
   if (y.key < (*node)->dataL.key) {
      (*node)->dataR = (*node)->dataL;
      (*node)->dataL = y;
      (*node)->RightChild = (*node)->MiddleChild;
      (*node)->MiddleChild = a;
   }
   else {
     (*node)->dataR = y;
     (*node)->RightChild = a;
   }
}


void order(element child[3])
{
/* node must be split, order the two elements and the new one to
determine the spliting */
  int i,j,min;
  element temp;
  for (i = 0; i <= 1; i++) {
    min = i;
    for (j = 1; j <= 2; j++)
       if (child[j].key < child[min].key)
	 min = j;
    SWAP(child[min],child[i],temp);
  }
}

void split(TwoThreePtr node, element *y, TwoThreePtr *a)
{
/* node is a three node, split it into two nodes */
  element child[3];
  TwoThreePtr right;

  child[0] = node->dataL;
  child[1] = node->dataR;
  child[2] = *y;
  order(child);

  node->dataL = child[0];
  node->dataR.key = INT_MAX;

  right = (TwoThreePtr)malloc(sizeof(struct TwoThree));
  right->dataL = child[2];
  right->LeftChild = node->RightChild;
  node->RightChild = NULL;
  right->dataR.key = INT_MAX;
  if (*a != NULL) {
    right->MiddleChild = *a;
    right->RightChild = NULL;
  }
  else {
    right->MiddleChild = right->RightChild = NULL;
  }
  *a = right;
  *y = child[1];
}

void insert23(TwoThreePtr *root, element y)
{/* insert the element y into the 23 tree */
  TwoThreePtr a, node, temp;

  if (!*root)  /* tree is empty */
     NewRoot(root, y, NULL);
  else {
  /* insert into a non-empty tree */
    node = FindNode(*root,y);
    if (!node)
      InsertionError();
    else {
       a = NULL;
       while (1)
	  if (node->dataR.key == INT_MAX) { /*2-node */
	     PutIn(&node,y,a);
	     break;
	  }
	  else {   /* 3-node */
	     split(node,&y,&a);
	     if (node == *root) { /* split the root */
		     NewRoot(root,y,a);
		     break;
	     }
	     else
	       node = pop();
	  }
     }
   }
}


void PrintTree(TwoThreePtr node, int level)
{
   int i;
   if (node) {
      for (i =1; i <= level; i++)
	     printf("     ");
      printf("%5d",node->dataL.key);
      if (node->dataR.key != INT_MAX)
	      printf("%5d",node->dataR.key);
      printf("\n");
      PrintTree(node->LeftChild, level+1);
      PrintTree(node->MiddleChild, level+1);
      PrintTree(node->RightChild, level+1);
   }
}

void EmptyStack(void)
{
   StackPtr temp;
   while(top) {
     temp = top;
     top = top->link;
     free(temp);
    }
    top = NULL;
}

void push(TwoThreePtr node)
{
  StackPtr temp;
  temp = (StackPtr)malloc(sizeof(struct stack));
  temp->data = node;
  temp->link = NULL;
  if (top)
    temp->link = top;
  top = temp;
}

TwoThreePtr FindDelNode(TwoThreePtr node, element x)
{/* modified search procedure to determine the correct leaf node.  This
node is returned in FindNode.  The stack contains the node's ancestors */
  StackPtr    temp;
  int done = FALSE;
  top = NULL;
  while (node && !done) {
      push(node);
      switch(compare(x,node)) {
	  case 1: node = node->LeftChild;
		 break;
	  case 2: node = node->MiddleChild;
		 break;
	  case 3: node = node->RightChild;
		 break;
	  case 4: done = TRUE;
      }
   }
   if (done)
     return pop();
   else
     return NULL;
}

void DeletionError(void)
{ printf("The key is not in the tree \n");}


void rotate(TwoThreePtr *node, TwoThreePtr *sibling,
	    TwoThreePtr *root, int num)
{
    if (*sibling)
      switch(num) {
	 case 1: /* rotation when node is left child of root */
		 printf("Rotate node is left \n");
		 (*node)->dataL = (*root)->dataL;
		 (*root)->dataL = (*sibling)->dataL;
		 (*sibling)->dataL = (*sibling)->dataR;
		 (*sibling)->dataR.key = INT_MAX;
		 (*node)->MiddleChild  = (*sibling)->LeftChild;
		 (*sibling)->LeftChild = (*sibling)->MiddleChild;
		 (*sibling)->MiddleChild = (*sibling)->RightChild;
		 (*sibling)->RightChild = NULL;
		 break;

	 case 2: /* rotation when node is the middle child of root */
		 printf("Middle rotate \n");
		 (*node)->dataL = (*root)->dataL;
		 (*root)->dataL = (*sibling)->dataR;
		 (*sibling)->dataR.key = INT_MAX;
		 (*node)->MiddleChild = (*node)->LeftChild;
		 (*node)->LeftChild = (*sibling)->RightChild;
		 (*sibling)->RightChild = NULL;
		 break;
	 case 3: /* rotation when node is the right child of root */
		 printf("Right rotate \n");
		 (*node)->dataL = (*root)->dataR;
		 (*root)->dataR = (*sibling)->dataR;
		 (*sibling)->dataR.key = INT_MAX;
		 (*node)->MiddleChild = (*node)->LeftChild;
		 (*node)->LeftChild = (*sibling)->RightChild;
		 (*sibling)->RightChild = NULL;
	}
}

void combine(TwoThreePtr *node, TwoThreePtr *sibling,
	     TwoThreePtr root, int num, int *done)

{
   if (*sibling)
      switch(num) {
	 case 1: /* node is the left child */
		 printf("Left combine\n");
		 (*node)->dataL = (root)->dataL;
		 (*node)->dataR = (*sibling)->dataL;
		 (*node)->MiddleChild = (*sibling)->LeftChild;
		 (*node)->RightChild = (*sibling)->LeftChild;
		 if ((root)->dataR.key == INT_MAX)
		 /* root was a two node */
	        (root)->dataL.key = INT_MAX;
		 else {
		     (root)->dataL = (root)->dataR;
		     (root)->dataR.key = INT_MAX;
		     (root)->MiddleChild = (root)->RightChild;
		     (root)->RightChild = NULL;
		     *done = TRUE;
		 }
		break;
       case  2: /* node is the middle child */
		printf("middle combine\n");
		if ((root)->dataR.key == INT_MAX) {
		  (root)->dataR = (root)->dataL;
		  (root)->RightChild = (*node)->LeftChild;
		  (root)->MiddleChild = (*sibling)->MiddleChild;
		  (root)->LeftChild = (*sibling)->LeftChild;
		  (root)->dataL = (*sibling)->dataL;
		  free(*sibling);
		}
		else {
		   (*sibling)->dataR = (root)->dataL;
		   (*sibling)->RightChild = (*node)->LeftChild;
		   (root)->dataL = (root)->dataR;
		   (root)->dataR.key = INT_MAX;
		   (root)->MiddleChild = (root)->RightChild;
		   (root)->RightChild = NULL;
		 }
		 free(*node);
		 *done = TRUE;
		 break;
       case 3:   /* node is the right child, root must have 2 kids */
		 printf("Right combine\n");
		 (*sibling)->dataR = (root)->dataR;
		 (*sibling)->RightChild = (*node)->LeftChild;
		 (root)->dataR.key = INT_MAX;
		 (root)->RightChild = NULL;
		 free(*node);
		 *done = TRUE;
       }
}

void delete23(TwoThreePtr *tree, element x)
{
   TwoThreePtr node, root, sibling;
   int done;

   node = FindDelNode(*tree, x);
   if  (!node)
     DeletionError();
   else {
      printf("IN deletion, left = %d, right = %d\n",node->dataL.key, node->dataR.key);
      if (x.key == node->dataL.key)
	    if (node->dataR.key !=  INT_MAX) { 
	      node->dataL = node->dataR;
	      node->dataR.key = INT_MAX;
	     }
	    else
	      node->dataL.key = INT_MIN;
      else
	    node->dataR.key = INT_MAX;
       done = !(node->dataL.key == INT_MIN);
       while (!done) {
	  root = pop();
	  if (node == root->LeftChild) {
	     sibling = root->MiddleChild;
	     if (sibling->dataR.key != INT_MAX) {
		   rotate(&node,&sibling,&root,1);
		   done =  TRUE;
	      }
	      else {
		    if (root == *tree) {
		    combine(&node,&sibling,root,1,&done);
		    *tree = (*tree)->LeftChild;
		    }
		    else
		    combine(&node, &sibling, root,1, &done);
	      }
	   } /* left child */
	   else if (node == root->MiddleChild) {
	      sibling = root->LeftChild;
	      if (sibling->dataR.key != INT_MAX) {
		     rotate(&node,&sibling,&root,2);
		     done = TRUE;
	       }
	      else
		     combine(&node,&sibling,root,2,&done);
	    }
	    else { /* node is the right child */
	       sibling = node->MiddleChild;
	       if (sibling->dataR.key != INT_MAX) {
		 	 rotate(&node, &sibling, &root, 3);
		  	 done = TRUE;
		    }
		  else
               combine(&node, &sibling, root, 3, &done);
	      }
	  }
   }
}