# HG changeset patch
# User Eris Caffee <discordia@eldalin.com>
# Date 1349410068 18000
# Node ID 5d8158ad2d61992f6f7b738dfabb766987773cab
# Parent  d11dfc49b5595b96bd60711d55229489ed701ef3
sedgewick trie

diff -r d11dfc49b559 -r 5d8158ad2d61 CMakeLists.txt
--- a/CMakeLists.txt	Wed Oct 03 01:07:04 2012 -0500
+++ b/CMakeLists.txt	Thu Oct 04 23:07:48 2012 -0500
@@ -111,3 +111,10 @@
   ${ctrie_SRCS}
   ${list_SRCS}
   )
+
+set (trie_sedgewick_SRCS src/trie_sedgewick.h src/trie_sedgewick.c)
+add_executable (trie_sedgewick_test
+  src/trie_sedgewick_test.c
+  ${trie_sedgewick_SRCS}
+  )
+
diff -r d11dfc49b559 -r 5d8158ad2d61 src/trie_sedgewick.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/trie_sedgewick.c	Thu Oct 04 23:07:48 2012 -0500
@@ -0,0 +1,114 @@
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+
+#include "trie_sedgewick.h"
+
+// Our alphabet size.  One byte's worth.
+#define RADIX 256
+
+struct trie_node
+   {
+   void * data;
+   struct trie_node * next[RADIX];
+   };
+
+struct trie
+   {
+   struct trie_node * root;
+   };
+
+
+struct trie_node * trie_node_new();
+void * trie_node_get(struct trie_node * node, char * key, int d);
+struct trie_node * trie_node_put(struct trie_node * node, char * key, void * data, int d);
+
+////////////////////////////////////////////////////////////////////////////////
+struct trie_node *
+trie_node_new()
+   {
+   struct trie_node * node = malloc(sizeof(struct trie_node));
+   if (NULL == node)
+      return NULL;
+
+   for (int i = 0; i < RADIX; ++i)
+      node->next[i] = NULL;
+   node->data = NULL;
+
+   return node;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+struct trie *
+trie_new()
+   {
+   struct trie * trie = malloc(sizeof(struct trie));
+   if (NULL == trie)
+      return NULL;
+
+   trie->root = NULL;
+   return trie;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void
+trie_delete(struct trie * trie)
+   {
+   if (NULL == trie)
+      return;
+   // TODO free nodes
+   free(trie);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+char *
+trie_put(struct trie * trie, char * key, void * data)
+   {
+   if ( (NULL == trie) || (NULL == key) )
+      return NULL;
+   trie->root = trie_node_put(trie->root, key, data, 0);
+   return key;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+struct trie_node *
+trie_node_put(struct trie_node * node, char * key, void * data, int d)
+   {
+   if (NULL == node)
+      node = trie_node_new();
+   if (NULL == node)
+      return NULL;
+
+   if (d == strlen(key))
+      {
+      node->data = data;
+      return node;
+      }
+   int c = key[d];
+   node->next[c] = trie_node_put(node->next[c], key, data, d+1);
+   return node;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void *
+trie_get(struct trie * trie, char * key)
+   {
+   if ( (NULL == trie) || (NULL == key) )
+      return NULL;
+
+   struct trie_node * node = trie_node_get(trie->root, key, 0);
+   if (NULL == node)
+      return NULL;
+   return node->data;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void *
+trie_node_get(struct trie_node * node, char * key, int d)
+   {
+   if (NULL == node)
+      return NULL;
+   if (d == strlen(key))
+      return node;
+   return trie_node_get(node->next[(int) key[d]], key, d+1);
+   }
diff -r d11dfc49b559 -r 5d8158ad2d61 src/trie_sedgewick.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/trie_sedgewick.h	Thu Oct 04 23:07:48 2012 -0500
@@ -0,0 +1,14 @@
+#ifndef TRIE_SEDGEWICK_H_
+#define TRIE_SEDGEWICK_H_
+
+// Simple trie.  After Sedgewick, Algorithms, Ch 5.
+
+struct trie;
+
+struct trie * trie_new();
+void trie_delete(struct trie * trie);
+
+char * trie_put(struct trie * trie, char * key, void * data);
+void * trie_get(struct trie * trie, char * key);
+
+#endif
diff -r d11dfc49b559 -r 5d8158ad2d61 src/trie_sedgewick_test.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/trie_sedgewick_test.c	Thu Oct 04 23:07:48 2012 -0500
@@ -0,0 +1,47 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "trie_sedgewick.h"
+
+int main(int argc, char ** argv)
+   {
+   struct trie * trie = trie_new();
+   if (NULL == trie)
+      {
+      fprintf(stderr, "trie_new failed\n");
+      exit(EXIT_FAILURE);
+      }
+
+   char * words[] = 
+	 {
+	 "she", "sells", "sea", "shells", "by", "the", "sea", "shore", NULL,
+	 };
+
+   printf("Loading trie\n");
+   char ** w = words;
+   while (*w)
+      {
+      if (NULL == trie_put(trie, *w, *w))
+	 {
+	 fprintf(stderr, "trie_put failed on %s\n", *w);
+	 exit(EXIT_FAILURE);
+	 }
+      w++;
+      }
+
+   printf("Reading trie\n");
+   w = words;
+   while (*w)
+      {
+      char * value;
+      if (NULL == (value = trie_get(trie, *w)))
+	 {
+	 fprintf(stderr, "trie_get failed on %s\n", *w);
+	 exit(EXIT_FAILURE);
+	 }
+      printf("%s\n", value);
+      w++;
+      }
+
+   exit(EXIT_SUCCESS);
+   }