DUNE PDELab (git)

accumulate_static.hh
1// -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2// vi: set et ts=4 sw=2 sts=2:
3// SPDX-FileCopyrightInfo: Copyright © DUNE Project contributors, see file LICENSE.md in module root
4// SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-GPL-2.0-only-with-PDELab-exception
5
6#ifndef DUNE_TYPETREE_ACCUMULATE_STATIC_HH
7#define DUNE_TYPETREE_ACCUMULATE_STATIC_HH
8
9#include <dune/common/typetraits.hh>
10#include <dune/typetree/nodeinterface.hh>
11#include <dune/typetree/nodetags.hh>
12#include <dune/typetree/treepath.hh>
13#include <dune/typetree/utility.hh>
14
15
16namespace Dune {
17 namespace TypeTree {
18
25 template<typename result_type>
26 struct or_
27 {
28 template<result_type r1, result_type r2>
29 struct reduce
30 {
31 static const result_type result = r1 || r2;
32 };
33 };
34
36 template<typename result_type>
37 struct and_
38 {
39 template<result_type r1, result_type r2>
40 struct reduce
41 {
42 static const result_type result = r1 && r2;
43 };
44 };
45
47 template<typename result_type>
48 struct plus
49 {
50 template<result_type r1, result_type r2>
51 struct reduce
52 {
53 static const result_type result = r1 + r2;
54 };
55 };
56
58 template<typename result_type>
59 struct minus
60 {
61 template<result_type r1, result_type r2>
62 struct reduce
63 {
64 static const result_type result = r1 - r2;
65 };
66 };
67
69 template<typename result_type>
70 struct multiply
71 {
72 template<result_type r1, result_type r2>
73 struct reduce
74 {
75 static const result_type result = r1 * r2;
76 };
77 };
78
80 template<typename result_type>
81 struct min
82 {
83 template<result_type r1, result_type r2>
84 struct reduce
85 {
86 static const result_type result = r1 < r2 ? r1 : r2;
87 };
88 };
89
91 template<typename result_type>
92 struct max
93 {
94 template<result_type r1, result_type r2>
95 struct reduce
96 {
97 static const result_type result = r1 > r2 ? r1 : r2;
98 };
99 };
100
101
102 namespace {
103
104 // implementation of the traversal algorithm
105
107 template<typename Node, typename Functor, typename Reduction, typename Functor::result_type current_value, typename TreePath, bool doVisit>
108 struct accumulate_node_helper
109 {
110
111 typedef typename Functor::result_type result_type;
112
113 static const result_type result = current_value;
114
115 };
116
118 template<typename Node, typename Functor, typename Reduction, typename Functor::result_type current_value, typename TreePath>
119 struct accumulate_node_helper<Node,Functor,Reduction,current_value,TreePath,true>
120 {
121
122 typedef typename Functor::result_type result_type;
123
124 static const result_type result = Reduction::template reduce<current_value,Functor::template visit<Node,TreePath>::result>::result;
125
126 };
127
129 template<typename Tree, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath, typename Tag>
130 struct accumulate_value;
131
133 template<typename LeafNode, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath>
134 struct accumulate_value<LeafNode,Functor,Reduction,ParentChildReduction,current_value,TreePath,LeafNodeTag>
135 {
136
137 typedef typename Functor::result_type result_type;
138
139 static const result_type result =
140
141 accumulate_node_helper<LeafNode,Functor,Reduction,current_value,TreePath,Functor::template doVisit<LeafNode,TreePath>::value>::result;
142
143 };
144
146 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>
147 struct accumulate_over_children
148 {
149
150 typedef typename Functor::result_type result_type;
151
152 typedef decltype(push_back(TreePath{},index_constant<i>{})) child_tree_path;
153
154 typedef typename Node::template Child<i>::Type child;
155
156 static const result_type child_result = accumulate_value<child,Functor,Reduction,ParentChildReduction,current_value,child_tree_path,NodeTag<child>>::result;
157
158 static const result_type result = accumulate_over_children<Node,Functor,Reduction,ParentChildReduction,child_result,TreePath,i+1,n>::result;
159
160 };
161
163 template<typename Node, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath, std::size_t n>
164 struct accumulate_over_children<Node,Functor,Reduction,ParentChildReduction,current_value,TreePath,n,n>
165 {
166
167 typedef typename Functor::result_type result_type;
168
169 static const result_type result = current_value;
170
171 };
172
175 template<typename Node, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath>
176 struct accumulate_value_generic_composite_node
177 {
178
179 typedef typename Functor::result_type result_type;
180
181 static const result_type child_result = accumulate_over_children<Node,Functor,Reduction,ParentChildReduction,current_value,TreePath,0,StaticDegree<Node>::value>::result;
182
183 static const result_type result =
184 accumulate_node_helper<Node,Functor,ParentChildReduction,child_result,TreePath,Functor::template doVisit<Node,TreePath>::value>::result;
185
186
187 };
188
190 template<typename PowerNode, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath>
191 struct accumulate_value<PowerNode,Functor,Reduction,ParentChildReduction,current_value,TreePath,PowerNodeTag>
192 : public accumulate_value_generic_composite_node<PowerNode,Functor,Reduction,ParentChildReduction,current_value,TreePath>
193 {};
194
196 template<typename CompositeNode, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath>
197 struct accumulate_value<CompositeNode,Functor,Reduction,ParentChildReduction,current_value,TreePath,CompositeNodeTag>
198 : public accumulate_value_generic_composite_node<CompositeNode,Functor,Reduction,ParentChildReduction,current_value,TreePath>
199 {};
200
201 } // anonymous namespace
202
204
260 template<typename Tree, typename Functor, typename Reduction, typename Functor::result_type startValue, typename ParentChildReduction = Reduction>
261 struct AccumulateValue
262 {
263
265 typedef typename Functor::result_type result_type;
266
268 static const result_type result = accumulate_value<Tree,Functor,Reduction,ParentChildReduction,startValue,HybridTreePath<>,NodeTag<Tree>>::result;
269
270 };
271
274 struct flattened_reduction;
275
278 struct bottom_up_reduction;
279
280 namespace {
281
282 // implementation of the traversal algorithm
283
286 template<typename Node, typename Functor, typename Reduction, typename current_type, typename TreePath, bool doVisit>
287 struct accumulate_type_node_helper
288 {
289
290 typedef current_type type;
291
292 };
293
295 template<typename Node, typename Functor, typename Reduction, typename current_type, typename TreePath>
296 struct accumulate_type_node_helper<Node,Functor,Reduction,current_type,TreePath,true>
297 {
298
299 typedef typename Reduction::template reduce<
300 current_type,
301 typename Functor::template visit<
302 Node,
303 TreePath
304 >::type
305 >::type type;
306
307 };
308
310 template<typename Tree, typename Policy, typename current_type, typename TreePath, typename Tag>
311 struct accumulate_type;
312
314 template<typename LeafNode, typename Policy, typename current_type, typename TreePath>
315 struct accumulate_type<LeafNode,Policy,current_type,TreePath,LeafNodeTag>
316 {
317
318 typedef typename accumulate_type_node_helper<
319 LeafNode,
320 typename Policy::functor,
321 typename Policy::sibling_reduction,
322 current_type,
323 TreePath,
324 Policy::functor::template doVisit<
325 LeafNode,
326 TreePath>::value
327 >::type type;
328
329 };
330
331
334 template<typename current_type, typename tree_path, typename start_type, typename reduction_strategy>
335 struct propagate_type_down_tree;
336
338 template<typename current_type, typename tree_path, typename start_type>
339 struct propagate_type_down_tree<
340 current_type,
341 tree_path,
342 start_type,
343 bottom_up_reduction
344 >
345 {
346 typedef current_type type;
347 };
348
350 template<typename current_type, typename tree_path, typename start_type>
351 struct propagate_type_down_tree<
352 current_type,
353 tree_path,
354 start_type,
355 flattened_reduction
356 >
357 {
358 typedef typename std::conditional<
359 TreePathBack<tree_path>::value == 0,
360 start_type,
361 current_type
362 >::type type;
363 };
364
365
367 template<typename Node, typename Policy, typename current_type, typename TreePath, std::size_t i, std::size_t n>
368 struct accumulate_type_over_children
369 {
370
371 typedef decltype(push_back(TreePath{},index_constant<i>{})) child_tree_path;
372
373 typedef typename Node::template Child<i>::Type child;
374
375 typedef typename accumulate_type<
376 child,
377 Policy,
378 // apply reduction choice (flat / hierarchic)
379 typename propagate_type_down_tree<
380 current_type,
381 child_tree_path,
382 typename Policy::start_type,
383 typename Policy::reduction_strategy
384 >::type,
385 child_tree_path,
386 NodeTag<child>
387 >::type child_result_type;
388
389 typedef typename accumulate_type_over_children<
390 Node,
391 Policy,
392 child_result_type,
393 TreePath,
394 i+1,
395 n
396 >::type type;
397
398 };
399
401 template<typename Node, typename Policy, typename current_type, typename TreePath, std::size_t n>
402 struct accumulate_type_over_children<Node,Policy,current_type,TreePath,n,n>
403 {
404
405 typedef current_type type;
406
407 };
408
409
412 template<typename Node, typename Policy, typename current_type, typename TreePath>
413 struct accumulate_type_generic_composite_node
414 {
415
416 typedef typename accumulate_type_over_children<
417 Node,
418 Policy,
419 current_type,
420 TreePath,
421 0,
422 StaticDegree<Node>::value
423 >::type children_result_type;
424
425 typedef typename accumulate_type_node_helper<
426 Node,
427 typename Policy::functor,
428 typename Policy::parent_child_reduction,
429 children_result_type,
430 TreePath,
431 Policy::functor::template doVisit<
432 Node,
433 TreePath
434 >::value
435 >::type type;
436
437 };
438
440 template<typename PowerNode, typename Policy, typename current_type, typename TreePath>
441 struct accumulate_type<PowerNode,Policy,current_type,TreePath,PowerNodeTag>
442 : public accumulate_type_generic_composite_node<PowerNode,Policy,current_type,TreePath>
443 {};
444
446 template<typename CompositeNode, typename Policy, typename current_type, typename TreePath>
447 struct accumulate_type<CompositeNode,Policy,current_type,TreePath,CompositeNodeTag>
448 : public accumulate_type_generic_composite_node<CompositeNode,Policy,current_type,TreePath>
449 {};
450
451 } // anonymous namespace
452
453
461 template<
462 typename Functor,
463 typename Reduction,
464 typename StartType,
465 typename ParentChildReduction = Reduction,
466 typename ReductionAlgorithm = flattened_reduction
467 >
468 struct TypeAccumulationPolicy
469 {
470
498 typedef Functor functor;
499
519 typedef Reduction sibling_reduction;
520
527 typedef ParentChildReduction parent_child_reduction;
528
535 typedef StartType start_type;
536
541 typedef ReductionAlgorithm reduction_strategy;
542 };
543
544
546
554 template<typename Tree, typename Policy>
555 struct AccumulateType
556 {
557
559 typedef typename accumulate_type<
560 Tree,
561 Policy,
562 typename Policy::start_type,
563 HybridTreePath<>,
564 NodeTag<Tree>
565 >::type type;
566
567 };
568
569
570
571
572
573 /***************************************************/
574
575 namespace Experimental {
576 namespace Impl {
577
579 template<class T, class TreePath, class V, class U,
580 std::enable_if_t<std::decay_t<T>::isLeaf, int> = 0>
581 auto hybridApplyToTree(T&& tree, TreePath treePath, V&& visitor, U&& current_val)
582 {
583 return visitor.leaf(tree, treePath, std::forward<U>(current_val));
584 }
585
587 template<class T, class TreePath, class V, class U,
588 std::enable_if_t<not std::decay_t<T>::isLeaf, int> = 0>
589 auto hybridApplyToTree(T&& tree, TreePath treePath, V&& visitor, U&& current_val)
590 {
591 using Tree = std::remove_reference_t<T>;
592 using Visitor = std::remove_reference_t<V>;
593 auto pre_val = visitor.pre(tree, treePath, std::forward<U>(current_val));
594
595 // check which type of traversal is supported by the tree
596 using allowDynamicTraversal = Dune::Std::is_detected<Detail::DynamicTraversalConcept,Tree>;
597 using allowStaticTraversal = Dune::Std::is_detected<Detail::StaticTraversalConcept,Tree>;
598
599 // the tree must support either dynamic or static traversal
600 static_assert(allowDynamicTraversal::value || allowStaticTraversal::value);
601
602 // the visitor may specify preferred dynamic traversal
603 using preferDynamicTraversal = std::bool_constant<Visitor::treePathType == TreePathType::dynamic>;
604
605 // declare rule that applies visitor and current value to a child i. Returns next value
606 auto apply_i = [&](auto&& value, const auto& i){
607 auto&& child = tree.child(i);
608 using Child = std::decay_t<decltype(child)>;
609
610 auto val_before = visitor.beforeChild(tree, child, treePath, i, std::move(value));
611
612 // visits between children
613 auto val_in = Hybrid::ifElse(
614 Hybrid::equal_to(i,Indices::_0),
615 [&](auto id){return std::move(val_before);},
616 [&](auto id){return visitor.in(tree, treePath, std::move(val_before));}
617 );
618
619 constexpr bool visitChild = Visitor::template VisitChild<Tree,Child,TreePath>::value;
620 auto val_visit = [&](){
621 if constexpr (visitChild) {
622 auto childTreePath = Dune::TypeTree::push_back(treePath, i);
623 return hybridApplyToTree(child, childTreePath, visitor, std::move(val_in));
624 }
625 else
626 return std::move(val_in);
627 }();
628
629 return visitor.afterChild(tree, child, treePath, i, std::move(val_visit));
630 };
631
632 // apply visitor to children
633 auto in_val = [&](){
634 if constexpr (allowStaticTraversal::value && not preferDynamicTraversal::value) {
635 // get list of static indices
636 auto indices = std::make_index_sequence<Tree::degree()>{};
637
638 // unfold apply_i left to right
639 return unpackIntegerSequence([&](auto... i) {
659 return left_fold(std::move(apply_i),std::move(pre_val), i...);
660 }, indices);
661
662 } else {
663 // unfold first child to get type
664 auto i_val = apply_i(std::move(pre_val),std::size_t{0});
665 // dynamically loop rest of the children to accumulate remindng values
666 for(std::size_t i = 1; i < tree.degree(); i++)
667 i_val = apply_i(i_val,i);
668 return i_val;
669 }
670 }();
671
672 return visitor.post(tree, treePath, in_val);
673 }
674
675 }
676
700 template<typename Tree, typename Visitor, typename Init>
701 auto hybridApplyToTree(Tree&& tree, Visitor&& visitor, Init&& init)
702 {
703 return Impl::hybridApplyToTree(tree, hybridTreePath(), visitor, init);
704 }
705
706 } // namespace Experimental
707
709 } // namespace TypeTree
710} //namespace Dune
711
712#endif // DUNE_TYPETREE_ACCUMULATE_STATIC_HH
typetraits.hh
Traits for type conversions and type information.
Dune::Indices::_0
constexpr index_constant< 0 > _0
Compile time index with value 0.
Definition: indices.hh:52
Dune::unpackIntegerSequence
decltype(auto) constexpr unpackIntegerSequence(F &&f, std::integer_sequence< I, i... > sequence)
Unpack an std::integer_sequence<I,i...> to std::integral_constant<I,i>...
Definition: indices.hh:124
Dune::Std::is_detected
typename detected_or< nonesuch, Op, Args... >::value_t is_detected
Detects whether Op<Args...> is valid.
Definition: type_traits.hh:145
Dune::Hybrid::equal_to
constexpr auto equal_to
Function object for performing equality comparison.
Definition: hybridutilities.hh:572
Dune::Hybrid::ifElse
decltype(auto) ifElse(const Condition &condition, IfFunc &&ifFunc, ElseFunc &&elseFunc)
A conditional expression.
Definition: hybridutilities.hh:344
Dune::TypeTree::degree
std::size_t degree(const Node &node)
Returns the degree of node as run time information.
Definition: nodeinterface.hh:79
Dune::TypeTree::NodeTag
typename std::decay_t< Node >::NodeTag NodeTag
Returns the node tag of the given Node.
Definition: nodeinterface.hh:70
Dune::TypeTree::push_back
constexpr HybridTreePath< T..., std::size_t > push_back(const HybridTreePath< T... > &tp, std::size_t i)
Appends a run time index to a HybridTreePath.
Definition: treepath.hh:416
Dune::TypeTree::hybridTreePath
constexpr auto hybridTreePath(const T &... t)
Constructs a new HybridTreePath from the given indices.
Definition: treepath.hh:312
Dune::TypeTree::treePath
constexpr auto treePath(const T &... t)
Constructs a new HybridTreePath from the given indices.
Definition: treepath.hh:326
Dune::TypeTree::Child
typename impl::_Child< Node, indices... >::type Child
Template alias for the type of a child node given by a list of child indices.
Definition: childextraction.hh:225
Dune::TypeTree::child
ImplementationDefined child(Node &&node, Indices... indices)
Extracts the child of a node given by a sequence of compile-time and run-time indices.
Definition: childextraction.hh:128
Dune
Dune namespace.
Definition: alignedallocator.hh:13
Dune::push_back
constexpr std::integer_sequence< T, II..., T(IN)> push_back(std::integer_sequence< T, II... >, std::integral_constant< T, IN >={})
Append an index IN to the back of the sequence.
Definition: integersequence.hh:69
std
STL namespace.
Dune::TypeTree::AccumulateType
Statically accumulate a type over the nodes of a TypeTree.
Definition: accumulate_static.hh:556
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:565
Dune::TypeTree::AccumulateValue
Statically accumulate a value over the nodes of a TypeTree.
Definition: accumulate_static.hh:262
Dune::TypeTree::AccumulateValue::result_type
Functor::result_type result_type
The result type of the computation.
Definition: accumulate_static.hh:265
Dune::TypeTree::AccumulateValue::result
static const result_type result
The accumulated result of the computation.
Definition: accumulate_static.hh:268
Dune::TypeTree::TypeAccumulationPolicy
Definition: accumulate_static.hh:469
Dune::TypeTree::TypeAccumulationPolicy::parent_child_reduction
ParentChildReduction parent_child_reduction
Definition: accumulate_static.hh:527
Dune::TypeTree::TypeAccumulationPolicy::functor
Functor functor
Definition: accumulate_static.hh:498
Dune::TypeTree::TypeAccumulationPolicy::start_type
StartType start_type
Definition: accumulate_static.hh:535
Dune::TypeTree::TypeAccumulationPolicy::reduction_strategy
ReductionAlgorithm reduction_strategy
Definition: accumulate_static.hh:541
Dune::TypeTree::TypeAccumulationPolicy::sibling_reduction
Reduction sibling_reduction
Definition: accumulate_static.hh:519
Dune::TypeTree::and_
Statically combine two values of type result_type using &&.
Definition: accumulate_static.hh:38
Dune::TypeTree::max
Statically combine two values of type result_type by returning their maximum.
Definition: accumulate_static.hh:93
Dune::TypeTree::min
Statically combine two values of type result_type by returning their minimum.
Definition: accumulate_static.hh:82
Dune::TypeTree::minus
Statically combine two values of type result_type using -.
Definition: accumulate_static.hh:60
Dune::TypeTree::multiply
Statically combine two values of type result_type using *.
Definition: accumulate_static.hh:71
Dune::TypeTree::or_
Statically combine two values of type result_type using ||.
Definition: accumulate_static.hh:27
Dune::TypeTree::plus
Statically combine two values of type result_type using +.
Definition: accumulate_static.hh:49
Creative Commons License   |  Legal Statements / Impressum  |  Hosted by TU Dresden  |  generated with Hugo v0.111.3 (Nov 12, 23:30, 2024)