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 
9 #include <dune/common/documentation.hh>
10 #include <dune/common/typetraits.hh>
11 
13 #include <dune/typetree/utility.hh>
14 
15 
16 namespace Dune {
17  namespace TypeTree {
18 
19 
23 
24  namespace TreePathType {
26  }
27 
28  template<std::size_t... i>
29  struct TreePath {
30  typedef TreePath ViewType;
31  TreePath view() { return *this; }
32  TreePath mutablePath() { return *this; }
33  };
34 
35  template<typename>
36  struct TreePathSize;
37 
38  template<std::size_t... i>
39  struct TreePathSize<TreePath<i...> >
40  : public integral_constant<std::size_t, sizeof...(i)>
41  {};
42 
43  template<typename,std::size_t>
45 
46  template<std::size_t k, std::size_t... i>
47  struct TreePathPushBack<TreePath<i...>,k>
48  {
49  typedef TreePath<i...,k> type;
50  };
51 
52  template<typename,std::size_t>
54 
55  template<std::size_t k, std::size_t... i>
56  struct TreePathPushFront<TreePath<i...>,k>
57  {
58  typedef TreePath<k,i...> type;
59  };
60 
61  template<typename>
62  struct TreePathBack;
63 
64  // There is only a single element, so return that...
65  template<std::size_t k>
66  struct TreePathBack<TreePath<k> >
67  : public integral_constant<std::size_t,k>
68  {};
69 
70  // We need to explicitly provide two elements here, as
71  // the template argument pack would match the empty list
72  // and create a conflict with the single-element specialization.
73  // Here, we just shave off the first element and recursively
74  // instantiate ourselves.
75  template<std::size_t j, std::size_t k, std::size_t... l>
76  struct TreePathBack<TreePath<j,k,l...> >
77  : public TreePathBack<TreePath<k,l...> >
78  {};
79 
80  template<typename>
81  struct TreePathFront;
82 
83  template<std::size_t k, std::size_t... i>
84  struct TreePathFront<TreePath<k,i...> >
85  : public integral_constant<std::size_t,k>
86  {};
87 
88  template<typename, std::size_t...>
90 
91  template<std::size_t k, std::size_t... i>
92  struct TreePathPopBack<TreePath<k>,i...>
93  {
94  typedef TreePath<i...> type;
95  };
96 
97  template<std::size_t j,
98  std::size_t k,
99  std::size_t... l,
100  std::size_t... i>
101  struct TreePathPopBack<TreePath<j,k,l...>,i...>
102  : public TreePathPopBack<TreePath<k,l...>,i...,j>
103  {};
104 
105  template<typename>
107 
108  template<std::size_t k, std::size_t... i>
109  struct TreePathPopFront<TreePath<k,i...> >
110  {
111  typedef TreePath<i...> type;
112  };
113 
114  template<typename, typename>
116 
117  template<std::size_t... i, std::size_t... k>
118  struct TreePathConcat<TreePath<i...>,TreePath<k...> >
119  {
120  typedef TreePath<i...,k...> type;
121  };
122 
123  template<std::size_t... i>
124  void print_tree_path(std::ostream& os)
125  {}
126 
127  template<std::size_t k, std::size_t... i>
128  void print_tree_path(std::ostream& os)
129  {
130  os << k << " ";
131  print_tree_path<i...>(os);
132  }
133 
134  template<std::size_t... i>
135  std::ostream& operator<<(std::ostream& os, const TreePath<i...>& tp)
136  {
137  os << "TreePath< ";
138  print_tree_path<i...>(os);
139  os << ">";
140  return os;
141  }
142 
145  {
146 
147  public:
148 
150  std::size_t size() const
151  {
152  return _stack.size();
153  }
154 
156  std::size_t element(std::size_t pos) const
157  {
158  return _stack[pos];
159  }
160 
162  std::size_t back() const
163  {
164  return _stack.back();
165  }
166 
168  std::size_t front() const
169  {
170  return _stack.front();
171  }
172 
173  friend std::ostream& operator<<(std::ostream& os, const DynamicTreePath& tp)
174  {
175  os << "TreePath( ";
176  for (std::size_t i = 0; i < tp.size(); ++i)
177  os << tp.element(i) << " ";
178  os << ")";
179  return os;
180  }
181 
182  protected:
183 
184 #ifndef DOXYGEN
185 
187 
188  Stack& _stack;
189 
190  DynamicTreePath(Stack& stack)
191  : _stack(stack)
192  {}
193 
194 #endif // DOXYGEN
195 
196  };
197 
198 #ifndef DOXYGEN // DynamicTreePath subclasses are implementation details and never exposed to the user
199 
200  // This is the object that gets passed around by the traversal algorithm. It
201  // extends the DynamicTreePath with stack-like modifier methods. Note that
202  // it does not yet allocate any storage for the index values. It just uses
203  // the reference to a storage vector of the base class. This implies that all
204  // objects that are copy-constructed from each other share a single index storage!
205  // The reason for this is to avoid differentiating the visitor signature for static
206  // and dynamic traversal: Having very cheap copy-construction for these objects
207  // allows us to pass them by value.
208  class MutableDynamicTreePath
209  : public DynamicTreePath
210  {
211 
212  public:
213 
214  typedef DynamicTreePath ViewType;
215 
216  void push_back(std::size_t v)
217  {
218  _stack.push_back(v);
219  }
220 
221  void pop_back()
222  {
223  _stack.pop_back();
224  }
225 
226  void set_back(std::size_t v)
227  {
228  _stack.back() = v;
229  }
230 
231  DynamicTreePath view()
232  {
233  return *this;
234  }
235 
236  protected:
237 
238  MutableDynamicTreePath(Stack& stack)
239  : DynamicTreePath(stack)
240  {}
241 
242  };
243 
244  // DynamicTreePath storage provider.
245  // This objects provides the storage for the DynamicTreePath
246  // during the tree traversal. After construction, it should
247  // not be used directly - the traversal framework uses the
248  // base class returned by calling mutablePath().
249  template<std::size_t treeDepth>
250  class MakeableDynamicTreePath
251  : private FixedCapacityStack<std::size_t,treeDepth>
252  , public MutableDynamicTreePath
253  {
254 
255  public:
256 
257  MutableDynamicTreePath mutablePath()
258  {
259  return static_cast<MutableDynamicTreePath&>(*this);
260  }
261 
262  MakeableDynamicTreePath()
263  : MutableDynamicTreePath(static_cast<FixedCapacityStackView<std::size_t>&>(*this))
264  {
265  }
266 
267  };
268 
269  // Factory for creating the right type of TreePath based on the requested
270  // traversal pattern (static or dynamic).
271  template<TreePathType::Type tpType>
272  struct TreePathFactory;
273 
274  // Factory for static traversal.
275  template<>
276  struct TreePathFactory<TreePathType::fullyStatic>
277  {
278  template<typename Tree>
279  static TreePath<> create(const Tree& tree)
280  {
281  return TreePath<>();
282  }
283  };
284 
285  // Factory for dynamic traversal.
286  template<>
287  struct TreePathFactory<TreePathType::dynamic>
288  {
289  template<typename Tree>
290  static MakeableDynamicTreePath<TreeInfo<Tree>::depth> create(const Tree& tree)
291  {
292  return MakeableDynamicTreePath<TreeInfo<Tree>::depth>();
293  }
294  };
295 
296 #endif // DOXYGEN
297 
299 
300  } // namespace TypeTree
301 } //namespace Dune
302 
303 #endif // DUNE_TYPETREE_TREEPATH_HH
TreePath ViewType
Definition: treepath.hh:30
Definition: treepath.hh:89
Definition: treepath.hh:44
std::size_t element(std::size_t pos) const
Get the index value at position pos.
Definition: treepath.hh:156
Definition: treepath.hh:62
Definition: accumulate_static.hh:12
std::ostream & operator<<(std::ostream &os, const TreePath< i...> &tp)
Definition: treepath.hh:135
STL namespace.
Definition: treepath.hh:115
TreePath< i...> type
Definition: treepath.hh:94
TreePath< k, i...> type
Definition: treepath.hh:58
friend std::ostream & operator<<(std::ostream &os, const DynamicTreePath &tp)
Definition: treepath.hh:173
TreePath mutablePath()
Definition: treepath.hh:32
TreePath< i..., k > type
Definition: treepath.hh:49
Definition: treepath.hh:53
std::size_t back() const
Get the last index value.
Definition: treepath.hh:162
A TreePath that stores the path of a node as runtime information.
Definition: treepath.hh:144
TreePath< i...> type
Definition: treepath.hh:111
Definition: treepath.hh:106
Type
Definition: treepath.hh:25
Definition: treepath.hh:25
TreePath view()
Definition: treepath.hh:31
void print_tree_path(std::ostream &os)
Definition: treepath.hh:124
Definition: treepath.hh:81
std::size_t size() const
Get the size (length) of this path.
Definition: treepath.hh:150
std::size_t front() const
Get the first index value.
Definition: treepath.hh:168
Definition: treepath.hh:29
TreePath< i..., k...> type
Definition: treepath.hh:120
Definition: treepath.hh:36
Definition: fixedcapacitystack.hh:19