Dune Core Modules (2.8.0)

traversal.hh
1// -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2// vi: set et ts=4 sw=2 sts=2:
3
4#ifndef DUNE_TYPETREE_TRAVERSAL_HH
5#define DUNE_TYPETREE_TRAVERSAL_HH
6
7#include <utility>
8
9#include <dune/common/hybridutilities.hh>
10#include <dune/common/std/type_traits.hh>
11
12#include <dune/typetree/childextraction.hh>
13#include <dune/typetree/nodetags.hh>
14#include <dune/typetree/treepath.hh>
15#include <dune/typetree/visitor.hh>
16
17namespace Dune {
18 namespace TypeTree {
19
25#ifndef DOXYGEN
27 struct NoOp
28 {
29 template<class... T>
30 constexpr void operator()(T&&...) const { /* do nothing */ }
31 };
32#endif
33
34 namespace Detail {
35
36 // SFINAE template check that Tree has a degree() function and a child() function accepting integer indices
37 template<class Tree>
38 using DynamicTraversalConcept = decltype((
39 std::declval<Tree>().degree(),
40 std::declval<Tree>().child(0u)
41 ));
42
43 // SFINAE template check that Tree has static (constexpr) function Tree::degree()
44 template<class Tree>
45 using StaticTraversalConcept = decltype((
46 std::integral_constant<std::size_t, Tree::degree()>{}
47 ));
48
49
50 template<class Tree, TreePathType::Type pathType, class Prefix,
51 std::enable_if_t<Tree::isLeaf, int> = 0>
52 constexpr auto leafTreePathTuple(Prefix prefix)
53 {
54 return std::make_tuple(prefix);
55 }
56
57 template<class Tree, TreePathType::Type pathType, class Prefix,
58 std::enable_if_t<not Tree::isLeaf, int> = 0>
59 constexpr auto leafTreePathTuple(Prefix prefix);
60
61 template<class Tree, TreePathType::Type pathType, class Prefix, std::size_t... indices,
62 std::enable_if_t<(Tree::isComposite or (Tree::isPower and (pathType!=TreePathType::dynamic))), int> = 0>
63 constexpr auto leafTreePathTuple(Prefix prefix, std::index_sequence<indices...>)
64 {
65 return std::tuple_cat(Detail::leafTreePathTuple<TypeTree::Child<Tree,indices>, pathType>(Dune::TypeTree::push_back(prefix, Dune::index_constant<indices>{}))...);
66 }
67
68 template<class Tree, TreePathType::Type pathType, class Prefix, std::size_t... indices,
69 std::enable_if_t<(Tree::isPower and (pathType==TreePathType::dynamic)), int> = 0>
70 constexpr auto leafTreePathTuple(Prefix prefix, std::index_sequence<indices...>)
71 {
72 return std::tuple_cat(Detail::leafTreePathTuple<TypeTree::Child<Tree,indices>, pathType>(Dune::TypeTree::push_back(prefix, indices))...);
73 }
74
75 template<class Tree, TreePathType::Type pathType, class Prefix,
76 std::enable_if_t<not Tree::isLeaf, int>>
77 constexpr auto leafTreePathTuple(Prefix prefix)
78 {
79 return Detail::leafTreePathTuple<Tree, pathType>(prefix, std::make_index_sequence<Tree::degree()>{});
80 }
81
82 /* The signature is the same as for the public applyToTree
83 * function in Dune::Typetree, despite the additionally passed
84 * treePath argument. The path passed here is associated to
85 * the tree and the relative paths of the children (wrt. to tree)
86 * are appended to this. Hence the behavior of the public function
87 * is resembled by passing an empty treePath.
88 */
89
90 /*
91 * This is the overload for leaf traversal
92 */
93 template<class T, class TreePath, class V,
94 std::enable_if_t<std::decay_t<T>::isLeaf, int> = 0>
95 void applyToTree(T&& tree, TreePath treePath, V&& visitor)
96 {
97 visitor.leaf(tree, treePath);
98 }
99
100 /*
101 * This is the general overload doing child traversal.
102 */
103 template<class T, class TreePath, class V,
104 std::enable_if_t<not std::decay_t<T>::isLeaf, int> = 0>
105 void applyToTree(T&& tree, TreePath treePath, V&& visitor)
106 {
107 using Tree = std::remove_reference_t<T>;
108 using Visitor = std::remove_reference_t<V>;
109 visitor.pre(tree, treePath);
110
111 // check which type of traversal is supported by the tree
112 using allowDynamicTraversal = Dune::Std::is_detected<DynamicTraversalConcept,Tree>;
113 using allowStaticTraversal = Dune::Std::is_detected<StaticTraversalConcept,Tree>;
114
115 // the tree must support either dynamic or static traversal
116 static_assert(allowDynamicTraversal::value || allowStaticTraversal::value);
117
118 // the visitor may specify preferred dynamic traversal
119 using preferDynamicTraversal = std::bool_constant<Visitor::treePathType == TreePathType::dynamic>;
120
121 // create a dynamic or static index range
122 auto indices = [&]{
123 if constexpr(preferDynamicTraversal::value && allowDynamicTraversal::value)
124 return Dune::range(std::size_t(tree.degree()));
125 else
126 return Dune::range(tree.degree());
127 }();
128
129 if constexpr(allowDynamicTraversal::value || allowStaticTraversal::value) {
130 Hybrid::forEach(indices, [&](auto i) {
131 auto&& child = tree.child(i);
132 using Child = std::decay_t<decltype(child)>;
133
134 visitor.beforeChild(tree, child, treePath, i);
135
136 // This requires that visitor.in(...) can always be instantiated,
137 // even if there's a single child only.
138 if (i>0)
139 visitor.in(tree, treePath);
140
141 constexpr bool visitChild = Visitor::template VisitChild<Tree,Child,TreePath>::value;
142 if constexpr(visitChild) {
143 auto childTreePath = Dune::TypeTree::push_back(treePath, i);
144 applyToTree(child, childTreePath, visitor);
145 }
146
147 visitor.afterChild(tree, child, treePath, i);
148 });
149 }
150 visitor.post(tree, treePath);
151 }
152
153 /* Traverse tree and visit each node. The signature is the same
154 * as for the public forEachNode function in Dune::Typtree,
155 * despite the additionally passed treePath argument. The path
156 * passed here is associated to the tree and the relative
157 * paths of the children (wrt. to tree) are appended to this.
158 * Hence the behavior of the public function is resembled
159 * by passing an empty treePath.
160 */
161 template<class T, class TreePath, class PreFunc, class LeafFunc, class PostFunc>
162 void forEachNode(T&& tree, TreePath treePath, PreFunc&& preFunc, LeafFunc&& leafFunc, PostFunc&& postFunc)
163 {
164 using Tree = std::decay_t<T>;
165 if constexpr(Tree::isLeaf) {
166 leafFunc(tree, treePath);
167 } else {
168 preFunc(tree, treePath);
169
170 // check which type of traversal is supported by the tree, prefer dynamic traversal
171 using allowDynamicTraversal = Dune::Std::is_detected<DynamicTraversalConcept,Tree>;
172 using allowStaticTraversal = Dune::Std::is_detected<StaticTraversalConcept,Tree>;
173
174 // the tree must support either dynamic or static traversal
175 static_assert(allowDynamicTraversal::value || allowStaticTraversal::value);
176
177 if constexpr(allowDynamicTraversal::value) {
178 // Specialization for dynamic traversal
179 for (std::size_t i = 0; i < tree.degree(); ++i) {
180 auto childTreePath = Dune::TypeTree::push_back(treePath, i);
181 forEachNode(tree.child(i), childTreePath, preFunc, leafFunc, postFunc);
182 }
183 } else if constexpr(allowStaticTraversal::value) {
184 // Specialization for static traversal
185 auto indices = std::make_index_sequence<Tree::degree()>{};
186 Hybrid::forEach(indices, [&](auto i) {
187 auto childTreePath = Dune::TypeTree::push_back(treePath, i);
188 forEachNode(tree.child(i), childTreePath, preFunc, leafFunc, postFunc);
189 });
190 }
191 postFunc(tree, treePath);
192 }
193 }
194
195 } // namespace Detail
196
197
198 // ********************************************************************************
199 // Public Interface
200 // ********************************************************************************
201
215 template<class Tree, TreePathType::Type pathType=TreePathType::dynamic>
216 constexpr auto leafTreePathTuple()
217 {
218 return Detail::leafTreePathTuple<std::decay_t<Tree>, pathType>(hybridTreePath());
219 }
220
222
236 template<typename Tree, typename Visitor>
237 void applyToTree(Tree&& tree, Visitor&& visitor)
238 {
239 Detail::applyToTree(tree, hybridTreePath(), visitor);
240 }
241
255 template<class Tree, class PreFunc, class LeafFunc, class PostFunc>
256 [[deprecated]] void forEachNode(Tree&& tree, PreFunc&& preFunc, LeafFunc&& leafFunc, PostFunc&& postFunc)
257 {
258 Detail::forEachNode(tree, hybridTreePath(), preFunc, leafFunc, postFunc);
259 }
260
273 template<class Tree, class InnerFunc, class LeafFunc>
274 [[deprecated]] void forEachNode(Tree&& tree, InnerFunc&& innerFunc, LeafFunc&& leafFunc)
275 {
276 Detail::forEachNode(tree, hybridTreePath(), innerFunc, leafFunc, NoOp{});
277 }
278
288 template<class Tree, class NodeFunc>
289 void forEachNode(Tree&& tree, NodeFunc&& nodeFunc)
290 {
291 Detail::forEachNode(tree, hybridTreePath(), nodeFunc, nodeFunc, NoOp{});
292 }
293
303 template<class Tree, class LeafFunc>
304 void forEachLeafNode(Tree&& tree, LeafFunc&& leafFunc)
305 {
306 Detail::forEachNode(tree, hybridTreePath(), NoOp{}, leafFunc, NoOp{});
307 }
308
310
311 } // namespace TypeTree
312} //namespace Dune
313
314#endif // DUNE_TYPETREE_TRAVERSAL_HH
std::integral_constant< std::size_t, i > index_constant
An index constant with value i.
Definition: indices.hh:28
typename detected_or< nonesuch, Op, Args... >::value_t is_detected
Detects whether Op<Args...> is valid.
Definition: type_traits.hh:326
constexpr void forEach(Range &&range, F &&f)
Range based for loop.
Definition: hybridutilities.hh:266
std::size_t degree(const Node &node)
Returns the degree of node as run time information.
Definition: nodeinterface.hh:76
constexpr HybridTreePath< T..., std::size_t > push_back(const HybridTreePath< T... > &tp, std::size_t i)
Appends a run time index to a HybridTreePath.
Definition: treepath.hh:278
constexpr HybridTreePath< T... > hybridTreePath(const T &... t)
Constructs a new HybridTreePath from the given indices.
Definition: treepath.hh:177
constexpr HybridTreePath< T... > treePath(const T &... t)
Constructs a new HybridTreePath from the given indices.
Definition: treepath.hh:188
void forEachNode(Tree &&tree, NodeFunc &&nodeFunc)
Traverse tree and visit each node.
Definition: traversal.hh:289
constexpr auto leafTreePathTuple()
Create tuple of tree paths to leafs.
Definition: traversal.hh:216
void forEachLeafNode(Tree &&tree, LeafFunc &&leafFunc)
Traverse tree and visit each leaf node.
Definition: traversal.hh:304
void applyToTree(Tree &&tree, Visitor &&visitor)
Apply visitor to TypeTree.
Definition: traversal.hh:237
typename impl::_Child< Node, indices... >::type Child
Template alias for the type of a child node given by a list of child indices.
Definition: childextraction.hh:223
ImplementationDefined child(Node &&node, Indices... indices)
Extracts the child of a node given by a sequence of compile-time and run-time indices.
Definition: childextraction.hh:126
Dune namespace.
Definition: alignedallocator.hh:11
Creative Commons License   |  Legal Statements / Impressum  |  Hosted by TU Dresden  |  generated with Hugo v0.111.3 (Nov 25, 23:30, 2024)