1 // This file is part of Eigen, a lightweight C++ template library
2 // for linear algebra.
3 //
4 // Copyright (C) 2008-2011 Gael Guennebaud <gael.guennebaud@inria.fr>
5 //
6 // This Source Code Form is subject to the terms of the Mozilla
7 // Public License v. 2.0. If a copy of the MPL was not distributed
8 // with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
9 
10 #ifndef EIGEN_SPARSEMATRIXBASE_H
11 #define EIGEN_SPARSEMATRIXBASE_H
12 
13 namespace Eigen {
14 
15 /** \ingroup SparseCore_Module
16   *
17   * \class SparseMatrixBase
18   *
19   * \brief Base class of any sparse matrices or sparse expressions
20   *
21   * \tparam Derived
22   *
23   * This class can be extended with the help of the plugin mechanism described on the page
24   * \ref TopicCustomizingEigen by defining the preprocessor symbol \c EIGEN_SPARSEMATRIXBASE_PLUGIN.
25   */
26 template<typename Derived> class SparseMatrixBase : public EigenBase<Derived>
27 {
28   public:
29 
30     typedef typename internal::traits<Derived>::Scalar Scalar;
31     typedef typename internal::packet_traits<Scalar>::type PacketScalar;
32     typedef typename internal::traits<Derived>::StorageKind StorageKind;
33     typedef typename internal::traits<Derived>::Index Index;
34     typedef typename internal::add_const_on_value_type_if_arithmetic<
35                          typename internal::packet_traits<Scalar>::type
36                      >::type PacketReturnType;
37 
38     typedef SparseMatrixBase StorageBaseType;
39     typedef EigenBase<Derived> Base;
40 
41     template<typename OtherDerived>
42     Derived& operator=(const EigenBase<OtherDerived> &other)
43     {
44       other.derived().evalTo(derived());
45       return derived();
46     }
47 
48     enum {
49 
50       RowsAtCompileTime = internal::traits<Derived>::RowsAtCompileTime,
51         /**< The number of rows at compile-time. This is just a copy of the value provided
52           * by the \a Derived type. If a value is not known at compile-time,
53           * it is set to the \a Dynamic constant.
54           * \sa MatrixBase::rows(), MatrixBase::cols(), ColsAtCompileTime, SizeAtCompileTime */
55 
56       ColsAtCompileTime = internal::traits<Derived>::ColsAtCompileTime,
57         /**< The number of columns at compile-time. This is just a copy of the value provided
58           * by the \a Derived type. If a value is not known at compile-time,
59           * it is set to the \a Dynamic constant.
60           * \sa MatrixBase::rows(), MatrixBase::cols(), RowsAtCompileTime, SizeAtCompileTime */
61 
62 
63       SizeAtCompileTime = (internal::size_at_compile_time<internal::traits<Derived>::RowsAtCompileTime,
64                                                    internal::traits<Derived>::ColsAtCompileTime>::ret),
65         /**< This is equal to the number of coefficients, i.e. the number of
66           * rows times the number of columns, or to \a Dynamic if this is not
67           * known at compile-time. \sa RowsAtCompileTime, ColsAtCompileTime */
68 
69       MaxRowsAtCompileTime = RowsAtCompileTime,
70       MaxColsAtCompileTime = ColsAtCompileTime,
71 
72       MaxSizeAtCompileTime = (internal::size_at_compile_time<MaxRowsAtCompileTime,
73                                                       MaxColsAtCompileTime>::ret),
74 
75       IsVectorAtCompileTime = RowsAtCompileTime == 1 || ColsAtCompileTime == 1,
76         /**< This is set to true if either the number of rows or the number of
77           * columns is known at compile-time to be equal to 1. Indeed, in that case,
78           * we are dealing with a column-vector (if there is only one column) or with
79           * a row-vector (if there is only one row). */
80 
81       Flags = internal::traits<Derived>::Flags,
82         /**< This stores expression \ref flags flags which may or may not be inherited by new expressions
83           * constructed from this one. See the \ref flags "list of flags".
84           */
85 
86       CoeffReadCost = internal::traits<Derived>::CoeffReadCost,
87         /**< This is a rough measure of how expensive it is to read one coefficient from
88           * this expression.
89           */
90 
91       IsRowMajor = Flags&RowMajorBit ? 1 : 0,
92 
93       InnerSizeAtCompileTime = int(IsVectorAtCompileTime) ? int(SizeAtCompileTime)
94                              : int(IsRowMajor) ? int(ColsAtCompileTime) : int(RowsAtCompileTime),
95 
96       #ifndef EIGEN_PARSED_BY_DOXYGEN
97       _HasDirectAccess = (int(Flags)&DirectAccessBit) ? 1 : 0 // workaround sunCC
98       #endif
99     };
100 
101     /** \internal the return type of MatrixBase::adjoint() */
102     typedef typename internal::conditional<NumTraits<Scalar>::IsComplex,
103                         CwiseUnaryOp<internal::scalar_conjugate_op<Scalar>, Eigen::Transpose<const Derived> >,
104                         Transpose<const Derived>
105                      >::type AdjointReturnType;
106 
107 
108     typedef SparseMatrix<Scalar, Flags&RowMajorBit ? RowMajor : ColMajor, Index> PlainObject;
109 
110 
111 #ifndef EIGEN_PARSED_BY_DOXYGEN
112     /** This is the "real scalar" type; if the \a Scalar type is already real numbers
113       * (e.g. int, float or double) then \a RealScalar is just the same as \a Scalar. If
114       * \a Scalar is \a std::complex<T> then RealScalar is \a T.
115       *
116       * \sa class NumTraits
117       */
118     typedef typename NumTraits<Scalar>::Real RealScalar;
119 
120     /** \internal the return type of coeff()
121       */
122     typedef typename internal::conditional<_HasDirectAccess, const Scalar&, Scalar>::type CoeffReturnType;
123 
124     /** \internal Represents a matrix with all coefficients equal to one another*/
125     typedef CwiseNullaryOp<internal::scalar_constant_op<Scalar>,Matrix<Scalar,Dynamic,Dynamic> > ConstantReturnType;
126 
127     /** type of the equivalent square matrix */
128     typedef Matrix<Scalar,EIGEN_SIZE_MAX(RowsAtCompileTime,ColsAtCompileTime),
129                           EIGEN_SIZE_MAX(RowsAtCompileTime,ColsAtCompileTime)> SquareMatrixType;
130 
derived()131     inline const Derived& derived() const { return *static_cast<const Derived*>(this); }
derived()132     inline Derived& derived() { return *static_cast<Derived*>(this); }
const_cast_derived()133     inline Derived& const_cast_derived() const
134     { return *static_cast<Derived*>(const_cast<SparseMatrixBase*>(this)); }
135 #endif // not EIGEN_PARSED_BY_DOXYGEN
136 
137 #define EIGEN_CURRENT_STORAGE_BASE_CLASS Eigen::SparseMatrixBase
138 #   include "../plugins/CommonCwiseUnaryOps.h"
139 #   include "../plugins/CommonCwiseBinaryOps.h"
140 #   include "../plugins/MatrixCwiseUnaryOps.h"
141 #   include "../plugins/MatrixCwiseBinaryOps.h"
142 #   include "../plugins/BlockMethods.h"
143 #   ifdef EIGEN_SPARSEMATRIXBASE_PLUGIN
144 #     include EIGEN_SPARSEMATRIXBASE_PLUGIN
145 #   endif
146 #   undef EIGEN_CURRENT_STORAGE_BASE_CLASS
147 #undef EIGEN_CURRENT_STORAGE_BASE_CLASS
148 
149     /** \returns the number of rows. \sa cols() */
rows()150     inline Index rows() const { return derived().rows(); }
151     /** \returns the number of columns. \sa rows() */
cols()152     inline Index cols() const { return derived().cols(); }
153     /** \returns the number of coefficients, which is \a rows()*cols().
154       * \sa rows(), cols(). */
size()155     inline Index size() const { return rows() * cols(); }
156     /** \returns the number of nonzero coefficients which is in practice the number
157       * of stored coefficients. */
nonZeros()158     inline Index nonZeros() const { return derived().nonZeros(); }
159     /** \returns true if either the number of rows or the number of columns is equal to 1.
160       * In other words, this function returns
161       * \code rows()==1 || cols()==1 \endcode
162       * \sa rows(), cols(), IsVectorAtCompileTime. */
isVector()163     inline bool isVector() const { return rows()==1 || cols()==1; }
164     /** \returns the size of the storage major dimension,
165       * i.e., the number of columns for a columns major matrix, and the number of rows otherwise */
outerSize()166     Index outerSize() const { return (int(Flags)&RowMajorBit) ? this->rows() : this->cols(); }
167     /** \returns the size of the inner dimension according to the storage order,
168       * i.e., the number of rows for a columns major matrix, and the number of cols otherwise */
innerSize()169     Index innerSize() const { return (int(Flags)&RowMajorBit) ? this->cols() : this->rows(); }
170 
isRValue()171     bool isRValue() const { return m_isRValue; }
markAsRValue()172     Derived& markAsRValue() { m_isRValue = true; return derived(); }
173 
SparseMatrixBase()174     SparseMatrixBase() : m_isRValue(false) { /* TODO check flags */ }
175 
176 
177     template<typename OtherDerived>
178     Derived& operator=(const ReturnByValue<OtherDerived>& other)
179     {
180       other.evalTo(derived());
181       return derived();
182     }
183 
184 
185     template<typename OtherDerived>
186     inline Derived& operator=(const SparseMatrixBase<OtherDerived>& other)
187     {
188       return assign(other.derived());
189     }
190 
191     inline Derived& operator=(const Derived& other)
192     {
193 //       if (other.isRValue())
194 //         derived().swap(other.const_cast_derived());
195 //       else
196       return assign(other.derived());
197     }
198 
199   protected:
200 
201     template<typename OtherDerived>
assign(const OtherDerived & other)202     inline Derived& assign(const OtherDerived& other)
203     {
204       const bool transpose = (Flags & RowMajorBit) != (OtherDerived::Flags & RowMajorBit);
205       const Index outerSize = (int(OtherDerived::Flags) & RowMajorBit) ? other.rows() : other.cols();
206       if ((!transpose) && other.isRValue())
207       {
208         // eval without temporary
209         derived().resize(other.rows(), other.cols());
210         derived().setZero();
211         derived().reserve((std::max)(this->rows(),this->cols())*2);
212         for (Index j=0; j<outerSize; ++j)
213         {
214           derived().startVec(j);
215           for (typename OtherDerived::InnerIterator it(other, j); it; ++it)
216           {
217             Scalar v = it.value();
218             derived().insertBackByOuterInner(j,it.index()) = v;
219           }
220         }
221         derived().finalize();
222       }
223       else
224       {
225         assignGeneric(other);
226       }
227       return derived();
228     }
229 
230     template<typename OtherDerived>
assignGeneric(const OtherDerived & other)231     inline void assignGeneric(const OtherDerived& other)
232     {
233       //const bool transpose = (Flags & RowMajorBit) != (OtherDerived::Flags & RowMajorBit);
234       eigen_assert(( ((internal::traits<Derived>::SupportedAccessPatterns&OuterRandomAccessPattern)==OuterRandomAccessPattern) ||
235                   (!((Flags & RowMajorBit) != (OtherDerived::Flags & RowMajorBit)))) &&
236                   "the transpose operation is supposed to be handled in SparseMatrix::operator=");
237 
238       enum { Flip = (Flags & RowMajorBit) != (OtherDerived::Flags & RowMajorBit) };
239 
240       const Index outerSize = other.outerSize();
241       //typedef typename internal::conditional<transpose, LinkedVectorMatrix<Scalar,Flags&RowMajorBit>, Derived>::type TempType;
242       // thanks to shallow copies, we always eval to a tempary
243       Derived temp(other.rows(), other.cols());
244 
245       temp.reserve((std::max)(this->rows(),this->cols())*2);
246       for (Index j=0; j<outerSize; ++j)
247       {
248         temp.startVec(j);
249         for (typename OtherDerived::InnerIterator it(other.derived(), j); it; ++it)
250         {
251           Scalar v = it.value();
252           temp.insertBackByOuterInner(Flip?it.index():j,Flip?j:it.index()) = v;
253         }
254       }
255       temp.finalize();
256 
257       derived() = temp.markAsRValue();
258     }
259 
260   public:
261 
262     template<typename Lhs, typename Rhs>
263     inline Derived& operator=(const SparseSparseProduct<Lhs,Rhs>& product);
264 
265     friend std::ostream & operator << (std::ostream & s, const SparseMatrixBase& m)
266     {
267       typedef typename Derived::Nested Nested;
268       typedef typename internal::remove_all<Nested>::type NestedCleaned;
269 
270       if (Flags&RowMajorBit)
271       {
272         const Nested nm(m.derived());
273         for (Index row=0; row<nm.outerSize(); ++row)
274         {
275           Index col = 0;
276           for (typename NestedCleaned::InnerIterator it(nm.derived(), row); it; ++it)
277           {
278             for ( ; col<it.index(); ++col)
279               s << "0 ";
280             s << it.value() << " ";
281             ++col;
282           }
283           for ( ; col<m.cols(); ++col)
284             s << "0 ";
285           s << std::endl;
286         }
287       }
288       else
289       {
290         const Nested nm(m.derived());
291         if (m.cols() == 1) {
292           Index row = 0;
293           for (typename NestedCleaned::InnerIterator it(nm.derived(), 0); it; ++it)
294           {
295             for ( ; row<it.index(); ++row)
296               s << "0" << std::endl;
297             s << it.value() << std::endl;
298             ++row;
299           }
300           for ( ; row<m.rows(); ++row)
301             s << "0" << std::endl;
302         }
303         else
304         {
305           SparseMatrix<Scalar, RowMajorBit, Index> trans = m;
306           s << static_cast<const SparseMatrixBase<SparseMatrix<Scalar, RowMajorBit, Index> >&>(trans);
307         }
308       }
309       return s;
310     }
311 
312     template<typename OtherDerived>
313     Derived& operator+=(const SparseMatrixBase<OtherDerived>& other);
314     template<typename OtherDerived>
315     Derived& operator-=(const SparseMatrixBase<OtherDerived>& other);
316 
317     Derived& operator*=(const Scalar& other);
318     Derived& operator/=(const Scalar& other);
319 
320     #define EIGEN_SPARSE_CWISE_PRODUCT_RETURN_TYPE \
321       CwiseBinaryOp< \
322         internal::scalar_product_op< \
323           typename internal::scalar_product_traits< \
324             typename internal::traits<Derived>::Scalar, \
325             typename internal::traits<OtherDerived>::Scalar \
326           >::ReturnType \
327         >, \
328         const Derived, \
329         const OtherDerived \
330       >
331 
332     template<typename OtherDerived>
333     EIGEN_STRONG_INLINE const EIGEN_SPARSE_CWISE_PRODUCT_RETURN_TYPE
334     cwiseProduct(const MatrixBase<OtherDerived> &other) const;
335 
336     // sparse * sparse
337     template<typename OtherDerived>
338     const typename SparseSparseProductReturnType<Derived,OtherDerived>::Type
339     operator*(const SparseMatrixBase<OtherDerived> &other) const;
340 
341     // sparse * diagonal
342     template<typename OtherDerived>
343     const SparseDiagonalProduct<Derived,OtherDerived>
344     operator*(const DiagonalBase<OtherDerived> &other) const;
345 
346     // diagonal * sparse
347     template<typename OtherDerived> friend
348     const SparseDiagonalProduct<OtherDerived,Derived>
349     operator*(const DiagonalBase<OtherDerived> &lhs, const SparseMatrixBase& rhs)
350     { return SparseDiagonalProduct<OtherDerived,Derived>(lhs.derived(), rhs.derived()); }
351 
352     /** dense * sparse (return a dense object unless it is an outer product) */
353     template<typename OtherDerived> friend
354     const typename DenseSparseProductReturnType<OtherDerived,Derived>::Type
355     operator*(const MatrixBase<OtherDerived>& lhs, const Derived& rhs)
356     { return typename DenseSparseProductReturnType<OtherDerived,Derived>::Type(lhs.derived(),rhs); }
357 
358     /** sparse * dense (returns a dense object unless it is an outer product) */
359     template<typename OtherDerived>
360     const typename SparseDenseProductReturnType<Derived,OtherDerived>::Type
361     operator*(const MatrixBase<OtherDerived> &other) const
362     { return typename SparseDenseProductReturnType<Derived,OtherDerived>::Type(derived(), other.derived()); }
363 
364      /** \returns an expression of P H P^-1 where H is the matrix represented by \c *this */
twistedBy(const PermutationMatrix<Dynamic,Dynamic,Index> & perm)365     SparseSymmetricPermutationProduct<Derived,Upper|Lower> twistedBy(const PermutationMatrix<Dynamic,Dynamic,Index>& perm) const
366     {
367       return SparseSymmetricPermutationProduct<Derived,Upper|Lower>(derived(), perm);
368     }
369 
370     template<typename OtherDerived>
371     Derived& operator*=(const SparseMatrixBase<OtherDerived>& other);
372 
373     #ifdef EIGEN2_SUPPORT
374     // deprecated
375     template<typename OtherDerived>
376     typename internal::plain_matrix_type_column_major<OtherDerived>::type
377     solveTriangular(const MatrixBase<OtherDerived>& other) const;
378 
379     // deprecated
380     template<typename OtherDerived>
381     void solveTriangularInPlace(MatrixBase<OtherDerived>& other) const;
382     #endif // EIGEN2_SUPPORT
383 
384     template<int Mode>
385     inline const SparseTriangularView<Derived, Mode> triangularView() const;
386 
387     template<unsigned int UpLo> inline const SparseSelfAdjointView<Derived, UpLo> selfadjointView() const;
388     template<unsigned int UpLo> inline SparseSelfAdjointView<Derived, UpLo> selfadjointView();
389 
390     template<typename OtherDerived> Scalar dot(const MatrixBase<OtherDerived>& other) const;
391     template<typename OtherDerived> Scalar dot(const SparseMatrixBase<OtherDerived>& other) const;
392     RealScalar squaredNorm() const;
393     RealScalar norm()  const;
394     RealScalar blueNorm() const;
395 
transpose()396     Transpose<Derived> transpose() { return derived(); }
transpose()397     const Transpose<const Derived> transpose() const { return derived(); }
adjoint()398     const AdjointReturnType adjoint() const { return transpose(); }
399 
400     // inner-vector
401     typedef Block<Derived,IsRowMajor?1:Dynamic,IsRowMajor?Dynamic:1,true>       InnerVectorReturnType;
402     typedef Block<const Derived,IsRowMajor?1:Dynamic,IsRowMajor?Dynamic:1,true> ConstInnerVectorReturnType;
403     InnerVectorReturnType innerVector(Index outer);
404     const ConstInnerVectorReturnType innerVector(Index outer) const;
405 
406     // set of inner-vectors
407     typedef Block<Derived,Dynamic,Dynamic,true> InnerVectorsReturnType;
408     typedef Block<const Derived,Dynamic,Dynamic,true> ConstInnerVectorsReturnType;
409     InnerVectorsReturnType innerVectors(Index outerStart, Index outerSize);
410     const ConstInnerVectorsReturnType innerVectors(Index outerStart, Index outerSize) const;
411 
412     /** \internal use operator= */
413     template<typename DenseDerived>
evalTo(MatrixBase<DenseDerived> & dst)414     void evalTo(MatrixBase<DenseDerived>& dst) const
415     {
416       dst.setZero();
417       for (Index j=0; j<outerSize(); ++j)
418         for (typename Derived::InnerIterator i(derived(),j); i; ++i)
419           dst.coeffRef(i.row(),i.col()) = i.value();
420     }
421 
toDense()422     Matrix<Scalar,RowsAtCompileTime,ColsAtCompileTime> toDense() const
423     {
424       return derived();
425     }
426 
427     template<typename OtherDerived>
428     bool isApprox(const SparseMatrixBase<OtherDerived>& other,
429                   const RealScalar& prec = NumTraits<Scalar>::dummy_precision()) const
430     { return toDense().isApprox(other.toDense(),prec); }
431 
432     template<typename OtherDerived>
433     bool isApprox(const MatrixBase<OtherDerived>& other,
434                   const RealScalar& prec = NumTraits<Scalar>::dummy_precision()) const
435     { return toDense().isApprox(other,prec); }
436 
437     /** \returns the matrix or vector obtained by evaluating this expression.
438       *
439       * Notice that in the case of a plain matrix or vector (not an expression) this function just returns
440       * a const reference, in order to avoid a useless copy.
441       */
eval()442     inline const typename internal::eval<Derived>::type eval() const
443     { return typename internal::eval<Derived>::type(derived()); }
444 
445     Scalar sum() const;
446 
447   protected:
448 
449     bool m_isRValue;
450 };
451 
452 } // end namespace Eigen
453 
454 #endif // EIGEN_SPARSEMATRIXBASE_H
455