// BTree.cpp :

#include "stdafx.h"
#include <time.h>    
#include <iostream>
#include <string>
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 () : v (0)
	{
		for (int i = 0; i < N+1; i++) key [i] = 0;
		for (int i = 0; i < N+2; i++) ptr [i] = nullptr;
	}
};

void insert2 (item * target, int x)
{
	if (target->ptr[0] == nullptr) { // list na nejnizsim patre
		// vyhledam pozici pro klic x
		int i=0;
		while (i<target->v && target->key[i]<x) i++;
		if (i<target->v && target->key[i]==x) return;

		// odsunu klice a ukazatele s vyssimi indexy
		for (int j=target->v-1;j>=i;j--) 
			target->key[j+1]=target->key[j];
		for (int j=target->v;j>i;j--) 
			target->ptr[j+1]=target->ptr[j];

		target->ptr[i+1]=nullptr;
		target->key[i]=x; // pridam novy klic
		target->v++;
	}
	else {
		// vyhledam vetev pro klic x
		int i=0;
		while(i<target->v && target->key[i]<x) i++;
		if(i<target->v && target->key[i]==x) return;

		// vlozim klic o patro nize
		item * left = target->ptr[i];
		insert2 (left, x);

		if (left->v > N) {
				item * right = new item; // novy pravy blok 
				for (int j = 0; j < Z; j++) // zkopiruji Z klicu
					right->key[j] = left->key[Z+1+j];
				for (int j = 0; j <= Z; j++) // a Z+1 ukazatelu
					right->ptr[j] = left->ptr[Z+1+j];
				right->v = Z;

				int pom = left->key[Z]; // prostredni prvek jde nahoru

				// uklid v levem bloku
				for (int j=Z+1; j<N+1; j++)
					left->key[j] = 0;
				for (int j=Z+1; j<=N+1; j++)
					left->ptr[j] = nullptr;
				left->v = Z;
			
				// posun v hornim bloku
				for (int j=target->v-1;j>=i;j--) 
					target->key[j+1] = target->key[j];
				for (int j=target->v;j>i;j--) 
					target->ptr[j+1] = target->ptr[j];

				// vloz delici klic a pravy blok
				target->key[i] = pom;
				target->ptr[i+1] = right;
				target->v++; // zvetsi pocet prvku v hornim bloku, NA CVICENI CHYBELO
		}
	}
}

void insert (item *& target, int x)
{
	if(target == nullptr) target = new item;
	insert2(target, x);
	item* left = target;
	if (left->v > N) {
			item * right = new item;
			for (int j = 0; j < Z; j++)
				right->key[j] = left->key[Z+1+j];
			for (int j = 0; j <= Z; j++)
				right->ptr[j] = left->ptr[Z+1+j];
			right->v = Z;

			int pom = left->key[Z];
			for (int j=Z+1; j<N+1; j++)
				left->key[j] = 0;
			for (int j=Z+1; j<=N+1; j++)
				left->ptr[j] = nullptr;
			left->v = Z;

			target = new item;
			target->v = 1;
			target->ptr[0] = left;
			target->key[0] = pom;
			target->ptr[1] = right;
	}
}

item * root = nullptr;

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[])
{
    /* initialize random seed: */
    srand (time (NULL));

	root = nullptr;
	// for (int i = 1; i <= 1000; i++) add (rand() % 5000);

	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);
	// for (int i = 1; i <= 100; i++) add (rand() % 100);

	show (root);

	cout << "Hotovo" << endl;
	system ("pause");

	return 0;
}