File view_matrix_sparse_set.hpp

template<typename T>
class SparseSetView : public CompositeMatrix<AllocatedListOfLists<IndexedValue<T>>, AllocatedCContiguousView<uint32>>
#include <view_matrix_sparse_set.hpp>

A two-dimensional view that provides random read and write access, as well as row-wise read and write access via iterators, to values stored in a sparse matrix in the list of lists (LIL) format. Compared to the view ListOfLists, the ability to provide random access to the elements in the view comes at the expense of memory efficiency, as it requires to not only maintain a sparse matrix that stores the non-zero elements, but also a dense matrix that stores for each element the corresponding position in the sparse matrix, if available.

The data structure that is used for the representation of a single row is often referred to as an “unordered sparse

set”. It was originally proposed in “An efficient representation for sparse sets”, Briggs, Torczon, 1993 (see

https://dl.acm.org/doi/pdf/10.1145/176454.176484).

Template Parameters:

T – The type of the values, the view provides access to

Public Types

typedef AllocatedListOfLists<IndexedValue<T>>::value_type value_type

The type of the values, the view provides access to.

typedef AllocatedListOfLists<IndexedValue<T>>::value_const_iterator value_const_iterator

An iterator that provides read-only access to the values in the view.

typedef AllocatedListOfLists<IndexedValue<T>>::value_iterator value_iterator

An iterator that provides access to the values in the view and allows to modify them.

typedef ConstRow<typename AllocatedListOfLists<IndexedValue<T>>::const_row, typename AllocatedCContiguousView<uint32>::value_const_iterator> const_row

Provides read-only access to an individual row in the view.

typedef Row<typename AllocatedListOfLists<IndexedValue<T>>::row, typename AllocatedCContiguousView<uint32>::value_iterator> row

Provides access to an individual row in the view and allows to modify it.

Public Functions

inline SparseSetView(uint32 numRows, uint32 numCols)
Parameters:

  • numRows – The number of rows in the view

  • numCols – The number of columns in the view

inline SparseSetView(SparseSetView &&other)
Parameters:

other – A reference to an object of type SparseSetView that should be moved

inline virtual ~SparseSetView() override
inline const_row operator[](uint32 row) const

Creates and returns a view that provides read-only access to a specific row in the view.

Parameters:

row – The index of the row

Returns:

A const_row

inline row operator[](uint32 row)

Creates and returns a view that provides access to a specific row in the view and allows to modify it.

Parameters:

row – The index of the row

Returns:

A row

inline value_const_iterator values_cbegin(uint32 row) const

Returns a value_const_iterator to the beginning of the values in a specific row of the view.

Parameters:

row – The index of the row

Returns:

A value_const_iterator to the beginning of the values

inline value_const_iterator values_cend(uint32 row) const

Returns a value_const_iterator to the end of the values in a specific row of the view.

Parameters:

row – The index of the row

Returns:

A value_const_iterator to the end of the values

inline value_iterator values_begin(uint32 row)

Returns a value_iterator to the beginning of the values in a specific row of the view.

Parameters:

row – The index of the row

Returns:

A value_iterator to the beginning of the values

inline value_iterator values_end(uint32 row)

Returns a value_iterator to the end of the values in a specific row of the view.

Parameters:

row – The index of the row

Returns:

A value_iterator to the end of the values

inline void clear()

Sets all values stored in the matrix to zero.

Protected Static Attributes

static const uint32 MAX_INDEX = std::numeric_limits<uint32>::max()

The index that is used to indicate that the value at a specific row and column is zero.

template<typename ValueRow, typename IndexIterator>
class ConstRow

Provides read-only access to a single row of a SparseSetView.

Template Parameters:

  • ValueRow – The type of the object that provides access to the non-zero elements in the row

  • IndexIterator – The type of the iterator that provides access to the indices of non-zero elements that correspond to certain columns

Public Types

typedef SparseSetView::value_type value_type

The type of the values in the row.

typedef SparseSetView::value_const_iterator const_iterator

An iterator that provides read-only access to the values in the row.

Public Functions

inline ConstRow(ValueRow row, IndexIterator indexIterator)
Parameters:

  • row – An object of template type ValueRow that provides access to the non-zero elements in the row

  • indexIterator – An iterator that provides access to the indices in row that correspond to certain columns

inline const_iterator cbegin() const

Returns a const_iterator to the beginning of the row.

Returns:

A const_iterator to the beginning

inline const_iterator cend() const

Returns a const_iterator to the end of the row.

Returns:

A const_iterator to the end

inline const value_type *operator[](uint32 index) const

Returns a pointer to the element that corresponds to a specific index.

Parameters:

index – The index of the element to be returned

Returns:

A pointer to the element that corresponds to the given index or a null pointer, if no such element is available

Public Members

const uint32 numElements

The number of elements in the row.

Protected Attributes

ValueRow row_

A view that provides access to the non-zero elements in the view.

IndexIterator indexIterator_

A view that provides access to the indices of non-zero elements in the row that correspond to certain columns.

template<typename ValueRow, typename IndexIterator>
class Row : public SparseSetView<ValueRow, IndexIterator>::ConstRow

Provides read and write access to a single row of a SparseSetView.

Template Parameters:

  • ValueRow – The type of the object that provides access to the non-zero elements in the row

  • IndexIterator – The type of the iterator that provides access to the indices of non-zero elements that correspond to certain columns

Public Types

typedef SparseSetView::value_iterator iterator

An iterator that provides access to the values in the row and allows to modify them.

Public Functions

inline Row(ValueRow row, IndexIterator indexIterator)
Parameters:

  • row – An object of template type ValueRow that provides access to the non-zero elements in the row

  • indexIterator – An iterator that provides access to the indices in row that correspond to certain columns

inline iterator begin()

Returns an iterator to the beginning of the row.

Returns:

An iterator to the beginning

inline iterator end()

Returns an iterator to the end of the row.

Returns:

An iterator to the end

inline SparseSetView::value_type *operator[](uint32 index)

Returns a pointer to the element that corresponds to a specific index.

Parameters:

index – The index of the element to be returned

Returns:

A pointer to the element that corresponds to the given index or a null pointer, if no such element is available

inline SparseSetView::value_type &emplace(uint32 index)

Returns a reference to the element that corresponds to a specific index. If no such element is available, it is inserted into the vector.

Parameters:

index – The index of the element to be returned

Returns:

A reference to the element that corresponds to the given index

inline SparseSetView::value_type &emplace(uint32 index, const T &defaultValue)

Returns a reference to the element that corresponds to a specific index. If no such element is available, it is inserted into the vector using a specific default value.

Parameters:

  • index – The index of the element to be returned

  • defaultValue – The default value to be used

Returns:

A reference to the element that corresponds to the given index

inline void erase(uint32 index)

Removes the element that corresponds to a specific index, if available.

Parameters:

index – The index of the element to be removed

inline void clear()

Removes all elements from the row.

template<typename Matrix>
class IterableSparseSetViewDecorator : public Matrix
#include <view_matrix_sparse_set.hpp>

Provides random read and write access, as well as row-wise read and write access via iterators, to values stored in a sparse matrix in the list of lists (LIL) format.

Template Parameters:

Matrix – The type of the matrix

Subclassed by SparseSetMatrix< T >

Public Types

typedef Matrix::view_type::value_const_iterator value_const_iterator

An iterator that provides read-only access to the values in the matrix.

typedef Matrix::view_type::value_iterator value_iterator

An iterator that provides access to the values in the matrix and allows to modify them.

typedef Matrix::view_type::const_row const_row

Provides read-only access to an individual row in the matrix.

typedef Matrix::view_type::row row

Provides access to an individual row in the matrix and allows to modify it.

Public Functions

inline IterableSparseSetViewDecorator(typename Matrix::view_type &&view)
Parameters:

view – The view, the matrix should be backed by

inline virtual ~IterableSparseSetViewDecorator() override
inline const_row operator[](uint32 row) const

Creates and returns a view that provides read-only access to a specific row in the matrix.

Parameters:

row – The index of the row

Returns:

A const_row

inline row operator[](uint32 row)

Creates and returns a view that provides access to a specific row in the matrix and allows to modify it.

Parameters:

row – The index of the row

Returns:

A row

inline value_const_iterator values_cbegin(uint32 row) const

Returns a value_const_iterator to the beginning of the values in a specific row of the matrix.

Parameters:

row – The index of the row

Returns:

A value_const_iterator to the beginning of the values

inline value_const_iterator values_cend(uint32 row) const

Returns a value_const_iterator to the end of the values in a specific row of the matrix.

Parameters:

row – The index of the row

Returns:

A value_const_iterator to the end of the values

inline value_iterator values_begin(uint32 row)

Returns a value_iterator to the beginning of the values in a specific row of the matrix.

Parameters:

row – The index of the row

Returns:

A value_iterator to the beginning of the values

inline value_iterator values_end(uint32 row)

Returns a value_iterator to the end of the values in a specific row of the matrix.

Parameters:

row – The index of the row

Returns:

A value_iterator to the end of the values