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_if (trie_t           *trie,
 193                trie_predicate_t  predicate)
 194 {
 195     int i;
 196     int count = 0;
 197
 198     if (predicate == NULL || (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_if (trie->next[i], predicate);
 206     }
 207
 208     return count;
 209 }
 210
 211 static int
 212 trie_for_each_of_length_if (trie_t              *trie,
 213                             dict_action_t        action,
 214                             void                *closure,
 215                             int                  min_length,
 216                             int                  max_length,
 217                             trie_predicate_t     predicate,
 218                             string_t            *string,
 219                             int                  length)
 220
 221 {
 222     char c;
 223     int i;
 224     int count = 0;
 225
 226     if (length >= min_length && (predicate) (trie))
 227     {
 228         count = 1;
 229
 230         if (action)
 231             action (closure, string->s, &trie->flags);
 232     }
 233
 234     if (max_length > 0 && length == max_length)
 235         return count;
 236
 237     /* Loop over each element, appending the character and recursing. */
 238     for (i = 0; i < 26; i++) {
 239         if (trie->next[i] == NULL)
 240             continue;
 241
 242         c = TRIE_INDEX_TO_CHAR (i);
 243
 244         string_append_char (string, c);
 245         count += trie_for_each_of_length_if (trie->next[i],
 246                                              action, closure,
 247                                              min_length, max_length,
 248                                              predicate,
 249                                              string, length + 1);
 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_t *trie;
 273
 274     trie = trie_add (dict, word);
 275     trie->flags |= DICT_ENTRY_FLAG_IS_WORD;
 276 }
 277
 278 void
 279 dict_add_words_from_file (dict_t        *dict,
 280                           const char    *filename)
 281 {
 282     FILE *file;
 283     char *line = NULL;
 284     size_t line_size = 0;
 285     ssize_t bytes_read;
 286
 287     file = fopen (filename, "r");
 288     if (file == NULL) {
 289         fprintf (stderr, "Error: failed to open %s: %s\n",
 290                  filename, strerror (errno));
 291         exit (1);
 292     }
 293
 294     while (1) {
 295         bytes_read = getline (&line, &line_size, file);
 296         if (bytes_read == -1)
 297             break;
 298         chomp (line);
 299         dict_add_word (dict, line);
 300     }
 301     if (line)
 302         free (line);
 303
 304     fclose (file);
 305 }
 306
 307 dict_entry_t *
 308 dict_lookup (dict_t     *dict,
 309              const char *word)
 310 {
 311     trie_t *trie;
 312
 313     trie = trie_find (dict, word);
 314     if (trie == NULL)
 315         return NULL;
 316     else
 317         return &trie->flags;
 318 }
 319
 320 /* Yes, this function is rather silly. I have it here in the hope that
 321  * it could be used for some better type-checking, (if only C had such
 322  * a thing). */
 323 dict_cursor_t
 324 dict_root (dict_t *dict)
 325 {
 326     return dict;
 327 }
 328
 329 dict_cursor_t
 330 dict_cursor_next (dict_cursor_t cursor,
 331                   char          next)
 332 {
 333     trie_t *trie = cursor;
 334
 335     if (trie == NULL)
 336         return DICT_CURSOR_NIL;
 337
 338     return trie->next[TRIE_CHAR_TO_INDEX (next)];
 339 }
 340
 341 dict_entry_t *
 342 dict_cursor_resolve (dict_cursor_t cursor)
 343 {
 344     trie_t *trie;
 345
 346     if (cursor == DICT_CURSOR_NIL)
 347         return NULL;
 348
 349     trie = cursor;
 350     return &trie->flags;
 351 }
 352
 353 /* XXX: This static function pointer is really nasty and definitely
 354  * un-thread safe. What I really want it a lambda so I can construct a
 355  * composite predicate on the fly. Oh well... */
 356 static dict_entry_predicate_t dict_entry_predicate = NULL;
 357
 358 static bool_t
 359 dict_predicate (trie_t *trie)
 360 {
 361     dict_entry_t *entry;
 362
 363     entry = dict_cursor_resolve (trie);
 364     if (! DICT_ENTRY_IS_WORD (entry))
 365         return FALSE;
 366
 367     if (dict_entry_predicate)
 368         return (dict_entry_predicate) (*entry);
 369
 370     return TRUE;
 371 }
 372
 373 int
 374 dict_count_if (dict_t                   *dict,
 375                dict_entry_predicate_t    predicate)
 376 {
 377     dict_entry_predicate = predicate;
 378     return  trie_count_if (dict, dict_predicate);
 379 }
 380
 381 int
 382 dict_count (dict_t *dict)
 383 {
 384     return dict_count_if (dict, NULL);
 385 }
 386
 387 int
 388 dict_for_each_of_length_if (dict_t                      *dict,
 389                             dict_action_t                action,
 390                             void                        *closure,
 391                             int                          min_length,
 392                             int                          max_length,
 393                             dict_entry_predicate_t       predicate)
 394 {
 395     int count;
 396     string_t string;
 397
 398     string_init (&string);
 399
 400     dict_entry_predicate = predicate;
 401
 402     count = trie_for_each_of_length_if (dict,
 403                                         action, closure,
 404                                         min_length, max_length,
 405                                         dict_predicate,
 406                                         &string, 0);
 407
 408     string_fini (&string);
 409
 410     return count;
 411 }
 412
 413 int
 414 dict_for_each_of_length (dict_t         *dict,
 415                          dict_action_t   action,
 416                          void           *closure,
 417                          int             min_length,
 418                          int             max_length)
 419 {
 420     return dict_for_each_of_length_if (dict,
 421                                        action, closure,
 422                                        min_length, max_length,
 423                                        NULL);
 424 }
 425
 426 int
 427 dict_for_each_if (dict_t                        *dict,
 428                   dict_action_t                  action,
 429                   void                          *closure,
 430                   dict_entry_predicate_t         predicate)
 431
 432 {
 433     return dict_for_each_of_length_if (dict,
 434                                        action, closure,
 435                                        0, 0,
 436                                        predicate);
 437 }
 438
 439 int
 440 dict_for_each (dict_t           *dict,
 441                dict_action_t     action,
 442                void             *closure)
 443 {
 444     return dict_for_each_if (dict, action, closure, NULL);
 445 }
 446
 447 static void
 448 dict_action_print (void *closure, char *word, dict_entry_t *entry)
 449 {
 450     int *first = closure;
 451
 452     if (*first)
 453         *first = 0;
 454     else
 455         printf(" ");
 456
 457     printf ("%s", word);
 458 }
 459
 460 int
 461 dict_print_of_length_if (dict_t                 *dict,
 462                          int                     min_length,
 463                          int                     max_length,
 464                          dict_entry_predicate_t  predicate)
 465 {
 466     int first = TRUE;
 467
 468     return dict_for_each_of_length_if (dict,
 469                                        dict_action_print, &first,
 470                                        min_length, max_length,
 471                                        predicate);
 472 }
 473
 474 int
 475 dict_print_by_length_if (dict_t                 *dict,
 476                          dict_entry_predicate_t  predicate)
 477 {
 478     int length, total, words, count = 0;
 479
 480     total = dict_count_if (dict, predicate);
 481
 482     length = 1;
 483     do {
 484         words = dict_print_of_length_if (dict, length, length, predicate);
 485         if (words) {
 486             count += words;
 487             printf ("\n");
 488         }
 489         length++;
 490     } while (count < total);
 491
 492     return count;
 493 }
 494
 495 int
 496 dict_print_of_length (dict_t    *dict,
 497                       int        min_length,
 498                       int        max_length)
 499 {
 500     return dict_print_of_length_if (dict, min_length, max_length, NULL);
 501 }
 502
 503 int
 504 dict_print_if (dict_t                   *dict,
 505                dict_entry_predicate_t    predicate)
 506 {
 507     return dict_print_of_length_if (dict, 0, 0, predicate);
 508 }
 509
 510 int
 511 dict_print (dict_t *dict)
 512 {
 513     return dict_print_if (dict, NULL);
 514 }