# HG changeset patch
# User Eris Caffee <discordia@eldalin.com>
# Date 1350608931 18000
# Node ID 66aecb6a0057bd2c9023a66be11103fbf30b21b6
# Parent  0bf94d0ed0b0f79882e76c61e03ff20ddf55ef6e
making progress

diff -r 0bf94d0ed0b0 -r 66aecb6a0057 src/btree_mem.c
--- a/src/btree_mem.c	Thu Oct 18 01:04:17 2012 -0500
+++ b/src/btree_mem.c	Thu Oct 18 20:08:51 2012 -0500
@@ -36,19 +36,34 @@
 struct btree_mem_node * btree_mem_split_child         (struct btree_mem * bt, struct btree_mem_node * x, int i);
 
 void                    btree_mem_node_walk_inorder   (struct btree_mem_node * node, void (*f)(int, void const * const, void *), int depth);
+void                    btree_mem_node_dump           (struct btree_mem_node * node, void (*f)(int, void const * const, void *), int depth);
 
-void *                  btree_mem_node_remove         (struct btree_mem * bt, struct btree_mem_node * node, void * key);
+void *                  btree_mem_node_remove         (struct btree_mem * bt, struct btree_mem_node * node, void * key, 
+						       void ** key_value, void ** data_value);
+
+void                    btree_mem_node_add_key        (struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data);
 void *                  btree_mem_node_remove_key     (struct btree_mem_node * node, int i);
 void *                  btree_mem_node_first_key      (struct btree_mem_node * node);
 void *                  btree_mem_node_last_key       (struct btree_mem_node * node);
-
+void                    btree_mem_node_merge          (struct btree_mem_node * a, struct btree_mem_node * b);
 
 #ifdef DEBUG
 #define DEBUG_BLOCK(x) x
+
+void btree_mem_nonde_print_keys(struct btree_mem_node * node);
+
 #else
 #define DEBUG_BLOCK(x)
 #endif
 
+void printit(int h, void * k, void * d)
+   {
+   for (int i = 0; i < h; i++)
+      printf("\t");
+   printf("%d %s\n", *((int*)k), (char *) d);
+   }
+
+
 ////////////////////////////////////////////////////////////////////////////////
 struct btree_mem *
 btree_mem_new(int min_degree, int (*cmp)(void *, void *))
@@ -307,14 +322,50 @@
    }
 
 ////////////////////////////////////////////////////////////////////////////////
+void
+btree_mem_dump(struct btree_mem * bt, void (*f)(int, void const * const, void *))
+   {
+   btree_mem_node_dump(bt->root, f, 0);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void
+btree_mem_node_dump(struct btree_mem_node * node, void (*f)(int, void const * const, void *), int depth)
+   {
+
+   if (0 == node->nkeys)
+      {
+      if (NULL != node->child[0])
+	 btree_mem_node_dump(node->child[0], f, depth+1);
+      return;
+      }
+
+   for (int i = 0; i < node->nkeys; i++)
+      {
+      if (! node->leaf) 
+	 btree_mem_node_dump(node->child[i], f, depth+1);
+      printf("node: %p nkeys %10d \t", node, node->nkeys);
+      f(depth, node->key[i], node->data[i]);
+      }
+   if (! node->leaf) 
+      btree_mem_node_dump(node->child[node->nkeys], f, depth+1);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
 void *
-btree_mem_remove(struct btree_mem * bt, void * key)
+btree_mem_remove(struct btree_mem * bt, void * key, void ** key_value, void ** data_value)
    {
-   void * data = btree_mem_node_remove(bt, bt->root, key);
+   if ( (NULL == bt) || (NULL == key) || (NULL == key_value) || (NULL == data_value) )
+      return NULL;
+
+   DEBUG_BLOCK( printf("Removing %d\n", *((int *) key)); )
+   void * data = btree_mem_node_remove(bt, bt->root, key, key_value, data_value);
    if (NULL == data)
       return NULL;
+
    if (0 == bt->root->nkeys)
       {
+      DEBUG_BLOCK( printf("Freeing the root node\n"); )
       struct btree_mem_node * n = bt->root;
       bt->root = bt->root->child[0];
       free(n);
@@ -326,9 +377,11 @@
 // Assumption: node has bt->mindeg keys or is the root.
 
 void *
-btree_mem_node_remove(struct btree_mem * bt, struct btree_mem_node * node, void * key)
+btree_mem_node_remove(struct btree_mem * bt, struct btree_mem_node * node, void * key, void ** key_value, void ** data_value)
    {
-#ifdef NOTHING
+
+   DEBUG_BLOCK( btree_mem_node_print_keys(node); )
+
    int i = node->nkeys - 1;
    while ( (i >= 0) && (bt->cmp(key, node->key[i]) < 0) )
       i--;
@@ -336,10 +389,15 @@
    if ( (i >= 0) && (bt->cmp(key, node->key[i]) == 0) )
       {
       // key is in node at key[i]
+      *key_value = node->key[i];
+      *data_value = node->data[i];
+      //      printf("Will return key_value %p (%d)   data_value %p (%s)\n", *key_value, *((int*)(*key_value)), (char*)(*data_value));
       if (node->leaf)
 	 {
-	 // Cormen: case 1
-	 return btree_mem_node_remove_key(node, i);
+	 // case 1
+	 DEBUG_BLOCK( printf("remove: case 1\n"); )
+	 btree_mem_node_remove_key(node, i);
+	 return *data_value;
 	 }
       else
 	 {
@@ -350,62 +408,214 @@
 	 //    (child next that follows  key in node has at least bt->mindeg keys)
 	 if ( (prev->nkeys >= bt->mindeg) || (next->nkeys >= bt->mindeg) )
 	    {
+	    void * kp;
 	    if (prev->nkeys >= bt->mindeg)
 	       {
-	       // Cormen: case 2a
-	       void * kp = btree_mem_node_last_key(prev);
+	       // case 2a
+	       DEBUG_BLOCK( printf("remove: case 2a\n"); )
+	       kp = btree_mem_node_last_key(prev);
+	       //	       printf("remove: kp %d\n", *((int*)kp)); 
+	       node->data[i] = btree_mem_node_remove(bt, prev, kp, key_value, data_value);
 	       }
 	    else
 	       {
-	       // Cormen: case 2b	
-	       void * kp = btree_mem_node_first_key(prev);
+	       // case 2b
+	       DEBUG_BLOCK( printf("remove: case 2b\n"); )
+	       kp = btree_mem_node_first_key(next);
+	       //	       printf("remove: kp %d\n", *((int*)kp)); 
+	       node->data[i] = btree_mem_node_remove(bt, next, kp, key_value, data_value);
 	       }
-	    void * kp_data = btree_mem_node_remove(bt, y, kp);
-	    void * data = node->data[i];
+	    //	    printf("i %d\n", i);
+	    //	       printf("remove: kp %d\n", *((int*)kp)); 
 	    node->key[i] = kp;
-	    node->data[i] = kp_data;
-	    return data;
+	    //	    	    printf("=====\n"); 	    btree_mem_node_dump(node, printit, 0); 	    printf("=====\n");
+	    //		    printf("returning %p\n", *data_value);
+	    return *data_value;
 	    }
 	 else
 	    {
-	    // Cormen: case 2c
+	    // case 2c
+	    DEBUG_BLOCK( printf("remove: case 2c\n"); )
+	    btree_mem_node_add_key(bt, prev, node->key[i], node->data[i]);
+	    btree_mem_node_remove_key(node, i);	
+	    btree_mem_node_merge(prev, next);
+	    return *data_value;
 	    }
 	 }
       }
    else
       {
+      if (node->leaf)
+	 {
+	 DEBUG_BLOCK( printf("remove: key not found\n"); )
+	 return NULL;
+	 }
+
       // key is in child[i+1], if anywhere
+      struct btree_mem_node * c = node->child[i+1];
+
+      DEBUG_BLOCK( printf("remove: key should be in node %p\n", c); )
       if (c->nkeys == bt->mindeg - 1)
 	 {
-	 if ()
+	 struct btree_mem_node * prev = NULL;
+	 if (i >= 0)
+	    prev = node->child[i];
+
+	 struct btree_mem_node * next = NULL;
+	 if (i+2 <= node->nkeys)
+	    next = node->child[i+2];
+
+	 DEBUG_BLOCK( printf("remove: prev %p  next %p\n", prev, next); )
+
+	 if ( (prev) && (prev->nkeys >= bt->mindeg) )
 	    {
-	    // Cormen: case 3a
+	    // case 3a (with prev sibling)
+	    // Move node->key[i] into c->key[0] shifting over existing keys
+	    // Move prev->key[prev->nkeys-1] into node->key[i]
+	    // if (prev->leaf)
+	    //     move prev->child[prev->nkeys] into c->child[0] shifting over existing children
+	    // prev->nkeys--;
+	    
+	    DEBUG_BLOCK( printf("remove: case 3a.1\n"); )
+
+	    btree_mem_node_add_key(bt, c, node->key[i-1], node->data[i-1]);
+
+	    node->key[i-1]  = prev->key[prev->nkeys-1];
+	    node->data[i-1] = prev->data[prev->nkeys-1];
+
+	    if (prev->leaf)
+	       {
+	       for (int j = c->nkeys; j >= 0; j--)
+		  c->child[j+1] = c->child[j];
+	       c->child[0] = prev->child[prev->nkeys];
+	       }
+
+	    prev->nkeys--;
+	    }
+	 else if ( (next) && (next->nkeys >= bt->mindeg) )
+	    {
+	    // case 3a (with next sibling)
+	    // Symmetric with the above
+
+	    DEBUG_BLOCK( printf("remove: case 3a.2\n"); )
+	    btree_mem_node_add_key(bt, c, node->key[i+1], node->data[i+1]);
+
+	    //	    printf("=====\n"); 	    btree_mem_node_dump(node, printit, 0); 	    printf("=====\n");
+
+	    node->key[i+1]  = next->key[0];
+	    node->data[i+1] = next->data[0];
+	    for (int j = 0; j < next->nkeys - 1; j++)
+	       {
+	       next->key[j]  = next->key[j+1];
+	       next->data[j] = next->data[j+1];
+	       }
+
+	    if (next->leaf)
+	       {
+	       c->child[c->nkeys] = next->child[0];
+	       for (int j = 0; j < next->nkeys; j++)
+		  next->child[j] = next->child[j+1];
+	       }
+
+	    next->nkeys--;
+
 	    }
 	 else
 	    {
-	    // Cormen: case 3b
+	    // case 3b
+	    DEBUG_BLOCK( printf("remove: case 3b\n"); )
+		  //	    printf("=====\n"); 	    btree_mem_node_dump(node, printit, 0); 	    printf("=====\n");
+		  //	    printf("node %p  i %d\n", node, i); fflush(stdout);
+		  //	    printf("adding %d to %p\n", *((int*)node->key[i+1]), (next ? next : prev));	    fflush(stdout);
+	    btree_mem_node_add_key(bt, (next ? next : prev), node->key[i+1], node->data[i+1]);
+	    //	    printf("=====\n");	    btree_mem_node_dump(node, printit, 0);	    printf("=====\n");
+
+	    if (next)
+	       {
+	       //	       printf("here\n");
+	       btree_mem_node_merge(c, next);
+	       }
+	    else
+	       {
+	       //	       printf("there\n");
+	       btree_mem_node_merge(prev, c);
+	       }
+
+	    //	    printf("=====\n");	    btree_mem_node_dump(node, printit, 0);	    printf("=====\n");
+
+	    btree_mem_node_remove_key(node, i+1);
+
+	    if (next)
+	       {
+	       for (int j = i+2; j <= node->nkeys+1; j++)
+		  node->child[j] = node->child[j+1];
+	       }
+	    else
+	       {
+	       for (int j = i; j <= node->nkeys+1; j++)
+		  node->child[j] = node->child[j+1];
+	       }
+
+	    //	    printf("=====\n");	    btree_mem_node_dump(node, printit, 0);	    printf("=====\n");
 	    }
 	 }
-      return btree_mem_node_remove(bt, c, key);
+      return btree_mem_node_remove(bt, c, key, key_value, data_value);
       }
-#endif
    }
 
 ////////////////////////////////////////////////////////////////////////////////
+// Assumption: node is not full
+// Assumption: key is not already in node
+void
+btree_mem_node_add_key(struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data)
+   {
+   int i = node->nkeys;
+   while ( (i > 0) && (bt->cmp(key, node->key[i-1]) < 0) )
+      i--;
+
+   for (int j = node->nkeys - 1; j >= i; j--)
+      {
+      node->key[j+1] = node->key[j];
+      node->data[j+1] = node->data[j];
+      }
+
+   node->key[i] = key;
+   node->data[i] = data;
+   node->nkeys++;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+// Assumption: node has at least mindeg keys.
+// Does not remove any children.
 void *
 btree_mem_node_remove_key(struct btree_mem_node * node, int i)
    {
    void * data = node->key[i];
-   for (int j = node->nkeys - 1; j > i; j--)
+   for (int j = i; j < node->nkeys; j++)
       {
-      node->key[j-1]  = node->key[j];
-      node->data[j-1] = node->data[j];
+      node->key[j]  = node->key[j+1];
+      node->data[j] = node->data[j+1];
       }
    node->nkeys--;
    return data;
    }
 
 ////////////////////////////////////////////////////////////////////////////////
+// Return the lowest valued key of the subtree rooted at node
+void *
+btree_mem_node_first_key(struct btree_mem_node * node)
+   {
+   if (0 == node->nkeys)
+      return NULL;
+
+   if (node->leaf)
+      return node->key[0];
+
+   return btree_mem_node_last_key(node->child[0]);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+// Return the highest valued key of the subtree rooted at node
 void *
 btree_mem_node_last_key(struct btree_mem_node * node)
    {
@@ -418,15 +628,34 @@
    return btree_mem_node_last_key(node->child[node->nkeys]);
    }
 
-////////////////////////////////////////////////////////////////////////////////
-void *
-btree_mem_node_first_key(struct btree_mem_node * node)
+/////////////////////////////////////////////////////////////////////////////////
+// move all keys/data from node b into node a
+// Assumption: all keys in b come after the keys in a
+void
+btree_mem_node_merge(struct btree_mem_node * a, struct btree_mem_node * b)
    {
-   if (0 == node->nkeys)
-      return NULL;
 
-   if (node->leaf)
-      return node->key[0];
+   DEBUG_BLOCK( printf("merging %p with %p\n", a, b); )
+   int i = a->nkeys;
+   int j = 0;
+   for (;  j < b->nkeys; i++, j++)
+      {
+      a->key[i] = b->key[j];
+      a->data[i] = b->data[j];
+      }
+   a->nkeys += b->nkeys;
+   b->nkeys = 0;
+   }
 
-   return btree_mem_node_last_key(node->child[0]);
+/////////////////////////////////////////////////////////////////////////////////
+#ifdef DEBUG
+void
+btree_mem_node_print_keys(struct btree_mem_node * node)
+   {
+   printf("node: %p nkeys %10d keys: ", node, node->nkeys);
+   for (int i = 0; i < node->nkeys; i++)
+      printf("%d ", *((int *) node->key[i]));
+   printf("\n");
    }
+#endif
+
diff -r 0bf94d0ed0b0 -r 66aecb6a0057 src/btree_mem.h
--- a/src/btree_mem.h	Thu Oct 18 01:04:17 2012 -0500
+++ b/src/btree_mem.h	Thu Oct 18 20:08:51 2012 -0500
@@ -2,7 +2,7 @@
 #define BTREE_MEM_H_
 
 
-// #define DEBUG
+#define DEBUG
 
 
 struct btree_mem_node;
@@ -16,7 +16,7 @@
 
 void *             btree_mem_insert       (struct btree_mem * bt, void * key, void * data);
 void *             btree_mem_find         (struct btree_mem * bt, void * key);
-void *             btree_mem_remove       (struct btree_mem * bt, void * key);
+void *             btree_mem_remove       (struct btree_mem * bt, void * key, void ** key_value, void ** data_value);
 
 // Walk the tree in key order, starting with the lowest, and apply the function f to each one.  The argumemnts to f are
 // int depth in the tree, the pointer to the key, and the pointer to the data. Note that the key cannot be modified,
@@ -26,4 +26,9 @@
 // remove and insert.
 void               btree_mem_walk_inorder (struct btree_mem * bt, void (*f)(int, void const * const, void * const));
 
+#ifdef DEBUG
+// btree_mem_dump takes a pointer to a function that prints a represenation of the keya nd data to the stdout.
+void               btree_mem_dump         (struct btree_mem * bt, void (*f)(int, void const * const, void * const));
 #endif
+
+#endif
diff -r 0bf94d0ed0b0 -r 66aecb6a0057 src/btree_mem_test.c
--- a/src/btree_mem_test.c	Thu Oct 18 01:04:17 2012 -0500
+++ b/src/btree_mem_test.c	Thu Oct 18 20:08:51 2012 -0500
@@ -6,7 +6,7 @@
 #include "btree_mem.h"
 
 
-#define MIN_DEGREE 3
+#define MIN_DEGREE 2
 #define MAX_LINE 1024
 
 #ifdef DEBUG
@@ -56,7 +56,7 @@
 print_tree(struct btree_mem * bt)
    {
    printf("==================================\n");
-   btree_mem_walk_inorder(bt, print_data);
+   btree_mem_dump(bt, print_data);
    printf("==================================\n");
    }
 
@@ -130,5 +130,28 @@
    //   wackify_tree(bt);
    print_tree(bt);
 
+   int * k;
+   char * d;
+   int key = 5;
+   printf("removing %d\n", key);
+   if (NULL == btree_mem_remove(bt, &key, (void *) &k, (void *) &d))
+      {
+      printf("not found!\n");
+      }
+   else
+      {
+      if (NULL == k)
+	 printf("k is NULL\n");
+      else
+	 free(k);
+
+      if (NULL == d)
+	 printf("d is NULL\n");
+      else
+	 free(d);
+      }
+   print_tree(bt);
+
+
    exit(EXIT_SUCCESS);
    }