dune-typetree  2.5-dev
accumulate_static.hh
Go to the documentation of this file.
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 
7 #include <dune/common/typetraits.hh>
11 
12 
13 namespace Dune {
14  namespace TypeTree {
15 
21  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 typename TreePathPushBack<TreePath,i>::type 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 
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,TreePath<>,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<
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 typename TreePathPushBack<TreePath,i>::type 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,
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,
560  TreePath<>,
563 
564  };
565 
566 
568 
569  } // namespace TypeTree
570 } //namespace Dune
571 
572 #endif // DUNE_TYPETREE_ACCUMULATE_STATIC_HH
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:179
Statically combine two values of type result_type using +.
Definition: accumulate_static.hh:45
Tag designating a composite node.
Definition: nodetags.hh:22
Functor functor
Definition: accumulate_static.hh:495
Definition: accumulate_static.hh:26
Statically accumulate a value over the nodes of a TypeTree.
Definition: accumulate_static.hh:258
ParentChildReduction parent_child_reduction
Definition: accumulate_static.hh:524
Definition: accumulate_static.hh:70
Collect k instances of type T within a dune-typetree.
Definition: powernode.hh:91
Statically combine two values of type result_type using -.
Definition: accumulate_static.hh:56
Definition: accumulate_static.hh:37
Tag designating a power node.
Definition: nodetags.hh:19
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:307
Definition: accumulate_static.hh:13
Definition: treepath.hh:75
Definition: accumulate_static.hh:465
Definition: accumulate_static.hh:81
Statically combine two values of type result_type using *.
Definition: accumulate_static.hh:67
Functor::result_type result_type
The result type of the computation.
Definition: accumulate_static.hh:262
static const result_type result
Definition: accumulate_static.hh:28
Statically accumulate a type over the nodes of a TypeTree.
Definition: accumulate_static.hh:552
Statically combine two values of type result_type by returning their maximum.
Definition: accumulate_static.hh:89
Reduction sibling_reduction
Definition: accumulate_static.hh:516
Statically combine two values of type result_type using ||.
Definition: accumulate_static.hh:23
Base class for leaf nodes in a dune-typetree.
Definition: leafnode.hh:24
accumulate_type< Tree, Policy, typename Policy::start_type, TreePath<>, NodeTag< Tree > >::type type
The accumulated result of the computation.
Definition: accumulate_static.hh:562
static const result_type result
Definition: accumulate_static.hh:110
static const result_type child_result
Definition: accumulate_static.hh:153
Definition: accumulate_static.hh:48
std::integral_constant< std::size_t, degree(static_cast< std::decay_t< Node > * >(nullptr), NodeTag< std::decay_t< Node >>()) > StaticDegree
Returns the statically known degree of the given Node type as a std::integral_constant.
Definition: nodeinterface.hh:105
Statically combine two values of type result_type using &&.
Definition: accumulate_static.hh:34
Tag designating a leaf node.
Definition: nodetags.hh:16
ReductionAlgorithm reduction_strategy
Definition: accumulate_static.hh:538
Statically combine two values of type result_type by returning their minimum.
Definition: accumulate_static.hh:78
Definition: treepath.hh:57
Definition: accumulate_static.hh:59
StartType start_type
Definition: accumulate_static.hh:532
Definition: treepath.hh:30
Base class for composite nodes based on variadic templates.
Definition: compositenode.hh:23
Definition: accumulate_static.hh:92
typename std::decay_t< Node >::NodeTag NodeTag
Returns the node tag of the given Node.
Definition: nodeinterface.hh:62
Type
Definition: treepath.hh:26