From e5a5469c5ea0df72c5e0bb6f742923ba692ea7f8 Mon Sep 17 00:00:00 2001
From: Jesper Jensen <jesper@jnsn.dev>
Date: Sat, 29 Mar 2025 23:28:17 +0100
Subject: Separate the tree expander out

---
 src/tree.c | 77 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 src/tree.h | 23 +++++++++++++++++++
 2 files changed, 100 insertions(+)
 create mode 100644 src/tree.c
 create mode 100644 src/tree.h

(limited to 'src')

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;
+}
diff --git a/src/tree.h b/src/tree.h
new file mode 100644
index 0000000..e1dd424
--- /dev/null
+++ b/src/tree.h
@@ -0,0 +1,23 @@
+#pragma once
+
+#include "parse.h"
+#include <stddef.h>
+
+#define ACTIONS(X) \
+        X(ACTION_MATCH) \
+        X(ACTION_DEL_A) \
+        X(ACTION_ADD_B) \
+        X(ACTION_END) \
+
+#define ENUM_VALUE(NAME) NAME,
+#define STRING_ARRAY_VALUE(NAME) #NAME,
+
+enum Action {
+    ACTIONS(ENUM_VALUE)
+};
+
+static const char *ActionNames[] = {
+    ACTIONS(STRING_ARRAY_VALUE)
+};
+
+void expand_alignment(struct Tree a_tree, struct Tree b_tree, uint32_t *alignment, enum Action *emit_actions);
-- 
cgit v1.2.3