succinct sparse vector with runtime compression using bit-slicing / transposition method More...

#include <bmsparsevec.h>

Inheritance diagram for bm::sparse_vector< Val, BV >:

[legend]

Collaboration diagram for bm::sparse_vector< Val, BV >:

[legend]

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

Public Types
typedef Val	value_type
typedef BV	bvector_type
typedef bvector_type *	bvector_type_ptr
typedef bvector_type::size_type	size_type
typedef bvector_type::block_idx_type	block_idx_type
typedef const bvector_type *	bvector_type_const_ptr
typedef const value_type &	const_reference
typedef BV::allocator_type	allocator_type
typedef bvector_type::allocation_policy	allocation_policy_type
typedef bvector_type::enumerator	bvector_enumerator_type
typedef allocator_type::allocator_pool_type	allocator_pool_type
typedef bm::basic_bmatrix< BV >	bmatrix_type
typedef base_sparse_vector< Val, BV, 1 >	parent_type
typedef parent_type::unsigned_value_type	unsigned_value_type
Public Types inherited from bm::base_sparse_vector< Val, BV, 1 >
enum	bit_planes
enum	vector_capacity
typedef Val	value_type
typedef BV	bvector_type
typedef BV::size_type	size_type
typedef bvector_type *	bvector_type_ptr
typedef const bvector_type *	bvector_type_const_ptr
typedef const value_type &	const_reference
typedef BV::allocator_type	allocator_type
typedef bvector_type::allocation_policy	allocation_policy_type
typedef bvector_type::enumerator	bvector_enumerator_type
typedef allocator_type::allocator_pool_type	allocator_pool_type
typedef bm::basic_bmatrix< BV >	bmatrix_type
typedef std::make_unsigned< value_type >::type	unsigned_value_type

Public Member Functions
void	swap (sparse_vector< Val, BV > &sv) BMNOEXCEPT
	content exchange
void	set_allocator_pool (allocator_pool_type *pool_ptr) BMNOEXCEPT
	Set allocator pool for local (non-threaded) memory cyclic(lots of alloc-free ops) opertations.
Construction and assignment
	sparse_vector (bm::null_support null_able=bm::no_null, allocation_policy_type ap=allocation_policy_type(), size_type bv_max_size=bm::id_max, const allocator_type &alloc=allocator_type())
	Sparse vector constructor.
	sparse_vector (const sparse_vector< Val, BV > &sv)
sparse_vector< Val, BV > &	operator= (const sparse_vector< Val, BV > &sv)
	sparse_vector (sparse_vector< Val, BV > &&sv) BMNOEXCEPT
sparse_vector< Val, BV > &	operator= (sparse_vector< Val, BV > &&sv) BMNOEXCEPT
	~sparse_vector () BMNOEXCEPT
Element access, editing
reference	operator[] (size_type idx) BMNOEXCEPT
	Operator to get write access to an element.
value_type	operator[] (size_type idx) const BMNOEXCEPT
	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
value_type	get_no_check (size_type idx) const BMNOEXCEPT
	get specified element without checking boundary conditions
bool	try_get (size_type idx, value_type &v) const BMNOEXCEPT
	get specified element with NOT NULL check
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	push_back (value_type v)
	push value back into vector
void	push_back_null (size_type count)
	push back specified amount of NULL values
void	push_back_null ()
	push back NULL value
void	insert (size_type idx, value_type v)
	insert specified element into container
void	erase (size_type idx, bool erase_null=true)
	erase specified element from container
void	swap (size_type idx1, size_type idx2)
	swap two vector elements between each other
void	clear (size_type idx, bool set_null)
	clear specified element with bounds checking and automatic resize
void	set_null (size_type idx)
	set specified element to unassigned value (NULL)
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).
unsigned_value_type	get_unsigned_bits (size_type idx, size_type N_bits) const BMNOEXCEPT
	Get raw unsigned value first N bits.
Iterator access
const_iterator	begin () const BMNOEXCEPT
	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 ()
	Provide back insert iterator Back insert iterator implements buffered insertion, which is faster, than random access or push_back.
Loading of sparse vector from C-style array
void	import (const value_type *arr, size_type arr_size, size_type offset=0, bool set_not_null=true)
	Import list of elements from a C-style array.
void	import_back (const value_type *arr, size_type arr_size, bool set_not_null=true)
	Import list of elements from a C-style array (pushed back).
Export content to C-style array
size_type	decode (value_type *arr, size_type idx_from, size_type dec_size, bool zero_mem=true) const
	Bulk export list of elements to a C-style array.
size_type	gather (value_type arr, const size_type idx, size_type size, bm::sort_order sorted_idx) const
	Gather elements to a C-style array.
Clear
void	clear_all (bool free_mem, unsigned) BMNOEXCEPT
	resize to zero, free memory
void	clear () BMNOEXCEPT
	resize to zero, free memory
sparse_vector< Val, BV > &	clear_range (size_type left, size_type right, bool set_null=false)
	clear range (assign bit 0 for all planes)
Size, etc
size_type	size () const BMNOEXCEPT
	return size of the vector
bool	empty () const BMNOEXCEPT
	return true if vector is empty
void	resize (size_type sz)
	resize vector
void	sync_size () BMNOEXCEPT
	recalculate size to exclude tail NULL elements After this call size() will return the true size of the vector
Comparison
bool	equal (const sparse_vector< Val, BV > &sv, bm::null_support null_able=bm::use_null) const BMNOEXCEPT
	check if another sparse vector has the same content and size
Element comparison
int	compare (size_type idx, const value_type val) const BMNOEXCEPT
	Compare vector element with argument.
Memory optimization
void	optimize (bm::word_t temp_block=0, typename bvector_type::optmode opt_mode=bvector_type::opt_compress, typename sparse_vector< Val, BV >::statistics stat=0)
	run memory optimization for all vector planes
void	optimize_gap_size ()
	Optimize sizes of GAP blocks.
void	calc_stat (struct sparse_vector< Val, BV >::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
sparse_vector< Val, BV > &	join (const sparse_vector< Val, BV > &sv)
	join all with another sparse vector using OR operation
sparse_vector< Val, BV > &	merge (sparse_vector< Val, BV > &sv)
	merge with another sparse vector using OR operation Merge is different from join(), because it borrows data from the source vector, so it gets modified.
void	copy_range (const sparse_vector< Val, BV > &sv, size_type left, size_type right, bm::null_support slice_null=bm::use_null)
	copy range of values from another sparse vector
void	keep_range (size_type left, size_type right, bm::null_support slice_null=bm::use_null)
	Keep only specified interval in the sparse vector, clear all other elements.
void	filter (const bvector_type &bv_mask)
	Apply value filter, defined by mask vector.
Public Member Functions inherited from bm::base_sparse_vector< Val, BV, 1 >
	base_sparse_vector ()
	base_sparse_vector (bm::null_support null_able, bool is_dynamic, allocation_policy_type ap=allocation_policy_type(), size_type bv_max_size=bm::id_max, const allocator_type &alloc=allocator_type())
	base_sparse_vector (const base_sparse_vector< Val, BV, MAX_SIZE > &bsv)
	base_sparse_vector (base_sparse_vector< Val, BV, MAX_SIZE > &&bsv) BMNOEXCEPT
void	swap (base_sparse_vector< Val, BV, MAX_SIZE > &bsv) BMNOEXCEPT
size_type	size () const BMNOEXCEPT
void	resize (size_type new_size, bool set_null)
void	clear_range (size_type left, size_type right, bool set_null)
void	keep_range_no_check (size_type left, size_type right, bm::null_support slice_null)
void	clear_all (bool free_mem=true) BMNOEXCEPT
	resize to zero, free memory
bool	empty () const BMNOEXCEPT
void	swap_elements (size_type idx1, size_type idx2)
	swap two vector elements
void	optimize (bm::word_t temp_block=0, typename bvector_type::optmode opt_mode=bvector_type::opt_compress, typename bvector_type::statistics stat=0)
	run memory optimization for all bit-vector rows
void	calc_stat (typename bvector_type::statistics *st) const BMNOEXCEPT
	Calculates memory statistics.
bool	equal (const base_sparse_vector< Val, BV, MAX_SIZE > &sv, bm::null_support null_able=bm::use_null) const BMNOEXCEPT
	check if another sparse vector has the same content and size
bool	is_nullable () const BMNOEXCEPT
	check if container supports NULL(unassigned) values
bm::null_support	get_null_support () const BMNOEXCEPT
	check if container supports NULL (unassigned) values
const bvector_type *	get_null_bvector () const BMNOEXCEPT
	Get bit-vector of assigned values or NULL (if not constructed that way).
bool	is_null (size_type idx) const BMNOEXCEPT
	test if specified element is NULL
void	set_allocator_pool (allocator_pool_type *pool_ptr) BMNOEXCEPT
	Set allocation pool.
allocator_pool_type *	get_allocator_pool () const BMNOEXCEPT
	Get allocation pool.
bvector_type_ptr	get_create_slice (unsigned i)
	get access to bit-plain, function checks and creates a plane
bvector_type_const_ptr	get_slice (unsigned i) const BMNOEXCEPT
	get read-only access to bit-plane
unsigned	effective_slices () const BMNOEXCEPT
	Number of effective bit-planes in the value type.
bvector_type_ptr	slice (unsigned i) BMNOEXCEPT
	get access to bit-plane as is (can return NULL)
bvector_type_const_ptr	slice (unsigned i) const BMNOEXCEPT
bvector_type *	get_null_bvect () BMNOEXCEPT
void	free_slice (unsigned i)
	free memory in bit-plane
bm::id64_t	get_slice_mask (unsigned element_idx) const BMNOEXCEPT
const bmatrix_type &	get_bmatrix () const BMNOEXCEPT
bmatrix_type &	get_bmatrix () BMNOEXCEPT
	access to internal bit-matrix
void	mark_null_idx (unsigned null_idx) BMNOEXCEPT
	Set NULL plain index.

Static Public Member Functions
Various traits
static constexpr bool	is_compressed () BMNOEXCEPT
	various type traits
static constexpr bool	is_str () BMNOEXCEPT
static constexpr bool	is_signed () BMNOEXCEPT
	returns true if value type is signed integral type
static unsigned	slices () BMNOEXCEPT
	get total number of bit-planes in the vector
static unsigned	stored_slices () BMNOEXCEPT
	Number of stored bit-planes (value planes + extra.
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
	Convert unsigned value type to signed representation.

Data Fields
friend	const_iterator
friend	back_insert_iterator

Protected Types
enum	octet_slices { sv_octet_slices = sizeof(value_type) }
enum	buf_size_e { n_buf_size = 1024 * 8 }
typedef bm::heap_matrix< unsigned char, sizeof(value_type), 256, typename bvector_type::allocator_type >	remap_matrix_type
	unused remap matrix type for compatibility with the sparse serializer
Protected Types inherited from bm::base_sparse_vector< Val, BV, 1 >
typedef bvector_type::block_idx_type	block_idx_type

Protected Member Functions
void	set_value (size_type idx, value_type v, bool need_clear)
	set value without checking boundaries
void	set_value_no_null (size_type idx, value_type v, bool need_clear)
	set value without checking boundaries or support of NULL
void	push_back_no_null (value_type v)
	push value back into vector without NULL semantics
void	insert_value (size_type idx, value_type v)
	insert value without checking boundaries
void	insert_value_no_null (size_type idx, value_type v)
	insert value without checking boundaries or support of NULL
void	resize_internal (size_type sz, bool set_null=true)
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 ()
bool	resolve_range (size_type from, size_type to, size_type idx_from, size_type idx_to) const BMNOEXCEPT
void	inc_no_null (size_type idx)
	Increment element by 1 without chnaging NULL vector or size.
void	inc_no_null (size_type idx, value_type v)
	increment by v without chnaging NULL vector or size
void	import_back_u (const unsigned_value_type *arr, size_type arr_size, bool set_not_null=true)
	Import list of elements from a C-style array (pushed back).
void	import_u (const unsigned_value_type *arr, size_type arr_size, size_type offset, bool set_not_null)
	Import list of elements from a C-style array.
void	import_u_nocheck (const unsigned_value_type *arr, size_type arr_size, size_type offset, bool set_not_null)
void	join_null_slice (const sparse_vector< Val, BV > &sv)
unsigned_value_type	get_unsigned (size_type idx) const BMNOEXCEPT
	get raw unsigned value
Protected Member Functions inherited from bm::base_sparse_vector< Val, BV, 1 >
void	copy_from (const base_sparse_vector< Val, BV, MAX_SIZE > &bsv)
void	merge_matr (bmatrix_type &bmatr)
	Merge plane bvectors from an outside base matrix Note: outside base matrix gets destroyed.
void	freeze_matr ()
	Turn on RO mode.
void	clear_value_planes_from (unsigned plane_idx, size_type idx)
void	insert_clear_value_planes_from (unsigned plane_idx, size_type idx)
void	erase_column (size_type idx, bool erase_null)
void	insert_null (size_type idx, bool not_null)
void	bit_sub_rows (const bvector_type &bv, bool use_null)
	Set SUB (MINUS) operation on all existing bit-slices.
void	bit_and_rows (const bvector_type &bv)
	Set AND (intersect) operation on all existing bit-slices.
void	optimize_block (block_idx_type nb, typename BV::optmode opt_mode)
	plane index for the "NOT NULL" flags plane
void	sync_ro () BMNOEXCEPT
	Sybc read-only state.
void	copy_range_slices (const base_sparse_vector< Val, BV, MAX_SIZE > &bsv, typename base_sparse_vector< Val, BV, MAX_SIZE >::size_type left, typename base_sparse_vector< Val, BV, MAX_SIZE >::size_type right, bm::null_support slice_null)
	Perform copy_range() on a set of planes.

Static Protected Member Functions
static void	u2s_translate (value_type *arr, size_type sz) BMNOEXCEPT
Static Protected Member Functions inherited from bm::base_sparse_vector< Val, BV, 1 >
static constexpr unsigned	value_bits () BMNOEXCEPT
	Number of total bit-planes in the value type.

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

Access to internals
void	sync (bool)
	syncronize internal structures, build fast access index
size_type	extract (value_type *arr, size_type size, size_type offset=0, bool zero_mem=true) const BMNOEXCEPT2
	Bulk export list of elements to a C-style array.
size_type	extract_range (value_type *arr, size_type size, size_type offset, bool zero_mem=true) const
	extract small window without use of masking vector
size_type	extract_planes (value_type *arr, size_type size, size_type offset, bool zero_mem=true) const
	extract medium window without use of masking vector
size_type	effective_size () const BMNOEXCEPT
	size of sparse vector (may be different for RSC)
size_type	effective_vector_max () const BMNOEXCEPT
	Always 1 (non-matrix type).
static size_type	translate_address (size_type i) BMNOEXCEPT
	address translation for this type of container
static void	throw_range_error (const char *err_msg)
	throw range error
static void	throw_bad_alloc ()
	throw bad alloc
static bool	find_rank (size_type rank, size_type &pos) BMNOEXCEPT
	find position of compressed element by its rank

Additional Inherited Members
Protected Attributes inherited from bm::base_sparse_vector< Val, BV, 1 >
bmatrix_type	bmatr_
	bit-transposed matrix
unsigned_value_type	slice_mask_
	slice presence bit-mask
size_type	size_
	array size
unsigned	effective_slices_
	number of bit slices actually allocated
bool	is_ro_
	read-only

Detailed Description

template<class Val, class BV>
class bm::sparse_vector< Val, BV >

succinct sparse vector with runtime compression using bit-slicing / transposition method

Sparse vector implements variable bit-depth storage model. Initial data is bit-sliced into bit-vectors (all bits 0 become bv[0] so each element may use less memory than the original native data type. For example, 32-bit integer may only use 20 bits.

Container supports both signed and unsigned integer types.

Another level of compression is provided by bit-vector (BV template parameter) used for storing bit planes. bvector<> implements varians of on the fly block compression, so if a significant area of a sparse vector uses less bits - it will save memory. bm::bvector<> is a sparse data strucrture, so is bm::sparse_vector<>. It should be noted that as succinct data it works for both sparse or dense vectors.

Container also supports notion of NULL (unassigned value) which can be treated differently than 0.

Definition at line 86 of file bmsparsevec.h.

Member Typedef Documentation

◆ allocation_policy_type

template<class Val, class BV>

typedef bvector_type::allocation_policy bm::sparse_vector< Val, BV >::allocation_policy_type

Definition at line 97 of file bmsparsevec.h.

◆ allocator_pool_type

template<class Val, class BV>

typedef allocator_type::allocator_pool_type bm::sparse_vector< Val, BV >::allocator_pool_type

Definition at line 99 of file bmsparsevec.h.

◆ allocator_type

template<class Val, class BV>

typedef BV::allocator_type bm::sparse_vector< Val, BV >::allocator_type

Definition at line 96 of file bmsparsevec.h.

◆ block_idx_type

template<class Val, class BV>

typedef bvector_type::block_idx_type bm::sparse_vector< Val, BV >::block_idx_type

Definition at line 93 of file bmsparsevec.h.

◆ bmatrix_type

template<class Val, class BV>

typedef bm::basic_bmatrix<BV> bm::sparse_vector< Val, BV >::bmatrix_type

Definition at line 100 of file bmsparsevec.h.

◆ bvector_enumerator_type

template<class Val, class BV>

typedef bvector_type::enumerator bm::sparse_vector< Val, BV >::bvector_enumerator_type

Definition at line 98 of file bmsparsevec.h.

◆ bvector_type

template<class Val, class BV>

typedef BV bm::sparse_vector< Val, BV >::bvector_type

Definition at line 90 of file bmsparsevec.h.

◆ bvector_type_const_ptr

template<class Val, class BV>

typedef const bvector_type* bm::sparse_vector< Val, BV >::bvector_type_const_ptr

Definition at line 94 of file bmsparsevec.h.

◆ bvector_type_ptr

template<class Val, class BV>

typedef bvector_type* bm::sparse_vector< Val, BV >::bvector_type_ptr

Definition at line 91 of file bmsparsevec.h.

◆ const_reference

template<class Val, class BV>

typedef const value_type& bm::sparse_vector< Val, BV >::const_reference

Definition at line 95 of file bmsparsevec.h.

◆ parent_type

template<class Val, class BV>

typedef base_sparse_vector<Val, BV, 1> bm::sparse_vector< Val, BV >::parent_type

Definition at line 101 of file bmsparsevec.h.

◆ remap_matrix_type

template<class Val, class BV>

typedef bm::heap_matrix<unsigned char, sizeof(value_type), 256, typename bvector_type::allocator_type> bm::sparse_vector< Val, BV >::remap_matrix_type

protected

unused remap matrix type for compatibility with the sparse serializer

Definition at line 1035 of file bmsparsevec.h.

◆ size_type

template<class Val, class BV>

typedef bvector_type::size_type bm::sparse_vector< Val, BV >::size_type

Definition at line 92 of file bmsparsevec.h.

◆ unsigned_value_type

template<class Val, class BV>

typedef parent_type::unsigned_value_type bm::sparse_vector< Val, BV >::unsigned_value_type

Definition at line 102 of file bmsparsevec.h.

◆ value_type

template<class Val, class BV>

typedef Val bm::sparse_vector< Val, BV >::value_type

Definition at line 89 of file bmsparsevec.h.

Member Enumeration Documentation

◆ buf_size_e

template<class Val, class BV>

enum bm::sparse_vector::buf_size_e

protected

Enumerator
n_buf_size

Definition at line 994 of file bmsparsevec.h.

◆ octet_slices

template<class Val, class BV>

enum bm::sparse_vector::octet_slices

protected

Enumerator
sv_octet_slices

Definition at line 990 of file bmsparsevec.h.

Constructor & Destructor Documentation

◆ sparse_vector() [1/3]

template<class Val, class BV>

bm::sparse_vector< Val, BV >::sparse_vector	(	bm::null_support	null_able = bm::no_null,
		allocation_policy_type	ap = allocation_policy_type(),
		size_type	bv_max_size = bm::id_max,
		const allocator_type &	alloc = allocator_type() )

Sparse vector constructor.

Parameters

null_able	- defines if vector supports NULL values flag by default it is OFF, use bm::use_null to enable it
ap	- allocation strategy for underlying bit-vectors Default allocation policy uses BM_BIT setting (fastest access)
bv_max_size	- maximum possible size of underlying bit-vectors Please note, this is NOT size of svector itself, it is dynamic upper limit which should be used very carefully if we surely know the ultimate size
alloc	- allocator for bit-vectors

See also: bvector<>; bm::bvector<>::allocation_policy; bm::startegy

Definition at line 1100 of file bmsparsevec.h.

Referenced by copy_range(), equal(), join(), join_null_slice(), merge(), bm::sparse_vector< Val, BV >::reference::reference(), sparse_vector(), sparse_vector(), and swap().

◆ sparse_vector() [2/3]

template<class Val, class BV>

bm::sparse_vector< Val, BV >::sparse_vector ( const sparse_vector< Val, BV > & sv )

copy-ctor

Definition at line 1111 of file bmsparsevec.h.

References sparse_vector().

◆ sparse_vector() [3/3]

template<class Val, class BV>

bm::sparse_vector< Val, BV >::sparse_vector ( sparse_vector< Val, BV > && sv )

move-ctor

Definition at line 1119 of file bmsparsevec.h.

References BMNOEXCEPT, sparse_vector(), and bm::base_sparse_vector< Val, BV, 1 >::swap().

◆ ~sparse_vector()

template<class Val, class BV>

bm::sparse_vector< Val, BV >::~sparse_vector ( )

Definition at line 1130 of file bmsparsevec.h.

References BMNOEXCEPT.

Member Function Documentation

◆ at()

template<class Val, class BV>

sparse_vector< Val, BV >::value_type bm::sparse_vector< Val, BV >::at ( size_type idx ) const

access specified element with bounds checking

Parameters

idx	- element index

Returns: value of the element

Examples: svsample03.cpp.

Definition at line 1747 of file bmsparsevec.h.

References get(), bm::base_sparse_vector< Val, BV, 1 >::size_, and throw_range_error().

Referenced by Demo1(), main(), and print_svector().

◆ begin()

template<class Val, class BV>

sparse_vector< Val, BV >::const_iterator bm::sparse_vector< Val, BV >::begin ( ) const

Provide const iterator access to container content.

Definition at line 2310 of file bmsparsevec.h.

References BMNOEXCEPT.

Referenced by build_vector_pairs(), compare_sv_it(), Demo1(), Demo2(), and main().

◆ calc_stat()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::calc_stat ( struct sparse_vector< Val, BV >::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 2132 of file bmsparsevec.h.

References BM_ASSERT, BMNOEXCEPT, and bm::base_sparse_vector< Val, BV, 1 >::calc_stat().

Referenced by main(), and SDemo2().

◆ clear() [1/3]

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::clear ( )

inline

resize to zero, free memory

Definition at line 708 of file bmsparsevec.h.

◆ clear() [2/3]

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::clear ( const bvector_type & bv_idx )

inline

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 554 of file bmsparsevec.h.

◆ clear() [3/3]

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::clear	(	size_type	idx,
		bool	set_null )

clear specified element with bounds checking and automatic resize

Parameters

idx	- element index
set_null	- if true the value receives NULL (unassigned) value

Definition at line 1865 of file bmsparsevec.h.

References bm::base_sparse_vector< Val, BV, 1 >::get_null_bvect(), set_null(), set_value(), size(), and bm::base_sparse_vector< Val, BV, 1 >::size_.

Referenced by main(), and set_null().

◆ clear_all()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::clear_all	(	bool	free_mem,
		unsigned	)

resize to zero, free memory

Parameters

free_mem - true - indicates the need to free underlying memory in bit-vectors

Definition at line 2101 of file bmsparsevec.h.

References BMNOEXCEPT, and bm::base_sparse_vector< Val, BV, 1 >::clear_all().

Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::clear(), and bm::sparse_vector< unsigned, bm::bvector<> >::operator=().

◆ clear_range()

template<class Val, class BV>

sparse_vector< Val, BV > & bm::sparse_vector< Val, BV >::clear_range	(	size_type	left,
		size_type	right,
		bool	set_null = false )

clear range (assign bit 0 for all planes)

Parameters

left	- interval start
right	- interval end (closed interval)
set_null	- set cleared values to unassigned (NULL)

Definition at line 2120 of file bmsparsevec.h.

References bm::base_sparse_vector< Val, BV, 1 >::clear_range(), and set_null().

Referenced by import_u().

◆ compare()

template<class Val, class BV>

int bm::sparse_vector< Val, BV >::compare	(	size_type	idx,
		const value_type	val ) const

Compare vector element with argument.

Parameters

idx	- vactor element index
val	- argument to compare with

Returns: 0 - equal, < 0 - vect[i] < val, >0 otherwise

Definition at line 2289 of file bmsparsevec.h.

References BMNOEXCEPT, and get().

◆ copy_range()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::copy_range	(	const sparse_vector< Val, BV > &	sv,
		size_type	left,
		size_type	right,
		bm::null_support	slice_null = bm::use_null )

copy range of values from another sparse vector

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

Parameters

sv	- source vector
left	- index from in losed diapason of [left..right]
right	- index to in losed diapason of [left..right]
slice_null	- "use_null" copy range for NULL vector or do not copy it

Definition at line 2248 of file bmsparsevec.h.

References bm::base_sparse_vector< Val, BV, 1 >::copy_range_slices(), resize(), size(), sparse_vector(), and bm::xor_swap().

◆ decode()

template<class Val, class BV>

sparse_vector< Val, BV >::size_type bm::sparse_vector< Val, BV >::decode	(	value_type *	arr,
		size_type	idx_from,
		size_type	dec_size,
		bool	zero_mem = true ) const

Bulk export list of elements to a C-style array.

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	- dest array
idx_from	- index in the sparse vector to export from
dec_size	- decoding size (array allocation should match)
zero_mem	- set to false if target array is pre-initialized with 0s to avoid performance penalty

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

See also: gather

Examples: svsample03.cpp.

Definition at line 1356 of file bmsparsevec.h.

References extract().

Referenced by main().

◆ effective_size()

template<class Val, class BV>

size_type bm::sparse_vector< Val, BV >::effective_size ( ) const

inline

size of sparse vector (may be different for RSC)

Definition at line 975 of file bmsparsevec.h.

◆ effective_vector_max()

template<class Val, class BV>

size_type bm::sparse_vector< Val, BV >::effective_vector_max ( ) const

inline

Always 1 (non-matrix type).

Definition at line 980 of file bmsparsevec.h.

◆ empty()

template<class Val, class BV>

bool bm::sparse_vector< Val, BV >::empty ( ) const

inline

return true if vector is empty

Returns: true if empty

Definition at line 734 of file bmsparsevec.h.

Referenced by main(), and run_benchmark().

◆ end()

template<class Val, class BV>

const_iterator bm::sparse_vector< Val, BV >::end ( ) const

inline

Provide const iterator access to the end.

Definition at line 575 of file bmsparsevec.h.

Referenced by build_vector_pairs(), Demo1(), Demo2(), extract(), extract_planes(), extract_range(), and main().

◆ equal()

template<class Val, class BV>

bool bm::sparse_vector< Val, BV >::equal	(	const sparse_vector< Val, BV > &	sv,
		bm::null_support	null_able = bm::use_null ) const

check if another sparse vector has the same content and size

Parameters

sv	- sparse vector for comparison
null_able	- flag to consider NULL vector in comparison (default) or compare only value content planes

Returns: true, if it is the same

Definition at line 2300 of file bmsparsevec.h.

References BMNOEXCEPT, bm::base_sparse_vector< Val, BV, 1 >::equal(), and sparse_vector().

Referenced by main(), main(), SDemo1(), and SDemo2().

◆ erase()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::erase	(	size_type	idx,
		bool	erase_null = true )

erase specified element from container

Parameters

idx	- element index
erase_null	- erase the NULL vector (if exists) (default: true)

Definition at line 1975 of file bmsparsevec.h.

References BM_ASSERT, bm::base_sparse_vector< Val, BV, 1 >::erase_column(), and bm::base_sparse_vector< Val, BV, 1 >::size_.

◆ extract()

template<class Val, class BV>

sparse_vector< Val, BV >::size_type bm::sparse_vector< Val, BV >::extract	(	value_type *	arr,
		size_type	size,
		size_type	offset = 0,
		bool	zero_mem = true ) const

Bulk export list of elements to a C-style array.

Use of all extract() methods is restricted. Please consider decode() for the same purpose.

Parameters

arr	- dest array
size	- dest size
offset	- target index in the sparse vector to export from
zero_mem	- set to false if target array is pre-initialized with 0s to avoid performance penalty

Returns: effective size(number) of exported elements

See also: decode

Decoder functor

< target array for de-transpose

< bit-plane mask

< SV read offset

Definition at line 1660 of file bmsparsevec.h.

References BM_ASSERT, bm::base_sparse_vector< Val, BV, 1 >::bmatr_, BMNOEXCEPT, BMNOEXCEPT2, BMRESTRICT, bm::base_sparse_vector< Val, BV, 1 >::effective_slices(), end(), bm::for_each_bit_range_no_check(), bm::base_sparse_vector< Val, BV, 1 >::is_signed(), size(), bm::base_sparse_vector< Val, BV, 1 >::size_, and u2s_translate().

Referenced by decode().

◆ extract_planes()

template<class Val, class BV>

sparse_vector< Val, BV >::size_type bm::sparse_vector< Val, BV >::extract_planes	(	value_type *	arr,
		size_type	size,
		size_type	offset,
		bool	zero_mem = true ) const

extract medium window without use of masking vector

See also: decode

Definition at line 1618 of file bmsparsevec.h.

References bm::base_sparse_vector< Val, BV, 1 >::bmatr_, end(), size(), bm::base_sparse_vector< Val, BV, 1 >::size_, and bm::base_sparse_vector< Val, BV, 1 >::value_bits().

◆ extract_range()

template<class Val, class BV>

sparse_vector< Val, BV >::size_type bm::sparse_vector< Val, BV >::extract_range	(	value_type *	arr,
		size_type	size,
		size_type	offset,
		bool	zero_mem = true ) const

extract small window without use of masking vector

See also: decode

Definition at line 1533 of file bmsparsevec.h.

References BM_ASSERT, BM_IS_GAP, bm::base_sparse_vector< Val, BV, 1 >::bmatr_, BMGAP_PTR, bm::base_sparse_vector< Val, BV, 1 >::effective_slices(), end(), FULL_BLOCK_FAKE_ADDR, bm::gap_test_unr(), bm::get_block_coord(), IS_FULL_BLOCK, bm::base_sparse_vector< Val, BV, 1 >::is_signed(), bm::set_block_mask, bm::set_block_shift, bm::set_word_mask, bm::set_word_shift, size(), bm::base_sparse_vector< Val, BV, 1 >::size_, and u2s_translate().

◆ filter()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::filter ( const bvector_type & bv_mask )

Apply value filter, defined by mask vector.

All bit-planes are ANDed against the filter mask.

Definition at line 2275 of file bmsparsevec.h.

References bm::base_sparse_vector< Val, BV, 1 >::bmatr_, bm::base_sparse_vector< Val, BV, 1 >::get_bmatrix(), and bm::base_sparse_vector< Val, BV, 1 >::slices().

◆ find_rank()

template<class Val, class BV>

bool bm::sparse_vector< Val, BV >::find_rank	(	size_type	rank,
		size_type &	pos )

static

find position of compressed element by its rank

Definition at line 2109 of file bmsparsevec.h.

References BM_ASSERT, and BMNOEXCEPT.

◆ freeze()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::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 825 of file bmsparsevec.h.

◆ gather()

template<class Val, class BV>

sparse_vector< Val, BV >::size_type bm::sparse_vector< Val, BV >::gather	(	value_type *	arr,
		const size_type *	idx,
		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	- dest array
idx	- index list to gather elements
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 1368 of file bmsparsevec.h.

References bm::bit_block_gather_scatter(), BM_ASSERT, BM_IS_GAP, bm::BM_SORTED, bm::BM_SORTED_UNIFORM, bm::BM_UNKNOWN, bm::BM_UNSORTED, bm::base_sparse_vector< Val, BV, 1 >::bmatr_, BMGAP_PTR, bm::base_sparse_vector< Val, BV, 1 >::effective_slices(), FULL_BLOCK_FAKE_ADDR, bm::gap_bfind(), bm::gap_test_unr(), get(), bm::get_block_coord(), get_unsigned(), bm::id_max, bm::idx_arr_block_lookup_u32(), bm::idx_arr_block_lookup_u64(), bm::base_sparse_vector< Val, BV, 1 >::is_signed(), bm::set_block_mask, bm::set_block_shift, size(), and u2s_translate().

◆ get()

template<class Val, class BV>

sparse_vector< Val, BV >::value_type bm::sparse_vector< Val, BV >::get ( size_type idx ) const

get specified element without bounds checking

Parameters

idx	- element index

Returns: value of the element

Definition at line 1758 of file bmsparsevec.h.

References BM_ASSERT, BMNOEXCEPT, get_no_check(), and size().

Referenced by at(), compare(), counting_sort_naive(), gather(), inc_no_null(), inc_no_null(), bm::sparse_vector< unsigned, bm::bvector<> >::operator[](), print_sorted(), raw_data_size(), test_data(), and try_get().

◆ get_back_inserter()

template<class Val, class BV>

back_insert_iterator bm::sparse_vector< Val, BV >::get_back_inserter ( )

inline

Provide back insert iterator Back insert iterator implements buffered insertion, which is faster, than random access or push_back.

Definition at line 588 of file bmsparsevec.h.

Referenced by compute_historgam(), generate_DNA_vector(), generate_test_set(), main(), write_as_rsc_svector(), and write_as_svector().

◆ get_const_iterator()

template<class Val, class BV>

const_iterator bm::sparse_vector< Val, BV >::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 581 of file bmsparsevec.h.

◆ get_no_check()

template<class Val, class BV>

sparse_vector< Val, BV >::value_type bm::sparse_vector< Val, BV >::get_no_check ( size_type idx ) const

get specified element without checking boundary conditions

Parameters

idx	- element index

Returns: value of the element

Definition at line 1769 of file bmsparsevec.h.

References BMNOEXCEPT, get_unsigned(), bm::base_sparse_vector< Val, BV, 1 >::is_signed(), and bm::base_sparse_vector< Val, BV, 1 >::u2s().

Referenced by get().

◆ get_remap_buffer()

template<class Val, class BV>

const unsigned char * bm::sparse_vector< Val, BV >::get_remap_buffer ( ) const

inlineprotected

Definition at line 1025 of file bmsparsevec.h.

◆ get_remap_matrix() [1/2]

template<class Val, class BV>

remap_matrix_type * bm::sparse_vector< Val, BV >::get_remap_matrix ( )

inlineprotected

Definition at line 1038 of file bmsparsevec.h.

◆ get_remap_matrix() [2/2]

template<class Val, class BV>

const remap_matrix_type * bm::sparse_vector< Val, BV >::get_remap_matrix ( ) const

inlineprotected

Definition at line 1037 of file bmsparsevec.h.

◆ get_unsigned()

template<class Val, class BV>

sparse_vector< Val, BV >::unsigned_value_type bm::sparse_vector< Val, BV >::get_unsigned ( size_type idx ) const

protected

get raw unsigned value

Definition at line 1783 of file bmsparsevec.h.

References BM_ASSERT, bm::base_sparse_vector< Val, BV, 1 >::bmatr_, BMNOEXCEPT, bm::base_sparse_vector< Val, BV, 1 >::effective_slices(), bm::id_max, and bm::base_sparse_vector< Val, BV, 1 >::slice_mask_.

Referenced by gather(), and get_no_check().

◆ get_unsigned_bits()

template<class Val, class BV>

sparse_vector< Val, BV >::unsigned_value_type bm::sparse_vector< Val, BV >::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 1809 of file bmsparsevec.h.

References BM_ASSERT, bm::base_sparse_vector< Val, BV, 1 >::bmatr_, BMNOEXCEPT, bm::base_sparse_vector< Val, BV, 1 >::effective_slices(), and bm::id_max.

◆ import()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::import	(	const value_type *	arr,
		size_type	arr_size,
		size_type	offset = 0,
		bool	set_not_null = true )

Import list of elements from a C-style array.

Parameters

arr	- source array
arr_size	- source size
offset	- target index in the sparse vector
set_not_null	- import should register in not null vector

Examples: svsample03.cpp.

Definition at line 1172 of file bmsparsevec.h.

References import_u(), and bm::base_sparse_vector< Val, BV, 1 >::s2u().

Referenced by convert_bv2sv(), Demo1(), Demo2(), and main().

◆ import_back()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::import_back	(	const value_type *	arr,
		size_type	arr_size,
		bool	set_not_null = true )

Import list of elements from a C-style array (pushed back).

Parameters

arr	- source array
arr_size	- source array size
set_not_null	- import should register in not null vector

Definition at line 1312 of file bmsparsevec.h.

References import_back_u(), and bm::base_sparse_vector< Val, BV, 1 >::s2u().

◆ import_back_u()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::import_back_u	(	const unsigned_value_type *	arr,
		size_type	arr_size,
		bool	set_not_null = true )

protected

Import list of elements from a C-style array (pushed back).

Parameters

arr	- source array
arr_size	- source array size
set_not_null	- import should register in not null vector

Definition at line 1345 of file bmsparsevec.h.

References import_u_nocheck(), and size().

Referenced by import_back().

◆ import_u()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::import_u	(	const unsigned_value_type *	arr,
		size_type	arr_size,
		size_type	offset,
		bool	set_not_null )

protected

Import list of elements from a C-style array.

Parameters

arr	- source array
arr_size	- source size
offset	- target index in the sparse vector
set_not_null	- import should register in not null vector

Definition at line 1205 of file bmsparsevec.h.

References clear_range(), import_u_nocheck(), bm::base_sparse_vector< Val, BV, 1 >::size_, and throw_range_error().

Referenced by import().

◆ import_u_nocheck()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::import_u_nocheck	(	const unsigned_value_type *	arr,
		size_type	arr_size,
		size_type	offset,
		bool	set_not_null )

protected

Definition at line 1222 of file bmsparsevec.h.

References bm::bitscan(), BM_ASSERT, bm::base_sparse_vector< Val, BV, 1 >::get_create_slice(), bm::base_sparse_vector< Val, BV, 1 >::get_null_bvect(), bm::tmatrix< T, ROWS, COLS >::row(), bm::tmatrix< T, ROWS, COLS >::rows(), and bm::base_sparse_vector< Val, BV, 1 >::size_.

Referenced by import_back_u(), and import_u().

◆ inc()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::inc ( size_type idx )

increment specified element by one

Parameters

idx	- element index

Definition at line 2052 of file bmsparsevec.h.

References bm::base_sparse_vector< Val, BV, 1 >::get_null_bvect(), inc_no_null(), set_value_no_null(), and bm::base_sparse_vector< Val, BV, 1 >::size_.

Referenced by counting_sort(), counting_sort_parallel(), and counting_sort_subbatch().

◆ inc_no_null() [1/2]

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::inc_no_null ( size_type idx )

protected

Increment element by 1 without chnaging NULL vector or size.

Definition at line 2069 of file bmsparsevec.h.

References get(), bm::base_sparse_vector< Val, BV, 1 >::get_create_slice(), bm::base_sparse_vector< Val, BV, 1 >::is_signed(), set_value_no_null(), and bm::base_sparse_vector< Val, BV, 1 >::sv_value_slices.

Referenced by inc().

◆ inc_no_null() [2/2]

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::inc_no_null	(	size_type	idx,
		value_type	v )

protected

increment by v without chnaging NULL vector or size

Definition at line 2092 of file bmsparsevec.h.

References get(), and set_value_no_null().

◆ init_remap_buffer()

template<class Val, class BV>

unsigned char * bm::sparse_vector< Val, BV >::init_remap_buffer ( )

inlineprotected

Definition at line 1026 of file bmsparsevec.h.

◆ insert()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::insert	(	size_type	idx,
		value_type	v )

insert specified element into container

Parameters

idx	- element index
v	- element value

Definition at line 1916 of file bmsparsevec.h.

References insert_value(), set_value(), size(), and bm::base_sparse_vector< Val, BV, 1 >::size_.

Referenced by insertion_sort().

◆ insert_value()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::insert_value	(	size_type	idx,
		value_type	v )

protected

insert value without checking boundaries

Definition at line 1930 of file bmsparsevec.h.

References bm::base_sparse_vector< Val, BV, 1 >::insert_null(), and insert_value_no_null().

Referenced by insert().

◆ insert_value_no_null()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::insert_value_no_null	(	size_type	idx,
		value_type	v )

protected

insert value without checking boundaries or support of NULL

Definition at line 1939 of file bmsparsevec.h.

References bm::bit_scan_reverse(), BM_ASSERT, bm::base_sparse_vector< Val, BV, 1 >::bmatr_, bm::base_sparse_vector< Val, BV, 1 >::effective_slices(), bm::base_sparse_vector< Val, BV, 1 >::get_create_slice(), bm::base_sparse_vector< Val, BV, 1 >::s2u(), and bm::base_sparse_vector< Val, BV, 1 >::size_.

Referenced by insert_value().

◆ is_compressed()

template<class Val, class BV>

constexpr bool bm::sparse_vector< Val, BV >::is_compressed ( )

inlinestaticconstexpr

various type traits

Definition at line 600 of file bmsparsevec.h.

◆ is_remap()

template<class Val, class BV>

bool bm::sparse_vector< Val, BV >::is_remap ( ) const

inlineconstexprprotected

Definition at line 1023 of file bmsparsevec.h.

◆ is_ro()

template<class Val, class BV>

bool bm::sparse_vector< Val, BV >::is_ro ( ) const

inline

Returns true if vector is read-only.

Definition at line 828 of file bmsparsevec.h.

Referenced by SDemo2().

◆ is_str()

template<class Val, class BV>

constexpr bool bm::sparse_vector< Val, BV >::is_str ( )

inlinestaticconstexpr

Definition at line 603 of file bmsparsevec.h.

◆ join()

template<class Val, class BV>

sparse_vector< Val, BV > & bm::sparse_vector< Val, BV >::join ( const sparse_vector< Val, BV > & sv )

join all with another sparse vector using OR operation

Parameters

sv	- argument vector to join with

Returns: slf reference

See also: merge

Examples: svsample03.cpp.

Definition at line 2181 of file bmsparsevec.h.

References bm::base_sparse_vector< Val, BV, MAX_SIZE >::bmatr_, bm::base_sparse_vector< Val, BV, 1 >::bmatr_, bm::base_sparse_vector< Val, BV, MAX_SIZE >::get_bmatrix(), bm::base_sparse_vector< Val, BV, 1 >::get_create_slice(), join_null_slice(), resize(), bm::basic_bmatrix< BV >::row(), bm::basic_bmatrix< BV >::rows(), size(), bm::base_sparse_vector< Val, BV, 1 >::size_, and sparse_vector().

Referenced by main().

◆ join_null_slice()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::join_null_slice ( const sparse_vector< Val, BV > & sv )

protected

Definition at line 2224 of file bmsparsevec.h.

References BM_ASSERT, bm::base_sparse_vector< Val, BV, MAX_SIZE >::bmatr_, bm::base_sparse_vector< Val, BV, 1 >::bmatr_, bm::base_sparse_vector< Val, BV, 1 >::get_null_bvect(), bm::basic_bmatrix< BV >::get_null_idx(), bm::base_sparse_vector< Val, BV, MAX_SIZE >::is_nullable(), size(), and sparse_vector().

Referenced by join(), and merge().

◆ keep_range()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::keep_range	(	size_type	left,
		size_type	right,
		bm::null_support	slice_null = bm::use_null )

Keep only specified interval in the sparse vector, clear all other elements.

Parameters

left	- interval start
right	- interval end (closed interval)
slice_null	- "use_null" copy range for NULL vector or not

Definition at line 2263 of file bmsparsevec.h.

References bm::base_sparse_vector< Val, BV, 1 >::keep_range_no_check(), and bm::xor_swap().

◆ merge()

template<class Val, class BV>

sparse_vector< Val, BV > & bm::sparse_vector< Val, BV >::merge ( sparse_vector< Val, BV > & sv )

merge with another sparse vector using OR operation Merge is different from join(), because it borrows data from the source vector, so it gets modified.

Parameters

sv	- [in, out]argument vector to join with (vector mutates)

Returns: slf reference

See also: join

Definition at line 2208 of file bmsparsevec.h.

References bm::base_sparse_vector< Val, BV, MAX_SIZE >::bmatr_, join_null_slice(), bm::base_sparse_vector< Val, BV, 1 >::merge_matr(), resize(), size(), bm::base_sparse_vector< Val, BV, 1 >::size_, and sparse_vector().

Referenced by counting_sort_parallel().

◆ operator=() [1/2]

template<class Val, class BV>

sparse_vector< Val, BV > & bm::sparse_vector< Val, BV >::operator= ( const sparse_vector< Val, BV > & sv )

inline

copy assignmment operator

Definition at line 405 of file bmsparsevec.h.

◆ operator=() [2/2]

template<class Val, class BV>

sparse_vector< Val, BV > & bm::sparse_vector< Val, BV >::operator= ( sparse_vector< Val, BV > && sv )

inline

move assignmment operator

Definition at line 416 of file bmsparsevec.h.

◆ operator[]() [1/2]

template<class Val, class BV>

reference bm::sparse_vector< Val, BV >::operator[] ( size_type idx )

inline

Operator to get write access to an element.

Definition at line 435 of file bmsparsevec.h.

◆ operator[]() [2/2]

template<class Val, class BV>

value_type bm::sparse_vector< Val, BV >::operator[] ( size_type idx ) const

inline

get specified element without bounds checking

Parameters

idx	- element index

Returns: value of the element

Definition at line 443 of file bmsparsevec.h.

◆ optimize()

template<class Val, class BV>

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

run memory optimization for all vector planes

Parameters

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

Examples: svsample03.cpp.

Definition at line 2148 of file bmsparsevec.h.

References bm::bv_statistics::add(), bm::base_sparse_vector< Val, BV, 1 >::optimize(), and bm::bv_statistics::reset().

Referenced by compute_historgam(), convert_bv2sv(), Demo1(), Demo2(), generate_big_case(), main(), main(), SDemo1(), SDemo2(), and write_as_svector().

◆ optimize_gap_size()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::optimize_gap_size ( )

Optimize sizes of GAP blocks.

This method runs an analysis to find optimal GAP levels for all bit planes of the vector.

Definition at line 2167 of file bmsparsevec.h.

References bm::base_sparse_vector< Val, BV, 1 >::bmatr_, and bm::base_sparse_vector< Val, BV, 1 >::stored_slices().

◆ push_back()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::push_back ( value_type v )

push value back into vector

Parameters

v	- element value

Examples: svsample04.cpp.

Definition at line 1883 of file bmsparsevec.h.

References set_value(), and bm::base_sparse_vector< Val, BV, 1 >::size_.

Referenced by generate_random_subset(), main(), and SDemo1().

◆ push_back_no_null()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::push_back_no_null ( value_type v )

protected

push value back into vector without NULL semantics

Definition at line 1988 of file bmsparsevec.h.

References set_value_no_null(), and bm::base_sparse_vector< Val, BV, 1 >::size_.

◆ push_back_null() [1/2]

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::push_back_null ( )

inline

push back NULL value

Definition at line 504 of file bmsparsevec.h.

Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::push_back_null().

◆ push_back_null() [2/2]

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::push_back_null ( size_type count )

push back specified amount of NULL values

Parameters

count - number of NULLs to push back

Definition at line 1892 of file bmsparsevec.h.

References BM_ASSERT, bm::id_max, bm::base_sparse_vector< Val, BV, 1 >::is_nullable(), and bm::base_sparse_vector< Val, BV, 1 >::size_.

◆ remap_size()

template<class Val, class BV>

size_t bm::sparse_vector< Val, BV >::remap_size ( ) const

inlineprotected

Definition at line 1024 of file bmsparsevec.h.

◆ resize()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::resize ( size_type sz )

inline

resize vector

Parameters

sz	- new size

Definition at line 739 of file bmsparsevec.h.

Referenced by copy_range(), join(), main(), and merge().

◆ resize_internal()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::resize_internal	(	size_type	sz,
		bool	set_null = true )

inlineprotected

Definition at line 1019 of file bmsparsevec.h.

◆ resolve_range()

template<class Val, class BV>

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

inlineprotected

Definition at line 1040 of file bmsparsevec.h.

◆ set()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::set	(	size_type	idx,
		value_type	v )

set specified element with bounds checking and automatic resize

Parameters

idx	- element index
v	- element value

Examples: svsample03.cpp.

Definition at line 1849 of file bmsparsevec.h.

References set_value(), size(), and bm::base_sparse_vector< Val, BV, 1 >::size_.

Referenced by build_histogram(), compute_rsc_historgam(), convert_bv2sv(), counting_sort_naive(), fill_test_data(), load_snp_report(), main(), SDemo2(), test_mismatch_search(), test_sv_cmp(), and test_sv_cmp_it().

◆ set_allocator_pool()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::set_allocator_pool ( allocator_pool_type * pool_ptr )

Set allocator pool for local (non-threaded) memory cyclic(lots of alloc-free ops) opertations.

Definition at line 2319 of file bmsparsevec.h.

References bm::base_sparse_vector< Val, BV, 1 >::bmatr_, and BMNOEXCEPT.

◆ set_null() [1/2]

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::set_null ( const bvector_type & bv_idx )

inline

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

Function also clears all the values to 0.

Parameters

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

Definition at line 546 of file bmsparsevec.h.

◆ set_null() [2/2]

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::set_null ( size_type idx )

set specified element to unassigned value (NULL)

Parameters

idx	- element index

Definition at line 1164 of file bmsparsevec.h.

References clear().

Referenced by clear(), clear_range(), and main().

◆ set_remap()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::set_remap ( )

inlineprotected

Definition at line 1027 of file bmsparsevec.h.

◆ set_value()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::set_value	(	size_type	idx,
		value_type	v,
		bool	need_clear )

protected

set value without checking boundaries

Definition at line 1997 of file bmsparsevec.h.

References bm::base_sparse_vector< Val, BV, 1 >::get_null_bvect(), and set_value_no_null().

Referenced by clear(), insert(), push_back(), and set().

◆ set_value_no_null()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::set_value_no_null	(	size_type	idx,
		value_type	v,
		bool	need_clear )

protected

set value without checking boundaries or support of NULL

Parameters

idx	- element index
v	- value to set
need_clear	- if clear 0 bits is necessary (or not if vector is resized)

Definition at line 2008 of file bmsparsevec.h.

References bm::bit_scan_reverse(), BM_ASSERT, bm::base_sparse_vector< Val, BV, 1 >::bmatr_, bm::base_sparse_vector< Val, BV, 1 >::effective_slices(), bm::get_block_coord(), bm::base_sparse_vector< Val, BV, 1 >::get_create_slice(), bm::base_sparse_vector< Val, BV, 1 >::s2u(), and bm::set_block_shift.

Referenced by inc(), inc_no_null(), inc_no_null(), push_back_no_null(), and set_value().

◆ size()

template<class Val, class BV>

size_type bm::sparse_vector< Val, BV >::size ( ) const

inline

return size of the vector

Returns: size of sparse vector

Examples: svsample03.cpp.

Definition at line 729 of file bmsparsevec.h.

Referenced by add_centromer_Ns(), clear(), compare_sv_it(), copy_range(), Demo1(), Demo2(), bm::sparse_vector< unsigned, bm::bvector<> >::effective_size(), bm::sparse_vector< unsigned, bm::bvector<> >::empty(), extract(), extract_planes(), extract_range(), gather(), get(), import_back_u(), insert(), join(), join_null_slice(), main(), merge(), print_svector(), raw_data_size(), set(), bm::sparse_vector< unsigned, bm::bvector<> >::size_internal(), and swap().

◆ size_internal()

template<class Val, class BV>

size_type bm::sparse_vector< Val, BV >::size_internal ( ) const

inlineprotected

Definition at line 1021 of file bmsparsevec.h.

◆ swap() [1/2]

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::swap	(	size_type	idx1,
		size_type	idx2 )

swap two vector elements between each other

Parameters

idx1	- element index 1
idx1	- element index 2

Definition at line 1904 of file bmsparsevec.h.

References BM_ASSERT, size(), and bm::base_sparse_vector< Val, BV, 1 >::swap_elements().

Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::operator=().

◆ swap() [2/2]

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::swap ( sparse_vector< Val, BV > & sv )

content exchange

Definition at line 1136 of file bmsparsevec.h.

References BMNOEXCEPT, sparse_vector(), and bm::base_sparse_vector< Val, BV, 1 >::swap().

◆ sync()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::sync ( bool )

inline

syncronize internal structures, build fast access index

Definition at line 902 of file bmsparsevec.h.

◆ sync_size()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::sync_size ( )

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

Definition at line 1300 of file bmsparsevec.h.

References BMNOEXCEPT, bm::base_sparse_vector< Val, BV, 1 >::get_null_bvector(), and bm::base_sparse_vector< Val, BV, 1 >::size_.

◆ throw_bad_alloc()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::throw_bad_alloc ( )

static

throw bad alloc

Definition at line 1156 of file bmsparsevec.h.

◆ throw_range_error()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::throw_range_error ( const char * err_msg )

static

throw range error

Definition at line 1144 of file bmsparsevec.h.

References BM_ASSERT_THROW.

Referenced by at(), and import_u().

◆ translate_address()

template<class Val, class BV>

size_type bm::sparse_vector< Val, BV >::translate_address ( size_type i )

inlinestatic

address translation for this type of container

Definition at line 949 of file bmsparsevec.h.

◆ try_get()

template<class Val, class BV>

bool bm::sparse_vector< Val, BV >::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 1836 of file bmsparsevec.h.

References BMNOEXCEPT, get(), and bm::base_sparse_vector< Val, BV, 1 >::is_null().

◆ u2s_translate()

template<class Val, class BV>

void bm::sparse_vector< Val, BV >::u2s_translate	(	value_type *	arr,
		size_type	sz )

staticprotected

Definition at line 1732 of file bmsparsevec.h.

References BMNOEXCEPT, and bm::base_sparse_vector< Val, BV, 1 >::u2s().

Referenced by extract(), extract_range(), and gather().

◆ rsc_sparse_vector

template<class Val, class BV>

template<class V, class SV>

friend class rsc_sparse_vector

friend

Definition at line 1087 of file bmsparsevec.h.

◆ sparse_vector_deserializer

template<class Val, class BV>

template<class SVect>

friend class sparse_vector_deserializer

friend

Definition at line 1090 of file bmsparsevec.h.

◆ sparse_vector_scanner

template<class Val, class BV>

template<class SVect, unsigned S_FACTOR>

friend class sparse_vector_scanner

friend

Definition at line 1088 of file bmsparsevec.h.

◆ sparse_vector_serializer

template<class Val, class BV>

template<class SVect>

friend class sparse_vector_serializer

friend

Definition at line 1089 of file bmsparsevec.h.

Field Documentation

◆ back_insert_iterator

template<class Val, class BV>

friend bm::sparse_vector< Val, BV >::back_insert_iterator

Definition at line 373 of file bmsparsevec.h.

Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::get_back_inserter().

◆ const_iterator

template<class Val, class BV>

friend bm::sparse_vector< Val, BV >::const_iterator

Definition at line 372 of file bmsparsevec.h.

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

bmsparsevec.h

Data Structures

Public Types

Public Member Functions

Static Public Member Functions

Data Fields

Protected Types

Protected Member Functions

Static Protected Member Functions

Friends

Access to internals

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ allocation_policy_type

◆ allocator_pool_type

◆ allocator_type

◆ block_idx_type

◆ bmatrix_type

◆ bvector_enumerator_type

◆ bvector_type

◆ bvector_type_const_ptr

◆ bvector_type_ptr

◆ const_reference

◆ parent_type

◆ remap_matrix_type

◆ size_type

◆ unsigned_value_type

◆ value_type

Member Enumeration Documentation

◆ buf_size_e

◆ octet_slices

Constructor & Destructor Documentation

◆ sparse_vector() [1/3]

◆ sparse_vector() [2/3]

◆ sparse_vector() [3/3]

◆ ~sparse_vector()

Member Function Documentation

◆ at()

◆ begin()

◆ calc_stat()

◆ clear() [1/3]

◆ clear() [2/3]

◆ clear() [3/3]

◆ clear_all()

◆ clear_range()

◆ compare()

◆ copy_range()

◆ decode()

◆ effective_size()

◆ effective_vector_max()

◆ empty()

◆ end()

◆ equal()

◆ erase()

◆ extract()

◆ extract_planes()

◆ extract_range()

◆ filter()

◆ find_rank()

◆ freeze()

◆ gather()

◆ get()

◆ get_back_inserter()

◆ get_const_iterator()

◆ get_no_check()

◆ get_remap_buffer()

◆ get_remap_matrix() [1/2]

◆ get_remap_matrix() [2/2]

◆ get_unsigned()

◆ get_unsigned_bits()

◆ import()

◆ import_back()

◆ import_back_u()

◆ import_u()

◆ import_u_nocheck()

◆ inc()

◆ inc_no_null() [1/2]

◆ inc_no_null() [2/2]

◆ init_remap_buffer()

◆ insert()