Rank-Select compressed sparse vector. More...

#include <bmsparsevec_compr.h>

Inheritance diagram for bm::rsc_sparse_vector< Val, SV >:

[legend]

Data Structures
struct	is_remap_support
struct	is_rsc_support
struct	is_dynamic_splices
struct	statistics
class	reference
	Reference class to access elements via common [] operator. More...
class	const_iterator
	Const iterator to traverse the rsc sparse vector. More...
class	back_insert_iterator
	Back insert iterator implements buffered insert, faster than generic access assignment. More...

Public Types
enum	bit_slices { sv_slices = (sizeof(Val) * 8 + 1) , sv_value_slices = (sizeof(Val) * 8) }
enum	vector_capacity { max_vector_size = 1 }
typedef Val	value_type
typedef const value_type &	const_reference
typedef SV::size_type	size_type
typedef SV	sparse_vector_type
typedef SV::const_iterator	sparse_vector_const_iterator
typedef SV::bvector_type	bvector_type
typedef bvector_type *	bvector_type_ptr
typedef const bvector_type *	bvector_type_const_ptr
typedef bvector_type::allocator_type	allocator_type
typedef bvector_type::allocation_policy	allocation_policy_type
typedef bvector_type::rs_index_type	rs_index_type
typedef bvector_type::enumerator	bvector_enumerator_type
typedef SV::bmatrix_type	bmatrix_type
typedef SV::unsigned_value_type	unsigned_value_type

Public Member Functions
Construction and assignment
	rsc_sparse_vector (bm::null_support null_able=bm::use_null, allocation_policy_type ap=allocation_policy_type(), size_type bv_max_size=bm::id_max, const allocator_type &alloc=allocator_type())
	rsc_sparse_vector (const bvector_type &bv_null)
	Contructor to pre-initialize the list of assigned (not NULL) elements.
	~rsc_sparse_vector ()
	rsc_sparse_vector (const rsc_sparse_vector< Val, SV > &csv)
rsc_sparse_vector< Val, SV > &	operator= (const rsc_sparse_vector< Val, SV > &csv)
	rsc_sparse_vector (rsc_sparse_vector< Val, SV > &&csv) BMNOEXCEPT
rsc_sparse_vector< Val, SV > &	operator= (rsc_sparse_vector< Val, SV > &&csv) BMNOEXCEPT
Size, etc
size_type	size () const BMNOEXCEPT
	return size of the vector
bool	empty () const BMNOEXCEPT
	return true if vector is empty
void	sync_size () BMNOEXCEPT
	recalculate size to exclude tail NULL elements After this call size() will return the true size of the vector
void	resize (size_type new_size)
	change vector size
size_type	count_range_notnull (size_type left, size_type right) const BMNOEXCEPT
Element access
value_type	operator[] (size_type idx) const
	get specified element without bounds checking
value_type	at (size_type idx) const
	access specified element with bounds checking
value_type	get (size_type idx) const BMNOEXCEPT
	get specified element without bounds checking
unsigned_value_type	get_unsigned_bits (size_type idx, size_type N_bits) const BMNOEXCEPT
	Get raw unsigned value first N bits.
bool	try_get (size_type idx, value_type &v) const BMNOEXCEPT
	get specified element with NOT NULL check
bool	try_get_sync (size_type idx, value_type &v) const BMNOEXCEPT
	get specified element with NOT NULL check Caller guarantees that the vector is in sync mode (RS-index access).
void	push_back (size_type idx, value_type v)
	set specified element with bounds checking and automatic resize
void	push_back (value_type v)
	add element with automatic resize
void	push_back_null (size_type count)
	push back specified amount of NULL values
void	push_back_null ()
	push back NULL value
void	set (size_type idx, value_type v)
	set specified element with bounds checking and automatic resize
void	inc (size_type idx)
	increment specified element by one
void	inc (size_type idx, value_type v)
	increment specified element by one
void	inc_not_null (size_type idx, value_type v)
	increment specified element by one, element MUST be NOT NULL Faster than just inc() if element is NULL - behavior is undefined
void	set_null (size_type idx)
	set specified element to NULL RSC vector actually erases element when it is set to NULL (expensive).
void	set_null (const bvector_type &bv_idx)
	Set NULL all elements set as 1 in the argument vector.
void	clear (const bvector_type &bv_idx)
	Set vector elements spcified by argument bit-vector to zero Note that set to 0 elements are NOT going to tuned to NULL (NULL qualifier is preserved).
bool	is_null (size_type idx) const BMNOEXCEPT
	test if specified element is NULL
const bvector_type *	get_null_bvector () const BMNOEXCEPT
	Get bit-vector of assigned values (or NULL).
bool	find_rank (size_type rank, size_type &idx) const BMNOEXCEPT
	find position of compressed element by its rank
Export content to C-stype array
size_type	decode (value_type *arr, size_type idx_from, size_type size, bool zero_mem=true) const
	C-style decode.
size_type	decode_buf (value_type arr, value_type arr_buf_tmp, size_type idx_from, size_type size, bool zero_mem=true) const BMNOEXCEPT
	C-style decode (variant with external memory) Analog of decode, but requires two arrays.
size_type	gather (value_type arr, const size_type idx, size_type *idx_tmp_buf, size_type size, bm::sort_order sorted_idx) const
	Gather elements to a C-style array.
Comparison
bool	equal (const rsc_sparse_vector< Val, SV > &csv) const BMNOEXCEPT
	check if another vector has the same content
Load-Export compressed vector with data
void	load_from (const sparse_vector_type &sv_src)
	Load compressed vector from a sparse vector (with NULLs).
void	load_to (sparse_vector_type &sv) const
	Exort compressed vector to a sparse vector (with NULLs).
Iterator access
const_iterator	begin () const
	Provide const iterator access to container content.
const_iterator	end () const BMNOEXCEPT
	Provide const iterator access to the end.
const_iterator	get_const_iterator (size_type idx) const BMNOEXCEPT
	Get const_itertor re-positioned to specific element.
back_insert_iterator	get_back_inserter ()
Memory optimization
void	optimize (bm::word_t temp_block=0, typename bvector_type::optmode opt_mode=bvector_type::opt_compress, statistics stat=0)
	run memory optimization for all vector slices
void	clear_all (bool free_mem, unsigned) BMNOEXCEPT
	resize to zero, free memory
void	clear () BMNOEXCEPT
	resize to zero, free memory
void	calc_stat (struct rsc_sparse_vector< Val, SV >::statistics *st) const BMNOEXCEPT
	Calculates memory statistics.
void	freeze ()
	Turn sparse vector into immutable mode Read-only (immutable) vector uses less memory and allows faster searches.
bool	is_ro () const BMNOEXCEPT
	Returns true if vector is read-only.
Merge, split, partition data
void	copy_range (const rsc_sparse_vector< Val, SV > &csv, size_type left, size_type right)
	copy range of values from another sparse vector
void	merge_not_null (rsc_sparse_vector< Val, SV > &csv)
	merge two vectors (argument gets destroyed) It is important that both vectors have the same NULL vectors
Fast access structues sync
void	sync (bool force)
	Re-calculate rank-select index for faster access to vector.
void	sync ()
	Re-calculate prefix sum table used for rank search (if necessary).
bool	in_sync () const BMNOEXCEPT
	returns true if prefix sum table is in sync with the vector
bool	is_sync () const BMNOEXCEPT
	returns true if prefix sum table is in sync with the vector
void	unsync () BMNOEXCEPT
	Unsync the prefix sum table.

Protected Types
enum	octet_slices { sv_octet_slices = sizeof(value_type) }
typedef bm::heap_matrix< unsigned char, 1, 1, typename bvector_type::allocator_type >	remap_matrix_type
	unused remap matrix type for compatibility with the sparse serializer

Protected Member Functions
bool	resolve_sync (size_type idx, size_type *idx_to) const BMNOEXCEPT
bool	resolve_range (size_type from, size_type to, size_type idx_from, size_type idx_to) const BMNOEXCEPT
void	resize_internal (size_type sz)
size_type	size_internal () const BMNOEXCEPT
constexpr bool	is_remap () const BMNOEXCEPT
size_t	remap_size () const BMNOEXCEPT
const unsigned char *	get_remap_buffer () const BMNOEXCEPT
unsigned char *	init_remap_buffer () BMNOEXCEPT
void	set_remap () BMNOEXCEPT
const remap_matrix_type *	get_remap_matrix () const
remap_matrix_type *	get_remap_matrix ()
void	push_back_no_check (size_type idx, value_type v)

Static Protected Member Functions
static unsigned_value_type	s2u (value_type v) BMNOEXCEPT
	Convert signed value type to unsigned representation.
static value_type	u2s (unsigned_value_type v) BMNOEXCEPT

Friends
template<class SVect, unsigned S_FACTOR>
class	sparse_vector_scanner
template<class SVect>
class	sparse_vector_serializer
template<class SVect>
class	sparse_vector_deserializer

Various traits
bool	is_nullable () const
	if container supports NULL(unassigned) values (true)
static constexpr bool	is_compressed () BMNOEXCEPT
	various type traits
static constexpr bool	is_str () BMNOEXCEPT

Access to internals
bvector_type_const_ptr	get_slice (unsigned i) const BMNOEXCEPT
	get access to bit-plane, function checks and creates a plane
bvector_type_ptr	get_create_slice (unsigned i)
bvector_type_ptr	slice (unsigned i)
unsigned	effective_slices () const BMNOEXCEPT
const sparse_vector_type &	get_sv () const BMNOEXCEPT
	access dense vector
size_type	effective_size () const BMNOEXCEPT
	size of internal dense vector
size_type	effective_vector_max () const BMNOEXCEPT
	Always 1 (non-matrix type).
const bmatrix_type &	get_bmatrix () const BMNOEXCEPT
bmatrix_type &	get_bmatrix () BMNOEXCEPT
const rs_index_type *	get_RS () const BMNOEXCEPT
void	mark_null_idx (unsigned null_idx) BMNOEXCEPT
bool	resolve (size_type idx, size_type *idx_to) const BMNOEXCEPT
	Resolve logical address to access via rank compressed address.
static unsigned	slices () BMNOEXCEPT
	get total number of bit-slices in the vector
static unsigned	stored_slices ()
	Number of stored bit-slices (value slices + extra.

Detailed Description

template<class Val, class SV>
class bm::rsc_sparse_vector< Val, SV >

Rank-Select compressed sparse vector.

Container uses Rank-Select method of compression, where all NULL columns gets dropped, effective address of columns is computed using address bit-vector.

Use for cases, where memory efficiency is preferable over single element access latency.

Examples: inv_list.cpp, rscsample01.cpp, rscsample02.cpp, rscsample03.cpp, rscsample04.cpp, rscsample05.cpp, rscsample06.cpp, xsample03.cpp, xsample07.cpp, xsample08.cpp, and xsample09.cpp.

Definition at line 58 of file bmsparsevec_compr.h.

Member Typedef Documentation

◆ allocation_policy_type

template<class Val, class SV>

typedef bvector_type::allocation_policy bm::rsc_sparse_vector< Val, SV >::allocation_policy_type

Definition at line 76 of file bmsparsevec_compr.h.

◆ allocator_type

template<class Val, class SV>

typedef bvector_type::allocator_type bm::rsc_sparse_vector< Val, SV >::allocator_type

Definition at line 75 of file bmsparsevec_compr.h.

◆ bmatrix_type

template<class Val, class SV>

typedef SV::bmatrix_type bm::rsc_sparse_vector< Val, SV >::bmatrix_type

Definition at line 79 of file bmsparsevec_compr.h.

◆ bvector_enumerator_type

template<class Val, class SV>

typedef bvector_type::enumerator bm::rsc_sparse_vector< Val, SV >::bvector_enumerator_type

Definition at line 78 of file bmsparsevec_compr.h.

◆ bvector_type

template<class Val, class SV>

typedef SV::bvector_type bm::rsc_sparse_vector< Val, SV >::bvector_type

Definition at line 72 of file bmsparsevec_compr.h.

◆ bvector_type_const_ptr

template<class Val, class SV>

typedef const bvector_type* bm::rsc_sparse_vector< Val, SV >::bvector_type_const_ptr

Definition at line 74 of file bmsparsevec_compr.h.

◆ bvector_type_ptr

template<class Val, class SV>

typedef bvector_type* bm::rsc_sparse_vector< Val, SV >::bvector_type_ptr

Definition at line 73 of file bmsparsevec_compr.h.

◆ const_reference

template<class Val, class SV>

typedef const value_type& bm::rsc_sparse_vector< Val, SV >::const_reference

Definition at line 68 of file bmsparsevec_compr.h.

◆ remap_matrix_type

template<class Val, class SV>

typedef bm::heap_matrix<unsigned char, 1, 1, typename bvector_type::allocator_type> bm::rsc_sparse_vector< Val, SV >::remap_matrix_type

protected

unused remap matrix type for compatibility with the sparse serializer

Definition at line 938 of file bmsparsevec_compr.h.

◆ rs_index_type

template<class Val, class SV>

typedef bvector_type::rs_index_type bm::rsc_sparse_vector< Val, SV >::rs_index_type

Definition at line 77 of file bmsparsevec_compr.h.

◆ size_type

template<class Val, class SV>

typedef SV::size_type bm::rsc_sparse_vector< Val, SV >::size_type

Definition at line 69 of file bmsparsevec_compr.h.

◆ sparse_vector_const_iterator

template<class Val, class SV>

typedef SV::const_iterator bm::rsc_sparse_vector< Val, SV >::sparse_vector_const_iterator

Definition at line 71 of file bmsparsevec_compr.h.

◆ sparse_vector_type

template<class Val, class SV>

typedef SV bm::rsc_sparse_vector< Val, SV >::sparse_vector_type

Definition at line 70 of file bmsparsevec_compr.h.

◆ unsigned_value_type

template<class Val, class SV>

typedef SV::unsigned_value_type bm::rsc_sparse_vector< Val, SV >::unsigned_value_type

Definition at line 80 of file bmsparsevec_compr.h.

◆ value_type

template<class Val, class SV>

typedef Val bm::rsc_sparse_vector< Val, SV >::value_type

Definition at line 67 of file bmsparsevec_compr.h.

Member Enumeration Documentation

◆ bit_slices

template<class Val, class SV>

enum bm::rsc_sparse_vector::bit_slices

Enumerator
sv_slices
sv_value_slices

Definition at line 61 of file bmsparsevec_compr.h.

◆ octet_slices

template<class Val, class SV>

enum bm::rsc_sparse_vector::octet_slices

protected

Enumerator
sv_octet_slices

Definition at line 912 of file bmsparsevec_compr.h.

◆ vector_capacity

template<class Val, class SV>

enum bm::rsc_sparse_vector::vector_capacity

Enumerator
max_vector_size

Definition at line 82 of file bmsparsevec_compr.h.

Constructor & Destructor Documentation

◆ rsc_sparse_vector() [1/4]

template<class Val, class SV>

bm::rsc_sparse_vector< Val, SV >::rsc_sparse_vector	(	bm::null_support	null_able = bm::use_null,
		allocation_policy_type	ap = allocation_policy_type(),
		size_type	bv_max_size = bm::id_max,
		const allocator_type &	alloc = allocator_type() )

Definition at line 990 of file bmsparsevec_compr.h.

References BM_ASSERT, sv_value_slices, and bm::use_null.

Referenced by copy_range(), equal(), merge_not_null(), bm::rsc_sparse_vector< Val, SV >::reference::reference(), rsc_sparse_vector(), and rsc_sparse_vector().

◆ rsc_sparse_vector() [2/4]

template<class Val, class SV>

bm::rsc_sparse_vector< Val, SV >::rsc_sparse_vector ( const bvector_type & bv_null )

Contructor to pre-initialize the list of assigned (not NULL) elements.

If the list of not NULL elements is known upfront it can help to pre-declare it, enable rank-select index and then use set function. This scenario gives significant speed boost, comparing random assignment

Parameters

bv_null - not NULL vector for the container

Definition at line 1006 of file bmsparsevec_compr.h.

References BM_ASSERT, and bm::use_null.

◆ ~rsc_sparse_vector()

template<class Val, class SV>

bm::rsc_sparse_vector< Val, SV >::~rsc_sparse_vector ( )

Definition at line 1031 of file bmsparsevec_compr.h.

◆ rsc_sparse_vector() [3/4]

template<class Val, class SV>

bm::rsc_sparse_vector< Val, SV >::rsc_sparse_vector ( const rsc_sparse_vector< Val, SV > & csv )

copy-ctor

Definition at line 1039 of file bmsparsevec_compr.h.

References BM_ASSERT, rsc_sparse_vector(), and sv_value_slices.

◆ rsc_sparse_vector() [4/4]

template<class Val, class SV>

bm::rsc_sparse_vector< Val, SV >::rsc_sparse_vector ( rsc_sparse_vector< Val, SV > && csv )

move-ctor

Definition at line 1053 of file bmsparsevec_compr.h.

References BMNOEXCEPT, rsc_sparse_vector(), and bm::use_null.

Member Function Documentation

◆ at()

template<class Val, class SV>

rsc_sparse_vector< Val, SV >::value_type bm::rsc_sparse_vector< Val, SV >::at ( size_type idx ) const

access specified element with bounds checking

Parameters

idx	- element index

Returns: value of the element

Definition at line 1561 of file bmsparsevec_compr.h.

References resolve(), and size().

◆ begin()

template<class Val, class SV>

const_iterator bm::rsc_sparse_vector< Val, SV >::begin ( ) const

inline

Provide const iterator access to container content.

Definition at line 697 of file bmsparsevec_compr.h.

◆ calc_stat()

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::calc_stat ( struct rsc_sparse_vector< Val, SV >::statistics * st ) const

Calculates memory statistics.

Function fills statistics structure containing information about how this vector uses memory and estimation of max. amount of memory bvector needs to serialize itself.

Parameters

st	- pointer on statistics structure to be filled in.

See also: statistics

Definition at line 1672 of file bmsparsevec_compr.h.

References BM_ASSERT, and BMNOEXCEPT.

Referenced by main().

◆ clear() [1/2]

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::clear ( )

inline

resize to zero, free memory

Parameters

free_mem - free bit vector slices if true

Definition at line 740 of file bmsparsevec_compr.h.

◆ clear() [2/2]

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::clear ( const bvector_type & bv_idx )

Set vector elements spcified by argument bit-vector to zero Note that set to 0 elements are NOT going to tuned to NULL (NULL qualifier is preserved).

Parameters

bv_idx - index bit-vector for elements which to be set to 0

Definition at line 1223 of file bmsparsevec_compr.h.

References bm::rank_compressor< BV >::compress().

◆ clear_all()

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::clear_all	(	bool	free_mem,
		unsigned	)

resize to zero, free memory

Parameters

free_mem - free bit vector slices if true

Definition at line 1663 of file bmsparsevec_compr.h.

References BMNOEXCEPT.

Referenced by bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::clear(), and bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::operator=().

◆ copy_range()

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::copy_range	(	const rsc_sparse_vector< Val, SV > &	csv,
		size_type	left,
		size_type	right )

copy range of values from another sparse vector

Copy [left..right] values from the source vector, clear everything outside the range.

Parameters

csv	- source vector
left	- index from in losed diapason of [left..right]
right	- index to in losed diapason of [left..right]

Definition at line 1932 of file bmsparsevec_compr.h.

References bm::no_null, resolve_range(), rsc_sparse_vector(), size(), and bm::xor_swap().

◆ count_range_notnull()

template<class Val, class SV>

rsc_sparse_vector< Val, SV >::size_type bm::rsc_sparse_vector< Val, SV >::count_range_notnull	(	size_type	left,
		size_type	right ) const

Definition at line 1976 of file bmsparsevec_compr.h.

References BMNOEXCEPT, bm::rs3_border0, and bm::xor_swap().

◆ decode()

template<class Val, class SV>

rsc_sparse_vector< Val, SV >::size_type bm::rsc_sparse_vector< Val, SV >::decode	(	value_type *	arr,
		size_type	idx_from,
		size_type	size,
		bool	zero_mem = true ) const

C-style decode.

Parameters

arr	- decode target array (must be properly sized)
idx_from	- start address to decode
size	- number of elements to decode
zero_mem	- flag if array needs to beset to zeros first

Returns: actual decoded size

See also: decode_buf

Definition at line 1729 of file bmsparsevec_compr.h.

References bm::bvector< Alloc >::enumerator::advance(), BM_ASSERT, bm::id_max, size(), and bm::bvector< Alloc >::iterator_base::valid().

◆ decode_buf()

template<class Val, class SV>

rsc_sparse_vector< Val, SV >::size_type bm::rsc_sparse_vector< Val, SV >::decode_buf	(	value_type *	arr,
		value_type *	arr_buf_tmp,
		size_type	idx_from,
		size_type	size,
		bool	zero_mem = true ) const

C-style decode (variant with external memory) Analog of decode, but requires two arrays.

Faster than decode in many cases.

Parameters

arr	- decode target array (must be properly sized)
arr_buf_tmp	- decode temp bufer (must be same size of arr)
idx_from	- start address to decode
size	- number of elements to decode
zero_mem	- flag if array needs to beset to zeros first

Returns: actual decoded size

See also: decode

Definition at line 1789 of file bmsparsevec_compr.h.

References bm::bvector< Alloc >::enumerator::advance(), BM_ASSERT, BMNOEXCEPT, bm::id_max, size(), bm::bvector< Alloc >::iterator_base::valid(), and bm::bvector< Alloc >::enumerator::value().

◆ effective_size()

template<class Val, class SV>

size_type bm::rsc_sparse_vector< Val, SV >::effective_size ( ) const

inline

size of internal dense vector

Definition at line 868 of file bmsparsevec_compr.h.

◆ effective_slices()

template<class Val, class SV>

unsigned bm::rsc_sparse_vector< Val, SV >::effective_slices ( ) const

inline

Number of effective bit-slices in the value type

Definition at line 847 of file bmsparsevec_compr.h.

◆ effective_vector_max()

template<class Val, class SV>

size_type bm::rsc_sparse_vector< Val, SV >::effective_vector_max ( ) const

inline

Always 1 (non-matrix type).

Definition at line 873 of file bmsparsevec_compr.h.

◆ empty()

template<class Val, class SV>

bool bm::rsc_sparse_vector< Val, SV >::empty ( ) const

inline

return true if vector is empty

Returns: true if empty

Definition at line 379 of file bmsparsevec_compr.h.

Referenced by main(), and run_benchmark().

◆ end()

template<class Val, class SV>

const_iterator bm::rsc_sparse_vector< Val, SV >::end ( ) const

inline

Provide const iterator access to the end.

Definition at line 705 of file bmsparsevec_compr.h.

◆ equal()

template<class Val, class SV>

bool bm::rsc_sparse_vector< Val, SV >::equal ( const rsc_sparse_vector< Val, SV > & csv ) const

check if another vector has the same content

Returns: true, if it is the same

Definition at line 1355 of file bmsparsevec_compr.h.

References BMNOEXCEPT, and rsc_sparse_vector().

Referenced by main(), and main().

◆ find_rank()

template<class Val, class SV>

bool bm::rsc_sparse_vector< Val, SV >::find_rank	(	size_type	rank,
		size_type &	idx ) const

find position of compressed element by its rank

Parameters

rank	- rank (virtual index in sparse vector)
idx	- index (true position)

Definition at line 1699 of file bmsparsevec_compr.h.

References BM_ASSERT, BMNOEXCEPT, get_null_bvector(), and in_sync().

◆ freeze()

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::freeze ( )

inline

Turn sparse vector into immutable mode Read-only (immutable) vector uses less memory and allows faster searches.

Before freezing it is recommenede to call optimize() to get full memory saving effect

See also: optimize

Definition at line 762 of file bmsparsevec_compr.h.

◆ gather()

template<class Val, class SV>

rsc_sparse_vector< Val, SV >::size_type bm::rsc_sparse_vector< Val, SV >::gather	(	value_type *	arr,
		const size_type *	idx,
		size_type *	idx_tmp_buf,
		size_type	size,
		bm::sort_order	sorted_idx ) const

Gather elements to a C-style array.

Gather collects values from different locations, for best performance feed it with sorted list of indexes.

Faster than one-by-one random access.

For efficiency, this is left as a low level function, it does not do any bounds checking on the target array, it will override memory and crash if you are not careful with allocation and request size.

Parameters

arr	- destination array
idx	- index list to gather elements (read only)
idx_tmp_buf	- temp scratch buffer for index rank-select index translation must be correctly allocated to match size. No value initialization requirement.
size	- decoding index list size (array allocation should match)
sorted_idx	- sort order directive for the idx array (BM_UNSORTED, BM_SORTED, BM_UNKNOWN) Sort order affects both performance and correctness(!), use BM_UNKNOWN if not sure.

Returns: number of actually exported elements (can be less than requested)

See also: decode

Definition at line 1847 of file bmsparsevec_compr.h.

References BM_ASSERT, bm::BM_SORTED, bm::BM_UNKNOWN, get(), bm::id_max, resolve(), and size().

Referenced by main().

◆ get()

template<class Val, class SV>

rsc_sparse_vector< Val, SV >::value_type bm::rsc_sparse_vector< Val, SV >::get ( size_type idx ) const

get specified element without bounds checking

Parameters

idx	- element index

Returns: value of the element

Definition at line 1579 of file bmsparsevec_compr.h.

References BM_ASSERT, BMNOEXCEPT, is_null(), and resolve().

Referenced by compute_frequent_kmers(), compute_kmer_histogram(), gather(), main(), bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::operator[](), print_model(), raw_data_size(), and test_data().

◆ get_back_inserter()

template<class Val, class SV>

back_insert_iterator bm::rsc_sparse_vector< Val, SV >::get_back_inserter ( )

inline

Definition at line 714 of file bmsparsevec_compr.h.

Referenced by bm::rsc_sparse_vector< Val, SV >::back_insert_iterator::back_insert_iterator(), generate_test_data(), and main().

◆ get_bmatrix() [1/2]

template<class Val, class SV>

bmatrix_type & bm::rsc_sparse_vector< Val, SV >::get_bmatrix ( )

inline

get read-only access to inetrnal bit-matrix

Definition at line 884 of file bmsparsevec_compr.h.

◆ get_bmatrix() [2/2]

template<class Val, class SV>

const bmatrix_type & bm::rsc_sparse_vector< Val, SV >::get_bmatrix ( ) const

inline

get read-only access to inetrnal bit-matrix

Definition at line 878 of file bmsparsevec_compr.h.

Referenced by deserialize_df2().

◆ get_const_iterator()

template<class Val, class SV>

const_iterator bm::rsc_sparse_vector< Val, SV >::get_const_iterator ( size_type idx ) const

inline

Get const_itertor re-positioned to specific element.

Parameters

idx	- position in the sparse vector

Definition at line 711 of file bmsparsevec_compr.h.

Referenced by main().

◆ get_create_slice()

template<class Val, class SV>

bvector_type_ptr bm::rsc_sparse_vector< Val, SV >::get_create_slice ( unsigned i )

inline

Definition at line 838 of file bmsparsevec_compr.h.

◆ get_null_bvector()

template<class Val, class SV>

const rsc_sparse_vector< Val, SV >::bvector_type * bm::rsc_sparse_vector< Val, SV >::get_null_bvector ( ) const

Get bit-vector of assigned values (or NULL).

Definition at line 1690 of file bmsparsevec_compr.h.

References BMNOEXCEPT.

Referenced by access_bench2(), access_bench3(), compute_adaptive_rsc_histogram(), compute_frequent_kmers(), compute_historgam(), compute_kmer_histogram(), compute_rsc_historgam(), find_rank(), load_to(), main(), and verify_histograms().

◆ get_remap_buffer()

template<class Val, class SV>

const unsigned char * bm::rsc_sparse_vector< Val, SV >::get_remap_buffer ( ) const

inlineprotected

Definition at line 931 of file bmsparsevec_compr.h.

◆ get_remap_matrix() [1/2]

template<class Val, class SV>

remap_matrix_type * bm::rsc_sparse_vector< Val, SV >::get_remap_matrix ( )

inlineprotected

Definition at line 941 of file bmsparsevec_compr.h.

◆ get_remap_matrix() [2/2]

template<class Val, class SV>

const remap_matrix_type * bm::rsc_sparse_vector< Val, SV >::get_remap_matrix ( ) const

inlineprotected

Definition at line 940 of file bmsparsevec_compr.h.

◆ get_RS()

template<class Val, class SV>

const rs_index_type * bm::rsc_sparse_vector< Val, SV >::get_RS ( ) const

inline

Get Rank-Select index pointer

Returns: NULL if sync() was not called to construct the index

See also: sync()

Definition at line 892 of file bmsparsevec_compr.h.

◆ get_slice()

template<class Val, class SV>

bvector_type_const_ptr bm::rsc_sparse_vector< Val, SV >::get_slice ( unsigned i ) const

inline

get access to bit-plane, function checks and creates a plane

Returns: bit-vector for the bit slice

Definition at line 835 of file bmsparsevec_compr.h.

◆ get_sv()

template<class Val, class SV>

const sparse_vector_type & bm::rsc_sparse_vector< Val, SV >::get_sv ( ) const

inline

access dense vector

Definition at line 863 of file bmsparsevec_compr.h.

◆ get_unsigned_bits()

template<class Val, class SV>

rsc_sparse_vector< Val, SV >::unsigned_value_type bm::rsc_sparse_vector< Val, SV >::get_unsigned_bits	(	size_type	idx,
		size_type	N_bits ) const

Get raw unsigned value first N bits.

Parameters

idx	- element index in the vector
N_bits	- number of bits to be extracted (should be > 0)

Returns: unsigned value for

Definition at line 1593 of file bmsparsevec_compr.h.

References BM_ASSERT, BMNOEXCEPT, is_null(), and resolve().

◆ in_sync()

template<class Val, class SV>

bool bm::rsc_sparse_vector< Val, SV >::in_sync ( ) const

inline

returns true if prefix sum table is in sync with the vector

Definition at line 815 of file bmsparsevec_compr.h.

Referenced by find_rank(), and main().

◆ inc() [1/2]

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::inc ( size_type idx )

increment specified element by one

Parameters

idx	- element index

Definition at line 1240 of file bmsparsevec_compr.h.

References BM_ASSERT.

Referenced by main().

◆ inc() [2/2]

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::inc	(	size_type	idx,
		value_type	v )

increment specified element by one

Parameters

idx	- element index
v	- increment value

Definition at line 1272 of file bmsparsevec_compr.h.

References BM_ASSERT.

◆ inc_not_null()

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::inc_not_null	(	size_type	idx,
		value_type	v )

increment specified element by one, element MUST be NOT NULL Faster than just inc() if element is NULL - behavior is undefined

Parameters

idx	- element index
v	- increment value

See also: inc

Definition at line 1304 of file bmsparsevec_compr.h.

References BM_ASSERT.

◆ init_remap_buffer()

template<class Val, class SV>

unsigned char * bm::rsc_sparse_vector< Val, SV >::init_remap_buffer ( )

inlineprotected

Definition at line 932 of file bmsparsevec_compr.h.

◆ is_compressed()

template<class Val, class SV>

constexpr bool bm::rsc_sparse_vector< Val, SV >::is_compressed ( )

inlinestaticconstexpr

various type traits

Definition at line 655 of file bmsparsevec_compr.h.

◆ is_null()

template<class Val, class SV>

bool bm::rsc_sparse_vector< Val, SV >::is_null ( size_type idx ) const

test if specified element is NULL

Parameters

idx	- element index

Returns: true if it is NULL false if it was assigned or container is not configured to support assignment flags

Definition at line 1634 of file bmsparsevec_compr.h.

References BM_ASSERT, and BMNOEXCEPT.

Referenced by get(), get_unsigned_bits(), and set_feature_strand().

◆ is_nullable()

template<class Val, class SV>

bool bm::rsc_sparse_vector< Val, SV >::is_nullable ( ) const

inline

if container supports NULL(unassigned) values (true)

Definition at line 650 of file bmsparsevec_compr.h.

◆ is_remap()

template<class Val, class SV>

bool bm::rsc_sparse_vector< Val, SV >::is_remap ( ) const

inlineconstexprprotected

Definition at line 929 of file bmsparsevec_compr.h.

◆ is_ro()

template<class Val, class SV>

bool bm::rsc_sparse_vector< Val, SV >::is_ro ( ) const

inline

Returns true if vector is read-only.

Definition at line 765 of file bmsparsevec_compr.h.

◆ is_str()

template<class Val, class SV>

constexpr bool bm::rsc_sparse_vector< Val, SV >::is_str ( )

inlinestaticconstexpr

Definition at line 658 of file bmsparsevec_compr.h.

◆ is_sync()

template<class Val, class SV>

bool bm::rsc_sparse_vector< Val, SV >::is_sync ( ) const

inline

returns true if prefix sum table is in sync with the vector

Definition at line 819 of file bmsparsevec_compr.h.

Referenced by optimize().

◆ load_from()

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::load_from ( const sparse_vector_type & sv_src )

Load compressed vector from a sparse vector (with NULLs).

Parameters

sv_src - source sparse vector

Definition at line 1369 of file bmsparsevec_compr.h.

References BM_ASSERT, bm::rank_compressor< BV >::compress(), and sync().

Referenced by compute_rsc_historgam(), main(), main(), and write_as_rsc_svector().

◆ load_to()

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::load_to ( sparse_vector_type & sv ) const

Exort compressed vector to a sparse vector (with NULLs).

Parameters

sv	- target sparse vector

Definition at line 1410 of file bmsparsevec_compr.h.

References BM_ASSERT, bm::rank_compressor< BV >::decompress(), get_null_bvector(), and size().

Referenced by main(), and main().

◆ mark_null_idx()

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::mark_null_idx ( unsigned null_idx )

inline

Definition at line 895 of file bmsparsevec_compr.h.

◆ merge_not_null()

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::merge_not_null ( rsc_sparse_vector< Val, SV > & csv )

merge two vectors (argument gets destroyed) It is important that both vectors have the same NULL vectors

Parameters

csv	- [in,out] argumnet vector to merge (works like move so arg should not be used after the merge)

Definition at line 1964 of file bmsparsevec_compr.h.

References BM_ASSERT, and rsc_sparse_vector().

◆ operator=() [1/2]

template<class Val, class SV>

rsc_sparse_vector< Val, SV > & bm::rsc_sparse_vector< Val, SV >::operator= ( const rsc_sparse_vector< Val, SV > & csv )

inline

copy assignmment operator

Definition at line 332 of file bmsparsevec_compr.h.

◆ operator=() [2/2]

template<class Val, class SV>

rsc_sparse_vector< Val, SV > & bm::rsc_sparse_vector< Val, SV >::operator= ( rsc_sparse_vector< Val, SV > && csv )

inline

move assignmment operator

Definition at line 352 of file bmsparsevec_compr.h.

◆ operator[]()

template<class Val, class SV>

value_type bm::rsc_sparse_vector< Val, SV >::operator[] ( size_type idx ) const

inline

get specified element without bounds checking

Parameters

idx	- element index

Returns: value of the element

Definition at line 416 of file bmsparsevec_compr.h.

◆ optimize()

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::optimize	(	bm::word_t *	temp_block = 0,
		typename bvector_type::optmode	opt_mode = bvector_type::opt_compress,
		statistics *	stat = 0 )

run memory optimization for all vector slices

Parameters

temp_block	- pre-allocated memory block to avoid unnecessary re-allocs
opt_mode	- requested compression depth
stat	- memory allocation statistics after optimization

Definition at line 1644 of file bmsparsevec_compr.h.

References is_sync(), bm::bv_statistics::memory_used, and sync().

Referenced by compute_adaptive_rsc_histogram(), compute_rsc_historgam(), generate_test_data(), main(), main(), and write_as_rsc_svector().

◆ push_back() [1/2]

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::push_back	(	size_type	idx,
		value_type	v )

set specified element with bounds checking and automatic resize

Method cannot insert elements, so every new idx has to be greater or equal than what it used before. Elements must be loaded in a sorted order.

Parameters

idx	- element index
v	- element value

Definition at line 1126 of file bmsparsevec_compr.h.

References push_back_no_check().

Referenced by compute_adaptive_rsc_histogram(), and bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::push_back().

◆ push_back() [2/2]

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::push_back ( value_type v )

inline

add element with automatic resize

Parameters

v	- element value

Definition at line 477 of file bmsparsevec_compr.h.

◆ push_back_no_check()

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::push_back_no_check	(	size_type	idx,
		value_type	v )

protected

Definition at line 1151 of file bmsparsevec_compr.h.

References BM_ASSERT.

Referenced by push_back().

◆ push_back_null() [1/2]

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::push_back_null ( )

inline

push back NULL value

Definition at line 489 of file bmsparsevec_compr.h.

Referenced by bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::push_back_null().

◆ push_back_null() [2/2]

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::push_back_null ( size_type count )

push back specified amount of NULL values

Parameters

count - number of NULLs to push back

Definition at line 1141 of file bmsparsevec_compr.h.

References BM_ASSERT, and bm::id_max.

◆ remap_size()

template<class Val, class SV>

size_t bm::rsc_sparse_vector< Val, SV >::remap_size ( ) const

inlineprotected

Definition at line 930 of file bmsparsevec_compr.h.

◆ resize()

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::resize ( size_type new_size )

change vector size

Parameters

new_size - new vector size

Definition at line 1079 of file bmsparsevec_compr.h.

References BM_ASSERT, and bm::id_max.

◆ resize_internal()

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::resize_internal ( size_type sz )

inlineprotected

Definition at line 923 of file bmsparsevec_compr.h.

◆ resolve()

template<class Val, class SV>

bool bm::rsc_sparse_vector< Val, SV >::resolve	(	size_type	idx,
		size_type *	idx_to ) const

Resolve logical address to access via rank compressed address.

Parameters

idx	- input id to resolve
idx_to	- output id

Returns: true if id is known and resolved successfully

Definition at line 1481 of file bmsparsevec_compr.h.

References BM_ASSERT, BMNOEXCEPT, and resolve_sync().

Referenced by at(), gather(), get(), get_unsigned_bits(), and try_get().

◆ resolve_range()

template<class Val, class SV>

bool bm::rsc_sparse_vector< Val, SV >::resolve_range	(	size_type	from,
		size_type	to,
		size_type *	idx_from,
		size_type *	idx_to ) const

protected

Definition at line 1529 of file bmsparsevec_compr.h.

References BM_ASSERT, and BMNOEXCEPT.

Referenced by copy_range().

◆ resolve_sync()

template<class Val, class SV>

bool bm::rsc_sparse_vector< Val, SV >::resolve_sync	(	size_type	idx,
		size_type *	idx_to ) const

protected

Definition at line 1505 of file bmsparsevec_compr.h.

References BM_ASSERT, BMNOEXCEPT, and bm::id_max.

Referenced by resolve(), and try_get_sync().

◆ s2u()

template<class Val, class SV>

unsigned_value_type bm::rsc_sparse_vector< Val, SV >::s2u ( value_type v )

inlinestaticprotected

Convert signed value type to unsigned representation.

Definition at line 949 of file bmsparsevec_compr.h.

◆ set()

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::set	(	size_type	idx,
		value_type	v )

set specified element with bounds checking and automatic resize

Parameters

idx	- element index
v	- element value

Definition at line 1323 of file bmsparsevec_compr.h.

References BM_ASSERT.

Referenced by count_kmers(), fill_test_data(), main(), and set_feature_strand().

◆ set_null() [1/2]

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::set_null ( const bvector_type & bv_idx )

Set NULL all elements set as 1 in the argument vector.

Function also clears all the values to 0. Note: this can be a very expensive function for an RS container.

Parameters

bv_idx - index bit-vector for elements which to be set to NULL

Definition at line 1194 of file bmsparsevec_compr.h.

References bm::rank_compressor< BV >::compress(), and bm::bvector< Alloc >::iterator_base::valid().

◆ set_null() [2/2]

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::set_null ( size_type idx )

set specified element to NULL RSC vector actually erases element when it is set to NULL (expensive).

Parameters

idx	- element index

Definition at line 1167 of file bmsparsevec_compr.h.

References BM_ASSERT.

◆ set_remap()

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::set_remap ( )

inlineprotected

Definition at line 933 of file bmsparsevec_compr.h.

◆ size()

template<class Val, class SV>

rsc_sparse_vector< Val, SV >::size_type bm::rsc_sparse_vector< Val, SV >::size ( ) const

return size of the vector

Returns: size of sparse vector

Definition at line 1071 of file bmsparsevec_compr.h.

References BMNOEXCEPT.

Referenced by at(), compute_historgam(), compute_rsc_historgam(), copy_range(), decode(), decode_buf(), gather(), load_to(), main(), and raw_data_size().

◆ size_internal()

template<class Val, class SV>

size_type bm::rsc_sparse_vector< Val, SV >::size_internal ( ) const

inlineprotected

Definition at line 927 of file bmsparsevec_compr.h.

◆ slice()

template<class Val, class SV>

bvector_type_ptr bm::rsc_sparse_vector< Val, SV >::slice ( unsigned i )

inline

Definition at line 841 of file bmsparsevec_compr.h.

◆ slices()

template<class Val, class SV>

unsigned bm::rsc_sparse_vector< Val, SV >::slices ( )

inlinestatic

get total number of bit-slices in the vector

Definition at line 853 of file bmsparsevec_compr.h.

◆ stored_slices()

template<class Val, class SV>

unsigned bm::rsc_sparse_vector< Val, SV >::stored_slices ( )

inlinestatic

Number of stored bit-slices (value slices + extra.

Definition at line 857 of file bmsparsevec_compr.h.

◆ sync() [1/2]

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::sync ( )

inline

Re-calculate prefix sum table used for rank search (if necessary).

Definition at line 810 of file bmsparsevec_compr.h.

Referenced by bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::sync().

◆ sync() [2/2]

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::sync ( bool force )

Re-calculate rank-select index for faster access to vector.

Parameters

force - force recalculation even if it is already recalculated

Definition at line 1442 of file bmsparsevec_compr.h.

References BM_ASSERT, and sync_size().

Referenced by compute_adaptive_rsc_histogram(), compute_rsc_historgam(), fill_test_data(), generate_test_data(), load_from(), main(), main(), SortCounting_JobFunctor< BV >::operator()(), optimize(), and sync_size().

◆ sync_size()

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::sync_size ( )

recalculate size to exclude tail NULL elements After this call size() will return the true size of the vector

Definition at line 1465 of file bmsparsevec_compr.h.

References BM_ASSERT, BMNOEXCEPT, and sync().

Referenced by sync().

◆ try_get()

template<class Val, class SV>

bool bm::rsc_sparse_vector< Val, SV >::try_get	(	size_type	idx,
		value_type &	v ) const

get specified element with NOT NULL check

Parameters

idx	- element index
v	- [out] value to get

Returns: true if value was aquired (NOT NULL), false otherwise

See also: is_null, get

Definition at line 1607 of file bmsparsevec_compr.h.

References BMNOEXCEPT, and resolve().

◆ try_get_sync()

template<class Val, class SV>

bool bm::rsc_sparse_vector< Val, SV >::try_get_sync	(	size_type	idx,
		value_type &	v ) const

get specified element with NOT NULL check Caller guarantees that the vector is in sync mode (RS-index access).

Parameters

idx	- element index
v	- [out] value to get

Returns: true if value was aquired (NOT NULL), false otherwise

See also: is_null, get, sync

Definition at line 1620 of file bmsparsevec_compr.h.

References BMNOEXCEPT, and resolve_sync().

◆ u2s()

template<class Val, class SV>

value_type bm::rsc_sparse_vector< Val, SV >::u2s ( unsigned_value_type v )

inlinestaticprotected

Definition at line 952 of file bmsparsevec_compr.h.

◆ unsync()

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::unsync ( )

inline

Unsync the prefix sum table.

Definition at line 824 of file bmsparsevec_compr.h.

◆ sparse_vector_deserializer

template<class Val, class SV>

template<class SVect>

friend class sparse_vector_deserializer

friend

Definition at line 973 of file bmsparsevec_compr.h.

◆ sparse_vector_scanner

template<class Val, class SV>

template<class SVect, unsigned S_FACTOR>

friend class sparse_vector_scanner

friend

Definition at line 971 of file bmsparsevec_compr.h.

◆ sparse_vector_serializer

template<class Val, class SV>

template<class SVect>

friend class sparse_vector_serializer

friend

Definition at line 972 of file bmsparsevec_compr.h.

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

bmsparsevec_compr.h

Data Structures

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Static Protected Member Functions

Friends

Various traits

Access to internals

Detailed Description

Member Typedef Documentation

◆ allocation_policy_type

◆ allocator_type

◆ bmatrix_type

◆ bvector_enumerator_type

◆ bvector_type

◆ bvector_type_const_ptr

◆ bvector_type_ptr

◆ const_reference

◆ remap_matrix_type

◆ rs_index_type

◆ size_type

◆ sparse_vector_const_iterator

◆ sparse_vector_type

◆ unsigned_value_type

◆ value_type

Member Enumeration Documentation

◆ bit_slices

◆ octet_slices

◆ vector_capacity

Constructor & Destructor Documentation

◆ rsc_sparse_vector() [1/4]

◆ rsc_sparse_vector() [2/4]

◆ ~rsc_sparse_vector()

◆ rsc_sparse_vector() [3/4]

◆ rsc_sparse_vector() [4/4]

Member Function Documentation

◆ at()

◆ begin()

◆ calc_stat()

◆ clear() [1/2]

◆ clear() [2/2]

◆ clear_all()

◆ copy_range()

◆ count_range_notnull()

◆ decode()

◆ decode_buf()

◆ effective_size()

◆ effective_slices()

◆ effective_vector_max()

◆ empty()

◆ end()

◆ equal()

◆ find_rank()

◆ freeze()

◆ gather()

◆ get()

◆ get_back_inserter()

◆ get_bmatrix() [1/2]

◆ get_bmatrix() [2/2]

◆ get_const_iterator()

◆ get_create_slice()

◆ get_null_bvector()

◆ get_remap_buffer()

◆ get_remap_matrix() [1/2]

◆ get_remap_matrix() [2/2]

◆ get_RS()

◆ get_slice()

◆ get_sv()

◆ get_unsigned_bits()

◆ in_sync()

◆ inc() [1/2]

◆ inc() [2/2]

◆ inc_not_null()

◆ init_remap_buffer()

◆ is_compressed()

◆ is_null()

◆ is_nullable()

◆ is_remap()

◆ is_ro()