// 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) {
	int i=0;
	while(i<target->v && target->key[i]<x) i++;
	if(i<target->v && target->key[i]==x) return;
	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;
	target->v++;
	}
	else {
	int i=0;
	while(i<target->v && target->key[i]<x) i++;
	if(i<target->v && target->key[i]==x) return;
	item * left = target->ptr[i];
	insert2 (left, x);
	if (left->v > N) {
			item * right = new item;
			right->v = Z;
			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];
			left->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;
			
			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]=pom;
			target->ptr[i+1]=right;
	}
	}
}

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;
			right->v = Z;
			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];
			left->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;
			target = new item;
			target->v = 1;
			target->ptr[0]=left;
			target->key[0]=pom;
			target->ptr[1]=right;
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
    /* initialize random seed: */
    srand (time (NULL));

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

	return 0;
}