dune-typetree  2.4-dev
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 #include <iostream>
9 
10 #include <dune/common/documentation.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  template<std::size_t... i>
30  struct TreePath {
31 
32  constexpr TreePath() = default;
33  constexpr TreePath(const TreePath&) = default;
34  constexpr TreePath(TreePath&&) = default;
35 
36  typedef TreePath ViewType;
37  TreePath view() { return *this; }
38  TreePath mutablePath() { return *this; }
39  };
40 
41  template<typename>
42  struct TreePathSize;
43 
44  template<std::size_t... i>
45  struct TreePathSize<TreePath<i...> >
46  : public index_constant<sizeof...(i)>
47  {};
48 
50  template<std::size_t... i>
51  constexpr std::size_t treePathSize(const TreePath<i...>&)
52  {
53  return sizeof...(i);
54  }
55 
56  template<typename,std::size_t>
58 
59  template<std::size_t k, std::size_t... i>
60  struct TreePathPushBack<TreePath<i...>,k>
61  {
62  typedef TreePath<i...,k> type;
63  };
64 
65  template<typename,std::size_t>
67 
68  template<std::size_t k, std::size_t... i>
69  struct TreePathPushFront<TreePath<i...>,k>
70  {
71  typedef TreePath<k,i...> type;
72  };
73 
74  template<typename>
75  struct TreePathBack;
76 
77  // There is only a single element, so return that...
78  template<std::size_t k>
79  struct TreePathBack<TreePath<k> >
80  : public index_constant<k>
81  {};
82 
83  // We need to explicitly provide two elements here, as
84  // the template argument pack would match the empty list
85  // and create a conflict with the single-element specialization.
86  // Here, we just shave off the first element and recursively
87  // instantiate ourselves.
88  template<std::size_t j, std::size_t k, std::size_t... l>
89  struct TreePathBack<TreePath<j,k,l...> >
90  : public TreePathBack<TreePath<k,l...> >
91  {};
92 
93  template<typename>
94  struct TreePathFront;
95 
96  template<std::size_t k, std::size_t... i>
97  struct TreePathFront<TreePath<k,i...> >
98  : public index_constant<k>
99  {};
100 
101  template<typename, std::size_t...>
103 
104  template<std::size_t k, std::size_t... i>
105  struct TreePathPopBack<TreePath<k>,i...>
106  {
107  typedef TreePath<i...> type;
108  };
109 
110  template<std::size_t j,
111  std::size_t k,
112  std::size_t... l,
113  std::size_t... i>
114  struct TreePathPopBack<TreePath<j,k,l...>,i...>
115  : public TreePathPopBack<TreePath<k,l...>,i...,j>
116  {};
117 
118  template<typename>
120 
121  template<std::size_t k, std::size_t... i>
122  struct TreePathPopFront<TreePath<k,i...> >
123  {
124  typedef TreePath<i...> type;
125  };
126 
127  template<typename, typename>
129 
130  template<std::size_t... i, std::size_t... k>
131  struct TreePathConcat<TreePath<i...>,TreePath<k...> >
132  {
133  typedef TreePath<i...,k...> type;
134  };
135 
136  template<std::size_t... i>
137  void print_tree_path(std::ostream& os)
138  {}
139 
140  template<std::size_t k, std::size_t... i>
141  void print_tree_path(std::ostream& os)
142  {
143  os << k << " ";
144  print_tree_path<i...>(os);
145  }
146 
147  template<std::size_t... i>
148  std::ostream& operator<<(std::ostream& os, const TreePath<i...>& tp)
149  {
150  os << "TreePath< ";
151  print_tree_path<i...>(os);
152  os << ">";
153  return os;
154  }
155 
158  {
159 
160  public:
161 
163  std::size_t size() const
164  {
165  return _stack.size();
166  }
167 
169  std::size_t element(std::size_t pos) const
170  {
171  return _stack[pos];
172  }
173 
175  std::size_t back() const
176  {
177  return _stack.back();
178  }
179 
181  std::size_t front() const
182  {
183  return _stack.front();
184  }
185 
186  friend std::ostream& operator<<(std::ostream& os, const DynamicTreePath& tp)
187  {
188  os << "TreePath( ";
189  for (std::size_t i = 0; i < tp.size(); ++i)
190  os << tp.element(i) << " ";
191  os << ")";
192  return os;
193  }
194 
195  protected:
196 
197 #ifndef DOXYGEN
198 
200 
201  Stack& _stack;
202 
203  DynamicTreePath(Stack& stack)
204  : _stack(stack)
205  {}
206 
207 #endif // DOXYGEN
208 
209  };
210 
211 #ifndef DOXYGEN // DynamicTreePath subclasses are implementation details and never exposed to the user
212 
213  // This is the object that gets passed around by the traversal algorithm. It
214  // extends the DynamicTreePath with stack-like modifier methods. Note that
215  // it does not yet allocate any storage for the index values. It just uses
216  // the reference to a storage vector of the base class. This implies that all
217  // objects that are copy-constructed from each other share a single index storage!
218  // The reason for this is to avoid differentiating the visitor signature for static
219  // and dynamic traversal: Having very cheap copy-construction for these objects
220  // allows us to pass them by value.
221  class MutableDynamicTreePath
222  : public DynamicTreePath
223  {
224 
225  public:
226 
227  typedef DynamicTreePath ViewType;
228 
229  void push_back(std::size_t v)
230  {
231  _stack.push_back(v);
232  }
233 
234  void pop_back()
235  {
236  _stack.pop_back();
237  }
238 
239  void set_back(std::size_t v)
240  {
241  _stack.back() = v;
242  }
243 
244  DynamicTreePath view()
245  {
246  return *this;
247  }
248 
249  protected:
250 
251  MutableDynamicTreePath(Stack& stack)
252  : DynamicTreePath(stack)
253  {}
254 
255  };
256 
257  // DynamicTreePath storage provider.
258  // This objects provides the storage for the DynamicTreePath
259  // during the tree traversal. After construction, it should
260  // not be used directly - the traversal framework uses the
261  // base class returned by calling mutablePath().
262  template<std::size_t treeDepth>
263  class MakeableDynamicTreePath
264  : private FixedCapacityStack<std::size_t,treeDepth>
265  , public MutableDynamicTreePath
266  {
267 
268  public:
269 
270  MutableDynamicTreePath mutablePath()
271  {
272  return static_cast<MutableDynamicTreePath&>(*this);
273  }
274 
275  MakeableDynamicTreePath()
276  : MutableDynamicTreePath(static_cast<FixedCapacityStackView<std::size_t>&>(*this))
277  {
278  }
279 
280  };
281 
282  // Factory for creating the right type of TreePath based on the requested
283  // traversal pattern (static or dynamic).
284  template<TreePathType::Type tpType>
285  struct TreePathFactory;
286 
287  // Factory for static traversal.
288  template<>
289  struct TreePathFactory<TreePathType::fullyStatic>
290  {
291  template<typename Tree>
292  static TreePath<> create(const Tree& tree)
293  {
294  return TreePath<>();
295  }
296  };
297 
298  // Factory for dynamic traversal.
299  template<>
300  struct TreePathFactory<TreePathType::dynamic>
301  {
302  template<typename Tree>
303  static MakeableDynamicTreePath<TreeInfo<Tree>::depth> create(const Tree& tree)
304  {
305  return MakeableDynamicTreePath<TreeInfo<Tree>::depth>();
306  }
307  };
308 
309 #endif // DOXYGEN
310 
311 
313 
321  template<typename... T>
323  {
324 
325  public:
326 
329 
331  constexpr HybridTreePath()
332  {}
333 
334  constexpr HybridTreePath(const HybridTreePath& tp) = default;
335  constexpr HybridTreePath(HybridTreePath&& tp) = default;
336 
338  explicit constexpr HybridTreePath(std::tuple<T...> t)
339  : _data(t)
340  {}
341 
343  template<typename... U, typename std::enable_if<(sizeof...(T) > 0 && sizeof...(U) == sizeof...(T)),bool>::type = true>
344  explicit constexpr HybridTreePath(U... t)
345  : _data(t...)
346  {}
347 
349  constexpr static index_sequence enumerate()
350  {
351  return {};
352  }
353 
354 #ifndef DOXYGEN
355 
356  // I can't be bothered to make all the external accessors friends of HybridTreePath,
357  // so we'll only hide the data tuple from the user in Doxygen.
358 
359  using Data = std::tuple<T...>;
360  Data _data;
361 
362 #endif // DOXYGEN
363 
364  };
365 
366 
368 
372  template<typename... T>
373  constexpr HybridTreePath<T...> hybridTreePath(const T&... t)
374  {
375  return HybridTreePath<T...>(t...);
376  }
377 
378 
380  template<typename... T>
381  constexpr std::size_t treePathSize(const HybridTreePath<T...>&)
382  {
383  return sizeof...(T);
384  }
385 
387 
403  template<std::size_t i, typename... T>
405  -> typename std::decay<decltype(std::get<i>(tp._data))>::type
406  {
407  return std::get<i>(tp._data);
408  }
409 
411 
426  template<std::size_t i,typename... T>
428  {
429  return std::get<i>(tp._data);
430  }
431 
433 
438  template<typename... T, typename std::enable_if<(sizeof...(T) > 0),bool>::type = true>
439  auto back(const HybridTreePath<T...>& tp)
440  -> decltype(treePathEntry<treePathSize(tp)-1>(tp))
441  {
442  return treePathEntry<treePathSize(tp)-1>(tp);
443  }
444 
446  template<typename... T, typename std::enable_if<(sizeof...(T) > 0),bool>::type = true>
447  std::size_t backIndex(const HybridTreePath<T...>& tp)
448  {
449  return treePathEntry<treePathSize(tp)-1>(tp);
450  }
451 
453 
458  template<typename... T>
459  auto front(const HybridTreePath<T...>& tp)
460  -> decltype(treePathEntry<0>(tp))
461  {
462  return treePathEntry<0>(tp);
463  }
464 
466  template<typename... T>
467  std::size_t frontIndex(const HybridTreePath<T...>& tp)
468  {
469  return treePathEntry<0>(tp);
470  }
471 
473 
476  template<typename... T>
477  HybridTreePath<T...,std::size_t> push_back(const HybridTreePath<T...>& tp, std::size_t i)
478  {
479  return HybridTreePath<T...,std::size_t>(std::tuple_cat(tp._data,std::make_tuple(i)));
480  }
481 
483 
497  template<std::size_t i, typename... T>
499  {
500  return HybridTreePath<T...,index_constant<i> >(std::tuple_cat(tp._data,std::make_tuple(i_)));
501  }
502 
504 
507  template<typename... T>
508  HybridTreePath<std::size_t,T...> push_front(const HybridTreePath<T...>& tp, std::size_t element)
509  {
510  return HybridTreePath<std::size_t,T...>(std::tuple_cat(std::make_tuple(element),tp._data));
511  }
512 
514 
528  template<std::size_t i, typename... T>
530  {
531  return HybridTreePath<index_constant<i>,T...>(std::tuple_cat(std::make_tuple(_i),tp._data));
532  }
533 
534 #ifndef DOXYGEN
535 
536  namespace impl {
537 
538  // end of recursion
539  template<std::size_t i, typename... T>
540  typename std::enable_if<
541  (i == sizeof...(T))
542  >::type
543  print_hybrid_tree_path(std::ostream& os, const HybridTreePath<T...>& tp, index_constant<i> _i)
544  {}
545 
546  // print current entry and recurse
547  template<std::size_t i, typename... T>
548  typename std::enable_if<
549  (i < sizeof...(T))
550  >::type
551  print_hybrid_tree_path(std::ostream& os, const HybridTreePath<T...>& tp, index_constant<i> _i)
552  {
553  os << treePathIndex(tp,_i) << " ";
554  print_hybrid_tree_path(os,tp,index_constant<i+1>{});
555  }
556 
557  } // namespace impl
558 
559 #endif // DOXYGEN
560 
562  template<typename... T>
563  std::ostream& operator<<(std::ostream& os, const HybridTreePath<T...>& tp)
564  {
565  os << "HybridTreePath< ";
566  impl::print_hybrid_tree_path(os, tp, index_constant<0>{});
567  os << ">";
568  return os;
569  }
570 
572 
573  } // namespace TypeTree
574 } //namespace Dune
575 
576 #endif // DUNE_TYPETREE_TREEPATH_HH
TreePath< i...> type
Definition: treepath.hh:124
Definition: treepath.hh:94
Definition: treepath.hh:119
std::size_t element(std::size_t pos) const
Get the index value at position pos.
Definition: treepath.hh:169
std::size_t treePathIndex(const HybridTreePath< T...> &tp, index_constant< i >={})
Returns the index value of the i-th element of the HybridTreePath.
Definition: treepath.hh:427
HybridTreePath< std::size_t, T...> push_front(const HybridTreePath< T...> &tp, std::size_t element)
Prepends a run time index to a HybridTreePath.
Definition: treepath.hh:508
auto back(const HybridTreePath< T...> &tp) -> decltype(treePathEntry< treePathSize(tp)-1 >(tp))
Returns a copy of the last element of the HybridTreePath.
Definition: treepath.hh:439
Definition: accumulate_static.hh:12
std::size_t backIndex(const HybridTreePath< T...> &tp)
Returns the index value of the last element of the HybridTreePath.
Definition: treepath.hh:447
Definition: treepath.hh:42
make_index_sequence< impl::_get_pack_length< T...>{}> index_sequence_for
Create an index_sequence for the pack T..., i.e. [0,sizeof...(T)].
Definition: utility.hh:298
constexpr std::size_t treePathSize(const TreePath< i...> &)
Returns the size (number of components) of the given TreePath.
Definition: treepath.hh:51
constexpr HybridTreePath< T...> hybridTreePath(const T &...t)
Constructs a new HybridTreePath from the given indices.
Definition: treepath.hh:373
STL namespace.
friend std::ostream & operator<<(std::ostream &os, const DynamicTreePath &tp)
Definition: treepath.hh:186
std::integral_constant< std::size_t, i > index_constant
An index constant with value i.
Definition: utility.hh:312
auto treePathEntry(const HybridTreePath< T...> &tp, index_constant< i >={}) -> typename std::decay< decltype(std::get< i >(tp._data))>::type
Returns a copy of the i-th element of the HybridTreePath.
Definition: treepath.hh:404
Std::index_sequence_for< T...> index_sequence
An index_sequence for the entries in this HybridTreePath.
Definition: treepath.hh:328
Definition: treepath.hh:102
A hybrid version of TreePath that supports both compile time and run time indices.
Definition: treepath.hh:322
Definition: treepath.hh:57
TreePath view()
Definition: treepath.hh:37
TreePath< i...> type
Definition: treepath.hh:107
Definition: treepath.hh:75
std::size_t back() const
Get the last index value.
Definition: treepath.hh:175
Definition: treepath.hh:26
A TreePath that stores the path of a node as runtime information.
Definition: treepath.hh:157
TreePath< k, i...> type
Definition: treepath.hh:71
TreePath< i..., k > type
Definition: treepath.hh:62
auto front(const HybridTreePath< T...> &tp) -> decltype(treePathEntry< 0 >(tp))
Returns a copy of the first element of the HybridTreePath.
Definition: treepath.hh:459
constexpr TreePath()=default
std::size_t frontIndex(const HybridTreePath< T...> &tp)
Returns the index value of the first element of the HybridTreePath.
Definition: treepath.hh:467
static constexpr index_sequence enumerate()
Returns an index_sequence for enumerating the components of this HybridTreePath.
Definition: treepath.hh:349
Type
Definition: treepath.hh:26
Definition: treepath.hh:128
TreePath< i..., k...> type
Definition: treepath.hh:133
std::size_t size() const
Get the size (length) of this path.
Definition: treepath.hh:163
std::ostream & operator<<(std::ostream &os, const TreePath< i...> &tp)
Definition: treepath.hh:148
constexpr HybridTreePath()
Default constructor.
Definition: treepath.hh:331
std::size_t front() const
Get the first index value.
Definition: treepath.hh:181
void print_tree_path(std::ostream &os)
Definition: treepath.hh:137
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:477
constexpr HybridTreePath(U...t)
Constructor from arguments.
Definition: treepath.hh:344
Definition: treepath.hh:30
constexpr HybridTreePath(std::tuple< T...> t)
Constructor from a std::tuple
Definition: treepath.hh:338
TreePath mutablePath()
Definition: treepath.hh:38
Definition: treepath.hh:66
TreePath ViewType
Definition: treepath.hh:36
Definition: fixedcapacitystack.hh:19