Another set of UI messages fixes and tweaks! No functional changes.
[blender.git] / extern / Eigen3 / Eigen / src / Sparse / DynamicSparseMatrix.h
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@inria.fr>
5 //
6 // Eigen is free software; you can redistribute it and/or
7 // modify it under the terms of the GNU Lesser General Public
8 // License as published by the Free Software Foundation; either
9 // version 3 of the License, or (at your option) any later version.
10 //
11 // Alternatively, you can redistribute it and/or
12 // modify it under the terms of the GNU General Public License as
13 // published by the Free Software Foundation; either version 2 of
14 // the License, or (at your option) any later version.
15 //
16 // Eigen is distributed in the hope that it will be useful, but WITHOUT ANY
17 // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
18 // FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License or the
19 // GNU General Public License for more details.
20 //
21 // You should have received a copy of the GNU Lesser General Public
22 // License and a copy of the GNU General Public License along with
23 // Eigen. If not, see <http://www.gnu.org/licenses/>.
24
25 #ifndef EIGEN_DYNAMIC_SPARSEMATRIX_H
26 #define EIGEN_DYNAMIC_SPARSEMATRIX_H
27
28 /** \class DynamicSparseMatrix
29   *
30   * \brief A sparse matrix class designed for matrix assembly purpose
31   *
32   * \param _Scalar the scalar type, i.e. the type of the coefficients
33   *
34   * Unlike SparseMatrix, this class provides a much higher degree of flexibility. In particular, it allows
35   * random read/write accesses in log(rho*outer_size) where \c rho is the probability that a coefficient is
36   * nonzero and outer_size is the number of columns if the matrix is column-major and the number of rows
37   * otherwise.
38   *
39   * Internally, the data are stored as a std::vector of compressed vector. The performances of random writes might
40   * decrease as the number of nonzeros per inner-vector increase. In practice, we observed very good performance
41   * till about 100 nonzeros/vector, and the performance remains relatively good till 500 nonzeros/vectors.
42   *
43   * \see SparseMatrix
44   */
45
46 namespace internal {
47 template<typename _Scalar, int _Options, typename _Index>
48 struct traits<DynamicSparseMatrix<_Scalar, _Options, _Index> >
49 {
50   typedef _Scalar Scalar;
51   typedef _Index Index;
52   typedef Sparse StorageKind;
53   typedef MatrixXpr XprKind;
54   enum {
55     RowsAtCompileTime = Dynamic,
56     ColsAtCompileTime = Dynamic,
57     MaxRowsAtCompileTime = Dynamic,
58     MaxColsAtCompileTime = Dynamic,
59     Flags = _Options | NestByRefBit | LvalueBit,
60     CoeffReadCost = NumTraits<Scalar>::ReadCost,
61     SupportedAccessPatterns = OuterRandomAccessPattern
62   };
63 };
64 }
65
66 template<typename _Scalar, int _Options, typename _Index>
67 class DynamicSparseMatrix
68   : public SparseMatrixBase<DynamicSparseMatrix<_Scalar, _Options, _Index> >
69 {
70   public:
71     EIGEN_SPARSE_PUBLIC_INTERFACE(DynamicSparseMatrix)
72     // FIXME: why are these operator already alvailable ???
73     // EIGEN_SPARSE_INHERIT_ASSIGNMENT_OPERATOR(DynamicSparseMatrix, +=)
74     // EIGEN_SPARSE_INHERIT_ASSIGNMENT_OPERATOR(DynamicSparseMatrix, -=)
75     typedef MappedSparseMatrix<Scalar,Flags> Map;
76     using Base::IsRowMajor;
77     using Base::operator=;
78     enum {
79       Options = _Options
80     };
81
82   protected:
83
84     typedef DynamicSparseMatrix<Scalar,(Flags&~RowMajorBit)|(IsRowMajor?RowMajorBit:0)> TransposedSparseMatrix;
85
86     Index m_innerSize;
87     std::vector<CompressedStorage<Scalar,Index> > m_data;
88
89   public:
90
91     inline Index rows() const { return IsRowMajor ? outerSize() : m_innerSize; }
92     inline Index cols() const { return IsRowMajor ? m_innerSize : outerSize(); }
93     inline Index innerSize() const { return m_innerSize; }
94     inline Index outerSize() const { return static_cast<Index>(m_data.size()); }
95     inline Index innerNonZeros(Index j) const { return m_data[j].size(); }
96
97     std::vector<CompressedStorage<Scalar,Index> >& _data() { return m_data; }
98     const std::vector<CompressedStorage<Scalar,Index> >& _data() const { return m_data; }
99
100     /** \returns the coefficient value at given position \a row, \a col
101       * This operation involes a log(rho*outer_size) binary search.
102       */
103     inline Scalar coeff(Index row, Index col) const
104     {
105       const Index outer = IsRowMajor ? row : col;
106       const Index inner = IsRowMajor ? col : row;
107       return m_data[outer].at(inner);
108     }
109
110     /** \returns a reference to the coefficient value at given position \a row, \a col
111       * This operation involes a log(rho*outer_size) binary search. If the coefficient does not
112       * exist yet, then a sorted insertion into a sequential buffer is performed.
113       */
114     inline Scalar& coeffRef(Index row, Index col)
115     {
116       const Index outer = IsRowMajor ? row : col;
117       const Index inner = IsRowMajor ? col : row;
118       return m_data[outer].atWithInsertion(inner);
119     }
120
121     class InnerIterator;
122
123     void setZero()
124     {
125       for (Index j=0; j<outerSize(); ++j)
126         m_data[j].clear();
127     }
128
129     /** \returns the number of non zero coefficients */
130     Index nonZeros() const
131     {
132       Index res = 0;
133       for (Index j=0; j<outerSize(); ++j)
134         res += static_cast<Index>(m_data[j].size());
135       return res;
136     }
137
138
139
140     void reserve(Index reserveSize = 1000)
141     {
142       if (outerSize()>0)
143       {
144         Index reserveSizePerVector = (std::max)(reserveSize/outerSize(),Index(4));
145         for (Index j=0; j<outerSize(); ++j)
146         {
147           m_data[j].reserve(reserveSizePerVector);
148         }
149       }
150     }
151
152     /** Does nothing: provided for compatibility with SparseMatrix */
153     inline void startVec(Index /*outer*/) {}
154
155     /** \returns a reference to the non zero coefficient at position \a row, \a col assuming that:
156       * - the nonzero does not already exist
157       * - the new coefficient is the last one of the given inner vector.
158       *
159       * \sa insert, insertBackByOuterInner */
160     inline Scalar& insertBack(Index row, Index col)
161     {
162       return insertBackByOuterInner(IsRowMajor?row:col, IsRowMajor?col:row);
163     }
164
165     /** \sa insertBack */
166     inline Scalar& insertBackByOuterInner(Index outer, Index inner)
167     {
168       eigen_assert(outer<Index(m_data.size()) && inner<m_innerSize && "out of range");
169       eigen_assert(((m_data[outer].size()==0) || (m_data[outer].index(m_data[outer].size()-1)<inner))
170                 && "wrong sorted insertion");
171       m_data[outer].append(0, inner);
172       return m_data[outer].value(m_data[outer].size()-1);
173     }
174
175     inline Scalar& insert(Index row, Index col)
176     {
177       const Index outer = IsRowMajor ? row : col;
178       const Index inner = IsRowMajor ? col : row;
179
180       Index startId = 0;
181       Index id = static_cast<Index>(m_data[outer].size()) - 1;
182       m_data[outer].resize(id+2,1);
183
184       while ( (id >= startId) && (m_data[outer].index(id) > inner) )
185       {
186         m_data[outer].index(id+1) = m_data[outer].index(id);
187         m_data[outer].value(id+1) = m_data[outer].value(id);
188         --id;
189       }
190       m_data[outer].index(id+1) = inner;
191       m_data[outer].value(id+1) = 0;
192       return m_data[outer].value(id+1);
193     }
194
195     /** Does nothing: provided for compatibility with SparseMatrix */
196     inline void finalize() {}
197
198     /** Suppress all nonzeros which are smaller than \a reference under the tolerence \a epsilon */
199     void prune(Scalar reference, RealScalar epsilon = NumTraits<RealScalar>::dummy_precision())
200     {
201       for (Index j=0; j<outerSize(); ++j)
202         m_data[j].prune(reference,epsilon);
203     }
204
205     /** Resize the matrix without preserving the data (the matrix is set to zero)
206       */
207     void resize(Index rows, Index cols)
208     {
209       const Index outerSize = IsRowMajor ? rows : cols;
210       m_innerSize = IsRowMajor ? cols : rows;
211       setZero();
212       if (Index(m_data.size()) != outerSize)
213       {
214         m_data.resize(outerSize);
215       }
216     }
217
218     void resizeAndKeepData(Index rows, Index cols)
219     {
220       const Index outerSize = IsRowMajor ? rows : cols;
221       const Index innerSize = IsRowMajor ? cols : rows;
222       if (m_innerSize>innerSize)
223       {
224         // remove all coefficients with innerCoord>=innerSize
225         // TODO
226         //std::cerr << "not implemented yet\n";
227         exit(2);
228       }
229       if (m_data.size() != outerSize)
230       {
231         m_data.resize(outerSize);
232       }
233     }
234
235     inline DynamicSparseMatrix()
236       : m_innerSize(0), m_data(0)
237     {
238       eigen_assert(innerSize()==0 && outerSize()==0);
239     }
240
241     inline DynamicSparseMatrix(Index rows, Index cols)
242       : m_innerSize(0)
243     {
244       resize(rows, cols);
245     }
246
247     template<typename OtherDerived>
248     explicit inline DynamicSparseMatrix(const SparseMatrixBase<OtherDerived>& other)
249       : m_innerSize(0)
250     {
251     Base::operator=(other.derived());
252     }
253
254     inline DynamicSparseMatrix(const DynamicSparseMatrix& other)
255       : Base(), m_innerSize(0)
256     {
257       *this = other.derived();
258     }
259
260     inline void swap(DynamicSparseMatrix& other)
261     {
262       //EIGEN_DBG_SPARSE(std::cout << "SparseMatrix:: swap\n");
263       std::swap(m_innerSize, other.m_innerSize);
264       //std::swap(m_outerSize, other.m_outerSize);
265       m_data.swap(other.m_data);
266     }
267
268     inline DynamicSparseMatrix& operator=(const DynamicSparseMatrix& other)
269     {
270       if (other.isRValue())
271       {
272         swap(other.const_cast_derived());
273       }
274       else
275       {
276         resize(other.rows(), other.cols());
277         m_data = other.m_data;
278       }
279       return *this;
280     }
281
282     /** Destructor */
283     inline ~DynamicSparseMatrix() {}
284
285   public:
286
287     /** \deprecated
288       * Set the matrix to zero and reserve the memory for \a reserveSize nonzero coefficients. */
289     EIGEN_DEPRECATED void startFill(Index reserveSize = 1000)
290     {
291       setZero();
292       reserve(reserveSize);
293     }
294
295     /** \deprecated use insert()
296       * inserts a nonzero coefficient at given coordinates \a row, \a col and returns its reference assuming that:
297       *  1 - the coefficient does not exist yet
298       *  2 - this the coefficient with greater inner coordinate for the given outer coordinate.
299       * In other words, assuming \c *this is column-major, then there must not exists any nonzero coefficient of coordinates
300       * \c i \c x \a col such that \c i >= \a row. Otherwise the matrix is invalid.
301       *
302       * \see fillrand(), coeffRef()
303       */
304     EIGEN_DEPRECATED Scalar& fill(Index row, Index col)
305     {
306       const Index outer = IsRowMajor ? row : col;
307       const Index inner = IsRowMajor ? col : row;
308       return insertBack(outer,inner);
309     }
310
311     /** \deprecated use insert()
312       * Like fill() but with random inner coordinates.
313       * Compared to the generic coeffRef(), the unique limitation is that we assume
314       * the coefficient does not exist yet.
315       */
316     EIGEN_DEPRECATED Scalar& fillrand(Index row, Index col)
317     {
318       return insert(row,col);
319     }
320
321     /** \deprecated use finalize()
322       * Does nothing. Provided for compatibility with SparseMatrix. */
323     EIGEN_DEPRECATED void endFill() {}
324     
325 #   ifdef EIGEN_DYNAMICSPARSEMATRIX_PLUGIN
326 #     include EIGEN_DYNAMICSPARSEMATRIX_PLUGIN
327 #   endif
328 };
329
330 template<typename Scalar, int _Options, typename _Index>
331 class DynamicSparseMatrix<Scalar,_Options,_Index>::InnerIterator : public SparseVector<Scalar,_Options>::InnerIterator
332 {
333     typedef typename SparseVector<Scalar,_Options>::InnerIterator Base;
334   public:
335     InnerIterator(const DynamicSparseMatrix& mat, Index outer)
336       : Base(mat.m_data[outer]), m_outer(outer)
337     {}
338
339     inline Index row() const { return IsRowMajor ? m_outer : Base::index(); }
340     inline Index col() const { return IsRowMajor ? Base::index() : m_outer; }
341
342   protected:
343     const Index m_outer;
344 };
345
346 #endif // EIGEN_DYNAMIC_SPARSEMATRIX_H