Debian Codegraph @

dune/istl/vbvector.hh

raw
1 // SPDX-FileCopyrightText: Copyright © DUNE Project contributors, see file LICENSE.md in module root
2 // SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception
3 // -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
4 // vi: set et ts=4 sw=2 sts=2:
5 #ifndef DUNE_ISTL_VBVECTOR_HH
6 #define DUNE_ISTL_VBVECTOR_HH
7
8 #include <cmath>
9 #include <complex>
10 #include <iostream>
11 #include <iterator>
12 #include <memory>
13
14 #include <dune/common/ftraits.hh>
15 #include <dune/common/indexediterator.hh>
16 #include <dune/common/iteratorfacades.hh>
17 #include "istlexception.hh"
18 #include "bvector.hh"
19
20 #include <dune/istl/blocklevel.hh>
21
22 /** \file
23 * \brief ???
24 */
25
26 namespace Dune {
27
28 /**
29 @addtogroup ISTL_SPMV
30 @{
31 */
32
33 /**
34 \brief A Vector of blocks with different blocksizes.
35
36 implements a vector consisting of a number of blocks (to
37 be given at run-time) which themselves consist of a number
38 of blocks (also given at run-time) of the given type B.
39
40 VariableBlockVector is a container of containers!
41
42 */
43 template<class B, class A=std::allocator<B> >
44 class VariableBlockVector : public Imp::block_vector_unmanaged<B,typename A::size_type>
45 // this derivation gives us all the blas level 1 and norms
46 // on the large array. However, access operators have to be
47 // overwritten.
48 {
49 using Base = Imp::block_vector_unmanaged<B,typename A::size_type>;
50
51 // just a shorthand
52 using window_type = Imp::BlockVectorWindow<B,A>;
53
54 // data-structure holding the windows (but not the actual data)
55 using VectorWindows = std::vector<window_type, typename std::allocator_traits<A>::template rebind_alloc<window_type>>;
56
57 // block type bool is not supported since std::vector<bool> is used for storage
58 static_assert(not std::is_same_v<B,bool>, "Block type 'bool' not supported by VariableBlockVector.");
59
60 public:
61
62 //===== type definitions and constants
63
64 //! export the type representing the field
65 using field_type = typename Imp::BlockTraits<B>::field_type;
66
67 //! export the allocator type
68 using allocator_type = A;
69
70 /** \brief Export type used for references to container entries
71 *
72 * \note This is not B&, but an internal proxy class!
73 */
74 using reference = window_type&;
75
76 /** \brief Export type used for const references to container entries
77 *
78 * \note This is not B&, but an internal proxy class!
79 */
80 using const_reference = const window_type&;
81
82 //! The size type for the index access
83 using size_type = typename A::size_type;
84
85 /** \brief Type of the elements of the outer vector, i.e., dynamic vectors of B
86 *
87 * Note that this is *not* the type referred to by the iterators and random access operators,
88 * which return proxy objects.
89 */
90 using value_type = BlockVector<B,A>;
91
92 /** \brief Same as value_type, here for historical reasons
93 */
94 using block_type = BlockVector<B,A>;
95
96 //===== constructors and such
97
98 /**
99 * \brief Constructor without arguments makes an empty vector.
100 * \note object cannot be used yet. The size and block sizes need to be initialized.
101 */
102 VariableBlockVector () :
103 Base()
104 {}
105
106 /**
107 * \brief Construct a vector with given number of blocks, but size of each
108 * block is not yet known.
109 * \note Object cannot be used yet. Needs to be initialized using the
110 * `createbegin()` and `createend()` create-iterators to fill the block sizes.
111 */
112 explicit VariableBlockVector (size_type numBlocks) :
113 Base(),
114 block(numBlocks)
115 {}
116
117 /**
118 * \brief Construct a vector with given number of blocks each having a
119 * constant size.
120 * \note Object is fully usable after construction.
121 *
122 * \param numBlocks Number of blocks
123 * \param blockSize Number of elements in each block
124 */
125 VariableBlockVector (size_type numBlocks, size_type blockSize) :
126 Base(),
127 block(numBlocks),
128 storage_(numBlocks*blockSize)
129 {
130 // and we can allocate the big array in the base class
131 syncBaseArray();
132
133 // set the windows into the big array
134 for (size_type i=0; i<numBlocks; ++i)
135 block[i].set(blockSize,this->p+(i*blockSize));
136
137 // and the vector is usable
138 initialized = true;
139 }
140
141 //! Copy constructor, has copy semantics
142 VariableBlockVector (const VariableBlockVector& a) :
143 Base(static_cast<const Base&>(a)),
144 block(a.block),
145 storage_(a.storage_)
146 {
147 syncBaseArray();
148
149 // and we must set the windows
150 if (block.size()>0) {
151 block[0].set(block[0].getsize(),this->p); // first block
152 for (size_type i=1; i<block.size(); ++i) // and the rest
153 block[i].set(block[i].getsize(),block[i-1].getptr()+block[i-1].getsize());
154 }
155
156 // and we have a usable vector
157 initialized = a.initialized;
158 }
159
160 //! Move constructor:
161 VariableBlockVector (VariableBlockVector&& tmp) :
162 Base()
163 {
164 tmp.swap(*this);
165 }
166
167 ~VariableBlockVector () = default;
168
169
170 //! Copy and move assignment
171 VariableBlockVector& operator= (VariableBlockVector tmp)
172 {
173 tmp.swap(*this);
174 return *this;
175 }
176
177 //! Exchange the storage and internal state with `other`.
178 void swap (VariableBlockVector& other) noexcept
179 {
180 using std::swap;
181 swap(storage_, other.storage_);
182 swap(block, other.block);
183 swap(initialized, other.initialized);
184
185 other.syncBaseArray();
186 syncBaseArray();
187 }
188
189 //! Free function to swap the storage and internal state of `lhs` with `rhs`.
190 friend void swap (VariableBlockVector& lhs, VariableBlockVector& rhs) noexcept
191 {
192 lhs.swap(rhs);
193 }
194
195 //! same effect as constructor with same argument
196 void resize (size_type numBlocks)
197 {
198 storage_.clear();
199
200 syncBaseArray();
201
202 // we can allocate the windows now
203 block.resize(numBlocks);
204
205 // and the vector not fully usable
206 initialized = false;
207 }
208
209 //! same effect as constructor with same argument
210 void resize (size_type numBlocks, size_type blockSize)
211 {
212 // and we can allocate the big array in the base class
213 storage_.resize(numBlocks*blockSize);
214 block.resize(numBlocks);
215 syncBaseArray();
216
217 // set the windows into the big array
218 for (size_type i=0; i<block.size(); ++i)
219 block[i].set(blockSize,this->p+(i*blockSize));
220
221 // and the vector is usable
222 initialized = true;
223 }
224
225 //===== assignment from scalar
226
227 //! Set all entries to the given scalar `k`.
228 VariableBlockVector& operator= (const field_type& k)
229 {
230 (static_cast<Imp::block_vector_unmanaged<B,size_type>&>(*this)) = k;
231 return *this;
232 }
233
234
235 //===== the creation interface
236
237 class CreateIterator;
238
239 #ifndef DOXYGEN
240
241 // The window_type does not hand out a reference to its size,
242 // so in order to provide a valid iterator, we need a workaround
243 // to make assignment possible. This proxy enables just that by
244 // implicitly converting to the stored size for read access and
245 // tunneling assignment to the accessor method of the window.
246 struct SizeProxy
247 {
248
249 operator size_type () const
250 {
251 return target->getsize();
252 }
253
254 SizeProxy& operator= (size_type size)
255 {
256 target->setsize(size);
257 return *this;
258 }
259
260 private:
261
262 friend class CreateIterator;
263
264 SizeProxy (window_type& t) :
265 target(&t)
266 {}
267
268 window_type* target;
269 };
270
271 #endif // DOXYGEN
272
273 //! Iterator class for sequential creation of blocks
274 class CreateIterator
275 {
276 public:
277 //! iterator category
278 using iterator_category = std::output_iterator_tag;
279
280 //! value type
281 using value_type = size_type;
282
283 /**
284 * \brief difference type (unused)
285 *
286 * This type is required by the C++ standard, but not used for
287 * output iterators.
288 */
289 using difference_type = void;
290
291 //! pointer type
292 using pointer = size_type*;
293
294 //! reference type
295 using reference = SizeProxy;
296
297 //! constructor
298 CreateIterator (VariableBlockVector& _v, int _i, bool _isEnd) :
299 v(&_v),
300 i(_i),
301 isEnd(_isEnd)
302 {}
303
304 ~CreateIterator ()
305 {
306 // When the iterator gets destructed, we allocate the memory
307 // for the VariableBlockVector if
308 // 1. the current iterator was not created as enditerator
309 // 2. we're at the last block
310 // 3. the vector hasn't been initialized earlier
311 if (not isEnd && i==v->block.size() && not v->initialized)
312 v->allocate();
313 }
314
315 //! prefix increment
316 CreateIterator& operator++()
317 {
318 // go to next block
319 ++i;
320
321 return *this;
322 }
323
324 /** \brief postfix increment operator */
325 CreateIterator operator++ (int)
326 {
327 CreateIterator tmp(*this);
328 this->operator++();
329 return tmp;
330 }
331
332 //! inequality
333 bool operator!= (const CreateIterator& it) const
334 {
335 return not (*this == it);
336 }
337
338 //! equality
339 bool operator== (const CreateIterator& it) const
340 {
341 return (i==it.i) && (v==it.v);
342 }
343
344 //! dereferencing
345 size_type index () const
346 {
347 return i;
348 }
349
350 //! set size of current block
351 void setblocksize (size_type _k)
352 {
353 v->block[i].setsize(_k);
354 }
355
356 //! Access size of current block
357 #ifdef DOXYGEN
358 size_type&
359 #else
360 SizeProxy
361 #endif
362 operator*()
363 {
364 return {v->block[i]};
365 }
366
367 private:
368 VariableBlockVector* v; // my vector
369 size_type i; // current block to be defined
370 bool isEnd; // flag if this object was created as the end iterator.
371 };
372
373 // CreateIterator wants to set all the arrays ...
374 friend class CreateIterator;
375
376 //! get initial create iterator
377 CreateIterator createbegin ()
378 {
379 #ifdef DUNE_ISTL_WITH_CHECKING
380 if (initialized) DUNE_THROW(ISTLError,"no CreateIterator in initialized state");
381 #endif
382 return CreateIterator(*this, 0, false);
383 }
384
385 //! get create iterator pointing to one after the last block
386 CreateIterator createend ()
387 {
388 return CreateIterator(*this, block.size(), true);
389 }
390
391
392 //===== access to components
393 // has to be overwritten from base class because it must
394 // return access to the windows
395
396 //! random access to blocks
397 window_type& operator[] (size_type i)
398 {
399 #ifdef DUNE_ISTL_WITH_CHECKING
400 if (i>=block.size()) DUNE_THROW(ISTLError,"index out of range");
401 #endif
402 return block[i];
403 }
404
405 //! same for read only access
406 const window_type& operator[] (size_type i) const
407 {
408 #ifdef DUNE_ISTL_WITH_CHECKING
409 if (i<0 || i>=block.size()) DUNE_THROW(ISTLError,"index out of range");
410 #endif
411 return block[i];
412 }
413
414 using Iterator = IndexedIterator<typename VectorWindows::iterator>;
415
416 //! begin Iterator
417 Iterator begin ()
418 {
419 return Iterator{block.begin()};
420 }
421
422 //! end Iterator
423 Iterator end ()
424 {
425 return Iterator{block.end()};
426 }
427
428 //! @returns an iterator that is positioned before
429 //! the end iterator of the vector, i.e. at the last entry.
430 Iterator beforeEnd ()
431 {
432 return Iterator{--block.end()};
433 }
434
435 //! @returns an iterator that is positioned before
436 //! the first entry of the vector.
437 Iterator beforeBegin ()
438 {
439 return Iterator{--block.begin()};
440 }
441
442 /** \brief Export the iterator type using std naming rules */
443 using iterator = Iterator;
444
445 /** \brief Const iterator */
446 using ConstIterator = IndexedIterator<typename VectorWindows::const_iterator>;
447
448 /** \brief Export the const iterator type using std naming rules */
449 using const_iterator = ConstIterator;
450
451 //! begin ConstIterator
452 ConstIterator begin () const
453 {
454 return ConstIterator{block.begin()};
455 }
456
457 //! end ConstIterator
458 ConstIterator end () const
459 {
460 return ConstIterator{block.end()};
461 }
462
463 //! @returns an iterator that is positioned before
464 //! the end iterator of the vector. i.e. at the last element.
465 ConstIterator beforeEnd () const
466 {
467 return ConstIterator{--block.end()};
468 }
469
470 //! @returns an iterator that is positioned before
471 //! the first entry of the vector.
472 ConstIterator beforeBegin () const
473 {
474 return ConstIterator{--block.begin()};
475 }
476
477 //! end ConstIterator
478 ConstIterator rend () const
479 {
480 return ConstIterator{block.rend()};
481 }
482
483 //! random access returning iterator (end if not contained)
484 Iterator find (size_type i)
485 {
486 Iterator tmp = block.begin();
487 tmp+=std::min(i, block.size());
488 return tmp;
489 }
490
491 //! random access returning iterator (end if not contained)
492 ConstIterator find (size_type i) const
493 {
494 ConstIterator tmp = block.begin();
495 tmp+=std::min(i, block.size());
496 return tmp;
497 }
498
499 //===== sizes
500
501 //! number of blocks in the vector (are of variable size here)
502 size_type N () const noexcept
503 {
504 return block.size();
505 }
506
507 /** Number of blocks in the vector
508 *
509 * Returns the same value as method N(), because the vector is dense
510 */
511 size_type size () const noexcept
512 {
513 return block.size();
514 }
515
516
517 private:
518
519 void allocate ()
520 {
521 if (this->initialized)
522 DUNE_THROW(ISTLError, "Attempt to re-allocate already initialized VariableBlockVector");
523
524 // calculate space needed:
525 size_type storageNeeded = 0;
526 for(size_type i = 0; i < block.size(); i++)
527 storageNeeded += block[i].size();
528
529 storage_.resize(storageNeeded);
530 syncBaseArray();
531
532 // and we set the window pointers
533 block[0].setptr(this->p); // pointer to first block
534 for (size_type j=1; j<block.size(); ++j) // and the rest
535 block[j].setptr(block[j-1].getptr()+block[j-1].getsize());
536
537 // and the vector is ready
538 this->initialized = true;
539 }
540
541 void syncBaseArray () noexcept
542 {
543 this->p = storage_.data();
544 this->n = storage_.size();
545 }
546
547 VectorWindows block = {}; // vector of blocks pointing to the array in the base class
548 std::vector<B, A> storage_ = {};
549 bool initialized = false; // true if vector has been initialized
550 };
551
552 /** @addtogroup DenseMatVec
553 @{
554 */
555 template<class B, class A>
556 struct FieldTraits< VariableBlockVector<B, A> >
557 {
558 typedef typename FieldTraits<B>::field_type field_type;
559 typedef typename FieldTraits<B>::real_type real_type;
560 };
561 /**
562 @}
563 */
564
565
566 /** @} end documentation */
567
568 } // end namespace
569
570 #endif