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
102
|
#include "kdtree.h"
void print_node(kdtree_t *tree) {
printf("[%d,%d] %ld\n", tree->x, tree->y, (long)tree->value);
}
kdtree_t * kdtree_create(int x, int y, char * value) {
kdtree_t * tree = malloc(sizeof(kdtree_t));
tree->x = x;
tree->y = y;
tree->value = value;
tree->left = NULL;
tree->right = NULL;
return tree;
}
kdtree_t * kdtree_insert_rec(kdtree_t **root, int x, int y, char * value, int depth) {
if ((*root) == NULL)
return *root = kdtree_create(x, y, value);
int e = x < (*root)->x;
if (depth % 2 == 1) e = y < (*root)->y;
if (e)
return kdtree_insert_rec(&(*root)->left, x, y, value, depth+1);
return kdtree_insert_rec(&(*root)->right, x, y, value, depth+1);
}
kdtree_t * kdtree_insert(kdtree_t ** root, int x, int y, char * value) {
return kdtree_insert_rec(root, x, y, value, 0);
}
char * kdtree_search_rec(kdtree_t *root, int x, int y, int depth) {
if (root == NULL)
return NULL;
if (root->x == x && root->y == y)
return root->value;
unsigned int r, p;
if (depth % 2 == 0) {
r = root->x;
p = x;
} else {
r = root->y;
p = y;
}
if (p < r) {
if (root->left == NULL)
return NULL;
return kdtree_search_rec(root->left, x, y, depth+1);
}
if (root->right == NULL)
return NULL;
return kdtree_search_rec(root->right, x, y, depth+1);
}
char * kdtree_search(kdtree_t *root, int x, int y) {
return kdtree_search_rec(root, x, y, 0);
}
void kdtree_free(kdtree_t **root) {
if ((*root)->left != NULL)
kdtree_free(&(*root)->left);
if ((*root)->right != NULL)
kdtree_free(&(*root)->right);
free(*root);
}
void kdtree_walk(kdtree_t *root, void (* consume)(kdtree_t*)) {
if (root == NULL)
return;
kdtree_walk(root->left, consume);
consume(root);
kdtree_walk(root->right, consume);
}
int kdtree_size(kdtree_t *root) {
if (root == NULL)
return 0;
return 1 + kdtree_size(root->left) + kdtree_size(root->right);
}
int kdtree_fwrite(kdtree_t *root, FILE *file) {
return fwrite(root, 1, sizeof(kdtree_t), file)
| kdtree_fwrite(root->left, file)
| kdtree_fwrite(root->right, file);
}
int kdtree_fread(kdtree_t **root, FILE *file) {
return fread(*root, 1, sizeof(kdtree_t), file)
| kdtree_fread(&(*root)->left, file)
| kdtree_fread(&(*root)->right, file);
}
|
