git.cworth.org Git - wordgame/blob - wordgame.c

   1 /*
   2  * Copyright © 2006 Carl Worth
   3  *
   4  * This program is free software; you can redistribute it and\/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation; either version 2, or (at your option)
   7  * any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software Foundation,
  16  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA."
  17  */
  18
  19 /* Portably, schmortability. I want ease of programming. */
  20 #define _GNU_SOURCE
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <string.h>
  24 #include <errno.h>
  25 #include <ctype.h>
  26
  27 #ifndef FALSE
  28 # define FALSE 0
  29 #endif
  30
  31 #ifndef TRUE
  32 # define TRUE 1
  33 #endif
  34
  35 typedef int bool_t;
  36
  37 typedef struct _trie {
  38     bool_t is_word;
  39     struct _trie *next[26];
  40 } trie_t;
  41
  42 void *
  43 xmalloc (size_t size)
  44 {
  45     void *res;
  46
  47     res = malloc (size);
  48     if (res == NULL) {
  49         fprintf (stderr, "Error: out of memory\n");
  50         exit (1);
  51     }
  52
  53     return res;
  54 }
  55
  56 void *
  57 xrealloc (void *ptr, size_t size)
  58 {
  59     void *res;
  60
  61     res = realloc (ptr, size);
  62     if (res == NULL) {
  63         fprintf (stderr, "Error: out of memory\n");
  64         exit (1);
  65     }
  66
  67     return res;
  68 }
  69
  70 static void
  71 trie_init (trie_t *trie)
  72 {
  73     int i;
  74     trie->is_word = FALSE;
  75     for (i = 0; i < 26; i++)
  76         trie->next[i] = NULL;
  77 }
  78
  79 trie_t *
  80 trie_create (void)
  81 {
  82     trie_t *trie;
  83
  84     trie = xmalloc (sizeof (trie_t));
  85
  86     trie_init (trie);
  87
  88     return trie;
  89 }
  90
  91 void
  92 trie_destroy (trie_t *trie)
  93 {
  94     int i;
  95
  96     for (i = 0; i < 26; i++)
  97         if (trie->next[i])
  98             trie_destroy (trie->next[i]);
  99
 100     free (trie);
 101 }
 102
 103 #define TRIE_CHAR_TO_INDEX(c)   (tolower (c) - 'a')
 104 #define TRIE_INDEX_TO_CHAR(i)   (i + 'a')
 105 void
 106 trie_add (trie_t        *trie,
 107           const char    *word_chunk)
 108 {
 109     char c = word_chunk[0];
 110     int i;
 111
 112     if (c == '\0') {
 113         trie->is_word = TRUE;
 114         return;
 115     }
 116
 117     i = TRIE_CHAR_TO_INDEX (c);
 118     if (trie->next[i] == NULL)
 119         trie->next[i] = trie_create ();
 120
 121     trie_add (trie->next[i], word_chunk + 1);
 122 }
 123
 124 bool_t
 125 trie_contains (trie_t           *trie,
 126                const char       *word_chunk)
 127 {
 128     char c = word_chunk[0];
 129     int i;
 130
 131     if (c == '\0')
 132         return trie->is_word;
 133
 134     i = TRIE_CHAR_TO_INDEX (c);
 135     if (trie->next[i] == NULL)
 136         return FALSE;
 137
 138     return trie_contains (trie->next[i], word_chunk + 1);
 139 }
 140
 141 void
 142 trie_print (trie_t      *trie,
 143             char        **str,
 144             size_t      *str_size)
 145 {
 146     char c;
 147     int i;
 148     size_t str_len;
 149
 150     if (trie->is_word && *str)
 151         printf ("%s\n", *str);
 152
 153     /* Make room for the extra character. */
 154     if (*str == NULL) {
 155         *str_size = 8;
 156         *str = xmalloc (*str_size);
 157         (*str)[0] = '\0';
 158     }
 159
 160     str_len = strlen (*str);
 161
 162     if (str_len + 1 == *str_size) {
 163         *str_size *= 2;
 164         *str = xrealloc (*str, *str_size);
 165     }
 166
 167     (*str)[str_len + 1] = '\0';
 168
 169     /* Loop over each element, appending the character and recursing. */
 170     for (i = 0; i < 26; i++) {
 171         if (trie->next[i] == NULL)
 172             continue;
 173
 174         c = TRIE_INDEX_TO_CHAR (i);
 175
 176         (*str)[str_len] = c;
 177         trie_print (trie->next[i], str, str_size);
 178     }
 179
 180     (*str)[str_len] = '\0';
 181 }
 182
 183 void
 184 chomp (char *str)
 185 {
 186     if (str[strlen (str) - 1] == '\n')
 187         str[strlen (str) - 1] = '\0';
 188 }
 189
 190 typedef struct _dict {
 191     trie_t *trie;
 192 } dict_t;
 193
 194 void
 195 dict_init (dict_t       *dict,
 196            const char   *filename)
 197 {
 198     FILE *file;
 199     char *line = NULL;
 200     size_t line_size = 0;
 201     ssize_t bytes_read;
 202
 203     file = fopen (filename, "r");
 204     if (file == NULL) {
 205         fprintf (stderr, "Error: failed to open %s: %s\n",
 206                  filename, strerror (errno));
 207         exit (1);
 208     }
 209
 210     dict->trie = trie_create ();
 211
 212     while (1) {
 213         bytes_read = getline (&line, &line_size, file);
 214         if (bytes_read == -1)
 215             break;
 216         chomp (line);
 217         trie_add (dict->trie, line);
 218     }
 219     if (line)
 220         free (line);
 221 }
 222
 223 void
 224 dict_print (dict_t *dict)
 225 {
 226     char *str = NULL;
 227     size_t str_size = 0;
 228
 229     trie_print (dict->trie, &str, &str_size);
 230     if (str)
 231         free (str);
 232 }
 233
 234 int
 235 main (void)
 236 {
 237     dict_t dict;
 238
 239     dict_init (&dict, "words.txt");
 240     dict_print (&dict);
 241
 242     return 0;
 243 }
 244