Initial commit

3 files changed, 504 insertions, 0 deletions

diff --git a/test/contrained.c b/test/contrained.c
new file mode 100644
index 0000000..1af01a8
--- /dev/null
+++ b/test/contrained.c
@@ -0,0 +1,281 @@
+#include "leven.h"
+
+#include "log.h"
+
+DECL_MAT3(no_trace, uint32_t, 0, 0, 0);
+
+int main(int argc, char **argv) {
+	log("Constrained edit tests");
+
+	{
+		struct Tree a = {
+			.adj = { .data = &(nid){0},
+				.stride = 1,
+			},
+			.len = 1,
+		};
+
+		struct Tree b = {
+			.adj = {
+				.data = &(nid){0},
+				.stride = 1,
+			},
+			.len = 1,
+		};
+
+		DECL_MAT_DATA(cost, uint32_t, 2, 2, 
+			0, 2,
+			2, 1,
+		);
+		DECL_MAT(cost_n, uint32_t, 2, 2);
+		DECL_MAT(cost_f, uint32_t, 2, 2);
+		DECL_MAT(cost_s, uint32_t, 1, 1);
+
+		constrained_tree_distance(
+			a,
+			b,
+			cost,
+			cost_n,
+			cost_f,
+			cost_s
+		);
+
+		if(*imat_uint32_t(cost_n, 1, 1) != 1) {
+			log("Test Fail");
+			return 1;
+		}
+
+		DECL_MAT(alignment, uint32_t, 2, 2);
+		uint32_t adj_alignment[2] = {0, 0};
+		constrained_tree_alignment(
+			a,
+			b,
+			cost,
+			cost_n,
+			cost_f,
+			cost_s,
+			adj_alignment,
+			alignment
+		);
+	}
+
+	{
+		struct Tree a = {
+			.adj = {
+				.data = (nid[]){2, 0},
+				.stride = 1,
+			},
+			.len = 2,
+		};
+
+		struct Tree b = {
+			.adj = {
+				.data = &(nid){0},
+				.stride = 1,
+			},
+			.len = 1,
+		};
+
+		DECL_MAT_DATA(cost, uint32_t, 3, 2,
+			0, 1, 2,
+			2, 1, 1,
+		);
+		DECL_MAT(cost_n, uint32_t, 3, 2);
+		DECL_MAT(cost_f, uint32_t, 3, 2);
+		DECL_MAT(cost_s, uint32_t, 2, 2);
+
+		constrained_tree_distance(
+			a,
+			b,
+			cost,
+			cost_n,
+			cost_f,
+			cost_s
+		);
+
+		if(*imat_uint32_t(cost_n, 1, 1) != 2) {
+			log("Test Fail");
+			return 1;
+		}
+
+		DECL_MAT(alignment, uint32_t, 3, 2);
+		uint32_t adj_alignment[2] = {0, 0};
+		constrained_tree_alignment(
+			a,
+			b,
+			cost,
+			cost_n,
+			cost_f,
+			cost_s,
+			adj_alignment,
+			alignment
+		);
+	}
+
+	{
+		struct Tree a = {
+			.adj = {
+				.data = (nid[]){2, 0},
+				.stride = 1,
+			},
+			.len = 2,
+		};
+
+		struct Tree b = {
+			.adj = {
+				.data = (nid[]){2, 0},
+				.stride = 1,
+			},
+			.len = 2,
+		};
+
+		DECL_MAT_DATA(cost, uint32_t, 3, 3,
+			0, 2, 2,
+			2, 0, 2,
+			2, 2, 0,
+		);
+		DECL_MAT(cost_n, uint32_t, 3, 3);
+		DECL_MAT(cost_f, uint32_t, 3, 3);
+		DECL_MAT(cost_s, uint32_t, 2, 2);
+
+		constrained_tree_distance(
+			a,
+			b,
+			cost,
+			cost_n,
+			cost_f,
+			cost_s
+		);
+
+		if(*imat_uint32_t(cost_n, 1, 1) != 0) {
+			log("Test Fail");
+			return 1;
+		}
+
+		DECL_MAT(alignment, uint32_t, 2, 2);
+		uint32_t adj_alignment[2] = {0, 0};
+		constrained_tree_alignment(
+			a,
+			b,
+			cost,
+			cost_n,
+			cost_f,
+			cost_s,
+			adj_alignment,
+			alignment
+		);
+	}
+
+	{
+		struct Tree a = {
+			.adj = {
+				.data = (nid[]){2, 3, 0, 0, 0, 0},
+				.stride = 2,
+			},
+			.len = 3,
+		};
+
+		struct Tree b = {
+			.adj = {
+				.data = (nid[]){2, 0, 3, 4, 0, 0, 0, 0},
+				.stride = 2,
+			},
+			.len = 4,
+		};
+
+		DECL_MAT_DATA(cost, uint32_t, 4, 5,
+			2, 2, 2, 2,
+			2, 2, 2, 2,
+			2, 0, 2, 2,
+			2, 2, 0, 2,
+			2, 2, 2, 0,
+		);
+		DECL_MAT(cost_n, uint32_t, 4, 5);
+		DECL_MAT(cost_f, uint32_t, 4, 5);
+		DECL_MAT(cost_s, uint32_t, 3, 3);
+
+		constrained_tree_distance(
+			a,
+			b,
+			cost,
+			cost_n,
+			cost_f,
+			cost_s
+		);
+
+		if(*imat_uint32_t(cost_n, 1, 1) != 2) {
+			log("Test Fail\n");
+			return 1;
+		}
+
+		DECL_MAT(alignment, uint32_t, 2, 2);
+		uint32_t adj_alignment[2] = {0, 0};
+		constrained_tree_alignment(
+			a,
+			b,
+			cost,
+			cost_n,
+			cost_f,
+			cost_s,
+			adj_alignment,
+			alignment
+		);
+	}
+
+	{
+		struct Tree a = {
+			.adj = {
+				.data = (nid[]){2, 3, 0, 0, 0, 0},
+				.stride = 2,
+			},
+			.len = 3,
+		};
+
+		struct Tree b = {
+			.adj = {
+				.data = (nid[]){2, 3, 0},
+				.stride = 1,
+			},
+			.len = 3,
+		};
+
+		DECL_MAT_DATA(cost, uint32_t, 4, 4,
+			0, 2, 2, 2,
+			2, 0, 2, 2,
+			2, 2, 0, 2,
+			2, 2, 2, 0,
+		);
+		DECL_MAT(cost_n, uint32_t, 4, 4);
+		DECL_MAT(cost_f, uint32_t, 4, 4);
+		DECL_MAT(cost_s, uint32_t, 3, 2);
+
+		constrained_tree_distance(
+			a,
+			b,
+			cost,
+			cost_n,
+			cost_f,
+			cost_s
+		);
+
+		if(*imat_uint32_t(cost_n, 1, 1) != 4) {
+			log("Test Fail\n");
+			return 1;
+		}
+
+		DECL_MAT(alignment, uint32_t, 2, 2);
+		uint32_t adj_alignment[2] = {0, 0};
+		constrained_tree_alignment(
+			a,
+			b,
+			cost,
+			cost_n,
+			cost_f,
+			cost_s,
+			adj_alignment,
+			alignment
+		);
+	}
+
+	return 0;
+}
diff --git a/test/leven.c b/test/leven.c
new file mode 100644
index 0000000..500d7d1
--- /dev/null
+++ b/test/leven.c
@@ -0,0 +1,109 @@
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "leven.h"
+#include "log.h"
+
+DECL_MAT(weight, uint32_t, 256, 256);
+
+static void simple_distance() {
+	for(uint32_t i = 0; i < 256 * 256; i++) {
+		weight.data[i] = 2;
+	}
+
+	for(uint32_t i = 1; i < 256; i++) {
+		// The identity values
+		*imat_uint32_t(weight, i, i) = 0;
+
+		// Adding a character
+		*imat_uint32_t(weight, i, 0) = 1;
+		// Removing a character
+		*imat_uint32_t(weight, 0, i) = 1;
+	}
+}
+
+static size_t nidlen(nid *a) {
+	size_t l = 0;
+	while(a[l] != 0) l++;
+	return l;
+}
+
+static uint32_t* run_leven(nid *a, nid *b) {
+	size_t la = nidlen(a);
+	size_t lb = nidlen(b);
+
+	mat_uint32_t dist = {
+		.data = malloc((la+1) * (lb+1) * sizeof(uint32_t)),
+		.stride = la+1,
+	};
+	uint32_t *alignment = malloc(lb * sizeof(uint32_t));
+
+	string_edit_distance(a, la, b, lb, weight, dist);
+	string_edit_alignment(a, la, b, lb, weight, dist, alignment);
+
+	free(dist.data);
+	return alignment;
+}
+
+int main(int argc, char **argv) {
+
+	log("Levenshtein tests");
+
+	// Initialize the weight with simple weights
+	simple_distance();
+	{
+		uint32_t* alignment = run_leven((nid[]){1, 0}, (nid[]){2, 0});
+		uint32_t expected[] = {
+			0,
+		};
+		if(memcmp(alignment, expected, sizeof(expected)/sizeof(*expected)) != 0) {
+			return 1;
+		}
+		free(alignment);
+	}
+
+	{
+		uint32_t* alignment = run_leven((nid[]){1, 0}, (nid[]){2, 1, 0});
+		uint32_t expected[] = {
+			-1, 0,
+		};
+		if(memcmp(alignment, expected, sizeof(expected)/sizeof(*expected)) != 0) {
+			return 1;
+		}
+		free(alignment);
+	}
+
+	{
+		uint32_t* alignment = run_leven((nid[]){1, 2, 3, 3, 4, 5, 0}, (nid[]){7, 3, 3, 4, 5, 3, 8, 5, 0});
+		logb("Alignment: ");
+		for(size_t i = 0; i < 8; i++) {
+			logc("%d ", alignment[i]);
+		}
+		loge();
+		uint32_t expected[] = {
+			1, 2, 3, 4, -1, -1, -1, 5,
+		};
+		if(memcmp(alignment, expected, sizeof(expected)) != 0) {
+			return 1;
+		}
+		free(alignment);
+	}
+
+	// Turning an 1 into 2 now costs 3
+	*imat_uint32_t(weight, 1, 2) = 3;
+	{
+		uint32_t* alignment = run_leven((nid[]){1, 0}, (nid[]){2, 0});
+		// So it prefers to remove the a an add a b
+		uint32_t expected[] = {
+			-1,
+		};
+		if(memcmp(alignment, expected, sizeof(expected)/sizeof(*expected)) != 0) {
+			return 1;
+		}
+		free(alignment);
+	}
+	// Reset the cost of 1 into 2
+	*imat_uint32_t(weight, 1, 2) = 2;
+}
diff --git a/test/parse.c b/test/parse.c
new file mode 100644
index 0000000..07dbbfa
--- /dev/null
+++ b/test/parse.c
@@ -0,0 +1,114 @@
+#include "parse.h"
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
+#include "log.h"
+
+#define fail() fail_impl(__LINE__);
+
+int fail_impl(int line) {
+	log("%d: Test fail!\n", line);
+	return 1;
+}
+
+int main(int argc, char **argv) {
+	printf("Parser Tests\n");
+
+	{
+		struct Tree a;
+		size_t *chunks = NULL;
+		if(parse_string("<root></root>", &a, &chunks) != 0) return fail();
+		if(a.adj.stride != 1) return fail();
+		if(a.len != 1) return fail();
+		nid expected[] = {
+			0,
+		};
+		if(memcmp(a.adj.data, expected, sizeof(expected)) != 0) return fail();
+		
+		// Verify chunk offsets
+		if(chunks[0] != 0) return fail();
+		
+		free(chunks);
+		free(a.adj.data);
+	}
+
+	{
+		struct Tree a;
+		size_t *chunks = NULL;
+		if(parse_string("<root><a></a><b></b></root>", &a, &chunks) != 0) return fail();
+		if(a.adj.stride != 2) return fail();
+		if(a.len != 3) return fail();
+		nid expected[] = {
+			2, 3,
+			0, 0,
+			0, 0,
+		};
+		if(memcmp(a.adj.data, expected, sizeof(expected)) != 0) return fail();
+		
+		// Verify chunk offsets
+		if(chunks[0] != 0) return fail();
+		if(chunks[1] != 6) return fail();
+		if(chunks[2] != 13) return fail();
+		
+		free(chunks);
+		free(a.adj.data);
+	}
+
+	{
+		struct Tree a;
+		size_t *chunks = NULL;
+		if(parse_string("<root><a><c></c></a><b></b></root>", &a, &chunks) != 0) return fail();
+		if(a.adj.stride != 2) return fail();
+		if(a.len != 4) return fail();
+		nid expected[] = {
+			2, 4,
+			3, 0,
+			0, 0,
+			0, 0,
+		};
+		if(memcmp(a.adj.data, expected, sizeof(expected)) != 0) return fail();
+		
+		// Verify chunk offsets
+		if(chunks[0] != 0) return fail();
+		if(chunks[1] != 6) return fail();
+		if(chunks[2] != 9) return fail();
+		if(chunks[3] != 20) return fail();
+		
+		free(chunks);
+		free(a.adj.data);
+	}
+
+	// We forgot to close the open tag
+	{
+		struct Tree a;
+		size_t *chunks = NULL;
+		fflush(stdout);
+		if(parse_string("<root</root>", &a, &chunks) != 1) return fail();
+		fflush(stdout);
+	}
+
+	// Test self-closing tag
+	{
+		struct Tree a;
+		size_t *chunks = NULL;
+		fflush(stdout);
+		if(parse_string("<root><a /></root>", &a, &chunks) != 0) return fail();
+		if(a.adj.stride != 1) return fail();
+		if(a.len != 2) return fail();
+		nid expected[] = {
+			2,
+			0,
+		};
+		if(memcmp(a.adj.data, expected, sizeof(expected)) != 0) return fail();
+		
+		// Verify chunk offsets
+		if(chunks[0] != 0) return fail();
+		if(chunks[1] != 6) return fail();
+
+		free(chunks);
+		free(a.adj.data);
+	}
+
+	return 0;
+}