UFO 1.0.0
An Efficient Probabilistic 3D Mapping Framework That Embraces the Unknown
Loading...
Searching...
No Matches
map.hpp
1
42#ifndef UFO_MAP_HPP
43#define UFO_MAP_HPP
44
45// UFO
46#include <ufo/compute/compute.hpp>
47#include <ufo/container/tree/block.hpp>
48#include <ufo/container/tree/predicate.hpp>
49#include <ufo/container/tree/tree.hpp>
50#include <ufo/execution/algorithm.hpp>
51#include <ufo/map/header.hpp>
52#include <ufo/map/predicate_map_type.hpp>
53#include <ufo/map/serialized_block.hpp>
54#include <ufo/map/type.hpp>
55#include <ufo/map/utility.hpp>
56#include <ufo/utility/enum.hpp>
57#include <ufo/utility/io/buffer.hpp>
58#include <ufo/utility/macros.hpp>
59
60// STL
61#include <algorithm>
62#include <bitset>
63#include <cstddef>
64#include <filesystem>
65#include <fstream>
66#include <ios>
67#include <numeric>
68#include <tuple>
69#include <type_traits>
70#include <utility>
71
72namespace ufo
73{
74namespace detail
75{
76template <class Map>
77class MapHelper : public Map
78{
79};
80
81template <class... Maps>
82class MapHelper<std::tuple<Maps...>> : public Maps...
83{
84};
85
86template <std::size_t BF>
87struct Fulfill {
88 TreeIndex::pos_type block;
89 BitSet<BF> offsets;
90 BitSet<BF> children;
91};
92} // namespace detail
93
94// All your base are belong to us
95template <std::size_t Dim, class... Maps>
96class Map final
97 : public Tree<Map<Dim, Maps...>, Dim, typename Maps::Block...>
98 , public detail::MapHelper<typename Maps::template Map<
99 Map<Dim, Maps...>, Tree<Map<Dim, Maps...>, Dim, typename Maps::Block...>>>...
100{
101 using Base = Tree<Map<Dim, Maps...>, Dim, typename Maps::Block...>;
102
103 using MapBases = decltype(std::tuple_cat(
104 std::declval<as_tuple_t<typename Maps::template Map<Map, Base>>>()...));
105
106 using MapBasesISeq = std::make_index_sequence<std::tuple_size_v<MapBases>>;
107
108 static constexpr auto const BF = Base::branchingFactor();
109
110 template <class T>
111 static constexpr inline bool const is_node_type_v = Base::template is_node_type_v<T>;
112
113 //
114 // Friends
115 //
116
117 friend Base;
118
119#define UFO_MAP_FRIEND(F) \
120 friend std::tuple_element_t<std::min(static_cast<std::size_t>(F + 1), \
121 MapBasesISeq::size()), \
122 decltype(std::tuple_cat(std::declval<std::tuple<void>>(), \
123 std::declval<MapBases>()))>;
124 UFO_REPEAT_128(UFO_MAP_FRIEND, 0)
125
126 public:
127 /**************************************************************************************
128 | |
129 | Tags |
130 | |
131 **************************************************************************************/
132
133 using Index = typename Base::Index;
134 using Node = typename Base::Node;
135 using Code = typename Base::Code;
136 using Key = typename Base::Key;
137 using Point = typename Base::Point;
138 using Coord = typename Base::Coord;
139 using Bounds = typename Base::Bounds;
140 using Length = typename Base::Length;
141 using coord_type = typename Base::coord_type;
142 using depth_type = typename Base::depth_type;
143 using pos_type = typename Base::pos_type;
144 using offset_type = typename Base::offset_type;
145 using length_type = typename Base::length_type;
146
147 /**************************************************************************************
148 | |
149 | Constructors |
150 | |
151 **************************************************************************************/
152
153 Map(Length leaf_node_length = Length(0.1),
154 depth_type num_depth_levels = std::min(depth_type(17), Base::maxNumDepthLevels()))
155 : Base(leaf_node_length, num_depth_levels)
156 {
157 onInitRoot();
158 }
159
160 Map(length_type leaf_node_length,
161 depth_type num_depth_levels = std::min(depth_type(17), Base::maxNumDepthLevels()))
162 : Map(Length(leaf_node_length), num_depth_levels)
163 {
164 }
165
166 Map(std::filesystem::path const& file) : Map() { read(file); }
167
168 Map(std::istream& in) : Map() { read(in); }
169
170 Map(ReadBuffer& in) : Map() { read(in); }
171
172 Map(Map const&) = default;
173
174 Map(Map&&) = default;
175
176 template <class... Maps2>
177 Map(Map<Dim, Maps2...> const& other) : Map(other.write(pred::Leaf{}, mapTypes()))
178 {
179 }
180
181 /**************************************************************************************
182 | |
183 | Destructor |
184 | |
185 **************************************************************************************/
186
187 ~Map() = default;
188
189 /**************************************************************************************
190 | |
191 | Assignment operator |
192 | |
193 **************************************************************************************/
194
195 Map& operator=(Map const&) = default;
196
197 Map& operator=(Map&&) = default;
198
199 template <class... Maps2>
200 Map& operator=(Map<Dim, Maps2...> const& rhs)
201 {
202 read(rhs.write(pred::Leaf{}, mapTypes()));
203 return *this;
204 }
205
206 /**************************************************************************************
207 | |
208 | Map Types |
209 | |
210 **************************************************************************************/
211
212 [[nodiscard]] static constexpr MapType mapTypes() noexcept
213 {
214 return mapTypes(MapBasesISeq{});
215 }
216
217 [[nodiscard]] static constexpr std::size_t numMapTypes() noexcept
218 {
219 return MapBasesISeq::size();
220 }
221
222 [[nodiscard]] static constexpr bool hasMapTypes(MapType map_types) noexcept
223 {
224 return (mapTypes() & map_types) == map_types;
225 }
226
227 /**************************************************************************************
228 | |
229 | Propagate |
230 | |
231 **************************************************************************************/
232
236 void propagate(MapType map_types = MapType::ALL)
237 {
238 propagate(Base::index(), map_types);
239 }
240
241 template <class NodeType, std::enable_if_t<is_node_type_v<NodeType>, bool> = true>
242 void propagate(NodeType const& node, MapType map_types = MapType::ALL)
243 {
244 auto n = Base::index(node);
245
246 if (Base::isPureLeaf(n)) {
247 return;
248 }
249
250 // Const access more optimized
251 auto const& b = Base::treeInnerBlockConst(n.pos);
252 auto const c = Base::children(b, n.offset);
253
254 if (!Base::valid(c) || !Base::modified(b, n.offset)) {
255 return;
256 }
257
258 propagate(c, map_types);
259 onPropagateChildren(n, c, map_types);
260
261 if (onIsPrunable(c)) {
262 Base::pruneChildren(n, c);
263 }
264 }
265
266 template <
267 class ExecutionPolicy,
268 std::enable_if_t<execution::is_execution_policy_v<ExecutionPolicy>, bool> = true>
269 void propagate(ExecutionPolicy&& policy, MapType map_types = MapType::ALL)
270 {
271 propagate(std::forward<ExecutionPolicy>(policy), Base::index(), map_types);
272 }
273
274 template <
275 class ExecutionPolicy, class NodeType,
276 std::enable_if_t<execution::is_execution_policy_v<ExecutionPolicy>, bool> = true,
277 std::enable_if_t<is_node_type_v<NodeType>, bool> = true>
278 void propagate(ExecutionPolicy&& policy, NodeType node,
279 MapType map_types = MapType::ALL)
280 {
281 auto n = Base::index(node);
282
283 if (Base::isPureLeaf(n)) {
284 return;
285 }
286
287 // Const access more optimized
288 auto const& b = Base::treeInnerBlockConst(n.pos);
289 auto const c = Base::children(b, n.offset);
290
291 if (!Base::valid(c) || !Base::modified(b, n.offset)) {
292 return;
293 }
294
295 propagate(std::forward<ExecutionPolicy>(policy), c, map_types, false);
296 onPropagateChildren(n, c, map_types);
297
298 if (onIsPrunable(c)) {
299 Base::pruneChildren(n, c);
300 }
301 }
302
303 /**************************************************************************************
304 | |
305 | I/O |
306 | |
307 **************************************************************************************/
308
309 [[nodiscard]] MapHeader header(MapType map_types = MapType::ALL) const
310 {
311 return MapHeader(Base::length(0), Base::numDepthLevels(), mapTypes() & map_types);
312 }
313
314 [[nodiscard]] static bool isMap(std::filesystem::path const& file)
315 {
316 return MapHeader::isMap(file);
317 }
318
319 [[nodiscard]] static bool isMap(std::istream& in) { return MapHeader::isMap(in); }
320
321 [[nodiscard]] static bool isMap(ReadBuffer& in) { return MapHeader::isMap(in); }
322
323 void read(std::filesystem::path const& file, MapType map_types = MapType::ALL,
324 bool propagate = true)
325 {
326 std::ifstream f = MapHeader::openRead(file);
327 read(f, map_types, propagate);
328 }
329
330 void read(std::istream& in, MapType map_types = MapType::ALL, bool propagate = true)
331 {
332 readData(in, readHeader(in), map_types, propagate);
333 }
334
335 void read(ReadBuffer& in, MapType map_types = MapType::ALL, bool propagate = true)
336 {
337 readData(in, readHeader(in), map_types, propagate);
338 }
339
340 template <
341 class ExecutionPolicy,
342 std::enable_if_t<execution::is_execution_policy_v<ExecutionPolicy>, bool> = true>
343 void read(ExecutionPolicy&& policy, std::filesystem::path const& file,
344 MapType map_types = MapType::ALL, bool propagate = true)
345 {
346 std::ifstream f = MapHeader::openRead(file);
347 read(std::forward<ExecutionPolicy>(policy), f, map_types, propagate);
348 }
349
350 template <
351 class ExecutionPolicy,
352 std::enable_if_t<execution::is_execution_policy_v<ExecutionPolicy>, bool> = true>
353 void read(ExecutionPolicy&& policy, std::istream& in, MapType map_types = MapType::ALL,
354 bool propagate = true)
355 {
356 readData(std::forward<ExecutionPolicy>(policy), in, readHeader(in), map_types,
357 propagate);
358 }
359
360 template <
361 class ExecutionPolicy,
362 std::enable_if_t<execution::is_execution_policy_v<ExecutionPolicy>, bool> = true>
363 void read(ExecutionPolicy&& policy, ReadBuffer& in, MapType map_types = MapType::ALL,
364 bool propagate = true)
365 {
366 readData(std::forward<ExecutionPolicy>(policy), in, readHeader(in), map_types,
367 propagate);
368 }
369
370 [[nodiscard]] MapHeader readHeader(std::filesystem::path const& file) const
371 {
372 return MapHeader{file};
373 }
374
375 [[nodiscard]] MapHeader readHeader(std::istream& in) const { return MapHeader{in}; }
376
377 [[nodiscard]] MapHeader readHeader(ReadBuffer& in) const { return MapHeader{in}; }
378
379 void readData(std::istream& in, MapHeader const& header,
380 MapType map_types = MapType::ALL, bool propagate = true)
381 {
382 readData(execution::seq, in, header, map_types, propagate);
383 }
384
385 void readData(ReadBuffer& in, MapHeader const& header, MapType map_types = MapType::ALL,
386 bool propagate = true)
387 {
388 readData(execution::seq, in, header, map_types, propagate);
389 }
390
391 template <
392 class ExecutionPolicy,
393 std::enable_if_t<execution::is_execution_policy_v<ExecutionPolicy>, bool> = true>
394 void readData(ExecutionPolicy&& policy, std::istream& in, MapHeader const& header,
395 MapType map_types = MapType::ALL, bool propagate = true)
396 {
397 readDataImpl(std::forward<ExecutionPolicy>(policy), in, header, map_types, propagate);
398 }
399
400 template <
401 class ExecutionPolicy,
402 std::enable_if_t<execution::is_execution_policy_v<ExecutionPolicy>, bool> = true>
403 void readData(ExecutionPolicy&& policy, ReadBuffer& in, MapHeader const& header,
404 MapType map_types = MapType::ALL, bool propagate = true)
405 {
406 readDataImpl(std::forward<ExecutionPolicy>(policy), in, header, map_types, propagate);
407 }
408
409 template <class Predicate = pred::Leaf,
410 std::enable_if_t<pred::is_pred_v<Predicate>, bool> = true>
411 void write(std::filesystem::path const& file, Predicate const& pred = pred::Leaf{},
412 MapType map_types = MapType::ALL) const
413 {
414 write(execution::seq, file, pred, map_types);
415 }
416
417 template <class Predicate = pred::Leaf,
418 std::enable_if_t<pred::is_pred_v<Predicate>, bool> = true>
419 void write(std::ostream& out, Predicate const& pred = pred::Leaf{},
420 MapType map_types = MapType::ALL) const
421 {
422 write(execution::seq, out, pred, map_types);
423 }
424
425 template <class Predicate = pred::Leaf,
426 std::enable_if_t<pred::is_pred_v<Predicate>, bool> = true>
427 void write(WriteBuffer& out, Predicate const& pred = pred::Leaf{},
428 MapType map_types = MapType::ALL) const
429 {
430 write(execution::seq, out, pred, map_types);
431 }
432
433 template <class Predicate = pred::Leaf,
434 std::enable_if_t<pred::is_pred_v<Predicate>, bool> = true>
435 [[nodiscard]] Buffer write(Predicate const& pred = pred::Leaf{},
436 MapType map_types = MapType::ALL) const
437 {
438 return write(execution::seq, pred, map_types);
439 }
440
441 template <
442 class ExecutionPolicy, class Predicate = pred::Leaf,
443 std::enable_if_t<execution::is_execution_policy_v<ExecutionPolicy>, bool> = true,
444 std::enable_if_t<pred::is_pred_v<Predicate>, bool> = true>
445 void write(ExecutionPolicy&& policy, std::filesystem::path const& file,
446 Predicate const& pred = pred::Leaf{}, MapType map_types = MapType::ALL) const
447 {
448 std::ofstream f = MapHeader::openWrite(file);
449 return write(std::forward<ExecutionPolicy>(policy), f, pred, map_types);
450 }
451
452 template <
453 class ExecutionPolicy, class Predicate = pred::Leaf,
454 std::enable_if_t<execution::is_execution_policy_v<ExecutionPolicy>, bool> = true,
455 std::enable_if_t<pred::is_pred_v<Predicate>, bool> = true>
456 void write(ExecutionPolicy&& policy, std::ostream& out,
457 Predicate const& pred = pred::Leaf{}, MapType map_types = MapType::ALL) const
458 {
459 writeImpl(std::forward<ExecutionPolicy>(policy), out, pred, map_types, true);
460 }
461
462 template <
463 class ExecutionPolicy, class Predicate = pred::Leaf,
464 std::enable_if_t<execution::is_execution_policy_v<ExecutionPolicy>, bool> = true,
465 std::enable_if_t<pred::is_pred_v<Predicate>, bool> = true>
466 void write(ExecutionPolicy&& policy, WriteBuffer& out,
467 Predicate const& pred = pred::Leaf{}, MapType map_types = MapType::ALL) const
468 {
469 writeImpl(std::forward<ExecutionPolicy>(policy), out, pred, map_types, true);
470 }
471
472 template <
473 class ExecutionPolicy, class Predicate = pred::Leaf,
474 std::enable_if_t<execution::is_execution_policy_v<ExecutionPolicy>, bool> = true,
475 std::enable_if_t<pred::is_pred_v<Predicate>, bool> = true>
476 [[nodiscard]] Buffer write(ExecutionPolicy&& policy,
477 Predicate const& pred = pred::Leaf{},
478 MapType map_types = MapType::ALL) const
479 {
480 Buffer buffer;
481 write(std::forward<ExecutionPolicy>(policy), buffer, pred, map_types);
482 return buffer;
483 }
484
485 template <class Predicate = pred::Leaf,
486 std::enable_if_t<pred::is_pred_v<Predicate>, bool> = true>
487 [[nodiscard]] MapHeader writeData(std::filesystem::path const& file,
488 Predicate const& pred = pred::Leaf{},
489 MapType map_types = MapType::ALL) const
490 {
491 return writeData(execution::seq, file, pred, map_types);
492 }
493
494 template <class Predicate = pred::Leaf,
495 std::enable_if_t<pred::is_pred_v<Predicate>, bool> = true>
496 [[nodiscard]] MapHeader writeData(std::ostream& out,
497 Predicate const& pred = pred::Leaf{},
498 MapType map_types = MapType::ALL) const
499 {
500 return writeData(execution::seq, out, pred, map_types);
501 }
502
503 template <class Predicate = pred::Leaf,
504 std::enable_if_t<pred::is_pred_v<Predicate>, bool> = true>
505 [[nodiscard]] MapHeader writeData(WriteBuffer& out,
506 Predicate const& pred = pred::Leaf{},
507 MapType map_types = MapType::ALL) const
508 {
509 return writeData(execution::seq, out, pred, map_types);
510 }
511
512 template <
513 class ExecutionPolicy, class Predicate = pred::Leaf,
514 std::enable_if_t<execution::is_execution_policy_v<ExecutionPolicy>, bool> = true,
515 std::enable_if_t<pred::is_pred_v<Predicate>, bool> = true>
516 [[nodiscard]] MapHeader writeData(ExecutionPolicy&& policy,
517 std::filesystem::path const& file,
518 Predicate const& pred = pred::Leaf{},
519 MapType map_types = MapType::ALL) const
520 {
521 std::ofstream f = MapHeader::openWrite(file);
522 return writeData(std::forward<ExecutionPolicy>(policy), f, pred, map_types);
523 }
524
525 template <
526 class ExecutionPolicy, class Predicate = pred::Leaf,
527 std::enable_if_t<execution::is_execution_policy_v<ExecutionPolicy>, bool> = true,
528 std::enable_if_t<pred::is_pred_v<Predicate>, bool> = true>
529 [[nodiscard]] MapHeader writeData(ExecutionPolicy&& policy, std::ostream& out,
530 Predicate const& pred = pred::Leaf{},
531 MapType map_types = MapType::ALL) const
532 {
533 return writeImpl(std::forward<ExecutionPolicy>(policy), out, pred, map_types, false);
534 }
535
536 template <
537 class ExecutionPolicy, class Predicate = pred::Leaf,
538 std::enable_if_t<execution::is_execution_policy_v<ExecutionPolicy>, bool> = true,
539 std::enable_if_t<pred::is_pred_v<Predicate>, bool> = true>
540 [[nodiscard]] MapHeader writeData(ExecutionPolicy&& policy, WriteBuffer& out,
541 Predicate const& pred = pred::Leaf{},
542 MapType map_types = MapType::ALL) const
543 {
544 return writeImpl(std::forward<ExecutionPolicy>(policy), out, pred, map_types, false);
545 }
546
547 /**************************************************************************************
548 | |
549 | Dot file |
550 | |
551 **************************************************************************************/
552
553 template <class Predicate = pred::True,
554 std::enable_if_t<pred::is_pred_v<Predicate>, bool> = true>
555 void saveDotFile(std::filesystem::path const& file,
556 Predicate const& pred = pred::True{},
557 MapType map_types = MapType::ALL) const
558 {
559 saveDotFile(Base::node(), file, pred, map_types);
560 }
561
562 template <class Predicate = pred::True,
563 std::enable_if_t<pred::is_pred_v<Predicate>, bool> = true>
564 void saveDotFile(std::ostream& out, Predicate const& pred = pred::True{},
565 MapType map_types = MapType::ALL) const
566 {
567 saveDotFile(Base::node(), out, pred, map_types);
568 }
569
570 template <class NodeType, class Predicate = pred::True,
571 std::enable_if_t<is_node_type_v<NodeType>, bool> = true,
572 std::enable_if_t<pred::is_pred_v<Predicate>, bool> = true>
573 void saveDotFile(NodeType node, std::filesystem::path const& file,
574 Predicate const& pred = pred::True{},
575 MapType map_types = MapType::ALL) const
576 {
577 std::ofstream f = MapHeader::openWrite(file);
578 saveDotFile(node, f, pred, map_types);
579 }
580
581 template <class NodeType, class Predicate = pred::True,
582 std::enable_if_t<is_node_type_v<NodeType>, bool> = true,
583 std::enable_if_t<pred::is_pred_v<Predicate>, bool> = true>
584 void saveDotFile(NodeType node, std::ostream& out, Predicate const& pred = pred::True{},
585 MapType map_types = MapType::ALL) const
586 {
587 using Filter = pred::Filter<Predicate>;
588
589 Node n = Base::node(node);
590
591 std::string const parent_shape = "shape=polygon,sides=" + std::to_string(BF) + ' ';
592
593 out << std::boolalpha << "graph UFOMap {\n";
594 out << "fontname=\"Helvetica,Arial,sans-serif\"\n";
595 out << "node [fontname=\"Helvetica,Arial,sans-serif\" shape=ellipse color=lightblue2 "
596 "style=filled]\n";
597 out << "edge [fontname=\"Helvetica,Arial,sans-serif\"]\n";
598
599 Filter::init(pred, *this);
600 bool valid_return = Base::exists(n) && Filter::returnable(pred, *this, n);
601 bool valid_inner = Base::isParent(n) && Filter::traversable(pred, *this, n);
602
603 if (!valid_return && !valid_inner) {
604 out << "}";
605 return;
606 }
607
608 std::string id =
609 std::to_string(node.index.pos) + '.' + std::to_string(node.index.offset) + '.' +
610 std::to_string(node.code.depth()) + '.' + std::to_string(node.code.offset());
611 out << id << " [";
612
613 if (valid_inner) {
614 out << parent_shape;
615 }
616
617 out << "label=<";
618 if (valid_return) {
619 // We need to write this node regardless, otherwise we would have disconnected nodes
620 onDotFile(out, n.index, map_types);
621 } else {
622 out << ' ';
623 }
624
625 out << ">";
626 if (valid_inner) {
627 out << " color=darkorange1";
628 }
629 out << "]\n";
630
631 if (valid_inner) {
632 saveDotFileRecurs(out, n, id, pred, map_types, parent_shape);
633 }
634
635 out << "}";
636 }
637
638 /**************************************************************************************
639 | |
640 | GPU |
641 | |
642 **************************************************************************************/
643
644 void gpuRelease()
645 {
646 gpuRelease(MapBasesISeq{});
647 Base::gpuRelease();
648 }
649
650 [[nodiscard]] std::size_t gpuNumBuffers(MapType map_type) const
651 {
652 return MapType::TREE == map_type ? Base::template gpuNumBuffers<TreeBlock>()
653 : gpuNumBuffers(map_type, MapBasesISeq{});
654 }
655
656 [[nodiscard]] std::size_t gpuNumLeafBuffers(MapType map_type) const
657 {
658 return MapType::TREE == map_type ? Base::template gpuNumLeafBuffers<TreeBlock>()
659 : gpuNumLeafBuffers(map_type, MapBasesISeq{});
660 }
661
662 [[nodiscard]] std::size_t gpuNumInnerBuffers(MapType map_type) const
663 {
664 return MapType::TREE == map_type ? Base::template gpuNumInnerBuffers<TreeBlock>()
665 : gpuNumInnerBuffers(map_type, MapBasesISeq{});
666 }
667
668 [[nodiscard]] WGPUBuffer gpuLeafBuffer(MapType map_type, std::size_t index = 0) const
669 {
670 return MapType::TREE == map_type ? Base::template gpuLeafBuffer<TreeBlock>(index)
671 : gpuLeafBuffer(map_type, index, MapBasesISeq{});
672 }
673
674 [[nodiscard]] WGPUBuffer gpuInnerBuffer(MapType map_type, std::size_t index = 0) const
675 {
676 return MapType::TREE == map_type ? Base::template gpuInnerBuffer<TreeBlock>(index)
677 : gpuInnerBuffer(map_type, index, MapBasesISeq{});
678 }
679
680 [[nodiscard]] std::size_t gpuLeafBufferSize(MapType map_type,
681 std::size_t index = 0) const
682 {
683 return MapType::TREE == map_type ? Base::template gpuLeafBufferSize<TreeBlock>(index)
684 : gpuLeafBufferSize(map_type, index, MapBasesISeq{});
685 }
686
687 [[nodiscard]] std::size_t gpuInnerBufferSize(MapType map_type,
688 std::size_t index = 0) const
689 {
690 return MapType::TREE == map_type
691 ? Base::template gpuInnerBufferSize<TreeBlock>(index)
692 : gpuInnerBufferSize(map_type, index, MapBasesISeq{});
693 }
694
695 void gpuRead(MapType map_types = MapType::ALL)
696 {
697 Base::template gpuRead<TreeBlock>();
698 gpuRead(map_types, MapBasesISeq{});
699 }
700
701 void gpuReadLeaf(MapType map_types = MapType::ALL)
702 {
703 Base::template gpuReadLeaf<TreeBlock>();
704 gpuReadLeaf(map_types, MapBasesISeq{});
705 }
706
707 void gpuReadInner(MapType map_types = MapType::ALL)
708 {
709 Base::template gpuReadInner<TreeBlock>();
710 gpuReadInner(map_types, MapBasesISeq{});
711 }
712
713 template <class Predicate, std::enable_if_t<pred::is_pred_v<Predicate>, bool> = true>
714 void gpuRead(Predicate const& pred)
715 {
716 gpuRead(pred::predicate_map_type_v<Predicate>);
717 }
718
719 template <class Predicate, std::enable_if_t<pred::is_pred_v<Predicate>, bool> = true>
720 void gpuReadLeaf(Predicate const& pred)
721 {
722 gpuReadLeaf(pred::predicate_map_type_v<Predicate>);
723 }
724
725 template <class Predicate, std::enable_if_t<pred::is_pred_v<Predicate>, bool> = true>
726 void gpuReadInner(Predicate const& pred)
727 {
728 gpuReadInner(pred::predicate_map_type_v<Predicate>);
729 }
730
731 bool gpuWrite(MapType map_types = MapType::ALL)
732 {
733 bool updated = Base::template gpuWrite<TreeBlock>();
734 return gpuWrite(map_types, MapBasesISeq{}) || updated;
735 }
736
737 bool gpuWriteLeaf(MapType map_types = MapType::ALL)
738 {
739 bool updated = Base::template gpuWriteLeaf<TreeBlock>();
740 return gpuWriteLeaf(map_types, MapBasesISeq{}) || updated;
741 }
742
743 bool gpuWriteInner(MapType map_types = MapType::ALL)
744 {
745 bool updated = Base::template gpuWriteInner<TreeBlock>();
746 return gpuWriteInner(map_types, MapBasesISeq{}) || updated;
747 }
748
749 template <class Predicate, std::enable_if_t<pred::is_pred_v<Predicate>, bool> = true>
750 bool gpuWrite(Predicate const& pred)
751 {
752 return gpuWrite(pred::predicate_map_type_v<Predicate>);
753 }
754
755 template <class Predicate, std::enable_if_t<pred::is_pred_v<Predicate>, bool> = true>
756 bool gpuWriteLeaf(Predicate const& pred)
757 {
758 return gpuWriteLeaf(pred::predicate_map_type_v<Predicate>);
759 }
760
761 template <class Predicate, std::enable_if_t<pred::is_pred_v<Predicate>, bool> = true>
762 bool gpuWriteInner(Predicate const& pred)
763 {
764 return gpuWriteInner(pred::predicate_map_type_v<Predicate>);
765 }
766
767 protected:
768 /**************************************************************************************
769 | |
770 | Functions Maps Should Have |
771 | |
772 **************************************************************************************/
773
774 void onInitRoot() { onInitRoot(Base::block(), MapBasesISeq{}); }
775
776 template <std::size_t... Is>
777 void onInitRoot(pos_type block, std::index_sequence<Is...>)
778 {
779 return (onInitRoot<std::tuple_element_t<Is, MapBases>>(block), ...);
780 }
781
782 template <class Map>
783 void onInitRoot(pos_type block)
784 {
785 Map::onInitRoot(block);
786 }
787
788 void onInitLeafChildren(Index node, pos_type children)
789 {
790 onInitLeafChildren(node, children, MapBasesISeq{});
791 }
792
793 template <std::size_t... Is>
794 void onInitLeafChildren(Index node, pos_type children, std::index_sequence<Is...>)
795 {
796 return (onInitLeafChildren<std::tuple_element_t<Is, MapBases>>(node, children), ...);
797 }
798
799 template <class Map>
800 void onInitLeafChildren(Index node, pos_type children)
801 {
802 Map::onInitLeafChildren(node, children);
803 }
804
805 void onInitInnerChildren(Index node, pos_type children)
806 {
807 onInitInnerChildren(node, children, MapBasesISeq{});
808 }
809
810 template <std::size_t... Is>
811 void onInitInnerChildren(Index node, pos_type children, std::index_sequence<Is...>)
812 {
813 return (onInitInnerChildren<std::tuple_element_t<Is, MapBases>>(node, children), ...);
814 }
815
816 template <class Map>
817 void onInitInnerChildren(Index node, pos_type children)
818 {
819 Map::onInitInnerChildren(node, children);
820 }
821
822 void onPropagateChildren(Index node, pos_type children, MapType map_types)
823 {
824 onPropagateChildren(node, children, map_types, MapBasesISeq{});
825 }
826
827 template <std::size_t... Is>
828 void onPropagateChildren(Index node, pos_type children, MapType map_types,
829 std::index_sequence<Is...>)
830 {
831 return (onPropagateChildren<std::tuple_element_t<Is, MapBases>>(node, children,
832 map_types),
833 ...);
834 }
835
836 template <class Map>
837 void onPropagateChildren(Index node, pos_type children, MapType map_types)
838 {
839 if (!isMapType<Map>(map_types)) {
840 return;
841 }
842
843 Map::onPropagateChildren(node, children);
844 }
845
846 [[nodiscard]] bool onIsPrunable(pos_type block) const
847 {
848 return Base::noneParent(block) && onIsPrunable(block, MapBasesISeq{});
849 }
850
851 template <std::size_t... Is>
852 [[nodiscard]] bool onIsPrunable(pos_type block, std::index_sequence<Is...>) const
853 {
854 return (onIsPrunable<std::tuple_element_t<Is, MapBases>>(block) && ...);
855 }
856
857 template <class Map>
858 [[nodiscard]] bool onIsPrunable(pos_type block) const
859 {
860 return Map::onIsPrunable(block);
861 }
862
863 void onPruneLeafChildren(Index node, pos_type children)
864 {
865 onPruneLeafChildren(node, children, MapBasesISeq{});
866 }
867
868 template <std::size_t... Is>
869 void onPruneLeafChildren(Index node, pos_type children, std::index_sequence<Is...>)
870 {
871 (onPruneLeafChildren<std::tuple_element_t<Is, MapBases>>(node, children), ...);
872 }
873
874 template <class Map>
875 void onPruneLeafChildren(Index node, pos_type children)
876 {
877 Map::onPruneLeafChildren(node, children);
878 }
879
880 void onPruneInnerChildren(Index node, pos_type children)
881 {
882 onPruneInnerChildren(node, children, MapBasesISeq{});
883 }
884
885 template <std::size_t... Is>
886 void onPruneInnerChildren(Index node, pos_type children, std::index_sequence<Is...>)
887 {
888 (onPruneInnerChildren<std::tuple_element_t<Is, MapBases>>(node, children), ...);
889 }
890
891 template <class Map>
892 void onPruneInnerChildren(Index node, pos_type children)
893 {
894 Map::onPruneInnerChildren(node, children);
895 }
896
897 [[nodiscard]] std::size_t onSerializedSize(SerializedBlocks<BF> const& blocks,
898 std::size_t num_nodes,
899 MapType map_types) const
900 {
901 return onSerializedSize(blocks, num_nodes, map_types, MapBasesISeq{});
902 }
903
904 template <std::size_t... Is>
905 [[nodiscard]] std::size_t onSerializedSize(SerializedBlocks<BF> const& blocks,
906 std::size_t num_nodes, MapType map_types,
907 std::index_sequence<Is...>) const
908 {
909 return (onSerializedSize<std::tuple_element_t<Is, MapBases>>(blocks, num_nodes,
910 map_types) +
911 ...);
912 }
913
914 template <class Map>
915 [[nodiscard]] std::size_t onSerializedSize(SerializedBlocks<BF> const& blocks,
916 std::size_t num_nodes,
917 MapType map_types) const
918 {
919 return isMapType<Map>(map_types) ? Map::onSerializedSize(blocks, num_nodes) : 0;
920 }
921
922 template <
923 class ExecutionPolicy,
924 std::enable_if_t<execution::is_execution_policy_v<ExecutionPolicy>, bool> = true>
925 void onRead(ExecutionPolicy&& policy, ReadBuffer& in,
926 SerializedBlocks<BF> const& blocks, MapType map_type,
927 std::uint64_t data_size)
928 {
929 onRead(std::forward<ExecutionPolicy>(policy), in, blocks, map_type, data_size,
930 MapBasesISeq{});
931 }
932
933 template <
934 class ExecutionPolicy, std::size_t... Is,
935 std::enable_if_t<execution::is_execution_policy_v<ExecutionPolicy>, bool> = true>
936 void onRead(ExecutionPolicy&& policy, ReadBuffer& in,
937 SerializedBlocks<BF> const& blocks, MapType map_type,
938 std::uint64_t data_size, std::index_sequence<Is...>)
939 {
940 (onRead<std::tuple_element_t<Is, MapBases>>(policy, in, blocks, map_type,
941 data_size) ||
942 ...);
943 }
944
945 template <
946 class Map, class ExecutionPolicy,
947 std::enable_if_t<execution::is_execution_policy_v<ExecutionPolicy>, bool> = true>
948 bool onRead(ExecutionPolicy&& policy, ReadBuffer& in,
949 SerializedBlocks<BF> const& blocks, MapType map_type,
950 std::uint64_t data_size)
951 {
952 if (!isMapType<Map>(map_type)) {
953 return false;
954 }
955
956 Map::onRead(std::forward<ExecutionPolicy>(policy), in, blocks);
957 return true;
958 }
959
960 template <
961 class ExecutionPolicy,
962 std::enable_if_t<execution::is_execution_policy_v<ExecutionPolicy>, bool> = true>
963 void onWrite(ExecutionPolicy&& policy, WriteBuffer& out,
964 SerializedBlocks<BF> const& blocks, MapType map_type) const
965 {
966 onWrite(std::forward<ExecutionPolicy>(policy), out, blocks, map_type, MapBasesISeq{});
967 }
968
969 template <
970 class ExecutionPolicy, std::size_t... Is,
971 std::enable_if_t<execution::is_execution_policy_v<ExecutionPolicy>, bool> = true>
972 void onWrite(ExecutionPolicy&& policy, WriteBuffer& out,
973 SerializedBlocks<BF> const& blocks, MapType map_type,
974 std::index_sequence<Is...>) const
975 {
976 (onWrite<std::tuple_element_t<Is, MapBases>>(policy, out, blocks, map_type), ...);
977 }
978
979 template <
980 class Map, class ExecutionPolicy,
981 std::enable_if_t<execution::is_execution_policy_v<ExecutionPolicy>, bool> = true>
982 void onWrite(ExecutionPolicy&& policy, WriteBuffer& out,
983 SerializedBlocks<BF> const& blocks, MapType map_type) const
984 {
985 if (!isMapType<Map>(map_type)) {
986 return;
987 }
988
989 Map::onWrite(std::forward<ExecutionPolicy>(policy), out, blocks);
990 }
991
992 void onDotFile(std::ostream& out, Index node, MapType map_types) const
993 {
994 out << "<br/>Center: " << Base::center(node);
995 out << "<br/>Depth: " << Base::depth(node) << " | Length: " << Base::length(node);
996 if (Base::modified(node)) {
997 out << "Modified: <font color='green'><b>true</b></font>";
998 } else {
999 out << "Modified: <font color='red'>false</font>";
1000 }
1001
1002 onDotFile(out, node, map_types, MapBasesISeq{});
1003 }
1004
1005 template <std::size_t... Is>
1006 void onDotFile(std::ostream& out, Index node, MapType map_types) const
1007 {
1008 (onDotFile<std::tuple_element_t<Is, MapBases>>(out, node, map_types), ...);
1009 }
1010
1011 template <class Map>
1012 void onDotFile(std::ostream& out, Index node, MapType map_types) const
1013 {
1014 if (MapType::NONE == (mapType<Map>() & map_types)) {
1015 return;
1016 }
1017
1018 Map::onDotFile((out << "<br/>"), node);
1019 }
1020
1021 /**************************************************************************************
1022 | |
1023 | Map Types |
1024 | |
1025 **************************************************************************************/
1026
1027 template <std::size_t... Is>
1028 [[nodiscard]] static constexpr MapType mapTypes(std::index_sequence<Is...>) noexcept
1029 {
1030 return (mapType<std::tuple_element_t<Is, MapBases>>() | ...);
1031 }
1032
1033 template <class Map>
1034 [[nodiscard]] static constexpr MapType mapType() noexcept
1035 {
1036 return Map::Type;
1037 }
1038
1039 template <class Map>
1040 [[nodiscard]] static constexpr bool isMapType(MapType map_type) noexcept
1041 {
1042 return mapType<Map>() == (mapType<Map>() & map_type);
1043 }
1044
1045 /**************************************************************************************
1046 | |
1047 | Propagate |
1048 | |
1049 **************************************************************************************/
1050
1051 void propagate(pos_type block, MapType map_types)
1052 {
1053 if (Base::isPureLeaf(block)) {
1054 return;
1055 }
1056
1057 // Const access more optimized
1058 auto const& b = Base::treeInnerBlockConst(block);
1059
1060 if (Base::modifiedNone(b)) {
1061 return;
1062 }
1063
1064 for (offset_type i{}; BF > i; ++i) {
1065 Index n(block, i);
1066 auto c = Base::children(b, i);
1067
1068 if (!Base::valid(c) || !Base::modified(b, i)) {
1069 continue;
1070 }
1071
1072 propagate(c, map_types);
1073 onPropagateChildren(n, c, map_types);
1074
1075 if (onIsPrunable(c)) {
1076 Base::pruneChildren(n, c);
1077 }
1078 }
1079 }
1080
1081 template <
1082 class ExecutionPolicy,
1083 std::enable_if_t<execution::is_execution_policy_v<ExecutionPolicy>, bool> = true>
1084 void propagate(ExecutionPolicy&& policy, pos_type block, MapType map_types,
1085 bool is_parallel)
1086 {
1087 if (Base::isPureLeaf(block)) {
1088 return;
1089 }
1090
1091 // Const access more optimized
1092 auto const& b = Base::treeInnerBlockConst(block);
1093
1094 if (Base::modifiedNone(b)) {
1095 return;
1096 }
1097
1098 auto const d = Base::depth(block);
1099 if (BF - 2u <= Base::modifiedCount(b) && 2u < d) {
1100 ufo::for_each(policy, offset_type(0), offset_type(BF),
1101 [this, policy, block, map_types, is_parallel, &b](offset_type i) {
1102 Index n(block, i);
1103 auto c = Base::children(b, i);
1104
1105 if (!Base::valid(c) || !Base::modified(b, i)) {
1106 return;
1107 }
1108
1109 if (is_parallel) {
1110 propagate(c, map_types);
1111 } else {
1112 propagate(policy, c, map_types, true);
1113 }
1114 onPropagateChildren(n, c, map_types);
1115
1116 if (onIsPrunable(c)) {
1117 Base::pruneChildren(n, c);
1118 }
1119 });
1120 } else {
1121 for (offset_type i{}; BF > i; ++i) {
1122 Index n(block, i);
1123 auto c = Base::children(b, i);
1124
1125 if (!Base::valid(c) || !Base::modified(b, i)) {
1126 return;
1127 }
1128
1129 propagate(policy, c, map_types, is_parallel);
1130 onPropagateChildren(n, c, map_types);
1131
1132 if (onIsPrunable(c)) {
1133 Base::pruneChildren(n, c);
1134 }
1135 }
1136 }
1137 }
1138
1139 /**************************************************************************************
1140 | |
1141 | I/O |
1142 | |
1143 **************************************************************************************/
1144
1145 template <class ExecutionPolicy, class Input>
1146 void readDataImpl(ExecutionPolicy&& policy, Input& in, MapHeader const& header,
1147 MapType map_types, bool propagate)
1148 {
1149 if (Dim != header.leaf_node_length.size()) {
1150 throw std::runtime_error("Trying to read map with dimension " +
1151 std::to_string(header.leaf_node_length.size()) +
1152 " into a map with dimension " + std::to_string(Dim));
1153 }
1154
1155 Length leaf_node_length;
1156 for (std::size_t i{}; Dim > i; ++i) {
1157 leaf_node_length[i] = header.leaf_node_length[i];
1158 }
1159
1160 if (Base::length(0) != leaf_node_length ||
1161 Base::numDepthLevels() != header.num_depth_levels) {
1162 Base::clear(leaf_node_length, header.num_depth_levels);
1163 }
1164
1165 readMaps(policy, in, readBlocks(in, header), header, map_types);
1166
1167 if (propagate) {
1168 this->propagate(policy, map_types);
1169 }
1170 }
1171
1172 template <class Input>
1173 [[nodiscard]] SerializedBlocks<BF> readBlocks(Input& in, MapHeader const& header)
1174 {
1175 std::vector<BitSet<BF>> tree(header.map_info[0].size);
1176
1177 if (0 < header.map_info[0].size) {
1178 std::size_t size = header.map_info[0].size * sizeof(BitSet<BF>);
1179 if constexpr (std::is_base_of_v<std::istream, remove_cvref_t<Input>>) {
1180 in.read(reinterpret_cast<char*>(tree.data()), size);
1181 } else if constexpr (std::is_base_of_v<ReadBuffer, remove_cvref_t<Input>>) {
1182 in.read(tree.data(), size);
1183 } else {
1184 static_assert(dependent_false_v<Input>, "Wrong input type");
1185 }
1186 }
1187
1188 SerializedBlocks<BF> blocks;
1189
1190 if (0 < header.num_blocks) {
1191 blocks.reserve(header.num_blocks);
1192 readBlocksRecurs(Base::block(), tree.begin(), blocks);
1193
1194 for (std::size_t i = 1; blocks.size() > i; ++i) {
1195 blocks[i].data_start = blocks[i - 1].data_start + blocks[i - 1].offsets.count();
1196 }
1197 }
1198
1199 return blocks;
1200 }
1201
1202 typename std::vector<BitSet<BF>>::const_iterator readBlocksRecurs(
1203 pos_type block, typename std::vector<BitSet<BF>>::const_iterator tree,
1204 SerializedBlocks<BF>& blocks)
1205 {
1206 BitSet<BF> const valid_return = *tree++;
1207 BitSet<BF> const valid_inner = *tree++;
1208 BitSet<BF> const valid_erase_children = valid_return & ~valid_inner;
1209
1210 Base::modified(block) |= (valid_return & valid_inner).data();
1211
1212 if (valid_return.any()) {
1213 blocks.emplace_back(0u, block, valid_return);
1214 }
1215
1216 if (valid_inner.none() && valid_erase_children.none()) {
1217 return tree;
1218 }
1219
1220 for (offset_type i{}; BF > i; ++i) {
1221 if (valid_erase_children[i]) {
1222 Base::eraseChildren(Index(block, i));
1223 }
1224 }
1225
1226 for (offset_type i{}; BF > i; ++i) {
1227 if (valid_inner[i]) {
1228 tree = readBlocksRecurs(Base::createChildren(Index(block, i)), tree, blocks);
1229 }
1230 }
1231
1232 return tree;
1233 }
1234
1235 template <class ExecutionPolicy>
1236 void readMaps(ExecutionPolicy&& policy, std::istream& in,
1237 SerializedBlocks<BF> const& blocks, MapHeader const& header,
1238 MapType map_types)
1239 {
1240 Buffer buffer;
1241 for (std::size_t i = 1; header.map_info.size() > i; ++i) {
1242 auto map_type = header.map_info[i].type;
1243 auto data_size = header.map_info[i].size;
1244
1245 if (hasMapTypes(map_types & map_type)) {
1246 buffer.clear();
1247 buffer.write(in, data_size);
1248 onRead(policy, buffer, blocks, map_type, data_size);
1249 } else {
1250 // Skip forward
1251 in.seekg(static_cast<std::istream::off_type>(data_size), std::istream::cur);
1252 }
1253 }
1254 }
1255
1256 template <class ExecutionPolicy>
1257 void readMaps(ExecutionPolicy&& policy, ReadBuffer& in,
1258 SerializedBlocks<BF> const& blocks, MapHeader const& header,
1259 MapType map_types)
1260 {
1261 for (std::size_t i = 1; header.map_info.size() > i; ++i) {
1262 auto map_type = header.map_info[i].type;
1263 auto data_size = header.map_info[i].size;
1264 auto pos = in.readPos();
1265
1266 if (hasMapTypes(map_types & map_type)) {
1267 onRead(policy, in, blocks, map_type, data_size);
1268 }
1269
1270 // Skip forward
1271 in.readSeek(pos + data_size);
1272 }
1273 }
1274
1275 // template <class Predicate, std::enable_if_t<pred::is_pred_v<Predicate>, bool> = true>
1276 // [[nodiscard]] std::vector<detail::Fulfill<BF>> fulfills(Predicate pred) const
1277 // {
1278 // std::vector<detail::Fulfill<BF>> res;
1279
1280 // // TODO: Implement
1281
1282 // return res;
1283 // }
1284
1285 // template <class Predicate, std::enable_if_t<pred::is_pred_v<Predicate>, bool> = true>
1286 // void fulfillsRecurs(Node parent, Predicate const& pred,
1287 // std::vector<detail::Fulfill<BF>>& fulfills) const
1288 // {
1289 // // TODO: Implement
1290 // }
1291
1292 // void fulfillsModifiedRecurs(pos_type block,
1293 // std::vector<detail::Fulfill<BF>>& fulfills) const
1294 // {
1295 // // TODO: Implement
1296 // }
1297
1298 template <class ExecutionPolicy, class Output, class Predicate>
1299 MapHeader writeImpl(ExecutionPolicy&& policy, Output& out, Predicate const& pred,
1300 MapType map_types, bool write_header) const
1301 {
1302 auto [tree, blocks] = writeBlocks(pred);
1303
1304 for (std::size_t i = 1; blocks.size() > i; ++i) {
1305 blocks[i].data_start = blocks[i - 1].data_start + blocks[i - 1].offsets.count();
1306 }
1307
1308 MapHeader h = header(map_types);
1309 h.num_blocks = blocks.size();
1310 h.num_nodes = blocks.back().data_start + blocks.back().offsets.count();
1311 h.map_info[0].size = tree.size();
1312 for (std::size_t i = 1; h.map_info.size() > i; ++i) {
1313 h.map_info[i].size = onSerializedSize(blocks, h.num_nodes, h.map_info[i].type);
1314 }
1315
1316 if (write_header) {
1317 h.write(out);
1318 }
1319
1320 if (!tree.empty()) {
1321 std::size_t size = tree.size() * sizeof(BitSet<BF>);
1322 if constexpr (std::is_base_of_v<std::ostream, remove_cvref_t<Output>>) {
1323 out.write(reinterpret_cast<char*>(tree.data()), size);
1324 } else if constexpr (std::is_base_of_v<WriteBuffer, remove_cvref_t<Output>>) {
1325 out.write(tree.data(), size);
1326 } else {
1327 static_assert(dependent_false_v<Output>, "Wrong output type");
1328 }
1329 }
1330
1331 if (!blocks.empty()) {
1332 writeMaps(std::forward<ExecutionPolicy>(policy), out, blocks, h);
1333 }
1334
1335 return h;
1336 }
1337
1338 template <class Predicate>
1339 [[nodiscard]] std::pair<std::vector<BitSet<BF>>, SerializedBlocks<BF>> writeBlocks(
1340 Predicate pred) const
1341 {
1342 using P = remove_cvref_t<Predicate>;
1343 using Filter = pred::Filter<P>;
1344 using L = pred::Leaf;
1345 using M = pred::Modified<false>;
1346 using P1 = decltype(std::declval<L>() && std::declval<M>());
1347 using P2 = decltype(std::declval<M>() && std::declval<L>());
1348
1349 std::pair<std::vector<BitSet<BF>>, SerializedBlocks<BF>> res;
1350
1351 auto& tree = res.first;
1352 auto& blocks = res.second;
1353
1354 if constexpr (contains_type_v<P, P1, P2>) {
1355 auto root = Base::index();
1356
1357 bool leaf = Base::isLeaf(root);
1358 bool modified = Base::modified(root);
1359
1360 bool valid_return = leaf && modified;
1361 bool valid_inner = !leaf && modified;
1362
1363 tree.emplace_back(valid_return ? 1u : 0u);
1364 tree.emplace_back(valid_inner ? 1u : 0u);
1365
1366 if (valid_return) {
1367 blocks.emplace_back(0u, root.pos, BitSet<BF>(1u));
1368 } else if (valid_inner) {
1369 writeBlocksModifiedRecurs(Base::children(root), tree, blocks);
1370 }
1371 } else {
1372 Filter::init(pred, *this);
1373
1374 auto root = Base::node();
1375
1376 bool valid_return = Filter::returnable(pred, *this, root);
1377 bool valid_inner =
1378 Base::isParent(root.index) && Filter::traversable(pred, *this, root);
1379
1380 tree.emplace_back(valid_return ? 1u : 0u);
1381 tree.emplace_back(valid_inner ? 1u : 0u);
1382
1383 if (valid_return) {
1384 blocks.emplace_back(0u, root.index.pos, BitSet<BF>(1u));
1385 }
1386 if (valid_inner) {
1387 writeBlocksRecurs(root, pred, tree, blocks);
1388 }
1389 }
1390
1391 if (blocks.empty()) {
1392 tree.clear();
1393 }
1394
1395 return res;
1396 }
1397
1398 template <class Predicate>
1399 bool writeBlocksRecurs(Node parent, Predicate const& pred,
1400 std::vector<BitSet<BF>>& tree,
1401 SerializedBlocks<BF>& blocks) const
1402 {
1403 using P = remove_cvref_t<Predicate>;
1404 using Filter = pred::Filter<P>;
1405
1406 auto const& block = Base::TreeInnerBlock(parent.index.pos);
1407 auto const c = Base::children(block, parent.index.offset);
1408
1409 if (Base::isPureLeaf(c)) {
1410 BitSet<BF> vr;
1411 for (offset_type i{}; BF > i; ++i) {
1412 Node node(Base::child(parent.code, i), Index(c, i));
1413 vr[i] = Filter::returnable(pred, *this, node);
1414 }
1415
1416 if (vr.none()) {
1417 return false;
1418 }
1419
1420 tree.push_back(vr);
1421 blocks.emplace_back(0u, c, vr);
1422 return true;
1423 }
1424
1425 BitSet<BF> vr;
1426 BitSet<BF> vi;
1427 std::array<Node, BF> node;
1428 for (offset_type i{}; BF > i; ++i) {
1429 node[i].code = Base::child(parent.code, i);
1430 node[i].index = Index(c, i);
1431 vr[i] = Filter::returnable(pred, *this, node[i]);
1432 vi[i] = Base::isParent(node.index) && Filter::traversable(pred, *this, node[i]);
1433 }
1434
1435 if (vr.none() && vi.none()) {
1436 return false;
1437 }
1438
1439 std::size_t const tree_size_before = tree.size();
1440 tree.emplace_back(vr);
1441 BitSet<BF>& valid_inner = tree.emplace_back(vi);
1442
1443 if (vr.any()) {
1444 blocks.emplace_back(0u, block, vr);
1445 }
1446
1447 if (vi.none()) {
1448 return true;
1449 }
1450
1451 for (offset_type i{}; BF > i; ++i) {
1452 vi[i] = vi[i] && writeNodesRecurs(node[i], pred, tree, blocks);
1453 }
1454
1455 valid_inner = vi;
1456
1457 if (vr.any() || vi.any()) {
1458 return true;
1459 }
1460
1461 tree.resize(tree_size_before);
1462 return false;
1463 }
1464
1465 bool writeBlocksModifiedRecurs(pos_type block, std::vector<BitSet<BF>>& tree,
1466 SerializedBlocks<BF>& blocks) const
1467 {
1468 if (Base::isPureLeaf(block)) {
1469 auto const m = BitSet<BF>(Base::modified(Base::treeLeafBlock(block)));
1470 if (m.none()) {
1471 return false;
1472 }
1473
1474 tree.push_back(m);
1475 blocks.emplace_back(0u, block, m);
1476 return true;
1477 }
1478
1479 auto const& b = Base::treeInnerBlock(block);
1480 auto const m = BitSet<BF>(Base::modified(b));
1481 auto const& c = Base::children(b);
1482
1483 BitSet<BF> leaf;
1484 for (offset_type i{}; BF > i; ++i) {
1485 leaf[i] = !Base::valid(c[i]);
1486 }
1487
1488 BitSet<BF> const vr = leaf & m;
1489 BitSet<BF> vi = ~leaf & m;
1490
1491 if (vr.none() && vi.none()) {
1492 return false;
1493 }
1494
1495 std::size_t const tree_size_before = tree.size();
1496 tree.emplace_back(vr);
1497 BitSet<BF>& valid_inner = tree.emplace_back(vi);
1498
1499 if (vr.any()) {
1500 blocks.emplace_back(0u, block, vr);
1501 }
1502
1503 if (vi.none()) {
1504 return true;
1505 }
1506
1507 for (offset_type i{}; BF > i; ++i) {
1508 vi[i] = vi[i] && writeBlocksModifiedRecurs(c[i], tree, blocks);
1509 }
1510
1511 valid_inner = vi;
1512
1513 if (vr.any() || vi.any()) {
1514 return true;
1515 }
1516
1517 tree.resize(tree_size_before);
1518 return false;
1519 }
1520
1521 template <class ExecutionPolicy>
1522 void writeMaps(ExecutionPolicy&& policy, std::ostream& out,
1523 SerializedBlocks<BF> const& blocks, MapHeader const& header) const
1524 {
1525 if (blocks.empty()) {
1526 return;
1527 }
1528
1529 std::uint64_t max_size{};
1530 for (std::size_t i = 1; header.map_info.size() > i; ++i) {
1531 max_size = std::max(max_size, header.map_info[i].size);
1532 }
1533
1534 Buffer buffer;
1535 buffer.reserve(max_size);
1536
1537 for (std::size_t i = 1; header.map_info.size() > i; ++i) {
1538 buffer.clear();
1539 onWrite(policy, buffer, blocks, header.map_info[i].type);
1540 if (!buffer.empty()) {
1541 buffer.read(out, buffer.size());
1542 }
1543 // TODO: Fill in compressed size
1544 }
1545 }
1546
1547 template <class ExecutionPolicy>
1548 void writeMaps(ExecutionPolicy&& policy, WriteBuffer& out,
1549 SerializedBlocks<BF> const& blocks, MapHeader const& header) const
1550 {
1551 if (blocks.empty()) {
1552 return;
1553 }
1554
1555 std::size_t total_size{};
1556 for (std::size_t i = 1; header.map_info.size() > i; ++i) {
1557 total_size += header.map_info[i].size;
1558 }
1559
1560 out.reserve(out.size() + total_size);
1561
1562 for (std::size_t i = 1; header.map_info.size() > i; ++i) {
1563 onWrite(policy, out, blocks, header.map_info[i].type);
1564 // TODO: Fill in compressed size
1565 }
1566 }
1567
1568 /**************************************************************************************
1569 | |
1570 | Dot file |
1571 | |
1572 **************************************************************************************/
1573
1574 template <class Predicate, std::enable_if_t<pred::is_pred_v<Predicate>, bool> = true>
1575 void saveDotFileRecurs(std::ostream& out, Node node, std::string const& id,
1576 Predicate const& pred, MapType map_types,
1577 std::string const& parent_shape) const
1578 {
1579 using Filter = pred::Filter<Predicate>;
1580
1581 for (std::size_t i{}; BF > i; ++i) {
1582 Node child = Base::child(node, i);
1583 bool valid_return = Filter::returnable(pred, *this, child);
1584 bool valid_inner = Base::isParent(child) && Filter::traversable(pred, *this, child);
1585
1586 if (!valid_return && !valid_inner) {
1587 continue;
1588 }
1589
1590 std::string child_id = std::to_string(child.index.pos) + '.' +
1591 std::to_string(child.index.offset) + '.' +
1592 std::to_string(child.code.depth()) + '.' +
1593 std::to_string(child.code.offset());
1594 out << child_id << " [";
1595
1596 if (valid_inner) {
1597 out << parent_shape;
1598 }
1599
1600 out << "label=<";
1601 if (valid_return) {
1602 // We need to write this node regardless, otherwise we would have disconnected
1603 // nodes
1604 onDotFile(out, child.index, map_types);
1605 } else {
1606 out << ' ';
1607 }
1608
1609 out << ">";
1610 if (valid_inner) {
1611 out << " color=darkorange1";
1612 }
1613 out << "]\n";
1614 out << id << " -- " << child_id << '\n';
1615
1616 if (valid_inner) {
1617 saveDotFileRecurs(out, child, child_id, pred, map_types, parent_shape);
1618 }
1619 }
1620 }
1621
1622 /**************************************************************************************
1623 | |
1624 | GPU |
1625 | |
1626 **************************************************************************************/
1627
1628 template <std::size_t... Is>
1629 void gpuRelease(std::index_sequence<Is...>)
1630 {
1631 (gpuRelease<std::tuple_element_t<Is, MapBases>>(), ...);
1632 }
1633
1634 template <class Map>
1635 void gpuRelease()
1636 {
1637 Map::onGpuRelease();
1638 }
1639
1640 template <std::size_t... Is>
1641 [[nodiscard]] std::size_t gpuNumBuffers(MapType map_type,
1642 std::index_sequence<Is...>) const
1643 {
1644 return std::max({gpuNumBuffers<std::tuple_element_t<Is, MapBases>>(map_type)...});
1645 }
1646
1647 template <class Map>
1648 [[nodiscard]] std::size_t gpuNumBuffers(MapType map_type) const
1649 {
1650 return isMapType<Map>(map_type) ? Base::template gpuNumBuffers<typename Map::Block>()
1651 : std::size_t(0);
1652 }
1653
1654 template <std::size_t... Is>
1655 [[nodiscard]] std::size_t gpuNumLeafBuffers(MapType map_type,
1656 std::index_sequence<Is...>) const
1657 {
1658 return std::max({gpuNumLeafBuffers<std::tuple_element_t<Is, MapBases>>(map_type)...});
1659 }
1660
1661 template <class Map>
1662 [[nodiscard]] std::size_t gpuNumLeafBuffers(MapType map_type) const
1663 {
1664 return isMapType<Map>(map_type)
1665 ? Base::template gpuNumLeafBuffers<typename Map::Block>()
1666 : std::size_t(0);
1667 }
1668
1669 template <std::size_t... Is>
1670 [[nodiscard]] std::size_t gpuNumInnerBuffers(MapType map_type,
1671 std::index_sequence<Is...>) const
1672 {
1673 return std::max(
1674 {gpuNumInnerBuffers<std::tuple_element_t<Is, MapBases>>(map_type)...});
1675 }
1676
1677 template <class Map>
1678 [[nodiscard]] std::size_t gpuNumInnerBuffers(MapType map_type) const
1679 {
1680 return isMapType<Map>(map_type)
1681 ? Base::template gpuNumInnerBuffers<typename Map::Block>()
1682 : std::size_t(0);
1683 }
1684
1685 template <std::size_t... Is>
1686 [[nodiscard]] WGPUBuffer gpuLeafBuffer(MapType map_type, std::size_t index,
1687 std::index_sequence<Is...>) const
1688 {
1689 return std::max(
1690 {gpuLeafBuffer<std::tuple_element_t<Is, MapBases>>(map_type, index)...});
1691 }
1692
1693 template <class Map>
1694 [[nodiscard]] WGPUBuffer gpuLeafBuffer(MapType map_type, std::size_t index) const
1695 {
1696 return isMapType<Map>(map_type)
1697 ? Base::template gpuLeafBuffer<typename Map::Block>(index)
1698 : nullptr;
1699 }
1700
1701 template <std::size_t... Is>
1702 [[nodiscard]] WGPUBuffer gpuInnerBuffer(MapType map_type, std::size_t index,
1703 std::index_sequence<Is...>) const
1704 {
1705 return std::max(
1706 {gpuInnerBuffer<std::tuple_element_t<Is, MapBases>>(map_type, index)...});
1707 }
1708
1709 template <class Map>
1710 [[nodiscard]] WGPUBuffer gpuInnerBuffer(MapType map_type, std::size_t index) const
1711 {
1712 return isMapType<Map>(map_type)
1713 ? Base::template gpuInnerBuffer<typename Map::Block>(index)
1714 : nullptr;
1715 }
1716
1717 template <std::size_t... Is>
1718 [[nodiscard]] std::size_t gpuLeafBufferSize(MapType map_type, std::size_t index,
1719 std::index_sequence<Is...>) const
1720 {
1721 return std::max(
1722 {gpuLeafBufferSize<std::tuple_element_t<Is, MapBases>>(map_type, index)...});
1723 }
1724
1725 template <class Map>
1726 [[nodiscard]] std::size_t gpuLeafBufferSize(MapType map_type, std::size_t index) const
1727 {
1728 return isMapType<Map>(map_type)
1729 ? Base::template gpuLeafBufferSize<typename Map::Block>(index)
1730 : std::size_t(0);
1731 }
1732
1733 template <std::size_t... Is>
1734 [[nodiscard]] std::size_t gpuInnerBufferSize(MapType map_type, std::size_t index,
1735 std::index_sequence<Is...>) const
1736 {
1737 return std::max(
1738 {gpuInnerBufferSize<std::tuple_element_t<Is, MapBases>>(map_type, index)...});
1739 }
1740
1741 template <class Map>
1742 [[nodiscard]] std::size_t gpuInnerBufferSize(MapType map_type, std::size_t index) const
1743 {
1744 return isMapType<Map>(map_type)
1745 ? Base::template gpuInnerBufferSize<typename Map::Block>(index)
1746 : std::size_t(0);
1747 }
1748
1749 template <std::size_t... Is>
1750 void gpuRead(MapType map_types, std::index_sequence<Is...>)
1751 {
1752 (gpuRead<std::tuple_element_t<Is, MapBases>>(map_types), ...);
1753 }
1754
1755 template <class Map>
1756 void gpuRead(MapType map_types)
1757 {
1758 if (!isMapType<Map>(map_types)) {
1759 return;
1760 }
1761
1762 Map::onGpuRead();
1763 Base::template gpuRead<typename Map::Block>();
1764 }
1765
1766 template <std::size_t... Is>
1767 void gpuReadLeaf(MapType map_types, std::index_sequence<Is...>)
1768 {
1769 (gpuReadLeaf<std::tuple_element_t<Is, MapBases>>(map_types), ...);
1770 }
1771
1772 template <class Map>
1773 void gpuReadLeaf(MapType map_types)
1774 {
1775 if (!isMapType<Map>(map_types)) {
1776 return;
1777 }
1778
1779 Map::onGpuReadLeaf();
1780 Base::template gpuReadLeaf<typename Map::Block>();
1781 }
1782
1783 template <std::size_t... Is>
1784 void gpuReadInner(MapType map_types, std::index_sequence<Is...>)
1785 {
1786 (gpuReadLeaf<std::tuple_element_t<Is, MapBases>>(map_types), ...);
1787 }
1788
1789 template <class Map>
1790 void gpuReadInner(MapType map_types)
1791 {
1792 if (!isMapType<Map>(map_types)) {
1793 return;
1794 }
1795
1796 Map::onGpuReadInner();
1797 Base::template gpuReadInner<typename Map::Block>();
1798 }
1799
1800 template <std::size_t... Is>
1801 bool gpuWrite(MapType map_types, std::index_sequence<Is...>)
1802 {
1803 return (gpuWrite<std::tuple_element_t<Is, MapBases>>(map_types) | ...);
1804 }
1805
1806 template <class Map>
1807 bool gpuWrite(MapType map_types)
1808 {
1809 if (!isMapType<Map>(map_types)) {
1810 return false;
1811 }
1812
1813 Map::onGpuWrite();
1814 return Base::template gpuWrite<typename Map::Block>();
1815 }
1816
1817 template <std::size_t... Is>
1818 bool gpuWriteLeaf(MapType map_types, std::index_sequence<Is...>)
1819 {
1820 return (gpuWriteLeaf<std::tuple_element_t<Is, MapBases>>(map_types) | ...);
1821 }
1822
1823 template <class Map>
1824 bool gpuWriteLeaf(MapType map_types)
1825 {
1826 if (!isMapType<Map>(map_types)) {
1827 return false;
1828 }
1829
1830 Map::onGpuWriteLeaf();
1831 return Base::template gpuWriteLeaf<typename Map::Block>();
1832 }
1833
1834 template <std::size_t... Is>
1835 bool gpuWriteInner(MapType map_types, std::index_sequence<Is...>)
1836 {
1837 return (gpuWriteLeaf<std::tuple_element_t<Is, MapBases>>(map_types) | ...);
1838 }
1839
1840 template <class Map>
1841 bool gpuWriteInner(MapType map_types)
1842 {
1843 if (!isMapType<Map>(map_types)) {
1844 return false;
1845 }
1846
1847 Map::onGpuWriteInner();
1848 return Base::template gpuWriteInner<typename Map::Block>();
1849 }
1850};
1851} // namespace ufo
1852
1853#endif // UFO_MAP_HPP
ufo::Map::propagate
void propagate(MapType map_types=MapType::ALL)
Propagate modified information up the tree.
Definition map.hpp:236
ufo::Tree
Utilizing curiously recurring template pattern (CRTP)
Definition tree.hpp:104
ufo::Tree::center
Coord center() const
Returns the center of the tree (/ root node).
Definition tree.hpp:637
ufo::Tree::block
constexpr pos_type block() const noexcept
Returns the block position of the root node.
Definition tree.hpp:743
ufo::Tree::isParent
bool isParent(NodeType node) const
Checks if the node is a parent (i.e., has children).
Definition tree.hpp:1308
ufo::Tree::isPureLeaf
bool isPureLeaf(pos_type block) const
Checks if the block is pure leaf (i.e., can never have children).
Definition tree.hpp:1256
ufo::Tree::valid
bool valid(pos_type block) const
Checks if a block is valid.
Definition tree.hpp:1361
ufo::Tree< Map< Dim, Maps... >, Dim, Maps::Block... >::size
std::size_t size() const
Returns the number of nodes in the tree.
Definition tree.hpp:218
ufo::Tree::depth
depth_type depth() const
Returns the depth of the root node, i.e. numDepthLevels() - 1.
Definition tree.hpp:290
ufo::Tree::noneParent
bool noneParent(pos_type block) const
Checks if no nodes of a block are parents.
Definition tree.hpp:2573
ufo::Tree::index
constexpr Index index() const noexcept
Returns the index of the root node.
Definition tree.hpp:803
ufo::Tree::child
constexpr auto child(NodeType node, offset_type offset) const
Returns the i:th child of node.
Definition tree.hpp:1450
ufo::Tree::length
Length length() const
Returns the length of the tree (/ root node), i.e. leaf_node_length * 2^depth().
Definition tree.hpp:342
ufo::Tree::branchingFactor
static constexpr offset_type branchingFactor() noexcept
Returns the branching factor of the tree (i.e., 2 = binary tree, 4 = quadtree, 8 = octree,...
Definition tree.hpp:203
ufo::Tree::maxNumDepthLevels
static constexpr depth_type maxNumDepthLevels() noexcept
Returns the maximum number of depth levels a tree can have.
Definition tree.hpp:278
ufo::Tree::numDepthLevels
constexpr depth_type numDepthLevels() const noexcept
Returns the number of depth levels of the tree, i.e. depth() + 1.
Definition tree.hpp:261
ufo::Tree< Map< Dim, Maps... >, Dim, Maps::Block... >::node
Node node() const
Returns the root node.
Definition tree.hpp:843
ufo::Tree::clear
void clear()
Erases all nodes from the tree.
Definition tree.hpp:234
ufo::Tree::isLeaf
bool isLeaf(NodeType node) const
Checks if the node is a leaf (i.e., has no children).
Definition tree.hpp:1292
ufo::Tree::modified
bool modified() const
Check if the root of the tree is modified.
Definition tree.hpp:981
std
STL namespace.
ufo
All vision-related classes and functions.
Definition cloud.hpp:49
ufo::for_each
constexpr UnaryFunc for_each(Index first, Index last, UnaryFunc f, Proj proj={})
Applies f to each integer index in [first, last) sequentially.
Definition algorithm.hpp:80
ufo::b
constexpr T b(Lab< T, Flags > color) noexcept
Returns the un-weighted blue–yellow axis value.
Definition lab.hpp:326
ufo::AABB
Axis-Aligned Bounding Box (AABB) in Dim-dimensional space.
Definition aabb.hpp:70