# HG changeset patch
# User Eris Caffee <discordia@eldalin.com>
# Date 1348683069 18000
# Node ID 9f1e34c4a8105c6446ab38e43eaf1261d2662488
# Parent  e117c4d93602d3303b9a5999a55c2f05b2caf100# Parent  5dfdc70e30254488121128277648b21c0bcd9868
Merge list and bst changesets

diff -r e117c4d93602 -r 9f1e34c4a810 CMakeLists.txt
--- a/CMakeLists.txt	Fri Sep 21 18:42:49 2012 -0500
+++ b/CMakeLists.txt	Wed Sep 26 13:11:09 2012 -0500
@@ -72,3 +72,7 @@
   ${list_SRCS}
   )
 
+set (bst_SRCS src/bst.h src/bst.c src/bst_test.c)
+add_executable (bst_test
+  ${bst_SRCS}
+  )
diff -r e117c4d93602 -r 9f1e34c4a810 src/bst.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/bst.c	Wed Sep 26 13:11:09 2012 -0500
@@ -0,0 +1,190 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "bst.h"
+
+// Private functions.
+void bst_node_walk_inorder(struct bst_node * node, void (*op)(void * data));
+void * bst_node_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);
+
+////////////////////////////////////////////////////////////////////////////////
+struct bst *
+bst_new(bool (*le)(void * a, void * b),
+	bool (*eq)(void * a, void * b))
+   {
+   if ( (NULL == le) || (NULL == eq) )
+      return NULL;
+
+   struct bst * bst = malloc(sizeof(struct bst));
+   if (NULL == bst)
+      return NULL;
+
+   bst->root = NULL;
+   bst->size = 0;
+   bst->le = le;
+   bst->eq = eq;
+   return bst;
+   }
+
+
+////////////////////////////////////////////////////////////////////////////////
+void
+bst_delete(struct bst * bst)
+   {
+   if (NULL == bst) return;
+   if (0 < bst->size)
+      {
+      // Walk the tree and delete the nodes.
+      // This will cause memory leaks, so hopefully the user has already
+      // emptied the tree.
+      }
+   free(bst);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void *
+bst_insert(struct bst * bst, void * data)
+   {
+   if ( (NULL == bst) || (NULL == data) )
+      return NULL;
+
+   struct bst_node * new = malloc(sizeof(struct bst_node));
+   if (NULL == new)
+      return NULL;
+   new->left = new->right = new->parent = NULL;
+   new->data = data;
+
+   if (NULL == bst->root)
+      {
+      bst->root = new;
+      return new->data;
+      }
+
+   struct bst_node * p = NULL;
+   struct bst_node * c = bst->root;
+
+   while (NULL != c)
+      {
+      p = c;
+      if (bst->le(new->data, c->data))
+	 c = c->left;
+      else
+	 c = c->right;
+      }
+   new->parent = p;
+   if (bst->le(new->data, p->data))
+      p->left = new;
+   else
+      p->right = new;
+
+   return new->data;
+   }
+
+
+////////////////////////////////////////////////////////////////////////////////
+void bst_walk_inorder(struct bst * bst, void (*op)(void * data))
+   {
+   if ( (NULL == bst) || (NULL == bst->root) || (NULL == op) )
+      return;
+
+   bst_node_walk_inorder(bst->root, op);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void bst_node_walk_inorder(struct bst_node * node, void (*op)(void * data))
+   {
+   if (NULL != node)
+      {
+      bst_node_walk_inorder(node->left, op);
+      op(node->data);
+      bst_node_walk_inorder(node->right, op);
+      }
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void * bst_search(struct bst * bst, void * data)
+   {
+   if ( (NULL == bst) || (NULL == bst->root) || (NULL == data) )
+      return NULL;
+
+   return bst_node_search(bst, bst->root, data);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+// Recursive
+void * 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->data;
+
+   if (bst->le(data, node->data))
+      return bst_node_search(bst, node->left, data);
+   else
+      return bst_node_search(bst, node->right, data);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+// Iterative
+void * bst_search_iterative(struct bst * bst, void * data)
+   {
+   if ( (NULL == bst) || (NULL == bst->root) || (NULL == data) )
+      return NULL;
+
+   struct bst_node * node = bst->root;
+   while (1)
+      {
+      if (NULL == node)
+	 return NULL;
+      
+      if (bst->eq(data, node->data))
+	 return node->data;
+      
+      if (bst->le(data, node->data))
+	 node = node->left;
+      else
+	 node = node->right;
+      }
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void * bst_minimum(struct bst * bst)
+   {
+   if (NULL == bst)
+      return NULL;
+
+   return bst_node_minimum(bst->root);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void * bst_node_minimum(struct bst_node * node)
+   {
+   while ( (NULL != node) && (NULL != node->left) )
+      node = node->left;
+   if (NULL == node)
+      return NULL;
+   return node->data;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void * bst_maximum(struct bst * bst)
+   {
+   if (NULL == bst)
+      return NULL;
+
+   return bst_node_maximum(bst->root);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void * bst_node_maximum(struct bst_node * node)
+   {
+   while ( (NULL != node) && (NULL != node->right) )
+      node = node->right;
+   if (NULL == node)
+      return NULL;
+   return node->data;
+   }
diff -r e117c4d93602 -r 9f1e34c4a810 src/bst.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/bst.h	Wed Sep 26 13:11:09 2012 -0500
@@ -0,0 +1,36 @@
+#ifndef BST_H_
+#define BST_H_
+
+#include <stddef.h>
+#include <stdbool.h>
+
+struct bst_node
+   {
+   struct bst_node * parent;
+   struct bst_node * left;
+   struct bst_node * right;
+   void * data;
+   };
+
+struct bst
+   {
+   struct bst_node * root;
+   size_t size;
+   bool (*le)(void * a, void * b);
+   bool (*eq)(void * a, void * b);
+   };
+
+struct bst * bst_new(bool (*le)(void * a, void * b), bool (*eq)(void * a, void * b));
+void bst_delete(struct bst * bst);
+
+void * bst_insert(struct bst * bst, void * data);
+
+void * bst_search(struct bst * bst, void * data);
+void * bst_search_iterative(struct bst * bst, void * data);
+
+void * bst_minimum(struct bst * bst);
+void * bst_maximum(struct bst * bst);
+
+void bst_walk_inorder(struct bst * bst, void (*op)(void * data));
+
+#endif
diff -r e117c4d93602 -r 9f1e34c4a810 src/bst_test.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/bst_test.c	Wed Sep 26 13:11:09 2012 -0500
@@ -0,0 +1,91 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <time.h>
+
+#include "bst.h"
+
+#define MAX_NUMS 10
+
+bool le(void *a, void * b)
+   {
+   return *((int *) a) <= *((int *) b);
+   }
+
+bool eq(void *a, void * b)
+   {
+   return *((int *) a) == *((int *) b);
+   }
+
+void print(void * d)
+   {
+   printf("%d\n", *((int *) d) );
+   }
+
+int main(int argc, char ** argv)
+   {
+   struct bst * bst = bst_new(le, eq);
+   if (NULL == bst)
+      {
+      perror("bst_new");
+      exit(EXIT_FAILURE);
+      }
+
+   //srand(time());
+   int * ip;
+   for (int i = 0 ; i < MAX_NUMS ; ++i)
+      {
+      ip = malloc(sizeof(int));
+      if (NULL == ip)
+	 {
+	 perror("malloc");
+	 exit(EXIT_FAILURE);
+	 }
+
+      *ip = rand();
+
+      if (NULL == bst_insert(bst, ip))
+	 {
+	 perror("bst_insert");
+	 exit(EXIT_FAILURE);
+	 }
+      }
+
+   bst_walk_inorder(bst, print);
+
+   int i = 1;
+   int * p = (int *) bst_search(bst, &i);
+   if (NULL == p)
+      printf("%d NOT FOUND\n", i);
+   else
+      printf("%d FOUND\n", i);
+
+   i = *ip;
+   p = (int *) bst_search(bst, &i);
+   if (NULL == p)
+      printf("%d NOT FOUND\n", i);
+   else
+      printf("%d FOUND\n", i);
+
+   i = *ip;
+   p = (int *) bst_search_iterative(bst, &i);
+   if (NULL == p)
+      printf("%d NOT FOUND\n", i);
+   else
+      printf("%d FOUND\n", i);
+
+
+   int * min = bst_minimum(bst);
+   if (NULL == min)
+      printf("tree has no minimum.  empty?\n");
+   else
+      printf("%d MINIMUM\n", *min);
+
+   int * max = bst_maximum(bst);
+   if (NULL == max)
+      printf("tree has no maximum.  empty?\n");
+   else
+      printf("%d MAXIMUM\n", *max);
+
+   exit(EXIT_SUCCESS);
+   }