summaryrefslogtreecommitdiff
path: root/test
diff options
context:
space:
mode:
Diffstat (limited to 'test')
-rw-r--r--test/contrained.c281
-rw-r--r--test/leven.c109
-rw-r--r--test/parse.c114
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;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2026-08-03 19:14:17 +0000