#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, int & d, item * & next)
{
	int c = branch->v;
	int a = Z;		// doleva
	int b = c-a-1;	// doprava
 
	next = alloc(); // novy pravy prvek
	for (int k = 0; k < b; k++) // klice pro pravy prvek
		next->key[k] = branch->key[a+1+k];
	for (int k = 0; k < b+1; k++)  // ukazatele
		next->ptr[k] = branch->ptr[(a+1)+k];
	next->v = b; // pocet prvku
 
	d=branch->key[a]; // klic, ktery pujde o patro vyse
 
	for(int k = a; k < c; k++) // vymazat prebytecne klice
		branch->key[k] = 0;
	for(int k = a+1; k < c+1; k++) // a prebytecne ukazatele
		branch->ptr[k] = nullptr;
	branch->v = a; // novy pocet prvku
}
 
void shift (item * target, int i)
// posun klice key[i], ..., key[v-1] o policko dale
// posun ukazatele ptr[i+1], ..., ptr[v] o policko dale
{
   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];
}
 
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 klic bude d
			int d;
			item * next;
			split (branch, d, next);
 
			// vloz next a klic d do naseho prvku target
			shift (target, i);
			target->key[i] = d; // vloz delici klic
			target->ptr[i+1] = next; // vloz pridanou pravou stranku
			target->v++; // zvetsi pocet prvku
		}
	}
	else
	{
		// vkladani do listu
		shift (target, i); // posun policka
		target->key [i] = x; // pridej cislo
		target->ptr [i+1] = nullptr;
		target->v ++;
	}
}
 
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;   
			int d;
			item * next;
			split (branch, d, next);
 
			// 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 zadane hloubky
{
	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) // zobraz 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
 
	for (int i = 1; i <= 70; i++) add (i);
 
	show (root);
 
	cout << "Konec - stisknete enter" << endl;
 
	char c;
	cin >> c;
 
	return 0;
}