bm::rsc_sparse_vector< Val, SV > Class Template Reference
BitMagic Library » bit-sliced (bitwise transposition) succinct sparse vectors

Rank-Select compressed sparse vector. More...

`#include <bmsparsevec_compr.h>`

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

## Data Structures

struct | is_remap_support
struct | is_rsc_support
struct | is_dynamic_splices
struct | statistics
class | reference
| Reference class to access elements via common [] operator. More...
class | const_iterator
| Const iterator to traverse the rsc sparse vector. More...
class | back_insert_iterator
| Back insert iterator implements buffered insert, faster than generic access assignment. More...

## 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_type & | const_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_type * | bvector_type_ptr
typedef const bvector_type * | bvector_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
| 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 (const bvector_type &bv_null)
| Contructor to pre-initialize the list of assigned (not NULL) elements.
| ~rsc_sparse_vector ()
| rsc_sparse_vector (const rsc_sparse_vector< Val, SV > &csv)
rsc_sparse_vector< Val, SV > & | operator= (const rsc_sparse_vector< Val, SV > &csv)
| rsc_sparse_vector (rsc_sparse_vector< Val, SV > &&csv) BMNOEXCEPT
rsc_sparse_vector< Val, SV > & | operator= (rsc_sparse_vector< Val, SV > &&csv) BMNOEXCEPT
Size, etc
size_type | size () const BMNOEXCEPT
| return size of the vector
bool | empty () const BMNOEXCEPT
| return true if vector is empty
void | sync_size () BMNOEXCEPT
| recalculate size to exclude tail NULL elements After this call size() will return the true size of the vector
void | resize (size_type new_size)
| change vector size
size_type | count_range_notnull (size_type left, size_type right) const BMNOEXCEPT
Element access
value_type | operator[] (size_type idx) const
| get specified element without bounds checking
value_type | at (size_type idx) const
| access specified element with bounds checking
value_type | get (size_type idx) const BMNOEXCEPT
| get specified element without bounds checking
unsigned_value_type | get_unsigned_bits (size_type idx, size_type N_bits) const BMNOEXCEPT
| Get raw unsigned value first N bits.
bool | try_get (size_type idx, value_type &v) const BMNOEXCEPT
| get specified element with NOT NULL check
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).
void | push_back (size_type idx, value_type v)
| set specified element with bounds checking and automatic resize
void | push_back (value_type v)
| add element with automatic resize
void | push_back_null (size_type count)
| push back specified amount of NULL values
void | push_back_null ()
| push back NULL value
void | set (size_type idx, value_type v)
| set specified element with bounds checking and automatic resize
void | inc (size_type idx)
| increment specified element by one
void | inc (size_type idx, value_type v)
| increment specified element by one
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
void | set_null (size_type idx)
| set specified element to NULL RSC vector actually erases element when it is set to NULL (expensive).
void | set_null (const bvector_type &bv_idx)
| Set NULL all elements set as 1 in the argument vector.
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).
bool | is_null (size_type idx) const BMNOEXCEPT
| test if specified element is NULL
const bvector_type * | get_null_bvector () const BMNOEXCEPT
| Get bit-vector of assigned values (or NULL).
bool | find_rank (size_type rank, size_type &idx) const BMNOEXCEPT
| find position of compressed element by its rank
Export content to C-stype array
size_type | decode (value_type *arr, size_type idx_from, size_type size, bool zero_mem=true) const
| C-style decode.
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.
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.
Comparison
bool | equal (const rsc_sparse_vector< Val, SV > &csv) const BMNOEXCEPT
| check if another vector has the same content
Load-Export compressed vector with data
void | load_from (const sparse_vector_type &sv_src)
| Load compressed vector from a sparse vector (with NULLs).
void | load_to (sparse_vector_type &sv) const
| Exort compressed vector to a sparse vector (with NULLs).
Iterator access
const_iterator | begin () const
| Provide const iterator access to container content.
const_iterator | end () const BMNOEXCEPT
| Provide const iterator access to the end.
const_iterator | get_const_iterator (size_type idx) const BMNOEXCEPT
| Get const_itertor re-positioned to specific element.
back_insert_iterator | get_back_inserter ()
Memory optimization
void | optimize (bm::word_t *temp_block=0, typename bvector_type::optmode opt_mode=bvector_type::opt_compress, statistics *stat=0)
| run memory optimization for all vector slices
void | clear_all (bool free_mem, unsigned) BMNOEXCEPT
| resize to zero, free memory
void | clear () BMNOEXCEPT
| resize to zero, free memory
void | calc_stat (struct rsc_sparse_vector< Val, SV >::statistics *st) const BMNOEXCEPT
| Calculates memory statistics.
void | freeze ()
| Turn sparse vector into immutable mode Read-only (immutable) vector uses less memory and allows faster searches.
bool | is_ro () const BMNOEXCEPT
| Returns true if vector is read-only.
Merge, split, partition data
void | copy_range (const rsc_sparse_vector< Val, SV > &csv, size_type left, size_type right)
| copy range of values from another sparse vector
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
Fast access structues sync
void | sync (bool force)
| Re-calculate rank-select index for faster access to vector.
void | sync ()
| Re-calculate prefix sum table used for rank search (if necessary).
bool | in_sync () const BMNOEXCEPT
| returns true if prefix sum table is in sync with the vector
bool | is_sync () const BMNOEXCEPT
| returns true if prefix sum table is in sync with the vector
void | unsync () BMNOEXCEPT
| Unsync the prefix sum table.

## Protected Types

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

## Protected Member Functions

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

## Static Protected Member Functions

static unsigned_value_type | s2u (value_type v) BMNOEXCEPT
| Convert signed value type to unsigned representation.
static value_type | u2s (unsigned_value_type v) BMNOEXCEPT

## Friends

template<class SVect, unsigned S_FACTOR>
class | sparse_vector_scanner
template<class SVect>
class | sparse_vector_serializer
template<class SVect>
class | sparse_vector_deserializer

## Various traits

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

## Access to internals

bvector_type_const_ptr | get_slice (unsigned i) const BMNOEXCEPT
| get access to bit-plane, function checks and creates a plane
bvector_type_ptr | get_create_slice (unsigned i)
bvector_type_ptr | slice (unsigned i)
unsigned | effective_slices () const BMNOEXCEPT
const sparse_vector_type & | get_sv () const BMNOEXCEPT
| access dense vector
size_type | effective_size () const BMNOEXCEPT
| size of internal dense vector
size_type | effective_vector_max () const BMNOEXCEPT
| Always 1 (non-matrix type).
const bmatrix_type & | get_bmatrix () const BMNOEXCEPT
bmatrix_type & | get_bmatrix () BMNOEXCEPT
const rs_index_type * | get_RS () const BMNOEXCEPT
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.
static unsigned | slices () BMNOEXCEPT
| get total number of bit-slices in the vector
static unsigned | stored_slices ()
| Number of stored bit-slices (value slices + extra.

## 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
  inv_list.cpp, rscsample01.cpp, rscsample02.cpp, rscsample03.cpp, rscsample04.cpp, rscsample05.cpp, rscsample06.cpp, xsample03.cpp, xsample07.cpp, xsample08.cpp, and xsample09.cpp.

Definition at line 58 of file bmsparsevec_compr.h.

## Member Typedef Documentation

## allocation_policy_type

template<class Val, class SV>

typedef bvector_type::allocation_policy bm::rsc_sparse_vector< Val, SV >::allocation_policy_type

Definition at line 76 of file bmsparsevec_compr.h.

## allocator_type

template<class Val, class SV>

typedef bvector_type::allocator_type bm::rsc_sparse_vector< Val, SV >::allocator_type

Definition at line 75 of file bmsparsevec_compr.h.

## bmatrix_type

template<class Val, class SV>

typedef SV::bmatrix_type bm::rsc_sparse_vector< Val, SV >::bmatrix_type

Definition at line 79 of file bmsparsevec_compr.h.

## bvector_enumerator_type

template<class Val, class SV>

typedef bvector_type::enumerator bm::rsc_sparse_vector< Val, SV >::bvector_enumerator_type

Definition at line 78 of file bmsparsevec_compr.h.

## bvector_type

template<class Val, class SV>

typedef SV::bvector_type bm::rsc_sparse_vector< Val, SV >::bvector_type

Definition at line 72 of file bmsparsevec_compr.h.

## bvector_type_const_ptr

template<class Val, class SV>

typedef const bvector_type* bm::rsc_sparse_vector< Val, SV >::bvector_type_const_ptr

Definition at line 74 of file bmsparsevec_compr.h.

## bvector_type_ptr

template<class Val, class SV>

typedef bvector_type* bm::rsc_sparse_vector< Val, SV >::bvector_type_ptr

Definition at line 73 of file bmsparsevec_compr.h.

## const_reference

template<class Val, class SV>

typedef const value_type& bm::rsc_sparse_vector< Val, SV >::const_reference

Definition at line 68 of file bmsparsevec_compr.h.

## 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 938 of file bmsparsevec_compr.h.

## rs_index_type

template<class Val, class SV>

typedef bvector_type::rs_index_type bm::rsc_sparse_vector< Val, SV >::rs_index_type

Definition at line 77 of file bmsparsevec_compr.h.

## size_type

template<class Val, class SV>

typedef SV::size_type bm::rsc_sparse_vector< Val, SV >::size_type

Definition at line 69 of file bmsparsevec_compr.h.

## sparse_vector_const_iterator

template<class Val, class SV>

typedef SV::const_iterator bm::rsc_sparse_vector< Val, SV >::sparse_vector_const_iterator

Definition at line 71 of file bmsparsevec_compr.h.

## sparse_vector_type

template<class Val, class SV>

typedef SV bm::rsc_sparse_vector< Val, SV >::sparse_vector_type

Definition at line 70 of file bmsparsevec_compr.h.

## unsigned_value_type

template<class Val, class SV>

typedef SV::unsigned_value_type bm::rsc_sparse_vector< Val, SV >::unsigned_value_type

Definition at line 80 of file bmsparsevec_compr.h.

## value_type

template<class Val, class SV>

typedef Val bm::rsc_sparse_vector< Val, SV >::value_type

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

Definition at line 990 of file bmsparsevec_compr.h.

References BM_ASSERT, sv_value_slices, and bm::use_null.

Referenced by copy_range(), equal(), merge_not_null(), bm::rsc_sparse_vector< Val, SV >::reference::reference(), rsc_sparse_vector(), and rsc_sparse_vector().

## 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 1006 of file bmsparsevec_compr.h.

References BM_ASSERT, and bm::use_null.

## ~rsc_sparse_vector()

template<class Val, class SV>

bm::rsc_sparse_vector< Val, SV >::~rsc_sparse_vector | ( |  | ) |

Definition at line 1031 of file bmsparsevec_compr.h.

## 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 1039 of file bmsparsevec_compr.h.

References BM_ASSERT, rsc_sparse_vector(), and 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 1053 of file bmsparsevec_compr.h.

References BMNOEXCEPT, rsc_sparse_vector(), and bm::use_null.

## 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 1561 of file bmsparsevec_compr.h.

References resolve(), and size().

## 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 697 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 1672 of file bmsparsevec_compr.h.

References BM_ASSERT, and BMNOEXCEPT.

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 740 of file bmsparsevec_compr.h.

## 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 1223 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,
|  | unsigned | )

resize to zero, free memory

Parameters

  free_mem | - free bit vector slices if true

Definition at line 1663 of file bmsparsevec_compr.h.

References BMNOEXCEPT.

Referenced by bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::clear(), and bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::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 1932 of file bmsparsevec_compr.h.

References bm::no_null, resolve_range(), rsc_sparse_vector(), 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 1976 of file bmsparsevec_compr.h.

References BMNOEXCEPT, 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 1729 of file bmsparsevec_compr.h.

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

## 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 1789 of file bmsparsevec_compr.h.

References bm::bvector< Alloc >::enumerator::advance(), BM_ASSERT, BMNOEXCEPT, bm::id_max, size(), 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 868 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 847 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 873 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 705 of file bmsparsevec_compr.h.

## 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 1355 of file bmsparsevec_compr.h.

References BMNOEXCEPT, and rsc_sparse_vector().

Referenced by main(), and 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 1699 of file bmsparsevec_compr.h.

References BM_ASSERT, BMNOEXCEPT, get_null_bvector(), and in_sync().

## 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 762 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 1847 of file bmsparsevec_compr.h.

References BM_ASSERT, bm::BM_SORTED, bm::BM_UNKNOWN, get(), bm::id_max, resolve(), and size().

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

Definition at line 1579 of file bmsparsevec_compr.h.

References BM_ASSERT, BMNOEXCEPT, is_null(), and resolve().

Referenced by compute_frequent_kmers(), compute_kmer_histogram(), gather(), main(), bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::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

Definition at line 714 of file bmsparsevec_compr.h.

Referenced by bm::rsc_sparse_vector< Val, SV >::back_insert_iterator::back_insert_iterator(), generate_test_data(), and main().

## 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 884 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 878 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 711 of file bmsparsevec_compr.h.

Referenced by main().

## get_create_slice()

template<class Val, class SV>

bvector_type_ptr bm::rsc_sparse_vector< Val, SV >::get_create_slice | ( | unsigned | i | ) |

inline

Definition at line 838 of file bmsparsevec_compr.h.

## 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 | ( |  | ) | const

Get bit-vector of assigned values (or NULL).

Definition at line 1690 of file bmsparsevec_compr.h.

References BMNOEXCEPT.

Referenced by access_bench2(), access_bench3(), compute_adaptive_rsc_histogram(), compute_frequent_kmers(), compute_historgam(), compute_kmer_histogram(), compute_rsc_historgam(), find_rank(), load_to(), main(), and verify_histograms().

## get_remap_buffer()

template<class Val, class SV>

const unsigned char * bm::rsc_sparse_vector< Val, SV >::get_remap_buffer | ( |  | ) | const

inline protected

Definition at line 931 of file bmsparsevec_compr.h.

## get_remap_matrix() [1/2]

template<class Val, class SV>

remap_matrix_type * bm::rsc_sparse_vector< Val, SV >::get_remap_matrix | ( |  | ) |

inline protected

Definition at line 941 of file bmsparsevec_compr.h.

## get_remap_matrix() [2/2]

template<class Val, class SV>

const remap_matrix_type * bm::rsc_sparse_vector< Val, SV >::get_remap_matrix | ( |  | ) | const

inline protected

Definition at line 940 of file bmsparsevec_compr.h.

## 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 892 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 835 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 863 of file bmsparsevec_compr.h.

## get_unsigned_bits()

template<class Val, class SV>

rsc_sparse_vector< Val, SV >::unsigned_value_type bm::rsc_sparse_vector< Val, SV >::get_unsigned_bits | ( | size_type | idx,
|  | size_type | N_bits ) const

Get raw unsigned value first N bits.

Parameters

  idx | - element index in the vector
  N_bits | - number of bits to be extracted (should be > 0)

Returns
  unsigned value for

Definition at line 1593 of file bmsparsevec_compr.h.

References BM_ASSERT, BMNOEXCEPT, is_null(), and resolve().

## 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 815 of file bmsparsevec_compr.h.

Referenced by find_rank(), and main().

## 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 1240 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 1272 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 1304 of file bmsparsevec_compr.h.

References BM_ASSERT.

## init_remap_buffer()

template<class Val, class SV>

unsigned char * bm::rsc_sparse_vector< Val, SV >::init_remap_buffer | ( |  | ) |

inline protected

Definition at line 932 of file bmsparsevec_compr.h.

## is_compressed()

template<class Val, class SV>

constexpr bool bm::rsc_sparse_vector< Val, SV >::is_compressed | ( |  | ) |

inline static constexpr

various type traits

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

Definition at line 1634 of file bmsparsevec_compr.h.

References BM_ASSERT, and BMNOEXCEPT.

Referenced by get(), get_unsigned_bits(), and 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 650 of file bmsparsevec_compr.h.

## is_remap()

template<class Val, class SV>

bool bm::rsc_sparse_vector< Val, SV >::is_remap | ( |  | ) | const

inline constexpr protected

Definition at line 929 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 765 of file bmsparsevec_compr.h.

## is_str()

template<class Val, class SV>

constexpr bool bm::rsc_sparse_vector< Val, SV >::is_str | ( |  | ) |

inline static constexpr

Definition at line 658 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 819 of file bmsparsevec_compr.h.

Referenced by optimize().

## 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 1369 of file bmsparsevec_compr.h.

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

Referenced by compute_rsc_historgam(), main(), 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 1410 of file bmsparsevec_compr.h.

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

Referenced by main(), and main().

## mark_null_idx()

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::mark_null_idx | ( | unsigned | null_idx | ) |

inline

Definition at line 895 of file bmsparsevec_compr.h.

## 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 1964 of file bmsparsevec_compr.h.

References BM_ASSERT, and rsc_sparse_vector().

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

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

## 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 1644 of file bmsparsevec_compr.h.

References is_sync(), bm::bv_statistics::memory_used, and sync().

Referenced by compute_adaptive_rsc_histogram(), compute_rsc_historgam(), generate_test_data(), main(), 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 1126 of file bmsparsevec_compr.h.

References push_back_no_check().

Referenced by compute_adaptive_rsc_histogram(), and bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::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 477 of file bmsparsevec_compr.h.

## 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 1151 of file bmsparsevec_compr.h.

References BM_ASSERT.

Referenced by push_back().

## push_back_null() [1/2]

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::push_back_null | ( |  | ) |

inline

push back NULL value

Definition at line 489 of file bmsparsevec_compr.h.

Referenced by bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::push_back_null().

## 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 1141 of file bmsparsevec_compr.h.

References BM_ASSERT, and bm::id_max.

## remap_size()

template<class Val, class SV>

size_t bm::rsc_sparse_vector< Val, SV >::remap_size | ( |  | ) | const

inline protected

Definition at line 930 of file bmsparsevec_compr.h.

## 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 1079 of file bmsparsevec_compr.h.

References BM_ASSERT, and bm::id_max.

## resize_internal()

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::resize_internal | ( | size_type | sz | ) |

inline protected

Definition at line 923 of file bmsparsevec_compr.h.

## 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 1481 of file bmsparsevec_compr.h.

References BM_ASSERT, BMNOEXCEPT, and resolve_sync().

Referenced by at(), gather(), get(), get_unsigned_bits(), and try_get().

## 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 1529 of file bmsparsevec_compr.h.

References BM_ASSERT, and BMNOEXCEPT.

Referenced by 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 1505 of file bmsparsevec_compr.h.

References BM_ASSERT, BMNOEXCEPT, and bm::id_max.

Referenced by resolve(), and try_get_sync().

## s2u()

template<class Val, class SV>

unsigned_value_type bm::rsc_sparse_vector< Val, SV >::s2u | ( | value_type | v | ) |

inline static protected

Convert signed value type to unsigned representation.

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

Definition at line 1323 of file bmsparsevec_compr.h.

References BM_ASSERT.

Referenced by count_kmers(), fill_test_data(), main(), 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 1194 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 1167 of file bmsparsevec_compr.h.

References BM_ASSERT.

## set_remap()

template<class Val, class SV>

void bm::rsc_sparse_vector< Val, SV >::set_remap | ( |  | ) |

inline protected

Definition at line 933 of file bmsparsevec_compr.h.

## size()

template<class Val, class SV>

rsc_sparse_vector< Val, SV >::size_type bm::rsc_sparse_vector< Val, SV >::size | ( |  | ) | const

return size of the vector

Returns
  size of sparse vector

Definition at line 1071 of file bmsparsevec_compr.h.

References BMNOEXCEPT.

Referenced by at(), compute_historgam(), compute_rsc_historgam(), copy_range(), decode(), decode_buf(), gather(), load_to(), main(), and raw_data_size().

## size_internal()

template<class Val, class SV>

size_type bm::rsc_sparse_vector< Val, SV >::size_internal | ( |  | ) | const

inline protected

Definition at line 927 of file bmsparsevec_compr.h.

## slice()

template<class Val, class SV>

bvector_type_ptr bm::rsc_sparse_vector< Val, SV >::slice | ( | unsigned | i | ) |

inline

Definition at line 841 of file bmsparsevec_compr.h.

## slices()

template<class Val, class SV>

unsigned bm::rsc_sparse_vector< Val, SV >::slices | ( |  | ) |

inline static

get total number of bit-slices in the vector

Definition at line 853 of file bmsparsevec_compr.h.

## stored_slices()

template<class Val, class SV>

unsigned bm::rsc_sparse_vector< Val, SV >::stored_slices | ( |  | ) |

inline static

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

Definition at line 857 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 810 of file bmsparsevec_compr.h.

Referenced by bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::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 1442 of file bmsparsevec_compr.h.

References BM_ASSERT, and sync_size().

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

## 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 1465 of file bmsparsevec_compr.h.

References BM_ASSERT, BMNOEXCEPT, and sync().

Referenced by sync().

## 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 1607 of file bmsparsevec_compr.h.

References BMNOEXCEPT, and resolve().

## 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 1620 of file bmsparsevec_compr.h.

References BMNOEXCEPT, and resolve_sync().

## u2s()

template<class Val, class SV>

value_type bm::rsc_sparse_vector< Val, SV >::u2s | ( | unsigned_value_type | v | ) |

inline static protected

Definition at line 952 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 824 of file bmsparsevec_compr.h.

## Friends And Related Symbol Documentation

## sparse_vector_deserializer

template<class Val, class SV>
template<class SVect>

friend class sparse_vector_deserializer

friend

Definition at line 973 of file bmsparsevec_compr.h.

## sparse_vector_scanner

template<class Val, class SV>
template<class SVect, unsigned S_FACTOR>

friend class sparse_vector_scanner

friend

Definition at line 971 of file bmsparsevec_compr.h.

## sparse_vector_serializer

template<class Val, class SV>
template<class SVect>

friend class sparse_vector_serializer

friend

Definition at line 972 of file bmsparsevec_compr.h.

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

- bmsparsevec_compr.h