From dd4b319cdb6e2883ae76317036b57b670344160a Mon Sep 17 00:00:00 2001 From: Carl Worth Date: Thu, 21 Sep 2006 00:36:10 -0700 Subject: [PATCH] Complete the dict layer by adding dict_cursor_t and dict_entry_t Some might argue that this is a gratuitous layer and that it hides the elegance of the trie implementation where pointers to the entire structure and pointers to a single node are equivalent. But I think the elegance is still all there in the implementation, and I think there's some real benefit in making separate notions of the entire structure (dict_t) and a pointer to a single element for navigating (dict_cursor_t) since the operations one might want to perform on one or the other are entirely separate. With this change, the only remaining dependence of grid.c on any trie or TRIE symbols is a single flag definition (which I want to put entirely in grid.c) and the print functionality. --- dict.c | 46 ++++++++++++++++++++++++++++++++++++++++++++++ dict.h | 31 +++++++++++++++++++++++++++++-- grid.c | 35 ++++++++++++++++------------------- 3 files changed, 91 insertions(+), 21 deletions(-) diff --git a/dict.c b/dict.c index 00d54e0..715e48f 100644 --- a/dict.c +++ b/dict.c @@ -283,6 +283,52 @@ dict_add_words_from_file (dict_t *dict, fclose (file); } +dict_entry_t * +dict_lookup (dict_t *dict, + const char *word) +{ + trie_t *trie; + + trie = trie_find (dict, word); + if (trie == NULL) + return NULL; + else + return &trie->flags; +} + +/* 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; +} + void dict_print (dict_t *dict) { diff --git a/dict.h b/dict.h index e58c8b4..d87e765 100644 --- a/dict.h +++ b/dict.h @@ -23,10 +23,17 @@ /* Only looks opaque. Perfectly stack-allocatable */ typedef trie_t dict_t; +typedef trie_t *dict_cursor_t; +typedef uint32_t dict_entry_t; +/* Initialization and cleanup */ void dict_init (dict_t *dict); +void +dict_fini (dict_t *dict); + +/* Adding new words */ void dict_add_word (dict_t *dict, const char *word); @@ -34,7 +41,27 @@ void dict_add_words_from_file (dict_t *dict, const char *filename); -void -dict_fini (dict_t *dict); +/* Looking up an entry in the dictionary */ +dict_entry_t * +dict_lookup (dict_t *dict, + const char *word); + +/* Querying a dictionary entry. The dict interface uses 1 bit. + * All of the remaining bits are available for application use. + */ +#define DICT_ENTRY_IS_WORD(entry) ((entry) && ((*entry) & 0x01)) + +/* Character-by-character perusal of the dictionary */ +dict_cursor_t +dict_root (dict_t *dict); + +dict_cursor_t +dict_cursor_next (dict_cursor_t cursor, + char next); + +dict_entry_t * +dict_cursor_resolve (dict_cursor_t cursor); + +#define DICT_CURSOR_NIL NULL #endif /* _DICT_H_ */ diff --git a/grid.c b/grid.c index 9b0ffbe..44ffa9d 100644 --- a/grid.c +++ b/grid.c @@ -101,11 +101,14 @@ board_enumerate (board_t *board, int y, int16_t seen, string_t *word, - trie_t *dict_trie) + dict_cursor_t dict_cursor) { char c; int dx, dy; + if (dict_cursor == DICT_CURSOR_NIL) + return; + if (x < 0 || x >= 4 || y < 0 || y >= 4 || seen & SEEN_BIT (x, y)) @@ -117,28 +120,22 @@ board_enumerate (board_t *board, c = board->letters[y][x]; string_append_char (word, c); - dict_trie = dict_trie->next[TRIE_CHAR_TO_INDEX (c)]; - if (dict_trie == NULL) - goto BAIL0; + dict_cursor = dict_cursor_next (dict_cursor, c); if (c == 'q') { string_append_char (word, 'u'); - dict_trie = dict_trie->next[TRIE_CHAR_TO_INDEX ('u')]; - if (dict_trie == NULL) - goto BAIL1; + dict_cursor = dict_cursor_next (dict_cursor, 'u'); } - if (dict_trie->flags & TRIE_FLAGS_IS_WORD) + if (DICT_ENTRY_IS_WORD (dict_cursor_resolve (dict_cursor))) dict_add_word (board->results, word->s); for (dy = -1; dy <= 1; dy++) for (dx = -1; dx <= 1; dx++) - board_enumerate (board, x + dx, y + dy, seen, word, dict_trie); + board_enumerate (board, x + dx, y + dy, seen, word, dict_cursor); - BAIL1: if (c == 'q') string_chop (word); - BAIL0: string_chop (word); } @@ -155,7 +152,7 @@ board_solve (board_t *board, dict_t *dict, dict_t *solution) for (y = 0; y < 4; y++) for (x = 0; x < 4; x++) - board_enumerate (board, x, y, seen, &word, dict); + board_enumerate (board, x, y, seen, &word, dict_root (dict)); string_fini (&word); } @@ -198,16 +195,16 @@ main (void) if (strlen (response) == 0) { board_print (&board); } else { - trie_t *t; - t = trie_find (&solution, response); - if (t && (t->flags & TRIE_FLAGS_IS_WORD)) { - if (t->flags & TRIE_FLAGS_SEEN) + dict_entry_t *entry; + entry = dict_lookup (&solution, response); + if (DICT_ENTRY_IS_WORD (entry)) { + if (*entry & TRIE_FLAGS_SEEN) printf ("(repeat)\n"); else - t->flags |= TRIE_FLAGS_SEEN; + *entry |= TRIE_FLAGS_SEEN; } else { - t = trie_find (&dict, response); - if (t && (t->flags & TRIE_FLAGS_IS_WORD)) + entry = dict_lookup (&dict, response); + if (DICT_ENTRY_IS_WORD (entry)) printf ("(a good word, but it's not in the puzzle)\n"); else printf ("*** %s is not a word\n", response); -- 2.43.0