Recently, I’ve been implementing an internal scene graph data structure and I want to show my solution for building generic scene graph visitors.
Lets consider a basis type for our tree.
class base_node {
public:
base_node() : m_name{"default"} {}
base_node(std::string name) : m_name{std::move(name)} {}
[[nodiscard]] auto& name() { return m_name; }
[[nodiscard]] auto& name() const { return m_name; }
[[nodiscard]] auto& children() { return m_children; }
[[nodiscard]] auto& children() const { return m_children; }
private:
std::string m_name;
std::vector<base_node> m_children;
};
We can create a new scene graph like this:
auto layer_1 = base_node{"parent"};
auto& layer_2 = layer_1.children();
layer_2 = {{"child_1"},{"child_2"},{"child_3"},{"child_4"},{"child_5"}};
auto& layer_3 = layer_2[1].children();
layer_3 = {{"child_6"},{"child_7"},{"child_8"},{"child_9"},{"child_10"}};
It has a name and a vector of base_nodes to hold its children.
So now lets say you want to apply some function to the whole scene graph; lets say you want to print the hierarchy.
We could write a visitor functor which takes a base_node and recursively calls itself with all of its children printing the name of each node. For this example, we will visit in a preorder fashion.
We will also add some state to make it look pretty.
struct print_hierarchy {
void operator()(base_node& parent) {
auto put_indent = [count = m_level] (const char indent_char) mutable {
while(count--) std::cout << indent_char;
};
auto increase_indent = [&] () {
m_level += 2;
};
auto decrease_indent = [&] () {
m_level -= 2;
};
put_indent('-');
std::cout << parent.name() << '\n';
increase_indent();
for(auto& node: parent.children()) {
(*this)(node);
}
decrease_indent();
}
private:
size_t m_level{0};
};
If we call this on our hierarchy, we get:
parent
--child_1
--child_2
----child_6
----child_7
----child_8
----child_9
----child_10
--child_3
--child_4
--child_5
We can make this more generic by replacing the cout with a call to some callable.
We need to pass a Callable template argument to our visitor. We will also rename it to hierarchy_visitor
struct hierarchy_visitor {
template<class TCallable>
void operator()(base_node& parent, TCallable callable) {
auto put_indent = [count = m_level] (const char indent_char) mutable {
while(count--) std::cout << indent_char;
};
auto increase_indent = [&] () {
m_level += 2;
};
auto decrease_indent = [&] () {
m_level -= 2;
};
put_indent('-');
callable(parent);
increase_indent();
for(auto& node: parent.children()) {
(*this)(node, callable);
}
decrease_indent();
}
private:
size_t m_level{0};
};
We can now do this:
auto print_node = [](base_node& parent) {
std::cout << parent.name() << '\n';
};
auto visitor = hierarchy_visitor();
visitor(layer_1, print_node);
But now we have a new problem. We have formatting hard coded into our visitor. It isn’t as generic as it could be.
We want to refactor out the formatting code. We can move put_indent to the callable and make the callable accept a layer parameter that tells the current level in the hierarchy visitor. It makes since for a hierarchy visitor to know its current level so level will remain inside the visitor. We will also rename the lambdas to something that sounds more generic.
struct hierarchy_visitor {
template <class TCallable>
void operator()(base_node& parent, TCallable callable) {
auto increase_level = [&]() { m_level += 1; };
auto decrease_level = [&]() { m_level -= 1; };
callable(parent, m_level);
increase_level();
for (auto& node : parent.children()) {
(*this)(node, callable);
}
decrease_level();
}
private:
size_t m_level{0};
};
auto print_node = [indent_char = '-', indent_width = 2](base_node& parent, auto level) {
auto put_indent = [&indent_width, level](auto indent_char) mutable {
level *= indent_width;
while (level--) std::cout << indent_char;
};
put_indent(indent_char);
std::cout << parent.name() << '\n';
};
What if we don’t want to pass our callable in every recursive call? We can allow our hierarchy visitor to store it as a private member.
template<class TCallable>
struct hierarchy_visitor {
void operator()(base_node& parent) {
auto increase_level = [&]() { m_level += 1; };
auto decrease_level = [&]() { m_level -= 1; };
m_callable(parent, m_level);
increase_level();
for (auto& node : parent.children()) {
(*this)(node, callable);
}
decrease_level();
}
private:
TCallable m_callable;
size_t m_level{0};
};
But now we have an issue where we cant determine the type of a lambda to instantiate an instance of hierarchy_visitor. We will have to give hierarchy_visitor a constructor which takes a TCallable.
But even this is not enough. Since
We will have to create a builder.
template <typename Callable>
hierarchy_visitor<Callable> build_hierarchy_visitor(Callable callable) {
return {callable};
}
Now we can build a hierarchy_visitor but what about other types of visitors?
We can use some lambda magic with variable templates to accept a generic TCallable and TVisitor.
template <template <class> class TVisitor>
auto build_visitor =
[](auto callable) -> TVisitor<std::decay_t<decltype(callable)>> {
return {callable};
};
Unfortunately this doesn’t work in MSVC without -std:c++latest so we’ll have to try something else for the most portable code.
template <template <class> class TVisitor, class TCallable>
TVisitor<TCallable> build_visitor(TCallable callable) {
return {callable};
}
We can then create new visitors and call them like this:
auto visitor = build_visitor<hierarchy_visitor>(print_node);
visitor(layer_1);
I tested this one on Clang 9, GCC 9.2, and MSVC 19.24 and it works fine.
Here is an alternative which may be more flexible and also works on all platforms:
template <template <class> class TVisitor>
struct build_visitor_impl {
template <typename TCallable>
constexpr auto operator()(TCallable callable) const
-> TVisitor<decltype(callable)> {
return {callable};
}
};
template <template <class> class TVisitor>
inline constexpr auto build_visitor = build_visitor_impl<TVisitor>{};
View the full code on Compiler Explorer.
Thanks for reading!
