00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012 #ifndef __deal2__compressed_sparsity_pattern_h
00013 #define __deal2__compressed_sparsity_pattern_h
00014
00015
00016 #include <deal.II/base/config.h>
00017 #include <deal.II/base/subscriptor.h>
00018 #include <deal.II/lac/exceptions.h>
00019
00020 #include <vector>
00021 #include <algorithm>
00022
00023 DEAL_II_NAMESPACE_OPEN
00024
00025 template <typename number> class SparseMatrix;
00026
00027
00028
00029
00088 class CompressedSparsityPattern : public Subscriptor
00089 {
00090 public:
00097 typedef std::vector<unsigned int>::const_iterator row_iterator;
00098
00109 CompressedSparsityPattern ();
00110
00127 CompressedSparsityPattern (const CompressedSparsityPattern &);
00128
00134 CompressedSparsityPattern (const unsigned int m,
00135 const unsigned int n);
00136
00141 CompressedSparsityPattern (const unsigned int n);
00142
00151 CompressedSparsityPattern & operator = (const CompressedSparsityPattern &);
00152
00161 void reinit (const unsigned int m,
00162 const unsigned int n);
00163
00173 void compress ();
00174
00182 bool empty () const;
00183
00190 unsigned int max_entries_per_row () const;
00191
00197 void add (const unsigned int i,
00198 const unsigned int j);
00199
00206 template <typename ForwardIterator>
00207 void add_entries (const unsigned int row,
00208 ForwardIterator begin,
00209 ForwardIterator end,
00210 const bool indices_are_unique_and_sorted = false);
00211
00216 bool exists (const unsigned int i,
00217 const unsigned int j) const;
00218
00230 void symmetrize ();
00231
00241 void print (std::ostream &out) const;
00242
00266 void print_gnuplot (std::ostream &out) const;
00267
00273 unsigned int n_rows () const;
00274
00280 unsigned int n_cols () const;
00281
00285 unsigned int row_length (const unsigned int row) const;
00286
00292 unsigned int column_number (const unsigned int row,
00293 const unsigned int index) const;
00294
00301 row_iterator row_begin (const unsigned int row) const;
00302
00306 row_iterator row_end (const unsigned int row) const;
00307
00316 unsigned int bandwidth () const;
00317
00323 unsigned int n_nonzero_elements () const;
00324
00340 static
00341 bool stores_only_added_elements ();
00342
00343 private:
00348 unsigned int rows;
00349
00354 unsigned int cols;
00355
00413 struct Line
00414 {
00415 private:
00419 static const unsigned int cache_size = 8;
00420
00421 public:
00428 mutable std::vector<unsigned int> entries;
00429
00434 mutable unsigned int cache[cache_size];
00435
00439 mutable unsigned int cache_entries;
00440
00444 Line ();
00445
00450 void add (const unsigned int col_num);
00451
00456 template <typename ForwardIterator>
00457 void add_entries (ForwardIterator begin,
00458 ForwardIterator end,
00459 const bool indices_are_sorted);
00460
00465 void flush_cache () const;
00466 };
00467
00468
00474 std::vector<Line> lines;
00475 };
00476
00478
00479
00480
00481 inline
00482 void
00483 CompressedSparsityPattern::Line::add (const unsigned int j)
00484 {
00485
00486
00487
00488 for (unsigned int i=0; i<cache_entries; ++i)
00489 if (cache[i] == j)
00490 return;
00491
00492
00493
00494
00495 if (cache_entries == cache_size && cache_entries != 0)
00496 flush_cache ();
00497
00498 cache[cache_entries] = j;
00499 ++cache_entries;
00500 }
00501
00502
00503
00504 inline
00505 unsigned int
00506 CompressedSparsityPattern::n_rows () const
00507 {
00508 return rows;
00509 }
00510
00511
00512
00513 inline
00514 unsigned int
00515 CompressedSparsityPattern::n_cols () const
00516 {
00517 return cols;
00518 }
00519
00520
00521
00522 inline
00523 void
00524 CompressedSparsityPattern::add (const unsigned int i,
00525 const unsigned int j)
00526 {
00527 Assert (i<rows, ExcIndexRange(i, 0, rows));
00528 Assert (j<cols, ExcIndexRange(j, 0, cols));
00529
00530 lines[i].add (j);
00531 }
00532
00533
00534
00535 template <typename ForwardIterator>
00536 inline
00537 void
00538 CompressedSparsityPattern::add_entries (const unsigned int row,
00539 ForwardIterator begin,
00540 ForwardIterator end,
00541 const bool indices_are_sorted)
00542 {
00543 Assert (row < rows, ExcIndexRange (row, 0, rows));
00544
00545 lines[row].add_entries (begin, end, indices_are_sorted);
00546 }
00547
00548
00549
00550 inline
00551 CompressedSparsityPattern::Line::Line ()
00552 :
00553 cache_entries (0)
00554 {}
00555
00556
00557
00558 inline
00559 unsigned int
00560 CompressedSparsityPattern::row_length (const unsigned int row) const
00561 {
00562 Assert (row < n_rows(), ExcIndexRange (row, 0, n_rows()));
00563
00564 if (lines[row].cache_entries != 0)
00565 lines[row].flush_cache ();
00566 return lines[row].entries.size();
00567 }
00568
00569
00570
00571 inline
00572 unsigned int
00573 CompressedSparsityPattern::column_number (const unsigned int row,
00574 const unsigned int index) const
00575 {
00576 Assert (row < n_rows(), ExcIndexRange (row, 0, n_rows()));
00577 Assert (index < lines[row].entries.size(),
00578 ExcIndexRange (index, 0, lines[row].entries.size()));
00579
00580 if (lines[row].cache_entries != 0)
00581 lines[row].flush_cache ();
00582 return lines[row].entries[index];
00583 }
00584
00585
00586
00587 inline
00588 CompressedSparsityPattern::row_iterator
00589 CompressedSparsityPattern::row_begin (const unsigned int row) const
00590 {
00591 Assert (row < n_rows(), ExcIndexRange (row, 0, n_rows()));
00592
00593 if (lines[row].cache_entries != 0)
00594 lines[row].flush_cache ();
00595 return lines[row].entries.begin();
00596 }
00597
00598
00599
00600 inline
00601 CompressedSparsityPattern::row_iterator
00602 CompressedSparsityPattern::row_end (const unsigned int row) const
00603 {
00604 Assert (row < n_rows(), ExcIndexRange (row, 0, n_rows()));
00605 return lines[row].entries.end();
00606 }
00607
00608
00609
00610 inline
00611 bool
00612 CompressedSparsityPattern::stores_only_added_elements ()
00613 {
00614 return true;
00615 }
00616
00617
00618
00619
00620 DEAL_II_NAMESPACE_CLOSE
00621
00622 #endif
00623