Eigen  3.2.91
SparseVector.h
1 // This file is part of Eigen, a lightweight C++ template library
2 // for linear algebra.
3 //
4 // Copyright (C) 2008-2014 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 _StorageIndex>
30 struct traits<SparseVector<_Scalar, _Options, _StorageIndex> >
31 {
32  typedef _Scalar Scalar;
33  typedef _StorageIndex StorageIndex;
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 _StorageIndex>
65 class SparseVector
66  : public SparseMatrixBase<SparseVector<_Scalar, _Options, _StorageIndex> >
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,StorageIndex> 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 StorageIndex* innerIndexPtr() const { return &m_data.index(0); }
91  EIGEN_STRONG_INLINE StorageIndex* innerIndexPtr() { return &m_data.index(0); }
92 
94  inline Storage& data() { return m_data; }
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(StorageIndex(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 coeffRef(IsColVector ? row : col);
113  }
114 
121  inline Scalar& coeffRef(Index i)
122  {
123  eigen_assert(i>=0 && i<m_size);
124  return m_data.atWithInsertion(StorageIndex(i));
125  }
126 
127  public:
128 
129  class InnerIterator;
130  class ReverseInnerIterator;
131 
132  inline void setZero() { m_data.clear(); }
133 
135  inline Index nonZeros() const { return 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  Scalar& insertBackByOuterInnerUnordered(Index outer, Index inner)
156  {
157  EIGEN_UNUSED_VARIABLE(outer);
158  eigen_assert(outer==0);
159  return insertBackUnordered(inner);
160  }
161  inline Scalar& insertBackUnordered(Index i)
162  {
163  m_data.append(0, i);
164  return m_data.value(m_data.size()-1);
165  }
166 
167  inline Scalar& insert(Index row, Index col)
168  {
169  eigen_assert(IsColVector ? (col==0 && row>=0 && row<m_size) : (row==0 && col>=0 && col<m_size));
170 
171  Index inner = IsColVector ? row : col;
172  Index outer = IsColVector ? col : row;
173  EIGEN_ONLY_USED_FOR_DEBUG(outer);
174  eigen_assert(outer==0);
175  return insert(inner);
176  }
177  Scalar& insert(Index i)
178  {
179  eigen_assert(i>=0 && i<m_size);
180 
181  Index startId = 0;
182  Index p = Index(m_data.size()) - 1;
183  // TODO smart realloc
184  m_data.resize(p+2,1);
185 
186  while ( (p >= startId) && (m_data.index(p) > i) )
187  {
188  m_data.index(p+1) = m_data.index(p);
189  m_data.value(p+1) = m_data.value(p);
190  --p;
191  }
192  m_data.index(p+1) = convert_index(i);
193  m_data.value(p+1) = 0;
194  return m_data.value(p+1);
195  }
196 
199  inline void reserve(Index reserveSize) { m_data.reserve(reserveSize); }
200 
201 
202  inline void finalize() {}
203 
204  void prune(const Scalar& reference, const RealScalar& epsilon = NumTraits<RealScalar>::dummy_precision())
205  {
206  m_data.prune(reference,epsilon);
207  }
208 
209  void resize(Index rows, Index cols)
210  {
211  eigen_assert((IsColVector ? cols : rows)==1 && "Outer dimension must equal 1");
212  resize(IsColVector ? rows : cols);
213  }
214 
215  void resize(Index newSize)
216  {
217  m_size = newSize;
218  m_data.clear();
219  }
220 
221  void resizeNonZeros(Index size) { m_data.resize(size); }
222 
223  inline SparseVector() : m_size(0) { check_template_parameters(); resize(0); }
224 
225  explicit inline SparseVector(Index size) : m_size(0) { check_template_parameters(); resize(size); }
226 
227  inline SparseVector(Index rows, Index cols) : m_size(0) { check_template_parameters(); resize(rows,cols); }
228 
229  template<typename OtherDerived>
230  inline SparseVector(const SparseMatrixBase<OtherDerived>& other)
231  : m_size(0)
232  {
233  check_template_parameters();
234  *this = other.derived();
235  }
236 
237  inline SparseVector(const SparseVector& other)
238  : SparseBase(other), m_size(0)
239  {
240  check_template_parameters();
241  *this = other.derived();
242  }
243 
248  inline void swap(SparseVector& other)
249  {
250  std::swap(m_size, other.m_size);
251  m_data.swap(other.m_data);
252  }
253 
254  inline SparseVector& operator=(const SparseVector& other)
255  {
256  if (other.isRValue())
257  {
258  swap(other.const_cast_derived());
259  }
260  else
261  {
262  resize(other.size());
263  m_data = other.m_data;
264  }
265  return *this;
266  }
267 
268  template<typename OtherDerived>
269  inline SparseVector& operator=(const SparseMatrixBase<OtherDerived>& other)
270  {
271  SparseVector tmp(other.size());
272  internal::sparse_vector_assign_selector<SparseVector,OtherDerived>::run(tmp,other.derived());
273  this->swap(tmp);
274  return *this;
275  }
276 
277  #ifndef EIGEN_PARSED_BY_DOXYGEN
278  template<typename Lhs, typename Rhs>
279  inline SparseVector& operator=(const SparseSparseProduct<Lhs,Rhs>& product)
280  {
281  return Base::operator=(product);
282  }
283  #endif
284 
285  friend std::ostream & operator << (std::ostream & s, const SparseVector& m)
286  {
287  for (Index i=0; i<m.nonZeros(); ++i)
288  s << "(" << m.m_data.value(i) << "," << m.m_data.index(i) << ") ";
289  s << std::endl;
290  return s;
291  }
292 
294  inline ~SparseVector() {}
295 
297  Scalar sum() const;
298 
299  public:
300 
302  EIGEN_DEPRECATED void startFill(Index reserve)
303  {
304  setZero();
305  m_data.reserve(reserve);
306  }
307 
309  EIGEN_DEPRECATED Scalar& fill(Index r, Index c)
310  {
311  eigen_assert(r==0 || c==0);
312  return fill(IsColVector ? r : c);
313  }
314 
316  EIGEN_DEPRECATED Scalar& fill(Index i)
317  {
318  m_data.append(0, i);
319  return m_data.value(m_data.size()-1);
320  }
321 
323  EIGEN_DEPRECATED Scalar& fillrand(Index r, Index c)
324  {
325  eigen_assert(r==0 || c==0);
326  return fillrand(IsColVector ? r : c);
327  }
328 
330  EIGEN_DEPRECATED Scalar& fillrand(Index i)
331  {
332  return insert(i);
333  }
334 
336  EIGEN_DEPRECATED void endFill() {}
337 
338  // These two functions were here in the 3.1 release, so let's keep them in case some code rely on them.
340  EIGEN_DEPRECATED Storage& _data() { return m_data; }
342  EIGEN_DEPRECATED const Storage& _data() const { return m_data; }
343 
344 # ifdef EIGEN_SPARSEVECTOR_PLUGIN
345 # include EIGEN_SPARSEVECTOR_PLUGIN
346 # endif
347 
348 protected:
349 
350  static void check_template_parameters()
351  {
352  EIGEN_STATIC_ASSERT(NumTraits<StorageIndex>::IsSigned,THE_INDEX_TYPE_MUST_BE_A_SIGNED_TYPE);
353  EIGEN_STATIC_ASSERT((_Options&(ColMajor|RowMajor))==Options,INVALID_MATRIX_TEMPLATE_PARAMETERS);
354  }
355 
356  Storage m_data;
357  Index m_size;
358 };
359 
360 template<typename Scalar, int _Options, typename _StorageIndex>
361 class SparseVector<Scalar,_Options,_StorageIndex>::InnerIterator
362 {
363  public:
364  explicit InnerIterator(const SparseVector& vec, Index outer=0)
365  : m_data(vec.m_data), m_id(0), m_end(m_data.size())
366  {
367  EIGEN_UNUSED_VARIABLE(outer);
368  eigen_assert(outer==0);
369  }
370 
371  explicit InnerIterator(const internal::CompressedStorage<Scalar,StorageIndex>& data)
372  : m_data(data), m_id(0), m_end(m_data.size())
373  {}
374 
375  inline InnerIterator& operator++() { m_id++; return *this; }
376 
377  inline Scalar value() const { return m_data.value(m_id); }
378  inline Scalar& valueRef() { return const_cast<Scalar&>(m_data.value(m_id)); }
379 
380  inline StorageIndex index() const { return m_data.index(m_id); }
381  inline Index row() const { return IsColVector ? index() : 0; }
382  inline Index col() const { return IsColVector ? 0 : index(); }
383 
384  inline operator bool() const { return (m_id < m_end); }
385 
386  protected:
387  const internal::CompressedStorage<Scalar,StorageIndex>& m_data;
388  Index m_id;
389  const Index m_end;
390  private:
391  // If you get here, then you're not using the right InnerIterator type, e.g.:
392  // SparseMatrix<double,RowMajor> A;
393  // SparseMatrix<double>::InnerIterator it(A,0);
394  template<typename T> InnerIterator(const SparseMatrixBase<T>&,Index outer=0);
395 };
396 
397 template<typename Scalar, int _Options, typename _StorageIndex>
398 class SparseVector<Scalar,_Options,_StorageIndex>::ReverseInnerIterator
399 {
400  public:
401  explicit ReverseInnerIterator(const SparseVector& vec, Index outer=0)
402  : m_data(vec.m_data), m_id(m_data.size()), m_start(0)
403  {
404  EIGEN_UNUSED_VARIABLE(outer);
405  eigen_assert(outer==0);
406  }
407 
408  explicit ReverseInnerIterator(const internal::CompressedStorage<Scalar,StorageIndex>& data)
409  : m_data(data), m_id(m_data.size()), m_start(0)
410  {}
411 
412  inline ReverseInnerIterator& operator--() { m_id--; return *this; }
413 
414  inline Scalar value() const { return m_data.value(m_id-1); }
415  inline Scalar& valueRef() { return const_cast<Scalar&>(m_data.value(m_id-1)); }
416 
417  inline StorageIndex index() const { return m_data.index(m_id-1); }
418  inline Index row() const { return IsColVector ? index() : 0; }
419  inline Index col() const { return IsColVector ? 0 : index(); }
420 
421  inline operator bool() const { return (m_id > m_start); }
422 
423  protected:
424  const internal::CompressedStorage<Scalar,StorageIndex>& m_data;
425  Index m_id;
426  const Index m_start;
427 };
428 
429 namespace internal {
430 
431 template<typename _Scalar, int _Options, typename _Index>
432 struct evaluator<SparseVector<_Scalar,_Options,_Index> >
433  : evaluator_base<SparseVector<_Scalar,_Options,_Index> >
434 {
435  typedef SparseVector<_Scalar,_Options,_Index> SparseVectorType;
436  typedef typename SparseVectorType::InnerIterator InnerIterator;
437  typedef typename SparseVectorType::ReverseInnerIterator ReverseInnerIterator;
438 
439  enum {
440  CoeffReadCost = NumTraits<_Scalar>::ReadCost,
441  Flags = SparseVectorType::Flags
442  };
443 
444  explicit evaluator(const SparseVectorType &mat) : m_matrix(mat) {}
445 
446  inline Index nonZerosEstimate() const {
447  return m_matrix.nonZeros();
448  }
449 
450  operator SparseVectorType&() { return m_matrix.const_cast_derived(); }
451  operator const SparseVectorType&() const { return m_matrix; }
452 
453  const SparseVectorType &m_matrix;
454 };
455 
456 template< typename Dest, typename Src>
457 struct sparse_vector_assign_selector<Dest,Src,SVA_Inner> {
458  static void run(Dest& dst, const Src& src) {
459  eigen_internal_assert(src.innerSize()==src.size());
460  typedef internal::evaluator<Src> SrcEvaluatorType;
461  SrcEvaluatorType srcEval(src);
462  for(typename SrcEvaluatorType::InnerIterator it(srcEval, 0); it; ++it)
463  dst.insert(it.index()) = it.value();
464  }
465 };
466 
467 template< typename Dest, typename Src>
468 struct sparse_vector_assign_selector<Dest,Src,SVA_Outer> {
469  static void run(Dest& dst, const Src& src) {
470  eigen_internal_assert(src.outerSize()==src.size());
471  typedef internal::evaluator<Src> SrcEvaluatorType;
472  SrcEvaluatorType srcEval(src);
473  for(Index i=0; i<src.size(); ++i)
474  {
475  typename SrcEvaluatorType::InnerIterator it(srcEval, i);
476  if(it)
477  dst.insert(i) = it.value();
478  }
479  }
480 };
481 
482 template< typename Dest, typename Src>
483 struct sparse_vector_assign_selector<Dest,Src,SVA_RuntimeSwitch> {
484  static void run(Dest& dst, const Src& src) {
485  if(src.outerSize()==1) sparse_vector_assign_selector<Dest,Src,SVA_Inner>::run(dst, src);
486  else sparse_vector_assign_selector<Dest,Src,SVA_Outer>::run(dst, src);
487  }
488 };
489 
490 }
491 
492 } // end namespace Eigen
493 
494 #endif // EIGEN_SPARSEVECTOR_H
Definition: Constants.h:314
const unsigned int LvalueBit
Definition: Constants.h:130
Scalar & coeffRef(Index i)
Definition: SparseVector.h:121
Definition: LDLT.h:16
Index nonZeros() const
Definition: SparseVector.h:135
Eigen::Index Index
The interface type of indices.
Definition: EigenBase.h:37
const unsigned int RowMajorBit
Definition: Constants.h:53
~SparseVector()
Definition: SparseVector.h:294
void swap(SparseVector &other)
Definition: SparseVector.h:248
Scalar sum() const
Definition: SparseRedux.h:38
a sparse vector class
Definition: SparseUtil.h:70
Definition: Eigen_Colamd.h:54
Definition: Constants.h:312