NDEVR
API Documentation
Tree.hpp
1/*--------------------------------------------------------------------------------------------
2Copyright (c) 2019, NDEVR LLC
3tyler.parke@ndevr.org
4 __ __ ____ _____ __ __ _______
5 | \ | | | __ \ | ___|\ \ / / | __ \
6 | \ | | | | \ \ | |___ \ \ / / | |__) |
7 | . \| | | |__/ / | |___ \ V / | _ /
8 | |\ |_|_____/__|_____|___\_/____| | \ \
9 |__| \__________________________________| \__\
10
11Subject to the terms of the Enterprise+ Agreement, NDEVR hereby grants
12Licensee a limited, non-exclusive, non-transferable, royalty-free license
13(without the right to sublicense) to use the API solely for the purpose of
14Licensee's internal development efforts to develop applications for which
15the API was provided.
16
17The above copyright notice and this permission notice shall be included in all
18copies or substantial portions of the Software.
19
20THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
21INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
22PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
23FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
24OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
25DEALINGS IN THE SOFTWARE.
26
27Library: Tree
28File: Tree
29Included in API: False
30Author(s): Tyler Parke
31\internal
32 *-----------------------------------------------------------------------------------------**/
33#pragma once
34#include <NDEVR/TreeIterator.h>
35#include <NDEVR/Node.h>
36#include <NDEVR/BaseValues.h>
37#include <NDEVR/Buffer.h>
38#include <NDEVR/Bounds.h>
39#include <NDEVR/InfoPipe.h>
40#include <NDEVR/Vector.h>
41#include <NDEVR/VectorFunctions.h>
42#include <NDEVR/Intersection.h>
43#include <NDEVR/BinaryHeap.h>
44
45
46namespace NDEVR
47{
48 class TreeObject
49 {
50
51 };
52
53 template<class t_node_type, class t_type, uint01 t_node_child_size>
54 class TreeBase : public TreeObject
55 {
56 static_assert(std::is_base_of<TreeNode, t_node_type>::value, "t_node_type must inherit from Node");
57 protected:
58 explicit TreeBase(uint04 bucket_size)
59 : m_indices(bucket_size)
60 , m_nodes(1, t_node_type(0))
61 , m_bucket_size(bucket_size)
62 {
63 m_indices.addSpace<false>(bucket_size);
64 }
65 TreeBase(const TreeBase& tree)
66 : m_indices(tree.m_indices)
67 , m_nodes(tree.m_nodes)
68 , m_available_node_positions(tree.m_available_node_positions)
69 , m_available_indexed_positions(tree.m_available_indexed_positions)
70 , m_bucket_size(tree.m_bucket_size)
71 {}
72 TreeBase(TreeBase&& tree)
73 : m_indices()
74 , m_nodes()
75 , m_available_node_positions()
76 , m_available_indexed_positions()
77 , m_bucket_size(tree.m_bucket_size)
78 {
79 std::swap(m_indices, tree.m_indices);
80 std::swap(m_nodes, tree.m_nodes);
81 std::swap(m_available_node_positions, tree.m_available_node_positions);
82 std::swap(m_available_indexed_positions, tree.m_available_indexed_positions);
83 }
84 TreeBase(const Buffer<t_node_type>& nodes, const Buffer<uint04>& indices, bool is_read_only)
85 : m_indices(indices)
86 , m_nodes(nodes)
87 , m_available_node_positions()
88 , m_available_indexed_positions()
89 {
90 UNUSED(is_read_only);
91 }
92 virtual ~TreeBase(){}
93 public:
94 uint04 getIndex(uint04 index) const { return m_indices[index]; }
95 void clear()
96 {
97 m_indices.clear();
98 m_indices.addSpace<false>(m_bucket_size);
99 m_nodes.clear();
100 m_nodes.add(t_node_type(0));
101 m_available_node_positions.clear();
102 m_available_indexed_positions.clear();
103 }
104
105 uint04 getNumberOfNodes() const
106 {
107 return m_nodes.size();
108 }
109 const t_node_type& getNode(uint04 node_id) const
110 {
111 return m_nodes[node_id];
112 }
113
114 void removeIndices(const Buffer<bool>& deletion_indices)
115 {
116 Buffer<uint04> new_indices(deletion_indices.size());
117 uint04 index = 0;
118 for (uint04 i = 0; i < deletion_indices.size(); i++)
119 {
120 new_indices.add(index);
121 if (!deletion_indices[i])
122 index++;
123 }
124 TreeIterator iterator(root_node);
125 while (iterator.valid())
126 {
127 uint04 node_index = iterator.get();
128 t_node_type& node = m_nodes[node_index];
129 iterator.pop();
130 if (node.isLeaf())
131 {
132 const uint04 end = node.end();
133 for (uint04 i = node.begin(); i < end; i++)
134 {
135 lib_assert(!deletion_indices[m_indices[i]], "Must Call remove values prior to removeIndices");
136 m_indices[i] = new_indices[m_indices[i]];
137 }
138 }
139 else
140 {
141 iterator.addAndGoToIndices(node.childNodeStart(), t_node_child_size);
142 }
143 }
144 }
145
146 void removeIndices(uint04 begin, uint04 end)
147 {
148 uint04 size = end - begin;
149 TreeIterator iterator(root_node);
150 while (iterator.valid())
151 {
152 uint04 node_index = iterator.get();
153 t_node_type& node = m_nodes[node_index];
154 iterator.pop();
155 if (node.isLeaf())
156 {
157 const uint04 node_end = node.end();
158 for (uint04 i = node.begin(); i < node_end; i++)
159 {
160 lib_assert(end <= m_indices[i] || begin > m_indices[i], "Must Call remove values prior to removeIndices");
161 if (m_indices[i] >= end)
162 m_indices[i] -= size;
163 }
164 }
165 else
166 {
167 iterator.addAndGoToIndices(node.childNodeStart(), t_node_child_size);
168 }
169 }
170 }
171
172
173 void addIndices(const Buffer<bool>& insertion_indices)
174 {
175 Buffer<uint04> index_mapping(m_indices.size());
176 uint04 index = 0;
177 for (uint04 i = 0; i < insertion_indices.size(); i++)
178 {
179 if (!insertion_indices[i])
180 index_mapping.add(index);
181 index++;
182 }
183 lib_assert(index_mapping.size() == m_indices.size(), "Unexpected Insertion Structure");
184 TreeIterator iterator(root_node);
185 while (iterator.valid())
186 {
187 uint04 node_index = iterator.get();
188 t_node_type& node = m_nodes[node_index];
189 iterator.pop();
190 if (node.isLeaf())
191 {
192 const uint04 end = node.end();
193 for (uint04 i = node.begin(); i < end; i++)
194 {
195 m_indices[i] = index_mapping[m_indices[i]];
196 }
197 }
198 else
199 {
200 iterator.addAndGoToIndices(node.childNodeStart(), t_node_child_size);
201 }
202 }
203 }
204
205 void addIndices(uint04 begin, uint04 end)
206 {
207 uint04 size = end - begin;
208 TreeIterator iterator(root_node);
209 while (iterator.valid())
210 {
211 uint04 node_index = iterator.get();
212 t_node_type& node = m_nodes[node_index];
213 iterator.pop();
214 if (node.isLeaf())
215 {
216 const uint04 node_end = node.end();
217 for (uint04 i = node.begin(); i < node_end; i++)
218 {
219 if (m_indices[i] > end)
220 m_indices[i] += size;
221 }
222 }
223 else
224 {
225 iterator.addAndGoToIndices(node.childNodeStart(), t_node_child_size);
226 }
227 }
228 }
229
230 uint04 size() const
231 {
232 return m_nodes[root_node].size();;
233 }
234
235 void removeIndex(uint04 index) const
236 {
237 TreeIterator iterator(root_node);
238 while (iterator.valid())
239 {
240 const t_node_type& node = m_nodes[iterator.get()];
241 iterator.pop();
242 if (node.isLeaf())
243 {
244 uint04 end = node.end();
245 for (uint04 i = node.begin(); i < end; i++)
246 {
247 if (m_indices[index] > index)
248 --index;
249 lib_assert(index != m_indices[index], "Must Call remove value prior to removeIndex");
250 }
251 }
252 else
253 iterator.addAndGoToIndices(node.childNodeStart(), t_node_child_size);
254 }
255 }
256
257 template<uint01 t_dims, class t_buffer_type>
258 Bounds<t_dims, t_type> _getBounds(const Buffer<uint04>& indices, const t_buffer_type& elements, uint04 start, uint04 end)
259 {
260 Bounds<t_dims, t_type> bounds(Constant<Bounds<t_dims, t_type>>::Min);
261 for (uint04 i = start; i < end; i++)
262 {
263 bounds.addToBoundingBox(elements[indices[i]]);
264 }
265 return bounds;
266 }
267
268 void addIndex(uint04 index) const
269 {
270 TreeIterator iterator(index);
271 while (iterator.valid())
272 {
273 const t_node_type& node = m_nodes[iterator.get()];
274 iterator.pop();
275 if (node.isLeaf())
276 {
277 uint04 end = node.end();
278 for (uint04 i = node.begin(); i < end; i++)
279 {
280 if (m_indices[index] >= index)
281 ++index;
282 }
283 }
284 else
285 iterator.addAndGoToIndices(node.childNodeStart(), t_node_child_size);
286 }
287 }
288 const Buffer<uint04>& indices() const
289 {
290 return m_indices;
291 }
292 Buffer<uint04>& indices()
293 {
294 return m_indices;
295 }
296 void optimize()
297 {
298 optimize(m_nodes[root_node].size());
299 }
300 void optimize(uint04 optimized_size)
301 {
302 Buffer<uint04> indices(optimized_size);
303 TreeIterator iterator(root_node);
304 while (iterator.valid())
305 {
306 uint04 node_index = iterator.get();
307 iterator.pop();
308 if (m_nodes[node_index].isLeaf())
309 {
310 uint04 begin = indices.size();
311 indices.addAll(m_indices.begin(m_nodes[node_index].begin()), m_nodes[node_index].size());
312 m_nodes[node_index].setBegin(begin);
313 }
314 else
315 {
316 iterator.addAndGoToIndex(m_nodes[node_index].left(), m_nodes[node_index].right());
317 }
318 }
319 m_available_node_positions.clear(0U);
320 m_available_indexed_positions.clear(0U);
321 m_indices = indices;
322 }
323 template<class t_buffer_type>
324 void sortVertices(const t_buffer_type& elements, t_buffer_type& sorted) const
325 {
326 sorted.setSize(indexSize());
327 for (uint04 i = 0; i < m_indices.size(); ++i)
328 {
329 if (m_indices[i] < elements.size())
330 sorted[i] = elements[m_indices[i]];
331 }
332 }
333 public:
334 //Operators
335 //-------------------
336 inline TreeBase& operator=(const TreeBase& value)
337 {
338 m_indices = value.m_indices;//setting equal to ourselves
339 m_nodes = value.m_nodes;
340 m_available_node_positions = value.m_available_node_positions;
341 m_available_indexed_positions = value.m_available_indexed_positions;
342 return (*this);
343 }
344 inline TreeBase& operator=(TreeBase&& value)
345 {
346 std::swap(m_indices, value.m_indices);//setting equal to ourselves
347 std::swap(m_nodes, value.m_nodes);
348 std::swap(m_available_node_positions, value.m_available_node_positions);
349 std::swap(m_available_indexed_positions, value.m_available_indexed_positions);
350 return (*this);
351 }
352 protected:
353 template<bool t_use_values>
354 Buffer<uint04> prepareAddAll(const Buffer<bool>& index_values)
355 {
356 uint04 index_count = index_values.count(true);
357 Buffer<uint04> indices(t_use_values ? index_count : index_values.size() - index_count);
358 for (uint04 i = 0; i < index_values.size(); i++)
359 if (t_use_values == index_values[i])
360 indices.add(i);
361 return indices;
362 }
363 template<class t_buffer_type>
364 Buffer<uint04> prepareAddAll(uint04 start_index, uint04 end_index, const t_buffer_type& elements)
365 {
366 Buffer<uint04> indices(end_index - start_index);
367 for (uint04 i = start_index; i < end_index; i++)
368 {
369 if(IsValid(elements[i]))
370 indices.add(i);
371 }
372 return indices;
373 }
374
375 uint04 getNumberOfFreeIndices()
376 {
377 return m_available_indexed_positions.size() * m_bucket_size;
378 }
379
380 uint04 getNumberOfFreeNodes()
381 {
382 return m_available_node_positions.size() * t_node_child_size;
383 }
384
385 void splitLeafNode(uint04 index)
386 {
387 uint04 child_node_index;
388 if (m_available_node_positions.size() == 0)
389 {
390 child_node_index = m_nodes.size();
391 m_nodes.add(t_node_type(m_nodes[index].begin()));
392 for (uint04 i = 0; i < t_node_child_size - 1; ++i)
393 {
394 if (m_available_indexed_positions.size() == 0)
395 {
396 m_nodes.add(t_node_type(m_indices.size()));
397 m_indices.addSpace<true>(m_bucket_size);
398 }
399 else
400 {
401 m_nodes.add(t_node_type(m_available_indexed_positions.last()));
402 m_available_indexed_positions.removeLast();
403 }
404 }
405 }
406 else
407 {
408 child_node_index = m_available_node_positions.last();
409 m_available_node_positions.removeLast();
410
411 m_nodes[child_node_index + 0].clear(m_nodes[index].begin());
412 for (uint04 i = 1; i < t_node_child_size; ++i)
413 {
414 if (m_available_indexed_positions.size() == 0)
415 {
416 m_nodes[child_node_index + i].clear(m_indices.size());
417 m_indices.addSpace<true>(m_bucket_size);
418 }
419 else
420 {
421 m_nodes[child_node_index + i].clear(m_available_indexed_positions.last());
422 m_available_indexed_positions.removeLast();
423 }
424 }
425 }
426 m_nodes[index].setChildNodeStart(child_node_index);
427 }
428
429 void reclaimChildren(uint04 index)
430 {
431 if (!m_nodes[index].isLeaf())
432 {
433 TreeIterator iterator(index);
434 while (iterator.valid())
435 {
436 uint04 i = iterator.get();
437 iterator.pop();
438 if (m_nodes[i].isLeaf())
439 {
440 lib_assert(!m_available_indexed_positions.contains(m_nodes[i].begin()), "Bad contains");
441 m_available_indexed_positions.add(m_nodes[i].begin());
442 }
443 else
444 {
445 m_available_node_positions.add(m_nodes[i].childNodeStart());
446 iterator.addAndGoToIndex(m_nodes[i].left(), m_nodes[i].right());
447 }
448 }
449 m_nodes[index].setBegin(m_available_indexed_positions.last());
450 m_available_indexed_positions.removeLast();
451 }
452 }
453
454 template<bool t_is_presorted, bool t_set_true>
455 void _getAllT(const uint04& node_index, Buffer<bool>& indices) const
456 {
457 TreeIterator iterator(node_index);
458 while (iterator.valid())
459 {
460 const t_node_type& node = m_nodes[iterator.get()];
461 iterator.pop();
462 if (node.isLeaf())
463 {
464 const uint04 end = node.end();
465 for (uint04 i = node.begin(); i < end; i++)
466 {
467 if constexpr (t_is_presorted)
468 indices[i] = t_set_true;
469 else
470 indices[m_indices[i]] = t_set_true;
471 }
472 }
473 else
474 {
475 iterator.addAndGoToIndices(node.childNodeStart(), t_node_child_size);
476 }
477 }
478 }
479 template<bool t_is_presorted>
480 void _getAll(const uint04& node_index, Buffer<uint04>& indices) const
481 {
482 TreeIterator iterator(node_index);
483 while (iterator.valid())
484 {
485 const t_node_type& node = m_nodes[iterator.get()];
486 iterator.pop();
487 if (node.isLeaf())
488 {
489 if constexpr (!t_is_presorted)
490 {
491 indices.addAll(m_indices.begin(node.begin()), node.size());
492 }
493 else
494 {
495 const uint04 end = node.begin() + node.size();
496 for(uint04 i = node.begin(); i < end; i++)
497 indices.add(i);
498 }
499 }
500 else
501 iterator.addAndGoToIndices(node.childNodeStart(), t_node_child_size);
502 }
503 }
504 public:
505 uint04 indexSize() const
506 {
507 return m_indices.size();
508 }
509 uint04 nodeSize() const
510 {
511 return m_nodes.size();
512 }
513 protected:
514 Buffer<uint04> m_indices;
515 PrimitiveBuffer<t_node_type> m_nodes;
516 Buffer<uint04> m_available_node_positions;
517 Buffer<uint04> m_available_indexed_positions;
518 static const uint04 root_node = 0;
519 uint04 m_bucket_size;
520 };
521
522 template<uint01 t_dims, class t_type, class t_child_tree>
523 class Tree : public t_child_tree
524 {
525 protected:
526 explicit Tree(uint04 bucket_size)
527 : t_child_tree(bucket_size)
528 {}
529 Tree(const t_child_tree& tree)
530 : t_child_tree(tree)
531 {}
532 Tree(t_child_tree&& tree)
533 : t_child_tree(std::move(tree))
534 {}
535 public:
536 void getAll(Buffer<bool>& indices) const
537 {
538 if (t_child_tree::m_indices.size() == 0)
539 t_child_tree::template _getAllT<true, true>(t_child_tree::root_node, indices);
540 else
541 t_child_tree::template _getAllT<false, true>(t_child_tree::root_node, indices);
542 }
543
544 void getAll(Buffer<uint04>& indices) const
545 {
546 if (t_child_tree::m_indices.size() == 0)
547 t_child_tree::template _getAll<true>(t_child_tree::root_node, indices);
548 else
549 t_child_tree::template _getAll<false>(t_child_tree::root_node, indices);
550 }
551 template<class t_reference_type, class t_buffer_type>
552 uint04 closestElement(const t_reference_type& point, const t_buffer_type& elements, t_type epsilon = cast<t_type>(0)) const
553 {
554 t_type max_distance = Constant<t_type>::Max;
555 return closestElement(point, elements, max_distance, epsilon);
556 }
557 template<class t_reference_type, class t_buffer_type>
558 uint04 closestElement(const t_reference_type& point, const t_buffer_type& elements, t_type& max_distance_squared, t_type epsilon = cast<t_type>(0)) const
559 {
560 uint04 index = Constant<uint04>::Invalid;
561 if (t_child_tree::m_indices.size() == 0)
562 t_child_tree::template _getClosestElement<true>(t_child_tree::root_node, point, elements, max_distance_squared, epsilon, index);
563 else
564 t_child_tree::template _getClosestElement<false>(t_child_tree::root_node, point, elements, max_distance_squared, epsilon, index);
565 return index;
566 }
567 template<class t_reference_type, class t_buffer_type>
568 uint04 closestElementPresorted(const t_reference_type& point, const t_buffer_type& elements, t_type epsilon = cast<t_type>(0)) const
569 {
570 t_type max_distance = Constant<t_type>::Max;
571 return closestElementPresorted(point, elements, max_distance, epsilon);
572 }
573 template<class t_reference_type, class t_buffer_type>
574 uint04 closestElementPresorted(const t_reference_type& point, const t_buffer_type& elements, t_type& max_distance_squared, t_type epsilon = cast<t_type>(0)) const
575 {
576 uint04 index = Constant<uint04>::Invalid;
577 t_child_tree::template _getClosestElement<true>(t_child_tree::root_node, point, elements, max_distance_squared, epsilon, index);
578 return index;
579 }
580 template<class t_area_type, class t_buffer_type>
581 void enclosedElements(const t_area_type& area, Buffer<uint04>& indices, const t_buffer_type& elements) const
582 {
583 if (t_child_tree::m_indices.size() == 0)
584 t_child_tree::template _getEnclosedElements<true>(t_child_tree::root_node, area, indices, elements);
585 else
586 t_child_tree::template _getEnclosedElements<false>(t_child_tree::root_node, area, indices, elements);
587 }
588 template<class t_area_type, class t_buffer_type>
589 void presortedEnclosedElements(const t_area_type& area, Buffer<uint04>& indices, const t_buffer_type& elements) const
590 {
591 t_child_tree::template _getEnclosedElements<true>(t_child_tree::root_node, area, indices, elements);
592 }
593
594
595 template<class t_area_type, class t_buffer_type>
596 void getChangedElements(const t_area_type& new_area, const t_area_type& old_area, Buffer<bool>& indices, const t_buffer_type& elements, bool allow_enable, bool allow_disable) const
597 {
598 if (allow_enable && allow_disable)
599 {
600 if (t_child_tree::m_indices.size() == 0)
601 t_child_tree::template _getChangedElements<true, true, true>(t_child_tree::root_node, new_area, old_area, indices, elements);
602 else
603 t_child_tree::template _getChangedElements<false, true, true>(t_child_tree::root_node, new_area, old_area, indices, elements);
604 }
605 else if (allow_enable)
606 {
607 if (t_child_tree::m_indices.size() == 0)
608 t_child_tree::template _getChangedElements<true, true, false>(t_child_tree::root_node, new_area, old_area, indices, elements);
609 else
610 t_child_tree::template _getChangedElements<false, true, false>(t_child_tree::root_node, new_area, old_area, indices, elements);
611 }
612 else if (allow_disable)
613 {
614 if (t_child_tree::m_indices.size() == 0)
615 t_child_tree::template _getChangedElements<true, false, true>(t_child_tree::root_node, new_area, old_area, indices, elements);
616 else
617 t_child_tree::template _getChangedElements<false, false, true>(t_child_tree::root_node, new_area, old_area, indices, elements);
618 }
619 }
620 template<class t_area_type, class t_buffer_type>
621 void enclosedElements(const t_area_type& area, Buffer<bool>& indices, const t_buffer_type& elements) const
622 {
623 if (t_child_tree::m_indices.size() == 0)
624 t_child_tree::template _getEnclosedElements<true>(t_child_tree::root_node, area, indices, elements);
625 else
626 t_child_tree::template _getEnclosedElements<false>(t_child_tree::root_node, area, indices, elements);
627 }
628 template<class t_area_type, class t_buffer_type>
629 void nearElements(const t_area_type& area, Buffer<uint04>& indices, const t_buffer_type& elements, t_type max_distance_sqrd) const
630 {
631 if (t_child_tree::m_indices.size() == 0)
632 t_child_tree::template _getNearElements<true>(t_child_tree::root_node, area, indices, elements, max_distance_sqrd);
633 else
634 t_child_tree::template _getNearElements<false>(t_child_tree::root_node, area, indices, elements, max_distance_sqrd);
635 }
636 template<class t_area_type, class t_buffer_type>
637 uint04 getNumberOfEnclosedElements(const t_area_type& area, const t_buffer_type& elements) const
638 {
639 return t_child_tree::_getNumberOfEnclosedElements(t_child_tree::root_node, area, elements);
640 }
641
642 template<class t_reference_type, class t_buffer_type>
643 void closestElements(const t_reference_type& point, uint04 size, Buffer<uint04>& indices, const t_buffer_type& elements, t_type& max_distance, t_type epsilon = cast<t_type>(0)) const
644 {
645 if (size <= 1)
646 {
647 uint04 index = closestElement(point, elements, max_distance, epsilon);
648 if(IsValid(index))
649 indices.add(index);
650 return;
651 }
652 MaxHeap<t_type, uint04> heap(size + 1);
653 if(t_child_tree::m_indices.size() == 0)
654 t_child_tree::template _getClosestElements<true>(t_child_tree::root_node, point, elements, max_distance, epsilon, heap, size);
655 else
656 t_child_tree::template _getClosestElements<false>(t_child_tree::root_node, point, elements, max_distance, epsilon, heap, size);
657 indices.addAll(heap.sortedIndices());
658 }
659
660 template<class t_reference_type, class t_buffer_type>
661 void closestElements(const t_reference_type& point, uint04 size, MaxHeap<t_type, uint04>& value_heap, const t_buffer_type& elements, t_type& max_distance, t_type epsilon = cast<t_type>(0)) const
662 {
663 t_child_tree::template _getClosestElements<false>(t_child_tree::root_node, point, elements, max_distance, epsilon, value_heap, size);
664 }
665 template<class t_reference_type, class t_buffer_type>
666 void presortedClosestElements(const t_reference_type& point, uint04 size, MaxHeap<t_type, uint04>& value_heap, const t_buffer_type& elements, t_type& max_distance, t_type epsilon = cast<t_type>(0)) const
667 {
668 t_child_tree::template _getClosestElements<true>(t_child_tree::root_node, point, elements, max_distance, epsilon, value_heap, size);
669 }
670 void swapIndices(uint04 index_a, uint04 index_b)
671 {
672 t_child_tree::m_indices.swapAllElements(index_a, index_b);
673 }
674
675
676 template<bool t_has_nans, bool t_uses_boundary, class t_buffer_type>
677 void addValue(uint04 index, const t_buffer_type& elements, bool rebalance)
678 {
679 t_child_tree::template _addValue<t_has_nans, t_uses_boundary>(t_child_tree::root_node, index, elements, rebalance);
680 }
681
682 template<bool t_has_nans, bool t_uses_boundary, class t_buffer_type>
683 void addValues(const Buffer<bool>& insertion_indices, const t_buffer_type& elements, bool is_precise)
684 {
685 if (t_child_tree::useBulkResize(insertion_indices.count(true)))
686 {
687 t_child_tree::template _addValues<t_has_nans, t_uses_boundary>(t_child_tree::root_node, t_child_tree::template prepareAddAll<true>(insertion_indices), elements, is_precise);
688 }
689 else
690 {
691 for (uint04 i = 0; i < elements.size(); i++)
692 {
693 if (insertion_indices[i])
694 addValue<t_has_nans, t_uses_boundary>(i, elements);
695 }
696 }
697 }
698 template<bool t_has_nans, bool t_uses_boundary, class t_buffer_type>
699 void addValues(const t_buffer_type& elements, bool is_precise)
700 {
701 addValues<t_has_nans, t_uses_boundary>(0, elements.size(), elements, is_precise);
702 }
703 template<bool t_has_nans, bool t_uses_boundary, class t_buffer_type>
704 void addValues(uint04 start_index, uint04 end_index, const t_buffer_type& elements, bool is_precise)
705 {
706 if (t_child_tree::useBulkResize(end_index - start_index))
707 {
708 t_child_tree::template _addValues<t_has_nans, t_uses_boundary>(t_child_tree::root_node, t_child_tree::prepareAddAll(start_index, end_index, elements), elements, is_precise);
709 }
710 else
711 {
712 for (uint04 i = start_index; i < end_index; i++)
713 {
714 if constexpr (t_has_nans)
715 {
716 if (IsInvalid(elements[i]))
717 continue;
718 }
719 addValue<t_has_nans, t_uses_boundary>(i, elements, is_precise);
720 }
721 }
722 };
723
724 template<bool t_has_nans, bool t_uses_boundary, class t_buffer_type>
725 void addValues(const Buffer<uint04>& indices, const t_buffer_type& elements, bool is_precise)
726 {
727 if (t_child_tree::useBulkResize(indices.size()))
728 {
729 t_child_tree::template _addValues<t_has_nans, t_uses_boundary>(t_child_tree::root_node, indices, elements, is_precise);
730 }
731 else
732 {
733 for (uint04 i = 0; i < indices.size(); i++)
734 {
735 addValue<t_has_nans, t_uses_boundary>(indices[i], elements, is_precise);
736 }
737 }
738 }
739
740
741
742 template<class t_buffer_type>
743 void removeValue(uint04 index, const t_buffer_type& elements)
744 {
745 t_child_tree::_removeValue(t_child_tree::root_node, index, elements);
746 }
747
748 template<class t_buffer_type>
749 void removeValues(const Buffer<bool>& insertion_indices, const t_buffer_type& elements)
750 {
751 if (t_child_tree::useBulkResize(insertion_indices.count(true)))
752 {
753 t_child_tree::clear();
754 t_child_tree::_addValues(t_child_tree::root_node, t_child_tree::template prepareAddAll<false>(insertion_indices), elements);
755 }
756 else
757 {
758 for (uint04 i = 0; i < elements.size(); i++)
759 {
760 if (insertion_indices[i])
761 t_child_tree::removeValue(i, elements);
762 }
763 }
764 }
765
766 template<class t_buffer_type>
767 void removeValues(uint04 start_index, uint04 end_index, const t_buffer_type& elements)
768 {
769 if (t_child_tree::useBulkResize(end_index - start_index))
770 {
771 t_child_tree::clear();
772 Buffer<uint04> indices(elements.size() - (end_index - start_index));
773 for (uint04 i = 0; i < start_index; i++)
774 indices.add(i);
775 for (uint04 i = end_index; i < elements.size(); i++)
776 indices.add(i);
777 t_child_tree::_addValues(t_child_tree::root_node, indices, elements);
778 }
779 else
780 {
781 for (uint04 i = start_index; i < end_index; i++)
782 {
783 removeValue(i, elements);
784 }
785 }
786 }
787
788
789 /*Tree getAsReadOnly() const
790 {
791 Buffer<uint04> indices(t_child_tree::size());
792 auto nodes = t_child_tree::m_nodes;
793 TreeIterator iterator(t_child_tree::root_node);
794 while (iterator.valid())
795 {
796 uint04 node_index = iterator.get();
797 iterator.pop();
798 if (nodes[node_index].isLeaf())
799 {
800 nodes[node_index].setBegin(indices.size());
801 indices.addAll(t_child_tree::m_indices.begin(t_child_tree::m_nodes[node_index].begin()), t_child_tree::m_nodes[node_index].size());
802 }
803 else
804 {
805 iterator.addAndGoToIndex(t_child_tree::m_nodes[node_index].left(), t_child_tree::m_nodes[node_index].right());
806 }
807
808 }
809 return Tree(nodes, indices, true);
810 }*/
811
812 virtual const char* getTreeType() const = 0;
813 };
814};
815/*--------------------------------------------------------------------------------------------
816\endinternal
817 *-----------------------------------------------------------------------------------------**/
818
NDEVR
The primary namespace for the NDEVR SDK.
Definition ArialTileFetcherModule.h:35
IsValid
static constexpr bool IsValid(const Angle< t_type > &value)
Checks whether the given Angle holds a valid value.
Definition Angle.h:398
uint04
uint32_t uint04
-Defines an alias representing a 4 byte, unsigned integer -Can represent exact integer values 0 throu...
Definition BaseValues.hpp:97
IsInvalid
static constexpr bool IsInvalid(const Angle< t_type > &value)
Checks whether the given Angle holds an invalid value.
Definition Angle.h:388
Min
constexpr HSLColor Constant< HSLColor >::Min
The minimum HSLColor constant with saturation, brightness, and alpha at zero.
Definition HSLColor.h:266
cast
constexpr t_to cast(const Angle< t_from > &value)
Casts an Angle from one backing type to another.
Definition Angle.h:408