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."
19 /* Portably, schmortability. I want ease of programming. */
29 typedef struct _string {
36 (*trie_predicate_t) (trie_t *trie);
38 #define TRIE_CHAR_TO_INDEX(c) (tolower (c) - 'a')
39 #define TRIE_INDEX_TO_CHAR(i) (i + 'a')
48 fprintf (stderr, "Error: out of memory\n");
56 xrealloc (void *ptr, size_t size)
60 res = realloc (ptr, size);
62 fprintf (stderr, "Error: out of memory\n");
75 if (s[len - 1] == '\n')
80 string_init (string_t *string)
88 string_fini (string_t *string)
97 string_append_char (string_t *string, char c)
99 if (string->size == 0) {
101 string->s = xmalloc (string->size);
106 if (string->len + 1 == string->size) {
108 string->s = xrealloc (string->s, string->size);
111 string->s[string->len++] = c;
112 string->s[string->len] = '\0';
116 string_chop (string_t *string)
118 if (string->len == 0)
121 string->s[--string->len] = '\0';
125 trie_init (trie_t *trie)
129 for (i = 0; i < 26; i++)
130 trie->next[i] = NULL;
134 trie_destroy (trie_t *trie);
137 trie_fini (trie_t *trie)
141 for (i = 0; i < 26; i++)
143 trie_destroy (trie->next[i]);
151 trie = xmalloc (sizeof (trie_t));
159 trie_destroy (trie_t *trie)
167 trie_add (trie_t *trie,
168 const char *word_chunk)
170 char c = word_chunk[0];
176 i = TRIE_CHAR_TO_INDEX (c);
177 if (trie->next[i] == NULL)
178 trie->next[i] = trie_create ();
180 return trie_add (trie->next[i], word_chunk + 1);
184 trie_find (trie_t *trie,
185 const char *word_chunk)
187 const char *s = word_chunk;
190 trie = trie->next[TRIE_CHAR_TO_INDEX (*s++)];
196 trie_count (trie_t *trie,
197 trie_predicate_t predicate)
202 if ((predicate) (trie))
205 for (i = 0; i < 26; i++) {
206 if (trie->next[i] == NULL)
209 count += trie_count (trie->next[i], predicate);
216 trie_print (trie_t *trie,
218 trie_predicate_t predicate,
227 if (length >= min_length && (predicate) (trie))
230 printf ("%s ", string->s);
233 if (length == max_length)
236 /* Loop over each element, appending the character and recursing. */
237 for (i = 0; i < 26; i++) {
238 if (trie->next[i] == NULL)
241 c = TRIE_INDEX_TO_CHAR (i);
243 string_append_char (string, c);
244 count += trie_print (trie->next[i], string, predicate,
245 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_print (dict_t *dict)
383 string_init (&string);
385 dict_entry_predicate = NULL;
386 count = trie_print (dict, &string, dict_predicate,
389 string_fini (&string);
395 dict_print_if (dict_t *dict,
396 dict_entry_predicate_t predicate)
401 string_init (&string);
403 dict_entry_predicate = predicate;
404 count = trie_print (dict, &string, dict_predicate,
407 string_fini (&string);
413 dict_print_by_length_if (dict_t *dict,
414 dict_entry_predicate_t predicate)
416 int length, total, words, count = 0;
419 string_init (&string);
421 dict_entry_predicate = predicate;
423 total = trie_count (dict, dict_predicate);
427 words = trie_print (dict, &string, dict_predicate,
434 } while (count < total);
436 string_fini (&string);