Add some cost calculation

3 files changed, 79 insertions, 3 deletions

diff --git a/cmd/main.c b/cmd/main.c
index 4e4c42d..62292f9 100644
--- a/cmd/main.c
+++ b/cmd/main.c
@@ -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;
 }