dune-pdelab  2.5-dev
lfsindexcache.hh
Go to the documentation of this file.
1 // -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2 // vi: set et ts=4 sw=2 sts=2:
3 #ifndef DUNE_PDELAB_GRIDFUNCTIONSPACE_LFSINDEXCACHE_HH
4 #define DUNE_PDELAB_GRIDFUNCTIONSPACE_LFSINDEXCACHE_HH
5 
6 #include <vector>
7 #include <stack>
8 #include <algorithm>
9 #include <unordered_map>
10 
11 #include <dune/common/reservedvector.hh>
12 #include <dune/common/exceptions.hh>
13 #include <dune/common/hash.hh>
14 #include <dune/common/iteratorfacades.hh>
15 
16 #include <dune/typetree/typetree.hh>
17 
20 
21 namespace Dune {
22  namespace PDELab {
23 
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
29  >
30  {
31 
32  friend class RandomAccessIteratorFacade<
33  DOFIndexViewIterator,
34  const typename std::iterator_traits<Iterator>::value_type::View,
35  const typename std::iterator_traits<Iterator>::value_type::View
36  >;
37 
38  typedef typename std::iterator_traits<Iterator>::value_type::View View;
39 
40  public:
41 
42  // Add support for returning non-references from iterator.
43  // We need a little bit of magic to make operator->() work for this iterator
44  // because we return a temporary object from dereference(), and the standard
45  // implementation of operator->() in the facade tries to take the address of
46  // that temporary, which the compiler will vehemently object to... ;-)
47  //
48  // So I borrowed the following neat little trick from Boost's iterator library:
49  // The proxy object stores a copy of the temporary View object, and operator()->
50  // returns the proxy object to the caller. As mandated by the standard, the compiler
51  // will then attempt to repeat the operator->() on the returned object and get the
52  // address of the copy stored in the (temporary) proxy object. That proxy object
53  // is guaranteed to live until the next sequence point, and that is precisely as
54  // long as we have to guarantee the validity of the pointer to our View object.
55  // Problem solved - and another example of how difficult it is to get this low-level
56  // stuff implemented on the same level as Boost...
57  struct proxy
58  {
59 
60  explicit proxy(const View& v)
61  : _tmp(v)
62  {}
63 
64  View* operator->()
65  {
66  return &_tmp;
67  }
68 
69  View _tmp;
70  };
71 
72  // The proxy object will stand in as a pointer
73  typedef proxy pointer;
74 
76  : _iterator()
77  , _tail_length(0)
78  {}
79 
80  explicit DOFIndexViewIterator(Iterator it, std::size_t tail_length = 0)
81  : _iterator(it)
82  , _tail_length(tail_length)
83  {}
84 
85  void cut_back()
86  {
87  ++_tail_length;
88  }
89 
90  void restore_back()
91  {
92  --_tail_length;
93  }
94 
95  const typename std::iterator_traits<Iterator>::reference raw_index() const
96  {
97  return *_iterator;
98  }
99 
100  bool equals(const DOFIndexViewIterator& other) const
101  {
102  return _iterator == other._iterator;
103  }
104 
105  void increment()
106  {
107  ++_iterator;
108  }
109 
110  void decrement()
111  {
112  --_iterator;
113  }
114 
115  void advance(int n)
116  {
117  _iterator += n;
118  }
119 
120  std::ptrdiff_t distanceTo(DOFIndexViewIterator& other) const
121  {
122  return other._iterator - _iterator;
123  }
124 
125  const View dereference() const
126  {
127  return _iterator->view(_iterator->treeIndex().size() - _tail_length);
128  }
129 
130  pointer operator->() const
131  {
132  return pointer(dereference());
133  }
134 
135  private:
136 
137  Iterator _iterator;
138  std::size_t _tail_length;
139 
140  };
141 
142 
143  template<typename Iterator>
145  : public TypeTree::TreeVisitor
146  , public TypeTree::DynamicTraversal
147  {
148 
149  template<typename LeafLFS, typename TreePath>
150  void leaf(const LeafLFS& leaf_lfs, TreePath tp)
151  {
152  (*it) = leaf_lfs.size();
153  ++it;
154  }
155 
156  extract_lfs_leaf_size_visitor(Iterator leaf_size_container_iterator)
157  : it(leaf_size_container_iterator)
158  {}
159 
160  Iterator it;
161 
162  };
163 
164  template<typename LFS, typename Iterator>
165  Iterator extract_lfs_leaf_sizes(const LFS& lfs, Iterator it)
166  {
168  TypeTree::applyToTree(lfs,visitor);
169  return visitor.it;
170  }
171 
172 
173  template<typename DOFIterator,
174  typename ContainerIterator,
175  typename LeafSizeIterator,
176  std::size_t tree_depth>
178  : public TypeTree::TreeVisitor
179  , public TypeTree::DynamicTraversal
180  {
181 
182  template<typename Ordering, typename TreePath>
183  void leaf(const Ordering& ordering, TreePath tp)
184  {
185  std::size_t leaf_size = *(leaf_size_pos++);
186  dof_end += leaf_size;
187  ordering.map_lfs_indices(dof_pos,dof_end,container_pos);
188  dof_pos = dof_end;
189  container_pos += leaf_size;
190  }
191 
192  template<typename Ordering, typename TreePath>
193  void post(const Ordering& ordering, TreePath tp)
194  {
195  if (Ordering::consume_tree_index)
196  {
197  dof_pos.restore_back();
198  dof_end.restore_back();
199  }
200  ordering.map_lfs_indices(dof_stack.top(),dof_end,container_stack.top());
201  dof_stack.pop();
202  container_stack.pop();
203  }
204 
205  template<typename Ordering, typename TreePath>
206  void pre(const Ordering& ordering, TreePath tp)
207  {
208  dof_stack.push(dof_pos);
209  container_stack.push(container_pos);
210  if (Ordering::consume_tree_index)
211  {
212  dof_pos.cut_back();
213  dof_end.cut_back();
214  }
215  }
216 
218  ContainerIterator container_begin,
219  LeafSizeIterator leaf_size_begin,
220  std::size_t dof_index_tail_length = 0)
221  : dof_pos(dof_begin,dof_index_tail_length)
222  , dof_end(dof_begin,dof_index_tail_length)
223  , container_pos(container_begin)
224  , leaf_size_pos(leaf_size_begin)
225  {}
226 
227 
230  ContainerIterator container_pos;
231  LeafSizeIterator leaf_size_pos;
232  std::stack<DOFIndexViewIterator<DOFIterator>,ReservedVector<DOFIndexViewIterator<DOFIterator>,tree_depth> > dof_stack;
233  std::stack<ContainerIterator,ReservedVector<ContainerIterator,tree_depth> > container_stack;
234 
235  };
236 
237 
238 
239  template<typename LFS, typename C, typename CacheTag>
241  {
242 
243  enum DOFFlags
244  {
245  DOF_NONCONSTRAINED = 0,
246  DOF_CONSTRAINED = 1<<0,
247  DOF_DIRICHLET = 1<<1
248  };
249 
250  public:
251 
252  typedef LFS LocalFunctionSpace;
253 
254  typedef typename LFS::Traits::GridFunctionSpace GFS;
255  typedef typename GFS::Ordering Ordering;
256  typedef typename Ordering::Traits::ContainerIndex ContainerIndex;
257  typedef ContainerIndex CI;
258  typedef typename Ordering::Traits::DOFIndex DOFIndex;
259  typedef DOFIndex DI;
260  typedef std::size_t size_type;
261 
262  typedef std::vector<CI> CIVector;
263  typedef std::unordered_map<DI,CI> CIMap;
264 
265  typedef std::unordered_map<const CI*,std::pair<size_type,bool> > InverseMap;
266 
268  : public std::pair<const CI*,typename C::mapped_type::mapped_type>
269  {
270  typedef CI ContainerIndex;
271  typedef typename C::mapped_type::mapped_type Weight;
272 
273  const ContainerIndex& containerIndex() const
274  {
275  return *(this->first);
276  }
277 
278  const Weight& weight() const
279  {
280  return this->second;
281  }
282  };
283 
284  //typedef std::pair<CI,typename C::mapped_type::mapped_type> ConstraintsEntry;
285 
286  typedef std::vector<ConstraintsEntry> ConstraintsVector;
287  typedef typename ConstraintsVector::const_iterator ConstraintsIterator;
288 
289  LFSIndexCacheBase(const LFS& lfs, const C& constraints, bool enable_constraints_caching)
290  : _lfs(lfs)
291  , _enable_constraints_caching(enable_constraints_caching)
292  , _container_indices(lfs.maxSize())
293  , _dof_flags(lfs.maxSize(),0)
294  , _constraints_iterators(lfs.maxSize())
295  , _inverse_cache_built(false)
296  , _gfs_constraints(constraints)
297  {
298  }
299 
300  void update()
301  {
302  // clear out existing state
303  _container_index_map.clear();
304  for (typename CIVector::iterator it = _container_indices.begin(); it != _container_indices.end(); ++it)
305  it->clear();
306 
307  _inverse_map.clear();
308  _inverse_cache_built = false;
309 
310  // extract size for all leaf spaces (into a flat list)
311  typedef ReservedVector<size_type,TypeTree::TreeInfo<LFS>::leafCount> LeafSizeVector;
312  LeafSizeVector leaf_sizes;
313  leaf_sizes.resize(TypeTree::TreeInfo<LFS>::leafCount);
314  extract_lfs_leaf_sizes(_lfs,leaf_sizes.begin());
315 
316  // perform the actual mapping
318  typename LFS::Traits::DOFIndexContainer::const_iterator,
319  typename CIVector::iterator,
320  typename LeafSizeVector::const_iterator,
321  TypeTree::TreeInfo<Ordering>::depth
322  > index_mapper(_lfs._dof_indices->begin(),_container_indices.begin(),leaf_sizes.begin(),_lfs.subSpaceDepth());
323  TypeTree::applyToTree(_lfs.gridFunctionSpace().ordering(),index_mapper);
324 
325  if (_enable_constraints_caching)
326  {
327  _constraints.resize(0);
328  std::vector<std::pair<size_type,typename C::const_iterator> > non_dirichlet_constrained_dofs;
329  size_type constraint_entry_count = 0;
330  for (size_type i = 0; i < _lfs.size(); ++i)
331  {
332  const CI& container_index = _container_indices[i];
333  const typename C::const_iterator cit = _gfs_constraints.find(container_index);
334  if (cit == _gfs_constraints.end())
335  {
336  _dof_flags[i] = DOF_NONCONSTRAINED;
337  continue;
338  }
339 
340  if (cit->second.size() == 0)
341  {
342  _dof_flags[i] = DOF_CONSTRAINED | DOF_DIRICHLET;
343  _constraints_iterators[i] = make_pair(_constraints.end(),_constraints.end());
344  }
345  else
346  {
347  _dof_flags[i] = DOF_CONSTRAINED;
348  constraint_entry_count += cit->second.size();
349  non_dirichlet_constrained_dofs.push_back(make_pair(i,cit));
350  }
351  }
352 
353  if (constraint_entry_count > 0)
354  {
355  _constraints.resize(constraint_entry_count);
356  typename ConstraintsVector::iterator eit = _constraints.begin();
357  for (typename std::vector<std::pair<size_type,typename C::const_iterator> >::const_iterator it = non_dirichlet_constrained_dofs.begin();
358  it != non_dirichlet_constrained_dofs.end();
359  ++it)
360  {
361  _constraints_iterators[it->first].first = eit;
362  for (typename C::mapped_type::const_iterator cit = it->second->second.begin(); cit != it->second->second.end(); ++cit, ++eit)
363  {
364  eit->first = &(cit->first);
365  eit->second = cit->second;
366  }
367  _constraints_iterators[it->first].second = eit;
368  }
369  }
370  }
371  }
372 
373  const DI& dofIndex(size_type i) const
374  {
375  return _lfs.dofIndex(i);
376  }
377 
378  const CI& containerIndex(size_type i) const
379  {
380  return _container_indices[i];
381  }
382 
383  const CI& containerIndex(const DI& i) const
384  {
385  // look up DOFIndex i
386  std::pair<typename CIMap::iterator,bool> r = _container_index_map.insert(std::make_pair(std::ref(i),CI()));
387 
388  // i did not exist in the cache, map it into the newly inserted container index
389  if (r.second)
390  _lfs.gridFunctionSpace().ordering().mapIndex(i.view(),r.first->second);
391 
392  // return cached container index
393  return r.first->second;
394  }
395 
396  bool isConstrained(size_type i) const
397  {
398  return _dof_flags[i] & DOF_CONSTRAINED;
399  }
400 
401  bool isDirichletConstraint(size_type i) const
402  {
403  return _dof_flags[i] & DOF_DIRICHLET;
404  }
405 
406  ConstraintsIterator constraintsBegin(size_type i) const
407  {
408  assert(isConstrained(i));
409  return _constraints_iterators[i].first;
410  }
411 
412  ConstraintsIterator constraintsEnd(size_type i) const
413  {
414  assert(isConstrained(i));
415  return _constraints_iterators[i].second;
416  }
417 
418  const LocalFunctionSpace& localFunctionSpace() const
419  {
420  return _lfs;
421  }
422 
423  size_type size() const
424  {
425  return _lfs.size();
426  }
427 
428  std::pair<size_type,bool> localIndex(const ContainerIndex& ci) const
429  {
430  if (!_inverse_cache_built)
431  build_inverse_cache();
432  return _inverse_map[ci];
433  }
434 
435  size_type offset(size_type i) const
436  {
437  if (!_inverse_cache_built)
438  build_inverse_cache();
439  return _offsets[i];
440  }
441 
442  size_type extendedOffset(size_type i) const
443  {
444  if (!_inverse_cache_built)
445  build_inverse_cache();
446  return _extended_offsets[i];
447  }
448 
450  {
451  return _enable_constraints_caching;
452  }
453 
454  private:
455 
456  struct sort_container_indices
457  {
458  template<typename T>
459  bool operator()(const T* a, const T* b) const
460  {
461  return std::lexicographical_compare(reversed_iterator(a->end()),reversed_iterator(a->begin()),
462  reversed_iterator(b->end()),reversed_iterator(b->begin())
463  );
464  }
465  };
466 
467 
468  void build_inverse_cache()
469  {
470  size_type i = 0;
471  size_type child = 0;
472  _offsets[0] = 0;
473  for (typename CIVector::const_iterator it = _container_indices.begin(),
474  endit = _container_indices.end();
475  it != endit;
476  ++it, ++i
477  )
478  {
479  _inverse_map.insert(std::make_pair(&(*it),std::make_pair(i,false)));
480  if (it->back() != child)
481  {
482  _offsets[child+1] = i;
483  ++child;
484  }
485  }
486 
487  std::vector<const ContainerIndex*> extended_cis;
488  extended_cis.reserve(_constraints.size());
489 
490  for (typename ConstraintsVector::const_iterator it = _constraints.begin(),
491  endit = _constraints.end();
492  it != endit;
493  ++it
494  )
495  {
496  if (_inverse_map.count(it->first) == 0)
497  extended_cis.push_back(it->first);
498  }
499 
500  std::sort(extended_cis.begin(),extended_cis.end(),sort_container_indices());
501 
502  typename std::vector<const ContainerIndex*>::const_iterator endit = std::unique(extended_cis.begin(),extended_cis.end());
503 
504  i = 0;
505  child = 0;
506  for (typename std::vector<const ContainerIndex*>::const_iterator it = extended_cis.begin(); it != endit; ++it, ++i)
507  {
508  _inverse_map.insert(std::make_pair(&(*it),std::make_pair(i,true)));
509  if (it->back() != child)
510  {
511  _extended_offsets[child+1] = i;
512  ++child;
513  }
514  }
515 
516  _inverse_cache_built = true;
517 
518  }
519 
520  const LFS& _lfs;
521  const bool _enable_constraints_caching;
522  CIVector _container_indices;
523  std::vector<unsigned char> _dof_flags;
524  std::vector<std::pair<ConstraintsIterator,ConstraintsIterator> > _constraints_iterators;
525  mutable CIMap _container_index_map;
526  ConstraintsVector _constraints;
529  mutable bool _inverse_cache_built;
530  mutable InverseMap _inverse_map;
531 
532  const C& _gfs_constraints;
533 
534  };
535 
536 
537  template<typename LFS, typename CacheTag>
539  {
540 
541  public:
542 
543  typedef LFS LocalFunctionSpace;
544  typedef typename LFS::Traits::GridFunctionSpace GFS;
545  typedef typename GFS::Ordering Ordering;
546  typedef typename Ordering::Traits::ContainerIndex ContainerIndex;
547  typedef ContainerIndex CI;
548  typedef typename Ordering::Traits::DOFIndex DOFIndex;
549  typedef DOFIndex DI;
550  typedef std::size_t size_type;
551 
552  typedef std::vector<CI> CIVector;
553  typedef std::unordered_map<DI,CI> CIMap;
554 
555  struct ConstraintsEntry
556  : public std::pair<const CI*,double>
557  {
558  typedef CI ContainerIndex;
559  typedef double Weight;
560 
561  const ContainerIndex& containerIndex() const
562  {
563  return *(this->first);
564  }
565 
566  const Weight& weight() const
567  {
568  return this->second;
569  }
570  };
571 
572  typedef std::vector<ConstraintsEntry> ConstraintsVector;
573  typedef typename ConstraintsVector::const_iterator ConstraintsIterator;
574 
575  explicit LFSIndexCacheBase(const LFS& lfs)
576  : _lfs(lfs)
577  , _container_indices(lfs.maxSize())
578  {
579  }
580 
581  template<typename C>
582  LFSIndexCacheBase(const LFS& lfs, const C& c, bool enable_constraints_caching)
583  : _lfs(lfs)
584  , _container_indices(lfs.maxSize())
585  {
586  }
587 
588 
589  void update()
590  {
591  // clear out existing state
592  _container_index_map.clear();
593  for (typename CIVector::iterator it = _container_indices.begin(); it != _container_indices.end(); ++it)
594  it->clear();
595 
596  // extract size for all leaf spaces (into a flat list)
597  typedef ReservedVector<size_type,TypeTree::TreeInfo<LFS>::leafCount> LeafSizeVector;
598  LeafSizeVector leaf_sizes;
599  leaf_sizes.resize(TypeTree::TreeInfo<LFS>::leafCount);
600  extract_lfs_leaf_sizes(_lfs,leaf_sizes.begin());
601 
602  // perform the actual mapping
604  typename LFS::Traits::DOFIndexContainer::const_iterator,
605  typename CIVector::iterator,
606  typename LeafSizeVector::const_iterator,
607  TypeTree::TreeInfo<Ordering>::depth
608  > index_mapper(_lfs._dof_indices->begin(),_container_indices.begin(),leaf_sizes.begin(),_lfs.subSpaceDepth());
609  TypeTree::applyToTree(_lfs.gridFunctionSpace().ordering(),index_mapper);
610  }
611 
612  const DI& dofIndex(size_type i) const
613  {
614  return _lfs.dofIndex(i);
615  }
616 
617  const CI& containerIndex(size_type i) const
618  {
619  return _container_indices[i];
620  }
621 
622  const CI& containerIndex(const DI& i) const
623  {
624  // look up DOFIndex i
625  std::pair<typename CIMap::iterator,bool> r = _container_index_map.insert(std::make_pair(std::ref(i),CI()));
626 
627  // i did not exist in the cache, map it into the newly inserted container index
628  if (r.second)
629  _lfs.gridFunctionSpace().ordering().mapIndex(i.view(),r.first->second);
630 
631  // return cached container index
632  return r.first->second;
633  }
634 
635  bool isConstrained(size_type i) const
636  {
637  return false;
638  }
639 
640  bool isDirichletConstraint(size_type i) const
641  {
642  return false;
643  }
644 
645  ConstraintsIterator constraintsBegin(size_type i) const
646  {
647  return _constraints.begin();
648  }
649 
650  ConstraintsIterator constraintsEnd(size_type i) const
651  {
652  return _constraints.end();
653  }
654 
655  const LocalFunctionSpace& localFunctionSpace() const
656  {
657  return _lfs;
658  }
659 
660  size_type size() const
661  {
662  return _lfs.size();
663  }
664 
666  {
667  return false;
668  }
669 
670  private:
671 
672  const LFS& _lfs;
673  CIVector _container_indices;
674  mutable CIMap _container_index_map;
675  const ConstraintsVector _constraints;
676 
677  };
678 
679 
680 
681  template<typename LFS, typename C>
683  {
684 
685  enum DOFFlags
686  {
687  DOF_NONCONSTRAINED = 0,
688  DOF_CONSTRAINED = 1<<0,
689  DOF_DIRICHLET = 1<<1
690  };
691 
692  public:
693 
694  typedef LFS LocalFunctionSpace;
695 
696  typedef typename LFS::Traits::GridFunctionSpace GFS;
697  typedef typename GFS::Ordering Ordering;
698  typedef typename Ordering::Traits::ContainerIndex CI;
699  typedef typename Ordering::Traits::DOFIndex DI;
700  typedef std::size_t size_type;
701 
702  typedef std::vector<CI> CIVector;
703  typedef std::unordered_map<DI,CI> CIMap;
704 
705  struct ConstraintsEntry
706  : public std::pair<CI,typename C::mapped_type::mapped_type>
707  {
708  typedef CI ContainerIndex;
709  typedef typename C::mapped_type::mapped_type Weight;
710 
711  const ContainerIndex& containerIndex() const
712  {
713  return this->first;
714  }
715 
716  const Weight& weight() const
717  {
718  return this->second;
719  }
720  };
721 
722  typedef std::vector<ConstraintsEntry> ConstraintsVector;
723  typedef typename ConstraintsVector::const_iterator ConstraintsIterator;
724 
725  LFSIndexCacheBase(const LFS& lfs, const C& constraints)
726  : _lfs(lfs)
727  , _dof_flags(lfs.maxSize())
728  , _constraints_iterators(lfs.maxSize())
729  , _gfs_constraints(constraints)
730  {
731  }
732 
733  void update()
734  {
735  _constraints.resize(0);
736  std::vector<std::pair<size_type,typename C::const_iterator> > non_dirichlet_constrained_dofs;
737  size_type constraint_entry_count = 0;
738  for (size_type i = 0; i < _lfs.size(); ++i)
739  {
740  const DI& dof_index = _lfs.dofIndex(i);
741  const typename C::const_iterator cit = _gfs_constraints.find(dof_index);
742  if (cit == _gfs_constraints.end())
743  {
744  _dof_flags[i] = DOF_NONCONSTRAINED;
745  continue;
746  }
747 
748  if (cit->second.size() == 0)
749  {
750  _dof_flags[i] = DOF_CONSTRAINED | DOF_DIRICHLET;
751  _constraints_iterators[i] = make_pair(_constraints.end(),_constraints.end());
752  }
753  else
754  {
755  _dof_flags[i] = DOF_CONSTRAINED;
756  constraint_entry_count += cit->second.size();
757  non_dirichlet_constrained_dofs.push_back(make_pair(i,cit));
758  }
759  }
760 
761  if (constraint_entry_count > 0)
762  {
763  _constraints.resize(constraint_entry_count);
764  typename ConstraintsVector::iterator eit = _constraints.begin();
765  for (typename std::vector<std::pair<size_type,typename C::const_iterator> >::const_iterator it = non_dirichlet_constrained_dofs.begin();
766  it != non_dirichlet_constrained_dofs.end();
767  ++it)
768  {
769  _constraints_iterators[it->first].first = eit;
770  for (typename C::mapped_type::const_iterator cit = it->second->second.begin(); cit != it->second->second.end(); ++cit, ++eit)
771  {
772  eit->first = cit->first;
773  eit->second = cit->second;
774  }
775  _constraints_iterators[it->first].second = eit;
776  }
777  }
778  }
779 
780  const DI& dofIndex(size_type i) const
781  {
782  return _lfs.dofIndex(i);
783  }
784 
785  CI containerIndex(size_type i) const
786  {
787  return CI(_lfs.dofIndex(i)[0]);
788  }
789 
790  const CI& containerIndex(const DI& i) const
791  {
792  return CI(i[0]);
793  }
794 
795  bool isConstrained(size_type i) const
796  {
797  return _dof_flags[i] & DOF_CONSTRAINED;
798  }
799 
800  bool isDirichletConstraint(size_type i) const
801  {
802  return _dof_flags[i] & DOF_DIRICHLET;
803  }
804 
805  ConstraintsIterator constraintsBegin(size_type i) const
806  {
807  assert(isConstrained(i));
808  return _constraints_iterators[i].first;
809  }
810 
811  ConstraintsIterator constraintsEnd(size_type i) const
812  {
813  assert(isConstrained(i));
814  return _constraints_iterators[i].second;
815  }
816 
817  const LocalFunctionSpace& localFunctionSpace() const
818  {
819  return _lfs;
820  }
821 
822  size_type size() const
823  {
824  return _lfs.size();
825  }
826 
827  private:
828 
829  const LFS& _lfs;
830  CIVector _container_indices;
831  std::vector<unsigned char> _dof_flags;
832  std::vector<std::pair<ConstraintsIterator,ConstraintsIterator> > _constraints_iterators;
833  mutable CIMap _container_index_map;
834  ConstraintsVector _constraints;
835 
836  const C& _gfs_constraints;
837 
838  };
839 
840 
841  template<typename LFS>
843  {
844 
845  public:
846 
847  typedef LFS LocalFunctionSpace;
848  typedef typename LFS::Traits::GridFunctionSpace GFS;
849  typedef typename GFS::Ordering Ordering;
850  private:
851  typedef typename Ordering::Traits::ContainerIndex CI;
852  typedef typename Ordering::Traits::DOFIndex DI;
853  public:
854  typedef CI ContainerIndex;
855  typedef DI DOFIndex;
856  typedef std::size_t size_type;
857 
858  typedef std::vector<CI> CIVector;
859  typedef std::unordered_map<DI,CI> CIMap;
860 
861  struct ConstraintsEntry
862  : public std::pair<const CI*,double>
863  {
864  typedef CI ContainerIndex;
865  typedef double Weight;
866 
867  const ContainerIndex& containerIndex() const
868  {
869  return *(this->first);
870  }
871 
872  const Weight& weight() const
873  {
874  return this->second;
875  }
876  };
877 
878  typedef std::vector<ConstraintsEntry> ConstraintsVector;
879  typedef typename ConstraintsVector::const_iterator ConstraintsIterator;
880 
881  explicit LFSIndexCacheBase(const LFS& lfs)
882  : _lfs(lfs)
883  {
884  }
885 
886  template<typename C>
887  LFSIndexCacheBase(const LFS& lfs, const C& c)
888  : _lfs(lfs)
889  {
890  }
891 
892 
893  void update()
894  {
895  // there's nothing to do here...
896  }
897 
898  CI containerIndex(size_type i) const
899  {
900  return CI(_lfs.dofIndex(i)[0]);
901  }
902 
903  CI containerIndex(const DI& i) const
904  {
905  return CI(i[0]);
906  }
907 
908  bool isConstrained(size_type i) const
909  {
910  return false;
911  }
912 
913  bool isDirichletConstraint(size_type i) const
914  {
915  return false;
916  }
917 
918  ConstraintsIterator constraintsBegin(size_type i) const
919  {
920  return _constraints.begin();
921  }
922 
923  ConstraintsIterator constraintsEnd(size_type i) const
924  {
925  return _constraints.end();
926  }
927 
928  const LocalFunctionSpace& localFunctionSpace() const
929  {
930  return _lfs;
931  }
932 
933  size_type size() const
934  {
935  return _lfs.size();
936  }
937 
938  private:
939 
940  const LFS& _lfs;
941  mutable CIMap _container_index_map;
942  const ConstraintsVector _constraints;
943 
944  };
945 
946 
947  template<typename LFS, typename C = EmptyTransformation>
949  : public LFSIndexCacheBase<LFS,C,typename LFS::Traits::GridFunctionSpace::Ordering::CacheTag>
950  {
951 
952  public:
953 
954  template<typename CC>
955  LFSIndexCache(const LFS& lfs, const CC& c, bool enable_constraints_caching = !std::is_same<C,EmptyTransformation>::value)
956  : LFSIndexCacheBase<LFS,C,typename LFS::Traits::GridFunctionSpace::Ordering::CacheTag>(lfs,c,enable_constraints_caching)
957  {
958  }
959 
960  explicit LFSIndexCache(const LFS& lfs)
961  : LFSIndexCacheBase<LFS,C,typename LFS::Traits::GridFunctionSpace::Ordering::CacheTag>(lfs)
962  {
963  }
964 
965  };
966 
967 
968  } // namespace PDELab
969 } // namespace Dune
970 
971 #endif // DUNE_PDELAB_GRIDFUNCTIONSPACE_LFSINDEXCACHE_HH
void pre(const Ordering &ordering, TreePath tp)
Definition: lfsindexcache.hh:206
std::size_t size_type
Definition: lfsindexcache.hh:260
ContainerIndex CI
Definition: lfsindexcache.hh:257
DOFIndexViewIterator(Iterator it, std::size_t tail_length=0)
Definition: lfsindexcache.hh:80
const CI & containerIndex(size_type i) const
Definition: lfsindexcache.hh:378
std::unordered_map< DI, CI > CIMap
Definition: lfsindexcache.hh:703
View * operator->()
Definition: lfsindexcache.hh:64
ConstraintsIterator constraintsEnd(size_type i) const
Definition: lfsindexcache.hh:412
LFSIndexCacheBase(const LFS &lfs)
Definition: lfsindexcache.hh:881
ConstraintsVector::const_iterator ConstraintsIterator
Definition: lfsindexcache.hh:287
LFS LocalFunctionSpace
Definition: lfsindexcache.hh:694
std::vector< ConstraintsEntry > ConstraintsVector
Definition: lfsindexcache.hh:878
void cut_back()
Definition: lfsindexcache.hh:85
const Weight & weight() const
Definition: lfsindexcache.hh:716
LFSIndexCacheBase(const LFS &lfs)
Definition: lfsindexcache.hh:575
std::unordered_map< DI, CI > CIMap
Definition: lfsindexcache.hh:263
bool isDirichletConstraint(size_type i) const
Definition: lfsindexcache.hh:401
bool constraintsCachingEnabled() const
Definition: lfsindexcache.hh:665
LFSIndexCacheBase(const LFS &lfs, const C &c, bool enable_constraints_caching)
Definition: lfsindexcache.hh:582
CI containerIndex(size_type i) const
Definition: lfsindexcache.hh:898
const DI & dofIndex(size_type i) const
Definition: lfsindexcache.hh:373
void increment()
Definition: lfsindexcache.hh:105
Definition: lfsindexcache.hh:948
const ContainerIndex & containerIndex() const
Definition: lfsindexcache.hh:711
LFSIndexCache(const LFS &lfs, const CC &c, bool enable_constraints_caching=!std::is_same< C, EmptyTransformation >::value)
Definition: lfsindexcache.hh:955
std::vector< CI > CIVector
Definition: lfsindexcache.hh:552
extract_lfs_leaf_size_visitor(Iterator leaf_size_container_iterator)
Definition: lfsindexcache.hh:156
void leaf(const Ordering &ordering, TreePath tp)
Definition: lfsindexcache.hh:183
bool isDirichletConstraint(size_type i) const
Definition: lfsindexcache.hh:640
size_type size() const
Definition: lfsindexcache.hh:822
ConstraintsIterator constraintsBegin(size_type i) const
Definition: lfsindexcache.hh:918
size_type size() const
Definition: lfsindexcache.hh:660
LFS::Traits::GridFunctionSpace GFS
Definition: lfsindexcache.hh:544
const ContainerIndex & containerIndex() const
Definition: lfsindexcache.hh:561
ConstraintsIterator constraintsEnd(size_type i) const
Definition: lfsindexcache.hh:650
ConstraintsIterator constraintsBegin(size_type i) const
Definition: lfsindexcache.hh:645
std::vector< CI > CIVector
Definition: lfsindexcache.hh:702
LFSIndexCache(const LFS &lfs)
Definition: lfsindexcache.hh:960
CI ContainerIndex
Definition: lfsindexcache.hh:270
C::mapped_type::mapped_type Weight
Definition: lfsindexcache.hh:709
ConstraintsIterator constraintsEnd(size_type i) const
Definition: lfsindexcache.hh:811
Definition: lfsindexcache.hh:57
bool isConstrained(size_type i) const
Definition: lfsindexcache.hh:635
ConstraintsIterator constraintsBegin(size_type i) const
Definition: lfsindexcache.hh:406
const LocalFunctionSpace & localFunctionSpace() const
Definition: lfsindexcache.hh:817
Definition: gridfunctionspace/tags.hh:216
View _tmp
Definition: lfsindexcache.hh:69
const DI & dofIndex(size_type i) const
Definition: lfsindexcache.hh:780
std::size_t size_type
Definition: lfsindexcache.hh:700
const LocalFunctionSpace & localFunctionSpace() const
Definition: lfsindexcache.hh:655
pointer operator->() const
Definition: lfsindexcache.hh:130
void restore_back()
Definition: lfsindexcache.hh:90
ContainerIndex CI
Definition: lfsindexcache.hh:547
ConstraintsVector::const_iterator ConstraintsIterator
Definition: lfsindexcache.hh:573
For backward compatibility – Do not use this!
Definition: adaptivity.hh:27
bool constraintsCachingEnabled() const
Definition: lfsindexcache.hh:449
std::unordered_map< DI, CI > CIMap
Definition: lfsindexcache.hh:553
LFS::Traits::GridFunctionSpace GFS
Definition: lfsindexcache.hh:254
Ordering::Traits::DOFIndex DOFIndex
Definition: lfsindexcache.hh:258
std::pair< size_type, bool > localIndex(const ContainerIndex &ci) const
Definition: lfsindexcache.hh:428
ConstraintsVector::const_iterator ConstraintsIterator
Definition: lfsindexcache.hh:723
std::stack< DOFIndexViewIterator< DOFIterator >, ReservedVector< DOFIndexViewIterator< DOFIterator >, tree_depth > > dof_stack
Definition: lfsindexcache.hh:232
void decrement()
Definition: lfsindexcache.hh:110
std::ptrdiff_t distanceTo(DOFIndexViewIterator &other) const
Definition: lfsindexcache.hh:120
DOFIndexViewIterator()
Definition: lfsindexcache.hh:75
const Weight & weight() const
Definition: lfsindexcache.hh:278
std::unordered_map< const CI *, std::pair< size_type, bool > > InverseMap
Definition: lfsindexcache.hh:265
const ContainerIndex & containerIndex() const
Definition: lfsindexcache.hh:867
const LocalFunctionSpace & localFunctionSpace() const
Definition: lfsindexcache.hh:928
std::vector< ConstraintsEntry > ConstraintsVector
Definition: lfsindexcache.hh:572
LFSIndexCacheBase(const LFS &lfs, const C &c)
Definition: lfsindexcache.hh:887
const CI & containerIndex(const DI &i) const
Definition: lfsindexcache.hh:790
GFS::Ordering Ordering
Definition: lfsindexcache.hh:545
ConstraintsIterator constraintsEnd(size_type i) const
Definition: lfsindexcache.hh:923
static const unsigned int value
Definition: gridfunctionspace/tags.hh:139
ConstraintsIterator constraintsBegin(size_type i) const
Definition: lfsindexcache.hh:805
CI containerIndex(size_type i) const
Definition: lfsindexcache.hh:785
bool isConstrained(size_type i) const
Definition: lfsindexcache.hh:396
LFS LocalFunctionSpace
Definition: lfsindexcache.hh:252
LFS::Traits::GridFunctionSpace GFS
Definition: lfsindexcache.hh:848
Definition: lfsindexcache.hh:25
A grid function space.
Definition: gridfunctionspace.hh:169
Iterator extract_lfs_leaf_sizes(const LFS &lfs, Iterator it)
Definition: lfsindexcache.hh:165
size_type offset(size_type i) const
Definition: lfsindexcache.hh:435
std::vector< ConstraintsEntry > ConstraintsVector
Definition: lfsindexcache.hh:286
const View dereference() const
Definition: lfsindexcache.hh:125
Ordering::Traits::DOFIndex DOFIndex
Definition: lfsindexcache.hh:548
bool isConstrained(size_type i) const
Definition: lfsindexcache.hh:795
const CI & containerIndex(const DI &i) const
Definition: lfsindexcache.hh:383
const std::iterator_traits< Iterator >::reference raw_index() const
Definition: lfsindexcache.hh:95
bool isDirichletConstraint(size_type i) const
Definition: lfsindexcache.hh:800
void post(const Ordering &ordering, TreePath tp)
Definition: lfsindexcache.hh:193
DOFIndex DI
Definition: lfsindexcache.hh:259
Definition: lfsindexcache.hh:144
Ordering::Traits::ContainerIndex ContainerIndex
Definition: lfsindexcache.hh:256
proxy pointer
Definition: lfsindexcache.hh:73
void advance(int n)
Definition: lfsindexcache.hh:115
ContainerIterator container_pos
Definition: lfsindexcache.hh:230
bool isDirichletConstraint(size_type i) const
Definition: lfsindexcache.hh:913
Ordering::Traits::ContainerIndex ContainerIndex
Definition: lfsindexcache.hh:546
GFS::Ordering Ordering
Definition: lfsindexcache.hh:255
void constraints(const GFS &gfs, CG &cg, const bool verbose=false)
construct constraints
Definition: constraints.hh:751
void leaf(const LeafLFS &leaf_lfs, TreePath tp)
Definition: lfsindexcache.hh:150
Ordering::Traits::ContainerIndex CI
Definition: lfsindexcache.hh:698
std::stack< ContainerIterator, ReservedVector< ContainerIterator, tree_depth > > container_stack
Definition: lfsindexcache.hh:233
Iterator it
Definition: lfsindexcache.hh:160
LeafSizeIterator leaf_size_pos
Definition: lfsindexcache.hh:231
GFS::Ordering Ordering
Definition: lfsindexcache.hh:697
const CI & containerIndex(size_type i) const
Definition: lfsindexcache.hh:617
Ordering::Traits::DOFIndex DI
Definition: lfsindexcache.hh:699
size_type size() const
Definition: lfsindexcache.hh:423
C::mapped_type::mapped_type Weight
Definition: lfsindexcache.hh:271
proxy(const View &v)
Definition: lfsindexcache.hh:60
DOFIndexViewIterator< DOFIterator > dof_end
Definition: lfsindexcache.hh:229
std::vector< ConstraintsEntry > ConstraintsVector
Definition: lfsindexcache.hh:722
ConstraintsVector::const_iterator ConstraintsIterator
Definition: lfsindexcache.hh:879
Definition: lfsindexcache.hh:240
CI containerIndex(const DI &i) const
Definition: lfsindexcache.hh:903
const ContainerIndex & containerIndex() const
Definition: lfsindexcache.hh:273
map_dof_indices_to_container_indices(DOFIterator dof_begin, ContainerIterator container_begin, LeafSizeIterator leaf_size_begin, std::size_t dof_index_tail_length=0)
Definition: lfsindexcache.hh:217
const DI & dofIndex(size_type i) const
Definition: lfsindexcache.hh:612
LFSIndexCacheBase(const LFS &lfs, const C &constraints, bool enable_constraints_caching)
Definition: lfsindexcache.hh:289
const LocalFunctionSpace & localFunctionSpace() const
Definition: lfsindexcache.hh:418
Definition: constraintstransformation.hh:111
void update()
Definition: lfsindexcache.hh:300
DOFIndexViewIterator< DOFIterator > dof_pos
Definition: lfsindexcache.hh:228
bool isConstrained(size_type i) const
Definition: lfsindexcache.hh:908
LFS::Traits::GridFunctionSpace GFS
Definition: lfsindexcache.hh:696
bool equals(const DOFIndexViewIterator &other) const
Definition: lfsindexcache.hh:100
LFSIndexCacheBase(const LFS &lfs, const C &constraints)
Definition: lfsindexcache.hh:725
const CI & containerIndex(const DI &i) const
Definition: lfsindexcache.hh:622
std::unordered_map< DI, CI > CIMap
Definition: lfsindexcache.hh:859
size_type extendedOffset(size_type i) const
Definition: lfsindexcache.hh:442
std::vector< CI > CIVector
Definition: lfsindexcache.hh:262