summaryrefslogtreecommitdiffstats
path: root/kd-forest.h
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2020-05-03 10:55:16 -0400
committerGitHub <noreply@github.com>2020-05-03 10:55:16 -0400
commitce2904b4840611f769b92b55bf6d9b5afe84d3d7 (patch)
treea133319a302f95edf7a7a261262a8f24473bd21c /kd-forest.h
parentd95e93bf70f3351e6fd489284794ef7909fd94ce (diff)
parent2984e8f93fe88d0ee7eb3c0561dcd2da44807429 (diff)
downloadkd-forest-ce2904b4840611f769b92b55bf6d9b5afe84d3d7.tar.xz
Merge pull request #1 from tavianator/rust
Rewrite in rust
Diffstat (limited to 'kd-forest.h')
-rw-r--r--kd-forest.h56
1 files changed, 0 insertions, 56 deletions
diff --git a/kd-forest.h b/kd-forest.h
deleted file mode 100644
index 3651bfe..0000000
--- a/kd-forest.h
+++ /dev/null
@@ -1,56 +0,0 @@
-/*********************************************************************
- * kd-forest *
- * Copyright (C) 2014 Tavian Barnes <tavianator@tavianator.com> *
- * *
- * This program is free software. It comes without any warranty, to *
- * the extent permitted by applicable law. You can redistribute it *
- * and/or modify it under the terms of the Do What The Fuck You Want *
- * To Public License, Version 2, as published by Sam Hocevar. See *
- * the COPYING file or http://www.wtfpl.net/ for more details. *
- *********************************************************************/
-
-#ifndef KD_FOREST_H
-#define KD_FOREST_H
-
-#include <stdbool.h>
-#include <stddef.h>
-#include <stdint.h>
-
-#define KD_DIMEN 3
-
-// Single node in a k-d tree
-typedef struct kd_node_t {
- // Node coordinates
- double coords[KD_DIMEN];
- // Sub-trees
- struct kd_node_t *left, *right;
- // Used to keep track of which sub-tree a node is in during construction
- bool is_left;
- // Weak delete support
- bool removed;
-
- // Corresponding image position for this node
- unsigned int x, y;
-} kd_node_t;
-
-kd_node_t *new_kd_node(double coords[KD_DIMEN], unsigned int x, unsigned int y);
-
-// A forest of k-d trees
-typedef struct {
- // Array of k-d tree roots
- kd_node_t **roots;
- // Size and capacity of the roots array
- unsigned int roots_size, roots_capacity;
- // The actual size of this tree
- size_t size;
- // The size estimate for this tree, counting removed nodes
- size_t size_est;
-} kd_forest_t;
-
-void kdf_init(kd_forest_t *kdf);
-void kdf_destroy(kd_forest_t *kdf);
-void kdf_insert(kd_forest_t *kdf, kd_node_t *node);
-void kdf_remove(kd_forest_t *kdf, kd_node_t *node);
-kd_node_t *kdf_find_nearest(const kd_forest_t *kdf, const double target[KD_DIMEN]);
-
-#endif // KD_FOREST_H