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

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

#include <bmsparsevec.h>

Inheritance diagram for bm::sparse_vector< Val, BV >:
Inheritance graph
[legend]
Collaboration diagram for bm::sparse_vector< Val, BV >:
Collaboration 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...
 
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_typebvector_type_ptr
 
typedef bvector_type::size_type size_type
 
typedef bvector_type::block_idx_type block_idx_type
 
typedef const bvector_typebvector_type_const_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
 
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_typebvector_type_ptr
 
typedef const bvector_typebvector_type_const_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
 
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_typeget_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_typeget_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_typeget_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_typeget_bmatrix () const BMNOEXCEPT
  More...
 
bmatrix_typeget_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_typeremap_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_typeget_remap_matrix () const
 
remap_matrix_typeget_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...
 

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
 

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

Detailed Description

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

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

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

Container supports both signed and unsigned integer types.

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

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

Examples
inv_list.cpp, rscsample01.cpp, rscsample02.cpp, rscsample03.cpp, rscsample04.cpp, rscsample05.cpp, rscsample06.cpp, svsample01.cpp, svsample02.cpp, svsample03.cpp, svsample04.cpp, svsample05.cpp, svsample06.cpp, svsample07.cpp, svsample07a.cpp, svsample08.cpp, svsample09.cpp, svsample10.cpp, xsample01.cpp, xsample02.cpp, xsample03.cpp, xsample06.cpp, xsample07.cpp, xsample08.cpp, and xsample09.cpp.

Definition at line 86 of file bmsparsevec.h.

Member Typedef Documentation

◆ remap_matrix_type

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

unused remap matrix type for compatibility with the sparse serializer

Definition at line 1017 of file bmsparsevec.h.

Member Enumeration Documentation

◆ buf_size_e

template<class Val , class BV >
enum bm::sparse_vector::buf_size_e
protected
Enumerator
n_buf_size 

Definition at line 976 of file bmsparsevec.h.

◆ octet_slices

template<class Val , class BV >
enum bm::sparse_vector::octet_slices
protected
Enumerator
sv_octet_slices 

Definition at line 972 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<> container
bm::bvector<>::allocation_policy
bm::startegy

Definition at line 1082 of file bmsparsevec.h.

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

Member Function Documentation

◆ at()

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

access specified element with bounds checking

Parameters
idx- element index
Returns
value of the element
Examples
svsample03.cpp.

Definition at line 1730 of file bmsparsevec.h.

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

◆ begin()

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

Provide const iterator access to container content

Examples
svsample01.cpp.

Definition at line 2256 of file bmsparsevec.h.

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

◆ calc_stat()

template<class Val , class BV >
void bm::sparse_vector< Val, BV >::calc_stat ( struct sparse_vector< Val, BV >::statistics st) const

Calculates memory statistics.

Function fills statistics structure containing information about how this vector uses memory and estimation of max. amount of memory bvector needs to serialize itself.

Parameters
st- pointer on statistics structure to be filled in.
See also
statistics

Definition at line 2078 of file bmsparsevec.h.

References BM_ASSERT.

Referenced by main().

◆ clear() [1/3]

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

resize to zero, free memory

Definition at line 690 of file bmsparsevec.h.

References bm::sparse_vector< Val, BV >::clear_all().

◆ clear() [2/3]

template<class Val , class BV >
void bm::sparse_vector< Val, BV >::clear ( const bvector_type bv_idx)
inline

Set vector elements spcified by argument bit-vector to zero Note that set to 0 elements are NOT going to tuned to NULL (NULL qualifier is preserved)

Parameters
bv_idx- index bit-vector for elements which to be set to 0

Definition at line 545 of file bmsparsevec.h.

References bm::base_sparse_vector< Val, BV, 1 >::bit_sub_rows().

◆ clear() [3/3]

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

clear specified element with bounds checking and automatic resize

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

Definition at line 1820 of file bmsparsevec.h.

Referenced by main().

◆ clear_all()

template<class Val , class BV >
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=().

◆ clear_range()

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

clear range (assign bit 0 for all planes)

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

Definition at line 2066 of file bmsparsevec.h.

◆ compare()

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

Compare vector element with argument.

Parameters
idx- vactor element index
val- argument to compare with
Returns
0 - equal, < 0 - vect[i] < val, >0 otherwise

Definition at line 2235 of file bmsparsevec.h.

◆ copy_range()

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

copy range of values from another sparse vector

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

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

Definition at line 2194 of file bmsparsevec.h.

References bm::sparse_vector< Val, BV >::size(), and bm::xor_swap().

◆ decode()

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

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

For efficiency, this is left as a low level function, it does not do any bounds checking on the target array, it will override memory and crash if you are not careful with allocation and request size.

Parameters
arr- dest array
idx_from- index in the sparse vector to export from
dec_size- decoding size (array allocation should match)
zero_mem- set to false if target array is pre-initialized with 0s to avoid performance penalty
Returns
number of actually exported elements (can be less than requested)
See also
gather
Examples
svsample03.cpp.

Definition at line 1338 of file bmsparsevec.h.

Referenced by main().

◆ effective_size()

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

size of sparse vector (may be different for RSC)

Definition at line 957 of file bmsparsevec.h.

References bm::sparse_vector< Val, BV >::size().

◆ effective_vector_max()

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

Always 1 (non-matrix type)

Definition at line 962 of file bmsparsevec.h.

◆ empty()

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

return true if vector is empty

Returns
true if empty

Definition at line 716 of file bmsparsevec.h.

References bm::sparse_vector< Val, BV >::size().

Referenced by main(), and run_benchmark().

◆ end()

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

Provide const iterator access to the end

Examples
svsample01.cpp.

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().

◆ equal()

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

check if another sparse vector has the same content and size

Parameters
sv- sparse vector for comparison
null_able- flag to consider NULL vector in comparison (default) or compare only value content planes
Returns
true, if it is the same

Definition at line 2246 of file bmsparsevec.h.

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

◆ erase()

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

erase specified element from container

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

Definition at line 1919 of file bmsparsevec.h.

References BM_ASSERT.

◆ extract()

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

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

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

Parameters
arr- dest array
size- dest size
offset- target index in the sparse vector to export from
zero_mem- set to false if target array is pre-initialized with 0s to avoid performance penalty
Returns
effective size(number) of exported elements
See also
decode

Decoder functor

< target array for de-transpose

< bit-plane mask

< SV read offset

Definition at line 1643 of file bmsparsevec.h.

References BM_ASSERT, BMNOEXCEPT, BMNOEXCEPT2, BMRESTRICT, and bm::for_each_bit_range_no_check().

◆ extract_planes()

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

extract medium window without use of masking vector

See also
decode

Definition at line 1601 of file bmsparsevec.h.

◆ 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

◆ filter()

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

Apply value filter, defined by mask vector.

All bit-planes are ANDed against the filter mask.

Definition at line 2221 of file bmsparsevec.h.

◆ find_rank()

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

find position of compressed element by its rank

Definition at line 2055 of file bmsparsevec.h.

References BM_ASSERT.

◆ freeze()

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

Turn sparse vector into immutable mode Read-only (immutable) vector uses less memory and allows faster searches.

Before freezing it is recommenede to call optimize() to get full memory saving effect

See also
optimize

Definition at line 807 of file bmsparsevec.h.

References bm::base_sparse_vector< Val, BV, 1 >::freeze_matr().

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

◆ get()

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

get specified element without bounds checking

Parameters
idx- element index
Returns
value of the element

Definition at line 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().

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

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

References bm::sparse_vector< Val, BV >::const_iterator::const_iterator().

◆ get_no_check()

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

get specified element without checking boundary conditions

Parameters
idx- element index
Returns
value of the element

Definition at line 1752 of file bmsparsevec.h.

◆ get_unsigned()

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

Definition at line 1766 of file bmsparsevec.h.

References BM_ASSERT, and bm::id_max.

◆ import()

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

Import list of elements from a C-style array.

Parameters
arr- source array
arr_size- source size
offset- target index in the sparse vector
set_not_null- import should register in not null vector
Examples
svsample01.cpp, and svsample03.cpp.

Definition at line 1154 of file bmsparsevec.h.

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

◆ import_back()

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

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

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

Definition at line 1294 of file bmsparsevec.h.

◆ import_back_u()

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

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

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

Definition at line 1327 of file bmsparsevec.h.

◆ import_u()

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

Import list of elements from a C-style array.

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

Definition at line 1187 of file bmsparsevec.h.

◆ import_u_nocheck()

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

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

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

◆ inc_no_null() [1/2]

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

Increment element by 1 without chnaging NULL vector or size.

Definition at line 2015 of file bmsparsevec.h.

◆ inc_no_null() [2/2]

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

increment by v without chnaging NULL vector or size

Definition at line 2038 of file bmsparsevec.h.

◆ insert()

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

insert specified element into container

Parameters
idx- element index
v- element value

Definition at line 1860 of file bmsparsevec.h.

Referenced by insertion_sort().

◆ insert_value()

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

insert value without checking boundaries

Definition at line 1874 of file bmsparsevec.h.

◆ insert_value_no_null()

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

insert value without checking boundaries or support of NULL

Definition at line 1883 of file bmsparsevec.h.

References bm::bit_scan_reverse(), and BM_ASSERT.

◆ is_compressed()

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

various type traits

Definition at line 584 of file bmsparsevec.h.

◆ is_ro()

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

Returns true if vector is read-only.

Definition at line 810 of file bmsparsevec.h.

References bm::base_sparse_vector< Val, BV, 1 >::is_ro_.

◆ join()

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

join all with another sparse vector using OR operation

Parameters
sv- argument vector to join with
Returns
slf reference
See also
merge
Examples
svsample03.cpp.

Definition at line 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().

◆ join_null_slice()

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

◆ keep_range()

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

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

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

Definition at line 2209 of file bmsparsevec.h.

References bm::xor_swap().

◆ merge()

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

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

Parameters
sv- [in, out]argument vector to join with (vector mutates)
Returns
slf reference
See also
join

Definition at line 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().

◆ operator=() [1/2]

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

copy assignmment operator

Definition at line 405 of file bmsparsevec.h.

References bm::base_sparse_vector< Val, BV, 1 >::copy_from().

◆ operator=() [2/2]

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

move assignmment operator

Definition at line 416 of file bmsparsevec.h.

References bm::sparse_vector< Val, BV >::clear_all(), and bm::sparse_vector< Val, BV >::swap().

◆ operator[]() [1/2]

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

Operator to get write access to an element

Definition at line 435 of file bmsparsevec.h.

◆ operator[]() [2/2]

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

get specified element without bounds checking

Parameters
idx- element index
Returns
value of the element

Definition at line 443 of file bmsparsevec.h.

References bm::sparse_vector< Val, BV >::get().

◆ optimize()

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

run memory optimization for all vector planes

Parameters
temp_block- pre-allocated memory block to avoid unnecessary re-allocs
opt_mode- requested compression depth
stat- memory allocation statistics after optimization
Examples
svsample01.cpp, and svsample03.cpp.

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().

◆ optimize_gap_size()

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

Optimize sizes of GAP blocks.

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

Definition at line 2113 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
Examples
svsample04.cpp.

Definition at line 1838 of file bmsparsevec.h.

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

◆ push_back_no_null()

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

push value back into vector without NULL semantics

Definition at line 1932 of file bmsparsevec.h.

◆ push_back_null() [1/2]

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

push back NULL value

Definition at line 504 of file bmsparsevec.h.

References bm::sparse_vector< Val, BV >::push_back_null().

Referenced by bm::sparse_vector< Val, BV >::push_back_null().

◆ push_back_null() [2/2]

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

push back specified amount of NULL values

Parameters
count- number of NULLs to push back

Definition at line 1847 of file bmsparsevec.h.

References BM_ASSERT, and bm::id_max.

◆ resize()

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

resize vector

Parameters
sz- new size

Definition at line 721 of file bmsparsevec.h.

References bm::base_sparse_vector< Val, BV, 1 >::resize().

Referenced by main().

◆ resize_internal()

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

◆ set()

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

set specified element with bounds checking and automatic resize

Parameters
idx- element index
v- element value
Examples
svsample03.cpp.

Definition at line 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().

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

◆ set_null() [1/2]

template<class Val , class BV >
void bm::sparse_vector< Val, BV >::set_null ( const bvector_type bv_idx)
inline

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

Function also clears all the values to 0.

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

Definition at line 537 of file bmsparsevec.h.

References bm::base_sparse_vector< Val, BV, 1 >::bit_sub_rows().

◆ set_null() [2/2]

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

set specified element to unassigned value (NULL)

Parameters
idx- element index

Definition at line 1146 of file bmsparsevec.h.

Referenced by main(), and bm::sparse_vector< Val, BV >::resize_internal().

◆ set_value()

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

set value without checking boundaries

Definition at line 1941 of file bmsparsevec.h.

◆ set_value_no_null()

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

set value without checking boundaries or support of NULL

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

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

◆ size()

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

◆ size_internal()

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

Definition at line 1003 of file bmsparsevec.h.

References bm::sparse_vector< Val, BV >::size().

◆ swap()

template<class Val , class BV >
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=().

◆ sync()

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

syncronize internal structures, build fast access index

Definition at line 884 of file bmsparsevec.h.

◆ sync_size()

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

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

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

◆ throw_range_error()

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

throw range error

Definition at line 1126 of file bmsparsevec.h.

References BM_ASSERT_THROW.

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

◆ try_get()

template<class Val , class BV >
bool bm::sparse_vector< Val, BV >::try_get ( size_type  idx,
value_type v 
) const

get specified element with NOT NULL check

Parameters
idx- element index
v- [out] value to get
Returns
true if value was aquired (NOT NULL), false otherwise
See also
is_null, get

Definition at line 1791 of file bmsparsevec.h.


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