SparseVector.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_SPARSEVECTOR_H
00026 #define EIGEN_SPARSEVECTOR_H
00027 
00028 namespace Eigen { 
00029 
00043 namespace internal {
00044 template<typename _Scalar, int _Options, typename _Index>
00045 struct traits<SparseVector<_Scalar, _Options, _Index> >
00046 {
00047   typedef _Scalar Scalar;
00048   typedef _Index Index;
00049   typedef Sparse StorageKind;
00050   typedef MatrixXpr XprKind;
00051   enum {
00052     IsColVector = (_Options & RowMajorBit) ? 0 : 1,
00053 
00054     RowsAtCompileTime = IsColVector ? Dynamic : 1,
00055     ColsAtCompileTime = IsColVector ? 1 : Dynamic,
00056     MaxRowsAtCompileTime = RowsAtCompileTime,
00057     MaxColsAtCompileTime = ColsAtCompileTime,
00058     Flags = _Options | NestByRefBit | LvalueBit | (IsColVector ? 0 : RowMajorBit),
00059     CoeffReadCost = NumTraits<Scalar>::ReadCost,
00060     SupportedAccessPatterns = InnerRandomAccessPattern
00061   };
00062 };
00063 }
00064 
00065 template<typename _Scalar, int _Options, typename _Index>
00066 class SparseVector
00067   : public SparseMatrixBase<SparseVector<_Scalar, _Options, _Index> >
00068 {
00069   public:
00070     EIGEN_SPARSE_PUBLIC_INTERFACE(SparseVector)
00071     EIGEN_SPARSE_INHERIT_ASSIGNMENT_OPERATOR(SparseVector, +=)
00072     EIGEN_SPARSE_INHERIT_ASSIGNMENT_OPERATOR(SparseVector, -=)
00073 
00074   protected:
00075   public:
00076 
00077     typedef SparseMatrixBase<SparseVector> SparseBase;
00078     enum { IsColVector = internal::traits<SparseVector>::IsColVector };
00079     
00080     enum {
00081       Options = _Options
00082     };
00083 
00084     internal::CompressedStorage<Scalar,Index> m_data;
00085     Index m_size;
00086 
00087     internal::CompressedStorage<Scalar,Index>& _data() { return m_data; }
00088     internal::CompressedStorage<Scalar,Index>& _data() const { return m_data; }
00089 
00090   public:
00091 
00092     EIGEN_STRONG_INLINE Index rows() const { return IsColVector ? m_size : 1; }
00093     EIGEN_STRONG_INLINE Index cols() const { return IsColVector ? 1 : m_size; }
00094     EIGEN_STRONG_INLINE Index innerSize() const { return m_size; }
00095     EIGEN_STRONG_INLINE Index outerSize() const { return 1; }
00096 
00097     EIGEN_STRONG_INLINE const Scalar* valuePtr() const { return &m_data.value(0); }
00098     EIGEN_STRONG_INLINE Scalar* valuePtr() { return &m_data.value(0); }
00099 
00100     EIGEN_STRONG_INLINE const Index* innerIndexPtr() const { return &m_data.index(0); }
00101     EIGEN_STRONG_INLINE Index* innerIndexPtr() { return &m_data.index(0); }
00102 
00103     inline Scalar coeff(Index row, Index col) const
00104     {
00105       eigen_assert((IsColVector ? col : row)==0);
00106       return coeff(IsColVector ? row : col);
00107     }
00108     inline Scalar coeff(Index i) const { return m_data.at(i); }
00109 
00110     inline Scalar& coeffRef(Index row, Index col)
00111     {
00112       eigen_assert((IsColVector ? col : row)==0);
00113       return coeff(IsColVector ? row : col);
00114     }
00115 
00122     inline Scalar& coeffRef(Index i)
00123     {
00124       return m_data.atWithInsertion(i);
00125     }
00126 
00127   public:
00128 
00129     class InnerIterator;
00130     class ReverseInnerIterator;
00131 
00132     inline void setZero() { m_data.clear(); }
00133 
00135     inline Index nonZeros() const  { return static_cast<Index>(m_data.size()); }
00136 
00137     inline void startVec(Index outer)
00138     {
00139       EIGEN_UNUSED_VARIABLE(outer);
00140       eigen_assert(outer==0);
00141     }
00142 
00143     inline Scalar& insertBackByOuterInner(Index outer, Index inner)
00144     {
00145       EIGEN_UNUSED_VARIABLE(outer);
00146       eigen_assert(outer==0);
00147       return insertBack(inner);
00148     }
00149     inline Scalar& insertBack(Index i)
00150     {
00151       m_data.append(0, i);
00152       return m_data.value(m_data.size()-1);
00153     }
00154 
00155     inline Scalar& insert(Index row, Index col)
00156     {
00157       Index inner = IsColVector ? row : col;
00158       Index outer = IsColVector ? col : row;
00159       eigen_assert(outer==0);
00160       return insert(inner);
00161     }
00162     Scalar& insert(Index i)
00163     {
00164       Index startId = 0;
00165       Index p = Index(m_data.size()) - 1;
00166       // TODO smart realloc
00167       m_data.resize(p+2,1);
00168 
00169       while ( (p >= startId) && (m_data.index(p) > i) )
00170       {
00171         m_data.index(p+1) = m_data.index(p);
00172         m_data.value(p+1) = m_data.value(p);
00173         --p;
00174       }
00175       m_data.index(p+1) = i;
00176       m_data.value(p+1) = 0;
00177       return m_data.value(p+1);
00178     }
00179 
00182     inline void reserve(Index reserveSize) { m_data.reserve(reserveSize); }
00183 
00184 
00185     inline void finalize() {}
00186 
00187     void prune(Scalar reference, RealScalar epsilon = NumTraits<RealScalar>::dummy_precision())
00188     {
00189       m_data.prune(reference,epsilon);
00190     }
00191 
00192     void resize(Index rows, Index cols)
00193     {
00194       eigen_assert(rows==1 || cols==1);
00195       resize(IsColVector ? rows : cols);
00196     }
00197 
00198     void resize(Index newSize)
00199     {
00200       m_size = newSize;
00201       m_data.clear();
00202     }
00203 
00204     void resizeNonZeros(Index size) { m_data.resize(size); }
00205 
00206     inline SparseVector() : m_size(0) { resize(0); }
00207 
00208     inline SparseVector(Index size) : m_size(0) { resize(size); }
00209 
00210     inline SparseVector(Index rows, Index cols) : m_size(0) { resize(rows,cols); }
00211 
00212     template<typename OtherDerived>
00213     inline SparseVector(const SparseMatrixBase<OtherDerived>& other)
00214       : m_size(0)
00215     {
00216       *this = other.derived();
00217     }
00218 
00219     inline SparseVector(const SparseVector& other)
00220       : m_size(0)
00221     {
00222       *this = other.derived();
00223     }
00224 
00225     inline void swap(SparseVector& other)
00226     {
00227       std::swap(m_size, other.m_size);
00228       m_data.swap(other.m_data);
00229     }
00230 
00231     inline SparseVector& operator=(const SparseVector& other)
00232     {
00233       if (other.isRValue())
00234       {
00235         swap(other.const_cast_derived());
00236       }
00237       else
00238       {
00239         resize(other.size());
00240         m_data = other.m_data;
00241       }
00242       return *this;
00243     }
00244 
00245     template<typename OtherDerived>
00246     inline SparseVector& operator=(const SparseMatrixBase<OtherDerived>& other)
00247     {
00248       if (int(RowsAtCompileTime)!=int(OtherDerived::RowsAtCompileTime))
00249         return assign(other.transpose());
00250       else
00251         return assign(other);
00252     }
00253 
00254     #ifndef EIGEN_PARSED_BY_DOXYGEN
00255     template<typename Lhs, typename Rhs>
00256     inline SparseVector& operator=(const SparseSparseProduct<Lhs,Rhs>& product)
00257     {
00258       return Base::operator=(product);
00259     }
00260     #endif
00261 
00262     friend std::ostream & operator << (std::ostream & s, const SparseVector& m)
00263     {
00264       for (Index i=0; i<m.nonZeros(); ++i)
00265         s << "(" << m.m_data.value(i) << "," << m.m_data.index(i) << ") ";
00266       s << std::endl;
00267       return s;
00268     }
00269 
00271     inline ~SparseVector() {}
00272 
00274     Scalar sum() const;
00275 
00276   public:
00277 
00279     EIGEN_DEPRECATED void startFill(Index reserve)
00280     {
00281       setZero();
00282       m_data.reserve(reserve);
00283     }
00284 
00286     EIGEN_DEPRECATED Scalar& fill(Index r, Index c)
00287     {
00288       eigen_assert(r==0 || c==0);
00289       return fill(IsColVector ? r : c);
00290     }
00291 
00293     EIGEN_DEPRECATED Scalar& fill(Index i)
00294     {
00295       m_data.append(0, i);
00296       return m_data.value(m_data.size()-1);
00297     }
00298 
00300     EIGEN_DEPRECATED Scalar& fillrand(Index r, Index c)
00301     {
00302       eigen_assert(r==0 || c==0);
00303       return fillrand(IsColVector ? r : c);
00304     }
00305 
00307     EIGEN_DEPRECATED Scalar& fillrand(Index i)
00308     {
00309       return insert(i);
00310     }
00311 
00313     EIGEN_DEPRECATED void endFill() {}
00314     
00315 #   ifdef EIGEN_SPARSEVECTOR_PLUGIN
00316 #     include EIGEN_SPARSEVECTOR_PLUGIN
00317 #   endif
00318 
00319 protected:
00320     template<typename OtherDerived>
00321     EIGEN_DONT_INLINE SparseVector& assign(const SparseMatrixBase<OtherDerived>& _other)
00322     {
00323       const OtherDerived& other(_other.derived());
00324       const bool needToTranspose = (Flags & RowMajorBit) != (OtherDerived::Flags & RowMajorBit);
00325       if(needToTranspose)
00326       {
00327         Index size = other.size();
00328         Index nnz = other.nonZeros();
00329         resize(size);
00330         reserve(nnz);
00331         for(Index i=0; i<size; ++i)
00332         {
00333           typename OtherDerived::InnerIterator it(other, i);
00334           if(it)
00335               insert(i) = it.value();
00336         }
00337         return *this;
00338       }
00339       else
00340       {
00341         // there is no special optimization
00342         return Base::operator=(other);
00343       }
00344     }
00345 };
00346 
00347 template<typename Scalar, int _Options, typename _Index>
00348 class SparseVector<Scalar,_Options,_Index>::InnerIterator
00349 {
00350   public:
00351     InnerIterator(const SparseVector& vec, Index outer=0)
00352       : m_data(vec.m_data), m_id(0), m_end(static_cast<Index>(m_data.size()))
00353     {
00354       EIGEN_UNUSED_VARIABLE(outer);
00355       eigen_assert(outer==0);
00356     }
00357 
00358     InnerIterator(const internal::CompressedStorage<Scalar,Index>& data)
00359       : m_data(data), m_id(0), m_end(static_cast<Index>(m_data.size()))
00360     {}
00361 
00362     inline InnerIterator& operator++() { m_id++; return *this; }
00363 
00364     inline Scalar value() const { return m_data.value(m_id); }
00365     inline Scalar& valueRef() { return const_cast<Scalar&>(m_data.value(m_id)); }
00366 
00367     inline Index index() const { return m_data.index(m_id); }
00368     inline Index row() const { return IsColVector ? index() : 0; }
00369     inline Index col() const { return IsColVector ? 0 : index(); }
00370 
00371     inline operator bool() const { return (m_id < m_end); }
00372 
00373   protected:
00374     const internal::CompressedStorage<Scalar,Index>& m_data;
00375     Index m_id;
00376     const Index m_end;
00377 };
00378 
00379 template<typename Scalar, int _Options, typename _Index>
00380 class SparseVector<Scalar,_Options,_Index>::ReverseInnerIterator
00381 {
00382   public:
00383     ReverseInnerIterator(const SparseVector& vec, Index outer=0)
00384       : m_data(vec.m_data), m_id(static_cast<Index>(m_data.size())), m_start(0)
00385     {
00386       EIGEN_UNUSED_VARIABLE(outer);
00387       eigen_assert(outer==0);
00388     }
00389 
00390     ReverseInnerIterator(const internal::CompressedStorage<Scalar,Index>& data)
00391       : m_data(data), m_id(static_cast<Index>(m_data.size())), m_start(0)
00392     {}
00393 
00394     inline ReverseInnerIterator& operator--() { m_id--; return *this; }
00395 
00396     inline Scalar value() const { return m_data.value(m_id-1); }
00397     inline Scalar& valueRef() { return const_cast<Scalar&>(m_data.value(m_id-1)); }
00398 
00399     inline Index index() const { return m_data.index(m_id-1); }
00400     inline Index row() const { return IsColVector ? index() : 0; }
00401     inline Index col() const { return IsColVector ? 0 : index(); }
00402 
00403     inline operator bool() const { return (m_id > m_start); }
00404 
00405   protected:
00406     const internal::CompressedStorage<Scalar,Index>& m_data;
00407     Index m_id;
00408     const Index m_start;
00409 };
00410 
00411 } // end namespace Eigen
00412 
00413 #endif // EIGEN_SPARSEVECTOR_H