4#ifndef DUNE_PDELAB_ORDERING_GRIDVIEWORDERING_HH
5#define DUNE_PDELAB_ORDERING_GRIDVIEWORDERING_HH
7#include <dune/typetree/typetree.hh>
9#include <dune/pdelab/ordering/utility.hh>
10#include <dune/pdelab/ordering/localorderingbase.hh>
11#include <dune/pdelab/ordering/orderingbase.hh>
12#include <dune/pdelab/ordering/leaflocalordering.hh>
13#include <dune/pdelab/ordering/lexicographicordering.hh>
14#include <dune/pdelab/ordering/leafgridviewordering.hh>
22 template<
typename Codims>
23 struct collect_used_codims
24 :
public TypeTree::TreeVisitor
25 ,
public TypeTree::DynamicTraversal
28 template<
typename Node,
typename TreePath>
29 void leaf(Node& node, TreePath tp)
31 node.collect_used_codims(codims);
34 collect_used_codims(Codims& codims_)
43 struct collect_a_priori_fixed_size
44 :
public TypeTree::TreeVisitor
45 ,
public TypeTree::DynamicTraversal
48 template<
typename Node,
typename TreePath>
49 void leaf(Node& node, TreePath tp)
51 node.update_a_priori_fixed_size();
52 any = any || node._fixed_size;
53 all =
all && node._fixed_size;
56 template<
typename Node,
typename TreePath>
57 void pre(Node& node, TreePath tp)
const
59 node._fixed_size =
true;
62 template<
typename Node,
typename Child,
typename TreePath,
typename ChildIndex>
65 node._fixed_size = node._fixed_size &&
child._fixed_size;
68 collect_a_priori_fixed_size()
80 struct update_fixed_size
81 :
public TypeTree::TreeVisitor
82 ,
public TypeTree::DynamicTraversal
85 template<
typename Node,
typename TreePath>
86 void leaf(Node& node, TreePath tp)
const
90 typedef typename Node::Traits::SizeType size_type;
91 const size_type dim = ES::dimension;
92 node._codim_used.reset();
95 for (
const auto&
gt : es.indexSet().types())
97 size_type
size = node.finiteElementMap().size(
gt);
100 node._codim_used[dim -
gt.dim()] = node._codim_used[dim -
gt.dim()] || (
size > 0);
102 node._max_local_size = node.finiteElementMap().maxLocalSize();
106 template<
typename Node,
typename TreePath>
107 void pre(Node& node, TreePath tp)
const
109 if (node._fixed_size)
111 typedef typename Node::Traits::SizeType size_type;
112 const size_type dim = ES::dimension;
113 node._codim_used.reset();
116 node._max_local_size = 0;
120 template<
typename Node,
typename Child,
typename TreePath,
typename ChildIndex>
123 if (node._fixed_size)
125 node._codim_used |=
child._codim_used;
127 std::transform(node._gt_used.begin(),
129 child._gt_used.begin(),
130 node._gt_used.begin(),
131 std::logical_or<bool>());
133 node._max_local_size +=
child._max_local_size;
135 typedef typename Node::Traits::SizeType size_type;
137 const size_type per_gt_size =
child._child_count > 0 ?
child._child_count : 1;
138 const size_type size_offset =
child._child_count > 0 ?
child._child_count - 1 : 0;
145 template<
typename Node,
typename TreePath>
146 void post(Node& node, TreePath tp)
const
148 if (node._fixed_size)
150 typedef typename std::vector<typename Node::Traits::SizeType>::iterator iterator;
152 iterator next_gt_it = node._gt_dof_offsets.begin() +
TypeTree::degree(node);
153 const iterator end_it = node._gt_dof_offsets.end();
155 for (iterator it = node._gt_dof_offsets.begin();
158 std::partial_sum(it,next_gt_it,it);
162 update_fixed_size(
const ES es_)
171 struct pre_collect_used_geometry_types
172 :
public TypeTree::TreeVisitor
173 ,
public TypeTree::DynamicTraversal
176 template<
typename Node,
typename TreePath>
177 void leaf(Node& node, TreePath tp)
const
179 if (!node._fixed_size)
181 node._codim_used.reset();
188 template<
typename Node,
typename TreePath>
189 void pre(Node& node, TreePath tp)
const
194 pre_collect_used_geometry_types(std::size_t dimension)
198 const std::size_t dim;
203 template<
typename Cell>
204 struct collect_used_geometry_types_from_cell_visitor
205 :
public TypeTree::TreeVisitor
206 ,
public TypeTree::DynamicTraversal
209 template<
typename Node,
typename TreePath>
210 void leaf(Node& node, TreePath tp)
const
212 if (!node._fixed_size)
213 node.collect_used_geometry_types_from_cell(cell);
216 collect_used_geometry_types_from_cell_visitor(
const Cell& cell_)
218 , ref_el(
Dune::ReferenceElements<typename Cell::Geometry::ctype,Cell::dimension>::general(cell_.type()))
222 Dune::ReferenceElement<typename Cell::Geometry> ref_el;
227 template<
typename ES>
228 struct post_collect_used_geometry_types
229 :
public TypeTree::TreeVisitor
230 ,
public TypeTree::DynamicTraversal
233 template<
typename Node,
typename TreePath>
234 void leaf(Node& node, TreePath tp)
const
236 if (!node._fixed_size)
238 typedef typename Node::Traits::SizeType size_type;
240 for (
const auto&
gt : es.indexSet().types())
246 std::partial_sum(node._gt_entity_offsets.begin(),node._gt_entity_offsets.end(),node._gt_entity_offsets.begin());
247 node._entity_dof_offsets.assign(node._gt_entity_offsets.back() *
std::max(node._child_count,
static_cast<size_type
>(1)),0);
248 node.setup_fixed_size_possible();
252 template<
typename Node,
typename Child,
typename TreePath,
typename ChildIndex>
255 if (!node._fixed_size)
257 node._codim_used |=
child._codim_used;
259 std::transform(node._gt_used.begin(),
261 child._gt_used.begin(),
262 node._gt_used.begin(),
263 std::logical_or<bool>());
267 template<
typename Node,
typename TreePath>
268 void post(Node& node, TreePath tp)
const
273 post_collect_used_geometry_types(
const ES& es_)
282 template<
typename ES>
283 struct extract_per_entity_sizes_from_cell_visitor
284 :
public TypeTree::TreeVisitor
285 ,
public TypeTree::DynamicTraversal
288 static const std::size_t dim = ES::dimension;
289 typedef typename ES::template Codim<0>::Entity Cell;
290 typedef std::size_t size_type;
292 template<
typename Node,
typename TreePath>
293 void leaf(Node& node, TreePath tp)
295 if (!node._fixed_size)
296 node.extract_per_entity_sizes_from_cell(*cell,gt_sizes);
299 extract_per_entity_sizes_from_cell_visitor(
const ES& es_)
303 , gt_sizes(
Dune::GlobalGeometryTypeIndex::
size(dim),0)
306 void set_cell(
const Cell& cell_)
314 Dune::ReferenceElement<typename Cell::Geometry> ref_el;
315 std::vector<size_type> gt_sizes;
320 template<
typename ES>
321 struct post_extract_per_entity_sizes
322 :
public TypeTree::TreeVisitor
323 ,
public TypeTree::DynamicTraversal
326 typedef std::vector<GeometryType> GTVector;
329 template<
typename Node,
typename TreePath>
330 void leaf(Node& node, TreePath tp)
const
332 if (!node._fixed_size)
335 for (
auto&
size : node._gt_dof_offsets)
336 if (
size == Node::GT_UNUSED)
338 if (node._fixed_size_possible)
340 node._entity_dof_offsets = std::vector<typename Node::Traits::SizeType>();
341 node._fixed_size =
true;
346 template<
typename Node,
typename TreePath>
347 void pre(Node& node, TreePath tp)
const
349 if (!node._fixed_size)
351 node._fixed_size_possible =
true;
352 node._max_local_size = 0;
357 template<
typename Node,
typename Child,
typename TreePath,
typename ChildIndex>
360 if (!node._fixed_size)
362 node._fixed_size_possible = node._fixed_size_possible &&
child._fixed_size;
363 node._max_local_size +=
child._max_local_size;
368 template<
typename Node,
typename TreePath>
369 void post(Node& node, TreePath tp)
const
371 if (!node._fixed_size)
374 typedef typename Node::Traits::SizeType size_type;
375 const size_type dim = ES::dimension;
377 if (node._fixed_size_possible)
382 for (size_type child_index = 0; child_index <
TypeTree::degree(node); ++child_index)
384 const size_type per_gt_size = node.childOrdering(child_index)._child_count > 0 ? node.childOrdering(child_index)._child_count : 1;
385 const size_type size_offset = node.childOrdering(child_index)._child_count > 0 ? node.childOrdering(child_index)._child_count - 1 : 0;
387 node._gt_dof_offsets[
gt *
TypeTree::degree(node) + child_index] = node.childOrdering(child_index)._gt_dof_offsets[
gt * per_gt_size + size_offset];
391 typedef typename std::vector<typename Node::Traits::SizeType>::iterator iterator;
393 const iterator end_it = node._gt_dof_offsets.end();
395 for (iterator it = node._gt_dof_offsets.begin();
400 node._fixed_size =
true;
404 typedef typename Node::Traits::SizeType size_type;
409 if (!node._gt_used[geometry_type_index])
411 const size_type entity_count = node._gt_entity_offsets[geometry_type_index+1] - node._gt_entity_offsets[geometry_type_index];
412 for (size_type entity_index = 0; entity_index < entity_count; ++entity_index)
415 for (size_type child_index = 0; child_index <
TypeTree::degree(node); ++child_index)
416 node._entity_dof_offsets[index++] = (carry += node.childOrdering(child_index).size(geometry_type_index,entity_index));
424 post_extract_per_entity_sizes(
const ES& es_)
433 template<
typename LocalOrdering>
436 ,
public VirtualOrderingBase<typename LocalOrdering::Traits::DOFIndex,
437 typename LocalOrdering::Traits::ContainerIndex>
438 ,
public OrderingBase<typename LocalOrdering::Traits::DOFIndex,
439 typename LocalOrdering::Traits::ContainerIndex>
442 typedef typename LocalOrdering::Traits Traits;
444 static const bool has_dynamic_ordering_children =
false;
446 static const bool consume_tree_index =
false;
451 typedef OrderingBase<
452 typename LocalOrdering::Traits::DOFIndex,
453 typename LocalOrdering::Traits::ContainerIndex
456 using EntitySet =
typename Traits::EntitySet;
466 bool container_blocked,
467 typename BaseT::GFSData *gfs_data,
468 const EntitySet &entity_Set)
469 :
NodeT(local_ordering),
470 BaseT(*this, container_blocked, gfs_data, this), _es(entity_Set) {
473 localOrdering().disable_container_blocking();
482 : NodeT(r.nodeStorage())
485 , _gt_dof_offsets(r._gt_dof_offsets)
486 , _gt_entity_offsets(r._gt_entity_offsets)
487 , _entity_dof_offsets(r._entity_dof_offsets)
489 this->setDelegate(
this);
493 : NodeT(r.nodeStorage())
494 , BaseT(
std::move(r))
495 , _es(
std::move(r._es))
496 , _gt_dof_offsets(
std::move(r._gt_dof_offsets))
497 , _gt_entity_offsets(
std::move(r._gt_entity_offsets))
498 , _entity_dof_offsets(
std::move(r._entity_dof_offsets))
500 this->setDelegate(
this);
503 virtual ~GridViewOrdering()
override =
default;
514 typename Traits::SizeType
size(
typename Traits::ContainerIndex suffix)
const
516 using size_type =
typename Traits::SizeType;
517 if (suffix.size() == Traits::ContainerIndex::max_depth)
519 if (suffix.size() == 0)
523 typename Traits::DOFIndex::EntityIndex entity_index;
526 auto back_index = suffix.back();
528 if (_container_blocked)
531 auto dof_begin = _fixed_size ? _gt_dof_offsets.begin() : _entity_dof_offsets.begin();
532 auto dof_end = _fixed_size ? _gt_dof_offsets.end() : _entity_dof_offsets.end();
533 auto dof_it = std::prev(std::upper_bound(dof_begin, dof_end, back_index));
534 size_type dof_dist = std::distance(dof_begin, dof_it);
537 Traits::DOFIndexAccessor::GeometryIndex::store(entity_index,dof_dist,~size_type{0});
539 auto gt_begin = _gt_entity_offsets.begin();
540 auto gt_end = _gt_entity_offsets.end();
541 auto gt_it = std::prev(std::upper_bound(gt_begin, gt_end, dof_dist));
542 size_type
gt = std::distance(gt_begin, gt_it);
543 assert(dof_dist >= *gt_it);
544 size_type ei = dof_dist - *gt_it;
545 Traits::DOFIndexAccessor::GeometryIndex::store(entity_index,
gt,ei);
549 return localOrdering().size(suffix, entity_index);
552 LocalOrdering& localOrdering()
554 return this->
template child<0>();
557 const LocalOrdering& localOrdering()
const
559 return this->
template child<0>();
562 virtual void map_index_dynamic(
typename Traits::DOFIndexView di,
typename Traits::ContainerIndex& ci)
const override
567 typename Traits::ContainerIndex mapIndex(
const typename Traits::DOFIndex& di)
const
569 typename Traits::ContainerIndex ci;
570 mapIndex(di.view(),ci);
574 void mapIndex(
typename Traits::DOFIndexView di,
typename Traits::ContainerIndex& ci)
const
576 typedef typename Traits::SizeType size_type;
577 const size_type geometry_type_index = Traits::DOFIndexAccessor::geometryType(di);
578 const size_type entity_index = Traits::DOFIndexAccessor::entityIndex(di);
579 localOrdering().map_local_index(geometry_type_index,entity_index,di.treeIndex(),ci);
580 if (_container_blocked)
584 ci.push_back(_gt_dof_offsets[geometry_type_index] + entity_index);
588 ci.push_back(_entity_dof_offsets[_gt_entity_offsets[geometry_type_index] + entity_index]);
595 ci.back() += _gt_dof_offsets[geometry_type_index] + entity_index * localOrdering().size(geometry_type_index,entity_index);
599 ci.back() += _entity_dof_offsets[_gt_entity_offsets[geometry_type_index] + entity_index];
604 template<
typename ItIn,
typename ItOut>
605 void map_lfs_indices(
const ItIn begin,
const ItIn end, ItOut out)
const
607 typedef typename Traits::SizeType size_type;
608 if (_container_blocked)
611 for (ItIn in = begin; in != end; ++in, ++out)
613 const size_type geometry_type_index = Traits::DOFIndexAccessor::geometryType(*in);
614 const size_type entity_index = Traits::DOFIndexAccessor::entityIndex(*in);
615 out->push_back(_gt_dof_offsets[geometry_type_index] + entity_index);
618 for (ItIn in = begin; in != end; ++in, ++out)
620 const size_type geometry_type_index = Traits::DOFIndexAccessor::geometryType(*in);
621 const size_type entity_index = Traits::DOFIndexAccessor::entityIndex(*in);
622 out->push_back(_entity_dof_offsets[_gt_entity_offsets[geometry_type_index] + entity_index]);
625 else if (_fixed_size)
627 for (ItIn in = begin; in != end; ++in, ++out)
629 const size_type geometry_type_index = Traits::DOFIndexAccessor::geometryType(*in);
630 const size_type entity_index = Traits::DOFIndexAccessor::entityIndex(*in);
631 out->back() += _gt_dof_offsets[geometry_type_index] + entity_index * localOrdering().size(geometry_type_index,entity_index);
636 for (ItIn in = begin; in != end; ++in, ++out)
638 const size_type geometry_type_index = Traits::DOFIndexAccessor::geometryType(*in);
639 const size_type entity_index = Traits::DOFIndexAccessor::entityIndex(*in);
640 out->back() += _entity_dof_offsets[_gt_entity_offsets[geometry_type_index] + entity_index];
645 template<
typename CIOutIterator>
646 typename Traits::SizeType
647 extract_entity_indices(
const typename Traits::DOFIndex::EntityIndex& ei,
648 typename Traits::SizeType child_index,
649 CIOutIterator ci_out,
const CIOutIterator ci_end)
const
651 typedef typename Traits::SizeType size_type;
653 const size_type geometry_type_index = Traits::DOFIndexAccessor::GeometryIndex::geometryType(ei);
654 const size_type entity_index = Traits::DOFIndexAccessor::GeometryIndex::entityIndex(ei);
656 if (_container_blocked)
659 for (; ci_out != ci_end; ++ci_out)
661 ci_out->push_back(_gt_dof_offsets[geometry_type_index] + entity_index);
664 for (; ci_out != ci_end; ++ci_out)
666 ci_out->push_back(_entity_dof_offsets[_gt_entity_offsets[geometry_type_index] + entity_index]);
669 else if (_fixed_size)
671 for (; ci_out != ci_end; ++ci_out)
673 ci_out->back() += _gt_dof_offsets[geometry_type_index] + entity_index * localOrdering().size(geometry_type_index,entity_index);
678 for (; ci_out != ci_end; ++ci_out)
680 ci_out->back() += _entity_dof_offsets[_gt_entity_offsets[geometry_type_index] + entity_index];
691 typedef typename Traits::SizeType size_type;
692 using ES =
typename Traits::EntitySet;
693 const size_type dim = ES::dimension;
695 typename ES::CodimMask codims;
700 for (
typename ES::dim_type codim = 0; codim <= ES::dimension; ++codim)
701 if (codims.test(codim))
707 collect_a_priori_fixed_size fixed_size_collector;
709 _fixed_size = localOrdering().fixedSize();
713 if (fixed_size_collector.any)
719 if (!fixed_size_collector.all)
723 using Element =
typename ES::template Codim<0>::Entity;
725 for (
const auto& element : elements(_es))
727 TypeTree::applyToTree(localOrdering(),collect_used_geometry_types_from_cell_visitor<Element>(element));
733 extract_per_entity_sizes_from_cell_visitor<ES> visitor(_es);
734 for (
const auto& element : elements(_es))
736 visitor.set_cell(element);
742 _codim_used = localOrdering()._codim_used;
747 _gt_dof_offsets.assign(gt_index_count + 1,0);
753 for (
const auto&
gt : _es.indexSet().types())
756 size_type gt_size = localOrdering().size(gt_index,0);
757 const size_type gt_entity_count = _es.indexSet().size(
gt);
758 _size += gt_size * gt_entity_count;
759 if (_container_blocked)
760 gt_size = gt_size > 0;
761 _gt_dof_offsets[gt_index + 1] = gt_size * gt_entity_count;
764 std::partial_sum(_gt_dof_offsets.begin(),_gt_dof_offsets.end(),_gt_dof_offsets.begin());
765 _block_count = _gt_dof_offsets.back();
767 _codim_fixed_size.set();
772 _gt_entity_offsets.assign(gt_index_count + 1,0);
774 for (
const auto&
gt : _es.indexSet().types())
779 _gt_entity_offsets[gt_index + 1] = _es.indexSet().size(
gt);
782 std::partial_sum(_gt_entity_offsets.begin(),_gt_entity_offsets.end(),_gt_entity_offsets.begin());
783 _entity_dof_offsets.assign(_gt_entity_offsets.back()+1,0);
786 size_type carry_size = 0;
787 size_type carry_block = 0;
791 if (!localOrdering().contains_geometry_type(gt_index))
793 const size_type entity_count = _gt_entity_offsets[gt_index + 1] - _gt_entity_offsets[gt_index];
794 for (size_type entity_index = 0; entity_index < entity_count; ++entity_index)
796 const size_type
size = localOrdering().size(gt_index,entity_index);
798 carry_block += (_container_blocked ? (
size > 0) :
size);
799 _entity_dof_offsets[++index] = carry_block;
800 _block_count += (
size > 0);
804 _block_count = _block_count;
806 _codim_fixed_size.reset();
809 _max_local_size = localOrdering().maxLocalSize();
816 using BaseT::_container_blocked;
817 using BaseT::_fixed_size;
818 using BaseT::_max_local_size;
820 using BaseT::_block_count;
821 using BaseT::_codim_used;
822 using BaseT::_codim_fixed_size;
824 typename Traits::EntitySet _es;
825 std::vector<typename Traits::SizeType> _gt_dof_offsets;
826 std::vector<typename Traits::SizeType> _gt_entity_offsets;
827 std::vector<typename Traits::SizeType> _entity_dof_offsets;
static constexpr std::size_t index(const GeometryType >)
Compute the index for the given geometry type over all dimensions.
Definition: typeindex.hh:138
static constexpr std::size_t size(std::size_t maxdim)
Compute total number of geometry types up to and including the given dimension.
Definition: typeindex.hh:125
Transforms a local ordering (entity-wise order) into a global ordering.
Definition: gridviewordering.hh:440
GridViewOrdering(const typename NodeT::NodeStorage &local_ordering, bool container_blocked, typename BaseT::GFSData *gfs_data, const EntitySet &entity_Set)
Construct ordering object.
Definition: gridviewordering.hh:465
Traits::SizeType size(typename Traits::ContainerIndex suffix) const
Gives the size for a given suffix.
Definition: gridviewordering.hh:514
Base class for composite nodes based on variadic templates.
Definition: compositenode.hh:28
std::tuple< std::shared_ptr< Children >... > NodeStorage
The type used for storing the children.
Definition: compositenode.hh:36
bool gt(const T &first, const T &second, typename EpsilonType< T >::Type epsilon)
test if first greater than second
Definition: float_cmp.cc:158
unspecified value type referenceElement(T &&... t)
Returns a reference element for the objects t....
constexpr auto max
Function object that returns the greater of the given values.
Definition: hybridutilities.hh:484
std::size_t degree(const Node &node)
Returns the degree of node as run time information.
Definition: nodeinterface.hh:79
void applyToTree(Tree &&tree, Visitor &&visitor)
Apply visitor to TypeTree.
Definition: traversal.hh:239
constexpr All all
PartitionSet for all partitions.
Definition: partitionset.hh:295
Dune namespace.
Definition: alignedallocator.hh:13
constexpr std::integral_constant< std::size_t, sizeof...(II)> size(std::integer_sequence< T, II... >)
Return the size of the sequence.
Definition: integersequence.hh:75
constexpr std::bool_constant<((II==value)||...)> contains(std::integer_sequence< T, II... >, std::integral_constant< T, value >)
Checks whether or not a given sequence contains a value.
Definition: integersequence.hh:137
void afterChild(T &&, Child &&, TreePath, ChildIndex) const
Method for child-parent traversal.
Definition: visitor.hh:122
void post(T &&, TreePath) const
Method for postfix tree traversal.
Definition: visitor.hh:83
void leaf(T &&, TreePath) const
Method for leaf traversal.
Definition: visitor.hh:93
void pre(T &&, TreePath) const
Method for prefix tree traversal.
Definition: visitor.hh:60
std::size_t fixedSize
The number of data items per index if it is fixed, 0 otherwise.
Definition: variablesizecommunicator.hh:264