dune-typetree  2.3.1
treepath.hh
Go to the documentation of this file.
1 // -*- tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2 // vi: set et ts=8 sw=2 sts=2:
3 
4 #ifndef DUNE_TYPETREE_TREEPATH_HH
5 #define DUNE_TYPETREE_TREEPATH_HH
6 
7 #include <cstddef>
8 
9 #include <dune/common/documentation.hh>
10 #include <dune/common/static_assert.hh>
11 #include <dune/common/typetraits.hh>
12 
14 #include <dune/typetree/utility.hh>
15 
16 
17 namespace Dune {
18  namespace TypeTree {
19 
20 
24 
25  namespace TreePathType {
27  }
28 
29 #if HAVE_VARIADIC_TEMPLATES || DOXYGEN
30 
31  template<std::size_t... i>
32  struct TreePath {
33  typedef TreePath ViewType;
34  TreePath view() { return *this; }
35  TreePath mutablePath() { return *this; }
36  };
37 
38  template<typename>
39  struct TreePathSize;
40 
41  template<std::size_t... i>
42  struct TreePathSize<TreePath<i...> >
43  : public integral_constant<std::size_t, sizeof...(i)>
44  {};
45 
46  template<typename,std::size_t>
48 
49  template<std::size_t k, std::size_t... i>
50  struct TreePathPushBack<TreePath<i...>,k>
51  {
52  typedef TreePath<i...,k> type;
53  };
54 
55  template<typename,std::size_t>
57 
58  template<std::size_t k, std::size_t... i>
59  struct TreePathPushFront<TreePath<i...>,k>
60  {
61  typedef TreePath<k,i...> type;
62  };
63 
64  template<typename>
65  struct TreePathBack;
66 
67  // There is only a single element, so return that...
68  template<std::size_t k>
69  struct TreePathBack<TreePath<k> >
70  : public integral_constant<std::size_t,k>
71  {};
72 
73  // We need to explicitly provide two elements here, as
74  // the template argument pack would match the empty list
75  // and create a conflict with the single-element specialization.
76  // Here, we just shave off the first element and recursively
77  // instantiate ourselves.
78  template<std::size_t j, std::size_t k, std::size_t... l>
79  struct TreePathBack<TreePath<j,k,l...> >
80  : public TreePathBack<TreePath<k,l...> >
81  {};
82 
83  template<typename>
84  struct TreePathFront;
85 
86  template<std::size_t k, std::size_t... i>
87  struct TreePathFront<TreePath<k,i...> >
88  : public integral_constant<std::size_t,k>
89  {};
90 
91  template<typename, std::size_t...>
93 
94  template<std::size_t k, std::size_t... i>
95  struct TreePathPopBack<TreePath<k>,i...>
96  {
97  typedef TreePath<i...> type;
98  };
99 
100  template<std::size_t j,
101  std::size_t k,
102  std::size_t... l,
103  std::size_t... i>
104  struct TreePathPopBack<TreePath<j,k,l...>,i...>
105  : public TreePathPopBack<TreePath<k,l...>,i...,j>
106  {};
107 
108  template<typename>
110 
111  template<std::size_t k, std::size_t... i>
112  struct TreePathPopFront<TreePath<k,i...> >
113  {
114  typedef TreePath<i...> type;
115  };
116 
117  template<typename, typename>
119 
120  template<std::size_t... i, std::size_t... k>
121  struct TreePathConcat<TreePath<i...>,TreePath<k...> >
122  {
123  typedef TreePath<i...,k...> type;
124  };
125 
126  template<std::size_t... i>
127  void print_tree_path(std::ostream& os)
128  {}
129 
130  template<std::size_t k, std::size_t... i>
131  void print_tree_path(std::ostream& os)
132  {
133  os << k << " ";
134  print_tree_path<i...>(os);
135  }
136 
137  template<std::size_t... i>
138  std::ostream& operator<<(std::ostream& os, const TreePath<i...>& tp)
139  {
140  os << "TreePath< ";
141  print_tree_path<i...>(os);
142  os << ">";
143  return os;
144  }
145 
146 #else
147 
149 
153  static const std::size_t noChildIndex = ~std::size_t(0);
154 
156 
171  template<std::size_t i0 = noChildIndex, std::size_t i1 = noChildIndex,
172  std::size_t i2 = noChildIndex, std::size_t i3 = noChildIndex,
173  std::size_t i4 = noChildIndex, std::size_t i5 = noChildIndex,
174  std::size_t i6 = noChildIndex, std::size_t i7 = noChildIndex,
175  std::size_t i8 = noChildIndex, std::size_t i9 = noChildIndex>
176  class TreePath {
177  dune_static_assert(i0 == noChildIndex ? i1 == noChildIndex : true,
178  "Only trailing indices my be noChildIndex");
179  dune_static_assert(i1 == noChildIndex ? i2 == noChildIndex : true,
180  "Only trailing indices my be noChildIndex");
181  dune_static_assert(i2 == noChildIndex ? i3 == noChildIndex : true,
182  "Only trailing indices my be noChildIndex");
183  dune_static_assert(i3 == noChildIndex ? i4 == noChildIndex : true,
184  "Only trailing indices my be noChildIndex");
185  dune_static_assert(i4 == noChildIndex ? i5 == noChildIndex : true,
186  "Only trailing indices my be noChildIndex");
187  dune_static_assert(i5 == noChildIndex ? i6 == noChildIndex : true,
188  "Only trailing indices my be noChildIndex");
189  dune_static_assert(i6 == noChildIndex ? i7 == noChildIndex : true,
190  "Only trailing indices my be noChildIndex");
191  dune_static_assert(i7 == noChildIndex ? i8 == noChildIndex : true,
192  "Only trailing indices my be noChildIndex");
193  dune_static_assert(i8 == noChildIndex ? i9 == noChildIndex : true,
194  "Only trailing indices my be noChildIndex");
195 
196  typedef TreePath ViewType;
197  TreePath view() { return *this; }
198  TreePath mutablePath() { return *this; }
199 
200  };
201 
202  //
203  // The following classes operate on the front of a TreePath: They extract,
204  // remove or prepend the first element.
205  //
206 
208  template<class TP>
209  class TreePathPopFront {
210  dune_static_assert(AlwaysTrue<TP>::value,
211  "TreePathPopFront works on TreePaths only");
212  public:
214  typedef ImplementationDefined type;
215  };
216 
217 #ifndef DOXYGEN
218  template<std::size_t i0, std::size_t i1, std::size_t i2, std::size_t i3,
219  std::size_t i4, std::size_t i5, std::size_t i6, std::size_t i7,
220  std::size_t i8, std::size_t i9>
221  struct TreePathPopFront<TreePath<i0, i1, i2, i3, i4, i5, i6, i7, i8, i9> >
222  {
223  dune_static_assert(i0 != noChildIndex,
224  "Can't pop first element from an empty TreePath");
225  typedef TreePath<i1, i2, i3, i4, i5, i6, i7, i8, i9> type;
226  };
227 #endif // DOXYGEN
228 
230  template<class TP>
231  class TreePathFront {
232  dune_static_assert(AlwaysTrue<TP>::value,
233  "TreePathPopFront works on TreePaths only");
234  public:
236  static const std::size_t value = implementationDefined;
237  };
238 
239 #ifndef DOXYGEN
240  template<std::size_t i0, std::size_t i1, std::size_t i2, std::size_t i3,
241  std::size_t i4, std::size_t i5, std::size_t i6, std::size_t i7,
242  std::size_t i8, std::size_t i9>
243  class TreePathFront<TreePath<i0, i1, i2, i3, i4, i5, i6, i7, i8, i9> > :
244  public integral_constant<std::size_t, i0>
245  {
246  dune_static_assert(i0 != noChildIndex,
247  "Can't take first element of an empty TreePath");
248  };
249 #endif // DOXYGEN
250 
252  template<class TP, std::size_t i>
253  class TreePathPushFront {
254  dune_static_assert(AlwaysTrue<TP>::value,
255  "TreePathPushFront works on TreePaths only");
256  public:
258  typedef ImplementationDefined type;
259  };
260 
261 #ifndef DOXYGEN
262  template<std::size_t i0, std::size_t i1, std::size_t i2, std::size_t i3,
263  std::size_t i4, std::size_t i5, std::size_t i6, std::size_t i7,
264  std::size_t i8, std::size_t i9, std::size_t i>
265  struct TreePathPushFront<TreePath<i0, i1, i2, i3, i4, i5, i6, i7, i8, i9>,
266  i>
267  {
268  dune_static_assert(i0 ? false : false, "TreePathPushFront: exceeded "
269  "implementation limit on TreePath size");
270  };
271  template<std::size_t i0, std::size_t i1, std::size_t i2, std::size_t i3,
272  std::size_t i4, std::size_t i5, std::size_t i6, std::size_t i7,
273  std::size_t i8, std::size_t i>
274  struct TreePathPushFront<TreePath<i0, i1, i2, i3, i4, i5, i6, i7, i8>, i> {
275  typedef TreePath<i, i0, i1, i2, i3, i4, i5, i6, i7, i8> type;
276  };
277 #endif // DOXYGEN
278 
279  //
280  // Using the front operations from above, is is easy to reverse an
281  // arbitrary TreePath
282  //
283 
284 #ifdef DOXYGEN
285  template<class TP>
287  class TreePathReverse {
288  public:
290  typedef ImplementationDefined type;
291  };
292 #else // !DOXYGEN
293  template<class TP, class TP2 = TreePath<> >
294  struct TreePathReverse :
295  public TreePathReverse<
296  typename TreePathPopFront<TP>::type,
297  typename TreePathPushFront<TP2, TreePathFront<TP>::value>::type>
298  { };
299  template<class TP2>
300  struct TreePathReverse<TreePath<>, TP2>
301  { typedef TP2 type; };
302 #endif // DOXYGEN
303 
304  //
305  // The following classes operate on the back of a TreePath: They extract,
306  // remove or append the last element. They are easy to implement using
307  // the reverse operation.
308  //
309 
310 #ifdef DOXYGEN
311  template<class TP>
313  struct TreePathPopBack {
315  typedef ImplementationDefined type;
316  };
317 #else // !DOXYGEN
318  template<class TP>
319  struct TreePathPopBack :
320  public TreePathReverse<
321  typename TreePathPopFront<typename TreePathReverse<TP>::type>::type
322  >
323  { };
324 #endif // DOXYGEN
325 
326 #ifdef DOXYGEN
327  template<class TP>
329  struct TreePathBack {
331  static const std::size_t value = implementationDefined;
332  };
333 #else // !DOXYGEN
334  template<class TP>
335  struct TreePathBack :
336  public TreePathFront<typename TreePathReverse<TP>::type>
337  { };
338 #endif // DOXYGEN
339 
340 #ifdef DOXYGEN
341  template<class TP, std::size_t i>
343  struct TreePathPushBack {
345  typedef ImplementationDefined type;
346  };
347 #else // !DOXYGEN
348  template<class TP, std::size_t i>
349  struct TreePathPushBack :
350  public TreePathReverse<
351  typename TreePathPushFront<typename TreePathReverse<TP>::type, i>::type
352  >
353  { };
354 #endif // DOXYGEN
355 
356  //
357  // Finally some tuple-like classes to determine the length of the TreePath
358  // and to extract particular elements.
359  //
360 
361 #ifdef DOXYGEN
362  template<class TP>
364  struct TreePathSize {
366  static const std::size_t value = implementationDefined;
367  };
368 #else // !DOXYGEN
369  template<class TP>
370  struct TreePathSize :
371  public integral_constant<
372  std::size_t,
373  TreePathSize<typename TreePathPopFront<TP>::type>::value+1
374  >
375  { };
376  template<>
377  struct TreePathSize<TreePath<> > :
378  public integral_constant<std::size_t, 0>
379  { };
380 #endif // DOXYGEN
381 
382 #ifdef DOXYGEN
383  template<class TP>
385  struct TreePathElement {
387  static const std::size_t value = implementationDefined;
388  };
389 #else // !DOXYGEN
390  template<std::size_t pos, class TP>
391  struct TreePathElement :
392  public TreePathElement<pos-1, typename TreePathPopFront<TP>::type>
393  { };
394  template<class TP>
395  struct TreePathElement<0, TP> :
396  public TreePathFront<TP>
397  { };
398 #endif // DOXYGEN
399 
400 
401  template<typename, typename>
402  struct TreePathConcat;
403 
404  template<typename TP1, typename TP2>
405  struct TreePathConcat
406  {
407  typedef typename TreePathConcat<
408  typename TreePathPushBack<
409  TP1,
411  >::type,
412  typename TreePathPopFront<TP2>::type
413  >::type type;
414  };
415 
416  template<typename TP1>
417  struct TreePathConcat<TP1,TreePath<> >
418  {
419  typedef TP1 type;
420  };
421 
422 #endif // HAVE_VARIADIC_TEMPLATES
423 
424 
427  {
428 
429  public:
430 
432  std::size_t size() const
433  {
434  return _stack.size();
435  }
436 
438  std::size_t element(std::size_t pos) const
439  {
440  return _stack[pos];
441  }
442 
444  std::size_t back() const
445  {
446  return _stack.back();
447  }
448 
450  std::size_t front() const
451  {
452  return _stack.front();
453  }
454 
455  friend std::ostream& operator<<(std::ostream& os, const DynamicTreePath& tp)
456  {
457  os << "TreePath( ";
458  for (std::size_t i = 0; i < tp.size(); ++i)
459  os << tp.element(i) << " ";
460  os << ")";
461  return os;
462  }
463 
464  protected:
465 
466 #ifndef DOXYGEN
467 
469 
470  Stack& _stack;
471 
472  DynamicTreePath(Stack& stack)
473  : _stack(stack)
474  {}
475 
476 #endif // DOXYGEN
477 
478  };
479 
480 #ifndef DOXYGEN // DynamicTreePath subclasses are implementation details and never exposed to the user
481 
482  // This is the object that gets passed around by the traversal algorithm. It
483  // extends the DynamicTreePath with stack-like modifier methods. Note that
484  // it does not yet allocate any storage for the index values. It just uses
485  // the reference to a storage vector of the base class. This implies that all
486  // objects that are copy-constructed from each other share a single index storage!
487  // The reason for this is to avoid differentiating the visitor signature for static
488  // and dynamic traversal: Having very cheap copy-construction for these objects
489  // allows us to pass them by value.
490  class MutableDynamicTreePath
491  : public DynamicTreePath
492  {
493 
494  public:
495 
496  typedef DynamicTreePath ViewType;
497 
498  void push_back(std::size_t v)
499  {
500  _stack.push_back(v);
501  }
502 
503  void pop_back()
504  {
505  _stack.pop_back();
506  }
507 
508  void set_back(std::size_t v)
509  {
510  _stack.back() = v;
511  }
512 
513  DynamicTreePath view()
514  {
515  return *this;
516  }
517 
518  protected:
519 
520  MutableDynamicTreePath(Stack& stack)
521  : DynamicTreePath(stack)
522  {}
523 
524  };
525 
526  // DynamicTreePath storage provider.
527  // This objects provides the storage for the DynamicTreePath
528  // during the tree traversal. After construction, it should
529  // not be used directly - the traversal framework uses the
530  // base class returned by calling mutablePath().
531  template<std::size_t treeDepth>
532  class MakeableDynamicTreePath
533  : private FixedCapacityStack<std::size_t,treeDepth>
534  , public MutableDynamicTreePath
535  {
536 
537  public:
538 
539  MutableDynamicTreePath mutablePath()
540  {
541  return static_cast<MutableDynamicTreePath&>(*this);
542  }
543 
544  MakeableDynamicTreePath()
545  : MutableDynamicTreePath(static_cast<FixedCapacityStackView<std::size_t>&>(*this))
546  {
547  }
548 
549  };
550 
551  // Factory for creating the right type of TreePath based on the requested
552  // traversal pattern (static or dynamic).
553  template<TreePathType::Type tpType>
554  struct TreePathFactory;
555 
556  // Factory for static traversal.
557  template<>
558  struct TreePathFactory<TreePathType::fullyStatic>
559  {
560  template<typename Tree>
561  static TreePath<> create(const Tree& tree)
562  {
563  return TreePath<>();
564  }
565  };
566 
567  // Factory for dynamic traversal.
568  template<>
569  struct TreePathFactory<TreePathType::dynamic>
570  {
571  template<typename Tree>
572  static MakeableDynamicTreePath<TreeInfo<Tree>::depth> create(const Tree& tree)
573  {
574  return MakeableDynamicTreePath<TreeInfo<Tree>::depth>();
575  }
576  };
577 
578 #endif // DOXYGEN
579 
581 
582  } // namespace TypeTree
583 } //namespace Dune
584 
585 #endif // DUNE_TYPETREE_TREEPATH_HH
Definition: treepath.hh:26
TreePath mutablePath()
Definition: treepath.hh:35
Definition: treepath.hh:32
std::size_t front() const
Get the first index value.
Definition: treepath.hh:450
TreePath< i..., k...> type
Definition: treepath.hh:123
TreePath< k, i...> type
Definition: treepath.hh:61
void print_tree_path(std::ostream &os)
Definition: treepath.hh:127
std::size_t element(std::size_t pos) const
Get the index value at position pos.
Definition: treepath.hh:438
Definition: treepath.hh:92
Definition: treepath.hh:56
std::size_t back() const
Get the last index value.
Definition: treepath.hh:444
std::size_t size() const
Get the size (length) of this path.
Definition: treepath.hh:432
A TreePath that stores the path of a node as runtime information.
Definition: treepath.hh:426
std::ostream & operator<<(std::ostream &os, const TreePath< i...> &tp)
Definition: treepath.hh:138
TreePath view()
Definition: treepath.hh:34
Definition: treepath.hh:118
TreePath< i..., k > type
Definition: treepath.hh:52
Definition: fixedcapacitystack.hh:19
friend std::ostream & operator<<(std::ostream &os, const DynamicTreePath &tp)
Definition: treepath.hh:455
Definition: treepath.hh:39
static const std::size_t value
Definition: compositenode.hh:38
Definition: treepath.hh:65
TreePath< i...> type
Definition: treepath.hh:97
Type
Definition: treepath.hh:26
Definition: treepath.hh:84
Definition: treepath.hh:47
TreePath ViewType
Definition: treepath.hh:33
Definition: treepath.hh:109
TreePath< i...> type
Definition: treepath.hh:114