Main MRPT website > C++ reference
MRPT logo

CSparseMatrixTemplate.h

Go to the documentation of this file.
00001 /* +---------------------------------------------------------------------------+
00002    |          The Mobile Robot Programming Toolkit (MRPT) C++ library          |
00003    |                                                                           |
00004    |                   http://mrpt.sourceforge.net/                            |
00005    |                                                                           |
00006    |   Copyright (C) 2005-2011  University of Malaga                           |
00007    |                                                                           |
00008    |    This software was written by the Machine Perception and Intelligent    |
00009    |      Robotics Lab, University of Malaga (Spain).                          |
00010    |    Contact: Jose-Luis Blanco  <jlblanco@ctima.uma.es>                     |
00011    |                                                                           |
00012    |  This file is part of the MRPT project.                                   |
00013    |                                                                           |
00014    |     MRPT is free software: you can redistribute it and/or modify          |
00015    |     it under the terms of the GNU General Public License as published by  |
00016    |     the Free Software Foundation, either version 3 of the License, or     |
00017    |     (at your option) any later version.                                   |
00018    |                                                                           |
00019    |   MRPT is distributed in the hope that it will be useful,                 |
00020    |     but WITHOUT ANY WARRANTY; without even the implied warranty of        |
00021    |     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         |
00022    |     GNU General Public License for more details.                          |
00023    |                                                                           |
00024    |     You should have received a copy of the GNU General Public License     |
00025    |     along with MRPT.  If not, see <http://www.gnu.org/licenses/>.         |
00026    |                                                                           |
00027    +---------------------------------------------------------------------------+ */
00028 #ifndef CSparseMatrixTemplate_H
00029 #define CSparseMatrixTemplate_H
00030 
00031 #include <mrpt/utils/utils_defs.h>
00032 
00033 namespace mrpt  {
00034 namespace math  {
00035     using namespace std;
00036 
00037     /** A sparse matrix container (with cells of any type), with iterators.
00038       *  This class stores only those elements created by assigning them a value, for example: "M(2,3)=8;".
00039       *
00040       *  This class doesn't implement math operations since it's a generic sparse container, but it can be
00041       *   used to initialize the contents of a CSparse library-based matrix of type mrpt::math::CSparseMatrix.
00042       *
00043       *  Note that reading non-existing cell elements will return the default value (0 for numbers)
00044       *   and that cell will remain non-created in the matrix.
00045       *
00046       *  There is an additional method "exists(i,j)" to check whether a given element exists in the matrix.
00047       *
00048       *  \sa mrpt::math::CSparseMatrix, CSparseSymmetricalMatrix
00049       *  \note Methods marked as "Doesn't check bounds" mean that if an access to an element out of the matrix size is tried, an empty element will be assumed, but this will not raise any invalid memory access.
00050       */
00051         template<class T>
00052         class CSparseMatrixTemplate     {
00053                 //Public typedefs
00054         public:
00055                 /**
00056                   * Internal map type, used to store the actual matrix.
00057                   */
00058                 typedef typename std::map<std::pair<size_t,size_t>,T> SparseMatrixMap;
00059                 /**
00060                   * Const iterator to move through the matrix.
00061                   * \sa CSparseMatrixTemplate::const_reverse_iterator
00062                   */
00063                 typedef typename SparseMatrixMap::const_iterator const_iterator;
00064                 /**
00065                   * Const reverse iterator to move through the matrix.
00066                   * \sa CSparseMatrixTemplate::const_iterator
00067                   */
00068                 typedef typename SparseMatrixMap::const_reverse_iterator const_reverse_iterator;
00069         protected:
00070                 /**
00071                   * Size of the matrix.
00072                   */
00073                 size_t mRows,mColumns;
00074                 /**
00075                   * Actual matrix.
00076                   */
00077                 SparseMatrixMap objectList;
00078         public:
00079                 /**
00080                   * Basic constructor with no data. Size is set to (0,0).
00081                   */
00082                 CSparseMatrixTemplate():mRows(0),mColumns(0)    {}
00083                 /**
00084                   * Constructor with default size.
00085                   */
00086                 CSparseMatrixTemplate(size_t nR,size_t nC):mRows(nR),mColumns(nC)       {}
00087                 /**
00088                   * Element access operator. Doesn't check bounds.
00089                   */
00090                 inline T operator()(size_t r,size_t c) const    {
00091                         const_iterator it=objectList.find(make_pair(r,c));
00092                         if (it==objectList.end()) return T();
00093                         else return it->second;
00094                 }
00095 
00096                 /** Element access operator. Checks bounds.
00097                   */
00098                 inline bool exists(size_t r,size_t c) const     {
00099 #if defined(_DEBUG) || (MRPT_ALWAYS_CHECKS_DEBUG_MATRICES)
00100                         if (r>=mRows||c>=mColumns) throw std::logic_error("Out of range");
00101 #endif
00102                         return (objectList.find(make_pair(r,c)) != objectList.end());
00103                 }
00104 
00105                 /**
00106                   * Reference access operator. Checks for bounds.
00107                   */
00108                 inline T& operator()(size_t r,size_t c) {
00109 #if defined(_DEBUG) || (MRPT_ALWAYS_CHECKS_DEBUG_MATRICES)
00110                         if (r>=mRows||c>=mColumns) throw std::logic_error("Out of range");
00111 #endif
00112                         return objectList[make_pair(r,c)];
00113                 }
00114                 /**
00115                   * Returns the amount of rows in this matrix.
00116                   * \sa getColCount,getRow
00117                   */
00118                 inline size_t getRowCount() const       {
00119                         return mRows;
00120                 }
00121                 /**
00122                   * Returns the amount of columns in this matrix.
00123                   * \sa getRowCount
00124                   */
00125                 inline size_t getColCount() const       {
00126                         return mColumns;
00127                 }
00128                 /**
00129                   * Extracts a full row from the matrix.
00130                   * \sa getRowCount,getColumn,setRow
00131                   * \throw std::logic_error on out of range.
00132                   */
00133                 void getRow(size_t nRow,std::vector<T> &vec) const      {
00134 #if defined(_DEBUG) || (MRPT_ALWAYS_CHECKS_DEBUG_MATRICES)
00135                         if (nRow>=mRows) throw std::logic_error("Out of range");
00136 #endif
00137                         vec.resize(mColumns);
00138                         size_t nextIndex=0;
00139                         for (typename SparseMatrixMap::const_iterator it=objectList.begin();it!=objectList.end();++it)  {
00140                                 const pair<size_t,size_t> &index=it->first;
00141                                 if (index.first<nRow) continue;
00142                                 else if (index.first==nRow)     {
00143                                         for (size_t i=nextIndex;i<index.second;i++) vec[i]=T();
00144                                         vec[index.second]=it->second;
00145                                         nextIndex=index.second+1;
00146                                 }       else    {
00147                                         for (size_t i=nextIndex;i<mColumns;i++) vec[i]=T();
00148                                         break;
00149                                 }
00150                         }
00151                 }
00152                 /**
00153                   * Extracts a full column from the matrix.
00154                   * \sa getColCount,getRow,setColumn
00155                   * \throw std::logic_error on out of range.
00156                   */
00157                 void getColumn(size_t nCol,std::vector<T> &vec) const   {
00158 #if defined(_DEBUG) || (MRPT_ALWAYS_CHECKS_DEBUG_MATRICES)
00159                         if (nCol>=mColumns) throw std::logic_error("Out of range");
00160 #endif
00161                         vec.resize(mRows);
00162                         size_t nextIndex=0;
00163                         for (typename SparseMatrixMap::const_iterator it=objectList.begin();it!=objectList.end();++it)  {
00164                                 const pair<size_t,size_t> &index=it->first;
00165                                 if (index.second==nCol) {
00166                                         for (size_t i=nextIndex;i<index.first;i++) vec[i]=T();
00167                                         vec[index.first]=it->second;
00168                                         nextIndex=index.first+1;
00169                                 }
00170                         }
00171                         for (size_t i=nextIndex;i<mRows;i++) vec[i]=T();
00172                 }
00173                 /**
00174                   * Inserts an element into the matrix.
00175                   * \sa operator()(size_t,size_t)
00176                   */
00177                 inline void insert(size_t row,size_t column,const T& obj)       {
00178                         operator()(row,column)=obj;
00179                 }
00180 
00181                 /** Inserts submatrix at a given location */
00182                 template <class MATRIX_LIKE>
00183                 inline void insertMatrix(size_t row,size_t column,const MATRIX_LIKE& mat)
00184                 {
00185                         for (size_t nr=0;nr<mat.getRowCount();nr++)
00186                                 for (size_t nc=0;nc<mat.getColCount();nc++)
00187                                         operator()(row+nr,column+nc)=mat(nr,nc);
00188                 }
00189 
00190                 //Public interface only supports const iterators. This way, no user of this class will be able to freely modify it contents.
00191                 /**
00192                   * Returns an iterator which points to the starting point of the matrix. It's a const_iterator, so that the usar isn't able to modify the matrix content into an invalid state.
00193                   * \sa end,rbegin,rend
00194                   */
00195                 inline const_iterator begin() const     {
00196                         return objectList.begin();
00197                 }
00198                 /**
00199                   * Returns an iterator which points to the end of the matrix. It's a const_iterator, so that the usar isn't able to modify the matrix content into an invalid state.
00200                   * \sa begin,rbegin,rend
00201                   */
00202                 inline const_iterator end() const       {
00203                         return objectList.end();
00204                 }
00205                 /**
00206                   * Returns an iterator which points to the end of the matrix, and can be used to move backwards. It's a const_reverse_iterator, so that the usar isn't able to modify the matrix content into an invalid state.
00207                   * \sa begin,end,rend
00208                   */
00209                 inline const_reverse_iterator rbegin() const    {
00210                         return objectList.rbegin();
00211                 }
00212                 /**
00213                   * Returns an iterator which points to the starting point of the matrix, although it's the upper limit of the matrix since it's a reverse iterator. Also, it's a const_reverse_iterator, so that the usar isn't able to modify the matrix content into an invalid state.
00214                   * \sa begin,end,rbegin
00215                   */
00216                 inline const_reverse_iterator rend() const      {
00217                         return objectList.rend();
00218                 }
00219                 /**
00220                   * Inserts a full row into the matrix. The third argument is used to specify a null object (which won't be inserted, since the matrix is sparse).
00221                   * \sa getRow
00222                   * \throw std::logic_error on out of range or wrong sized vector.
00223                   */
00224                 void setRow(size_t nRow,const std::vector<T> &vec,const T& nullObject=T())      {
00225 #if defined(_DEBUG) || (MRPT_ALWAYS_CHECKS_DEBUG_MATRICES)
00226                         if (nRow>=mRows) throw std::logic_error("Out of range");
00227 #endif
00228                         size_t N=vec.size();
00229                         if (N!=mColumns) throw std::logic_error("Wrong-sized vector");
00230                         for (size_t i=0;i<N;i++)        {
00231                                 const T &obj=vec[i];
00232                                 pair<size_t,size_t> index=make_pair(nRow,i);
00233                                 if (obj==nullObject) objectList.erase(index);
00234                                 else objectList[index]=obj;
00235                         }
00236                 }
00237                 /**
00238                   * Inserts a full column into the matrix. The third argument is used to specify a null object (which won't be inserted, since the matrix is sparse).
00239                   * \sa getColumn
00240                   * \throw std::logic_error on out of range or wrong sized vector.
00241                   */
00242                 void setColumn(size_t nCol,const std::vector<T> &vec,const T& nullObject=T())   {
00243 #if defined(_DEBUG) || (MRPT_ALWAYS_CHECKS_DEBUG_MATRICES)
00244                         if (nCol>=mColumns) throw std::logic_error("Out of range");
00245 #endif
00246                         size_t N=vec.size();
00247                         if (N!=mRows) throw std::logic_error("Wrong-sized vector");
00248                         for (size_t i=0;i<N;i++)        {
00249                                 const T &obj=vec[i];
00250                                 pair<size_t,size_t> index=make_pair(i,nCol);
00251                                 if (obj==nullObject) objectList.erase(index);
00252                                 else objectList[index]=obj;
00253                         }
00254                 }
00255                 /**
00256                   * Changes the size of the matrix.
00257                   */
00258                 void resize(size_t nRows,size_t nCols)  {
00259                         // if (mRows<0||mColumns<0) throw std::logic_error("Invalid range"); // This case never happens!
00260                         if (mRows==nRows && mColumns==nCols) return;
00261                         mRows=nRows;
00262                         mColumns=nCols;
00263                         std::vector<pair<size_t,size_t> > toErase;
00264                         for (const_iterator it=objectList.begin();it!=objectList.end();++it)    {
00265                                 const pair<size_t,size_t> &i=it->first;
00266                                 if (i.first>=nRows||i.second>=nCols) toErase.push_back(it->first);
00267                         }
00268                         for (std::vector<pair<size_t,size_t> >::const_iterator it=toErase.begin();it!=toErase.end();++it) objectList.erase(*it);
00269                 }
00270                 /**
00271                   * Extracts a submatrix form the matrix.
00272                   * \sa operator()(size_t,size_t)
00273                   * \throw std::logic_error on invalid bounds.
00274                   */
00275                 CSparseMatrixTemplate<T> operator()(size_t firstRow,size_t lastRow,size_t firstColumn,size_t lastColumn) const  {
00276 #if defined(_DEBUG) || (MRPT_ALWAYS_CHECKS_DEBUG_MATRICES)
00277                         if (lastRow>=mRows||lastColumn>=mColumns) throw std::logic_error("Out of range");
00278                         if (firstRow>lastRow||firstColumn>lastColumn) throw std::logic_error("Invalid size");
00279 #endif
00280                         CSparseMatrixTemplate<T> res=CSparseMatrixTemplate<T>(lastRow+1-firstRow,lastColumn+1-firstColumn);
00281                         for (typename SparseMatrixMap::const_iterator it=begin();it!=end();++it)        {
00282                                 const pair<size_t,size_t> &i=it->first;
00283                                 if (i.first>=firstRow&&i.first<=lastRow&&i.second>=firstColumn&&i.second<=lastColumn) res(i.first-firstRow,i.second-firstColumn)=it->second;
00284                         }
00285                         return res;
00286                 }
00287                 /**
00288                   * Gets a vector containing all the elements of the matrix, ignoring their position.
00289                   */
00290                 void getAsVector(std::vector<T> &vec) const     {
00291                         size_t N=objectList.size();
00292                         vec.resize(0);
00293                         vec.reserve(N);
00294                         for (const_iterator it=objectList.begin();it!=objectList.end();++it) vec.push_back(it->second);
00295                 }
00296                 /**
00297                   * Gets the amount of non-null elements inside the matrix.
00298                   * \sa getNullElements,isNull,isNotNull
00299                   */
00300                 inline size_t getNonNullElements() const        {
00301                         return objectList.size();
00302                 }
00303                 /** Are there no elements set to !=0 ?
00304                   * \sa getNullElements,isNull,isNotNull
00305                   */
00306                 inline bool empty() const       { return objectList.empty(); }
00307 
00308                 /**
00309                   * Gets the amount of null elements inside the matrix.
00310                   * \sa getNonNullElements,isNull,isNotNull
00311                   */
00312                 inline size_t getNullElements() const   {
00313                         return mRows*mColumns-getNonNullElements();
00314                 }
00315                 /**
00316                   * Checks whether an element of the matrix is the default object.
00317                   * \sa getNonNullElements,getNullElements,isNotNull
00318                   * \throw std::logic_error on out of range
00319                   */
00320                 inline bool isNull(size_t nRow,size_t nCol) const       {
00321                         if (nRow>=mRows||nCol>=mColumns) throw std::logic_error("Out of range");
00322                         return objectList.count(make_pair(nRow,nCol))==0;
00323                 }
00324                 /**
00325                   * Checks whether an element of the matrix is not the default object.
00326                   * \sa getNonNullElements,getNullElements,isNull
00327                   */
00328                 inline bool isNotNull(size_t nRow,size_t nCol) const    {
00329                         if (nRow>=mRows||nCol>=mColumns) throw std::logic_error("Out of range");
00330                         return objectList.count(make_pair(nRow,nCol))>0;
00331                 }
00332                 /**
00333                   * Completely removes all elements, although maintaining the matrix's size.
00334                   */
00335                 inline void clear()     {
00336                         objectList.clear();
00337                 }
00338                 /**
00339                   * Checks each non-null elements against the basic objects, erasing unnecesary references to it.
00340                   */
00341                 void purge(T nullObject=T())    {
00342                         std::vector<std::pair<size_t,size_t> > nulls;
00343                         for (const_iterator it=begin();it!=end();++it) if (it->second==nullObject) nulls.push_back(it->first);
00344                         for (std::vector<std::pair<size_t,size_t> >::const_iterator it=nulls.begin();it!=nulls.end();++it) objectList.erase(*it);
00345                 }
00346         }; // end of sparse matrix
00347 
00348     /** A sparse matrix container for square symmetrical content around the main diagonal.
00349       *  This class saves half of the space with respect to CSparseMatrixTemplate since only those entries (c,r) such as c>=r are really stored,
00350       *   but both (c,r) and (r,c) can be retrieved or set and both redirect to the same internal cell container.
00351       *  \sa CSparseMatrixTemplate
00352       */
00353         template<class T>
00354         class CSparseSymmetricalMatrix : public CSparseMatrixTemplate<T> {
00355                 public:
00356                 CSparseSymmetricalMatrix() : CSparseMatrixTemplate<T>() { }
00357                 explicit CSparseSymmetricalMatrix(const CSparseSymmetricalMatrix &o) : CSparseMatrixTemplate<T>(o) { }
00358                 explicit CSparseSymmetricalMatrix(const CSparseMatrixTemplate<T> &o) : CSparseMatrixTemplate<T>(o) { }
00359                 virtual ~CSparseSymmetricalMatrix() { }
00360 
00361                 void resize(size_t matrixSize) {
00362                         CSparseMatrixTemplate<T>::resize(matrixSize,matrixSize);
00363                 }
00364 
00365                 inline T operator()(size_t r,size_t c) const    {
00366                         if (c<r) std::swap(r,c); // Symmetrical matrix
00367                         typename CSparseMatrixTemplate<T>::const_iterator it=CSparseMatrixTemplate<T>::objectList.find(make_pair(r,c));
00368                         if (it==CSparseMatrixTemplate<T>::objectList.end()) return T();
00369                         else return it->second;
00370                 }
00371                 inline T& operator()(size_t r,size_t c) {
00372                         if (c<r) std::swap(r,c); // Symmetrical matrix
00373                         if (r>=CSparseMatrixTemplate<T>::mRows||c>=CSparseMatrixTemplate<T>::mColumns) throw std::logic_error("Out of range");
00374                         return CSparseMatrixTemplate<T>::objectList[make_pair(r,c)];
00375                 }
00376 
00377         }; // end of CSparseSymmetricalMatrix
00378 
00379 }
00380 }
00381 #endif



Page generated by Doxygen 1.7.3 for MRPT 0.9.4 SVN:exported at Tue Jan 25 21:56:31 UTC 2011