# HG changeset patch
# User Eris Caffee <discordia@eldalin.com>
# Date 1348761461 18000
# Node ID 6605a342e8f885438d9d725fbadcbb0c7d6819d1
# Parent  b38243d51aea04e535e85da121a22014f3a27ba1
bst working, but not elegant

diff -r b38243d51aea -r 6605a342e8f8 src/bst.c
--- a/src/bst.c	Wed Sep 26 18:59:22 2012 -0500
+++ b/src/bst.c	Thu Sep 27 10:57:41 2012 -0500
@@ -10,11 +10,15 @@
 
 void bst_node_walk_postorder(struct bst_node * node, void (*op)(struct bst_node * n));
 
-void * bst_node_search(struct bst * bst, struct bst_node * node, void * data);
+void * bst_data_search(struct bst * bst, struct bst_node * node, void * data);
 void * bst_node_minimum(struct bst_node * node);
 void * bst_node_maximum(struct bst_node * node);
 void bst_node_free(struct bst_node * node);
 
+struct bst_node * bst_node_search(struct bst * bst, struct bst_node * node, void * data);
+
+struct bst_node * bst_transplant(struct bst * bst, struct bst_node * a, struct bst_node * b);
+
 ////////////////////////////////////////////////////////////////////////////////
 struct bst *
 bst_new(bool (*le)(void * a, void * b),
@@ -175,12 +179,12 @@
    if ( (NULL == bst) || (NULL == bst->root) || (NULL == data) )
       return NULL;
 
-   return bst_node_search(bst, bst->root, data);
+   return bst_data_search(bst, bst->root, data);
    }
 
 ////////////////////////////////////////////////////////////////////////////////
 // Recursive
-void * bst_node_search(struct bst * bst, struct bst_node * node, void * data)
+void * bst_data_search(struct bst * bst, struct bst_node * node, void * data)
    {
    if (NULL == node)
       return NULL;
@@ -189,9 +193,9 @@
       return node->data;
 
    if (bst->le(data, node->data))
-      return bst_node_search(bst, node->left, data);
+      return bst_data_search(bst, node->left, data);
    else
-      return bst_node_search(bst, node->right, data);
+      return bst_data_search(bst, node->right, data);
    }
 
 ////////////////////////////////////////////////////////////////////////////////
@@ -360,3 +364,89 @@
    return it->curr->data;
    }
 
+////////////////////////////////////////////////////////////////////////////////
+void *
+bst_find(struct bst_iterator * it, void * data)
+   {
+   if ( (NULL == it) || (NULL == it->bst) || (NULL == it->bst->root) || (NULL == data) )
+      return NULL;
+
+   return bst_node_search(it->bst, it->bst->root, data);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+// Recursive
+struct bst_node *
+bst_node_search(struct bst * bst, struct bst_node * node, void * data)
+   {
+   if (NULL == node)
+      return NULL;
+
+   if (bst->eq(data, node->data))
+      return node;
+
+   if (bst->le(data, node->data))
+      return bst_node_search(bst, node->left, data);
+   else
+      return bst_node_search(bst, node->right, data);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+struct bst_node *
+bst_transplant(struct bst * bst, struct bst_node * a, struct bst_node * b)
+   {
+   if ( (NULL == a) || (NULL == b) )
+      return NULL;
+
+   if (NULL == a->parent)
+      bst->root = b;
+   else if (a == a->parent->left)
+      a->parent->left = b;
+   else
+      a->parent->right = b;
+
+   if (NULL != b)
+      b->parent = a->parent;
+
+   return a;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void *
+bst_remove(struct bst_iterator * it)
+   {
+   if ( (NULL == it) || (NULL == it->curr) )
+      return NULL;
+
+   struct bst_node * y;
+
+   if (NULL == it->curr->left)
+      {
+      bst_transplant(it->bst, it->curr, it->curr->right);
+      y = it->curr->right;
+      }
+   else if (NULL == it->curr->right)
+      {
+      bst_transplant(it->bst, it->curr, it->curr->left);
+      y = it->curr->left;
+      }
+   else
+      {
+      y = bst_node_minimum(it->curr->right);
+      if (NULL != y->parent)
+	 {
+	 bst_transplant(it->bst, y, y->right);
+	 y->right = it->curr->right;
+	 y->right->parent = y;
+	 }
+      bst_transplant(it->bst, it->curr, y);
+      y->left = it->curr->left;
+      y->left->parent = y;
+      }
+
+   void * data = it->curr->data;
+   free(it->curr);
+   it->curr = y;
+   return data;
+   }
+
diff -r b38243d51aea -r 6605a342e8f8 src/bst.h
--- a/src/bst.h	Wed Sep 26 18:59:22 2012 -0500
+++ b/src/bst.h	Thu Sep 27 10:57:41 2012 -0500
@@ -48,4 +48,7 @@
 struct bst_iterator * bst_prev(struct bst_iterator * it);
 void * bst_value(struct bst_iterator * it);
 
+void * bst_find(struct bst_iterator * it, void * data);
+void * bst_remove(struct bst_iterator * it);
+
 #endif
diff -r b38243d51aea -r 6605a342e8f8 src/bst_test.c
--- a/src/bst_test.c	Wed Sep 26 18:59:22 2012 -0500
+++ b/src/bst_test.c	Thu Sep 27 10:57:41 2012 -0500
@@ -126,6 +126,31 @@
    free(it);
 
 
+   ////////////////////////////////////////
+   printf("========================================\nRemoving third element\n");
+   it = bst_begin(bst);
+   if (NULL == it)
+      {
+      perror("bst_begin");
+      exit(EXIT_FAILURE);
+      }
+   bst_next(it);
+   bst_next(it);
+   void * d = bst_remove(it);
+   if (NULL == d)
+      printf("Unable to remove element!\n");
+   else
+      free(d);
+   free(it);
+   it = bst_begin(bst);
+   do
+      printf("%d\n", *((int *) bst_value(it)));
+   while (bst_next(it));
+   free(it);
+
+
+
+   ////////////////////////////////////////
    bst_walk_inorder(bst, free_data);
    bst_delete(bst);