Break wordgame.c into dict.c and grid.c in preparation for more programs

[wordgame] / dict.c

diff --git a/dict.c b/dict.c
new file mode 100644 (file)
index 0000000..98c9476
--- /dev/null
+++ b/dict.c
@@ -0,0 +1,276 @@
+/*
+ * Copyright © 2006 Carl Worth
+ *
+ * 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.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA."
+ */
+
+/* Portably, schmortability. I want ease of programming. */
+#define _GNU_SOURCE
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <errno.h>
+#include <ctype.h>
+
+#include "dict.h"
+
+void *
+xmalloc (size_t size)
+{
+    void *res;
+
+    res = malloc (size);
+    if (res == NULL) {
+       fprintf (stderr, "Error: out of memory\n");
+       exit (1);
+    }
+
+    return res;
+}
+
+void *
+xrealloc (void *ptr, size_t size)
+{
+    void *res;
+
+    res = realloc (ptr, size);
+    if (res == NULL) {
+       fprintf (stderr, "Error: out of memory\n");
+       exit (1);
+    }
+
+    return res;
+}
+
+void
+chomp (char *s)
+{
+    int len = strlen (s);
+    if (s[len - 1] == '\n')
+       s[len - 1] = '\0';
+}
+
+void
+string_init (string_t *string)
+{
+    string->size = 0;
+    string->s = NULL;
+    string->len = 0;
+}
+
+void
+string_fini (string_t *string)
+{
+    string->size = 0;
+    if (string->s)
+       free (string->s);
+    string->len = 0;
+}
+
+void
+string_append_char (string_t *string, char c)
+{
+    if (string->size == 0) {
+       string->size = 8;
+       string->s = xmalloc (string->size);
+       string->s[0] = '\0';
+       string->len = 0;
+    }
+
+    if (string->len + 1 == string->size) {
+       string->size *= 2;
+       string->s = xrealloc (string->s, string->size);
+    }
+
+    string->s[string->len++] = c;
+    string->s[string->len] = '\0';
+}
+
+void
+string_chop (string_t *string)
+{
+    if (string->len == 0)
+       return;
+
+    string->s[--string->len] = '\0';
+}
+
+static void
+trie_init (trie_t *trie)
+{
+    int i;
+    trie->flags = 0;
+    for (i = 0; i < 26; i++)
+       trie->next[i] = NULL;
+}
+
+trie_t *
+trie_create (void)
+{
+    trie_t *trie;
+
+    trie = xmalloc (sizeof (trie_t));
+
+    trie_init (trie);
+
+    return trie;
+}
+
+void
+trie_destroy (trie_t *trie)
+{
+    int i;
+
+    for (i = 0; i < 26; i++)
+       if (trie->next[i])
+           trie_destroy (trie->next[i]);
+
+    free (trie);
+}
+
+void
+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;
+    }
+
+    i = TRIE_CHAR_TO_INDEX (c);
+    if (trie->next[i] == NULL)
+       trie->next[i] = trie_create ();
+
+    trie_add (trie->next[i], word_chunk + 1);
+}
+
+trie_t *
+trie_find (trie_t      *trie,
+          const char   *word_chunk)
+{
+    const char *s = word_chunk;
+
+    while (trie && *s)
+       trie = trie->next[TRIE_CHAR_TO_INDEX (*s++)];
+
+    return trie;
+}
+
+int
+trie_print (trie_t             *trie,
+           string_t            *string,
+           trie_predicate_t     predicate)
+{
+    char c;
+    int i;
+    int count = 0;
+
+    if (trie->flags & TRIE_FLAGS_IS_WORD
+       && (predicate == NULL || predicate (trie)))
+    {
+       count = 1;
+       printf ("%s ", string->s);
+    }
+
+    /* Loop over each element, appending the character and recursing. */
+    for (i = 0; i < 26; i++) {
+       if (trie->next[i] == NULL)
+           continue;
+
+       c = TRIE_INDEX_TO_CHAR (i);
+
+       string_append_char (string, c);
+       count += trie_print (trie->next[i], string, predicate);
+       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)
+{
+    return (! trie_seen_predicate (trie));
+}
+
+int
+trie_print_unseen (trie_t *trie, string_t *word)
+{
+    return trie_print (trie, word, trie_unseen_predicate);
+}
+
+void
+dict_init (dict_t      *dict,
+          const char   *filename)
+{
+    FILE *file;
+    char *line = NULL;
+    size_t line_size = 0;
+    ssize_t bytes_read;
+
+    file = fopen (filename, "r");
+    if (file == NULL) {
+       fprintf (stderr, "Error: failed to open %s: %s\n",
+                filename, strerror (errno));
+       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);
+    }
+    if (line)
+       free (line);
+
+    fclose (file);
+}
+
+void
+dict_fini (dict_t *dict)
+{
+    trie_destroy (dict->trie);
+}
+
+void
+dict_print (dict_t *dict)
+{
+    string_t string;
+
+    string_init (&string);
+
+    trie_print (dict->trie, &string, NULL);
+
+    string_fini (&string);
+}