BitMagic-C++
Data Structures | Public Types | Public Member Functions | Data Fields | Protected Member Functions | Friends
bm::sparse_vector< Val, BV > Class Template Reference

sparse vector with runtime compression using bit transposition method More...

#include <bmsparsevec.h>

Inheritance diagram for bm::sparse_vector< Val, BV >:
Inheritance graph
[legend]

Data Structures

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

Public Types

enum  bit_plains { sv_plains = (sizeof(Val) * 8 + 1), sv_value_plains = (sizeof(Val) * 8) }
 
typedef Val value_type
 
typedef bm::id_t size_type
 
typedef BV bvector_type
 
typedef bvector_typebvector_type_ptr
 
typedef const value_typeconst_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
 

Public Member Functions

void swap (sparse_vector< Val, BV > &sv) BMNOEXEPT
 content exchange More...
 
void set_allocator_pool (allocator_pool_type *pool_ptr)
 Set allocator pool for local (non-threaded) memory cyclic(lots of alloc-free ops) opertations. More...
 
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. More...
 
 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) BMNOEXEPT
 
sparse_vector< Val, BV > & operator= (sparse_vector< Val, BV > &&sv) BMNOEXEPT
 
 ~sparse_vector () BMNOEXEPT
 
Element access
reference operator[] (size_type idx)
 Operator to get write access to an element. More...
 
value_type operator[] (size_type idx) const
 get specified element without bounds checking More...
 
value_type at (size_type idx) const
 access specified element with bounds checking More...
 
value_type get (bm::id_t idx) const
 get specified element without bounds checking More...
 
void set (size_type idx, value_type v)
 set specified element with bounds checking and automatic resize More...
 
void inc (size_type idx)
 increment specified element by one More...
 
void push_back (value_type v)
 push value back into vector More...
 
void clear (size_type idx, bool set_null=false)
 clear specified element with bounds checking and automatic resize More...
 
Iterator access
const_iterator begin () const
 Provide const iterator access to container content. More...
 
const_iterator end () const
 Provide const iterator access to the end. More...
 
const_iterator get_const_iterator (size_type idx) const
 Get const_itertor re-positioned to specific element. More...
 
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. More...
 
Loading of sparse vector from C-style array
void import (const value_type *arr, size_type size, size_type offset=0)
 Import list of elements from a C-style array. More...
 
void import_back (const value_type *arr, size_type size)
 Import list of elements from a C-style array (pushed back) More...
 
Export content to C-style array
size_type decode (value_type *arr, size_type idx_from, size_type size, bool zero_mem=true) const
 Bulk export list of elements to a C-style array. More...
 
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. More...
 
Clear
void clear () BMNOEXEPT
 resize to zero, free memory More...
 
sparse_vector< Val, BV > & clear_range (size_type left, size_type right, bool set_null=false)
 clear range (assign bit 0 for all plains) More...
 
Size, etc
size_type size () const
 return size of the vector More...
 
bool empty () const
 return true if vector is empty More...
 
void resize (size_type sz)
 resize vector More...
 
Comparison
bool 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 More...
 
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 plains More...
 
void optimize_gap_size ()
 Optimize sizes of GAP blocks. More...
 
void calc_stat (struct sparse_vector< Val, BV >::statistics *st) const
 Calculates memory statistics. More...
 
Merge, split, partition data
sparse_vector< Val, BV > & join (const sparse_vector< Val, BV > &sv)
 join all with another sparse vector using OR operation More...
 
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. More...
 
void copy_range (const sparse_vector< Val, BV > &sv, size_type left, size_type right)
 copy range of values from another sparse vector More...
 
void filter (const bvector_type &bv_mask)
 Apply value filter, defined by mask vector. More...
 

Data Fields

friend const_iterator
 
friend back_insert_iterator
 

Protected Member Functions

void set_value (size_type idx, value_type v)
 set value without checking boundaries More...
 
void set_value_no_null (size_type idx, value_type v)
 set value without checking boundaries or support of NULL More...
 
void push_back_no_null (value_type v)
 push value back into vector without NULL semantics More...
 
const bm::word_tget_block (unsigned p, unsigned i, unsigned j) const
 
bvector_typeconstruct_bvector (const bvector_type *bv) const
 
void destruct_bvector (bvector_type *bv) const
 
bvector_typeget_null_bvect ()
 
void resize_internal (size_type sz)
 
size_type size_internal () const
 

Friends

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

Various traits

bool is_nullable () const
 check if container supports NULL(unassigned) values More...
 
const bvector_typeget_null_bvector () const
 Get bit-vector of assigned values or NULL (if not constructed that way) More...
 
bool is_null (size_type idx) const
 test if specified element is NULL More...
 
void set_null (size_type idx)
 set specified element to unassigned value (NULL) More...
 
static bool is_compressed ()
 trait if sparse vector is "compressed" (false) More...
 

Access to internals

bvector_type_ptr get_plain (unsigned i)
 get access to bit-plain, function checks and creates a plain More...
 
const bvector_type_ptr get_plain (unsigned i) const
 get read-only access to bit-plain More...
 
bvector_type_ptr plain (unsigned i)
 get access to bit-plain as is (can return NULL) More...
 
const bvector_type_ptr plain (unsigned i) const
 
void sync (bool)
 syncronize internal structures More...
 
void free_plain (unsigned i)
 free memory in bit-plain More...
 
size_type extract (value_type *arr, size_type size, size_type offset=0, bool zero_mem=true, allocator_pool_type *pool_ptr=0) const
 Bulk export list of elements to a C-style array. More...
 
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 More...
 
size_type extract_plains (value_type *arr, size_type size, size_type offset, bool zero_mem=true) const
 extract medium window without use of masking vector More...
 
unsigned effective_plains () const
 Number of effective bit-plains in the value type. More...
 
bool find_rank (bm::id_t rank, bm::id_t &pos) const
 find position of compressed element by its rank More...
 
size_type effective_size () const
 size of sparse vector (may be different for RSC) More...
 
static unsigned plains ()
 get total number of bit-plains in the vector More...
 
static unsigned stored_plains ()
 Number of stored bit-plains (value plains + extra. More...
 
static size_type translate_address (size_type i)
 address translation for this type of container More...
 
static void throw_range_error (const char *err_msg)
 throw range error More...
 
static void throw_bad_alloc ()
 throw bad alloc More...
 

Detailed Description

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

sparse vector with runtime compression using bit transposition method

Sparse vector implements variable bit-depth storage model. Initial data is bit-transposed into bit-planes so initial each element may use less memory than the original native data type prescribes. For example, 32-bit integer may only use 20 bits.

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.

Overall it provides variable bit-depth compression, sparse compression in bit-plains.

Examples:
rscsample01.cpp, svsample01.cpp, svsample02.cpp, svsample03.cpp, svsample04.cpp, svsample05.cpp, svsample06.cpp, xsample01.cpp, xsample02.cpp, and xsample03.cpp.

Definition at line 74 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 90 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 92 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 89 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 91 of file bmsparsevec.h.

◆ bvector_type

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

Definition at line 86 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 87 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 88 of file bmsparsevec.h.

◆ size_type

template<class Val, class BV>
typedef bm::id_t bm::sparse_vector< Val, BV >::size_type

Definition at line 85 of file bmsparsevec.h.

◆ value_type

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

Definition at line 84 of file bmsparsevec.h.

Member Enumeration Documentation

◆ bit_plains

template<class Val, class BV>
enum bm::sparse_vector::bit_plains
Enumerator
sv_plains 
sv_value_plains 

Definition at line 78 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 921 of file bmsparsevec.h.

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

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

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

◆ ~sparse_vector()

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

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

Definition at line 1629 of file bmsparsevec.h.

Referenced by main(), bm::sparse_vector< unsigned, bm::bvector<> >::operator[](), 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 2263 of file bmsparsevec.h.

Referenced by build_vector_pairs(), main(), and bm::sparse_vector< unsigned, bm::bvector<> >::operator[]().

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

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

◆ clear() [1/2]

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

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

Referenced by main().

◆ clear() [2/2]

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

◆ 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 plains)

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

Definition at line 1950 of file bmsparsevec.h.

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

◆ construct_bvector()

template<class Val , class BV >
sparse_vector< Val, BV >::bvector_type * bm::sparse_vector< Val, BV >::construct_bvector ( const bvector_type bv) const
protected

◆ 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 
)

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]

Definition at line 2153 of file bmsparsevec.h.

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

◆ 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  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
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

Definition at line 1191 of file bmsparsevec.h.

Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::is_compressed(), and main().

◆ destruct_bvector()

template<class Val , class BV >
void bm::sparse_vector< Val, BV >::destruct_bvector ( bvector_type bv) const
protected

◆ effective_plains()

template<class Val, class BV>
unsigned bm::sparse_vector< Val, BV >::effective_plains ( ) const
inline

Number of effective bit-plains in the value type.

Definition at line 845 of file bmsparsevec.h.

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

◆ empty()

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

return true if vector is empty

Returns
true if empty

Definition at line 1578 of file bmsparsevec.h.

Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::is_compressed(), main(), bm::sparse_vector< Val, BV >::back_insert_iterator::operator++(), 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 476 of file bmsparsevec.h.

Referenced by build_vector_pairs(), 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 plains
Returns
true, if it is the same

Definition at line 2213 of file bmsparsevec.h.

Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::is_compressed(), and main().

◆ 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,
allocator_pool_type pool_ptr = 0 
) 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
number of exported elements
See also
decode

Decoder functor

Definition at line 1477 of file bmsparsevec.h.

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

◆ extract_plains()

template<class Val , class BV >
sparse_vector< Val, BV >::size_type bm::sparse_vector< Val, BV >::extract_plains ( 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 1432 of file bmsparsevec.h.

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

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

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

◆ 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-plains are ANDed against the filter mask.

Definition at line 2188 of file bmsparsevec.h.

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

◆ find_rank()

template<class Val , class BV >
bool bm::sparse_vector< Val, BV >::find_rank ( bm::id_t  rank,
bm::id_t pos 
) const

find position of compressed element by its rank

Definition at line 1927 of file bmsparsevec.h.

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

◆ free_plain()

template<class Val , class BV >
void bm::sparse_vector< Val, BV >::free_plain ( unsigned  i)

free memory in bit-plain

Definition at line 1938 of file bmsparsevec.h.

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

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

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

◆ get()

template<class Val , class BV >
sparse_vector< Val, BV >::value_type bm::sparse_vector< Val, BV >::get ( bm::id_t  idx) const

get specified element without bounds checking

Parameters
idx- element index
Returns
value of the element

Definition at line 1654 of file bmsparsevec.h.

Referenced by counting_sort_naive(), and print_sorted().

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

Referenced by generate_test_set().

◆ get_block()

template<class Val , class BV >
const bm::word_t * bm::sparse_vector< Val, BV >::get_block ( unsigned  p,
unsigned  i,
unsigned  j 
) const
protected

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

◆ get_null_bvect()

template<class Val, class BV>
bvector_type* bm::sparse_vector< Val, BV >::get_null_bvect ( )
inlineprotected

Definition at line 892 of file bmsparsevec.h.

◆ get_null_bvector()

template<class Val , class BV >
const sparse_vector< Val, BV >::bvector_type * bm::sparse_vector< Val, BV >::get_null_bvector ( ) const

◆ get_plain() [1/2]

template<class Val , class BV >
sparse_vector< Val, BV >::bvector_type_ptr bm::sparse_vector< Val, BV >::get_plain ( unsigned  i)

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

Returns
bit-vector for the bit plain

Definition at line 1611 of file bmsparsevec.h.

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

◆ get_plain() [2/2]

template<class Val, class BV>
const bvector_type_ptr bm::sparse_vector< Val, BV >::get_plain ( unsigned  i) const
inline

get read-only access to bit-plain

Returns
bit-vector for the bit plain or NULL

Definition at line 758 of file bmsparsevec.h.

◆ import()

template<class Val , class BV >
void bm::sparse_vector< Val, BV >::import ( const value_type arr,
size_type  size,
size_type  offset = 0 
)

Import list of elements from a C-style array.

Parameters
arr- source array
size- source size
offset- target index in the sparse vector

Definition at line 1108 of file bmsparsevec.h.

Referenced by convert_bv2sv(), and main().

◆ import_back()

template<class Val , class BV >
void bm::sparse_vector< Val, BV >::import_back ( const value_type arr,
size_type  size 
)

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

Parameters
arr- source array
size- source size

Definition at line 1181 of file bmsparsevec.h.

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

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

Referenced by counting_sort(), counting_sort_parallel(), counting_sort_subbatch(), and bm::sparse_vector< unsigned, bm::bvector<> >::operator[]().

◆ is_compressed()

template<class Val, class BV>
static bool bm::sparse_vector< Val, BV >::is_compressed ( )
inlinestatic

trait if sparse vector is "compressed" (false)

Definition at line 520 of file bmsparsevec.h.

◆ is_null()

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

Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::get_back_inserter(), bm::sparse_vector< Val, BV >::const_iterator::operator++(), and print_svector().

◆ is_nullable()

template<class Val , class BV >
bool bm::sparse_vector< Val, BV >::is_nullable ( ) const

◆ 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

Definition at line 2076 of file bmsparsevec.h.

Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::is_compressed(), and main().

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

Referenced by counting_sort_parallel(), and bm::sparse_vector< unsigned, bm::bvector<> >::is_compressed().

◆ 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 354 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 398 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 418 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 425 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 plains

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

Referenced by convert_bv2sv(), bm::sparse_vector< unsigned, bm::bvector<> >::is_compressed(), and main().

◆ 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 plains of the vector.

Definition at line 2059 of file bmsparsevec.h.

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

◆ plain() [1/2]

template<class Val, class BV>
bvector_type_ptr bm::sparse_vector< Val, BV >::plain ( unsigned  i)
inline

get access to bit-plain as is (can return NULL)

Definition at line 771 of file bmsparsevec.h.

◆ plain() [2/2]

template<class Val, class BV>
const bvector_type_ptr bm::sparse_vector< Val, BV >::plain ( unsigned  i) const
inline

Definition at line 772 of file bmsparsevec.h.

◆ plains()

template<class Val, class BV>
static unsigned bm::sparse_vector< Val, BV >::plains ( )
inlinestatic

get total number of bit-plains in the vector

Definition at line 763 of file bmsparsevec.h.

◆ 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

Definition at line 1780 of file bmsparsevec.h.

Referenced by generate_random_subset(), main(), and bm::sparse_vector< unsigned, bm::bvector<> >::operator[]().

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

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

◆ resize()

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

◆ resize_internal()

template<class Val, class BV>
void bm::sparse_vector< Val, BV >::resize_internal ( size_type  sz)
inlineprotected

Definition at line 894 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

Definition at line 1751 of file bmsparsevec.h.

Referenced by build_histogram(), convert_bv2sv(), counting_sort_naive(), load_snp_report(), and main().

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

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

◆ set_null()

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

Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::get_back_inserter(), main(), and bm::sparse_vector< unsigned, bm::bvector<> >::operator[]().

◆ set_value()

template<class Val , class BV >
void bm::sparse_vector< Val, BV >::set_value ( size_type  idx,
value_type  v 
)
protected

set value without checking boundaries

Definition at line 1798 of file bmsparsevec.h.

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

◆ 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 
)
protected

set value without checking boundaries or support of NULL

Definition at line 1809 of file bmsparsevec.h.

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

◆ size()

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

◆ size_internal()

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

Definition at line 895 of file bmsparsevec.h.

◆ stored_plains()

template<class Val, class BV>
static unsigned bm::sparse_vector< Val, BV >::stored_plains ( )
inlinestatic

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

Definition at line 766 of file bmsparsevec.h.

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

◆ swap()

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

◆ sync()

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

syncronize internal structures

Definition at line 775 of file bmsparsevec.h.

◆ throw_bad_alloc()

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

throw bad alloc

Definition at line 1039 of file bmsparsevec.h.

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

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

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

◆ translate_address()

template<class Val, class BV>
static size_type bm::sparse_vector< Val, BV >::translate_address ( size_type  i)
inlinestatic

address translation for this type of container

Definition at line 828 of file bmsparsevec.h.

Friends And Related Function Documentation

◆ rsc_sparse_vector

template<class Val, class BV>
template<class V , class SV >
friend class rsc_sparse_vector
friend

Definition at line 898 of file bmsparsevec.h.

◆ sparse_vector_deserializer

template<class Val, class BV>
template<class SVect >
friend class sparse_vector_deserializer
friend

Definition at line 901 of file bmsparsevec.h.

◆ sparse_vector_scanner

template<class Val, class BV>
template<class SVect >
friend class sparse_vector_scanner
friend

Definition at line 899 of file bmsparsevec.h.

◆ sparse_vector_serializer

template<class Val, class BV>
template<class SVect >
friend class sparse_vector_serializer
friend

Definition at line 900 of file bmsparsevec.h.

Field Documentation

◆ back_insert_iterator

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

◆ const_iterator

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

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