add kdtree

5 files changed, 108 insertions, 2 deletions

diff --git a/src/kdtree.c b/src/kdtree.c
new file mode 100644
index 0000000..6e9323b
--- /dev/null
+++ b/src/kdtree.c
@@ -0,0 +1,85 @@
+#include <stdlib.h>
+
+#include "kdtree.h"
+
+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;
+
+    if (root->left != NULL)
+        kdtree_walk(root->left, consume);
+    
+    consume(root);
+    
+    if (root->right != NULL)
+        kdtree_walk(root->right, consume);
+}
diff --git a/src/kdtree.h b/src/kdtree.h
new file mode 100644
index 0000000..8969533
--- /dev/null
+++ b/src/kdtree.h
@@ -0,0 +1,21 @@
+typedef struct KDTree {
+    unsigned int x;
+    unsigned int y;
+    char    *value;
+
+    struct KDTree *left;
+    struct KDTree *right;
+} kdtree_t;
+
+//! insert an element into a kdtree
+kdtree_t *  kdtree_insert(kdtree_t ** root, int x, int y, char * value);
+
+//! return a value from a kdtree, NULL if not present
+char * kdtree_search(kdtree_t *root, int x, int y);
+
+//! free memory for a kdtree
+void kdtree_free(kdtree_t **root);
+
+//! in order walk of nodes in kdtree
+void kdtree_walk(kdtree_t *root, void (* consume)(kdtree_t*));
+
diff --git a/src/tiled.h b/src/tiled.h
index 735c3a9..9890a72 100644
--- a/src/tiled.h
+++ b/src/tiled.h
@@ -1,6 +1,6 @@
 #include <raylib.h>
 
-#include "tiledfile.h"
+#include "tiledmap.h"
 
 #define SCREEN_W 1280
 #define SCREEN_H 720
diff --git a/src/tiledfile.c b/src/tiledmap.c
index eaeb814..69dcdaa 100644
--- a/src/tiledfile.c
+++ b/src/tiledmap.c
@@ -3,7 +3,7 @@
 #include <stdio.h>
 #include <string.h>
 
-#include "tiledfile.h"
+#include "tiledmap.h"
 
 const int i = 1;
 #define is_bigendian() ( (*(char*)&i) == 0 )
diff --git a/src/tiledfile.h b/src/tiledmap.h
index fb9c789..fb9c789 100644
--- a/src/tiledfile.h
+++ b/src/tiledmap.h