]> git.llucax.com Git - z.facultad/75.52/treemulator.git/blobdiff - src/btree.cpp
Selección visual del nodo actual.
[z.facultad/75.52/treemulator.git] / src / btree.cpp
index 4d28e4989d4cb905d87bd8880ec808dabc6d9e58..225d0435eddefa9aa97ffd98219aa8590cb8506c 100644 (file)
@@ -103,21 +103,44 @@ Clave* BTree::AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &ri
        ReadNodoHeader (node, &node_header);
 
        if (node_header.level != 0) {
+               std::cout << "Entrando nodo level = " << node_header.level << std::endl;
                /* No estoy en una hoja, asi que tengo que buscar
                 * para donde moverme para agregar la clave
                 */
-               /* TODO :) */
+               std::cout << "Leo Claves" << std::endl;
                node_keys = ReadKeys (node, node_header);
+
                std::list<BTreeData *>::iterator it = node_keys.begin ();
+               std::list<BTreeData *>::iterator posterior;
+               std::list<BTreeData *>::iterator ultima;
        
                /* Se supone que la primera es un hijo :) */
-               //BTreeData *left_child = (*it);
-               PrintNode (node_num);
-               std::cout << "TODO!!" << std::endl;
-               return NULL;
+               BTreeData *lchild = (*it++);
+               posterior = it;
+
+               while (it != node_keys.end ()) {
+                       if ((*data) < (*(*it)))
+                               break;
+                       ultima = it;
+                       it++;
+               }
+
+               if (it == posterior) {
+                       std::cout << "==== Me voy al nodo " << lchild->getChild () << std::endl;
+                       k = AddKeyR (k, lchild->getChild (), left_child, right_child);
+               } else {
+                       std::cout << "==== Me voy al nodo " << (*ultima)->getChild () << std::endl;
+                       k = AddKeyR (k, (*ultima)->getChild (), left_child, right_child);
+               }
+               if (k) {
+                       data = new BTreeData (k->Clone (), right_child);
+               }
        }
 
 
+       /* Nada que hacer */
+       if (!k) return NULL;
+
        /* Estoy en una hoja, veo si lo puedo agregar */
 
        if (node_header.free_space > data->Size ()) {
@@ -148,19 +171,28 @@ Clave* BTree::AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &ri
                uint new_node_num;
                uchar *new_node = NewBlock (new_node_num);
                ReadNodoHeader (new_node, &new_node_header);
+               new_node_header.level = node_header.level;
 
                node_keys = ReadKeys (node, node_header);
                new_node_keys = ReadKeys (new_node, new_node_header);
 
                /* Agrego la clave en la lista que ya tengo de manera ordenada */
                std::list<BTreeData *>::iterator it = node_keys.begin ();
+               std::list<BTreeData *>::iterator previt = node_keys.begin ();
 
+               if (node_header.level != 0) {
+                       /* La primera es ChildData */
+                       it++;
+                       previt = it;
+               }
+       
                while (it != node_keys.end ()) {
                        BTreeData *datait;
                        datait = (*it);
                        if ((*data) < (*datait))
                                /* Me pase, lo agrego aca! */
                                break;
+                       previt = it;
                        it++;
                }
                if (it != node_keys.end ())
@@ -196,7 +228,14 @@ Clave* BTree::AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &ri
                        used += d->Size ();
                        it++;
                }
-               kout = (*it++)->getClave (); // Esta se retorna al "padre" para que se la agregue
+               kout = (*it)->getClave (); // Esta se retorna al "padre" para que se la agregue
+               if (node_header.level != 0) {
+                       new_node_keys.push_back ( new BTreeChildData ((*it)->getChild ()));
+               }
+               it++;
+
+               std::string s = *kout;
+               std::cout << "SPLIT Retorna : " << s << std::endl;
                while (it != node_keys.end ()) {
                        BTreeData *d = (*it);
                        new_node_keys.push_back (d);
@@ -250,6 +289,7 @@ std::list<BTreeData *> BTree::ReadKeys (uchar *node, BTreeNodeHeader &node_heade
 {
        std::list<BTreeData *> keys;
        node += sizeof (BTreeNodeHeader);
+       uint count = node_header.item_count;
 
        if (node_header.item_count == 0) return keys;
 
@@ -258,9 +298,10 @@ std::list<BTreeData *> BTree::ReadKeys (uchar *node, BTreeNodeHeader &node_heade
                BTreeChildData *d = new BTreeChildData (node);
                node += d->Size ();
                keys.push_back (d);
+               count--;
        }
 
-       for (uint i=0; i<node_header.item_count; i++) {
+       for (uint i=0; i<count; i++) {
                /* TODO : El tipo de clave deberia ser usado 
                 * dependiendo de algun dato en el header del
                 * arbol
@@ -315,7 +356,7 @@ void BTree::PrintNode (uint num)
        std::cout << "Free  : " << node_header.free_space << " (" << (header.block_size - sizeof (BTreeNodeHeader)) << ")" << std::endl;
        while (it != node_keys.end ()) {
                std::string s = *(*it);
-               std::cout << s << " ";
+               std::cout << s << " "; 
                it++;
        }
        std::cout << std::endl;
@@ -340,7 +381,7 @@ uchar *BTree::NewBlock (uint &num)
        nh.free_space = header.block_size - sizeof (BTreeNodeHeader);
        nh.item_count = 0;
        WriteNodoHeader (node, &nh);
-       WriteBlock (node, 0);
+       WriteBlock (node, num);
 
        return node;
 }