BitMagic-C++
|
succinct sparse vector with runtime compression using bit-slicing / transposition method More...
#include <bmsparsevec.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 sparse vector. More... | |
struct | is_dynamic_splices |
struct | is_remap_support |
struct | is_rsc_support |
class | reference |
Reference class to access elements via common [] operator. More... | |
struct | statistics |
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 More... | |
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. More... | |
Construction and assignment <br> | |
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) | |
More... | |
sparse_vector< Val, BV > & | operator= (const sparse_vector< Val, BV > &sv) |
More... | |
sparse_vector (sparse_vector< Val, BV > &&sv) BMNOEXCEPT | |
More... | |
sparse_vector< Val, BV > & | operator= (sparse_vector< Val, BV > &&sv) BMNOEXCEPT |
More... | |
~sparse_vector () BMNOEXCEPT | |
Element access, editing <br> | |
reference | operator[] (size_type idx) BMNOEXCEPT |
Operator to get write access to an element More... | |
value_type | operator[] (size_type idx) const BMNOEXCEPT |
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... | |
value_type | get_no_check (size_type idx) const BMNOEXCEPT |
get specified element without checking boundary conditions More... | |
bool | try_get (size_type idx, value_type &v) const BMNOEXCEPT |
get specified element with NOT NULL check 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 | push_back_null (size_type count) |
push back specified amount of NULL values More... | |
void | push_back_null () |
push back NULL value More... | |
void | insert (size_type idx, value_type v) |
insert specified element into container More... | |
void | erase (size_type idx, bool erase_null=true) |
erase specified element from container More... | |
void | clear (size_type idx, bool set_null) |
clear specified element with bounds checking and automatic resize More... | |
void | set_null (size_type idx) |
set specified element to unassigned value (NULL) More... | |
void | set_null (const bvector_type &bv_idx) |
Set NULL all elements set as 1 in the argument vector. More... | |
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) 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 () |
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 <br> | |
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. More... | |
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) More... | |
Export content to C-style array <br> | |
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. 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 <br> | |
void | clear_all (bool free_mem) BMNOEXCEPT |
resize to zero, free memory More... | |
void | clear () BMNOEXCEPT |
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 planes) More... | |
Size, etc <br> | |
size_type | size () const BMNOEXCEPT |
return size of the vector More... | |
bool | empty () const BMNOEXCEPT |
return true if vector is empty More... | |
void | resize (size_type sz) |
resize vector More... | |
void | sync_size () BMNOEXCEPT |
recalculate size to exclude tail NULL elements After this call size() will return the true size of the vector More... | |
Comparison <br> | |
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 More... | |
Element comparison <br> | |
int | compare (size_type idx, const value_type val) const BMNOEXCEPT |
Compare vector element with argument. More... | |
Memory optimization <br> | |
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 More... | |
void | optimize_gap_size () |
Optimize sizes of GAP blocks. More... | |
void | calc_stat (struct sparse_vector< Val, BV >::statistics *st) const BMNOEXCEPT |
Calculates memory statistics. More... | |
void | freeze () |
Turn sparse vector into immutable mode Read-only (immutable) vector uses less memory and allows faster searches. More... | |
bool | is_ro () const BMNOEXCEPT |
Returns true if vector is read-only. More... | |
Merge, split, partition data <br> | |
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, bm::null_support slice_null=bm::use_null) |
copy range of values from another sparse vector More... | |
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. More... | |
void | filter (const bvector_type &bv_mask) |
Apply value filter, defined by mask vector. More... | |
Public Member Functions inherited from bm::base_sparse_vector< Val, BV, 1 > | |
base_sparse_vector () | |
base_sparse_vector (bm::null_support null_able, 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 | |
More... | |
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 More... | |
bool | empty () const BMNOEXCEPT |
More... | |
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 More... | |
void | calc_stat (typename bvector_type::statistics *st) const BMNOEXCEPT |
Calculates memory statistics. More... | |
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 More... | |
bool | is_nullable () const BMNOEXCEPT |
check if container supports NULL(unassigned) values More... | |
bm::null_support | get_null_support () const BMNOEXCEPT |
check if container supports NULL (unassigned) values More... | |
const bvector_type * | get_null_bvector () const BMNOEXCEPT |
Get bit-vector of assigned values or NULL (if not constructed that way) More... | |
bool | is_null (size_type idx) const BMNOEXCEPT |
test if specified element is NULL More... | |
void | set_allocator_pool (allocator_pool_type *pool_ptr) BMNOEXCEPT |
Set allocation pool. More... | |
allocator_pool_type * | get_allocator_pool () const BMNOEXCEPT |
Get allocation pool. More... | |
bvector_type_ptr | get_create_slice (unsigned i) |
get access to bit-plain, function checks and creates a plane More... | |
bvector_type_const_ptr | get_slice (unsigned i) const BMNOEXCEPT |
get read-only access to bit-plane More... | |
unsigned | effective_slices () const BMNOEXCEPT |
Number of effective bit-planes in the value type. More... | |
bvector_type_ptr | slice (unsigned i) BMNOEXCEPT |
get access to bit-plane as is (can return NULL) More... | |
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 More... | |
bm::id64_t | get_slice_mask (unsigned element_idx) const BMNOEXCEPT |
More... | |
const bmatrix_type & | get_bmatrix () const BMNOEXCEPT |
More... | |
bmatrix_type & | get_bmatrix () BMNOEXCEPT |
access to internal bit-matrix More... | |
void | mark_null_idx (unsigned null_idx) BMNOEXCEPT |
Set NULL plain index. More... | |
Static Public Member Functions | |
Various traits <br> | |
static constexpr bool | is_compressed () BMNOEXCEPT |
various type traits More... | |
static constexpr bool | is_str () BMNOEXCEPT |
Static Public Member Functions inherited from bm::base_sparse_vector< Val, BV, 1 > | |
static constexpr bool | is_signed () BMNOEXCEPT |
returns true if value type is signed integral type More... | |
static unsigned | slices () BMNOEXCEPT |
get total number of bit-planes in the vector More... | |
static unsigned | stored_slices () BMNOEXCEPT |
Number of stored bit-planes (value planes + extra. More... | |
static unsigned_value_type | s2u (value_type v) BMNOEXCEPT |
Convert signed value type to unsigned representation. More... | |
static value_type | u2s (unsigned_value_type v) BMNOEXCEPT |
Convert unsigned value type to signed representation. More... | |
Data Fields | |
friend | const_iterator |
friend | back_insert_iterator |
More... | |
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 More... | |
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 More... | |
void | set_value_no_null (size_type idx, value_type v, bool need_clear) |
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... | |
void | insert_value (size_type idx, value_type v) |
insert value without checking boundaries More... | |
void | insert_value_no_null (size_type idx, value_type v) |
insert value without checking boundaries or support of NULL More... | |
void | resize_internal (size_type sz, bool set_null=true) |
More... | |
size_type | size_internal () const BMNOEXCEPT |
More... | |
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. More... | |
void | inc_no_null (size_type idx, value_type v) |
increment by v without chnaging NULL vector or size More... | |
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) More... | |
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. More... | |
void | import_u_nocheck (const unsigned_value_type *arr, size_type arr_size, size_type offset, bool set_not_null) |
More... | |
void | join_null_slice (const sparse_vector< Val, BV > &sv) |
More... | |
unsigned_value_type | get_unsigned (size_type idx) const BMNOEXCEPT |
More... | |
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. More... | |
void | freeze_matr () |
Turn on RO mode. More... | |
void | clear_value_planes_from (unsigned plane_idx, size_type idx) |
More... | |
void | insert_clear_value_planes_from (unsigned plane_idx, size_type idx) |
More... | |
void | erase_column (size_type idx, bool erase_null) |
More... | |
void | insert_null (size_type idx, bool not_null) |
More... | |
void | bit_sub_rows (const bvector_type &bv, bool use_null) |
Set SUB (MINUS) operation on all existing bit-slices. More... | |
void | bit_and_rows (const bvector_type &bv) |
Set AND (intersect) operation on all existing bit-slices. More... | |
void | optimize_block (block_idx_type nb, typename BV::optmode opt_mode) |
plane index for the "NOT NULL" flags plane More... | |
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. More... | |
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. More... | |
Access to internals <br> | |
void | sync (bool) |
syncronize internal structures, build fast access index More... | |
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. 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_planes (value_type *arr, size_type size, size_type offset, bool zero_mem=true) const |
extract medium window without use of masking vector More... | |
size_type | effective_size () const BMNOEXCEPT |
size of sparse vector (may be different for RSC) More... | |
size_type | effective_vector_max () const BMNOEXCEPT |
Always 1 (non-matrix type) More... | |
static size_type | translate_address (size_type i) BMNOEXCEPT |
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... | |
static bool | find_rank (size_type rank, size_type &pos) BMNOEXCEPT |
find position of compressed element by its rank More... | |
Additional Inherited Members | |
Protected Attributes inherited from bm::base_sparse_vector< Val, BV, 1 > | |
bmatrix_type | bmatr_ |
bit-transposed matrix More... | |
unsigned_value_type | slice_mask_ |
slice presence bit-mask More... | |
size_type | size_ |
array size More... | |
unsigned | effective_slices_ |
number of bit slices actually allocated More... | |
bool | is_ro_ |
read-only More... | |
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.
|
protected |
unused remap matrix type for compatibility with the sparse serializer
Definition at line 1017 of file bmsparsevec.h.
|
protected |
Enumerator | |
---|---|
n_buf_size |
Definition at line 976 of file bmsparsevec.h.
|
protected |
Enumerator | |
---|---|
sv_octet_slices |
Definition at line 972 of file bmsparsevec.h.
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.
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 |
Definition at line 1082 of file bmsparsevec.h.
bm::sparse_vector< Val, BV >::sparse_vector | ( | const sparse_vector< Val, BV > & | sv | ) |
copy-ctor
Definition at line 1093 of file bmsparsevec.h.
bm::sparse_vector< Val, BV >::sparse_vector | ( | sparse_vector< Val, BV > && | sv | ) |
move-ctor
Definition at line 1101 of file bmsparsevec.h.
sparse_vector< Val, BV >::value_type bm::sparse_vector< Val, BV >::at | ( | size_type | idx | ) | const |
access specified element with bounds checking
idx | - element index |
Definition at line 1730 of file bmsparsevec.h.
Referenced by Demo1(), main(), and print_svector().
sparse_vector< Val, BV >::const_iterator bm::sparse_vector< Val, BV >::begin |
Provide const iterator access to container content
Definition at line 2256 of file bmsparsevec.h.
Referenced by build_vector_pairs(), compare_sv_it(), Demo1(), Demo2(), and main().
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.
st | - pointer on statistics structure to be filled in. |
Definition at line 2078 of file bmsparsevec.h.
References BM_ASSERT.
Referenced by main().
|
inline |
resize to zero, free memory
Definition at line 690 of file bmsparsevec.h.
References bm::sparse_vector< Val, BV >::clear_all().
|
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)
bv_idx | - index bit-vector for elements which to be set to 0 |
Definition at line 545 of file bmsparsevec.h.
References bm::base_sparse_vector< Val, BV, 1 >::bit_sub_rows().
void bm::sparse_vector< Val, BV >::clear | ( | size_type | idx, |
bool | set_null | ||
) |
clear specified element with bounds checking and automatic resize
idx | - element index |
set_null | - if true the value receives NULL (unassigned) value |
Definition at line 1820 of file bmsparsevec.h.
Referenced by main().
void bm::sparse_vector< Val, BV >::clear_all | ( | bool | free_mem | ) |
resize to zero, free memory
Definition at line 2047 of file bmsparsevec.h.
Referenced by bm::sparse_vector< Val, BV >::clear(), and bm::sparse_vector< Val, BV >::operator=().
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)
left | - interval start |
right | - interval end (closed interval) |
set_null | - set cleared values to unassigned (NULL) |
Definition at line 2066 of file bmsparsevec.h.
int bm::sparse_vector< Val, BV >::compare | ( | size_type | idx, |
const value_type | val | ||
) | const |
Compare vector element with argument.
idx | - vactor element index |
val | - argument to compare with |
Definition at line 2235 of file bmsparsevec.h.
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.
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 2194 of file bmsparsevec.h.
References bm::sparse_vector< Val, BV >::size(), and bm::xor_swap().
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.
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 |
Definition at line 1338 of file bmsparsevec.h.
Referenced by main().
|
inline |
size of sparse vector (may be different for RSC)
Definition at line 957 of file bmsparsevec.h.
References bm::sparse_vector< Val, BV >::size().
|
inline |
Always 1 (non-matrix type)
Definition at line 962 of file bmsparsevec.h.
|
inline |
return true if vector is empty
Definition at line 716 of file bmsparsevec.h.
References bm::sparse_vector< Val, BV >::size().
Referenced by main(), and run_benchmark().
|
inline |
Provide const iterator access to the end
Definition at line 559 of file bmsparsevec.h.
References bm::sparse_vector< Val, BV >::const_iterator::const_iterator(), and bm::id_max.
Referenced by build_vector_pairs(), Demo1(), Demo2(), and main().
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
sv | - sparse vector for comparison |
null_able | - flag to consider NULL vector in comparison (default) or compare only value content planes |
Definition at line 2246 of file bmsparsevec.h.
void bm::sparse_vector< Val, BV >::erase | ( | size_type | idx, |
bool | erase_null = true |
||
) |
erase specified element from container
idx | - element index |
erase_null | - erase the NULL vector (if exists) (default: true) |
Definition at line 1919 of file bmsparsevec.h.
References BM_ASSERT.
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.
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 |
Decoder functor
< target array for de-transpose
< bit-plane mask
< SV read offset
Definition at line 1643 of file bmsparsevec.h.
References BM_ASSERT, BMNOEXCEPT, BMNOEXCEPT2, BMRESTRICT, and bm::for_each_bit_range_no_check().
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
Definition at line 1601 of file bmsparsevec.h.
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
Definition at line 1516 of file bmsparsevec.h.
References BM_ASSERT, BM_IS_GAP, BMGAP_PTR, FULL_BLOCK_FAKE_ADDR, bm::gap_test_unr(), IS_FULL_BLOCK, bm::set_array_mask, bm::set_array_shift, bm::set_block_mask, bm::set_block_shift, bm::set_word_mask, and bm::set_word_shift.
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 2221 of file bmsparsevec.h.
|
static |
find position of compressed element by its rank
Definition at line 2055 of file bmsparsevec.h.
References BM_ASSERT.
|
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
Definition at line 807 of file bmsparsevec.h.
References bm::base_sparse_vector< Val, BV, 1 >::freeze_matr().
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.
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. |
Definition at line 1350 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, BMGAP_PTR, FULL_BLOCK_FAKE_ADDR, bm::gap_bfind(), bm::gap_test_unr(), bm::id_max, bm::idx_arr_block_lookup_u32(), bm::idx_arr_block_lookup_u64(), bm::set_array_mask, bm::set_array_shift, bm::set_block_mask, and bm::set_block_shift.
sparse_vector< Val, BV >::value_type bm::sparse_vector< Val, BV >::get | ( | size_type | idx | ) | const |
get specified element without bounds checking
idx | - element index |
Definition at line 1741 of file bmsparsevec.h.
References BM_ASSERT.
Referenced by counting_sort_naive(), sparse_vect_index::get_vector(), bm::sparse_vector< Val, BV >::operator[](), print_sorted(), raw_data_size(), and test_data().
|
inline |
Provide back insert iterator Back insert iterator implements buffered insertion, which is faster, than random access or push_back.
Definition at line 572 of file bmsparsevec.h.
References bm::sparse_vector< Val, BV >::back_insert_iterator.
Referenced by compute_historgam(), generate_DNA_vector(), generate_test_set(), main(), write_as_rsc_svector(), and write_as_svector().
|
inline |
Get const_itertor re-positioned to specific element.
idx | - position in the sparse vector |
Definition at line 565 of file bmsparsevec.h.
References bm::sparse_vector< Val, BV >::const_iterator::const_iterator().
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
idx | - element index |
Definition at line 1752 of file bmsparsevec.h.
|
protected |
Definition at line 1766 of file bmsparsevec.h.
References BM_ASSERT, and bm::id_max.
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.
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 1154 of file bmsparsevec.h.
Referenced by convert_bv2sv(), Demo1(), Demo2(), and main().
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)
arr | - source array |
arr_size | - source array size |
set_not_null | - import should register in not null vector |
Definition at line 1294 of file bmsparsevec.h.
|
protected |
Import list of elements from a C-style array (pushed back)
arr | - source array |
arr_size | - source array size |
set_not_null | - import should register in not null vector |
Definition at line 1327 of file bmsparsevec.h.
|
protected |
Import list of elements from a C-style array.
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 1187 of file bmsparsevec.h.
|
protected |
Definition at line 1204 of file bmsparsevec.h.
References bm::bitscan(), BM_ASSERT, bm::tmatrix< T, ROWS, COLS >::row(), and bm::tmatrix< T, ROWS, COLS >::rows().
void bm::sparse_vector< Val, BV >::inc | ( | size_type | idx | ) |
increment specified element by one
idx | - element index |
Definition at line 1998 of file bmsparsevec.h.
Referenced by counting_sort(), counting_sort_parallel(), and counting_sort_subbatch().
|
protected |
Increment element by 1 without chnaging NULL vector or size.
Definition at line 2015 of file bmsparsevec.h.
|
protected |
increment by v without chnaging NULL vector or size
Definition at line 2038 of file bmsparsevec.h.
void bm::sparse_vector< Val, BV >::insert | ( | size_type | idx, |
value_type | v | ||
) |
insert specified element into container
idx | - element index |
v | - element value |
Definition at line 1860 of file bmsparsevec.h.
Referenced by insertion_sort().
|
protected |
insert value without checking boundaries
Definition at line 1874 of file bmsparsevec.h.
|
protected |
insert value without checking boundaries or support of NULL
Definition at line 1883 of file bmsparsevec.h.
References bm::bit_scan_reverse(), and BM_ASSERT.
|
inlinestaticconstexpr |
various type traits
Definition at line 584 of file bmsparsevec.h.
|
inline |
Returns true if vector is read-only.
Definition at line 810 of file bmsparsevec.h.
References bm::base_sparse_vector< Val, BV, 1 >::is_ro_.
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
sv | - argument vector to join with |
Definition at line 2127 of file bmsparsevec.h.
References bm::base_sparse_vector< Val, BV, MAX_SIZE >::bmatr_, bm::base_sparse_vector< Val, BV, MAX_SIZE >::get_bmatrix(), bm::basic_bmatrix< BV >::row(), bm::basic_bmatrix< BV >::rows(), and bm::sparse_vector< Val, BV >::size().
Referenced by main().
|
protected |
Definition at line 2170 of file bmsparsevec.h.
References BM_ASSERT, bm::base_sparse_vector< Val, BV, MAX_SIZE >::bmatr_, bm::basic_bmatrix< BV >::get_null_idx(), bm::base_sparse_vector< Val, BV, MAX_SIZE >::is_nullable(), and bm::sparse_vector< Val, BV >::size().
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.
left | - interval start |
right | - interval end (closed interval) |
slice_null | - "use_null" copy range for NULL vector or not |
Definition at line 2209 of file bmsparsevec.h.
References bm::xor_swap().
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.
sv | - [in, out]argument vector to join with (vector mutates) |
Definition at line 2154 of file bmsparsevec.h.
References bm::base_sparse_vector< Val, BV, MAX_SIZE >::bmatr_, and bm::sparse_vector< Val, BV >::size().
Referenced by counting_sort_parallel().
|
inline |
copy assignmment operator
Definition at line 405 of file bmsparsevec.h.
References bm::base_sparse_vector< Val, BV, 1 >::copy_from().
|
inline |
move assignmment operator
Definition at line 416 of file bmsparsevec.h.
References bm::sparse_vector< Val, BV >::clear_all(), and bm::sparse_vector< Val, BV >::swap().
|
inline |
Operator to get write access to an element
Definition at line 435 of file bmsparsevec.h.
|
inline |
get specified element without bounds checking
idx | - element index |
Definition at line 443 of file bmsparsevec.h.
References bm::sparse_vector< Val, BV >::get().
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
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 2094 of file bmsparsevec.h.
References bm::bv_statistics::add(), and bm::bv_statistics::reset().
Referenced by compute_historgam(), convert_bv2sv(), Demo1(), Demo2(), generate_big_case(), main(), SDemo1(), SDemo2(), and write_as_svector().
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 2113 of file bmsparsevec.h.
void bm::sparse_vector< Val, BV >::push_back | ( | value_type | v | ) |
push value back into vector
v | - element value |
Definition at line 1838 of file bmsparsevec.h.
Referenced by generate_random_subset(), main(), and SDemo1().
|
protected |
push value back into vector without NULL semantics
Definition at line 1932 of file bmsparsevec.h.
|
inline |
push back NULL value
Definition at line 504 of file bmsparsevec.h.
References bm::sparse_vector< Val, BV >::push_back_null().
Referenced by bm::sparse_vector< Val, BV >::push_back_null().
void bm::sparse_vector< Val, BV >::push_back_null | ( | size_type | count | ) |
push back specified amount of NULL values
count | - number of NULLs to push back |
Definition at line 1847 of file bmsparsevec.h.
References BM_ASSERT, and bm::id_max.
|
inline |
resize vector
sz | - new size |
Definition at line 721 of file bmsparsevec.h.
References bm::base_sparse_vector< Val, BV, 1 >::resize().
Referenced by main().
|
inlineprotected |
Definition at line 1001 of file bmsparsevec.h.
References bm::base_sparse_vector< Val, BV, 1 >::resize(), and bm::sparse_vector< Val, BV >::set_null().
void bm::sparse_vector< Val, BV >::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 1804 of file bmsparsevec.h.
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().
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 2265 of file bmsparsevec.h.
|
inline |
Set NULL all elements set as 1 in the argument vector.
Function also clears all the values to 0.
bv_idx | - index bit-vector for elements which to be set to NULL |
Definition at line 537 of file bmsparsevec.h.
References bm::base_sparse_vector< Val, BV, 1 >::bit_sub_rows().
void bm::sparse_vector< Val, BV >::set_null | ( | size_type | idx | ) |
set specified element to unassigned value (NULL)
idx | - element index |
Definition at line 1146 of file bmsparsevec.h.
Referenced by main(), and bm::sparse_vector< Val, BV >::resize_internal().
|
protected |
set value without checking boundaries
Definition at line 1941 of file bmsparsevec.h.
|
protected |
set value without checking boundaries or support of NULL
idx | - element index |
v | - value to set |
need_clear | - if clear 0 bits is necessary (or not if vector is resized) |
Definition at line 1952 of file bmsparsevec.h.
References bm::bit_scan_reverse(), BM_ASSERT, bm::set_array_mask, bm::set_array_shift, and bm::set_block_shift.
|
inline |
return size of the vector
Definition at line 711 of file bmsparsevec.h.
References bm::base_sparse_vector< Val, BV, 1 >::size_.
Referenced by add_centromer_Ns(), compare_sv_it(), bm::sparse_vector< Val, BV >::copy_range(), Demo1(), Demo2(), bm::sparse_vector< Val, BV >::effective_size(), bm::sparse_vector< Val, BV >::empty(), bm::sparse_vector< Val, BV >::join(), bm::sparse_vector< Val, BV >::join_null_slice(), main(), bm::sparse_vector< Val, BV >::merge(), print_svector(), raw_data_size(), and bm::sparse_vector< Val, BV >::size_internal().
|
inlineprotected |
Definition at line 1003 of file bmsparsevec.h.
References bm::sparse_vector< Val, BV >::size().
void bm::sparse_vector< Val, BV >::swap | ( | sparse_vector< Val, BV > & | sv | ) |
content exchange
Definition at line 1118 of file bmsparsevec.h.
Referenced by bm::sparse_vector< Val, BV >::operator=().
|
inline |
syncronize internal structures, build fast access index
Definition at line 884 of file bmsparsevec.h.
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 1282 of file bmsparsevec.h.
|
static |
throw bad alloc
Definition at line 1138 of file bmsparsevec.h.
|
static |
|
inlinestatic |
address translation for this type of container
Definition at line 931 of file bmsparsevec.h.
bool bm::sparse_vector< Val, BV >::try_get | ( | size_type | idx, |
value_type & | v | ||
) | const |
get specified element with NOT NULL check
idx | - element index |
v | - [out] value to get |
Definition at line 1791 of file bmsparsevec.h.