1 // This file is part of Eigen, a lightweight C++ template library
2 // for linear algebra.
3 //
4 // Copyright (C) 2008-2009 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_SPARSEVECTOR_H
11 #define EIGEN_SPARSEVECTOR_H
12 
13 namespace Eigen {
14 
15 /** \ingroup SparseCore_Module
16   * \class SparseVector
17   *
18   * \brief a sparse vector class
19   *
20   * \tparam _Scalar the scalar type, i.e. the type of the coefficients
21   *
22   * See http://www.netlib.org/linalg/html_templates/node91.html for details on the storage scheme.
23   *
24   * This class can be extended with the help of the plugin mechanism described on the page
25   * \ref TopicCustomizingEigen by defining the preprocessor symbol \c EIGEN_SPARSEVECTOR_PLUGIN.
26   */
27 
28 namespace internal {
29 template<typename _Scalar, int _Options, typename _Index>
30 struct traits<SparseVector<_Scalar, _Options, _Index> >
31 {
32   typedef _Scalar Scalar;
33   typedef _Index Index;
34   typedef Sparse StorageKind;
35   typedef MatrixXpr XprKind;
36   enum {
37     IsColVector = (_Options & RowMajorBit) ? 0 : 1,
38 
39     RowsAtCompileTime = IsColVector ? Dynamic : 1,
40     ColsAtCompileTime = IsColVector ? 1 : Dynamic,
41     MaxRowsAtCompileTime = RowsAtCompileTime,
42     MaxColsAtCompileTime = ColsAtCompileTime,
43     Flags = _Options | NestByRefBit | LvalueBit | (IsColVector ? 0 : RowMajorBit),
44     CoeffReadCost = NumTraits<Scalar>::ReadCost,
45     SupportedAccessPatterns = InnerRandomAccessPattern
46   };
47 };
48 
49 // Sparse-Vector-Assignment kinds:
50 enum {
51   SVA_RuntimeSwitch,
52   SVA_Inner,
53   SVA_Outer
54 };
55 
56 template< typename Dest, typename Src,
57           int AssignmentKind = !bool(Src::IsVectorAtCompileTime) ? SVA_RuntimeSwitch
58                              : Src::InnerSizeAtCompileTime==1 ? SVA_Outer
59                              : SVA_Inner>
60 struct sparse_vector_assign_selector;
61 
62 }
63 
64 template<typename _Scalar, int _Options, typename _Index>
65 class SparseVector
66   : public SparseMatrixBase<SparseVector<_Scalar, _Options, _Index> >
67 {
68     typedef SparseMatrixBase<SparseVector> SparseBase;
69 
70   public:
71     EIGEN_SPARSE_PUBLIC_INTERFACE(SparseVector)
72     EIGEN_SPARSE_INHERIT_ASSIGNMENT_OPERATOR(SparseVector, +=)
73     EIGEN_SPARSE_INHERIT_ASSIGNMENT_OPERATOR(SparseVector, -=)
74 
75     typedef internal::CompressedStorage<Scalar,Index> Storage;
76     enum { IsColVector = internal::traits<SparseVector>::IsColVector };
77 
78     enum {
79       Options = _Options
80     };
81 
82     EIGEN_STRONG_INLINE Index rows() const { return IsColVector ? m_size : 1; }
83     EIGEN_STRONG_INLINE Index cols() const { return IsColVector ? 1 : m_size; }
84     EIGEN_STRONG_INLINE Index innerSize() const { return m_size; }
85     EIGEN_STRONG_INLINE Index outerSize() const { return 1; }
86 
87     EIGEN_STRONG_INLINE const Scalar* valuePtr() const { return &m_data.value(0); }
88     EIGEN_STRONG_INLINE Scalar* valuePtr() { return &m_data.value(0); }
89 
90     EIGEN_STRONG_INLINE const Index* innerIndexPtr() const { return &m_data.index(0); }
91     EIGEN_STRONG_INLINE Index* innerIndexPtr() { return &m_data.index(0); }
92 
93     /** \internal */
94     inline Storage& data() { return m_data; }
95     /** \internal */
96     inline const Storage& data() const { return m_data; }
97 
98     inline Scalar coeff(Index row, Index col) const
99     {
100       eigen_assert(IsColVector ? (col==0 && row>=0 && row<m_size) : (row==0 && col>=0 && col<m_size));
101       return coeff(IsColVector ? row : col);
102     }
103     inline Scalar coeff(Index i) const
104     {
105       eigen_assert(i>=0 && i<m_size);
106       return m_data.at(i);
107     }
108 
109     inline Scalar& coeffRef(Index row, Index col)
110     {
111       eigen_assert(IsColVector ? (col==0 && row>=0 && row<m_size) : (row==0 && col>=0 && col<m_size));
112       return coeff(IsColVector ? row : col);
113     }
114 
115     /** \returns a reference to the coefficient value at given index \a i
116       * This operation involes a log(rho*size) binary search. If the coefficient does not
117       * exist yet, then a sorted insertion into a sequential buffer is performed.
118       *
119       * This insertion might be very costly if the number of nonzeros above \a i is large.
120       */
121     inline Scalar& coeffRef(Index i)
122     {
123       eigen_assert(i>=0 && i<m_size);
124       return m_data.atWithInsertion(i);
125     }
126 
127   public:
128 
129     class InnerIterator;
130     class ReverseInnerIterator;
131 
132     inline void setZero() { m_data.clear(); }
133 
134     /** \returns the number of non zero coefficients */
135     inline Index nonZeros() const  { return static_cast<Index>(m_data.size()); }
136 
137     inline void startVec(Index outer)
138     {
139       EIGEN_UNUSED_VARIABLE(outer);
140       eigen_assert(outer==0);
141     }
142 
143     inline Scalar& insertBackByOuterInner(Index outer, Index inner)
144     {
145       EIGEN_UNUSED_VARIABLE(outer);
146       eigen_assert(outer==0);
147       return insertBack(inner);
148     }
149     inline Scalar& insertBack(Index i)
150     {
151       m_data.append(0, i);
152       return m_data.value(m_data.size()-1);
153     }
154 
155     inline Scalar& insert(Index row, Index col)
156     {
157       eigen_assert(IsColVector ? (col==0 && row>=0 && row<m_size) : (row==0 && col>=0 && col<m_size));
158 
159       Index inner = IsColVector ? row : col;
160       Index outer = IsColVector ? col : row;
161       eigen_assert(outer==0);
162       return insert(inner);
163     }
164     Scalar& insert(Index i)
165     {
166       eigen_assert(i>=0 && i<m_size);
167 
168       Index startId = 0;
169       Index p = Index(m_data.size()) - 1;
170       // TODO smart realloc
171       m_data.resize(p+2,1);
172 
173       while ( (p >= startId) && (m_data.index(p) > i) )
174       {
175         m_data.index(p+1) = m_data.index(p);
176         m_data.value(p+1) = m_data.value(p);
177         --p;
178       }
179       m_data.index(p+1) = i;
180       m_data.value(p+1) = 0;
181       return m_data.value(p+1);
182     }
183 
184     /**
185       */
186     inline void reserve(Index reserveSize) { m_data.reserve(reserveSize); }
187 
188 
189     inline void finalize() {}
190 
191     void prune(const Scalar& reference, const RealScalar& epsilon = NumTraits<RealScalar>::dummy_precision())
192     {
193       m_data.prune(reference,epsilon);
194     }
195 
196     void resize(Index rows, Index cols)
197     {
198       eigen_assert(rows==1 || cols==1);
199       resize(IsColVector ? rows : cols);
200     }
201 
202     void resize(Index newSize)
203     {
204       m_size = newSize;
205       m_data.clear();
206     }
207 
208     void resizeNonZeros(Index size) { m_data.resize(size); }
209 
210     inline SparseVector() : m_size(0) { check_template_parameters(); resize(0); }
211 
212     inline SparseVector(Index size) : m_size(0) { check_template_parameters(); resize(size); }
213 
214     inline SparseVector(Index rows, Index cols) : m_size(0) { check_template_parameters(); resize(rows,cols); }
215 
216     template<typename OtherDerived>
217     inline SparseVector(const SparseMatrixBase<OtherDerived>& other)
218       : m_size(0)
219     {
220       check_template_parameters();
221       *this = other.derived();
222     }
223 
224     inline SparseVector(const SparseVector& other)
225       : SparseBase(other), m_size(0)
226     {
227       check_template_parameters();
228       *this = other.derived();
229     }
230 
231     /** Swaps the values of \c *this and \a other.
232       * Overloaded for performance: this version performs a \em shallow swap by swaping pointers and attributes only.
233       * \sa SparseMatrixBase::swap()
234       */
235     inline void swap(SparseVector& other)
236     {
237       std::swap(m_size, other.m_size);
238       m_data.swap(other.m_data);
239     }
240 
241     inline SparseVector& operator=(const SparseVector& other)
242     {
243       if (other.isRValue())
244       {
245         swap(other.const_cast_derived());
246       }
247       else
248       {
249         resize(other.size());
250         m_data = other.m_data;
251       }
252       return *this;
253     }
254 
255     template<typename OtherDerived>
256     inline SparseVector& operator=(const SparseMatrixBase<OtherDerived>& other)
257     {
258       SparseVector tmp(other.size());
259       internal::sparse_vector_assign_selector<SparseVector,OtherDerived>::run(tmp,other.derived());
260       this->swap(tmp);
261       return *this;
262     }
263 
264     #ifndef EIGEN_PARSED_BY_DOXYGEN
265     template<typename Lhs, typename Rhs>
266     inline SparseVector& operator=(const SparseSparseProduct<Lhs,Rhs>& product)
267     {
268       return Base::operator=(product);
269     }
270     #endif
271 
272     friend std::ostream & operator << (std::ostream & s, const SparseVector& m)
273     {
274       for (Index i=0; i<m.nonZeros(); ++i)
275         s << "(" << m.m_data.value(i) << "," << m.m_data.index(i) << ") ";
276       s << std::endl;
277       return s;
278     }
279 
280     /** Destructor */
281     inline ~SparseVector() {}
282 
283     /** Overloaded for performance */
284     Scalar sum() const;
285 
286   public:
287 
288     /** \internal \deprecated use setZero() and reserve() */
289     EIGEN_DEPRECATED void startFill(Index reserve)
290     {
291       setZero();
292       m_data.reserve(reserve);
293     }
294 
295     /** \internal \deprecated use insertBack(Index,Index) */
296     EIGEN_DEPRECATED Scalar& fill(Index r, Index c)
297     {
298       eigen_assert(r==0 || c==0);
299       return fill(IsColVector ? r : c);
300     }
301 
302     /** \internal \deprecated use insertBack(Index) */
303     EIGEN_DEPRECATED Scalar& fill(Index i)
304     {
305       m_data.append(0, i);
306       return m_data.value(m_data.size()-1);
307     }
308 
309     /** \internal \deprecated use insert(Index,Index) */
310     EIGEN_DEPRECATED Scalar& fillrand(Index r, Index c)
311     {
312       eigen_assert(r==0 || c==0);
313       return fillrand(IsColVector ? r : c);
314     }
315 
316     /** \internal \deprecated use insert(Index) */
317     EIGEN_DEPRECATED Scalar& fillrand(Index i)
318     {
319       return insert(i);
320     }
321 
322     /** \internal \deprecated use finalize() */
323     EIGEN_DEPRECATED void endFill() {}
324 
325     // These two functions were here in the 3.1 release, so let's keep them in case some code rely on them.
326     /** \internal \deprecated use data() */
327     EIGEN_DEPRECATED Storage& _data() { return m_data; }
328     /** \internal \deprecated use data() */
329     EIGEN_DEPRECATED const Storage& _data() const { return m_data; }
330 
331 #   ifdef EIGEN_SPARSEVECTOR_PLUGIN
332 #     include EIGEN_SPARSEVECTOR_PLUGIN
333 #   endif
334 
335 protected:
336 
337     static void check_template_parameters()
338     {
339       EIGEN_STATIC_ASSERT(NumTraits<Index>::IsSigned,THE_INDEX_TYPE_MUST_BE_A_SIGNED_TYPE);
340       EIGEN_STATIC_ASSERT((_Options&(ColMajor|RowMajor))==Options,INVALID_MATRIX_TEMPLATE_PARAMETERS);
341     }
342 
343     Storage m_data;
344     Index m_size;
345 };
346 
347 template<typename Scalar, int _Options, typename _Index>
348 class SparseVector<Scalar,_Options,_Index>::InnerIterator
349 {
350   public:
351     InnerIterator(const SparseVector& vec, Index outer=0)
352       : m_data(vec.m_data), m_id(0), m_end(static_cast<Index>(m_data.size()))
353     {
354       EIGEN_UNUSED_VARIABLE(outer);
355       eigen_assert(outer==0);
356     }
357 
358     InnerIterator(const internal::CompressedStorage<Scalar,Index>& data)
359       : m_data(data), m_id(0), m_end(static_cast<Index>(m_data.size()))
360     {}
361 
362     inline InnerIterator& operator++() { m_id++; return *this; }
363 
364     inline Scalar value() const { return m_data.value(m_id); }
365     inline Scalar& valueRef() { return const_cast<Scalar&>(m_data.value(m_id)); }
366 
367     inline Index index() const { return m_data.index(m_id); }
368     inline Index row() const { return IsColVector ? index() : 0; }
369     inline Index col() const { return IsColVector ? 0 : index(); }
370 
371     inline operator bool() const { return (m_id < m_end); }
372 
373   protected:
374     const internal::CompressedStorage<Scalar,Index>& m_data;
375     Index m_id;
376     const Index m_end;
377 };
378 
379 template<typename Scalar, int _Options, typename _Index>
380 class SparseVector<Scalar,_Options,_Index>::ReverseInnerIterator
381 {
382   public:
383     ReverseInnerIterator(const SparseVector& vec, Index outer=0)
384       : m_data(vec.m_data), m_id(static_cast<Index>(m_data.size())), m_start(0)
385     {
386       EIGEN_UNUSED_VARIABLE(outer);
387       eigen_assert(outer==0);
388     }
389 
390     ReverseInnerIterator(const internal::CompressedStorage<Scalar,Index>& data)
391       : m_data(data), m_id(static_cast<Index>(m_data.size())), m_start(0)
392     {}
393 
394     inline ReverseInnerIterator& operator--() { m_id--; return *this; }
395 
396     inline Scalar value() const { return m_data.value(m_id-1); }
397     inline Scalar& valueRef() { return const_cast<Scalar&>(m_data.value(m_id-1)); }
398 
399     inline Index index() const { return m_data.index(m_id-1); }
400     inline Index row() const { return IsColVector ? index() : 0; }
401     inline Index col() const { return IsColVector ? 0 : index(); }
402 
403     inline operator bool() const { return (m_id > m_start); }
404 
405   protected:
406     const internal::CompressedStorage<Scalar,Index>& m_data;
407     Index m_id;
408     const Index m_start;
409 };
410 
411 namespace internal {
412 
413 template< typename Dest, typename Src>
414 struct sparse_vector_assign_selector<Dest,Src,SVA_Inner> {
415   static void run(Dest& dst, const Src& src) {
416     eigen_internal_assert(src.innerSize()==src.size());
417     for(typename Src::InnerIterator it(src, 0); it; ++it)
418       dst.insert(it.index()) = it.value();
419   }
420 };
421 
422 template< typename Dest, typename Src>
423 struct sparse_vector_assign_selector<Dest,Src,SVA_Outer> {
424   static void run(Dest& dst, const Src& src) {
425     eigen_internal_assert(src.outerSize()==src.size());
426     for(typename Dest::Index i=0; i<src.size(); ++i)
427     {
428       typename Src::InnerIterator it(src, i);
429       if(it)
430         dst.insert(i) = it.value();
431     }
432   }
433 };
434 
435 template< typename Dest, typename Src>
436 struct sparse_vector_assign_selector<Dest,Src,SVA_RuntimeSwitch> {
437   static void run(Dest& dst, const Src& src) {
438     if(src.outerSize()==1)  sparse_vector_assign_selector<Dest,Src,SVA_Inner>::run(dst, src);
439     else                    sparse_vector_assign_selector<Dest,Src,SVA_Outer>::run(dst, src);
440   }
441 };
442 
443 }
444 
445 } // end namespace Eigen
446 
447 #endif // EIGEN_SPARSEVECTOR_H
448