summaryrefslogtreecommitdiff
path: root/cmd
diff options
context:
space:
mode:
Diffstat (limited to 'cmd')
-rw-r--r--cmd/main.c155
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) {
generated by cgit v1.2.3 (git 2.25.1) at 2026-08-03 19:13:53 +0000