X-Git-Url: https://git.cworth.org/git?a=blobdiff_plain;f=dict.c;h=a9202934035d35346f0ac75905f4baa130fff9ed;hb=ea2a992111737eccb174f26f71ab5357597d5147;hp=715e48f8deaa52c73bf499a3aae856dcc16a1e24;hpb=dd4b319cdb6e2883ae76317036b57b670344160a;p=wordgame diff --git a/dict.c b/dict.c index 715e48f..a920293 100644 --- a/dict.c +++ b/dict.c @@ -16,17 +16,25 @@ * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA." */ -/* Portably, schmortability. I want ease of programming. */ -#define _GNU_SOURCE -#include -#include +#include "dict.h" + #include #include #include -#include "dict.h" +typedef struct _string { + size_t size; + char *s; + size_t len; +} string_t; -void * +typedef bool_t +(*trie_predicate_t) (trie_t *trie); + +#define TRIE_CHAR_TO_INDEX(c) (tolower (c) - 'a') +#define TRIE_INDEX_TO_CHAR(i) (i + 'a') + +static void * xmalloc (size_t size) { void *res; @@ -40,7 +48,7 @@ xmalloc (size_t size) return res; } -void * +static void * xrealloc (void *ptr, size_t size) { void *res; @@ -54,15 +62,17 @@ xrealloc (void *ptr, size_t size) return res; } -void +static void chomp (char *s) { int len = strlen (s); + if (len == 0) + return; if (s[len - 1] == '\n') s[len - 1] = '\0'; } -void +static void string_init (string_t *string) { string->size = 0; @@ -70,7 +80,7 @@ string_init (string_t *string) string->len = 0; } -void +static void string_fini (string_t *string) { string->size = 0; @@ -79,7 +89,7 @@ string_fini (string_t *string) string->len = 0; } -void +static void string_append_char (string_t *string, char c) { if (string->size == 0) { @@ -98,7 +108,7 @@ string_append_char (string_t *string, char c) string->s[string->len] = '\0'; } -void +static void string_chop (string_t *string) { if (string->len == 0) @@ -129,7 +139,7 @@ trie_fini (trie_t *trie) trie_destroy (trie->next[i]); } -trie_t * +static trie_t * trie_create (void) { trie_t *trie; @@ -149,26 +159,24 @@ trie_destroy (trie_t *trie) free (trie); } -void +static trie_t * trie_add (trie_t *trie, const char *word_chunk) { char c = word_chunk[0]; int i; - if (c == '\0') { - trie->flags |= TRIE_FLAGS_IS_WORD; - return; - } + if (c == '\0') + return trie; i = TRIE_CHAR_TO_INDEX (c); if (trie->next[i] == NULL) trie->next[i] = trie_create (); - trie_add (trie->next[i], word_chunk + 1); + return trie_add (trie->next[i], word_chunk + 1); } -trie_t * +static trie_t * trie_find (trie_t *trie, const char *word_chunk) { @@ -180,22 +188,47 @@ trie_find (trie_t *trie, return trie; } -int +static int +trie_count (trie_t *trie, + trie_predicate_t predicate) +{ + int i; + int count = 0; + + if ((predicate) (trie)) + count = 1; + + for (i = 0; i < 26; i++) { + if (trie->next[i] == NULL) + continue; + + count += trie_count (trie->next[i], predicate); + } + + return count; +} + +static int trie_print (trie_t *trie, string_t *string, - trie_predicate_t predicate) + trie_predicate_t predicate, + int length, + int min_length, + int max_length) { char c; int i; int count = 0; - if (trie->flags & TRIE_FLAGS_IS_WORD - && (predicate == NULL || predicate (trie))) + if (length >= min_length && (predicate) (trie)) { count = 1; printf ("%s ", string->s); } + if (length == max_length) + return count; + /* Loop over each element, appending the character and recursing. */ for (i = 0; i < 26; i++) { if (trie->next[i] == NULL) @@ -204,37 +237,14 @@ trie_print (trie_t *trie, c = TRIE_INDEX_TO_CHAR (i); string_append_char (string, c); - count += trie_print (trie->next[i], string, predicate); + count += trie_print (trie->next[i], string, predicate, + length + 1, min_length, max_length); string_chop (string); } return count; } -bool_t -trie_seen_predicate (trie_t *trie) -{ - return (trie->flags & TRIE_FLAGS_SEEN); -} - -int -trie_print_seen (trie_t *trie, string_t *word) -{ - return trie_print (trie, word, trie_seen_predicate); -} - -bool_t -trie_unseen_predicate (trie_t *trie) -{ - return (! trie_seen_predicate (trie)); -} - -int -trie_print_unseen (trie_t *trie, string_t *word) -{ - return trie_print (trie, word, trie_unseen_predicate); -} - void dict_init (dict_t *dict) { @@ -251,7 +261,10 @@ void dict_add_word (dict_t *dict, const char *word) { - trie_add (dict, word); + trie_t *trie; + + trie = trie_add (dict, word); + trie->flags |= DICT_ENTRY_FLAG_IS_WORD; } void @@ -329,14 +342,94 @@ dict_cursor_resolve (dict_cursor_t cursor) return &trie->flags; } -void +/* XXX: This static function pointer is really nasty and definitely + * un-thread safe. What I really want it a lambda so I can construct a + * composite predicate on the fly. Oh well... */ +static dict_entry_predicate_t dict_entry_predicate = NULL; + +static bool_t +dict_predicate (trie_t *trie) +{ + dict_entry_t *entry; + + entry = dict_cursor_resolve (trie); + if (! DICT_ENTRY_IS_WORD (entry)) + return FALSE; + + if (dict_entry_predicate) + return (dict_entry_predicate) (*entry); + + return TRUE; +} + +int +dict_count (dict_t *dict, + dict_entry_predicate_t predicate) +{ + dict_entry_predicate = predicate; + return trie_count (dict, dict_predicate); +} + +int dict_print (dict_t *dict) { + int count; string_t string; string_init (&string); - trie_print (dict, &string, NULL); + dict_entry_predicate = NULL; + count = trie_print (dict, &string, dict_predicate, + 0, 0, -1); string_fini (&string); + + return count; +} + +int +dict_print_if (dict_t *dict, + dict_entry_predicate_t predicate) +{ + int count; + string_t string; + + string_init (&string); + + dict_entry_predicate = predicate; + count = trie_print (dict, &string, dict_predicate, + 0, 0, -1); + + string_fini (&string); + + return count; +} + +int +dict_print_by_length_if (dict_t *dict, + dict_entry_predicate_t predicate) +{ + int length, total, words, count = 0; + string_t string; + + string_init (&string); + + dict_entry_predicate = predicate; + + total = trie_count (dict, dict_predicate); + + length = 1; + do { + words = trie_print (dict, &string, dict_predicate, + 0, length, length); + if (words) { + printf ("\n"); + count += words; + } + length++; + } while (count < total); + + string_fini (&string); + + return count; }