From: Ricardo Markiewicz Date: Tue, 1 Nov 2005 04:00:25 +0000 (+0000) Subject: Test del orto :S X-Git-Tag: 1_0-pre2~14 X-Git-Url: https://git.llucax.com/z.facultad/75.52/treemulator.git/commitdiff_plain/de3b0cb3cb22673c55c267a6cfd0428df0a084f8 Test del orto :S --- diff --git a/src/btree.h b/src/btree.h index 2d9ca6a..5d05ae4 100644 --- a/src/btree.h +++ b/src/btree.h @@ -82,9 +82,7 @@ * * Para saber si hay que romper en dos un nodo, se debe ver si la clave * a agregar entra en el espacio libre del nodo encontrado como "lugar - * de inserción". Ahora, un problema a resolver es cuando se debe - * juntar nodos, ya que el árbol B este es particular (Preguntar a - * Cerveto?). + * de inserción". * * \section page_model_op Operaciones Básicas * @@ -165,6 +163,23 @@ * al algoritmo de borrado en una hoja. De acá en más todo sigue como fue descripto * en el borrado en una hoja. * + * \subsubsection page_model_problema El problema de la Clave Mayor. + * + * Este es un problema que hemos encontrado en la actual implementación de árbol + * B con claves variables. + * + * Este puede ocurrir únicamente cuando sucede una junta de nodos. Lo que ocurre + * se ejemplifica a continuación. Supongamos por un momento que tenemos dos + * nodos a unir cuya suma de tamaños ocupados es N. Ahora supongamos que la clave + * del padre, que debe ser unida con los nodos es de tamaño M. + * + * Si por algun caso particular de las claves N+M es mayor al tamaño del bloque, + * la junta no podrá ser realizada. + * + * Hemos detectado este problema seguido en árboles con bloques de 128 o 256, y muy + * rara vez en nodos de 512 o superiores, por lo que no hemos tomado medida alguna + * más que documentar su existencia. + * * \subsection page_model_find Búsqueda de una Clave. * * Esta operación se realiza haciendo una búsqueda en profundidad en el árbol. diff --git a/viewer/main.cpp b/viewer/main.cpp index b4f3c63..89b66bc 100644 --- a/viewer/main.cpp +++ b/viewer/main.cpp @@ -118,7 +118,8 @@ void nuevo_arbol () double paltas = bajas / (double)altas; int type = d.getKeyType (); - tree = Glib::RefPtr(new ViewBTree (real_canvas->root(), "test.idx", d.getBlockSize (), type)); + int atype = d.getTreeType (); + tree = Glib::RefPtr(new ViewBTree (real_canvas->root(), "test.idx", d.getBlockSize (), atype, type)); tree->signal_selected ().connect ( sigc::mem_fun (*real_frame, &ViewProperties::ShowItem) ); if (type == BTree::KEY_FIXED) { std::list lst; diff --git a/viewer/new_tree_dialog.cpp b/viewer/new_tree_dialog.cpp index edb1f5a..a2a9552 100644 --- a/viewer/new_tree_dialog.cpp +++ b/viewer/new_tree_dialog.cpp @@ -3,22 +3,26 @@ NewTreeDialog::NewTreeDialog(): Gtk::Dialog ("Nuevo Arbol", true, true), - fixed_key ("Clave Fija"), variable_key ("Clave Variable") + fixed_key ("Clave Fija"), variable_key ("Clave Variable"), + tree_ident ("Arbol de Indentificación"), tree_class ("Arbol de Clasificacion") { - table.attach (fixed_key, 0, 1, 0, 1); - table.attach (variable_key, 1, 2, 0, 1); + table.attach (tree_ident, 0, 1, 0, 1); + table.attach (tree_class, 1, 2, 0, 1); + + table.attach (fixed_key, 0, 1, 1, 2); + table.attach (variable_key, 1, 2, 1, 2); label_block.set_label ("Tamaño de Bloque : "); - table.attach (label_block, 0, 1, 1, 2, Gtk::FILL|Gtk::SHRINK, Gtk::SHRINK, 8, 8); - table.attach (entry_block, 1, 2, 1, 2, Gtk::FILL|Gtk::EXPAND, Gtk::SHRINK, 8, 8); + table.attach (label_block, 0, 1, 2, 3, Gtk::FILL|Gtk::SHRINK, Gtk::SHRINK, 8, 8); + table.attach (entry_block, 1, 2, 2, 3, Gtk::FILL|Gtk::EXPAND, Gtk::SHRINK, 8, 8); label_count.set_label ("Cantidad a insertar : "); - table.attach (label_count, 0, 1, 2, 3, Gtk::FILL|Gtk::SHRINK, Gtk::SHRINK, 8, 8); - table.attach (entry_count, 1, 2, 2, 3, Gtk::FILL|Gtk::EXPAND, Gtk::SHRINK, 8, 8); + table.attach (label_count, 0, 1, 3, 4, Gtk::FILL|Gtk::SHRINK, Gtk::SHRINK, 8, 8); + table.attach (entry_count, 1, 2, 3, 4, Gtk::FILL|Gtk::EXPAND, Gtk::SHRINK, 8, 8); label_dels.set_label ("Cantidad a eliminar : "); - table.attach (label_dels, 0, 1, 3, 4, Gtk::FILL|Gtk::SHRINK, Gtk::SHRINK, 8, 8); - table.attach (entry_dels, 1, 2, 3, 4, Gtk::FILL|Gtk::EXPAND, Gtk::SHRINK, 8, 8); + table.attach (label_dels, 0, 1, 4, 5, Gtk::FILL|Gtk::SHRINK, Gtk::SHRINK, 8, 8); + table.attach (entry_dels, 1, 2, 4, 5, Gtk::FILL|Gtk::EXPAND, Gtk::SHRINK, 8, 8); get_vbox ()->add (table); @@ -28,6 +32,10 @@ NewTreeDialog::NewTreeDialog(): Gtk::Dialog ("Nuevo Arbol", true, true), Gtk::RadioButton::Group group = fixed_key.get_group(); fixed_key.set_group (group); variable_key.set_group (group); + + Gtk::RadioButton::Group group1 = tree_ident.get_group(); + tree_ident.set_group (group); + tree_class.set_group (group); show_all (); } @@ -55,3 +63,11 @@ int NewTreeDialog::getKeyType () return BTree::KEY_VARIABLE; } +int NewTreeDialog::getTreeType () +{ + if (tree_ident.get_active ()) + return BTree::TYPE_IDENTIFICACION; + + return BTree::TYPE_CLASIFICACION; +} + diff --git a/viewer/new_tree_dialog.h b/viewer/new_tree_dialog.h index 1edb27c..63a5e56 100644 --- a/viewer/new_tree_dialog.h +++ b/viewer/new_tree_dialog.h @@ -13,16 +13,20 @@ class NewTreeDialog : public Gtk::Dialog { uint getDels (); uint getBlockSize (); int getKeyType (); + int getTreeType (); private: Gtk::Table table; Gtk::Label label_count; Gtk::Label label_block; Gtk::Label label_dels; + Gtk::Label label_tt; Gtk::Entry entry_count; Gtk::Entry entry_dels; Gtk::Entry entry_block; Gtk::RadioButton fixed_key; Gtk::RadioButton variable_key; + Gtk::RadioButton tree_ident; + Gtk::RadioButton tree_class; }; #endif diff --git a/viewer/view_btree.cpp b/viewer/view_btree.cpp index 353fd2b..6a1fd16 100644 --- a/viewer/view_btree.cpp +++ b/viewer/view_btree.cpp @@ -7,8 +7,8 @@ double ViewBTree::byte_to_pixels = 0; double ViewBTree::node_width = 0; double ViewBTree::node_height = 0; -ViewBTree::ViewBTree (Canvas::Group *parent, std::string filename, uint block_size, int type):Canvas::Group (*parent, 0, 0), - BTree (filename, block_size, BTree::TYPE_IDENTIFICACION, type) +ViewBTree::ViewBTree (Canvas::Group *parent, std::string filename, uint block_size, int tree_type, int type):Canvas::Group (*parent, 0, 0), + BTree (filename, block_size, tree_type, type) { /* Cada bytes lo hago de 5 units de ancho */ node_width = 4 * block_size; diff --git a/viewer/view_btree.h b/viewer/view_btree.h index bb955bd..894bf5d 100644 --- a/viewer/view_btree.h +++ b/viewer/view_btree.h @@ -14,7 +14,7 @@ class ViewNode; class ViewBTree : public Canvas::Group, public BTree { public: - ViewBTree (Canvas::Group *parent, std::string filename, uint block_size, int type); + ViewBTree (Canvas::Group *parent, std::string filename, uint block_size, int tree_type, int type); void Clear (); void HighliteKey (Clave &k); diff --git a/viewer/view_btree_data.cpp b/viewer/view_btree_data.cpp index e1df3c2..2d4a753 100644 --- a/viewer/view_btree_data.cpp +++ b/viewer/view_btree_data.cpp @@ -12,8 +12,6 @@ ViewBTreeData::ViewBTreeData (BTreeData *data, Canvas::Group *parent, double x1, void ViewBTreeData::init (Canvas::Group *parent) { - double w = property_x2() - property_x1(); - double h = property_y2() - property_y1(); } bool ViewBTreeData::on_event (GdkEvent *p1)