src/tree.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
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;
}