include/deal.II/lac/compressed_sparsity_pattern.h

00001 //---------------------------------------------------------------------------
00002 //    @f$Id: compressed_sparsity_pattern.h 25345 2012-03-31 08:37:04Z bangerth @f$
00003 //
00004 //    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2012 by the deal.II authors
00005 //
00006 //    This file is subject to QPL and may not be  distributed
00007 //    without copyright and license information. Please refer
00008 //    to the file deal.II/doc/license.html for the  text  and
00009 //    further information on this license.
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 //TODO[WB]: Unify implementation with the CompressedSetSparsityPattern since really all that's different is the Line structure in the two classes. We should have a templatized base class that simply gets the particular Line structure from a derived class.
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 /*---------------------- Inline functions -----------------------------------*/
00479 
00480 
00481 inline
00482 void
00483 CompressedSparsityPattern::Line::add (const unsigned int j)
00484 {
00485                                    // first check whether this entry is
00486                                    // already in the cache. if so, we can
00487                                    // safely return
00488   for (unsigned int i=0; i<cache_entries; ++i)
00489     if (cache[i] == j)
00490       return;
00491 
00492                                    // if not, see whether there is still some
00493                                    // space in the cache. if not, then flush
00494                                    // the cache first
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 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

deal.II documentation generated on Tue May 22 2012 12:06:11 by doxygen 1.7.3