SparseMatrix.h revision c981c48f5bc9aefeffc0bcb0cc3934c2fae179dd
1c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath// This file is part of Eigen, a lightweight C++ template library 2c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath// for linear algebra. 3c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath// 4c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath// Copyright (C) 2008-2010 Gael Guennebaud <gael.guennebaud@inria.fr> 5c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath// 6c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath// This Source Code Form is subject to the terms of the Mozilla 7c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath// Public License v. 2.0. If a copy of the MPL was not distributed 8c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath// with this file, You can obtain one at http://mozilla.org/MPL/2.0/. 9c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 10c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath#ifndef EIGEN_SPARSEMATRIX_H 11c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath#define EIGEN_SPARSEMATRIX_H 12c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 13c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamathnamespace Eigen { 14c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 15c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath/** \ingroup SparseCore_Module 16c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * 17c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \class SparseMatrix 18c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * 19c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \brief A versatible sparse matrix representation 20c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * 21c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * This class implements a more versatile variants of the common \em compressed row/column storage format. 22c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * Each colmun's (resp. row) non zeros are stored as a pair of value with associated row (resp. colmiun) index. 23c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * All the non zeros are stored in a single large buffer. Unlike the \em compressed format, there might be extra 24c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * space inbetween the nonzeros of two successive colmuns (resp. rows) such that insertion of new non-zero 25c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * can be done with limited memory reallocation and copies. 26c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * 27c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * A call to the function makeCompressed() turns the matrix into the standard \em compressed format 28c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * compatible with many library. 29c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * 30c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * More details on this storage sceheme are given in the \ref TutorialSparse "manual pages". 31c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * 32c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \tparam _Scalar the scalar type, i.e. the type of the coefficients 33c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \tparam _Options Union of bit flags controlling the storage scheme. Currently the only possibility 34c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * is RowMajor. The default is 0 which means column-major. 35c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \tparam _Index the type of the indices. It has to be a \b signed type (e.g., short, int, std::ptrdiff_t). Default is \c int. 36c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * 37c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * This class can be extended with the help of the plugin mechanism described on the page 38c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \ref TopicCustomizingEigen by defining the preprocessor symbol \c EIGEN_SPARSEMATRIX_PLUGIN. 39c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath */ 40c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 41c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamathnamespace internal { 42c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamathtemplate<typename _Scalar, int _Options, typename _Index> 43c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamathstruct traits<SparseMatrix<_Scalar, _Options, _Index> > 44c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath{ 45c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath typedef _Scalar Scalar; 46c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath typedef _Index Index; 47c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath typedef Sparse StorageKind; 48c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath typedef MatrixXpr XprKind; 49c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath enum { 50c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath RowsAtCompileTime = Dynamic, 51c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath ColsAtCompileTime = Dynamic, 52c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath MaxRowsAtCompileTime = Dynamic, 53c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath MaxColsAtCompileTime = Dynamic, 54c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Flags = _Options | NestByRefBit | LvalueBit, 55c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath CoeffReadCost = NumTraits<Scalar>::ReadCost, 56c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath SupportedAccessPatterns = InnerRandomAccessPattern 57c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath }; 58c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath}; 59c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 60c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamathtemplate<typename _Scalar, int _Options, typename _Index, int DiagIndex> 61c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamathstruct traits<Diagonal<const SparseMatrix<_Scalar, _Options, _Index>, DiagIndex> > 62c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath{ 63c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath typedef SparseMatrix<_Scalar, _Options, _Index> MatrixType; 64c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath typedef typename nested<MatrixType>::type MatrixTypeNested; 65c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath typedef typename remove_reference<MatrixTypeNested>::type _MatrixTypeNested; 66c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 67c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath typedef _Scalar Scalar; 68c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath typedef Dense StorageKind; 69c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath typedef _Index Index; 70c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath typedef MatrixXpr XprKind; 71c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 72c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath enum { 73c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath RowsAtCompileTime = Dynamic, 74c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath ColsAtCompileTime = 1, 75c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath MaxRowsAtCompileTime = Dynamic, 76c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath MaxColsAtCompileTime = 1, 77c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Flags = 0, 78c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath CoeffReadCost = _MatrixTypeNested::CoeffReadCost*10 79c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath }; 80c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath}; 81c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 82c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath} // end namespace internal 83c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 84c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamathtemplate<typename _Scalar, int _Options, typename _Index> 85c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamathclass SparseMatrix 86c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath : public SparseMatrixBase<SparseMatrix<_Scalar, _Options, _Index> > 87c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath{ 88c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath public: 89c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath EIGEN_SPARSE_PUBLIC_INTERFACE(SparseMatrix) 90c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath EIGEN_SPARSE_INHERIT_ASSIGNMENT_OPERATOR(SparseMatrix, +=) 91c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath EIGEN_SPARSE_INHERIT_ASSIGNMENT_OPERATOR(SparseMatrix, -=) 92c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 93c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath typedef MappedSparseMatrix<Scalar,Flags> Map; 94c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath using Base::IsRowMajor; 95c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath typedef internal::CompressedStorage<Scalar,Index> Storage; 96c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath enum { 97c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Options = _Options 98c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath }; 99c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 100c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath protected: 101c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 102c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath typedef SparseMatrix<Scalar,(Flags&~RowMajorBit)|(IsRowMajor?RowMajorBit:0)> TransposedSparseMatrix; 103c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 104c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index m_outerSize; 105c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index m_innerSize; 106c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index* m_outerIndex; 107c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index* m_innerNonZeros; // optional, if null then the data is compressed 108c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Storage m_data; 109c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 110c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Eigen::Map<Matrix<Index,Dynamic,1> > innerNonZeros() { return Eigen::Map<Matrix<Index,Dynamic,1> >(m_innerNonZeros, m_innerNonZeros?m_outerSize:0); } 111c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath const Eigen::Map<const Matrix<Index,Dynamic,1> > innerNonZeros() const { return Eigen::Map<const Matrix<Index,Dynamic,1> >(m_innerNonZeros, m_innerNonZeros?m_outerSize:0); } 112c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 113c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath public: 114c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 115c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \returns whether \c *this is in compressed form. */ 116c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline bool isCompressed() const { return m_innerNonZeros==0; } 117c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 118c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \returns the number of rows of the matrix */ 119c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline Index rows() const { return IsRowMajor ? m_outerSize : m_innerSize; } 120c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \returns the number of columns of the matrix */ 121c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline Index cols() const { return IsRowMajor ? m_innerSize : m_outerSize; } 122c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 123c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \returns the number of rows (resp. columns) of the matrix if the storage order column major (resp. row major) */ 124c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline Index innerSize() const { return m_innerSize; } 125c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \returns the number of columns (resp. rows) of the matrix if the storage order column major (resp. row major) */ 126c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline Index outerSize() const { return m_outerSize; } 127c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 128c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \returns a const pointer to the array of values. 129c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * This function is aimed at interoperability with other libraries. 130c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \sa innerIndexPtr(), outerIndexPtr() */ 131c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline const Scalar* valuePtr() const { return &m_data.value(0); } 132c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \returns a non-const pointer to the array of values. 133c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * This function is aimed at interoperability with other libraries. 134c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \sa innerIndexPtr(), outerIndexPtr() */ 135c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline Scalar* valuePtr() { return &m_data.value(0); } 136c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 137c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \returns a const pointer to the array of inner indices. 138c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * This function is aimed at interoperability with other libraries. 139c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \sa valuePtr(), outerIndexPtr() */ 140c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline const Index* innerIndexPtr() const { return &m_data.index(0); } 141c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \returns a non-const pointer to the array of inner indices. 142c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * This function is aimed at interoperability with other libraries. 143c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \sa valuePtr(), outerIndexPtr() */ 144c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline Index* innerIndexPtr() { return &m_data.index(0); } 145c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 146c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \returns a const pointer to the array of the starting positions of the inner vectors. 147c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * This function is aimed at interoperability with other libraries. 148c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \sa valuePtr(), innerIndexPtr() */ 149c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline const Index* outerIndexPtr() const { return m_outerIndex; } 150c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \returns a non-const pointer to the array of the starting positions of the inner vectors. 151c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * This function is aimed at interoperability with other libraries. 152c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \sa valuePtr(), innerIndexPtr() */ 153c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline Index* outerIndexPtr() { return m_outerIndex; } 154c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 155c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \returns a const pointer to the array of the number of non zeros of the inner vectors. 156c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * This function is aimed at interoperability with other libraries. 157c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \warning it returns the null pointer 0 in compressed mode */ 158c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline const Index* innerNonZeroPtr() const { return m_innerNonZeros; } 159c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \returns a non-const pointer to the array of the number of non zeros of the inner vectors. 160c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * This function is aimed at interoperability with other libraries. 161c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \warning it returns the null pointer 0 in compressed mode */ 162c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline Index* innerNonZeroPtr() { return m_innerNonZeros; } 163c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 164c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \internal */ 165c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline Storage& data() { return m_data; } 166c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \internal */ 167c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline const Storage& data() const { return m_data; } 168c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 169c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \returns the value of the matrix at position \a i, \a j 170c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * This function returns Scalar(0) if the element is an explicit \em zero */ 171c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline Scalar coeff(Index row, Index col) const 172c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 173c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath const Index outer = IsRowMajor ? row : col; 174c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath const Index inner = IsRowMajor ? col : row; 175c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index end = m_innerNonZeros ? m_outerIndex[outer] + m_innerNonZeros[outer] : m_outerIndex[outer+1]; 176c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath return m_data.atInRange(m_outerIndex[outer], end, inner); 177c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 178c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 179c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \returns a non-const reference to the value of the matrix at position \a i, \a j 180c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * 181c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * If the element does not exist then it is inserted via the insert(Index,Index) function 182c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * which itself turns the matrix into a non compressed form if that was not the case. 183c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * 184c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * This is a O(log(nnz_j)) operation (binary search) plus the cost of insert(Index,Index) 185c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * function if the element does not already exist. 186c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath */ 187c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline Scalar& coeffRef(Index row, Index col) 188c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 189c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath const Index outer = IsRowMajor ? row : col; 190c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath const Index inner = IsRowMajor ? col : row; 191c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 192c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index start = m_outerIndex[outer]; 193c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index end = m_innerNonZeros ? m_outerIndex[outer] + m_innerNonZeros[outer] : m_outerIndex[outer+1]; 194c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath eigen_assert(end>=start && "you probably called coeffRef on a non finalized matrix"); 195c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if(end<=start) 196c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath return insert(row,col); 197c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath const Index p = m_data.searchLowerIndex(start,end-1,inner); 198c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if((p<end) && (m_data.index(p)==inner)) 199c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath return m_data.value(p); 200c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath else 201c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath return insert(row,col); 202c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 203c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 204c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \returns a reference to a novel non zero coefficient with coordinates \a row x \a col. 205c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * The non zero coefficient must \b not already exist. 206c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * 207c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * If the matrix \c *this is in compressed mode, then \c *this is turned into uncompressed 208c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * mode while reserving room for 2 non zeros per inner vector. It is strongly recommended to first 209c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * call reserve(const SizesType &) to reserve a more appropriate number of elements per 210c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * inner vector that better match your scenario. 211c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * 212c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * This function performs a sorted insertion in O(1) if the elements of each inner vector are 213c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * inserted in increasing inner index order, and in O(nnz_j) for a random insertion. 214c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * 215c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath */ 216c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath EIGEN_DONT_INLINE Scalar& insert(Index row, Index col) 217c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 218c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if(isCompressed()) 219c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 220c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath reserve(VectorXi::Constant(outerSize(), 2)); 221c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 222c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath return insertUncompressed(row,col); 223c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 224c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 225c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath public: 226c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 227c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath class InnerIterator; 228c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath class ReverseInnerIterator; 229c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 230c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** Removes all non zeros but keep allocated memory */ 231c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline void setZero() 232c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 233c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.clear(); 234c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath memset(m_outerIndex, 0, (m_outerSize+1)*sizeof(Index)); 235c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if(m_innerNonZeros) 236c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath memset(m_innerNonZeros, 0, (m_outerSize)*sizeof(Index)); 237c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 238c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 239c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \returns the number of non zero coefficients */ 240c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline Index nonZeros() const 241c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 242c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if(m_innerNonZeros) 243c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath return innerNonZeros().sum(); 244c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath return static_cast<Index>(m_data.size()); 245c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 246c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 247c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** Preallocates \a reserveSize non zeros. 248c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * 249c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * Precondition: the matrix must be in compressed mode. */ 250c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline void reserve(Index reserveSize) 251c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 252c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath eigen_assert(isCompressed() && "This function does not make sense in non compressed mode."); 253c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.reserve(reserveSize); 254c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 255c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 256c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath #ifdef EIGEN_PARSED_BY_DOXYGEN 257c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** Preallocates \a reserveSize[\c j] non zeros for each column (resp. row) \c j. 258c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * 259c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * This function turns the matrix in non-compressed mode */ 260c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath template<class SizesType> 261c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline void reserve(const SizesType& reserveSizes); 262c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath #else 263c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath template<class SizesType> 264c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline void reserve(const SizesType& reserveSizes, const typename SizesType::value_type& enableif = typename SizesType::value_type()) 265c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 266c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath EIGEN_UNUSED_VARIABLE(enableif); 267c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath reserveInnerVectors(reserveSizes); 268c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 269c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath template<class SizesType> 270c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline void reserve(const SizesType& reserveSizes, const typename SizesType::Scalar& enableif = 271c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath #if (!defined(_MSC_VER)) || (_MSC_VER>=1500) // MSVC 2005 fails to compile with this typename 272c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath typename 273c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath #endif 274c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath SizesType::Scalar()) 275c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 276c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath EIGEN_UNUSED_VARIABLE(enableif); 277c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath reserveInnerVectors(reserveSizes); 278c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 279c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath #endif // EIGEN_PARSED_BY_DOXYGEN 280c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath protected: 281c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath template<class SizesType> 282c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline void reserveInnerVectors(const SizesType& reserveSizes) 283c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 284c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 285c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if(isCompressed()) 286c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 287c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath std::size_t totalReserveSize = 0; 288c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // turn the matrix into non-compressed mode 289c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_innerNonZeros = new Index[m_outerSize]; 290c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 291c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // temporarily use m_innerSizes to hold the new starting points. 292c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index* newOuterIndex = m_innerNonZeros; 293c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 294c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index count = 0; 295c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath for(Index j=0; j<m_outerSize; ++j) 296c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 297c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath newOuterIndex[j] = count; 298c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath count += reserveSizes[j] + (m_outerIndex[j+1]-m_outerIndex[j]); 299c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath totalReserveSize += reserveSizes[j]; 300c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 301c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.reserve(totalReserveSize); 302c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath std::ptrdiff_t previousOuterIndex = m_outerIndex[m_outerSize]; 303c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath for(std::ptrdiff_t j=m_outerSize-1; j>=0; --j) 304c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 305c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath ptrdiff_t innerNNZ = previousOuterIndex - m_outerIndex[j]; 306c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath for(std::ptrdiff_t i=innerNNZ-1; i>=0; --i) 307c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 308c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.index(newOuterIndex[j]+i) = m_data.index(m_outerIndex[j]+i); 309c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.value(newOuterIndex[j]+i) = m_data.value(m_outerIndex[j]+i); 310c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 311c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath previousOuterIndex = m_outerIndex[j]; 312c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_outerIndex[j] = newOuterIndex[j]; 313c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_innerNonZeros[j] = innerNNZ; 314c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 315c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_outerIndex[m_outerSize] = m_outerIndex[m_outerSize-1] + m_innerNonZeros[m_outerSize-1] + reserveSizes[m_outerSize-1]; 316c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 317c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.resize(m_outerIndex[m_outerSize]); 318c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 319c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath else 320c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 321c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index* newOuterIndex = new Index[m_outerSize+1]; 322c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index count = 0; 323c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath for(Index j=0; j<m_outerSize; ++j) 324c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 325c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath newOuterIndex[j] = count; 326c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index alreadyReserved = (m_outerIndex[j+1]-m_outerIndex[j]) - m_innerNonZeros[j]; 327c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index toReserve = std::max<std::ptrdiff_t>(reserveSizes[j], alreadyReserved); 328c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath count += toReserve + m_innerNonZeros[j]; 329c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 330c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath newOuterIndex[m_outerSize] = count; 331c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 332c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.resize(count); 333c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath for(ptrdiff_t j=m_outerSize-1; j>=0; --j) 334c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 335c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath std::ptrdiff_t offset = newOuterIndex[j] - m_outerIndex[j]; 336c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if(offset>0) 337c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 338c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath std::ptrdiff_t innerNNZ = m_innerNonZeros[j]; 339c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath for(std::ptrdiff_t i=innerNNZ-1; i>=0; --i) 340c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 341c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.index(newOuterIndex[j]+i) = m_data.index(m_outerIndex[j]+i); 342c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.value(newOuterIndex[j]+i) = m_data.value(m_outerIndex[j]+i); 343c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 344c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 345c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 346c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 347c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath std::swap(m_outerIndex, newOuterIndex); 348c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath delete[] newOuterIndex; 349c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 350c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 351c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 352c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath public: 353c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 354c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath //--- low level purely coherent filling --- 355c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 356c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \internal 357c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \returns a reference to the non zero coefficient at position \a row, \a col assuming that: 358c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * - the nonzero does not already exist 359c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * - the new coefficient is the last one according to the storage order 360c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * 361c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * Before filling a given inner vector you must call the statVec(Index) function. 362c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * 363c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * After an insertion session, you should call the finalize() function. 364c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * 365c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \sa insert, insertBackByOuterInner, startVec */ 366c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline Scalar& insertBack(Index row, Index col) 367c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 368c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath return insertBackByOuterInner(IsRowMajor?row:col, IsRowMajor?col:row); 369c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 370c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 371c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \internal 372c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \sa insertBack, startVec */ 373c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline Scalar& insertBackByOuterInner(Index outer, Index inner) 374c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 375c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath eigen_assert(size_t(m_outerIndex[outer+1]) == m_data.size() && "Invalid ordered insertion (invalid outer index)"); 376c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath eigen_assert( (m_outerIndex[outer+1]-m_outerIndex[outer]==0 || m_data.index(m_data.size()-1)<inner) && "Invalid ordered insertion (invalid inner index)"); 377c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index p = m_outerIndex[outer+1]; 378c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath ++m_outerIndex[outer+1]; 379c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.append(0, inner); 380c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath return m_data.value(p); 381c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 382c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 383c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \internal 384c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \warning use it only if you know what you are doing */ 385c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline Scalar& insertBackByOuterInnerUnordered(Index outer, Index inner) 386c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 387c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index p = m_outerIndex[outer+1]; 388c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath ++m_outerIndex[outer+1]; 389c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.append(0, inner); 390c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath return m_data.value(p); 391c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 392c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 393c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \internal 394c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \sa insertBack, insertBackByOuterInner */ 395c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline void startVec(Index outer) 396c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 397c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath eigen_assert(m_outerIndex[outer]==int(m_data.size()) && "You must call startVec for each inner vector sequentially"); 398c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath eigen_assert(m_outerIndex[outer+1]==0 && "You must call startVec for each inner vector sequentially"); 399c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_outerIndex[outer+1] = m_outerIndex[outer]; 400c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 401c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 402c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \internal 403c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * Must be called after inserting a set of non zero entries using the low level compressed API. 404c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath */ 405c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline void finalize() 406c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 407c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if(isCompressed()) 408c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 409c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index size = static_cast<Index>(m_data.size()); 410c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index i = m_outerSize; 411c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // find the last filled column 412c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath while (i>=0 && m_outerIndex[i]==0) 413c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath --i; 414c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath ++i; 415c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath while (i<=m_outerSize) 416c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 417c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_outerIndex[i] = size; 418c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath ++i; 419c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 420c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 421c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 422c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 423c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath //--- 424c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 425c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath template<typename InputIterators> 426c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath void setFromTriplets(const InputIterators& begin, const InputIterators& end); 427c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 428c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath void sumupDuplicates(); 429c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 430c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath //--- 431c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 432c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \internal 433c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * same as insert(Index,Index) except that the indices are given relative to the storage order */ 434c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath EIGEN_DONT_INLINE Scalar& insertByOuterInner(Index j, Index i) 435c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 436c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath return insert(IsRowMajor ? j : i, IsRowMajor ? i : j); 437c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 438c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 439c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** Turns the matrix into the \em compressed format. 440c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath */ 441c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath void makeCompressed() 442c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 443c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if(isCompressed()) 444c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath return; 445c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 446c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index oldStart = m_outerIndex[1]; 447c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_outerIndex[1] = m_innerNonZeros[0]; 448c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath for(Index j=1; j<m_outerSize; ++j) 449c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 450c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index nextOldStart = m_outerIndex[j+1]; 451c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath std::ptrdiff_t offset = oldStart - m_outerIndex[j]; 452c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if(offset>0) 453c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 454c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath for(Index k=0; k<m_innerNonZeros[j]; ++k) 455c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 456c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.index(m_outerIndex[j]+k) = m_data.index(oldStart+k); 457c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.value(m_outerIndex[j]+k) = m_data.value(oldStart+k); 458c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 459c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 460c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_outerIndex[j+1] = m_outerIndex[j] + m_innerNonZeros[j]; 461c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath oldStart = nextOldStart; 462c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 463c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath delete[] m_innerNonZeros; 464c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_innerNonZeros = 0; 465c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.resize(m_outerIndex[m_outerSize]); 466c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.squeeze(); 467c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 468c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 469c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** Suppresses all nonzeros which are \b much \b smaller \b than \a reference under the tolerence \a epsilon */ 470c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath void prune(Scalar reference, RealScalar epsilon = NumTraits<RealScalar>::dummy_precision()) 471c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 472c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath prune(default_prunning_func(reference,epsilon)); 473c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 474c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 475c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** Turns the matrix into compressed format, and suppresses all nonzeros which do not satisfy the predicate \a keep. 476c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * The functor type \a KeepFunc must implement the following function: 477c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \code 478c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * bool operator() (const Index& row, const Index& col, const Scalar& value) const; 479c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \endcode 480c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \sa prune(Scalar,RealScalar) 481c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath */ 482c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath template<typename KeepFunc> 483c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath void prune(const KeepFunc& keep = KeepFunc()) 484c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 485c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // TODO optimize the uncompressed mode to avoid moving and allocating the data twice 486c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // TODO also implement a unit test 487c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath makeCompressed(); 488c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 489c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index k = 0; 490c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath for(Index j=0; j<m_outerSize; ++j) 491c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 492c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index previousStart = m_outerIndex[j]; 493c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_outerIndex[j] = k; 494c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index end = m_outerIndex[j+1]; 495c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath for(Index i=previousStart; i<end; ++i) 496c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 497c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if(keep(IsRowMajor?j:m_data.index(i), IsRowMajor?m_data.index(i):j, m_data.value(i))) 498c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 499c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.value(k) = m_data.value(i); 500c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.index(k) = m_data.index(i); 501c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath ++k; 502c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 503c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 504c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 505c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_outerIndex[m_outerSize] = k; 506c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.resize(k,0); 507c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 508c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 509c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** Resizes the matrix to a \a rows x \a cols matrix and initializes it to zero. 510c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \sa resizeNonZeros(Index), reserve(), setZero() 511c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath */ 512c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath void resize(Index rows, Index cols) 513c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 514c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath const Index outerSize = IsRowMajor ? rows : cols; 515c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_innerSize = IsRowMajor ? cols : rows; 516c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.clear(); 517c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if (m_outerSize != outerSize || m_outerSize==0) 518c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 519c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath delete[] m_outerIndex; 520c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_outerIndex = new Index [outerSize+1]; 521c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_outerSize = outerSize; 522c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 523c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if(m_innerNonZeros) 524c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 525c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath delete[] m_innerNonZeros; 526c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_innerNonZeros = 0; 527c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 528c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath memset(m_outerIndex, 0, (m_outerSize+1)*sizeof(Index)); 529c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 530c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 531c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \internal 532c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * Resize the nonzero vector to \a size */ 533c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath void resizeNonZeros(Index size) 534c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 535c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // TODO remove this function 536c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.resize(size); 537c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 538c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 539c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \returns a const expression of the diagonal coefficients */ 540c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath const Diagonal<const SparseMatrix> diagonal() const { return *this; } 541c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 542c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** Default constructor yielding an empty \c 0 \c x \c 0 matrix */ 543c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline SparseMatrix() 544c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath : m_outerSize(-1), m_innerSize(0), m_outerIndex(0), m_innerNonZeros(0) 545c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 546c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath check_template_parameters(); 547c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath resize(0, 0); 548c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 549c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 550c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** Constructs a \a rows \c x \a cols empty matrix */ 551c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline SparseMatrix(Index rows, Index cols) 552c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath : m_outerSize(0), m_innerSize(0), m_outerIndex(0), m_innerNonZeros(0) 553c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 554c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath check_template_parameters(); 555c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath resize(rows, cols); 556c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 557c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 558c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** Constructs a sparse matrix from the sparse expression \a other */ 559c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath template<typename OtherDerived> 560c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline SparseMatrix(const SparseMatrixBase<OtherDerived>& other) 561c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath : m_outerSize(0), m_innerSize(0), m_outerIndex(0), m_innerNonZeros(0) 562c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 563c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath check_template_parameters(); 564c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath *this = other.derived(); 565c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 566c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 567c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** Copy constructor (it performs a deep copy) */ 568c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline SparseMatrix(const SparseMatrix& other) 569c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath : Base(), m_outerSize(0), m_innerSize(0), m_outerIndex(0), m_innerNonZeros(0) 570c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 571c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath check_template_parameters(); 572c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath *this = other.derived(); 573c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 574c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 575c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** Swaps the content of two sparse matrices of the same type. 576c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * This is a fast operation that simply swaps the underlying pointers and parameters. */ 577c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline void swap(SparseMatrix& other) 578c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 579c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath //EIGEN_DBG_SPARSE(std::cout << "SparseMatrix:: swap\n"); 580c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath std::swap(m_outerIndex, other.m_outerIndex); 581c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath std::swap(m_innerSize, other.m_innerSize); 582c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath std::swap(m_outerSize, other.m_outerSize); 583c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath std::swap(m_innerNonZeros, other.m_innerNonZeros); 584c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.swap(other.m_data); 585c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 586c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 587c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline SparseMatrix& operator=(const SparseMatrix& other) 588c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 589c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if (other.isRValue()) 590c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 591c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath swap(other.const_cast_derived()); 592c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 593c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath else 594c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 595c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath initAssignment(other); 596c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if(other.isCompressed()) 597c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 598c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath memcpy(m_outerIndex, other.m_outerIndex, (m_outerSize+1)*sizeof(Index)); 599c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data = other.m_data; 600c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 601c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath else 602c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 603c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Base::operator=(other); 604c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 605c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 606c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath return *this; 607c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 608c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 609c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath #ifndef EIGEN_PARSED_BY_DOXYGEN 610c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath template<typename Lhs, typename Rhs> 611c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline SparseMatrix& operator=(const SparseSparseProduct<Lhs,Rhs>& product) 612c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { return Base::operator=(product); } 613c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 614c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath template<typename OtherDerived> 615c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline SparseMatrix& operator=(const ReturnByValue<OtherDerived>& other) 616c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { return Base::operator=(other.derived()); } 617c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 618c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath template<typename OtherDerived> 619c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline SparseMatrix& operator=(const EigenBase<OtherDerived>& other) 620c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { return Base::operator=(other.derived()); } 621c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath #endif 622c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 623c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath template<typename OtherDerived> 624c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath EIGEN_DONT_INLINE SparseMatrix& operator=(const SparseMatrixBase<OtherDerived>& other) 625c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 626c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath initAssignment(other.derived()); 627c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath const bool needToTranspose = (Flags & RowMajorBit) != (OtherDerived::Flags & RowMajorBit); 628c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if (needToTranspose) 629c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 630c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // two passes algorithm: 631c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // 1 - compute the number of coeffs per dest inner vector 632c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // 2 - do the actual copy/eval 633c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // Since each coeff of the rhs has to be evaluated twice, let's evaluate it if needed 634c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath typedef typename internal::nested<OtherDerived,2>::type OtherCopy; 635c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath typedef typename internal::remove_all<OtherCopy>::type _OtherCopy; 636c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath OtherCopy otherCopy(other.derived()); 637c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 638c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Eigen::Map<Matrix<Index, Dynamic, 1> > (m_outerIndex,outerSize()).setZero(); 639c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // pass 1 640c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // FIXME the above copy could be merged with that pass 641c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath for (Index j=0; j<otherCopy.outerSize(); ++j) 642c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath for (typename _OtherCopy::InnerIterator it(otherCopy, j); it; ++it) 643c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath ++m_outerIndex[it.index()]; 644c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 645c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // prefix sum 646c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index count = 0; 647c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath VectorXi positions(outerSize()); 648c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath for (Index j=0; j<outerSize(); ++j) 649c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 650c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index tmp = m_outerIndex[j]; 651c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_outerIndex[j] = count; 652c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath positions[j] = count; 653c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath count += tmp; 654c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 655c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_outerIndex[outerSize()] = count; 656c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // alloc 657c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.resize(count); 658c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // pass 2 659c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath for (Index j=0; j<otherCopy.outerSize(); ++j) 660c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 661c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath for (typename _OtherCopy::InnerIterator it(otherCopy, j); it; ++it) 662c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 663c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index pos = positions[it.index()]++; 664c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.index(pos) = j; 665c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.value(pos) = it.value(); 666c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 667c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 668c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath return *this; 669c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 670c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath else 671c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 672c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // there is no special optimization 673c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath return Base::operator=(other.derived()); 674c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 675c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 676c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 677c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath friend std::ostream & operator << (std::ostream & s, const SparseMatrix& m) 678c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 679c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath EIGEN_DBG_SPARSE( 680c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath s << "Nonzero entries:\n"; 681c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if(m.isCompressed()) 682c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath for (Index i=0; i<m.nonZeros(); ++i) 683c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath s << "(" << m.m_data.value(i) << "," << m.m_data.index(i) << ") "; 684c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath else 685c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath for (Index i=0; i<m.outerSize(); ++i) 686c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 687c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath int p = m.m_outerIndex[i]; 688c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath int pe = m.m_outerIndex[i]+m.m_innerNonZeros[i]; 689c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index k=p; 690c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath for (; k<pe; ++k) 691c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath s << "(" << m.m_data.value(k) << "," << m.m_data.index(k) << ") "; 692c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath for (; k<m.m_outerIndex[i+1]; ++k) 693c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath s << "(_,_) "; 694c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 695c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath s << std::endl; 696c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath s << std::endl; 697c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath s << "Outer pointers:\n"; 698c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath for (Index i=0; i<m.outerSize(); ++i) 699c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath s << m.m_outerIndex[i] << " "; 700c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath s << " $" << std::endl; 701c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if(!m.isCompressed()) 702c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 703c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath s << "Inner non zeros:\n"; 704c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath for (Index i=0; i<m.outerSize(); ++i) 705c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath s << m.m_innerNonZeros[i] << " "; 706c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath s << " $" << std::endl; 707c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 708c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath s << std::endl; 709c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath ); 710c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath s << static_cast<const SparseMatrixBase<SparseMatrix>&>(m); 711c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath return s; 712c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 713c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 714c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** Destructor */ 715c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline ~SparseMatrix() 716c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 717c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath delete[] m_outerIndex; 718c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath delete[] m_innerNonZeros; 719c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 720c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 721c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath#ifndef EIGEN_PARSED_BY_DOXYGEN 722c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** Overloaded for performance */ 723c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Scalar sum() const; 724c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath#endif 725c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 726c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath# ifdef EIGEN_SPARSEMATRIX_PLUGIN 727c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath# include EIGEN_SPARSEMATRIX_PLUGIN 728c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath# endif 729c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 730c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamathprotected: 731c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 732c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath template<typename Other> 733c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath void initAssignment(const Other& other) 734c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 735c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath resize(other.rows(), other.cols()); 736c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if(m_innerNonZeros) 737c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 738c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath delete[] m_innerNonZeros; 739c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_innerNonZeros = 0; 740c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 741c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 742c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 743c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \internal 744c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \sa insert(Index,Index) */ 745c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath EIGEN_DONT_INLINE Scalar& insertCompressed(Index row, Index col) 746c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 747c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath eigen_assert(isCompressed()); 748c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 749c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath const Index outer = IsRowMajor ? row : col; 750c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath const Index inner = IsRowMajor ? col : row; 751c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 752c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index previousOuter = outer; 753c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if (m_outerIndex[outer+1]==0) 754c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 755c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // we start a new inner vector 756c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath while (previousOuter>=0 && m_outerIndex[previousOuter]==0) 757c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 758c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_outerIndex[previousOuter] = static_cast<Index>(m_data.size()); 759c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath --previousOuter; 760c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 761c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_outerIndex[outer+1] = m_outerIndex[outer]; 762c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 763c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 764c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // here we have to handle the tricky case where the outerIndex array 765c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // starts with: [ 0 0 0 0 0 1 ...] and we are inserted in, e.g., 766c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // the 2nd inner vector... 767c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath bool isLastVec = (!(previousOuter==-1 && m_data.size()!=0)) 768c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath && (size_t(m_outerIndex[outer+1]) == m_data.size()); 769c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 770c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath size_t startId = m_outerIndex[outer]; 771c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // FIXME let's make sure sizeof(long int) == sizeof(size_t) 772c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath size_t p = m_outerIndex[outer+1]; 773c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath ++m_outerIndex[outer+1]; 774c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 775c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath float reallocRatio = 1; 776c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if (m_data.allocatedSize()<=m_data.size()) 777c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 778c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // if there is no preallocated memory, let's reserve a minimum of 32 elements 779c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if (m_data.size()==0) 780c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 781c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.reserve(32); 782c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 783c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath else 784c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 785c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // we need to reallocate the data, to reduce multiple reallocations 786c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // we use a smart resize algorithm based on the current filling ratio 787c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // in addition, we use float to avoid integers overflows 788c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath float nnzEstimate = float(m_outerIndex[outer])*float(m_outerSize)/float(outer+1); 789c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath reallocRatio = (nnzEstimate-float(m_data.size()))/float(m_data.size()); 790c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // furthermore we bound the realloc ratio to: 791c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // 1) reduce multiple minor realloc when the matrix is almost filled 792c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // 2) avoid to allocate too much memory when the matrix is almost empty 793c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath reallocRatio = (std::min)((std::max)(reallocRatio,1.5f),8.f); 794c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 795c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 796c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.resize(m_data.size()+1,reallocRatio); 797c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 798c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if (!isLastVec) 799c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 800c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if (previousOuter==-1) 801c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 802c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // oops wrong guess. 803c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // let's correct the outer offsets 804c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath for (Index k=0; k<=(outer+1); ++k) 805c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_outerIndex[k] = 0; 806c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index k=outer+1; 807c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath while(m_outerIndex[k]==0) 808c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_outerIndex[k++] = 1; 809c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath while (k<=m_outerSize && m_outerIndex[k]!=0) 810c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_outerIndex[k++]++; 811c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath p = 0; 812c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath --k; 813c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath k = m_outerIndex[k]-1; 814c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath while (k>0) 815c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 816c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.index(k) = m_data.index(k-1); 817c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.value(k) = m_data.value(k-1); 818c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath k--; 819c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 820c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 821c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath else 822c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 823c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // we are not inserting into the last inner vec 824c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // update outer indices: 825c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index j = outer+2; 826c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath while (j<=m_outerSize && m_outerIndex[j]!=0) 827c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_outerIndex[j++]++; 828c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath --j; 829c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // shift data of last vecs: 830c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index k = m_outerIndex[j]-1; 831c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath while (k>=Index(p)) 832c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 833c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.index(k) = m_data.index(k-1); 834c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.value(k) = m_data.value(k-1); 835c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath k--; 836c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 837c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 838c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 839c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 840c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath while ( (p > startId) && (m_data.index(p-1) > inner) ) 841c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 842c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.index(p) = m_data.index(p-1); 843c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.value(p) = m_data.value(p-1); 844c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath --p; 845c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 846c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 847c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.index(p) = inner; 848c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath return (m_data.value(p) = 0); 849c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 850c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 851c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \internal 852c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * A vector object that is equal to 0 everywhere but v at the position i */ 853c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath class SingletonVector 854c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 855c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index m_index; 856c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index m_value; 857c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath public: 858c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath typedef Index value_type; 859c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath SingletonVector(Index i, Index v) 860c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath : m_index(i), m_value(v) 861c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath {} 862c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 863c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index operator[](Index i) const { return i==m_index ? m_value : 0; } 864c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath }; 865c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 866c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \internal 867c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \sa insert(Index,Index) */ 868c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath EIGEN_DONT_INLINE Scalar& insertUncompressed(Index row, Index col) 869c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 870c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath eigen_assert(!isCompressed()); 871c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 872c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath const Index outer = IsRowMajor ? row : col; 873c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath const Index inner = IsRowMajor ? col : row; 874c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 875c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath std::ptrdiff_t room = m_outerIndex[outer+1] - m_outerIndex[outer]; 876c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath std::ptrdiff_t innerNNZ = m_innerNonZeros[outer]; 877c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if(innerNNZ>=room) 878c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 879c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // this inner vector is full, we need to reallocate the whole buffer :( 880c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath reserve(SingletonVector(outer,std::max<std::ptrdiff_t>(2,innerNNZ))); 881c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 882c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 883c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index startId = m_outerIndex[outer]; 884c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index p = startId + m_innerNonZeros[outer]; 885c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath while ( (p > startId) && (m_data.index(p-1) > inner) ) 886c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 887c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.index(p) = m_data.index(p-1); 888c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.value(p) = m_data.value(p-1); 889c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath --p; 890c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 891c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 892c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_innerNonZeros[outer]++; 893c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 894c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.index(p) = inner; 895c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath return (m_data.value(p) = 0); 896c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 897c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 898c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamathpublic: 899c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath /** \internal 900c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \sa insert(Index,Index) */ 901c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline Scalar& insertBackUncompressed(Index row, Index col) 902c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 903c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath const Index outer = IsRowMajor ? row : col; 904c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath const Index inner = IsRowMajor ? col : row; 905c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 906c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath eigen_assert(!isCompressed()); 907c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath eigen_assert(m_innerNonZeros[outer]<=(m_outerIndex[outer+1] - m_outerIndex[outer])); 908c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 909c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index p = m_outerIndex[outer] + m_innerNonZeros[outer]; 910c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_innerNonZeros[outer]++; 911c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.index(p) = inner; 912c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath return (m_data.value(p) = 0); 913c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 914c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 915c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamathprivate: 916c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath static void check_template_parameters() 917c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 918c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath EIGEN_STATIC_ASSERT(NumTraits<Index>::IsSigned,THE_INDEX_TYPE_MUST_BE_A_SIGNED_TYPE); 919c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 920c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 921c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath struct default_prunning_func { 922c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath default_prunning_func(Scalar ref, RealScalar eps) : reference(ref), epsilon(eps) {} 923c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline bool operator() (const Index&, const Index&, const Scalar& value) const 924c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 925c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath return !internal::isMuchSmallerThan(value, reference, epsilon); 926c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 927c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Scalar reference; 928c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath RealScalar epsilon; 929c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath }; 930c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath}; 931c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 932c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamathtemplate<typename Scalar, int _Options, typename _Index> 933c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamathclass SparseMatrix<Scalar,_Options,_Index>::InnerIterator 934c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath{ 935c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath public: 936c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath InnerIterator(const SparseMatrix& mat, Index outer) 937c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath : m_values(mat.valuePtr()), m_indices(mat.innerIndexPtr()), m_outer(outer), m_id(mat.m_outerIndex[outer]) 938c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 939c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if(mat.isCompressed()) 940c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_end = mat.m_outerIndex[outer+1]; 941c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath else 942c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_end = m_id + mat.m_innerNonZeros[outer]; 943c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 944c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 945c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline InnerIterator& operator++() { m_id++; return *this; } 946c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 947c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline const Scalar& value() const { return m_values[m_id]; } 948c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline Scalar& valueRef() { return const_cast<Scalar&>(m_values[m_id]); } 949c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 950c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline Index index() const { return m_indices[m_id]; } 951c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline Index outer() const { return m_outer; } 952c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline Index row() const { return IsRowMajor ? m_outer : index(); } 953c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline Index col() const { return IsRowMajor ? index() : m_outer; } 954c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 955c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline operator bool() const { return (m_id < m_end); } 956c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 957c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath protected: 958c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath const Scalar* m_values; 959c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath const Index* m_indices; 960c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath const Index m_outer; 961c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index m_id; 962c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index m_end; 963c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath}; 964c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 965c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamathtemplate<typename Scalar, int _Options, typename _Index> 966c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamathclass SparseMatrix<Scalar,_Options,_Index>::ReverseInnerIterator 967c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath{ 968c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath public: 969c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath ReverseInnerIterator(const SparseMatrix& mat, Index outer) 970c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath : m_values(mat.valuePtr()), m_indices(mat.innerIndexPtr()), m_outer(outer), m_start(mat.m_outerIndex[outer]) 971c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 972c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if(mat.isCompressed()) 973c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_id = mat.m_outerIndex[outer+1]; 974c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath else 975c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_id = m_start + mat.m_innerNonZeros[outer]; 976c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 977c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 978c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline ReverseInnerIterator& operator--() { --m_id; return *this; } 979c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 980c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline const Scalar& value() const { return m_values[m_id-1]; } 981c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline Scalar& valueRef() { return const_cast<Scalar&>(m_values[m_id-1]); } 982c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 983c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline Index index() const { return m_indices[m_id-1]; } 984c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline Index outer() const { return m_outer; } 985c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline Index row() const { return IsRowMajor ? m_outer : index(); } 986c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline Index col() const { return IsRowMajor ? index() : m_outer; } 987c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 988c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath inline operator bool() const { return (m_id > m_start); } 989c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 990c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath protected: 991c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath const Scalar* m_values; 992c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath const Index* m_indices; 993c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath const Index m_outer; 994c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index m_id; 995c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath const Index m_start; 996c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath}; 997c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 998c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamathnamespace internal { 999c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 1000c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamathtemplate<typename InputIterator, typename SparseMatrixType> 1001c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamathvoid set_from_triplets(const InputIterator& begin, const InputIterator& end, SparseMatrixType& mat, int Options = 0) 1002c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath{ 1003c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath EIGEN_UNUSED_VARIABLE(Options); 1004c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath enum { IsRowMajor = SparseMatrixType::IsRowMajor }; 1005c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath typedef typename SparseMatrixType::Scalar Scalar; 1006c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath typedef typename SparseMatrixType::Index Index; 1007c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath SparseMatrix<Scalar,IsRowMajor?ColMajor:RowMajor> trMat(mat.rows(),mat.cols()); 1008c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 1009c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // pass 1: count the nnz per inner-vector 1010c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath VectorXi wi(trMat.outerSize()); 1011c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath wi.setZero(); 1012c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath for(InputIterator it(begin); it!=end; ++it) 1013c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath wi(IsRowMajor ? it->col() : it->row())++; 1014c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 1015c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // pass 2: insert all the elements into trMat 1016c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath trMat.reserve(wi); 1017c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath for(InputIterator it(begin); it!=end; ++it) 1018c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath trMat.insertBackUncompressed(it->row(),it->col()) = it->value(); 1019c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 1020c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // pass 3: 1021c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath trMat.sumupDuplicates(); 1022c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 1023c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // pass 4: transposed copy -> implicit sorting 1024c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath mat = trMat; 1025c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath} 1026c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 1027c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath} 1028c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 1029c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 1030c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath/** Fill the matrix \c *this with the list of \em triplets defined by the iterator range \a begin - \b. 1031c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * 1032c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * A \em triplet is a tuple (i,j,value) defining a non-zero element. 1033c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * The input list of triplets does not have to be sorted, and can contains duplicated elements. 1034c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * In any case, the result is a \b sorted and \b compressed sparse matrix where the duplicates have been summed up. 1035c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * This is a \em O(n) operation, with \em n the number of triplet elements. 1036c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * The initial contents of \c *this is destroyed. 1037c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * The matrix \c *this must be properly resized beforehand using the SparseMatrix(Index,Index) constructor, 1038c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * or the resize(Index,Index) method. The sizes are not extracted from the triplet list. 1039c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * 1040c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * The \a InputIterators value_type must provide the following interface: 1041c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \code 1042c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * Scalar value() const; // the value 1043c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * Scalar row() const; // the row index i 1044c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * Scalar col() const; // the column index j 1045c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \endcode 1046c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * See for instance the Eigen::Triplet template class. 1047c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * 1048c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * Here is a typical usage example: 1049c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \code 1050c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath typedef Triplet<double> T; 1051c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath std::vector<T> tripletList; 1052c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath triplets.reserve(estimation_of_entries); 1053c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath for(...) 1054c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 1055c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // ... 1056c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath tripletList.push_back(T(i,j,v_ij)); 1057c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 1058c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath SparseMatrixType m(rows,cols); 1059c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m.setFromTriplets(tripletList.begin(), tripletList.end()); 1060c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // m is ready to go! 1061c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \endcode 1062c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * 1063c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * \warning The list of triplets is read multiple times (at least twice). Therefore, it is not recommended to define 1064c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * an abstract iterator over a complex data-structure that would be expensive to evaluate. The triplets should rather 1065c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath * be explicitely stored into a std::vector for instance. 1066c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath */ 1067c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamathtemplate<typename Scalar, int _Options, typename _Index> 1068c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamathtemplate<typename InputIterators> 1069c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamathvoid SparseMatrix<Scalar,_Options,_Index>::setFromTriplets(const InputIterators& begin, const InputIterators& end) 1070c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath{ 1071c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath internal::set_from_triplets(begin, end, *this); 1072c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath} 1073c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 1074c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath/** \internal */ 1075c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamathtemplate<typename Scalar, int _Options, typename _Index> 1076c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamathvoid SparseMatrix<Scalar,_Options,_Index>::sumupDuplicates() 1077c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath{ 1078c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath eigen_assert(!isCompressed()); 1079c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // TODO, in practice we should be able to use m_innerNonZeros for that task 1080c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath VectorXi wi(innerSize()); 1081c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath wi.fill(-1); 1082c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index count = 0; 1083c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // for each inner-vector, wi[inner_index] will hold the position of first element into the index/value buffers 1084c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath for(int j=0; j<outerSize(); ++j) 1085c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 1086c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index start = count; 1087c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index oldEnd = m_outerIndex[j]+m_innerNonZeros[j]; 1088c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath for(Index k=m_outerIndex[j]; k<oldEnd; ++k) 1089c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 1090c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath Index i = m_data.index(k); 1091c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath if(wi(i)>=start) 1092c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 1093c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // we already meet this entry => accumulate it 1094c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.value(wi(i)) += m_data.value(k); 1095c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 1096c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath else 1097c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath { 1098c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.value(count) = m_data.value(k); 1099c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.index(count) = m_data.index(k); 1100c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath wi(i) = count; 1101c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath ++count; 1102c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 1103c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 1104c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_outerIndex[j] = start; 1105c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath } 1106c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_outerIndex[m_outerSize] = count; 1107c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 1108c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath // turn the matrix into compressed form 1109c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath delete[] m_innerNonZeros; 1110c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_innerNonZeros = 0; 1111c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath m_data.resize(m_outerIndex[m_outerSize]); 1112c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath} 1113c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 1114c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath} // end namespace Eigen 1115c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath 1116c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath#endif // EIGEN_SPARSEMATRIX_H 1117