diff options
author | davidovski <david@davidovski.xyz> | 2023-07-21 00:21:17 +0200 |
---|---|---|
committer | davidovski <david@davidovski.xyz> | 2023-07-21 00:21:17 +0200 |
commit | 1aceb70c5659677929bfbbd3f6480bacd8d75e35 (patch) | |
tree | 2ac18694e329c2aab894173bf3eb5165a9678a4c /src | |
parent | 894e465ffcdaf706eaa3de9e426d4c0c10d4513b (diff) |
add kdtree
Diffstat (limited to 'src')
-rw-r--r-- | src/kdtree.c | 85 | ||||
-rw-r--r-- | src/kdtree.h | 21 | ||||
-rw-r--r-- | src/tiled.h | 2 | ||||
-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 |