Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
SparseMatrix.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// SPDX-License-Identifier: MPL-2.0
10
11#ifndef EIGEN_SPARSEMATRIX_H
12#define EIGEN_SPARSEMATRIX_H
13
14// IWYU pragma: private
15#include "./InternalHeaderCheck.h"
16
17namespace Eigen {
18
49
50namespace internal {
51template <typename Scalar_, int Options_, typename StorageIndex_>
52struct traits<SparseMatrix<Scalar_, Options_, StorageIndex_>> {
53 using Scalar = Scalar_;
54 using StorageIndex = StorageIndex_;
55 using StorageKind = Sparse;
56 using XprKind = MatrixXpr;
57 enum {
58 RowsAtCompileTime = Dynamic,
59 ColsAtCompileTime = Dynamic,
60 MaxRowsAtCompileTime = Dynamic,
61 MaxColsAtCompileTime = Dynamic,
62 Options = Options_,
63 Flags = Options_ | NestByRefBit | LvalueBit | CompressedAccessBit,
64 SupportedAccessPatterns = InnerRandomAccessPattern
65 };
66};
67
68template <typename Scalar_, int Options_, typename StorageIndex_, int DiagIndex>
69struct traits<Diagonal<SparseMatrix<Scalar_, Options_, StorageIndex_>, DiagIndex>> {
70 // No member may be named MatrixType or XprType: expression traits derive from this class as
71 // traits<Xpr<MatrixType>> : traits<MatrixType>, and MSVC in permissive mode looks unqualified names up in dependent
72 // bases, where such a member hides the template parameter.
73 using Scalar = Scalar_;
74 using StorageKind = Dense;
75 using StorageIndex = StorageIndex_;
76 using XprKind = MatrixXpr;
77
78 enum {
79 RowsAtCompileTime = Dynamic,
80 ColsAtCompileTime = 1,
81 MaxRowsAtCompileTime = Dynamic,
82 MaxColsAtCompileTime = 1,
83 Flags = LvalueBit
84 };
85};
86
87template <typename Scalar_, int Options_, typename StorageIndex_, int DiagIndex>
88struct traits<Diagonal<const SparseMatrix<Scalar_, Options_, StorageIndex_>, DiagIndex>>
89 : public traits<Diagonal<SparseMatrix<Scalar_, Options_, StorageIndex_>, DiagIndex>> {
90 enum { Flags = 0 };
91};
92
93template <typename StorageIndex>
94struct sparse_reserve_op {
95 EIGEN_DEVICE_FUNC sparse_reserve_op(Index begin, Index end, Index size) {
96 Index range = numext::mini(end - begin, size);
97 m_begin = begin;
98 m_end = begin + range;
99 m_val = StorageIndex(size / range);
100 m_remainder = StorageIndex(size % range);
101 }
102 template <typename IndexType>
103 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE StorageIndex operator()(IndexType i) const {
104 if ((i >= m_begin) && (i < m_end))
105 return m_val + ((i - m_begin) < m_remainder ? 1 : 0);
106 else
107 return 0;
108 }
109 StorageIndex m_val, m_remainder;
110 Index m_begin, m_end;
111};
112
113template <typename Scalar>
114struct functor_traits<sparse_reserve_op<Scalar>> {
115 enum { Cost = 1, PacketAccess = false, IsRepeatable = true };
116};
117
118} // end namespace internal
119
120template <typename Scalar_, int Options_, typename StorageIndex_>
121class SparseMatrix : public SparseCompressedBase<SparseMatrix<Scalar_, Options_, StorageIndex_>> {
123 using Base::convert_index;
124 friend class SparseVector<Scalar_, 0, StorageIndex_>;
125 friend class SparseVector<Scalar_, RowMajor, StorageIndex_>;
126 template <typename, typename, typename, typename, typename>
127 friend struct internal::Assignment;
128
129 public:
130 using Base::isCompressed;
131 using Base::nonZeros;
132 EIGEN_SPARSE_PUBLIC_INTERFACE(SparseMatrix)
133 using Base::operator+=;
134 using Base::operator-=;
135
137 using DiagonalReturnType = Diagonal<SparseMatrix>;
138 using ConstDiagonalReturnType = Diagonal<const SparseMatrix>;
139 using InnerIterator = typename Base::InnerIterator;
140 using ReverseInnerIterator = typename Base::ReverseInnerIterator;
141
142 using Base::IsRowMajor;
143 using Storage = internal::CompressedStorage<Scalar, StorageIndex>;
144 enum { Options = Options_ };
145
146 using IndexVector = typename Base::IndexVector;
147 using ScalarVector = typename Base::ScalarVector;
148
149 protected:
151
152 Index m_outerSize;
153 Index m_innerSize;
154 StorageIndex* m_outerIndex;
155 StorageIndex* m_innerNonZeros; // optional, if null then the data is compressed
156 Storage m_data;
157
158 public:
160 inline Index rows() const { return IsRowMajor ? m_outerSize : m_innerSize; }
162 inline Index cols() const { return IsRowMajor ? m_innerSize : m_outerSize; }
163
165 inline Index innerSize() const { return m_innerSize; }
167 inline Index outerSize() const { return m_outerSize; }
168
172 inline const Scalar* valuePtr() const { return m_data.valuePtr(); }
176 inline Scalar* valuePtr() { return m_data.valuePtr(); }
177
181 inline const StorageIndex* innerIndexPtr() const { return m_data.indexPtr(); }
185 inline StorageIndex* innerIndexPtr() { return m_data.indexPtr(); }
186
190 inline const StorageIndex* outerIndexPtr() const { return m_outerIndex; }
194 inline StorageIndex* outerIndexPtr() { return m_outerIndex; }
195
199 inline const StorageIndex* innerNonZeroPtr() const { return m_innerNonZeros; }
203 inline StorageIndex* innerNonZeroPtr() { return m_innerNonZeros; }
204
206 constexpr Storage& data() { return m_data; }
208 constexpr const Storage& data() const { return m_data; }
209
212 inline Scalar coeff(Index row, Index col) const {
213 eigen_assert(row >= 0 && row < rows() && col >= 0 && col < cols());
214
215 const Index outer = IsRowMajor ? row : col;
216 const Index inner = IsRowMajor ? col : row;
217 Index end = m_innerNonZeros ? m_outerIndex[outer] + m_innerNonZeros[outer] : m_outerIndex[outer + 1];
218 return m_data.atInRange(m_outerIndex[outer], end, inner);
219 }
220
232 inline Scalar& findOrInsertCoeff(Index row, Index col, bool* inserted) {
233 eigen_assert(row >= 0 && row < rows() && col >= 0 && col < cols());
234 const Index outer = IsRowMajor ? row : col;
235 const Index inner = IsRowMajor ? col : row;
236 Index start = m_outerIndex[outer];
237 Index end = isCompressed() ? m_outerIndex[outer + 1] : m_outerIndex[outer] + m_innerNonZeros[outer];
238 eigen_assert(end >= start && "you probably called coeffRef on a non finalized matrix");
239 Index dst = start == end ? end : m_data.searchLowerIndex(start, end, inner);
240 if (dst == end) {
241 Index capacity = m_outerIndex[outer + 1] - end;
242 if (capacity > 0) {
243 // implies uncompressed: push to back of vector
244 m_innerNonZeros[outer]++;
245 m_data.index(end) = StorageIndex(inner);
246 m_data.value(end) = Scalar(0);
247 if (inserted != nullptr) {
248 *inserted = true;
249 }
250 return m_data.value(end);
251 }
252 }
253 if ((dst < end) && (m_data.index(dst) == inner)) {
254 // this coefficient exists, return a reference to it
255 if (inserted != nullptr) {
256 *inserted = false;
257 }
258 return m_data.value(dst);
259 } else {
260 if (inserted != nullptr) {
261 *inserted = true;
262 }
263 // insertion will require reconfiguring the buffer
264 return insertAtByOuterInner(outer, inner, dst);
265 }
266 }
267
276 inline Scalar& coeffRef(Index row, Index col) { return findOrInsertCoeff(row, col, nullptr); }
277
295 inline Scalar& insert(Index row, Index col);
296
297 public:
305 inline void setZero() {
306 m_data.clear();
307 using std::fill_n;
308 fill_n(m_outerIndex, m_outerSize + 1, StorageIndex(0));
309 if (m_innerNonZeros) {
310 fill_n(m_innerNonZeros, m_outerSize, StorageIndex(0));
311 }
312 }
313
317 inline void reserve(Index reserveSize) {
318 eigen_assert(isCompressed() && "This function does not make sense in non compressed mode.");
319 m_data.reserve(reserveSize);
320 }
321
322#ifdef EIGEN_PARSED_BY_DOXYGEN
335 template <class SizesType>
336 inline void reserve(const SizesType& reserveSizes);
337#else
338 template <class SizesType>
339 inline void reserve(const SizesType& reserveSizes,
340 const typename SizesType::value_type& enableif = typename SizesType::value_type()) {
341 EIGEN_UNUSED_VARIABLE(enableif);
342 reserveInnerVectors(reserveSizes);
343 }
344#endif // EIGEN_PARSED_BY_DOXYGEN
345 protected:
346 template <class SizesType>
347 inline void reserveInnerVectors(const SizesType& reserveSizes) {
348 if (isCompressed()) {
349 Index totalReserveSize = 0;
350 for (Index j = 0; j < m_outerSize; ++j) totalReserveSize += internal::convert_index<Index>(reserveSizes[j]);
351
352 // if reserveSizes is empty, don't do anything!
353 if (totalReserveSize == 0) return;
354
355 // turn the matrix into non-compressed mode
356 m_innerNonZeros = internal::conditional_aligned_new_auto<StorageIndex, true>(m_outerSize);
357
358 // temporarily use m_innerNonZeros to hold the new starting points.
359 StorageIndex* newOuterIndex = m_innerNonZeros;
360
361 Index count = 0;
362 for (Index j = 0; j < m_outerSize; ++j) {
363 newOuterIndex[j] = internal::convert_index<StorageIndex>(count);
364 Index reserveSize = internal::convert_index<Index>(reserveSizes[j]);
365 count += reserveSize + internal::convert_index<Index>(m_outerIndex[j + 1] - m_outerIndex[j]);
366 }
367
368 m_data.reserve(totalReserveSize);
369 StorageIndex previousOuterIndex = m_outerIndex[m_outerSize];
370 for (Index j = m_outerSize - 1; j >= 0; --j) {
371 StorageIndex innerNNZ = previousOuterIndex - m_outerIndex[j];
372 StorageIndex begin = m_outerIndex[j];
373 StorageIndex end = begin + innerNNZ;
374 StorageIndex target = newOuterIndex[j];
375 // m_outerIndex[0] == 0, which removeOuterVectors() restores, so target - begin is the room reserved before
376 // vector j: the shift goes right, and target == begin iff it is empty, where a self-move would leave the
377 // entries unspecified.
378 eigen_internal_assert(target >= begin);
379 if (target != begin) {
380 std::move_backward(innerIndexPtr() + begin, innerIndexPtr() + end, innerIndexPtr() + target + innerNNZ);
381 internal::move_or_copy_backward(valuePtr() + begin, valuePtr() + end, valuePtr() + target + innerNNZ);
382 }
383 previousOuterIndex = m_outerIndex[j];
384 m_outerIndex[j] = newOuterIndex[j];
385 m_innerNonZeros[j] = innerNNZ;
386 }
387 if (m_outerSize > 0)
388 m_outerIndex[m_outerSize] = m_outerIndex[m_outerSize - 1] + m_innerNonZeros[m_outerSize - 1] +
389 internal::convert_index<StorageIndex>(reserveSizes[m_outerSize - 1]);
390
391 m_data.resize(internal::convert_index<Index>(m_outerIndex[m_outerSize]));
392 } else {
393 StorageIndex* newOuterIndex = internal::conditional_aligned_new_auto<StorageIndex, true>(m_outerSize + 1);
394
395 Index count = 0;
396 for (Index j = 0; j < m_outerSize; ++j) {
397 newOuterIndex[j] = internal::convert_index<StorageIndex>(count);
398 Index alreadyReserved =
399 internal::convert_index<Index>(m_outerIndex[j + 1] - m_outerIndex[j] - m_innerNonZeros[j]);
400 Index reserveSize = internal::convert_index<Index>(reserveSizes[j]);
401 Index toReserve = numext::maxi(reserveSize, alreadyReserved);
402 count += toReserve + internal::convert_index<Index>(m_innerNonZeros[j]);
403 }
404 newOuterIndex[m_outerSize] = internal::convert_index<StorageIndex>(count);
405
406 m_data.resize(count);
407 for (Index j = m_outerSize - 1; j >= 0; --j) {
408 StorageIndex innerNNZ = m_innerNonZeros[j];
409 StorageIndex begin = m_outerIndex[j];
410 StorageIndex end = begin + innerNNZ;
411 StorageIndex target = newOuterIndex[j];
412 // As above, and every vector in front of j keeps at least its current room: target - begin is the room
413 // added before vector j.
414 eigen_internal_assert(target >= begin);
415 if (target != begin) {
416 std::move_backward(innerIndexPtr() + begin, innerIndexPtr() + end, innerIndexPtr() + target + innerNNZ);
417 internal::move_or_copy_backward(valuePtr() + begin, valuePtr() + end, valuePtr() + target + innerNNZ);
418 }
419 }
420
421 std::swap(m_outerIndex, newOuterIndex);
422 internal::conditional_aligned_delete_auto<StorageIndex, true>(newOuterIndex, m_outerSize + 1);
423 }
424 }
425
426 public:
427 //--- low level purely coherent filling ---
428
439 inline Scalar& insertBack(Index row, Index col) {
440 return insertBackByOuterInner(IsRowMajor ? row : col, IsRowMajor ? col : row);
441 }
442
445 inline Scalar& insertBackByOuterInner(Index outer, Index inner) {
446 eigen_assert(Index(m_outerIndex[outer + 1]) == m_data.size() && "Invalid ordered insertion (invalid outer index)");
447 eigen_assert((m_outerIndex[outer + 1] - m_outerIndex[outer] == 0 || m_data.index(m_data.size() - 1) < inner) &&
448 "Invalid ordered insertion (invalid inner index)");
449 StorageIndex p = m_outerIndex[outer + 1];
450 ++m_outerIndex[outer + 1];
451 m_data.append(Scalar(0), inner);
452 return m_data.value(internal::convert_index<Index>(p));
453 }
454
457 inline Scalar& insertBackByOuterInnerUnordered(Index outer, Index inner) {
458 StorageIndex p = m_outerIndex[outer + 1];
459 ++m_outerIndex[outer + 1];
460 m_data.append(Scalar(0), inner);
461 return m_data.value(p);
462 }
463
466 inline void startVec(Index outer) {
467 eigen_assert(m_outerIndex[outer] == Index(m_data.size()) &&
468 "You must call startVec for each inner vector sequentially");
469 eigen_assert(m_outerIndex[outer + 1] == 0 && "You must call startVec for each inner vector sequentially");
470 m_outerIndex[outer + 1] = m_outerIndex[outer];
471 }
472
476 inline void finalize() {
477 if (isCompressed()) {
478 StorageIndex size = internal::convert_index<StorageIndex>(m_data.size());
479 Index i = m_outerSize;
480 // find the last filled column
481 while (i >= 0 && m_outerIndex[i] == 0) --i;
482 ++i;
483 while (i <= m_outerSize) {
484 m_outerIndex[i] = size;
485 ++i;
486 }
487 }
488 }
489
490 // remove outer vectors j, j+1 ... j+num-1 and resize the matrix
491 void removeOuterVectors(Index j, Index num = 1) {
492 eigen_assert(num >= 0 && j >= 0 && j + num <= m_outerSize && "Invalid parameters");
493
494 const Index newRows = IsRowMajor ? m_outerSize - num : rows();
495 const Index newCols = IsRowMajor ? cols() : m_outerSize - num;
496
497 const Index begin = j + num;
498 const Index end = m_outerSize;
499 const Index target = j;
500
501 // if the removed vectors are not empty, uncompress the matrix
502 if (m_outerIndex[j + num] > m_outerIndex[j]) uncompress();
503
504 // shift m_outerIndex and m_innerNonZeros [num] to the left
505 if (num > 0) {
506 std::copy(m_outerIndex + begin, m_outerIndex + end + 1, m_outerIndex + target);
507 if (!isCompressed()) std::copy(m_innerNonZeros + begin, m_innerNonZeros + end, m_innerNonZeros + target);
508 }
509
510 // if m_outerIndex[0] > 0, shift the data within the first vector while it is easy to do so
511 if (num < m_outerSize && m_outerIndex[0] > StorageIndex(0)) {
512 uncompress();
513 const Index from = internal::convert_index<Index>(m_outerIndex[0]);
514 const Index chunkSize = internal::convert_index<Index>(m_innerNonZeros[0]);
515 internal::move_or_copy(valuePtr() + from, valuePtr() + from + chunkSize, valuePtr());
516 std::move(innerIndexPtr() + from, innerIndexPtr() + from + chunkSize, innerIndexPtr());
517 m_outerIndex[0] = StorageIndex(0);
518 }
519
520 // truncate the matrix to the smaller size
521 conservativeResize(newRows, newCols);
522 }
523
524 // insert empty outer vectors at indices j, j+1 ... j+num-1 and resize the matrix
525 void insertEmptyOuterVectors(Index j, Index num = 1) {
526 using std::fill_n;
527 eigen_assert(num >= 0 && j >= 0 && j < m_outerSize && "Invalid parameters");
528
529 const Index newRows = IsRowMajor ? m_outerSize + num : rows();
530 const Index newCols = IsRowMajor ? cols() : m_outerSize + num;
531
532 const Index begin = j;
533 const Index end = m_outerSize;
534
535 // expand the matrix to the larger size
536 conservativeResize(newRows, newCols);
537
538 if (num == 0) return;
539
540 // shift m_outerIndex and m_innerNonZeros [num] to the right
541 std::copy_backward(m_outerIndex + begin, m_outerIndex + end + 1, m_outerIndex + end + 1 + num);
542 // m_outerIndex[begin] == m_outerIndex[begin + num], set all indices in this range to same value
543 fill_n(m_outerIndex + begin, num, m_outerIndex[begin]);
544
545 if (!isCompressed()) {
546 std::copy_backward(m_innerNonZeros + begin, m_innerNonZeros + end, m_innerNonZeros + end + num);
547 // set the nonzeros of the newly inserted vectors to 0
548 fill_n(m_innerNonZeros + begin, num, StorageIndex(0));
549 }
550 }
551
552 template <typename InputIterators>
553 void setFromTriplets(const InputIterators& begin, const InputIterators& end);
554
555 template <typename InputIterators, typename DupFunctor>
556 void setFromTriplets(const InputIterators& begin, const InputIterators& end, DupFunctor dup_func);
557
558 template <typename Derived, typename DupFunctor>
559 void collapseDuplicates(DenseBase<Derived>& wi, DupFunctor dup_func = DupFunctor());
560
561 template <typename InputIterators>
562 void setFromSortedTriplets(const InputIterators& begin, const InputIterators& end);
563
564 template <typename InputIterators, typename DupFunctor>
565 void setFromSortedTriplets(const InputIterators& begin, const InputIterators& end, DupFunctor dup_func);
566
567 template <typename InputIterators>
568 void insertFromTriplets(const InputIterators& begin, const InputIterators& end);
569
570 template <typename InputIterators, typename DupFunctor>
571 void insertFromTriplets(const InputIterators& begin, const InputIterators& end, DupFunctor dup_func);
572
573 template <typename InputIterators>
574 void insertFromSortedTriplets(const InputIterators& begin, const InputIterators& end);
575
576 template <typename InputIterators, typename DupFunctor>
577 void insertFromSortedTriplets(const InputIterators& begin, const InputIterators& end, DupFunctor dup_func);
578
579 //---
580
583 Scalar& insertByOuterInner(Index j, Index i) {
584 eigen_assert(j >= 0 && j < m_outerSize && "invalid outer index");
585 eigen_assert(i >= 0 && i < m_innerSize && "invalid inner index");
586 Index start = internal::convert_index<Index>(m_outerIndex[j]);
587 Index end = isCompressed() ? internal::convert_index<Index>(m_outerIndex[j + 1])
588 : start + internal::convert_index<Index>(m_innerNonZeros[j]);
589 Index dst = start == end ? end : m_data.searchLowerIndex(start, end, i);
590 if (dst == end) {
591 Index capacity = internal::convert_index<Index>(m_outerIndex[j + 1]) - end;
592 if (capacity > 0) {
593 // implies uncompressed: push to back of vector
594 m_innerNonZeros[j]++;
595 m_data.index(end) = StorageIndex(i);
596 m_data.value(end) = Scalar(0);
597 return m_data.value(end);
598 }
599 }
600 eigen_assert((dst == end || m_data.index(dst) != i) &&
601 "you cannot insert an element that already exists, you must call coeffRef to this end");
602 return insertAtByOuterInner(j, i, dst);
603 }
604
608 if (isCompressed()) return;
609
610 eigen_internal_assert(m_outerIndex != 0 && m_outerSize > 0);
611
612 StorageIndex start = m_outerIndex[1];
613 m_outerIndex[1] = m_innerNonZeros[0];
614 // try to move fewer, larger contiguous chunks
615 Index copyStart = internal::convert_index<Index>(start);
616 Index copyTarget = internal::convert_index<Index>(m_innerNonZeros[0]);
617 for (Index j = 1; j < m_outerSize; j++) {
618 StorageIndex end = start + m_innerNonZeros[j];
619 StorageIndex nextStart = m_outerIndex[j + 1];
620 // dont forget to move the last chunk!
621 bool breakUpCopy = (end != nextStart) || (j == m_outerSize - 1);
622 if (breakUpCopy) {
623 Index chunkSize = internal::convert_index<Index>(end) - copyStart;
624 // A leading chunk is already in place; a self-move would leave it unspecified.
625 if (copyTarget != copyStart) {
626 internal::move_or_copy(valuePtr() + copyStart, valuePtr() + copyStart + chunkSize, valuePtr() + copyTarget);
627 std::move(innerIndexPtr() + copyStart, innerIndexPtr() + copyStart + chunkSize, innerIndexPtr() + copyTarget);
628 }
629 copyStart = internal::convert_index<Index>(nextStart);
630 copyTarget += chunkSize;
631 }
632 start = nextStart;
633 m_outerIndex[j + 1] = m_outerIndex[j] + m_innerNonZeros[j];
634 }
635 m_data.resize(internal::convert_index<Index>(m_outerIndex[m_outerSize]));
636
637 // release as much memory as possible
638 internal::conditional_aligned_delete_auto<StorageIndex, true>(m_innerNonZeros, m_outerSize);
639 m_innerNonZeros = 0;
640 m_data.squeeze();
641 }
642
644 void uncompress() {
645 if (!isCompressed()) return;
646 m_innerNonZeros = internal::conditional_aligned_new_auto<StorageIndex, true>(m_outerSize);
647 if (m_outerIndex[m_outerSize] == 0) {
648 using std::fill_n;
649 fill_n(m_innerNonZeros, m_outerSize, StorageIndex(0));
650 } else {
651 for (Index j = 0; j < m_outerSize; j++) m_innerNonZeros[j] = m_outerIndex[j + 1] - m_outerIndex[j];
652 }
653 }
654
656 void prune(const Scalar& reference, const RealScalar& epsilon = NumTraits<RealScalar>::dummy_precision()) {
657 prune(default_prunning_func(reference, epsilon));
658 }
659
668 template <typename KeepFunc>
669 void prune(const KeepFunc& keep = KeepFunc()) {
670 StorageIndex k = 0;
671 for (Index j = 0; j < m_outerSize; ++j) {
672 StorageIndex previousStart = m_outerIndex[j];
673 if (isCompressed())
674 m_outerIndex[j] = k;
675 else
676 k = m_outerIndex[j];
677 StorageIndex end = isCompressed() ? m_outerIndex[j + 1] : previousStart + m_innerNonZeros[j];
678 for (StorageIndex i = previousStart; i < end; ++i) {
679 StorageIndex row = IsRowMajor ? StorageIndex(j) : m_data.index(i);
680 StorageIndex col = IsRowMajor ? m_data.index(i) : StorageIndex(j);
681 bool keepEntry = keep(row, col, m_data.value(i));
682 if (keepEntry) {
683 // Entries in front of the first dropped one are already in place, where a self-move would leave them
684 // unspecified. A trivially copyable scalar is assigned anyway, which costs less than the branch.
685 if (std::is_trivially_copyable<Scalar>::value || k != i) {
686 m_data.value(k) = internal::move_if_assignable(m_data.value(i));
687 m_data.index(k) = m_data.index(i);
688 }
689 ++k;
690 } else if (!isCompressed())
691 m_innerNonZeros[j]--;
692 }
693 }
694 if (isCompressed()) {
695 m_outerIndex[m_outerSize] = k;
696 m_data.resize(k, 0);
697 }
698 }
699
713 void conservativeResize(Index rows, Index cols) {
714 // If one dimension is null, then there is nothing to be preserved
715 if (rows == 0 || cols == 0) return resize(rows, cols);
716
717 Index newOuterSize = IsRowMajor ? rows : cols;
718 Index newInnerSize = IsRowMajor ? cols : rows;
719
720 Index innerChange = newInnerSize - m_innerSize;
721 Index outerChange = newOuterSize - m_outerSize;
722
723 if (outerChange != 0) {
724 m_outerIndex = internal::conditional_aligned_realloc_new_auto<StorageIndex, true>(m_outerIndex, newOuterSize + 1,
725 m_outerSize + 1);
726
727 if (!isCompressed())
728 m_innerNonZeros = internal::conditional_aligned_realloc_new_auto<StorageIndex, true>(m_innerNonZeros,
729 newOuterSize, m_outerSize);
730
731 if (outerChange > 0) {
732 StorageIndex lastIdx = m_outerSize == 0 ? StorageIndex(0) : m_outerIndex[m_outerSize];
733 using std::fill_n;
734 fill_n(m_outerIndex + m_outerSize, outerChange + 1, lastIdx);
735
736 if (!isCompressed()) fill_n(m_innerNonZeros + m_outerSize, outerChange, StorageIndex(0));
737 }
738 }
739 m_outerSize = newOuterSize;
740
741 if (innerChange < 0) {
742 for (Index j = 0; j < m_outerSize; j++) {
743 Index start = m_outerIndex[j];
744 Index end = isCompressed() ? m_outerIndex[j + 1] : start + m_innerNonZeros[j];
745 Index lb = m_data.searchLowerIndex(start, end, newInnerSize);
746 if (lb != end) {
747 uncompress();
748 m_innerNonZeros[j] = StorageIndex(lb - start);
749 }
750 }
751 }
752 m_innerSize = newInnerSize;
753
754 Index newSize = m_outerIndex[m_outerSize];
755 eigen_assert(newSize <= m_data.size());
756 m_data.resize(newSize);
757 }
758
760 void conservativeResize(NoChange_t, Index cols) { conservativeResize(rows(), cols); }
761
763 void conservativeResize(Index rows, NoChange_t) { conservativeResize(rows, cols()); }
764
772 void resize(Index rows, Index cols) {
773 const Index outerSize = IsRowMajor ? rows : cols;
774 m_innerSize = IsRowMajor ? cols : rows;
775 m_data.clear();
776
777 if ((m_outerIndex == 0) || (m_outerSize != outerSize)) {
778 m_outerIndex = internal::conditional_aligned_realloc_new_auto<StorageIndex, true>(m_outerIndex, outerSize + 1,
779 m_outerSize + 1);
780 m_outerSize = outerSize;
781 }
782
783 internal::conditional_aligned_delete_auto<StorageIndex, true>(m_innerNonZeros, m_outerSize);
784 m_innerNonZeros = 0;
785
786 using std::fill_n;
787 fill_n(m_outerIndex, m_outerSize + 1, StorageIndex(0));
788 }
789
791 void resize(NoChange_t, Index cols) { resize(rows(), cols); }
792
794 void resize(Index rows, NoChange_t) { resize(rows, cols()); }
795
798 void resizeNonZeros(Index size) { m_data.resize(size); }
799
801 const ConstDiagonalReturnType diagonal() const { return ConstDiagonalReturnType(*this); }
802
807 DiagonalReturnType diagonal() { return DiagonalReturnType(*this); }
808
810 inline SparseMatrix() : m_outerSize(0), m_innerSize(0), m_outerIndex(0), m_innerNonZeros(0) { resize(0, 0); }
811
813 inline SparseMatrix(Index rows, Index cols) : m_outerSize(0), m_innerSize(0), m_outerIndex(0), m_innerNonZeros(0) {
814 resize(rows, cols);
815 }
816
818 template <typename OtherDerived>
820 : m_outerSize(0), m_innerSize(0), m_outerIndex(0), m_innerNonZeros(0) {
821 EIGEN_STATIC_ASSERT(
822 (std::is_same<Scalar, typename OtherDerived::Scalar>::value),
823 YOU_MIXED_DIFFERENT_NUMERIC_TYPES__YOU_NEED_TO_USE_THE_CAST_METHOD_OF_MATRIXBASE_TO_CAST_NUMERIC_TYPES_EXPLICITLY)
824 const bool needToTranspose = (Flags & RowMajorBit) != (internal::evaluator<OtherDerived>::Flags & RowMajorBit);
825 if (needToTranspose)
826 *this = other.derived();
827 else {
828#ifdef EIGEN_SPARSE_CREATE_TEMPORARY_PLUGIN
829 EIGEN_SPARSE_CREATE_TEMPORARY_PLUGIN
830#endif
831 internal::call_assignment_no_alias(*this, other.derived());
832 }
833 }
834
836 template <typename OtherDerived, unsigned int UpLo>
838 : m_outerSize(0), m_innerSize(0), m_outerIndex(0), m_innerNonZeros(0) {
839 Base::operator=(other);
840 }
841
843 inline SparseMatrix(SparseMatrix&& other) : SparseMatrix() { this->swap(other); }
844
845 template <typename OtherDerived>
847 *this = other.derived().markAsRValue();
848 }
849
851 inline SparseMatrix(const SparseMatrix& other)
852 : Base(), m_outerSize(0), m_innerSize(0), m_outerIndex(0), m_innerNonZeros(0) {
853 *this = other.derived();
854 }
855
857 template <typename OtherDerived>
858 SparseMatrix(const ReturnByValue<OtherDerived>& other)
859 : Base(), m_outerSize(0), m_innerSize(0), m_outerIndex(0), m_innerNonZeros(0) {
860 initAssignment(other);
861 other.evalTo(*this);
862 }
863
865 template <typename OtherDerived>
867 : Base(), m_outerSize(0), m_innerSize(0), m_outerIndex(0), m_innerNonZeros(0) {
868 *this = other.derived();
869 }
870
873 inline void swap(SparseMatrix& other) {
874 std::swap(m_outerIndex, other.m_outerIndex);
875 std::swap(m_innerSize, other.m_innerSize);
876 std::swap(m_outerSize, other.m_outerSize);
877 std::swap(m_innerNonZeros, other.m_innerNonZeros);
878 m_data.swap(other.m_data);
879 }
880
881 friend EIGEN_DEVICE_FUNC void swap(SparseMatrix& a, SparseMatrix& b) { a.swap(b); }
882
885 inline void setIdentity() {
886 eigen_assert(m_outerSize == m_innerSize && "ONLY FOR SQUARED MATRICES");
887 internal::conditional_aligned_delete_auto<StorageIndex, true>(m_innerNonZeros, m_outerSize);
888 m_innerNonZeros = 0;
889 m_data.resize(m_outerSize);
890 // is it necessary to squeeze?
891 m_data.squeeze();
892 std::iota(m_outerIndex, m_outerIndex + m_outerSize + 1, StorageIndex(0));
893 std::iota(innerIndexPtr(), innerIndexPtr() + m_outerSize, StorageIndex(0));
894 using std::fill_n;
895 fill_n(valuePtr(), m_outerSize, Scalar(1));
896 }
897
898 inline SparseMatrix& operator=(const SparseMatrix& other) {
899 if (other.isRValue()) {
900 swap(other.const_cast_derived());
901 } else if (this != &other) {
902#ifdef EIGEN_SPARSE_CREATE_TEMPORARY_PLUGIN
903 EIGEN_SPARSE_CREATE_TEMPORARY_PLUGIN
904#endif
905 initAssignment(other);
906 if (other.isCompressed()) {
907 internal::smart_copy(other.m_outerIndex, other.m_outerIndex + m_outerSize + 1, m_outerIndex);
908 m_data = other.m_data;
909 } else {
910 Base::operator=(other);
911 }
912 }
913 return *this;
914 }
915
916 inline SparseMatrix& operator=(SparseMatrix&& other) {
917 this->swap(other);
918 return *this;
919 }
920
921 template <typename OtherDerived>
922 inline SparseMatrix& operator=(const EigenBase<OtherDerived>& other) {
923 return Base::operator=(other.derived());
924 }
925
926 template <typename Lhs, typename Rhs>
927 inline SparseMatrix& operator=(const Product<Lhs, Rhs, AliasFreeProduct>& other);
928
929 template <typename OtherDerived>
930 EIGEN_DONT_INLINE SparseMatrix& operator=(const SparseMatrixBase<OtherDerived>& other);
931
932 template <typename OtherDerived>
933 inline SparseMatrix& operator=(SparseCompressedBase<OtherDerived>&& other) {
934 *this = other.derived().markAsRValue();
935 return *this;
936 }
937
938#ifndef EIGEN_NO_IO
939 friend std::ostream& operator<<(std::ostream& s, const SparseMatrix& m) {
940 EIGEN_DBG_SPARSE(
941 s << "Nonzero entries:\n"; if (m.isCompressed()) {
942 for (Index i = 0; i < m.nonZeros(); ++i) s << "(" << m.m_data.value(i) << "," << m.m_data.index(i) << ") ";
943 } else {
944 for (Index i = 0; i < m.outerSize(); ++i) {
945 Index p = m.m_outerIndex[i];
946 Index pe = m.m_outerIndex[i] + m.m_innerNonZeros[i];
947 Index k = p;
948 for (; k < pe; ++k) {
949 s << "(" << m.m_data.value(k) << "," << m.m_data.index(k) << ") ";
950 }
951 for (; k < m.m_outerIndex[i + 1]; ++k) {
952 s << "(_,_) ";
953 }
954 }
955 } s << std::endl;
956 s << std::endl; s << "Outer pointers:\n";
957 for (Index i = 0; i < m.outerSize(); ++i) { s << m.m_outerIndex[i] << " "; } s << " $" << std::endl;
958 if (!m.isCompressed()) {
959 s << "Inner non zeros:\n";
960 for (Index i = 0; i < m.outerSize(); ++i) {
961 s << m.m_innerNonZeros[i] << " ";
962 }
963 s << " $" << std::endl;
964 } s
965 << std::endl;);
966 s << static_cast<const SparseMatrixBase<SparseMatrix>&>(m);
967 return s;
968 }
969#endif
970
972 inline ~SparseMatrix() {
973 internal::conditional_aligned_delete_auto<StorageIndex, true>(m_outerIndex, m_outerSize + 1);
974 internal::conditional_aligned_delete_auto<StorageIndex, true>(m_innerNonZeros, m_outerSize);
975 }
976
978 Scalar sum() const;
979
980#ifdef EIGEN_SPARSEMATRIX_PLUGIN
981#include EIGEN_SPARSEMATRIX_PLUGIN
982#endif
983
984 protected:
985 template <typename Other>
986 void initAssignment(const Other& other) {
987 resize(other.rows(), other.cols());
988 internal::conditional_aligned_delete_auto<StorageIndex, true>(m_innerNonZeros, m_outerSize);
989 m_innerNonZeros = 0;
990 }
991
994 EIGEN_DEPRECATED EIGEN_DONT_INLINE Scalar& insertCompressed(Index row, Index col);
995
998 EIGEN_DEPRECATED EIGEN_DONT_INLINE Scalar& insertUncompressed(Index row, Index col);
999
1000 public:
1003 EIGEN_STRONG_INLINE Scalar& insertBackUncompressed(Index row, Index col) {
1004 const Index outer = IsRowMajor ? row : col;
1005 const Index inner = IsRowMajor ? col : row;
1006
1007 eigen_assert(!isCompressed());
1008 eigen_assert(m_innerNonZeros[outer] <= (m_outerIndex[outer + 1] - m_outerIndex[outer]));
1009
1010 Index p = m_outerIndex[outer] + m_innerNonZeros[outer]++;
1011 m_data.index(p) = StorageIndex(inner);
1012 m_data.value(p) = Scalar(0);
1013 return m_data.value(p);
1014 }
1015
1016 protected:
1017 struct IndexPosPair {
1018 IndexPosPair(Index a_i, Index a_p) : i(a_i), p(a_p) {}
1019 Index i;
1020 Index p;
1021 };
1022
1032 template <typename DiagXpr, typename Func>
1033 void assignDiagonal(const DiagXpr diagXpr, const Func& assignFunc) {
1034 constexpr StorageIndex kEmptyIndexVal(-1);
1035 using ValueMap = typename ScalarVector::AlignedMapType;
1036
1037 Index n = diagXpr.size();
1038
1039 const bool overwrite = std::is_same<Func, internal::assign_op<Scalar, Scalar>>::value;
1040 if (overwrite) {
1041 if ((m_outerSize != n) || (m_innerSize != n) || (n == 0)) resize(n, n);
1042 }
1043
1044 if (m_data.size() == 0 || overwrite) {
1045 internal::conditional_aligned_delete_auto<StorageIndex, true>(m_innerNonZeros, m_outerSize);
1046 m_innerNonZeros = 0;
1047 resizeNonZeros(n);
1048 ValueMap valueMap(valuePtr(), n);
1049 std::iota(m_outerIndex, m_outerIndex + n + 1, StorageIndex(0));
1050 std::iota(innerIndexPtr(), innerIndexPtr() + n, StorageIndex(0));
1051 valueMap.setZero();
1052 internal::call_assignment_no_alias(valueMap, diagXpr, assignFunc);
1053 } else {
1054 internal::evaluator<DiagXpr> diaEval(diagXpr);
1055
1056 ei_declare_aligned_stack_constructed_variable(StorageIndex, tmp, n, 0);
1057 typename IndexVector::AlignedMapType insertionLocations(tmp, n);
1058 insertionLocations.setConstant(kEmptyIndexVal);
1059
1060 Index deferredInsertions = 0;
1061 Index shift = 0;
1062
1063 for (Index j = 0; j < n; j++) {
1064 Index begin = m_outerIndex[j];
1065 Index end = isCompressed() ? m_outerIndex[j + 1] : begin + m_innerNonZeros[j];
1066 Index capacity = m_outerIndex[j + 1] - end;
1067 Index dst = m_data.searchLowerIndex(begin, end, j);
1068 // the entry exists: update it now
1069 if (dst != end && m_data.index(dst) == StorageIndex(j))
1070 assignFunc.assignCoeff(m_data.value(dst), diaEval.coeff(j));
1071 // the entry belongs at the back of the vector: push to back
1072 else if (dst == end && capacity > 0)
1073 assignFunc.assignCoeff(insertBackUncompressed(j, j), diaEval.coeff(j));
1074 // the insertion requires a data move, record insertion location and handle in second pass
1075 else {
1076 insertionLocations.coeffRef(j) = StorageIndex(dst);
1077 deferredInsertions++;
1078 // if there is no capacity, all vectors to the right of this are shifted
1079 if (capacity == 0) shift++;
1080 }
1081 }
1082
1083 if (deferredInsertions > 0) {
1084 m_data.resize(m_data.size() + shift);
1085 Index copyEnd = isCompressed() ? m_outerIndex[m_outerSize]
1086 : m_outerIndex[m_outerSize - 1] + m_innerNonZeros[m_outerSize - 1];
1087 for (Index j = m_outerSize - 1; deferredInsertions > 0; j--) {
1088 Index begin = m_outerIndex[j];
1089 Index end = isCompressed() ? m_outerIndex[j + 1] : begin + m_innerNonZeros[j];
1090 Index capacity = m_outerIndex[j + 1] - end;
1091
1092 bool doInsertion = insertionLocations(j) >= 0;
1093 bool breakUpCopy = doInsertion && (capacity > 0);
1094 // break up copy for sorted insertion into inactive nonzeros
1095 // optionally, add another criterion, i.e. 'breakUpCopy || (capacity > threshold)'
1096 // where `threshold >= 0` to skip inactive nonzeros in each vector
1097 // this reduces the total number of moved elements, but requires more move calls
1098 if (breakUpCopy) {
1099 Index copyBegin = m_outerIndex[j + 1];
1100 // shift == 0: every remaining insertion fits in its vector's capacity, so the chunk stays in place.
1101 if (shift > 0) {
1102 internal::move_or_copy_backward(valuePtr() + copyBegin, valuePtr() + copyEnd,
1103 valuePtr() + copyEnd + shift);
1104 std::move_backward(innerIndexPtr() + copyBegin, innerIndexPtr() + copyEnd,
1105 innerIndexPtr() + copyEnd + shift);
1106 }
1107 copyEnd = end;
1108 }
1109
1110 m_outerIndex[j + 1] += shift;
1111
1112 if (doInsertion) {
1113 // if there is capacity, shift into the inactive nonzeros
1114 if (capacity > 0) shift++;
1115 // shift >= 1 here: this insertion either took a slot of capacity or was counted in the first pass.
1116 Index copyBegin = insertionLocations(j);
1117 internal::move_or_copy_backward(valuePtr() + copyBegin, valuePtr() + copyEnd, valuePtr() + copyEnd + shift);
1118 std::move_backward(innerIndexPtr() + copyBegin, innerIndexPtr() + copyEnd,
1119 innerIndexPtr() + copyEnd + shift);
1120 Index dst = copyBegin + shift - 1;
1121 m_data.index(dst) = StorageIndex(j);
1122 m_data.value(dst) = Scalar(0);
1123 assignFunc.assignCoeff(m_data.value(dst), diaEval.coeff(j));
1124 if (!isCompressed()) m_innerNonZeros[j]++;
1125 shift--;
1126 deferredInsertions--;
1127 copyEnd = copyBegin;
1128 }
1129 }
1130 }
1131 eigen_assert((shift == 0) && (deferredInsertions == 0));
1132 }
1133 }
1134
1135 /* These functions are used to avoid a redundant binary search operation in functions such as coeffRef() and assume
1136 * `dst` is the appropriate sorted insertion point */
1137 EIGEN_STRONG_INLINE Scalar& insertAtByOuterInner(Index outer, Index inner, Index dst);
1138 Scalar& insertCompressedAtByOuterInner(Index outer, Index inner, Index dst);
1139 Scalar& insertUncompressedAtByOuterInner(Index outer, Index inner, Index dst);
1140
1141 private:
1142 EIGEN_STATIC_ASSERT(NumTraits<StorageIndex>::IsSigned, THE_INDEX_TYPE_MUST_BE_A_SIGNED_TYPE)
1143 EIGEN_STATIC_ASSERT((Options & (ColMajor | RowMajor)) == Options, INVALID_MATRIX_TEMPLATE_PARAMETERS)
1144
1145 struct default_prunning_func {
1146 default_prunning_func(const Scalar& ref, const RealScalar& eps) : reference(ref), epsilon(eps) {}
1147 inline bool operator()(const Index&, const Index&, const Scalar& value) const {
1148 return !internal::isMuchSmallerThan(value, reference, epsilon);
1149 }
1150 Scalar reference;
1151 RealScalar epsilon;
1152 };
1153};
1154
1155namespace internal {
1156
1157// Creates a compressed sparse matrix from a range of unsorted triplets
1158// Requires temporary storage to handle duplicate entries
1159template <typename InputIterator, typename SparseMatrixType, typename DupFunctor>
1160void set_from_triplets(const InputIterator& begin, const InputIterator& end, SparseMatrixType& mat,
1161 DupFunctor dup_func) {
1162 constexpr bool IsRowMajor = SparseMatrixType::IsRowMajor;
1163 using StorageIndex = typename SparseMatrixType::StorageIndex;
1164 using IndexMap = typename VectorX<StorageIndex>::AlignedMapType;
1165 using TransposedSparseMatrix =
1166 SparseMatrix<typename SparseMatrixType::Scalar, IsRowMajor ? ColMajor : RowMajor, StorageIndex>;
1167
1168 if (begin == end) {
1169 // Clear out existing data (if any), including the inner non-zero counts of an uncompressed matrix.
1170 mat.setZero();
1171 mat.makeCompressed();
1172 return;
1173 }
1174
1175 // There are two strategies to consider for constructing a matrix from unordered triplets:
1176 // A) construct the 'mat' in its native storage order and sort in-place (less memory); or,
1177 // B) construct the transposed matrix and use an implicit sort upon assignment to `mat` (less time).
1178 // This routine uses B) for faster execution time.
1179 TransposedSparseMatrix trmat(mat.rows(), mat.cols());
1180
1181 // scan triplets to determine allocation size before constructing matrix
1182 Index nonZeros = 0;
1183 for (InputIterator it(begin); it != end; ++it) {
1184 eigen_assert(it->row() >= 0 && it->row() < mat.rows() && it->col() >= 0 && it->col() < mat.cols());
1185 StorageIndex j = convert_index<StorageIndex>(IsRowMajor ? it->col() : it->row());
1186 eigen_assert(nonZeros < NumTraits<StorageIndex>::highest() &&
1187 "non-zero count exceeds StorageIndex range, use a wider StorageIndex (e.g. int64_t)");
1188 if (nonZeros >= NumTraits<StorageIndex>::highest()) internal::throw_std_bad_alloc();
1189 trmat.outerIndexPtr()[j + 1]++;
1190 nonZeros++;
1191 }
1192
1193 std::partial_sum(trmat.outerIndexPtr(), trmat.outerIndexPtr() + trmat.outerSize() + 1, trmat.outerIndexPtr());
1194 eigen_assert(nonZeros == trmat.outerIndexPtr()[trmat.outerSize()]);
1195 trmat.resizeNonZeros(nonZeros);
1196
1197 // construct temporary array to track insertions (outersize) and collapse duplicates (innersize)
1198 ei_declare_aligned_stack_constructed_variable(StorageIndex, tmp, numext::maxi(mat.innerSize(), mat.outerSize()), 0);
1199 smart_copy(trmat.outerIndexPtr(), trmat.outerIndexPtr() + trmat.outerSize(), tmp);
1200
1201 // push triplets to back of each vector
1202 for (InputIterator it(begin); it != end; ++it) {
1203 StorageIndex j = convert_index<StorageIndex>(IsRowMajor ? it->col() : it->row());
1204 StorageIndex i = convert_index<StorageIndex>(IsRowMajor ? it->row() : it->col());
1205 StorageIndex k = tmp[j];
1206 trmat.data().index(k) = i;
1207 trmat.data().value(k) = it->value();
1208 tmp[j]++;
1209 }
1210
1211 IndexMap wi(tmp, trmat.innerSize());
1212 trmat.collapseDuplicates(wi, dup_func);
1213 // implicit sorting
1214 mat = trmat;
1215}
1216
1217// Creates a compressed sparse matrix from a sorted range of triplets
1218template <typename InputIterator, typename SparseMatrixType, typename DupFunctor>
1219void set_from_triplets_sorted(const InputIterator& begin, const InputIterator& end, SparseMatrixType& mat,
1220 DupFunctor dup_func) {
1221 constexpr bool IsRowMajor = SparseMatrixType::IsRowMajor;
1222 using StorageIndex = typename SparseMatrixType::StorageIndex;
1223
1224 if (begin == end) {
1225 // Clear out existing data (if any), including the inner non-zero counts of an uncompressed matrix.
1226 mat.setZero();
1227 mat.makeCompressed();
1228 return;
1229 }
1230
1231 constexpr StorageIndex kEmptyIndexValue(-1);
1232 // deallocate inner nonzeros if present and zero outerIndexPtr
1233 mat.resize(mat.rows(), mat.cols());
1234 // use outer indices to count non zero entries (excluding duplicate entries)
1235 StorageIndex previous_j = kEmptyIndexValue;
1236 StorageIndex previous_i = kEmptyIndexValue;
1237 // scan triplets to determine allocation size before constructing matrix
1238 Index nonZeros = 0;
1239 for (InputIterator it(begin); it != end; ++it) {
1240 eigen_assert(it->row() >= 0 && it->row() < mat.rows() && it->col() >= 0 && it->col() < mat.cols());
1241 StorageIndex j = convert_index<StorageIndex>(IsRowMajor ? it->row() : it->col());
1242 StorageIndex i = convert_index<StorageIndex>(IsRowMajor ? it->col() : it->row());
1243 eigen_assert(j > previous_j || (j == previous_j && i >= previous_i));
1244 // identify duplicates by examining previous location
1245 bool duplicate = (previous_j == j) && (previous_i == i);
1246 if (!duplicate) {
1247 eigen_assert(nonZeros < NumTraits<StorageIndex>::highest() &&
1248 "non-zero count exceeds StorageIndex range, use a wider StorageIndex (e.g. int64_t)");
1249 if (nonZeros >= NumTraits<StorageIndex>::highest()) internal::throw_std_bad_alloc();
1250 nonZeros++;
1251 mat.outerIndexPtr()[j + 1]++;
1252 previous_j = j;
1253 previous_i = i;
1254 }
1255 }
1256
1257 // finalize outer indices and allocate memory
1258 std::partial_sum(mat.outerIndexPtr(), mat.outerIndexPtr() + mat.outerSize() + 1, mat.outerIndexPtr());
1259 eigen_assert(nonZeros == mat.outerIndexPtr()[mat.outerSize()]);
1260 mat.resizeNonZeros(nonZeros);
1261
1262 previous_i = kEmptyIndexValue;
1263 previous_j = kEmptyIndexValue;
1264 Index back = 0;
1265 for (InputIterator it(begin); it != end; ++it) {
1266 StorageIndex j = convert_index<StorageIndex>(IsRowMajor ? it->row() : it->col());
1267 StorageIndex i = convert_index<StorageIndex>(IsRowMajor ? it->col() : it->row());
1268 bool duplicate = (previous_j == j) && (previous_i == i);
1269 if (duplicate) {
1270 mat.data().value(back - 1) = dup_func(mat.data().value(back - 1), it->value());
1271 } else {
1272 // push triplets to back
1273 mat.data().index(back) = i;
1274 mat.data().value(back) = it->value();
1275 previous_j = j;
1276 previous_i = i;
1277 back++;
1278 }
1279 }
1280 eigen_assert(back == nonZeros);
1281 // matrix is finalized
1282}
1283
1284// thin wrapper around a generic binary functor to use the sparse disjunction evaluator instead of the default
1285// "arithmetic" evaluator
1286template <typename DupFunctor, typename LhsScalar, typename RhsScalar = LhsScalar>
1287struct scalar_disjunction_op {
1288 using result_type = typename result_of<DupFunctor(LhsScalar, RhsScalar)>::type;
1289 scalar_disjunction_op(const DupFunctor& op) : m_functor(op) {}
1290 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE result_type operator()(const LhsScalar& a, const RhsScalar& b) const {
1291 return m_functor(a, b);
1292 }
1293 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE const DupFunctor& functor() const { return m_functor; }
1294 const DupFunctor& m_functor;
1295};
1296
1297template <typename DupFunctor, typename LhsScalar, typename RhsScalar>
1298struct functor_traits<scalar_disjunction_op<DupFunctor, LhsScalar, RhsScalar>> : public functor_traits<DupFunctor> {};
1299
1300// Creates a compressed sparse matrix from its existing entries and those from an unsorted range of triplets
1301template <typename InputIterator, typename SparseMatrixType, typename DupFunctor>
1302void insert_from_triplets(const InputIterator& begin, const InputIterator& end, SparseMatrixType& mat,
1303 DupFunctor dup_func) {
1304 using Scalar = typename SparseMatrixType::Scalar;
1305 using SrcXprType =
1306 CwiseBinaryOp<scalar_disjunction_op<DupFunctor, Scalar>, const SparseMatrixType, const SparseMatrixType>;
1307
1308 // set_from_triplets is necessary to sort the inner indices and remove the duplicate entries
1309 SparseMatrixType trips(mat.rows(), mat.cols());
1310 set_from_triplets(begin, end, trips, dup_func);
1311
1312 SrcXprType src = mat.binaryExpr(trips, scalar_disjunction_op<DupFunctor, Scalar>(dup_func));
1313 // the sparse assignment procedure creates a temporary matrix and swaps the final result
1314 assign_sparse_to_sparse<SparseMatrixType, SrcXprType>(mat, src);
1315}
1316
1317// Creates a compressed sparse matrix from its existing entries and those from an sorted range of triplets
1318template <typename InputIterator, typename SparseMatrixType, typename DupFunctor>
1319void insert_from_triplets_sorted(const InputIterator& begin, const InputIterator& end, SparseMatrixType& mat,
1320 DupFunctor dup_func) {
1321 using Scalar = typename SparseMatrixType::Scalar;
1322 using SrcXprType =
1323 CwiseBinaryOp<scalar_disjunction_op<DupFunctor, Scalar>, const SparseMatrixType, const SparseMatrixType>;
1324
1325 // Saving the trips temporary would need a direct mat+triplets merge with
1326 // on-the-fly duplicate collapsing (non-trivial).
1327 SparseMatrixType trips(mat.rows(), mat.cols());
1328 set_from_triplets_sorted(begin, end, trips, dup_func);
1329
1330 SrcXprType src = mat.binaryExpr(trips, scalar_disjunction_op<DupFunctor, Scalar>(dup_func));
1331 // the sparse assignment procedure creates a temporary matrix and swaps the final result
1332 assign_sparse_to_sparse<SparseMatrixType, SrcXprType>(mat, src);
1333}
1334
1335} // namespace internal
1336
1374template <typename Scalar, int Options_, typename StorageIndex_>
1375template <typename InputIterators>
1377 const InputIterators& end) {
1378 internal::set_from_triplets<InputIterators, SparseMatrix<Scalar, Options_, StorageIndex_>>(
1379 begin, end, *this, internal::scalar_sum_op<Scalar, Scalar>());
1380}
1381
1391template <typename Scalar, int Options_, typename StorageIndex_>
1392template <typename InputIterators, typename DupFunctor>
1394 const InputIterators& end, DupFunctor dup_func) {
1395 internal::set_from_triplets<InputIterators, SparseMatrix<Scalar, Options_, StorageIndex_>, DupFunctor>(
1396 begin, end, *this, dup_func);
1397}
1398
1403template <typename Scalar, int Options_, typename StorageIndex_>
1404template <typename InputIterators>
1406 const InputIterators& end) {
1407 internal::set_from_triplets_sorted<InputIterators, SparseMatrix<Scalar, Options_, StorageIndex_>>(
1408 begin, end, *this, internal::scalar_sum_op<Scalar, Scalar>());
1409}
1410
1420template <typename Scalar, int Options_, typename StorageIndex_>
1421template <typename InputIterators, typename DupFunctor>
1423 const InputIterators& end,
1424 DupFunctor dup_func) {
1425 internal::set_from_triplets_sorted<InputIterators, SparseMatrix<Scalar, Options_, StorageIndex_>, DupFunctor>(
1426 begin, end, *this, dup_func);
1427}
1428
1467template <typename Scalar, int Options_, typename StorageIndex_>
1468template <typename InputIterators>
1470 const InputIterators& end) {
1471 internal::insert_from_triplets<InputIterators, SparseMatrix<Scalar, Options_, StorageIndex_>>(
1472 begin, end, *this, internal::scalar_sum_op<Scalar, Scalar>());
1473}
1474
1484template <typename Scalar, int Options_, typename StorageIndex_>
1485template <typename InputIterators, typename DupFunctor>
1487 const InputIterators& end, DupFunctor dup_func) {
1488 internal::insert_from_triplets<InputIterators, SparseMatrix<Scalar, Options_, StorageIndex_>, DupFunctor>(
1489 begin, end, *this, dup_func);
1490}
1491
1496template <typename Scalar, int Options_, typename StorageIndex_>
1497template <typename InputIterators>
1499 const InputIterators& end) {
1500 internal::insert_from_triplets_sorted<InputIterators, SparseMatrix<Scalar, Options_, StorageIndex_>>(
1501 begin, end, *this, internal::scalar_sum_op<Scalar, Scalar>());
1502}
1503
1513template <typename Scalar, int Options_, typename StorageIndex_>
1514template <typename InputIterators, typename DupFunctor>
1516 const InputIterators& end,
1517 DupFunctor dup_func) {
1518 internal::insert_from_triplets_sorted<InputIterators, SparseMatrix<Scalar, Options_, StorageIndex_>, DupFunctor>(
1519 begin, end, *this, dup_func);
1520}
1521
1523template <typename Scalar_, int Options_, typename StorageIndex_>
1524template <typename Derived, typename DupFunctor>
1525void SparseMatrix<Scalar_, Options_, StorageIndex_>::collapseDuplicates(DenseBase<Derived>& wi, DupFunctor dup_func) {
1526 // removes duplicate entries and compresses the matrix
1527 // the excess allocated memory is not released
1528 // the inner indices do not need to be sorted, nor is the matrix returned in a sorted state
1529 eigen_assert(wi.size() == m_innerSize);
1530 constexpr StorageIndex kEmptyIndexValue(-1);
1531 wi.setConstant(kEmptyIndexValue);
1532 StorageIndex count = 0;
1533 const bool is_compressed = isCompressed();
1534 // for each inner-vector, wi[inner_index] will hold the position of first element into the index/value buffers
1535 for (Index j = 0; j < m_outerSize; ++j) {
1536 const StorageIndex newBegin = count;
1537 const StorageIndex end = is_compressed ? m_outerIndex[j + 1] : m_outerIndex[j] + m_innerNonZeros[j];
1538 for (StorageIndex k = m_outerIndex[j]; k < end; ++k) {
1539 StorageIndex i = m_data.index(k);
1540 if (wi(i) >= newBegin) {
1541 // entry at k is a duplicate
1542 // accumulate it into the primary entry located at wi(i)
1543 m_data.value(wi(i)) = dup_func(m_data.value(wi(i)), m_data.value(k));
1544 } else {
1545 // k is the primary entry in j with inner index i
1546 // shift it to the left and record its location at wi(i). Until the first duplicate it is already in place,
1547 // where a self-move would leave it unspecified; a trivially copyable scalar is assigned anyway.
1548 if (std::is_trivially_copyable<Scalar>::value || count != k) {
1549 m_data.index(count) = i;
1550 m_data.value(count) = internal::move_if_assignable(m_data.value(k));
1551 }
1552 wi(i) = count;
1553 ++count;
1554 }
1555 }
1556 m_outerIndex[j] = newBegin;
1557 }
1558 m_outerIndex[m_outerSize] = count;
1559 m_data.resize(count);
1560
1561 // turn the matrix into compressed form (if it is not already)
1562 internal::conditional_aligned_delete_auto<StorageIndex, true>(m_innerNonZeros, m_outerSize);
1563 m_innerNonZeros = 0;
1564}
1565
1567template <typename Scalar, int Options_, typename StorageIndex_>
1568template <typename OtherDerived>
1569EIGEN_DONT_INLINE SparseMatrix<Scalar, Options_, StorageIndex_>&
1570SparseMatrix<Scalar, Options_, StorageIndex_>::operator=(const SparseMatrixBase<OtherDerived>& other) {
1571 EIGEN_STATIC_ASSERT(
1572 (std::is_same<Scalar, typename OtherDerived::Scalar>::value),
1573 YOU_MIXED_DIFFERENT_NUMERIC_TYPES__YOU_NEED_TO_USE_THE_CAST_METHOD_OF_MATRIXBASE_TO_CAST_NUMERIC_TYPES_EXPLICITLY)
1574
1575#ifdef EIGEN_SPARSE_CREATE_TEMPORARY_PLUGIN
1576 EIGEN_SPARSE_CREATE_TEMPORARY_PLUGIN
1577#endif
1578
1579 const bool needToTranspose = (Flags & RowMajorBit) != (internal::evaluator<OtherDerived>::Flags & RowMajorBit);
1580 if (needToTranspose) {
1581#ifdef EIGEN_SPARSE_TRANSPOSED_COPY_PLUGIN
1582 EIGEN_SPARSE_TRANSPOSED_COPY_PLUGIN
1583#endif
1584 // two passes algorithm:
1585 // 1 - compute the number of coeffs per dest inner vector
1586 // 2 - do the actual copy/eval
1587 // Since each coeff of the rhs has to be evaluated twice, let's evaluate it if needed
1588 using OtherCopy =
1589 typename internal::nested_eval<OtherDerived, 2, typename internal::plain_matrix_type<OtherDerived>::type>::type;
1590 using OtherCopy_ = internal::remove_all_t<OtherCopy>;
1591 using OtherCopyEval = internal::evaluator<OtherCopy_>;
1592 OtherCopy otherCopy(other.derived());
1593 OtherCopyEval otherCopyEval(otherCopy);
1594
1595 SparseMatrix dest(other.rows(), other.cols());
1596 Eigen::Map<IndexVector>(dest.m_outerIndex, dest.outerSize()).setZero();
1597
1598 // pass 1
1599 // FIXME: merge the above copy into this pass to avoid iterating twice.
1600 for (Index j = 0; j < otherCopy.outerSize(); ++j)
1601 for (typename OtherCopyEval::InnerIterator it(otherCopyEval, j); it; ++it) ++dest.m_outerIndex[it.index()];
1602
1603 // prefix sum
1604 Index count = 0;
1605 IndexVector positions(dest.outerSize());
1606 for (Index j = 0; j < dest.outerSize(); ++j) {
1607 StorageIndex tmp = dest.m_outerIndex[j];
1608 dest.m_outerIndex[j] = internal::convert_index<StorageIndex>(count);
1609 positions[j] = internal::convert_index<StorageIndex>(count);
1610 count += tmp;
1611 }
1612 dest.m_outerIndex[dest.outerSize()] = internal::convert_index<StorageIndex>(count);
1613 // alloc
1614 dest.m_data.resize(count);
1615 // pass 2
1616 for (Index j = 0; j < otherCopy.outerSize(); ++j) {
1617 for (typename OtherCopyEval::InnerIterator it(otherCopyEval, j); it; ++it) {
1618 Index pos = internal::convert_index<Index>(positions.coeff(it.index()));
1619 positions.coeffRef(it.index()) = internal::convert_index<StorageIndex>(pos + 1);
1620 dest.m_data.index(pos) = internal::convert_index<StorageIndex>(j);
1621 dest.m_data.value(pos) = it.value();
1622 }
1623 }
1624 this->swap(dest);
1625 return *this;
1626 } else {
1627 if (other.isRValue()) {
1628 initAssignment(other.derived());
1629 }
1630 // there is no special optimization
1631 return Base::operator=(other.derived());
1632 }
1633}
1634
1635template <typename Scalar_, int Options_, typename StorageIndex_>
1636inline typename SparseMatrix<Scalar_, Options_, StorageIndex_>::Scalar&
1638 return insertByOuterInner(IsRowMajor ? row : col, IsRowMajor ? col : row);
1639}
1640
1641template <typename Scalar_, int Options_, typename StorageIndex_>
1642EIGEN_STRONG_INLINE typename SparseMatrix<Scalar_, Options_, StorageIndex_>::Scalar&
1643SparseMatrix<Scalar_, Options_, StorageIndex_>::insertAtByOuterInner(Index outer, Index inner, Index dst) {
1644 // random insertion into compressed matrix is very slow
1645 uncompress();
1646 return insertUncompressedAtByOuterInner(outer, inner, dst);
1647}
1648
1649template <typename Scalar_, int Options_, typename StorageIndex_>
1650EIGEN_DEPRECATED EIGEN_DONT_INLINE typename SparseMatrix<Scalar_, Options_, StorageIndex_>::Scalar&
1651SparseMatrix<Scalar_, Options_, StorageIndex_>::insertUncompressed(Index row, Index col) {
1652 eigen_assert(!isCompressed());
1653 Index outer = IsRowMajor ? row : col;
1654 Index inner = IsRowMajor ? col : row;
1655 Index start = m_outerIndex[outer];
1656 Index end = start + m_innerNonZeros[outer];
1657 Index dst = start == end ? end : m_data.searchLowerIndex(start, end, inner);
1658 if (dst == end) {
1659 Index capacity = m_outerIndex[outer + 1] - end;
1660 if (capacity > 0) {
1661 // implies uncompressed: push to back of vector
1662 m_innerNonZeros[outer]++;
1663 m_data.index(end) = StorageIndex(inner);
1664 m_data.value(end) = Scalar(0);
1665 return m_data.value(end);
1666 }
1667 }
1668 eigen_assert((dst == end || m_data.index(dst) != inner) &&
1669 "you cannot insert an element that already exists, you must call coeffRef to this end");
1670 return insertUncompressedAtByOuterInner(outer, inner, dst);
1671}
1672
1673template <typename Scalar_, int Options_, typename StorageIndex_>
1674EIGEN_DEPRECATED EIGEN_DONT_INLINE typename SparseMatrix<Scalar_, Options_, StorageIndex_>::Scalar&
1675SparseMatrix<Scalar_, Options_, StorageIndex_>::insertCompressed(Index row, Index col) {
1676 eigen_assert(isCompressed());
1677 Index outer = IsRowMajor ? row : col;
1678 Index inner = IsRowMajor ? col : row;
1679 Index start = m_outerIndex[outer];
1680 Index end = m_outerIndex[outer + 1];
1681 Index dst = start == end ? end : m_data.searchLowerIndex(start, end, inner);
1682 eigen_assert((dst == end || m_data.index(dst) != inner) &&
1683 "you cannot insert an element that already exists, you must call coeffRef to this end");
1684 return insertCompressedAtByOuterInner(outer, inner, dst);
1685}
1686
1687template <typename Scalar_, int Options_, typename StorageIndex_>
1688typename SparseMatrix<Scalar_, Options_, StorageIndex_>::Scalar&
1689SparseMatrix<Scalar_, Options_, StorageIndex_>::insertCompressedAtByOuterInner(Index outer, Index inner, Index dst) {
1690 eigen_assert(isCompressed());
1691 // compressed insertion always requires expanding the buffer
1692 // first, check if there is adequate allocated memory
1693 if (m_data.allocatedSize() <= m_data.size()) {
1694 // if there is no capacity for a single insertion, double the capacity
1695 // increase capacity by a minimum of 32
1696 Index minReserve = 32;
1697 Index reserveSize = numext::maxi(minReserve, m_data.allocatedSize());
1698 m_data.reserve(reserveSize);
1699 }
1700 m_data.resize(m_data.size() + 1);
1701 Index end = m_outerIndex[m_outerSize];
1702 // shift the existing data to the right if necessary
1703 internal::move_or_copy_backward(valuePtr() + dst, valuePtr() + end, valuePtr() + end + 1);
1704 std::move_backward(innerIndexPtr() + dst, innerIndexPtr() + end, innerIndexPtr() + end + 1);
1705 // update nonzero counts
1706 // potentially O(outerSize) bottleneck!
1707 for (Index j = outer; j < m_outerSize; j++) m_outerIndex[j + 1]++;
1708 // initialize the coefficient
1709 m_data.index(dst) = StorageIndex(inner);
1710 m_data.value(dst) = Scalar(0);
1711 // return a reference to the coefficient
1712 return m_data.value(dst);
1713}
1714
1715template <typename Scalar_, int Options_, typename StorageIndex_>
1716typename SparseMatrix<Scalar_, Options_, StorageIndex_>::Scalar&
1717SparseMatrix<Scalar_, Options_, StorageIndex_>::insertUncompressedAtByOuterInner(Index outer, Index inner, Index dst) {
1718 eigen_assert(!isCompressed());
1719 // find a vector with capacity, starting at `outer` and searching to the left and right
1720 for (Index leftTarget = outer - 1, rightTarget = outer; (leftTarget >= 0) || (rightTarget < m_outerSize);) {
1721 if (rightTarget < m_outerSize) {
1722 Index start = internal::convert_index<Index>(m_outerIndex[rightTarget]);
1723 Index end = start + internal::convert_index<Index>(m_innerNonZeros[rightTarget]);
1724 Index nextStart = internal::convert_index<Index>(m_outerIndex[rightTarget + 1]);
1725 Index capacity = nextStart - end;
1726 if (capacity > 0) {
1727 // move [dst, end) to dst+1 and insert at dst
1728 internal::move_or_copy_backward(valuePtr() + dst, valuePtr() + end, valuePtr() + end + 1);
1729 std::move_backward(innerIndexPtr() + dst, innerIndexPtr() + end, innerIndexPtr() + end + 1);
1730 m_innerNonZeros[outer]++;
1731 for (Index j = outer; j < rightTarget; j++) m_outerIndex[j + 1]++;
1732 m_data.index(dst) = StorageIndex(inner);
1733 m_data.value(dst) = Scalar(0);
1734 return m_data.value(dst);
1735 }
1736 rightTarget++;
1737 }
1738 if (leftTarget >= 0) {
1739 Index start = internal::convert_index<Index>(m_outerIndex[leftTarget]);
1740 Index end = start + internal::convert_index<Index>(m_innerNonZeros[leftTarget]);
1741 Index nextStart = internal::convert_index<Index>(m_outerIndex[leftTarget + 1]);
1742 Index capacity = nextStart - end;
1743 if (capacity > 0) {
1744 // tricky: dst is a lower bound, so we must insert at dst-1 when shifting left
1745 // move [nextStart, dst) to nextStart-1 and insert at dst-1
1746 internal::move_or_copy(valuePtr() + nextStart, valuePtr() + dst, valuePtr() + nextStart - 1);
1747 std::move(innerIndexPtr() + nextStart, innerIndexPtr() + dst, innerIndexPtr() + nextStart - 1);
1748 m_innerNonZeros[outer]++;
1749 for (Index j = leftTarget; j < outer; j++) m_outerIndex[j + 1]--;
1750 m_data.index(dst - 1) = StorageIndex(inner);
1751 m_data.value(dst - 1) = Scalar(0);
1752 return m_data.value(dst - 1);
1753 }
1754 leftTarget--;
1755 }
1756 }
1757
1758 // no room for interior insertion
1759 // nonZeros() == m_data.size()
1760 // record offset as outerIndexPtr will change
1761 Index dst_offset = dst - internal::convert_index<Index>(m_outerIndex[outer]);
1762 // allocate space for random insertion
1763 // StorageIndex can be wider than Index (long long with a 32-bit Index), so clamp its maximum to Index's.
1764 using WideIndex = typename std::common_type<Index, StorageIndex>::type;
1765 const Index maxSize =
1766 static_cast<Index>(numext::mini<WideIndex>(NumTraits<StorageIndex>::highest(), NumTraits<Index>::highest()));
1767 if (m_data.allocatedSize() == 0 && m_outerSize <= maxSize) {
1768 // fast method to allocate space for one element per vector in empty matrix
1769 m_data.resize(m_outerSize);
1770 std::iota(m_outerIndex, m_outerIndex + m_outerSize + 1, StorageIndex(0));
1771 } else {
1772 // The index range bounds the stored entries, m_data.size() here; setZero() and reserve() can leave
1773 // allocatedSize() at the bound. A full matrix throws, as setFromTriplets() does.
1774 Index maxReserveSize = maxSize - m_data.size();
1775 if (maxReserveSize <= 0) internal::throw_std_bad_alloc();
1776 if (m_outerSize <= maxReserveSize) {
1777 // allocate space for one additional element per vector
1778 reserveInnerVectors(IndexVector::Constant(m_outerSize, 1));
1779 } else {
1780 // StorageIndex cannot hold outerSize more entries. Double the storage instead, capped by the index range, and
1781 // spread the new slots over the vectors from `outer` on. Reserving the whole range at once would allocate
1782 // highest() entries on the first insert into an empty matrix with an outer size past highest().
1783 Index reserveSize = numext::mini(maxReserveSize, numext::maxi<Index>(m_data.size(), 1));
1784 using ReserveSizesOp = internal::sparse_reserve_op<StorageIndex>;
1785 using ReserveSizesXpr = CwiseNullaryOp<ReserveSizesOp, IndexVector>;
1786 ReserveSizesXpr reserveSizesXpr(m_outerSize, 1, ReserveSizesOp(outer, m_outerSize, reserveSize));
1787 reserveInnerVectors(reserveSizesXpr);
1788 }
1789 }
1790 // insert element at `dst` with new outer indices
1791 Index start = internal::convert_index<Index>(m_outerIndex[outer]);
1792 Index end = start + internal::convert_index<Index>(m_innerNonZeros[outer]);
1793 Index new_dst = start + dst_offset;
1794 internal::move_or_copy_backward(valuePtr() + new_dst, valuePtr() + end, valuePtr() + end + 1);
1795 std::move_backward(innerIndexPtr() + new_dst, innerIndexPtr() + end, innerIndexPtr() + end + 1);
1796 m_innerNonZeros[outer]++;
1797 m_data.index(new_dst) = StorageIndex(inner);
1798 m_data.value(new_dst) = Scalar(0);
1799 return m_data.value(new_dst);
1800}
1801
1802namespace internal {
1803
1804template <typename Scalar_, int Options_, typename StorageIndex_>
1805struct evaluator<SparseMatrix<Scalar_, Options_, StorageIndex_>>
1806 : evaluator<SparseCompressedBase<SparseMatrix<Scalar_, Options_, StorageIndex_>>> {
1807 using Base = evaluator<SparseCompressedBase<SparseMatrix<Scalar_, Options_, StorageIndex_>>>;
1808 using SparseMatrixType = SparseMatrix<Scalar_, Options_, StorageIndex_>;
1809 evaluator() = default;
1810 explicit evaluator(const SparseMatrixType& mat) : Base(mat) {}
1811};
1812
1813} // namespace internal
1814
1815// Specialization for SparseMatrix.
1816// Serializes [rows, cols, isCompressed, outerSize, innerBufferSize,
1817// innerNonZeros, outerIndices, innerIndices, values].
1818template <typename Scalar, int Options, typename StorageIndex>
1819class Serializer<SparseMatrix<Scalar, Options, StorageIndex>, void> {
1820 public:
1821 using SparseMat = SparseMatrix<Scalar, Options, StorageIndex>;
1822
1823 struct Header {
1824 typename SparseMat::Index rows;
1825 typename SparseMat::Index cols;
1826 bool compressed;
1827 Index outer_size;
1828 Index inner_buffer_size;
1829 };
1830
1831 EIGEN_DEVICE_FUNC size_t size(const SparseMat& value) const {
1832 // innerNonZeros.
1833 std::size_t num_storage_indices = value.isCompressed() ? 0 : value.outerSize();
1834 // Outer indices.
1835 num_storage_indices += value.outerSize() + 1;
1836 // Inner indices.
1837 const StorageIndex inner_buffer_size = value.outerIndexPtr()[value.outerSize()];
1838 num_storage_indices += inner_buffer_size;
1839 // Values.
1840 std::size_t num_values = inner_buffer_size;
1841 return sizeof(Header) + sizeof(Scalar) * num_values + sizeof(StorageIndex) * num_storage_indices;
1842 }
1843
1844 EIGEN_DEVICE_FUNC uint8_t* serialize(uint8_t* dest, uint8_t* end, const SparseMat& value) {
1845 if (EIGEN_PREDICT_FALSE(dest == nullptr)) return nullptr;
1846 if (EIGEN_PREDICT_FALSE(dest + size(value) > end)) return nullptr;
1847
1848 const size_t header_bytes = sizeof(Header);
1849 Header header = {value.rows(), value.cols(), value.isCompressed(), value.outerSize(),
1850 value.outerIndexPtr()[value.outerSize()]};
1851 EIGEN_USING_STD(memcpy)
1852 memcpy(dest, &header, header_bytes);
1853 dest += header_bytes;
1854
1855 // Empty arrays may have null pointers, which memcpy does not accept even for zero bytes.
1856 // innerNonZeros.
1857 if (!header.compressed) {
1858 std::size_t data_bytes = sizeof(StorageIndex) * header.outer_size;
1859 if (data_bytes != 0) memcpy(dest, value.innerNonZeroPtr(), data_bytes);
1860 dest += data_bytes;
1861 }
1862
1863 // Outer indices.
1864 std::size_t data_bytes = sizeof(StorageIndex) * (header.outer_size + 1);
1865 memcpy(dest, value.outerIndexPtr(), data_bytes);
1866 dest += data_bytes;
1867
1868 // Inner indices.
1869 data_bytes = sizeof(StorageIndex) * header.inner_buffer_size;
1870 if (data_bytes != 0) memcpy(dest, value.innerIndexPtr(), data_bytes);
1871 dest += data_bytes;
1872
1873 // Values.
1874 data_bytes = sizeof(Scalar) * header.inner_buffer_size;
1875 if (data_bytes != 0) memcpy(dest, value.valuePtr(), data_bytes);
1876 dest += data_bytes;
1877
1878 return dest;
1879 }
1880
1881 EIGEN_DEVICE_FUNC const uint8_t* deserialize(const uint8_t* src, const uint8_t* end, SparseMat& value) const {
1882 if (EIGEN_PREDICT_FALSE(src == nullptr)) return nullptr;
1883 if (EIGEN_PREDICT_FALSE(src + sizeof(Header) > end)) return nullptr;
1884
1885 const size_t header_bytes = sizeof(Header);
1886 Header header;
1887 EIGEN_USING_STD(memcpy)
1888 memcpy(&header, src, header_bytes);
1889 src += header_bytes;
1890
1891 // The header is untrusted: check that the sizes agree and that the arrays fit in the buffer before allocating.
1892 // `compressed` is read through its byte, since a bool holding anything but 0 or 1 is undefined.
1893 unsigned char compressed_byte;
1894 memcpy(&compressed_byte, &header.compressed, 1);
1895 const bool compressed = compressed_byte == 1;
1896 numext::uint64_t remaining = static_cast<numext::uint64_t>(end - src);
1897 if (EIGEN_PREDICT_FALSE(
1898 compressed_byte > 1 || header.rows < 0 || header.cols < 0 ||
1899 header.outer_size != (SparseMat::IsRowMajor ? header.rows : header.cols) || header.inner_buffer_size < 0 ||
1900 header.inner_buffer_size > NumTraits<StorageIndex>::highest() ||
1901 !take(remaining, compressed ? 0 : header.outer_size, sizeof(StorageIndex)) ||
1902 !take(remaining, static_cast<numext::uint64_t>(header.outer_size) + 1, sizeof(StorageIndex)) ||
1903 !take(remaining, header.inner_buffer_size, sizeof(StorageIndex)) ||
1904 !take(remaining, header.inner_buffer_size, sizeof(Scalar))))
1905 return nullptr;
1906
1907 value.setZero();
1908 value.resize(header.rows, header.cols);
1909 if (compressed) {
1910 value.makeCompressed();
1911 } else {
1912 value.uncompress();
1913 }
1914
1915 // Adjust value ptr size.
1916 value.data().resize(header.inner_buffer_size);
1917
1918 // Initialize compressed state and inner non-zeros.
1919 if (!compressed) {
1920 // Inner non-zero counts.
1921 std::size_t data_bytes = sizeof(StorageIndex) * header.outer_size;
1922 if (data_bytes != 0) {
1923 memcpy(value.innerNonZeroPtr(), src, data_bytes);
1924 }
1925 src += data_bytes;
1926 }
1927
1928 // Outer indices.
1929 std::size_t data_bytes = sizeof(StorageIndex) * (header.outer_size + 1);
1930 memcpy(value.outerIndexPtr(), src, data_bytes);
1931 src += data_bytes;
1932
1933 // Inner indices.
1934 data_bytes = sizeof(StorageIndex) * header.inner_buffer_size;
1935 if (data_bytes != 0) {
1936 memcpy(value.innerIndexPtr(), src, data_bytes);
1937 }
1938 src += data_bytes;
1939
1940 // Values.
1941 data_bytes = sizeof(Scalar) * header.inner_buffer_size;
1942 if (data_bytes != 0) {
1943 memcpy(value.valuePtr(), src, data_bytes);
1944 }
1945 src += data_bytes;
1946
1947 if (EIGEN_PREDICT_FALSE(!valid_indices(value))) {
1948 value.resize(0, 0);
1949 return nullptr;
1950 }
1951 return src;
1952 }
1953
1954 private:
1955 // Takes count elements of elem_bytes each from the remaining bytes; false if they do not fit.
1956 EIGEN_DEVICE_FUNC static bool take(numext::uint64_t& remaining, numext::uint64_t count, std::size_t elem_bytes) {
1957 if (count > remaining / elem_bytes) return false;
1958 remaining -= count * elem_bytes;
1959 return true;
1960 }
1961
1962 // The index arrays are untrusted too. Outer vector j stores its entries in [outer[j], outer[j] + nnz[j]) of the
1963 // value buffer, nnz[j] = outer[j + 1] - outer[j] when compressed; each must lie in the buffer and have an inner index
1964 // in [0, innerSize()). Unused entries of an uncompressed matrix are not read.
1965 EIGEN_DEVICE_FUNC static bool valid_indices(const SparseMat& value) {
1966 const StorageIndex* outer = value.outerIndexPtr();
1967 const StorageIndex* inner_non_zeros = value.innerNonZeroPtr();
1968 const StorageIndex* inner = value.innerIndexPtr();
1969 const Index buffer_size = value.data().size();
1970 if (outer[0] != 0 || outer[value.outerSize()] != buffer_size) return false;
1971 for (Index j = 0; j < value.outerSize(); ++j) {
1972 if (outer[j + 1] < outer[j] || outer[j + 1] > buffer_size) return false;
1973 Index stop = outer[j + 1];
1974 if (inner_non_zeros != nullptr) {
1975 if (inner_non_zeros[j] < 0 || inner_non_zeros[j] > outer[j + 1] - outer[j]) return false;
1976 stop = outer[j] + inner_non_zeros[j];
1977 }
1978 for (Index k = outer[j]; k < stop; ++k) {
1979 if (inner[k] < 0 || inner[k] >= value.innerSize()) return false;
1980 }
1981 }
1982 return true;
1983 }
1984};
1985
1986} // end namespace Eigen
1987
1988#endif // EIGEN_SPARSEMATRIX_H
Base class for all dense matrices, vectors, and arrays.
Definition DenseBase.h:45
Derived & setConstant(const Scalar &value)
Definition CwiseNullaryOp.h:333
Base class for diagonal matrices and expressions.
Definition DiagonalMatrix.h:34
const Derived & derived() const
Definition DiagonalMatrix.h:60
Expression of a diagonal/subdiagonal/superdiagonal in a matrix.
Definition Diagonal.h:78
A matrix or vector expression mapping an existing array of data.
Definition Map.h:97
Common base class for sparse [compressed]-{row|column}-storage format.
Definition SparseCompressedBase.h:44
Index nonZeros() const
Definition SparseCompressedBase.h:65
bool isCompressed() const
Definition SparseCompressedBase.h:115
Base class of any sparse matrices or sparse expressions.
Definition SparseMatrixBase.h:31
typename NumTraits< Scalar >::Real RealScalar
Definition SparseMatrixBase.h:128
constexpr RowXpr row(Index i)
Definition SparseMatrixBase.h:1095
typename internal::traits< SparseMatrix< Scalar_, Options_, StorageIndex_ > >::StorageIndex StorageIndex
Definition SparseMatrixBase.h:45
constexpr ColXpr col(Index i)
Definition SparseMatrixBase.h:1082
@ Flags
Definition SparseMatrixBase.h:95
A versatile sparse matrix representation.
Definition SparseMatrix.h:121
Scalar coeff(Index row, Index col) const
Definition SparseMatrix.h:212
void resize(Index rows, NoChange_t)
Definition SparseMatrix.h:794
const ConstDiagonalReturnType diagonal() const
Definition SparseMatrix.h:801
void swap(SparseMatrix &other)
Definition SparseMatrix.h:873
void insertFromSortedTriplets(const InputIterators &begin, const InputIterators &end, DupFunctor dup_func)
Definition SparseMatrix.h:1515
const StorageIndex * innerIndexPtr() const
Definition SparseMatrix.h:181
void setZero()
Definition SparseMatrix.h:305
bool isCompressed() const
Definition SparseCompressedBase.h:115
Index cols() const
Definition SparseMatrix.h:162
StorageIndex * innerIndexPtr()
Definition SparseMatrix.h:185
SparseMatrix(const ReturnByValue< OtherDerived > &other)
Copy constructor with in-place evaluation.
Definition SparseMatrix.h:858
void setFromSortedTriplets(const InputIterators &begin, const InputIterators &end)
Definition SparseMatrix.h:1405
void setFromTriplets(const InputIterators &begin, const InputIterators &end, DupFunctor dup_func)
Definition SparseMatrix.h:1393
Index outerSize() const
Definition SparseMatrix.h:167
SparseMatrix()
Definition SparseMatrix.h:810
void uncompress()
Definition SparseMatrix.h:644
void insertFromSortedTriplets(const InputIterators &begin, const InputIterators &end)
Definition SparseMatrix.h:1498
const Scalar * valuePtr() const
Definition SparseMatrix.h:172
void makeCompressed()
Definition SparseMatrix.h:607
void setFromSortedTriplets(const InputIterators &begin, const InputIterators &end, DupFunctor dup_func)
Definition SparseMatrix.h:1422
SparseMatrix(const SparseSelfAdjointView< OtherDerived, UpLo > &other)
Definition SparseMatrix.h:837
void resize(Index rows, Index cols)
Definition SparseMatrix.h:772
void conservativeResize(Index rows, NoChange_t)
Definition SparseMatrix.h:763
Index rows() const
Definition SparseMatrix.h:160
SparseMatrix(const SparseMatrix &other)
Definition SparseMatrix.h:851
StorageIndex * innerNonZeroPtr()
Definition SparseMatrix.h:203
void setFromTriplets(const InputIterators &begin, const InputIterators &end)
Definition SparseMatrix.h:1376
SparseMatrix(const DiagonalBase< OtherDerived > &other)
Copy constructor with in-place evaluation.
Definition SparseMatrix.h:866
void setIdentity()
Definition SparseMatrix.h:885
Index innerSize() const
Definition SparseMatrix.h:165
SparseMatrix(Index rows, Index cols)
Definition SparseMatrix.h:813
StorageIndex * outerIndexPtr()
Definition SparseMatrix.h:194
const StorageIndex * innerNonZeroPtr() const
Definition SparseMatrix.h:199
void conservativeResize(Index rows, Index cols)
Definition SparseMatrix.h:713
void insertFromTriplets(const InputIterators &begin, const InputIterators &end, DupFunctor dup_func)
Definition SparseMatrix.h:1486
void prune(const Scalar &reference, const RealScalar &epsilon=NumTraits< RealScalar >::dummy_precision())
Definition SparseMatrix.h:656
const StorageIndex * outerIndexPtr() const
Definition SparseMatrix.h:190
SparseMatrix(const SparseMatrixBase< OtherDerived > &other)
Definition SparseMatrix.h:819
friend void swap(SparseMatrix &a, SparseMatrix &b)
Definition SparseMatrix.h:881
~SparseMatrix()
Definition SparseMatrix.h:972
Scalar * valuePtr()
Definition SparseMatrix.h:176
void prune(const KeepFunc &keep=KeepFunc())
Definition SparseMatrix.h:669
void conservativeResize(NoChange_t, Index cols)
Definition SparseMatrix.h:760
Scalar sum() const
Definition SparseRedux.h:32
void reserve(Index reserveSize)
Definition SparseMatrix.h:317
Scalar & coeffRef(Index row, Index col)
Definition SparseMatrix.h:276
Scalar & insert(Index row, Index col)
Definition SparseMatrix.h:1637
void reserve(const SizesType &reserveSizes)
DiagonalReturnType diagonal()
Definition SparseMatrix.h:807
void resize(NoChange_t, Index cols)
Definition SparseMatrix.h:791
Scalar & findOrInsertCoeff(Index row, Index col, bool *inserted)
Definition SparseMatrix.h:232
void insertFromTriplets(const InputIterators &begin, const InputIterators &end)
Definition SparseMatrix.h:1469
SparseMatrix(SparseMatrix &&other)
Definition SparseMatrix.h:843
Pseudo expression to manipulate a triangular sparse matrix as a selfadjoint matrix.
Definition SparseSelfAdjointView.h:53
a sparse vector class
Definition SparseVector.h:63
@ RowMajor
Definition Constants.h:321
constexpr unsigned int LvalueBit
Definition Constants.h:149
constexpr unsigned int RowMajorBit
Definition Constants.h:71
constexpr unsigned int CompressedAccessBit
Definition Constants.h:196
constexpr Derived & derived()
Definition EigenBase.h:50
constexpr Index size() const noexcept
Definition EigenBase.h:65