From ad76589898e84732ada3a3cc8fcbbd0cba6083c5 Mon Sep 17 00:00:00 2001 From: Jesper Jensen Date: Mon, 24 Mar 2025 07:55:05 +0100 Subject: Produce the alignment --- cmd/main.c | 14 ++++-- src/leven.c | 17 +++---- src/leven.h | 2 +- test/contrained.c | 132 ++++++++++++++++++++++++++++++++++++++++++++++++------ 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 +#include 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; -- cgit v1.2.3