Loading...
Searching...
No Matches
accumulate_static.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_ACCUMULATE_STATIC_HH
#define DUNE_TYPETREE_ACCUMULATE_STATIC_HH
#include <dune/common/typetraits.hh>
#include <dune/typetree/nodeinterface.hh>
#include <dune/typetree/nodetags.hh>
#include <dune/typetree/traversal.hh>
#include <dune/typetree/treepath.hh>
#include <dune/typetree/utility.hh>
namespace Dune {
namespace TypeTree {
template<typename result_type>
struct or_
{
template<result_type r1, result_type r2>
struct reduce
{
static const result_type result = r1 || r2;
};
};
template<typename result_type>
struct and_
{
template<result_type r1, result_type r2>
struct reduce
{
static const result_type result = r1 && r2;
};
};
template<typename result_type>
struct plus
{
template<result_type r1, result_type r2>
struct reduce
{
static const result_type result = r1 + r2;
};
};
template<typename result_type>
struct minus
{
template<result_type r1, result_type r2>
struct reduce
{
static const result_type result = r1 - r2;
};
};
template<typename result_type>
struct multiply
{
template<result_type r1, result_type r2>
struct reduce
{
static const result_type result = r1 * r2;
};
};
template<typename result_type>
struct min
{
template<result_type r1, result_type r2>
struct reduce
{
static const result_type result = r1 < r2 ? r1 : r2;
};
};
template<typename result_type>
struct max
{
template<result_type r1, result_type r2>
struct reduce
{
static const result_type result = r1 > r2 ? r1 : r2;
};
};
namespace {
// implementation of the traversal algorithm
template<typename Node, typename Functor, typename Reduction, typename Functor::result_type current_value, typename TreePath, bool doVisit>
struct accumulate_node_helper
{
typedef typename Functor::result_type result_type;
static const result_type result = current_value;
};
template<typename Node, typename Functor, typename Reduction, typename Functor::result_type current_value, typename TreePath>
struct accumulate_node_helper<Node,Functor,Reduction,current_value,TreePath,true>
{
typedef typename Functor::result_type result_type;
static const result_type result = Reduction::template reduce<current_value,Functor::template visit<Node,TreePath>::result>::result;
};
template<typename Tree, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath, typename Tag>
struct accumulate_value;
template<typename LeafNode, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath>
struct accumulate_value<LeafNode,Functor,Reduction,ParentChildReduction,current_value,TreePath,LeafNodeTag>
{
typedef typename Functor::result_type result_type;
static const result_type result =
accumulate_node_helper<LeafNode,Functor,Reduction,current_value,TreePath,Functor::template doVisit<LeafNode,TreePath>::value>::result;
};
template<typename Node, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath, std::size_t i, std::size_t n>
struct accumulate_over_children
{
typedef typename Functor::result_type result_type;
typedef decltype(push_back(TreePath{},index_constant<i>{})) child_tree_path;
typedef typename Node::template Child<i>::Type child;
static const result_type child_result = accumulate_value<child,Functor,Reduction,ParentChildReduction,current_value,child_tree_path,NodeTag<child>>::result;
static const result_type result = accumulate_over_children<Node,Functor,Reduction,ParentChildReduction,child_result,TreePath,i+1,n>::result;
};
template<typename Node, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath, std::size_t n>
struct accumulate_over_children<Node,Functor,Reduction,ParentChildReduction,current_value,TreePath,n,n>
{
typedef typename Functor::result_type result_type;
static const result_type result = current_value;
};
template<typename Node, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath>
struct accumulate_value_generic_composite_node
{
typedef typename Functor::result_type result_type;
static const result_type child_result = accumulate_over_children<Node,Functor,Reduction,ParentChildReduction,current_value,TreePath,0,StaticDegree<Node>::value>::result;
static const result_type result =
accumulate_node_helper<Node,Functor,ParentChildReduction,child_result,TreePath,Functor::template doVisit<Node,TreePath>::value>::result;
};
template<typename PowerNode, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath>
struct accumulate_value<PowerNode,Functor,Reduction,ParentChildReduction,current_value,TreePath,PowerNodeTag>
: public accumulate_value_generic_composite_node<PowerNode,Functor,Reduction,ParentChildReduction,current_value,TreePath>
{};
template<typename CompositeNode, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath>
struct accumulate_value<CompositeNode,Functor,Reduction,ParentChildReduction,current_value,TreePath,CompositeNodeTag>
: public accumulate_value_generic_composite_node<CompositeNode,Functor,Reduction,ParentChildReduction,current_value,TreePath>
{};
} // anonymous namespace
template<typename Tree, typename Functor, typename Reduction, typename Functor::result_type startValue, typename ParentChildReduction = Reduction>
struct AccumulateValue
{
typedef typename Functor::result_type result_type;
static const result_type result = accumulate_value<Tree,Functor,Reduction,ParentChildReduction,startValue,HybridTreePath<>,NodeTag<Tree>>::result;
};
struct flattened_reduction;
struct bottom_up_reduction;
namespace {
// implementation of the traversal algorithm
template<typename Node, typename Functor, typename Reduction, typename current_type, typename TreePath, bool doVisit>
struct accumulate_type_node_helper
{
typedef current_type type;
};
template<typename Node, typename Functor, typename Reduction, typename current_type, typename TreePath>
struct accumulate_type_node_helper<Node,Functor,Reduction,current_type,TreePath,true>
{
typedef typename Reduction::template reduce<
current_type,
typename Functor::template visit<
Node,
TreePath
>::type
>::type type;
};
template<typename Tree, typename Policy, typename current_type, typename TreePath, typename Tag>
struct accumulate_type;
template<typename LeafNode, typename Policy, typename current_type, typename TreePath>
struct accumulate_type<LeafNode,Policy,current_type,TreePath,LeafNodeTag>
{
typedef typename accumulate_type_node_helper<
LeafNode,
typename Policy::functor,
typename Policy::sibling_reduction,
current_type,
TreePath,
Policy::functor::template doVisit<
LeafNode,
TreePath>::value
>::type type;
};
template<typename current_type, typename tree_path, typename start_type, typename reduction_strategy>
struct propagate_type_down_tree;
template<typename current_type, typename tree_path, typename start_type>
struct propagate_type_down_tree<
current_type,
tree_path,
start_type,
bottom_up_reduction
>
{
typedef current_type type;
};
template<typename current_type, typename tree_path, typename start_type>
struct propagate_type_down_tree<
current_type,
tree_path,
start_type,
flattened_reduction
>
{
typedef typename std::conditional<
tree_path().back() == 0,
start_type,
current_type
>::type type;
};
template<typename Node, typename Policy, typename current_type, typename TreePath, std::size_t i, std::size_t n>
struct accumulate_type_over_children
{
typedef decltype(push_back(TreePath{},index_constant<i>{})) child_tree_path;
typedef typename Node::template Child<i>::Type child;
typedef typename accumulate_type<
child,
Policy,
// apply reduction choice (flat / hierarchic)
typename propagate_type_down_tree<
current_type,
child_tree_path,
typename Policy::start_type,
typename Policy::reduction_strategy
>::type,
child_tree_path,
NodeTag<child>
>::type child_result_type;
typedef typename accumulate_type_over_children<
Node,
Policy,
child_result_type,
TreePath,
i+1,
n
>::type type;
};
template<typename Node, typename Policy, typename current_type, typename TreePath, std::size_t n>
struct accumulate_type_over_children<Node,Policy,current_type,TreePath,n,n>
{
typedef current_type type;
};
template<typename Node, typename Policy, typename current_type, typename TreePath>
struct accumulate_type_generic_composite_node
{
typedef typename accumulate_type_over_children<
Node,
Policy,
current_type,
TreePath,
0,
StaticDegree<Node>::value
>::type children_result_type;
typedef typename accumulate_type_node_helper<
Node,
typename Policy::functor,
typename Policy::parent_child_reduction,
children_result_type,
TreePath,
Policy::functor::template doVisit<
Node,
TreePath
>::value
>::type type;
};
template<typename PowerNode, typename Policy, typename current_type, typename TreePath>
struct accumulate_type<PowerNode,Policy,current_type,TreePath,PowerNodeTag>
: public accumulate_type_generic_composite_node<PowerNode,Policy,current_type,TreePath>
{};
template<typename CompositeNode, typename Policy, typename current_type, typename TreePath>
struct accumulate_type<CompositeNode,Policy,current_type,TreePath,CompositeNodeTag>
: public accumulate_type_generic_composite_node<CompositeNode,Policy,current_type,TreePath>
{};
} // anonymous namespace
template<
typename Functor,
typename Reduction,
typename StartType,
typename ParentChildReduction = Reduction,
typename ReductionAlgorithm = flattened_reduction
>
struct TypeAccumulationPolicy
{
typedef Functor functor;
typedef Reduction sibling_reduction;
typedef ParentChildReduction parent_child_reduction;
typedef StartType start_type;
typedef ReductionAlgorithm reduction_strategy;
};
template<typename Tree, typename Policy>
struct AccumulateType
{
typedef typename accumulate_type<
Tree,
Policy,
typename Policy::start_type,
HybridTreePath<>,
NodeTag<Tree>
>::type type;
};
/***************************************************/
namespace Experimental {
namespace Impl {
template<class T, class TreePath, class V, class U,
std::enable_if_t<std::decay_t<T>::isLeaf, int> = 0>
auto hybridApplyToTree(T&& tree, TreePath treePath, V&& visitor, U&& current_val)
{
return visitor.leaf(tree, treePath, std::forward<U>(current_val));
}
template<class T, class TreePath, class V, class U,
std::enable_if_t<not std::decay_t<T>::isLeaf, int> = 0>
auto hybridApplyToTree(T&& tree, TreePath treePath, V&& visitor, U&& current_val)
{
using Tree = std::remove_reference_t<T>;
using Visitor = std::remove_reference_t<V>;
auto pre_val = visitor.pre(tree, treePath, std::forward<U>(current_val));
// check which type of traversal is supported by the tree
using allowDynamicTraversal = Dune::Std::is_detected<Detail::DynamicTraversalConcept,Tree>;
using allowStaticTraversal = Dune::Std::is_detected<Detail::StaticTraversalConcept,Tree>;
// the tree must support either dynamic or static traversal
static_assert(allowDynamicTraversal::value || allowStaticTraversal::value);
// the visitor may specify preferred dynamic traversal
using preferDynamicTraversal = std::bool_constant<Visitor::treePathType == TreePathType::dynamic>;
// declare rule that applies visitor and current value to a child i. Returns next value
auto apply_i = [&](auto&& value, const auto& i){
auto&& child = tree.child(i);
using Child = std::decay_t<decltype(child)>;
auto val_before = visitor.beforeChild(tree, child, treePath, i, std::move(value));
// visits between children
auto val_in = Hybrid::ifElse(
Hybrid::equal_to(i,Indices::_0),
[&](auto id){return std::move(val_before);},
[&](auto id){return visitor.in(tree, treePath, std::move(val_before));}
);
constexpr bool visitChild = Visitor::template VisitChild<Tree,Child,TreePath>::value;
auto val_visit = [&](){
if constexpr (visitChild) {
auto childTreePath = Dune::TypeTree::push_back(treePath, i);
return hybridApplyToTree(child, childTreePath, visitor, std::move(val_in));
}
else
return std::move(val_in);
}();
return visitor.afterChild(tree, child, treePath, i, std::move(val_visit));
};
// apply visitor to children
auto in_val = [&](){
if constexpr (allowStaticTraversal::value && not preferDynamicTraversal::value) {
// get list of static indices
auto indices = std::make_index_sequence<Tree::degree()>{};
// unfold apply_i left to right
return unpackIntegerSequence([&](auto... i) {
return left_fold(std::move(apply_i),std::move(pre_val), i...);
}, indices);
} else {
// unfold first child to get type
auto i_val = apply_i(std::move(pre_val),std::size_t{0});
// dynamically loop rest of the children to accumulate remindng values
for(std::size_t i = 1; i < tree.degree(); i++)
i_val = apply_i(i_val,i);
return i_val;
}
}();
return visitor.post(tree, treePath, in_val);
}
}
template<typename Tree, typename Visitor, typename Init>
auto hybridApplyToTree(Tree&& tree, Visitor&& visitor, Init&& init)
{
return Impl::hybridApplyToTree(tree, hybridTreePath(), visitor, init);
}
} // namespace Experimental
} // namespace TypeTree
} //namespace Dune
#endif // DUNE_TYPETREE_ACCUMULATE_STATIC_HH
nodetags.hh
treepath.hh
traversal.hh
utility.hh
nodeinterface.hh
Dune::TypeTree::NodeTag
typename std::decay_t< Node >::NodeTag NodeTag
Returns the node tag of the given Node.
Definition nodeinterface.hh:70
Dune::TypeTree::hybridTreePath
constexpr auto hybridTreePath(const T &... t)
Constructs a new HybridTreePath from the given indices.
Definition treepath.hh:102
Dune::TypeTree::HybridTreePath
Dune::HybridMultiIndex< T... > HybridTreePath
A type for representing tree paths that supports both compile time and run time indices.
Definition treepath.hh:85
Dune
Definition accumulate_static.hh:17
Dune::TypeTree
Definition accumulate_static.hh:18
Dune::TypeTree::Experimental
Definition accumulate_static.hh:576
Dune::TypeTree::Experimental::hybridApplyToTree
auto hybridApplyToTree(Tree &&tree, Visitor &&visitor, Init &&init)
Apply hybrid visitor to TypeTree.
Definition accumulate_static.hh:702
Dune::TypeTree::or_
Statically combine two values of type result_type using ||.
Definition accumulate_static.hh:28
Dune::TypeTree::or_::reduce
Definition accumulate_static.hh:31
Dune::TypeTree::or_::reduce::result
static const result_type result
Definition accumulate_static.hh:32
Dune::TypeTree::and_
Statically combine two values of type result_type using &&.
Definition accumulate_static.hh:39
Dune::TypeTree::and_::reduce
Definition accumulate_static.hh:42
Dune::TypeTree::and_::reduce::result
static const result_type result
Definition accumulate_static.hh:43
Dune::TypeTree::plus
Statically combine two values of type result_type using +.
Definition accumulate_static.hh:50
Dune::TypeTree::plus::reduce
Definition accumulate_static.hh:53
Dune::TypeTree::plus::reduce::result
static const result_type result
Definition accumulate_static.hh:54
Dune::TypeTree::minus
Statically combine two values of type result_type using -.
Definition accumulate_static.hh:61
Dune::TypeTree::minus::reduce
Definition accumulate_static.hh:64
Dune::TypeTree::minus::reduce::result
static const result_type result
Definition accumulate_static.hh:65
Dune::TypeTree::multiply
Statically combine two values of type result_type using *.
Definition accumulate_static.hh:72
Dune::TypeTree::multiply::reduce
Definition accumulate_static.hh:75
Dune::TypeTree::multiply::reduce::result
static const result_type result
Definition accumulate_static.hh:76
Dune::TypeTree::min
Statically combine two values of type result_type by returning their minimum.
Definition accumulate_static.hh:83
Dune::TypeTree::min::reduce
Definition accumulate_static.hh:86
Dune::TypeTree::min::reduce::result
static const result_type result
Definition accumulate_static.hh:87
Dune::TypeTree::max
Statically combine two values of type result_type by returning their maximum.
Definition accumulate_static.hh:94
Dune::TypeTree::max::reduce
Definition accumulate_static.hh:97
Dune::TypeTree::max::reduce::result
static const result_type result
Definition accumulate_static.hh:98
Dune::TypeTree::AccumulateValue
Statically accumulate a value over the nodes of a TypeTree.
Definition accumulate_static.hh:263
Dune::TypeTree::AccumulateValue::result_type
Functor::result_type result_type
The result type of the computation.
Definition accumulate_static.hh:266
Dune::TypeTree::AccumulateValue::result
static const result_type result
The accumulated result of the computation.
Definition accumulate_static.hh:269
Dune::TypeTree::TypeAccumulationPolicy
Definition accumulate_static.hh:470
Dune::TypeTree::TypeAccumulationPolicy::parent_child_reduction
ParentChildReduction parent_child_reduction
Definition accumulate_static.hh:528
Dune::TypeTree::TypeAccumulationPolicy::functor
Functor functor
Definition accumulate_static.hh:499
Dune::TypeTree::TypeAccumulationPolicy::start_type
StartType start_type
Definition accumulate_static.hh:536
Dune::TypeTree::TypeAccumulationPolicy::reduction_strategy
ReductionAlgorithm reduction_strategy
Definition accumulate_static.hh:542
Dune::TypeTree::TypeAccumulationPolicy::sibling_reduction
Reduction sibling_reduction
Definition accumulate_static.hh:520
Dune::TypeTree::AccumulateType
Statically accumulate a type over the nodes of a TypeTree.
Definition accumulate_static.hh:557
Dune::TypeTree::AccumulateType::type
accumulate_type< Tree, Policy, typenamePolicy::start_type, HybridTreePath<>, NodeTag< Tree > >::type type
The accumulated result of the computation.
Definition accumulate_static.hh:566