/*
* Copyright © 2006 Carl Worth
*
- * This program is free software; you can redistribute it and\/or modify
+ * This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2, or (at your option)
* any later version.
* Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA."
*/
-/* Portably, schmortability. I want ease of programming. */
-#define _GNU_SOURCE
-#include <stdio.h>
-#include <stdlib.h>
+#include "dict.h"
+
#include <string.h>
#include <errno.h>
#include <ctype.h>
-#include "dict.h"
+typedef struct _string {
+ size_t size;
+ char *s;
+ size_t len;
+} string_t;
+
+typedef bool_t
+(*trie_predicate_t) (trie_t *trie);
+
+#define TRIE_CHAR_TO_INDEX(c) (tolower (c) - 'a')
+#define TRIE_INDEX_TO_CHAR(i) (i + 'a')
-void *
+static void *
xmalloc (size_t size)
{
void *res;
return res;
}
-void *
+static void *
xrealloc (void *ptr, size_t size)
{
void *res;
return res;
}
-void
+static void
chomp (char *s)
{
int len = strlen (s);
+ if (len == 0)
+ return;
if (s[len - 1] == '\n')
s[len - 1] = '\0';
}
-void
+static void
string_init (string_t *string)
{
string->size = 0;
string->len = 0;
}
-void
+static void
string_fini (string_t *string)
{
string->size = 0;
string->len = 0;
}
-void
+static void
string_append_char (string_t *string, char c)
{
if (string->size == 0) {
string->s[string->len] = '\0';
}
-void
+static void
string_chop (string_t *string)
{
if (string->len == 0)
trie->next[i] = NULL;
}
-trie_t *
+void
+trie_destroy (trie_t *trie);
+
+static void
+trie_fini (trie_t *trie)
+{
+ int i;
+
+ for (i = 0; i < 26; i++)
+ if (trie->next[i])
+ trie_destroy (trie->next[i]);
+}
+
+static trie_t *
trie_create (void)
{
trie_t *trie;
void
trie_destroy (trie_t *trie)
{
- int i;
-
- for (i = 0; i < 26; i++)
- if (trie->next[i])
- trie_destroy (trie->next[i]);
+ trie_fini (trie);
free (trie);
}
-void
+static trie_t *
trie_add (trie_t *trie,
const char *word_chunk)
{
char c = word_chunk[0];
int i;
- if (c == '\0') {
- trie->flags |= TRIE_FLAGS_IS_WORD;
- return;
- }
+ if (c == '\0')
+ return trie;
i = TRIE_CHAR_TO_INDEX (c);
if (trie->next[i] == NULL)
trie->next[i] = trie_create ();
- trie_add (trie->next[i], word_chunk + 1);
+ return trie_add (trie->next[i], word_chunk + 1);
}
-trie_t *
+static trie_t *
trie_find (trie_t *trie,
const char *word_chunk)
{
return trie;
}
-int
-trie_print (trie_t *trie,
- string_t *string,
- trie_predicate_t predicate)
+static int
+trie_count_if (trie_t *trie,
+ trie_predicate_t predicate)
+{
+ int i;
+ int count = 0;
+
+ if (predicate == NULL || (predicate) (trie))
+ count = 1;
+
+ for (i = 0; i < 26; i++) {
+ if (trie->next[i] == NULL)
+ continue;
+
+ count += trie_count_if (trie->next[i], predicate);
+ }
+
+ return count;
+}
+
+static int
+trie_for_each_of_length_if (trie_t *trie,
+ dict_action_t action,
+ void *closure,
+ int min_length,
+ int max_length,
+ trie_predicate_t predicate,
+ string_t *string,
+ int length)
+
{
char c;
int i;
int count = 0;
- if (trie->flags & TRIE_FLAGS_IS_WORD
- && (predicate == NULL || predicate (trie)))
+ if (length >= min_length && (predicate) (trie))
{
count = 1;
- printf ("%s ", string->s);
+
+ if (action)
+ action (closure, string->s, &trie->flags);
}
+ if (max_length > 0 && length == max_length)
+ return count;
+
/* Loop over each element, appending the character and recursing. */
for (i = 0; i < 26; i++) {
if (trie->next[i] == NULL)
c = TRIE_INDEX_TO_CHAR (i);
string_append_char (string, c);
- count += trie_print (trie->next[i], string, predicate);
+ count += trie_for_each_of_length_if (trie->next[i],
+ action, closure,
+ min_length, max_length,
+ predicate,
+ string, length + 1);
string_chop (string);
}
return count;
}
-bool_t
-trie_seen_predicate (trie_t *trie)
+void
+dict_init (dict_t *dict)
{
- return (trie->flags & TRIE_FLAGS_SEEN);
+ trie_init (dict);
}
-int
-trie_print_seen (trie_t *trie, string_t *word)
+void
+dict_fini (dict_t *dict)
{
- return trie_print (trie, word, trie_seen_predicate);
+ trie_fini (dict);
}
-bool_t
-trie_unseen_predicate (trie_t *trie)
+void
+dict_add_word (dict_t *dict,
+ const char *word)
{
- return (! trie_seen_predicate (trie));
-}
+ trie_t *trie;
-int
-trie_print_unseen (trie_t *trie, string_t *word)
-{
- return trie_print (trie, word, trie_unseen_predicate);
+ trie = trie_add (dict, word);
+ trie->flags |= DICT_ENTRY_FLAG_IS_WORD;
}
void
-dict_init (dict_t *dict,
- const char *filename)
+dict_add_words_from_file (dict_t *dict,
+ const char *filename)
{
FILE *file;
char *line = NULL;
exit (1);
}
- dict->trie = trie_create ();
-
while (1) {
bytes_read = getline (&line, &line_size, file);
if (bytes_read == -1)
break;
chomp (line);
- trie_add (dict->trie, line);
+ dict_add_word (dict, line);
}
if (line)
free (line);
fclose (file);
}
-void
-dict_fini (dict_t *dict)
+dict_entry_t *
+dict_lookup (dict_t *dict,
+ const char *word)
{
- trie_destroy (dict->trie);
+ trie_t *trie;
+
+ trie = trie_find (dict, word);
+ if (trie == NULL)
+ return NULL;
+ else
+ return &trie->flags;
}
-void
-dict_print (dict_t *dict)
+/* Yes, this function is rather silly. I have it here in the hope that
+ * it could be used for some better type-checking, (if only C had such
+ * a thing). */
+dict_cursor_t
+dict_root (dict_t *dict)
{
+ return dict;
+}
+
+dict_cursor_t
+dict_cursor_next (dict_cursor_t cursor,
+ char next)
+{
+ trie_t *trie = cursor;
+
+ if (trie == NULL)
+ return DICT_CURSOR_NIL;
+
+ return trie->next[TRIE_CHAR_TO_INDEX (next)];
+}
+
+dict_entry_t *
+dict_cursor_resolve (dict_cursor_t cursor)
+{
+ trie_t *trie;
+
+ if (cursor == DICT_CURSOR_NIL)
+ return NULL;
+
+ trie = cursor;
+ return &trie->flags;
+}
+
+/* XXX: This static function pointer is really nasty and definitely
+ * un-thread safe. What I really want it a lambda so I can construct a
+ * composite predicate on the fly. Oh well... */
+static dict_entry_predicate_t dict_entry_predicate = NULL;
+
+static bool_t
+dict_predicate (trie_t *trie)
+{
+ dict_entry_t *entry;
+
+ entry = dict_cursor_resolve (trie);
+ if (! DICT_ENTRY_IS_WORD (entry))
+ return FALSE;
+
+ if (dict_entry_predicate)
+ return (dict_entry_predicate) (*entry);
+
+ return TRUE;
+}
+
+int
+dict_count_if (dict_t *dict,
+ dict_entry_predicate_t predicate)
+{
+ dict_entry_predicate = predicate;
+ return trie_count_if (dict, dict_predicate);
+}
+
+int
+dict_count (dict_t *dict)
+{
+ return dict_count_if (dict, NULL);
+}
+
+int
+dict_for_each_of_length_if (dict_t *dict,
+ dict_action_t action,
+ void *closure,
+ int min_length,
+ int max_length,
+ dict_entry_predicate_t predicate)
+{
+ int count;
string_t string;
string_init (&string);
- trie_print (dict->trie, &string, NULL);
+ dict_entry_predicate = predicate;
+
+ count = trie_for_each_of_length_if (dict,
+ action, closure,
+ min_length, max_length,
+ dict_predicate,
+ &string, 0);
string_fini (&string);
+
+ return count;
+}
+
+int
+dict_for_each_of_length (dict_t *dict,
+ dict_action_t action,
+ void *closure,
+ int min_length,
+ int max_length)
+{
+ return dict_for_each_of_length_if (dict,
+ action, closure,
+ min_length, max_length,
+ NULL);
+}
+
+int
+dict_for_each_if (dict_t *dict,
+ dict_action_t action,
+ void *closure,
+ dict_entry_predicate_t predicate)
+
+{
+ return dict_for_each_of_length_if (dict,
+ action, closure,
+ 0, 0,
+ predicate);
+}
+
+int
+dict_for_each (dict_t *dict,
+ dict_action_t action,
+ void *closure)
+{
+ return dict_for_each_if (dict, action, closure, NULL);
+}
+
+static void
+dict_action_print (void *closure, char *word, dict_entry_t *entry)
+{
+ int *first = closure;
+
+ if (*first)
+ *first = 0;
+ else
+ printf(" ");
+
+ printf ("%s", word);
+}
+
+int
+dict_print_of_length_if (dict_t *dict,
+ int min_length,
+ int max_length,
+ dict_entry_predicate_t predicate)
+{
+ int first = TRUE;
+
+ return dict_for_each_of_length_if (dict,
+ dict_action_print, &first,
+ min_length, max_length,
+ predicate);
+}
+
+int
+dict_print_by_length_if (dict_t *dict,
+ dict_entry_predicate_t predicate)
+{
+ int length, total, words, count = 0;
+
+ total = dict_count_if (dict, predicate);
+
+ length = 1;
+ do {
+ words = dict_print_of_length_if (dict, length, length, predicate);
+ if (words) {
+ count += words;
+ printf ("\n");
+ }
+ length++;
+ } while (count < total);
+
+ return count;
+}
+
+int
+dict_print_of_length (dict_t *dict,
+ int min_length,
+ int max_length)
+{
+ return dict_print_of_length_if (dict, min_length, max_length, NULL);
+}
+
+int
+dict_print_if (dict_t *dict,
+ dict_entry_predicate_t predicate)
+{
+ return dict_print_of_length_if (dict, 0, 0, predicate);
+}
+
+int
+dict_print (dict_t *dict)
+{
+ return dict_print_if (dict, NULL);
}
projects / wordgame / blobdiff