#include "stdafx.h"
#include <string>
#include <iostream>
using namespace std;

const int Z = 2;
const int N = 2*Z;

struct item {
   int v;
   int key [N+1];
   item * ptr [N+2];
};

item * root;

item * alloc ()
{
    item * result = new item;
    result->v = 0;
    for (int i = 0; i < N+1; i++) result->key[i] = 0;
    for (int i = 0; i < N+2; i++) result->ptr[i] = nullptr;
    return result;
}

void split (item * branch, item * & next, int & d)
{
	          int c = branch->v;
			  int a=Z;		// doleva
			  int b=c-a-1;	// doprava

			  next = alloc();
			  for(int k=0; k<b; k++) 
				  next->key[k]=branch->key[a+1+k];
			  for(int k=0; k<b+1; k++) 
				  next->ptr[k]=branch->ptr[(a+1)+k];
			  next->v=b;

			  d=branch->key[a];	// jde nahoru

			  for(int k=a;k<c;k++) 
				  branch->key[k]=0;
			  for(int k=a+1;k<c+1;k++) 
				  branch->ptr[k]=nullptr;
			  branch->v=a;
}

void insert2 (item * target, int x)
{
      // najdi vhodne misto
      int i = 0;
      while (i < target->v && target->key[i] < x) i ++;

	  if (i < target->v && target->key[i] == x)
		  return ; // hodnota je jiz ve stromu

	  item * branch = target->ptr[i];
	  if (branch!=nullptr)
	  {
		  insert2 (branch,x); // vloz do podstromu
		  if(branch->v>N)
		  {
			  // prilis mnoho prvku 
			  // rozdel na vetve branch a next
			  // delici kilc bude d
			  item * next;
			  int d;
			  split (branch, next, d);

			  // vloz next a klic d do naseho prvku
			  for(int k= target->v -1; k >= i; k--)
				  target->key[k+1] = target->key[k];
			  for(int k= target->v ; k >= i+1; k--)
				  target->ptr[k+1] = target->ptr[k];
			  target->ptr[i+1] = next;
			  target->key[i] = d;
			  target->v++;
		  }
	  }
	  else
	  {
		  // vkladani do listu
		  int k = target->v - 1;
		  target->ptr [k+2] = target->ptr [k+1];
		  while (k >= i) 
		  { 
			 target->key [k+1] = target->key [k];
			 target->ptr [k+1] = target->ptr [k];
			 k --; 
		  }

		  target->key [i] = x;
		  target->ptr [i] = nullptr;
		  target->v = target->v+1;
	  }
}

void insert (item * & target, int x)
{
   if (target == nullptr)
   {
      // prazdny strom -> jednoprvkovy strom
      target = alloc ();
      target->v = 1;
      target->key[0] = x;
      target->ptr[0] = nullptr;
      target->ptr[1] = nullptr;
   }
   else
   {
	   insert2 (target, x); // pouzij predchozi funkci
	   if (target->v > N)
	   {
		   // musime pridat novy korenovy prvek

		   // rozdel na dve casti branch a next
		   item * branch = target;   
  		   item * next;
		   int d;
		   split (branch, next, d);
		   
		   // uloz do noveho korenoveho prvku
		   target = alloc ();
		   target->v = 1;
		   target->key [0] = d;
		   target->ptr [0] = branch;
		   target->ptr [1] = next;
	   }
   }
}

void add (int x)
{
	insert(root, x);
}

void print(item * target) // zobrazi jeden uzel
{
	cout << "(" ;
	for(int i=0; i<target->v; i++){
		cout << target->key[i];
		if (i < target->v-1)
			cout << ",";
	}
	cout << ")" ;
}

void display (item * target, int level)
// zobrazi patro cislo level
{
	if (target != nullptr)
	{
   	   if (level <= 1)
	   {
  		   print (target);
	   }
       else
	   {
		   for (int i = 0; i <= target->v ; i ++)
		   {
			   if (level > 2) cout << "[";
			   display (target->ptr [i], level-1);
			   if (level > 2) cout << "] ";
		   }
	   }
	}
}

void show (item * target) // zobrazi strom
{
	int h = 0;
	item * p = target;
	while (p != nullptr)
	{
		p = p->ptr[0];
		h ++;
	}

	for (int t = 1; t <= h; t++)
	{
		cout << t << ". patro" << endl;
		cout << "--------" << endl;
		display (target, t);
		cout << endl;
		cout << endl;
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	root = nullptr;
	add(5);	// print(root); cout << endl;
	add(7);	// print(root); cout << endl;
	add(1);	// print(root); cout << endl;
	add(4);	// print(root); cout << endl;

	add (10);
	add (15);
	add (25);
	add (14);
	add (8);
	add (11);
	add (12); // rozdelovani bloku

	add (76);
	add (72);
	add (74);
	add (70);
	add (30); 
	add (32); // rozdelovani bloku, pridani patra

	show (root);
	
	cout << "Konec - stisknete enter" << endl;

	char c;
	cin >> c;

    return 0;
}