dune-typetree  2.3.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 
13 #include <dune/typetree/visitor.hh>
15 
16 namespace Dune {
17  namespace TypeTree {
18 
25 #ifndef DOXYGEN // these are all internals and not public API. Only access is using applyToTree().
26 
27 
28  // This struct is the core of the algorithm. While this specialization simply serves as the starting point
29  // of the traversal and takes care of some setup work, the struct has to be specialized for each TreeType node type it
30  // should support.
31  // The first parameter specifies the kind of TreePath (dynamic/static) to use, the second one is the tag of the node type
32  // and the third one must always be specialized as true, as a value of false means the node should in fact not be visited.
33  // That case is already handled by a specialization of the struct.
34  template<TreePathType::Type tpType, bool doApply>
35  struct ApplyToTree<tpType,StartTag,doApply>
36  {
37 
38 #if HAVE_RVALUE_REFERENCES
39 
40  template<typename Node, typename Visitor>
41  static void apply(Node&& node, Visitor&& visitor)
42  {
43  ApplyToTree<tpType,typename remove_reference<Node>::type::NodeTag>::apply(std::forward<Node>(node),
44  std::forward<Visitor>(visitor),
45  TreePathFactory<tpType>::create(node).mutablePath());
46  }
47 
48 #else
49 
50  template<typename Node, typename Visitor>
51  static void apply(Node& node, Visitor& visitor)
52  {
53  ApplyToTree<tpType,typename Node::NodeTag>::apply(node,visitor,TreePathFactory<tpType>::create(node).mutablePath());
54  }
55 
56  template<typename Node, typename Visitor>
57  static void apply(const Node& node, Visitor& visitor)
58  {
59  ApplyToTree<tpType,typename Node::NodeTag>::apply(node,visitor,TreePathFactory<tpType>::create(node).mutablePath());
60  }
61 
62  template<typename Node, typename Visitor>
63  static void apply(Node& node, const Visitor& visitor)
64  {
65  ApplyToTree<tpType,typename Node::NodeTag>::apply(node,visitor,TreePathFactory<tpType>::create(node).mutablePath());
66  }
67 
68  template<typename Node, typename Visitor>
69  static void apply(const Node& node, const Visitor& visitor)
70  {
71  ApplyToTree<tpType,typename Node::NodeTag>::apply(node,visitor,TreePathFactory<tpType>::create(node).mutablePath());
72  }
73 
74 #endif // HAVE_RVALUE_REFERENCES
75 
76  };
77 
78 
79  // Do not visit nodes the visitor is not interested in
80  template<TreePathType::Type tpType, typename NodeTag>
81  struct ApplyToTree<tpType,NodeTag,false>
82  {
83 
84  // we won't do anything with the objects, so having them all const
85  // works fine.
86  template<typename Node, typename Visitor, typename TreePath>
87  static void apply(const Node& node, const Visitor& visitor, TreePath treePath)
88  {}
89 
90  };
91 
92 
93 
94  // ********************************************************************************
95  // LeafNode
96  // ********************************************************************************
97 
98  // LeafNode - just call the leaf() callback
99  template<TreePathType::Type tpType>
100  struct ApplyToTree<tpType,LeafNodeTag,true>
101  {
102 
103 #if HAVE_RVALUE_REFERENCES
104 
105  template<typename N, typename V, typename TreePath>
106  static void apply(N&& n, V&& v, TreePath tp)
107  {
108  v.leaf(std::forward<N>(n),tp.view());
109  }
110 
111 #else
112 
113  template<typename N, typename V, typename TreePath>
114  static void apply(N& n, V& v, TreePath tp)
115  {
116  v.leaf(n,tp.view());
117  }
118 
119  template<typename N, typename V, typename TreePath>
120  static void apply(const N& n, V& v, TreePath tp)
121  {
122  v.leaf(n,tp.view());
123  }
124 
125  template<typename N, typename V, typename TreePath>
126  static void apply(N& n, const V& v, TreePath tp)
127  {
128  v.leaf(n,tp.view());
129  }
130 
131  template<typename N, typename V, typename TreePath>
132  static void apply(const N& n, const V& v, TreePath tp)
133  {
134  v.leaf(n,tp.view());
135  }
136 
137 #endif // HAVE_RVALUE_REFERENCES
138 
139  };
140 
141 
142 
143  // ********************************************************************************
144  // PowerNode
145  // ********************************************************************************
146 
147  // Traverse PowerNode statically - in this case, we simply use the
148  // generic child traversal algorithm
149  template<>
150  struct ApplyToTree<TreePathType::fullyStatic,PowerNodeTag,true>
151  : public ApplyToGenericCompositeNode
152  {
153  };
154 
155  // Traverse PowerNode dynamically. Here, we exploit the fact that is possible
156  // to do the child traversal using runtime iteration, as that saves a lot of
157  // template instantiations.
158  template<>
159  struct ApplyToTree<TreePathType::dynamic,PowerNodeTag,true>
160  {
161 
162 #if HAVE_RVALUE_REFERENCES
163 
164  template<typename N, typename V, typename TreePath>
165  static void apply(N&& n, V&& v, TreePath tp)
166  {
167  // first encounter of this node
168  v.pre(std::forward<N>(n),tp.view());
169 
170  // strip types of possible references
171  typedef typename remove_reference<N>::type Node;
172  typedef typename remove_reference<V>::type Visitor;
173 
174  // get child type
175  typedef typename Node::template Child<0>::Type C;
176 
177  // Do we have to visit the children? As the TreePath is dynamic, it does not
178  // contain any information that could be evaluated at compile time, so we only
179  // have to query the visitor once.
180  const bool visit = Visitor::template VisitChild<Node,C,typename TreePath::ViewType>::value;
181 
182  // iterate over children
183  for (std::size_t k = 0; k < Node::CHILDREN; ++k)
184  {
185  // always call beforeChild(), regardless of the value of visit
186  v.beforeChild(std::forward<N>(n),n.child(k),tp.view(),k);
187 
188  // update TreePath
189  tp.push_back(k);
190 
191  // descend to child
192  ApplyToTree<Visitor::treePathType,typename C::NodeTag,visit>::apply(n.child(k),std::forward<V>(v),tp);
193 
194  // restore TreePath
195  tp.pop_back();
196 
197  // always call afterChild(), regardless of the value of visit
198  v.afterChild(std::forward<N>(n),n.child(k),tp.view(),k);
199 
200  // if this is not the last child, call infix callback
201  if (k < Node::CHILDREN-1)
202  v.in(std::forward<N>(n),tp.view());
203  }
204 
205  // node is done - call postfix callback
206  v.post(std::forward<N>(n),tp.view());
207  }
208 
209 #else
210 
211  // non-const node, non-const visitor
212  template<typename N, typename V, typename TreePath>
213  static void apply(N& n, V& v, TreePath tp)
214  {
215  v.pre(n,tp.view());
216  typedef typename N::template Child<0>::Type C;
217  const bool visit = V::template VisitChild<N,C,typename TreePath::ViewType>::value;
218  for (std::size_t k = 0; k < N::CHILDREN; ++k)
219  {
220  v.beforeChild(n,n.child(k),tp.view(),k);
221  tp.push_back(k);
222  ApplyToTree<V::treePathType,typename C::NodeTag,visit>::apply(n.child(k),v,tp);
223  tp.pop_back();
224  v.afterChild(n,n.child(k),tp.view(),k);
225  if (k < N::CHILDREN-1)
226  v.in(n,tp.view());
227  }
228  v.post(n,tp.view());
229  }
230 
231  // const node, non-const visitor
232  template<typename N, typename V, typename TreePath>
233  static void apply(const N& n, V& v, TreePath tp)
234  {
235  v.pre(n,tp.view());
236  typedef typename N::template Child<0>::Type C;
237  const bool visit = V::template VisitChild<N,C,typename TreePath::ViewType>::value;
238  for (std::size_t k = 0; k < N::CHILDREN; ++k)
239  {
240  v.beforeChild(n,n.child(k),tp.view(),k);
241  tp.push_back(k);
242  ApplyToTree<V::treePathType,typename C::NodeTag,visit>::apply(n.child(k),v,tp);
243  tp.pop_back();
244  v.afterChild(n,n.child(k),tp.view(),k);
245  if (k < N::CHILDREN-1)
246  v.in(n,tp.view());
247  }
248  v.post(n,tp.view());
249  }
250 
251  // non-const node, const visitor
252  template<typename N, typename V, typename TreePath>
253  static void apply(N& n, const V& v, TreePath tp)
254  {
255  v.pre(n,tp.view());
256  typedef typename N::template Child<0>::Type C;
257  const bool visit = V::template VisitChild<N,C,typename TreePath::ViewType>::value;
258  for (std::size_t k = 0; k < N::CHILDREN; ++k)
259  {
260  v.beforeChild(n,n.child(k),tp.view(),k);
261  tp.push_back(k);
262  ApplyToTree<V::treePathType,typename C::NodeTag,visit>::apply(n.child(k),v,tp);
263  tp.pop_back();
264  v.afterChild(n,n.child(k),tp.view(),k);
265  if (k < N::CHILDREN-1)
266  v.in(n,tp.view());
267  }
268  v.post(n,tp.view());
269  }
270 
271  // const node, const visitor
272  template<typename N, typename V, typename TreePath>
273  static void apply(const N& n, const V& v, TreePath tp)
274  {
275  v.pre(n,tp.view());
276  typedef typename N::template Child<0>::Type C;
277  const bool visit = V::template VisitChild<N,C,typename TreePath::ViewType>::value;
278  for (std::size_t k = 0; k < N::CHILDREN; ++k)
279  {
280  v.beforeChild(n,n.child(k),tp.view(),k);
281  tp.push_back(k);
282  ApplyToTree<V::treePathType,typename C::NodeTag,visit>::apply(n.child(k),v,tp);
283  tp.pop_back();
284  v.afterChild(n,n.child(k),tp.view(),k);
285  if (k < N::CHILDREN-1)
286  v.in(n,tp.view());
287  }
288  v.post(n,tp.view());
289  }
290 
291 #endif // HAVE_RVALUE_REFERENCES
292 
293  };
294 
295 
296 
297  // ********************************************************************************
298  // CompositeNode, VariadicCompositeNode
299  // ********************************************************************************
300 
301  // Traverse CompositeNode - just forward to the generic algorithm
302  template<TreePathType::Type treePathType>
303  struct ApplyToTree<treePathType,CompositeNodeTag,true>
304  : public ApplyToGenericCompositeNode
305  {
306  };
307 
308 
309  // Traverse VariadicCompositeNode - just forward to the generic algorithm
310  template<TreePathType::Type treePathType>
311  struct ApplyToTree<treePathType,VariadicCompositeNodeTag,true>
312  : public ApplyToGenericCompositeNode
313  {
314  };
315 
316 #endif // DOXYGEN
317 
318 
319 
320  // ********************************************************************************
321  // Public Interface
322  // ********************************************************************************
323 
324 #if HAVE_RVALUE_REFERENCES || DOXYGEN
325 
327 
341  template<typename Tree, typename Visitor>
342  void applyToTree(Tree&& tree, Visitor&& visitor)
343  {
345  std::forward<Visitor>(visitor));
346  }
347 
348 #else
349 
350  template<typename Tree, typename Visitor>
351  void applyToTree(Tree& tree, Visitor& visitor)
352  {
353  ApplyToTree<Visitor::treePathType>::apply(tree,visitor);
354  }
355 
356  template<typename Tree, typename Visitor>
357  void applyToTree(const Tree& tree, Visitor& visitor)
358  {
359  ApplyToTree<Visitor::treePathType>::apply(tree,visitor);
360  }
361 
362  template<typename Tree, typename Visitor>
363  void applyToTree(Tree& tree, const Visitor& visitor)
364  {
365  ApplyToTree<Visitor::treePathType>::apply(tree,visitor);
366  }
367 
368  template<typename Tree, typename Visitor>
369  void applyToTree(const Tree& tree, const Visitor& visitor)
370  {
371  ApplyToTree<Visitor::treePathType>::apply(tree,visitor);
372  }
373 
374 #endif // HAVE_RVALUE_REFERENCES || DOXYGEN
375 
377 
378  } // namespace TypeTree
379 } //namespace Dune
380 
381 #endif // DUNE_TYPETREE_TRAVERSAL_HH
Definition: treepath.hh:26
static const TreePathType::Type treePathType
Definition: traversalutilities.hh:30
void applyToTree(Tree &&tree, Visitor &&visitor)
Apply visitor to TypeTree.
Definition: traversal.hh:342
static const std::size_t value
Definition: compositenode.hh:38
Type
Definition: treepath.hh:26