Traversal.hpp 9.23 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
// -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
// vi: set et ts=4 sw=2 sts=2:

#ifndef DUNE_TYPETREE_TRAVERSAL_HYBRID_HH
#define DUNE_TYPETREE_TRAVERSAL_HYBRID_HH

#include <dune/typetree/nodetags.hh>
#include <dune/typetree/treepath.hh>
#include <dune/typetree/visitor.hh>

namespace Dune {
  namespace TypeTree {

    /** \addtogroup Tree Traversal
     *  \ingroup TypeTree
     *  \{
     */


#ifndef DOXYGEN // these are all internals and not public API. Only access is using applyToTree().

    // forward declaration of main engine struct
    template <typename tag = StartTag, bool doApply = true>
    struct TraverseTree;

    // This struct is the core of the algorithm. While this specialization simply serves as the starting point
    // of the traversal and takes care of some setup work, the struct has to be specialized for each TreeType node type it
    // should support.
    // The first parameter is the tag of the node type
    // and the second one must always be specialized as true, as a value of false means the node should in fact not be visited.
    // That case is already handled by a specialization of the struct.
    template <bool doApply>
    struct TraverseTree<StartTag, doApply>
    {

      template <typename Node, typename Visitor>
      static void apply(Node&& node, Visitor&& visitor)
      {
        TraverseTree<NodeTag<Node>>::apply(std::forward<Node>(node),
                                           std::forward<Visitor>(visitor),
                                           hybridTreePath());
      }

    };


    // Do not visit nodes the visitor is not interested in
    template <typename NodeTag>
    struct TraverseTree<NodeTag, false>
    {
      // we won't do anything with the objects, so having them all const
      // works fine.
      template <typename Node, typename Visitor, typename TreePath>
      static void apply(const Node& node, const Visitor& visitor, TreePath treePath)
      {}
    };



    // ********************************************************************************
    // LeafNode
    // ********************************************************************************

    // LeafNode - just call the leaf() callback
    template <>
    struct TraverseTree<LeafNodeTag, true>
    {
      template <typename N, typename V, typename TreePath>
      static void apply(N&& n, V&& v, TreePath tp)
      {
        v.leaf(std::forward<N>(n),tp);
      }
    };


    // ********************************************************************************
    // PwerNode
    // ********************************************************************************

    template <>
    struct TraverseTree<PowerNodeTag, true>
    {
      template <typename N, typename V, typename TreePath>
      static void apply(N&& n, V&& v, TreePath tp)
      {
        v.pre(std::forward<N>(n),tp);

        typedef typename std::remove_reference<N>::type Node;
        typedef typename std::remove_reference<V>::type Visitor;

        // get child type
        typedef typename Node::template Child<0>::Type C;

        // Do we have to visit the children? As the TreePath is dynamic, it does not
        // contain any information that could be evaluated at compile time, so we only
        // have to query the visitor once.
97
        const bool visit = Visitor::template VisitChild<Node,C,TreePath>::value;
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

        auto child_tp = push_back(tp, std::size_t(0));
        static const std::size_t last = treePathSize(tp);

        // iterate over children
        for (std::size_t k = 0; k < degree(n); ++k)
        {
          // always call beforeChild(), regardless of the value of visit
          v.beforeChild(std::forward<N>(n),n.child(k),tp,k);

          // update TreePath
          std::get<last>(child_tp._data) = k;

          // descend to child
          TraverseTree<NodeTag<C>,visit>::apply(n.child(k),std::forward<V>(v),child_tp);

          // always call afterChild(), regardless of the value of visit
          v.afterChild(std::forward<N>(n),n.child(k),tp,k);

          // if this is not the last child, call infix callback
          if (k < degree(n) - 1)
119
            v.in(std::forward<N>(n),tp);
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
        }

        v.post(std::forward<N>(n),tp);
      }
    };


    namespace Impl
    {
      // ********************************************************************************
      // Static Version
      // ********************************************************************************

      template <std::size_t inverse_k, std::size_t count>
      struct TraverseTreeStatic
      {
        template <typename N, typename V, typename TreePath>
        static void apply(N&& n, V&& v, TreePath tp)
        {
          // make sure we do not try to work with references to the actual types
          typedef typename std::remove_reference<N>::type Node;
          typedef typename std::remove_reference<V>::type Visitor;

          // get child type
          typedef typename Node::template Child<count-inverse_k>::Type C;

          // extend TreePath by child index
          auto k = std::integral_constant<std::size_t, count-inverse_k>{};
          auto child_tp = push_back(tp, k);

          // is the visitor interested in this child?
          const bool visit = Visitor::template VisitChild<Node,C,decltype(child_tp)>::value;

          // beforeChild() gets called regardless of the value of visit
          v.beforeChild(std::forward<N>(n),n.template child<count-inverse_k>(),tp,k);

          // traverse to child
          TraverseTree<NodeTag<C>,visit>::apply(n.template child<count-inverse_k>(),
                                                std::forward<V>(v),
                                                child_tp);

          // afterChild() gets called regardless of the value of visit
          v.afterChild(std::forward<N>(n),n.template child<count-inverse_k>(),tp,k);

          // we are not at the last child (that is specialized), so call infix visitor callback
          v.in(std::forward<N>(n),tp);

          // continue with next child
          TraverseTreeStatic<inverse_k-1,count>::apply(std::forward<N>(n), std::forward<V>(v), tp);
        }
      };

      // Specialization for last child. This specialization stops the recursion and
      // does not call the infix visitor on the CompositeNode.
      template <std::size_t count>
      struct TraverseTreeStatic<1,count>
      {
        template<typename N, typename V, typename TreePath>
        static void apply(N&& n, V&& v, TreePath tp)
        {
          typedef typename std::remove_reference<N>::type Node;
          typedef typename std::remove_reference<V>::type Visitor;
          typedef typename Node::template Child<count-1>::Type C;
          auto k = std::integral_constant<std::size_t, count-1>{};
          auto child_tp = push_back(tp, k);

          const bool visit = Visitor::template VisitChild<Node,C,decltype(child_tp)>::value;
          v.beforeChild(std::forward<N>(n),n.template child<count-1>(),tp,k);
          TraverseTree<NodeTag<C>,visit>::apply(n.template child<count-1>(),
                                                std::forward<V>(v),
                                                child_tp);
          v.afterChild(std::forward<N>(n),n.template child<count-1>(),tp,k);
        }
      };

      // Specialization for CompositeNode without any children.
      template <>
      struct TraverseTreeStatic<0,0>
      {
        template <typename N, typename V, typename TreePath>
        static void apply(N&& n, V&& v, TreePath tp) {}
      };

    } // end namespace Impl


    // ********************************************************************************
    // CompositeNode
    // ********************************************************************************

    // Traverse CompositeNode - just forward to the generic algorithm
    template <>
    struct TraverseTree<CompositeNodeTag,true>
    {
      template <typename N, typename V, typename TreePath>
      static void apply(N&& n, V&& v, TreePath tp)
      {
        v.pre(std::forward<N>(n),tp);
        typedef typename std::remove_reference<N>::type Node;
        static const std::size_t C = StaticDegree<Node>::value;
        Impl::TraverseTreeStatic<C,C>::apply(std::forward<N>(n), std::forward<V>(v), tp);
        v.post(std::forward<N>(n),tp);
      }
    };

    #endif // DOXYGEN

    // ********************************************************************************
    // Public Interface
    // ********************************************************************************

    //! Apply visitor to TypeTree.
    /**
     * This function applies the given visitor to the given tree. Both visitor and tree may be const
     * or non-const (if the compiler supports rvalue references, they may even be a non-const temporary).
     *
     * \note The visitor must implement the interface laid out by DefaultVisitor (most easily achieved by
237
     *       inheriting from it).
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
     *
     * \param tree    The tree the visitor will be applied to.
     * \param visitor The visitor to apply to the tree.
     */
    template <typename Tree, typename Visitor>
    void traverseTree(Tree&& tree, Visitor&& visitor)
    {
      TraverseTree<>::apply(std::forward<Tree>(tree), std::forward<Visitor>(visitor));
    }

    //! \} group Tree Traversal

  } // namespace TypeTree
} //namespace Dune

#endif // DUNE_TYPETREE_TRAVERSAL_HH