#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define FALSE 0
#define TRUE  1

typedef struct {
		   int key; } element;
typedef struct two34 *two34pointer;
	struct two34  {
			element dataL, dataM, dataR;
			two34pointer LeftChild, LeftMidChild,
			 RightMidChild, RightChild; } ;
typedef enum {equal,leaf,lchild,lmchild,rmchild,rchild} CompareResult;
typedef enum {TwoNode,ThreeNode} NodeResult;

CompareResult compare(element,two34pointer);
void NewRoot(two34pointer *, element);
int FourNode(two34pointer);
NodeResult NodeType(two34pointer);
void InsertionError(void);
void PutIn(element, two34pointer *);
void SplitRoot(two34pointer *);
void SplitChildOf2(two34pointer *, two34pointer *);
void SplitChildOf3(two34pointer *, two34pointer *);
void insert234(two34pointer *, element);
void PrintTree(two34pointer, int);

int main()
{
  two34pointer root = NULL;
  element  num;

  printf("Enter a number, <0> to quit: ");
  scanf("%d",&num.key);
  while (num.key) {
      insert234(&root,num);
      printf("Your tree contains: \n");
      PrintTree(root,0);
      printf("\n\n Enter a number, <0> to quit: ");
      scanf("%d",&num.key);
  }
}

CompareResult compare(element x, two34pointer node)
{
  if (x.key == node->dataL.key || x.key == node->dataM.key ||
  x.key == node->dataR.key)
     return equal;
  else if (node->LeftChild == NULL && node->RightChild == NULL &&
  node->LeftMidChild == NULL && node->RightMidChild == NULL)
     return leaf;
  else if (x.key < node->dataL.key)
     return lchild;
  else if  (x.key < node->dataM.key)
     return lmchild;
  else if (x.key < node->dataR.key)
     return rmchild;
  else
    return rchild;
}


void NewRoot(two34pointer *root, element x)
{
   *root = (two34pointer)malloc(sizeof(struct two34));
   (*root)->dataL = x;
   (*root)->dataM.key = (*root)->dataR.key = INT_MAX;
   (*root)->LeftChild = (*root)->LeftMidChild = (*root)->RightMidChild =
   (*root)->RightChild = NULL;
}

int FourNode(two34pointer node)
{ return (node->dataR.key != INT_MAX);}



NodeResult NodeType(two34pointer node)
{ (node->dataM.key == INT_MAX) ? TwoNode : ThreeNode;}


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

void PutIn(element x, two34pointer *node)
{/* node is a two node, and has room for another key */
  printf("IN PUT IN: ");
   if (x.key < (*node)->dataL.key) {
      (*node)->dataR = (*node)->dataM;
      (*node)->dataM = (*node)->dataL;
      (*node)->dataL = x;
   }
   else if (x.key < (*node)->dataM.key) {
     (*node)->dataR = (*node)->dataM;
     (*node)->dataM = x;
   }
   else
      (*node)->dataR = x;
}

void SplitRoot(two34pointer *root)
{
  two34pointer left,right;
    printf("IN split ROOT\n");
  left = (two34pointer)malloc(sizeof(struct two34));
  left->dataL = (*root)->dataL;
  left->dataM.key = left->dataR.key = INT_MAX;
  left->LeftChild = (*root)->LeftChild;
  left->LeftMidChild = (*root)->LeftMidChild;
  left->RightMidChild = left->RightChild = NULL;

  right = (two34pointer)malloc(sizeof(struct two34));
  right->dataL = (*root)->dataR;
  right->dataM.key = right->dataR.key = INT_MAX;
  right->LeftChild = (*root)->RightMidChild;
  right->LeftMidChild = (*root)->RightChild;
  right->RightMidChild = right->RightChild = NULL;

  (*root)->dataL = (*root)->dataM;
  (*root)->dataM.key = (*root)->dataR.key = INT_MAX;
  (*root)->LeftChild = left;
  (*root)->LeftMidChild = right;
  (*root)->RightMidChild = (*root)->RightChild = NULL;
}

void SplitChildOf2(two34pointer *node, two34pointer *parent)
{
   two34pointer child;
   printf("IN SplitCHildof2\n");
   if (*node == (*parent)->LeftChild) {
      (*parent)->dataM = (*parent)->dataL;
      (*parent)->dataL = (*node)->dataM;
      (*parent)->RightMidChild = (*parent)->RightChild;
   }
   else
      (*parent)->dataM = (*node)->dataM;
   (*node)->dataM.key = INT_MAX;

   child = (two34pointer)malloc(sizeof(struct two34));
   child->dataL = (*node)->dataR;
   child->dataM.key = child->dataR.key = (*node)->dataR.key = INT_MAX;
   child->LeftChild = (*node)->RightMidChild;
   child->LeftMidChild = (*node)->RightChild;
   child->RightMidChild = child->RightChild = NULL;
   (*node)->RightMidChild = (*node)->RightChild = NULL;
   if (*node == (*parent)->LeftChild)
      (*parent)->LeftMidChild = child;
   else
      (*parent)->RightMidChild = child;
}

void SplitChildOf3(two34pointer *node, two34pointer *parent)
{
   two34pointer child;
   printf("IN SplitChildOf3\n");
   if (*node == (*parent)->LeftChild) {
      (*parent)->dataR = (*parent)->dataM;
      (*parent)->dataM = (*parent)->dataL;
      (*parent)->dataL = (*node)->dataM;
      (*parent)->RightChild = (*parent)->RightMidChild;
      (*parent)->RightMidChild = (*parent)->LeftMidChild;
   }
   else if (*node == (*parent)->LeftMidChild) {
      (*parent)->dataR = (*parent)->dataM;
      (*parent)->dataM = (*node)->dataM;
   }
   else
      (*parent)->dataR = (*node)->dataM;
   (*node)->dataM.key = INT_MAX;
   child = (two34pointer)malloc(sizeof(struct two34));
   child->dataL = (*node)->dataR;
   child->dataM.key = child->dataR.key = (*node)->dataR.key = INT_MAX;
   child->LeftChild = (*node)->RightMidChild;
   child->LeftMidChild = (*node)->RightChild;
   child->RightMidChild = child->RightChild = NULL;
   (*node)->RightMidChild = (*node)->RightChild = NULL;
   if (*node == (*parent)->LeftChild)
      (*parent)->LeftMidChild = child;
   else if (*node == (*parent)->LeftMidChild)
      (*parent)->RightMidChild = child;
   else
      (*parent)->RightChild = child;
}

void insert234(two34pointer *root, element x)
{/* insert the key into the 234 tree */
   two34pointer node, parent;
   int done;

   if (!*root)
      NewRoot(root, x);
   else {
      if (FourNode(*root))
	 SplitRoot(root);
      node = *root;   parent = NULL;
      done = FALSE;
      while (!done) {
	 if (FourNode(node)) {
	    if (NodeType(parent) == TwoNode)
		   SplitChildOf2(&node,&parent);
	    else
		  SplitChildOf3(&node,&parent);
	    node = parent;
	 }
	 parent = node;
	 switch (compare(x,node)) {
	   case equal:   InsertionError();
			 done = TRUE;
			 break;
	   case leaf:    PutIn(x, &node);
			 done = TRUE;
			 break;
	   case lchild:  node = node->LeftChild;
	  	 break;
	   case lmchild: node = node->LeftMidChild;
			 break;
	   case rmchild: node = node->RightMidChild;
			 break;
	   case rchild:  node = node->RightChild;
	 }
    }
  }
}

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