Loading...
Searching...
No Matches
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: LGPL-3.0-or-later OR LicenseRef-GPL-2.0-only-with-PDELab-exception
#ifndef DUNE_TYPETREE_TRAVERSAL_HH
#define DUNE_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/childaccess.hh>
#include <dune/common/typetree/nodeconcepts.hh>
#include <dune/common/typetree/traversal.hh>
#include <dune/typetree/treepath.hh>
#include <dune/typetree/visitor.hh>
namespace Dune {
namespace TypeTree {
namespace Detail {
// SFINAE template check that Tree has a degree() function and a child() function accepting integer indices
template<class Tree>
using DynamicTraversalConcept = decltype((
std::declval<Tree>().degree(),
std::declval<Tree>().child(0u)
));
// SFINAE template check that Tree has static (constexpr) function Tree::degree()
template<class Tree>
using StaticTraversalConcept = decltype((
std::integral_constant<std::size_t, Tree::degree()>{}
));
template<class Tree, TreePathType::Type pathType, class Prefix,
std::enable_if_t<Tree::isLeaf, int> = 0>
constexpr auto leafTreePathTuple(Prefix prefix)
{
return std::make_tuple(prefix);
}
template<class Tree, TreePathType::Type pathType, class Prefix,
std::enable_if_t<not Tree::isLeaf, int> = 0>
constexpr auto leafTreePathTuple(Prefix prefix);
template<class Tree, TreePathType::Type pathType, class Prefix, std::size_t... indices,
std::enable_if_t<(Tree::isComposite or (Tree::isPower and (pathType!=TreePathType::dynamic))), int> = 0>
constexpr auto leafTreePathTuple(Prefix prefix, std::index_sequence<indices...>)
{
return std::tuple_cat(Detail::leafTreePathTuple<TypeTree::Child<Tree,indices>, pathType>(Dune::TypeTree::push_back(prefix, Dune::index_constant<indices>{}))...);
}
template<class Tree, TreePathType::Type pathType, class Prefix, std::size_t... indices,
std::enable_if_t<(Tree::isPower and (pathType==TreePathType::dynamic)), int> = 0>
constexpr auto leafTreePathTuple(Prefix prefix, std::index_sequence<indices...>)
{
return std::tuple_cat(Detail::leafTreePathTuple<TypeTree::Child<Tree,indices>, pathType>(Dune::TypeTree::push_back(prefix, indices))...);
}
template<class Tree, TreePathType::Type pathType, class Prefix,
std::enable_if_t<not Tree::isLeaf, int>>
constexpr auto leafTreePathTuple(Prefix prefix)
{
return Detail::leafTreePathTuple<Tree, pathType>(prefix, std::make_index_sequence<Tree::degree()>{});
}
/* The signature is the same as for the public applyToTree
* function in Dune::Typetree, 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.
*/
/*
* This is the overload for leaf traversal
*/
template<class T, class TreePath, class V,
std::enable_if_t<std::decay_t<T>::isLeaf, int> = 0>
void applyToTree(T&& tree, TreePath treePath, V&& visitor)
{
visitor.leaf(tree, treePath);
}
/*
* This is the general overload doing child traversal.
*/
template<class T, class TreePath, class V,
std::enable_if_t<not std::decay_t<T>::isLeaf, int> = 0>
void applyToTree(T&& tree, TreePath treePath, V&& visitor)
{
using Tree = std::remove_reference_t<T>;
using Visitor = std::remove_reference_t<V>;
visitor.pre(tree, treePath);
// the visitor may specify preferred dynamic traversal
using preferDynamicTraversal = std::bool_constant<Visitor::treePathType == TreePathType::dynamic>;
// create a dynamic or static index range
auto indices = [&]{
if constexpr(preferDynamicTraversal::value && Concept::UniformInnerTreeNode<Tree>)
return Dune::range(std::size_t(tree.degree()));
else
return Dune::range(tree.degree());
}();
if constexpr(Concept::InnerTreeNode<Tree>) {
Hybrid::forEach(indices, [&](auto i) {
auto&& child = tree.child(i);
using Child = std::decay_t<decltype(child)>;
visitor.beforeChild(tree, child, treePath, i);
// This requires that visitor.in(...) can always be instantiated,
// even if there's a single child only.
if (i>0)
visitor.in(tree, treePath);
constexpr bool visitChild = Visitor::template VisitChild<Tree,Child,TreePath>::value;
if constexpr(visitChild) {
auto childTreePath = Dune::TypeTree::push_back(treePath, i);
applyToTree(child, childTreePath, visitor);
}
visitor.afterChild(tree, child, treePath, i);
});
}
visitor.post(tree, treePath);
}
} // namespace Detail
// ********************************************************************************
// Public Interface
// ********************************************************************************
template<class Tree, TreePathType::Type pathType=TreePathType::dynamic>
constexpr auto leafTreePathTuple()
{
return Detail::leafTreePathTuple<std::decay_t<Tree>, pathType>(hybridTreePath());
}
template<Concept::TreeNode Tree, typename Visitor>
void applyToTree(Tree&& tree, Visitor&& visitor)
{
Detail::applyToTree(tree, hybridTreePath(), visitor);
}
} // namespace TypeTree
} //namespace Dune
#endif // DUNE_TYPETREE_TRAVERSAL_HH
visitor.hh
treepath.hh
Dune::TypeTree::leafTreePathTuple
constexpr auto leafTreePathTuple()
Create tuple of tree paths to leafs.
Definition traversal.hh:163
Dune::TypeTree::applyToTree
void applyToTree(Tree &&tree, Visitor &&visitor)
Apply visitor to TypeTree.
Definition traversal.hh:184
Dune::TypeTree::hybridTreePath
constexpr auto hybridTreePath(const T &... t)
Constructs a new HybridTreePath from the given indices.
Definition treepath.hh:102
Dune
Definition accumulate_static.hh:17
Dune::TypeTree
Definition accumulate_static.hh:18
Dune::TypeTree::Detail
Definition pairtraversal.hh:25
Dune::TypeTree::Detail::applyToTree
void applyToTree(T &&tree, TreePath treePath, V &&visitor)
Definition traversal.hh:91
Dune::TypeTree::Detail::StaticTraversalConcept
decltype(( std::integral_constant< std::size_t, Tree::degree()>{})) StaticTraversalConcept
Definition traversal.hh:41
Dune::TypeTree::Detail::leafTreePathTuple
constexpr auto leafTreePathTuple(Prefix prefix)
Definition traversal.hh:48
Dune::TypeTree::Detail::DynamicTraversalConcept
decltype(( std::declval< Tree >().degree(), std::declval< Tree >().child(0u))) DynamicTraversalConcept
Definition traversal.hh:34
Dune::TypeTree::TreePathType::Type
Type
Definition treepath.hh:108
Dune::TypeTree::TreePathType::dynamic
@ dynamic
Definition treepath.hh:108