Debian Codegraph @

include/deal.II/lac/block_indices.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2000 - 2025 by the deal.II authors
5 //
6 // This file is part of the deal.II library.
7 //
8 // Part of the source code is dual licensed under Apache-2.0 WITH
9 // LLVM-exception OR LGPL-2.1-or-later. Detailed license information
10 // governing the source code and code contributions can be found in
11 // LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II.
12 //
13 // ------------------------------------------------------------------------
14
15 #ifndef dealii_block_indices_h
16 #define dealii_block_indices_h
17
18
19 #include <deal.II/base/config.h>
20
21 #include <deal.II/base/enable_observer_pointer.h>
22 #include <deal.II/base/exceptions.h>
23 #include <deal.II/base/logstream.h>
24 #include <deal.II/base/types.h>
25
26 #include <algorithm>
27 #include <cstddef>
28 #include <string>
29 #include <vector>
30
31 DEAL_II_NAMESPACE_OPEN
32
33
34 /**
35 * BlockIndices represents a range of indices (such as the range $[0,N)$
36 * of valid indices for elements of a vector) and how this one range
37 * is broken down into smaller but contiguous "blocks" (such as the velocity
38 * and pressure parts of a solution vector). In particular, it provides the
39 * ability to translate between global indices and the indices <i>within</i>
40 * a block. This class is used, for example, in the BlockVector,
41 * BlockSparsityPattern, and BlockMatrixBase classes.
42 *
43 * The information that can be obtained from this class falls into two groups.
44 * First, it is possible to query the global size of the index space (through
45 * the total_size() member function), and the number of blocks and their sizes
46 * (via size() and the block_size() functions).
47 *
48 * Secondly, this class manages the conversion of global indices to the
49 * local indices within this block, and the other way around. This is required,
50 * for example, when you address a global element in a block vector and want to
51 * know within which block this is, and which index within this block it
52 * corresponds to. It is also useful if a matrix is composed of several
53 * blocks, where you have to translate global row and column indices to local
54 * ones.
55 *
56 * @ingroup data
57 * @see
58 * @ref GlossBlockLA "Block (linear algebra)"
59 */
60 class BlockIndices : public EnableObserverPointer
61 {
62 public:
63 /**
64 * Declare the type for container size.
65 */
66 using size_type = types::global_dof_index;
67
68 /**
69 * Default constructor. Initialize for zero blocks.
70 */
71 BlockIndices();
72
73 /**
74 * Constructor. Initialize the number of entries in each block @p i as
75 * <tt>block_sizes[i]</tt>. The number of blocks will be the size of @p
76 * block_sizes.
77 */
78 BlockIndices(const std::vector<size_type> &block_sizes);
79
80 /**
81 * Move constructor. Initialize a new object by stealing the internal data of
82 * another BlockIndices object.
83 */
84 BlockIndices(BlockIndices &&b) noexcept;
85
86 /**
87 * Copy constructor.
88 */
89 BlockIndices(const BlockIndices &) = default;
90
91 /**
92 * Specialized constructor for a structure with blocks of equal size.
93 */
94 explicit BlockIndices(const unsigned int n_blocks,
95 const size_type block_size = 0);
96
97 /**
98 * Reinitialize the number of blocks and assign each block the same number
99 * of elements.
100 */
101 void
102 reinit(const unsigned int n_blocks, const size_type n_elements_per_block);
103
104 /**
105 * Reinitialize the number of indices within each block from the given
106 * argument. The number of blocks will be adjusted to the size of
107 * <tt>block_sizes</tt> and the size of block @p i is set to
108 * <tt>block_sizes[i]</tt>.
109 */
110 void
111 reinit(const std::vector<size_type> &block_sizes);
112
113 /**
114 * Add another block of given size to the end of the block structure.
115 */
116 void
117 push_back(const size_type size);
118
119 /**
120 * @name Size information
121 */
122 /** @{ */
123
124 /**
125 * Number of blocks in index field.
126 */
127 unsigned int
128 size() const;
129
130 /**
131 * Return the total number of indices accumulated over all blocks, that is,
132 * the dimension of the vector space of the block vector.
133 */
134 size_type
135 total_size() const;
136
137 /**
138 * The size of the @p ith block.
139 */
140 size_type
141 block_size(const unsigned int i) const;
142
143 /**
144 * String representation of the block sizes. The output is of the form
145 * `[nb->b1,b2,b3|s]`, where `nb` is n_blocks(), `s` is total_size() and
146 * `b1` etc. are the values returned by block_size() for each of the blocks.
147 */
148 std::string
149 to_string() const;
150
151 /** @} */
152
153 /**
154 * @name Index conversion
155 *
156 * Functions in this group assume an object, which was created after sorting
157 * by block, such that each block forms a set of consecutive indices in the
158 * object. If applied to other objects, the numbers obtained from these
159 * functions are meaningless.
160 */
161 /** @{ */
162
163 /**
164 * Return the block and the index within that block for the global index @p
165 * i. The first element of the pair is the block, the second the index
166 * within it.
167 */
168 std::pair<unsigned int, size_type>
169 global_to_local(const size_type i) const;
170
171 /**
172 * Return the global index of @p index in block @p block.
173 */
174 size_type
175 local_to_global(const unsigned int block, const size_type index) const;
176
177 /**
178 * The start index of the ith block.
179 */
180 size_type
181 block_start(const unsigned int i) const;
182 /** @} */
183
184 /**
185 * Copy operator.
186 */
187 BlockIndices &
188 operator=(const BlockIndices &b);
189
190 /**
191 * Move assignment operator. Move another BlockIndices object onto the
192 * current one by transferring its contents.
193 */
194 BlockIndices &
195 operator=(BlockIndices &&) noexcept;
196
197 /**
198 * Compare whether two objects are the same, i.e. whether the number of
199 * blocks and the sizes of all blocks are equal.
200 */
201 bool
202 operator==(const BlockIndices &b) const;
203
204 /**
205 * Swap the contents of these two objects.
206 */
207 void
208 swap(BlockIndices &b) noexcept;
209
210 /**
211 * Determine an estimate for the memory consumption (in bytes) of this
212 * object.
213 */
214 std::size_t
215 memory_consumption() const;
216
217 private:
218 /**
219 * Number of blocks. While this value could be obtained through
220 * <tt>start_indices.size()-1</tt>, we cache this value for faster access.
221 */
222 unsigned int n_blocks;
223
224 /**
225 * Global starting index of each vector. The last and redundant value is the
226 * total number of entries.
227 */
228 std::vector<size_type> start_indices;
229 };
230
231
232 /**
233 * Operator for logging BlockIndices. Writes the number of blocks, the size of
234 * each block and the total size of the index field.
235 *
236 * @ref BlockIndices
237 */
238 inline LogStream &
239 operator<<(LogStream &s, const BlockIndices &bi)
240 {
241 const unsigned int n = bi.size();
242 s << n << ":[";
243 // Write first size without leading space
244 if (n > 0)
245 s << bi.block_size(0);
246 // Write all other sizes
247 for (unsigned int i = 1; i < n; ++i)
248 s << ' ' << bi.block_size(i);
249 s << "]->" << bi.total_size();
250 return s;
251 }
252
253
254
255 /* ---------------------- template and inline functions ------------------- */
256
257 inline void
258 BlockIndices::reinit(const unsigned int nb, const size_type block_size)
259 {
260 n_blocks = nb;
261 start_indices.resize(n_blocks + 1);
262 for (size_type i = 0; i <= n_blocks; ++i)
263 start_indices[i] = i * block_size;
264 }
265
266
267
268 inline void
269 BlockIndices::reinit(const std::vector<size_type> &block_sizes)
270 {
271 if (start_indices.size() != block_sizes.size() + 1)
272 {
273 n_blocks = static_cast<unsigned int>(block_sizes.size());
274 start_indices.resize(n_blocks + 1);
275 }
276 start_indices[0] = 0;
277 for (size_type i = 1; i <= n_blocks; ++i)
278 start_indices[i] = start_indices[i - 1] + block_sizes[i - 1];
279 }
280
281
282 inline BlockIndices::BlockIndices()
283 : n_blocks(0)
284 , start_indices(1, 0)
285 {}
286
287
288
289 inline BlockIndices::BlockIndices(const unsigned int n_blocks,
290 const size_type block_size)
291 : n_blocks(n_blocks)
292 , start_indices(n_blocks + 1)
293 {
294 for (size_type i = 0; i <= n_blocks; ++i)
295 start_indices[i] = i * block_size;
296 }
297
298
299
300 inline BlockIndices::BlockIndices(const std::vector<size_type> &block_sizes)
301 : n_blocks(static_cast<unsigned int>(block_sizes.size()))
302 , start_indices(block_sizes.size() + 1)
303 {
304 reinit(block_sizes);
305 }
306
307
308
309 inline BlockIndices::BlockIndices(BlockIndices &&b) noexcept
310 : n_blocks(b.n_blocks)
311 , start_indices(std::move(b.start_indices))
312 {
313 b.n_blocks = 0;
314 b.start_indices = std::vector<size_type>(1, 0);
315 }
316
317
318
319 inline void
320 BlockIndices::push_back(const size_type sz)
321 {
322 start_indices.push_back(start_indices[n_blocks] + sz);
323 ++n_blocks;
324 AssertDimension(start_indices.size(), n_blocks + 1);
325 }
326
327
328 inline std::pair<unsigned int, BlockIndices::size_type>
329 BlockIndices::global_to_local(const size_type i) const
330 {
331 AssertIndexRange(i, total_size());
332 Assert(n_blocks > 0, ExcLowerRangeType<size_type>(i, size_type(1)));
333
334 // start_indices[0] == 0 so we might as well start from the next one
335 const auto it = std::prev(
336 std::upper_bound(std::next(start_indices.begin()), start_indices.end(), i));
337
338 return {std::distance(start_indices.begin(), it), i - *it};
339 }
340
341
342 inline BlockIndices::size_type
343 BlockIndices::local_to_global(const unsigned int block,
344 const size_type index) const
345 {
346 AssertIndexRange(block, n_blocks);
347 AssertIndexRange(index, start_indices[block + 1] - start_indices[block]);
348
349 return start_indices[block] + index;
350 }
351
352
353 inline unsigned int
354 BlockIndices::size() const
355 {
356 return n_blocks;
357 }
358
359
360
361 inline BlockIndices::size_type
362 BlockIndices::total_size() const
363 {
364 if (n_blocks == 0)
365 return 0;
366 return start_indices[n_blocks];
367 }
368
369
370
371 inline BlockIndices::size_type
372 BlockIndices::block_size(const unsigned int block) const
373 {
374 AssertIndexRange(block, n_blocks);
375 return start_indices[block + 1] - start_indices[block];
376 }
377
378
379
380 inline std::string
381 BlockIndices::to_string() const
382 {
383 std::string result = "[" + std::to_string(n_blocks) + "->";
384 for (unsigned int i = 0; i < n_blocks; ++i)
385 {
386 if (i > 0)
387 result += ',';
388 result += std::to_string(block_size(i));
389 }
390 result += "|" + std::to_string(total_size()) + ']';
391 return result;
392 }
393
394
395
396 inline BlockIndices::size_type
397 BlockIndices::block_start(const unsigned int block) const
398 {
399 AssertIndexRange(block, n_blocks);
400 return start_indices[block];
401 }
402
403
404
405 inline BlockIndices &
406 BlockIndices::operator=(const BlockIndices &b)
407 {
408 start_indices = b.start_indices;
409 n_blocks = b.n_blocks;
410 return *this;
411 }
412
413
414
415 inline BlockIndices &
416 BlockIndices::operator=(BlockIndices &&b) noexcept
417 {
418 start_indices = std::move(b.start_indices);
419 n_blocks = b.n_blocks;
420
421 b.start_indices = std::vector<size_type>(1, 0);
422 b.n_blocks = 0;
423
424 return *this;
425 }
426
427
428
429 inline bool
430 BlockIndices::operator==(const BlockIndices &b) const
431 {
432 if (n_blocks != b.n_blocks)
433 return false;
434
435 for (size_type i = 0; i <= n_blocks; ++i)
436 if (start_indices[i] != b.start_indices[i])
437 return false;
438
439 return true;
440 }
441
442
443
444 inline void
445 BlockIndices::swap(BlockIndices &b) noexcept
446 {
447 std::swap(n_blocks, b.n_blocks);
448 std::swap(start_indices, b.start_indices);
449 }
450
451
452
453 inline std::size_t
454 BlockIndices::memory_consumption() const
455 {
456 return (sizeof(*this) + start_indices.size() * sizeof(start_indices[0]));
457 }
458
459
460
461 /* ----------------- global functions ---------------------------- */
462
463
464 /**
465 * Global function @p swap which overloads the default implementation of the
466 * C++ standard library which uses a temporary object. The function simply
467 * exchanges the data of the two objects.
468 *
469 * @relatesalso BlockIndices
470 */
471 inline void
472 swap(BlockIndices &u, BlockIndices &v) noexcept
473 {
474 u.swap(v);
475 }
476
477
478
479 DEAL_II_NAMESPACE_CLOSE
480
481 #endif