X-Git-Url: https://git.cworth.org/git?a=blobdiff_plain;f=dict.c;h=a9202934035d35346f0ac75905f4baa130fff9ed;hb=ea2a992111737eccb174f26f71ab5357597d5147;hp=98c9476ce08ba09c99043d1c770249e8a3b929ac;hpb=2eb18813b84ae8ad4faeb92b1d8570599135d537;p=wordgame diff --git a/dict.c b/dict.c index 98c9476..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; + +typedef bool_t +(*trie_predicate_t) (trie_t *trie); -void * +#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) @@ -116,7 +126,20 @@ trie_init (trie_t *trie) trie->next[i] = NULL; } -trie_t * +void +trie_destroy (trie_t *trie); + +static void +trie_fini (trie_t *trie) +{ + int i; + + for (i = 0; i < 26; i++) + if (trie->next[i]) + trie_destroy (trie->next[i]); +} + +static trie_t * trie_create (void) { trie_t *trie; @@ -131,35 +154,29 @@ trie_create (void) void trie_destroy (trie_t *trie) { - int i; - - for (i = 0; i < 26; i++) - if (trie->next[i]) - trie_destroy (trie->next[i]); + trie_fini (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) { @@ -171,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) @@ -195,40 +237,39 @@ 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) +void +dict_init (dict_t *dict) { - return (trie->flags & TRIE_FLAGS_SEEN); + trie_init (dict); } -int -trie_print_seen (trie_t *trie, string_t *word) +void +dict_fini (dict_t *dict) { - return trie_print (trie, word, trie_seen_predicate); + trie_fini (dict); } -bool_t -trie_unseen_predicate (trie_t *trie) +void +dict_add_word (dict_t *dict, + const char *word) { - return (! trie_seen_predicate (trie)); -} + trie_t *trie; -int -trie_print_unseen (trie_t *trie, string_t *word) -{ - return trie_print (trie, word, trie_unseen_predicate); + trie = trie_add (dict, word); + trie->flags |= DICT_ENTRY_FLAG_IS_WORD; } void -dict_init (dict_t *dict, - const char *filename) +dict_add_words_from_file (dict_t *dict, + const char *filename) { FILE *file; char *line = NULL; @@ -242,14 +283,12 @@ dict_init (dict_t *dict, exit (1); } - dict->trie = trie_create (); - while (1) { bytes_read = getline (&line, &line_size, file); if (bytes_read == -1) break; chomp (line); - trie_add (dict->trie, line); + dict_add_word (dict, line); } if (line) free (line); @@ -257,20 +296,140 @@ dict_init (dict_t *dict, fclose (file); } -void -dict_fini (dict_t *dict) +dict_entry_t * +dict_lookup (dict_t *dict, + const char *word) { - trie_destroy (dict->trie); + trie_t *trie; + + trie = trie_find (dict, word); + if (trie == NULL) + return NULL; + else + return &trie->flags; } -void +/* Yes, this function is rather silly. I have it here in the hope that + * it could be used for some better type-checking, (if only C had such + * a thing). */ +dict_cursor_t +dict_root (dict_t *dict) +{ + return dict; +} + +dict_cursor_t +dict_cursor_next (dict_cursor_t cursor, + char next) +{ + trie_t *trie = cursor; + + if (trie == NULL) + return DICT_CURSOR_NIL; + + return trie->next[TRIE_CHAR_TO_INDEX (next)]; +} + +dict_entry_t * +dict_cursor_resolve (dict_cursor_t cursor) +{ + trie_t *trie; + + if (cursor == DICT_CURSOR_NIL) + return NULL; + + trie = cursor; + return &trie->flags; +} + +/* 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); + + 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); - trie_print (dict->trie, &string, NULL); + 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; }