#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 (+ 1)
    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++;
        /* a) i == p->cnt
           b) i <= p->cnt , p->key[i] >= name */
 
        if (i < p->cnt && p->key[i] == name)
            result = true;
        else
            p = p->ptr[i];
    }
    return result;
}
 
/* ---------------------------------------------------------------------- */
 
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)
    { }
    else
    {
       if (p->ptr[i]==nullptr){ // vkladani 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; k--) p->ptr[k+1] = p->ptr[k];
          p->key[i] = name;
          p->ptr[i+1] = nullptr;
          p->cnt++;
      }
      else{ // vlozit do podstromu
         enter0 (p->ptr[i], name);
         if (p->ptr[i]->cnt>=Max)
         {
            Item *a= p->ptr[i]; // a ... puvodni, preplneny podstrom
            int t=a->key[Min]; // nova delici hodnota
 
            // prebytecne prvky do noveho 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; k++) b->ptr[k-Min-1] = a->ptr[k];
            b->cnt= a->cnt-1-Min;
 
            a->cnt=Min; // Min si jich nechame v a
 
            // posuneme hodnoty v (hornim) p
            for (int k = p->cnt-1; k >= i; k--) p->key[k+1] = p->key[k];
            for (int k = p->cnt; k > i; k--) p->ptr[k+1] = p->ptr[k];
            p->key[i] = t; // vlozime novou hodnou
            p->ptr[i+1] = b; // novy ukazatel
            p->cnt++;
       }
      }
  }
}
 
void enter(Item * & p, int name)
{
    if (p==nullptr) p = new Item;
    enter0(p, name);
    if(p->cnt==Max+1){
        Item* a= new Item;
        for (int k = 0; k<Min; k++) a->key[k] = p->key[k];
        for (int k = 0; k<=Min; k++) a->ptr[k] = p->ptr[k];
        a->cnt= Min;
 
        int t=p->key[Min];
 
        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; k++) b->ptr[k-Min-1] = p->ptr[k];
        b->cnt= p->cnt-1-Min;
 
        p->key[0]=t;
        p->ptr[0]=a;
        p->ptr[1]=b;
        p->cnt=1;
 
 
    }
}
 
/* ---------------------------------------------------------------------- */
 
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 (false)
   {
       enter (root, 10);
       enter (root, 5);
       enter (root, 20);
       enter (root, 7);
       enter (root, 15);
 
       enter (root, 30);
       enter (root, 40);
       enter (root, 50);
 
       for (int i = 60; i <= 80; i++)
             enter (root, i);
   }
   else if (false)
   {
      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();
}