dune-typetree  2.5.0
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 
165 
166  // ********************************************************************************
167  // Public Interface
168  // ********************************************************************************
169 
171 
185  template<typename Tree, typename Visitor>
186  void applyToTree(Tree&& tree, Visitor&& visitor)
187  {
189  std::forward<Visitor>(visitor));
190  }
191 
193 
194  } // namespace TypeTree
195 } //namespace Dune
196 
197 #endif // DUNE_TYPETREE_TRAVERSAL_HH
static const TreePathType::Type treePathType
Definition: traversalutilities.hh:30
Definition: accumulate_static.hh:13
void applyToTree(Tree &&tree, Visitor &&visitor)
Apply visitor to TypeTree.
Definition: traversal.hh:186
std::size_t degree(const Node &node)
Returns the degree of node as run time information.
Definition: nodeinterface.hh:71
Definition: treepath.hh:26
typename std::decay_t< Node >::NodeTag NodeTag
Returns the node tag of the given Node.
Definition: nodeinterface.hh:62
Type
Definition: treepath.hh:26