Separate the tree expander outHEADmaster

1 files changed, 49 insertions, 106 deletions

diff --git a/cmd/main.c b/cmd/main.c
index 5e72fea..dd95024 100644
--- a/cmd/main.c
+++ b/cmd/main.c
@@ -11,23 +11,11 @@
 #include "leven.h"
 #include "parse.h"
 #include "log.h"
+#include "tree.h"
 
-#define ACTIONS(X) \
-        X(ACTION_MATCH) \
-        X(ACTION_DEL_A) \
-        X(ACTION_ADD_B) \
-        X(ACTION_ET) \
-
-#define ENUM_VALUE(NAME) NAME,
-#define STRING_ARRAY_VALUE(NAME) #NAME,
-
-enum Action {
-    ACTIONS(ENUM_VALUE)
-};
-
-static const char *ActionNames[] = {
-    ACTIONS(STRING_ARRAY_VALUE)
-};
+size_t max(size_t a, size_t b) {
+	return a > b ? a : b;
+}
 
 int main(int argc, char **argv) {
 	int rc;
@@ -74,18 +62,41 @@ int main(int argc, char **argv) {
 	size_t *b_opens = malloc(b_tree.len * sizeof(size_t));
 
 	{
-		size_t *a_cursor = a_opens;
-		for(size_t i = 0; i < a_tree.len*2; i++) {
-			if(a_chunks[i] >= 0) {
-				*(a_cursor++) = a_chunks[i];
+		size_t *stack_base = malloc(max(a_tree.len, b_tree.len) * sizeof(size_t));
+		{
+			size_t *stack = stack_base;
+			size_t *write_cursor = a_opens;
+			ssize_t *read_cursor = a_chunks;
+			struct Tree tree = a_tree;
+
+			for(size_t i = 0; i < tree.len; i++) {
+				*(write_cursor++) = *(read_cursor++);
+
+				while(*stack < tree.adj.stride && *imat_nid(tree.adj, *stack, i) != 0) (*stack)++;
+				stack++;
+				// @CLEANUP: Maybe it would be nicer if we just added a fake
+				// element to the start of the array to abosrb the read
+				while(stack > stack_base && stack[-1] == 0) {
+					(stack--);
+					(*stack)--;
+				}
 			}
 		}
-	}
-	{
-		size_t *b_cursor = b_opens;
-		for(size_t i = 0; i < b_tree.len*2; i++) {
-			if(b_chunks[i] >= 0) {
-				*(b_cursor++) = b_chunks[i];
+		{
+			size_t *stack = stack_base;
+			size_t *write_cursor = b_opens;
+			ssize_t *read_cursor = b_chunks;
+			struct Tree tree = b_tree;
+
+			for(size_t i = 0; i < tree.len; i++) {
+				*(write_cursor++) = *(read_cursor++);
+
+				while(*stack < tree.adj.stride && *imat_nid(tree.adj, *stack, i) != 0) (*stack)++;
+				stack++;
+				while(stack > stack_base && stack[-1] == 0) {
+					(stack--);
+					(*stack)--;
+				}
 			}
 		}
 	}
@@ -97,13 +108,13 @@ int main(int argc, char **argv) {
 		*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];
+		size_t b_tag_end = b_opens[j];
 		while(b[b_tag_end] != '>') b_tag_end++;
-		size_t b_len = b_tag_end - b_chunks[j];
+		size_t b_len = b_tag_end - b_opens[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];
+		size_t b_tag_end = b_opens[j];
 		while(b[b_tag_end] != '>') b_tag_end++;
 		for(size_t i = 0; i < 4; i++) {
 			size_t a_tag_end = a_opens[i];
@@ -111,11 +122,11 @@ int main(int argc, char **argv) {
 			log("%ld, %ld", i, j);
 			
 			size_t a_len = a_tag_end - a_opens[i];
-			size_t b_len = b_tag_end - b_chunks[j];
+			size_t b_len = b_tag_end - b_opens[j];
 			log("B: %ld, A: %ld", b_len, a_len);
-			log("A: %.*s, B: %.*s", (int)a_len, a + a_opens[i], (int)b_len, b + b_chunks[j]);
+			log("A: %.*s, B: %.*s", (int)a_len, a + a_opens[i], (int)b_len, b + b_opens[j]);
 
-			*imat_uint32_t(cost, i+1, j+1) = !(a_len == b_len && memcmp(a + a_opens[i], b + b_chunks[j], a_len) == 0) * 1;
+			*imat_uint32_t(cost, i+1, j+1) = !(a_len == b_len && memcmp(a + a_opens[i], b + b_opens[j], a_len) == 0) * 1;
 		}
 	}
 	printf("\n");
@@ -188,88 +199,20 @@ int main(int argc, char **argv) {
 	// going to solve right now. I think we may have to lookup what decision
 	// we made for the open tag
 	// The worst case would be that we remove the whole A tree and the whole B tree
-	enum Action *emit_actions = malloc((a_tree.len + b_tree.len) * 2 * sizeof(*emit_actions));
-	size_t current_action = 0;
-	size_t a_cursor = 0;
-	size_t b_cursor = 0;
-	size_t alignment_cursor = 0;
-
-	size_t *a_close = malloc(a_tree.len * sizeof(size_t));
-	size_t a_close_top = 0;
-	size_t *b_close = malloc(b_tree.len * sizeof(size_t));
-	size_t b_close_top = 0;
-
-	while(a_cursor < a_tree.len && b_cursor < b_tree.len) {
-		if(alignment[alignment_cursor] == 0) {
-			alignment_cursor++;
-			emit_actions[current_action++] = ACTION_ADD_B;
-
-			b_close[b_close_top] = 0;
-			while(b_close[b_close_top] < b_tree.adj.stride && *imat_nid(b_tree.adj, b_close[b_close_top], b_cursor) != 0)
-				b_close[b_close_top]++;
-			b_close_top++;
-
-			b_cursor++;
-		} else if(a_cursor + 1 < alignment[alignment_cursor]) {
-			emit_actions[current_action++] = ACTION_DEL_A;
-
-			a_close[a_close_top] = 0;
-			while(a_close[a_close_top] < a_tree.adj.stride && *imat_nid(a_tree.adj, a_close[a_close_top], a_cursor) != 0)
-				a_close[a_close_top]++;
-			a_close_top++;
-
-			a_cursor++;
-		} else {
-			alignment_cursor++;
-			emit_actions[current_action++] = ACTION_MATCH;
-
-			b_close[b_close_top] = 0;
-			while(b_close[b_close_top] < b_tree.adj.stride && *imat_nid(b_tree.adj, b_close[b_close_top], b_cursor) != 0)
-				b_close[b_close_top]++;
-			b_close_top++;
-
-			a_close[a_close_top] = 0;
-			while(a_close[a_close_top] < a_tree.adj.stride && *imat_nid(a_tree.adj, a_close[a_close_top], a_cursor) != 0)
-				a_close[a_close_top]++;
-			a_close_top++;
-
-			a_cursor++;
-			b_cursor++;
-		}
-
-		while(a_close[a_close_top-1] == 0 || b_close[b_close_top-1] == 0) {
-			if(a_close[a_close_top-1] == 0 && b_close[b_close_top-1] == 0) {
-				a_close_top--;
-				a_close[a_close_top-1]--;
-				b_close_top--;
-				b_close[b_close_top-1]--;
-
-				emit_actions[current_action++] = ACTION_MATCH;
-			} else if(a_close[a_close_top-1] == 0) {
-				a_close_top--;
-				a_close[a_close_top-1]--;
-
-				emit_actions[current_action++] = ACTION_DEL_A;
-			} else if(b_close[b_close_top-1] == 0) {
-				b_close_top--;
-				b_close[b_close_top-1]--;
-
-				emit_actions[current_action++] = ACTION_ADD_B;
-			}
-		}
-	}
+	enum Action *emit_actions = malloc((a_tree.len + b_tree.len) * 2 * sizeof(*emit_actions) + 1);
+	expand_alignment(a_tree, b_tree, alignment, emit_actions);
 
 	logb("Actions: ");
-	for(size_t i = 0; i < current_action; i++) {
+	for(size_t i = 0; emit_actions[i] != ACTION_END; i++) {
 		lognl();
 		logc("    %s", ActionNames[emit_actions[i]]);
 	}
 	loge();
 	
-	b_cursor = 0;
-	a_cursor = 0;
+	size_t a_cursor = 0;
+	size_t b_cursor = 0;
 
-	for(size_t i = 0; i < current_action; i++) {
+	for(size_t i = 0; emit_actions[i] != ACTION_END; i++) {
 		size_t bc_len = (b_cursor+1 >= b_tree.len*2 ? strlen(b) : b_chunks[b_cursor+1]) - b_chunks[b_cursor];
 		size_t ac_len = (a_cursor+1 >= a_tree.len*2 ? strlen(a) : a_chunks[a_cursor+1]) - a_chunks[a_cursor];
 		if(emit_actions[i] == ACTION_MATCH) {