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

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

5
6
7
#include <dune/typetree/nodetags.hh>
#include <dune/typetree/treepath.hh>

8
#include <amdis/common/ForEach.hpp>
9
#include <amdis/common/TypeTraits.hpp>
10

11
12
// NOTE: backport of dune/typetree/traversal.hpp from Dune 2.7

13
14
15
16
17
namespace AMDiS
{
  namespace Impl
  {
    /// \brief Helper function that returns the degree of a Tree.
18
    /**
19
20
21
     * The return type is either `size_t` if it is a dynamic tree or the flag `dynamic`
     * is set to `true`, or as the type returned by the `degree()` member function of the
     * tree.
22
     *
23
24
25
26
27
28
     * This function allows to change the tree traversal from static to dynamic in case
     * of power nodes and uses static traversal for composite and dynamic traversal for
     * all dynamic nodes.
     **/
    template <bool dynamic = true, class Tree>
    auto traversalDegree(Tree const& tree)
29
    {
30
31
32
33
34
35
      if constexpr (dynamic && Tree::isPower)
        return std::size_t(tree.degree());
      else if constexpr (Tree::isPower || Tree::isComposite)
        return std::integral_constant<std::size_t, Tree::degree()>{};
      else
        return tree.degree();
36
    }
37

38
    /**
39
40
41
42
43
44
45
46
47
48
     * 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.
     **/
    template <class Tree, class TreePath, class PreFunc, class LeafFunc, class PostFunc>
    void for_each_node(Tree&& tree, TreePath treePath, PreFunc&& preFunc, LeafFunc&& leafFunc, PostFunc&& postFunc)
49
    {
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
      using TreeType = std::decay_t<Tree>;
      if constexpr (TreeType::isLeaf) {
        // If we have a leaf tree just visit it using the leaf function.
        leafFunc(tree, treePath);
      } else {
        // Otherwise visit the tree with the pre function,
        // visit all children using a static or dynamic loop, and
        // finally visit the tree with the post function.
        preFunc(tree, treePath);
        Dune::Hybrid::forEach(Dune::range(traversalDegree(tree)), [&](auto i) {
          auto childTreePath = push_back(treePath, i);
          Impl::for_each_node(tree.child(i), childTreePath, preFunc, leafFunc, postFunc);
        });
        postFunc(tree, treePath);
      }
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
124
125
126
127
128
129
130
131
  } // end namespace Impl


  /// \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 PreFunc, class LeafFunc, class PostFunc>
  void for_each_node(Tree&& tree, PreFunc&& preFunc, LeafFunc&& leafFunc, PostFunc&& postFunc)
  {
    auto root = Dune::TypeTree::hybridTreePath();
    Impl::for_each_node(tree, root, preFunc, leafFunc, postFunc);
  }

  /// \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 InnerFunc, class LeafFunc>
  void for_each_node(Tree&& tree, InnerFunc&& innerFunc, LeafFunc&& leafFunc)
  {
    auto root = Dune::TypeTree::hybridTreePath();
    Impl::for_each_node(tree, root, innerFunc, leafFunc, NoOp{});
  }

  /// \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{});
  }

  /// \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 LeafFunc>
  void for_each_leaf_node(Tree&& tree, LeafFunc&& leafFunc)
  {
    auto root = Dune::TypeTree::hybridTreePath();
    Impl::for_each_node(tree, root, NoOp{}, leafFunc, NoOp{});
  }
132
133

} // end namespace AMDiS