dune-typetree 3.0-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
15
16
17namespace 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
37 TreePath view() { return *this; }
38 TreePath mutablePath() { return *this; }
39 };
40
41 template<typename>
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>
70 {
71 typedef TreePath<k,i...> type;
72 };
73
74 template<typename>
76
77 // There is only a single element, so return that...
78 template<std::size_t 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>
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
328 using index_sequence = std::index_sequence_for<T...>;
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>
404 auto treePathEntry(const HybridTreePath<T...>& tp, index_constant<i> = {})
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>
427 std::size_t treePathIndex(const HybridTreePath<T...>& tp, index_constant<i> = {})
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>
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>
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>
498 HybridTreePath<T...,index_constant<i>> push_back(const HybridTreePath<T...>& tp, index_constant<i> i_ = {})
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>
529 HybridTreePath<index_constant<i>,T...> push_front(const HybridTreePath<T...>& tp, index_constant<i> _i = {})
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
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
constexpr HybridTreePath< T... > hybridTreePath(const T &... t)
Constructs a new HybridTreePath from the given indices.
Definition treepath.hh:373
constexpr std::size_t treePathSize(const TreePath< i... > &)
Returns the size (number of components) of the given TreePath.
Definition treepath.hh:51
std::size_t backIndex(const HybridTreePath< T... > &tp)
Returns the index value of the last element of the HybridTreePath.
Definition treepath.hh:447
std::ostream & operator<<(std::ostream &os, const TreePath< i... > &tp)
Definition treepath.hh:148
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
auto front(const HybridTreePath< T... > &tp) -> decltype(treePathEntry< 0 >(tp))
Returns a copy of the first element of the HybridTreePath.
Definition treepath.hh:459
std::size_t frontIndex(const HybridTreePath< T... > &tp)
Returns the index value of the first element of the HybridTreePath.
Definition treepath.hh:467
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 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
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
Definition accumulate_static.hh:13
Type
Definition treepath.hh:26
@ mostlyStatic
Definition treepath.hh:26
@ fullyStatic
Definition treepath.hh:26
@ dynamic
Definition treepath.hh:26
Definition fixedcapacitystack.hh:20
Definition treepath.hh:30
TreePath view()
Definition treepath.hh:37
constexpr TreePath()=default
constexpr TreePath(TreePath &&)=default
TreePath mutablePath()
Definition treepath.hh:38
constexpr TreePath(const TreePath &)=default
TreePath ViewType
Definition treepath.hh:36
Definition treepath.hh:42
Definition treepath.hh:57
TreePath< i..., k > type
Definition treepath.hh:62
Definition treepath.hh:66
TreePath< k, i... > type
Definition treepath.hh:71
Definition treepath.hh:75
Definition treepath.hh:94
Definition treepath.hh:102
TreePath< i... > type
Definition treepath.hh:107
Definition treepath.hh:119
TreePath< i... > type
Definition treepath.hh:124
Definition treepath.hh:128
TreePath< i..., k... > type
Definition treepath.hh:133
A TreePath that stores the path of a node as runtime information.
Definition treepath.hh:158
std::size_t size() const
Get the size (length) of this path.
Definition treepath.hh:163
std::size_t element(std::size_t pos) const
Get the index value at position pos.
Definition treepath.hh:169
friend std::ostream & operator<<(std::ostream &os, const DynamicTreePath &tp)
Definition treepath.hh:186
std::size_t back() const
Get the last index value.
Definition treepath.hh:175
std::size_t front() const
Get the first index value.
Definition treepath.hh:181
A hybrid version of TreePath that supports both compile time and run time indices.
Definition treepath.hh:323
constexpr HybridTreePath(HybridTreePath &&tp)=default
constexpr HybridTreePath(std::tuple< T... > t)
Constructor from a std::tuple
Definition treepath.hh:338
constexpr HybridTreePath(U... t)
Constructor from arguments.
Definition treepath.hh:344
constexpr HybridTreePath()
Default constructor.
Definition treepath.hh:331
static constexpr index_sequence enumerate()
Returns an index_sequence for enumerating the components of this HybridTreePath.
Definition treepath.hh:349
constexpr HybridTreePath(const HybridTreePath &tp)=default
std::index_sequence_for< T... > index_sequence
An index_sequence for the entries in this HybridTreePath.
Definition treepath.hh:328