1 // This file is part of Eigen, a lightweight C++ template library 2 // for linear algebra. 3 // 4 // Copyright (C) 2008-2009 Gael Guennebaud <gael.guennebaud (at) inria.fr> 5 // 6 // This Source Code Form is subject to the terms of the Mozilla 7 // Public License v. 2.0. If a copy of the MPL was not distributed 8 // with this file, You can obtain one at http://mozilla.org/MPL/2.0/. 9 10 #ifndef EIGEN_SPARSEVECTOR_H 11 #define EIGEN_SPARSEVECTOR_H 12 13 namespace Eigen { 14 15 /** \ingroup SparseCore_Module 16 * \class SparseVector 17 * 18 * \brief a sparse vector class 19 * 20 * \tparam _Scalar the scalar type, i.e. the type of the coefficients 21 * 22 * See http://www.netlib.org/linalg/html_templates/node91.html for details on the storage scheme. 23 * 24 * This class can be extended with the help of the plugin mechanism described on the page 25 * \ref TopicCustomizingEigen by defining the preprocessor symbol \c EIGEN_SPARSEVECTOR_PLUGIN. 26 */ 27 28 namespace internal { 29 template<typename _Scalar, int _Options, typename _Index> 30 struct traits<SparseVector<_Scalar, _Options, _Index> > 31 { 32 typedef _Scalar Scalar; 33 typedef _Index Index; 34 typedef Sparse StorageKind; 35 typedef MatrixXpr XprKind; 36 enum { 37 IsColVector = (_Options & RowMajorBit) ? 0 : 1, 38 39 RowsAtCompileTime = IsColVector ? Dynamic : 1, 40 ColsAtCompileTime = IsColVector ? 1 : Dynamic, 41 MaxRowsAtCompileTime = RowsAtCompileTime, 42 MaxColsAtCompileTime = ColsAtCompileTime, 43 Flags = _Options | NestByRefBit | LvalueBit | (IsColVector ? 0 : RowMajorBit), 44 CoeffReadCost = NumTraits<Scalar>::ReadCost, 45 SupportedAccessPatterns = InnerRandomAccessPattern 46 }; 47 }; 48 } 49 50 template<typename _Scalar, int _Options, typename _Index> 51 class SparseVector 52 : public SparseMatrixBase<SparseVector<_Scalar, _Options, _Index> > 53 { 54 public: 55 EIGEN_SPARSE_PUBLIC_INTERFACE(SparseVector) 56 EIGEN_SPARSE_INHERIT_ASSIGNMENT_OPERATOR(SparseVector, +=) 57 EIGEN_SPARSE_INHERIT_ASSIGNMENT_OPERATOR(SparseVector, -=) 58 59 protected: 60 public: 61 62 typedef SparseMatrixBase<SparseVector> SparseBase; 63 enum { IsColVector = internal::traits<SparseVector>::IsColVector }; 64 65 enum { 66 Options = _Options 67 }; 68 69 internal::CompressedStorage<Scalar,Index> m_data; 70 Index m_size; 71 72 internal::CompressedStorage<Scalar,Index>& _data() { return m_data; } 73 internal::CompressedStorage<Scalar,Index>& _data() const { return m_data; } 74 75 public: 76 77 EIGEN_STRONG_INLINE Index rows() const { return IsColVector ? m_size : 1; } 78 EIGEN_STRONG_INLINE Index cols() const { return IsColVector ? 1 : m_size; } 79 EIGEN_STRONG_INLINE Index innerSize() const { return m_size; } 80 EIGEN_STRONG_INLINE Index outerSize() const { return 1; } 81 82 EIGEN_STRONG_INLINE const Scalar* valuePtr() const { return &m_data.value(0); } 83 EIGEN_STRONG_INLINE Scalar* valuePtr() { return &m_data.value(0); } 84 85 EIGEN_STRONG_INLINE const Index* innerIndexPtr() const { return &m_data.index(0); } 86 EIGEN_STRONG_INLINE Index* innerIndexPtr() { return &m_data.index(0); } 87 88 inline Scalar coeff(Index row, Index col) const 89 { 90 eigen_assert((IsColVector ? col : row)==0); 91 return coeff(IsColVector ? row : col); 92 } 93 inline Scalar coeff(Index i) const { return m_data.at(i); } 94 95 inline Scalar& coeffRef(Index row, Index col) 96 { 97 eigen_assert((IsColVector ? col : row)==0); 98 return coeff(IsColVector ? row : col); 99 } 100 101 /** \returns a reference to the coefficient value at given index \a i 102 * This operation involes a log(rho*size) binary search. If the coefficient does not 103 * exist yet, then a sorted insertion into a sequential buffer is performed. 104 * 105 * This insertion might be very costly if the number of nonzeros above \a i is large. 106 */ 107 inline Scalar& coeffRef(Index i) 108 { 109 return m_data.atWithInsertion(i); 110 } 111 112 public: 113 114 class InnerIterator; 115 class ReverseInnerIterator; 116 117 inline void setZero() { m_data.clear(); } 118 119 /** \returns the number of non zero coefficients */ 120 inline Index nonZeros() const { return static_cast<Index>(m_data.size()); } 121 122 inline void startVec(Index outer) 123 { 124 EIGEN_UNUSED_VARIABLE(outer); 125 eigen_assert(outer==0); 126 } 127 128 inline Scalar& insertBackByOuterInner(Index outer, Index inner) 129 { 130 EIGEN_UNUSED_VARIABLE(outer); 131 eigen_assert(outer==0); 132 return insertBack(inner); 133 } 134 inline Scalar& insertBack(Index i) 135 { 136 m_data.append(0, i); 137 return m_data.value(m_data.size()-1); 138 } 139 140 inline Scalar& insert(Index row, Index col) 141 { 142 Index inner = IsColVector ? row : col; 143 Index outer = IsColVector ? col : row; 144 eigen_assert(outer==0); 145 return insert(inner); 146 } 147 Scalar& insert(Index i) 148 { 149 Index startId = 0; 150 Index p = Index(m_data.size()) - 1; 151 // TODO smart realloc 152 m_data.resize(p+2,1); 153 154 while ( (p >= startId) && (m_data.index(p) > i) ) 155 { 156 m_data.index(p+1) = m_data.index(p); 157 m_data.value(p+1) = m_data.value(p); 158 --p; 159 } 160 m_data.index(p+1) = i; 161 m_data.value(p+1) = 0; 162 return m_data.value(p+1); 163 } 164 165 /** 166 */ 167 inline void reserve(Index reserveSize) { m_data.reserve(reserveSize); } 168 169 170 inline void finalize() {} 171 172 void prune(Scalar reference, RealScalar epsilon = NumTraits<RealScalar>::dummy_precision()) 173 { 174 m_data.prune(reference,epsilon); 175 } 176 177 void resize(Index rows, Index cols) 178 { 179 eigen_assert(rows==1 || cols==1); 180 resize(IsColVector ? rows : cols); 181 } 182 183 void resize(Index newSize) 184 { 185 m_size = newSize; 186 m_data.clear(); 187 } 188 189 void resizeNonZeros(Index size) { m_data.resize(size); } 190 191 inline SparseVector() : m_size(0) { resize(0); } 192 193 inline SparseVector(Index size) : m_size(0) { resize(size); } 194 195 inline SparseVector(Index rows, Index cols) : m_size(0) { resize(rows,cols); } 196 197 template<typename OtherDerived> 198 inline SparseVector(const SparseMatrixBase<OtherDerived>& other) 199 : m_size(0) 200 { 201 *this = other.derived(); 202 } 203 204 inline SparseVector(const SparseVector& other) 205 : m_size(0) 206 { 207 *this = other.derived(); 208 } 209 210 inline void swap(SparseVector& other) 211 { 212 std::swap(m_size, other.m_size); 213 m_data.swap(other.m_data); 214 } 215 216 inline SparseVector& operator=(const SparseVector& other) 217 { 218 if (other.isRValue()) 219 { 220 swap(other.const_cast_derived()); 221 } 222 else 223 { 224 resize(other.size()); 225 m_data = other.m_data; 226 } 227 return *this; 228 } 229 230 template<typename OtherDerived> 231 inline SparseVector& operator=(const SparseMatrixBase<OtherDerived>& other) 232 { 233 if (int(RowsAtCompileTime)!=int(OtherDerived::RowsAtCompileTime)) 234 return assign(other.transpose()); 235 else 236 return assign(other); 237 } 238 239 #ifndef EIGEN_PARSED_BY_DOXYGEN 240 template<typename Lhs, typename Rhs> 241 inline SparseVector& operator=(const SparseSparseProduct<Lhs,Rhs>& product) 242 { 243 return Base::operator=(product); 244 } 245 #endif 246 247 friend std::ostream & operator << (std::ostream & s, const SparseVector& m) 248 { 249 for (Index i=0; i<m.nonZeros(); ++i) 250 s << "(" << m.m_data.value(i) << "," << m.m_data.index(i) << ") "; 251 s << std::endl; 252 return s; 253 } 254 255 /** Destructor */ 256 inline ~SparseVector() {} 257 258 /** Overloaded for performance */ 259 Scalar sum() const; 260 261 public: 262 263 /** \deprecated use setZero() and reserve() */ 264 EIGEN_DEPRECATED void startFill(Index reserve) 265 { 266 setZero(); 267 m_data.reserve(reserve); 268 } 269 270 /** \deprecated use insertBack(Index,Index) */ 271 EIGEN_DEPRECATED Scalar& fill(Index r, Index c) 272 { 273 eigen_assert(r==0 || c==0); 274 return fill(IsColVector ? r : c); 275 } 276 277 /** \deprecated use insertBack(Index) */ 278 EIGEN_DEPRECATED Scalar& fill(Index i) 279 { 280 m_data.append(0, i); 281 return m_data.value(m_data.size()-1); 282 } 283 284 /** \deprecated use insert(Index,Index) */ 285 EIGEN_DEPRECATED Scalar& fillrand(Index r, Index c) 286 { 287 eigen_assert(r==0 || c==0); 288 return fillrand(IsColVector ? r : c); 289 } 290 291 /** \deprecated use insert(Index) */ 292 EIGEN_DEPRECATED Scalar& fillrand(Index i) 293 { 294 return insert(i); 295 } 296 297 /** \deprecated use finalize() */ 298 EIGEN_DEPRECATED void endFill() {} 299 300 # ifdef EIGEN_SPARSEVECTOR_PLUGIN 301 # include EIGEN_SPARSEVECTOR_PLUGIN 302 # endif 303 304 protected: 305 template<typename OtherDerived> 306 EIGEN_DONT_INLINE SparseVector& assign(const SparseMatrixBase<OtherDerived>& _other) 307 { 308 const OtherDerived& other(_other.derived()); 309 const bool needToTranspose = (Flags & RowMajorBit) != (OtherDerived::Flags & RowMajorBit); 310 if(needToTranspose) 311 { 312 Index size = other.size(); 313 Index nnz = other.nonZeros(); 314 resize(size); 315 reserve(nnz); 316 for(Index i=0; i<size; ++i) 317 { 318 typename OtherDerived::InnerIterator it(other, i); 319 if(it) 320 insert(i) = it.value(); 321 } 322 return *this; 323 } 324 else 325 { 326 // there is no special optimization 327 return Base::operator=(other); 328 } 329 } 330 }; 331 332 template<typename Scalar, int _Options, typename _Index> 333 class SparseVector<Scalar,_Options,_Index>::InnerIterator 334 { 335 public: 336 InnerIterator(const SparseVector& vec, Index outer=0) 337 : m_data(vec.m_data), m_id(0), m_end(static_cast<Index>(m_data.size())) 338 { 339 EIGEN_UNUSED_VARIABLE(outer); 340 eigen_assert(outer==0); 341 } 342 343 InnerIterator(const internal::CompressedStorage<Scalar,Index>& data) 344 : m_data(data), m_id(0), m_end(static_cast<Index>(m_data.size())) 345 {} 346 347 inline InnerIterator& operator++() { m_id++; return *this; } 348 349 inline Scalar value() const { return m_data.value(m_id); } 350 inline Scalar& valueRef() { return const_cast<Scalar&>(m_data.value(m_id)); } 351 352 inline Index index() const { return m_data.index(m_id); } 353 inline Index row() const { return IsColVector ? index() : 0; } 354 inline Index col() const { return IsColVector ? 0 : index(); } 355 356 inline operator bool() const { return (m_id < m_end); } 357 358 protected: 359 const internal::CompressedStorage<Scalar,Index>& m_data; 360 Index m_id; 361 const Index m_end; 362 }; 363 364 template<typename Scalar, int _Options, typename _Index> 365 class SparseVector<Scalar,_Options,_Index>::ReverseInnerIterator 366 { 367 public: 368 ReverseInnerIterator(const SparseVector& vec, Index outer=0) 369 : m_data(vec.m_data), m_id(static_cast<Index>(m_data.size())), m_start(0) 370 { 371 EIGEN_UNUSED_VARIABLE(outer); 372 eigen_assert(outer==0); 373 } 374 375 ReverseInnerIterator(const internal::CompressedStorage<Scalar,Index>& data) 376 : m_data(data), m_id(static_cast<Index>(m_data.size())), m_start(0) 377 {} 378 379 inline ReverseInnerIterator& operator--() { m_id--; return *this; } 380 381 inline Scalar value() const { return m_data.value(m_id-1); } 382 inline Scalar& valueRef() { return const_cast<Scalar&>(m_data.value(m_id-1)); } 383 384 inline Index index() const { return m_data.index(m_id-1); } 385 inline Index row() const { return IsColVector ? index() : 0; } 386 inline Index col() const { return IsColVector ? 0 : index(); } 387 388 inline operator bool() const { return (m_id > m_start); } 389 390 protected: 391 const internal::CompressedStorage<Scalar,Index>& m_data; 392 Index m_id; 393 const Index m_start; 394 }; 395 396 } // end namespace Eigen 397 398 #endif // EIGEN_SPARSEVECTOR_H 399
