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  : 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 (int(RowsAtCompileTime)!=int(OtherDerived::RowsAtCompileTime))
234  return assign(other.transpose());
235  else
236  return assign(other);
237  }
238 
239  #ifndef EIGEN_PARSED_BY_DOXYGEN
240  template<typename Lhs, typename Rhs>
241  inline SparseVector& operator=(const SparseSparseProduct<Lhs,Rhs>& product)
242  {
243  return Base::operator=(product);
244  }
245  #endif
246 
247  friend std::ostream & operator << (std::ostream & s, const SparseVector& m)
248  {
249  for (Index i=0; i<m.nonZeros(); ++i)
250  s << "(" << m.m_data.value(i) << "," << m.m_data.index(i) << ") ";
251  s << std::endl;
252  return s;
253  }
254 
256  inline ~SparseVector() {}
257 
259  Scalar sum() const;
260 
261  public:
262 
264  EIGEN_DEPRECATED void startFill(Index reserve)
265  {
266  setZero();
267  m_data.reserve(reserve);
268  }
269 
271  EIGEN_DEPRECATED Scalar& fill(Index r, Index c)
272  {
273  eigen_assert(r==0 || c==0);
274  return fill(IsColVector ? r : c);
275  }
276 
278  EIGEN_DEPRECATED Scalar& fill(Index i)
279  {
280  m_data.append(0, i);
281  return m_data.value(m_data.size()-1);
282  }
283 
285  EIGEN_DEPRECATED Scalar& fillrand(Index r, Index c)
286  {
287  eigen_assert(r==0 || c==0);
288  return fillrand(IsColVector ? r : c);
289  }
290 
292  EIGEN_DEPRECATED Scalar& fillrand(Index i)
293  {
294  return insert(i);
295  }
296 
298  EIGEN_DEPRECATED void endFill() {}
299 
300 # ifdef EIGEN_SPARSEVECTOR_PLUGIN
301 # include EIGEN_SPARSEVECTOR_PLUGIN
302 # endif
303 
304 protected:
305  template<typename OtherDerived>
306  EIGEN_DONT_INLINE SparseVector& assign(const SparseMatrixBase<OtherDerived>& _other)
307  {
308  const OtherDerived& other(_other.derived());
309  const bool needToTranspose = (Flags & RowMajorBit) != (OtherDerived::Flags & RowMajorBit);
310  if(needToTranspose)
311  {
312  Index size = other.size();
313  Index nnz = other.nonZeros();
314  resize(size);
315  reserve(nnz);
316  for(Index i=0; i<size; ++i)
317  {
318  typename OtherDerived::InnerIterator it(other, i);
319  if(it)
320  insert(i) = it.value();
321  }
322  return *this;
323  }
324  else
325  {
326  // there is no special optimization
327  return Base::operator=(other);
328  }
329  }
330 };
331 
332 template<typename Scalar, int _Options, typename _Index>
333 class SparseVector<Scalar,_Options,_Index>::InnerIterator
334 {
335  public:
336  InnerIterator(const SparseVector& vec, Index outer=0)
337  : m_data(vec.m_data), m_id(0), m_end(static_cast<Index>(m_data.size()))
338  {
339  EIGEN_UNUSED_VARIABLE(outer);
340  eigen_assert(outer==0);
341  }
342 
343  InnerIterator(const internal::CompressedStorage<Scalar,Index>& data)
344  : m_data(data), m_id(0), m_end(static_cast<Index>(m_data.size()))
345  {}
346 
347  inline InnerIterator& operator++() { m_id++; return *this; }
348 
349  inline Scalar value() const { return m_data.value(m_id); }
350  inline Scalar& valueRef() { return const_cast<Scalar&>(m_data.value(m_id)); }
351 
352  inline Index index() const { return m_data.index(m_id); }
353  inline Index row() const { return IsColVector ? index() : 0; }
354  inline Index col() const { return IsColVector ? 0 : index(); }
355 
356  inline operator bool() const { return (m_id < m_end); }
357 
358  protected:
359  const internal::CompressedStorage<Scalar,Index>& m_data;
360  Index m_id;
361  const Index m_end;
362 };
363 
364 template<typename Scalar, int _Options, typename _Index>
365 class SparseVector<Scalar,_Options,_Index>::ReverseInnerIterator
366 {
367  public:
368  ReverseInnerIterator(const SparseVector& vec, Index outer=0)
369  : m_data(vec.m_data), m_id(static_cast<Index>(m_data.size())), m_start(0)
370  {
371  EIGEN_UNUSED_VARIABLE(outer);
372  eigen_assert(outer==0);
373  }
374 
375  ReverseInnerIterator(const internal::CompressedStorage<Scalar,Index>& data)
376  : m_data(data), m_id(static_cast<Index>(m_data.size())), m_start(0)
377  {}
378 
379  inline ReverseInnerIterator& operator--() { m_id--; return *this; }
380 
381  inline Scalar value() const { return m_data.value(m_id-1); }
382  inline Scalar& valueRef() { return const_cast<Scalar&>(m_data.value(m_id-1)); }
383 
384  inline Index index() const { return m_data.index(m_id-1); }
385  inline Index row() const { return IsColVector ? index() : 0; }
386  inline Index col() const { return IsColVector ? 0 : index(); }
387 
388  inline operator bool() const { return (m_id > m_start); }
389 
390  protected:
391  const internal::CompressedStorage<Scalar,Index>& m_data;
392  Index m_id;
393  const Index m_start;
394 };
395 
396 } // end namespace Eigen
397 
398 #endif // EIGEN_SPARSEVECTOR_H