dune-typetree  2.9
traversal.hh
Go to the documentation of this file.
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 
15 #include <dune/typetree/visitor.hh>
16 
17 namespace 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
void forEachNode(Tree &&tree, PreFunc &&preFunc, LeafFunc &&leafFunc, PostFunc &&postFunc)
Traverse tree and visit each node.
Definition: traversal.hh:256
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
std::size_t degree(const Node &node)
Returns the degree of node as run time information.
Definition: nodeinterface.hh:85
constexpr HybridTreePath< T... > treePath(const T &... t)
Constructs a new HybridTreePath from the given indices.
Definition: treepath.hh:191
constexpr HybridTreePath< T... > hybridTreePath(const T &... t)
Constructs a new HybridTreePath from the given indices.
Definition: treepath.hh:180
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:281
HybridTreePath< Dune::index_constant< i >... > TreePath
Definition: treepath.hh:521
Definition: accumulate_static.hh:13
void forEachNode(T &&tree, TreePath treePath, PreFunc &&preFunc, LeafFunc &&leafFunc, PostFunc &&postFunc)
Definition: traversal.hh:162
decltype((std::declval< Tree >().degree(), std::declval< Tree >().child(0u))) DynamicTraversalConcept
Definition: traversal.hh:41
decltype((std::integral_constant< std::size_t, Tree::degree()>{})) StaticTraversalConcept
Definition: traversal.hh:47
void applyToTree(T &&tree, TreePath treePath, V &&visitor)
Definition: traversal.hh:95
constexpr auto leafTreePathTuple(Prefix prefix)
Definition: traversal.hh:52
Type
Definition: treepath.hh:30
@ dynamic
Definition: treepath.hh:30
A hybrid version of TreePath that supports both compile time and run time indices.
Definition: treepath.hh:79