dune-typetree  2.4.0-rc1
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>
10 
11 
12 namespace Dune {
13  namespace TypeTree {
14 
20  template<typename result_type>
22  struct or_
23  {
24  template<result_type r1, result_type r2>
25  struct reduce
26  {
27  static const result_type result = r1 || r2;
28  };
29  };
30 
32  template<typename result_type>
33  struct and_
34  {
35  template<result_type r1, result_type r2>
36  struct reduce
37  {
38  static const result_type result = r1 && r2;
39  };
40  };
41 
43  template<typename result_type>
44  struct plus
45  {
46  template<result_type r1, result_type r2>
47  struct reduce
48  {
49  static const result_type result = r1 + r2;
50  };
51  };
52 
54  template<typename result_type>
55  struct minus
56  {
57  template<result_type r1, result_type r2>
58  struct reduce
59  {
60  static const result_type result = r1 - r2;
61  };
62  };
63 
65  template<typename result_type>
66  struct multiply
67  {
68  template<result_type r1, result_type r2>
69  struct reduce
70  {
71  static const result_type result = r1 * r2;
72  };
73  };
74 
76  template<typename result_type>
77  struct min
78  {
79  template<result_type r1, result_type r2>
80  struct reduce
81  {
82  static const result_type result = r1 < r2 ? r1 : r2;
83  };
84  };
85 
87  template<typename result_type>
88  struct max
89  {
90  template<result_type r1, result_type r2>
91  struct reduce
92  {
93  static const result_type result = r1 > r2 ? r1 : r2;
94  };
95  };
96 
97 
98  namespace {
99 
100  // implementation of the traversal algoritm
101 
103  template<typename Node, typename Functor, typename Reduction, typename Functor::result_type current_value, typename TreePath, bool doVisit>
104  struct accumulate_node_helper
105  {
106 
107  typedef typename Functor::result_type result_type;
108 
109  static const result_type result = current_value;
110 
111  };
112 
114  template<typename Node, typename Functor, typename Reduction, typename Functor::result_type current_value, typename TreePath>
115  struct accumulate_node_helper<Node,Functor,Reduction,current_value,TreePath,true>
116  {
117 
118  typedef typename Functor::result_type result_type;
119 
120  static const result_type result = Reduction::template reduce<current_value,Functor::template visit<Node,TreePath>::result>::result;
121 
122  };
123 
125  template<typename Tree, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath, typename Tag>
126  struct accumulate_value;
127 
129  template<typename LeafNode, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath>
130  struct accumulate_value<LeafNode,Functor,Reduction,ParentChildReduction,current_value,TreePath,LeafNodeTag>
131  {
132 
133  typedef typename Functor::result_type result_type;
134 
135  static const result_type result =
136 
137  accumulate_node_helper<LeafNode,Functor,Reduction,current_value,TreePath,Functor::template doVisit<LeafNode,TreePath>::value>::result;
138 
139  };
140 
142  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>
143  struct accumulate_over_children
144  {
145 
146  typedef typename Functor::result_type result_type;
147 
148  typedef typename TreePathPushBack<TreePath,i>::type child_tree_path;
149 
150  typedef typename Node::template Child<i>::Type child;
151 
153 
155 
156  };
157 
159  template<typename Node, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath, std::size_t n>
160  struct accumulate_over_children<Node,Functor,Reduction,ParentChildReduction,current_value,TreePath,n,n>
161  {
162 
163  typedef typename Functor::result_type result_type;
164 
165  static const result_type result = current_value;
166 
167  };
168 
171  template<typename Node, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath>
172  struct accumulate_value_generic_composite_node
173  {
174 
175  typedef typename Functor::result_type result_type;
176 
178 
179  static const result_type result =
180  accumulate_node_helper<Node,Functor,ParentChildReduction,child_result,TreePath,Functor::template doVisit<Node,TreePath>::value>::result;
181 
182 
183  };
184 
186  template<typename PowerNode, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath>
187  struct accumulate_value<PowerNode,Functor,Reduction,ParentChildReduction,current_value,TreePath,PowerNodeTag>
188  : public accumulate_value_generic_composite_node<PowerNode,Functor,Reduction,ParentChildReduction,current_value,TreePath>
189  {};
190 
192  template<typename CompositeNode, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath>
193  struct accumulate_value<CompositeNode,Functor,Reduction,ParentChildReduction,current_value,TreePath,CompositeNodeTag>
194  : public accumulate_value_generic_composite_node<CompositeNode,Functor,Reduction,ParentChildReduction,current_value,TreePath>
195  {};
196 
197  } // anonymous namespace
198 
200 
256  template<typename Tree, typename Functor, typename Reduction, typename Functor::result_type startValue, typename ParentChildReduction = Reduction>
258  {
259 
261  typedef typename Functor::result_type result_type;
262 
264  static const result_type result = accumulate_value<Tree,Functor,Reduction,ParentChildReduction,startValue,TreePath<>,typename Tree::NodeTag>::result;
265 
266  };
267 
270  struct flattened_reduction;
271 
274  struct bottom_up_reduction;
275 
276  namespace {
277 
278  // implementation of the traversal algoritm
279 
282  template<typename Node, typename Functor, typename Reduction, typename current_type, typename TreePath, bool doVisit>
283  struct accumulate_type_node_helper
284  {
285 
286  typedef current_type type;
287 
288  };
289 
291  template<typename Node, typename Functor, typename Reduction, typename current_type, typename TreePath>
292  struct accumulate_type_node_helper<Node,Functor,Reduction,current_type,TreePath,true>
293  {
294 
295  typedef typename Reduction::template reduce<
296  current_type,
297  typename Functor::template visit<
298  Node,
299  TreePath
300  >::type
301  >::type type;
302 
303  };
304 
306  template<typename Tree, typename Policy, typename current_type, typename TreePath, typename Tag>
307  struct accumulate_type;
308 
310  template<typename LeafNode, typename Policy, typename current_type, typename TreePath>
311  struct accumulate_type<LeafNode,Policy,current_type,TreePath,LeafNodeTag>
312  {
313 
314  typedef typename accumulate_type_node_helper<
315  LeafNode,
316  typename Policy::functor,
317  typename Policy::sibling_reduction,
318  current_type,
319  TreePath,
320  Policy::functor::template doVisit<
321  LeafNode,
322  TreePath>::value
323  >::type type;
324 
325  };
326 
327 
330  template<typename current_type, typename tree_path, typename start_type, typename reduction_strategy>
331  struct propagate_type_down_tree;
332 
334  template<typename current_type, typename tree_path, typename start_type>
335  struct propagate_type_down_tree<
336  current_type,
337  tree_path,
338  start_type,
339  bottom_up_reduction
340  >
341  {
342  typedef current_type type;
343  };
344 
346  template<typename current_type, typename tree_path, typename start_type>
347  struct propagate_type_down_tree<
348  current_type,
349  tree_path,
350  start_type,
351  flattened_reduction
352  >
353  {
354  typedef typename Dune::conditional<
355  TreePathBack<tree_path>::value == 0,
356  start_type,
357  current_type
358  >::type type;
359  };
360 
361 
363  template<typename Node, typename Policy, typename current_type, typename TreePath, std::size_t i, std::size_t n>
364  struct accumulate_type_over_children
365  {
366 
367  typedef typename TreePathPushBack<TreePath,i>::type child_tree_path;
368 
369  typedef typename Node::template Child<i>::Type child;
370 
371  typedef typename accumulate_type<
372  child,
373  Policy,
374  // apply reduction choice (flat / hierarchic)
375  typename propagate_type_down_tree<
376  current_type,
377  child_tree_path,
378  typename Policy::start_type,
379  typename Policy::reduction_strategy
380  >::type,
381  child_tree_path,
382  typename child::NodeTag
383  >::type child_result_type;
384 
385  typedef typename accumulate_type_over_children<
386  Node,
387  Policy,
388  child_result_type,
389  TreePath,
390  i+1,
391  n
392  >::type type;
393 
394  };
395 
397  template<typename Node, typename Policy, typename current_type, typename TreePath, std::size_t n>
398  struct accumulate_type_over_children<Node,Policy,current_type,TreePath,n,n>
399  {
400 
401  typedef current_type type;
402 
403  };
404 
405 
408  template<typename Node, typename Policy, typename current_type, typename TreePath>
409  struct accumulate_type_generic_composite_node
410  {
411 
412  typedef typename accumulate_type_over_children<
413  Node,
414  Policy,
415  current_type,
416  TreePath,
417  0,
418  Node::CHILDREN
419  >::type children_result_type;
420 
421  typedef typename accumulate_type_node_helper<
422  Node,
423  typename Policy::functor,
424  typename Policy::parent_child_reduction,
425  children_result_type,
426  TreePath,
427  Policy::functor::template doVisit<
428  Node,
429  TreePath
430  >::value
431  >::type type;
432 
433  };
434 
436  template<typename PowerNode, typename Policy, typename current_type, typename TreePath>
437  struct accumulate_type<PowerNode,Policy,current_type,TreePath,PowerNodeTag>
438  : public accumulate_type_generic_composite_node<PowerNode,Policy,current_type,TreePath>
439  {};
440 
442  template<typename CompositeNode, typename Policy, typename current_type, typename TreePath>
443  struct accumulate_type<CompositeNode,Policy,current_type,TreePath,CompositeNodeTag>
444  : public accumulate_type_generic_composite_node<CompositeNode,Policy,current_type,TreePath>
445  {};
446 
447  } // anonymous namespace
448 
449 
457  template<
458  typename Functor,
459  typename Reduction,
460  typename StartType,
461  typename ParentChildReduction = Reduction,
462  typename ReductionAlgorithm = flattened_reduction
463  >
465  {
466 
494  typedef Functor functor;
495 
515  typedef Reduction sibling_reduction;
516 
523  typedef ParentChildReduction parent_child_reduction;
524 
531  typedef StartType start_type;
532 
537  typedef ReductionAlgorithm reduction_strategy;
538  };
539 
540 
542 
550  template<typename Tree, typename Policy>
552  {
553 
555  typedef typename accumulate_type<
556  Tree,
557  Policy,
558  typename Policy::start_type,
559  TreePath<>,
560  typename Tree::NodeTag
562 
563  };
564 
565 
567 
568  } // namespace TypeTree
569 } //namespace Dune
570 
571 #endif // DUNE_TYPETREE_ACCUMULATE_STATIC_HH
static const result_type result
Definition: accumulate_static.hh:27
Statically combine two values of type result_type by returning their maximum.
Definition: accumulate_static.hh:88
Statically accumulate a type over the nodes of a TypeTree.
Definition: accumulate_static.hh:551
ParentChildReduction parent_child_reduction
Definition: accumulate_static.hh:523
static const result_type result
Definition: accumulate_static.hh:60
Definition: accumulate_static.hh:12
Statically combine two values of type result_type using *.
Definition: accumulate_static.hh:66
Definition: accumulate_static.hh:69
Definition: accumulate_static.hh:25
Definition: accumulate_static.hh:80
static const result_type result
Definition: accumulate_static.hh:71
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:472
Statically combine two values of type result_type using -.
Definition: accumulate_static.hh:55
Definition: accumulate_static.hh:58
Definition: accumulate_static.hh:47
accumulate_type< Tree, Policy, typename Policy::start_type, TreePath<>, typename Tree::NodeTag >::type type
The accumulated result of the computation.
Definition: accumulate_static.hh:561
Definition: accumulate_static.hh:464
static const result_type result
Definition: accumulate_static.hh:109
Statically combine two values of type result_type using ||.
Definition: accumulate_static.hh:22
Type
Definition: treepath.hh:26
Statically combine two values of type result_type using &&.
Definition: accumulate_static.hh:33
Statically combine two values of type result_type by returning their minimum.
Definition: accumulate_static.hh:77
static const result_type result
Definition: accumulate_static.hh:82
static const result_type child_result
Definition: accumulate_static.hh:152
static const result_type result
The accumulated result of the computation.
Definition: accumulate_static.hh:264
Functor::result_type result_type
The result type of the computation.
Definition: accumulate_static.hh:261
static const result_type result
Definition: accumulate_static.hh:38
StartType start_type
Definition: accumulate_static.hh:531
Definition: accumulate_static.hh:36
ReductionAlgorithm reduction_strategy
Definition: accumulate_static.hh:537
Statically accumulate a value over the nodes of a TypeTree.
Definition: accumulate_static.hh:257
Definition: treepath.hh:30
Definition: accumulate_static.hh:91
Reduction sibling_reduction
Definition: accumulate_static.hh:515
static const result_type result
Definition: accumulate_static.hh:93
static const result_type result
Definition: accumulate_static.hh:49
Functor functor
Definition: accumulate_static.hh:494
Statically combine two values of type result_type using +.
Definition: accumulate_static.hh:44