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.

diff --git a/dict.c b/dict.c
index 00d54e04036b79576a4fa2dc155853ee9d663864..715e48f8deaa52c73bf499a3aae856dcc16a1e24 100644 (file)
--- 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 e58c8b4c4e3c992ca82ff67c0c04039af43fc8f1..d87e7659031e3497a1158a94ffde33ed948e82d8 100644 (file)
--- 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 9b0ffbe7eeb30896af40c006dae551373463a70d..44ffa9d23f7487b90a8c0c71f542ae267d364c62 100644 (file)
--- 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);