Main MRPT website > C++ reference
MRPT logo

DynamicSparseMatrix.h

Go to the documentation of this file.
00001 // This file is part of Eigen, a lightweight C++ template library
00002 // for linear algebra.
00003 //
00004 // Copyright (C) 2008-2009 Gael Guennebaud <gael.guennebaud@inria.fr>
00005 //
00006 // Eigen is free software; you can redistribute it and/or
00007 // modify it under the terms of the GNU Lesser General Public
00008 // License as published by the Free Software Foundation; either
00009 // version 3 of the License, or (at your option) any later version.
00010 //
00011 // Alternatively, you can redistribute it and/or
00012 // modify it under the terms of the GNU General Public License as
00013 // published by the Free Software Foundation; either version 2 of
00014 // the License, or (at your option) any later version.
00015 //
00016 // Eigen is distributed in the hope that it will be useful, but WITHOUT ANY
00017 // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
00018 // FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License or the
00019 // GNU General Public License for more details.
00020 //
00021 // You should have received a copy of the GNU Lesser General Public
00022 // License and a copy of the GNU General Public License along with
00023 // Eigen. If not, see <http://www.gnu.org/licenses/>.
00024 
00025 #ifndef EIGEN_DYNAMIC_SPARSEMATRIX_H
00026 #define EIGEN_DYNAMIC_SPARSEMATRIX_H
00027 
00028 /** \class DynamicSparseMatrix
00029   *
00030   * \brief A sparse matrix class designed for matrix assembly purpose
00031   *
00032   * \param _Scalar the scalar type, i.e. the type of the coefficients
00033   *
00034   * Unlike SparseMatrix, this class provides a much higher degree of flexibility. In particular, it allows
00035   * random read/write accesses in log(rho*outer_size) where \c rho is the probability that a coefficient is
00036   * nonzero and outer_size is the number of columns if the matrix is column-major and the number of rows
00037   * otherwise.
00038   *
00039   * Internally, the data are stored as a std::vector of compressed vector. The performances of random writes might
00040   * decrease as the number of nonzeros per inner-vector increase. In practice, we observed very good performance
00041   * till about 100 nonzeros/vector, and the performance remains relatively good till 500 nonzeros/vectors.
00042   *
00043   * \see SparseMatrix
00044   */
00045 
00046 namespace internal {
00047 template<typename _Scalar, int _Options, typename _Index>
00048 struct traits<DynamicSparseMatrix<_Scalar, _Options, _Index> >
00049 {
00050   typedef _Scalar Scalar;
00051   typedef _Index Index;
00052   typedef Sparse StorageKind;
00053   typedef MatrixXpr XprKind;
00054   enum {
00055     RowsAtCompileTime = Dynamic,
00056     ColsAtCompileTime = Dynamic,
00057     MaxRowsAtCompileTime = Dynamic,
00058     MaxColsAtCompileTime = Dynamic,
00059     Flags = _Options | NestByRefBit | LvalueBit,
00060     CoeffReadCost = NumTraits<Scalar>::ReadCost,
00061     SupportedAccessPatterns = OuterRandomAccessPattern
00062   };
00063 };
00064 }
00065 
00066 template<typename _Scalar, int _Options, typename _Index>
00067 class DynamicSparseMatrix
00068   : public SparseMatrixBase<DynamicSparseMatrix<_Scalar, _Options, _Index> >
00069 {
00070   public:
00071     EIGEN_SPARSE_PUBLIC_INTERFACE(DynamicSparseMatrix)
00072     // FIXME: why are these operator already alvailable ???
00073     // EIGEN_SPARSE_INHERIT_ASSIGNMENT_OPERATOR(DynamicSparseMatrix, +=)
00074     // EIGEN_SPARSE_INHERIT_ASSIGNMENT_OPERATOR(DynamicSparseMatrix, -=)
00075     typedef MappedSparseMatrix<Scalar,Flags> Map;
00076     using Base::IsRowMajor;
00077     using Base::operator=;
00078     enum {
00079       Options = _Options
00080     };
00081 
00082   protected:
00083 
00084     typedef DynamicSparseMatrix<Scalar,(Flags&~RowMajorBit)|(IsRowMajor?RowMajorBit:0)> TransposedSparseMatrix;
00085 
00086     Index m_innerSize;
00087     std::vector<CompressedStorage<Scalar,Index> > m_data;
00088 
00089   public:
00090 
00091     inline Index rows() const { return IsRowMajor ? outerSize() : m_innerSize; }
00092     inline Index cols() const { return IsRowMajor ? m_innerSize : outerSize(); }
00093     inline Index innerSize() const { return m_innerSize; }
00094     inline Index outerSize() const { return static_cast<Index>(m_data.size()); }
00095     inline Index innerNonZeros(Index j) const { return m_data[j].size(); }
00096 
00097     std::vector<CompressedStorage<Scalar,Index> >& _data() { return m_data; }
00098     const std::vector<CompressedStorage<Scalar,Index> >& _data() const { return m_data; }
00099 
00100     /** \returns the coefficient value at given position \a row, \a col
00101       * This operation involes a log(rho*outer_size) binary search.
00102       */
00103     inline Scalar coeff(Index row, Index col) const
00104     {
00105       const Index outer = IsRowMajor ? row : col;
00106       const Index inner = IsRowMajor ? col : row;
00107       return m_data[outer].at(inner);
00108     }
00109 
00110     /** \returns a reference to the coefficient value at given position \a row, \a col
00111       * This operation involes a log(rho*outer_size) binary search. If the coefficient does not
00112       * exist yet, then a sorted insertion into a sequential buffer is performed.
00113       */
00114     inline Scalar& coeffRef(Index row, Index col)
00115     {
00116       const Index outer = IsRowMajor ? row : col;
00117       const Index inner = IsRowMajor ? col : row;
00118       return m_data[outer].atWithInsertion(inner);
00119     }
00120 
00121     class InnerIterator;
00122 
00123     void setZero()
00124     {
00125       for (Index j=0; j<outerSize(); ++j)
00126         m_data[j].clear();
00127     }
00128 
00129     /** \returns the number of non zero coefficients */
00130     Index nonZeros() const
00131     {
00132       Index res = 0;
00133       for (Index j=0; j<outerSize(); ++j)
00134         res += static_cast<Index>(m_data[j].size());
00135       return res;
00136     }
00137 
00138 
00139 
00140     void reserve(Index reserveSize = 1000)
00141     {
00142       if (outerSize()>0)
00143       {
00144         Index reserveSizePerVector = std::max(reserveSize/outerSize(),Index(4));
00145         for (Index j=0; j<outerSize(); ++j)
00146         {
00147           m_data[j].reserve(reserveSizePerVector);
00148         }
00149       }
00150     }
00151 
00152     /** Does nothing: provided for compatibility with SparseMatrix */
00153     inline void startVec(Index /*outer*/) {}
00154 
00155     /** \returns a reference to the non zero coefficient at position \a row, \a col assuming that:
00156       * - the nonzero does not already exist
00157       * - the new coefficient is the last one of the given inner vector.
00158       *
00159       * \sa insert, insertBackByOuterInner */
00160     inline Scalar& insertBack(Index row, Index col)
00161     {
00162       return insertBackByOuterInner(IsRowMajor?row:col, IsRowMajor?col:row);
00163     }
00164 
00165     /** \sa insertBack */
00166     inline Scalar& insertBackByOuterInner(Index outer, Index inner)
00167     {
00168       eigen_assert(outer<Index(m_data.size()) && inner<m_innerSize && "out of range");
00169       eigen_assert(((m_data[outer].size()==0) || (m_data[outer].index(m_data[outer].size()-1)<inner))
00170                 && "wrong sorted insertion");
00171       m_data[outer].append(0, inner);
00172       return m_data[outer].value(m_data[outer].size()-1);
00173     }
00174 
00175     inline Scalar& insert(Index row, Index col)
00176     {
00177       const Index outer = IsRowMajor ? row : col;
00178       const Index inner = IsRowMajor ? col : row;
00179 
00180       Index startId = 0;
00181       Index id = static_cast<Index>(m_data[outer].size()) - 1;
00182       m_data[outer].resize(id+2,1);
00183 
00184       while ( (id >= startId) && (m_data[outer].index(id) > inner) )
00185       {
00186         m_data[outer].index(id+1) = m_data[outer].index(id);
00187         m_data[outer].value(id+1) = m_data[outer].value(id);
00188         --id;
00189       }
00190       m_data[outer].index(id+1) = inner;
00191       m_data[outer].value(id+1) = 0;
00192       return m_data[outer].value(id+1);
00193     }
00194 
00195     /** Does nothing: provided for compatibility with SparseMatrix */
00196     inline void finalize() {}
00197 
00198     /** Suppress all nonzeros which are smaller than \a reference under the tolerence \a epsilon */
00199     void prune(Scalar reference, RealScalar epsilon = NumTraits<RealScalar>::dummy_precision())
00200     {
00201       for (Index j=0; j<outerSize(); ++j)
00202         m_data[j].prune(reference,epsilon);
00203     }
00204 
00205     /** Resize the matrix without preserving the data (the matrix is set to zero)
00206       */
00207     void resize(Index rows, Index cols)
00208     {
00209       const Index outerSize = IsRowMajor ? rows : cols;
00210       m_innerSize = IsRowMajor ? cols : rows;
00211       setZero();
00212       if (Index(m_data.size()) != outerSize)
00213       {
00214         m_data.resize(outerSize);
00215       }
00216     }
00217 
00218     void resizeAndKeepData(Index rows, Index cols)
00219     {
00220       const Index outerSize = IsRowMajor ? rows : cols;
00221       const Index innerSize = IsRowMajor ? cols : rows;
00222       if (m_innerSize>innerSize)
00223       {
00224         // remove all coefficients with innerCoord>=innerSize
00225         // TODO
00226         //std::cerr << "not implemented yet\n";
00227         exit(2);
00228       }
00229       if (m_data.size() != outerSize)
00230       {
00231         m_data.resize(outerSize);
00232       }
00233     }
00234 
00235     inline DynamicSparseMatrix()
00236       : m_innerSize(0), m_data(0)
00237     {
00238       eigen_assert(innerSize()==0 && outerSize()==0);
00239     }
00240 
00241     inline DynamicSparseMatrix(Index rows, Index cols)
00242       : m_innerSize(0)
00243     {
00244       resize(rows, cols);
00245     }
00246 
00247     template<typename OtherDerived>
00248     inline DynamicSparseMatrix(const SparseMatrixBase<OtherDerived>& other)
00249       : m_innerSize(0)
00250     {
00251       *this = other.derived();
00252     }
00253 
00254     inline DynamicSparseMatrix(const DynamicSparseMatrix& other)
00255       : Base(), m_innerSize(0)
00256     {
00257       *this = other.derived();
00258     }
00259 
00260     inline void swap(DynamicSparseMatrix& other)
00261     {
00262       //EIGEN_DBG_SPARSE(std::cout << "SparseMatrix:: swap\n");
00263       std::swap(m_innerSize, other.m_innerSize);
00264       //std::swap(m_outerSize, other.m_outerSize);
00265       m_data.swap(other.m_data);
00266     }
00267 
00268     inline DynamicSparseMatrix& operator=(const DynamicSparseMatrix& other)
00269     {
00270       if (other.isRValue())
00271       {
00272         swap(other.const_cast_derived());
00273       }
00274       else
00275       {
00276         resize(other.rows(), other.cols());
00277         m_data = other.m_data;
00278       }
00279       return *this;
00280     }
00281 
00282     template<typename OtherDerived>
00283     inline DynamicSparseMatrix& operator=(const SparseMatrixBase<OtherDerived>& other)
00284     {
00285       return SparseMatrixBase<DynamicSparseMatrix>::operator=(other.derived());
00286     }
00287     
00288     template<typename OtherDerived>
00289     EIGEN_STRONG_INLINE DynamicSparseMatrix& operator=(const ReturnByValue<OtherDerived>& func)
00290     {
00291       return Base::operator=(func);
00292     }
00293 
00294     /** Destructor */
00295     inline ~DynamicSparseMatrix() {}
00296 
00297   public:
00298 
00299     /** \deprecated
00300       * Set the matrix to zero and reserve the memory for \a reserveSize nonzero coefficients. */
00301     EIGEN_DEPRECATED void startFill(Index reserveSize = 1000)
00302     {
00303       setZero();
00304       reserve(reserveSize);
00305     }
00306 
00307     /** \deprecated use insert()
00308       * inserts a nonzero coefficient at given coordinates \a row, \a col and returns its reference assuming that:
00309       *  1 - the coefficient does not exist yet
00310       *  2 - this the coefficient with greater inner coordinate for the given outer coordinate.
00311       * In other words, assuming \c *this is column-major, then there must not exists any nonzero coefficient of coordinates
00312       * \c i \c x \a col such that \c i >= \a row. Otherwise the matrix is invalid.
00313       *
00314       * \see fillrand(), coeffRef()
00315       */
00316     EIGEN_DEPRECATED Scalar& fill(Index row, Index col)
00317     {
00318       const Index outer = IsRowMajor ? row : col;
00319       const Index inner = IsRowMajor ? col : row;
00320       return insertBack(outer,inner);
00321     }
00322 
00323     /** \deprecated use insert()
00324       * Like fill() but with random inner coordinates.
00325       * Compared to the generic coeffRef(), the unique limitation is that we assume
00326       * the coefficient does not exist yet.
00327       */
00328     EIGEN_DEPRECATED Scalar& fillrand(Index row, Index col)
00329     {
00330       return insert(row,col);
00331     }
00332 
00333     /** \deprecated use finalize()
00334       * Does nothing. Provided for compatibility with SparseMatrix. */
00335     EIGEN_DEPRECATED void endFill() {}
00336 };
00337 
00338 template<typename Scalar, int _Options, typename _Index>
00339 class DynamicSparseMatrix<Scalar,_Options,_Index>::InnerIterator : public SparseVector<Scalar,_Options>::InnerIterator
00340 {
00341     typedef typename SparseVector<Scalar,_Options>::InnerIterator Base;
00342   public:
00343     InnerIterator(const DynamicSparseMatrix& mat, Index outer)
00344       : Base(mat.m_data[outer]), m_outer(outer)
00345     {}
00346 
00347     inline Index row() const { return IsRowMajor ? m_outer : Base::index(); }
00348     inline Index col() const { return IsRowMajor ? Base::index() : m_outer; }
00349 
00350   protected:
00351     const Index m_outer;
00352 };
00353 
00354 #endif // EIGEN_DYNAMIC_SPARSEMATRIX_H



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