#include <cstdio>
#include <cstdlib>

#define DEBUG
#define null 0

class B_Tree{
    private:
        typedef struct NODE{
            int key;
            NODE *next;
            NODE *prev;
            NODE *left_child;
            NODE *right_child;
            void *addr;
        }node;
        typedef struct ADDRESS{
            node *parent_on_left;
            node *parent_on_right;
            node *first;
            node *last;
            int nodes_in_list;
            int visited;
        }addr_block;
        node *root;
        int memory_used;
        int nodes;
        int addr_blocks;
        bool printed;
    public:
        int minimum_degree;
    public:
        B_Tree (int);
        int add_data(int);
        int delete_data(int);
        void * search_data(int);
        void print_tree();
        void print_node(node *);
        ~B_Tree();
    private:
        void * create_node (int ,node *, node *);
        void * initialize_addr (node *, node *, node *, node *);
        void * split_node(node *);
        void * insert_in_list(int, node *);
        void * delete_from_list(int, node*);
        void print_address_block (node *);
        void print_delete(int);

};

B_Tree::B_Tree (int pMinimum_degree){
    memory_used = 0;
    root = null;
    printed = false;
    minimum_degree = pMinimum_degree;
    root = (node *)create_node(0, null, null);
    root->addr = initialize_addr(null, null, root, root);
    nodes = 1;
    addr_blocks = 1;
    return;
}

B_Tree::~B_Tree(){
    #ifdef DEBUG
        printf("@B_tree::~B_Tree().\n");
    #endif
    print_delete(2);
    #ifdef DEBUG
        printf ("@B_Tree::~B_Tree program exited normally.\n");
    #endif
            printf ("@B_Tree::~B_Tree program exited normally.\n");
    return;
}

void * B_Tree::create_node (int pKey, node *pFirst, node *pNext){
    addr_block *laddr = null;
    if (root!=null && root->key==0 && nodes==1){
        root->key = pKey;
        return root;
    }
    node *ltemp = (node *)malloc (sizeof (node));
    ltemp->key = pKey;
    ltemp->prev = pFirst;
    ltemp->next = pNext;
    ltemp->left_child = null;
    ltemp->right_child = null;
    ltemp->addr = null;
    if (pNext!=null){
        if (pNext->prev!=null)
            pNext->prev->next = ltemp;
        pNext->prev = ltemp;
        ltemp->addr = pNext->addr;
    }else
    if (pFirst!=null){
        pFirst->next = ltemp;
        ltemp->addr = pFirst->addr;
    }

    if (ltemp->addr!=null){
         laddr = (addr_block *)ltemp->addr;
         laddr->nodes_in_list++;
         if (ltemp->prev==null)
            laddr->first= ltemp;
         if (ltemp->next==null)
            laddr->last= ltemp;
    }
    memory_used = memory_used+sizeof(ltemp);
    nodes++;
    return ltemp;
}

void * B_Tree::initialize_addr (node *pLeft, node *pRight, node *pFirst, node *pLast){
    addr_block *laddr = null;
    laddr = (addr_block *)malloc (sizeof (addr_block));
    laddr->parent_on_left = pLeft;
    laddr->parent_on_right = pRight;
    laddr->first = pFirst;
    laddr->last = pLast;
    int lcount=0;
    node *lnode = laddr->first;
    while (lnode!=null){
        lnode->addr = laddr;
        lnode = lnode->next;
        lcount++;
    }
    laddr->nodes_in_list=lcount;
    laddr->visited = 0;
    memory_used = memory_used+sizeof(laddr);
    addr_blocks++;
    return laddr;
}

void B_Tree::print_tree (){
    print_delete(0);
//  print_delete(1);
    return;
}

void B_Tree::print_delete(int pTask){
    bool ldone = false, ldelete = false;
    node *lnode = root;
    addr_block *laddr = null;
    if (pTask==2){
        ldelete = true;
        #ifdef DEBUG
            printf ("memory_used: %i nodes %i addr_blocks: %i.\n", memory_used, nodes, addr_blocks);
        #endif
        pTask = 0;
    }
    if (printed){
        pTask = 1;
        printed = false;
    }else{
        pTask = 0; printed = true;
    }
	while (!ldone){
     laddr = (addr_block *)lnode->addr;
	    if (lnode->left_child!=null){
            laddr = (addr_block *)lnode->left_child->addr;
            if (laddr->visited==pTask){
                lnode = lnode->left_child;
                continue;
            }
            else
               laddr = (addr_block *)lnode->addr;
        }
	    if (laddr->visited==pTask){
            if (!pTask){
                if(!ldelete)
                    print_node(lnode);
            }
            if (lnode->next==null){
                laddr->visited = !pTask;
                if (laddr->parent_on_left!=null){
                    lnode = laddr->parent_on_left;
                    if (ldelete){
                        lnode->right_child = (node *)delete_from_list(lnode->right_child->key, lnode->right_child);
                        if (lnode->right_child!=null){
                            laddr = (addr_block *)lnode->right_child->addr;
                            laddr->visited = pTask;
                            lnode = lnode->right_child;
                        }
                    }
                }else
                if (laddr->parent_on_right!=null){
                        lnode = laddr->parent_on_right;
                    if (ldelete){
                        lnode->left_child = (node *)delete_from_list(lnode->left_child->key, lnode->left_child);
                        if (lnode->left_child!=null){
                            laddr = (addr_block *)lnode->left_child->addr;
                            laddr->visited = pTask;
                            lnode = lnode->left_child;
                        }
                    }
                }else
                if (laddr->parent_on_left==null && laddr->parent_on_right==null){
                    laddr->visited = !pTask;
                    if (ldelete){
                        lnode = (node *)delete_from_list(lnode->key, lnode);
                        if (lnode!=null){
                            laddr = (addr_block *)lnode->addr;
                            laddr->visited = pTask;
                            continue;
                        }
                        if (lnode==null){
                            ldone = true;
                            continue;
                        }
                    }
                    ldone = true;
                    continue;
                }
            }else
                lnode = lnode->next;
        }else
        if (laddr->visited!=pTask){
            if (laddr->parent_on_left!=null)
                lnode = laddr->parent_on_left;
            else
            if (laddr->parent_on_right!=null)
                lnode = laddr->parent_on_right;
        }
        if (lnode->right_child!=null){
            laddr = (addr_block *)lnode->right_child->addr;
            if (laddr->visited==pTask){
                lnode = lnode->right_child;
            }else
                laddr = (addr_block *)lnode->addr;
        }
    }
    #ifdef DEBUG
        if (ldelete)
            printf ("memory_left: %i nodes %i addr_blocks: %i.\n", memory_used, nodes, addr_blocks);
    #endif
    return ;
}

void B_Tree::print_node (node *pNode){
    addr_block *laddr = (addr_block *)pNode->addr;
    node *lnode = pNode;
    if(laddr->first==root)
        printf( "ROOT: %i ",lnode->key);
    else
        printf( "node: %i ",lnode->key);
        if (lnode->prev!=null)
            printf( " prev: %i ",lnode->prev->key);
        if (lnode->next!=null)
            printf( " next: %i ",lnode->next->key);
        if (lnode->left_child!=null)
            printf( " left_child: %i ",lnode->left_child->key);
        if (lnode->right_child!=null)
            printf( " right_child: %i ",lnode->right_child->key);
        if (laddr->parent_on_left!=null)
            printf( " left_parent: %i ",laddr->parent_on_left->key);
        if (laddr->parent_on_right!=null)
            printf( " right_parent: %i ",laddr->parent_on_right->key);
        if (lnode==laddr->first)
            printf( " nodes_in_list: %i ",laddr->nodes_in_list);
        printf( "\n");
    return;
}

void B_Tree::print_address_block (node *pNode){
    addr_block *laddr = (addr_block *)pNode->addr;
    printf("@B_Tree::print_address node: %i\n", pNode->key);
    printf("\tnodes_in_list: %i.\n", laddr->nodes_in_list);
    if (laddr->parent_on_left!=null)
        printf("\tparent_on_left: %i\n", laddr->parent_on_left->key);
    if (laddr->parent_on_right!=null)
        printf("\tparent_on_right: %i\n", laddr->parent_on_right->key);
    if (laddr->first!=null)
        printf("\tfirst: %i\n", laddr->first->key);
    if (laddr->last!=null)
        printf("\tlast: %i\n", laddr->last->key);
    return;
}

int B_Tree::add_data(int pKey){
    #ifdef DEBUG
         printf("@B_tree::add_data root: %i key: %i.\n", root->key, pKey);
    #endif
    addr_block *laddr = null;
    node *ltemp = null, *lnode=root;
    lnode = (node *)search_data(pKey);
    #ifdef DEBUG
       printf("@B_tree::add_data after search_node: %i\n", lnode->key);
    #endif
    ltemp = (node *)insert_in_list(pKey, lnode);
    laddr = (addr_block *)ltemp->addr;
    if (laddr->nodes_in_list>=minimum_degree)
        root = (node *)split_node(laddr->first);
    #ifdef DEBUG
        printf("@B_tree::add_data after addition of %i\n", pKey);
//      print_tree ();
        printf("========================\n");
    #endif
    return 0;
}

void * B_Tree::search_data(int pKey){
    bool ldone = false;
    addr_block *laddr = null;
    node *lnode=root;
    while (!ldone){
        laddr = (addr_block *)lnode->addr;
        if (lnode->key>pKey){
            if (lnode->left_child!=null){
                lnode = lnode->left_child;
            }
            else
                 ldone = true;
        }else
        if (lnode->key<pKey){
            if (lnode->next!=null)
                lnode = lnode->next;
            else
            if (lnode->right_child!=null){
                lnode = lnode->right_child;
            }
            else
                ldone = true;
        }else
        if (lnode->key==pKey)
            ldone = true;
    }
    return lnode;
}

int B_Tree::delete_data(int pKey){
    node *lnode = (node *)search_data(pKey);
    addr_block *laddr = (addr_block *)lnode->addr;
    if (lnode==null)
        return 0;
    else
         lnode = (node *)delete_from_list(pKey, laddr->first);
    return 1;
}

void * B_Tree::split_node(node *pNode){
    #ifdef DEBUG
        printf ("@B_tree::split_node\n");
    #endif
    bool ldone = false;
    node *lnode = null, *lparent_on_left = null, *lparent_on_right = null;
    int lcount = 0;
    addr_block *laddr = (addr_block *)pNode->addr, *lnew_addr = null;
    while (!ldone){
        if (laddr->nodes_in_list>=minimum_degree){
            lnode = laddr->first;
            lcount = 0;
            while (lcount<(2*minimum_degree/3)){
                if (minimum_degree<=3 && lcount==1)break;
                lnode = lnode->next;
                lcount++;
            }
            lparent_on_left = laddr->parent_on_left;
            lparent_on_right = laddr->parent_on_right;
            if (lnode->right_child!=null){
                lnew_addr = (addr_block *)lnode->right_child->addr;
                lnew_addr->parent_on_left = null;
            }
            if (lnode->left_child!=null){
                lnew_addr = (addr_block *)lnode->left_child->addr;
                lnew_addr->parent_on_right = null;
            }
            node *llast = laddr->last;
            laddr->last = lnode->prev;
            laddr->parent_on_left = lparent_on_left;
            laddr->parent_on_right = lnode;
            node *ltemp = laddr->first;
            int lcount =0;
            while (ltemp!=null){
                lcount++;
                if (ltemp==laddr->last)break;
                ltemp = ltemp->next;
            }
            laddr->nodes_in_list = lcount;
            lnode->prev->next=null;
            lnode->next->prev = null;
            lnode->left_child = laddr->first;
            lnew_addr = (addr_block *)initialize_addr(lnode, lparent_on_right, lnode->next, llast);
            lnode->prev = null;
            lnode->next = null;
            ltemp = lnew_addr->first;
            while (ltemp!=null){
                ltemp->addr = lnew_addr;
                ltemp = ltemp->next;
            }
            lnode->right_child = lnew_addr->first;
            if (lparent_on_left!=null){
                if (lparent_on_right!=null)
                    lparent_on_right->prev = lnode;
                lparent_on_left->next = lnode;
                lnode->prev = lparent_on_left;
                lnode->prev->next = lnode;
                lnode->next = lparent_on_right;
                lparent_on_left->right_child = lnode->left_child;
                if (lparent_on_right!=null)
                    lparent_on_right->prev = lnode;
                laddr = (addr_block *)lparent_on_left->addr;
                if (lnode->next==null)
                    laddr->last = lnode;
                lcount = 0;
                ltemp = laddr->first;
                while (ltemp!=null){
                    lcount++;
                    ltemp = ltemp->next;
                }
                laddr->nodes_in_list++;
                lnode->addr = laddr;
                if (laddr->parent_on_left!=null)
                    laddr->parent_on_left->right_child = laddr->first;
            }
            if(lparent_on_right!=null){
                lparent_on_right->prev = lnode;
                lnode->prev = lparent_on_left;
                lparent_on_right->left_child = lnode->right_child;
                lnode->next = lparent_on_right;
                lnode->next->prev = lnode;
                if (lparent_on_left!=null)
                    lparent_on_left->next = lnode;
                lparent_on_right->left_child = lnode->right_child;
                laddr = (addr_block *)lparent_on_right->addr;
                if (lnode->prev==null)
                    laddr->first = lnode;
                lcount = 0;
                ltemp = laddr->first;
                while (ltemp!=null){
                    lcount++;
                    ltemp = ltemp->next;
                }
                laddr->nodes_in_list= lcount;
                lnode->addr = laddr;
                if (laddr->parent_on_right!=null)
                    laddr->parent_on_right->left_child = laddr->first;
            }
            if (lparent_on_right==null && lparent_on_left==null){
                lnew_addr = (addr_block *)initialize_addr(null, null, lnode, lnode);
                lnode->addr = lnew_addr;
                lnode->prev = null;
                lnode->next = null;
            }
            #ifdef DEBUG
//                print_tree();
            #endif
        }else
        if (laddr->parent_on_left==null && laddr->parent_on_right==null){
            laddr = (addr_block *)lnode->addr;
            node *ltemp = laddr->first;
            lcount =0;
            while (ltemp!=null){
                lcount++;
                ltemp = ltemp->next;
            }
            laddr->nodes_in_list = lcount;
            root = laddr->first;
            if (laddr->nodes_in_list<minimum_degree){
                ldone = true;
            }
        }else{
            if (laddr->parent_on_left!=null)
                lnode = laddr->parent_on_left;
            if (laddr->parent_on_right!=null)
                lnode = laddr->parent_on_right;
            laddr = (addr_block *)lnode->addr;
            lnode = laddr->first;
        }
    }
    #ifdef DEBUG
      printf ("@B_tree::split_node exit\n");
    #endif
    return root;
}

void * B_Tree::insert_in_list(int pKey, node *pNode){
    #ifdef DEBUG
        printf("@B_tree::insert_in_list node: %i key: %i.\n", pNode->key, pKey);
    #endif
    node *lnode = pNode, *ltemp = null;
    addr_block *laddr = null;
    laddr = (addr_block *)lnode->addr;
    lnode = laddr->first;
    while (lnode!=null){
        if (pKey==lnode->key)
            return laddr->first;
        else
        if (pKey<lnode->key && lnode->prev==null){
            ltemp = (node *)create_node(pKey, null, lnode);
            laddr->first = ltemp;
            if (laddr->parent_on_left!=null)
                laddr->parent_on_left->right_child = laddr->first;
            if (laddr->parent_on_right!=null)
                laddr->parent_on_right->left_child = laddr->first;
        }
        else
        if (pKey>lnode->key && lnode->next==null){
            ltemp = (node *)create_node(pKey, lnode, null);
            laddr->last = ltemp;
        }
        else
        if (pKey>lnode->key  && pKey<lnode->next->key)
            ltemp = (node *)create_node(pKey, lnode, lnode->next);
        else
            lnode = lnode->next;
    }
    lnode = ltemp;
    #ifdef DEBUG
        print_address_block (lnode);
        printf("@B_tree::insert_in_list exit.\n");
    #endif
    return laddr->first;
}

void * B_Tree::delete_from_list(int pKey, node *pNode){
    #ifdef DEBUG
//      printf("@B_tree::delete_from_list first_node: %i key: %i.\n", pNode->key, pKey);
//        print_node (pNode);
    #endif
    node *lnode = pNode;
    addr_block *laddr = null;
    while (lnode!=null){
        if (lnode->key==pKey){
                bool ldone = false; node *lparent = lnode;
                while (!ldone){
                    laddr = (addr_block *)lparent->addr;
                    if (lparent->right_child!=null && lparent->right_child->left_child!=null){
                        lparent->key = lparent->right_child->left_child->key;
                        lparent = lparent->right_child->left_child;
                    }else
                    if (lparent->left_child!= null && lparent->left_child->right_child!=null){
                        lparent->key = lparent->left_child->right_child->key;
                        lparent = lparent->left_child->right_child;
                    }else
                    if (lparent->right_child!=null){
                        lparent->key = lparent->right_child->key;
                        lparent = lparent->right_child;
                    }else
                    if (lparent->left_child!=null){
                        lparent->key = lparent->left_child->key;
                        lparent = lparent->left_child;
                    }else
                    if (lparent->left_child==null && lparent->right_child==null){
                        if (lparent->prev!=null)
                            lparent->prev->next = lparent->next;
                        if (lparent->next!=null)
                            lparent->next->prev = lparent->prev;
                        laddr = (addr_block *)lparent->addr;
                        if (lparent == laddr->last)
                            laddr->last = lparent->prev;
                        if (lparent == laddr->first){
                            if (laddr->parent_on_left!=null)
                                laddr->parent_on_left->right_child = lparent->next;
                            if (laddr->parent_on_right!=null)
                                laddr->parent_on_right->left_child = lparent->next;
                            laddr->first = lparent->next;
                        }
                        laddr->nodes_in_list--;
                        if (lparent->prev==null && lparent->next==null){
                            memory_used = memory_used - sizeof(laddr);
                            addr_blocks--;
                            free(laddr);
                            laddr = null;
                        }
                        memory_used = memory_used - sizeof(lparent);
                        nodes--;
                        #ifdef DEBUG
                            printf(" deleted node: %i\n", lparent->key);
                        #endif
                        free(lparent);
                        ldone = true;
                        lnode = null;
                    }
                }
            }else
                lnode = lnode->next;
    }
    #ifdef DEBUG
//        if (laddr!=null){
//            print_node (laddr->first);
//            print_address_block(laddr->first);
//        }
//        print_tree();
//        printf("@B_tree::delete_from_list exit.\n");
    #endif
    if (laddr!=null)
        return laddr->first;
    else
        return null;
}

int main(void){
    #ifdef DEBUG
        printf ("@main .\n");
    #endif
///*
    int i = 1;
    int limit = 100000;
    B_Tree t(500);
    for (; i<=limit ; i++)
       t.add_data(i);
//    for (i=limit; i>=1 ; i--)
//        t.add_data(i);
//*/

/*
    B_Tree t(3);
    t.add_data (9);
    t.add_data (8);
    t.add_data (2);
    t.add_data (7);
    t.add_data (4);
    t.add_data (5);
    t.add_data (0);
    t.add_data (6);
    t.add_data (9);
    t.add_data (1);
    t.add_data (3);
    t.delete_data(1);
    t.delete_data(2);
    t.delete_data(5);
*/
   t.print_tree();
    return 0;
}