#include <time.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <sstream>
#include <string>

using namespace std;

typedef struct Node {
	int n;
	Node *parent;
    //string info[3];
    int key[3];
	Node* ptr[4];
}Node;

typedef struct Table{
	string fname;
	Node *root;
}Table;
#pragma region Заголовки
vector<string> msgs = { "0. Quit", "1. Add", "2. Show", "3. Delete", "4. Find", "5. Timing","6. Return next" };
vector<string> errmsgs = { "Ok", "Duplicate key" };
vector<string> msgdel = { "Ok","No Item" };

bool StrToInt(string str, int* k)
{
    try
    {
        *k = std::stoi(str);
        return true;
    }
    catch (const std::exception&)
    {
        return false;
    }
}
int dialog();

int D_Add(Node** root);
int D_Show(Node** root);
int D_Delete(Node** root);
int D_Find(Node** root);
int D_Timing(Node**);
int D_Return(Node** root);
//D_Add
int findplace(Node* cur);
Node* split(Node* cur, int position);
int insert(Node** root, int k, string info);
//D_Show
void printTree(Node* root, int level);
void reserve(Node* root);
//D_Delete
Node* workhead(Node*);
Node* sit1(Node*, int k);
Node* sit2(Node*, int);
int del(Node** root, int k);
//D_Find
int find(Node** root, int k);
//D_Timing
int findt(Node** root, int k);
//D_Return
int findr(Node** root, int k);
bool D_Load(Table* ptab);
bool loaded(Table* ptab, string fname);
int D_Save(Table* ptab);
void save(FILE* fp, Node* cur);
void delTree(Node* root);
#pragma endregion

int dialog()
{
    string errmsg = "";
    string result;
    int i,rc;
    while (true)
    {
        for (i = 0; i < msgs.size(); ++i)
            cout << msgs[i] << endl;
        cin >> result;
        if (StrToInt(result, &rc) && rc >= 0 && rc <= 6)
            return rc;
        else
            cout << "Wrong. Repeat.";
    }
    return 0;
}

//1.
int D_Add(Node** root)
{
    int k, rc;
    string info = "", str;
    do
    {
        cout << "Enter key:-->";
        cin >> str;
    } while (!StrToInt(str, &k));
    cout << "Enter info:" << endl;
    cin >> info;
    if (info == "")
        return 0;
    rc = insert(root, k, info);
    cout << errmsgs[rc] << " : " << k << endl;
    return 1;
}
//2.
int D_Show(Node **root)
{
    int level = 0, k = 0, n;
    Node *cur=*root;
    string str;
    do
    {
        cout << "Which kind of form?" << endl;
        cout << "0.Tree     N.Inverse" << endl;
        cin >> str;
    } while (!StrToInt(str, &k));
    if (k==0)
        printTree(cur,level);
    else
        reserve(cur);
    return 1;
}
//3.
int D_Delete(Node** root)
{
    int k = 0, rc;
    string str;
    do
    {
        cout << "Enter key:-->";
        cin >> str;
    } while (!StrToInt(str, &k));
    rc = del(root, k);
    cout << msgdel[rc] << ": " << k;
    return 1;
}
//4.
int D_Find(Node **root)
{
    int k,rc,n;
    string str;
    do
    {
        cout << "Enter key:-->";
        cin >> str;
    } while (!StrToInt(str, &k));
    rc = find (root,k);
    if (rc == 0)
        cout << "No item" << endl;
    else
        cout << "Ok - " << k << endl;;
    return 1;
}
//5.
int D_Timing(Node** cur)
{
    Node* root = NULL;
    int n = 10, key[10000], k, cnt = 1000000, i, m;
    clock_t first, last;
    srand(time(NULL));
    while (n-- > 0)
    {
        for (i = 0; i < 10000; ++i)
            key[i] = rand() * rand();
        for (i = 0; i < cnt;)
        {
            k = rand() * rand();
            if (!insert(&root, k, "a"))
                ++i;
        }
        m = 0;
        first = clock();
        for (i = 0; i < 10000; ++i)
            if (findt(&root, key[i]))
                ++m;
        last = clock();
        cout << m << "items was found" << endl;
        cout << "test #" << 10 - n << ", number of nodes = " << (10 - n) * cnt << ", time = " << last - first << endl;
    }
    delTree(root);
    return 1;
}
//6.
int D_Return(Node **root)
{
	int k,rc,n;
	printf("Enter key:-->");
	//n=getInt(&k);
	if (n==0)
	    return 0;
	rc = findr (root,k);
	if (rc==1)
	    printf("No item\n");
	else
	    printf("Ok\n",k);
	return 1;
}

//D_Add
int findplace(Node *cur) //Поиск узла необходимого для разбиения
{
    int k = cur->key[1];
    Node *par= cur->parent;
    for (int i=0;i<par->n;++i)
        if (k < par->key[i])
            return i;

    return par->n;
}

Node *split(Node *cur,int position)
{
    //for (int i = 0; i < 4; i++)
    //{
    //    x->ptr[i] = 0;
    //    y->ptr[i] = 0;
    //    z->ptr[i] = 0;
    //}
    //for (int i = 0; i < 3; i++)
    //{
    //    x->key[i] = 0;
    //    y->key[i] = 0;
    //    z->key[i] = 0;
    //    x->info[i] = "";
    //    y->info[i] = "";
    //    z->info[i] = "";
    //}
    //Узел который мы должны разбить
    Node* x = new Node();//левый узел
    Node* z = new Node();//правый узел
    Node* par = cur->parent;
    if (par != NULL) // Случай когда разбиваем не корневую вершину
    {
        for (int i = 2; i > position; --i)//Сдвигаем вправо в предке ключи
        {
            par->key[i] = par->key[i - 1];
            //par->info[i] = par->info[i - 1];
        }
        for (int i = 3; i > position + 1; --i)//сдвигаем указатели
            par->ptr[i] = par->ptr[i - 1];

        par->key[position] = cur->key[1];
        //par->info[position] = cur->info[1];
        par->ptr[position] = x;
        par->ptr[position + 1] = z;
        par->n++;

        x->parent = par;
        z->parent = par;

        //Описываем левого
        x->n = 1;
        x->key[0] = cur->key[0];
        //x->info[0] = cur->info[0];
        if (cur->ptr[0] != NULL)//Если есть внизу листья надо указать им предка
        {
            x->ptr[0] = cur->ptr[0];
            x->ptr[0]->parent = x;
        }
        if (cur->ptr[1] != NULL)
        {
            x->ptr[1] = cur->ptr[1];
            x->ptr[1]->parent = x;
        }

        //Правого
        z->n = 1;
        z->key[0] = cur->key[2];
        //z->info[0] = cur->info[2];
        if (cur->ptr[2] != NULL)//Если есть внизу листья надо указать им предка
        {
            z->ptr[0] = cur->ptr[2];
            z->ptr[0]->parent = z;
        }
        if (cur->ptr[3] != NULL)
        {
            z->ptr[1] = cur->ptr[3];
            z->ptr[1]->parent = z;
        }
        //Возвращаем предка в который скинули медиалнный узел
        delete cur;
        return par;
    }
    else
    {
        cur->n = 1;
        x->parent = cur;
        z->parent = cur;

        x->n = 1;
        x->key[0] = cur->key[0];
        //x->info[0] = cur->info[0];
        if (cur->ptr[0] != NULL)
        {
            x->ptr[0] = cur->ptr[0];
            x->ptr[0]->parent = x;
        }
        if (cur->ptr[1] != NULL)
        {
            x->ptr[1] = cur->ptr[1];
            x->ptr[1]->parent = x;
        }

        z->n = 1;
        z->key[0] = cur->key[2];
        //z->info[0] = cur->info[2];
        if (cur->ptr[2] != NULL)
        {
            z->ptr[0] = cur->ptr[2];
            z->ptr[0]->parent = z;
        }
        if (cur->ptr[3] != NULL)
        {
            z->ptr[1] = cur->ptr[3];
            z->ptr[1]->parent = z;
        }

        cur->key[0] = cur->key[1];
        //cur->info[0] = cur->info[1];
        cur->ptr[0] = x;
        cur->ptr[1] = z;

        //для удобства отладки очистим остальные поля
        cur->key[1] = 0;
        //cur->info[1] = "";
        cur->key[2] = 0;
        //cur->info[2] = "";
        cur->ptr[2] = NULL;
        cur->ptr[3] = NULL;
        //Возвращаем результат разбиения
        return cur;
    }
}

int insert(Node** root, int k, string info)
{
    int i, j = 0, f = 0;
    Node* newnode = NULL, * cur = NULL;
    if (*root == NULL) //Проверяем корень дерева
    {
        *root = new Node();
        (*root)->n = 1;
        (*root)->key[0] = k;
        //(*root)->info[0] = info;
        (*root)->parent = NULL;
        for (i = 0; i < 4; ++i)
            (*root)->ptr[i] = NULL;
        return 0;
    }
    cur = *root;
    while (cur != NULL)
    {
        if (cur->n == 3)//Если узел полный
        {
            if(cur->parent!=NULL)
                j = findplace(cur);
            cur = split(cur, j);
            if (cur->parent==NULL)
                *root = cur;
        }
        for (i = 0; i < cur->n; ++i) //Проверяем ключи
            if (cur->key[i] == k)
                return 1;

        //Вставка элементов узел
        if (k < cur->key[0]) //Уход в 1 ветвь
        {
            if (cur->ptr[0] == NULL)//Листа нет
            {
                //Вставляем со сдвигом вправо.
                cur->key[2] = cur->key[1];
                //cur->info[2] = cur->info[1];
                cur->key[1] = cur->key[0];
                //cur->info[1] = cur->info[0];
                cur->key[0] = k;
                //cur->info[0] = info;
                cur->ptr[3] = cur->ptr[2];
                cur->ptr[2] = cur->ptr[1];
                cur->ptr[1] = NULL;
                cur->n++;
                return 0;
            }
            else
                cur = cur->ptr[0];
        }
        else
            if (cur->n == 1 || k < cur->key[1])//Случай когда либо 1 элемент либо надо вставить между 1 и 2 *|А|*|*
            {
                if (cur->ptr[1] == NULL)
                {
                    cur->key[2] = cur->key[1];
                    //cur->info[2] = cur->info[1];
                    cur->ptr[3] = cur->ptr[2];
                    cur->ptr[2] = NULL;
                    cur->key[1] = k;
                    //cur->info[1] = info;
                    cur->n++;
                    return 0;
                }
                else
                    cur = cur->ptr[1];
            }
            else
            {
                if (cur->ptr[2] == NULL)
                {
                    cur->key[2] = k;
                    //cur->info[2] = info;
                    cur->n = 3;
                    cur->ptr[3] = NULL;
                    return 0;
                }
                else
                    cur = cur->ptr[2];
            }
    }
}

//D_Show
void printTree(Node *root,int level)
{
    int i;
    if (root)
    {
        printTree(root->ptr[0],level+1);
        for ( i=0;i<level;i++)
            printf("    ");
        if (root->n==1)
        {
            printf(" {%d} \n",root->key[0]);
            printf("\n");
        }
        else
            printf(" {%d \n",root->key[0]);
        if (root->n > 1)
        {
            for ( i=0;i<level;i++)
                printf("    ");
            if (root->n==2)
            {
                printf(" %d} \n",root->key[1]);
                printf("\n");
            }
            else
                printf(" %d \n",root->key[1]);
        }
        printTree(root->ptr[1],level+1);
        printTree(root->ptr[2],level+1);
        if (root->n > 2)
        {
            for ( i=0;i<level;i++)
                printf("    ");
            printf(" %d}\n",root->key[2]);
            printf("\n");
        }
        printTree(root->ptr[3],level+1);
    }
}

void reserve(Node* root)
{
    /*if (root == NULL)
    {
        return;
    }
    reserve(root->ptr[3]);
    if (root->n == 3)
        printf("%d:%s  ", root->key[2], root->info[2]);
    reserve(root->ptr[2]);
    if (root->n > 1)
        printf("%d:%s  ", root->key[1], root->info[1]);
    reserve(root->ptr[1]);
    printf("%d:%s  ", root->key[0], root->info[0]);
    reserve(root->ptr[0]);*/
}

//D_Delete
Node *sit1(Node *cur,int k)
{
    int j,i,p,s;
    Node *rod,*x1=NULL,*x2=NULL,*z1,*z2;
    while (cur != NULL)
    {
        j=cur->n;
        for (i=0;i<cur->n;++i)
        {
            if (k==cur->key[i])
            {
                rod=cur->parent;
                for(p=0;p<rod->n+1;++p)
                {
                    if (rod->ptr[p]==cur)
                        break;
                }
                if (p+1 <=rod->n)
                    x1=rod->ptr[p+1];
                if (p-1 >= 0)
                    x2=rod->ptr[p-1];
                if (cur->n==1)
                {
                    if (x1 != NULL)
                        if (x1->n >=2)
                        {
                            cur->key[1]=rod->key[p];
                            //cur->info[1]=rod->info[p];
                            cur->n=cur->n+1;
                            rod->key[p]=x1->key[0];
                            //rod->info[p]=x1->info[0];
                            cur->ptr[2]=x1->ptr[0];
                            x1->key[0]=x1->key[1];
                            //x1->info[0]=x1->info[1];
                            x1->key[1]=x1->key[2];
                            //x1->info[1]=x1->info[2];
                            x1->n=x1->n-1;
                            return cur;
                        }
                    if (x2 != NULL)
                        if ((x2->n >=2) && (rod->n > 1))
                        {
                            if (p < rod->n)
                            {
                                cur->key[1]=cur->key[0];
                                //cur->info[1]=cur->info[0];
                                cur->ptr[2]=cur->ptr[1];
                                cur->ptr[1]=cur->ptr[0];
                                cur->ptr[0]=x2->ptr[x2->n-1];
                                cur->key[0]=rod->key[p-1];
                                //cur->info[0]=rod->info[p-1];
                                cur->n=cur->n+1;
                            }
                            rod->key[p-1]=x2->key[x2->n-1];
                            rod->ptr[p-1]=x2;
                            //rod->info[p-1]=x2->info[x2->n-1];
                            if (p>= rod->n)
                                rod->n=rod->n+1;
                            x2->n=x2->n-1;
                            return cur;
                        }
                }
                else
                {
                    if ((x1 != NULL) && (x2 != NULL))
                        if ((x1->n==1) && (x2->n==1)  && (cur->n==1))
                        {
                            if ( x1 != NULL)
                            {
                                cur->key[1]=rod->key[p];
                                //cur->info[1]=rod->info[p];
                                cur->key[2]=x1->key[0];
                                //cur->info[2]=x1->info[0];
                                cur->ptr[2]=x1->ptr[0];
                                cur->ptr[3]=x1->ptr[1];
                                rod->n=rod->n-1;
                                for (s=p;s<rod->n-p;++s)
                                {
                                    rod->key[s]=rod->key[s+1];
                                    //rod->info[s]=rod->info[s+1];
                                }
                                if (p==0)
                                {
                                    rod->ptr[1]=rod->ptr[2];
                                    rod->ptr[2]=rod->ptr[3];
                                }
                                if (p==1)
                                {
                                    rod->ptr[2]=rod->ptr[3];
                                }
                                z1=x1->ptr[0];
                                z2=x1->ptr[1];
                                if (z1 != NULL)
                                    z1->parent=cur;
                                if (z2 != NULL)
                                    z2->parent=cur;
                                cur->n=3;
                                return cur;
                            }
                        }
                }
                return cur;
            }
            if (k < cur->key[i])
            {
                j=i;
                break;
            }
        }
        cur=cur->ptr[j];
    }
    return NULL;
}

Node *sit2(Node *cur,int i)
{
    Node *y=cur->ptr[i],*z=cur->ptr[i+1],*z1,*z2,*rod;
    int k,j;
    string in;
    if (z->n >= 2 )
    {
        k=cur->key[i];
        //in=cur->info[i];
        cur->key[i]=z->key[z->n-1];
        //cur->info[i]=z->info[z->n-1];
        z->key[z->n-1]=k;
        //z->info[z->n-1]=in;
        cur=z;
    }
    if (y->n >= 2 )
    {
        k=cur->key[i];
        //in=cur->info[i];
        cur->key[i]=y->key[y->n-1];
        //cur->info[i]=y->info[y->n-1];
        y->key[y->n-1]=k;
        //y->info[y->n-1]=in;
        cur=y;
    }
    else
    if (y->n >= 2 )
    {
        k=cur->key[i];
        //in=cur->info[i];
        cur->key[i]=y->key[y->n-1];
        //cur->info[i]=y->info[y->n-1];
        y->key[y->n-1]=k;
        //y->info[y->n-1]=in;
        cur=y;
    }
    else
    if ((y->n == 1) && (z->n == 1))
    {
        y->key[1]=cur->key[i];
        //y->info[1]=cur->info[i];
        cur->n=cur->n-1;
        cur->ptr[i+1]=NULL;
        y->ptr[2]=z->ptr[0];
        y->ptr[3]=z->ptr[1];
        y->key[2]=z->key[0];
        //y->info[2]=z->info[0];
        y->n=3;
        z1=z->ptr[0];
        z2=z->ptr[1];
        if (z1 != NULL)
            z1->parent=y;
        if (z2 != NULL)
            z2->parent=y;
        for (j=i;j<cur->n-i;++j)
        {
            cur->key[j]=cur->key[j+1];
            //cur->info[j]=cur->info[j+1];
        }
        if (i==0)
        {
            cur->ptr[1]=cur->ptr[2];
            cur->ptr[2]=cur->ptr[3];
        }
        if (i==1)
        {
            cur->ptr[2]=cur->ptr[3];
        }
        free(z);
        if (cur->n==0)
        {
            y->parent=cur->parent;
            rod=cur->parent;
            for (j=0;j<rod->n+1;++j)
                if (rod->ptr[j]==cur)
                {
                    rod->ptr[j]=y;
                    free(cur);
                }
        }
        cur=y;
    }
    return cur;
}

int del(Node** root, int k)
{
    Node* cur = *root, * br = NULL, * rod = NULL;
    int i, j, c;
    cur = workhead(cur);
    *root = cur;
    if (cur == NULL)
        return 1;
    while ((cur->ptr[0] != NULL))
    {
        for (i = 0; i < cur->n; ++i)
            if (cur->key[i] == k)
            {
                cur = sit2(cur, i);
                c++;
                break;
            }
        if (c != 1)
            cur = sit1(cur, k);
        c = 0;
        if (cur == NULL)
            return 1;
    }
    if (cur->n > 1)
    {
        for (i = 0; i < cur->n; ++i)
            if (cur->key[i] == k)
            {
                cur->n = cur->n - 1;
                for (j = i; j < cur->n; ++j)
                {
                    cur->key[j] = cur->key[j + 1];
                    //cur->info[j]=cur->info[j+1];
                }
                return 0;
            }

    }
    else {
        rod = cur->parent;
        if (rod == NULL)
        {
            *root = NULL;
            free(cur);

            return 0;
        }
        for (i = 0; i < rod->n + 1; ++i)
        {
            if (rod->ptr[i] == cur)
            {
                if ((rod->ptr[i + 1] != NULL) && (rod->n >= i + 1))
                {

                    br = rod->ptr[i + 1];
                    if (br->n > 1)
                    {
                        cur->key[0] = rod->key[i];
                        //cur->info[0]=rod->info[i];
                        rod->key[i] = br->key[0];
                        //rod->info[i]=br->info[0];
                        br->key[0] = br->key[1];
                        //br->info[0]=br->info[1];
                        br->key[1] = br->key[2];
                        //br->info[1]=br->info[2];
                        br->n = br->n - 1;
                        return 0;
                    }
                    else
                    {
                        if (rod->n == 1)
                        {
                            rod->n = 2;
                            rod->key[1] = rod->key[0];
                            //rod->info[1]=rod->info[0];
                            rod->key[0] = br->key[0];
                            //rod->info[0]=br->info[0];

                            for (j = 0; j < 3; ++j)
                                rod->ptr[j] = NULL;
                            free(cur);
                            free(br);
                            return 0;
                        }
                        else
                            rod->ptr[i] = NULL;
                        free(cur);
                        return 0;
                    }
                }
                else {
                    rod->ptr[i] = NULL;
                    free(cur);
                    return 0;
                }
            }
        }
    }
}

Node *workhead(Node *root)
{
    Node *cur=root,*y,*z,*z1,*z2;
    if ((cur->n==1) && (cur->ptr[0] != NULL) && (cur->ptr[1] != NULL))
    {
        if ((cur->ptr[0]->n==1) && (cur->ptr[1]->n==1))
        {
            y=cur->ptr[0];
            z=cur->ptr[1];
            z1=z->ptr[0];
            z2=z->ptr[1];
            y->n=3;
            y->parent=NULL;
            y->key[1]=cur->key[0];
            y->key[2]=z->key[0];
            y->ptr[2]=z->ptr[0];
            y->ptr[3]=z->ptr[1];
            z1->parent=y;
            z2->parent=y;
            free(z);
            free(cur);
            root=y;
        }
    }
    return root;
}

//D_Find
int find(Node **root,int k)
{
    Node *cur=*root;
    int i,j;
    while (cur != NULL)
    {
        j=cur->n;
        for (i=0;i<cur->n;++i)
        {
            if (k==cur->key[i])
            {
                //cout << cur->info[i] << " key:" << cur->key[i] << endl;
                cout << " key:" << cur->key[i] << endl;
                return 1;
            }
            if (k < cur->key[i])
            {
                j=i;
                break;
            }
        }
        cur=cur->ptr[j];
    }
    return 0;
}

//D_Timing
int findt(Node** root, int k)
{
    Node* cur = *root;
    int i, j;
    while (cur != NULL)
    {
        j = cur->n;
        for (i = 0; i < cur->n; ++i)
        {
            if (k == cur->key[i])
                return 1;
            if (k < cur->key[i])
            {
                j = i;
                break;
            }
        }
        //if (cur->ptr[j] != NULL)
        cur = cur->ptr[j];
    }
    return 0;
}

//D_Return
int findr(Node** root, int k)
{
    Node* cur = *root;
    string in;
    int i, j, l, n;
    while (cur != NULL)
    {
        j = cur->n;
        for (i = 0; i < cur->n; ++i)
        {
            if (k == cur->key[i])
            {
                n = cur->n;
                if (i < cur->n - 1)
                {
                    l = cur->key[i + 1];
                    in = cur->key[i + 1];
                }
                cur = cur->ptr[i + 1];
                if (cur != NULL)
                {
                    //printf("\"%s\" key:%d\n",cur->info[0],cur->key[0]);
                    return 0;
                }
                else
                {
                    if (i < n - 1)
                    {
                        //printf("\"%s\" key:%d\n",in,l);
                        return 0;
                    }
                }
                return 1;
            }
            if (k < cur->key[i])
            {
                j = i;
                break;
            }
        }
        cur = cur->ptr[j];
    }
}

#pragma region Load_Save
bool D_Load(Table* ptab)
{
    int rc;
    string fname;
    cout << "Enter file name: -->";
    //getline(cin, fname);
    fname = "D:\\tree.txt";
    if (fname == "")
        return true;
    if (loaded(ptab, fname))
        return true;
    else
    {
        cout<<"The appropriate date file is not exists";
        false;
    }
}
bool loaded(Table* ptab, string fname)
{
    std::ifstream fin;
    fin.open("D:\\tree.txt");
    if (fin.is_open())
    {
        int count;
        string str, line;
        while (getline(fin, line))
        {
            stringstream ss(line);
            vector <string> array;
            while (ss >> str)
                array.push_back(str);
            insert(&(ptab->root), std::stoi(array[0]), array[1]);
        }
        fin.close();
        return true;
    }
    else
        return false;
}

int D_Save(Table* ptab)
{
    //FILE *fd=NULL;
    //int c=0;
    //fd=fopen(ptab->fname,"w");
    //if (fd==NULL)
    //   return 0;
    //save(fd,ptab->root);
    //fclose(fd);
    return 1;
}
void save(FILE* fp, Node* cur)
{
    if (cur == NULL)
    {
        return;
    }
    save(fp, cur->ptr[3]);
    if (cur->n == 3)
    {
        fprintf(fp, "%d\n", cur->key[2]);
        //fprintf(fp, "%s\n", cur->info[2]);
    }
    save(fp, cur->ptr[2]);
    if (cur->n > 1)
    {
        fprintf(fp, "%d\n", cur->key[1]);
        //fprintf(fp, "%s\n", cur->info[1]);
    }
    save(fp, cur->ptr[1]);
    fprintf(fp, "%d\n", cur->key[0]);
    //fprintf(fp, "%s\n", cur->info[0]);
    save(fp, cur->ptr[0]);
}
#pragma endregion



void delTree(Node *root)
{
    if (root ==NULL)
	{
		return;
	}
	delTree(root->ptr[0]);
    delTree(root->ptr[1]);
    delTree(root->ptr[2]);
    delTree(root->ptr[3]);
    delete(root);
}

int main() {
    Table ptab;
    int rc, kc;
    int (*fptr[])(Node**) = { NULL, D_Add,D_Show,D_Delete,D_Find,D_Timing,D_Return };
    ptab.root = NULL;

    if (!D_Load(&ptab))
        return 1;

    while (rc = dialog())
        if (!fptr[rc](&(ptab.root)))
            break;

    //kc = D_Save(&ptab);
    //if (kc == 0)
    //    printf("Invalid save");
    //delTree(ptab.root);
    cout << "That all";
    return 0;
}