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
13namespace 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  */
26template<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
131    inline const Derived& derived() const { return *static_cast<const Derived*>(this); }
132    inline Derived& derived() { return *static_cast<Derived*>(this); }
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() */
150    inline Index rows() const { return derived().rows(); }
151    /** \returns the number of columns. \sa rows() */
152    inline Index cols() const { return derived().cols(); }
153    /** \returns the number of coefficients, which is \a rows()*cols().
154      * \sa rows(), cols(). */
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. */
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. */
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 */
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 */
169    Index innerSize() const { return (int(Flags)&RowMajorBit) ? this->cols() : this->rows(); }
170
171    bool isRValue() const { return m_isRValue; }
172    Derived& markAsRValue() { m_isRValue = true; return derived(); }
173
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>
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>
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
363     /** \returns an expression of P H P^-1 where H is the matrix represented by \c *this */
364    SparseSymmetricPermutationProduct<Derived,Upper|Lower> twistedBy(const PermutationMatrix<Dynamic,Dynamic,Index>& perm) const
365    {
366      return SparseSymmetricPermutationProduct<Derived,Upper|Lower>(derived(), perm);
367    }
368
369    template<typename OtherDerived>
370    Derived& operator*=(const SparseMatrixBase<OtherDerived>& other);
371
372    #ifdef EIGEN2_SUPPORT
373    // deprecated
374    template<typename OtherDerived>
375    typename internal::plain_matrix_type_column_major<OtherDerived>::type
376    solveTriangular(const MatrixBase<OtherDerived>& other) const;
377
378    // deprecated
379    template<typename OtherDerived>
380    void solveTriangularInPlace(MatrixBase<OtherDerived>& other) const;
381    #endif // EIGEN2_SUPPORT
382
383    template<int Mode>
384    inline const SparseTriangularView<Derived, Mode> triangularView() const;
385
386    template<unsigned int UpLo> inline const SparseSelfAdjointView<Derived, UpLo> selfadjointView() const;
387    template<unsigned int UpLo> inline SparseSelfAdjointView<Derived, UpLo> selfadjointView();
388
389    template<typename OtherDerived> Scalar dot(const MatrixBase<OtherDerived>& other) const;
390    template<typename OtherDerived> Scalar dot(const SparseMatrixBase<OtherDerived>& other) const;
391    RealScalar squaredNorm() const;
392    RealScalar norm()  const;
393    RealScalar blueNorm() const;
394
395    Transpose<Derived> transpose() { return derived(); }
396    const Transpose<const Derived> transpose() const { return derived(); }
397    const AdjointReturnType adjoint() const { return transpose(); }
398
399    // inner-vector
400    typedef Block<Derived,IsRowMajor?1:Dynamic,IsRowMajor?Dynamic:1,true>       InnerVectorReturnType;
401    typedef Block<const Derived,IsRowMajor?1:Dynamic,IsRowMajor?Dynamic:1,true> ConstInnerVectorReturnType;
402    InnerVectorReturnType innerVector(Index outer);
403    const ConstInnerVectorReturnType innerVector(Index outer) const;
404
405    // set of inner-vectors
406    Block<Derived,Dynamic,Dynamic,true> innerVectors(Index outerStart, Index outerSize);
407    const Block<const Derived,Dynamic,Dynamic,true> innerVectors(Index outerStart, Index outerSize) const;
408
409    /** \internal use operator= */
410    template<typename DenseDerived>
411    void evalTo(MatrixBase<DenseDerived>& dst) const
412    {
413      dst.setZero();
414      for (Index j=0; j<outerSize(); ++j)
415        for (typename Derived::InnerIterator i(derived(),j); i; ++i)
416          dst.coeffRef(i.row(),i.col()) = i.value();
417    }
418
419    Matrix<Scalar,RowsAtCompileTime,ColsAtCompileTime> toDense() const
420    {
421      return derived();
422    }
423
424    template<typename OtherDerived>
425    bool isApprox(const SparseMatrixBase<OtherDerived>& other,
426                  const RealScalar& prec = NumTraits<Scalar>::dummy_precision()) const
427    { return toDense().isApprox(other.toDense(),prec); }
428
429    template<typename OtherDerived>
430    bool isApprox(const MatrixBase<OtherDerived>& other,
431                  const RealScalar& prec = NumTraits<Scalar>::dummy_precision()) const
432    { return toDense().isApprox(other,prec); }
433
434    /** \returns the matrix or vector obtained by evaluating this expression.
435      *
436      * Notice that in the case of a plain matrix or vector (not an expression) this function just returns
437      * a const reference, in order to avoid a useless copy.
438      */
439    inline const typename internal::eval<Derived>::type eval() const
440    { return typename internal::eval<Derived>::type(derived()); }
441
442    Scalar sum() const;
443
444  protected:
445
446    bool m_isRValue;
447};
448
449} // end namespace Eigen
450
451#endif // EIGEN_SPARSEMATRIXBASE_H
452