2 * Copyright © 2006 Carl Worth
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)
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.
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."
25 typedef struct _string {
32 (*trie_predicate_t) (trie_t *trie);
34 #define TRIE_CHAR_TO_INDEX(c) (tolower (c) - 'a')
35 #define TRIE_INDEX_TO_CHAR(i) (i + 'a')
44 fprintf (stderr, "Error: out of memory\n");
52 xrealloc (void *ptr, size_t size)
56 res = realloc (ptr, size);
58 fprintf (stderr, "Error: out of memory\n");
71 if (s[len - 1] == '\n')
76 string_init (string_t *string)
84 string_fini (string_t *string)
93 string_append_char (string_t *string, char c)
95 if (string->size == 0) {
97 string->s = xmalloc (string->size);
102 if (string->len + 1 == string->size) {
104 string->s = xrealloc (string->s, string->size);
107 string->s[string->len++] = c;
108 string->s[string->len] = '\0';
112 string_chop (string_t *string)
114 if (string->len == 0)
117 string->s[--string->len] = '\0';
121 trie_init (trie_t *trie)
125 for (i = 0; i < 26; i++)
126 trie->next[i] = NULL;
130 trie_destroy (trie_t *trie);
133 trie_fini (trie_t *trie)
137 for (i = 0; i < 26; i++)
139 trie_destroy (trie->next[i]);
147 trie = xmalloc (sizeof (trie_t));
155 trie_destroy (trie_t *trie)
163 trie_add (trie_t *trie,
164 const char *word_chunk)
166 char c = word_chunk[0];
172 i = TRIE_CHAR_TO_INDEX (c);
173 if (trie->next[i] == NULL)
174 trie->next[i] = trie_create ();
176 return trie_add (trie->next[i], word_chunk + 1);
180 trie_find (trie_t *trie,
181 const char *word_chunk)
183 const char *s = word_chunk;
186 trie = trie->next[TRIE_CHAR_TO_INDEX (*s++)];
192 trie_count (trie_t *trie,
193 trie_predicate_t predicate)
198 if ((predicate) (trie))
201 for (i = 0; i < 26; i++) {
202 if (trie->next[i] == NULL)
205 count += trie_count (trie->next[i], predicate);
212 trie_for_each (trie_t *trie,
214 trie_predicate_t predicate,
218 dict_action_t action,
225 if (length >= min_length && (predicate) (trie))
229 action (closure, string->s, &trie->flags);
232 if (length == max_length)
235 /* Loop over each element, appending the character and recursing. */
236 for (i = 0; i < 26; i++) {
237 if (trie->next[i] == NULL)
240 c = TRIE_INDEX_TO_CHAR (i);
242 string_append_char (string, c);
243 count += trie_for_each (trie->next[i], string, predicate,
244 length + 1, min_length, max_length,
246 string_chop (string);
253 dict_init (dict_t *dict)
259 dict_fini (dict_t *dict)
265 dict_add_word (dict_t *dict,
270 trie = trie_add (dict, word);
271 trie->flags |= DICT_ENTRY_FLAG_IS_WORD;
275 dict_add_words_from_file (dict_t *dict,
276 const char *filename)
280 size_t line_size = 0;
283 file = fopen (filename, "r");
285 fprintf (stderr, "Error: failed to open %s: %s\n",
286 filename, strerror (errno));
291 bytes_read = getline (&line, &line_size, file);
292 if (bytes_read == -1)
295 dict_add_word (dict, line);
304 dict_lookup (dict_t *dict,
309 trie = trie_find (dict, word);
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
320 dict_root (dict_t *dict)
326 dict_cursor_next (dict_cursor_t cursor,
329 trie_t *trie = cursor;
332 return DICT_CURSOR_NIL;
334 return trie->next[TRIE_CHAR_TO_INDEX (next)];
338 dict_cursor_resolve (dict_cursor_t cursor)
342 if (cursor == DICT_CURSOR_NIL)
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;
355 dict_predicate (trie_t *trie)
359 entry = dict_cursor_resolve (trie);
360 if (! DICT_ENTRY_IS_WORD (entry))
363 if (dict_entry_predicate)
364 return (dict_entry_predicate) (*entry);
370 dict_count (dict_t *dict,
371 dict_entry_predicate_t predicate)
373 dict_entry_predicate = predicate;
374 return trie_count (dict, dict_predicate);
378 dict_for_each_if (dict_t *dict,
379 dict_action_t action,
381 dict_entry_predicate_t predicate)
387 string_init (&string);
389 dict_entry_predicate = predicate;
390 count = trie_for_each (dict, &string, dict_predicate,
391 0, 0, -1, action, closure);
393 string_fini (&string);
399 dict_for_each (dict_t *dict,
400 dict_action_t action,
403 return dict_for_each_if (dict, action, closure, NULL);
407 dict_for_each_by_length_if (dict_t *dict,
408 dict_action_t action,
410 dict_entry_predicate_t predicate)
412 int length, total, words, count = 0;
415 string_init (&string);
417 dict_entry_predicate = predicate;
419 total = trie_count (dict, dict_predicate);
423 words = trie_for_each (dict, &string, dict_predicate,
429 } while (count < total);
431 string_fini (&string);
437 dict_for_each_by_length (dict_t *dict,
438 dict_action_t action,
441 return dict_for_each_by_length_if (dict, action, closure, NULL);
445 dict_action_print (void *closure, char *word, dict_entry_t *entry)
447 int *length_of_last = closure;
448 int length = strlen (word);
450 if (length == *length_of_last)
452 else if (*length_of_last)
457 *length_of_last = length;
461 dict_print (dict_t *dict)
463 int length_of_last = 0;
465 return dict_for_each (dict,
466 dict_action_print, &length_of_last);
470 dict_print_by_length (dict_t *dict)
472 int length_of_last = 0;
474 return dict_for_each_by_length (dict,
475 dict_action_print, &length_of_last);
479 dict_print_if (dict_t *dict,
480 dict_entry_predicate_t predicate)
482 int length_of_last = 0;
484 return dict_for_each_if (dict,
485 dict_action_print, &length_of_last,
490 dict_print_by_length_if (dict_t *dict,
491 dict_entry_predicate_t predicate)
493 int length_of_last = 0;
495 return dict_for_each_by_length_if (dict,
496 dict_action_print, &length_of_last,