"Fossies" - the Fresh Open Source Software Archive 
Member "dune-typetree-2.8.0/dune/typetree/traversal.hh" (31 Aug 2021, 12440 Bytes) of package /linux/misc/dune/dune-typetree-2.8.0.tar.gz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
For more information about "traversal.hh" see the
Fossies "Dox" file reference documentation.
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
17 namespace Dune {
18 namespace TypeTree {
19
20 /** \addtogroup Tree Traversal
21 * \ingroup TypeTree
22 * \{
23 */
24
25 #ifndef DOXYGEN
26 /// A functor with no operation
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
202 /**
203 * \brief Create tuple of tree paths to leafs
204 *
205 * This creates a tuple of HybridTreePath objects refering to the
206 * leaf nodes in the tree. The generated tree paths are always
207 * HybridTreePath instances. If pathType is TreePathType::dynamic
208 * then path entries for power nodes are of type std::size_t.
209 * For all other nodes and if pathType is not TreePathType::dynamic,
210 * the entries are instances of Dune::index_constant.
211 *
212 * \tparam Tree Type of tree to generate tree paths for
213 * \tparam pathType Type of paths to generate
214 */
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
221 //! Apply visitor to TypeTree.
222 /**
223 * \code
224 #include <dune/typetree/traversal.hh>
225 * \endcode
226 * This function applies the given visitor to the given tree. Both visitor and tree may be const
227 * or non-const (if the compiler supports rvalue references, they may even be a non-const temporary).
228 *
229 * \note The visitor must implement the interface laid out by DefaultVisitor (most easily achieved by
230 * inheriting from it) and specify the required type of tree traversal (static or dynamic) by
231 * inheriting from either StaticTraversal or DynamicTraversal.
232 *
233 * \param tree The tree the visitor will be applied to.
234 * \param visitor The visitor to apply to the tree.
235 */
236 template<typename Tree, typename Visitor>
237 void applyToTree(Tree&& tree, Visitor&& visitor)
238 {
239 Detail::applyToTree(tree, hybridTreePath(), visitor);
240 }
241
242 /**
243 * \brief Traverse tree and visit each node
244 *
245 * All passed callback functions are called with the
246 * node and corresponding treepath as arguments.
247 *
248 * \param tree The tree to traverse
249 * \param preFunc This function is called for each inner node before visiting its children
250 * \param leafFunc This function is called for each leaf node
251 * \param postFunc This function is called for each inner node after visiting its children
252 *
253 * \deprecated Use the more general \ref applyToTree instead.
254 */
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
261 /**
262 * \brief Traverse tree and visit each node
263 *
264 * All passed callback functions are called with the
265 * node and corresponding treepath as arguments.
266 *
267 * \param tree The tree to traverse
268 * \param innerFunc This function is called for each inner node before visiting its children
269 * \param leafFunc This function is called for each leaf node
270 *
271 * \deprecated Use the more general \ref applyToTree instead.
272 */
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
279 /**
280 * \brief Traverse tree and visit each node
281 *
282 * The passed callback function is called with the
283 * node and corresponding treepath as arguments.
284 *
285 * \param tree The tree to traverse
286 * \param nodeFunc This function is called for each node
287 */
288 template<class Tree, class NodeFunc>
289 void forEachNode(Tree&& tree, NodeFunc&& nodeFunc)
290 {
291 Detail::forEachNode(tree, hybridTreePath(), nodeFunc, nodeFunc, NoOp{});
292 }
293
294 /**
295 * \brief Traverse tree and visit each leaf node
296 *
297 * The passed callback function is called with the
298 * node and corresponding treepath as arguments.
299 *
300 * \param tree The tree to traverse
301 * \param leafFunc This function is called for each leaf node
302 */
303 template<class Tree, class LeafFunc>
304 void forEachLeafNode(Tree&& tree, LeafFunc&& leafFunc)
305 {
306 Detail::forEachNode(tree, hybridTreePath(), NoOp{}, leafFunc, NoOp{});
307 }
308
309 //! \} group Tree Traversal
310
311 } // namespace TypeTree
312 } //namespace Dune
313
314 #endif // DUNE_TYPETREE_TRAVERSAL_HH