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