BitMagic-C++
|
Rank-Select compressed sparse vector. More...
#include <bmsparsevec_compr.h>
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 rsc sparse vector. More... | |
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 |
typedef SV::bmatrix_type | bmatrix_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) BMNOEXCEPT | |
rsc_sparse_vector< Val, SV > & | operator= (rsc_sparse_vector< Val, SV > &&csv) BMNOEXCEPT |
Size, etc | |
| |
size_type | size () const BMNOEXCEPT |
return size of the vector 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 BMNOEXCEPT |
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 BMNOEXCEPT |
test if specified element is NULL More... | |
const bvector_type * | get_null_bvector () const BMNOEXCEPT |
Get bit-vector of assigned values (or NULL) More... | |
bool | find_rank (size_type rank, size_type &idx) const BMNOEXCEPT |
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 |
C-style decode. More... | |
size_type | decode_buf (value_type *arr, value_type *arr_buf_tmp, size_type idx_from, size_type size, bool zero_mem=true) const BMNOEXCEPT |
C-style decode (variant with external memory) Analog of decode, but requires two arrays. More... | |
Comparison | |
bool | equal (const rsc_sparse_vector< Val, SV > &csv) const BMNOEXCEPT |
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... | |
Iterator access | |
const_iterator | begin () const BMNOEXCEPT |
Provide const iterator access to container content More... | |
const_iterator | end () const BMNOEXCEPT |
Provide const iterator access to the end More... | |
const_iterator | get_const_iterator (size_type idx) const BMNOEXCEPT |
Get const_itertor re-positioned to specific element. More... | |
back_insert_iterator | get_back_inserter () |
Memory optimization | |
| |
void | optimize (bm::word_t *temp_block=0, typename bvector_type::optmode opt_mode=bvector_type::opt_compress, statistics *stat=0) |
run memory optimization for all vector plains More... | |
void | clear () BMNOEXCEPT |
resize to zero, free memory More... | |
void | calc_stat (struct rsc_sparse_vector< Val, SV >::statistics *st) const BMNOEXCEPT |
Calculates memory statistics. More... | |
Merge, split, partition data | |
| |
void | copy_range (const rsc_sparse_vector< Val, SV > &csv, size_type left, size_type right) |
copy range of values from another sparse vector 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 BMNOEXCEPT |
returns true if prefix sum table is in sync with the vector More... | |
void | unsync () BMNOEXCEPT |
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 BMNOEXCEPT |
Resolve logical address to access via rank compressed address. More... | |
bool | resolve_range (size_type from, size_type to, size_type *idx_from, size_type *idx_to) const BMNOEXCEPT |
void | resize_internal (size_type sz) |
size_type | size_internal () const BMNOEXCEPT |
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 |
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 BMNOEXCEPT |
get access to bit-plain, function checks and creates a plain More... | |
bvector_type_ptr | get_plain (unsigned i) BMNOEXCEPT |
unsigned | effective_plains () const BMNOEXCEPT |
const sparse_vector_type & | get_sv () const BMNOEXCEPT |
access dense vector More... | |
size_type | effective_size () const BMNOEXCEPT |
size of internal dense vector More... | |
size_type | effective_vector_max () const BMNOEXCEPT |
Always 1 (non-matrix type) More... | |
const bmatrix_type & | get_bmatrix () const BMNOEXCEPT |
static unsigned | plains () BMNOEXCEPT |
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 SV::bmatrix_type bm::rsc_sparse_vector< Val, SV >::bmatrix_type |
Definition at line 79 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 683 of file bmsparsevec_compr.h.
enum bm::rsc_sparse_vector::vector_capacity |
Enumerator | |
---|---|
max_vector_size |
Definition at line 81 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 735 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 750 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 758 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 772 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 1040 of file bmsparsevec_compr.h.
|
inline |
Provide const iterator access to container content
Definition at line 534 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 1107 of file bmsparsevec_compr.h.
References BM_ASSERT.
void bm::rsc_sparse_vector< Val, SV >::clear | ( | ) |
resize to zero, free memory
Definition at line 1098 of file bmsparsevec_compr.h.
Referenced by bm::rsc_sparse_vector< Val, SV >::operator=().
void bm::rsc_sparse_vector< Val, SV >::copy_range | ( | const rsc_sparse_vector< Val, SV > & | csv, |
size_type | left, | ||
size_type | right | ||
) |
copy range of values from another sparse vector
Copy [left..right] values from the source vector, clear everything outside the range.
csv | - source vector |
left | - index from in losed diapason of [left..right] |
right | - index to in losed diapason of [left..right] |
Definition at line 1290 of file bmsparsevec_compr.h.
References bm::no_null, bm::rsc_sparse_vector< Val, SV >::resolve_range(), bm::rsc_sparse_vector< Val, SV >::size(), and bm::xor_swap().
rsc_sparse_vector< Val, SV >::size_type bm::rsc_sparse_vector< Val, SV >::decode | ( | value_type * | arr, |
size_type | idx_from, | ||
size_type | size, | ||
bool | zero_mem = true |
||
) | const |
C-style decode.
arr | - decode target array (must be properly sized) |
idx_from | - start address to decode |
size | - number of elements to decode |
zero_mem | - flag if array needs to beset to zeros first |
Definition at line 1152 of file bmsparsevec_compr.h.
References BM_ASSERT, and bm::id_max.
rsc_sparse_vector< Val, SV >::size_type bm::rsc_sparse_vector< Val, SV >::decode_buf | ( | value_type * | arr, |
value_type * | arr_buf_tmp, | ||
size_type | idx_from, | ||
size_type | size, | ||
bool | zero_mem = true |
||
) | const |
C-style decode (variant with external memory) Analog of decode, but requires two arrays.
Faster than decode in many cases.
arr | - decode target array (must be properly sized) |
arr_buf_tmp | - decode temp bufer (must be same size of arr) |
idx_from | - start address to decode |
size | - number of elements to decode |
zero_mem | - flag if array needs to beset to zeros first |
Definition at line 1209 of file bmsparsevec_compr.h.
References BM_ASSERT, bm::id_max, and bm::bvector< Alloc >::enumerator::value().
|
inline |
Number of effective bit-plains in the value type
Definition at line 646 of file bmsparsevec_compr.h.
|
inline |
size of internal dense vector
Definition at line 667 of file bmsparsevec_compr.h.
|
inline |
Always 1 (non-matrix type)
Definition at line 672 of file bmsparsevec_compr.h.
|
inline |
return true if vector is empty
Definition at line 361 of file bmsparsevec_compr.h.
Referenced by main(), and run_benchmark().
|
inline |
Provide const iterator access to the end
Definition at line 538 of file bmsparsevec_compr.h.
References bm::id_max.
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 875 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 1134 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 1058 of file bmsparsevec_compr.h.
Referenced by bm::rsc_sparse_vector< Val, SV >::operator[](), and print_model().
|
inline |
Definition at line 547 of file bmsparsevec_compr.h.
References bm::rsc_sparse_vector< Val, SV >::back_insert_iterator::back_insert_iterator().
Referenced by main().
|
inline |
get read-only access to inetrnal bit-matrix
Definition at line 677 of file bmsparsevec_compr.h.
|
inline |
Get const_itertor re-positioned to specific element.
idx | - position in the sparse vector |
Definition at line 544 of file bmsparsevec_compr.h.
Referenced by main().
const rsc_sparse_vector< Val, SV >::bvector_type * bm::rsc_sparse_vector< Val, SV >::get_null_bvector | ( | ) | const |
Get bit-vector of assigned values (or NULL)
Definition at line 1125 of file bmsparsevec_compr.h.
|
inline |
Definition at line 640 of file bmsparsevec_compr.h.
|
inline |
get access to bit-plain, function checks and creates a plain
Definition at line 637 of file bmsparsevec_compr.h.
|
inlineprotected |
Definition at line 706 of file bmsparsevec_compr.h.
|
inline |
access dense vector
Definition at line 662 of file bmsparsevec_compr.h.
|
inline |
returns true if prefix sum table is in sync with the vector
Definition at line 621 of file bmsparsevec_compr.h.
|
inlineprotected |
Definition at line 707 of file bmsparsevec_compr.h.
|
inlinestatic |
trait if sparse vector is "compressed" (true)
Definition at line 492 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 1071 of file bmsparsevec_compr.h.
References BM_ASSERT.
Referenced by set_feature_strand().
|
inline |
if container supports NULL(unassigned) values (true)
Definition at line 487 of file bmsparsevec_compr.h.
|
inlineprotected |
Definition at line 704 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 889 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 930 of file bmsparsevec_compr.h.
References BM_ASSERT, and bm::rank_compressor< BV >::decompress().
Referenced by main().
|
inline |
copy assignmment operator
Definition at line 312 of file bmsparsevec_compr.h.
|
inline |
move assignmment operator
Definition at line 332 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 374 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 1081 of file bmsparsevec_compr.h.
Referenced by main().
|
inlinestatic |
get total number of bit-plains in the vector
Definition at line 652 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 798 of file bmsparsevec_compr.h.
|
protected |
Definition at line 813 of file bmsparsevec_compr.h.
References BM_ASSERT.
|
inlineprotected |
Definition at line 705 of file bmsparsevec_compr.h.
|
inlineprotected |
Definition at line 701 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 988 of file bmsparsevec_compr.h.
References BM_ASSERT.
|
protected |
Definition at line 1008 of file bmsparsevec_compr.h.
References BM_ASSERT.
Referenced by bm::rsc_sparse_vector< Val, SV >::copy_range().
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 847 of file bmsparsevec_compr.h.
References BM_ASSERT.
Referenced by set_feature_strand().
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 829 of file bmsparsevec_compr.h.
References BM_ASSERT.
|
inlineprotected |
Definition at line 708 of file bmsparsevec_compr.h.
rsc_sparse_vector< Val, SV >::size_type bm::rsc_sparse_vector< Val, SV >::size | ( | ) | const |
return size of the vector
Definition at line 790 of file bmsparsevec_compr.h.
Referenced by bm::rsc_sparse_vector< Val, SV >::copy_range().
|
inlineprotected |
Definition at line 702 of file bmsparsevec_compr.h.
|
inlinestatic |
Number of stored bit-plains (value plains + extra.
Definition at line 656 of file bmsparsevec_compr.h.
|
inline |
Re-calculate prefix sum table used for rank search (if necessary)
Definition at line 616 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 963 of file bmsparsevec_compr.h.
References BM_ASSERT.
Referenced by main().
|
inline |
Unsync the prefix sum table.
Definition at line 626 of file bmsparsevec_compr.h.
Definition at line 720 of file bmsparsevec_compr.h.
Definition at line 718 of file bmsparsevec_compr.h.
Definition at line 719 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.