Eigen  3.2.93
SparseVector.h
1 // This file is part of Eigen, a lightweight C++ template library
2 // for linear algebra.
3 //
4 // Copyright (C) 2008-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_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) | CompressedAccessBit,
44  SupportedAccessPatterns = InnerRandomAccessPattern
45  };
46 };
47 
48 // Sparse-Vector-Assignment kinds:
49 enum {
50  SVA_RuntimeSwitch,
51  SVA_Inner,
52  SVA_Outer
53 };
54 
55 template< typename Dest, typename Src,
56  int AssignmentKind = !bool(Src::IsVectorAtCompileTime) ? SVA_RuntimeSwitch
57  : Src::InnerSizeAtCompileTime==1 ? SVA_Outer
58  : SVA_Inner>
59 struct sparse_vector_assign_selector;
60 
61 }
62 
63 template<typename _Scalar, int _Options, typename _StorageIndex>
64 class SparseVector
65  : public SparseCompressedBase<SparseVector<_Scalar, _Options, _StorageIndex> >
66 {
67  typedef SparseCompressedBase<SparseVector> Base;
68  using Base::convert_index;
69  public:
70  EIGEN_SPARSE_PUBLIC_INTERFACE(SparseVector)
71  EIGEN_SPARSE_INHERIT_ASSIGNMENT_OPERATOR(SparseVector, +=)
72  EIGEN_SPARSE_INHERIT_ASSIGNMENT_OPERATOR(SparseVector, -=)
73 
74  typedef internal::CompressedStorage<Scalar,StorageIndex> Storage;
75  enum { IsColVector = internal::traits<SparseVector>::IsColVector };
76 
77  enum {
78  Options = _Options
79  };
80 
81  EIGEN_STRONG_INLINE Index rows() const { return IsColVector ? m_size : 1; }
82  EIGEN_STRONG_INLINE Index cols() const { return IsColVector ? 1 : m_size; }
83  EIGEN_STRONG_INLINE Index innerSize() const { return m_size; }
84  EIGEN_STRONG_INLINE Index outerSize() const { return 1; }
85 
86  EIGEN_STRONG_INLINE const Scalar* valuePtr() const { return m_data.valuePtr(); }
87  EIGEN_STRONG_INLINE Scalar* valuePtr() { return m_data.valuePtr(); }
88 
89  EIGEN_STRONG_INLINE const StorageIndex* innerIndexPtr() const { return m_data.indexPtr(); }
90  EIGEN_STRONG_INLINE StorageIndex* innerIndexPtr() { return m_data.indexPtr(); }
91 
92  inline const StorageIndex* outerIndexPtr() const { return 0; }
93  inline StorageIndex* outerIndexPtr() { return 0; }
94  inline const StorageIndex* innerNonZeroPtr() const { return 0; }
95  inline StorageIndex* innerNonZeroPtr() { return 0; }
96 
98  inline Storage& data() { return m_data; }
100  inline const Storage& data() const { return m_data; }
101 
102  inline Scalar coeff(Index row, Index col) const
103  {
104  eigen_assert(IsColVector ? (col==0 && row>=0 && row<m_size) : (row==0 && col>=0 && col<m_size));
105  return coeff(IsColVector ? row : col);
106  }
107  inline Scalar coeff(Index i) const
108  {
109  eigen_assert(i>=0 && i<m_size);
110  return m_data.at(StorageIndex(i));
111  }
112 
113  inline Scalar& coeffRef(Index row, Index col)
114  {
115  eigen_assert(IsColVector ? (col==0 && row>=0 && row<m_size) : (row==0 && col>=0 && col<m_size));
116  return coeffRef(IsColVector ? row : col);
117  }
118 
125  inline Scalar& coeffRef(Index i)
126  {
127  eigen_assert(i>=0 && i<m_size);
128 
129  return m_data.atWithInsertion(StorageIndex(i));
130  }
131 
132  public:
133 
134  typedef typename Base::InnerIterator InnerIterator;
135  typedef typename Base::ReverseInnerIterator ReverseInnerIterator;
136 
137  inline void setZero() { m_data.clear(); }
138 
140  inline Index nonZeros() const { return m_data.size(); }
141 
142  inline void startVec(Index outer)
143  {
144  EIGEN_UNUSED_VARIABLE(outer);
145  eigen_assert(outer==0);
146  }
147 
148  inline Scalar& insertBackByOuterInner(Index outer, Index inner)
149  {
150  EIGEN_UNUSED_VARIABLE(outer);
151  eigen_assert(outer==0);
152  return insertBack(inner);
153  }
154  inline Scalar& insertBack(Index i)
155  {
156  m_data.append(0, i);
157  return m_data.value(m_data.size()-1);
158  }
159 
160  Scalar& insertBackByOuterInnerUnordered(Index outer, Index inner)
161  {
162  EIGEN_UNUSED_VARIABLE(outer);
163  eigen_assert(outer==0);
164  return insertBackUnordered(inner);
165  }
166  inline Scalar& insertBackUnordered(Index i)
167  {
168  m_data.append(0, i);
169  return m_data.value(m_data.size()-1);
170  }
171 
172  inline Scalar& insert(Index row, Index col)
173  {
174  eigen_assert(IsColVector ? (col==0 && row>=0 && row<m_size) : (row==0 && col>=0 && col<m_size));
175 
176  Index inner = IsColVector ? row : col;
177  Index outer = IsColVector ? col : row;
178  EIGEN_ONLY_USED_FOR_DEBUG(outer);
179  eigen_assert(outer==0);
180  return insert(inner);
181  }
182  Scalar& insert(Index i)
183  {
184  eigen_assert(i>=0 && i<m_size);
185 
186  Index startId = 0;
187  Index p = Index(m_data.size()) - 1;
188  // TODO smart realloc
189  m_data.resize(p+2,1);
190 
191  while ( (p >= startId) && (m_data.index(p) > i) )
192  {
193  m_data.index(p+1) = m_data.index(p);
194  m_data.value(p+1) = m_data.value(p);
195  --p;
196  }
197  m_data.index(p+1) = convert_index(i);
198  m_data.value(p+1) = 0;
199  return m_data.value(p+1);
200  }
201 
204  inline void reserve(Index reserveSize) { m_data.reserve(reserveSize); }
205 
206 
207  inline void finalize() {}
208 
210  void prune(const Scalar& reference, const RealScalar& epsilon = NumTraits<RealScalar>::dummy_precision())
211  {
212  m_data.prune(reference,epsilon);
213  }
214 
223  void resize(Index rows, Index cols)
224  {
225  eigen_assert((IsColVector ? cols : rows)==1 && "Outer dimension must equal 1");
226  resize(IsColVector ? rows : cols);
227  }
228 
233  void resize(Index newSize)
234  {
235  m_size = newSize;
236  m_data.clear();
237  }
238 
246  void conservativeResize(Index newSize)
247  {
248  if (newSize < m_size)
249  {
250  Index i = 0;
251  while (i<m_data.size() && m_data.index(i)<newSize) ++i;
252  m_data.resize(i);
253  }
254  m_size = newSize;
255  }
256 
257  void resizeNonZeros(Index size) { m_data.resize(size); }
258 
259  inline SparseVector() : m_size(0) { check_template_parameters(); resize(0); }
260 
261  explicit inline SparseVector(Index size) : m_size(0) { check_template_parameters(); resize(size); }
262 
263  inline SparseVector(Index rows, Index cols) : m_size(0) { check_template_parameters(); resize(rows,cols); }
264 
265  template<typename OtherDerived>
266  inline SparseVector(const SparseMatrixBase<OtherDerived>& other)
267  : m_size(0)
268  {
269  #ifdef EIGEN_SPARSE_CREATE_TEMPORARY_PLUGIN
270  EIGEN_SPARSE_CREATE_TEMPORARY_PLUGIN
271  #endif
272  check_template_parameters();
273  *this = other.derived();
274  }
275 
276  inline SparseVector(const SparseVector& other)
277  : Base(other), m_size(0)
278  {
279  check_template_parameters();
280  *this = other.derived();
281  }
282 
287  inline void swap(SparseVector& other)
288  {
289  std::swap(m_size, other.m_size);
290  m_data.swap(other.m_data);
291  }
292 
293  inline SparseVector& operator=(const SparseVector& other)
294  {
295  if (other.isRValue())
296  {
297  swap(other.const_cast_derived());
298  }
299  else
300  {
301  resize(other.size());
302  m_data = other.m_data;
303  }
304  return *this;
305  }
306 
307  template<typename OtherDerived>
308  inline SparseVector& operator=(const SparseMatrixBase<OtherDerived>& other)
309  {
310  SparseVector tmp(other.size());
311  internal::sparse_vector_assign_selector<SparseVector,OtherDerived>::run(tmp,other.derived());
312  this->swap(tmp);
313  return *this;
314  }
315 
316  #ifndef EIGEN_PARSED_BY_DOXYGEN
317  template<typename Lhs, typename Rhs>
318  inline SparseVector& operator=(const SparseSparseProduct<Lhs,Rhs>& product)
319  {
320  return Base::operator=(product);
321  }
322  #endif
323 
324  friend std::ostream & operator << (std::ostream & s, const SparseVector& m)
325  {
326  for (Index i=0; i<m.nonZeros(); ++i)
327  s << "(" << m.m_data.value(i) << "," << m.m_data.index(i) << ") ";
328  s << std::endl;
329  return s;
330  }
331 
333  inline ~SparseVector() {}
334 
336  Scalar sum() const;
337 
338  public:
339 
341  EIGEN_DEPRECATED void startFill(Index reserve)
342  {
343  setZero();
344  m_data.reserve(reserve);
345  }
346 
348  EIGEN_DEPRECATED Scalar& fill(Index r, Index c)
349  {
350  eigen_assert(r==0 || c==0);
351  return fill(IsColVector ? r : c);
352  }
353 
355  EIGEN_DEPRECATED Scalar& fill(Index i)
356  {
357  m_data.append(0, i);
358  return m_data.value(m_data.size()-1);
359  }
360 
362  EIGEN_DEPRECATED Scalar& fillrand(Index r, Index c)
363  {
364  eigen_assert(r==0 || c==0);
365  return fillrand(IsColVector ? r : c);
366  }
367 
369  EIGEN_DEPRECATED Scalar& fillrand(Index i)
370  {
371  return insert(i);
372  }
373 
375  EIGEN_DEPRECATED void endFill() {}
376 
377  // These two functions were here in the 3.1 release, so let's keep them in case some code rely on them.
379  EIGEN_DEPRECATED Storage& _data() { return m_data; }
381  EIGEN_DEPRECATED const Storage& _data() const { return m_data; }
382 
383 # ifdef EIGEN_SPARSEVECTOR_PLUGIN
384 # include EIGEN_SPARSEVECTOR_PLUGIN
385 # endif
386 
387 protected:
388 
389  static void check_template_parameters()
390  {
391  EIGEN_STATIC_ASSERT(NumTraits<StorageIndex>::IsSigned,THE_INDEX_TYPE_MUST_BE_A_SIGNED_TYPE);
392  EIGEN_STATIC_ASSERT((_Options&(ColMajor|RowMajor))==Options,INVALID_MATRIX_TEMPLATE_PARAMETERS);
393  }
394 
395  Storage m_data;
396  Index m_size;
397 };
398 
399 namespace internal {
400 
401 template<typename _Scalar, int _Options, typename _Index>
402 struct evaluator<SparseVector<_Scalar,_Options,_Index> >
403  : evaluator_base<SparseVector<_Scalar,_Options,_Index> >
404 {
405  typedef SparseVector<_Scalar,_Options,_Index> SparseVectorType;
406  typedef typename SparseVectorType::InnerIterator InnerIterator;
407  typedef typename SparseVectorType::ReverseInnerIterator ReverseInnerIterator;
408 
409  enum {
410  CoeffReadCost = NumTraits<_Scalar>::ReadCost,
411  Flags = SparseVectorType::Flags
412  };
413 
414  explicit evaluator(const SparseVectorType &mat) : m_matrix(mat)
415  {
416  EIGEN_INTERNAL_CHECK_COST_VALUE(CoeffReadCost);
417  }
418 
419  inline Index nonZerosEstimate() const {
420  return m_matrix.nonZeros();
421  }
422 
423  operator SparseVectorType&() { return m_matrix.const_cast_derived(); }
424  operator const SparseVectorType&() const { return m_matrix; }
425 
426  const SparseVectorType &m_matrix;
427 };
428 
429 template< typename Dest, typename Src>
430 struct sparse_vector_assign_selector<Dest,Src,SVA_Inner> {
431  static void run(Dest& dst, const Src& src) {
432  eigen_internal_assert(src.innerSize()==src.size());
433  typedef internal::evaluator<Src> SrcEvaluatorType;
434  SrcEvaluatorType srcEval(src);
435  for(typename SrcEvaluatorType::InnerIterator it(srcEval, 0); it; ++it)
436  dst.insert(it.index()) = it.value();
437  }
438 };
439 
440 template< typename Dest, typename Src>
441 struct sparse_vector_assign_selector<Dest,Src,SVA_Outer> {
442  static void run(Dest& dst, const Src& src) {
443  eigen_internal_assert(src.outerSize()==src.size());
444  typedef internal::evaluator<Src> SrcEvaluatorType;
445  SrcEvaluatorType srcEval(src);
446  for(Index i=0; i<src.size(); ++i)
447  {
448  typename SrcEvaluatorType::InnerIterator it(srcEval, i);
449  if(it)
450  dst.insert(i) = it.value();
451  }
452  }
453 };
454 
455 template< typename Dest, typename Src>
456 struct sparse_vector_assign_selector<Dest,Src,SVA_RuntimeSwitch> {
457  static void run(Dest& dst, const Src& src) {
458  if(src.outerSize()==1) sparse_vector_assign_selector<Dest,Src,SVA_Inner>::run(dst, src);
459  else sparse_vector_assign_selector<Dest,Src,SVA_Outer>::run(dst, src);
460  }
461 };
462 
463 }
464 
465 } // end namespace Eigen
466 
467 #endif // EIGEN_SPARSEVECTOR_H
Index nonZeros() const
Definition: SparseVector.h:140
Definition: Constants.h:320
const unsigned int CompressedAccessBit
Definition: Constants.h:186
const unsigned int LvalueBit
Definition: Constants.h:139
Scalar & coeffRef(Index i)
Definition: SparseVector.h:125
Namespace containing all symbols from the Eigen library.
Definition: Core:271
Holds information about the various numeric (i.e. scalar) types allowed by Eigen. ...
Definition: NumTraits.h:167
void conservativeResize(Index newSize)
Definition: SparseVector.h:246
Derived & derived()
Definition: EigenBase.h:44
Eigen::Index Index
The interface type of indices.
Definition: EigenBase.h:37
const unsigned int RowMajorBit
Definition: Constants.h:61
~SparseVector()
Definition: SparseVector.h:333
void swap(SparseVector &other)
Definition: SparseVector.h:287
Index size() const
Definition: SparseMatrixBase.h:161
Base class of any sparse matrices or sparse expressions.
Definition: ForwardDeclarations.h:281
a sparse vector class
Definition: SparseUtil.h:54
EIGEN_DEFAULT_DENSE_INDEX_TYPE Index
The Index type as used for the API.
Definition: XprHelper.h:35
void resize(Index newSize)
Definition: SparseVector.h:233
void resize(Index rows, Index cols)
Definition: SparseVector.h:223
Definition: Eigen_Colamd.h:50
Definition: Constants.h:322
const int Dynamic
Definition: Constants.h:21
void prune(const Scalar &reference, const RealScalar &epsilon=NumTraits< RealScalar >::dummy_precision())
Definition: SparseVector.h:210