summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--cmd/main.c14
-rw-r--r--src/leven.c17
-rw-r--r--src/leven.h2
-rw-r--r--test/contrained.c132
4 files changed, 139 insertions, 26 deletions
diff --git a/cmd/main.c b/cmd/main.c
index d143766..797e043 100644
--- a/cmd/main.c
+++ b/cmd/main.c
@@ -15,14 +15,14 @@ int main(int argc, char **argv) {
int rc;
char *a;
{
- int fd = open("/Users/delusional/Documents/xmldiff/file_a.xml", O_RDONLY);
+ int fd = open("../xmldiff/file_a.xml", O_RDONLY);
int len = lseek(fd, 0, SEEK_END);
a = mmap(0, len, PROT_READ, MAP_PRIVATE, fd, 0);
}
char* b;
{
- int fd = open("/Users/delusional/Documents/xmldiff/file_b.xml", O_RDONLY);
+ int fd = open("../xmldiff/file_b.xml", O_RDONLY);
int len = lseek(fd, 0, SEEK_END);
b = mmap(0, len, PROT_READ, MAP_PRIVATE, fd, 0);
}
@@ -128,8 +128,8 @@ int main(int argc, char **argv) {
log("Final Cost %d", *imat_uint32_t(cost_n, 1, 1));
- DECL_MAT(alignment, uint32_t, 2, 2);
- uint32_t adj_alignment[2] = {0, 0};
+ uint32_t *alignment = malloc(b_tree.len * sizeof(*alignment));
+ uint32_t *adj_alignment = malloc(b_tree.adj.stride * sizeof(*adj_alignment));
constrained_tree_alignment(
a_tree,
b_tree,
@@ -138,5 +138,11 @@ int main(int argc, char **argv) {
alignment
);
+ logb("Alignment: ");
+ for(size_t i = 0; i < b_tree.len; i++) {
+ logc("%d ", alignment[i]);
+ }
+ loge();
+
return 0;
}
diff --git a/src/leven.c b/src/leven.c
index efd5247..d110a64 100644
--- a/src/leven.c
+++ b/src/leven.c
@@ -181,7 +181,7 @@ void constrained_tree_alignment (
CTedData data,
uint32_t *adj_alignment,
- mat_uint32_t alignment
+ uint32_t *alignment
) {
mat_uint32_t cost = data.cost;
@@ -238,11 +238,11 @@ void constrained_tree_alignment (
size_t b_adj_len = 0;
while(b_adj_len < b.adj.stride && *imat_nid(b.adj, b_adj_len, j-1) != 0) b_adj_len++;
- uint32_t min_cost_a = UINT32_MAX;
+ int32_t min_cost_a = INT32_MAX;
ssize_t min_a = -1;
if(a_adj_len > 0) {
for(uint32_t k = 0; k < a_adj_len; k++) {
- uint32_t cost = *imat_uint32_t(cost_n, *imat_nid(a.adj, k, i-1), j) - *imat_uint32_t(cost_n, *imat_nid(a.adj, k, i-1), 0);
+ int32_t cost = *imat_uint32_t(cost_n, *imat_nid(a.adj, k, i-1), j) - *imat_uint32_t(cost_n, *imat_nid(a.adj, k, i-1), 0);
if(min_cost_a > cost) {
min_cost_a = cost;
min_a = k;
@@ -250,11 +250,11 @@ void constrained_tree_alignment (
}
}
- uint32_t min_cost_b = UINT32_MAX;
+ int32_t min_cost_b = UINT32_MAX;
ssize_t min_b = -1;
if(b_adj_len > 0) {
for(uint32_t k = 0; k < b_adj_len; k++) {
- uint32_t cost = *imat_uint32_t(cost_n, i, *imat_nid(b.adj, k, j-1)) - *imat_uint32_t(cost_n, 0, *imat_nid(b.adj, k, j-1));
+ int32_t cost = *imat_uint32_t(cost_n, i, *imat_nid(b.adj, k, j-1)) - *imat_uint32_t(cost_n, 0, *imat_nid(b.adj, k, j-1));
if(min_cost_b > cost) {
min_cost_b = cost;
min_b = k;
@@ -263,7 +263,7 @@ void constrained_tree_alignment (
}
if(*imat_uint32_t(cost_n, i, j) == *imat_uint32_t(cost_f, i, j) + *imat_uint32_t(cost, i, j)) {
- log("MATCH %d %d", i, j);
+ *(alignment++) = i;
// Compare the forests underneath this node
string_edit_distance(imat_nid(a.adj, 0, i-1), a_adj_len, imat_nid(b.adj, 0, j-1), b_adj_len, cost_n, cost_s);
assert(*imat_uint32_t(cost_s, a_adj_len, b_adj_len) == *imat_uint32_t(cost_f, i, j));
@@ -311,7 +311,8 @@ void constrained_tree_alignment (
}
} else if(a_adj_len > 0 && *imat_uint32_t(cost_n, i, j) == *imat_uint32_t(cost_n, i, 0) + min_cost_a) {
// Remove this node and replace it with one of its children
- log("REMOVE %ld %ld", i, j);
+ // This doesn't write to the alignment since we dont map operations
+ // on a
for(size_t x = 0; x < a_adj_len; x++) {
uint32_t *slot = imat_uint32_t(to_compute, 0, to_compute_head);
to_compute_head++;
@@ -325,7 +326,7 @@ void constrained_tree_alignment (
}
} else if(b_adj_len > 0 && *imat_uint32_t(cost_n, i, j) == *imat_uint32_t(cost_n, 0, j) + min_cost_b) {
// Inject a node here, moving the current node (from a) into the child forest.
- log("ADD %ld %ld", i, j);
+ *(alignment++) = 0;
for(size_t x = 0; x < b_adj_len; x++) {
uint32_t *slot = imat_uint32_t(to_compute, 0, to_compute_head);
to_compute_head++;
diff --git a/src/leven.h b/src/leven.h
index 8f6fcf4..bdd27f6 100644
--- a/src/leven.h
+++ b/src/leven.h
@@ -54,5 +54,5 @@ void constrained_tree_alignment(
const struct Tree b,
CTedData data,
uint32_t *adj_alignment,
- mat_uint32_t alignment
+ uint32_t *alignment
);
diff --git a/test/contrained.c b/test/contrained.c
index c7e2c03..c930960 100644
--- a/test/contrained.c
+++ b/test/contrained.c
@@ -1,6 +1,8 @@
#include "leven.h"
#include "log.h"
+#include <stdlib.h>
+#include <string.h>
DECL_MAT3(no_trace, uint32_t, 0, 0, 0);
@@ -47,8 +49,8 @@ int main(int argc, char **argv) {
return 1;
}
- DECL_MAT(alignment, uint32_t, 2, 2);
- uint32_t adj_alignment[2] = {0, 0};
+ uint32_t alignment[1];
+ uint32_t adj_alignment[2];
constrained_tree_alignment(
a,
b,
@@ -61,6 +63,12 @@ int main(int argc, char **argv) {
adj_alignment,
alignment
);
+
+ if(memcmp(alignment, (uint32_t[]) {
+ 1
+ }, sizeof(alignment)) != 0) {
+ return 1;
+ }
}
{
@@ -104,8 +112,8 @@ int main(int argc, char **argv) {
return 1;
}
- DECL_MAT(alignment, uint32_t, 3, 2);
- uint32_t adj_alignment[2] = {0, 0};
+ uint32_t alignment[1];
+ uint32_t adj_alignment[2];
constrained_tree_alignment(
a,
b,
@@ -118,6 +126,12 @@ int main(int argc, char **argv) {
adj_alignment,
alignment
);
+
+ if(memcmp(alignment, (uint32_t[]) {
+ 2
+ }, sizeof(alignment)) != 0) {
+ return 1;
+ }
}
{
@@ -162,8 +176,8 @@ int main(int argc, char **argv) {
return 1;
}
- DECL_MAT(alignment, uint32_t, 2, 2);
- uint32_t adj_alignment[2] = {0, 0};
+ uint32_t alignment[2];
+ uint32_t adj_alignment[2];
constrained_tree_alignment(
a,
b,
@@ -176,6 +190,12 @@ int main(int argc, char **argv) {
adj_alignment,
alignment
);
+
+ if(memcmp(alignment, (uint32_t[]) {
+ 1, 2
+ }, sizeof(alignment)) != 0) {
+ return 1;
+ }
}
{
@@ -222,8 +242,8 @@ int main(int argc, char **argv) {
return 1;
}
- DECL_MAT(alignment, uint32_t, 2, 2);
- uint32_t adj_alignment[2] = {0, 0};
+ uint32_t alignment[4];
+ uint32_t adj_alignment[2];
constrained_tree_alignment(
a,
b,
@@ -236,6 +256,13 @@ int main(int argc, char **argv) {
adj_alignment,
alignment
);
+
+ if(memcmp(alignment, (uint32_t[]) {
+ 0, 1, 2, 3
+ }, sizeof(alignment)) != 0) {
+ abort();
+ return 1;
+ }
}
{
@@ -281,8 +308,8 @@ int main(int argc, char **argv) {
return 1;
}
- DECL_MAT(alignment, uint32_t, 2, 2);
- uint32_t adj_alignment[2] = {0, 0};
+ uint32_t alignment[3];
+ uint32_t adj_alignment[2];
constrained_tree_alignment(
a,
b,
@@ -295,6 +322,13 @@ int main(int argc, char **argv) {
adj_alignment,
alignment
);
+
+ if(memcmp(alignment, (uint32_t[]) {
+ 1, 0, 3
+ }, sizeof(alignment)) != 0) {
+ abort();
+ return 1;
+ }
}
{
@@ -322,7 +356,72 @@ int main(int argc, char **argv) {
);
DECL_MAT(cost_n, uint32_t, 3, 4);
DECL_MAT(cost_f, uint32_t, 3, 4);
- DECL_MAT(cost_s, uint32_t, 3, 2);
+ DECL_MAT(cost_s, uint32_t, 2, 2);
+
+ constrained_tree_distance(
+ a,
+ b,
+ (CTedData) {
+ cost,
+ cost_n,
+ cost_f,
+ cost_s,
+ }
+ );
+
+ if(*imat_uint32_t(cost_n, 1, 1) != 2) {
+ log("Test Fail\n");
+ return 1;
+ }
+
+ uint32_t alignment[3];
+ uint32_t adj_alignment[2];
+ constrained_tree_alignment(
+ a,
+ b,
+ (CTedData) {
+ cost,
+ cost_n,
+ cost_f,
+ cost_s,
+ },
+ adj_alignment,
+ alignment
+ );
+
+ if(memcmp(alignment, (uint32_t[]) {
+ 1, 0, 2
+ }, sizeof(alignment)) != 0) {
+ abort();
+ return 1;
+ }
+ }
+
+ {
+ struct Tree a = {
+ .adj = {
+ .data = (nid[]){2, 3, 0},
+ .stride = 1,
+ },
+ .len = 3,
+ };
+
+ struct Tree b = {
+ .adj = {
+ .data = (nid[]){2, 0},
+ .stride = 1,
+ },
+ .len = 2,
+ };
+
+ DECL_MAT_DATA(cost, uint32_t, 4, 3,
+ 0, 2, 2, 2,
+ 2, 0, 2, 2,
+ 2, 2, 2, 0,
+ );
+ DECL_MAT(cost_n, uint32_t, 4, 3);
+ DECL_MAT(cost_f, uint32_t, 4, 3);
+ DECL_MAT(cost_s, uint32_t, 2, 2);
constrained_tree_distance(
a,
@@ -340,8 +439,8 @@ int main(int argc, char **argv) {
return 1;
}
- DECL_MAT(alignment, uint32_t, 2, 2);
- uint32_t adj_alignment[2] = {0, 0};
+ uint32_t alignment[2];
+ uint32_t adj_alignment[2];
constrained_tree_alignment(
a,
b,
@@ -354,6 +453,13 @@ int main(int argc, char **argv) {
adj_alignment,
alignment
);
+
+ if(memcmp(alignment, (uint32_t[]) {
+ 1, 3
+ }, sizeof(alignment)) != 0) {
+ abort();
+ return 1;
+ }
}
return 0;
generated by cgit v1.2.3 (git 2.25.1) at 2026-08-03 18:16:07 +0000