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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

#include <stdio.h>
#include <stdlib.h>

struct s_node {
	struct s_node *left;
	struct s_node *right;
	struct s_node *up;
	struct s_node *down;
	int no_links;
};

struct s_links {
	struct s_node *head;
	struct s_node **columns;
};

void init_node(struct s_node *node)
{
	node->left = NULL;
	node->right = NULL;
	node->up = NULL;
	node->down = NULL;
	node->no_links = 0;
}

struct s_links * create_links(char *data, int w, int h)
{
	struct s_links *links = malloc(sizeof(struct s_links));
	links->head = malloc(sizeof(struct s_node));
	links->columns = malloc(sizeof(struct s_node *) * w);
	init_node(links->head);
	// Create the columns
	for(int x = 0; x < w; x++) {
		links->columns[x] = malloc(sizeof(struct s_node));
		init_node(links->columns[x]);
		// we need to make sure the first one is linked to head
		if (x) {
			links->columns[x-1]->right = links->columns[x];
			links->columns[x]->left = links->columns[x-1];
		} else {
			links->head->right = links->columns[x];
			links->columns[x]->left = links->head;
		}
	}
	// parse the matrix
	for (int y = 0; y < h; y++) {
		struct s_node *first = NULL;
		struct s_node *n = NULL;
		for (int x = 0; x < w; x++) {
			if (data[y * w + x]) {
				if (first == NULL) {
					first = malloc(sizeof(struct s_node));
					init_node(first);
					n = first;
				} else {
					n->right = malloc(sizeof(struct s_node));
					init_node(n->right);
					n->right->left = n;
					n = n->right;
				}
				// we found a link, increment the counter
				links->columns[x]->no_links++;

				// setup the up / down link
				struct s_node *parent = NULL;
				// if column down isn't set, the parent should be the column
				if (links->columns[x]->down == NULL)
					parent = links->columns[x];
				// otherwise it should be what column down was pointing to before
				else
					parent = links->columns[x]->up;
				// setup the link to our node
				parent->down = n;
				n->up = parent;
				// setup the link to the column
				links->columns[x]->up = n;
				n->down = links->columns[x];
			}
		}
		// end of row, point first to the last node
		first->left = n;
		n->right = first;
		first = NULL;
	}
	return links;
}

int main(int argc, char **argv)
{
	char data[] = 
	{
		0,0,1,0,1,1,0,
		1,0,0,1,0,0,1,
		0,1,1,0,0,1,0,
		1,0,0,1,0,0,0,
		0,1,0,0,0,0,1,
		0,0,0,1,1,0,1
	};
	struct s_links *links = create_links(data, 7, 6);
	return 0;
}