Debian Codegraph @

include/deal.II/base/index_set.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2009 - 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_index_set_h
16 #define dealii_index_set_h
17
18 #include <deal.II/base/config.h>
19
20 #include <deal.II/base/exceptions.h>
21 #include <deal.II/base/memory_space.h>
22 #include <deal.II/base/mpi_stub.h>
23 #include <deal.II/base/mutex.h>
24 #include <deal.II/base/trilinos_utilities.h>
25 #include <deal.II/base/types.h>
26
27 #include <deal.II/lac/trilinos_tpetra_types.h>
28
29 #include <boost/container/small_vector.hpp>
30
31 #include <algorithm>
32 #include <vector>
33
34
35 #ifdef DEAL_II_WITH_TRILINOS
36
37 DEAL_II_DISABLE_EXTRA_DIAGNOSTICS
38 # include <Epetra_Map.h>
39 # ifdef DEAL_II_TRILINOS_WITH_TPETRA
40 # include <Tpetra_Map.hpp>
41 # endif
42 DEAL_II_ENABLE_EXTRA_DIAGNOSTICS
43
44 #endif
45
46 #ifdef DEAL_II_WITH_PETSC
47 # include <petscis.h>
48 #endif
49
50 DEAL_II_NAMESPACE_OPEN
51
52 /**
53 * A class that represents a subset of indices among a larger set. For
54 * example, it can be used to denote the set of degrees of freedom within the
55 * range $[0,\mathrm{dof\_handler.n\_dofs()})$ that belongs to a particular
56 * subdomain, or those among all degrees of freedom that are stored on a
57 * particular processor in a distributed parallel computation.
58 *
59 * This class can represent a collection of half-open ranges of indices as
60 * well as individual elements. For practical purposes it also stores the
61 * overall range these indices can assume. In other words, you need to specify
62 * the size of the index space $[0,\text{size})$ of which objects of this
63 * class are a subset.
64 *
65 * There are two ways to iterate over the IndexSets: First, begin() and end()
66 * allow iteration over individual indices in the set. Second,
67 * begin_interval() and end_interval() allow iteration over the half-open
68 * ranges as described above.
69 *
70 * The data structures used in this class along with a rationale can be found
71 * in the
72 * @ref distributed_paper "Distributed Computing paper".
73 */
74 class IndexSet
75 {
76 public:
77 // forward declarations:
78 class ElementIterator;
79 class IntervalIterator;
80
81 /**
82 * @p size_type is the type used for storing the size and the individual
83 * entries in the IndexSet.
84 */
85 using size_type = types::global_dof_index;
86
87 /**
88 * One can see an IndexSet as a container of size size(), where the elements
89 * of the containers are bool values that are either false or true,
90 * depending on whether a particular index is an element of the IndexSet or
91 * not. In other words, an IndexSet is a bit like a vector in which the
92 * elements we store are booleans. In this view, the correct local alias
93 * indicating the type of the elements of the vector would then be @p bool.
94 *
95 * On the other hand, @p bool has the disadvantage that it is not a
96 * numerical type that, for example, allows multiplication with a @p double.
97 * In other words, one can not easily use a vector of booleans in a place
98 * where other vectors are allowed. Consequently, we declare the type of the
99 * elements of such a vector as a signed integer. This uses the fact that in
100 * the C++ language, booleans are implicitly convertible to integers. In
101 * other words, declaring the type of the elements of the vector as a signed
102 * integer is only a small lie, but it is a useful one.
103 */
104 using value_type = signed int;
105
106
107 /**
108 * Default constructor.
109 */
110 IndexSet();
111
112 /**
113 * Constructor that also sets the overall size of the index range.
114 */
115 explicit IndexSet(const size_type size);
116
117 /**
118 * Copy constructor.
119 */
120 IndexSet(const IndexSet &) = default;
121
122 /**
123 * Copy assignment operator.
124 */
125 IndexSet &
126 operator=(const IndexSet &) = default;
127
128 /**
129 * Move constructor. Create a new IndexSet by transferring the internal data
130 * of the input set.
131 */
132 IndexSet(IndexSet &&is) noexcept;
133
134 /**
135 * Move assignment operator. Transfer the internal data of the input set into
136 * the current one.
137 */
138 IndexSet &
139 operator=(IndexSet &&is) noexcept;
140
141 #ifdef DEAL_II_WITH_TRILINOS
142
143 # ifdef DEAL_II_TRILINOS_WITH_TPETRA
144 /**
145 * Constructor from a Trilinos Teuchos::RCP<Tpetra::Map>.
146 */
147 template <typename NodeType>
148 explicit IndexSet(
149 const Teuchos::RCP<
150 const Tpetra::Map<int, types::signed_global_dof_index, NodeType>> &map);
151 # endif // DEAL_II_TRILINOS_WITH_TPETRA
152
153 /**
154 * Constructor from a Trilinos Epetra_BlockMap.
155 */
156 explicit IndexSet(const Epetra_BlockMap &map);
157 #endif // DEAL_II_WITH_TRILINOS
158
159 /**
160 * Remove all indices from this index set. The index set retains its size,
161 * however.
162 */
163 void
164 clear();
165
166 /**
167 * Set the maximal size of the indices upon which this object operates.
168 *
169 * This function can only be called if the index set does not yet contain
170 * any elements. This can be achieved by calling clear(), for example.
171 */
172 void
173 set_size(const size_type size);
174
175 /**
176 * Return the size of the index space of which this index set is a subset
177 * of.
178 *
179 * Note that the result is not equal to the number of indices within this
180 * set. The latter information is returned by n_elements().
181 */
182 size_type
183 size() const;
184
185 /**
186 * Add the half-open range $[\text{begin},\text{end})$ to the set of indices
187 * represented by this class.
188 * @param[in] begin The first element of the range to be added.
189 * @param[in] end The past-the-end element of the range to be added.
190 */
191 void
192 add_range(const size_type begin, const size_type end);
193
194 /**
195 * Add an individual index to the set of indices.
196 *
197 * If you have many indices to add to the set, consider calling the
198 * add_indices() function below. It is considerably more efficient,
199 * particularly if the indices to be added are stored in an array
200 * that is already sorted.
201 */
202 void
203 add_index(const size_type index);
204
205 /**
206 * Add a whole set of indices described by dereferencing every element of
207 * the iterator range <code>[begin,end)</code>.
208 *
209 * @param[in] begin Iterator to the first element of range of indices to be
210 * added.
211 * @param[in] end The past-the-end iterator for the range of elements to be
212 * added.
213 *
214 * @pre The condition <code>begin@<=end</code> needs to be satisfied. They
215 * also obviously have to point into the same container.
216 *
217 * @note The operations of this function are substantially more efficient
218 * if the indices pointed to by the range of iterators are already sorted.
219 * As a consequence, it is often highly beneficial to sort the range of
220 * indices pointed to by the iterator range given by the arguments
221 * before calling this function. Note also that the function deals
222 * efficiently with sorted indices that contain duplicates (e.g., if
223 * the iterator range points to the list `(1,1,1,2,2,4,6,8,8,8)`).
224 * In other words, it is very useful to call `std::sort()` on the
225 * range of indices you are about to add, but it is not necessary
226 * to call the usual combination of `std::unique` and `std::erase`
227 * to reduce the list of indices to only a set of unique elements.
228 */
229 template <typename ForwardIterator>
230 void
231 add_indices(const ForwardIterator &begin, const ForwardIterator &end);
232
233 /**
234 * Add the given IndexSet @p other to the current one, constructing the
235 * union of *this and @p other.
236 *
237 * If the @p offset argument is nonzero, then every index in @p other is
238 * shifted by @p offset before being added to the current index set. This
239 * allows to construct, for example, one index set from several others that
240 * are supposed to represent index sets corresponding to different ranges
241 * (e.g., when constructing the set of nonzero entries of a block vector
242 * from the sets of nonzero elements of the individual blocks of a vector).
243 *
244 * This function will generate an exception if any of the (possibly shifted)
245 * indices of the @p other index set lie outside the range
246 * <code>[0,size())</code> represented by the current object.
247 */
248 void
249 add_indices(const IndexSet &other, const size_type offset = 0);
250
251 /**
252 * Return whether the specified index is an element of the index set.
253 */
254 bool
255 is_element(const size_type index) const;
256
257 /**
258 * Return whether the index set stored by this object defines a contiguous
259 * range. This is true also if no indices are stored at all.
260 */
261 bool
262 is_contiguous() const;
263
264 /**
265 * Return whether the index set stored by this object contains no elements.
266 * This is similar, but faster than checking <code>n_elements() == 0</code>.
267 *
268 * Note that a set being empty does not imply that the size of the
269 * index space must be zero. Rather, this function returns `true` if
270 * the subset of indices in the index space is the empty set,
271 * regardless of the size of the index space.
272 */
273 bool
274 is_empty() const;
275
276 /**
277 * Return whether the IndexSets are ascending with respect to MPI process
278 * number and 1:1, i.e., each index is contained in exactly one IndexSet
279 * (among those stored on the different processes), each process stores
280 * contiguous subset of indices, and the index set on process $p+1$ starts
281 * at the index one larger than the last one stored on process $p$.
282 * In case there is only one MPI process, this just means that the IndexSet
283 * is complete.
284 */
285 bool
286 is_ascending_and_one_to_one(const MPI_Comm communicator) const;
287
288 /**
289 * Return the number of elements stored in this index set.
290 */
291 size_type
292 n_elements() const;
293
294 /**
295 * Return the global index of the local index with number @p local_index
296 * stored in this index set. @p local_index obviously needs to be less than
297 * n_elements().
298 */
299 size_type
300 nth_index_in_set(const size_type local_index) const;
301
302 /**
303 * Return the how-manyth element of this set (counted in ascending order) @p
304 * global_index is. @p global_index needs to be less than the size(). This
305 * function returns numbers::invalid_dof_index if the index @p global_index is not actually
306 * a member of this index set, i.e. if `is_element(global_index)` is false.
307 */
308 size_type
309 index_within_set(const size_type global_index) const;
310
311 /**
312 * Each index set can be represented as the union of a number of contiguous
313 * intervals of indices, where if necessary intervals may only consist of
314 * individual elements to represent isolated members of the index set.
315 *
316 * This function returns the minimal number of such intervals that are
317 * needed to represent the index set under consideration.
318 */
319 unsigned int
320 n_intervals() const;
321
322 /**
323 * This function returns the local index of the beginning of the largest
324 * range.
325 *
326 * In other words, the return value is nth_index_in_set(x), where x is the
327 * first index of the largest contiguous range of indices in the
328 * IndexSet. The return value is therefore equal to the number of elements
329 * in the set that come before the largest range.
330 *
331 * This call assumes that the IndexSet is nonempty.
332 */
333 size_type
334 largest_range_starting_index() const;
335
336 /**
337 * Compress the internal representation by merging individual elements with
338 * contiguous ranges, etc. This function does not have any external effect.
339 */
340 void
341 compress() const;
342
343 /**
344 * Comparison for equality of index sets.
345 *
346 * This operation is only allowed if the size of the two sets is the
347 * same (though of course they do not have to have the same number
348 * of indices), or if one of the two objects being compared is empty.
349 * The comparison between two objects of different sizes would of course,
350 * intuitively, result in a `false` outcome, but it is often a sign of
351 * a programming mistake to compare index sets of different sizes
352 * against each other, and the comparison is consequently not allowed.
353 * On the other hand, the comparison against an empty object makes
354 * sense to ensure, for example, that an IndexSet object has been
355 * initialized.
356 */
357 bool
358 operator==(const IndexSet &is) const;
359
360 /**
361 * Comparison for inequality of index sets.
362 *
363 * This operation is only allowed if the size of the two sets is the
364 * same (though of course they do not have to have the same number
365 * of indices), or if one of the two objects being compared is empty.
366 * The comparison between two objects of different sizes would of course,
367 * intuitively, result in a `false` outcome, but it is often a sign of
368 * a programming mistake to compare index sets of different sizes
369 * against each other, and the comparison is consequently not allowed.
370 * On the other hand, the comparison against an empty object makes
371 * sense to ensure, for example, that an IndexSet object has been
372 * initialized.
373 */
374 bool
375 operator!=(const IndexSet &is) const;
376
377 /**
378 * Return the intersection of the current index set and the argument given,
379 * i.e. a set of indices that are elements of both index sets. The two index
380 * sets must have the same size (though of course they do not have to have
381 * the same number of indices).
382 */
383 IndexSet
384 operator&(const IndexSet &is) const;
385
386 /**
387 * This command takes an interval <tt>[begin, end)</tt> and returns the
388 * intersection of the current index set with the interval, shifted to the
389 * range <tt>[0, end-begin)</tt>.
390 *
391 * In other words, the result of this operation is the intersection of the
392 * set represented by the current object and the interval <tt>[begin,
393 * end)</tt>, as seen <i>within the interval <tt>[begin, end)</tt></i> by
394 * shifting the result of the intersection operation to the left by
395 * <tt>begin</tt>. This corresponds to the notion of a <i>view</i>: The
396 * interval <tt>[begin, end)</tt> is a <i>window</i> through which we see
397 * the set represented by the current object.
398 *
399 * A more general function of the same name, taking a mask instead
400 * of just an interval to define the view, is below.
401 */
402 IndexSet
403 get_view(const size_type begin, const size_type end) const;
404
405 /**
406 * This command takes a "mask", i.e., a second index set of same size as the
407 * current one and returns the intersection of the current index set the mask,
408 * shifted to the index of an entry within the given mask. For example,
409 * if the current object is a an IndexSet object representing an index space
410 * `[0,100)` containing indices `[20,40)`, and if the mask represents
411 * an index space of the same size but containing all 50 *odd* indices in this
412 * range, then the result will be an index set for a space of size 50 that
413 * contains those indices that correspond to the question "the how many'th
414 * entry in the mask are the indices `[20,40)`. This will result in an index
415 * set of size 50 that contains the indices `{11,12,13,14,15,16,17,18,19,20}`
416 * (because, for example, the index 20 in the original set is not in the mask,
417 * but 21 is and corresponds to the 11th entry of the mask -- the mask
418 * contains the elements `{1,3,5,7,9,11,13,15,17,19,21,...}`).
419 *
420 * In other words, the result of this operation is the intersection of the
421 * set represented by the current object and the mask, as seen
422 * <i>within the mask</i>. This corresponds to the notion of a <i>view</i>:
423 * The mask is a <i>window</i> through which we see the set represented by the
424 * current object.
425 *
426 * A typical case where this function is useful is as follows. Say,
427 * you have a block linear system in which you have blocks
428 * corresponding to variables $(u,p,T,c)$ (which you can think of as
429 * velocity, pressure, temperature, and chemical composition -- or
430 * whatever other kind of problem you are currently considering in
431 * your own work). We solve this in parallel, so every MPI process
432 * has its own `locally_owned_dofs` index set that describes which
433 * among all $N_\text{dofs}$ degrees of freedom this process
434 * owns. Let's assume we have developed a linear solver or
435 * preconditioner that first solves the coupled $u$-$T$ system, and
436 * once that is done, solves the $p$-$c$ system. In this case, it is
437 * often useful to set up block vectors with only two components
438 * corresponding to the $u$ and $T$ components, and later for only
439 * the $p$-$c$ components of the solution. The question is which of
440 * the components of these 2-block vectors are locally owned? The
441 * answer is that we need to get a view of the `locally_owned_dofs`
442 * index set in which we apply a mask that corresponds to the
443 * variables we're currently interested in. For the $u$-$T$ system,
444 * we need a mask (corresponding to an index set of size
445 * $N_\text{dofs}$) that contains all indices of $u$ degrees of
446 * freedom as well as all indices of $T$ degrees of freedom. The
447 * resulting view is an index set of size $N_u+N_T$ that contains
448 * the indices of the locally owned $u$ and $T$ degrees of freedom.
449 */
450 IndexSet
451 get_view(const IndexSet &mask) const;
452
453 /**
454 * Split the set indices represented by this object into blocks given by the
455 * @p n_indices_per_block structure. The sum of its entries must match the
456 * global size of the current object.
457 */
458 std::vector<IndexSet>
459 split_by_block(
460 const std::vector<types::global_dof_index> &n_indices_per_block) const;
461
462 /**
463 * Remove all elements contained in @p other from this set. In other words,
464 * if $x$ is the current object and $o$ the argument, then we compute $x
465 * \leftarrow x \backslash o$.
466 */
467 void
468 subtract_set(const IndexSet &other);
469
470 /**
471 * Return a new IndexSet, with global size equal to
472 * `this->size()*other.size()`, containing for every element `n` of this
473 * IndexSet, the entries in the half open range `[n*other.size(),
474 * (n+1)*other.size())` of the @p other IndexSet.
475 *
476 * The name results from the perspective that one starts with an IndexSet and
477 * takes the tensor product with another IndexSet with `other.size()`
478 * elements; this results in a matrix of size `this->size()` times
479 * `other.size()` that has ones in exactly the rows for which this IndexSet
480 * contained an index and in the columns for which the @p other IndexSet
481 * contained an index. This matrix is then "unrolled" again by going through
482 * each row one by one and reindexing the entries of the matrix in consecutive
483 * order. A one in the matrix then corresponds to an entry in the reindexed
484 * IndexSet that is returned by this function.
485 */
486 IndexSet
487 tensor_product(const IndexSet &other) const;
488
489 /**
490 * Remove and return the last element of the last range.
491 * This function throws an exception if the IndexSet is empty.
492 *
493 * @deprecated This function is deprecated. Conceptually, an index set is a
494 * set; it should not be seen as a sorted container in which it is clear
495 * what element is stored "last".
496 */
497 DEAL_II_DEPRECATED_EARLY
498 size_type
499 pop_back();
500
501 /**
502 * Remove and return the first element of the first range.
503 * This function throws an exception if the IndexSet is empty.
504 *
505 * @deprecated This function is deprecated. Conceptually, an index set is a
506 * set; it should not be seen as a sorted container in which it is clear
507 * what element is stored "first".
508 */
509 DEAL_II_DEPRECATED_EARLY
510 size_type
511 pop_front();
512
513 /**
514 * Return a vector with all indices contained in this IndexSet. This
515 * vector may of course be quite large if the IndexSet stores many
516 * indices. (This may be true even if the IndexSet itself does not
517 * take up much memory: IndexSet stores indices in a compressed
518 * format in which contiguous ranges of indices are only stored using
519 * pairs of indices.)
520 */
521 std::vector<size_type>
522 get_index_vector() const;
523
524 /**
525 * Fill the given vector with all indices contained in this IndexSet.
526 *
527 * This function is equivalent to calling get_index_vector() and
528 * assigning the result to the @p indices argument.
529 */
530 DEAL_II_DEPRECATED
531 void
532 fill_index_vector(std::vector<size_type> &indices) const;
533
534 /**
535 * Fill the given vector with either zero or one elements, providing a
536 * binary representation of this index set. The given vector is assumed to
537 * already have the correct size.
538 *
539 * The given argument is filled with integer values zero and one, using
540 * <code>vector.operator[]</code>. Thus, any object that has such an
541 * operator can be used as long as it allows conversion of integers zero and
542 * one to elements of the vector. Specifically, this is the case for classes
543 * Vector, BlockVector, but also std::vector@<bool@>, std::vector@<int@>,
544 * and std::vector@<double@>.
545 */
546 template <typename VectorType>
547 void
548 fill_binary_vector(VectorType &vector) const;
549
550 /**
551 * Determine whether the current object represents a set of indices
552 * that is a subset of the set represented by the argument. This
553 * function returns `true` if the two sets are the same, that is, it
554 * considers the "subset" comparison typically used in set theory,
555 * rather than the "strict subset" comparison.
556 */
557 bool
558 is_subset_of(const IndexSet &other) const;
559
560 /**
561 * Output a text representation of this IndexSet to the given stream. Used
562 * for testing.
563 */
564 template <typename StreamType>
565 void
566 print(StreamType &out) const;
567
568 /**
569 * Write the IndexSet into a text based file format, that can be read in
570 * again using the read() function.
571 */
572 void
573 write(std::ostream &out) const;
574
575 /**
576 * Construct the IndexSet from a text based representation given by the
577 * stream @p in written by the write() function.
578 */
579 void
580 read(std::istream &in);
581
582 /**
583 * Write the IndexSet into a binary, compact representation, that can be
584 * read in again using the block_read() function.
585 */
586 void
587 block_write(std::ostream &out) const;
588
589 /**
590 * Construct the IndexSet from a binary representation given by the stream
591 * @p in written by the write_block() function.
592 */
593 void
594 block_read(std::istream &in);
595
596 #ifdef DEAL_II_WITH_TRILINOS
597 /**
598 * Given an MPI communicator, create a Trilinos map object that represents a
599 * distribution of vector elements or matrix rows in which we will locally
600 * store those elements or rows for which we store the index in the current
601 * index set, and all the other elements/rows elsewhere on one of the other
602 * MPI processes.
603 *
604 * The last argument only plays a role if the communicator is a parallel
605 * one, distributing computations across multiple processors. In that case,
606 * if the last argument is false, then it is assumed that the index sets
607 * this function is called with on all processors are mutually exclusive but
608 * together enumerate each index exactly once. In other words, if you call
609 * this function on two processors, then the index sets this function is
610 * called with must together have all possible indices from zero to
611 * size()-1, and no index must appear in both index sets. This corresponds,
612 * for example, to the case where we want to split the elements of vectors
613 * into unique subsets to be stored on different processors -- no element
614 * should be owned by more than one processor, but each element must be
615 * owned by one.
616 *
617 * On the other hand, if the second argument is true, then the index sets
618 * can be overlapping, and they also do not need to span the whole index
619 * set. This is a useful operation if we want to create vectors that not
620 * only contain the locally owned indices, but for example also the elements
621 * that correspond to degrees of freedom located on ghost cells. Another
622 * application of this method is to select a subset of the elements of a
623 * vector, e.g. for extracting only certain solution components.
624 */
625 Epetra_Map
626 make_trilinos_map(const MPI_Comm communicator = MPI_COMM_WORLD,
627 const bool overlapping = false) const;
628
629 # ifdef DEAL_II_TRILINOS_WITH_TPETRA
630 template <
631 typename NodeType =
632 LinearAlgebra::TpetraWrappers::TpetraTypes::NodeType<MemorySpace::Host>>
633 Tpetra::Map<int, types::signed_global_dof_index, NodeType>
634 make_tpetra_map(const MPI_Comm communicator = MPI_COMM_WORLD,
635 const bool overlapping = false) const;
636
637 template <
638 typename NodeType =
639 LinearAlgebra::TpetraWrappers::TpetraTypes::NodeType<MemorySpace::Host>>
640 Teuchos::RCP<Tpetra::Map<int, types::signed_global_dof_index, NodeType>>
641 make_tpetra_map_rcp(const MPI_Comm communicator = MPI_COMM_WORLD,
642 const bool overlapping = false) const;
643 # endif
644 #endif
645
646 #ifdef DEAL_II_WITH_PETSC
647 IS
648 make_petsc_is(const MPI_Comm communicator = MPI_COMM_WORLD) const;
649 #endif
650
651
652 /**
653 * Determine an estimate for the memory consumption (in bytes) of this
654 * object.
655 */
656 std::size_t
657 memory_consumption() const;
658
659 DeclException1(ExcIndexNotPresent,
660 size_type,
661 << "The global index " << arg1
662 << " is not an element of this set.");
663
664 /**
665 * Write or read the data of this object to or from a stream for the purpose
666 * of serialization using the [BOOST serialization
667 * library](https://www.boost.org/doc/libs/1_74_0/libs/serialization/doc/index.html).
668 */
669 template <class Archive>
670 void
671 serialize(Archive &ar, const unsigned int version);
672
673
674 /**
675 * @name Iterators
676 * @{
677 */
678
679 /**
680 * Dereferencing an IntervalIterator will return a reference to an object of
681 * this type. It allows access to a contiguous interval $[a,b[$ (also called
682 * a range) of the IndexSet being iterated over.
683 */
684 class IntervalAccessor
685 {
686 public:
687 /**
688 * Construct a valid accessor given an IndexSet and the index @p range_idx
689 * of the range to point to.
690 */
691 IntervalAccessor(const IndexSet *idxset, const size_type range_idx);
692
693 /**
694 * Construct an invalid accessor for the IndexSet.
695 */
696 explicit IntervalAccessor(const IndexSet *idxset);
697
698 /**
699 * Number of elements in this interval.
700 */
701 size_type
702 n_elements() const;
703
704 /**
705 * If true, we are pointing at a valid interval in the IndexSet.
706 */
707 bool
708 is_valid() const;
709
710 /**
711 * Return an iterator pointing at the first index in this interval.
712 */
713 ElementIterator
714 begin() const;
715
716 /**
717 * Return an iterator pointing directly after the last index in this
718 * interval.
719 */
720 ElementIterator
721 end() const;
722
723 /**
724 * Return the index of the last index in this interval.
725 */
726 size_type
727 last() const;
728
729 private:
730 /**
731 * Private copy constructor.
732 */
733 IntervalAccessor(const IntervalAccessor &other);
734 /**
735 * Private copy operator.
736 */
737 IntervalAccessor &
738 operator=(const IntervalAccessor &other);
739
740 /**
741 * Test for equality, used by IntervalIterator.
742 */
743 bool
744 operator==(const IntervalAccessor &other) const;
745 /**
746 * Smaller-than operator, used by IntervalIterator.
747 */
748 bool
749 operator<(const IntervalAccessor &other) const;
750 /**
751 * Advance this accessor to point to the next interval in the @p
752 * index_set.
753 */
754 void
755 advance();
756 /**
757 * Reference to the IndexSet.
758 */
759 const IndexSet *index_set;
760
761 /**
762 * Index into index_set.ranges[]. Set to numbers::invalid_dof_index if
763 * invalid or the end iterator.
764 */
765 size_type range_idx;
766
767 friend class IntervalIterator;
768 };
769
770 /**
771 * Class that represents an iterator pointing to a contiguous interval
772 * $[a,b[$ as returned by IndexSet::begin_interval().
773 */
774 class IntervalIterator
775 {
776 public:
777 /**
778 * Construct a valid iterator pointing to the interval with index @p
779 * range_idx.
780 */
781 IntervalIterator(const IndexSet *idxset, const size_type range_idx);
782
783 /**
784 * Construct an invalid iterator (used as end()).
785 */
786 explicit IntervalIterator(const IndexSet *idxset);
787
788 /**
789 * Construct an empty iterator.
790 */
791 IntervalIterator();
792
793 /**
794 * Copy constructor from @p other iterator.
795 */
796 IntervalIterator(const IntervalIterator &other) = default;
797
798 /**
799 * Assignment of another iterator.
800 */
801 IntervalIterator &
802 operator=(const IntervalIterator &other) = default;
803
804 /**
805 * Prefix increment.
806 */
807 IntervalIterator &
808 operator++();
809
810 /**
811 * Postfix increment.
812 */
813 IntervalIterator
814 operator++(int);
815
816 /**
817 * Dereferencing operator, returns an IntervalAccessor.
818 */
819 const IntervalAccessor &
820 operator*() const;
821
822 /**
823 * Dereferencing operator, returns a pointer to an IntervalAccessor.
824 */
825 const IntervalAccessor *
826 operator->() const;
827
828 /**
829 * Comparison.
830 */
831 bool
832 operator==(const IntervalIterator &) const;
833
834 /**
835 * Inverse of <tt>==</tt>.
836 */
837 bool
838 operator!=(const IntervalIterator &) const;
839
840 /**
841 * Comparison operator.
842 */
843 bool
844 operator<(const IntervalIterator &) const;
845
846 /**
847 * Return the distance between the current iterator and the argument. The
848 * distance is given by how many times one has to apply operator++ to the
849 * current iterator to get the argument (for a positive return value), or
850 * operator-- (for a negative return value).
851 */
852 int
853 operator-(const IntervalIterator &p) const;
854
855 /**
856 * Mark the class as forward iterator and declare some alias which are
857 * standard for iterators and are used by algorithms to enquire about the
858 * specifics of the iterators they work on.
859 */
860 using iterator_category = std::forward_iterator_tag;
861 using value_type = IntervalAccessor;
862 using difference_type = std::ptrdiff_t;
863 using pointer = IntervalAccessor *;
864 using reference = IntervalAccessor &;
865
866 private:
867 /**
868 * Accessor that contains what IndexSet and interval we are pointing at.
869 */
870 IntervalAccessor accessor;
871 };
872
873 /**
874 * Class that represents an iterator pointing to a single element in the
875 * IndexSet as returned by IndexSet::begin().
876 */
877 class ElementIterator
878 {
879 public:
880 /**
881 * Construct an iterator pointing to the global index @p index in the
882 * interval @p range_idx
883 */
884 ElementIterator(const IndexSet *idxset,
885 const size_type range_idx,
886 const size_type index);
887
888 /**
889 * Construct an iterator pointing to the end of the IndexSet.
890 */
891 explicit ElementIterator(const IndexSet *idxset);
892
893 /**
894 * Dereferencing operator. The returned value is the index of the element
895 * inside the IndexSet.
896 */
897 size_type
898 operator*() const;
899
900 /**
901 * Does this iterator point to an existing element?
902 */
903 bool
904 is_valid() const;
905
906 /**
907 * Prefix increment.
908 */
909 ElementIterator &
910 operator++();
911
912 /**
913 * Postfix increment.
914 */
915 ElementIterator
916 operator++(int);
917
918 /**
919 * Comparison.
920 */
921 bool
922 operator==(const ElementIterator &) const;
923
924 /**
925 * Inverse of <tt>==</tt>.
926 */
927 bool
928 operator!=(const ElementIterator &) const;
929
930 /**
931 * Comparison operator.
932 */
933 bool
934 operator<(const ElementIterator &) const;
935
936 /**
937 * Return the distance between the current iterator and the argument. In
938 * the expression <code>it_left-it_right</code> the distance is given by
939 * how many times one has to apply operator++ to the right operand @p
940 * it_right to get the left operand @p it_left (for a positive return
941 * value), or to @p it_left to get the @p it_right (for a negative return
942 * value).
943 */
944 std::ptrdiff_t
945 operator-(const ElementIterator &p) const;
946
947 /**
948 * Mark the class as forward iterator and declare some alias which are
949 * standard for iterators and are used by algorithms to enquire about the
950 * specifics of the iterators they work on.
951 */
952 using iterator_category = std::forward_iterator_tag;
953 using value_type = size_type;
954 using difference_type = std::ptrdiff_t;
955 using pointer = size_type *;
956 using reference = size_type &;
957
958 private:
959 /**
960 * Advance iterator by one.
961 */
962 void
963 advance();
964
965 /**
966 * The parent IndexSet.
967 */
968 const IndexSet *index_set;
969 /**
970 * Index into index_set.ranges.
971 */
972 size_type range_idx;
973 /**
974 * The global index this iterator is pointing at.
975 */
976 size_type idx;
977 };
978
979 /**
980 * Return an iterator that points at the first index that is contained in
981 * this IndexSet.
982 */
983 ElementIterator
984 begin() const;
985
986 /**
987 * Return an element iterator pointing to the element with global index
988 * @p global_index or the next larger element if the index is not in the
989 * set. This is equivalent to
990 * @code
991 * auto p = begin();
992 * while (*p<global_index)
993 * ++p;
994 * return p;
995 * @endcode
996 *
997 * If there is no element in this IndexSet at or behind @p global_index,
998 * this method will return end().
999 */
1000 ElementIterator
1001 at(const size_type global_index) const;
1002
1003 /**
1004 * Return an iterator that points one after the last index that is contained
1005 * in this IndexSet.
1006 */
1007 ElementIterator
1008 end() const;
1009
1010 /**
1011 * Return an Iterator that points at the first interval of this IndexSet.
1012 */
1013 IntervalIterator
1014 begin_intervals() const;
1015
1016 /**
1017 * Return an Iterator that points one after the last interval of this
1018 * IndexSet.
1019 */
1020 IntervalIterator
1021 end_intervals() const;
1022
1023 /**
1024 * @}
1025 */
1026
1027 private:
1028 /**
1029 * A type that denotes the half open index range <code>[begin,end)</code>.
1030 *
1031 * The nth_index_in_set denotes the how many-th index within this IndexSet
1032 * the first element of the current range is. This information is only
1033 * accurate if IndexSet::compress() has been called after the last
1034 * insertion.
1035 */
1036 struct Range
1037 {
1038 size_type begin;
1039 size_type end;
1040
1041 size_type nth_index_in_set;
1042
1043 /**
1044 * Default constructor. Since there is no useful choice for a default
1045 * constructed interval, this constructor simply creates something that
1046 * resembles an invalid range. We need this constructor for serialization
1047 * purposes, but the invalid range should be filled with something read
1048 * from the archive before it is used, so we should hopefully never get to
1049 * see an invalid range in the wild.
1050 */
1051 Range();
1052
1053 /**
1054 * Constructor. Create a half-open interval with the given indices.
1055 *
1056 * @param i1 Left end point of the interval.
1057 * @param i2 First index greater than the last index of the indicated
1058 * range.
1059 */
1060 Range(const size_type i1, const size_type i2);
1061
1062 friend inline bool
1063 operator<(const Range &range_1, const Range &range_2)
1064 {
1065 return (
1066 (range_1.begin < range_2.begin) ||
1067 ((range_1.begin == range_2.begin) && (range_1.end < range_2.end)));
1068 }
1069
1070 static bool
1071 end_compare(const IndexSet::Range &x, const IndexSet::Range &y)
1072 {
1073 return x.end < y.end;
1074 }
1075
1076 static bool
1077 nth_index_compare(const IndexSet::Range &x, const IndexSet::Range &y)
1078 {
1079 return (x.nth_index_in_set + (x.end - x.begin) <
1080 y.nth_index_in_set + (y.end - y.begin));
1081 }
1082
1083 friend inline bool
1084 operator==(const Range &range_1, const Range &range_2)
1085 {
1086 return ((range_1.begin == range_2.begin) && (range_1.end == range_2.end));
1087 }
1088
1089 static std::size_t
1090 memory_consumption()
1091 {
1092 return sizeof(Range);
1093 }
1094
1095 /**
1096 * Write or read the data of this object to or from a stream for the
1097 * purpose of serialization using the [BOOST serialization
1098 * library](https://www.boost.org/doc/libs/1_74_0/libs/serialization/doc/index.html).
1099 */
1100 template <class Archive>
1101 void
1102 serialize(Archive &ar, const unsigned int version);
1103 };
1104
1105 /**
1106 * A set of contiguous ranges of indices that make up (part of) this index
1107 * set. This variable is always kept sorted.
1108 *
1109 * The variable is marked "mutable" so that it can be changed by compress(),
1110 * though this of course doesn't change anything about the external
1111 * representation of this index set.
1112 */
1113 mutable std::vector<Range> ranges;
1114
1115 /**
1116 * True if compress() has been called after the last change in the set of
1117 * indices.
1118 *
1119 * The variable is marked "mutable" so that it can be changed by compress(),
1120 * though this of course doesn't change anything about the external
1121 * representation of this index set.
1122 */
1123 mutable bool is_compressed;
1124
1125 /**
1126 * The overall size of the index range. Elements of this index set have to
1127 * have a smaller number than this value.
1128 */
1129 size_type index_space_size;
1130
1131 /**
1132 * This integer caches the index of the largest range in @p ranges. This
1133 * gives <tt>O(1)</tt> access to the range with most elements, while general
1134 * access costs <tt>O(log(n_ranges))</tt>. The largest range is needed for
1135 * the methods @p is_element(), @p index_within_set(), @p nth_index_in_set.
1136 * In many applications, the largest range contains most elements (the
1137 * locally owned range), whereas there are only a few other elements
1138 * (ghosts).
1139 */
1140 mutable size_type largest_range;
1141
1142 /**
1143 * A mutex that is used to synchronize operations of the do_compress()
1144 * function that is called from many 'const' functions via compress().
1145 */
1146 mutable Threads::Mutex compress_mutex;
1147
1148 /**
1149 * Actually perform the compress() operation.
1150 */
1151 void
1152 do_compress() const;
1153
1154 /**
1155 * Expensive part of is_element() that does a binary search in case we did
1156 * not find the index in the largest range. Kept separate to avoid pulling
1157 * in a binary search in the header and make it easy for the compiler to
1158 * inline the fast path.
1159 */
1160 bool
1161 is_element_binary_search(const size_type local_index) const;
1162
1163 /**
1164 * Expensive part of nth_index_in_set() that does the binary search in case
1165 * we did not find the index in the largest range. Kept separate to avoid
1166 * using a binary search in the header and make it easy for the compiler to
1167 * inline the fast path.
1168 */
1169 size_type
1170 nth_index_in_set_binary_search(const size_type local_index) const;
1171
1172 /**
1173 * Expensive part of index_within_set() that does the binary search in case
1174 * we did not find the index in the largest range. Kept separate to avoid
1175 * using a binary search in the header and make it easy for the compiler to
1176 * inline the fast path.
1177 */
1178 size_type
1179 index_within_set_binary_search(const size_type global_index) const;
1180
1181 /**
1182 * Expensive part of add_index() and add_range(). Defined in separate
1183 * function to avoid using a binary search in the header and make it easy
1184 * for the compiler to inline the fast path.
1185 */
1186 void
1187 add_range_lower_bound(const Range &range);
1188
1189 /**
1190 * Expensive part of add_indices().
1191 */
1192 void
1193 add_ranges_internal(
1194 boost::container::small_vector<std::pair<size_type, size_type>, 200>
1195 &tmp_ranges,
1196 const bool ranges_are_sorted);
1197 };
1198
1199
1200
1201 /**
1202 * Create and return an index set of size $N$ that contains every single index
1203 * within this range. In essence, this function returns an index set created
1204 * by
1205 * @code
1206 * IndexSet is (N);
1207 * is.add_range(0, N);
1208 * @endcode
1209 * This function exists so that one can create and initialize index sets that
1210 * are complete in one step, or so one can write code like
1211 * @code
1212 * if (my_index_set == complete_index_set(my_index_set.size())
1213 * ...
1214 * @endcode
1215 *
1216 * @relatesalso IndexSet
1217 */
1218 inline IndexSet
1219 complete_index_set(const IndexSet::size_type N)
1220 {
1221 IndexSet is(N);
1222 is.add_range(0, N);
1223 is.compress();
1224 return is;
1225 }
1226
1227 /* ------------------ inline functions ------------------ */
1228
1229
1230 /* IntervalAccessor */
1231
1232 inline IndexSet::IntervalAccessor::IntervalAccessor(
1233 const IndexSet *idxset,
1234 const IndexSet::size_type range_idx)
1235 : index_set(idxset)
1236 , range_idx(range_idx)
1237 {
1238 Assert(range_idx < idxset->n_intervals(),
1239 ExcInternalError("Invalid range index"));
1240 }
1241
1242
1243
1244 inline IndexSet::IntervalAccessor::IntervalAccessor(const IndexSet *idxset)
1245 : index_set(idxset)
1246 , range_idx(numbers::invalid_dof_index)
1247 {}
1248
1249
1250
1251 inline IndexSet::IntervalAccessor::IntervalAccessor(
1252 const IndexSet::IntervalAccessor &other)
1253 : index_set(other.index_set)
1254 , range_idx(other.range_idx)
1255 {
1256 Assert(range_idx == numbers::invalid_dof_index || is_valid(),
1257 ExcMessage("invalid iterator"));
1258 }
1259
1260
1261
1262 inline IndexSet::size_type
1263 IndexSet::IntervalAccessor::n_elements() const
1264 {
1265 Assert(is_valid(), ExcMessage("invalid iterator"));
1266 return index_set->ranges[range_idx].end - index_set->ranges[range_idx].begin;
1267 }
1268
1269
1270
1271 inline bool
1272 IndexSet::IntervalAccessor::is_valid() const
1273 {
1274 return index_set != nullptr && range_idx < index_set->n_intervals();
1275 }
1276
1277
1278
1279 inline IndexSet::ElementIterator
1280 IndexSet::IntervalAccessor::begin() const
1281 {
1282 Assert(is_valid(), ExcMessage("invalid iterator"));
1283 return {index_set, range_idx, index_set->ranges[range_idx].begin};
1284 }
1285
1286
1287
1288 inline IndexSet::ElementIterator
1289 IndexSet::IntervalAccessor::end() const
1290 {
1291 Assert(is_valid(), ExcMessage("invalid iterator"));
1292
1293 // point to first index in next interval unless we are the last interval.
1294 if (range_idx < index_set->ranges.size() - 1)
1295 return {index_set, range_idx + 1, index_set->ranges[range_idx + 1].begin};
1296 else
1297 return index_set->end();
1298 }
1299
1300
1301
1302 inline IndexSet::size_type
1303 IndexSet::IntervalAccessor::last() const
1304 {
1305 Assert(is_valid(), ExcMessage("invalid iterator"));
1306
1307 return index_set->ranges[range_idx].end - 1;
1308 }
1309
1310
1311
1312 inline IndexSet::IntervalAccessor &
1313 IndexSet::IntervalAccessor::operator=(const IndexSet::IntervalAccessor &other)
1314 {
1315 index_set = other.index_set;
1316 range_idx = other.range_idx;
1317 Assert(range_idx == numbers::invalid_dof_index || is_valid(),
1318 ExcMessage("invalid iterator"));
1319 return *this;
1320 }
1321
1322
1323
1324 inline bool
1325 IndexSet::IntervalAccessor::operator==(
1326 const IndexSet::IntervalAccessor &other) const
1327 {
1328 Assert(index_set == other.index_set,
1329 ExcMessage(
1330 "Can not compare accessors pointing to different IndexSets"));
1331 return range_idx == other.range_idx;
1332 }
1333
1334
1335
1336 inline bool
1337 IndexSet::IntervalAccessor::operator<(
1338 const IndexSet::IntervalAccessor &other) const
1339 {
1340 Assert(index_set == other.index_set,
1341 ExcMessage(
1342 "Can not compare accessors pointing to different IndexSets"));
1343 return range_idx < other.range_idx;
1344 }
1345
1346
1347
1348 inline void
1349 IndexSet::IntervalAccessor::advance()
1350 {
1351 Assert(
1352 is_valid(),
1353 ExcMessage(
1354 "Impossible to advance an IndexSet::IntervalIterator that is invalid"));
1355 ++range_idx;
1356
1357 // set ourselves to invalid if we walk off the end
1358 if (range_idx >= index_set->ranges.size())
1359 range_idx = numbers::invalid_dof_index;
1360 }
1361
1362
1363 /* IntervalIterator */
1364
1365 inline IndexSet::IntervalIterator::IntervalIterator(
1366 const IndexSet *idxset,
1367 const IndexSet::size_type range_idx)
1368 : accessor(idxset, range_idx)
1369 {}
1370
1371
1372
1373 inline IndexSet::IntervalIterator::IntervalIterator()
1374 : accessor(nullptr)
1375 {}
1376
1377
1378
1379 inline IndexSet::IntervalIterator::IntervalIterator(const IndexSet *idxset)
1380 : accessor(idxset)
1381 {}
1382
1383
1384
1385 inline IndexSet::IntervalIterator &
1386 IndexSet::IntervalIterator::operator++()
1387 {
1388 accessor.advance();
1389 return *this;
1390 }
1391
1392
1393
1394 inline IndexSet::IntervalIterator
1395 IndexSet::IntervalIterator::operator++(int)
1396 {
1397 const IndexSet::IntervalIterator iter = *this;
1398 accessor.advance();
1399 return iter;
1400 }
1401
1402
1403
1404 inline const IndexSet::IntervalAccessor &
1405 IndexSet::IntervalIterator::operator*() const
1406 {
1407 return accessor;
1408 }
1409
1410
1411
1412 inline const IndexSet::IntervalAccessor *
1413 IndexSet::IntervalIterator::operator->() const
1414 {
1415 return &accessor;
1416 }
1417
1418
1419
1420 inline bool
1421 IndexSet::IntervalIterator::operator==(
1422 const IndexSet::IntervalIterator &other) const
1423 {
1424 return accessor == other.accessor;
1425 }
1426
1427
1428
1429 inline bool
1430 IndexSet::IntervalIterator::operator!=(
1431 const IndexSet::IntervalIterator &other) const
1432 {
1433 return !(*this == other);
1434 }
1435
1436
1437
1438 inline bool
1439 IndexSet::IntervalIterator::operator<(
1440 const IndexSet::IntervalIterator &other) const
1441 {
1442 return accessor < other.accessor;
1443 }
1444
1445
1446
1447 inline int
1448 IndexSet::IntervalIterator::operator-(
1449 const IndexSet::IntervalIterator &other) const
1450 {
1451 Assert(accessor.index_set == other.accessor.index_set,
1452 ExcMessage(
1453 "Can not compare iterators belonging to different IndexSets"));
1454
1455 const size_type lhs = (accessor.range_idx == numbers::invalid_dof_index) ?
1456 accessor.index_set->ranges.size() :
1457 accessor.range_idx;
1458 const size_type rhs =
1459 (other.accessor.range_idx == numbers::invalid_dof_index) ?
1460 accessor.index_set->ranges.size() :
1461 other.accessor.range_idx;
1462
1463 if (lhs > rhs)
1464 return static_cast<int>(lhs - rhs);
1465 else
1466 return -static_cast<int>(rhs - lhs);
1467 }
1468
1469
1470
1471 /* ElementIterator */
1472
1473 inline IndexSet::ElementIterator::ElementIterator(
1474 const IndexSet *idxset,
1475 const IndexSet::size_type range_idx,
1476 const IndexSet::size_type index)
1477 : index_set(idxset)
1478 , range_idx(range_idx)
1479 , idx(index)
1480 {
1481 Assert(range_idx < index_set->ranges.size(),
1482 ExcMessage(
1483 "Invalid range index for IndexSet::ElementIterator constructor."));
1484 Assert(
1485 idx >= index_set->ranges[range_idx].begin &&
1486 idx < index_set->ranges[range_idx].end,
1487 ExcInternalError(
1488 "Invalid index argument for IndexSet::ElementIterator constructor."));
1489 }
1490
1491
1492
1493 inline IndexSet::ElementIterator::ElementIterator(const IndexSet *idxset)
1494 : index_set(idxset)
1495 , range_idx(numbers::invalid_dof_index)
1496 , idx(numbers::invalid_dof_index)
1497 {}
1498
1499
1500
1501 inline bool
1502 IndexSet::ElementIterator::is_valid() const
1503 {
1504 Assert((range_idx == numbers::invalid_dof_index &&
1505 idx == numbers::invalid_dof_index) ||
1506 (range_idx < index_set->ranges.size() &&
1507 idx < index_set->ranges[range_idx].end),
1508 ExcInternalError("Invalid ElementIterator state."));
1509
1510 return (range_idx < index_set->ranges.size() &&
1511 idx < index_set->ranges[range_idx].end);
1512 }
1513
1514
1515
1516 inline IndexSet::size_type
1517 IndexSet::ElementIterator::operator*() const
1518 {
1519 Assert(
1520 is_valid(),
1521 ExcMessage(
1522 "Impossible to dereference an IndexSet::ElementIterator that is invalid"));
1523 return idx;
1524 }
1525
1526
1527
1528 inline bool
1529 IndexSet::ElementIterator::operator==(
1530 const IndexSet::ElementIterator &other) const
1531 {
1532 Assert(index_set == other.index_set,
1533 ExcMessage(
1534 "Can not compare iterators belonging to different IndexSets"));
1535 return range_idx == other.range_idx && idx == other.idx;
1536 }
1537
1538
1539
1540 inline void
1541 IndexSet::ElementIterator::advance()
1542 {
1543 Assert(
1544 is_valid(),
1545 ExcMessage(
1546 "Impossible to advance an IndexSet::ElementIterator that is invalid"));
1547 if (idx < index_set->ranges[range_idx].end)
1548 ++idx;
1549 // end of this range?
1550 if (idx == index_set->ranges[range_idx].end)
1551 {
1552 // point to first element in next interval if possible
1553 if (range_idx < index_set->ranges.size() - 1)
1554 {
1555 ++range_idx;
1556 idx = index_set->ranges[range_idx].begin;
1557 }
1558 else
1559 {
1560 // we just fell off the end, set to invalid:
1561 range_idx = numbers::invalid_dof_index;
1562 idx = numbers::invalid_dof_index;
1563 }
1564 }
1565 }
1566
1567
1568
1569 inline IndexSet::ElementIterator &
1570 IndexSet::ElementIterator::operator++()
1571 {
1572 advance();
1573 return *this;
1574 }
1575
1576
1577
1578 inline IndexSet::ElementIterator
1579 IndexSet::ElementIterator::operator++(int)
1580 {
1581 const IndexSet::ElementIterator it = *this;
1582 advance();
1583 return it;
1584 }
1585
1586
1587
1588 inline bool
1589 IndexSet::ElementIterator::operator!=(
1590 const IndexSet::ElementIterator &other) const
1591 {
1592 return !(*this == other);
1593 }
1594
1595
1596
1597 inline bool
1598 IndexSet::ElementIterator::operator<(
1599 const IndexSet::ElementIterator &other) const
1600 {
1601 Assert(index_set == other.index_set,
1602 ExcMessage(
1603 "Can not compare iterators belonging to different IndexSets"));
1604 return range_idx < other.range_idx ||
1605 (range_idx == other.range_idx && idx < other.idx);
1606 }
1607
1608
1609
1610 inline std::ptrdiff_t
1611 IndexSet::ElementIterator::operator-(
1612 const IndexSet::ElementIterator &other) const
1613 {
1614 Assert(index_set == other.index_set,
1615 ExcMessage(
1616 "Can not compare iterators belonging to different IndexSets"));
1617 if (*this == other)
1618 return 0;
1619 if (!(*this < other))
1620 return -(other - *this);
1621
1622 // only other can be equal to end() because of the checks above.
1623 Assert(is_valid(), ExcInternalError());
1624
1625 // Note: we now compute how far advance *this in "*this < other" to get other,
1626 // so we need to return -c at the end.
1627
1628 // first finish the current range:
1629 std::ptrdiff_t c = index_set->ranges[range_idx].end - idx;
1630
1631 // now walk in steps of ranges (need to start one behind our current one):
1632 for (size_type range = range_idx + 1;
1633 range < index_set->ranges.size() && range <= other.range_idx;
1634 ++range)
1635 c += index_set->ranges[range].end - index_set->ranges[range].begin;
1636
1637 Assert(
1638 other.range_idx < index_set->ranges.size() ||
1639 other.range_idx == numbers::invalid_dof_index,
1640 ExcMessage(
1641 "Inconsistent iterator state. Did you invalidate iterators by modifying the IndexSet?"));
1642
1643 // We might have walked too far because we went until the end of
1644 // other.range_idx, so walk backwards to other.idx:
1645 if (other.range_idx != numbers::invalid_dof_index)
1646 c -= index_set->ranges[other.range_idx].end - other.idx;
1647
1648 return -c;
1649 }
1650
1651
1652 /* Range */
1653
1654 inline IndexSet::Range::Range()
1655 : begin(numbers::invalid_dof_index)
1656 , end(numbers::invalid_dof_index)
1657 , nth_index_in_set(numbers::invalid_dof_index)
1658 {}
1659
1660
1661
1662 inline IndexSet::Range::Range(const size_type i1, const size_type i2)
1663 : begin(i1)
1664 , end(i2)
1665 , nth_index_in_set(numbers::invalid_dof_index)
1666 {}
1667
1668
1669
1670 /* IndexSet itself */
1671
1672 inline IndexSet::IndexSet()
1673 : is_compressed(true)
1674 , index_space_size(0)
1675 , largest_range(numbers::invalid_unsigned_int)
1676 {}
1677
1678
1679
1680 inline IndexSet::IndexSet(const size_type size)
1681 : is_compressed(true)
1682 , index_space_size(size)
1683 , largest_range(numbers::invalid_unsigned_int)
1684 {}
1685
1686
1687
1688 inline IndexSet::IndexSet(IndexSet &&is) noexcept
1689 : ranges(std::move(is.ranges))
1690 , is_compressed(is.is_compressed)
1691 , index_space_size(is.index_space_size)
1692 , largest_range(is.largest_range)
1693 {
1694 is.ranges.clear();
1695 is.is_compressed = true;
1696 is.index_space_size = 0;
1697 is.largest_range = numbers::invalid_unsigned_int;
1698
1699 compress();
1700 }
1701
1702
1703
1704 inline IndexSet &
1705 IndexSet::operator=(IndexSet &&is) noexcept
1706 {
1707 ranges = std::move(is.ranges);
1708 is_compressed = is.is_compressed;
1709 index_space_size = is.index_space_size;
1710 largest_range = is.largest_range;
1711
1712 is.ranges.clear();
1713 is.is_compressed = true;
1714 is.index_space_size = 0;
1715 is.largest_range = numbers::invalid_unsigned_int;
1716
1717 compress();
1718
1719 return *this;
1720 }
1721
1722
1723
1724 inline IndexSet::ElementIterator
1725 IndexSet::begin() const
1726 {
1727 compress();
1728 if (ranges.size() > 0)
1729 return {this, 0, ranges[0].begin};
1730 else
1731 return end();
1732 }
1733
1734
1735
1736 inline IndexSet::ElementIterator
1737 IndexSet::end() const
1738 {
1739 compress();
1740 return IndexSet::ElementIterator(this);
1741 }
1742
1743
1744
1745 inline IndexSet::IntervalIterator
1746 IndexSet::begin_intervals() const
1747 {
1748 compress();
1749 if (ranges.size() > 0)
1750 return IndexSet::IntervalIterator(this, 0);
1751 else
1752 return end_intervals();
1753 }
1754
1755
1756
1757 inline IndexSet::IntervalIterator
1758 IndexSet::end_intervals() const
1759 {
1760 compress();
1761 return IndexSet::IntervalIterator(this);
1762 }
1763
1764
1765
1766 inline void
1767 IndexSet::clear()
1768 {
1769 // reset so that there are no indices in the set any more; however,
1770 // as documented, the index set retains its size
1771 ranges.clear();
1772 is_compressed = true;
1773 largest_range = numbers::invalid_unsigned_int;
1774 }
1775
1776
1777
1778 inline void
1779 IndexSet::set_size(const size_type sz)
1780 {
1781 Assert(ranges.empty(),
1782 ExcMessage("This function can only be called if the current "
1783 "object does not yet contain any elements."));
1784 index_space_size = sz;
1785 is_compressed = true;
1786 }
1787
1788
1789
1790 inline IndexSet::size_type
1791 IndexSet::size() const
1792 {
1793 return index_space_size;
1794 }
1795
1796
1797
1798 inline void
1799 IndexSet::compress() const
1800 {
1801 if (is_compressed == true)
1802 return;
1803
1804 do_compress();
1805 }
1806
1807
1808
1809 inline void
1810 IndexSet::add_index(const size_type index)
1811 {
1812 add_range(index, index + 1);
1813 }
1814
1815
1816
1817 inline void
1818 IndexSet::add_range(const size_type begin, const size_type end)
1819 {
1820 Assert((begin < index_space_size) ||
1821 ((begin == index_space_size) && (end == index_space_size)),
1822 ExcIndexRangeType<size_type>(begin, 0, index_space_size));
1823 Assert(end <= index_space_size,
1824 ExcIndexRangeType<size_type>(end, 0, index_space_size + 1));
1825 AssertIndexRange(begin, end + 1);
1826
1827 if (begin != end)
1828 {
1829 // the new index might be larger than the last index present in the
1830 // ranges. Then we can skip the binary search
1831 if (ranges.empty() || begin > ranges.back().end)
1832 ranges.emplace_back(begin, end);
1833 else if (begin == ranges.back().end)
1834 ranges.back().end = end;
1835 else
1836 add_range_lower_bound(Range(begin, end));
1837
1838 is_compressed = false;
1839 }
1840 }
1841
1842
1843
1844 template <typename ForwardIterator>
1845 inline void
1846 IndexSet::add_indices(const ForwardIterator &begin, const ForwardIterator &end)
1847 {
1848 if (begin == end)
1849 return;
1850
1851 // identify ranges in the given iterator range by checking whether some
1852 // indices happen to be consecutive. to avoid quadratic complexity when
1853 // calling add_range many times (as add_range() going into the middle of an
1854 // already existing range must shift entries around), we first collect a
1855 // vector of ranges.
1856 boost::container::small_vector<std::pair<size_type, size_type>, 200>
1857 tmp_ranges;
1858 bool ranges_are_sorted = true;
1859 for (ForwardIterator p = begin; p != end;)
1860 {
1861 // Starting with the current iterator 'p', find an iterator
1862 // 'q' so that the indices pointed to by the iterators in
1863 // the range [p,q) are consecutive. These indices then form
1864 // a range that is contiguous, and that can be added all
1865 // at once.
1866 const size_type begin_index = *p;
1867 size_type end_index = begin_index + 1;
1868
1869 // Start looking at the position after 'p', and keep iterating while
1870 // 'q' points to a duplicate of 'p':
1871 ForwardIterator q = p;
1872 ++q;
1873 while ((q != end) && (*q == *p))
1874 ++q;
1875
1876 // Now we know that 'q' is either past the end, or points to a value
1877 // other than 'p'. If it points to 'end_index', we are still good with
1878 // a contiguous range; then increment the end index of that range, and
1879 // move to the next iterator that is not a duplicate of what
1880 // we were just looking at:
1881 while ((q != end) && (static_cast<size_type>(*q) == end_index))
1882 {
1883 ++q;
1884 while ((q != end) && (static_cast<size_type>(*q) == end_index))
1885 ++q;
1886
1887 ++end_index;
1888 }
1889
1890 // Add this range:
1891 tmp_ranges.emplace_back(begin_index, end_index);
1892
1893 // Then move on to the next element in the input range.
1894 // If the starting index of the next go-around of the for loop is less
1895 // than the end index of the one just identified, then we will have at
1896 // least one pair of ranges that are not sorted, and consequently the
1897 // whole collection of ranges is not sorted.
1898 p = q;
1899 if ((p != end) && (static_cast<size_type>(*p) < end_index))
1900 ranges_are_sorted = false;
1901 }
1902
1903 add_ranges_internal(tmp_ranges, ranges_are_sorted);
1904 }
1905
1906
1907
1908 inline bool
1909 IndexSet::is_element(const size_type index) const
1910 {
1911 if (ranges.empty() == false)
1912 {
1913 compress();
1914
1915 // fast check whether the index is in the largest range
1916 Assert(largest_range < ranges.size(), ExcInternalError());
1917 if (index >= ranges[largest_range].begin &&
1918 index < ranges[largest_range].end)
1919 return true;
1920 else if (ranges.size() > 1)
1921 return is_element_binary_search(index);
1922 else
1923 return false;
1924 }
1925 else
1926 return false;
1927 }
1928
1929
1930
1931 inline bool
1932 IndexSet::is_contiguous() const
1933 {
1934 compress();
1935 return (ranges.size() <= 1);
1936 }
1937
1938
1939
1940 inline bool
1941 IndexSet::is_empty() const
1942 {
1943 return ranges.empty();
1944 }
1945
1946
1947
1948 inline IndexSet::size_type
1949 IndexSet::n_elements() const
1950 {
1951 // make sure we have non-overlapping ranges
1952 compress();
1953
1954 size_type v = 0;
1955 if (!ranges.empty())
1956 {
1957 const Range &r = ranges.back();
1958 v = r.nth_index_in_set + r.end - r.begin;
1959 }
1960
1961 if constexpr (running_in_debug_mode())
1962 {
1963 size_type s = 0;
1964 for (const auto &range : ranges)
1965 s += (range.end - range.begin);
1966 Assert(s == v, ExcInternalError());
1967 }
1968
1969 return v;
1970 }
1971
1972
1973
1974 inline unsigned int
1975 IndexSet::n_intervals() const
1976 {
1977 compress();
1978 return ranges.size();
1979 }
1980
1981
1982
1983 inline IndexSet::size_type
1984 IndexSet::largest_range_starting_index() const
1985 {
1986 Assert(ranges.empty() == false, ExcMessage("IndexSet cannot be empty."));
1987
1988 compress();
1989 const std::vector<Range>::const_iterator main_range =
1990 ranges.begin() + largest_range;
1991
1992 return main_range->nth_index_in_set;
1993 }
1994
1995
1996
1997 inline IndexSet::size_type
1998 IndexSet::nth_index_in_set(const size_type n) const
1999 {
2000 AssertIndexRange(n, n_elements());
2001
2002 compress();
2003
2004 // first check whether the index is in the largest range
2005 Assert(largest_range < ranges.size(), ExcInternalError());
2006 const auto main_range = ranges.begin() + largest_range;
2007 if (n >= main_range->nth_index_in_set &&
2008 n < main_range->nth_index_in_set + (main_range->end - main_range->begin))
2009 return main_range->begin + (n - main_range->nth_index_in_set);
2010 else
2011 return nth_index_in_set_binary_search(n);
2012 }
2013
2014
2015
2016 inline IndexSet::size_type
2017 IndexSet::index_within_set(const size_type n) const
2018 {
2019 // to make this call thread-safe, compress() must not be called through this
2020 // function
2021 Assert(is_compressed == true, ExcMessage("IndexSet must be compressed."));
2022 AssertIndexRange(n, size());
2023
2024 // return immediately if the index set is empty
2025 if (is_empty())
2026 return numbers::invalid_dof_index;
2027
2028 // check whether the index is in the largest range. use the result to
2029 // perform a one-sided binary search afterward
2030 Assert(largest_range < ranges.size(), ExcInternalError());
2031 if (n >= ranges[largest_range].begin && n < ranges[largest_range].end)
2032 return (n - ranges[largest_range].begin) +
2033 ranges[largest_range].nth_index_in_set;
2034 else if (ranges.size() > 1)
2035 return index_within_set_binary_search(n);
2036 else
2037 return numbers::invalid_dof_index;
2038 }
2039
2040
2041
2042 inline bool
2043 IndexSet::operator==(const IndexSet &is) const
2044 {
2045 // If one of the two index sets has size zero, the other one has to
2046 // have size zero as well:
2047 if (size() == 0)
2048 return (is.size() == 0);
2049 if (is.size() == 0)
2050 return (size() == 0);
2051
2052 // Otherwise, they must have the same size (see the documentation):
2053 Assert(size() == is.size(), ExcDimensionMismatch(size(), is.size()));
2054
2055 compress();
2056 is.compress();
2057
2058 return (ranges == is.ranges);
2059 }
2060
2061
2062
2063 inline bool
2064 IndexSet::operator!=(const IndexSet &is) const
2065 {
2066 // If one of the two index sets has size zero, the other one has to
2067 // have a non-zero size for inequality:
2068 if (size() == 0)
2069 return (is.size() != 0);
2070 if (is.size() == 0)
2071 return (size() != 0);
2072
2073 // Otherwise, they must have the same size (see the documentation):
2074 Assert(size() == is.size(), ExcDimensionMismatch(size(), is.size()));
2075
2076 compress();
2077 is.compress();
2078
2079 return (ranges != is.ranges);
2080 }
2081
2082
2083
2084 template <typename Vector>
2085 void
2086 IndexSet::fill_binary_vector(Vector &vector) const
2087 {
2088 Assert(vector.size() == size(), ExcDimensionMismatch(vector.size(), size()));
2089
2090 compress();
2091 // first fill all elements of the vector with zeroes.
2092 std::fill(vector.begin(), vector.end(), 0);
2093
2094 // then write ones into the elements whose indices are contained in the
2095 // index set
2096 for (const auto &range : ranges)
2097 for (size_type i = range.begin; i < range.end; ++i)
2098 vector[i] = 1;
2099 }
2100
2101
2102
2103 template <typename StreamType>
2104 inline void
2105 IndexSet::print(StreamType &out) const
2106 {
2107 compress();
2108 out << '{';
2109 std::vector<Range>::const_iterator p;
2110 for (p = ranges.begin(); p != ranges.end(); ++p)
2111 {
2112 if (p->end - p->begin == 1)
2113 out << p->begin;
2114 else
2115 out << '[' << p->begin << ',' << p->end - 1 << ']';
2116
2117 if (p != --ranges.end())
2118 out << ", ";
2119 }
2120 out << '}' << std::endl;
2121 }
2122
2123
2124
2125 template <class Archive>
2126 inline void
2127 IndexSet::Range::serialize(Archive &ar, const unsigned int)
2128 {
2129 ar &begin &end &nth_index_in_set;
2130 }
2131
2132
2133
2134 template <class Archive>
2135 inline void
2136 IndexSet::serialize(Archive &ar, const unsigned int)
2137 {
2138 ar &ranges &is_compressed &index_space_size &largest_range;
2139 }
2140
2141 DEAL_II_NAMESPACE_CLOSE
2142
2143 #endif