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_print (trie_t *trie,
214 trie_predicate_t predicate,
223 if (length >= min_length && (predicate) (trie))
226 printf ("%s ", string->s);
229 if (length == max_length)
232 /* Loop over each element, appending the character and recursing. */
233 for (i = 0; i < 26; i++) {
234 if (trie->next[i] == NULL)
237 c = TRIE_INDEX_TO_CHAR (i);
239 string_append_char (string, c);
240 count += trie_print (trie->next[i], string, predicate,
241 length + 1, min_length, max_length);
242 string_chop (string);
249 dict_init (dict_t *dict)
255 dict_fini (dict_t *dict)
261 dict_add_word (dict_t *dict,
266 trie = trie_add (dict, word);
267 trie->flags |= DICT_ENTRY_FLAG_IS_WORD;
271 dict_add_words_from_file (dict_t *dict,
272 const char *filename)
276 size_t line_size = 0;
279 file = fopen (filename, "r");
281 fprintf (stderr, "Error: failed to open %s: %s\n",
282 filename, strerror (errno));
287 bytes_read = getline (&line, &line_size, file);
288 if (bytes_read == -1)
291 dict_add_word (dict, line);
300 dict_lookup (dict_t *dict,
305 trie = trie_find (dict, word);
312 /* Yes, this function is rather silly. I have it here in the hope that
313 * it could be used for some better type-checking, (if only C had such
316 dict_root (dict_t *dict)
322 dict_cursor_next (dict_cursor_t cursor,
325 trie_t *trie = cursor;
328 return DICT_CURSOR_NIL;
330 return trie->next[TRIE_CHAR_TO_INDEX (next)];
334 dict_cursor_resolve (dict_cursor_t cursor)
338 if (cursor == DICT_CURSOR_NIL)
345 /* XXX: This static function pointer is really nasty and definitely
346 * un-thread safe. What I really want it a lambda so I can construct a
347 * composite predicate on the fly. Oh well... */
348 static dict_entry_predicate_t dict_entry_predicate = NULL;
351 dict_predicate (trie_t *trie)
355 entry = dict_cursor_resolve (trie);
356 if (! DICT_ENTRY_IS_WORD (entry))
359 if (dict_entry_predicate)
360 return (dict_entry_predicate) (*entry);
366 dict_count (dict_t *dict,
367 dict_entry_predicate_t predicate)
369 dict_entry_predicate = predicate;
370 return trie_count (dict, dict_predicate);
374 dict_print (dict_t *dict)
379 string_init (&string);
381 dict_entry_predicate = NULL;
382 count = trie_print (dict, &string, dict_predicate,
385 string_fini (&string);
391 dict_print_if (dict_t *dict,
392 dict_entry_predicate_t predicate)
397 string_init (&string);
399 dict_entry_predicate = predicate;
400 count = trie_print (dict, &string, dict_predicate,
403 string_fini (&string);
409 dict_print_by_length_if (dict_t *dict,
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_print (dict, &string, dict_predicate,
430 } while (count < total);
432 string_fini (&string);