# HG changeset patch
# User Eris Caffee <discordia@eldalin.com>
# Date 1348703962 18000
# Node ID b38243d51aea04e535e85da121a22014f3a27ba1
# Parent  9f1e34c4a8105c6446ab38e43eaf1261d2662488
A bit more on the bst

diff -r 9f1e34c4a810 -r b38243d51aea src/bst.c
--- a/src/bst.c	Wed Sep 26 13:11:09 2012 -0500
+++ b/src/bst.c	Wed Sep 26 18:59:22 2012 -0500
@@ -4,10 +4,16 @@
 #include "bst.h"
 
 // Private functions.
-void bst_node_walk_inorder(struct bst_node * node, void (*op)(void * data));
+void bst_data_walk_inorder(struct bst_node * node, void (*op)(void * data));
+void bst_data_walk_preorder(struct bst_node * node, void (*op)(void * data));
+void bst_data_walk_postorder(struct bst_node * node, void (*op)(void * data));
+
+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_node_minimum(struct bst_node * node);
 void * bst_node_maximum(struct bst_node * node);
+void bst_node_free(struct bst_node * node);
 
 ////////////////////////////////////////////////////////////////////////////////
 struct bst *
@@ -37,13 +43,21 @@
    if (0 < bst->size)
       {
       // Walk the tree and delete the nodes.
-      // This will cause memory leaks, so hopefully the user has already
+      // This may cause memory leaks, so hopefully the user has already
       // emptied the tree.
+      bst_node_walk_postorder(bst->root, bst_node_free);
       }
    free(bst);
    }
 
 ////////////////////////////////////////////////////////////////////////////////
+void
+bst_node_free(struct bst_node * node)
+   {
+   free(node);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
 void *
 bst_insert(struct bst * bst, void * data)
    {
@@ -79,6 +93,7 @@
    else
       p->right = new;
 
+   bst->size++;
    return new->data;
    }
 
@@ -89,17 +104,68 @@
    if ( (NULL == bst) || (NULL == bst->root) || (NULL == op) )
       return;
 
-   bst_node_walk_inorder(bst->root, op);
+   bst_data_walk_inorder(bst->root, op);
    }
 
 ////////////////////////////////////////////////////////////////////////////////
-void bst_node_walk_inorder(struct bst_node * node, void (*op)(void * data))
+void bst_walk_postorder(struct bst * bst, void (*op)(void * data))
+   {
+   if ( (NULL == bst) || (NULL == bst->root) || (NULL == op) )
+      return;
+
+   bst_data_walk_postorder(bst->root, op);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void bst_walk_preorder(struct bst * bst, void (*op)(void * data))
+   {
+   if ( (NULL == bst) || (NULL == bst->root) || (NULL == op) )
+      return;
+
+   bst_data_walk_preorder(bst->root, op);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void bst_data_walk_inorder(struct bst_node * node, void (*op)(void * data))
    {
    if (NULL != node)
       {
-      bst_node_walk_inorder(node->left, op);
+      bst_data_walk_inorder(node->left, op);
       op(node->data);
-      bst_node_walk_inorder(node->right, op);
+      bst_data_walk_inorder(node->right, op);
+      }
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void bst_data_walk_postorder(struct bst_node * node, void (*op)(void * data))
+   {
+   if (NULL != node)
+      {
+      bst_data_walk_postorder(node->left, op);
+      bst_data_walk_postorder(node->right, op);
+      op(node->data);
+      }
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void bst_data_walk_preorder(struct bst_node * node, void (*op)(void * data))
+   {
+   if (NULL != node)
+      {
+      op(node->data);
+      bst_data_walk_preorder(node->left, op);
+      bst_data_walk_preorder(node->right, op);
+      }
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void bst_node_walk_postorder(struct bst_node * node, void (*op)(struct bst_node * n))
+   {
+   if (NULL != node)
+      {
+      bst_node_walk_postorder(node->left, op);
+      bst_node_walk_postorder(node->right, op);
+      op(node);
       }
    }
 
@@ -188,3 +254,109 @@
       return NULL;
    return node->data;
    }
+
+////////////////////////////////////////////////////////////////////////////////
+struct bst_iterator * bst_begin(struct bst * bst)
+   {
+   if ( (NULL == bst) || (NULL == bst->root) )
+      return NULL;
+
+   struct bst_node * min = bst->root;
+   while (min->left)
+      min = min->left;
+
+   struct bst_iterator * it = malloc(sizeof(struct bst_iterator));
+   if (NULL == it)
+      return NULL;
+
+   it->bst = bst;
+   it->curr = min;
+   return it;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+struct bst_iterator * bst_end(struct bst * bst)
+   {
+   if ( (NULL == bst) || (NULL == bst->root) )
+      return NULL;
+
+   struct bst_node * max = bst->root;
+   while (max->right)
+      max = max->right;
+
+   struct bst_iterator * it = malloc(sizeof(struct bst_iterator));
+   if (NULL == it)
+      return NULL;
+
+   it->bst = bst;
+   it->curr = max;
+   return it;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+struct bst_iterator * bst_next(struct bst_iterator * it)
+   {
+   if ( (NULL == it) || (NULL == it->bst) || (NULL == it->curr) )
+      return NULL;
+
+   if (NULL == it->curr->right)
+      {
+      struct bst_node * p = it->curr;
+      it->curr = it->curr->parent;
+      while ( (NULL != it->curr) && (p == it->curr->right) )
+	 {
+	 p = it->curr;
+	 it->curr = it->curr->parent;
+	 }
+
+      if (it->curr == NULL)
+	 return NULL;
+      }
+   else
+      {
+      struct bst_node * min = it->curr->right;
+      while (min->left)
+	 min = min->left;
+      it->curr = min;
+      }
+   return it;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+struct bst_iterator * bst_prev(struct bst_iterator * it)
+   {
+   if ( (NULL == it) || (NULL == it->bst) || (NULL == it->curr) )
+      return NULL;
+
+   if (NULL == it->curr->left)
+      {
+      struct bst_node * p = it->curr;
+      it->curr = it->curr->parent;
+      while ( (NULL != it->curr) && (p == it->curr->left) )
+	 {
+	 p = it->curr;
+	 it->curr = it->curr->parent;
+	 }
+
+      if (it->curr == NULL)
+	 return NULL;
+      }
+   else
+      {
+      struct bst_node * max = it->curr->left;
+      while (max->right)
+	 max = max->right;
+      it->curr = max;
+      }
+   return it;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void * bst_value(struct bst_iterator * it)
+   {
+   if ( (NULL == it) || (NULL == it->bst) || (NULL == it->curr) )
+      return NULL;
+
+   return it->curr->data;
+   }
+
diff -r 9f1e34c4a810 -r b38243d51aea src/bst.h
--- a/src/bst.h	Wed Sep 26 13:11:09 2012 -0500
+++ b/src/bst.h	Wed Sep 26 18:59:22 2012 -0500
@@ -20,6 +20,12 @@
    bool (*eq)(void * a, void * b);
    };
 
+struct bst_iterator
+   {
+   struct bst * bst;
+   struct bst_node * curr;
+   };
+
 struct bst * bst_new(bool (*le)(void * a, void * b), bool (*eq)(void * a, void * b));
 void bst_delete(struct bst * bst);
 
@@ -32,5 +38,14 @@
 void * bst_maximum(struct bst * bst);
 
 void bst_walk_inorder(struct bst * bst, void (*op)(void * data));
+void bst_walk_preorder(struct bst * bst, void (*op)(void * data));
+void bst_walk_postorder(struct bst * bst, void (*op)(void * data));
+
+
+struct bst_iterator * bst_begin(struct bst * bst);
+struct bst_iterator * bst_end(struct bst * bst);
+struct bst_iterator * bst_next(struct bst_iterator * it);
+struct bst_iterator * bst_prev(struct bst_iterator * it);
+void * bst_value(struct bst_iterator * it);
 
 #endif
diff -r 9f1e34c4a810 -r b38243d51aea src/bst_test.c
--- a/src/bst_test.c	Wed Sep 26 13:11:09 2012 -0500
+++ b/src/bst_test.c	Wed Sep 26 18:59:22 2012 -0500
@@ -22,6 +22,11 @@
    printf("%d\n", *((int *) d) );
    }
 
+void free_data(void * d)
+   {
+   free(d);
+   }
+
 int main(int argc, char ** argv)
    {
    struct bst * bst = bst_new(le, eq);
@@ -31,6 +36,8 @@
       exit(EXIT_FAILURE);
       }
 
+   ////////////////////////////////////////
+   printf ("======================\nGenerating\n");
    //srand(time());
    int * ip;
    for (int i = 0 ; i < MAX_NUMS ; ++i)
@@ -43,16 +50,20 @@
 	 }
 
       *ip = rand();
-
+      printf("%d\n", *ip);
       if (NULL == bst_insert(bst, ip))
 	 {
 	 perror("bst_insert");
 	 exit(EXIT_FAILURE);
 	 }
       }
+   printf ("======================\n");
 
+
+   ////////////////////////////////////////
    bst_walk_inorder(bst, print);
 
+   ////////////////////////////////////////
    int i = 1;
    int * p = (int *) bst_search(bst, &i);
    if (NULL == p)
@@ -87,5 +98,36 @@
    else
       printf("%d MAXIMUM\n", *max);
 
+   ////////////////////////////////////////
+   printf("\n\nWalking inorder with iterators\n");
+   struct bst_iterator * it = bst_begin(bst);
+   if (NULL == it)
+      {
+      perror("bst_begin");
+      exit(EXIT_FAILURE);
+      }
+   do
+      printf("%d\n", *((int *) bst_value(it)));
+   while (bst_next(it));
+   free(it);
+
+
+   ////////////////////////////////////////
+   printf("\n\nWalking reverse inorder with iterators\n");
+   it = bst_end(bst);
+   if (NULL == it)
+      {
+      perror("bst_end");
+      exit(EXIT_FAILURE);
+      }
+   do
+      printf("%d\n", *((int *) bst_value(it)));
+   while (bst_prev(it));
+   free(it);
+
+
+   bst_walk_inorder(bst, free_data);
+   bst_delete(bst);
+
    exit(EXIT_SUCCESS);
    }