X-Git-Url: https://git.ozlabs.org/?a=blobdiff_plain;f=ccan%2Faga%2Ftest%2Fapi-lazytrie.c;fp=ccan%2Faga%2Ftest%2Fapi-lazytrie.c;h=feea4d16838d399c4ac5dd11453df28b3d6a6abe;hb=06162212353c882249d7e207756ea81ea645fc30;hp=0000000000000000000000000000000000000000;hpb=e7c9d609f0c6bfb230f10bcd40a8ceee282deaa1;p=ccan

diff --git a/ccan/aga/test/api-lazytrie.c b/ccan/aga/test/api-lazytrie.c
new file mode 100644
index 00000000..feea4d16
--- /dev/null
+++ b/ccan/aga/test/api-lazytrie.c
@@ -0,0 +1,211 @@
+#include "config.h"
+
+#include <stddef.h>
+#include <assert.h>
+
+#include <ccan/ptrint/ptrint.h>
+#include <ccan/tal/tal.h>
+#include <ccan/tal/str/str.h>
+#include <ccan/take/take.h>
+#include <ccan/tal/grab_file/grab_file.h>
+#include <ccan/container_of/container_of.h>
+
+#include <ccan/aga/aga.h>
+
+#include <ccan/tap/tap.h>
+
+#define NWORDS		1000
+#define LETTERS		"abcdefghijklmnopqrstuvwxyz"
+#define NLETTERS	(sizeof(LETTERS) - 1)
+
+char **wordarray;
+char **wordarrayb; /* Word array sorted by length */
+int nwords;
+
+struct trie_node {
+	int start, end;
+	const char *prefix;
+	bool isword;
+	struct trie_node *next[NLETTERS];
+	struct aga_node agan;
+};
+
+/* Sorts by length first, then alphabetically */
+static int lensort(const void *xv, const void *yv)
+{
+	char *x = *((char **)xv);
+	char *y = *((char **)yv);
+	int xn = strlen(x);
+	int yn = strlen(y);
+
+	if (xn < yn)
+		return -1;
+	else if (xn > yn)
+		return 1;
+	else
+		/* We need this because qsort is not stable */
+		return strcmp(x, y);
+}
+
+static void setup_words(void)
+{
+	char *wordfile;
+
+	/* read in the words */
+	wordfile = grab_file(NULL, "test/api-lazytrie-words.txt");
+	ok1(wordfile);
+	wordarray = tal_strsplit(NULL, take(wordfile), "\n", STR_NO_EMPTY);
+	ok1(wordarray);
+	nwords = tal_count(wordarray) - 1;
+	diag("lazytrie: %d words loaded", nwords);
+	ok1(nwords == NWORDS);
+
+	wordarrayb = tal_arr(NULL, char *, nwords);
+	memcpy(wordarrayb, wordarray, tal_count(wordarrayb) * sizeof(char *));
+
+	qsort(wordarrayb, nwords, sizeof(char *), lensort);
+}
+
+struct lazytrie {
+	struct trie_node root;
+	struct aga_graph g;
+};
+
+static void init_trie_node(struct trie_node *n, int start, int end,
+			   const char *prefix)
+{
+	int i;
+
+	n->start = start;
+	n->end = end;
+	n->prefix = prefix;
+	n->isword = (strcmp(n->prefix, wordarray[n->start]) == 0);
+
+	for (i = 0; i < NLETTERS; i++)
+		n->next[i] = NULL;
+
+	aga_node_init(&n->agan);
+}
+
+static ptrint_t *lazytrie_first_edge(const struct aga_graph *g,
+				     const struct aga_node *n)
+{
+	return int2ptr(1);
+}
+
+static ptrint_t *lazytrie_next_edge(const struct aga_graph *g,
+				    const struct aga_node *n,
+				    ptrint_t *e)
+{
+	int index = ptr2int(e);
+
+	assert((index >= 1) && (index <= NLETTERS));
+	if (index == NLETTERS)
+		return NULL;
+	else
+		return int2ptr(index + 1);
+}
+
+static int lazytrie_edge_info(const struct aga_graph *g,
+			      const struct aga_node *n,
+			      ptrint_t *e,
+			      struct aga_edge_info *ei)
+{
+	struct trie_node *tn = container_of(n, struct trie_node, agan);
+	struct trie_node *next;
+	int index = ptr2int(e);
+
+	assert((index >= 1) && (index <= NLETTERS));
+
+	next = tn->next[index - 1];
+
+	if (!next) {
+		int depth = strlen(tn->prefix);
+		int start, end;
+
+		start = tn->start;
+		while (start < tn->end) {
+			if (wordarray[start][depth] >= LETTERS[index - 1])
+				break;
+			start++;
+		}
+
+		end = start;
+		while (end < tn->end) {
+			if (wordarray[end][depth] > LETTERS[index - 1])
+				break;
+			end++;
+		}
+
+		if (end > start) {
+			char plus[2] = { LETTERS[index - 1], '\0' };
+			next = tal(tn, struct trie_node);
+			init_trie_node(next, start, end,
+				       tal_strcat(next, tn->prefix, plus));
+		}
+	}
+
+	if (next)
+		ei->to = &next->agan;
+	return 0;
+}
+
+static struct lazytrie *setup_trie(void)
+{
+	struct lazytrie *lt;
+
+	lt = tal(NULL, struct lazytrie);
+	init_trie_node(&lt->root, 0, nwords, "");
+	aga_init_graph(&lt->g, lazytrie_first_edge, lazytrie_next_edge,
+		       lazytrie_edge_info);
+	return lt;
+}
+
+int main(void)
+{
+	struct lazytrie *lt;
+	struct aga_node *an;
+	int xn;
+
+	plan_tests(3 + NWORDS*2);
+	setup_words();
+
+	lt = setup_trie();
+
+	aga_dfs_start(&lt->g);
+
+	xn = 0;
+	aga_dfs(an, &lt->g, &lt->root.agan) {
+		struct trie_node *n = container_of(an, struct trie_node, agan);
+
+		diag("Visited \"%s\"\n", n->prefix);
+
+		if (n->isword) {
+			ok1(strcmp(n->prefix, wordarray[xn]) == 0);
+			xn++;
+		}
+	}
+
+	aga_finish(&lt->g);
+
+	tal_free(lt);
+
+	lt = setup_trie();
+
+	aga_bfs_start(&lt->g);
+
+	xn = 0;
+	aga_bfs(an, &lt->g, &lt->root.agan) {
+		struct trie_node *n = container_of(an, struct trie_node, agan);
+
+		diag("Visited \"%s\"\n", n->prefix);
+
+		if (n->isword) {
+			ok1(strcmp(n->prefix, wordarrayb[xn]) == 0);
+			xn++;
+		}
+	}
+
+	/* This exits depending on whether all tests passed */
+	return exit_status();
+}