git.cworth.org Git - wordgame/blob - dict.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 #include "dict.h"
  28
  29 void *
  30 xmalloc (size_t size)
  31 {
  32     void *res;
  33
  34     res = malloc (size);
  35     if (res == NULL) {
  36         fprintf (stderr, "Error: out of memory\n");
  37         exit (1);
  38     }
  39
  40     return res;
  41 }
  42
  43 void *
  44 xrealloc (void *ptr, size_t size)
  45 {
  46     void *res;
  47
  48     res = realloc (ptr, size);
  49     if (res == NULL) {
  50         fprintf (stderr, "Error: out of memory\n");
  51         exit (1);
  52     }
  53
  54     return res;
  55 }
  56
  57 void
  58 chomp (char *s)
  59 {
  60     int len = strlen (s);
  61     if (s[len - 1] == '\n')
  62         s[len - 1] = '\0';
  63 }
  64
  65 void
  66 string_init (string_t *string)
  67 {
  68     string->size = 0;
  69     string->s = NULL;
  70     string->len = 0;
  71 }
  72
  73 void
  74 string_fini (string_t *string)
  75 {
  76     string->size = 0;
  77     if (string->s)
  78         free (string->s);
  79     string->len = 0;
  80 }
  81
  82 void
  83 string_append_char (string_t *string, char c)
  84 {
  85     if (string->size == 0) {
  86         string->size = 8;
  87         string->s = xmalloc (string->size);
  88         string->s[0] = '\0';
  89         string->len = 0;
  90     }
  91
  92     if (string->len + 1 == string->size) {
  93         string->size *= 2;
  94         string->s = xrealloc (string->s, string->size);
  95     }
  96
  97     string->s[string->len++] = c;
  98     string->s[string->len] = '\0';
  99 }
 100
 101 void
 102 string_chop (string_t *string)
 103 {
 104     if (string->len == 0)
 105         return;
 106
 107     string->s[--string->len] = '\0';
 108 }
 109
 110 static void
 111 trie_init (trie_t *trie)
 112 {
 113     int i;
 114     trie->flags = 0;
 115     for (i = 0; i < 26; i++)
 116         trie->next[i] = NULL;
 117 }
 118
 119 trie_t *
 120 trie_create (void)
 121 {
 122     trie_t *trie;
 123
 124     trie = xmalloc (sizeof (trie_t));
 125
 126     trie_init (trie);
 127
 128     return trie;
 129 }
 130
 131 void
 132 trie_destroy (trie_t *trie)
 133 {
 134     int i;
 135
 136     for (i = 0; i < 26; i++)
 137         if (trie->next[i])
 138             trie_destroy (trie->next[i]);
 139
 140     free (trie);
 141 }
 142
 143 void
 144 trie_add (trie_t        *trie,
 145           const char    *word_chunk)
 146 {
 147     char c = word_chunk[0];
 148     int i;
 149
 150     if (c == '\0') {
 151         trie->flags |= TRIE_FLAGS_IS_WORD;
 152         return;
 153     }
 154
 155     i = TRIE_CHAR_TO_INDEX (c);
 156     if (trie->next[i] == NULL)
 157         trie->next[i] = trie_create ();
 158
 159     trie_add (trie->next[i], word_chunk + 1);
 160 }
 161
 162 trie_t *
 163 trie_find (trie_t       *trie,
 164            const char   *word_chunk)
 165 {
 166     const char *s = word_chunk;
 167
 168     while (trie && *s)
 169         trie = trie->next[TRIE_CHAR_TO_INDEX (*s++)];
 170
 171     return trie;
 172 }
 173
 174 int
 175 trie_print (trie_t              *trie,
 176             string_t            *string,
 177             trie_predicate_t     predicate)
 178 {
 179     char c;
 180     int i;
 181     int count = 0;
 182
 183     if (trie->flags & TRIE_FLAGS_IS_WORD
 184         && (predicate == NULL || predicate (trie)))
 185     {
 186         count = 1;
 187         printf ("%s ", string->s);
 188     }
 189
 190     /* Loop over each element, appending the character and recursing. */
 191     for (i = 0; i < 26; i++) {
 192         if (trie->next[i] == NULL)
 193             continue;
 194
 195         c = TRIE_INDEX_TO_CHAR (i);
 196
 197         string_append_char (string, c);
 198         count += trie_print (trie->next[i], string, predicate);
 199         string_chop (string);
 200     }
 201
 202     return count;
 203 }
 204
 205 bool_t
 206 trie_seen_predicate (trie_t *trie)
 207 {
 208     return (trie->flags & TRIE_FLAGS_SEEN);
 209 }
 210
 211 int
 212 trie_print_seen (trie_t *trie, string_t *word)
 213 {
 214     return trie_print (trie, word, trie_seen_predicate);
 215 }
 216
 217 bool_t
 218 trie_unseen_predicate (trie_t *trie)
 219 {
 220     return (! trie_seen_predicate (trie));
 221 }
 222
 223 int
 224 trie_print_unseen (trie_t *trie, string_t *word)
 225 {
 226     return trie_print (trie, word, trie_unseen_predicate);
 227 }
 228
 229 void
 230 dict_init (dict_t       *dict,
 231            const char   *filename)
 232 {
 233     FILE *file;
 234     char *line = NULL;
 235     size_t line_size = 0;
 236     ssize_t bytes_read;
 237
 238     file = fopen (filename, "r");
 239     if (file == NULL) {
 240         fprintf (stderr, "Error: failed to open %s: %s\n",
 241                  filename, strerror (errno));
 242         exit (1);
 243     }
 244
 245     dict->trie = trie_create ();
 246
 247     while (1) {
 248         bytes_read = getline (&line, &line_size, file);
 249         if (bytes_read == -1)
 250             break;
 251         chomp (line);
 252         trie_add (dict->trie, line);
 253     }
 254     if (line)
 255         free (line);
 256
 257     fclose (file);
 258 }
 259
 260 void
 261 dict_fini (dict_t *dict)
 262 {
 263     trie_destroy (dict->trie);
 264 }
 265
 266 void
 267 dict_print (dict_t *dict)
 268 {
 269     string_t string;
 270
 271     string_init (&string);
 272
 273     trie_print (dict->trie, &string, NULL);
 274
 275     string_fini (&string);
 276 }