X-Git-Url: https://git.cworth.org/git?p=wordgame;a=blobdiff_plain;f=dict.c;h=68703dafc603bf377ae3688f1dff78e0a7028cb0;hp=a3f088f0e084277416ce6ba3bd754cdee5abfacb;hb=HEAD;hpb=17755d5a91f1470057bf2308984a25e7432bcd8a diff --git a/dict.c b/dict.c index a3f088f..68703da 100644 --- a/dict.c +++ b/dict.c @@ -1,7 +1,7 @@ /* * Copyright © 2006 Carl Worth * - * This program is free software; you can redistribute it and\/or modify + * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2, or (at your option) * any later version. @@ -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); + +#define TRIE_CHAR_TO_INDEX(c) (tolower (c) - 'a') +#define TRIE_INDEX_TO_CHAR(i) (i + 'a') -void * +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,52 @@ trie_find (trie_t *trie, return trie; } -int -trie_print (trie_t *trie, - string_t *string, - trie_predicate_t predicate) +static int +trie_count_if (trie_t *trie, + trie_predicate_t predicate) +{ + int i; + int count = 0; + + if (predicate == NULL || (predicate) (trie)) + count = 1; + + for (i = 0; i < 26; i++) { + if (trie->next[i] == NULL) + continue; + + count += trie_count_if (trie->next[i], predicate); + } + + return count; +} + +static int +trie_for_each_of_length_if (trie_t *trie, + dict_action_t action, + void *closure, + int min_length, + int max_length, + trie_predicate_t predicate, + string_t *string, + int 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 (action) + action (closure, string->s, &trie->flags); } + if (max_length > 0 && 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,41 +242,37 @@ 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_for_each_of_length_if (trie->next[i], + action, closure, + min_length, max_length, + predicate, + string, length + 1); 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) +void +dict_init (dict_t *dict) { - return (! trie_seen_predicate (trie)); + trie_init (dict); } -int -trie_print_unseen (trie_t *trie, string_t *word) +void +dict_fini (dict_t *dict) { - return trie_print (trie, word, trie_unseen_predicate); + trie_fini (dict); } void -dict_init (dict_t *dict) +dict_add_word (dict_t *dict, + const char *word) { - dict->trie = trie_create (); + trie_t *trie; + + trie = trie_add (dict, word); + trie->flags |= DICT_ENTRY_FLAG_IS_WORD; } void @@ -253,7 +296,7 @@ dict_add_words_from_file (dict_t *dict, if (bytes_read == -1) break; chomp (line); - trie_add (dict->trie, line); + dict_add_word (dict, line); } if (line) free (line); @@ -261,20 +304,211 @@ dict_add_words_from_file (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 -dict_print (dict_t *dict) +/* 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_if (dict_t *dict, + dict_entry_predicate_t predicate) +{ + dict_entry_predicate = predicate; + return trie_count_if (dict, dict_predicate); +} + +int +dict_count (dict_t *dict) { + return dict_count_if (dict, NULL); +} + +int +dict_for_each_of_length_if (dict_t *dict, + dict_action_t action, + void *closure, + int min_length, + int max_length, + 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_for_each_of_length_if (dict, + action, closure, + min_length, max_length, + dict_predicate, + &string, 0); string_fini (&string); + + return count; +} + +int +dict_for_each_of_length (dict_t *dict, + dict_action_t action, + void *closure, + int min_length, + int max_length) +{ + return dict_for_each_of_length_if (dict, + action, closure, + min_length, max_length, + NULL); +} + +int +dict_for_each_if (dict_t *dict, + dict_action_t action, + void *closure, + dict_entry_predicate_t predicate) + +{ + return dict_for_each_of_length_if (dict, + action, closure, + 0, 0, + predicate); +} + +int +dict_for_each (dict_t *dict, + dict_action_t action, + void *closure) +{ + return dict_for_each_if (dict, action, closure, NULL); +} + +static void +dict_action_print (void *closure, char *word, dict_entry_t *entry) +{ + int *first = closure; + + if (*first) + *first = 0; + else + printf(" "); + + printf ("%s", word); +} + +int +dict_print_of_length_if (dict_t *dict, + int min_length, + int max_length, + dict_entry_predicate_t predicate) +{ + int first = TRUE; + + return dict_for_each_of_length_if (dict, + dict_action_print, &first, + min_length, max_length, + predicate); +} + +int +dict_print_by_length_if (dict_t *dict, + dict_entry_predicate_t predicate) +{ + int length, total, words, count = 0; + + total = dict_count_if (dict, predicate); + + length = 1; + do { + words = dict_print_of_length_if (dict, length, length, predicate); + if (words) { + count += words; + printf ("\n"); + } + length++; + } while (count < total); + + return count; +} + +int +dict_print_of_length (dict_t *dict, + int min_length, + int max_length) +{ + return dict_print_of_length_if (dict, min_length, max_length, NULL); +} + +int +dict_print_if (dict_t *dict, + dict_entry_predicate_t predicate) +{ + return dict_print_of_length_if (dict, 0, 0, predicate); +} + +int +dict_print (dict_t *dict) +{ + return dict_print_if (dict, NULL); }