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 #include "dict.h"
  20
  21 #include <string.h>
  22 #include <errno.h>
  23 #include <ctype.h>
  24
  25 typedef struct _string {
  26     size_t size;
  27     char *s;
  28     size_t len;
  29 } string_t;
  30
  31 typedef bool_t
  32 (*trie_predicate_t) (trie_t *trie);
  33
  34 #define TRIE_CHAR_TO_INDEX(c)   (tolower (c) - 'a')
  35 #define TRIE_INDEX_TO_CHAR(i)   (i + 'a')
  36
  37 static void *
  38 xmalloc (size_t size)
  39 {
  40     void *res;
  41
  42     res = malloc (size);
  43     if (res == NULL) {
  44         fprintf (stderr, "Error: out of memory\n");
  45         exit (1);
  46     }
  47
  48     return res;
  49 }
  50
  51 static void *
  52 xrealloc (void *ptr, size_t size)
  53 {
  54     void *res;
  55
  56     res = realloc (ptr, size);
  57     if (res == NULL) {
  58         fprintf (stderr, "Error: out of memory\n");
  59         exit (1);
  60     }
  61
  62     return res;
  63 }
  64
  65 static void
  66 chomp (char *s)
  67 {
  68     int len = strlen (s);
  69     if (len == 0)
  70         return;
  71     if (s[len - 1] == '\n')
  72         s[len - 1] = '\0';
  73 }
  74
  75 static void
  76 string_init (string_t *string)
  77 {
  78     string->size = 0;
  79     string->s = NULL;
  80     string->len = 0;
  81 }
  82
  83 static void
  84 string_fini (string_t *string)
  85 {
  86     string->size = 0;
  87     if (string->s)
  88         free (string->s);
  89     string->len = 0;
  90 }
  91
  92 static void
  93 string_append_char (string_t *string, char c)
  94 {
  95     if (string->size == 0) {
  96         string->size = 8;
  97         string->s = xmalloc (string->size);
  98         string->s[0] = '\0';
  99         string->len = 0;
 100     }
 101
 102     if (string->len + 1 == string->size) {
 103         string->size *= 2;
 104         string->s = xrealloc (string->s, string->size);
 105     }
 106
 107     string->s[string->len++] = c;
 108     string->s[string->len] = '\0';
 109 }
 110
 111 static void
 112 string_chop (string_t *string)
 113 {
 114     if (string->len == 0)
 115         return;
 116
 117     string->s[--string->len] = '\0';
 118 }
 119
 120 static void
 121 trie_init (trie_t *trie)
 122 {
 123     int i;
 124     trie->flags = 0;
 125     for (i = 0; i < 26; i++)
 126         trie->next[i] = NULL;
 127 }
 128
 129 void
 130 trie_destroy (trie_t *trie);
 131
 132 static void
 133 trie_fini (trie_t *trie)
 134 {
 135     int i;
 136
 137     for (i = 0; i < 26; i++)
 138         if (trie->next[i])
 139             trie_destroy (trie->next[i]);
 140 }
 141
 142 static trie_t *
 143 trie_create (void)
 144 {
 145     trie_t *trie;
 146
 147     trie = xmalloc (sizeof (trie_t));
 148
 149     trie_init (trie);
 150
 151     return trie;
 152 }
 153
 154 void
 155 trie_destroy (trie_t *trie)
 156 {
 157     trie_fini (trie);
 158
 159     free (trie);
 160 }
 161
 162 static trie_t *
 163 trie_add (trie_t        *trie,
 164           const char    *word_chunk)
 165 {
 166     char c = word_chunk[0];
 167     int i;
 168
 169     if (c == '\0')
 170         return trie;
 171
 172     i = TRIE_CHAR_TO_INDEX (c);
 173     if (trie->next[i] == NULL)
 174         trie->next[i] = trie_create ();
 175
 176     return trie_add (trie->next[i], word_chunk + 1);
 177 }
 178
 179 static trie_t *
 180 trie_find (trie_t       *trie,
 181            const char   *word_chunk)
 182 {
 183     const char *s = word_chunk;
 184
 185     while (trie && *s)
 186         trie = trie->next[TRIE_CHAR_TO_INDEX (*s++)];
 187
 188     return trie;
 189 }
 190
 191 static int
 192 trie_count (trie_t              *trie,
 193             trie_predicate_t     predicate)
 194 {
 195     int i;
 196     int count = 0;
 197
 198     if ((predicate) (trie))
 199         count = 1;
 200
 201     for (i = 0; i < 26; i++) {
 202         if (trie->next[i] == NULL)
 203             continue;
 204
 205         count += trie_count (trie->next[i], predicate);
 206     }
 207
 208     return count;
 209 }
 210
 211 static int
 212 trie_print (trie_t              *trie,
 213             string_t            *string,
 214             trie_predicate_t     predicate,
 215             int                  length,
 216             int                  min_length,
 217             int                  max_length)
 218 {
 219     char c;
 220     int i;
 221     int count = 0;
 222
 223     if (length >= min_length && (predicate) (trie))
 224     {
 225         count = 1;
 226         printf ("%s ", string->s);
 227     }
 228
 229     if (length == max_length)
 230         return count;
 231
 232     /* Loop over each element, appending the character and recursing. */
 233     for (i = 0; i < 26; i++) {
 234         if (trie->next[i] == NULL)
 235             continue;
 236
 237         c = TRIE_INDEX_TO_CHAR (i);
 238
 239         string_append_char (string, c);
 240         count += trie_print (trie->next[i], string, predicate,
 241                              length + 1, min_length, max_length);
 242         string_chop (string);
 243     }
 244
 245     return count;
 246 }
 247
 248 void
 249 dict_init (dict_t *dict)
 250 {
 251     trie_init (dict);
 252 }
 253
 254 void
 255 dict_fini (dict_t *dict)
 256 {
 257     trie_fini (dict);
 258 }
 259
 260 void
 261 dict_add_word (dict_t           *dict,
 262                const char       *word)
 263 {
 264     trie_t *trie;
 265
 266     trie = trie_add (dict, word);
 267     trie->flags |= DICT_ENTRY_FLAG_IS_WORD;
 268 }
 269
 270 void
 271 dict_add_words_from_file (dict_t        *dict,
 272                           const char    *filename)
 273 {
 274     FILE *file;
 275     char *line = NULL;
 276     size_t line_size = 0;
 277     ssize_t bytes_read;
 278
 279     file = fopen (filename, "r");
 280     if (file == NULL) {
 281         fprintf (stderr, "Error: failed to open %s: %s\n",
 282                  filename, strerror (errno));
 283         exit (1);
 284     }
 285
 286     while (1) {
 287         bytes_read = getline (&line, &line_size, file);
 288         if (bytes_read == -1)
 289             break;
 290         chomp (line);
 291         dict_add_word (dict, line);
 292     }
 293     if (line)
 294         free (line);
 295
 296     fclose (file);
 297 }
 298
 299 dict_entry_t *
 300 dict_lookup (dict_t     *dict,
 301              const char *word)
 302 {
 303     trie_t *trie;
 304
 305     trie = trie_find (dict, word);
 306     if (trie == NULL)
 307         return NULL;
 308     else
 309         return &trie->flags;
 310 }
 311
 312 /* Yes, this function is rather silly. I have it here in the hope that
 313  * it could be used for some better type-checking, (if only C had such
 314  * a thing). */
 315 dict_cursor_t
 316 dict_root (dict_t *dict)
 317 {
 318     return dict;
 319 }
 320
 321 dict_cursor_t
 322 dict_cursor_next (dict_cursor_t cursor,
 323                   char          next)
 324 {
 325     trie_t *trie = cursor;
 326
 327     if (trie == NULL)
 328         return DICT_CURSOR_NIL;
 329
 330     return trie->next[TRIE_CHAR_TO_INDEX (next)];
 331 }
 332
 333 dict_entry_t *
 334 dict_cursor_resolve (dict_cursor_t cursor)
 335 {
 336     trie_t *trie;
 337
 338     if (cursor == DICT_CURSOR_NIL)
 339         return NULL;
 340
 341     trie = cursor;
 342     return &trie->flags;
 343 }
 344
 345 /* XXX: This static function pointer is really nasty and definitely
 346  * un-thread safe. What I really want it a lambda so I can construct a
 347  * composite predicate on the fly. Oh well... */
 348 static dict_entry_predicate_t dict_entry_predicate = NULL;
 349
 350 static bool_t
 351 dict_predicate (trie_t *trie)
 352 {
 353     dict_entry_t *entry;
 354
 355     entry = dict_cursor_resolve (trie);
 356     if (! DICT_ENTRY_IS_WORD (entry))
 357         return FALSE;
 358
 359     if (dict_entry_predicate)
 360         return (dict_entry_predicate) (*entry);
 361
 362     return TRUE;
 363 }
 364
 365 int
 366 dict_count (dict_t                      *dict,
 367             dict_entry_predicate_t       predicate)
 368 {
 369     dict_entry_predicate = predicate;
 370     return  trie_count (dict, dict_predicate);
 371 }
 372
 373 int
 374 dict_print (dict_t *dict)
 375 {
 376     int count;
 377     string_t string;
 378
 379     string_init (&string);
 380
 381     dict_entry_predicate = NULL;
 382     count = trie_print (dict, &string, dict_predicate,
 383                         0, 0, -1);
 384
 385     string_fini (&string);
 386
 387     return count;
 388 }
 389
 390 int
 391 dict_print_if (dict_t                   *dict,
 392                dict_entry_predicate_t    predicate)
 393 {
 394     int count;
 395     string_t string;
 396
 397     string_init (&string);
 398
 399     dict_entry_predicate = predicate;
 400     count = trie_print (dict, &string, dict_predicate,
 401                         0, 0, -1);
 402
 403     string_fini (&string);
 404
 405     return count;
 406 }
 407
 408 int
 409 dict_print_by_length_if (dict_t                 *dict,
 410                          dict_entry_predicate_t  predicate)
 411 {
 412     int length, total, words, count = 0;
 413     string_t string;
 414
 415     string_init (&string);
 416
 417     dict_entry_predicate = predicate;
 418
 419     total = trie_count (dict, dict_predicate);
 420
 421     length = 1;
 422     do {
 423         words = trie_print (dict, &string, dict_predicate,
 424                             0, length, length);
 425         if (words) {
 426             printf ("\n");
 427             count += words;
 428         }
 429         length++;
 430     } while (count < total);
 431
 432     string_fini (&string);
 433
 434     return count;
 435 }