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

Rank-Select compressed sparse vector. More...

#include <bmsparsevec_compr.h>

Inheritance diagram for bm::rsc_sparse_vector< Val, SV >:
Inheritance graph
[legend]

Data Structures

class  back_insert_iterator
 Back insert iterator implements buffered insert, faster than generic access assignment. More...
 
class  const_iterator
 Const iterator to traverse the rsc 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

enum  bit_slices { sv_slices = (sizeof(Val) * 8 + 1) , sv_value_slices = (sizeof(Val) * 8) }
 
enum  vector_capacity { max_vector_size = 1 }
 
typedef Val value_type
 
typedef const value_typeconst_reference
 
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_typebvector_type_ptr
 
typedef const bvector_typebvector_type_const_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
 
typedef SV::unsigned_value_type unsigned_value_type
 

Public Member Functions

Construction and assignment <br>
 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())
  More...
 
 rsc_sparse_vector (const bvector_type &bv_null)
 Contructor to pre-initialize the list of assigned (not NULL) elements. More...
 
 ~rsc_sparse_vector ()
 
 rsc_sparse_vector (const rsc_sparse_vector< Val, SV > &csv)
  More...
 
rsc_sparse_vector< Val, SV > & operator= (const rsc_sparse_vector< Val, SV > &csv)
  More...
 
 rsc_sparse_vector (rsc_sparse_vector< Val, SV > &&csv) BMNOEXCEPT
  More...
 
rsc_sparse_vector< Val, SV > & operator= (rsc_sparse_vector< Val, SV > &&csv) BMNOEXCEPT
  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 sync_size () BMNOEXCEPT
 recalculate size to exclude tail NULL elements After this call size() will return the true size of the vector More...
 
void resize (size_type new_size)
 change vector size More...
 
size_type count_range_notnull (size_type left, size_type right) const BMNOEXCEPT
  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...
 
bool try_get (size_type idx, value_type &v) const BMNOEXCEPT
 get specified element with NOT NULL check More...
 
bool try_get_sync (size_type idx, value_type &v) const BMNOEXCEPT
 get specified element with NOT NULL check Caller guarantees that the vector is in sync mode (RS-index access). More...
 
void push_back (size_type idx, value_type v)
 set specified element with bounds checking and automatic resize More...
 
void push_back (value_type v)
 add element with automatic resize 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 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 inc (size_type idx, value_type v)
 increment specified element by one More...
 
void inc_not_null (size_type idx, value_type v)
 increment specified element by one, element MUST be NOT NULL Faster than just inc() if element is NULL - behavior is undefined 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...
 
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...
 
bool is_null (size_type idx) const BMNOEXCEPT
 test if specified element is NULL More...
 
const bvector_typeget_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 <br>
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...
 
size_type gather (value_type *arr, const size_type *idx, size_type *idx_tmp_buf, size_type size, bm::sort_order sorted_idx) const
 Gather elements to a C-style array. 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
 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 ()
  More...
 
Memory optimization <br>
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 slices More...
 
void clear_all (bool free_mem) BMNOEXCEPT
 resize to zero, free memory 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...
 
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>
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...
 
void merge_not_null (rsc_sparse_vector< Val, SV > &csv)
 merge two vectors (argument gets destroyed) It is important that both vectors have the same NULL vectors More...
 
Fast access structues sync <br>
void sync (bool force)
 Re-calculate rank-select index for faster access to vector. 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...
 
bool is_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...
 

Protected Types

enum  octet_slices { sv_octet_slices = sizeof(value_type) }
 
typedef bm::heap_matrix< unsigned char, 1, 1, typename bvector_type::allocator_typeremap_matrix_type
 unused remap matrix type for compatibility with the sparse serializer More...
 

Protected Member Functions

bool resolve_sync (size_type idx, size_type *idx_to) const BMNOEXCEPT
  More...
 
bool resolve_range (size_type from, size_type to, size_type *idx_from, size_type *idx_to) const BMNOEXCEPT
  More...
 
void resize_internal (size_type sz)
 
size_type size_internal () const BMNOEXCEPT
 
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 ()
 
void push_back_no_check (size_type idx, value_type v)
  More...
 

Static Protected Member Functions

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
 

Friends

template<class SVect >
class sparse_vector_scanner
 
template<class SVect >
class sparse_vector_serializer
 
template<class SVect >
class sparse_vector_deserializer
 
template<class SVect >
class sparse_vector_scanner
 

Various traits <br>

bool is_nullable () const
 if container supports NULL(unassigned) values (true) More...
 
static constexpr bool is_compressed () BMNOEXCEPT
 various type traits More...
 
static constexpr bool is_str () BMNOEXCEPT
 

Access to internals <br>

bvector_type_const_ptr get_slice (unsigned i) const BMNOEXCEPT
 get access to bit-plane, function checks and creates a plane More...
 
bvector_type_ptr get_create_slice (unsigned i)
 
unsigned effective_slices () const BMNOEXCEPT
  More...
 
const sparse_vector_typeget_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_typeget_bmatrix () const BMNOEXCEPT
  More...
 
bmatrix_typeget_bmatrix () BMNOEXCEPT
  More...
 
const rs_index_typeget_RS () const BMNOEXCEPT
  More...
 
void mark_null_idx (unsigned null_idx) BMNOEXCEPT
 
bool resolve (size_type idx, size_type *idx_to) const BMNOEXCEPT
 Resolve logical address to access via rank compressed address. More...
 
static unsigned slices () BMNOEXCEPT
 get total number of bit-slices in the vector More...
 
static unsigned stored_slices ()
 Number of stored bit-slices (value slices + extra. More...
 

Detailed Description

template<class Val, class SV>
class bm::rsc_sparse_vector< Val, SV >

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.

Examples
xsample08.cpp.

Definition at line 58 of file bmsparsevec_compr.h.

Member Typedef Documentation

◆ remap_matrix_type

template<class Val , class SV >
typedef bm::heap_matrix<unsigned char, 1, 1, typename bvector_type::allocator_type> bm::rsc_sparse_vector< Val, SV >::remap_matrix_type
protected

unused remap matrix type for compatibility with the sparse serializer

Definition at line 926 of file bmsparsevec_compr.h.

Member Enumeration Documentation

◆ bit_slices

template<class Val , class SV >
enum bm::rsc_sparse_vector::bit_slices
Enumerator
sv_slices 
sv_value_slices 

Definition at line 61 of file bmsparsevec_compr.h.

◆ octet_slices

template<class Val , class SV >
enum bm::rsc_sparse_vector::octet_slices
protected
Enumerator
sv_octet_slices 

Definition at line 900 of file bmsparsevec_compr.h.

◆ vector_capacity

template<class Val , class SV >
enum bm::rsc_sparse_vector::vector_capacity
Enumerator
max_vector_size 

Definition at line 82 of file bmsparsevec_compr.h.

Constructor & Destructor Documentation

◆ rsc_sparse_vector() [1/4]

template<class Val , class SV >
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() 
)

◆ rsc_sparse_vector() [2/4]

template<class Val , class SV >
bm::rsc_sparse_vector< Val, SV >::rsc_sparse_vector ( const bvector_type bv_null)

Contructor to pre-initialize the list of assigned (not NULL) elements.

If the list of not NULL elements is known upfront it can help to pre-declare it, enable rank-select index and then use set function. This scenario gives significant speed boost, comparing random assignment

Parameters
bv_null- not NULL vector for the container

Definition at line 995 of file bmsparsevec_compr.h.

References BM_ASSERT.

◆ rsc_sparse_vector() [3/4]

template<class Val , class SV >
bm::rsc_sparse_vector< Val, SV >::rsc_sparse_vector ( const rsc_sparse_vector< Val, SV > &  csv)

copy-ctor

Definition at line 1028 of file bmsparsevec_compr.h.

References BM_ASSERT, and bm::rsc_sparse_vector< Val, SV >::sv_value_slices.

◆ rsc_sparse_vector() [4/4]

template<class Val , class SV >
bm::rsc_sparse_vector< Val, SV >::rsc_sparse_vector ( rsc_sparse_vector< Val, SV > &&  csv)

move-ctor

Definition at line 1042 of file bmsparsevec_compr.h.

Member Function Documentation

◆ at()

template<class Val , class SV >
rsc_sparse_vector< Val, SV >::value_type bm::rsc_sparse_vector< Val, SV >::at ( size_type  idx) const

access specified element with bounds checking

Parameters
idx- element index
Returns
value of the element

Definition at line 1549 of file bmsparsevec_compr.h.

◆ begin()

template<class Val , class SV >
const_iterator bm::rsc_sparse_vector< Val, SV >::begin ( ) const
inline

Provide const iterator access to container content

Definition at line 688 of file bmsparsevec_compr.h.

◆ calc_stat()

template<class Val , class SV >
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.

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

Definition at line 1645 of file bmsparsevec_compr.h.

References BM_ASSERT.

Referenced by main().

◆ clear() [1/2]

template<class Val , class SV >
void bm::rsc_sparse_vector< Val, SV >::clear ( )
inline

resize to zero, free memory

Parameters
free_mem- free bit vector slices if true

Definition at line 731 of file bmsparsevec_compr.h.

References bm::rsc_sparse_vector< Val, SV >::clear_all().

◆ clear() [2/2]

template<class Val , class SV >
void bm::rsc_sparse_vector< Val, SV >::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)

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

Definition at line 1212 of file bmsparsevec_compr.h.

References bm::rank_compressor< BV >::compress().

◆ clear_all()

template<class Val , class SV >
void bm::rsc_sparse_vector< Val, SV >::clear_all ( bool  free_mem)

resize to zero, free memory

Parameters
free_mem- free bit vector slices if true

Definition at line 1636 of file bmsparsevec_compr.h.

Referenced by bm::rsc_sparse_vector< Val, SV >::clear(), and bm::rsc_sparse_vector< Val, SV >::operator=().

◆ copy_range()

template<class Val , class SV >
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.

Parameters
csv- source vector
left- index from in losed diapason of [left..right]
right- index to in losed diapason of [left..right]

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

◆ count_range_notnull()

template<class Val , class SV >
rsc_sparse_vector< Val, SV >::size_type bm::rsc_sparse_vector< Val, SV >::count_range_notnull ( size_type  left,
size_type  right 
) const

Definition at line 1949 of file bmsparsevec_compr.h.

References bm::rs3_border0, and bm::xor_swap().

◆ decode()

template<class Val , class SV >
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.

Parameters
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
Returns
actual decoded size
See also
decode_buf

Definition at line 1702 of file bmsparsevec_compr.h.

References bm::bvector< Alloc >::enumerator::advance(), BM_ASSERT, bm::id_max, bm::bvector< Alloc >::iterator_base::valid(), and bm::bvector< Alloc >::enumerator::value().

◆ decode_buf()

template<class Val , class SV >
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.

Parameters
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
Returns
actual decoded size
See also
decode

Definition at line 1762 of file bmsparsevec_compr.h.

References bm::bvector< Alloc >::enumerator::advance(), BM_ASSERT, bm::id_max, bm::bvector< Alloc >::iterator_base::valid(), and bm::bvector< Alloc >::enumerator::value().

◆ effective_size()

template<class Val , class SV >
size_type bm::rsc_sparse_vector< Val, SV >::effective_size ( ) const
inline

size of internal dense vector

Definition at line 856 of file bmsparsevec_compr.h.

◆ effective_slices()

template<class Val , class SV >
unsigned bm::rsc_sparse_vector< Val, SV >::effective_slices ( ) const
inline

Number of effective bit-slices in the value type

Definition at line 835 of file bmsparsevec_compr.h.

◆ effective_vector_max()

template<class Val , class SV >
size_type bm::rsc_sparse_vector< Val, SV >::effective_vector_max ( ) const
inline

Always 1 (non-matrix type)

Definition at line 861 of file bmsparsevec_compr.h.

◆ empty()

template<class Val , class SV >
bool bm::rsc_sparse_vector< Val, SV >::empty ( ) const
inline

return true if vector is empty

Returns
true if empty

Definition at line 379 of file bmsparsevec_compr.h.

Referenced by main(), and run_benchmark().

◆ end()

template<class Val , class SV >
const_iterator bm::rsc_sparse_vector< Val, SV >::end ( ) const
inline

Provide const iterator access to the end

Definition at line 696 of file bmsparsevec_compr.h.

References bm::id_max.

◆ equal()

template<class Val , class SV >
bool bm::rsc_sparse_vector< Val, SV >::equal ( const rsc_sparse_vector< Val, SV > &  csv) const

check if another vector has the same content

Returns
true, if it is the same

Definition at line 1344 of file bmsparsevec_compr.h.

Referenced by main().

◆ find_rank()

template<class Val , class SV >
bool bm::rsc_sparse_vector< Val, SV >::find_rank ( size_type  rank,
size_type idx 
) const

find position of compressed element by its rank

Parameters
rank- rank (virtual index in sparse vector)
idx- index (true position)

Definition at line 1672 of file bmsparsevec_compr.h.

References BM_ASSERT.

◆ freeze()

template<class Val , class SV >
void bm::rsc_sparse_vector< Val, SV >::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 753 of file bmsparsevec_compr.h.

◆ gather()

template<class Val , class SV >
rsc_sparse_vector< Val, SV >::size_type bm::rsc_sparse_vector< Val, SV >::gather ( value_type arr,
const size_type idx,
size_type idx_tmp_buf,
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- destination array
idx- index list to gather elements (read only)
idx_tmp_buf- temp scratch buffer for index rank-select index translation must be correctly allocated to match size. No value initialization requirement.
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 1820 of file bmsparsevec_compr.h.

References BM_ASSERT, bm::BM_SORTED, bm::BM_UNKNOWN, and bm::id_max.

Referenced by main().

◆ get()

template<class Val , class SV >
rsc_sparse_vector< Val, SV >::value_type bm::rsc_sparse_vector< Val, SV >::get ( size_type  idx) const

get specified element without bounds checking

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

Definition at line 1567 of file bmsparsevec_compr.h.

References BM_ASSERT.

Referenced by compute_frequent_kmers(), compute_kmer_histogram(), main(), bm::rsc_sparse_vector< Val, SV >::operator[](), print_model(), raw_data_size(), and test_data().

◆ get_back_inserter()

template<class Val , class SV >
back_insert_iterator bm::rsc_sparse_vector< Val, SV >::get_back_inserter ( )
inline

◆ get_bmatrix() [1/2]

template<class Val , class SV >
bmatrix_type& bm::rsc_sparse_vector< Val, SV >::get_bmatrix ( )
inline

get read-only access to inetrnal bit-matrix

Definition at line 872 of file bmsparsevec_compr.h.

◆ get_bmatrix() [2/2]

template<class Val , class SV >
const bmatrix_type& bm::rsc_sparse_vector< Val, SV >::get_bmatrix ( ) const
inline

get read-only access to inetrnal bit-matrix

Definition at line 866 of file bmsparsevec_compr.h.

Referenced by deserialize_df2().

◆ get_const_iterator()

template<class Val , class SV >
const_iterator bm::rsc_sparse_vector< Val, SV >::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 702 of file bmsparsevec_compr.h.

Referenced by main().

◆ get_null_bvector()

template<class Val , class SV >
const rsc_sparse_vector< Val, SV >::bvector_type * bm::rsc_sparse_vector< Val, SV >::get_null_bvector

◆ get_RS()

template<class Val , class SV >
const rs_index_type* bm::rsc_sparse_vector< Val, SV >::get_RS ( ) const
inline

Get Rank-Select index pointer

Returns
NULL if sync() was not called to construct the index
See also
sync()

Definition at line 880 of file bmsparsevec_compr.h.

◆ get_slice()

template<class Val , class SV >
bvector_type_const_ptr bm::rsc_sparse_vector< Val, SV >::get_slice ( unsigned  i) const
inline

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

Returns
bit-vector for the bit slice

Definition at line 826 of file bmsparsevec_compr.h.

◆ get_sv()

template<class Val , class SV >
const sparse_vector_type& bm::rsc_sparse_vector< Val, SV >::get_sv ( ) const
inline

access dense vector

Definition at line 851 of file bmsparsevec_compr.h.

◆ in_sync()

template<class Val , class SV >
bool bm::rsc_sparse_vector< Val, SV >::in_sync ( ) const
inline

returns true if prefix sum table is in sync with the vector

Definition at line 806 of file bmsparsevec_compr.h.

Referenced by main(), and Counting_JobFunctor< DNA_Scan >::operator()().

◆ inc() [1/2]

template<class Val , class SV >
void bm::rsc_sparse_vector< Val, SV >::inc ( size_type  idx)

increment specified element by one

Parameters
idx- element index

Definition at line 1229 of file bmsparsevec_compr.h.

References BM_ASSERT.

Referenced by main().

◆ inc() [2/2]

template<class Val , class SV >
void bm::rsc_sparse_vector< Val, SV >::inc ( size_type  idx,
value_type  v 
)

increment specified element by one

Parameters
idx- element index
v- increment value

Definition at line 1261 of file bmsparsevec_compr.h.

References BM_ASSERT.

◆ inc_not_null()

template<class Val , class SV >
void bm::rsc_sparse_vector< Val, SV >::inc_not_null ( size_type  idx,
value_type  v 
)

increment specified element by one, element MUST be NOT NULL Faster than just inc() if element is NULL - behavior is undefined

Parameters
idx- element index
v- increment value
See also
inc

Definition at line 1293 of file bmsparsevec_compr.h.

References BM_ASSERT.

◆ is_compressed()

template<class Val , class SV >
static constexpr bool bm::rsc_sparse_vector< Val, SV >::is_compressed ( )
inlinestaticconstexpr

various type traits

Definition at line 646 of file bmsparsevec_compr.h.

◆ is_null()

template<class Val , class SV >
bool bm::rsc_sparse_vector< Val, SV >::is_null ( size_type  idx) const

test if specified element is NULL

Parameters
idx- element index
Returns
true if it is NULL false if it was assigned or container is not configured to support assignment flags
Examples
xsample08.cpp.

Definition at line 1607 of file bmsparsevec_compr.h.

References BM_ASSERT.

Referenced by set_feature_strand().

◆ is_nullable()

template<class Val , class SV >
bool bm::rsc_sparse_vector< Val, SV >::is_nullable ( ) const
inline

if container supports NULL(unassigned) values (true)

Definition at line 641 of file bmsparsevec_compr.h.

◆ is_ro()

template<class Val , class SV >
bool bm::rsc_sparse_vector< Val, SV >::is_ro ( ) const
inline

Returns true if vector is read-only.

Definition at line 756 of file bmsparsevec_compr.h.

◆ is_sync()

template<class Val , class SV >
bool bm::rsc_sparse_vector< Val, SV >::is_sync ( ) const
inline

returns true if prefix sum table is in sync with the vector

Definition at line 810 of file bmsparsevec_compr.h.

◆ load_from()

template<class Val , class SV >
void bm::rsc_sparse_vector< Val, SV >::load_from ( const sparse_vector_type sv_src)

Load compressed vector from a sparse vector (with NULLs)

Parameters
sv_src- source sparse vector

Definition at line 1358 of file bmsparsevec_compr.h.

References BM_ASSERT, and bm::rank_compressor< BV >::compress().

Referenced by compute_rsc_historgam(), main(), and write_as_rsc_svector().

◆ load_to()

template<class Val , class SV >
void bm::rsc_sparse_vector< Val, SV >::load_to ( sparse_vector_type sv) const

Exort compressed vector to a sparse vector (with NULLs)

Parameters
sv- target sparse vector

Definition at line 1399 of file bmsparsevec_compr.h.

References BM_ASSERT, and bm::rank_compressor< BV >::decompress().

Referenced by main().

◆ merge_not_null()

template<class Val , class SV >
void bm::rsc_sparse_vector< Val, SV >::merge_not_null ( rsc_sparse_vector< Val, SV > &  csv)

merge two vectors (argument gets destroyed) It is important that both vectors have the same NULL vectors

Parameters
csv- [in,out] argumnet vector to merge (works like move so arg should not be used after the merge)

Definition at line 1937 of file bmsparsevec_compr.h.

References BM_ASSERT.

Referenced by SortCounting_JobFunctor< BV >::operator()().

◆ operator=() [1/2]

template<class Val , class SV >
rsc_sparse_vector<Val,SV>& bm::rsc_sparse_vector< Val, SV >::operator= ( const rsc_sparse_vector< Val, SV > &  csv)
inline

copy assignmment operator

Definition at line 332 of file bmsparsevec_compr.h.

◆ operator=() [2/2]

template<class Val , class SV >
rsc_sparse_vector<Val,SV>& bm::rsc_sparse_vector< Val, SV >::operator= ( rsc_sparse_vector< Val, SV > &&  csv)
inline

move assignmment operator

Definition at line 352 of file bmsparsevec_compr.h.

References bm::rsc_sparse_vector< Val, SV >::clear_all().

◆ operator[]()

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

get specified element without bounds checking

Parameters
idx- element index
Returns
value of the element

Definition at line 416 of file bmsparsevec_compr.h.

References bm::rsc_sparse_vector< Val, SV >::get().

◆ optimize()

template<class Val , class SV >
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 slices

Parameters
temp_block- pre-allocated memory block to avoid unnecessary re-allocs
opt_mode- requested compression depth
stat- memory allocation statistics after optimization

Definition at line 1617 of file bmsparsevec_compr.h.

References bm::bv_statistics::memory_used.

Referenced by compute_adaptive_rsc_histogram(), compute_rsc_historgam(), generate_test_data(), main(), and write_as_rsc_svector().

◆ push_back() [1/2]

template<class Val , class SV >
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.

Parameters
idx- element index
v- element value

Definition at line 1115 of file bmsparsevec_compr.h.

Referenced by compute_adaptive_rsc_histogram(), and bm::rsc_sparse_vector< Val, SV >::push_back().

◆ push_back() [2/2]

template<class Val , class SV >
void bm::rsc_sparse_vector< Val, SV >::push_back ( value_type  v)
inline

add element with automatic resize

Parameters
v- element value

Definition at line 468 of file bmsparsevec_compr.h.

References bm::rsc_sparse_vector< Val, SV >::push_back().

◆ push_back_no_check()

template<class Val , class SV >
void bm::rsc_sparse_vector< Val, SV >::push_back_no_check ( size_type  idx,
value_type  v 
)
protected

Definition at line 1140 of file bmsparsevec_compr.h.

References BM_ASSERT.

◆ push_back_null() [1/2]

template<class Val , class SV >
void bm::rsc_sparse_vector< Val, SV >::push_back_null ( )
inline

◆ push_back_null() [2/2]

template<class Val , class SV >
void bm::rsc_sparse_vector< Val, SV >::push_back_null ( size_type  count)

push back specified amount of NULL values

Parameters
count- number of NULLs to push back

Definition at line 1130 of file bmsparsevec_compr.h.

References BM_ASSERT, and bm::id_max.

◆ resize()

template<class Val , class SV >
void bm::rsc_sparse_vector< Val, SV >::resize ( size_type  new_size)

change vector size

Parameters
new_size- new vector size

Definition at line 1068 of file bmsparsevec_compr.h.

References BM_ASSERT, and bm::id_max.

◆ resolve()

template<class Val , class SV >
bool bm::rsc_sparse_vector< Val, SV >::resolve ( size_type  idx,
size_type idx_to 
) const

Resolve logical address to access via rank compressed address.

Parameters
idx- input id to resolve
idx_to- output id
Returns
true if id is known and resolved successfully

Definition at line 1469 of file bmsparsevec_compr.h.

References BM_ASSERT.

◆ resolve_range()

template<class Val , class SV >
bool bm::rsc_sparse_vector< Val, SV >::resolve_range ( size_type  from,
size_type  to,
size_type idx_from,
size_type idx_to 
) const
protected

Definition at line 1517 of file bmsparsevec_compr.h.

References BM_ASSERT.

Referenced by bm::rsc_sparse_vector< Val, SV >::copy_range().

◆ resolve_sync()

template<class Val , class SV >
bool bm::rsc_sparse_vector< Val, SV >::resolve_sync ( size_type  idx,
size_type idx_to 
) const
protected

Definition at line 1493 of file bmsparsevec_compr.h.

References BM_ASSERT, and bm::id_max.

◆ s2u()

template<class Val , class SV >
static unsigned_value_type bm::rsc_sparse_vector< Val, SV >::s2u ( value_type  v)
inlinestaticprotected

Convert signed value type to unsigned representation.

Definition at line 937 of file bmsparsevec_compr.h.

◆ set()

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

set specified element with bounds checking and automatic resize

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

Definition at line 1312 of file bmsparsevec_compr.h.

References BM_ASSERT.

Referenced by count_kmers(), fill_test_data(), main(), Counting_JobFunctor< DNA_Scan >::operator()(), and set_feature_strand().

◆ set_null() [1/2]

template<class Val , class SV >
void bm::rsc_sparse_vector< Val, SV >::set_null ( const bvector_type bv_idx)

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

Function also clears all the values to 0. Note: this can be a very expensive function for an RS container.

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

Definition at line 1183 of file bmsparsevec_compr.h.

References bm::rank_compressor< BV >::compress(), and bm::bvector< Alloc >::iterator_base::valid().

◆ set_null() [2/2]

template<class Val , class SV >
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).

Parameters
idx- element index

Definition at line 1156 of file bmsparsevec_compr.h.

References BM_ASSERT.

◆ size()

template<class Val , class SV >
rsc_sparse_vector< Val, SV >::size_type bm::rsc_sparse_vector< Val, SV >::size

return size of the vector

Returns
size of sparse vector

Definition at line 1060 of file bmsparsevec_compr.h.

Referenced by compute_historgam(), compute_rsc_historgam(), bm::rsc_sparse_vector< Val, SV >::copy_range(), main(), and raw_data_size().

◆ slices()

template<class Val , class SV >
static unsigned bm::rsc_sparse_vector< Val, SV >::slices ( )
inlinestatic

get total number of bit-slices in the vector

Definition at line 841 of file bmsparsevec_compr.h.

◆ stored_slices()

template<class Val , class SV >
static unsigned bm::rsc_sparse_vector< Val, SV >::stored_slices ( )
inlinestatic

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

Definition at line 845 of file bmsparsevec_compr.h.

◆ sync() [1/2]

template<class Val , class SV >
void bm::rsc_sparse_vector< Val, SV >::sync ( )
inline

Re-calculate prefix sum table used for rank search (if necessary)

Definition at line 801 of file bmsparsevec_compr.h.

References bm::rsc_sparse_vector< Val, SV >::sync().

Referenced by bm::rsc_sparse_vector< Val, SV >::sync().

◆ sync() [2/2]

template<class Val , class SV >
void bm::rsc_sparse_vector< Val, SV >::sync ( bool  force)

Re-calculate rank-select index for faster access to vector.

Parameters
force- force recalculation even if it is already recalculated

Definition at line 1431 of file bmsparsevec_compr.h.

References BM_ASSERT.

Referenced by compute_adaptive_rsc_histogram(), compute_rsc_historgam(), fill_test_data(), generate_test_data(), main(), and SortCounting_JobFunctor< BV >::operator()().

◆ sync_size()

template<class Val , class SV >
void bm::rsc_sparse_vector< Val, SV >::sync_size

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

Definition at line 1453 of file bmsparsevec_compr.h.

References BM_ASSERT.

◆ try_get()

template<class Val , class SV >
bool bm::rsc_sparse_vector< Val, SV >::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 1580 of file bmsparsevec_compr.h.

◆ try_get_sync()

template<class Val , class SV >
bool bm::rsc_sparse_vector< Val, SV >::try_get_sync ( size_type  idx,
value_type v 
) const

get specified element with NOT NULL check Caller guarantees that the vector is in sync mode (RS-index access).

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

Definition at line 1593 of file bmsparsevec_compr.h.

◆ unsync()

template<class Val , class SV >
void bm::rsc_sparse_vector< Val, SV >::unsync ( )
inline

Unsync the prefix sum table.

Definition at line 815 of file bmsparsevec_compr.h.


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