traversal.hh

// -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
// vi: set et ts=4 sw=2 sts=2:
// SPDX-FileCopyrightInfo: Copyright © DUNE Project contributors, see file LICENSE.md in module root
// SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception OR LGPL-3.0-or-later
 
#ifndef DUNE_COMMON_TYPETREE_TRAVERSAL_HH
#define DUNE_COMMON_TYPETREE_TRAVERSAL_HH
 
#include <utility>
 
#include <dune/common/hybridutilities.hh>
#include <dune/common/indices.hh>
#include <dune/common/std/type_traits.hh>
 
#include <dune/common/typetree/nodeconcepts.hh>
#include <dune/common/typetree/childaccess.hh>
#include <dune/common/typetree/treepath.hh>
 
namespace Dune::TypeTree {
 
  namespace Impl {
 
    template<class Callable, class Arg0, class Arg1>
    constexpr void invokeWithTwoOrOneArg(Callable&& callable, Arg0&& arg0, Arg1&& arg1) {
      static_assert(std::invocable<Callable&&, Arg0&&, Arg1&&> || std::invocable<Callable&&, Arg0&&>);
      if constexpr (std::invocable<Callable&&, Arg0&&, Arg1&&>)
        callable(arg0, arg1);
      else if constexpr (std::invocable<Callable&&, Arg0&&>)
        callable(arg0);
    };
 
  } // namespace Impl
 
#ifndef DOXYGEN
  struct NoOp
  {
    template<class... T>
    constexpr void operator()(T&&...) const { /* do nothing */ }
  };
#endif
 
  template<Concept::InnerTreeNode Tree, class Callable>
  constexpr void forEachChild(Tree&& container, Callable&& at_value)
  {
    if constexpr (Concept::UniformInnerTreeNode<Tree>)
      for (std::size_t i = 0; i != container.degree(); ++i)
        Impl::invokeWithTwoOrOneArg(at_value, std::forward<Tree>(container).child(i), i);
    else
      Dune::unpackIntegerSequence(
        [&](auto... i) { (Impl::invokeWithTwoOrOneArg(at_value, std::forward<Tree>(container).child(i), i), ...); },
        std::make_index_sequence<std::remove_cvref_t<Tree>::degree()>{});
  }
 
  namespace Impl {
 
    /* Traverse tree and visit each node. The signature is the same
     * as for the public forEachNode 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<Concept::TreeNode Tree, class TreePath, class PreFunc, class LeafFunc, class PostFunc>
    void forEachNode(Tree&& tree, TreePath treePath, PreFunc&& preFunc, LeafFunc&& leafFunc, PostFunc&& postFunc)
    {
      if constexpr(Concept::LeafTreeNode<std::decay_t<Tree>>) {
        Impl::invokeWithTwoOrOneArg(leafFunc, tree, treePath);
      } else {
        Impl::invokeWithTwoOrOneArg(preFunc, tree, treePath);
        forEachChild(
          tree,
          [&]<class Child>(Child&& child, auto i) {
            forEachNode(
              std::forward<Child>(child),
              push_back(treePath, i),
              preFunc,
              leafFunc,
              postFunc
            );
          });
        Impl::invokeWithTwoOrOneArg(postFunc, tree, treePath);
      }
    }
 
  } // namespace Impl
 
 
  // ********************************************************************************
  // Public Interface
  // ********************************************************************************
 
  template<class Tree, class PreNodeFunc, class LeafNodeFunc, class PostNodeFunc>
  void forEachNode(Tree&& tree, PreNodeFunc&& preNodeFunc, LeafNodeFunc&& leafNodeFunc, PostNodeFunc&& postNodeFunc)
  {
    Impl::forEachNode(tree, treePath(), preNodeFunc, leafNodeFunc, postNodeFunc);
  }
 
  template<Concept::TreeNode Tree, class NodeFunc>
  void forEachNode(Tree&& tree, NodeFunc&& nodeFunc)
  {
    forEachNode(tree, nodeFunc, nodeFunc, NoOp{});
  }
 
  template<Concept::TreeNode Tree, class LeafFunc>
  void forEachLeafNode(Tree&& tree, LeafFunc&& leafFunc)
  {
    forEachNode(tree, NoOp{}, leafFunc, NoOp{});
  }
 
 
} //namespace Dune::TypeTree
 
#endif // DUNE_COMMON_TYPETREE_TRAVERSAL_HH