Traversal.hpp 4.53 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
// NOTE: backport of dune/typetree/traversal.hh from Dune 2.7
12

13
14
15
namespace AMDiS {
namespace Traversal {
namespace Impl_ {
16

17
  /// \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
} // end namespace Impl_
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
/**
 * Traverse tree and visit each node. On each node call preFunc and postFunc before and after
 * visiting its childs. Call leafFunc on all leaf nodes.
 **/
template <class Tree, class TreePath, class Pre, class Leaf, class Post>
void forEachNode(Tree&& tree, TreePath treePath, Pre&& preFunc, Leaf&& leafFunc, Post&& postFunc)
{
  using TreeType = std::decay_t<Tree>;
  if constexpr (TreeType::isLeaf) {
    // For leaf nodes just visit using the leaf function.
    leafFunc(tree, treePath);
  } else {
    preFunc(tree, treePath);
    const auto degree = Impl_::traversalDegree(tree);
    if constexpr (std::is_integral_v<TYPEOF(degree)>) {
      // Specialization for dynamic traversal
      for (std::size_t i = 0; i < std::size_t(degree); ++i) {
        auto childTreePath = Dune::TypeTree::push_back(treePath, i);
        forEachNode(tree.child(i), childTreePath, preFunc, leafFunc, postFunc);
      }
    } else {
      // Specialization for static traversal
      const auto indices = std::make_index_sequence<VALUE(degree)>{};
      Ranges::forIndices(indices, [&](auto i) {
        auto childTreePath = Dune::TypeTree::push_back(treePath, i);
        forEachNode(tree.child(i), childTreePath, preFunc, leafFunc, postFunc);
      });
    }
    postFunc(tree, treePath);
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
132
133
134
135
}


/// \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 forEachNode(Tree&& tree, Pre&& preFunc, Leaf&& leafFunc, Post&& postFunc)
{
  auto root = Dune::TypeTree::hybridTreePath();
  forEachNode(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 Inner, class Leaf>
void forEachNode(Tree&& tree, Inner&& innerFunc, Leaf&& leafFunc)
{
  auto root = Dune::TypeTree::hybridTreePath();
  forEachNode(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 forEachNode(Tree&& tree, NodeFunc&& nodeFunc)
{
  auto root = Dune::TypeTree::hybridTreePath();
  forEachNode(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 Leaf>
void forEachLeafNode(Tree&& tree, Leaf&& leafFunc)
{
  auto root = Dune::TypeTree::hybridTreePath();
  forEachNode(tree, root, NoOp{}, leafFunc, NoOp{});
}
136

137
}} // end namespace AMDiS::Traversal