1 files changed, 77 insertions, 0 deletions
diff --git a/src/tree.c b/src/tree.c
new file mode 100644
index 0000000..3bb2737
--- /dev/null
+++ b/src/tree.c
@@ -0,0 +1,77 @@
+#include "tree.h"
+
+#include <stdlib.h>
+
+void expand_alignment(struct Tree a_tree, struct Tree b_tree, uint32_t *alignment, enum Action *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;
+			}
+		}
+	}
+
+	emit_actions[current_action] = ACTION_END;
+}