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