summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authordavidovski <david@davidovski.xyz>2023-07-21 00:21:17 +0200
committerdavidovski <david@davidovski.xyz>2023-07-21 00:21:17 +0200
commit1aceb70c5659677929bfbbd3f6480bacd8d75e35 (patch)
tree2ac18694e329c2aab894173bf3eb5165a9678a4c /src
parent894e465ffcdaf706eaa3de9e426d4c0c10d4513b (diff)
add kdtree
Diffstat (limited to 'src')
-rw-r--r--src/kdtree.c85
-rw-r--r--src/kdtree.h21
-rw-r--r--src/tiled.h2
-rw-r--r--src/tiledmap.c (renamed from src/tiledfile.c)2
-rw-r--r--src/tiledmap.h (renamed from src/tiledfile.h)0
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