SparseVector.h
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 
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 
50 template<typename _Scalar, int _Options, typename _Index>
52  : public SparseMatrixBase<SparseVector<_Scalar, _Options, _Index> >
53 {
54  public:
55  EIGEN_SPARSE_PUBLIC_INTERFACE(SparseVector)
56  EIGEN_SPARSE_INHERIT_ASSIGNMENT_OPERATOR(SparseVector, +=)
57  EIGEN_SPARSE_INHERIT_ASSIGNMENT_OPERATOR(SparseVector, -=)
58 
59  protected:
60  public:
61 
63  enum { IsColVector = internal::traits<SparseVector>::IsColVector };
64 
65  enum {
66  Options = _Options
67  };
68 
69  internal::CompressedStorage<Scalar,Index> m_data;
70  Index m_size;
71 
72  internal::CompressedStorage<Scalar,Index>& _data() { return m_data; }
73  internal::CompressedStorage<Scalar,Index>& _data() const { return m_data; }
74 
75  public:
76 
77  EIGEN_STRONG_INLINE Index rows() const { return IsColVector ? m_size : 1; }
78  EIGEN_STRONG_INLINE Index cols() const { return IsColVector ? 1 : m_size; }
79  EIGEN_STRONG_INLINE Index innerSize() const { return m_size; }
80  EIGEN_STRONG_INLINE Index outerSize() const { return 1; }
81 
82  EIGEN_STRONG_INLINE const Scalar* valuePtr() const { return &m_data.value(0); }
83  EIGEN_STRONG_INLINE Scalar* valuePtr() { return &m_data.value(0); }
84 
85  EIGEN_STRONG_INLINE const Index* innerIndexPtr() const { return &m_data.index(0); }
86  EIGEN_STRONG_INLINE Index* innerIndexPtr() { return &m_data.index(0); }
87 
88  inline Scalar coeff(Index row, Index col) const
89  {
90  eigen_assert((IsColVector ? col : row)==0);
91  return coeff(IsColVector ? row : col);
92  }
93  inline Scalar coeff(Index i) const { return m_data.at(i); }
94 
95  inline Scalar& coeffRef(Index row, Index col)
96  {
97  eigen_assert((IsColVector ? col : row)==0);
98  return coeff(IsColVector ? row : col);
99  }
100 
107  inline Scalar& coeffRef(Index i)
108  {
109  return m_data.atWithInsertion(i);
110  }
111 
112  public:
113 
114  class InnerIterator;
115  class ReverseInnerIterator;
116 
117  inline void setZero() { m_data.clear(); }
118 
120  inline Index nonZeros() const { return static_cast<Index>(m_data.size()); }
121 
122  inline void startVec(Index outer)
123  {
124  EIGEN_UNUSED_VARIABLE(outer);
125  eigen_assert(outer==0);
126  }
127 
128  inline Scalar& insertBackByOuterInner(Index outer, Index inner)
129  {
130  EIGEN_UNUSED_VARIABLE(outer);
131  eigen_assert(outer==0);
132  return insertBack(inner);
133  }
134  inline Scalar& insertBack(Index i)
135  {
136  m_data.append(0, i);
137  return m_data.value(m_data.size()-1);
138  }
139 
140  inline Scalar& insert(Index row, Index col)
141  {
142  Index inner = IsColVector ? row : col;
143  Index outer = IsColVector ? col : row;
144  eigen_assert(outer==0);
145  return insert(inner);
146  }
147  Scalar& insert(Index i)
148  {
149  Index startId = 0;
150  Index p = Index(m_data.size()) - 1;
151  // TODO smart realloc
152  m_data.resize(p+2,1);
153 
154  while ( (p >= startId) && (m_data.index(p) > i) )
155  {
156  m_data.index(p+1) = m_data.index(p);
157  m_data.value(p+1) = m_data.value(p);
158  --p;
159  }
160  m_data.index(p+1) = i;
161  m_data.value(p+1) = 0;
162  return m_data.value(p+1);
163  }
164 
167  inline void reserve(Index reserveSize) { m_data.reserve(reserveSize); }
168 
169 
170  inline void finalize() {}
171 
172  void prune(Scalar reference, RealScalar epsilon = NumTraits<RealScalar>::dummy_precision())
173  {
174  m_data.prune(reference,epsilon);
175  }
176 
177  void resize(Index rows, Index cols)
178  {
179  eigen_assert(rows==1 || cols==1);
180  resize(IsColVector ? rows : cols);
181  }
182 
183  void resize(Index newSize)
184  {
185  m_size = newSize;
186  m_data.clear();
187  }
188 
189  void resizeNonZeros(Index size) { m_data.resize(size); }
190 
191  inline SparseVector() : m_size(0) { resize(0); }
192 
193  inline SparseVector(Index size) : m_size(0) { resize(size); }
194 
195  inline SparseVector(Index rows, Index cols) : m_size(0) { resize(rows,cols); }
196 
197  template<typename OtherDerived>
198  inline SparseVector(const SparseMatrixBase<OtherDerived>& other)
199  : m_size(0)
200  {
201  *this = other.derived();
202  }
203 
204  inline SparseVector(const SparseVector& other)
205  : SparseBase(other), m_size(0)
206  {
207  *this = other.derived();
208  }
209 
210  inline void swap(SparseVector& other)
211  {
212  std::swap(m_size, other.m_size);
213  m_data.swap(other.m_data);
214  }
215 
216  inline SparseVector& operator=(const SparseVector& other)
217  {
218  if (other.isRValue())
219  {
220  swap(other.const_cast_derived());
221  }
222  else
223  {
224  resize(other.size());
225  m_data = other.m_data;
226  }
227  return *this;
228  }
229 
230  template<typename OtherDerived>
231  inline SparseVector& operator=(const SparseMatrixBase<OtherDerived>& other)
232  {
233  if ( (bool(OtherDerived::IsVectorAtCompileTime) && int(RowsAtCompileTime)!=int(OtherDerived::RowsAtCompileTime))
234  || ((!bool(OtherDerived::IsVectorAtCompileTime)) && ( bool(IsColVector) ? other.cols()>1 : other.rows()>1 )))
235  return assign(other.transpose());
236  else
237  return assign(other);
238  }
239 
240  #ifndef EIGEN_PARSED_BY_DOXYGEN
241  template<typename Lhs, typename Rhs>
242  inline SparseVector& operator=(const SparseSparseProduct<Lhs,Rhs>& product)
243  {
244  return Base::operator=(product);
245  }
246  #endif
247 
248  friend std::ostream & operator << (std::ostream & s, const SparseVector& m)
249  {
250  for (Index i=0; i<m.nonZeros(); ++i)
251  s << "(" << m.m_data.value(i) << "," << m.m_data.index(i) << ") ";
252  s << std::endl;
253  return s;
254  }
255 
257  inline ~SparseVector() {}
258 
260  Scalar sum() const;
261 
262  public:
263 
265  EIGEN_DEPRECATED void startFill(Index reserve)
266  {
267  setZero();
268  m_data.reserve(reserve);
269  }
270 
272  EIGEN_DEPRECATED Scalar& fill(Index r, Index c)
273  {
274  eigen_assert(r==0 || c==0);
275  return fill(IsColVector ? r : c);
276  }
277 
279  EIGEN_DEPRECATED Scalar& fill(Index i)
280  {
281  m_data.append(0, i);
282  return m_data.value(m_data.size()-1);
283  }
284 
286  EIGEN_DEPRECATED Scalar& fillrand(Index r, Index c)
287  {
288  eigen_assert(r==0 || c==0);
289  return fillrand(IsColVector ? r : c);
290  }
291 
293  EIGEN_DEPRECATED Scalar& fillrand(Index i)
294  {
295  return insert(i);
296  }
297 
299  EIGEN_DEPRECATED void endFill() {}
300 
301 # ifdef EIGEN_SPARSEVECTOR_PLUGIN
302 # include EIGEN_SPARSEVECTOR_PLUGIN
303 # endif
304 
305 protected:
306  template<typename OtherDerived>
307  EIGEN_DONT_INLINE SparseVector& assign(const SparseMatrixBase<OtherDerived>& _other)
308  {
309  const OtherDerived& other(_other.derived());
310  const bool needToTranspose = (Flags & RowMajorBit) != (OtherDerived::Flags & RowMajorBit);
311  if(needToTranspose)
312  {
313  Index size = other.size();
314  Index nnz = other.nonZeros();
315  resize(size);
316  reserve(nnz);
317  for(Index i=0; i<size; ++i)
318  {
319  typename OtherDerived::InnerIterator it(other, i);
320  if(it)
321  insert(i) = it.value();
322  }
323  return *this;
324  }
325  else
326  {
327  // there is no special optimization
328  return Base::operator=(other);
329  }
330  }
331 };
332 
333 template<typename Scalar, int _Options, typename _Index>
334 class SparseVector<Scalar,_Options,_Index>::InnerIterator
335 {
336  public:
337  InnerIterator(const SparseVector& vec, Index outer=0)
338  : m_data(vec.m_data), m_id(0), m_end(static_cast<Index>(m_data.size()))
339  {
340  EIGEN_UNUSED_VARIABLE(outer);
341  eigen_assert(outer==0);
342  }
343 
344  InnerIterator(const internal::CompressedStorage<Scalar,Index>& data)
345  : m_data(data), m_id(0), m_end(static_cast<Index>(m_data.size()))
346  {}
347 
348  inline InnerIterator& operator++() { m_id++; return *this; }
349 
350  inline Scalar value() const { return m_data.value(m_id); }
351  inline Scalar& valueRef() { return const_cast<Scalar&>(m_data.value(m_id)); }
352 
353  inline Index index() const { return m_data.index(m_id); }
354  inline Index row() const { return IsColVector ? index() : 0; }
355  inline Index col() const { return IsColVector ? 0 : index(); }
356 
357  inline operator bool() const { return (m_id < m_end); }
358 
359  protected:
360  const internal::CompressedStorage<Scalar,Index>& m_data;
361  Index m_id;
362  const Index m_end;
363 };
364 
365 template<typename Scalar, int _Options, typename _Index>
366 class SparseVector<Scalar,_Options,_Index>::ReverseInnerIterator
367 {
368  public:
369  ReverseInnerIterator(const SparseVector& vec, Index outer=0)
370  : m_data(vec.m_data), m_id(static_cast<Index>(m_data.size())), m_start(0)
371  {
372  EIGEN_UNUSED_VARIABLE(outer);
373  eigen_assert(outer==0);
374  }
375 
376  ReverseInnerIterator(const internal::CompressedStorage<Scalar,Index>& data)
377  : m_data(data), m_id(static_cast<Index>(m_data.size())), m_start(0)
378  {}
379 
380  inline ReverseInnerIterator& operator--() { m_id--; return *this; }
381 
382  inline Scalar value() const { return m_data.value(m_id-1); }
383  inline Scalar& valueRef() { return const_cast<Scalar&>(m_data.value(m_id-1)); }
384 
385  inline Index index() const { return m_data.index(m_id-1); }
386  inline Index row() const { return IsColVector ? index() : 0; }
387  inline Index col() const { return IsColVector ? 0 : index(); }
388 
389  inline operator bool() const { return (m_id > m_start); }
390 
391  protected:
392  const internal::CompressedStorage<Scalar,Index>& m_data;
393  Index m_id;
394  const Index m_start;
395 };
396 
397 } // end namespace Eigen
398 
399 #endif // EIGEN_SPARSEVECTOR_H