dune-typetree  2.4.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 #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 #if defined(__GNUC__) && !defined(__clang__) && __GNUC__ < 5 && __GNUC_MINOR__ < 8
441  -> decltype(treePathEntry<treePathSize(std::declval<HybridTreePath<T...>>())-1>(std::declval<HybridTreePath<T...>>()))
442 #else
443  -> decltype(treePathEntry<treePathSize(tp)-1>(tp))
444 #endif
445  {
446  return treePathEntry<treePathSize(tp)-1>(tp);
447  }
448 
450  template<typename... T, typename std::enable_if<(sizeof...(T) > 0),bool>::type = true>
451  std::size_t backIndex(const HybridTreePath<T...>& tp)
452  {
453  return treePathEntry<treePathSize(tp)-1>(tp);
454  }
455 
457 
462  template<typename... T>
463  auto front(const HybridTreePath<T...>& tp)
464  -> decltype(treePathEntry<0>(tp))
465  {
466  return treePathEntry<0>(tp);
467  }
468 
470  template<typename... T>
471  std::size_t frontIndex(const HybridTreePath<T...>& tp)
472  {
473  return treePathEntry<0>(tp);
474  }
475 
477 
480  template<typename... T>
481  HybridTreePath<T...,std::size_t> push_back(const HybridTreePath<T...>& tp, std::size_t i)
482  {
483  return HybridTreePath<T...,std::size_t>(std::tuple_cat(tp._data,std::make_tuple(i)));
484  }
485 
487 
501  template<std::size_t i, typename... T>
503  {
504  return HybridTreePath<T...,index_constant<i> >(std::tuple_cat(tp._data,std::make_tuple(i_)));
505  }
506 
508 
511  template<typename... T>
512  HybridTreePath<std::size_t,T...> push_front(const HybridTreePath<T...>& tp, std::size_t element)
513  {
514  return HybridTreePath<std::size_t,T...>(std::tuple_cat(std::make_tuple(element),tp._data));
515  }
516 
518 
532  template<std::size_t i, typename... T>
534  {
535  return HybridTreePath<index_constant<i>,T...>(std::tuple_cat(std::make_tuple(_i),tp._data));
536  }
537 
538 #ifndef DOXYGEN
539 
540  namespace impl {
541 
542  // end of recursion
543  template<std::size_t i, typename... T>
544  typename std::enable_if<
545  (i == sizeof...(T))
546  >::type
547  print_hybrid_tree_path(std::ostream& os, const HybridTreePath<T...>& tp, index_constant<i> _i)
548  {}
549 
550  // print current entry and recurse
551  template<std::size_t i, typename... T>
552  typename std::enable_if<
553  (i < sizeof...(T))
554  >::type
555  print_hybrid_tree_path(std::ostream& os, const HybridTreePath<T...>& tp, index_constant<i> _i)
556  {
557  os << treePathIndex(tp,_i) << " ";
558  print_hybrid_tree_path(os,tp,index_constant<i+1>{});
559  }
560 
561  } // namespace impl
562 
563 #endif // DOXYGEN
564 
566  template<typename... T>
567  std::ostream& operator<<(std::ostream& os, const HybridTreePath<T...>& tp)
568  {
569  os << "HybridTreePath< ";
570  impl::print_hybrid_tree_path(os, tp, index_constant<0>{});
571  os << ">";
572  return os;
573  }
574 
576 
577  } // namespace TypeTree
578 } //namespace Dune
579 
580 #endif // DUNE_TYPETREE_TREEPATH_HH
TreePath ViewType
Definition: treepath.hh:36
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:481
Definition: treepath.hh:42
std::integral_constant< std::size_t, i > index_constant
An index constant with value i.
Definition: utility.hh:312
std::size_t front() const
Get the first index value.
Definition: treepath.hh:181
constexpr HybridTreePath(std::tuple< T... > t)
Constructor from a std::tuple
Definition: treepath.hh:338
constexpr HybridTreePath< T... > hybridTreePath(const T &...t)
Constructs a new HybridTreePath from the given indices.
Definition: treepath.hh:373
A hybrid version of TreePath that supports both compile time and run time indices.
Definition: treepath.hh:322
std::ostream & operator<<(std::ostream &os, const TreePath< i... > &tp)
Definition: treepath.hh:148
TreePath< i..., k... > type
Definition: treepath.hh:133
TreePath< i..., k > type
Definition: treepath.hh:62
Definition: treepath.hh:57
std::size_t element(std::size_t pos) const
Get the index value at position pos.
Definition: treepath.hh:169
Definition: treepath.hh:75
std::size_t back() const
Get the last index value.
Definition: treepath.hh:175
std::size_t size() const
Get the size (length) of this path.
Definition: treepath.hh:163
TreePath view()
Definition: treepath.hh:37
Definition: treepath.hh:128
TreePath< i... > type
Definition: treepath.hh:107
A TreePath that stores the path of a node as runtime information.
Definition: treepath.hh:157
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
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
std::size_t frontIndex(const HybridTreePath< T... > &tp)
Returns the index value of the first element of the HybridTreePath.
Definition: treepath.hh:471
Definition: treepath.hh:30
Definition: treepath.hh:66
void print_tree_path(std::ostream &os)
Definition: treepath.hh:137
constexpr std::size_t treePathSize(const TreePath< i... > &)
Returns the size (number of components) of the given TreePath.
Definition: treepath.hh:51
Definition: fixedcapacitystack.hh:19
friend std::ostream & operator<<(std::ostream &os, const DynamicTreePath &tp)
Definition: treepath.hh:186
TreePath< k, i... > type
Definition: treepath.hh:71
Definition: treepath.hh:102
Std::index_sequence_for< T... > index_sequence
An index_sequence for the entries in this HybridTreePath.
Definition: treepath.hh:328
Definition: treepath.hh:94
TreePath< i... > type
Definition: treepath.hh:124
TreePath mutablePath()
Definition: treepath.hh:38
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
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
Definition: accumulate_static.hh:12
constexpr HybridTreePath()
Default constructor.
Definition: treepath.hh:331
Definition: treepath.hh:119
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:512
auto front(const HybridTreePath< T... > &tp) -> decltype(treePathEntry< 0 >(tp))
Returns a copy of the first element of the HybridTreePath.
Definition: treepath.hh:463
Definition: treepath.hh:26
constexpr HybridTreePath(U...t)
Constructor from arguments.
Definition: treepath.hh:344
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
Definition: fixedcapacitystack.hh:119
std::size_t backIndex(const HybridTreePath< T... > &tp)
Returns the index value of the last element of the HybridTreePath.
Definition: treepath.hh:451