3 #ifndef DUNE_PDELAB_GRIDFUNCTIONSPACE_LFSINDEXCACHE_HH
4 #define DUNE_PDELAB_GRIDFUNCTIONSPACE_LFSINDEXCACHE_HH
9 #include <unordered_map>
11 #include <dune/common/reservedvector.hh>
12 #include <dune/common/exceptions.hh>
13 #include <dune/common/hash.hh>
14 #include <dune/common/iteratorfacades.hh>
16 #include <dune/typetree/typetree.hh>
24 template<
typename Iterator>
26 :
public RandomAccessIteratorFacade<DOFIndexViewIterator<Iterator>,
27 const typename std::iterator_traits<Iterator>::value_type::View,
28 const typename std::iterator_traits<Iterator>::value_type::View
32 friend class RandomAccessIteratorFacade<
34 const typename std::iterator_traits<Iterator>::value_type::View,
35 const typename std::iterator_traits<Iterator>::value_type::View
38 typedef typename std::iterator_traits<Iterator>::value_type::View View;
82 , _tail_length(tail_length)
95 const typename std::iterator_traits<Iterator>::reference
raw_index()
const
102 return _iterator == other._iterator;
122 return other._iterator - _iterator;
127 return _iterator->view(_iterator->treeIndex().size() - _tail_length);
138 std::size_t _tail_length;
143 template<
typename Iterator>
145 :
public TypeTree::TreeVisitor
146 ,
public TypeTree::DynamicTraversal
149 template<
typename LeafLFS,
typename TreePath>
150 void leaf(
const LeafLFS& leaf_lfs, TreePath tp)
152 (*it) = leaf_lfs.size();
157 :
it(leaf_size_container_iterator)
164 template<
typename LFS,
typename Iterator>
168 TypeTree::applyToTree(lfs,visitor);
173 template<
typename DOFIterator,
174 typename ContainerIterator,
175 typename LeafSizeIterator,
176 std::size_t tree_depth,
179 :
public TypeTree::TreeVisitor
180 ,
public TypeTree::DynamicTraversal
183 template<
typename Ordering,
typename TreePath>
184 void leaf(
const Ordering& ordering, TreePath tp)
196 template<
typename Ordering,
typename TreePath>
197 void post(
const Ordering& ordering, TreePath tp)
199 if (Ordering::consume_tree_index)
209 template<
typename Ordering,
typename TreePath>
210 void pre(
const Ordering& ordering, TreePath tp)
214 if (Ordering::consume_tree_index)
222 ContainerIterator container_begin,
223 LeafSizeIterator leaf_size_begin,
224 std::size_t dof_index_tail_length = 0)
225 :
dof_pos(dof_begin,dof_index_tail_length)
226 ,
dof_end(dof_begin,dof_index_tail_length)
236 std::stack<DOFIndexViewIterator<DOFIterator>,ReservedVector<DOFIndexViewIterator<DOFIterator>,tree_depth> >
dof_stack;
237 std::stack<ContainerIterator,ReservedVector<ContainerIterator,tree_depth> >
container_stack;
243 template<
typename LFS,
typename C,
typename CacheTag,
bool fast>
249 DOF_NONCONSTRAINED = 0,
250 DOF_CONSTRAINED = 1<<0,
258 typedef typename LFS::Traits::GridFunctionSpace
GFS;
262 typedef typename Ordering::Traits::DOFIndex
DOFIndex;
267 typedef std::unordered_map<DI,CI>
CIMap;
269 typedef std::unordered_map<const CI*,std::pair<size_type,bool> >
InverseMap;
272 :
public std::pair<const CI*,typename C::mapped_type::mapped_type>
275 typedef typename C::mapped_type::mapped_type
Weight;
279 return *(this->first);
295 , _enable_constraints_caching(enable_constraints_caching)
296 , _container_indices(lfs.maxSize())
297 , _dof_flags(lfs.maxSize(),0)
298 , _constraints_iterators(lfs.maxSize())
299 , _inverse_cache_built(false)
307 _container_indices[0].resize(2);
308 _container_indices[0][0] = 0;
309 _container_indices[0][1] = LFS::Traits::GridFunctionSpace::Ordering::Traits::DOFIndexAccessor::entityIndex(_lfs.dofIndex(0));
314 _container_index_map.clear();
315 for (
typename CIVector::iterator it = _container_indices.begin(); it != _container_indices.end(); ++it)
318 _inverse_map.clear();
319 _inverse_cache_built =
false;
322 typedef ReservedVector<size_type,TypeTree::TreeInfo<LFS>::leafCount> LeafSizeVector;
323 LeafSizeVector leaf_sizes;
324 leaf_sizes.resize(TypeTree::TreeInfo<LFS>::leafCount);
329 typename LFS::Traits::DOFIndexContainer::const_iterator,
330 typename CIVector::iterator,
331 typename LeafSizeVector::const_iterator,
332 TypeTree::TreeInfo<Ordering>::depth,
334 > index_mapper(_lfs._dof_indices->begin(),_container_indices.begin(),leaf_sizes.begin(),_lfs.subSpaceDepth());
335 TypeTree::applyToTree(_lfs.gridFunctionSpace().ordering(),index_mapper);
337 if (_enable_constraints_caching)
339 _constraints.resize(0);
340 std::vector<std::pair<size_type,typename C::const_iterator> > non_dirichlet_constrained_dofs;
345 const CI& container_index = _container_indices[i];
346 const typename C::const_iterator cit = _gfs_constraints.find(container_index);
347 if (cit == _gfs_constraints.end())
349 _dof_flags[i] = DOF_NONCONSTRAINED;
353 if (cit->second.size() == 0)
355 _dof_flags[i] = DOF_CONSTRAINED | DOF_DIRICHLET;
356 _constraints_iterators[i] = make_pair(_constraints.end(),_constraints.end());
360 _dof_flags[i] = DOF_CONSTRAINED;
361 constraint_entry_count += cit->second.size();
362 non_dirichlet_constrained_dofs.push_back(make_pair(i,cit));
366 if (constraint_entry_count > 0)
368 _constraints.resize(constraint_entry_count);
369 typename ConstraintsVector::iterator eit = _constraints.begin();
370 for (
typename std::vector<std::pair<size_type,typename C::const_iterator> >::const_iterator it = non_dirichlet_constrained_dofs.begin();
371 it != non_dirichlet_constrained_dofs.end();
374 _constraints_iterators[it->first].first = eit;
375 for (
typename C::mapped_type::const_iterator cit = it->second->second.begin(); cit != it->second->second.end(); ++cit, ++eit)
377 eit->first = &(cit->first);
378 eit->second = cit->second;
380 _constraints_iterators[it->first].second = eit;
389 return _lfs.dofIndex(i);
394 return _container_indices[i];
400 std::pair<typename CIMap::iterator,bool> r = _container_index_map.insert(std::make_pair(std::ref(i),
CI()));
404 _lfs.gridFunctionSpace().ordering().mapIndex(i.view(),r.first->second);
407 return r.first->second;
412 return _dof_flags[i] & DOF_CONSTRAINED;
417 return _dof_flags[i] & DOF_DIRICHLET;
423 return _constraints_iterators[i].first;
429 return _constraints_iterators[i].second;
444 if (!_inverse_cache_built)
445 build_inverse_cache();
446 return _inverse_map[ci];
451 if (!_inverse_cache_built)
452 build_inverse_cache();
458 if (!_inverse_cache_built)
459 build_inverse_cache();
460 return _extended_offsets[i];
465 return _enable_constraints_caching;
470 struct sort_container_indices
473 bool operator()(
const T* a,
const T* b)
const
475 return std::lexicographical_compare(reversed_iterator(a->end()),reversed_iterator(a->begin()),
476 reversed_iterator(b->end()),reversed_iterator(b->begin())
482 void build_inverse_cache()
487 for (
typename CIVector::const_iterator it = _container_indices.begin(),
488 endit = _container_indices.end();
493 _inverse_map.insert(std::make_pair(&(*it),std::make_pair(i,
false)));
494 if (it->back() != child)
496 _offsets[child+1] = i;
501 std::vector<const ContainerIndex*> extended_cis;
502 extended_cis.reserve(_constraints.size());
504 for (
typename ConstraintsVector::const_iterator it = _constraints.begin(),
505 endit = _constraints.end();
510 if (_inverse_map.count(it->first) == 0)
511 extended_cis.push_back(it->first);
514 std::sort(extended_cis.begin(),extended_cis.end(),sort_container_indices());
516 typename std::vector<const ContainerIndex*>::const_iterator endit = std::unique(extended_cis.begin(),extended_cis.end());
520 for (
typename std::vector<const ContainerIndex*>::const_iterator it = extended_cis.begin(); it != endit; ++it, ++i)
522 _inverse_map.insert(std::make_pair(&(*it),std::make_pair(i,
true)));
523 if (it->back() != child)
525 _extended_offsets[child+1] = i;
530 _inverse_cache_built =
true;
535 const bool _enable_constraints_caching;
537 std::vector<unsigned char> _dof_flags;
538 std::vector<std::pair<ConstraintsIterator,ConstraintsIterator> > _constraints_iterators;
539 mutable CIMap _container_index_map;
543 mutable bool _inverse_cache_built;
546 const C& _gfs_constraints;
551 template<
typename LFS,
typename CacheTag,
bool fast>
558 typedef typename LFS::Traits::GridFunctionSpace
GFS;
562 typedef typename Ordering::Traits::DOFIndex
DOFIndex;
567 typedef std::unordered_map<DI,CI>
CIMap;
569 struct ConstraintsEntry
570 :
public std::pair<const CI*,double>
577 return *(this->first);
591 , _container_indices(lfs.maxSize())
598 , _container_indices(lfs.maxSize())
606 _container_indices[0].resize(2);
607 _container_indices[0][0] = 0;
608 _container_indices[0][1] = LFS::Traits::GridFunctionSpace::Ordering::Traits::DOFIndexAccessor::entityIndex(_lfs.dofIndex(0));
613 _container_index_map.clear();
614 for (
typename CIVector::iterator it = _container_indices.begin(); it != _container_indices.end(); ++it)
618 typedef ReservedVector<size_type,TypeTree::TreeInfo<LFS>::leafCount> LeafSizeVector;
619 LeafSizeVector leaf_sizes;
620 leaf_sizes.resize(TypeTree::TreeInfo<LFS>::leafCount);
625 typename LFS::Traits::DOFIndexContainer::const_iterator,
626 typename CIVector::iterator,
627 typename LeafSizeVector::const_iterator,
628 TypeTree::TreeInfo<Ordering>::depth,
630 > index_mapper(_lfs._dof_indices->begin(),_container_indices.begin(),leaf_sizes.begin(),_lfs.subSpaceDepth());
631 TypeTree::applyToTree(_lfs.gridFunctionSpace().ordering(),index_mapper);
637 return _lfs.dofIndex(i);
642 return _container_indices[i];
648 std::pair<typename CIMap::iterator,bool> r = _container_index_map.insert(std::make_pair(std::ref(i),
CI()));
652 _lfs.gridFunctionSpace().ordering().mapIndex(i.view(),r.first->second);
655 return r.first->second;
670 return _constraints.begin();
675 return _constraints.end();
697 mutable CIMap _container_index_map;
704 template<
typename LFS,
typename C,
bool fast>
710 DOF_NONCONSTRAINED = 0,
711 DOF_CONSTRAINED = 1<<0,
719 typedef typename LFS::Traits::GridFunctionSpace
GFS;
721 typedef typename Ordering::Traits::ContainerIndex
CI;
722 typedef typename Ordering::Traits::DOFIndex
DI;
726 typedef std::unordered_map<DI,CI>
CIMap;
728 struct ConstraintsEntry
729 :
public std::pair<CI,typename C::mapped_type::mapped_type>
732 typedef typename C::mapped_type::mapped_type
Weight;
750 , _dof_flags(lfs.maxSize())
751 , _constraints_iterators(lfs.maxSize())
759 DUNE_THROW(Dune::Exception,
"This function shouldn't be called in fast mode");
763 _constraints.resize(0);
764 std::vector<std::pair<size_type,typename C::const_iterator> > non_dirichlet_constrained_dofs;
766 for (
size_type i = 0; i < _lfs.size(); ++i)
768 const DI& dof_index = _lfs.dofIndex(i);
769 const typename C::const_iterator cit = _gfs_constraints.find(dof_index);
770 if (cit == _gfs_constraints.end())
772 _dof_flags[i] = DOF_NONCONSTRAINED;
776 if (cit->second.size() == 0)
778 _dof_flags[i] = DOF_CONSTRAINED | DOF_DIRICHLET;
779 _constraints_iterators[i] = make_pair(_constraints.end(),_constraints.end());
783 _dof_flags[i] = DOF_CONSTRAINED;
784 constraint_entry_count += cit->second.size();
785 non_dirichlet_constrained_dofs.push_back(make_pair(i,cit));
789 if (constraint_entry_count > 0)
791 _constraints.resize(constraint_entry_count);
792 typename ConstraintsVector::iterator eit = _constraints.begin();
793 for (
typename std::vector<std::pair<size_type,typename C::const_iterator> >::const_iterator it = non_dirichlet_constrained_dofs.begin();
794 it != non_dirichlet_constrained_dofs.end();
797 _constraints_iterators[it->first].first = eit;
798 for (
typename C::mapped_type::const_iterator cit = it->second->second.begin(); cit != it->second->second.end(); ++cit, ++eit)
800 eit->first = cit->first;
801 eit->second = cit->second;
803 _constraints_iterators[it->first].second = eit;
811 return _lfs.dofIndex(i);
816 return CI(_lfs.dofIndex(i)[0]);
826 return _dof_flags[i] & DOF_CONSTRAINED;
831 return _dof_flags[i] & DOF_DIRICHLET;
837 return _constraints_iterators[i].first;
843 return _constraints_iterators[i].second;
860 std::vector<unsigned char> _dof_flags;
861 std::vector<std::pair<ConstraintsIterator,ConstraintsIterator> > _constraints_iterators;
862 mutable CIMap _container_index_map;
865 const C& _gfs_constraints;
870 template<
typename LFS,
bool fast>
877 typedef typename LFS::Traits::GridFunctionSpace
GFS;
880 typedef typename Ordering::Traits::ContainerIndex
CI;
881 typedef typename Ordering::Traits::DOFIndex
DI;
888 typedef std::unordered_map<DI,CI>
CIMap;
890 struct ConstraintsEntry
891 :
public std::pair<const CI*,double>
898 return *(this->first);
929 return CI(_lfs.dofIndex(i)[0]);
949 return _constraints.begin();
954 return _constraints.end();
970 mutable CIMap _container_index_map;
976 template<
typename LFS,
typename C = EmptyTransformation,
bool fast = false>
978 :
public LFSIndexCacheBase<LFS,C,typename LFS::Traits::GridFunctionSpace::Ordering::CacheTag,fast>
983 template<
typename CC>
1000 #endif // DUNE_PDELAB_GRIDFUNCTIONSPACE_LFSINDEXCACHE_HH