From a9335b494c491cdab51b81619bdd0e11478522fb Mon Sep 17 00:00:00 2001 From: wolf Date: Thu, 10 May 2001 14:00:16 +0000 Subject: [PATCH] Implement a function copy_from. git-svn-id: https://svn.dealii.org/trunk@4587 0785d39b-7218-0410-832d-ea1e28bc413d --- deal.II/lac/include/lac/sparsity_pattern.h | 301 ++++++++++++++++++++- 1 file changed, 290 insertions(+), 11 deletions(-) diff --git a/deal.II/lac/include/lac/sparsity_pattern.h b/deal.II/lac/include/lac/sparsity_pattern.h index 898dbe6fee..c684071ad1 100644 --- a/deal.II/lac/include/lac/sparsity_pattern.h +++ b/deal.II/lac/include/lac/sparsity_pattern.h @@ -20,6 +20,7 @@ template class SparseMatrix; #include +#include /** @@ -207,14 +208,6 @@ class SparsityPattern : public Subscriptor SparsityPattern (const unsigned int m, const std::vector &row_lengths); - /** - * Copy operator. For this the same holds - * as for the copy constructor: it is - * declared, defined and fine to be called, - * but the latter only for empty objects. - */ - SparsityPattern & operator = (const SparsityPattern &); - /** * Make a copy with extra off-diagonals. * @@ -249,14 +242,22 @@ class SparsityPattern : public Subscriptor * structure is not compressed * after this function finishes. */ - SparsityPattern (const SparsityPattern& original, - const unsigned int max_per_row, - const unsigned int extra_off_diagonals); + SparsityPattern (const SparsityPattern &original, + const unsigned int max_per_row, + const unsigned int extra_off_diagonals); /** * Destructor. */ ~SparsityPattern (); + + /** + * Copy operator. For this the same holds + * as for the copy constructor: it is + * declared, defined and fine to be called, + * but the latter only for empty objects. + */ + SparsityPattern & operator = (const SparsityPattern &); /** * Reallocate memory and set up data @@ -315,6 +316,151 @@ class SparsityPattern : public Subscriptor */ void compress (); + /** + * This function can be used as a + * replacement for @ref{reinit}, + * subsequent calls to @ref{add} + * and a final call to + * @ref{close} if you know + * exactly in advance the entries + * that will form the matrix + * sparsity pattern. + * + * The first two parameters + * determine the size of the + * matrix. For the two last ones, + * note that a sparse matrix can + * be described by a sequence of + * rows, each of which is + * represented by a sequence of + * pairs of column indices and + * values. In the present + * context, the @ref{begin} and + * @ref{end} parameters designate + * iterators (of forward iterator + * type) into a container, one + * representing one row. The + * distance between @ref{begin} + * and @ref{end} should therefore + * be equal to + * @ref{n_rows}. These iterators + * may be iterators of + * @p{std::vector}, + * @p{std::list}, pointers into a + * C-style array, or any other + * iterator satisfying the + * requirements of a forward + * iterator. The objects pointed + * to by these iterators + * (i.e. what we get after + * applying @p{operator*} or + * @p{operator->} to one of these + * iterators) must be a container + * itself that provides functions + * @p{begin} and @p{end} + * designating a range of + * iterators that describe the + * contents of one + * line. Dereferencing these + * inner iterators must either + * yield a pair of an unsigned + * integer as column index and a + * value of arbitrary type (such + * a type would be used if we + * wanted to describe a sparse + * matrix with one such object), + * or simply an unsigned integer + * (of we only wanted to describe + * a sparsity pattern). The + * function is able to determine + * itself whether an unsigned + * integer or a pair is what we + * get after dereferencing the + * inner iterators, through some + * template magic. + * + * While the order of the outer + * iterators denotes the + * different rows of the matrix, + * the order of the inner + * iterator denoting the columns + * does not matter, as they are + * sorted internal to this + * function anyway. + * + * Since that all sounds very + * complicated, consider the + * following example code, which + * may be used to fill a sparsity + * pattern: + * @begin{verbatim} + * std::vector > column_indices (n_rows); + * for (unsigned int row=0; row > entries (n_rows); + * for (unsigned int row=0; row} + * could be replaced by + * @p{std::vector >}, + * or a list or set of such + * pairs, as they all return + * iterators that point to such + * pairs. + */ + template + void copy_from (const unsigned int n_rows, + const unsigned int n_cols, + const ForwardIterator begin, + const ForwardIterator end); + /** * Return whether the object is empty. It * is empty if no memory is allocated, @@ -563,6 +709,13 @@ class SparsityPattern : public Subscriptor * Exception */ DeclException0 (ExcNotSquare); + /** + * Exception + */ + DeclException2 (ExcIteratorRange, + int, int, + << "The iterators denote a range of " << arg1 + << " elements, but the given number of rows was " << arg2); private: /** @@ -711,6 +864,42 @@ class SparsityPattern : public Subscriptor optimized_lower_bound (const unsigned int *first, const unsigned int *last, const unsigned int &val); + + /** + * Helper function to get the + * column index from a + * dereferenced iterator in the + * @ref{copy_from} function, if + * the inner iterator type points + * to plain unsigned integers. + */ + static + unsigned int + get_column_index_from_iterator (const unsigned int i); + + /** + * Helper function to get the + * column index from a + * dereferenced iterator in the + * @ref{copy_from} function, if + * the inner iterator type points + * to pairs of unsigned integers + * and some other value. + */ + template + unsigned int + get_column_index_from_iterator (const std::pair &i); + + /** + * Likewise, but sometimes needed + * for certain types of + * containers that make the first + * element of the pair constant + * (such as @p{std::map}). + */ + template + unsigned int + get_column_index_from_iterator (const std::pair &i); /** * Make all sparse matrices @@ -887,4 +1076,94 @@ SparsityPattern::n_nonzero_elements () const }; + +inline +unsigned int +SparsityPattern::get_column_index_from_iterator (const unsigned int i) +{ + return i; +}; + + + +template +inline +unsigned int +SparsityPattern::get_column_index_from_iterator (const std::pair &i) +{ + return i.first; +}; + + + +template +inline +unsigned int +SparsityPattern::get_column_index_from_iterator (const std::pair &i) +{ + return i.first; +}; + + + +template +void +SparsityPattern::copy_from (const unsigned int n_rows, + const unsigned int n_cols, + const ForwardIterator begin, + const ForwardIterator end) +{ + Assert (static_cast(std::distance (begin, end)) == n_rows, + ExcIteratorRange (std::distance (begin, end), n_rows)); + + // first determine row lengths for + // each row. if the matrix is + // square, then we might have to + // add an additional entry for the + // diagonal, if that is not yet + // present. as we have to call + // compress anyway later on, don't + // bother to check whether that + // diagonal entry is in a certain + // row or not + const bool is_square = (n_rows == n_cols); + std::vector row_lengths; + row_lengths.reserve(n_rows); + for (ForwardIterator i=begin; i!=end; ++i) + row_lengths.push_back (std::distance (i->begin(), i->end()) + + + (is_square ? 1 : 0)); + reinit (n_rows, n_cols, row_lengths); + + // now enter all the elements into + // the matrix. note that if the + // matrix is square, then we + // already have the diagonal + // element preallocated + // + // for use in the inner loop, we + // define a typedef to the type of + // the inner iterators + unsigned int row = 0; + typedef typename std::iterator_traits::value_type::const_iterator inner_iterator; + for (ForwardIterator i=begin; i!=end; ++i, ++row) + { + unsigned int *cols = &colnums[rowstart[row]] + (is_square ? 1 : 0); + for (inner_iterator j=i->begin(); j!=i->end(); ++j) + { + const unsigned int col = get_column_index_from_iterator(*j); + Assert (col < n_cols, ExcInvalidIndex(col,n_cols)); + + if ((col!=row) || !is_square) + *cols++ = col; + }; + }; + + // finally compress + // everything. this also sorts the + // entries within each row + compress (); +}; + + #endif -- 2.39.5