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

typedef struct struct_234_tree * tree;
typedef struct struct_234_node * node;
typedef struct record Item;

struct record
{
  int key;
  char name[10];
};


struct struct_234_tree
{
  node root;
};


struct struct_234_node
{
  node parent;
  int number;
  Item items[3];
  node children[4];
};


void print_record(struct record item)
{
  printf("%5d, %s",item.key, item.name); 
}


struct record random_record()
{
  struct record result;
  result.key = rand() % 1000;
  
  int counter;
  int limit = 7;
  for (counter = 0; counter < limit; counter++)
  {
    result.name[counter] = 'a' + (rand() % 25);
  }
  
  result.name[limit] = 0;
  return result;
} 


tree new_tree()
{
  tree result = malloc(sizeof(*result));
  result->root = 0;
  return result;
}


node new_node(Item item)
{
  node result = malloc(sizeof(*result));
  result->parent = 0;
  result->number = 2;
  result->items[0] = item;
  result->children[0] = 0;  
  result->children[1] = 0;  
  result->children[2] = 0;  
  result->children[3] = 0;  
  return result;
} 




void destroy_node(node my_node)
{
  if (my_node == 0) return;

  int counter;
  for (counter = 0; counter < my_node->number; counter++)
  {
    destroy_node(my_node->children[counter]);
  }
 
  free(my_node);
}
  

void destroy_tree(tree my_tree)
{
  if (my_tree == 0) return;
  destroy_node(my_tree->root);
}


void print_node(node my_node, int level)
{
  if (my_node == 0) return;
  
  int counter; 
  for (counter = 0; counter < my_node->number; counter++)
  {
    print_node(my_node->children[counter], level +1);
    if (counter == my_node->number - 1) break;
    int second_counter;
    for (second_counter = 0; second_counter < 4*level; second_counter++)
    {
      printf("."); 
    }
    print_record(my_node->items[counter]);
    printf("\n");
  }
}


void print_tree(tree my_tree)
{
  print_node(my_tree->root, 0);
}

int is_root(node my_node)
{
  return (my_node->parent == 0);
}

int is_bottom(node my_node)
{
  return ((my_node->children[0] == 0) &&
          (my_node->children[1] == 0) &&
          (my_node->children[2] == 0) &&
          (my_node->children[3] == 0));
}


Item * search_node(node my_node, Item item)
{
  if (my_node == 0) return 0;

  if (item.key < my_node->items[0].key)
  {
    return search_node(my_node->children[0], item);
  }
  else if (item.key == my_node->items[0].key)
  {
    return &(my_node->items[0]);
  }
 else if ((my_node->number == 2) || (item.key < my_node->items[1].key))
  {
    return search_node(my_node->children[1], item);
  }
  else if (item.key == my_node->items[1].key)
  {
    return &(my_node->items[1]);
  }
 else if ((my_node->number == 3) || (item.key < my_node->items[2].key))
  {
     return search_node(my_node->children[2], item);
  }
 else if (item.key == my_node->items[2].key)
  {
    return &(my_node->items[2]);
  }
 else if (item.key > my_node->items[2].key)
  {
     return search_node(my_node->children[3], item);
  }
  else
  {
    printf("this should never happen:\n");
    exit(1);
  }
}


void split_root(node my_node)
{
  if (my_node->number != 4)
  {
    printf("split_root: this should never happen\n");
    exit(2);
 }

  // insert your code here.
}


void split_node(node my_node)
{
  if (my_node->number != 4)
  {
    printf("split_node: this should never happen\n");
    exit(2);
 }

  // insert your code here.
}


node insert_to_node(node my_node, Item item)
{
  if (my_node == 0) return new_node(item);

  if (my_node->number == 4)
  {
    if (is_root(my_node))
    {
      split_root(my_node);
    }
    else
    {
      node parent = my_node->parent;
      split_node(my_node);
      return insert_to_node(parent, item);
    }
  }
  
 
  // insert your code here.
 
  return my_node;    
}


Item * search(tree my_tree, Item item)
{
  return search_node(my_tree->root, item);
}


int insert(tree my_tree, Item item)
{
  Item * found = search(my_tree, item);
  if (found != 0)
  {
    return 0;
  }
  my_tree->root = insert_to_node(my_tree->root, item);
  return 1;
}



int main()
{
//  srand(time(0));
  
  tree my_tree = new_tree(); 

  while (1)
  {
    char command[100];
    printf("----------------------------------------------------------------\n");
    printf("enter command: ");
    scanf("%s", & command);

    if (strcasecmp(command, "q") == 0)
    {
      break;
    }

    struct record item = random_record();
    if (strcasecmp(command, "i") == 0)
    {
      scanf("%d", & item.key);
    }

    printf("\nrecord: "); 
    print_record(item); 
    insert(my_tree, item);
    printf("\n\n tree:\n\n"); 
    print_tree(my_tree);
    printf("\n"); 
  }  
  destroy_tree(my_tree);
  return 0;
}