From 3a7aa16a342ce2cca383b3e118d4f41ef1c698a4 Mon Sep 17 00:00:00 2001
From: Ricardo Markiewicz <rmarkie@fi.uba.ar>
Date: Sun, 23 Oct 2005 17:26:45 +0000
Subject: [PATCH] Borrado de un nodo.

---
 src/btree.cpp | 97 +++++++++++++++++++++++++++++++++++++++++++++++++--
 src/btree.h   |  2 +-
 2 files changed, 95 insertions(+), 4 deletions(-)

diff --git a/src/btree.cpp b/src/btree.cpp
index 9f69414..7a3daaf 100644
--- a/src/btree.cpp
+++ b/src/btree.cpp
@@ -419,6 +419,17 @@ void BTree::DelKeyR (BTreeData *k, uint node_num, uint padre)
 			/* La encontre!, retorno */
 			if (node_header.level == 0) {
 				DelKeyFromLeaf (k->getClave (), node_num, padre);
+			} else {
+				uint left, right;
+				if (it == posterior) {
+					left = lchild->getChild ();
+					right = (*it)->getChild ();
+				} else {
+					left = (*ultima)->getChild ();
+					right = (*it)->getChild ();
+				}
+				std::cout << "Eliminar de Nodo con hijos : " << left << " y " << right << std::endl;
+				DelKeyFromNode (k->getClave (), node_num, padre, left, right);
 			}
 			return;
 		}
@@ -478,7 +489,7 @@ void BTree::DelKeyFromLeaf (Clave *k, uint node_num, uint padre)
 	WriteBlock (node, node_num);
 
 	/* Veo si se cumple la condición de minimalidad */
-	if ((node_header.free_space <= (header.block_size/2)) && (node_num != 0)) {
+	if ((node_header.free_space <= ((header.block_size-sizeof(BTreeNodeHeader))/2)) && (node_num != 0)) {
 		/* Oops! Debo pedir prestada clave */
 		uint hi, hd;
 		Clave *pedida;
@@ -628,7 +639,7 @@ Clave *BTree::GetKey (uint node_num, char maxmin)
 
 	Clave *k;
 	uint free = node_header.free_space + (*it)->Size ();
-	if (free > (header.block_size/2)) {
+	if (free > ((header.block_size - sizeof (BTreeNodeHeader))/2)) {
 		WriteKeys (node, node_header, node_keys);
 		WriteNodoHeader (node, &node_header);
 		WriteBlock (node, node_num);
@@ -751,8 +762,88 @@ Clave *BTree::ReplaceKeyInFather (uint node_num, uint padre, Clave *k)
 	return ret;
 }
 
-void BTree::DelKeyFromOther (const Clave &k, BTreeFindResult *r)
+void BTree::DelKeyFromNode (Clave *k, uint node_num, uint padre, uint left, uint right)
 {
+	uint padre_hijo;
+	uchar *node;
+	BTreeNodeHeader node_header;
+	std::list<BTreeData *> node_keys;
+
+	node = ReadBlock (padre);
+	ReadNodoHeader (node, &node_header);
+	node_keys = ReadKeys (node, node_header);
+
+	if (right != 0) {
+		std::cout << "Busco para la derecha y luego todo a la izquierda\n";
+		uchar *node_r;
+		BTreeNodeHeader node_hr;
+		std::list<BTreeData *> node_keyr;
+
+		/* Busco la clave inmediatamente superior en el arbol */
+		padre_hijo = node_num;
+		do {
+			node_r = ReadBlock (right);
+			ReadNodoHeader (node_r, &node_hr);
+			if (node_hr.level != 0) {
+				BTreeData *data_r;
+				node_keyr = ReadKeys (node_r, node_hr);
+				data_r = *(node_keyr.begin ());
+				padre_hijo = right;
+				right = data_r->getChild ();
+
+				DeleteKeys (node_keyr);
+				delete [] node_r;
+			}
+		} while (node_hr.level != 0);
+
+		std::cout << "Voy a reemplazar en el nodo " << right << std::endl;
+
+		/* Reemplazo la clave a borrar por la de la hoja */
+		node_keyr = ReadKeys (node_r, node_hr);
+		BTreeData *reemplazar = *(node_keyr.begin ());
+
+		std::string ss = *reemplazar;
+		std::cout << "Voy a reemplazar por : " << ss << std::endl;
+
+		BTreeData *data = new BTreeLeafData (k->Clone());
+
+		std::list<BTreeData *>::iterator it = node_keys.begin ();
+		while (it != node_keys.end ()) {
+			if ((*data) == (*(*it))) {
+				break;
+			}
+			it++;
+		}
+		(*it)->setClave (reemplazar->getClave ());
+		reemplazar->setClave (k->Clone ());
+
+		std::cout << "Tengo todo reemplazado ...\n";
+
+		/* Grabo los nodos */
+		WriteKeys (node, node_header, node_keys);
+		WriteNodoHeader (node, &node_header);
+		WriteBlock (node, padre);
+		DeleteKeys (node_keys);
+		delete [] node;
+
+		WriteKeys (node_r, node_hr, node_keyr);
+		WriteNodoHeader (node_r, &node_hr);
+		WriteBlock (node_r, right);
+		DeleteKeys (node_keyr);
+		delete [] node_r;
+
+		std::cout << "Grabe todo en disco ...\n";
+
+		/* Ahora debo eliminar la clave que puse en el nodo hoja */
+		std::cout << "Borro la clave desde la hoja!\n";
+
+		DelKeyFromLeaf (k, right, padre_hijo);
+
+		std::cout << "Listo, Listo!\n";
+	} else if (left != 0) {
+	} else {
+		std::cout << "PANIC : No tengo hijos para reemplazar!!!!\n";
+	}
 }
 
 void BTree::ReadNodoHeader (uchar *node, BTreeNodeHeader *header)
diff --git a/src/btree.h b/src/btree.h
index ec81903..f7613f4 100644
--- a/src/btree.h
+++ b/src/btree.h
@@ -149,7 +149,7 @@ class BTree {
 		/* Funciones de Baja */
 		void DelKeyR (BTreeData *k, uint node, uint padre);
 		void DelKeyFromLeaf (Clave *k, uint node_num, uint padre);
-		void DelKeyFromOther (const Clave &k, BTreeFindResult *r);
+		void DelKeyFromNode (Clave *k, uint node_num, uint padre, uint left, uint right);
 		void FindBrothers (uint node_num, uint padre, uint &left, uint &right);
 		Clave *ReplaceKeyInFather (uint node_num, uint padre, Clave *k);
 		Clave *GetKey (uint node_num, char maxmin);
-- 
2.43.0