From bde4a47b45d312cac38200930a7c28d0a3d6c575 Mon Sep 17 00:00:00 2001
From: Carlos Daniel Ruvalcaba Valenzuela <clsdaniel@laptopD.casa.net>
Date: Thu, 30 Aug 2007 15:33:36 -0700
Subject: [PATCH] Added comments to searchtree

---
 include/libfmail/searchtree.h | 41 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 41 insertions(+)

diff --git a/include/libfmail/searchtree.h b/include/libfmail/searchtree.h
index 185e979..9005d94 100644
--- a/include/libfmail/searchtree.h
+++ b/include/libfmail/searchtree.h
@@ -18,10 +18,41 @@ with this program; if not, write to the Free Software Foundation, Inc.,
 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */
 
+/* Generic Search Tree
+ * For a given key string and value, generate
+ * a tree that can be navigated using the key
+ * characters to retrieve a value.
+ *
+ * Given the Key-Value:
+ *  * test-20
+ *  * key-8
+ *  * some-10
+ *  * same-11
+ *   ROOT
+ *  / | \
+ * t  k  s
+ * e  e  o \
+ * s  y  m  a
+ * t     e  m
+ *          e
+ * The search tree may be arranged this way, with the last
+ * node having the value.
+ *
+ * Notes:
+ *  * This algorithm is O(n), may be better than binary trees but not
+ *    so good as hash tables, proable is in the middle between speed
+ *    and memory usage.
+ *  * This algorithm may consume a lot of memory, depending on the
+ *    keys, it is recomended to use a hash function with values ranging
+ *    from 0 to 26 for best performance.
+ * */
+
 typedef int (*HASH_FUNC)(char s);
 
+/* Search failure exception */
 class SearchNotFound {};
 
+/* Node class */
 template <class T, int max> class TreeNode{
 public:
     T value;
@@ -34,6 +65,10 @@ public:
     }
 };
 
+/* Generic search tree class 
+ * may hold T type of values, may use
+ * max number for characters for key hashes,
+ * may use hash_func for character key hashes */
 template <class T, int max, HASH_FUNC hash_func> class SearchTree{
 private:
     TreeNode<T, max> *rootNode;
@@ -60,19 +95,25 @@ public:
         int i, l, tk;
         TreeNode<T, max> *c;
         
+		/* Grab root node and key length*/
         c = rootNode;
         l = strlen(key);
         
+		/* For each character in key insert a node */
         for (i = 0; i < l; i++){
+			/* Get the hash key character */
             tk = hash_func(key[i]);
 
+			/* If hash key character > max allowed should fail, undefined for now */
             if (tk > max)
                 printf("GOT MAX\n");
             
+			/* If next node is NULL create */
             if (c->tree[tk] == NULL)
                 c->tree[tk] = new TreeNode<T, max>();
             c = c->tree[tk];
         }
+		/* Once we reach the final node, set the value */
         c->value = value;
         return 0;
     }
-- 
2.11.4.GIT