# HG changeset patch # User Eris Caffee # Date 1349190787 18000 # Node ID 7886d2da8cc4714407195fb9dd42589ea721066b # Parent d359966ed8def853c8d792acbd123195754b293d Trie working OK. Started on compact trie, ctrie. diff -r d359966ed8de -r 7886d2da8cc4 CMakeLists.txt --- a/CMakeLists.txt Mon Oct 01 15:50:30 2012 -0500 +++ b/CMakeLists.txt Tue Oct 02 10:13:07 2012 -0500 @@ -102,4 +102,5 @@ add_executable (trie_test src/trie_test.c ${trie_SRCS} + ${list_SRCS} ) diff -r d359966ed8de -r 7886d2da8cc4 src/ctrie.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/ctrie.c Tue Oct 02 10:13:07 2012 -0500 @@ -0,0 +1,410 @@ +#include +#include +#include +#include +#include + +#include "list.h" + +struct ctrie_node + { + char * key; + struct ctrie_node * parent; + struct ctrie_node * child; + struct ctrie_node * next_sibling; + struct ctrie_node * prev_sibling; + void * data; + }; + +struct ctrie + { + struct ctrie_node * root; + size_t size; + size_t count; + }; + + +static struct list * subkey_list = NULL; +static size_t subkey_list_limit = 0; + +struct ctrie_node * ctrie_search_children(struct ctrie_node * node, char k); +void ctrie_visit_node(struct ctrie * ctrie, struct ctrie_node * node, void (*op)(char * k, void * d), char * key); +void ctrie_print_node(struct ctrie_node * node); +void ctrie_print_node(struct ctrie_node * node); +void ctrie_node_dump_preorder(struct ctrie * ctrie, struct ctrie_node * node, int depth); +void ctrie_node_dump_raw(struct ctrie_node * node, int depth); +void ctrie_subtree_list_push(char * k, void * d); +struct ctrie_node * ctrie_find_node(struct ctrie * ctrie, char * key); + +struct ctrie_node * ctrie_search_children_longest_match(struct ctrie_node * node, char * k); + +#undef MAX +#define MAX (a, b) ((a) > (b) ? (a) : (b)) + +//////////////////////////////////////////////////////////////////////////////// +struct ctrie * +ctrie_new() + { + struct ctrie * ctrie = malloc(sizeof(struct ctrie)); + if (NULL == ctrie) + return NULL; + + ctrie->root = malloc(sizeof(struct ctrie_node)); + if (NULL == ctrie->root) + return NULL; + + ctrie->root->parent = ctrie->root->child = ctrie->root->next_sibling = NULL; + ctrie->root->key = NULL; + ctrie->root->data = NULL; + ctrie->size = ctrie->count = 0; + + return ctrie; + } + +//////////////////////////////////////////////////////////////////////////////// +void +ctrie_delete(struct ctrie * ctrie) + { + if (NULL == ctrie) + return; + + free(ctrie); + } + +//////////////////////////////////////////////////////////////////////////////// +size_t +ctrie_size(struct ctrie * ctrie) + { + if (NULL == ctrie) + return 0; + return ctrie->size; + } + +//////////////////////////////////////////////////////////////////////////////// +size_t +ctrie_count(struct ctrie * ctrie) + { + if (NULL == ctrie) + return 0; + return ctrie->count; + } + +//////////////////////////////////////////////////////////////////////////////// +char * +ctrie_insert(struct ctrie * ctrie, char * key, void * data) + { + if ( (NULL == ctrie) || (NULL == key) ) + return NULL; + + struct ctrie_node * curr = ctrie->root; + struct ctrie_node * result; + + size_t len = strlen(key); + for (int i = 0; i <= len; ++i) + { + result = ctrie_search_children_longest_match(curr, key+i); + if (NULL == result) + { + // current char is not in the ctrie yet, allocate a new node and attach it to the children + struct ctrie_node * new = malloc(sizeof(struct ctrie_node)); + if (NULL == new) + return NULL; + new->key = tolower(key[i]); + new->child = new->next_sibling = new->prev_sibling = NULL; + new->data = NULL; + + if (NULL == curr->child) + curr->child = new; + else + { + struct ctrie_node * p = curr->child; + while (p->next_sibling) + p = p->next_sibling; + new->prev_sibling = p; + p->next_sibling = new; + } + + new->parent = curr; + curr = new; + ctrie->size++; + } + else + curr = result; + } + + // At this point, curr is either pointing to a new \0 node with a NULL data pointer, + // or an existing \0 node with a valid data pointer (in which case we were asked to "insert" + // a key that was already present in the ctrie. + // For now I am simply ignoring collisions. We will update the data. + + curr->data = data; + + ctrie->count++; + + return key; + } + +//////////////////////////////////////////////////////////////////////////////// +struct ctrie_node * +ctrie_search_children_longest_match(struct ctrie_node * node, char * k) + { + struct ctrie_node * p = node->child; + if (NULL == p) + return NULL; + + size_t klen = strlen(k); + struct ctrie_node * longest = NULL; + size_t length = 0; + while (NULL != p) + { + size_t len = strlen(p->key); + while (len > 0) + { + if ( (0 == strncmp(p->key, k, MAX(len, klen))) && + (length < MAX(len, klen)) ) + { + longest = p; + length = MAX(len, klen); + break; + } + len--; + } + p = p->next_sibling; + } + + return p; + } + +//////////////////////////////////////////////////////////////////////////////// +struct ctrie_node * +ctrie_search_children(struct ctrie_node * node, char k) + { + struct ctrie_node * p = node->child; + if (NULL == p) + return NULL; + + while ( (NULL != p) && (p->key != tolower(k)) ) + p = p->next_sibling; + return p; + } + +//////////////////////////////////////////////////////////////////////////////// +struct ctrie_node * +ctrie_find_node(struct ctrie * ctrie, char * key) + { + if ( (NULL == ctrie) || (NULL == key) ) + return NULL; + + struct ctrie_node * node = ctrie->root; + size_t len = strlen(key); + for (int i = 0; i <= len; i++) + { + node = ctrie_search_children(node, key[i]); + if (NULL == node) + return NULL; + if ('\0' == key[i]) + return node; + } + + // Should never get here + return NULL; + } + +//////////////////////////////////////////////////////////////////////////////// +void * +ctrie_find(struct ctrie * ctrie, char * key) + { + struct ctrie_node * node = ctrie_find_node(ctrie, key); + if (NULL == node) + return NULL; + return node->data; + } + +//////////////////////////////////////////////////////////////////////////////// +void * +ctrie_remove(struct ctrie * ctrie, char * key) + { + if ( (NULL == ctrie) || (NULL == key) ) + return NULL; + + struct ctrie_node * node = ctrie_find_node(ctrie, key); + if (NULL == node) + return NULL; + + void * data = node->data; + + while ( (NULL == node->prev_sibling) && (NULL == node->prev_sibling) ) + { + struct ctrie_node * p = node; + node = node->parent; + free(p); + ctrie->size--; + } + + if (node == ctrie->root) + return data; + + if (node->prev_sibling) + node->prev_sibling->next_sibling = node->next_sibling; + else + node->parent->child = node->next_sibling; + + if (node->next_sibling) + node->next_sibling->prev_sibling = node->prev_sibling; + + free(node); + + ctrie->count--; + + return data; + } + +//////////////////////////////////////////////////////////////////////////////// +void +ctrie_walk_keys(struct ctrie * ctrie, void (*op)(char * k, void * d)) + { + if (NULL == ctrie) + return; + ctrie_visit_node(ctrie, ctrie->root, op, ""); + } + +//////////////////////////////////////////////////////////////////////////////// +void +ctrie_visit_node(struct ctrie * ctrie, struct ctrie_node * node, void (*op)(char * k, void * d), char * key) + { + if ( (node->key == '\0') && (node != ctrie->root) ) + op(key, node->data); + else + { + size_t len = strlen(key); + char * k = malloc(len+2); + if (NULL == k) + return; + strcpy(k, key); + k[len] = node->key; + k[len+1] = '\0'; + struct ctrie_node * p = node->child; + while (NULL != p) + { + ctrie_visit_node(ctrie, p, op, k); + p = p->next_sibling; + } + free(k); + } + } + +//////////////////////////////////////////////////////////////////////////////// +void ctrie_dump_raw(struct ctrie * ctrie) + { + if (NULL == ctrie) + return; + + int depth = -1; + ctrie_node_dump_raw(ctrie->root, depth); + } + +//////////////////////////////////////////////////////////////////////////////// +void +ctrie_node_dump_raw(struct ctrie_node * node, int depth) + { + for (int i=0; i < depth; i++) + printf(" "); + ctrie_print_node(node); + if (node->child) + ctrie_node_dump_raw(node->child, depth+1); + if (NULL != node->next_sibling) + ctrie_node_dump_raw(node->next_sibling, depth+1); + } + +//////////////////////////////////////////////////////////////////////////////// +void ctrie_dump(struct ctrie * ctrie) + { + if (NULL == ctrie) + return; + + int depth = -1; + ctrie_node_dump_preorder(ctrie, ctrie->root, depth); + } + +//////////////////////////////////////////////////////////////////////////////// +void +ctrie_node_dump_preorder(struct ctrie * ctrie, struct ctrie_node * node, int depth) + { + printf("%c", node->key); + if ( (node != ctrie->root) && ('\0' == node->key) ) + printf("\n"); + if (node->child) + ctrie_node_dump_preorder(ctrie, node->child, depth+1); + if (NULL != node->next_sibling) + { + for (int i=0; i < depth; i++) + printf(" "); + ctrie_node_dump_preorder(ctrie, node->next_sibling, depth); + } + } + +//////////////////////////////////////////////////////////////////////////////// +void +ctrie_print_node(struct ctrie_node * node) + { + printf("%p\tchild %p\tnext_sibling %p\tkey %c\tdata %p\n", (void *) node, (void *) node->child, + (void *) node->next_sibling, node->key, node->data); + } + +//////////////////////////////////////////////////////////////////////////////// +void +ctrie_subtree_list_push(char * k, void * d) + { + if (NULL == subkey_list) + return; + + if ( (0 == subkey_list_limit) || (list_size(subkey_list) < subkey_list_limit) ) + list_push_front(subkey_list, k); + } + +//////////////////////////////////////////////////////////////////////////////// +// Not reentrant since it uses the package static subkeys_list variable. +// However, that variable is only used while building a subkey list, so you can +// get more than one subkey if you want. Just don't try to get them simultaneously. +struct list * +ctrie_get_subkeys(struct ctrie * ctrie, char * prefix, size_t limit) + { + if ( (NULL == ctrie) || (NULL == prefix) ) + return NULL; + + struct ctrie_node * node = ctrie_find_node(ctrie, prefix); + if (NULL == node) + return NULL; + + subkey_list = list_new(); + if (NULL == subkey_list) + return NULL; + subkey_list_limit = limit; + + size_t len = strlen(prefix); + char * pref = malloc(len+1); + if (NULL == pref) + return NULL; + strncpy(pref, prefix, len-1); + pref[len-1] = '\0'; + + ctrie_visit_node(ctrie, node->parent, ctrie_subtree_list_push, pref); + free(pref); + + return subkey_list; + } + +//////////////////////////////////////////////////////////////////////////////// +void +ctrie_free_subkey_list(struct list * list) + { + if (NULL == list) + return; + + struct list_iterator * it = list_begin(list); + void * data; + while (data = list_remove(it)) + free(data); + + list_delete(list); + } diff -r d359966ed8de -r 7886d2da8cc4 src/ctrie.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/ctrie.h Tue Oct 02 10:13:07 2012 -0500 @@ -0,0 +1,27 @@ +#ifndef CTRIE_H_ +#define CTRIE_H_ + +// Compact trie - internal nodes are collapsed together if they have no siblings. + +struct ctrie; + +struct ctrie * ctrie_new(); +void ctrie_delete(struct ctrie * ctrie); + +size_t ctrie_size(struct ctrie * ctrie); +size_t ctrie_count(struct ctrie * ctrie); + +char * ctrie_insert(struct ctrie * ctrie, char * key, void * data); +void * ctrie_find(struct ctrie * ctrie, char * key); +void * ctrie_remove(struct ctrie * ctrie, char * key); + +void ctrie_walk_keys(struct ctrie * ctrie, void (*op)(char * k, void * d) ); + +void ctrie_dump(struct ctrie * ctrie); +void ctrie_dump_raw(struct ctrie * ctrie); + +struct list * ctrie_get_subkeys(struct ctrie * ctrie, char * prefix, size_t limit); +void ctrie_free_subkey_list(struct list * list); + + +#endif diff -r d359966ed8de -r 7886d2da8cc4 src/ctrie_test.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/ctrie_test.c Tue Oct 02 10:13:07 2012 -0500 @@ -0,0 +1,128 @@ +#include +#include +#include + +#include "list.h" +#include "ctrie.h" + +void print_val(char * key, void * data) + { + printf("%s\t\t%s\n", key, data); + } + +int main(int argc, char ** argv) + { + struct ctrie * ctrie = ctrie_new(); + + char * words[] = { "hello", "interjection (used to express a greeting, answer a telephone, or attract attention.)", + "help", "to give or provide what is necessary to accomplish a task or satisfy a need.", + "helper", "a person or thing that helps or gives assistance, support, etc", + "helping", "the act of a person or thing that helps.", + "an", "indefinite article. the form of a before an initial vowel sound.", + "a", "indefinite article. Used before an initial consonant sound.", + "anne", "a female name", + "any", "one, a, an, or some; one or more without specification or identification", + "anyway", "in any case; anyhow; nonetheless; regardless", + "anna", "a female name", + "anyhow", "in any way whatever", + "anybody", "any person", + "Apple", "A computer manufacturer.", + "ABLE", "having necessary power, skill, resources, or qualifications", + NULL, NULL + }; + int i = 0; + while (words[i]) + { + ctrie_insert(ctrie, words[i], words[i+1]); + i += 2; + } + + ctrie_dump_raw(ctrie); + ctrie_dump(ctrie); + ctrie_walk_keys(ctrie, print_val); + printf("ctrie is storing %zd words in %zd keys\n", ctrie_count(ctrie), ctrie_size(ctrie)); + + //////////////////////////////////////////// + printf("===================================================\n"); + char word[100];; + strcpy(word, "any"); + printf("searching for %s\n", word); + + void * data = ctrie_find(ctrie, word); + if (NULL == data) + printf("Failed to find 'any'\n"); + else + printf("any: %s\n", (char *) data); + + + //////////////////////////////////////////// + printf("===================================================\n"); + strcpy(word, "an"); + printf("Looking for completions of '%s':\n", word); + struct list * list = ctrie_get_subkeys(ctrie, word, 0); + if (NULL == list) + printf("Nothing found for '%s'\n", word); + else + { + printf("list size is %d\n", list_size(list)); + struct list_iterator * it = list_begin(list); + struct list_iterator * next = it; + while (NULL != next) + { + printf("%s\n", list_value(it)); + next = list_next(it); + } + ctrie_free_subkey_list(list); + } + + //////////////////////////////////////////// + printf("===================================================\n"); + strcpy(word, "a"); + printf("Looking for first 5 completions of '%s':\n", word); + list = ctrie_get_subkeys(ctrie, word, 5); + if (NULL == list) + printf("Nothing found for '%s'\n", word); + else + { + printf("list size is %d\n", list_size(list)); + struct list_iterator * it = list_begin(list); + struct list_iterator * next = it; + while (NULL != next) + { + printf("%s\n", list_value(it)); + next = list_next(it); + } + ctrie_free_subkey_list(list); + } + + //////////////////////////////////////////// + printf("===================================================\n"); + strcpy(word, "anybody"); + printf("remove '%s'\n", word); + ctrie_remove(ctrie, word); + + strcpy(word, "ann"); + printf("remove '%s'\n", word); + ctrie_remove(ctrie, word); + + strcpy(word, "help"); + printf("remove '%s'\n", word); + ctrie_remove(ctrie, word); + + strcpy(word, "a"); + printf("remove '%s'\n", word); + ctrie_remove(ctrie, word); + + ctrie_dump(ctrie); + printf("ctrie is storing %zd words in %zd keys\n", ctrie_count(ctrie), ctrie_size(ctrie)); + + //////////////////////////////////////////// + printf("===================================================\n"); + strcpy(word, "anybody"); + printf("re-inserting '%s'\n", word); + ctrie_insert(ctrie, word, "fake definition"); + ctrie_dump(ctrie); + printf("ctrie is storing %zd words in %zd keys\n", ctrie_count(ctrie), ctrie_size(ctrie)); + + exit(EXIT_SUCCESS); + } diff -r d359966ed8de -r 7886d2da8cc4 src/trie.c --- a/src/trie.c Mon Oct 01 15:50:30 2012 -0500 +++ b/src/trie.c Tue Oct 02 10:13:07 2012 -0500 @@ -2,30 +2,39 @@ #include #include #include - - #include +#include "list.h" struct trie_node { char key; + struct trie_node * parent; struct trie_node * child; - struct trie_node * sibling; + struct trie_node * next_sibling; + struct trie_node * prev_sibling; void * data; }; struct trie { struct trie_node * root; + size_t size; + size_t count; }; + +static struct list * subkey_list = NULL; +static size_t subkey_list_limit = 0; + struct trie_node * trie_search_children(struct trie_node * node, char k); void trie_visit_node(struct trie * trie, struct trie_node * node, void (*op)(char * k, void * d), char * key); void trie_print_node(struct trie_node * node); void trie_print_node(struct trie_node * node); void trie_node_dump_preorder(struct trie * trie, struct trie_node * node, int depth); void trie_node_dump_raw(struct trie_node * node, int depth); +void trie_subtree_list_push(char * k, void * d); +struct trie_node * trie_find_node(struct trie * trie, char * key); //////////////////////////////////////////////////////////////////////////////// struct trie * @@ -39,9 +48,10 @@ if (NULL == trie->root) return NULL; - trie->root->child = trie->root->sibling = NULL; + trie->root->parent = trie->root->child = trie->root->next_sibling = NULL; trie->root->key = '\0'; trie->root->data = NULL; + trie->size = trie->count = 0; return trie; } @@ -57,6 +67,24 @@ } //////////////////////////////////////////////////////////////////////////////// +size_t +trie_size(struct trie * trie) + { + if (NULL == trie) + return 0; + return trie->size; + } + +//////////////////////////////////////////////////////////////////////////////// +size_t +trie_count(struct trie * trie) + { + if (NULL == trie) + return 0; + return trie->count; + } + +//////////////////////////////////////////////////////////////////////////////// char * trie_insert(struct trie * trie, char * key, void * data) { @@ -77,7 +105,7 @@ if (NULL == new) return NULL; new->key = tolower(key[i]); - new->child = new->sibling = NULL; + new->child = new->next_sibling = new->prev_sibling = NULL; new->data = NULL; if (NULL == curr->child) @@ -85,12 +113,15 @@ else { struct trie_node * p = curr->child; - while (p->sibling) - p = p->sibling; - p->sibling = new; + while (p->next_sibling) + p = p->next_sibling; + new->prev_sibling = p; + p->next_sibling = new; } + new->parent = curr; curr = new; + trie->size++; } else curr = result; @@ -102,6 +133,9 @@ // For now I am simply ignoring collisions. We will update the data. curr->data = data; + + trie->count++; + return key; } @@ -114,13 +148,13 @@ return NULL; while ( (NULL != p) && (p->key != tolower(k)) ) - p = p->sibling; + p = p->next_sibling; return p; } //////////////////////////////////////////////////////////////////////////////// -void * -trie_find(struct trie * trie, char * key) +struct trie_node * +trie_find_node(struct trie * trie, char * key) { if ( (NULL == trie) || (NULL == key) ) return NULL; @@ -133,7 +167,7 @@ if (NULL == node) return NULL; if ('\0' == key[i]) - return node->data; + return node; } // Should never get here @@ -142,9 +176,51 @@ //////////////////////////////////////////////////////////////////////////////// void * +trie_find(struct trie * trie, char * key) + { + struct trie_node * node = trie_find_node(trie, key); + if (NULL == node) + return NULL; + return node->data; + } + +//////////////////////////////////////////////////////////////////////////////// +void * trie_remove(struct trie * trie, char * key) { - return NULL; + if ( (NULL == trie) || (NULL == key) ) + return NULL; + + struct trie_node * node = trie_find_node(trie, key); + if (NULL == node) + return NULL; + + void * data = node->data; + + while ( (NULL == node->prev_sibling) && (NULL == node->prev_sibling) ) + { + struct trie_node * p = node; + node = node->parent; + free(p); + trie->size--; + } + + if (node == trie->root) + return data; + + if (node->prev_sibling) + node->prev_sibling->next_sibling = node->next_sibling; + else + node->parent->child = node->next_sibling; + + if (node->next_sibling) + node->next_sibling->prev_sibling = node->prev_sibling; + + free(node); + + trie->count--; + + return data; } //////////////////////////////////////////////////////////////////////////////// @@ -175,8 +251,9 @@ while (NULL != p) { trie_visit_node(trie, p, op, k); - p = p->sibling; + p = p->next_sibling; } + free(k); } } @@ -199,8 +276,8 @@ trie_print_node(node); if (node->child) trie_node_dump_raw(node->child, depth+1); - if (NULL != node->sibling) - trie_node_dump_raw(node->sibling, depth+1); + if (NULL != node->next_sibling) + trie_node_dump_raw(node->next_sibling, depth+1); } //////////////////////////////////////////////////////////////////////////////// @@ -222,11 +299,11 @@ printf("\n"); if (node->child) trie_node_dump_preorder(trie, node->child, depth+1); - if (NULL != node->sibling) + if (NULL != node->next_sibling) { for (int i=0; i < depth; i++) printf(" "); - trie_node_dump_preorder(trie, node->sibling, depth); + trie_node_dump_preorder(trie, node->next_sibling, depth); } } @@ -234,5 +311,64 @@ void trie_print_node(struct trie_node * node) { - printf("%p\tchild %p\tsibling %p\tkey %c\tdata %p\n", node, node->child, node->sibling, node->key, node->data); + printf("%p\tchild %p\tnext_sibling %p\tkey %c\tdata %p\n", (void *) node, (void *) node->child, + (void *) node->next_sibling, node->key, node->data); } + +//////////////////////////////////////////////////////////////////////////////// +void +trie_subtree_list_push(char * k, void * d) + { + if (NULL == subkey_list) + return; + + if ( (0 == subkey_list_limit) || (list_size(subkey_list) < subkey_list_limit) ) + list_push_front(subkey_list, k); + } + +//////////////////////////////////////////////////////////////////////////////// +// Not reentrant since it uses the package static subkeys_list variable. +// However, that variable is only used while building a subkey list, so you can +// get more than one subkey if you want. Just don't try to get them simultaneously. +struct list * +trie_get_subkeys(struct trie * trie, char * prefix, size_t limit) + { + if ( (NULL == trie) || (NULL == prefix) ) + return NULL; + + struct trie_node * node = trie_find_node(trie, prefix); + if (NULL == node) + return NULL; + + subkey_list = list_new(); + if (NULL == subkey_list) + return NULL; + subkey_list_limit = limit; + + size_t len = strlen(prefix); + char * pref = malloc(len+1); + if (NULL == pref) + return NULL; + strncpy(pref, prefix, len-1); + pref[len-1] = '\0'; + + trie_visit_node(trie, node->parent, trie_subtree_list_push, pref); + free(pref); + + return subkey_list; + } + +//////////////////////////////////////////////////////////////////////////////// +void +trie_free_subkey_list(struct list * list) + { + if (NULL == list) + return; + + struct list_iterator * it = list_begin(list); + void * data; + while (data = list_remove(it)) + free(data); + + list_delete(list); + } diff -r d359966ed8de -r 7886d2da8cc4 src/trie.h --- a/src/trie.h Mon Oct 01 15:50:30 2012 -0500 +++ b/src/trie.h Tue Oct 02 10:13:07 2012 -0500 @@ -6,6 +6,9 @@ struct trie * trie_new(); void trie_delete(struct trie * trie); +size_t trie_size(struct trie * trie); +size_t trie_count(struct trie * trie); + char * trie_insert(struct trie * trie, char * key, void * data); void * trie_find(struct trie * trie, char * key); void * trie_remove(struct trie * trie, char * key); @@ -15,4 +18,8 @@ void trie_dump(struct trie * trie); void trie_dump_raw(struct trie * trie); +struct list * trie_get_subkeys(struct trie * trie, char * prefix, size_t limit); +void trie_free_subkey_list(struct list * list); + + #endif diff -r d359966ed8de -r 7886d2da8cc4 src/trie_test.c --- a/src/trie_test.c Mon Oct 01 15:50:30 2012 -0500 +++ b/src/trie_test.c Tue Oct 02 10:13:07 2012 -0500 @@ -1,11 +1,13 @@ #include #include +#include +#include "list.h" #include "trie.h" void print_val(char * key, void * data) { - printf("%s\n", key); + printf("%s\t\t%s\n", key, data); } int main(int argc, char ** argv) @@ -16,12 +18,12 @@ "help", "to give or provide what is necessary to accomplish a task or satisfy a need.", "helper", "a person or thing that helps or gives assistance, support, etc", "helping", "the act of a person or thing that helps.", + "an", "indefinite article. the form of a before an initial vowel sound.", "a", "indefinite article. Used before an initial consonant sound.", - "an", "indefinite article. the form of a before an initial vowel sound.", - "anna", "a female name", "anne", "a female name", "any", "one, a, an, or some; one or more without specification or identification", - "anyway", "in any case; anyhow; nonetheless; regardless", + "anyway", "in any case; anyhow; nonetheless; regardless", + "anna", "a female name", "anyhow", "in any way whatever", "anybody", "any person", "Apple", "A computer manufacturer.", @@ -35,13 +37,92 @@ i += 2; } + trie_dump_raw(trie); trie_dump(trie); + trie_walk_keys(trie, print_val); + printf("trie is storing %zd words in %zd keys\n", trie_count(trie), trie_size(trie)); - void * data = trie_find(trie, "any"); + //////////////////////////////////////////// + printf("===================================================\n"); + char word[100];; + strcpy(word, "any"); + printf("searching for %s\n", word); + + void * data = trie_find(trie, word); if (NULL == data) printf("Failed to find 'any'\n"); else printf("any: %s\n", (char *) data); + + //////////////////////////////////////////// + printf("===================================================\n"); + strcpy(word, "an"); + printf("Looking for completions of '%s':\n", word); + struct list * list = trie_get_subkeys(trie, word, 0); + if (NULL == list) + printf("Nothing found for '%s'\n", word); + else + { + printf("list size is %d\n", list_size(list)); + struct list_iterator * it = list_begin(list); + struct list_iterator * next = it; + while (NULL != next) + { + printf("%s\n", list_value(it)); + next = list_next(it); + } + trie_free_subkey_list(list); + } + + //////////////////////////////////////////// + printf("===================================================\n"); + strcpy(word, "a"); + printf("Looking for first 5 completions of '%s':\n", word); + list = trie_get_subkeys(trie, word, 5); + if (NULL == list) + printf("Nothing found for '%s'\n", word); + else + { + printf("list size is %d\n", list_size(list)); + struct list_iterator * it = list_begin(list); + struct list_iterator * next = it; + while (NULL != next) + { + printf("%s\n", list_value(it)); + next = list_next(it); + } + trie_free_subkey_list(list); + } + + //////////////////////////////////////////// + printf("===================================================\n"); + strcpy(word, "anybody"); + printf("remove '%s'\n", word); + trie_remove(trie, word); + + strcpy(word, "ann"); + printf("remove '%s'\n", word); + trie_remove(trie, word); + + strcpy(word, "help"); + printf("remove '%s'\n", word); + trie_remove(trie, word); + + strcpy(word, "a"); + printf("remove '%s'\n", word); + trie_remove(trie, word); + + trie_dump(trie); + printf("trie is storing %zd words in %zd keys\n", trie_count(trie), trie_size(trie)); + + //////////////////////////////////////////// + printf("===================================================\n"); + strcpy(word, "anybody"); + printf("re-inserting '%s'\n", word); + trie_insert(trie, word, "fake definition"); + trie_dump(trie); + printf("trie is storing %zd words in %zd keys\n", trie_count(trie), trie_size(trie)); + exit(EXIT_SUCCESS); }