An index set class represents an ordered set of intervals. More...

#include <ginkgo/core/base/index_set.hpp>

Public Types
using	index_type = IndexType
	The type of elements stored in the index set.

Public Member Functions
	index_set (std::shared_ptr< const Executor > exec) noexcept
	Creates an empty index_set tied to the specified Executor. More...

	index_set (std::shared_ptr< const gko::Executor > exec, std::initializer_list< IndexType > init_list, const bool is_sorted=false)
	Creates an index set on the specified executor from the initializer list. More...

	index_set (std::shared_ptr< const gko::Executor > exec, const index_type size, const gko::array< index_type > &indices, const bool is_sorted=false)
	Creates an index set on the specified executor and the given size. More...

	index_set (std::shared_ptr< const Executor > exec, const index_set &other)
	Creates a copy of the input index_set on a different executor. More...

	index_set (const index_set &other)
	Creates a copy of the input index_set. More...

	index_set (std::shared_ptr< const Executor > exec, index_set &&other)
	Moves the input index_set to a different executor. More...

	index_set (index_set &&other)
	Moves the input index_set. More...

index_set &	operator= (const index_set &other)
	Copies data from another index_set. More...

index_set &	operator= (index_set &&other)
	Moves data from another index_set. More...

void	clear () noexcept
	Deallocates all data used by the index_set. More...

std::shared_ptr< const Executor >	get_executor () const
	Returns the executor of the index_set. More...

index_type	get_size () const
	Returns the size of the index set space. More...

bool	is_contiguous () const
	Returns if the index set is contiguous. More...

index_type	get_num_elems () const
	Return the actual number of indices stored in the index set. More...

index_type	get_global_index (index_type local_index) const
	Return the global index given a local index. More...

index_type	get_local_index (index_type global_index) const
	Return the local index given a global index. More...

array< index_type >	map_local_to_global (const array< index_type > &local_indices, const bool is_sorted=false) const
	This is an array version of the scalar function above. More...

array< index_type >	map_global_to_local (const array< index_type > &global_indices, const bool is_sorted=false) const
	This is an array version of the scalar function above. More...

array< index_type >	to_global_indices () const
	This function allows the user obtain a decompressed global_indices array from the indices stored in the index set. More...

array< bool >	contains (const array< index_type > &global_indices, const bool is_sorted=false) const
	Checks if the individual global indeices exist in the index set. More...

bool	contains (const index_type global_index) const
	Checks if the global index exists in the index set. More...

index_type	get_num_subsets () const
	Returns the number of subsets stored in the index set. More...

const index_type *	get_subsets_begin () const
	Returns a pointer to the beginning indices of the subsets. More...

const index_type *	get_subsets_end () const
	Returns a pointer to the end indices of the subsets. More...

const index_type *	get_superset_indices () const
	Returns a pointer to the cumulative indices of the superset of the subsets. More...

Detailed Description

template<typename IndexType = int32>
class gko::index_set< IndexType >

An index set class represents an ordered set of intervals.

The index set contains subsets which store the starting and end points of a range, [a,b), storing the first index and one past the last index. As the index set only stores the end-points of ranges, it can be quite efficient in terms of storage.

This class is particularly useful in storing continuous ranges. For example, consider the index set (1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 18, 19, 20, 21, 42). Instead of storing the entire array of indices, one can store intervals ([1,9), [10,13), [18,22), [42,43)), thereby only using half the storage.

We store three arrays, one (subsets_begin) with the starting indices of the subsets in the index set, another (subsets_end) storing one index beyond the end indices of the subsets and the last (superset_cumulative_indices) storing the cumulative number of indices in the subsequent subsets with an initial zero which speeds up the querying. Additionally, the arrays conataining the range boundaries (subsets_begin, subsets_end) are stored in a sorted fashion.

Therefore the storage would look as follows

index_set = (1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 18, 19, 20, 21, 42) subsets_begin = {1, 10, 18, 42} subsets_end = {9, 13, 22, 43} superset_cumulative_indices = {0, 8, 11, 15, 16}

Template Parameters

index_type type of the indices being stored in the index set.

Constructor & Destructor Documentation

◆ index_set() [1/7]

template<typename IndexType = int32>

gko::index_set< IndexType >::index_set ( std::shared_ptr< const Executor > exec )

inlineexplicitnoexcept

Creates an empty index_set tied to the specified Executor.

Parameters

exec	the Executor where the index_set data is allocated

◆ index_set() [2/7]

template<typename IndexType = int32>

gko::index_set< IndexType >::index_set	(	std::shared_ptr< const gko::Executor >	exec,
		std::initializer_list< IndexType >	init_list,
		const bool	is_sorted = `false`
	)

inlineexplicit

Creates an index set on the specified executor from the initializer list.

Parameters

exec	the Executor where the index set data will be allocated
init_list	the indices that the index set should hold in an initializer_list.
is_sorted	a parameter that specifies if the indices array is sorted or not. `true` if sorted.

◆ index_set() [3/7]

template<typename IndexType = int32>

gko::index_set< IndexType >::index_set	(	std::shared_ptr< const gko::Executor >	exec,
		const index_type	size,
		const gko::array< index_type > &	indices,
		const bool	is_sorted = `false`
	)

inlineexplicit

Creates an index set on the specified executor and the given size.

Parameters

exec	the Executor where the index set data will be allocated
size	the maximum index the index set it allowed to hold. This is the size of the index space.
indices	the indices that the index set should hold.
is_sorted	a parameter that specifies if the indices array is sorted or not. `true` if sorted.

References gko::array< ValueType >::get_size().

◆ index_set() [4/7]

template<typename IndexType = int32>

gko::index_set< IndexType >::index_set	(	std::shared_ptr< const Executor >	exec,
		const index_set< IndexType > &	other
	)

inline

Creates a copy of the input index_set on a different executor.

Parameters

exec	the executor where the new index_set will be created
other	the index_set to copy from

◆ index_set() [5/7]

template<typename IndexType = int32>

gko::index_set< IndexType >::index_set ( const index_set< IndexType > & other )

inline

Creates a copy of the input index_set.

Parameters

other the index_set to copy from

◆ index_set() [6/7]

template<typename IndexType = int32>

gko::index_set< IndexType >::index_set	(	std::shared_ptr< const Executor >	exec,
		index_set< IndexType > &&	other
	)

inline

Moves the input index_set to a different executor.

Parameters

exec	the executor where the new index_set will be moved to
other	the index_set to move from

◆ index_set() [7/7]

template<typename IndexType = int32>

gko::index_set< IndexType >::index_set ( index_set< IndexType > && other )

inline

Moves the input index_set.

Parameters

other the index_set to move from

Member Function Documentation

◆ clear()

template<typename IndexType = int32>

void gko::index_set< IndexType >::clear ( )

inlinenoexcept

Deallocates all data used by the index_set.

The index_set is left in a valid, but empty state, so the same index_set can be used to allocate new memory. Calls to index_set::get_subsets_begin() will return a nullptr.

References gko::array< ValueType >::clear().

◆ contains() [1/2]

template<typename IndexType = int32>

array<bool> gko::index_set< IndexType >::contains	(	const array< index_type > &	global_indices,
		const bool	is_sorted = `false`
	)		const

Checks if the individual global indeices exist in the index set.

Parameters

global_indices	the indices to check.
is_sorted	a parameter that specifies if the query array is sorted or not. `true` if sorted.

Returns: the array that contains element wise whether the corresponding global index in the index set or not.

◆ contains() [2/2]

template<typename IndexType = int32>

bool gko::index_set< IndexType >::contains ( const index_type global_index ) const

Checks if the global index exists in the index set.

Parameters

global_index the index to check.

Returns: whether the element exists in the index set.

Warning: This single entry query can have significant kernel launch overheads and should be avoided if possible.

◆ get_executor()

template<typename IndexType = int32>

std::shared_ptr<const Executor> gko::index_set< IndexType >::get_executor ( ) const

inline

Returns the executor of the index_set.

Returns: the executor.

◆ get_global_index()

template<typename IndexType = int32>

index_type gko::index_set< IndexType >::get_global_index ( index_type local_index ) const

Return the global index given a local index.

Consider the set idx_set = (0, 1, 2, 4, 6, 7, 8, 9). This function returns the element at the global index k stored in the index set. For example, idx_set.get_global_index(0) == 0 idx_set.get_global_index(3) == 4 and idx_set.get_global_index(7) == 9

Note: This function returns a scalar value and needs a scalar value. For repeated queries, it is more efficient to use the array functions that take and return arrays which allow for more throughput.

Parameters

local_index the local index.

Returns: the global index from the index set.

Warning: This single entry query can have significant kernel launch overheads and should be avoided if possible.

◆ get_local_index()

template<typename IndexType = int32>

index_type gko::index_set< IndexType >::get_local_index ( index_type global_index ) const

Return the local index given a global index.

Consider the set idx_set = (0, 1, 2, 4, 6, 7, 8, 9). This function returns the local index in the index set of the provided index set. For example, idx_set.get_local_index(0) == 0 idx_set.get_local_index(4) == 3 and idx_set.get_local_index(6) == 4.

Note: This function returns a scalar value and needs a scalar value. For repeated queries, it is more efficient to use the array functions that take and return arrays which allow for more throughput.

Parameters

global_index the global index.

Returns: the local index of the element in the index set.

Warning: This single entry query can have significant kernel launch overheads and should be avoided if possible.

◆ get_num_elems()

template<typename IndexType = int32>

index_type gko::index_set< IndexType >::get_num_elems ( ) const

inline

Return the actual number of indices stored in the index set.

Returns: number of indices stored in the index set

◆ get_num_subsets()

template<typename IndexType = int32>

index_type gko::index_set< IndexType >::get_num_subsets ( ) const

inline

Returns the number of subsets stored in the index set.

Returns: the number of stored subsets.

References gko::array< ValueType >::get_size().

Referenced by gko::index_set< IndexType >::is_contiguous().

◆ get_size()

template<typename IndexType = int32>

index_type gko::index_set< IndexType >::get_size ( ) const

inline

Returns the size of the index set space.

Returns: the size of the index set space.

◆ get_subsets_begin()

template<typename IndexType = int32>

const index_type* gko::index_set< IndexType >::get_subsets_begin ( ) const

inline

Returns a pointer to the beginning indices of the subsets.

Returns: a pointer to the beginning indices of the subsets.

References gko::array< ValueType >::get_const_data().

◆ get_subsets_end()

template<typename IndexType = int32>

const index_type* gko::index_set< IndexType >::get_subsets_end ( ) const

inline

Returns a pointer to the end indices of the subsets.

Returns: a pointer to the end indices of the subsets.

References gko::array< ValueType >::get_const_data().

◆ get_superset_indices()

template<typename IndexType = int32>

const index_type* gko::index_set< IndexType >::get_superset_indices ( ) const

inline

Returns a pointer to the cumulative indices of the superset of the subsets.

Returns: a pointer to the cumulative indices of the superset of the subsets.

References gko::array< ValueType >::get_const_data().

◆ is_contiguous()

template<typename IndexType = int32>

bool gko::index_set< IndexType >::is_contiguous ( ) const

inline

Returns if the index set is contiguous.

Returns: if the index set is contiguous.

References gko::index_set< IndexType >::get_num_subsets().

◆ map_global_to_local()

template<typename IndexType = int32>

array<index_type> gko::index_set< IndexType >::map_global_to_local	(	const array< index_type > &	global_indices,
		const bool	is_sorted = `false`
	)		const

This is an array version of the scalar function above.

Parameters

global_indices	the global index array.
is_sorted	a parameter that specifies if the query array is sorted or not. `true` if sorted.

Returns: the local index array from the index set.

Note: Whenever possible, passing a sorted array is preferred as the queries can be significantly faster.

◆ map_local_to_global()

template<typename IndexType = int32>

array<index_type> gko::index_set< IndexType >::map_local_to_global	(	const array< index_type > &	local_indices,
		const bool	is_sorted = `false`
	)		const

This is an array version of the scalar function above.

Parameters

local_indices	the local index array.
is_sorted	a parameter that specifies if the query array is sorted or not. `true` if sorted .

Returns: the global index array from the index set.

Note: Whenever possible, passing a sorted array is preferred as the queries can be significantly faster.; Passing local indices from [0, size) is equivalent to using the @to_global_indices function.

◆ operator=() [1/2]

template<typename IndexType = int32>

index_set& gko::index_set< IndexType >::operator= ( const index_set< IndexType > & other )

inline

Copies data from another index_set.

The executor of this is preserved. In case this does not have an assigned executor, it will inherit the executor of other.

Parameters

other the index_set to copy from

Returns: this

◆ operator=() [2/2]

template<typename IndexType = int32>

index_set& gko::index_set< IndexType >::operator= ( index_set< IndexType > && other )

inline

Moves data from another index_set.

The executor of this is preserved. In case this does not have an assigned executor, it will inherit the executor of other.

Parameters

other the index_set to move from

Returns: this

◆ to_global_indices()

template<typename IndexType = int32>

array<index_type> gko::index_set< IndexType >::to_global_indices ( ) const

This function allows the user obtain a decompressed global_indices array from the indices stored in the index set.

Returns: the decompressed set of indices.

The documentation for this class was generated from the following file:

ginkgo/core/base/index_set.hpp

Public Types

Public Member Functions

Detailed Description

template<typename IndexType = int32> class gko::index_set< IndexType >

Constructor & Destructor Documentation

◆ index_set() [1/7]

◆ index_set() [2/7]

◆ index_set() [3/7]

◆ index_set() [4/7]

◆ index_set() [5/7]

◆ index_set() [6/7]

◆ index_set() [7/7]

Member Function Documentation

◆ clear()

◆ contains() [1/2]

◆ contains() [2/2]

◆ get_executor()

◆ get_global_index()

◆ get_local_index()

◆ get_num_elems()

◆ get_num_subsets()

◆ get_size()

◆ get_subsets_begin()

◆ get_subsets_end()

◆ get_superset_indices()

◆ is_contiguous()

◆ map_global_to_local()

◆ map_local_to_global()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ to_global_indices()

template<typename IndexType = int32>
class gko::index_set< IndexType >