Debian Codegraph @

include/deal.II/lac/dynamic_sparsity_pattern.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2011 - 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_dynamic_sparsity_pattern_h
16 #define dealii_dynamic_sparsity_pattern_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/index_set.h>
23 #include <deal.II/base/utilities.h>
24
25 #include <deal.II/lac/exceptions.h>
26 #include <deal.II/lac/sparsity_pattern_base.h>
27
28 #include <algorithm>
29 #include <iostream>
30 #include <vector>
31
32 DEAL_II_NAMESPACE_OPEN
33
34 // Forward declaration
35 #ifndef DOXYGEN
36 class DynamicSparsityPattern;
37 #endif
38
39 /**
40 * @addtogroup Sparsity
41 * @{
42 */
43
44
45 /**
46 * Iterators on objects of type DynamicSparsityPattern.
47 */
48 namespace DynamicSparsityPatternIterators
49 {
50 // forward declaration
51 class Iterator;
52
53 /**
54 * Declare type for container size.
55 */
56 using size_type = types::global_dof_index;
57
58 /**
59 * Accessor class for iterators into objects of type DynamicSparsityPattern.
60 *
61 * Note that this class only allows read access to elements, providing their
62 * row and column number (or alternatively the index within the complete
63 * sparsity pattern). It does not allow modifying the sparsity pattern
64 * itself.
65 */
66 class Accessor
67 {
68 public:
69 /**
70 * Constructor.
71 */
72 Accessor(const DynamicSparsityPattern *sparsity_pattern,
73 const size_type row,
74 const unsigned int index_within_row);
75
76 /**
77 * Constructor. Construct the end accessor for the given sparsity pattern.
78 */
79 Accessor(const DynamicSparsityPattern *sparsity_pattern);
80
81 /**
82 * Default constructor creating a dummy accessor. This constructor is here
83 * only to be able to store accessors in STL containers such as
84 * `std::vector`.
85 */
86 Accessor();
87
88 /**
89 * Row number of the element represented by this object.
90 */
91 size_type
92 row() const;
93
94 /**
95 * Index within the current row of the element represented by this object.
96 */
97 size_type
98 index() const;
99
100 /**
101 * Column number of the element represented by this object.
102 */
103 size_type
104 column() const;
105
106 /**
107 * Comparison. True, if both iterators point to the same matrix position.
108 */
109 bool
110 operator==(const Accessor &) const;
111
112 /**
113 * Comparison operator. Result is true if either the first row number is
114 * smaller or if the row numbers are equal and the first index is smaller.
115 *
116 * This function is only valid if both iterators point into the same
117 * sparsity pattern.
118 */
119 bool
120 operator<(const Accessor &) const;
121
122 protected:
123 DeclExceptionMsg(DummyAccessor,
124 "The instance of this class was initialized"
125 " without DynamicSparsityPattern object, which"
126 " means that it is a dummy accessor that can"
127 " not do any operations.");
128
129 /**
130 * The sparsity pattern we operate on accessed.
131 */
132 const DynamicSparsityPattern *sparsity_pattern;
133
134 /**
135 * The row we currently point into.
136 */
137 size_type current_row;
138
139 /**
140 * A pointer to the element within the current row that we currently point
141 * to.
142 */
143 std::vector<size_type>::const_iterator current_entry;
144
145 /**
146 * A pointer to the end of the current row. We store this to make
147 * comparison against the end of line iterator cheaper as it otherwise
148 * needs to do the IndexSet translation from row index to the index within
149 * the 'lines' array of DynamicSparsityPattern.
150 */
151 std::vector<size_type>::const_iterator end_of_row;
152
153 /**
154 * Move the accessor to the next nonzero entry in the matrix.
155 */
156 void
157 advance();
158
159 // Grant access to iterator class.
160 friend class Iterator;
161 };
162
163
164
165 /**
166 * An iterator class for walking over the elements of a sparsity pattern.
167 *
168 * The typical use for these iterators is to iterate over the elements of a
169 * sparsity pattern (or, since they also serve as the basis for iterating
170 * over the elements of an associated matrix, over the elements of a sparse
171 * matrix), or over the elements of individual rows. There is no guarantee
172 * that the elements of a row are actually traversed in an order in which
173 * column numbers monotonically increase. See the documentation of the
174 * SparsityPattern class for more information.
175 *
176 * @note This class operates directly on the internal data structures of the
177 * DynamicSparsityPattern class. As a consequence, some operations are cheap
178 * and some are not. In particular, it is cheap to access the column index
179 * of the sparsity pattern entry pointed to. On the other hand, it is
180 * expensive to compute the distance between two iterators. As a
181 * consequence, when you design algorithms that use these iterators, it is
182 * common practice to not loop over <i>all</i> elements of a sparsity
183 * pattern at once, but to have an outer loop over all rows and within this
184 * loop iterate over the elements of this row. This way, you only ever need
185 * to dereference the iterator to obtain the column indices whereas the
186 * (expensive) lookup of the row index can be avoided by using the loop
187 * index instead.
188 */
189 class Iterator
190 {
191 public:
192 /**
193 * Constructor. Create an iterator into the sparsity pattern @p sp for the
194 * given global index (i.e., the index of the given element counting from
195 * the zeroth row).
196 */
197 Iterator(const DynamicSparsityPattern *sp,
198 const size_type row,
199 const unsigned int index_within_row);
200
201 /**
202 * Constructor. Create an invalid (end) iterator into the sparsity pattern
203 * @p sp.
204 */
205 Iterator(const DynamicSparsityPattern *sp);
206
207 /**
208 * Default constructor creating an invalid iterator. This constructor is
209 * here only to be able to store iterators in STL containers such as
210 * `std::vector`.
211 */
212 Iterator() = default;
213
214 /**
215 * Prefix increment.
216 */
217 Iterator &
218 operator++();
219
220 /**
221 * Postfix increment.
222 */
223 Iterator
224 operator++(int);
225
226 /**
227 * Dereferencing operator.
228 */
229 const Accessor &
230 operator*() const;
231
232 /**
233 * Dereferencing operator.
234 */
235 const Accessor *
236 operator->() const;
237
238 /**
239 * Comparison. True, if both iterators point to the same matrix position.
240 */
241 bool
242 operator==(const Iterator &) const;
243
244 /**
245 * Inverse of <tt>==</tt>.
246 */
247 bool
248 operator!=(const Iterator &) const;
249
250 /**
251 * Comparison operator. Result is true if either the first row number is
252 * smaller or if the row numbers are equal and the first index is smaller.
253 *
254 * This function is only valid if both iterators point into the same
255 * matrix.
256 */
257 bool
258 operator<(const Iterator &) const;
259
260 /**
261 * Return the distance between the current iterator and the argument. The
262 * distance is given by how many times one has to apply operator++ to the
263 * current iterator to get the argument (for a positive return value), or
264 * operator-- (for a negative return value).
265 */
266 int
267 operator-(const Iterator &p) const;
268
269 private:
270 /**
271 * Store an object of the accessor class.
272 */
273 Accessor accessor;
274 };
275 } // namespace DynamicSparsityPatternIterators
276
277
278 /**
279 * This class acts as an intermediate form of the SparsityPattern class. From
280 * the interface it mostly represents a SparsityPattern object that is kept
281 * compressed at all times. However, since the final sparsity pattern is not
282 * known while constructing it, keeping the pattern compressed at all times
283 * can only be achieved at the expense of either increased memory or run time
284 * consumption upon use. The main purpose of this class is to avoid some
285 * memory bottlenecks, so we chose to implement it memory conservative. The
286 * chosen data format is too unsuited to be used for actual matrices, though.
287 * It is therefore necessary to first copy the data of this object over to an
288 * object of type SparsityPattern before using it in actual matrices.
289 *
290 * Another viewpoint is that this class does not need up front allocation of a
291 * certain amount of memory, but grows as necessary. An extensive description
292 * of sparsity patterns can be found in the documentation of the
293 * @ref Sparsity
294 * topic.
295 *
296 * This class is an example of the "dynamic" type of
297 * @ref Sparsity.
298 * It is used in most tutorial programs in one way or another.
299 *
300 * <h3>Interface</h3>
301 *
302 * Since this class is intended as an intermediate replacement of the
303 * SparsityPattern class, it has mostly the same interface, with small changes
304 * where necessary. In particular, the add() function, and the functions
305 * inquiring properties of the sparsity pattern are the same.
306 *
307 *
308 * <h3>Usage</h3>
309 *
310 * Usage of this class is explained in step-2 (without constraints) and step-6
311 * (with AffineConstraints) and typically looks as follows:
312 * @code
313 * DynamicSparsityPattern dynamic_pattern (dof_handler.n_dofs());
314 * DoFTools::make_sparsity_pattern (dof_handler,
315 * dynamic_pattern,
316 * constraints);
317 * SparsityPattern sp;
318 * sp.copy_from (dynamic_pattern);
319 * @endcode
320 */
321 class DynamicSparsityPattern : public SparsityPatternBase
322 {
323 public:
324 /**
325 * Declare the type for container size.
326 */
327 using size_type = types::global_dof_index;
328
329 /**
330 * Typedef an for iterator class that allows to walk over all nonzero
331 * elements of a sparsity pattern.
332 *
333 * Since the iterator does not allow to modify the sparsity pattern, this
334 * type is the same as that for @p const_iterator.
335 */
336 using iterator = DynamicSparsityPatternIterators::Iterator;
337
338 /**
339 * Typedef for an iterator class that allows to walk over all nonzero
340 * elements of a sparsity pattern.
341 */
342 using const_iterator = DynamicSparsityPatternIterators::Iterator;
343
344 /**
345 * Initialize as an empty object. This is useful if you want such objects as
346 * member variables in other classes. You can make the structure usable by
347 * calling the reinit() function.
348 */
349 DynamicSparsityPattern();
350
351 /**
352 * Copy constructor. This constructor is only allowed to be called if the
353 * sparsity structure to be copied is empty. This is so in order to prevent
354 * involuntary copies of objects for temporaries, which can use large
355 * amounts of computing time. However, copy constructors are needed if you
356 * want to place a DynamicSparsityPattern in a container, e.g. to write such
357 * statements like <tt>v.push_back (DynamicSparsityPattern());</tt>, with @p
358 * v a vector of @p DynamicSparsityPattern objects.
359 */
360 DynamicSparsityPattern(const DynamicSparsityPattern &);
361
362 /**
363 * Initialize a rectangular sparsity pattern with @p m rows and @p n
364 * columns. The @p rowset restricts the storage to elements in rows of this
365 * set. Adding elements outside of this set has no effect. The default
366 * argument keeps all entries.
367 */
368 DynamicSparsityPattern(const size_type m,
369 const size_type n,
370 const IndexSet &rowset = IndexSet());
371
372 /**
373 * Create a square SparsityPattern using the given index set. The total size
374 * is given by the size of @p indexset and only rows corresponding to
375 * indices in @p indexset are stored on the current processor.
376 */
377 DynamicSparsityPattern(const IndexSet &indexset);
378
379 /**
380 * Initialize a square pattern of dimension @p n.
381 */
382 DynamicSparsityPattern(const size_type n);
383
384 /**
385 * Copy operator. For this the same holds as for the copy constructor: it is
386 * declared, defined and fine to be called, but the latter only for empty
387 * objects.
388 */
389 DynamicSparsityPattern &
390 operator=(const DynamicSparsityPattern &);
391
392 /**
393 * Reallocate memory and set up data structures for a new sparsity pattern
394 * with @p m rows and @p n columns. The @p rowset restricts the storage to
395 * elements in rows of this set. Adding elements outside of this set has no
396 * effect. The default argument keeps all entries.
397 */
398 void
399 reinit(const size_type m,
400 const size_type n,
401 const IndexSet &rowset = IndexSet());
402
403 /**
404 * Since this object is kept compressed at all times anyway, this function
405 * does nothing, but is declared to make the interface of this class as much
406 * alike as that of the SparsityPattern class.
407 */
408 void
409 compress();
410
411 /**
412 * Return whether the object is empty. It is empty if no memory is
413 * allocated, which is the same as that both dimensions are zero.
414 */
415 bool
416 empty() const;
417
418 /**
419 * Return the maximum number of entries per row. Note that this number may
420 * change as entries are added.
421 */
422 size_type
423 max_entries_per_row() const;
424
425 /**
426 * Add a nonzero entry. If the entry already exists, this call does nothing.
427 */
428 void
429 add(const size_type i, const size_type j);
430
431 /**
432 * Add several nonzero entries to the specified row. Already existing
433 * entries are ignored.
434 */
435 template <typename ForwardIterator>
436 void
437 add_entries(const size_type row,
438 ForwardIterator begin,
439 ForwardIterator end,
440 const bool indices_are_unique_and_sorted = false);
441
442 virtual void
443 add_row_entries(const size_type &row,
444 const ArrayView<const size_type> &columns,
445 const bool indices_are_sorted = false) override;
446
447 using SparsityPatternBase::add_entries;
448
449 /**
450 * Check if a value at a certain position may be non-zero.
451 */
452 bool
453 exists(const size_type i, const size_type j) const;
454
455 /**
456 * Return a view of this sparsity pattern.
457 * That is, for all rows in @p rows extract non-empty columns.
458 * The resulting sparsity pattern will have number of rows equal
459 * `rows.n_elements()`.
460 */
461 DynamicSparsityPattern
462 get_view(const IndexSet &rows) const;
463
464 /**
465 * Make the sparsity pattern symmetric by adding the sparsity pattern of the
466 * transpose object.
467 *
468 * This function throws an exception if the sparsity pattern does not
469 * represent a square matrix.
470 */
471 void
472 symmetrize();
473
474 /**
475 * Construct and store in this object the sparsity pattern corresponding to
476 * the product of @p left and @p right sparsity pattern.
477 */
478 template <typename SparsityPatternTypeLeft, typename SparsityPatternTypeRight>
479 void
480 compute_mmult_pattern(const SparsityPatternTypeLeft &left,
481 const SparsityPatternTypeRight &right);
482
483 /**
484 * Construct and store in this object the sparsity pattern corresponding to
485 * the product of transposed @p left and non-transpose @p right sparsity pattern.
486 */
487 template <typename SparsityPatternTypeLeft, typename SparsityPatternTypeRight>
488 void
489 compute_Tmmult_pattern(const SparsityPatternTypeLeft &left,
490 const SparsityPatternTypeRight &right);
491
492 /**
493 * Print the sparsity pattern. The output consists of one line per row of
494 * the format <tt>[i,j1,j2,j3,...]</tt>. <i>i</i> is the row number and
495 * <i>jn</i> are the allocated columns in this row.
496 */
497 void
498 print(std::ostream &out) const;
499
500 /**
501 * Print the sparsity pattern in a format that @p gnuplot understands and
502 * which can be used to plot the sparsity pattern in a graphical way. The
503 * format consists of pairs <tt>i j</tt> of nonzero elements, each
504 * representing one entry, one per line of the output file. Indices are
505 * counted from zero on, as usual. Since sparsity patterns are printed in
506 * the same way as matrices are displayed, we print the negative of the
507 * column index, which means that the <tt>(0,0)</tt> element is in the top
508 * left rather than in the bottom left corner.
509 *
510 * Print the sparsity pattern in gnuplot by setting the data style to dots
511 * or points and use the @p plot command.
512 */
513 void
514 print_gnuplot(std::ostream &out) const;
515
516 /**
517 * Number of entries in a specific row. This function can only be called if
518 * the given row is a member of the index set of rows that we want to store.
519 */
520 size_type
521 row_length(const size_type row) const;
522
523 /**
524 * Clear all entries stored in a specific row.
525 */
526 void
527 clear_row(const size_type row);
528
529 /**
530 * Access to column number field. Return the column number of the @p
531 * indexth entry in @p row.
532 */
533 size_type
534 column_number(const size_type row, const size_type index) const;
535
536 /**
537 * Return index of column @p col in row @p row. If the column does not
538 * exist in this sparsity pattern, the returned value will be
539 * 'numbers::invalid_size_type'.
540 */
541 size_type
542 column_index(const size_type row, const size_type col) const;
543
544 /**
545 * @name Iterators
546 * @{
547 */
548
549 /**
550 * Iterator starting at the first entry of the matrix. The resulting
551 * iterator can be used to walk over all nonzero entries of the sparsity
552 * pattern.
553 *
554 * Note the discussion in the general documentation of this class about the
555 * order in which elements are accessed.
556 *
557 * @note If the sparsity pattern has been initialized with an IndexSet that
558 * denotes which rows to store, then iterators will simply skip over rows
559 * that are not stored. In other words, they will look like empty rows, but
560 * no exception will be generated when iterating over such rows.
561 */
562 iterator
563 begin() const;
564
565 /**
566 * Final iterator.
567 */
568 iterator
569 end() const;
570
571 /**
572 * Iterator starting at the first entry of row <tt>r</tt>.
573 *
574 * Note that if the given row is empty, i.e. does not contain any nonzero
575 * entries, then the iterator returned by this function equals
576 * <tt>end(r)</tt>. Note also that the iterator may not be dereferenceable in
577 * that case.
578 *
579 * Note also the discussion in the general documentation of this class about
580 * the order in which elements are accessed.
581 *
582 * @note If the sparsity pattern has been initialized with an IndexSet that
583 * denotes which rows to store, then iterators will simply skip over rows
584 * that are not stored. In other words, they will look like empty rows, but
585 * no exception will be generated when iterating over such rows.
586 */
587 iterator
588 begin(const size_type r) const;
589
590 /**
591 * Final iterator of row <tt>r</tt>. It points to the first element past the
592 * end of line @p r, or past the end of the entire sparsity pattern.
593 *
594 * Note that the end iterator is not necessarily dereferenceable. This is in
595 * particular the case if it is the end iterator for the last row of a
596 * matrix.
597 */
598 iterator
599 end(const size_type r) const;
600
601 /**
602 * @}
603 */
604
605 /**
606 * Compute the bandwidth of the matrix represented by this structure. The
607 * bandwidth is the maximum of $|i-j|$ for which the index pair $(i,j)$
608 * represents a nonzero entry of the matrix.
609 */
610 size_type
611 bandwidth() const;
612
613 /**
614 * Return the number of nonzero elements allocated through this sparsity
615 * pattern.
616 */
617 size_type
618 n_nonzero_elements() const;
619
620 /**
621 * Return the IndexSet that sets which rows are active on the current
622 * processor. It corresponds to the IndexSet given to this class in the
623 * constructor or in the reinit function.
624 */
625 const IndexSet &
626 row_index_set() const;
627
628 /**
629 * Return the IndexSet that contains entries for all columns in which at least
630 * one element exists in this sparsity pattern.
631 *
632 * @note In a parallel context, this only considers the locally stored rows.
633 */
634 IndexSet
635 nonempty_cols() const;
636
637 /**
638 * Return the IndexSet that contains entries for all rows in which at least
639 * one element exists in this sparsity pattern.
640 *
641 * @note In a parallel context, this only considers the locally stored rows.
642 */
643 IndexSet
644 nonempty_rows() const;
645
646 /**
647 * return whether this object stores only those entries that have been added
648 * explicitly, or if the sparsity pattern contains elements that have been
649 * added through other means (implicitly) while building it. For the current
650 * class, the result is always true.
651 *
652 * This function mainly serves the purpose of describing the current class
653 * in cases where several kinds of sparsity patterns can be passed as
654 * template arguments.
655 */
656 static bool
657 stores_only_added_elements();
658
659 /**
660 * Determine an estimate for the memory consumption (in bytes) of this
661 * object.
662 */
663 size_type
664 memory_consumption() const;
665
666 private:
667 /**
668 * A flag that stores whether any entries have been added so far.
669 */
670 bool have_entries;
671
672 /**
673 * A set that contains the valid rows.
674 */
675
676 IndexSet rowset;
677
678
679 /**
680 * Store some data for each row describing which entries of this row are
681 * nonzero. Data is stored sorted in the @p entries std::vector. The vector
682 * per row is dynamically growing upon insertion doubling its memory each
683 * time.
684 */
685 struct Line
686 {
687 public:
688 /**
689 * Storage for the column indices of this row. This array is always kept
690 * sorted.
691 */
692 std::vector<size_type> entries;
693
694 /**
695 * Add the given column number to this line.
696 */
697 void
698 add(const size_type col_num);
699
700 /**
701 * Add the columns specified by the iterator range to this line.
702 */
703 template <typename ForwardIterator>
704 void
705 add_entries(ForwardIterator begin,
706 ForwardIterator end,
707 const bool indices_are_sorted);
708
709 /**
710 * estimates memory consumption.
711 */
712 size_type
713 memory_consumption() const;
714 };
715
716
717 /**
718 * Actual data: store for each row the set of nonzero entries.
719 */
720 std::vector<Line> lines;
721
722 // make the accessor class a friend
723 friend class DynamicSparsityPatternIterators::Accessor;
724 };
725
726 /** @} */
727 /*---------------------- Inline functions -----------------------------------*/
728
729
730 namespace DynamicSparsityPatternIterators
731 {
732 inline Accessor::Accessor(const DynamicSparsityPattern *sparsity_pattern,
733 const size_type row,
734 const unsigned int index_within_row)
735 : sparsity_pattern(sparsity_pattern)
736 , current_row(row)
737 , current_entry(
738 ((sparsity_pattern->rowset.size() == 0) ?
739 sparsity_pattern->lines[current_row].entries.begin() :
740 sparsity_pattern
741 ->lines[sparsity_pattern->rowset.index_within_set(current_row)]
742 .entries.begin()) +
743 index_within_row)
744 , end_of_row(
745 (sparsity_pattern->rowset.size() == 0) ?
746 sparsity_pattern->lines[current_row].entries.end() :
747 sparsity_pattern
748 ->lines[sparsity_pattern->rowset.index_within_set(current_row)]
749 .entries.end())
750 {
751 AssertIndexRange(current_row, sparsity_pattern->n_rows());
752 Assert((sparsity_pattern->rowset.size() == 0) ||
753 sparsity_pattern->rowset.is_element(current_row),
754 ExcMessage("You can't create an iterator into a "
755 "DynamicSparsityPattern's row that is not "
756 "actually stored by that sparsity pattern "
757 "based on the IndexSet argument to it."));
758 AssertIndexRange(
759 index_within_row,
760 ((sparsity_pattern->rowset.size() == 0) ?
761 sparsity_pattern->lines[current_row].entries.size() :
762 sparsity_pattern
763 ->lines[sparsity_pattern->rowset.index_within_set(current_row)]
764 .entries.size()));
765 }
766
767
768 inline Accessor::Accessor(const DynamicSparsityPattern *sparsity_pattern)
769 : sparsity_pattern(sparsity_pattern)
770 , current_row(numbers::invalid_size_type)
771 , current_entry()
772 , end_of_row()
773 {}
774
775
776
777 inline Accessor::Accessor()
778 : sparsity_pattern(nullptr)
779 , current_row(numbers::invalid_size_type)
780 , current_entry()
781 , end_of_row()
782 {}
783
784
785 inline size_type
786 Accessor::row() const
787 {
788 Assert(sparsity_pattern != nullptr, DummyAccessor());
789 Assert(current_row < sparsity_pattern->n_rows(), ExcInternalError());
790
791 return current_row;
792 }
793
794
795 inline size_type
796 Accessor::column() const
797 {
798 Assert(sparsity_pattern != nullptr, DummyAccessor());
799 Assert(current_row < sparsity_pattern->n_rows(), ExcInternalError());
800
801 return *current_entry;
802 }
803
804
805 inline size_type
806 Accessor::index() const
807 {
808 Assert(sparsity_pattern != nullptr, DummyAccessor());
809 Assert(current_row < sparsity_pattern->n_rows(), ExcInternalError());
810
811 return (current_entry -
812 ((sparsity_pattern->rowset.size() == 0) ?
813 sparsity_pattern->lines[current_row].entries.begin() :
814 sparsity_pattern
815 ->lines[sparsity_pattern->rowset.index_within_set(current_row)]
816 .entries.begin()));
817 }
818
819
820
821 inline bool
822 Accessor::operator==(const Accessor &other) const
823 {
824 Assert(sparsity_pattern != nullptr, DummyAccessor());
825 Assert(other.sparsity_pattern != nullptr, DummyAccessor());
826 // compare the sparsity pattern the iterator points into, the
827 // current row, and the location within this row. ignore the
828 // latter if the row is past-the-end because in that case the
829 // current_entry field may not point to a deterministic location
830 return (sparsity_pattern == other.sparsity_pattern &&
831 current_row == other.current_row &&
832 ((current_row == numbers::invalid_size_type) ||
833 (current_entry == other.current_entry)));
834 }
835
836
837
838 inline bool
839 Accessor::operator<(const Accessor &other) const
840 {
841 Assert(sparsity_pattern != nullptr, DummyAccessor());
842 Assert(other.sparsity_pattern != nullptr, DummyAccessor());
843 Assert(sparsity_pattern == other.sparsity_pattern, ExcInternalError());
844
845 // if *this is past-the-end, then it is less than no one
846 if (current_row == numbers::invalid_size_type)
847 return (false);
848 // now *this should be an valid value
849 Assert(current_row < sparsity_pattern->n_rows(), ExcInternalError());
850
851 // if other is past-the-end
852 if (other.current_row == numbers::invalid_size_type)
853 return (true);
854 // now other should be an valid value
855 Assert(other.current_row < sparsity_pattern->n_rows(), ExcInternalError());
856
857 // both iterators are not one-past-the-end
858 return ((current_row < other.current_row) ||
859 ((current_row == other.current_row) &&
860 (current_entry < other.current_entry)));
861 }
862
863
864 inline void
865 Accessor::advance()
866 {
867 Assert(sparsity_pattern != nullptr, DummyAccessor());
868 Assert(current_row < sparsity_pattern->n_rows(), ExcInternalError());
869
870 // move to the next element in this row
871 ++current_entry;
872
873 // if this moves us beyond the end of the row, go to the next row
874 // if possible, or set the iterator to an invalid state if not.
875 //
876 // going to the next row is a bit complicated because we may have
877 // to skip over empty rows, and because we also have to avoid rows
878 // that aren't listed in a possibly passed IndexSet argument of
879 // the sparsity pattern. consequently, rather than trying to
880 // duplicate code here, just call the begin() function of the
881 // sparsity pattern itself
882 if (current_entry == end_of_row)
883 {
884 if (current_row + 1 < sparsity_pattern->n_rows())
885 *this = *sparsity_pattern->begin(current_row + 1);
886 else
887 *this = Accessor(sparsity_pattern); // invalid object
888 }
889 }
890
891
892
893 inline Iterator::Iterator(const DynamicSparsityPattern *sparsity_pattern,
894 const size_type row,
895 const unsigned int index_within_row)
896 : accessor(sparsity_pattern, row, index_within_row)
897 {}
898
899
900
901 inline Iterator::Iterator(const DynamicSparsityPattern *sparsity_pattern)
902 : accessor(sparsity_pattern)
903 {}
904
905
906
907 inline Iterator &
908 Iterator::operator++()
909 {
910 accessor.advance();
911 return *this;
912 }
913
914
915
916 inline Iterator
917 Iterator::operator++(int)
918 {
919 const Iterator iter = *this;
920 accessor.advance();
921 return iter;
922 }
923
924
925
926 inline const Accessor &
927 Iterator::operator*() const
928 {
929 return accessor;
930 }
931
932
933
934 inline const Accessor *
935 Iterator::operator->() const
936 {
937 return &accessor;
938 }
939
940
941 inline bool
942 Iterator::operator==(const Iterator &other) const
943 {
944 return (accessor == other.accessor);
945 }
946
947
948
949 inline bool
950 Iterator::operator!=(const Iterator &other) const
951 {
952 return !(*this == other);
953 }
954
955
956 inline bool
957 Iterator::operator<(const Iterator &other) const
958 {
959 return accessor < other.accessor;
960 }
961
962
963 inline int
964 Iterator::operator-(const Iterator &other) const
965 {
966 Assert(accessor.sparsity_pattern == other.accessor.sparsity_pattern,
967 ExcInternalError());
968 DEAL_II_NOT_IMPLEMENTED();
969
970 return 0;
971 }
972 } // namespace DynamicSparsityPatternIterators
973
974
975 inline void
976 DynamicSparsityPattern::Line::add(const size_type j)
977 {
978 // first check the last element (or if line is still empty)
979 if ((entries.empty()) || (entries.back() < j))
980 {
981 entries.push_back(j);
982 return;
983 }
984
985 // do a binary search to find the place where to insert:
986 std::vector<size_type>::iterator it =
987 Utilities::lower_bound(entries.begin(), entries.end(), j);
988
989 // If this entry is a duplicate, exit immediately
990 if (*it == j)
991 return;
992
993 // Insert at the right place in the vector. Vector grows automatically to
994 // fit elements. Always doubles its size.
995 entries.insert(it, j);
996 }
997
998
999
1000 inline void
1001 DynamicSparsityPattern::add(const size_type i, const size_type j)
1002 {
1003 AssertIndexRange(i, n_rows());
1004 AssertIndexRange(j, n_cols());
1005
1006 if (rowset.size() > 0 && !rowset.is_element(i))
1007 return;
1008
1009 have_entries = true;
1010
1011 const size_type rowindex =
1012 rowset.size() == 0 ? i : rowset.index_within_set(i);
1013 lines[rowindex].add(j);
1014 }
1015
1016
1017
1018 template <typename ForwardIterator>
1019 inline void
1020 DynamicSparsityPattern::add_entries(const size_type row,
1021 ForwardIterator begin,
1022 ForwardIterator end,
1023 const bool indices_are_sorted)
1024 {
1025 AssertIndexRange(row, rows);
1026
1027 if (rowset.size() > 0 && !rowset.is_element(row))
1028 return;
1029
1030 if (!have_entries && begin < end)
1031 have_entries = true;
1032
1033 const size_type rowindex =
1034 rowset.size() == 0 ? row : rowset.index_within_set(row);
1035 lines[rowindex].add_entries(begin, end, indices_are_sorted);
1036 }
1037
1038
1039
1040 inline types::global_dof_index
1041 DynamicSparsityPattern::row_length(const size_type row) const
1042 {
1043 AssertIndexRange(row, n_rows());
1044
1045 if (!have_entries)
1046 return 0;
1047
1048 if (rowset.size() > 0 && !rowset.is_element(row))
1049 return 0;
1050
1051 const size_type rowindex =
1052 rowset.size() == 0 ? row : rowset.index_within_set(row);
1053 return lines[rowindex].entries.size();
1054 }
1055
1056
1057
1058 inline types::global_dof_index
1059 DynamicSparsityPattern::column_number(const size_type row,
1060 const size_type index) const
1061 {
1062 AssertIndexRange(row, n_rows());
1063 Assert(rowset.size() == 0 || rowset.is_element(row), ExcInternalError());
1064
1065 const size_type local_row =
1066 rowset.size() != 0u ? rowset.index_within_set(row) : row;
1067 AssertIndexRange(index, lines[local_row].entries.size());
1068 return lines[local_row].entries[index];
1069 }
1070
1071
1072
1073 inline DynamicSparsityPattern::iterator
1074 DynamicSparsityPattern::begin() const
1075 {
1076 if (n_rows() > 0)
1077 return begin(0);
1078 else
1079 return end();
1080 }
1081
1082
1083 inline DynamicSparsityPattern::iterator
1084 DynamicSparsityPattern::end() const
1085 {
1086 return {this};
1087 }
1088
1089
1090
1091 inline DynamicSparsityPattern::iterator
1092 DynamicSparsityPattern::begin(const size_type r) const
1093 {
1094 AssertIndexRange(r, n_rows());
1095
1096 if (!have_entries)
1097 return {this};
1098
1099 if (rowset.size() > 0)
1100 {
1101 // We have an IndexSet that describes the locally owned set. For
1102 // performance reasons we need to make sure that we don't do a
1103 // linear search over 0..n_rows(). Instead, find the first entry
1104 // >= row r in the locally owned set (this is done in log
1105 // n_ranges time inside at()). From there, we move forward until
1106 // we find a non-empty row. By iterating over the IndexSet instead
1107 // of incrementing the row index, we potentially skip over entries
1108 // not in the rowset.
1109 IndexSet::ElementIterator it = rowset.at(r);
1110 if (it == rowset.end())
1111 return end(); // we don't own any row between r and the end
1112
1113 // Instead of using row_length(*it)==0 in the while loop below,
1114 // which involves an expensive index_within_set() call, we
1115 // look at the lines vector directly. This works, because we are
1116 // walking over this vector entry by entry anyways.
1117 size_type rowindex = rowset.index_within_set(*it);
1118
1119 while (it != rowset.end() && lines[rowindex].entries.empty())
1120 {
1121 ++it;
1122 ++rowindex;
1123 }
1124
1125 if (it == rowset.end())
1126 return end();
1127 else
1128 return {this, *it, 0};
1129 }
1130
1131 // Without an index set we have to do a linear search starting at
1132 // row r until we find a non-empty one. We will check the lines vector
1133 // directly instead of going through the slower row_length() function
1134 size_type row = r;
1135
1136 while (row < n_rows() && lines[row].entries.empty())
1137 {
1138 ++row;
1139 }
1140
1141 if (row == n_rows())
1142 return {this};
1143 else
1144 return {this, row, 0};
1145 }
1146
1147
1148
1149 inline DynamicSparsityPattern::iterator
1150 DynamicSparsityPattern::end(const size_type r) const
1151 {
1152 AssertIndexRange(r, n_rows());
1153
1154 const size_type row = r + 1;
1155 if (row == n_rows())
1156 return {this};
1157 else
1158 return begin(row);
1159 }
1160
1161
1162
1163 inline const IndexSet &
1164 DynamicSparsityPattern::row_index_set() const
1165 {
1166 return rowset;
1167 }
1168
1169
1170
1171 inline bool
1172 DynamicSparsityPattern::stores_only_added_elements()
1173 {
1174 return true;
1175 }
1176
1177
1178 DEAL_II_NAMESPACE_CLOSE
1179
1180 #endif