template<typename RTreeType, typename InternalVisitor = internal::RTreeImplementation::EmptyVisitor, typename LeafVisitor = internal::RTreeImplementation::EmptyVisitor, typename ElementVisitor = internal::RTreeImplementation::EmptyVisitor, typename IndexableVisitor = internal::RTreeImplementation::EmptyVisitor>
struct RTreeFunctionalVisitor< RTreeType, InternalVisitor, LeafVisitor, ElementVisitor, IndexableVisitor >
A depth-first visitor for RTree that invokes user-provided lambdas.
For every RTree object, we distinguish between the root node, the internal nodes (i.e., nodes that have other nodes as children) and leaf nodes (i.e., nodes that store the actual leaf values). During the traversal of the tree, we may want to hook into the traversal at different levels of the hierarchy. For example, we may want to print the bounding box of each internal node, then print the bounding box of each leaf node, and then finally print each element stored in the leaf nodes.
This is a convenience visitor for the RTree data structure that forwards each traversal event to four (optional) independent callables:
- an internal node visitor (called once per internal node, before descending),
- a leaf node visitor (called once per leaf node, before visiting its leaf elements),
- an element visitor (called once per leaf value stored in a leaf node),
- an indexable visitor (called once per leaf value, after translating Value -> Indexable with the tree's indexable getter).
The traversal is depth-first: starting from the root, internal nodes are visited, their children are recursed immediately, and leaf elements are delivered in the order stored inside each leaf node. This allows users to plug lambdas directly without defining a specific visitor class.
Example (taken from one of the tests): build a tree from 8 random points, then hook all four callbacks:
std::vector<Point<2>> pts(8); for (auto &p : pts) p = random_point<2>();
const BoundingBox<2> &box,
auto &child) { std::cout <<
"Internal node (level
" << level << ") box " <<
};
std::endl;
};
const auto &
value) { std::cout <<
" element " <<
value;
};
[](auto &, const auto &indexable) { std::cout << ", indexable " << indexable
<< std::endl;
};
std::cout << "Visiting R-tree with " << pts.size() << " points, and " <<
n_levels(tree) << " levels." << std::endl;
const bool IsBlockVector< VectorType >::value
void visit_rtree(const RTreeType &tree, InternalVisitor internal_node_visitor={}, LeafVisitor leaf_visitor={}, ElementVisitor element_visitor={}, IndexableVisitor indexable_visitor={})
RTree< typename ContainerType::size_type, IndexType, IndexableGetterFromIndices< ContainerType > > pack_rtree_of_indices(const ContainerType &container)
A possible output (indices and boxes depend on the random points) is:
Internal node (level 0) box 0.277775, 0.197551 : 0.911647, 0.55397 Leaf
(level 1) box 0.277775, 0.513401 : 0.364784, 0.55397 element 4, indexable
0.277775 0.55397 element 6, indexable 0.364784 0.513401 Leaf (level 1)
box 0.840188, 0.197551 : 0.911647, 0.394383 element 0, indexable 0.840188
0.394383 element 2, indexable 0.911647 0.197551 Internal node (level 0)
box 0.335223, 0.628871 : 0.95223, 0.916195 Leaf (level 1) box 0.335223,
0.628871 : 0.477397, 0.76823 element 3, indexable 0.335223 0.76823
element 5, indexable 0.477397 0.628871 Leaf (level 1) box 0.783099,
0.79844 : 0.95223, 0.916195 element 1, indexable 0.783099 0.79844
element 7, indexable 0.95223 0.916195
This structure exists to make it easy to instrument or analyze an rtree (bounding boxes, counts, aggregations, debug prints, etc.) without writing the boilerplate of a custom visitor type every time.
Users can call directly the function visit_rtree() (see below) instead of instantiating this class.
Definition at line 420 of file rtree.h.
1.16.1