diff options
| -rw-r--r-- | cmd/main.c | 12 | ||||
| -rw-r--r-- | src/leven.c | 15 | ||||
| -rw-r--r-- | test/contrained.c | 55 |
3 files changed, 79 insertions, 3 deletions
@@ -51,6 +51,18 @@ int main(int argc, char **argv) { 2, 1, 1, 0, 1, 2, 1, 1, 1, 1 ); + for(size_t i = 0; i < 4; i++) { + size_t a_tag_end = a_chunks[i]; + while(a[a_tag_end] != '>') a_tag_end++; + size_t a_len = a_tag_end - a_chunks[i]; + *imat_uint32_t(cost, i+1, 0) = a_len; + } + for(size_t j = 0; j < 4; j++) { + size_t b_tag_end = b_chunks[j]; + while(b[b_tag_end] != '>') b_tag_end++; + size_t b_len = b_tag_end - b_chunks[j]; + *imat_uint32_t(cost, 0, j+1) = b_len; + } for(size_t j = 0; j < 4; j++) { size_t b_tag_end = b_chunks[j]; while(b[b_tag_end] != '>') b_tag_end++; diff --git a/src/leven.c b/src/leven.c index f060929..14f1772 100644 --- a/src/leven.c +++ b/src/leven.c @@ -115,11 +115,13 @@ void constrained_tree_distance( while(b_adj_len < b.adj.stride && *imat_nid(b.adj, b_adj_len, j-1) != 0) b_adj_len++; for(size_t i = a.len; i > 0; i--) { + log("Calculate %ld %ld", i, j); size_t a_adj_len = 0; while(a_adj_len < a.adj.stride && *imat_nid(a.adj, a_adj_len, i-1) != 0) a_adj_len++; 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); uint32_t min_cost = *imat_uint32_t(cost_s, a_adj_len, b_adj_len); + log("min_cost = %d", min_cost); if(a_adj_len > 0) { uint32_t temp_min = UINT32_MAX; @@ -130,6 +132,7 @@ void constrained_tree_distance( } min_cost = min(min_cost, *imat_uint32_t(cost_f, i, 0) + temp_min); } + log("min_cost = %d", min_cost); if(b_adj_len > 0) { uint32_t temp_min = UINT32_MAX; @@ -140,10 +143,12 @@ void constrained_tree_distance( } min_cost = min(min_cost, *imat_uint32_t(cost_f, 0, j) + temp_min); } + log("min_cost = %d %d %d", min_cost, a_adj_len, b_adj_len); *imat_uint32_t(cost_f, i, j) = min_cost; min_cost = *imat_uint32_t(cost_f, i, j) + *imat_uint32_t(cost, i, j); + log("min_cost = %d", min_cost); if(a_adj_len > 0) { uint32_t temp_min = UINT32_MAX; @@ -154,20 +159,24 @@ void constrained_tree_distance( } min_cost = min(min_cost, *imat_uint32_t(cost_n, i, 0) + temp_min); } + log("min_cost = %d", min_cost); if(b_adj_len > 0) { uint32_t temp_min = UINT32_MAX; 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(a.adj, k, j-1)); + 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)); if(temp_min > cost) temp_min = cost; } min_cost = min(min_cost, *imat_uint32_t(cost_n, 0, j) + temp_min); } + log("min_cost = %d", min_cost); *imat_uint32_t(cost_n, i, j) = min_cost; } } + debug2D(cost_n, b.len+1); + debug2D(cost_f, b.len+1); } void constrained_tree_alignment ( @@ -311,10 +320,10 @@ void constrained_tree_alignment ( to_compute_head++; if(x == min_a) { slot[0] = *imat_nid(a.adj, x, i-1); - slot[1] = -1; + slot[1] = i; } else { slot[0] = *imat_nid(a.adj, x, i-1); - slot[1] = i; + slot[1] = -1; } } } else if(b_adj_len > 0 && *imat_uint32_t(cost_n, i, j) == *imat_uint32_t(cost_n, 0, j) + min_cost_b) { diff --git a/test/contrained.c b/test/contrained.c index 1af01a8..37fae1d 100644 --- a/test/contrained.c +++ b/test/contrained.c @@ -277,5 +277,60 @@ int main(int argc, char **argv) { ); } + { + struct Tree a = { + .adj = { + .data = (nid[]){2, 0}, + .stride = 1, + }, + .len = 2, + }; + + struct Tree b = { + .adj = { + .data = (nid[]){2, 3, 0}, + .stride = 1, + }, + .len = 3, + }; + + DECL_MAT_DATA(cost, uint32_t, 3, 4, + 0, 2, 2, + 2, 0, 2, + 2, 2, 2, + 2, 2, 0, + ); + DECL_MAT(cost_n, uint32_t, 3, 4); + DECL_MAT(cost_f, uint32_t, 3, 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) != 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 + ); + } + return 0; } |