include/deal.II/lac/compressed_simple_sparsity_pattern.h

00001 //---------------------------------------------------------------------------
00002 //    @f$Id: compressed_simple_sparsity_pattern.h 25345 2012-03-31 08:37:04Z bangerth @f$
00003 //
00004 //    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2011, 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_simple_sparsity_pattern_h
00013 #define __deal2__compressed_simple_sparsity_pattern_h
00014 
00015 
00016 #include <deal.II/base/config.h>
00017 #include <deal.II/base/subscriptor.h>
00018 #include <deal.II/base/utilities.h>
00019 #include <deal.II/lac/exceptions.h>
00020 #include <deal.II/base/index_set.h>
00021 
00022 #include <vector>
00023 #include <algorithm>
00024 #include <iostream>
00025 
00026 DEAL_II_NAMESPACE_OPEN
00027 
00028 template <typename number> class SparseMatrix;
00029 
00030 
00087 class CompressedSimpleSparsityPattern : public Subscriptor
00088 {
00089   public:
00096     typedef std::vector<unsigned int>::const_iterator row_iterator;
00097 
00108     CompressedSimpleSparsityPattern ();
00109 
00126     CompressedSimpleSparsityPattern (const CompressedSimpleSparsityPattern &);
00127 
00139     CompressedSimpleSparsityPattern (const unsigned int m,
00140                                      const unsigned int n,
00141                                      const IndexSet & rowset = IndexSet());
00142 
00147     CompressedSimpleSparsityPattern (const unsigned int n);
00148 
00157     CompressedSimpleSparsityPattern & operator = (const CompressedSimpleSparsityPattern &);
00158 
00173     void reinit (const unsigned int m,
00174                  const unsigned int n,
00175                  const IndexSet & rowset = IndexSet());
00176 
00186     void compress ();
00187 
00195     bool empty () const;
00196 
00203     unsigned int max_entries_per_row () const;
00204 
00210     void add (const unsigned int i,
00211               const unsigned int j);
00212 
00219     template <typename ForwardIterator>
00220     void add_entries (const unsigned int row,
00221                       ForwardIterator    begin,
00222                       ForwardIterator    end,
00223                       const bool         indices_are_unique_and_sorted = false);
00224 
00229     bool exists (const unsigned int i,
00230                  const unsigned int j) const;
00231 
00243     void symmetrize ();
00244 
00254     void print (std::ostream &out) const;
00255 
00279     void print_gnuplot (std::ostream &out) const;
00280 
00286     unsigned int n_rows () const;
00287 
00293     unsigned int n_cols () const;
00294 
00303     unsigned int row_length (const unsigned int row) const;
00304 
00310     unsigned int column_number (const unsigned int row,
00311                                 const unsigned int index) const;
00312 
00319     row_iterator row_begin (const unsigned int row) const;
00320 
00324     row_iterator row_end (const unsigned int row) const;
00333     unsigned int bandwidth () const;
00334 
00339     unsigned int n_nonzero_elements () const;
00340 
00348     const IndexSet & row_index_set () const;
00349 
00365     static
00366     bool stores_only_added_elements ();
00367 
00373     std::size_t memory_consumption () const;
00374 
00375   private:
00380     unsigned int rows;
00381 
00386     unsigned int cols;
00387 
00392     IndexSet rowset;
00393 
00394 
00404     struct Line
00405     {
00406       public:
00412         std::vector<unsigned int> entries;
00413 
00417         Line ();
00418 
00423         void add (const unsigned int col_num);
00424 
00429         template <typename ForwardIterator>
00430         void add_entries (ForwardIterator begin,
00431                           ForwardIterator end,
00432                           const bool indices_are_sorted);
00433 
00437         std::size_t memory_consumption () const;
00438     };
00439 
00440 
00446     std::vector<Line> lines;
00447 };
00448 
00450 /*---------------------- Inline functions -----------------------------------*/
00451 
00452 
00453 inline
00454 void
00455 CompressedSimpleSparsityPattern::Line::add (const unsigned int j)
00456 {
00457                                    // first check the last element (or if line
00458                                    // is still empty)
00459   if ( (entries.size()==0) || ( entries.back() < j) )
00460     {
00461       entries.push_back(j);
00462       return;
00463     }
00464 
00465                                    // do a binary search to find the place
00466                                    // where to insert:
00467   std::vector<unsigned int>::iterator
00468     it = Utilities::lower_bound(entries.begin(),
00469                                           entries.end(),
00470                                           j);
00471 
00472                                    // If this entry is a duplicate, exit
00473                                    // immediately
00474   if (*it == j)
00475     return;
00476 
00477                                    // Insert at the right place in the
00478                                    // vector. Vector grows automatically to
00479                                    // fit elements. Always doubles its size.
00480   entries.insert(it, j);
00481 }
00482 
00483 
00484 
00485 inline
00486 unsigned int
00487 CompressedSimpleSparsityPattern::n_rows () const
00488 {
00489   return rows;
00490 }
00491 
00492 
00493 
00494 inline
00495 unsigned int
00496 CompressedSimpleSparsityPattern::n_cols () const
00497 {
00498   return cols;
00499 }
00500 
00501 
00502 
00503 inline
00504 void
00505 CompressedSimpleSparsityPattern::add (const unsigned int i,
00506                                       const unsigned int j)
00507 {
00508   Assert (i<rows, ExcIndexRange(i, 0, rows));
00509   Assert (j<cols, ExcIndexRange(j, 0, cols));
00510 
00511   if (rowset.size() > 0 && !rowset.is_element(i))
00512     return;
00513 
00514   const unsigned int rowindex =
00515     rowset.size()==0 ? i : rowset.index_within_set(i);
00516   lines[rowindex].add (j);
00517 }
00518 
00519 
00520 
00521 template <typename ForwardIterator>
00522 inline
00523 void
00524 CompressedSimpleSparsityPattern::add_entries (const unsigned int row,
00525                                               ForwardIterator begin,
00526                                               ForwardIterator end,
00527                                               const bool      indices_are_sorted)
00528 {
00529   Assert (row < rows, ExcIndexRange (row, 0, rows));
00530 
00531   if (rowset.size() > 0 && !rowset.is_element(row))
00532     return;
00533 
00534   const unsigned int rowindex =
00535     rowset.size()==0 ? row : rowset.index_within_set(row);
00536   lines[rowindex].add_entries (begin, end, indices_are_sorted);
00537 }
00538 
00539 
00540 
00541 inline
00542 CompressedSimpleSparsityPattern::Line::Line ()
00543 {}
00544 
00545 
00546 
00547 inline
00548 unsigned int
00549 CompressedSimpleSparsityPattern::row_length (const unsigned int row) const
00550 {
00551   Assert (row < n_rows(), ExcIndexRange (row, 0, n_rows()));
00552   if (rowset.size() > 0 && !rowset.is_element(row))
00553     return 0;
00554 
00555   const unsigned int rowindex =
00556     rowset.size()==0 ? row : rowset.index_within_set(row);
00557   return lines[rowindex].entries.size();
00558 }
00559 
00560 
00561 
00562 inline
00563 unsigned int
00564 CompressedSimpleSparsityPattern::column_number (const unsigned int row,
00565                                                 const unsigned int index) const
00566 {
00567   Assert (row < n_rows(), ExcIndexRange (row, 0, n_rows()));
00568   Assert( rowset.size() == 0 || rowset.is_element(row), ExcInternalError());
00569 
00570   const unsigned int local_row = rowset.size() ? rowset.index_within_set(row) : row;
00571   Assert (index < lines[local_row].entries.size(),
00572           ExcIndexRange (index, 0, lines[local_row].entries.size()));
00573   return lines[local_row].entries[index];
00574 }
00575 
00576 
00577 
00578 inline
00579 CompressedSimpleSparsityPattern::row_iterator
00580 CompressedSimpleSparsityPattern::row_begin (const unsigned int row) const
00581 {
00582   Assert (row < n_rows(), ExcIndexRange (row, 0, n_rows()));
00583   const unsigned int local_row = rowset.size() ? rowset.index_within_set(row) : row;
00584   return lines[local_row].entries.begin();
00585 }
00586 
00587 
00588 
00589 inline
00590 CompressedSimpleSparsityPattern::row_iterator
00591 CompressedSimpleSparsityPattern::row_end (const unsigned int row) const
00592 {
00593   Assert (row < n_rows(), ExcIndexRange (row, 0, n_rows()));
00594   const unsigned int local_row = rowset.size() ? rowset.index_within_set(row) : row;
00595   return lines[local_row].entries.end();
00596 }
00597 
00598 
00599 
00600 inline
00601 const IndexSet &
00602 CompressedSimpleSparsityPattern::row_index_set () const
00603 {
00604   return rowset;
00605 }
00606 
00607 
00608 
00609 inline
00610 bool
00611 CompressedSimpleSparsityPattern::stores_only_added_elements ()
00612 {
00613   return true;
00614 }
00615 
00616 
00617 DEAL_II_NAMESPACE_CLOSE
00618 
00619 #endif
00620 
 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