dune-typetree  2.6-rc1
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  template<typename Node, typename Visitor>
39  static void apply(Node&& node, Visitor&& visitor)
40  {
41  ApplyToTree<tpType,NodeTag<Node>>::apply(std::forward<Node>(node),
42  std::forward<Visitor>(visitor),
43  TreePathFactory<tpType>::create(node).mutablePath());
44  }
45 
46  };
47 
48 
49  // Do not visit nodes the visitor is not interested in
50  template<TreePathType::Type tpType, typename NodeTag>
51  struct ApplyToTree<tpType,NodeTag,false>
52  {
53 
54  // we won't do anything with the objects, so having them all const
55  // works fine.
56  template<typename Node, typename Visitor, typename TreePath>
57  static void apply(const Node& node, const Visitor& visitor, TreePath treePath)
58  {}
59 
60  };
61 
62 
63 
64  // ********************************************************************************
65  // LeafNode
66  // ********************************************************************************
67 
68  // LeafNode - just call the leaf() callback
69  template<TreePathType::Type tpType>
70  struct ApplyToTree<tpType,LeafNodeTag,true>
71  {
72 
73  template<typename N, typename V, typename TreePath>
74  static void apply(N&& n, V&& v, TreePath tp)
75  {
76  v.leaf(std::forward<N>(n),tp.view());
77  }
78 
79  };
80 
81 
82 
83  // ********************************************************************************
84  // PowerNode
85  // ********************************************************************************
86 
87  // Traverse PowerNode statically - in this case, we simply use the
88  // generic child traversal algorithm
89  template<>
90  struct ApplyToTree<TreePathType::fullyStatic,PowerNodeTag,true>
91  : public ApplyToGenericCompositeNode
92  {
93  };
94 
95  // Traverse PowerNode dynamically. Here, we exploit the fact that is possible
96  // to do the child traversal using runtime iteration, as that saves a lot of
97  // template instantiations.
98  template<>
99  struct ApplyToTree<TreePathType::dynamic,PowerNodeTag,true>
100  {
101 
102  template<typename N, typename V, typename TreePath>
103  static void apply(N&& n, V&& v, TreePath tp)
104  {
105  // first encounter of this node
106  v.pre(std::forward<N>(n),tp.view());
107 
108  // strip types of possible references
109  typedef typename std::remove_reference<N>::type Node;
110  typedef typename std::remove_reference<V>::type Visitor;
111 
112  // get child type
113  typedef typename Node::template Child<0>::Type C;
114 
115  // Do we have to visit the children? As the TreePath is dynamic, it does not
116  // contain any information that could be evaluated at compile time, so we only
117  // have to query the visitor once.
118  const bool visit = Visitor::template VisitChild<Node,C,typename TreePath::ViewType>::value;
119 
120  // iterate over children
121  for (std::size_t k = 0; k < degree(n); ++k)
122  {
123  // always call beforeChild(), regardless of the value of visit
124  v.beforeChild(std::forward<N>(n),n.child(k),tp.view(),k);
125 
126  // update TreePath
127  tp.push_back(k);
128 
129  // descend to child
130  ApplyToTree<Visitor::treePathType,NodeTag<C>,visit>::apply(n.child(k),std::forward<V>(v),tp);
131 
132  // restore TreePath
133  tp.pop_back();
134 
135  // always call afterChild(), regardless of the value of visit
136  v.afterChild(std::forward<N>(n),n.child(k),tp.view(),k);
137 
138  // if this is not the last child, call infix callback
139  if (k < degree(n) - 1)
140  v.in(std::forward<N>(n),tp.view());
141  }
142 
143  // node is done - call postfix callback
144  v.post(std::forward<N>(n),tp.view());
145  }
146 
147  };
148 
149 
150 
151  // ********************************************************************************
152  // CompositeNode
153  // ********************************************************************************
154 
155  // Traverse CompositeNode - just forward to the generic algorithm
156  template<TreePathType::Type treePathType>
157  struct ApplyToTree<treePathType,CompositeNodeTag,true>
158  : public ApplyToGenericCompositeNode
159  {
160  };
161 
162 #endif // DOXYGEN
163 
164  namespace Detail {
165 
166  template<class PreFunc, class LeafFunc, class PostFunc>
168  public TypeTree::TreeVisitor,
170  {
171  public:
172  CallbackVisitor(PreFunc& preFunc, LeafFunc& leafFunc, PostFunc& postFunc) :
173  preFunc_(preFunc),
174  leafFunc_(leafFunc),
175  postFunc_(postFunc)
176  {}
177 
178  template<typename Node, typename TreePath>
179  void pre(Node&& node, TreePath treePath)
180  {
181  preFunc_(node, treePath);
182  }
183 
184  template<typename Node, typename TreePath>
185  void leaf(Node&& node, TreePath treePath)
186  {
187  leafFunc_(node, treePath);
188  }
189 
190  template<typename Node, typename TreePath>
191  void post(Node&& node, TreePath treePath)
192  {
193  postFunc_(node, treePath);
194  }
195 
196  private:
197  PreFunc& preFunc_;
198  LeafFunc& leafFunc_;
199  PostFunc& postFunc_;
200  };
201 
202  template<class PreFunc, class LeafFunc, class PostFunc>
203  auto callbackVisitor(PreFunc& preFunc, LeafFunc& leafFunc, PostFunc& postFunc)
204  {
205  return CallbackVisitor<PreFunc, LeafFunc, PostFunc>(preFunc, leafFunc, postFunc);
206  }
207 
208  } // namespace Detail
209 
210 
211  // ********************************************************************************
212  // Public Interface
213  // ********************************************************************************
214 
216 
230  template<typename Tree, typename Visitor>
231  void applyToTree(Tree&& tree, Visitor&& visitor)
232  {
234  std::forward<Visitor>(visitor));
235  }
236 
248  template<class Tree, class PreFunc, class LeafFunc, class PostFunc>
249  void forEachNode(Tree&& tree, PreFunc&& preFunc, LeafFunc&& leafFunc, PostFunc&& postFunc)
250  {
251  applyToTree(tree, Detail::callbackVisitor(preFunc, leafFunc, postFunc));
252  }
253 
264  template<class Tree, class InnerFunc, class LeafFunc>
265  void forEachNode(Tree&& tree, InnerFunc&& innerFunc, LeafFunc&& leafFunc)
266  {
267  auto nop = [](auto&&... args) {};
268  forEachNode(tree, innerFunc, leafFunc, nop);
269  }
270 
280  template<class Tree, class NodeFunc>
281  void forEachNode(Tree&& tree, NodeFunc&& nodeFunc)
282  {
283  forEachNode(tree, nodeFunc, nodeFunc);
284  }
285 
295  template<class Tree, class LeafFunc>
296  void forEachLeafNode(Tree&& tree, LeafFunc&& leafFunc)
297  {
298  auto nop = [](auto&&... args) {};
299  forEachNode(tree, nop, leafFunc, nop);
300  }
301 
303 
304  } // namespace TypeTree
305 } //namespace Dune
306 
307 #endif // DUNE_TYPETREE_TRAVERSAL_HH
Definition: treepath.hh:26
static const TreePathType::Type treePathType
Definition: traversalutilities.hh:30
void pre(Node &&node, TreePath treePath)
Definition: traversal.hh:179
Convenience base class for visiting the entire tree.
Definition: visitor.hh:330
Type
Definition: treepath.hh:26
Definition: accumulate_static.hh:13
void forEachNode(Tree &&tree, PreFunc &&preFunc, LeafFunc &&leafFunc, PostFunc &&postFunc)
Traverse tree and visit each node.
Definition: traversal.hh:249
void leaf(Node &&node, TreePath treePath)
Definition: traversal.hh:185
void applyToTree(Tree &&tree, Visitor &&visitor)
Apply visitor to TypeTree.
Definition: traversal.hh:231
std::size_t degree(const Node &node)
Returns the degree of node as run time information.
Definition: nodeinterface.hh:71
auto callbackVisitor(PreFunc &preFunc, LeafFunc &leafFunc, PostFunc &postFunc)
Definition: traversal.hh:203
CallbackVisitor(PreFunc &preFunc, LeafFunc &leafFunc, PostFunc &postFunc)
Definition: traversal.hh:172
void forEachLeafNode(Tree &&tree, LeafFunc &&leafFunc)
Traverse tree and visit each leaf node.
Definition: traversal.hh:296
Definition: traversal.hh:167
typename std::decay_t< Node >::NodeTag NodeTag
Returns the node tag of the given Node.
Definition: nodeinterface.hh:62
Mixin base class for visitors that only need a dynamic TreePath during traversal. ...
Definition: visitor.hh:323
Definition: treepath.hh:30
void post(Node &&node, TreePath treePath)
Definition: traversal.hh:191