BitMagic-C++
|
Rank-Select compressed sparse vector. More...
#include <bmsparsevec_compr.h>
Data Structures | |
struct | is_remap_support |
struct | is_rsc_support |
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) } |
enum | vector_capacity { max_vector_size = 1 } |
typedef Val | value_type |
typedef SV::size_type | size_type |
typedef SV | sparse_vector_type |
typedef SV::const_iterator | sparse_vector_const_iterator |
typedef SV::bvector_type | bvector_type |
typedef bvector_type * | bvector_type_ptr |
typedef bvector_type::allocator_type | allocator_type |
typedef bvector_type::allocation_policy | allocation_policy_type |
typedef bvector_type::rs_index_type | rs_index_type |
typedef bvector_type::enumerator | bvector_enumerator_type |
Public Member Functions | |
Construction and assignment | |
| |
rsc_sparse_vector (bm::null_support null_able=bm::use_null, allocation_policy_type ap=allocation_policy_type(), size_type bv_max_size=bm::id_max, const allocator_type &alloc=allocator_type()) | |
~rsc_sparse_vector () | |
rsc_sparse_vector (const rsc_sparse_vector< Val, SV > &csv) | |
rsc_sparse_vector< Val, SV > & | operator= (const rsc_sparse_vector< Val, SV > &csv) |
rsc_sparse_vector (rsc_sparse_vector< Val, SV > &&csv) BMNOEXEPT | |
rsc_sparse_vector< Val, SV > & | operator= (rsc_sparse_vector< Val, SV > &&csv) BMNOEXEPT |
Size, etc | |
| |
size_type | size () const |
return size of the vector More... | |
bool | empty () const |
return true if vector is empty More... | |
Element access | |
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 (size_type idx) const |
get specified element without bounds checking More... | |
void | push_back (size_type idx, value_type v) |
set specified element with bounds checking and automatic resize More... | |
void | set (size_type idx, value_type v) |
set specified element with bounds checking and automatic resize More... | |
void | set_null (size_type idx) |
set specified element to NULL RSC vector actually erases element when it is set to NULL (expensive). More... | |
bool | is_null (size_type idx) const |
test if specified element is NULL More... | |
const bvector_type * | get_null_bvector () const |
Get bit-vector of assigned values (or NULL) More... | |
bool | find_rank (size_type rank, size_type &idx) const |
find position of compressed element by its rank More... | |
Export content to C-stype array | |
| |
size_type | decode (value_type *arr, size_type idx_from, size_type size, bool zero_mem=true) const |
Comparison | |
bool | equal (const rsc_sparse_vector< Val, SV > &csv) const |
check if another vector has the same content More... | |
Load-Export compressed vector with data | |
void | load_from (const sparse_vector_type &sv_src) |
Load compressed vector from a sparse vector (with NULLs) More... | |
void | load_to (sparse_vector_type &sv) const |
Exort compressed vector to a sparse vector (with NULLs) More... | |
Memory optimization | |
| |
void | optimize (bm::word_t *temp_block=0, typename bvector_type::optmode opt_mode=bvector_type::opt_compress, statistics *stat=0) |
run memory optimization for all vector plains More... | |
void | clear () BMNOEXEPT |
resize to zero, free memory More... | |
void | calc_stat (struct rsc_sparse_vector< Val, SV >::statistics *st) const |
Calculates memory statistics. More... | |
Fast access structues sync | |
| |
void | sync (bool force) |
Re-calculate prefix sum table used for rank search. More... | |
void | sync () |
Re-calculate prefix sum table used for rank search (if necessary) More... | |
bool | in_sync () const |
returns true if prefix sum table is in sync with the vector More... | |
void | unsync () |
Unsync the prefix sum table. More... | |
Data Fields | |
const typedef value_type & | const_reference |
const typedef bvector_type * | bvector_type_const_ptr |
Protected Types | |
enum | octet_plains { sv_octet_plains = sizeof(value_type) } |
Protected Member Functions | |
bool | resolve (size_type idx, size_type *idx_to) const |
Resolve logical address to access via rank compressed address. More... | |
void | resize_internal (size_type sz) |
size_type | size_internal () const |
bool | is_remap () const |
size_t | remap_size () const |
const unsigned char * | get_remap_buffer () const |
unsigned char * | init_remap_buffer () |
void | set_remap () |
void | push_back_no_check (size_type idx, value_type v) |
Friends | |
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 |
if container supports NULL(unassigned) values (true) More... | |
static bool | is_compressed () |
trait if sparse vector is "compressed" (true) More... | |
Access to internals | |
bvector_type_const_ptr | get_plain (unsigned i) const |
get access to bit-plain, function checks and creates a plain More... | |
bvector_type_ptr | get_plain (unsigned i) |
unsigned | effective_plains () const |
const sparse_vector_type & | get_sv () const |
access dense vector More... | |
size_type | effective_size () const |
size of internal dense vector More... | |
size_type | effective_vector_max () const |
Always 1 (non-matrix type) 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... | |
Rank-Select compressed sparse vector.
Container uses Rank-Select method of compression, where all NULL columns gets dropped, effective address of columns is computed using address bit-vector.
Use for cases, where memory efficiency is preferable over single element access latency.
Definition at line 58 of file bmsparsevec_compr.h.
typedef bvector_type::allocation_policy bm::rsc_sparse_vector< Val, SV >::allocation_policy_type |
Definition at line 76 of file bmsparsevec_compr.h.
typedef bvector_type::allocator_type bm::rsc_sparse_vector< Val, SV >::allocator_type |
Definition at line 75 of file bmsparsevec_compr.h.
typedef bvector_type::enumerator bm::rsc_sparse_vector< Val, SV >::bvector_enumerator_type |
Definition at line 78 of file bmsparsevec_compr.h.
typedef SV::bvector_type bm::rsc_sparse_vector< Val, SV >::bvector_type |
Definition at line 72 of file bmsparsevec_compr.h.
typedef bvector_type* bm::rsc_sparse_vector< Val, SV >::bvector_type_ptr |
Definition at line 73 of file bmsparsevec_compr.h.
typedef bvector_type::rs_index_type bm::rsc_sparse_vector< Val, SV >::rs_index_type |
Definition at line 77 of file bmsparsevec_compr.h.
typedef SV::size_type bm::rsc_sparse_vector< Val, SV >::size_type |
Definition at line 69 of file bmsparsevec_compr.h.
typedef SV::const_iterator bm::rsc_sparse_vector< Val, SV >::sparse_vector_const_iterator |
Definition at line 71 of file bmsparsevec_compr.h.
typedef SV bm::rsc_sparse_vector< Val, SV >::sparse_vector_type |
Definition at line 70 of file bmsparsevec_compr.h.
typedef Val bm::rsc_sparse_vector< Val, SV >::value_type |
Definition at line 67 of file bmsparsevec_compr.h.
enum bm::rsc_sparse_vector::bit_plains |
Enumerator | |
---|---|
sv_plains | |
sv_value_plains |
Definition at line 61 of file bmsparsevec_compr.h.
|
protected |
Enumerator | |
---|---|
sv_octet_plains |
Definition at line 416 of file bmsparsevec_compr.h.
enum bm::rsc_sparse_vector::vector_capacity |
Enumerator | |
---|---|
max_vector_size |
Definition at line 80 of file bmsparsevec_compr.h.
bm::rsc_sparse_vector< Val, SV >::rsc_sparse_vector | ( | bm::null_support | null_able = bm::use_null , |
allocation_policy_type | ap = allocation_policy_type() , |
||
size_type | bv_max_size = bm::id_max , |
||
const allocator_type & | alloc = allocator_type() |
||
) |
Definition at line 463 of file bmsparsevec_compr.h.
References BM_ASSERT, bm::rsc_sparse_vector< Val, SV >::sv_value_plains, and bm::use_null.
bm::rsc_sparse_vector< Val, SV >::~rsc_sparse_vector |
Definition at line 479 of file bmsparsevec_compr.h.
bm::rsc_sparse_vector< Val, SV >::rsc_sparse_vector | ( | const rsc_sparse_vector< Val, SV > & | csv | ) |
copy-ctor
Definition at line 487 of file bmsparsevec_compr.h.
References BM_ASSERT, and bm::rsc_sparse_vector< Val, SV >::sv_value_plains.
bm::rsc_sparse_vector< Val, SV >::rsc_sparse_vector | ( | rsc_sparse_vector< Val, SV > && | csv | ) |
move-ctor
Definition at line 505 of file bmsparsevec_compr.h.
rsc_sparse_vector< Val, SV >::value_type bm::rsc_sparse_vector< Val, SV >::at | ( | size_type | idx | ) | const |
access specified element with bounds checking
idx | - element index |
Definition at line 740 of file bmsparsevec_compr.h.
void bm::rsc_sparse_vector< Val, SV >::calc_stat | ( | struct rsc_sparse_vector< Val, SV >::statistics * | st | ) | const |
Calculates memory statistics.
Function fills statistics structure containing information about how this vector uses memory and estimation of max. amount of memory bvector needs to serialize itself.
st | - pointer on statistics structure to be filled in. |
Definition at line 804 of file bmsparsevec_compr.h.
References BM_ASSERT.
void bm::rsc_sparse_vector< Val, SV >::clear |
resize to zero, free memory
Definition at line 795 of file bmsparsevec_compr.h.
Referenced by bm::rsc_sparse_vector< Val, SV >::operator=().
rsc_sparse_vector< Val, SV >::size_type bm::rsc_sparse_vector< Val, SV >::decode | ( | value_type * | arr, |
size_type | idx_from, | ||
size_type | size, | ||
bool | zero_mem = true |
||
) | const |
Definition at line 848 of file bmsparsevec_compr.h.
References bm::bvector< Alloc >::enumerator::advance(), BM_ASSERT, bm::id_max, and bm::bvector< Alloc >::iterator_base::valid().
|
inline |
Number of effective bit-plains in the value type
Definition at line 388 of file bmsparsevec_compr.h.
|
inline |
size of internal dense vector
Definition at line 406 of file bmsparsevec_compr.h.
|
inline |
Always 1 (non-matrix type)
Definition at line 411 of file bmsparsevec_compr.h.
|
inline |
return true if vector is empty
Definition at line 177 of file bmsparsevec_compr.h.
Referenced by main(), and run_benchmark().
bool bm::rsc_sparse_vector< Val, SV >::equal | ( | const rsc_sparse_vector< Val, SV > & | csv | ) | const |
check if another vector has the same content
Definition at line 603 of file bmsparsevec_compr.h.
Referenced by main().
bool bm::rsc_sparse_vector< Val, SV >::find_rank | ( | size_type | rank, |
size_type & | idx | ||
) | const |
find position of compressed element by its rank
rank | - rank (virtual index in sparse vector) |
idx | - index (true position) |
Definition at line 831 of file bmsparsevec_compr.h.
References BM_ASSERT.
rsc_sparse_vector< Val, SV >::value_type bm::rsc_sparse_vector< Val, SV >::get | ( | size_type | idx | ) | const |
get specified element without bounds checking
idx | - element index |
Definition at line 755 of file bmsparsevec_compr.h.
Referenced by bm::rsc_sparse_vector< Val, SV >::operator[]().
const rsc_sparse_vector< Val, SV >::bvector_type * bm::rsc_sparse_vector< Val, SV >::get_null_bvector |
Get bit-vector of assigned values (or NULL)
Definition at line 822 of file bmsparsevec_compr.h.
|
inline |
Definition at line 383 of file bmsparsevec_compr.h.
|
inline |
get access to bit-plain, function checks and creates a plain
Definition at line 381 of file bmsparsevec_compr.h.
|
inlineprotected |
Definition at line 436 of file bmsparsevec_compr.h.
|
inline |
access dense vector
Definition at line 401 of file bmsparsevec_compr.h.
|
inline |
returns true if prefix sum table is in sync with the vector
Definition at line 365 of file bmsparsevec_compr.h.
|
inlineprotected |
Definition at line 437 of file bmsparsevec_compr.h.
|
inlinestatic |
trait if sparse vector is "compressed" (true)
Definition at line 277 of file bmsparsevec_compr.h.
bool bm::rsc_sparse_vector< Val, SV >::is_null | ( | size_type | idx | ) | const |
test if specified element is NULL
idx | - element index |
Definition at line 768 of file bmsparsevec_compr.h.
References BM_ASSERT.
|
inline |
if container supports NULL(unassigned) values (true)
Definition at line 272 of file bmsparsevec_compr.h.
|
inlineprotected |
Definition at line 434 of file bmsparsevec_compr.h.
void bm::rsc_sparse_vector< Val, SV >::load_from | ( | const sparse_vector_type & | sv_src | ) |
Load compressed vector from a sparse vector (with NULLs)
sv_src | - source sparse vector |
Definition at line 617 of file bmsparsevec_compr.h.
References BM_ASSERT, and bm::rank_compressor< BV >::compress().
Referenced by main().
void bm::rsc_sparse_vector< Val, SV >::load_to | ( | sparse_vector_type & | sv | ) | const |
Exort compressed vector to a sparse vector (with NULLs)
sv | - target sparse vector |
Definition at line 658 of file bmsparsevec_compr.h.
References BM_ASSERT, and bm::rank_compressor< BV >::decompress().
Referenced by main().
|
inline |
copy assignmment operator
Definition at line 128 of file bmsparsevec_compr.h.
|
inline |
move assignmment operator
Definition at line 148 of file bmsparsevec_compr.h.
References bm::rsc_sparse_vector< Val, SV >::clear().
|
inline |
get specified element without bounds checking
idx | - element index |
Definition at line 190 of file bmsparsevec_compr.h.
References bm::rsc_sparse_vector< Val, SV >::get().
void bm::rsc_sparse_vector< Val, SV >::optimize | ( | bm::word_t * | temp_block = 0 , |
typename bvector_type::optmode | opt_mode = bvector_type::opt_compress , |
||
statistics * | stat = 0 |
||
) |
run memory optimization for all vector plains
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 778 of file bmsparsevec_compr.h.
Referenced by main().
|
inlinestatic |
get total number of bit-plains in the vector
Definition at line 393 of file bmsparsevec_compr.h.
void bm::rsc_sparse_vector< Val, SV >::push_back | ( | size_type | idx, |
value_type | v | ||
) |
set specified element with bounds checking and automatic resize
Method cannot insert elements, so every new idx has to be greater or equal than what it used before. Elements must be loaded in a sorted order.
idx | - element index |
v | - element value |
Definition at line 530 of file bmsparsevec_compr.h.
|
protected |
Definition at line 545 of file bmsparsevec_compr.h.
References BM_ASSERT.
|
inlineprotected |
Definition at line 435 of file bmsparsevec_compr.h.
|
inlineprotected |
Definition at line 431 of file bmsparsevec_compr.h.
|
protected |
Resolve logical address to access via rank compressed address.
idx | - input id to resolve |
idx_to | - output id |
Definition at line 712 of file bmsparsevec_compr.h.
References BM_ASSERT.
void bm::rsc_sparse_vector< Val, SV >::set | ( | size_type | idx, |
value_type | v | ||
) |
set specified element with bounds checking and automatic resize
idx | - element index |
v | - element value |
Definition at line 577 of file bmsparsevec_compr.h.
References BM_ASSERT.
void bm::rsc_sparse_vector< Val, SV >::set_null | ( | size_type | idx | ) |
set specified element to NULL RSC vector actually erases element when it is set to NULL (expensive).
idx | - element index |
Definition at line 560 of file bmsparsevec_compr.h.
References BM_ASSERT.
|
inlineprotected |
Definition at line 438 of file bmsparsevec_compr.h.
rsc_sparse_vector< Val, SV >::size_type bm::rsc_sparse_vector< Val, SV >::size |
return size of the vector
Definition at line 522 of file bmsparsevec_compr.h.
|
inlineprotected |
Definition at line 432 of file bmsparsevec_compr.h.
|
inlinestatic |
Number of stored bit-plains (value plains + extra.
Definition at line 396 of file bmsparsevec_compr.h.
|
inline |
Re-calculate prefix sum table used for rank search (if necessary)
Definition at line 360 of file bmsparsevec_compr.h.
References bm::rsc_sparse_vector< Val, SV >::sync().
Referenced by bm::rsc_sparse_vector< Val, SV >::sync().
void bm::rsc_sparse_vector< Val, SV >::sync | ( | bool | force | ) |
Re-calculate prefix sum table used for rank search.
force | - force recalculation even if it is already recalculated |
Definition at line 691 of file bmsparsevec_compr.h.
References BM_ASSERT.
|
inline |
Unsync the prefix sum table.
Definition at line 370 of file bmsparsevec_compr.h.
|
friend |
Definition at line 450 of file bmsparsevec_compr.h.
Definition at line 448 of file bmsparsevec_compr.h.
Definition at line 449 of file bmsparsevec_compr.h.
const typedef bvector_type* bm::rsc_sparse_vector< Val, SV >::bvector_type_const_ptr |
Definition at line 74 of file bmsparsevec_compr.h.
const typedef value_type& bm::rsc_sparse_vector< Val, SV >::const_reference |
Definition at line 68 of file bmsparsevec_compr.h.