Dune Core Modules (2.8.0)

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
4#ifndef DUNE_TYPETREE_ACCUMULATE_STATIC_HH
5#define DUNE_TYPETREE_ACCUMULATE_STATIC_HH
6
8#include <dune/typetree/nodeinterface.hh>
9#include <dune/typetree/nodetags.hh>
10#include <dune/typetree/treepath.hh>
11
12
13namespace Dune {
14 namespace TypeTree {
15
22 template<typename result_type>
23 struct or_
24 {
25 template<result_type r1, result_type r2>
26 struct reduce
27 {
28 static const result_type result = r1 || r2;
29 };
30 };
31
33 template<typename result_type>
34 struct and_
35 {
36 template<result_type r1, result_type r2>
37 struct reduce
38 {
39 static const result_type result = r1 && r2;
40 };
41 };
42
44 template<typename result_type>
45 struct plus
46 {
47 template<result_type r1, result_type r2>
48 struct reduce
49 {
50 static const result_type result = r1 + r2;
51 };
52 };
53
55 template<typename result_type>
56 struct minus
57 {
58 template<result_type r1, result_type r2>
59 struct reduce
60 {
61 static const result_type result = r1 - r2;
62 };
63 };
64
66 template<typename result_type>
67 struct multiply
68 {
69 template<result_type r1, result_type r2>
70 struct reduce
71 {
72 static const result_type result = r1 * r2;
73 };
74 };
75
77 template<typename result_type>
78 struct min
79 {
80 template<result_type r1, result_type r2>
81 struct reduce
82 {
83 static const result_type result = r1 < r2 ? r1 : r2;
84 };
85 };
86
88 template<typename result_type>
89 struct max
90 {
91 template<result_type r1, result_type r2>
92 struct reduce
93 {
94 static const result_type result = r1 > r2 ? r1 : r2;
95 };
96 };
97
98
99 namespace {
100
101 // implementation of the traversal algorithm
102
104 template<typename Node, typename Functor, typename Reduction, typename Functor::result_type current_value, typename TreePath, bool doVisit>
105 struct accumulate_node_helper
106 {
107
108 typedef typename Functor::result_type result_type;
109
110 static const result_type result = current_value;
111
112 };
113
115 template<typename Node, typename Functor, typename Reduction, typename Functor::result_type current_value, typename TreePath>
116 struct accumulate_node_helper<Node,Functor,Reduction,current_value,TreePath,true>
117 {
118
119 typedef typename Functor::result_type result_type;
120
121 static const result_type result = Reduction::template reduce<current_value,Functor::template visit<Node,TreePath>::result>::result;
122
123 };
124
126 template<typename Tree, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath, typename Tag>
127 struct accumulate_value;
128
130 template<typename LeafNode, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath>
131 struct accumulate_value<LeafNode,Functor,Reduction,ParentChildReduction,current_value,TreePath,LeafNodeTag>
132 {
133
134 typedef typename Functor::result_type result_type;
135
136 static const result_type result =
137
138 accumulate_node_helper<LeafNode,Functor,Reduction,current_value,TreePath,Functor::template doVisit<LeafNode,TreePath>::value>::result;
139
140 };
141
143 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>
144 struct accumulate_over_children
145 {
146
147 typedef typename Functor::result_type result_type;
148
149 typedef decltype(push_back(TreePath{},index_constant<i>{})) child_tree_path;
150
151 typedef typename Node::template Child<i>::Type child;
152
153 static const result_type child_result = accumulate_value<child,Functor,Reduction,ParentChildReduction,current_value,child_tree_path,NodeTag<child>>::result;
154
155 static const result_type result = accumulate_over_children<Node,Functor,Reduction,ParentChildReduction,child_result,TreePath,i+1,n>::result;
156
157 };
158
160 template<typename Node, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath, std::size_t n>
161 struct accumulate_over_children<Node,Functor,Reduction,ParentChildReduction,current_value,TreePath,n,n>
162 {
163
164 typedef typename Functor::result_type result_type;
165
166 static const result_type result = current_value;
167
168 };
169
172 template<typename Node, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath>
173 struct accumulate_value_generic_composite_node
174 {
175
176 typedef typename Functor::result_type result_type;
177
178 static const result_type child_result = accumulate_over_children<Node,Functor,Reduction,ParentChildReduction,current_value,TreePath,0,StaticDegree<Node>::value>::result;
179
180 static const result_type result =
181 accumulate_node_helper<Node,Functor,ParentChildReduction,child_result,TreePath,Functor::template doVisit<Node,TreePath>::value>::result;
182
183
184 };
185
187 template<typename PowerNode, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath>
188 struct accumulate_value<PowerNode,Functor,Reduction,ParentChildReduction,current_value,TreePath,PowerNodeTag>
189 : public accumulate_value_generic_composite_node<PowerNode,Functor,Reduction,ParentChildReduction,current_value,TreePath>
190 {};
191
193 template<typename CompositeNode, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath>
194 struct accumulate_value<CompositeNode,Functor,Reduction,ParentChildReduction,current_value,TreePath,CompositeNodeTag>
195 : public accumulate_value_generic_composite_node<CompositeNode,Functor,Reduction,ParentChildReduction,current_value,TreePath>
196 {};
197
198 } // anonymous namespace
199
201
257 template<typename Tree, typename Functor, typename Reduction, typename Functor::result_type startValue, typename ParentChildReduction = Reduction>
259 {
260
262 typedef typename Functor::result_type result_type;
263
265 static const result_type result = accumulate_value<Tree,Functor,Reduction,ParentChildReduction,startValue,HybridTreePath<>,NodeTag<Tree>>::result;
266
267 };
268
271 struct flattened_reduction;
272
275 struct bottom_up_reduction;
276
277 namespace {
278
279 // implementation of the traversal algorithm
280
283 template<typename Node, typename Functor, typename Reduction, typename current_type, typename TreePath, bool doVisit>
284 struct accumulate_type_node_helper
285 {
286
287 typedef current_type type;
288
289 };
290
292 template<typename Node, typename Functor, typename Reduction, typename current_type, typename TreePath>
293 struct accumulate_type_node_helper<Node,Functor,Reduction,current_type,TreePath,true>
294 {
295
296 typedef typename Reduction::template reduce<
297 current_type,
298 typename Functor::template visit<
299 Node,
300 TreePath
301 >::type
302 >::type type;
303
304 };
305
307 template<typename Tree, typename Policy, typename current_type, typename TreePath, typename Tag>
308 struct accumulate_type;
309
311 template<typename LeafNode, typename Policy, typename current_type, typename TreePath>
312 struct accumulate_type<LeafNode,Policy,current_type,TreePath,LeafNodeTag>
313 {
314
315 typedef typename accumulate_type_node_helper<
316 LeafNode,
317 typename Policy::functor,
318 typename Policy::sibling_reduction,
319 current_type,
320 TreePath,
321 Policy::functor::template doVisit<
322 LeafNode,
323 TreePath>::value
324 >::type type;
325
326 };
327
328
331 template<typename current_type, typename tree_path, typename start_type, typename reduction_strategy>
332 struct propagate_type_down_tree;
333
335 template<typename current_type, typename tree_path, typename start_type>
336 struct propagate_type_down_tree<
337 current_type,
338 tree_path,
339 start_type,
340 bottom_up_reduction
341 >
342 {
343 typedef current_type type;
344 };
345
347 template<typename current_type, typename tree_path, typename start_type>
348 struct propagate_type_down_tree<
349 current_type,
350 tree_path,
351 start_type,
352 flattened_reduction
353 >
354 {
355 typedef typename std::conditional<
356 TreePathBack<tree_path>::value == 0,
357 start_type,
358 current_type
359 >::type type;
360 };
361
362
364 template<typename Node, typename Policy, typename current_type, typename TreePath, std::size_t i, std::size_t n>
365 struct accumulate_type_over_children
366 {
367
368 typedef decltype(push_back(TreePath{},index_constant<i>{})) child_tree_path;
369
370 typedef typename Node::template Child<i>::Type child;
371
372 typedef typename accumulate_type<
373 child,
374 Policy,
375 // apply reduction choice (flat / hierarchic)
376 typename propagate_type_down_tree<
377 current_type,
378 child_tree_path,
379 typename Policy::start_type,
380 typename Policy::reduction_strategy
381 >::type,
382 child_tree_path,
384 >::type child_result_type;
385
386 typedef typename accumulate_type_over_children<
387 Node,
388 Policy,
389 child_result_type,
390 TreePath,
391 i+1,
392 n
393 >::type type;
394
395 };
396
398 template<typename Node, typename Policy, typename current_type, typename TreePath, std::size_t n>
399 struct accumulate_type_over_children<Node,Policy,current_type,TreePath,n,n>
400 {
401
402 typedef current_type type;
403
404 };
405
406
409 template<typename Node, typename Policy, typename current_type, typename TreePath>
410 struct accumulate_type_generic_composite_node
411 {
412
413 typedef typename accumulate_type_over_children<
414 Node,
415 Policy,
416 current_type,
417 TreePath,
418 0,
419 StaticDegree<Node>::value
420 >::type children_result_type;
421
422 typedef typename accumulate_type_node_helper<
423 Node,
424 typename Policy::functor,
425 typename Policy::parent_child_reduction,
426 children_result_type,
427 TreePath,
428 Policy::functor::template doVisit<
429 Node,
430 TreePath
431 >::value
432 >::type type;
433
434 };
435
437 template<typename PowerNode, typename Policy, typename current_type, typename TreePath>
438 struct accumulate_type<PowerNode,Policy,current_type,TreePath,PowerNodeTag>
439 : public accumulate_type_generic_composite_node<PowerNode,Policy,current_type,TreePath>
440 {};
441
443 template<typename CompositeNode, typename Policy, typename current_type, typename TreePath>
444 struct accumulate_type<CompositeNode,Policy,current_type,TreePath,CompositeNodeTag>
445 : public accumulate_type_generic_composite_node<CompositeNode,Policy,current_type,TreePath>
446 {};
447
448 } // anonymous namespace
449
450
458 template<
459 typename Functor,
460 typename Reduction,
461 typename StartType,
462 typename ParentChildReduction = Reduction,
463 typename ReductionAlgorithm = flattened_reduction
464 >
466 {
467
495 typedef Functor functor;
496
516 typedef Reduction sibling_reduction;
517
524 typedef ParentChildReduction parent_child_reduction;
525
532 typedef StartType start_type;
533
538 typedef ReductionAlgorithm reduction_strategy;
539 };
540
541
543
551 template<typename Tree, typename Policy>
553 {
554
556 typedef typename accumulate_type<
557 Tree,
558 Policy,
559 typename Policy::start_type,
562 >::type type;
563
564 };
565
566
567
568
569
570 /***************************************************/
571
572 namespace Experimental {
573 namespace Impl {
574
576 template<class T, class TreePath, class V, class U,
577 std::enable_if_t<std::decay_t<T>::isLeaf, int> = 0>
578 auto hybridApplyToTree(T&& tree, TreePath treePath, V&& visitor, U&& current_val)
579 {
580 return visitor.leaf(tree, treePath, std::forward<U>(current_val));
581 }
582
584 template<class T, class TreePath, class V, class U,
585 std::enable_if_t<not std::decay_t<T>::isLeaf, int> = 0>
586 auto hybridApplyToTree(T&& tree, TreePath treePath, V&& visitor, U&& current_val)
587 {
588 using Tree = std::remove_reference_t<T>;
589 using Visitor = std::remove_reference_t<V>;
590 auto pre_val = visitor.pre(tree, treePath, std::forward<U>(current_val));
591
592 // check which type of traversal is supported by the tree
595
596 // the tree must support either dynamic or static traversal
597 static_assert(allowDynamicTraversal::value || allowStaticTraversal::value);
598
599 // the visitor may specify preferred dynamic traversal
600 using preferDynamicTraversal = std::bool_constant<Visitor::treePathType == TreePathType::dynamic>;
601
602 // declare rule that applies visitor and current value to a child i. Returns next value
603 auto apply_i = [&](auto&& value, const auto& i){
604 auto&& child = tree.child(i);
605 using Child = std::decay_t<decltype(child)>;
606
607 auto val_before = visitor.beforeChild(tree, child, treePath, i, std::move(value));
608
609 // visits between children
610 auto val_in = Hybrid::ifElse(
612 [&](auto id){return std::move(val_before);},
613 [&](auto id){return visitor.in(tree, treePath, std::move(val_before));}
614 );
615
616 constexpr bool visitChild = Visitor::template VisitChild<Tree,Child,TreePath>::value;
617 auto val_visit = [&](){
618 if constexpr (visitChild) {
619 auto childTreePath = Dune::TypeTree::push_back(treePath, i);
620 return hybridApplyToTree(child, childTreePath, visitor, std::move(val_in));
621 }
622 else
623 return std::move(val_in);
624 }();
625
626 return visitor.afterChild(tree, child, treePath, i, std::move(val_visit));
627 };
628
629 // apply visitor to children
630 auto in_val = [&](){
631 if constexpr (allowStaticTraversal::value && not preferDynamicTraversal::value) {
632 // get list of static indices
633 auto indices = std::make_index_sequence<Tree::degree()>{};
634
635 // unfold apply_i left to right
636 return unpackIntegerSequence([&](auto... i) {
656 return left_fold(std::move(apply_i),std::move(pre_val), i...);
657 }, indices);
658
659 } else {
660 // unfold first child to get type
661 auto i_val = apply_i(std::move(pre_val),std::size_t{0});
662 // dynamically loop rest of the children to accumulate remindng values
663 for(std::size_t i = 1; i < tree.degree(); i++)
664 i_val = apply_i(i_val,i);
665 return i_val;
666 }
667 }();
668
669 return visitor.post(tree, treePath, in_val);
670 }
671
672 }
673
697 template<typename Tree, typename Visitor, typename Init>
698 auto hybridApplyToTree(Tree&& tree, Visitor&& visitor, Init&& init)
699 {
700 return Impl::hybridApplyToTree(tree, hybridTreePath(), visitor, init);
701 }
702
703 } // namespace Experimental
704
706 } // namespace TypeTree
707} //namespace Dune
708
709#endif // DUNE_TYPETREE_ACCUMULATE_STATIC_HH
Traits for type conversions and type information.
decltype(auto) 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:123
constexpr index_constant< 0 > _0
Compile time index with value 0.
Definition: indices.hh:51
typename detected_or< nonesuch, Op, Args... >::value_t is_detected
Detects whether Op<Args...> is valid.
Definition: type_traits.hh:326
constexpr auto equals(T1 &&t1, T2 &&t2)
Equality comparison.
Definition: hybridutilities.hh:400
decltype(auto) ifElse(const Condition &condition, IfFunc &&ifFunc, ElseFunc &&elseFunc)
A conditional expression.
Definition: hybridutilities.hh:354
std::size_t degree(const Node &node)
Returns the degree of node as run time information.
Definition: nodeinterface.hh:76
typename std::decay_t< Node >::NodeTag NodeTag
Returns the node tag of the given Node.
Definition: nodeinterface.hh:67
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:278
constexpr HybridTreePath< T... > hybridTreePath(const T &... t)
Constructs a new HybridTreePath from the given indices.
Definition: treepath.hh:177
constexpr HybridTreePath< T... > treePath(const T &... t)
Constructs a new HybridTreePath from the given indices.
Definition: treepath.hh:188
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:223
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:126
Dune namespace.
Definition: alignedallocator.hh:11
STL namespace.
Statically accumulate a type over the nodes of a TypeTree.
Definition: accumulate_static.hh:553
accumulate_type< Tree, Policy, typenamePolicy::start_type, HybridTreePath<>, NodeTag< Tree > >::type type
The accumulated result of the computation.
Definition: accumulate_static.hh:562
Statically accumulate a value over the nodes of a TypeTree.
Definition: accumulate_static.hh:259
Functor::result_type result_type
The result type of the computation.
Definition: accumulate_static.hh:262
static const result_type result
The accumulated result of the computation.
Definition: accumulate_static.hh:265
Definition: accumulate_static.hh:466
ParentChildReduction parent_child_reduction
Definition: accumulate_static.hh:524
Functor functor
Definition: accumulate_static.hh:495
StartType start_type
Definition: accumulate_static.hh:532
ReductionAlgorithm reduction_strategy
Definition: accumulate_static.hh:538
Reduction sibling_reduction
Definition: accumulate_static.hh:516
Statically combine two values of type result_type using &&.
Definition: accumulate_static.hh:35
Statically combine two values of type result_type by returning their maximum.
Definition: accumulate_static.hh:90
Statically combine two values of type result_type by returning their minimum.
Definition: accumulate_static.hh:79
Statically combine two values of type result_type using -.
Definition: accumulate_static.hh:57
Statically combine two values of type result_type using *.
Definition: accumulate_static.hh:68
Statically combine two values of type result_type using ||.
Definition: accumulate_static.hh:24
Statically combine two values of type result_type using +.
Definition: accumulate_static.hh:46
Creative Commons License   |  Legal Statements / Impressum  |  Hosted by TU Dresden  |  generated with Hugo v0.111.3 (Nov 12, 23:30, 2024)