dune-typetree  2.7.1
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 #if HAVE_RVALUE_REFERENCES
8 #include <utility>
9 #endif
10 
11 #include <dune/common/std/type_traits.hh>
12 #include <dune/common/std/utility.hh>
13 #include <dune/common/std/type_traits.hh>
14 #include <dune/common/hybridutilities.hh>
15 
19 #include <dune/typetree/visitor.hh>
20 
21 namespace Dune {
22  namespace TypeTree {
23 
30  namespace Detail {
31 
32  // This is a constexpr version of the ternery operator c?t1:t1.
33  // In contrast to the latter the type of t1 and t2 can be different.
34  // Notice that std::conditional would not do the trick, because
35  // it only selects between types.
36  template<bool c, class T1, class T2,
37  std::enable_if_t<c, int> = 0>
38  constexpr auto conditionalValue(T1&& t1, T2&& t2) {
39  return std::forward<T1>(t1);
40  }
41 
42  template<bool c, class T1, class T2,
43  std::enable_if_t<not c, int> = 0>
44  constexpr auto conditionalValue(T1&& t1, T2&& t2) {
45  return std::forward<T2>(t2);
46  }
47 
48  template<class Tree, TreePathType::Type pathType, class Prefix,
49  std::enable_if_t<Tree::isLeaf, int> = 0>
50  constexpr auto leafTreePathTuple(Prefix prefix)
51  {
52  return std::make_tuple(prefix);
53  }
54 
55  template<class Tree, TreePathType::Type pathType, class Prefix,
56  std::enable_if_t<not Tree::isLeaf, int> = 0>
57  constexpr auto leafTreePathTuple(Prefix prefix);
58 
59  template<class Tree, TreePathType::Type pathType, class Prefix, std::size_t... indices,
60  std::enable_if_t<(Tree::isComposite or (Tree::isPower and (pathType!=TreePathType::dynamic))), int> = 0>
61  constexpr auto leafTreePathTuple(Prefix prefix, Std::index_sequence<indices...>)
62  {
63  return std::tuple_cat(Detail::leafTreePathTuple<TypeTree::Child<Tree,indices>, pathType>(Dune::TypeTree::push_back(prefix, Dune::index_constant<indices>{}))...);
64  }
65 
66  template<class Tree, TreePathType::Type pathType, class Prefix, std::size_t... indices,
67  std::enable_if_t<(Tree::isPower and (pathType==TreePathType::dynamic)), int> = 0>
68  constexpr auto leafTreePathTuple(Prefix prefix, Std::index_sequence<indices...>)
69  {
70  return std::tuple_cat(Detail::leafTreePathTuple<TypeTree::Child<Tree,indices>, pathType>(Dune::TypeTree::push_back(prefix, indices))...);
71  }
72 
73  template<class Tree, TreePathType::Type pathType, class Prefix,
74  std::enable_if_t<not Tree::isLeaf, int>>
75  constexpr auto leafTreePathTuple(Prefix prefix)
76  {
77  return Detail::leafTreePathTuple<Tree, pathType>(prefix, Dune::Std::make_index_sequence<Tree::degree()>{});
78  }
79 
80  /* The signature is the same as for the public applyToTree
81  * function in Dune::Typetree, despite the additionally passed
82  * treePath argument. The path passed here is associated to
83  * the tree and the relative paths of the children (wrt. to tree)
84  * are appended to this. Hence the behavior of the public function
85  * is resembled by passing an empty treePath.
86  */
87 
88  /*
89  * This is the overload for leaf traversal
90  */
91  template<class T, class TreePath, class V,
92  std::enable_if_t<std::decay_t<T>::isLeaf, int> = 0>
93  void applyToTree(T&& tree, TreePath treePath, V&& visitor)
94  {
95  visitor.leaf(tree, treePath);
96  }
97 
98  /*
99  * This is the general overload doing child traversal.
100  */
101  template<class T, class TreePath, class V,
102  std::enable_if_t<not std::decay_t<T>::isLeaf, int> = 0>
103  void applyToTree(T&& tree, TreePath treePath, V&& visitor)
104  {
105  // Do we really want to take care for const-ness of the Tree
106  // when instantiating VisitChild below? I'd rather expect this:
107  // using Tree = std::decay_t<T>;
108  // using Visitor = std::decay_t<V>;
109  using Tree = std::remove_reference_t<T>;
110  using Visitor = std::remove_reference_t<V>;
111  visitor.pre(tree, treePath);
112 
113  // Use statically encoded degree unless tree
114  // is a power node and dynamic traversal is requested.
115  constexpr auto useDynamicTraversal = (Tree::isPower and Visitor::treePathType==TreePathType::dynamic);
116  auto degree = conditionalValue<useDynamicTraversal>(Tree::degree(), Dune::index_constant<Tree::degree()>{});
117 
118  auto indices = Dune::range(degree);
119  Dune::Hybrid::forEach(indices, [&](auto i) {
120  auto childTreePath = Dune::TypeTree::push_back(treePath, i);
121  auto&& child = tree.child(i);
122  using Child = std::decay_t<decltype(child)>;
123 
124  visitor.beforeChild(tree, child, treePath, i);
125 
126  // This requires that visiotor.in(...) can always be instantiated,
127  // even if there's a single child only.
128  if (i>0)
129  visitor.in(tree, treePath);
130  static const auto visitChild = Visitor::template VisitChild<Tree,Child,TreePath>::value;
131  Dune::Hybrid::ifElse(Dune::Std::bool_constant<visitChild>{}, [&] (auto id) {
132  applyToTree(child, childTreePath, visitor);
133  });
134 
135  visitor.afterChild(tree, child, treePath, i);
136  });
137  visitor.post(tree, treePath);
138  }
139 
140 
141 
142  /* Traverse tree and visit each node. The signature is the same
143  * as for the public forEachNode function in Dune::Typtree,
144  * despite the additionally passed treePath argument. The path
145  * passed here is associated to the tree and the relative
146  * paths of the children (wrt. to tree) are appended to this.
147  * Hence the behavior of the public function is resembled
148  * by passing an empty treePath.
149  */
150  template<class Tree, class TreePath, class PreFunc, class LeafFunc, class PostFunc>
151  void forEachNode(Tree&& tree, TreePath treePath, PreFunc&& preFunc, LeafFunc&& leafFunc, PostFunc&& postFunc)
152  {
153  using TreeType = std::decay_t<Tree>;
154  Dune::Hybrid::ifElse(Dune::Std::bool_constant<TreeType::isLeaf>{}, [&] (auto id) {
155  // If we have a leaf tree just visit it using the leaf function.
156  leafFunc(id(tree), treePath);
157  }, [&] (auto id) {
158  // Otherwise visit the tree with the pre function,
159  // visit all children using a static loop, and
160  // finally visit the tree with the post function.
161  preFunc(id(tree), treePath);
162  auto indices = Dune::Std::make_index_sequence<TreeType::degree()>{};
163  Dune::Hybrid::forEach(indices, [&](auto i) {
164  auto childTreePath = Dune::TypeTree::push_back(treePath, i);
165  forEachNode(id(tree).child(i), childTreePath, preFunc, leafFunc, postFunc);
166  });
167  postFunc(id(tree), treePath);
168  });
169  }
170 
171  } // namespace Detail
172 
173 
174  // ********************************************************************************
175  // Public Interface
176  // ********************************************************************************
177 
191  template<class Tree, TreePathType::Type pathType=TreePathType::dynamic>
192  constexpr auto leafTreePathTuple()
193  {
194  return Detail::leafTreePathTuple<std::decay_t<Tree>, pathType>(hybridTreePath());
195  }
196 
198 
212  template<typename Tree, typename Visitor>
213  void applyToTree(Tree&& tree, Visitor&& visitor)
214  {
215  Detail::applyToTree(tree, hybridTreePath(), visitor);
216  }
217 
229  template<class Tree, class PreFunc, class LeafFunc, class PostFunc>
230  void forEachNode(Tree&& tree, PreFunc&& preFunc, LeafFunc&& leafFunc, PostFunc&& postFunc)
231  {
232  Detail::forEachNode(tree, hybridTreePath(), preFunc, leafFunc, postFunc);
233  }
234 
245  template<class Tree, class InnerFunc, class LeafFunc>
246  void forEachNode(Tree&& tree, InnerFunc&& innerFunc, LeafFunc&& leafFunc)
247  {
248  auto nop = [](auto&&... args) {};
249  forEachNode(tree, innerFunc, leafFunc, nop);
250  }
251 
261  template<class Tree, class NodeFunc>
262  void forEachNode(Tree&& tree, NodeFunc&& nodeFunc)
263  {
264  forEachNode(tree, nodeFunc, nodeFunc);
265  }
266 
276  template<class Tree, class LeafFunc>
277  void forEachLeafNode(Tree&& tree, LeafFunc&& leafFunc)
278  {
279  auto nop = [](auto&&... args) {};
280  forEachNode(tree, nop, leafFunc, nop);
281  }
282 
284 
285  } // namespace TypeTree
286 } //namespace Dune
287 
288 #endif // DUNE_TYPETREE_TRAVERSAL_HH
static const TreePathType::Type treePathType
Definition: traversalutilities.hh:30
void forEachNode(Tree &&tree, PreFunc &&preFunc, LeafFunc &&leafFunc, PostFunc &&postFunc)
Traverse tree and visit each node.
Definition: traversal.hh:230
constexpr auto leafTreePathTuple()
Create tuple of tree paths to leafs.
Definition: traversal.hh:192
void forEachLeafNode(Tree &&tree, LeafFunc &&leafFunc)
Traverse tree and visit each leaf node.
Definition: traversal.hh:277
void applyToTree(Tree &&tree, Visitor &&visitor)
Apply visitor to TypeTree.
Definition: traversal.hh:213
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:276
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:179
std::size_t degree(const Node &node)
Returns the degree of node as run time information.
Definition: nodeinterface.hh:71
constexpr HybridTreePath< T... > treePath(const T &... t)
Constructs a new HybridTreePath from the given indices.
Definition: treepath.hh:188
constexpr HybridTreePath< T... > hybridTreePath(const T &... t)
Constructs a new HybridTreePath from the given indices.
Definition: treepath.hh:177
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
HybridTreePath< Dune::index_constant< i >... > TreePath
Definition: treepath.hh:433
Definition: accumulate_static.hh:13
void forEachNode(Tree &&tree, TreePath treePath, PreFunc &&preFunc, LeafFunc &&leafFunc, PostFunc &&postFunc)
Definition: traversal.hh:151
void applyToTree(T &&tree, TreePath treePath, V &&visitor)
Definition: traversal.hh:93
constexpr auto conditionalValue(T1 &&t1, T2 &&t2)
Definition: traversal.hh:38
constexpr auto leafTreePathTuple(Prefix prefix)
Definition: traversal.hh:50
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