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