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_for_each (trie_t           *trie,
 213                string_t         *string,
 214                trie_predicate_t  predicate,
 215                int               length,
 216                int               min_length,
 217                int               max_length,
 218                dict_action_t     action,
 219                void             *closure)
 220 {
 221     char c;
 222     int i;
 223     int count = 0;
 224
 225     if (length >= min_length && (predicate) (trie))
 226     {
 227         count = 1;
 228
 229         action (closure, string->s, &trie->flags);
 230     }
 231
 232     if (length == max_length)
 233         return count;
 234
 235     /* Loop over each element, appending the character and recursing. */
 236     for (i = 0; i < 26; i++) {
 237         if (trie->next[i] == NULL)
 238             continue;
 239
 240         c = TRIE_INDEX_TO_CHAR (i);
 241
 242         string_append_char (string, c);
 243         count += trie_for_each (trie->next[i], string, predicate,
 244                                 length + 1, min_length, max_length,
 245                                 action, closure);
 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_for_each_if (dict_t                        *dict,
 379                   dict_action_t                  action,
 380                   void                          *closure,
 381                   dict_entry_predicate_t         predicate)
 382
 383 {
 384     int count;
 385     string_t string;
 386
 387     string_init (&string);
 388
 389     dict_entry_predicate = predicate;
 390     count = trie_for_each (dict, &string, dict_predicate,
 391                            0, 0, -1, action, closure);
 392
 393     string_fini (&string);
 394
 395     return count;
 396 }
 397
 398 int
 399 dict_for_each (dict_t           *dict,
 400                dict_action_t     action,
 401                void             *closure)
 402 {
 403     return dict_for_each_if (dict, action, closure, NULL);
 404 }
 405
 406 int
 407 dict_for_each_by_length_if (dict_t                      *dict,
 408                             dict_action_t                action,
 409                             void                        *closure,
 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_for_each (dict, &string, dict_predicate,
 424                                0, length, length,
 425                                action, closure);
 426         if (words)
 427             count += words;
 428         length++;
 429     } while (count < total);
 430
 431     string_fini (&string);
 432
 433     return count;
 434 }
 435
 436 int
 437 dict_for_each_by_length (dict_t         *dict,
 438                          dict_action_t   action,
 439                          void           *closure)
 440 {
 441     return dict_for_each_by_length_if (dict, action, closure, NULL);
 442 }
 443
 444 static void
 445 dict_action_print (void *closure, char *word, dict_entry_t *entry)
 446 {
 447     int *length_of_last = closure;
 448     int length = strlen (word);
 449
 450     if (length == *length_of_last)
 451         printf(" ");
 452     else if (*length_of_last)
 453         printf("\n");
 454
 455     printf ("%s", word);
 456
 457     *length_of_last = length;
 458 }
 459
 460 int
 461 dict_print (dict_t *dict)
 462 {
 463     int length_of_last = 0;
 464
 465     return dict_for_each (dict,
 466                           dict_action_print, &length_of_last);
 467 }
 468
 469 int
 470 dict_print_by_length (dict_t *dict)
 471 {
 472     int length_of_last = 0;
 473
 474     return dict_for_each_by_length (dict,
 475                                     dict_action_print, &length_of_last);
 476 }
 477
 478 int
 479 dict_print_if (dict_t                   *dict,
 480                dict_entry_predicate_t    predicate)
 481 {
 482     int length_of_last = 0;
 483
 484     return dict_for_each_if (dict,
 485                              dict_action_print, &length_of_last,
 486                              predicate);
 487 }
 488
 489 int
 490 dict_print_by_length_if (dict_t                 *dict,
 491                          dict_entry_predicate_t  predicate)
 492 {
 493     int length_of_last = 0;
 494
 495     return dict_for_each_by_length_if (dict,
 496                                        dict_action_print, &length_of_last,
 497                                        predicate);
 498 }