traversal.hh

Go to the documentation of this file.

// -*- 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