MRPT  2.0.4
CSparseMatrixTemplate.h
Go to the documentation of this file.
1 /* +------------------------------------------------------------------------+
2  | Mobile Robot Programming Toolkit (MRPT) |
3  | https://www.mrpt.org/ |
4  | |
5  | Copyright (c) 2005-2020, Individual contributors, see AUTHORS file |
6  | See: https://www.mrpt.org/Authors - All rights reserved. |
7  | Released under BSD License. See: https://www.mrpt.org/License |
8  +------------------------------------------------------------------------+ */
9 #pragma once
10 
11 #include <map>
12 #include <vector>
13 
14 namespace mrpt::math
15 {
16 /** A sparse matrix container (with cells of any type), with iterators.
17  * This class stores only those elements created by assigning them a value,
18  * for example: "M(2,3)=8;".
19  *
20  * This class doesn't implement math operations since it's a generic sparse
21  * container, but it can be
22  * used to initialize the contents of a CSparse library-based matrix of type
23  * mrpt::math::CSparseMatrix.
24  *
25  * Note that reading non-existing cell elements will return the default value
26  * (0 for numbers)
27  * and that cell will remain non-created in the matrix.
28  *
29  * There is an additional method "exists(i,j)" to check whether a given
30  * element exists in the matrix.
31  *
32  * \sa mrpt::math::MatrixBlockSparseCols, mrpt::math::CSparseMatrix,
33  * CSparseSymmetricalMatrix
34  * \note Methods marked as "Doesn't check bounds" mean that if an access to an
35  * element out of the matrix size is tried, an empty element will be assumed,
36  * but this will not raise any invalid memory access.
37  * \ingroup mrpt_math_grp
38  */
39 template <class T>
41 {
42  // Public typedefs
43  public:
44  /**
45  * Internal map type, used to store the actual matrix.
46  */
47  using SparseMatrixMap = typename std::map<std::pair<size_t, size_t>, T>;
48  /**
49  * Const iterator to move through the matrix.
50  * \sa CSparseMatrixTemplate::const_reverse_iterator
51  */
52  using const_iterator = typename SparseMatrixMap::const_iterator;
53  /**
54  * Const reverse iterator to move through the matrix.
55  * \sa CSparseMatrixTemplate::const_iterator
56  */
58  typename SparseMatrixMap::const_reverse_iterator;
59 
60  protected:
61  /**
62  * Size of the matrix.
63  */
64  size_t mRows{0}, mColumns{0};
65  /**
66  * Actual matrix.
67  */
69 
70  public:
71  /**
72  * Basic constructor with no data. Size is set to (0,0).
73  */
74  CSparseMatrixTemplate() = default;
75  /**
76  * Constructor with default size.
77  */
78  CSparseMatrixTemplate(size_t nR, size_t nC) : mRows(nR), mColumns(nC) {}
79  /**
80  * Element access operator. Doesn't check bounds.
81  */
82  inline T operator()(size_t r, size_t c) const
83  {
84  auto it = objectList.find(std::make_pair(r, c));
85  if (it == objectList.end())
86  return T();
87  else
88  return it->second;
89  }
90 
91  /** Element access operator. Checks bounds.
92  */
93  inline bool exists(size_t r, size_t c) const
94  {
95 #if defined(_DEBUG) || (MRPT_ALWAYS_CHECKS_DEBUG_MATRICES)
96  if (r >= mRows || c >= mColumns) throw std::logic_error("Out of range");
97 #endif
98  return (objectList.find(std::make_pair(r, c)) != objectList.end());
99  }
100 
101  /**
102  * Reference access operator. Checks for bounds.
103  */
104  inline T& operator()(size_t r, size_t c)
105  { //-V659
106 #if defined(_DEBUG) || (MRPT_ALWAYS_CHECKS_DEBUG_MATRICES)
107  if (r >= mRows || c >= mColumns) throw std::logic_error("Out of range");
108 #endif
109  return objectList[std::make_pair(r, c)];
110  }
111  /**
112  * Returns the amount of rows in this matrix.
113  * \sa getColCount,getRow
114  */
115  inline size_t rows() const { return mRows; }
116  /**
117  * Returns the amount of columns in this matrix.
118  * \sa rows()
119  */
120  inline size_t cols() const { return mColumns; }
121  /**
122  * Extracts a full row from the matrix.
123  * \sa rows(),getColumn,setRow
124  * \throw std::logic_error on out of range.
125  */
126  template <typename VECTOR>
127  void getRow(size_t nRow, VECTOR& vec) const
128  {
129 #if defined(_DEBUG) || (MRPT_ALWAYS_CHECKS_DEBUG_MATRICES)
130  if (nRow >= mRows) throw std::logic_error("Out of range");
131 #endif
132  vec.resize(mColumns);
133  size_t nextIndex = 0;
134  for (typename SparseMatrixMap::const_iterator it = objectList.begin();
135  it != objectList.end(); ++it)
136  {
137  const std::pair<size_t, size_t>& index = it->first;
138  if (index.first < nRow)
139  continue;
140  else if (index.first == nRow)
141  {
142  for (size_t i = nextIndex; i < index.second; i++) vec[i] = T();
143  vec[index.second] = it->second;
144  nextIndex = index.second + 1;
145  }
146  else
147  {
148  for (size_t i = nextIndex; i < mColumns; i++) vec[i] = T();
149  break;
150  }
151  }
152  }
153  /**
154  * Extracts a full column from the matrix.
155  * \sa getColCount,getRow,setColumn
156  * \throw std::logic_error on out of range.
157  */
158  template <typename VECTOR>
159  void getColumn(size_t nCol, VECTOR& vec) const
160  {
161 #if defined(_DEBUG) || (MRPT_ALWAYS_CHECKS_DEBUG_MATRICES)
162  if (nCol >= mColumns) throw std::logic_error("Out of range");
163 #endif
164  vec.resize(mRows);
165  size_t nextIndex = 0;
166  for (typename SparseMatrixMap::const_iterator it = objectList.begin();
167  it != objectList.end(); ++it)
168  {
169  const std::pair<size_t, size_t>& index = it->first;
170  if (index.second == nCol)
171  {
172  for (size_t i = nextIndex; i < index.first; i++) vec[i] = T();
173  vec[index.first] = it->second;
174  nextIndex = index.first + 1;
175  }
176  }
177  for (size_t i = nextIndex; i < mRows; i++) vec[i] = T();
178  }
179  /**
180  * Inserts an element into the matrix.
181  * \sa operator()(size_t,size_t)
182  */
183  inline void insert(size_t row, size_t column, const T& obj)
184  {
185  operator()(row, column) = obj;
186  }
187 
188  /** Inserts submatrix at a given location */
189  template <class MATRIX_LIKE>
190  inline void insertMatrix(size_t row, size_t column, const MATRIX_LIKE& mat)
191  {
192  for (size_t nr = 0; nr < mat.rows(); nr++)
193  for (size_t nc = 0; nc < mat.cols(); nc++)
194  operator()(row + nr, column + nc) = mat(nr, nc);
195  }
196 
197  // Public interface only supports const iterators. This way, no user of this
198  // class will be able to freely modify it contents.
199  /**
200  * Returns an iterator which points to the starting point of the matrix.
201  * It's a const_iterator, so that the usar isn't able to modify the matrix
202  * content into an invalid state.
203  * \sa end,rbegin,rend
204  */
205  inline const_iterator begin() const { return objectList.begin(); }
206  /**
207  * Returns an iterator which points to the end of the matrix. It's a
208  * const_iterator, so that the usar isn't able to modify the matrix content
209  * into an invalid state.
210  * \sa begin,rbegin,rend
211  */
212  inline const_iterator end() const { return objectList.end(); }
213  /**
214  * Returns an iterator which points to the end of the matrix, and can be
215  * used to move backwards. It's a const_reverse_iterator, so that the usar
216  * isn't able to modify the matrix content into an invalid state.
217  * \sa begin,end,rend
218  */
219  inline const_reverse_iterator rbegin() const { return objectList.rbegin(); }
220  /**
221  * Returns an iterator which points to the starting point of the matrix,
222  * although it's the upper limit of the matrix since it's a reverse
223  * iterator. Also, it's a const_reverse_iterator, so that the usar isn't
224  * able to modify the matrix content into an invalid state.
225  * \sa begin,end,rbegin
226  */
227  inline const_reverse_iterator rend() const { return objectList.rend(); }
228  /**
229  * Inserts a full row into the matrix. The third argument is used to
230  * specify a null object (which won't be inserted, since the matrix is
231  * sparse).
232  * \sa getRow
233  * \throw std::logic_error on out of range or wrong sized vector.
234  */
235  template <typename VECTOR>
236  void setRow(size_t nRow, const VECTOR& vec, const T& nullObject = T())
237  {
238 #if defined(_DEBUG) || (MRPT_ALWAYS_CHECKS_DEBUG_MATRICES)
239  if (nRow >= mRows) throw std::logic_error("Out of range");
240 #endif
241  size_t N = vec.size();
242  if (N != mColumns) throw std::logic_error("Wrong-sized vector");
243  for (size_t i = 0; i < N; i++)
244  {
245  const T& obj = vec[i];
246  std::pair<size_t, size_t> index = std::make_pair(nRow, i);
247  if (obj == nullObject)
248  objectList.erase(index);
249  else
250  objectList[index] = obj;
251  }
252  }
253  /**
254  * Inserts a full column into the matrix. The third argument is used to
255  * specify a null object (which won't be inserted, since the matrix is
256  * sparse).
257  * \sa getColumn
258  * \throw std::logic_error on out of range or wrong sized vector.
259  */
260  template <typename VECTOR>
261  void setColumn(size_t nCol, const VECTOR& vec, const T& nullObject = T())
262  {
263 #if defined(_DEBUG) || (MRPT_ALWAYS_CHECKS_DEBUG_MATRICES)
264  if (nCol >= mColumns) throw std::logic_error("Out of range");
265 #endif
266  size_t N = vec.size();
267  if (N != mRows) throw std::logic_error("Wrong-sized vector");
268  for (size_t i = 0; i < N; i++)
269  {
270  const T& obj = vec[i];
271  std::pair<size_t, size_t> index = std::make_pair(i, nCol);
272  if (obj == nullObject)
273  objectList.erase(index);
274  else
275  objectList[index] = obj;
276  }
277  }
278  /**
279  * Changes the size of the matrix.
280  */
281  void resize(size_t nRows, size_t nCols)
282  {
283  // if (mRows<0||mColumns<0) throw std::logic_error("Invalid range"); //
284  // This case never happens!
285  if (mRows == nRows && mColumns == nCols) return;
286  mRows = nRows;
287  mColumns = nCols;
288  std::vector<std::pair<size_t, size_t>> toErase;
289  for (auto it = objectList.begin(); it != objectList.end(); ++it)
290  {
291  const std::pair<size_t, size_t>& i = it->first;
292  if (i.first >= nRows || i.second >= nCols)
293  toErase.push_back(it->first);
294  }
295  for (auto it = toErase.begin(); it != toErase.end(); ++it)
296  objectList.erase(*it);
297  }
298  /**
299  * Extracts a submatrix form the matrix.
300  * \sa operator()(size_t,size_t)
301  * \throw std::logic_error on invalid bounds.
302  */
304  size_t firstRow, size_t lastRow, size_t firstColumn,
305  size_t lastColumn) const
306  {
307 #if defined(_DEBUG) || (MRPT_ALWAYS_CHECKS_DEBUG_MATRICES)
308  if (lastRow >= mRows || lastColumn >= mColumns)
309  throw std::logic_error("Out of range");
310  if (firstRow > lastRow || firstColumn > lastColumn)
311  throw std::logic_error("Invalid size");
312 #endif
314  lastRow + 1 - firstRow, lastColumn + 1 - firstColumn);
315  for (typename SparseMatrixMap::const_iterator it = begin(); it != end();
316  ++it)
317  {
318  const std::pair<size_t, size_t>& i = it->first;
319  if (i.first >= firstRow && i.first <= lastRow &&
320  i.second >= firstColumn && i.second <= lastColumn)
321  res(i.first - firstRow, i.second - firstColumn) = it->second;
322  }
323  return res;
324  }
325  /**
326  * Gets a vector containing all the elements of the matrix, ignoring their
327  * position.
328  */
329  template <typename VECTOR>
330  void asVector(VECTOR& vec) const
331  {
332  size_t N = objectList.size();
333  vec.resize(0);
334  vec.reserve(N);
335  for (const_iterator it = objectList.begin(); it != objectList.end();
336  ++it)
337  vec.push_back(it->second);
338  }
339  /**
340  * Gets the amount of non-null elements inside the matrix.
341  * \sa getNullElements,isNull,isNotNull
342  */
343  inline size_t getNonNullElements() const { return objectList.size(); }
344  /** Are there no elements set to !=0 ?
345  * \sa getNullElements,isNull,isNotNull
346  */
347  inline bool empty() const { return objectList.empty(); }
348  /**
349  * Gets the amount of null elements inside the matrix.
350  * \sa getNonNullElements,isNull,isNotNull
351  */
352  inline size_t getNullElements() const
353  {
354  return mRows * mColumns - getNonNullElements();
355  }
356  /**
357  * Checks whether an element of the matrix is the default object.
358  * \sa getNonNullElements,getNullElements,isNotNull
359  * \throw std::logic_error on out of range
360  */
361  inline bool isNull(size_t nRow, size_t nCol) const
362  {
363  if (nRow >= mRows || nCol >= mColumns)
364  throw std::logic_error("Out of range");
365  return objectList.count(std::make_pair(nRow, nCol)) == 0;
366  }
367  /**
368  * Checks whether an element of the matrix is not the default object.
369  * \sa getNonNullElements,getNullElements,isNull
370  */
371  inline bool isNotNull(size_t nRow, size_t nCol) const
372  {
373  if (nRow >= mRows || nCol >= mColumns)
374  throw std::logic_error("Out of range");
375  return objectList.count(std::make_pair(nRow, nCol)) > 0;
376  }
377  /**
378  * Completely removes all elements, although maintaining the matrix's size.
379  */
380  inline void clear() { objectList.clear(); }
381  /**
382  * Checks each non-null elements against the basic objects, erasing
383  * unnecesary references to it.
384  */
385  void purge(T nullObject = T())
386  {
387  std::vector<std::pair<size_t, size_t>> nulls;
388  for (const_iterator it = begin(); it != end(); ++it)
389  if (it->second == nullObject) nulls.push_back(it->first);
390  for (auto it = nulls.begin(); it != nulls.end(); ++it)
391  objectList.erase(*it);
392  }
393 }; // end of sparse matrix
394 
395 /** A sparse matrix container for square symmetrical content around the main
396  * diagonal.
397  * This class saves half of the space with respect to CSparseMatrixTemplate
398  * since only those entries (c,r) such as c>=r are really stored,
399  * but both (c,r) and (r,c) can be retrieved or set and both redirect to the
400  * same internal cell container.
401  * \sa CSparseMatrixTemplate
402  */
403 template <class T>
405 {
406  public:
409  : CSparseMatrixTemplate<T>(o)
410  {
411  }
413  : CSparseMatrixTemplate<T>(o)
414  {
415  }
416  virtual ~CSparseSymmetricalMatrix() = default;
417  void resize(size_t matrixSize)
418  {
419  CSparseMatrixTemplate<T>::resize(matrixSize, matrixSize);
420  }
421 
422  inline T operator()(size_t r, size_t c) const
423  {
424  if (c < r) std::swap(r, c); // Symmetrical matrix
426  CSparseMatrixTemplate<T>::objectList.find(std::make_pair(r, c));
428  return T();
429  else
430  return it->second;
431  }
432  inline T& operator()(size_t r, size_t c)
433  { //-V659
434  if (c < r) std::swap(r, c); // Symmetrical matrix
437  throw std::logic_error("Out of range");
438  return CSparseMatrixTemplate<T>::objectList[std::make_pair(r, c)];
439  }
440 
441 }; // end of CSparseSymmetricalMatrix
442 } // namespace mrpt::math
void insertMatrix(size_t row, size_t column, const MATRIX_LIKE &mat)
Inserts submatrix at a given location.
const_iterator begin() const
Returns an iterator which points to the starting point of the matrix.
bool isNotNull(size_t nRow, size_t nCol) const
Checks whether an element of the matrix is not the default object.
size_t getNullElements() const
Gets the amount of null elements inside the matrix.
size_t getNonNullElements() const
Gets the amount of non-null elements inside the matrix.
typename SparseMatrixMap::const_reverse_iterator const_reverse_iterator
Const reverse iterator to move through the matrix.
void getRow(size_t nRow, VECTOR &vec) const
Extracts a full row from the matrix.
void insert(size_t row, size_t column, const T &obj)
Inserts an element into the matrix.
T & operator()(size_t r, size_t c)
Reference access operator.
CSparseSymmetricalMatrix(const CSparseSymmetricalMatrix &o)
A sparse matrix container (with cells of any type), with iterators.
bool empty() const
Are there no elements set to !=0 ?
void purge(T nullObject=T())
Checks each non-null elements against the basic objects, erasing unnecesary references to it...
CSparseMatrixTemplate(size_t nR, size_t nC)
Constructor with default size.
This base provides a set of functions for maths stuff.
void asVector(VECTOR &vec) const
Gets a vector containing all the elements of the matrix, ignoring their position. ...
T operator()(size_t r, size_t c) const
Element access operator.
size_t cols() const
Returns the amount of columns in this matrix.
typename std::map< std::pair< size_t, size_t >, T > SparseMatrixMap
Internal map type, used to store the actual matrix.
size_t rows() const
Returns the amount of rows in this matrix.
CSparseMatrixTemplate()=default
Basic constructor with no data.
size_t mRows
Size of the matrix.
const_reverse_iterator rend() const
Returns an iterator which points to the starting point of the matrix, although it&#39;s the upper limit o...
void clear()
Completely removes all elements, although maintaining the matrix&#39;s size.
CSparseSymmetricalMatrix(const CSparseMatrixTemplate< T > &o)
const_iterator end() const
Returns an iterator which points to the end of the matrix.
bool isNull(size_t nRow, size_t nCol) const
Checks whether an element of the matrix is the default object.
T operator()(size_t r, size_t c) const
CSparseMatrixTemplate< T > operator()(size_t firstRow, size_t lastRow, size_t firstColumn, size_t lastColumn) const
Extracts a submatrix form the matrix.
void setRow(size_t nRow, const VECTOR &vec, const T &nullObject=T())
Inserts a full row into the matrix.
SparseMatrixMap objectList
Actual matrix.
void resize(size_t nRows, size_t nCols)
Changes the size of the matrix.
virtual ~CSparseSymmetricalMatrix()=default
void getColumn(size_t nCol, VECTOR &vec) const
Extracts a full column from the matrix.
bool exists(size_t r, size_t c) const
Element access operator.
void setColumn(size_t nCol, const VECTOR &vec, const T &nullObject=T())
Inserts a full column into the matrix.
const_reverse_iterator rbegin() const
Returns an iterator which points to the end of the matrix, and can be used to move backwards...
typename SparseMatrixMap::const_iterator const_iterator
Const iterator to move through the matrix.
A sparse matrix container for square symmetrical content around the main diagonal.



Page generated by Doxygen 1.8.14 for MRPT 2.0.4 Git: 33de1d0ad Sat Jun 20 11:02:42 2020 +0200 at sáb jun 20 17:35:17 CEST 2020