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_if (trie_t *trie,
193 trie_predicate_t predicate)
198 if (predicate == NULL || (predicate) (trie))
201 for (i = 0; i < 26; i++) {
202 if (trie->next[i] == NULL)
205 count += trie_count_if (trie->next[i], predicate);
212 trie_for_each_of_length_if (trie_t *trie,
213 dict_action_t action,
217 trie_predicate_t predicate,
226 if (length >= min_length && (predicate) (trie))
231 action (closure, string->s, &trie->flags);
234 if (length == max_length)
237 /* Loop over each element, appending the character and recursing. */
238 for (i = 0; i < 26; i++) {
239 if (trie->next[i] == NULL)
242 c = TRIE_INDEX_TO_CHAR (i);
244 string_append_char (string, c);
245 count += trie_for_each_of_length_if (trie->next[i],
247 min_length, max_length,
250 string_chop (string);
257 dict_init (dict_t *dict)
263 dict_fini (dict_t *dict)
269 dict_add_word (dict_t *dict,
274 trie = trie_add (dict, word);
275 trie->flags |= DICT_ENTRY_FLAG_IS_WORD;
279 dict_add_words_from_file (dict_t *dict,
280 const char *filename)
284 size_t line_size = 0;
287 file = fopen (filename, "r");
289 fprintf (stderr, "Error: failed to open %s: %s\n",
290 filename, strerror (errno));
295 bytes_read = getline (&line, &line_size, file);
296 if (bytes_read == -1)
299 dict_add_word (dict, line);
308 dict_lookup (dict_t *dict,
313 trie = trie_find (dict, word);
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
324 dict_root (dict_t *dict)
330 dict_cursor_next (dict_cursor_t cursor,
333 trie_t *trie = cursor;
336 return DICT_CURSOR_NIL;
338 return trie->next[TRIE_CHAR_TO_INDEX (next)];
342 dict_cursor_resolve (dict_cursor_t cursor)
346 if (cursor == DICT_CURSOR_NIL)
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;
359 dict_predicate (trie_t *trie)
363 entry = dict_cursor_resolve (trie);
364 if (! DICT_ENTRY_IS_WORD (entry))
367 if (dict_entry_predicate)
368 return (dict_entry_predicate) (*entry);
374 dict_count_if (dict_t *dict,
375 dict_entry_predicate_t predicate)
377 dict_entry_predicate = predicate;
378 return trie_count_if (dict, dict_predicate);
382 dict_count (dict_t *dict)
384 return dict_count_if (dict, NULL);
388 dict_for_each_of_length_if (dict_t *dict,
389 dict_action_t action,
393 dict_entry_predicate_t predicate)
398 string_init (&string);
400 dict_entry_predicate = predicate;
402 count = trie_for_each_of_length_if (dict,
404 min_length, max_length,
408 string_fini (&string);
414 dict_for_each_of_length (dict_t *dict,
415 dict_action_t action,
420 return dict_for_each_of_length_if (dict,
422 min_length, max_length,
427 dict_for_each_if (dict_t *dict,
428 dict_action_t action,
430 dict_entry_predicate_t predicate)
433 return dict_for_each_of_length_if (dict,
440 dict_for_each (dict_t *dict,
441 dict_action_t action,
444 return dict_for_each_if (dict, action, closure, NULL);
448 dict_action_print (void *closure, char *word, dict_entry_t *entry)
450 int *first = closure;
461 dict_print_of_length_if (dict_t *dict,
464 dict_entry_predicate_t predicate)
468 return dict_for_each_of_length_if (dict,
469 dict_action_print, &first,
470 min_length, max_length,
475 dict_print_by_length_if (dict_t *dict,
476 dict_entry_predicate_t predicate)
478 int length, total, words, count = 0;
480 total = dict_count_if (dict, predicate);
484 words = dict_print_of_length_if (dict, length, length, predicate);
490 } while (count < total);
496 dict_print_of_length (dict_t *dict,
500 return dict_print_of_length_if (dict, min_length, max_length, NULL);
504 dict_print_if (dict_t *dict,
505 dict_entry_predicate_t predicate)
507 return dict_print_of_length_if (dict, 0, 0, predicate);
511 dict_print (dict_t *dict)
513 return dict_print_if (dict, NULL);