// header file

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node NODE;	// forward declaration

typedef struct Record {
  char key[9];
  char value[25];
} RECORD;

typedef struct Leaf {
  int end;
  RECORD records[5]; 	// 1 extra
} LEAF;

typedef struct INode {
  int end;
  char* keys[5];	// both 1 extra
  NODE* child[6];
} INODE;

struct Node {
  char type;		// leaf=1 or inode=0
  union { 
  LEAF leaf;
  INODE inode;
  } data;
};

void insert(RECORD *r,NODE* nd);
void print(NODE* nd);


// functions source
#include "b+tree.h"
/* DEFITIONS FOR EASY ACCESS */
#define LEE(x)	((x)->data.leaf)
#define INTERN(x) ((x)->data.inode)


char isLeaf(NODE * nd) { return nd->type; }

void leafInsert(RECORD * r,NODE * nd)	// insertion to leaf, simple
{
  int i,j;
  char done=0;
  
  for(i=0;i<LEE(nd).end;i++)
  {
  	if(strcasecmp(r->key,LEE(nd).records[i].key) < 0)
	{
	   for(j=LEE(nd).end;j>i;j--)
	     LEE(nd).records[j] = LEE(nd).records[j-1];	// shifting for space
	   LEE(nd).records[i] = *r; 
	   done = 1;
	   break;
	}
  }

  if(!done)  LEE(nd).records[i] = *r;
  LEE(nd).end++;
    
}

void insert(RECORD * r,NODE * nd)
{
   if(!nd) { nd = malloc(sizeof(NODE));	nd->type = 1; LEE(nd).end = 0; }
   if(isLeaf(nd))
   {
     leafInsert(r,nd);
   }
}

void printRecord(RECORD * r)
{
  printf("<record>");
  printf("\'%s\'",r->key); printf(",\'%s\'",r->value);
  printf("</record>");
}

void print(NODE * nd)
{
  int i;
  if(!nd) printf("NOT FOUND\n");	// empty tree
  else
  if(isLeaf(nd))
  { printf("<data>");
    for(i=0;i<LEE(nd).end;i++)
    	printRecord(&(LEE(nd).records[i])); 
    printf("</data>");
  }
	  
}



// MAIN source
#include "b+tree.h"

// COMPLETE : Taking input.

int main(void)
{
  int i=0;
  RECORD r;
  NODE* root=0;		// WHY DOES THIS ALWAYS STAY 0 if initialized anywhere NODE * root=0; ??
  char command[10];
  char c;

  while(1)	// main loop
  {
	i=0;	// reset command string 
  	while(1)	// command scan loop
  	{
     		if((c=getchar())!=EOF && (c != ' ') && (c != '\n'))
     		{
        		command[i] = c;
			i++;
     		}
     		else break;
  	}
  
  	command[i] = 0; // end the string
  	if(!strcasecmp(command,"quit")) return 0;	// quit
	
	if(!strcasecmp(command,"print")) 		// print
	{
	   print(root);
	}	
	
	else if(!strcasecmp(command,"insert"))		// insert
	{
	   getchar();	// for '
	   i=0;
	   while(1)	// scan key loop
	   {
	   	if((c=getchar())!=EOF && (c != ' ') && (c != '\'') && (c != '\n'))
	   	{
		   r.key[i] = c;
		   i++;
		}
	        else break;	
	   }
	   r.key[i] = 0;	// end string
	   for(i=0;i<2;i++) getchar();	// for ,' (2 chars)
	   i=0;
	   while(1)
	   {
	   	if((c=getchar())!=EOF && (c != ' ') && (c != '\'') && (c != '\n'))
		{
		   r.value[i] = c;
		   i++;
		}
		else break;
	   }
	   r.value[i] = 0;	// end string
	   /* DEBUG INFORMATION */
	   printf("Key: %s\n",r.key);
	   printf("Value: %s\n",r.value);

	   insert(&r,root);	// actual insertion happens here!
	}
	
	else if(!strcasecmp(command,"delete"))		// delete
		return 2;
	
  

  }

  return 0;
}