dune-pdelab  2.5-dev
bcrspattern.hh
Go to the documentation of this file.
1 // -*- tab-width: 4; indent-tabs-mode: nil -*-
2 #ifndef DUNE_PDELAB_BACKEND_ISTL_BCRSPATTERN_HH
3 #define DUNE_PDELAB_BACKEND_ISTL_BCRSPATTERN_HH
4 
5 // this is here for backwards compatibility and deprecation warnings, remove after 2.5.0
6 #include "ensureistlinclude.hh"
7 
8 #include <utility>
9 #include <vector>
10 #include <algorithm>
11 #include <set>
12 
13 #include <dune/common/iteratorfacades.hh>
14 
19 
20 namespace Dune {
21  namespace PDELab {
22  namespace ISTL {
23 
25 
45  template<typename RowOrdering, typename ColOrdering>
47  {
48 
49  public:
50 
52  typedef typename RowOrdering::Traits::size_type size_type;
53 
55  typedef void SubPattern;
56 
57  private:
58 
60  static const size_type empty = ~static_cast<size_type>(0);
61 
63 
72  struct PaddedColumnCriterion
73  {
74 
75  bool operator()(size_type k) const
76  {
77  return k == _j || k == empty;
78  }
79 
80  PaddedColumnCriterion(size_type j)
81  : _j(j)
82  {}
83 
84  const size_type _j;
85 
86  };
87 
88 
89  typedef typename std::vector<size_type>::iterator IndicesIterator;
90  typedef typename std::set<std::pair<size_type,size_type> >::iterator OverflowIterator;
91 
92  typedef typename std::vector<size_type>::const_iterator ConstIndicesIterator;
93  typedef typename std::set<std::pair<size_type,size_type> >::const_iterator ConstOverflowIterator;
94 
95  public:
96 
98  template<typename RI, typename CI>
99  void add_link(const RI& ri, const CI& ci)
100  {
101  // extract block indices for current level
102  size_type i = ri.back();
103  size_type j = ci.back();
104 
105  IndicesIterator start = _indices.begin();
106  IndicesIterator begin = start + _entries_per_row*i;
107  IndicesIterator end = start + _entries_per_row*(i+1);
108 
109  // Does the entry (i,j) already exist?
110  IndicesIterator it = std::find_if(begin,end,PaddedColumnCriterion(j));
111  if (it != end)
112  {
113  // Yes, just write out j. This does the right thing regardless of whether
114  // it points at the correct column value or at an empty entry.
115  *it = j;
116  }
117  else
118  {
119  // The row is already full -> spill into map
120  _overflow.insert(std::make_pair(i,j));
121  }
122  }
123 
124 #ifndef DOXYGEN
125 
126  // implementation detail for nested patterns
127  template<typename RI, typename CI>
128  void recursive_add_entry(const RI& ri, const CI& ci)
129  {
130  add_link(ri,ci);
131  }
132 
133 #endif //DOXYGEN
134 
136  template<typename I>
137  void sizes(I rit) const
138  {
139  ConstIndicesIterator it = _indices.begin();
140  ConstIndicesIterator end = _indices.begin() + _entries_per_row;
141  ConstOverflowIterator oit = _overflow.begin();
142  ConstOverflowIterator oend = _overflow.end();
143  for (size_type i = 0; i < _row_ordering.blockCount(); ++i, ++rit, end+=_entries_per_row)
144  {
145  size_type s = 0;
146  // count non-empty column entries, break when first empty one is found.
147  for (; it != end; ++it)
148  {
149  if (*it == empty)
150  break;
151  ++s;
152  }
153  it = end;
154  // add overflow entries
155  for (; oit != oend && oit->first == i; ++oit)
156  ++s;
157  *rit = s;
158  }
159  }
160 
162  std::vector<size_type> sizes() const
163  {
164  std::vector<size_type> r(_row_ordering.blockCount());
165  sizes(r.begin());
166  return std::move(r);
167  }
168 
170  struct iterator
171  : public ForwardIteratorFacade<iterator, const size_type>
172  {
173 
174 #ifndef DOXYGEN
175 
176  const size_type& dereference() const
177  {
178  if (_in_overflow)
179  return _oit->second;
180  else
181  return *_it;
182  }
183 
184  void increment()
185  {
186  if (_in_overflow)
187  {
188  if (_oit != _oend)
189  ++_oit;
190  if (_oit->first == _row)
191  return;
192  // we have exhausted the row, invalidate iterator
193  _at_end = true;
194  }
195  else
196  {
197  if (_it != _end)
198  ++_it;
199  if (_it == _end || *_it == empty)
200  {
201  _in_overflow = true;
202  // we have exhausted the row, invalidate iterator
203  if (_oit == _oend || _oit->first > _row)
204  _at_end = true;
205  }
206  }
207  }
208 
209  bool equals(const iterator& other) const
210  {
211  if (_row != other._row)
212  return false;
213  if (_at_end || other._at_end)
214  return _at_end && other._at_end;
215  if (_in_overflow)
216  return _oit == other._oit;
217  else
218  return _it == other._it;
219  }
220 
221  iterator(const BCRSPattern& p, size_type row, bool at_end)
222  : _row(row)
223  , _in_overflow(false)
224  , _at_end(at_end)
225  , _it(p._indices.begin() + row * p._entries_per_row)
226  , _end(p._indices.begin() + (row+1) * p._entries_per_row)
227  , _oit(p._overflow.lower_bound(std::make_pair(row,0)))
228  , _oend(p._overflow.end())
229  {
230  // catch corner case with completely empty row
231  if ((!_at_end) && (_it == _end || *_it == empty))
232  {
233  _in_overflow = true;
234  _at_end = _oit == _oend || _oit->first != _row;
235  }
236  }
237 
238  size_type _row;
239  bool _in_overflow;
240  bool _at_end;
241  typename std::vector<size_type>::const_iterator _it;
242  typename std::vector<size_type>::const_iterator _end;
243  typename std::set<std::pair<size_type,size_type> >::const_iterator _oit;
244  const typename std::set<std::pair<size_type,size_type> >::const_iterator _oend;
245 
246 #endif // DOXYGEN
247 
248  };
249 
251  iterator begin(size_type i) const
252  {
253  return iterator(*this,i,false);
254  }
255 
257  iterator end(size_type i) const
258  {
259  return iterator(*this,i,true);
260  }
261 
263 
268  BCRSPattern(const RowOrdering& row_ordering, const ColOrdering& col_ordering, size_type entries_per_row)
269  : _row_ordering(row_ordering)
270  , _col_ordering(col_ordering)
271  , _entries_per_row(entries_per_row)
272  , _indices(row_ordering.blockCount()*entries_per_row,size_type(empty))
273  {}
274 
275  const RowOrdering& rowOrdering() const
276  {
277  return _row_ordering;
278  }
279 
280  const ColOrdering& colOrdering() const
281  {
282  return _row_ordering;
283  }
284 
286 
292  void clear()
293  {
294  _indices = std::vector<size_type>();
295  _overflow = std::set<std::pair<size_type,size_type> >();
296  }
297 
298  size_type entriesPerRow() const
299  {
300  return _entries_per_row;
301  }
302 
303  size_type overflowCount() const
304  {
305  return _overflow.size();
306  }
307 
308  private:
309 
310  const RowOrdering& _row_ordering;
311  const ColOrdering& _col_ordering;
312  const size_type _entries_per_row;
313 
314  std::vector<size_type> _indices;
315  std::set<std::pair<size_type,size_type> > _overflow;
316 
317  };
318 
319 
321 
326  template<typename RowOrdering, typename ColOrdering, typename SubPattern_>
328  {
329 
330  public:
331 
333  typedef SubPattern_ SubPattern;
334 
336  typedef typename SubPattern::size_type size_type;
337 
339 
343  template<typename RI, typename CI>
344  void add_link(const RI& ri, const CI& ci)
345  {
346  recursive_add_entry(ri.view(),ci.view());
347  }
348 
349 #ifndef DOXYGEN
350 
351  template<typename RI, typename CI>
352  void recursive_add_entry(const RI& ri, const CI& ci)
353  {
354  _sub_patterns[ri.back() * _col_ordering.blockCount() + ci.back()].recursive_add_entry(ri.back_popped(),ci.back_popped());
355  }
356 
357 #endif // DOXYGEN
358 
359  template<typename EntriesPerRow>
360  NestedPattern(const RowOrdering& row_ordering, const ColOrdering& col_ordering, const EntriesPerRow& entries_per_row)
361  : _row_ordering(row_ordering)
362  , _col_ordering(col_ordering)
363  {
364  size_type rows = row_ordering.blockCount();
365  size_type cols = col_ordering.blockCount();
366  for (size_type i = 0; i < rows; ++i)
367  for (size_type j = 0; j < cols; ++j)
368  _sub_patterns.push_back(
369  SubPattern(
370  _row_ordering.childOrdering(i),
371  _col_ordering.childOrdering(j),
372  entries_per_row[i][j]
373  )
374  );
375  }
376 
377  NestedPattern(const RowOrdering& row_ordering, const ColOrdering& col_ordering, size_type entries_per_row)
378  : _row_ordering(row_ordering)
379  , _col_ordering(col_ordering)
380  {
381  size_type rows = row_ordering.blockCount();
382  size_type cols = col_ordering.blockCount();
383  for (size_type i = 0; i < rows; ++i)
384  for (size_type j = 0; j < cols; ++j)
385  _sub_patterns.push_back(
386  SubPattern(
387  _row_ordering.childOrdering(i),
388  _col_ordering.childOrdering(j),
389  entries_per_row
390  )
391  );
392  }
393 
395  SubPattern& subPattern(size_type i, size_type j)
396  {
397  return _sub_patterns[i * _col_ordering.blockCount() + j];
398  }
399 
400  private:
401 
402  const RowOrdering& _row_ordering;
403  const ColOrdering& _col_ordering;
404  std::vector<SubPattern> _sub_patterns;
405 
406  };
407 
408 
409  } // namespace ISTL
410  } // namespace PDELab
411 } // namespace Dune
412 
413 #endif // DUNE_PDELAB_BACKEND_ISTL_BCRSPATTERN_HH
void clear()
Discard all internal data.
Definition: bcrspattern.hh:292
std::vector< size_type > sizes() const
Returns a vector with the size of all rows in the pattern.
Definition: bcrspattern.hh:162
const std::string s
Definition: function.hh:830
void SubPattern
BCRSPattern cannot contain nested subpatterns. This entry is only required for TMP purposes...
Definition: bcrspattern.hh:55
NestedPattern(const RowOrdering &row_ordering, const ColOrdering &col_ordering, const EntriesPerRow &entries_per_row)
Definition: bcrspattern.hh:360
const RowOrdering & rowOrdering() const
Definition: bcrspattern.hh:275
iterator end(size_type i) const
Returns an iterator past the last column index of row i.
Definition: bcrspattern.hh:257
void add_link(const RI &ri, const CI &ci)
Add a link between the row indicated by ri and the column indicated by ci.
Definition: bcrspattern.hh:344
For backward compatibility – Do not use this!
Definition: adaptivity.hh:27
iterator begin(size_type i) const
Returns an iterator to the first column index of row i.
Definition: bcrspattern.hh:251
Various tags for influencing backend behavior.
SubPattern_ SubPattern
The pattern type used for each block.
Definition: bcrspattern.hh:333
void sizes(I rit) const
Stream the sizes of all rows into the output iterator rit.
Definition: bcrspattern.hh:137
const P & p
Definition: constraints.hh:147
RowOrdering::Traits::size_type size_type
size type used by BCRSPattern.
Definition: bcrspattern.hh:52
void add_link(const RI &ri, const CI &ci)
Add a link between the row indicated by ri and the column indicated by ci.
Definition: bcrspattern.hh:99
NestedPattern(const RowOrdering &row_ordering, const ColOrdering &col_ordering, size_type entries_per_row)
Definition: bcrspattern.hh:377
size_type overflowCount() const
Definition: bcrspattern.hh:303
BCRSPattern(const RowOrdering &row_ordering, const ColOrdering &col_ordering, size_type entries_per_row)
Constructs a BCRSPattern for the given pair of orderings and reserves space for the provided average ...
Definition: bcrspattern.hh:268
Pattern builder for nested hierarchies of generic BCRS-like sparse matrices.
Definition: bcrspattern.hh:327
Pattern builder for generic BCRS-like sparse matrices.
Definition: bcrspattern.hh:46
SubPattern::size_type size_type
size type used by NestedPattern.
Definition: bcrspattern.hh:336
const ColOrdering & colOrdering() const
Definition: bcrspattern.hh:280
size_type entriesPerRow() const
Definition: bcrspattern.hh:298
Iterator over all column indices for a given row, unique but in arbitrary order.
Definition: bcrspattern.hh:170
SubPattern & subPattern(size_type i, size_type j)
Returns the subpattern associated with block (i,j).
Definition: bcrspattern.hh:395