dune-pdelab  2.7-git
localorderingbase.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_PDELAB_ORDERING_LOCALORDERINGBASE_HH
5 #define DUNE_PDELAB_ORDERING_LOCALORDERINGBASE_HH
6 
9 
10 #include <dune/common/rangeutilities.hh>
11 
12 #include <vector>
13 
14 namespace Dune {
15  namespace PDELab {
16 
19 
28  template<typename ES, typename DI, typename CI>
30  {
31 
33 
34  template<typename>
35  friend struct update_fixed_size;
36 
37  template<typename>
39 
40  template<typename>
42 
44 
45  template<typename>
47 
48  template<typename>
50 
51  template<typename>
52  friend class GridViewOrdering;
53 
54  template<typename size_type>
55  friend struct ::Dune::PDELab::impl::update_ordering_data;
56 
57  public:
58 
59  static const bool has_dynamic_ordering_children = true;
60 
61  static const bool consume_tree_index = true;
62 
64 
65  static constexpr auto GT_UNUSED = ~std::size_t(0);
66 
67  protected:
68 
69  typedef impl::GridFunctionSpaceOrderingData<typename Traits::SizeType> GFSData;
70 
71  public:
72 
73  void map_local_index(const typename Traits::SizeType geometry_type_index,
74  const typename Traits::SizeType entity_index,
75  typename Traits::TreeIndexView mi,
76  typename Traits::ContainerIndex& ci) const
77  {
78  if (_child_count == 0) // leaf nodes
79  {
80  assert(mi.size() == 1 && "MultiIndex length must match GridFunctionSpace tree depth");
81  ci.push_back(mi.back());
82  }
83  else // inner nodes
84  {
85  const typename Traits::SizeType child_index = mi.back();
86  if (!mi.empty())
87  _children[child_index]->map_local_index(geometry_type_index,entity_index,mi.back_popped(),ci);
89  {
90  ci.push_back(child_index);
91  }
92  else if (child_index > 0)
93  {
94  if (_fixed_size)
95  {
96  const typename Traits::SizeType index = geometry_type_index * _child_count + child_index - 1;
97  ci.back() += _gt_dof_offsets[index];
98  }
99  else
100  {
101  assert(_gt_used[geometry_type_index]);
102  const typename Traits::SizeType index = (_gt_entity_offsets[geometry_type_index] + entity_index) * _child_count + child_index - 1;
103  ci.back() += _entity_dof_offsets[index];
104  }
105  }
106  }
107  }
108 
109 
121  template<typename ItIn, typename ItOut>
122  void map_lfs_indices(const ItIn begin, const ItIn end, ItOut out) const
123  {
124  if (_child_count == 0) // leaf nodes
125  {
126  for (ItIn in = begin; in != end; ++in, ++out) {
127  assert(in->size() == 1 &&
128  "MultiIndex length must match GridFunctionSpace tree depth");
129  out->push_back(in->treeIndex().back());
130  }
131  } else if (_container_blocked) // blocked inner nodes
132  {
133  for (ItIn in = begin; in != end; ++in, ++out)
134  out->push_back(in->treeIndex().back());
135  } else if (_fixed_size) // non-blocked inner nodes with fixed sizes
136  {
137  for (ItIn in = begin; in != end; ++in, ++out) {
138  const typename Traits::SizeType child_index =
139  in->treeIndex().back();
140  const typename Traits::SizeType gt_index =
142  if (child_index > 0) {
143  const typename Traits::SizeType index =
144  gt_index * _child_count + child_index - 1;
145  out->back() += _gt_dof_offsets[index];
146  }
147  }
148  } else // non-blocked inner nodes with variable sizes
149  {
150  for (ItIn in = begin; in != end; ++in, ++out) {
151  const typename Traits::SizeType child_index =
152  in->treeIndex().back();
153  if (child_index > 0) {
154  const typename Traits::SizeType gt_index =
156  const typename Traits::SizeType entity_index =
158 
159  assert(_gt_used[gt_index]);
160 
161  const typename Traits::SizeType index =
162  (_gt_entity_offsets[gt_index] + entity_index) *
163  _child_count +
164  child_index - 1;
165  out->back() += _entity_dof_offsets[index];
166  }
167  }
168  }
169  }
170 
171  template<typename CIOutIterator, typename DIOutIterator = DummyDOFIndexIterator>
172  typename Traits::SizeType
173  extract_entity_indices(const typename Traits::DOFIndex::EntityIndex& ei,
174  typename Traits::SizeType child_index,
175  CIOutIterator ci_out, const CIOutIterator ci_end,
176  DIOutIterator di_out = DIOutIterator()) const
177  {
178  typedef typename Traits::SizeType size_type;
179 
180  const size_type geometry_type_index = Traits::DOFIndexAccessor::GeometryIndex::geometryType(ei);
181  const size_type entity_index = Traits::DOFIndexAccessor::GeometryIndex::entityIndex(ei);
182 
183  if (!_gt_used[geometry_type_index])
184  return 0;
185 
186  if (_child_count == 0)
187  {
188  const size_type size = _fixed_size
189  ? _gt_dof_offsets[geometry_type_index]
190  : _entity_dof_offsets[(_gt_entity_offsets[geometry_type_index] + entity_index)];
191 
192  for (size_type i = 0; i < size; ++i, ++ci_out, ++di_out)
193  {
194  ci_out->push_back(i);
195  di_out->treeIndex().push_back(i);
196  }
197  return size;
198  }
199  else
200  {
201  if (_container_blocked)
202  {
203  for (; ci_out != ci_end; ++ci_out)
204  {
205  ci_out->push_back(child_index);
206  }
207  }
208  else if (child_index > 0)
209  {
210  if (_fixed_size)
211  for (; ci_out != ci_end; ++ci_out)
212  {
213  const typename Traits::SizeType index = geometry_type_index * _child_count + child_index - 1;
214  ci_out->back() += _gt_dof_offsets[index];
215  }
216  else
217  for (; ci_out != ci_end; ++ci_out)
218  {
219  const typename Traits::SizeType index = (_gt_entity_offsets[geometry_type_index] + entity_index) * _child_count + child_index - 1;
220  ci_out->back() += _entity_dof_offsets[index];
221  }
222  }
223 
224  // The return value is not used for non-leaf orderings.
225  return 0;
226  }
227  }
228 
229  typename Traits::SizeType size(const typename Traits::DOFIndex::EntityIndex& index) const
230  {
231  return size(
232  Traits::DOFIndexAccessor::GeometryIndex::geometryType(index),
233  Traits::DOFIndexAccessor::GeometryIndex::entityIndex(index)
234  );
235  }
236 
237  typename Traits::SizeType size(const typename Traits::SizeType geometry_type_index, const typename Traits::SizeType entity_index) const
238  {
239  if (_fixed_size)
240  return _child_count > 0
241  ? _gt_dof_offsets[geometry_type_index * _child_count + _child_count - 1]
242  : _gt_dof_offsets[geometry_type_index];
243 
244  if (!_gt_used[geometry_type_index])
245  return 0;
246 
247  return _child_count > 0
248  ? _entity_dof_offsets[(_gt_entity_offsets[geometry_type_index] + entity_index) * _child_count + _child_count - 1]
249  : _entity_dof_offsets[(_gt_entity_offsets[geometry_type_index] + entity_index)];
250  }
251 
252  typename Traits::SizeType size(const typename Traits::SizeType geometry_type_index, const typename Traits::SizeType entity_index, const typename Traits::SizeType child_index) const
253  {
254  assert(child_index < _child_count);
255  if (_fixed_size)
256  {
257  const typename Traits::SizeType index = geometry_type_index * _child_count + child_index;
258  return child_index > 0 ? _gt_dof_offsets[index] - _gt_dof_offsets[index-1] : _gt_dof_offsets[index];
259  }
260  else
261  {
262  if (_gt_used[geometry_type_index])
263  {
264  const typename Traits::SizeType index = (_gt_entity_offsets[geometry_type_index] + entity_index) * _child_count + child_index;
266  }
267  else
268  {
269  return 0;
270  }
271  }
272  }
273 
274  protected:
275 
285  template<class Node>
286  typename Traits::SizeType
287  node_size(const Node& node, typename Traits::ContainerIndex suffix,
288  const typename Traits::DOFIndex::EntityIndex &index) const {
289  using size_type = typename Traits::size_type;
290 
291  // suffix wants the size for this node
292  if (suffix.size() == 0)
293  return node.size(index);
294 
295  if constexpr (Node::isLeaf) {
296  return 0; // Assume leaf local orderings are always field vectors
297  } else {
298  // the next index to find out its size
299  auto back_index = suffix.back();
300  // task: find child local ordering because it should know its own size
301  std::size_t _child;
302 
303  if (node.containerBlocked()) {
304  // in this case back index is the child ordering itself
305  _child = back_index;
306  suffix.pop_back();
307  } else {
308  // here we need to find the child that describes the back_index (solve child in map_lfs_indices)
309  const size_type gt_index = Traits::DOFIndexAccessor::GeometryIndex::geometryType(index);
310  const size_type entity_index = Traits::DOFIndexAccessor::GeometryIndex::entityIndex(index);
311  auto dof_begin = node._fixed_size ? node._gt_dof_offsets.begin() : node._entity_dof_offsets.begin();
312  auto dof_end = node._fixed_size ? node._gt_dof_offsets.end() : node._entity_dof_offsets.end();
313  auto dof_it = std::prev(std::upper_bound(dof_begin, dof_end, back_index));
314  size_type dof_dist = std::distance(dof_begin, dof_it);
315  if (node._fixed_size)
316  _child = dof_dist - gt_index * node._child_count + 1;
317  else
318  _child = dof_dist - (node._gt_entity_offsets[gt_index] + entity_index) * node._child_count + 1;
319  }
320 
321  assert(node.degree() > _child);
322  typename Traits::SizeType _size;
323  // create a dynamic or static index range
324  auto indices = Dune::range(node.degree());
325  // get size for required child
326  Hybrid::forEach(indices, [&](auto i){
327  if (i == _child)
328  _size = node.child(i).size(suffix, index);
329  });
330 
331  return _size;
332  }
333  }
334 
335  public:
336  typename Traits::SizeType offset(const typename Traits::SizeType geometry_type_index, const typename Traits::SizeType entity_index, const typename Traits::SizeType child_index) const
337  {
338  assert(child_index < _child_count);
339  assert(_gt_used[geometry_type_index]);
340  if (_fixed_size)
341  return child_index > 0 ? _gt_dof_offsets[geometry_type_index * _child_count + child_index - 1] : 0;
342  else
343  return child_index > 0 ? _entity_dof_offsets[(_gt_entity_offsets[geometry_type_index] + entity_index) * _child_count + child_index - 1] : 0;
344  }
345 
346  template<typename Node>
347  LocalOrderingBase(Node& node, bool container_blocked, GFSData* gfs_data)
348  : _fixed_size(false)
349  , _fixed_size_possible(false)
350  , _container_blocked(container_blocked)
351  , _max_local_size(0)
352  , _child_count(TypeTree::degree(node))
353  , _children(TypeTree::degree(node),nullptr)
354  , _gfs_data(gfs_data)
355  {
356  TypeTree::applyToTree(node,extract_child_bases<LocalOrderingBase>(_children));
357  }
358 
359  bool fixedSize() const
360  {
361  return _fixed_size;
362  }
363 
364  bool contains(const GeometryType& gt) const
365  {
367  }
368 
369  bool contains_geometry_type(typename Traits::SizeType gt_index) const
370  {
371  return _gt_used[gt_index];
372  }
373 
374  bool contains(typename Traits::SizeType codim) const
375  {
376  return _codim_used.test(codim);
377  }
378 
380  {
381  return _max_local_size;
382  }
383 
384  private:
385 
386  bool update_gfs_data_size(typename Traits::SizeType& size, typename Traits::SizeType& block_count) const
387  {
388  return false;
389  }
390 
391  protected:
392 
393  bool containerBlocked() const
394  {
395  return _container_blocked;
396  }
397 
398  std::size_t childOrderingCount() const
399  {
400  return _child_count;
401  }
402 
404  {
405  return *_children[i];
406  }
407 
409  {
410  return *_children[i];
411  }
412 
414  {
415  _container_blocked = false;
416  }
417 
419 
429  {
430  _fixed_size_possible = true;
431  for (const auto& child : _children)
432  _fixed_size_possible &= child->_fixed_size_possible;
433  }
434 
435 
436 
440  std::size_t _max_local_size;
441 
442  const std::size_t _child_count;
443  std::vector<LocalOrderingBase*> _children;
444 
446  std::vector<bool> _gt_used;
447 
448  std::vector<typename Traits::SizeType> _gt_entity_offsets;
449  std::vector<typename Traits::SizeType> _gt_dof_offsets;
450  std::vector<typename Traits::SizeType> _entity_dof_offsets;
451 
453 
454  };
455 
457 
458  } // namespace PDELab
459 } // namespace Dune
460 
461 #endif // DUNE_PDELAB_ORDERING_LOCALORDERINGBASE_HH
std::size_t index
Definition: interpolate.hh:97
For backward compatibility – Do not use this!
Definition: adaptivity.hh:28
Definition: gridviewordering.hh:46
Definition: gridviewordering.hh:83
Definition: gridviewordering.hh:174
Definition: gridviewordering.hh:231
Definition: gridviewordering.hh:324
Transforms a local ordering (entity-wise order) into a global ordering.
Definition: gridviewordering.hh:440
Entity-wise orderings.
Definition: localorderingbase.hh:30
void map_lfs_indices(const ItIn begin, const ItIn end, ItOut out) const
Set last index of container indices.
Definition: localorderingbase.hh:122
Traits::SizeType maxLocalSize() const
Definition: localorderingbase.hh:379
LocalOrderingTraits< ES, DI, CI, MultiIndexOrder::Inner2Outer > Traits
Definition: localorderingbase.hh:63
const std::size_t _child_count
Definition: localorderingbase.hh:442
bool containerBlocked() const
Definition: localorderingbase.hh:393
void setup_fixed_size_possible()
Initial setup of the flag indicating whether a fixed size ordering is possible.
Definition: localorderingbase.hh:428
void disable_container_blocking()
Definition: localorderingbase.hh:413
std::vector< typename Traits::SizeType > _gt_entity_offsets
Definition: localorderingbase.hh:448
bool contains_geometry_type(typename Traits::SizeType gt_index) const
Definition: localorderingbase.hh:369
static const bool has_dynamic_ordering_children
Definition: localorderingbase.hh:59
Traits::SizeType offset(const typename Traits::SizeType geometry_type_index, const typename Traits::SizeType entity_index, const typename Traits::SizeType child_index) const
Definition: localorderingbase.hh:336
bool _fixed_size_possible
Definition: localorderingbase.hh:438
Traits::SizeType node_size(const Node &node, typename Traits::ContainerIndex suffix, const typename Traits::DOFIndex::EntityIndex &index) const
Gives the size for a given entity and suffix.
Definition: localorderingbase.hh:287
Traits::SizeType size(const typename Traits::DOFIndex::EntityIndex &index) const
Definition: localorderingbase.hh:229
Traits::SizeType size(const typename Traits::SizeType geometry_type_index, const typename Traits::SizeType entity_index) const
Definition: localorderingbase.hh:237
friend struct collect_used_geometry_types_from_cell
Definition: localorderingbase.hh:46
GFSData * _gfs_data
Definition: localorderingbase.hh:452
bool contains(const GeometryType &gt) const
Definition: localorderingbase.hh:364
bool _fixed_size
Definition: localorderingbase.hh:437
std::vector< bool > _gt_used
Definition: localorderingbase.hh:446
bool contains(typename Traits::SizeType codim) const
Definition: localorderingbase.hh:374
Traits::CodimFlag _codim_used
Definition: localorderingbase.hh:445
bool _container_blocked
Definition: localorderingbase.hh:439
friend struct extract_per_entity_sizes_from_cell
Definition: localorderingbase.hh:49
LocalOrderingBase(Node &node, bool container_blocked, GFSData *gfs_data)
Definition: localorderingbase.hh:347
const LocalOrderingBase & childOrdering(typename Traits::SizeType i) const
Definition: localorderingbase.hh:408
void map_local_index(const typename Traits::SizeType geometry_type_index, const typename Traits::SizeType entity_index, typename Traits::TreeIndexView mi, typename Traits::ContainerIndex &ci) const
Definition: localorderingbase.hh:73
impl::GridFunctionSpaceOrderingData< typename Traits::SizeType > GFSData
Definition: localorderingbase.hh:69
Traits::SizeType extract_entity_indices(const typename Traits::DOFIndex::EntityIndex &ei, typename Traits::SizeType child_index, CIOutIterator ci_out, const CIOutIterator ci_end, DIOutIterator di_out=DIOutIterator()) const
Definition: localorderingbase.hh:173
bool fixedSize() const
Definition: localorderingbase.hh:359
std::vector< typename Traits::SizeType > _gt_dof_offsets
Definition: localorderingbase.hh:449
static constexpr auto GT_UNUSED
Definition: localorderingbase.hh:65
LocalOrderingBase & childOrdering(typename Traits::SizeType i)
Definition: localorderingbase.hh:403
static const bool consume_tree_index
Definition: localorderingbase.hh:61
std::size_t childOrderingCount() const
Definition: localorderingbase.hh:398
std::size_t _max_local_size
Definition: localorderingbase.hh:440
std::vector< LocalOrderingBase * > _children
Definition: localorderingbase.hh:443
Traits::SizeType size(const typename Traits::SizeType geometry_type_index, const typename Traits::SizeType entity_index, const typename Traits::SizeType child_index) const
Definition: localorderingbase.hh:252
std::vector< typename Traits::SizeType > _entity_dof_offsets
Definition: localorderingbase.hh:450
static std::size_t entityIndex(const DOFIndex &dof_index)
Definition: ordering/utility.hh:151
static std::size_t geometryType(const DOFIndex &dof_index)
Definition: ordering/utility.hh:145
std::size_t SizeType
Definition: ordering/utility.hh:178
CI ContainerIndex
Definition: ordering/utility.hh:176
std::bitset< max_dim > CodimFlag
Definition: ordering/utility.hh:211
DI::size_type SizeType
Definition: ordering/utility.hh:218
DI::View::TreeIndex TreeIndexView
Definition: ordering/utility.hh:216
DI::size_type size_type
Definition: ordering/utility.hh:219
Definition: ordering/utility.hh:224
Definition: ordering/utility.hh:259