dune-typetree 3.0-dev
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
15
16namespace 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 {
188 ApplyToTree<std::remove_reference<Visitor>::type::treePathType>::apply(std::forward<Tree>(tree),
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
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
typename std::decay_t< Node >::NodeTag NodeTag
Returns the node tag of the given Node.
Definition nodeinterface.hh:62
Definition accumulate_static.hh:13
@ fullyStatic
Definition treepath.hh:26
@ dynamic
Definition treepath.hh:26