Traversal.hpp 9.83 KB
Newer Older
1
#pragma once
2

3
4
5
#include <dune/common/hybridutilities.hh>
#include <dune/common/rangeutilities.hh>

6
#include <dune/typetree/childextraction.hh>
7
8
9
10
#include <dune/typetree/nodetags.hh>
#include <dune/typetree/treepath.hh>
#include <dune/typetree/visitor.hh>

11
#include <amdis/common/ForEach.hpp>
12
13
#include <amdis/common/Logical.hpp>
#include <amdis/common/Range.hpp>
14
#include <amdis/common/TypeTraits.hpp>
15

16
17
18
19
20
// NOTE: backport of dune/typetree/traversal.hpp from Dune 2.7

namespace AMDiS {

    enum class TreePathType
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
      DYNAMIC, STATIC
    };

    namespace Impl {

      // This is a constexpr version of the ternery operator c?t1:t1.
      // In contrast to the latter the type of t1 and t2 can be different.
      // Notice that std::conditional would not do the trick, because
      // it only selects between types.
      template<bool c, class T1, class T2,
        std::enable_if_t<c, int> = 0>
      constexpr auto conditionalValue(T1&& t1, T2&& t2) {
        return std::forward<T1>(t1);
      }

      template<bool c, class T1, class T2,
        std::enable_if_t<not c, int> = 0>
      constexpr auto conditionalValue(T1&& t1, T2&& t2) {
        return std::forward<T2>(t2);
      }


      /* The signature is the same as for the public applyToTree
       * function in Dune::Typetree, despite the additionally passed
       * treePath argument. The path passed here is associated to
       * the tree and the relative paths of the children (wrt. to tree)
       * are appended to this.  Hence the behavior of the public function
       * is resembled by passing an empty treePath.
       */

      /*
       * This is the overload for leaf traversal
       */
      template<class T, class TP, class V,
        std::enable_if_t<remove_cvref_t<T>::isLeaf, int> = 0>
      void apply_to_tree(T&& tree, TP treePath, V&& visitor)
      {
        visitor.leaf(tree, treePath);
      }

      /*
       * This is the general overload doing child traversal.
       */
      template<class T, class TP, class V,
        std::enable_if_t<not remove_cvref_t<T>::isLeaf, int> = 0>
      void apply_to_tree(T&& tree, TP treePath, V&& visitor)
      {
        // Do we really want to take care for const-ness of the Tree
        // when instantiating VisitChild below? I'd rather expect this:
        // using Tree = remove_cvref_t<T>;
        // using Visitor = remove_cvref_t<V>;
        using Tree = std::remove_reference_t<T>;
        using Visitor = std::remove_reference_t<V>;
        visitor.pre(tree, treePath);

        // Use statically encoded degree unless tree
        // is a power node and dynamic traversal is requested.
        constexpr auto useDynamicTraversal = (Tree::isPower and Visitor::treePathType==TreePathType::DYNAMIC);
        auto degree = conditionalValue<useDynamicTraversal>(Tree::degree(), Dune::index_constant<Tree::degree()>{});

        auto indices = Dune::range(degree);
        Dune::Hybrid::forEach(indices, [&](auto i) {
          auto childTP = Dune::TypeTree::push_back(treePath, i);
          auto&& child = tree.child(i);
          using Child = TYPEOF(child);

          visitor.beforeChild(tree, child, treePath, i);

          // This requires that visiotor.in(...) can always be instantiated,
          // even if there's a single child only.
          if (i>0)
            visitor.in(tree, treePath);
          static constexpr auto visitChild = Visitor::template VisitChild<Tree,Child,TP>::value;
          if constexpr(visitChild)
            applyToTree(child, childTP, visitor);
          visitor.afterChild(tree, child, treePath, i);
        });
        visitor.post(tree, treePath);
      }

      // Overload for leaf nodes
      template<class Tree, class TP, class Pre, class Leaf, class Post,
        std::enable_if_t<remove_cvref_t<Tree>::isLeaf, int> = 0>
      void for_each_node(Tree&& tree, TP treePath, Pre&& /*preFunc*/, Leaf&& leafFunc, Post&& /*postFunc*/)
      {
        leafFunc(tree, treePath);
      }

      // Overload for non-leaf nodes
      // Forward declaration needed for recursion
      template<class Tree, class TP, class Pre, class Leaf, class Post,
        std::enable_if_t<not remove_cvref_t<Tree>::isLeaf,int> = 0>
      void for_each_node(Tree&& tree, TP treePath, Pre&& preFunc, Leaf&& leafFunc, Post&& postFunc);

      // Helper for power nodes
      template<class Tree, class TP, class Pre, class Leaf, class Post, std::size_t... I,
        std::enable_if_t<remove_cvref_t<Tree>::isPower, int> = 0>
      void for_each_node_unfold(Tree&& tree, TP treePath, Pre&& preFunc, Leaf&& leafFunc, Post&& postFunc, std::index_sequence<I...>)
      {
        for (std::size_t i = 0; i < sizeof...(I); ++i)
          Impl::for_each_node(tree.child(i), Dune::TypeTree::push_back(treePath, i), preFunc, leafFunc, postFunc);
      }
124

125
126
127
128
129
130
131
132
133
134
      // Helper for composite nodes
      template<class Tree, class TP, class Pre, class Leaf, class Post, std::size_t... I,
        std::enable_if_t<not remove_cvref_t<Tree>::isPower, int> = 0>
      void for_each_node_unfold(Tree&& tree, TP treePath, Pre&& preFunc, Leaf&& leafFunc, Post&& postFunc, std::index_sequence<I...>)
      {
        (void)std::initializer_list<int>{(
          Impl::for_each_node(tree.child(Dune::index_constant<I>{}),
            Dune::TypeTree::push_back(treePath, Dune::index_constant<I>{}), preFunc, leafFunc, postFunc),0)...
        };
      }
135

136
137
138
139
140
141
142
143
144
145
146
147
148
149
      /*
       * Traverse tree and visit each node. The signature is the same
       * as for the public for_each_node function in Dune::Typtree,
       * despite the additionally passed treePath argument. The path
       * passed here is associated to the tree and the relative
       * paths of the children (wrt. to tree) are appended to this.
       * Hence the behavior of the public function is resembled
       * by passing an empty treePath.
       *
       * See also the specialization for leaf-nodes.
       */
      template<class Tree, class TP, class Pre, class Leaf, class Post,
        std::enable_if_t<not remove_cvref_t<Tree>::isLeaf,int>>
      void for_each_node(Tree&& tree, TP treePath, Pre&& preFunc, Leaf&& leafFunc, Post&& postFunc)
150
      {
151
152
153
154
155
156
157
158
159
160
161
162
        auto indices = std::make_index_sequence<TYPEOF(tree)::degree()>{};
        preFunc(tree, treePath);
        Impl::for_each_node_unfold(tree, treePath, preFunc, leafFunc, postFunc, indices);
        postFunc(tree, treePath);
      }

    } // namespace Impl


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

164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
    //! Apply visitor to TypeTree.
    /**
     * \code
     * #include <amdis/typetree/Traversal.hpp>
     * \endcode
     * 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
     *       inheriting from it) and specify the required type of tree traversal (static or dynamic) by
     *       inheriting from either StaticTraversal or DynamicTraversal.
     *
     * \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 apply_to_tree(Tree&& tree, Visitor&& visitor)
    {
      auto root = Dune::TypeTree::hybridTreePath();
      Impl::apply_to_tree(tree, root, visitor);
    }
185

186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
    /**
     * \brief Traverse tree and visit each node
     *
     * All passed callback functions are called with the
     * node and corresponding treepath as arguments.
     *
     * \param tree The tree to traverse
     * \param preFunc This function is called for each inner node before visiting its children
     * \param leafFunc This function is called for each leaf node
     * \param postFunc This function is called for each inner node after visiting its children
     */
    template<class Tree, class Pre, class Leaf, class Post>
    void for_each_node(Tree&& tree, Pre&& preFunc, Leaf&& leafFunc, Post&& postFunc)
    {
      auto root = Dune::TypeTree::hybridTreePath();
      Impl::for_each_node(tree, root, preFunc, leafFunc, postFunc);
    }
203

204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
    /**
     * \brief Traverse tree and visit each node
     *
     * All passed callback functions are called with the
     * node and corresponding treepath as arguments.
     *
     * \param tree The tree to traverse
     * \param innerFunc This function is called for each inner node before visiting its children
     * \param leafFunc This function is called for each leaf node
     */
    template<class Tree, class Inner, class Leaf>
    void for_each_node(Tree&& tree, Inner&& innerFunc, Leaf&& leafFunc)
    {
      auto root = Dune::TypeTree::hybridTreePath();
      Impl::for_each_node(tree, root, innerFunc, leafFunc, NoOp{});
    }
220

221
222
223
224
225
226
227
228
229
230
231
232
233
234
    /**
     * \brief Traverse tree and visit each node
     *
     * The passed callback function is called with the
     * node and corresponding treepath as arguments.
     *
     * \param tree The tree to traverse
     * \param nodeFunc This function is called for each node
     */
    template<class Tree, class NodeFunc>
    void for_each_node(Tree&& tree, NodeFunc&& nodeFunc)
    {
      auto root = Dune::TypeTree::hybridTreePath();
      Impl::for_each_node(tree, root, nodeFunc, nodeFunc, NoOp{});
235
    }
236
237
238
239
240
241
242
243
244
245
246
247

    /**
     * \brief Traverse tree and visit each leaf node
     *
     * The passed callback function is called with the
     * node and corresponding treepath as arguments.
     *
     * \param tree The tree to traverse
     * \param leafFunc This function is called for each leaf node
     */
    template<class Tree, class Leaf>
    void for_each_leaf_node(Tree&& tree, Leaf&& leafFunc)
248
    {
249
250
      auto root = Dune::TypeTree::hybridTreePath();
      Impl::for_each_node(tree, root, NoOp{}, leafFunc, NoOp{});
251
252
253
    }

} // end namespace AMDiS