/*
 * B-tree example, adopted and simplified -- HBF
*/
#include <stdio.h>
#include <stdlib.h>
#define MAX 4
#define MIN 2

typedef struct btnode
{
  int count;                     // number of key values
  int value[MAX + 1];            // key values
  struct btnode *child[MAX + 1]; // pointers to children
} tnode;

tnode *insert(tnode *,  int);
int setval(int, tnode *, int *, tnode **);
tnode *search(int, tnode *, int *);
int search_node(int, tnode *, int *);
void fill_node(int, tnode *, tnode *, int);
void split(int, tnode *, tnode *,int, int *, tnode **);
tnode *delete(tnode *, int);
int delhelp(tnode *, int);
void clear(tnode *, int);
void copysucc(tnode *, int);
void restore(tnode *, int);
void rightshift(tnode *, int);
void leftshift(tnode *, int);
void merge(tnode *, int);
void display(tnode *); //in-order traversal
void print_tree(tnode *root, int prelen);

int main()
{
  tnode *root = NULL;
  root = insert(root, 5);
  root = insert(root, 8);
  root = insert(root, 4);  
  root = insert(root, 9);
  root = insert(root, 6);  
  root = insert(root, 2);  
  root = insert(root, 10);
  root = insert(root, 7);
  root = insert(root, 3);
  root = insert(root, 1);
  
  printf("B-tree of order 5 display in-order :\n");
  display(root);
  printf("\n");
  print_tree(root, 0);
  root = delete(root, 10);
  printf("\n\nAfter deletion of values %d:\n", 10);
  display(root);
  printf("\n");
  print_tree(root, 0);
  return 0;
}

/* inserts a value in the B-tree*/
tnode *insert(tnode *root,  int val)
{
  int i;
  tnode *c, *n;
  int flag;
  flag = setval(val, root, &i, &c);
  if (flag)
    {
      n = (tnode *) malloc(sizeof(tnode));
      n -> count = 1;
      n -> value[1] = i;
      n -> child[0] = root;
      n -> child[1] = c;
      return n;
    }
  return root;
}

/* sets the value in the node */
int setval(int val, tnode *n, int *p, tnode **c)
{
  int k;
  if (n == NULL)
    {
      *p = val;
      *c = NULL;
      return 1;
    }
  else
    {
      if (search_node(val, n, &k))
	printf("\nKey value already exists.\n");
      if (setval(val, n -> child[k], p, c))
	{
	  if (n -> count < MAX)
	    {
	      fill_node(*p, *c, n, k);
	      return 0;
	    }
	  else
	    {
	      split(*p, *c, n, k, p, c);
	      return 1;
	    }
	}
      return 0;
    }
}

/* searches value in the node */
tnode *search(int val, tnode *root, int *pos)
{
  if (root == NULL)
    return NULL;
  else
    {
      if (search_node(val, root, pos))
	      return root;
      else
	     return search(val, root -> child[*pos], pos);
    }
}

/* searches for the node */
int search_node(int val, tnode *root, int *pos)
{
  if (val < root->value[1]) {
      *pos = 0;
      return 0;
  }
  else {
      *pos = root->count;
      while ((val < root->value[*pos]) && *pos > 1)
	    (*pos)--;
      
	  if (val == root->value[*pos]) //found
	     return 1;
      else
	     return 0;
    }
}

/* adjusts the value of the node */
void fill_node(int val, tnode *c, tnode *root, int k)
{
  int i;
  for (i = root -> count; i > k; i--)
    {
      root -> value[i + 1] = root -> value[i];
      root -> child[i + 1] = root -> child[i];
    }
  root -> value[k + 1] = val;
  root -> child[k + 1] = c;
  root -> count++;
}

/* splits the node */
void split(int val, tnode *c, tnode *n, int k, int *y, tnode **newnode)
{
  int i, mid;
  if (k <= MIN)
    mid = MIN;
  else
    mid = MIN + 1;
  *newnode = (tnode *) malloc(sizeof(tnode));
  for (i = mid + 1; i <= MAX; i++)
    {
      (*newnode) -> value[i - mid] = n -> value[i];
      (*newnode) -> child[i - mid] = n -> child[i];
    }
  (*newnode) -> count = MAX - mid;
  n -> count = mid;
  if (k <= MIN)
    fill_node(val, c, n, k);
  else
    fill_node(val, c, *newnode, k - mid);
  *y = n -> value[n -> count];
  (*newnode) -> child[0] = n -> child[n -> count];
  n -> count--;
}

/* deletes value from the node */
tnode *delete(tnode *root, int val)
{
  tnode *temp;
  if (! delhelp(root, val))
    printf("\nValue %d not found.", val);
  else
    {
      if (root -> count == 0)
	{
	  temp = root;
	  root = root -> child[0];
	  free(temp);
	}
    }
  return root;
}

/* helper function for delete() */
int delhelp(tnode *root, int val)
{
  int i;
  int flag;
  if (root == NULL)
    return 0;
  else
  {
    flag = search_node (val, root, &i);
    if (flag)
	{
	  if (root -> child[i - 1])
	  {	      
        copysucc(root, i);
        flag = delhelp(root -> child[i], root -> value[i]);
	    if (!flag)
		  printf("\nValue %d not found.", val);
	  }
	  else
	    clear(root, i);
    }
    else
	  flag = delhelp(root -> child[i], val);
    if (root -> child[i] != NULL)
	{
	  if (root -> child[i] -> count < MIN)
	    restore(root, i);
	}
    return flag;
  }
}

/* removes the value from the node and adjusts the values */
void clear(tnode *node, int k)
{
  int i;
  for (i = k + 1; i <= node -> count; i++)
    {
      node -> value[i - 1] = node -> value[i];
      node -> child[i - 1] = node -> child[i];
    }
  node -> count--;
}

/* copies the successor of the value that is to be deleted */
void copysucc(tnode *node, int i)
{
  tnode *temp;
  temp = node -> child[i];
  while (temp -> child[0])
     temp = temp -> child[0];
  node -> value[i] = temp -> value[1];
}

/* adjusts the node */
void restore(tnode *node, int i)
{
  if (i == 0)
  {
    if (node -> child[1] -> count > MIN)
	  leftshift(node, 1);
    else
	  merge(node, 1);
  }
  else
  {
    if (i == node -> count)
	{
	  if (node -> child[i - 1] -> count > MIN)
	    rightshift(node, i);
	  else
	    merge(node, i);
	}
    else
	{
	  if (node -> child[i - 1] -> count > MIN)
	    rightshift(node, i);
	  else
	  {
	    if (node -> child[i + 1] -> count > MIN)
		  leftshift(node, i + 1);
	    else
		  merge(node, i);
	  }
	}
  }
}

/* adjusts the values and children while shifting the value from parent to right child */
void rightshift(tnode *node, int k)
{
  int i;
  tnode *temp;
  temp = node -> child[k];
  for (i = temp -> count; i > 0; i--)
    {
      temp -> value[i + 1] = temp -> value[i];
      temp -> child[i + 1] = temp -> child[i];
    }
  temp -> child[1] = temp -> child[0];
  temp -> count++;
  temp -> value[1] = node -> value[k];
  temp = node -> child[k - 1];
  node -> value[k] = temp -> value[temp -> count];
  node -> child[k] -> child[0] = temp -> child[temp -> count];
  temp -> count--;
}
/* adjusts the values and children while shifting the value from parent to left child */
void leftshift(tnode *node, int k)
{
  int i;
  tnode *temp;
  temp = node -> child[k - 1];
  temp -> count++;
  temp -> value[temp -> count] = node -> value[k];
  temp -> child[temp -> count] = node -> child[k] -> child[0];
  temp = node -> child[k];
  node -> value[k] = temp -> value[1];
  temp -> child[0] = temp -> child[1];
  temp -> count--;
  for (i = 1; i <= temp -> count; i++)
  {
    temp -> value[i] = temp -> value[i + 1];
    temp -> child[i] = temp -> child[i + 1];
  }
}

/* merges two nodes */
void merge(tnode *node, int k)
{
  int i;
  tnode *temp1, *temp2;
  temp1 = node -> child[k];
  temp2 = node -> child[k - 1];
  temp2 -> count++;
  temp2 -> value[temp2 -> count] = node -> value[k];
  temp2 -> child[temp2 -> count] = node -> child[0];
  
  for (i = 1; i <= temp1 -> count; i++)
  {
    temp2 -> count++;
    temp2 -> value[temp2 -> count] = temp1 -> value[i];
    temp2 -> child[temp2 -> count] = temp1 -> child[i];
  }
  
  for (i = k; i < node -> count; i++)
  {
    node->value[i] = node -> value[i + 1];
    node->child[i] = node -> child[i + 1];
  }
  node->count--;
  free(temp1);
}

/* displays the B-tree */
void display(tnode *root)
{
  int i;
  if (root != NULL)
  {
    for (i = 0; i < root->count; i++)  
	{
	  display(root->child[i]);
	  printf("%d ", root->value[i + 1]);
	}
    display(root->child[i]);
  }
}

void print_tree(tnode *root, int prelen) {
  int i, j;
  if (root != NULL) {
    for (j = 0; j < prelen; j++)
      printf("%c", ' ');
    printf("%s", "|___");	  
    
	for (i = 1; i <= root->count; i++)  
	{
	  printf("%d ", root->value[i]);
	}
	printf("\n", root->value[i]);
	
    for (i = root->count; i>=0; i--)  
	{   	  
	   print_tree(root->child[i], 4);
	}

  }
}

/*
B-tree of order 5 display in-order :
1 2 3 4 5 6 7 8 9 10
|___3 6
    |___7 8 9 10
    |___4 5
    |___1 2


After deletion of values 10:
1 2 3 4 5 6 7 8 9
|___3 6
    |___7 8 9
    |___4 5
    |___1 2
*/