Traversal.hpp

#pragma once

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

namespace AMDiS
{
  // forward declaration of main engine struct
  template <typename NodeTag, bool visit = true>
  struct TraverseTree;


  // Do not visit nodes the visitor is not interested in
  template <typename NodeTag>
  struct TraverseTree<NodeTag, false>
  {
    template <typename Node, typename Visitor, typename TreePath>
    static void apply(const Node& node, const Visitor& visitor, TreePath const& tp)
    {}
  };

#ifndef DOXYGEN

  // some implementation details

  template <class Node, class Index>
  struct HybridChildType
      : HybridChildType<std::remove_const_t<Node>, std::remove_const_t<Index>> {};

  template <class Node>
  struct HybridChildType<Node, std::size_t>
  {
    using type = typename Node::template Child<0>::Type;
  };

  template <class Node, std::size_t K>
  struct HybridChildType<Node, Dune::index_constant<K>>
  {
    using type = typename Node::template Child<K>::Type;
  };

  template <class NodeTag, class Node>
  constexpr std::size_t hybridDegree(NodeTag, Node const& node)
  {
    return Dune::TypeTree::degree(node);
  }

  template <class Node>
  constexpr auto hybridDegree(Dune::TypeTree::CompositeNodeTag, Node const& node)
  {
    return Dune::index_constant<Node::CHILDREN>{};
  }


  template <std::size_t k, std::size_t n>
  constexpr bool notLastChild(Dune::index_constant<k> const&, Dune::index_constant<n> const&)
  {
    return k < n-1;
  }

  constexpr bool notLastChild(std::size_t k, std::size_t n)
  {
    return k < n-1;
  }

#endif


  template <class NodeTag>
  struct TraverseTree<NodeTag, true>
  {
    template <typename N, typename V, typename TreePath>
    static void apply(N&& n, V&& v, TreePath const& tp)
    {
      using Node = std::remove_reference_t<N>;
      using Visitor = std::remove_reference_t<V>;

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

      auto const deg = hybridDegree(NodeTag{}, n);
      forEach(Dune::range(deg), [&](auto const _k)
      {
        // always call beforeChild(), regardless of the value of visit
        v.beforeChild(std::forward<N>(n),n.child(_k),tp,_k);

        // descend to child
        using C = typename HybridChildType<Node, decltype(_k)>::type;
        const bool visit = Visitor::template VisitChild<Node,C,TreePath>::value;
        TraverseTree<Dune::TypeTree::NodeTag<C>,visit>::apply(n.child(_k),std::forward<V>(v),push_back(tp, _k));

        // 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 (notLastChild(_k, deg))
          v.in(std::forward<N>(n),tp);
      });

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

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

  //! 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
    *       inheriting from it).
    *
    * \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)
  {
    using Node = std::remove_reference_t<Tree>;
    using NodeTag = Dune::TypeTree::NodeTag<Node>;
    using TreePath = Dune::TypeTree::HybridTreePath<>;
    TraverseTree<NodeTag>::apply(std::forward<Tree>(tree), std::forward<Visitor>(visitor), TreePath{});
  }

} // end namespace AMDiS