13 #include "../stdafx.h"
34 template <
typename T,
typename TxyFunc,
typename CoordT,
typename DistT>
56 if (this->free_list.empty()) {
57 this->nodes.emplace_back(element);
58 return this->nodes.size() - 1;
60 size_t newidx = this->free_list.back();
61 this->free_list.pop_back();
62 this->nodes[newidx] =
node{ element };
68 template <
typename It>
71 It mid = begin + (end - begin) / 2;
72 std::nth_element(begin, mid, end, [&](T a, T b) {
return this->
xyfunc(a, level % 2) < this->
xyfunc(b, level % 2); });
73 return this->
xyfunc(*mid, level % 2);
77 template <
typename It>
80 ptrdiff_t count = end - begin;
84 }
else if (count == 1) {
86 }
else if (count > 1) {
88 It split = std::partition(begin, end, [&](T v) {
return this->
xyfunc(v, level % 2) < split_coord; });
89 size_t newidx = this->
AddNode(*split);
90 this->nodes[newidx].left = this->
BuildSubtree(begin, split, level + 1);
91 this->nodes[newidx].right = this->
BuildSubtree(split + 1, end, level + 1);
99 bool Rebuild(
const T *include_element,
const T *exclude_element)
101 size_t initial_count = this->
Count();
102 if (initial_count < 8)
return false;
104 T root_element = this->nodes[this->
root].element;
105 std::vector<T> elements = this->
FreeSubtree(this->root);
106 elements.push_back(root_element);
108 if (include_element !=
nullptr) {
109 elements.push_back(*include_element);
112 if (exclude_element !=
nullptr) {
113 typename std::vector<T>::iterator removed = std::remove(elements.begin(), elements.end(), *exclude_element);
114 elements.erase(removed, elements.end());
118 this->
Build(elements.begin(), elements.end());
119 assert(initial_count == this->
Count());
129 node &n = this->nodes[node_idx];
134 CoordT ec = this->
xyfunc(element, dim);
136 size_t &next = (ec < nc) ? n.
left : n.
right;
140 size_t newidx = this->
AddNode(element);
142 node &nn = this->nodes[node_idx];
143 if (ec < nc) nn.
left = newidx;
else nn.
right = newidx;
155 std::vector<T> subtree_elements;
156 node &n = this->nodes[node_idx];
159 size_t first_free = this->free_list.size();
166 for (
size_t i = first_free; i < this->free_list.size(); i++) {
167 node &fn = this->nodes[this->free_list[i]];
168 subtree_elements.push_back(fn.
element);
174 return subtree_elements;
187 node &n = this->nodes[node_idx];
191 this->free_list.push_back(node_idx);
197 std::vector<T> subtree_elements = this->
FreeSubtree(node_idx);
198 return this->
BuildSubtree(subtree_elements.begin(), subtree_elements.end(), level);;
207 CoordT ec = this->
xyfunc(element, dim);
209 size_t next = (ec < nc) ? n.
left : n.
right;
213 if (new_branch != next) {
215 node &nn = this->nodes[node_idx];
216 if (ec < nc) nn.
left = new_branch;
else nn.
right = new_branch;
223 DistT ManhattanDistance(
const T &element, CoordT x, CoordT y)
const
225 return abs((DistT)this->
xyfunc(element, 0) - (DistT)x) +
abs((DistT)this->
xyfunc(element, 1) - (DistT)y);
233 if (a.second < b.second)
return a;
234 if (b.second < a.second)
return b;
235 if (a.first < b.first)
return a;
236 if (b.first < a.first)
return b;
245 const node &n = this->nodes[node_idx];
250 DistT thisdist = ManhattanDistance(n.
element, xy[0], xy[1]);
255 size_t next = (xy[dim] < c) ? n.
left : n.
right;
261 limit = std::min(best.second, limit);
265 size_t opposite = (xy[dim] >= c) ? n.
left : n.
right;
274 template <
typename Outputter>
275 void FindContainedRecursive(CoordT p1[2], CoordT p2[2],
size_t node_idx,
int level,
const Outputter &outputter)
const
280 const node &n = this->nodes[node_idx];
283 CoordT ec = this->
xyfunc(n.element, dim);
285 CoordT oc = this->
xyfunc(n.element, 1 - dim);
288 if (ec >= p1[dim] && ec < p2[dim] && oc >= p1[1 - dim] && oc < p2[1 - dim]) outputter(n.element);
291 if (p1[dim] < ec && n.left !=
INVALID_NODE) this->FindContainedRecursive(p1, p2, n.left, level + 1, outputter);
294 if (p2[dim] > ec && n.right !=
INVALID_NODE) this->FindContainedRecursive(p1, p2, n.right, level + 1, outputter);
301 const node &n = this->nodes[node_idx];
305 void IncrementUnbalanced(
size_t amount = 1)
307 this->unbalanced += amount;
313 size_t count = this->
Count();
314 if (count < 8)
return false;
315 return this->unbalanced > this->
Count() / 4;
319 void CheckInvariant(
size_t node_idx,
int level, CoordT min_x, CoordT max_x, CoordT min_y, CoordT max_y)
323 const node &n = this->nodes[node_idx];
332 if (level % 2 == 0) {
347 CheckInvariant(this->root, 0, std::numeric_limits<CoordT>::min(), std::numeric_limits<CoordT>::max(), std::numeric_limits<CoordT>::min(), std::numeric_limits<CoordT>::max());
361 template <
typename It>
365 this->free_list.clear();
366 this->unbalanced = 0;
367 if (begin == end)
return;
368 this->nodes.reserve(end - begin);
380 this->free_list.clear();
381 this->unbalanced = 0;
390 this->
Rebuild(
nullptr,
nullptr);
400 if (this->
Count() == 0) {
401 this->root = this->
AddNode(element);
405 this->IncrementUnbalanced();
419 size_t count = this->
Count();
420 if (count == 0)
return;
424 this->IncrementUnbalanced();
432 assert(this->free_list.size() <= this->nodes.size());
433 return this->nodes.size() - this->free_list.size();
443 assert(this->
Count() > 0);
445 CoordT xy[2] = { x, y };
458 template <
typename Outputter>
459 void FindContained(CoordT x1, CoordT y1, CoordT x2, CoordT y2,
const Outputter &outputter)
const
464 if (this->
Count() == 0)
return;
466 CoordT p1[2] = { x1, y1 };
467 CoordT p2[2] = { x2, y2 };
468 this->FindContainedRecursive(p1, p2, this->root, 0, outputter);
475 std::vector<T>
FindContained(CoordT x1, CoordT y1, CoordT x2, CoordT y2)
const
477 std::vector<T> result;
478 this->
FindContained(x1, y1, x2, y2, [&result](T e) {result.push_back(e); });
K-dimensional tree, specialised for 2-dimensional space.
void Build(It begin, It end)
Clear and rebuild the tree from a new sequence of elements,.
size_t Count() const
Get number of elements stored in tree.
void FindContained(CoordT x1, CoordT y1, CoordT x2, CoordT y2, const Outputter &outputter) const
Find all items contained within the given rectangle.
bool Rebuild(const T *include_element, const T *exclude_element)
Rebuild the tree with all existing elements, optionally adding or removing one more.
std::vector< size_t > free_list
List of dead indices in the nodes vector.
node_distance FindNearestRecursive(CoordT xy[2], size_t node_idx, int level, DistT limit=std::numeric_limits< DistT >::max()) const
Search a sub-tree for the element nearest to a given point.
void InsertRecursive(const T &element, size_t node_idx, int level)
Insert one element in the tree somewhere below node_idx.
void Rebuild()
Reconstruct the tree with the same elements, letting it be fully balanced.
std::pair< T, DistT > node_distance
A data element and its distance to a searched-for point.
void Insert(const T &element)
Insert a single element in the tree.
Kdtree(TxyFunc xyfunc)
Construct a new Kdtree with the given xyfunc.
void CheckInvariant()
Verify the invariant for the entire tree, does nothing unless KDTREE_DEBUG is defined.
std::vector< node > nodes
Pool of all nodes in the tree.
bool IsUnbalanced()
Check if the entire tree is in need of rebuilding.
TxyFunc xyfunc
Functor to extract a coordinate from an element.
static node_distance SelectNearestNodeDistance(const node_distance &a, const node_distance &b)
Ordering function for node_distance objects, elements with equal distance are ordered by less-than co...
void Remove(const T &element)
Remove a single element from the tree, if it exists.
static const size_t INVALID_NODE
Index value indicating no-such-node.
void CheckInvariant(size_t node_idx, int level, CoordT min_x, CoordT max_x, CoordT min_y, CoordT max_y)
Verify that the invariant is true for a sub-tree, assert if not.
size_t root
Index of root node.
size_t RemoveRecursive(const T &element, size_t node_idx, int level)
Find and remove one element from the tree.
size_t BuildSubtree(It begin, It end, int level)
Construct a subtree from elements between begin and end iterators, return index of root.
size_t AddNode(const T &element)
Create one new node in the tree, return its index in the pool.
T FindNearest(CoordT x, CoordT y) const
Find the element closest to given coordinate, in Manhattan distance.
std::vector< T > FreeSubtree(size_t node_idx)
Free all children of the given node.
CoordT SelectSplitCoord(It begin, It end, int level)
Find a coordinate value to split a range of elements at.
std::vector< T > FindContained(CoordT x1, CoordT y1, CoordT x2, CoordT y2) const
Find all items contained within the given rectangle.
void Clear()
Clear the tree.
size_t CountValue(const T &element, size_t node_idx) const
Debugging function, counts number of occurrences of an element regardless of its correct position in ...
size_t unbalanced
Number approximating how unbalanced the tree might be.
constexpr T abs(const T a)
Returns the absolute value of (scalar) variable.
Type of a node in the tree.
T element
Element stored at node.
size_t left
Index of node to the left, INVALID_NODE if none.
size_t right
Index of node to the right, INVALID_NODE if none.