1 // This file is part of Eigen, a lightweight C++ template library
2 // for linear algebra.
3 //
4 // Copyright (C) 2015 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_SPARSE_MAP_H
11 #define EIGEN_SPARSE_MAP_H
12 
13 namespace Eigen {
14 
15 namespace internal {
16 
17 template<typename MatScalar, int MatOptions, typename MatIndex, int Options, typename StrideType>
18 struct traits<Map<SparseMatrix<MatScalar,MatOptions,MatIndex>, Options, StrideType> >
19   : public traits<SparseMatrix<MatScalar,MatOptions,MatIndex> >
20 {
21   typedef SparseMatrix<MatScalar,MatOptions,MatIndex> PlainObjectType;
22   typedef traits<PlainObjectType> TraitsBase;
23   enum {
24     Flags = TraitsBase::Flags & (~NestByRefBit)
25   };
26 };
27 
28 template<typename MatScalar, int MatOptions, typename MatIndex, int Options, typename StrideType>
29 struct traits<Map<const SparseMatrix<MatScalar,MatOptions,MatIndex>, Options, StrideType> >
30   : public traits<SparseMatrix<MatScalar,MatOptions,MatIndex> >
31 {
32   typedef SparseMatrix<MatScalar,MatOptions,MatIndex> PlainObjectType;
33   typedef traits<PlainObjectType> TraitsBase;
34   enum {
35     Flags = TraitsBase::Flags & (~ (NestByRefBit | LvalueBit))
36   };
37 };
38 
39 } // end namespace internal
40 
41 template<typename Derived,
42          int Level = internal::accessors_level<Derived>::has_write_access ? WriteAccessors : ReadOnlyAccessors
43 > class SparseMapBase;
44 
45 /** \ingroup SparseCore_Module
46   * class SparseMapBase
47   * \brief Common base class for Map and Ref instance of sparse matrix and vector.
48   */
49 template<typename Derived>
50 class SparseMapBase<Derived,ReadOnlyAccessors>
51   : public SparseCompressedBase<Derived>
52 {
53   public:
54     typedef SparseCompressedBase<Derived> Base;
55     typedef typename Base::Scalar Scalar;
56     typedef typename Base::StorageIndex StorageIndex;
57     enum { IsRowMajor = Base::IsRowMajor };
58     using Base::operator=;
59   protected:
60 
61     typedef typename internal::conditional<
62                          bool(internal::is_lvalue<Derived>::value),
63                          Scalar *, const Scalar *>::type ScalarPointer;
64     typedef typename internal::conditional<
65                          bool(internal::is_lvalue<Derived>::value),
66                          StorageIndex *, const StorageIndex *>::type IndexPointer;
67 
68     Index   m_outerSize;
69     Index   m_innerSize;
70     Array<StorageIndex,2,1>  m_zero_nnz;
71     IndexPointer  m_outerIndex;
72     IndexPointer  m_innerIndices;
73     ScalarPointer m_values;
74     IndexPointer  m_innerNonZeros;
75 
76   public:
77 
78     /** \copydoc SparseMatrixBase::rows() */
79     inline Index rows() const { return IsRowMajor ? m_outerSize : m_innerSize; }
80     /** \copydoc SparseMatrixBase::cols() */
81     inline Index cols() const { return IsRowMajor ? m_innerSize : m_outerSize; }
82     /** \copydoc SparseMatrixBase::innerSize() */
83     inline Index innerSize() const { return m_innerSize; }
84     /** \copydoc SparseMatrixBase::outerSize() */
85     inline Index outerSize() const { return m_outerSize; }
86     /** \copydoc SparseCompressedBase::nonZeros */
87     inline Index nonZeros() const { return m_zero_nnz[1]; }
88 
89     /** \copydoc SparseCompressedBase::isCompressed */
90     bool isCompressed() const { return m_innerNonZeros==0; }
91 
92     //----------------------------------------
93     // direct access interface
94     /** \copydoc SparseMatrix::valuePtr */
95     inline const Scalar* valuePtr() const { return m_values; }
96     /** \copydoc SparseMatrix::innerIndexPtr */
97     inline const StorageIndex* innerIndexPtr() const { return m_innerIndices; }
98     /** \copydoc SparseMatrix::outerIndexPtr */
99     inline const StorageIndex* outerIndexPtr() const { return m_outerIndex; }
100     /** \copydoc SparseMatrix::innerNonZeroPtr */
101     inline const StorageIndex* innerNonZeroPtr() const { return m_innerNonZeros; }
102     //----------------------------------------
103 
104     /** \copydoc SparseMatrix::coeff */
105     inline Scalar coeff(Index row, Index col) const
106     {
107       const Index outer = IsRowMajor ? row : col;
108       const Index inner = IsRowMajor ? col : row;
109 
110       Index start = m_outerIndex[outer];
111       Index end = isCompressed() ? m_outerIndex[outer+1] : start + m_innerNonZeros[outer];
112       if (start==end)
113         return Scalar(0);
114       else if (end>0 && inner==m_innerIndices[end-1])
115         return m_values[end-1];
116       // ^^  optimization: let's first check if it is the last coefficient
117       // (very common in high level algorithms)
118 
119       const StorageIndex* r = std::lower_bound(&m_innerIndices[start],&m_innerIndices[end-1],inner);
120       const Index id = r-&m_innerIndices[0];
121       return ((*r==inner) && (id<end)) ? m_values[id] : Scalar(0);
122     }
123 
124     inline SparseMapBase(Index rows, Index cols, Index nnz, IndexPointer outerIndexPtr, IndexPointer innerIndexPtr,
125                               ScalarPointer valuePtr, IndexPointer innerNonZerosPtr = 0)
126       : m_outerSize(IsRowMajor?rows:cols), m_innerSize(IsRowMajor?cols:rows), m_zero_nnz(0,internal::convert_index<StorageIndex>(nnz)), m_outerIndex(outerIndexPtr),
127         m_innerIndices(innerIndexPtr), m_values(valuePtr), m_innerNonZeros(innerNonZerosPtr)
128     {}
129 
130     // for vectors
131     inline SparseMapBase(Index size, Index nnz, IndexPointer innerIndexPtr, ScalarPointer valuePtr)
132       : m_outerSize(1), m_innerSize(size), m_zero_nnz(0,internal::convert_index<StorageIndex>(nnz)), m_outerIndex(m_zero_nnz.data()),
133         m_innerIndices(innerIndexPtr), m_values(valuePtr), m_innerNonZeros(0)
134     {}
135 
136     /** Empty destructor */
137     inline ~SparseMapBase() {}
138 
139   protected:
140     inline SparseMapBase() {}
141 };
142 
143 /** \ingroup SparseCore_Module
144   * class SparseMapBase
145   * \brief Common base class for writable Map and Ref instance of sparse matrix and vector.
146   */
147 template<typename Derived>
148 class SparseMapBase<Derived,WriteAccessors>
149   : public SparseMapBase<Derived,ReadOnlyAccessors>
150 {
151     typedef MapBase<Derived, ReadOnlyAccessors> ReadOnlyMapBase;
152 
153   public:
154     typedef SparseMapBase<Derived, ReadOnlyAccessors> Base;
155     typedef typename Base::Scalar Scalar;
156     typedef typename Base::StorageIndex StorageIndex;
157     enum { IsRowMajor = Base::IsRowMajor };
158 
159     using Base::operator=;
160 
161   public:
162 
163     //----------------------------------------
164     // direct access interface
165     using Base::valuePtr;
166     using Base::innerIndexPtr;
167     using Base::outerIndexPtr;
168     using Base::innerNonZeroPtr;
169     /** \copydoc SparseMatrix::valuePtr */
170     inline Scalar* valuePtr()              { return Base::m_values; }
171     /** \copydoc SparseMatrix::innerIndexPtr */
172     inline StorageIndex* innerIndexPtr()   { return Base::m_innerIndices; }
173     /** \copydoc SparseMatrix::outerIndexPtr */
174     inline StorageIndex* outerIndexPtr()   { return Base::m_outerIndex; }
175     /** \copydoc SparseMatrix::innerNonZeroPtr */
176     inline StorageIndex* innerNonZeroPtr() { return Base::m_innerNonZeros; }
177     //----------------------------------------
178 
179     /** \copydoc SparseMatrix::coeffRef */
180     inline Scalar& coeffRef(Index row, Index col)
181     {
182       const Index outer = IsRowMajor ? row : col;
183       const Index inner = IsRowMajor ? col : row;
184 
185       Index start = Base::m_outerIndex[outer];
186       Index end = Base::isCompressed() ? Base::m_outerIndex[outer+1] : start + Base::m_innerNonZeros[outer];
187       eigen_assert(end>=start && "you probably called coeffRef on a non finalized matrix");
188       eigen_assert(end>start && "coeffRef cannot be called on a zero coefficient");
189       StorageIndex* r = std::lower_bound(&Base::m_innerIndices[start],&Base::m_innerIndices[end],inner);
190       const Index id = r - &Base::m_innerIndices[0];
191       eigen_assert((*r==inner) && (id<end) && "coeffRef cannot be called on a zero coefficient");
192       return const_cast<Scalar*>(Base::m_values)[id];
193     }
194 
195     inline SparseMapBase(Index rows, Index cols, Index nnz, StorageIndex* outerIndexPtr, StorageIndex* innerIndexPtr,
196                          Scalar* valuePtr, StorageIndex* innerNonZerosPtr = 0)
197       : Base(rows, cols, nnz, outerIndexPtr, innerIndexPtr, valuePtr, innerNonZerosPtr)
198     {}
199 
200     // for vectors
201     inline SparseMapBase(Index size, Index nnz, StorageIndex* innerIndexPtr, Scalar* valuePtr)
202       : Base(size, nnz, innerIndexPtr, valuePtr)
203     {}
204 
205     /** Empty destructor */
206     inline ~SparseMapBase() {}
207 
208   protected:
209     inline SparseMapBase() {}
210 };
211 
212 /** \ingroup SparseCore_Module
213   *
214   * \brief Specialization of class Map for SparseMatrix-like storage.
215   *
216   * \tparam SparseMatrixType the equivalent sparse matrix type of the referenced data, it must be a template instance of class SparseMatrix.
217   *
218   * \sa class Map, class SparseMatrix, class Ref<SparseMatrixType,Options>
219   */
220 #ifndef EIGEN_PARSED_BY_DOXYGEN
221 template<typename MatScalar, int MatOptions, typename MatIndex, int Options, typename StrideType>
222 class Map<SparseMatrix<MatScalar,MatOptions,MatIndex>, Options, StrideType>
223   : public SparseMapBase<Map<SparseMatrix<MatScalar,MatOptions,MatIndex>, Options, StrideType> >
224 #else
225 template<typename SparseMatrixType>
226 class Map<SparseMatrixType>
227   : public SparseMapBase<Derived,WriteAccessors>
228 #endif
229 {
230   public:
231     typedef SparseMapBase<Map> Base;
232     EIGEN_SPARSE_PUBLIC_INTERFACE(Map)
233     enum { IsRowMajor = Base::IsRowMajor };
234 
235   public:
236 
237     /** Constructs a read-write Map to a sparse matrix of size \a rows x \a cols, containing \a nnz non-zero coefficients,
238       * stored as a sparse format as defined by the pointers \a outerIndexPtr, \a innerIndexPtr, and \a valuePtr.
239       * If the optional parameter \a innerNonZerosPtr is the null pointer, then a standard compressed format is assumed.
240       *
241       * This constructor is available only if \c SparseMatrixType is non-const.
242       *
243       * More details on the expected storage schemes are given in the \ref TutorialSparse "manual pages".
244       */
245     inline Map(Index rows, Index cols, Index nnz, StorageIndex* outerIndexPtr,
246                StorageIndex* innerIndexPtr, Scalar* valuePtr, StorageIndex* innerNonZerosPtr = 0)
247       : Base(rows, cols, nnz, outerIndexPtr, innerIndexPtr, valuePtr, innerNonZerosPtr)
248     {}
249 #ifndef EIGEN_PARSED_BY_DOXYGEN
250     /** Empty destructor */
251     inline ~Map() {}
252 };
253 
254 template<typename MatScalar, int MatOptions, typename MatIndex, int Options, typename StrideType>
255 class Map<const SparseMatrix<MatScalar,MatOptions,MatIndex>, Options, StrideType>
256   : public SparseMapBase<Map<const SparseMatrix<MatScalar,MatOptions,MatIndex>, Options, StrideType> >
257 {
258   public:
259     typedef SparseMapBase<Map> Base;
260     EIGEN_SPARSE_PUBLIC_INTERFACE(Map)
261     enum { IsRowMajor = Base::IsRowMajor };
262 
263   public:
264 #endif
265     /** This is the const version of the above constructor.
266       *
267       * This constructor is available only if \c SparseMatrixType is const, e.g.:
268       * \code Map<const SparseMatrix<double> >  \endcode
269       */
270     inline Map(Index rows, Index cols, Index nnz, const StorageIndex* outerIndexPtr,
271                const StorageIndex* innerIndexPtr, const Scalar* valuePtr, const StorageIndex* innerNonZerosPtr = 0)
272       : Base(rows, cols, nnz, outerIndexPtr, innerIndexPtr, valuePtr, innerNonZerosPtr)
273     {}
274 
275     /** Empty destructor */
276     inline ~Map() {}
277 };
278 
279 namespace internal {
280 
281 template<typename MatScalar, int MatOptions, typename MatIndex, int Options, typename StrideType>
282 struct evaluator<Map<SparseMatrix<MatScalar,MatOptions,MatIndex>, Options, StrideType> >
283   : evaluator<SparseCompressedBase<Map<SparseMatrix<MatScalar,MatOptions,MatIndex>, Options, StrideType> > >
284 {
285   typedef evaluator<SparseCompressedBase<Map<SparseMatrix<MatScalar,MatOptions,MatIndex>, Options, StrideType> > > Base;
286   typedef Map<SparseMatrix<MatScalar,MatOptions,MatIndex>, Options, StrideType> XprType;
287   evaluator() : Base() {}
288   explicit evaluator(const XprType &mat) : Base(mat) {}
289 };
290 
291 template<typename MatScalar, int MatOptions, typename MatIndex, int Options, typename StrideType>
292 struct evaluator<Map<const SparseMatrix<MatScalar,MatOptions,MatIndex>, Options, StrideType> >
293   : evaluator<SparseCompressedBase<Map<const SparseMatrix<MatScalar,MatOptions,MatIndex>, Options, StrideType> > >
294 {
295   typedef evaluator<SparseCompressedBase<Map<const SparseMatrix<MatScalar,MatOptions,MatIndex>, Options, StrideType> > > Base;
296   typedef Map<const SparseMatrix<MatScalar,MatOptions,MatIndex>, Options, StrideType> XprType;
297   evaluator() : Base() {}
298   explicit evaluator(const XprType &mat) : Base(mat) {}
299 };
300 
301 }
302 
303 } // end namespace Eigen
304 
305 #endif // EIGEN_SPARSE_MAP_H
306