#include "btreewin.h"
#include "ui_btreewin.h"

#include <QApplication>
#include <QTreeWidgetItem>

#include <string>
using namespace std;

#define nullptr NULL

BTreeWin * win = nullptr;

/* ---------------------------------------------------------------------- */

const int Min = 2;
const int Max = 2 * Min;

struct Item
{
    int cnt; // 1 <= cnt <= max
    int key [Max+1]; // 0..cnt-1
    Item* ptr [Max+2]; // 0..cnt
    Item ();
};

Item::Item ()
{
    cnt = 0;
    for (int i = 0; i < Max + 1; i++) key[i] = 0;
    for (int i = 0; i < Max + 2; i++) ptr[i] = nullptr;
}

Item * root = nullptr;
void display (Item * p);

/* ---------------------------------------------------------------------- */

bool search (Item * p, int name)
{
    bool result = false;
    while (p != nullptr && ! result)
    {
        int i = 0;
        while (i < p->cnt && p->key[i] < name) i++;
        if (i < p->cnt && p->key[i] == name)
            result = true;
        else
            p = p->ptr[i];
    }
    return true;
}

/* ---------------------------------------------------------------------- */

void enter0 (Item * p, int name)
{
    int i = 0;
    while (i < p->cnt && p->key[i] < name) i++;
    if (i < p->cnt && p->key[i] == name)
    { /* hodnota je jiz ve stromu */ }
    else
    {
        if (p->ptr[i] != nullptr)
        {
            Item * a = p->ptr[i];
            enter0 (a, name);
            if (a->cnt > Max)
            {
                int t = a->key [Min]; /* delici bod */

                /* presun do b */
                Item * b = new Item;
                for (int k = Min+1; k < a->cnt; k++) b->key[k-Min-1] = a->key[k];
                for (int k = Min+1; k < a->cnt+1; k++) b->ptr[k-Min-1] = a->ptr[k];
                b->cnt = a->cnt-1-Min;

                /* vymazani a */
                for (int k = Min; k < a->cnt; k++) a->key[k] = 0;
                for (int k = Min+1; k < a->cnt+1; k++) a->ptr[k] = nullptr;
                a->cnt = Min;

                /* pridani do p */
                for (int k = p->cnt-1; k >= i; k--) p->key[k+1] = p->key[k];
                for (int k = p->cnt; k >= i+1; k--) p->ptr[k+1] = p->ptr[k];
                p->key[i] = t;
                p->ptr[i+1] = b;
                p->cnt ++;
            }
        }
        else
        {
            /* pridani do listu */
            for (int k = p->cnt-1; k >= i; k--) p->key[k+1] = p->key[k];
            for (int k = p->cnt; k >= i+1; k--) p->ptr[k+1] = p->ptr[k];
            p->key[i] = name;
            p->ptr[i+1] = nullptr;
            p->cnt ++;
        }
    }
}

void enter (Item * & p, int name)
{
    if (p == nullptr)
        p = new Item; /* vytvorit koren dosud prazneho stromu */

    enter0 (p, name);

    if (p->cnt > Max)
    {
       /* novy levy prvek */
       Item * a = new Item;
       for (int k = 0; k < Min; k++) a->key[k] = p->key[k];
       for (int k = 0; k < Min+1; k++) a->ptr[k] = p->ptr[k];
       a->cnt = Min;

       /* delici bod */
       int t = p->key [Min];

       /* novy pravy prvek */
       Item * b = new Item;
       for (int k = Min+1; k < p->cnt; k++) b->key[k-Min-1] = p->key[k];
       for (int k = Min+1; k < p->cnt+1; k++) b->ptr[k-Min-1] = p->ptr[k];
       b->cnt = p->cnt-1-Min;

       /* korenovy prvek */
       for (int k = 0; k < p->cnt; k++) p->key[k] = 0;
       for (int k = 0; k < p->cnt+1; k++) p->ptr[k] = nullptr;
       p->cnt = 1;
       p->key [0] = t;
       p->ptr [0] = a;
       p->ptr [1] = b;
    }
}

/* ---------------------------------------------------------------------- */

QIcon folderIcon;
QIcon valueIcon;

const bool use_colors = true;

QColor color (int level)
{
   return QColor::fromHsv ((30*(level-1))%360, 255, 255);
}

void displayBranch (QTreeWidgetItem * target, Item * p, int level = 1)
{
    QTreeWidgetItem * node = new QTreeWidgetItem;
    node->setIcon (0, folderIcon);
    if (use_colors)
       node->setForeground (0, color (level));
    target->addChild (node);

    if (p != nullptr)
    {
        QString txt = "";
        for (int i = 0; i < p->cnt ; i++)
        {
            if (i != 0) txt = txt + ", ";
            txt = txt + QString::number (p->key[i]);
        }
        node->setText (0, txt);

        bool any = false;
        for (int i = 0; i < p->cnt ; i++)
        {
            if (p->ptr[i] != nullptr)
            {
                displayBranch (node, p->ptr[i], level+1);
                any = true;
            }

            QTreeWidgetItem * item = new QTreeWidgetItem;
            item->setText (0, QString::number (p->key[i]));
            item->setIcon (0, valueIcon);
            if (use_colors)
               item->setForeground (0, color (level+1));
            node->addChild (item);
        }

        int i = p->cnt;
        if (p->ptr[i] != nullptr)
        {
            displayBranch (node, p->ptr[i], level+1);
            any = true;
        }

        if (any)
           node->setExpanded (true);

    }
}

void display (Item * p)
{
    folderIcon = QIcon (":/folder.png");
    valueIcon = QIcon (":/value.png");
    displayBranch (win->ui->treeWidget->invisibleRootItem(), p);
    // win->ui->treeWidget->expandAll ();
}

/* ---------------------------------------------------------------------- */

void run ()
{
   if (true)
   {
       enter (root, 10);
       enter (root, 5);
       enter (root, 20);
       enter (root, 7);
       enter (root, 15);

       if (false)
          for (int i = 20; i <= 80; i++)
             enter (root, i);
   }
   else if (true)
   {
      for (int i = 1; i < 100; i++)
      {
         int v = rand () % 1000;
         enter (root, v);
      }
   }
   else
   {
      for (int i = 1; i < 8000; i++)
      {
         int v = rand () % 10000;
         enter (root, v);
      }
   }

    /*
    display (root);
    trace = true;
    enter (root, "41");
    */
    display (root);
}

/* ---------------------------------------------------------------------- */

BTreeWin::BTreeWin(QWidget *parent) :
    QMainWindow(parent),
    ui(new Ui::BTreeWin)
{
    ui->setupUi(this);
    ui->treeWidget->setFont(QFont ("SansSerif", 24));
    win = this;
    run ();
}

BTreeWin::~BTreeWin()
{
    delete ui;
}

int main(int argc, char *argv[])
{
    QApplication a(argc, argv);
    BTreeWin w;
    w.show();

    return a.exec();
}