Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
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// SPDX-License-Identifier: MPL-2.0
10
11#ifndef EIGEN_SPARSEVECTOR_H
12#define EIGEN_SPARSEVECTOR_H
13
14// IWYU pragma: private
15#include "./InternalHeaderCheck.h"
16
17namespace Eigen {
18
31
32namespace internal {
33template <typename Scalar_, int Options_, typename StorageIndex_>
34struct traits<SparseVector<Scalar_, Options_, StorageIndex_> > {
35 using Scalar = Scalar_;
36 using StorageIndex = StorageIndex_;
37 using StorageKind = Sparse;
38 using XprKind = MatrixXpr;
39 enum {
40 IsColVector = (Options_ & RowMajorBit) ? 0 : 1,
41
42 RowsAtCompileTime = IsColVector ? Dynamic : 1,
43 ColsAtCompileTime = IsColVector ? 1 : Dynamic,
44 MaxRowsAtCompileTime = RowsAtCompileTime,
45 MaxColsAtCompileTime = ColsAtCompileTime,
46 Flags = Options_ | NestByRefBit | LvalueBit | (IsColVector ? 0 : RowMajorBit) | CompressedAccessBit,
47 SupportedAccessPatterns = InnerRandomAccessPattern
48 };
49};
50
51// Sparse-Vector-Assignment kinds:
52enum { SVA_RuntimeSwitch, SVA_Inner, SVA_Outer };
53
54template <typename Dest, typename Src,
55 int AssignmentKind = !bool(Src::IsVectorAtCompileTime) ? SVA_RuntimeSwitch
56 : Src::InnerSizeAtCompileTime == 1 ? SVA_Outer
57 : SVA_Inner>
58struct sparse_vector_assign_selector;
59
60} // namespace internal
61
62template <typename Scalar_, int Options_, typename StorageIndex_>
63class SparseVector : public SparseCompressedBase<SparseVector<Scalar_, Options_, StorageIndex_> > {
65 using Base::convert_index;
66
67 public:
68 EIGEN_SPARSE_PUBLIC_INTERFACE(SparseVector)
69 EIGEN_SPARSE_INHERIT_ASSIGNMENT_OPERATOR(SparseVector, +=)
70 EIGEN_SPARSE_INHERIT_ASSIGNMENT_OPERATOR(SparseVector, -=)
71
72 using Storage = internal::CompressedStorage<Scalar, StorageIndex>;
73 enum { IsColVector = internal::traits<SparseVector>::IsColVector };
74
75 enum { Options = Options_ };
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.valuePtr(); }
83 EIGEN_STRONG_INLINE Scalar* valuePtr() { return m_data.valuePtr(); }
84
85 EIGEN_STRONG_INLINE const StorageIndex* innerIndexPtr() const { return m_data.indexPtr(); }
86 EIGEN_STRONG_INLINE StorageIndex* innerIndexPtr() { return m_data.indexPtr(); }
87
88 inline const StorageIndex* outerIndexPtr() const { return 0; }
89 inline StorageIndex* outerIndexPtr() { return 0; }
90 inline const StorageIndex* innerNonZeroPtr() const { return 0; }
91 inline StorageIndex* innerNonZeroPtr() { return 0; }
92
94 constexpr Storage& data() { return m_data; }
96 constexpr const Storage& data() const { return m_data; }
97
98 inline Scalar coeff(Index row, Index col) const {
99 eigen_assert(IsColVector ? (col == 0 && row >= 0 && row < m_size) : (row == 0 && col >= 0 && col < m_size));
100 return coeff(IsColVector ? row : col);
101 }
102 inline Scalar coeff(Index i) const {
103 eigen_assert(i >= 0 && i < m_size);
104 return m_data.at(StorageIndex(i));
105 }
106
107 inline Scalar& coeffRef(Index row, Index col) {
108 eigen_assert(IsColVector ? (col == 0 && row >= 0 && row < m_size) : (row == 0 && col >= 0 && col < m_size));
109 return coeffRef(IsColVector ? row : col);
110 }
111
118 inline Scalar& coeffRef(Index i) {
119 eigen_assert(i >= 0 && i < m_size);
120
121 return m_data.atWithInsertion(StorageIndex(i));
122 }
123
124 public:
125 using InnerIterator = typename Base::InnerIterator;
126 using ReverseInnerIterator = typename Base::ReverseInnerIterator;
127
128 inline void setZero() { m_data.clear(); }
129
131 inline Index nonZeros() const { return m_data.size(); }
132
133 inline void startVec(Index outer) {
134 EIGEN_UNUSED_VARIABLE(outer);
135 eigen_assert(outer == 0);
136 }
137
138 inline Scalar& insertBackByOuterInner(Index outer, Index inner) {
139 EIGEN_UNUSED_VARIABLE(outer);
140 eigen_assert(outer == 0);
141 return insertBack(inner);
142 }
143 inline Scalar& insertBack(Index i) {
144 m_data.append(Scalar(0), i);
145 return m_data.value(m_data.size() - 1);
146 }
147
148 Scalar& insertBackByOuterInnerUnordered(Index outer, Index inner) {
149 EIGEN_UNUSED_VARIABLE(outer);
150 eigen_assert(outer == 0);
151 return insertBackUnordered(inner);
152 }
153 inline Scalar& insertBackUnordered(Index i) {
154 m_data.append(Scalar(0), i);
155 return m_data.value(m_data.size() - 1);
156 }
157
158 inline Scalar& insert(Index row, Index col) {
159 eigen_assert(IsColVector ? (col == 0 && row >= 0 && row < m_size) : (row == 0 && col >= 0 && col < m_size));
160
161 Index inner = IsColVector ? row : col;
162 Index outer = IsColVector ? col : row;
163 EIGEN_ONLY_USED_FOR_DEBUG(outer);
164 eigen_assert(outer == 0);
165 return insert(inner);
166 }
167 Scalar& insert(Index i) {
168 eigen_assert(i >= 0 && i < m_size);
169
170 Index startId = 0;
171 Index p = Index(m_data.size()) - 1;
172 // TODO: implement smart reallocation.
173 m_data.resize(p + 2, 1);
174
175 while ((p >= startId) && (m_data.index(p) > i)) {
176 m_data.index(p + 1) = m_data.index(p);
177 m_data.value(p + 1) = internal::move_if_assignable(m_data.value(p));
178 --p;
179 }
180 m_data.index(p + 1) = convert_index(i);
181 m_data.value(p + 1) = Scalar(0);
182 return m_data.value(p + 1);
183 }
184
185 inline void reserve(Index reserveSize) { m_data.reserve(reserveSize); }
186
187 inline void finalize() {}
188
190 Index prune(const Scalar& reference, const RealScalar& epsilon = NumTraits<RealScalar>::dummy_precision()) {
191 return prune([&](const Scalar& val) { return !internal::isMuchSmallerThan(val, reference, epsilon); });
192 }
193
201 template <class F>
202 Index prune(F&& keep_predicate) {
203 Index k = 0;
204 Index n = m_data.size();
205 for (Index i = 0; i < n; ++i) {
206 if (keep_predicate(m_data.value(i))) {
207 // Entries in front of the first dropped one are already in place, where a self-move would leave them
208 // unspecified. A trivially copyable scalar is assigned anyway, which costs less than the branch.
209 if (std::is_trivially_copyable<Scalar>::value || k != i) {
210 m_data.value(k) = internal::move_if_assignable(m_data.value(i));
211 m_data.index(k) = m_data.index(i);
212 }
213 ++k;
214 }
215 }
216 m_data.resize(k);
217 return k;
218 }
219
228 void resize(Index rows, Index cols) {
229 eigen_assert((IsColVector ? cols : rows) == 1 && "Outer dimension must equal 1");
230 resize(IsColVector ? rows : cols);
231 }
232
234 void resize(NoChange_t, Index cols) { resize(rows(), cols); }
235
237 void resize(Index rows, NoChange_t) { resize(rows, cols()); }
238
243 void resize(Index newSize) {
244 m_size = newSize;
245 m_data.clear();
246 }
247
255 void conservativeResize(Index newSize) {
256 if (newSize < m_size) {
257 Index i = 0;
258 while (i < m_data.size() && m_data.index(i) < newSize) ++i;
259 m_data.resize(i);
260 }
261 m_size = newSize;
262 }
263
264 void resizeNonZeros(Index size) { m_data.resize(size); }
265
266 inline SparseVector() : m_size(0) { resize(0); }
267
268 explicit inline SparseVector(Index size) : m_size(0) { resize(size); }
269
270 inline SparseVector(Index rows, Index cols) : m_size(0) { resize(rows, cols); }
271
272 template <typename OtherDerived>
273 inline SparseVector(const SparseMatrixBase<OtherDerived>& other) : m_size(0) {
274#ifdef EIGEN_SPARSE_CREATE_TEMPORARY_PLUGIN
275 EIGEN_SPARSE_CREATE_TEMPORARY_PLUGIN
276#endif
277 *this = other.derived();
278 }
279
280 inline SparseVector(const SparseVector& other) : Base(other), m_size(0) { *this = other.derived(); }
281
286 inline void swap(SparseVector& other) {
287 std::swap(m_size, other.m_size);
288 m_data.swap(other.m_data);
289 }
290 friend EIGEN_DEVICE_FUNC void swap(SparseVector& a, SparseVector& b) { a.swap(b); }
291
292 template <int OtherOptions>
293 inline void swap(SparseMatrix<Scalar, OtherOptions, StorageIndex>& other) {
294 eigen_assert(other.outerSize() == 1);
295 other.makeCompressed();
296 std::swap(m_size, other.m_innerSize);
297 m_data.swap(other.m_data);
298 other.m_outerIndex[1] = convert_index(other.m_data.size());
299 }
300 template <int OtherOptions>
301 friend EIGEN_DEVICE_FUNC void swap(SparseVector& a, SparseMatrix<Scalar, OtherOptions, StorageIndex>& b) {
302 a.swap(b);
303 }
304 template <int OtherOptions>
305 friend EIGEN_DEVICE_FUNC void swap(SparseMatrix<Scalar, OtherOptions, StorageIndex>& a, SparseVector& b) {
306 b.swap(a);
307 }
308
309 inline SparseVector& operator=(const SparseVector& other) {
310 if (other.isRValue()) {
311 swap(other.const_cast_derived());
312 } else if (this != &other) {
313 // resize() clears m_data, so a self-assignment would copy an empty vector.
314 resize(other.size());
315 m_data = other.m_data;
316 }
317 return *this;
318 }
319
320 template <typename OtherDerived>
321 inline SparseVector& operator=(const SparseMatrixBase<OtherDerived>& other) {
322 SparseVector tmp(other.size());
323 internal::sparse_vector_assign_selector<SparseVector, OtherDerived>::run(tmp, other.derived());
324 this->swap(tmp);
325 return *this;
326 }
327
328 inline SparseVector(SparseVector&& other) : SparseVector() { this->swap(other); }
329
330 template <typename OtherDerived>
331 inline SparseVector(SparseCompressedBase<OtherDerived>&& other) : SparseVector() {
332 *this = other.derived().markAsRValue();
333 }
334
335 inline SparseVector& operator=(SparseVector&& other) {
336 this->swap(other);
337 return *this;
338 }
339
340 template <typename OtherDerived>
341 inline SparseVector& operator=(SparseCompressedBase<OtherDerived>&& other) {
342 *this = other.derived().markAsRValue();
343 return *this;
344 }
345
346#ifndef EIGEN_NO_IO
347 friend std::ostream& operator<<(std::ostream& s, const SparseVector& m) {
348 for (Index i = 0; i < m.nonZeros(); ++i) s << "(" << m.m_data.value(i) << "," << m.m_data.index(i) << ") ";
349 s << std::endl;
350 return s;
351 }
352#endif
353
355 Scalar sum() const;
356
357 public:
359 EIGEN_DEPRECATED_WITH_REASON("Use .setZero() and .reserve() instead.") void startFill(Index reserve) {
360 setZero();
361 m_data.reserve(reserve);
362 }
363
365 EIGEN_DEPRECATED_WITH_REASON("Use .insertBack() instead.") Scalar& fill(Index r, Index c) {
366 eigen_assert(r == 0 || c == 0);
367 return fill(IsColVector ? r : c);
368 }
369
371 EIGEN_DEPRECATED_WITH_REASON("Use .insertBack() instead.") Scalar& fill(Index i) {
372 m_data.append(Scalar(0), i);
373 return m_data.value(m_data.size() - 1);
374 }
375
377 EIGEN_DEPRECATED_WITH_REASON("Use .insert() instead.") Scalar& fillrand(Index r, Index c) {
378 eigen_assert(r == 0 || c == 0);
379 return fillrand(IsColVector ? r : c);
380 }
381
383 EIGEN_DEPRECATED_WITH_REASON("Use .insert() instead.") Scalar& fillrand(Index i) { return insert(i); }
384
386 EIGEN_DEPRECATED_WITH_REASON("Use .finalize() instead.") void endFill() {}
387
388 // These two functions were here in the 3.1 release, so let's keep them in case some code relies on them.
390 EIGEN_DEPRECATED_WITH_REASON("Use .data() instead.") Storage& _data() { return m_data; }
392 EIGEN_DEPRECATED_WITH_REASON("Use .data() instead.") const Storage& _data() const { return m_data; }
393
394#ifdef EIGEN_SPARSEVECTOR_PLUGIN
395#include EIGEN_SPARSEVECTOR_PLUGIN
396#endif
397
398 protected:
399 EIGEN_STATIC_ASSERT(NumTraits<StorageIndex>::IsSigned, THE_INDEX_TYPE_MUST_BE_A_SIGNED_TYPE)
400 EIGEN_STATIC_ASSERT((Options_ & (ColMajor | RowMajor)) == Options, INVALID_MATRIX_TEMPLATE_PARAMETERS)
401
402 Storage m_data;
403 Index m_size;
404};
405
406namespace internal {
407
408template <typename Scalar_, int Options_, typename Index_>
409struct evaluator<SparseVector<Scalar_, Options_, Index_> > : evaluator_base<SparseVector<Scalar_, Options_, Index_> > {
410 using SparseVectorType = SparseVector<Scalar_, Options_, Index_>;
411 using Base = evaluator_base<SparseVectorType>;
412 using InnerIterator = typename SparseVectorType::InnerIterator;
413 using ReverseInnerIterator = typename SparseVectorType::ReverseInnerIterator;
414
415 enum { CoeffReadCost = NumTraits<Scalar_>::ReadCost, Flags = SparseVectorType::Flags };
416
417 evaluator() : Base() {}
418
419 explicit evaluator(const SparseVectorType& mat) : m_matrix(&mat) { EIGEN_INTERNAL_CHECK_COST_VALUE(CoeffReadCost); }
420
421 inline Index nonZerosEstimate() const { return m_matrix->nonZeros(); }
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
429template <typename Dest, typename Src>
430struct 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 using SrcEvaluatorType = internal::evaluator<Src>;
434 SrcEvaluatorType srcEval(src);
435 for (typename SrcEvaluatorType::InnerIterator it(srcEval, 0); it; ++it) dst.insert(it.index()) = it.value();
436 }
437};
438
439template <typename Dest, typename Src>
440struct sparse_vector_assign_selector<Dest, Src, SVA_Outer> {
441 static void run(Dest& dst, const Src& src) {
442 eigen_internal_assert(src.outerSize() == src.size());
443 using SrcEvaluatorType = internal::evaluator<Src>;
444 SrcEvaluatorType srcEval(src);
445 for (Index i = 0; i < src.size(); ++i) {
446 typename SrcEvaluatorType::InnerIterator it(srcEval, i);
447 if (it) dst.insert(i) = it.value();
448 }
449 }
450};
451
452template <typename Dest, typename Src>
453struct sparse_vector_assign_selector<Dest, Src, SVA_RuntimeSwitch> {
454 static void run(Dest& dst, const Src& src) {
455 if (src.outerSize() == 1)
456 sparse_vector_assign_selector<Dest, Src, SVA_Inner>::run(dst, src);
457 else
458 sparse_vector_assign_selector<Dest, Src, SVA_Outer>::run(dst, src);
459 }
460};
461
462} // namespace internal
463
464// Specialization for SparseVector.
465// Serializes [size, numNonZeros, innerIndices, values].
466template <typename Scalar, int Options, typename StorageIndex>
467class Serializer<SparseVector<Scalar, Options, StorageIndex>, void> {
468 public:
469 using SparseMat = SparseVector<Scalar, Options, StorageIndex>;
470
471 struct Header {
472 typename SparseMat::Index size;
473 Index num_non_zeros;
474 };
475
476 EIGEN_DEVICE_FUNC size_t size(const SparseMat& value) const {
477 return sizeof(Header) + (sizeof(Scalar) + sizeof(StorageIndex)) * value.nonZeros();
478 }
479
480 EIGEN_DEVICE_FUNC uint8_t* serialize(uint8_t* dest, uint8_t* end, const SparseMat& value) {
481 if (EIGEN_PREDICT_FALSE(dest == nullptr)) return nullptr;
482 if (EIGEN_PREDICT_FALSE(dest + size(value) > end)) return nullptr;
483
484 const size_t header_bytes = sizeof(Header);
485 Header header = {value.innerSize(), value.nonZeros()};
486 EIGEN_USING_STD(memcpy)
487 memcpy(dest, &header, header_bytes);
488 dest += header_bytes;
489
490 // Inner indices.
491 std::size_t data_bytes = sizeof(StorageIndex) * header.num_non_zeros;
492 if (data_bytes != 0) {
493 memcpy(dest, value.innerIndexPtr(), data_bytes);
494 }
495 dest += data_bytes;
496
497 // Values.
498 data_bytes = sizeof(Scalar) * header.num_non_zeros;
499 if (data_bytes != 0) {
500 memcpy(dest, value.valuePtr(), data_bytes);
501 }
502 dest += data_bytes;
503
504 return dest;
505 }
506
507 EIGEN_DEVICE_FUNC const uint8_t* deserialize(const uint8_t* src, const uint8_t* end, SparseMat& value) const {
508 if (EIGEN_PREDICT_FALSE(src == nullptr)) return nullptr;
509 if (EIGEN_PREDICT_FALSE(src + sizeof(Header) > end)) return nullptr;
510
511 const size_t header_bytes = sizeof(Header);
512 Header header;
513 EIGEN_USING_STD(memcpy)
514 memcpy(&header, src, header_bytes);
515 src += header_bytes;
516
517 // The header is untrusted: check the sizes before allocating, and every inner index after copying.
518 if (EIGEN_PREDICT_FALSE(header.size < 0 || header.num_non_zeros < 0 ||
519 header.num_non_zeros > NumTraits<StorageIndex>::highest() ||
520 static_cast<numext::uint64_t>(header.num_non_zeros) >
521 static_cast<numext::uint64_t>(end - src) / (sizeof(StorageIndex) + sizeof(Scalar))))
522 return nullptr;
523
524 value.setZero();
525 value.resize(header.size);
526 value.resizeNonZeros(header.num_non_zeros);
527
528 // Inner indices.
529 std::size_t data_bytes = sizeof(StorageIndex) * header.num_non_zeros;
530 if (data_bytes != 0) {
531 memcpy(value.innerIndexPtr(), src, data_bytes);
532 }
533 src += data_bytes;
534
535 // Values.
536 data_bytes = sizeof(Scalar) * header.num_non_zeros;
537 if (data_bytes != 0) {
538 memcpy(value.valuePtr(), src, data_bytes);
539 }
540 src += data_bytes;
541
542 for (Index k = 0; k < header.num_non_zeros; ++k) {
543 if (EIGEN_PREDICT_FALSE(value.innerIndexPtr()[k] < 0 || value.innerIndexPtr()[k] >= header.size)) {
544 value.resize(0);
545 return nullptr;
546 }
547 }
548 return src;
549 }
550};
551
552} // end namespace Eigen
553
554#endif // EIGEN_SPARSEVECTOR_H
An InnerIterator allows to loop over the element of any matrix expression.
Definition CoreIterators.h:38
typename NumTraits< Scalar >::Real RealScalar
Definition SparseMatrixBase.h:128
constexpr RowXpr row(Index i)
Definition SparseMatrixBase.h:1095
typename internal::traits< SparseVector< Scalar_, Options_, StorageIndex_ > >::StorageIndex StorageIndex
Definition SparseMatrixBase.h:45
constexpr ColXpr col(Index i)
Definition SparseMatrixBase.h:1082
a sparse vector class
Definition SparseVector.h:63
void resize(NoChange_t, Index cols)
Definition SparseVector.h:234
void resize(Index rows, NoChange_t)
Definition SparseVector.h:237
void conservativeResize(Index newSize)
Definition SparseVector.h:255
Scalar & coeffRef(Index i)
Definition SparseVector.h:118
Index prune(const Scalar &reference, const RealScalar &epsilon=NumTraits< RealScalar >::dummy_precision())
Definition SparseVector.h:190
void resize(Index rows, Index cols)
Definition SparseVector.h:228
void swap(SparseVector &other)
Definition SparseVector.h:286
Index prune(F &&keep_predicate)
Prunes the entries of the vector based on a predicate
Definition SparseVector.h:202
Index nonZeros() const
Definition SparseVector.h:131
void resize(Index newSize)
Definition SparseVector.h:243
Scalar sum() const
Definition SparseRedux.h:41
constexpr unsigned int LvalueBit
Definition Constants.h:149
constexpr unsigned int RowMajorBit
Definition Constants.h:71
constexpr unsigned int CompressedAccessBit
Definition Constants.h:196