// BTree.cpp 
 
#include "stdafx.h"
 
#include <iostream>
#include <string>
using namespace std;
 
const int k = 2;
const int n = 2 * k;
 
struct item {
    int    cnt; // pocet klicu v bloku, k .. 2*k
    int    key [n + 1]; // key[0] ... key [cnt-1]
    item * ptr [n + 2]; // ptr[0] ... ptr [cnt]
};
 
item* root = nullptr;
 
bool search (item * p, int x)
{
    bool result = false;
    while (p != nullptr && ! result)
    {
        int i = 0;
        while (i < p->cnt && p->key[i] < x) 
           i ++;
        // i == p->cnt || i < p->cnt &&  p->key[i] >= x
        if (i < p->cnt &&  p->key[i] == x)
            result = true;
        else 
           // result = search (p->ptr [i], x);
           p = p->ptr [i];
    }
    return result;
}
 
void enter (item * & p, int x)
{
    if (p == nullptr )
    {
        item * t = new item;
        t->cnt=1;
        t->key[0]=x;
        t->ptr[0]=nullptr;
        t->ptr[1]=nullptr;
        p = t;
    }
    else
   {
        int i = 0;
        while (i < p->cnt && p->key[i] < x) 
           i ++;
        if (i < p->cnt &&  p->key[i] == x)
        {}
        else
        {
            if (p->ptr[i] == nullptr)
            {
                for(int j = p->cnt-1; j >= i; j--)
                    p->key[j+1] = p->key[j];
                p->key[i] = x;
                for(int j = p->cnt; j >= i+1; j--)
                    p->ptr[j+1] = p->ptr[j];
                p->ptr[i+1] = nullptr;
                p->cnt ++;
            }else{		   
                enter (p->ptr[i], x);
                item * u = p->ptr[i];
                if (u->cnt > n){
                    item * r = new item;
                    for (int j = k+1; j <= 2*k; j++)
                        r->key[j-k-1] = u->key[j];
                    for (int j = k+1; j <= 2*k+1; j++)
                        r->ptr[k+1] = u->ptr[j];
                    int v = u->key[k];
                    u->cnt = k;
                    r->cnt = k;
 
                    for(int j = p->cnt-1; j >= i; j--)
                    p->key[j+1] = p->key[j];
                    p->key[i] = v;
                    for(int j = p->cnt; j >= i+1; j--)
                        p->ptr[j+1] = p->ptr[j];
                    p->ptr[i+1] = r;
                    p->cnt ++;
                }
 
            }
 
        }
    }
}
 
int _tmain(int argc, _TCHAR* argv[])
{
    enter (root, 7);
    enter (root, 10);
    enter (root, 20);
    enter (root, 30);
    enter (root, 25);
    // tiskni (root);
 
    system ("pause");
    return 0;
}