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_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)
{
void
dict_print (dict_t *dict)
{
/* Only looks opaque. Perfectly stack-allocatable */
typedef trie_t dict_t;
/* 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_init (dict_t *dict);
+void
+dict_fini (dict_t *dict);
+
+/* Adding new words */
void
dict_add_word (dict_t *dict,
const char *word);
void
dict_add_word (dict_t *dict,
const char *word);
dict_add_words_from_file (dict_t *dict,
const char *filename);
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
int y,
int16_t seen,
string_t *word,
int y,
int16_t seen,
string_t *word,
+ dict_cursor_t dict_cursor)
+ if (dict_cursor == DICT_CURSOR_NIL)
+ return;
+
if (x < 0 || x >= 4 ||
y < 0 || y >= 4 ||
seen & SEEN_BIT (x, y))
if (x < 0 || x >= 4 ||
y < 0 || y >= 4 ||
seen & SEEN_BIT (x, y))
c = board->letters[y][x];
string_append_char (word, c);
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');
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++)
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);
if (c == 'q')
string_chop (word);
if (c == 'q')
string_chop (word);
for (y = 0; y < 4; y++)
for (x = 0; x < 4; x++)
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));
if (strlen (response) == 0) {
board_print (&board);
} else {
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
printf ("(repeat)\n");
else
- t->flags |= TRIE_FLAGS_SEEN;
+ *entry |= TRIE_FLAGS_SEEN;
- 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);
printf ("(a good word, but it's not in the puzzle)\n");
else
printf ("*** %s is not a word\n", response);