BitMagicC++Library
Data Structures | Public Types | Public Member Functions | Static Public Member Functions | Protected Member Functions
bm::sparse_vector< Val, BV > Class Template Reference

sparse vector with runtime compression using bit transposition method More...

#include <bmsparsevec.h>

Inheritance diagram for bm::sparse_vector< Val, BV >:
Inheritance graph
[legend]

Data Structures

class  reference
 Reference class to access elements via common [] operator. More...
 
struct  statistics
 

Public Types

typedef Val value_type
 
typedef bm::id_t size_type
 
typedef BV bvector_type
 
typedef bvector_typebvector_type_ptr
 
typedef const value_typeconst_reference
 
typedef BV::allocator_type allocator_type
 
typedef bvector_type::allocation_policy allocation_policy_type
 

Public Member Functions

 sparse_vector (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)
 
 sparse_vector (sparse_vector< Val, BV > &&sv) BMNOEXEPT
 
sparse_vector< Val, BV > & operator= (sparse_vector< Val, BV > &&sv) BMNOEXEPT
 
sparse_vector< Val, BV > & operator= (const sparse_vector< Val, BV > &sv)
 
 ~sparse_vector () BMNOEXEPT
 
reference operator[] (size_type idx)
 
void swap (sparse_vector< Val, BV > &sv) BMNOEXEPT
 content exchange More...
 
value_type operator[] (size_type idx) const
 get specified element without bounds checking More...
 
void import (const value_type *arr, size_type size, size_type offset=0)
 Import list of elements from a C-style array. More...
 
size_type decode (value_type *arr, size_type idx_from, size_type size, bool zero_mem=true) const
 Bulk export list of elements to a C-style array. More...
 
size_type size () const
 return size of the vector More...
 
bool empty () const
 return true if vector is empty More...
 
void resize (size_type sz)
 resize vector More...
 
void clear () BMNOEXEPT
 resize to zero, free memory More...
 
value_type at (size_type idx) const
 access specified element with bounds checking More...
 
value_type get (bm::id_t idx) const
 get specified element without bounds checking More...
 
void set (size_type idx, value_type v)
 set specified element with bounds checking and automatic resize More...
 
void push_back (value_type v)
 push value back into vector More...
 
bool equal (const sparse_vector< Val, BV > &sv) const
 check if another sparse vector has the same content and size More...
 
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 plains More...
 
void optimize_gap_size ()
 Optimize sizes of GAP blocks. More...
 
sparse_vector< Val, BV > & join (const sparse_vector< Val, BV > &sv)
 join all with another sparse vector using OR operation More...
 
void calc_stat (struct sparse_vector< Val, BV >::statistics *st) const
 Calculates memory statistics. More...
 
bvector_type_ptr get_plain (unsigned i)
 get access to bit-plain, function checks and creates a plain More...
 
bvector_type_ptr plain (unsigned i)
 get access to bit-plain as is (can return NULL) More...
 
const bvector_type_ptr plain (unsigned i) const
 
void free_plain (unsigned i)
 free memory in bit-plain More...
 
sparse_vector< Val, BV > & clear_range (size_type left, size_type right)
 clear range (assign bit 0 for all plains) More...
 
size_type 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. 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_plains (value_type *arr, size_type size, size_type offset, bool zero_mem=true) const
 extract medium window without use of masking vector More...
 

Static Public Member Functions

static unsigned plains ()
 get total number of bit-plains in the vector More...
 

Protected Member Functions

void set_value (size_type idx, value_type v)
 set value without checking boundaries More...
 
const bm::word_tget_block (unsigned p, unsigned i, unsigned j) const
 
void throw_range_error (const char *err_msg) const
 

Detailed Description

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

sparse vector with runtime compression using bit transposition method

Sparse vector implements variable bit-depth storage model. Initial data is bit-transposed into bit-planes so initial each element may use less memory than the original native data type prescribes. For example, 32-bit integer may only use 20 bits.

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.

Overall it provides variable bit-depth compression, sparse compression in bit-plains.

Examples:
svsample01.cpp, svsample02.cpp, svsample03.cpp, and xsample01.cpp.

Definition at line 60 of file bmsparsevec.h.

Member Typedef Documentation

◆ allocation_policy_type

template<class Val, class BV>
typedef bvector_type::allocation_policy bm::sparse_vector< Val, BV >::allocation_policy_type

Definition at line 69 of file bmsparsevec.h.

◆ allocator_type

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

Definition at line 68 of file bmsparsevec.h.

◆ bvector_type

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

Definition at line 65 of file bmsparsevec.h.

◆ bvector_type_ptr

template<class Val, class BV>
typedef bvector_type* bm::sparse_vector< Val, BV >::bvector_type_ptr

Definition at line 66 of file bmsparsevec.h.

◆ const_reference

template<class Val, class BV>
typedef const value_type& bm::sparse_vector< Val, BV >::const_reference

Definition at line 67 of file bmsparsevec.h.

◆ size_type

template<class Val, class BV>
typedef bm::id_t bm::sparse_vector< Val, BV >::size_type

Definition at line 64 of file bmsparsevec.h.

◆ value_type

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

Definition at line 63 of file bmsparsevec.h.

Constructor & Destructor Documentation

◆ sparse_vector() [1/3]

template<class Val , class BV >
bm::sparse_vector< Val, BV >::sparse_vector ( 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
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<>
bm::bvector<>::allocation_policy
bm::startegy

Definition at line 427 of file bmsparsevec.h.

Referenced by bm::sparse_vector< Val, BV >::reference::operator==().

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

◆ ~sparse_vector()

template<class Val , class BV >
bm::sparse_vector< Val, BV >::~sparse_vector ( )

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

Definition at line 916 of file bmsparsevec.h.

Referenced by main(), and bm::sparse_vector< unsigned, bm::bvector<> >::operator[]().

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

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

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

See also
statistics

Definition at line 1123 of file bmsparsevec.h.

Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::operator[]().

◆ clear()

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

◆ clear_range()

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

clear range (assign bit 0 for all plains)

Parameters
left- interval start
right- interval end (closed interval)

Definition at line 1099 of file bmsparsevec.h.

Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::plain().

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

Definition at line 608 of file bmsparsevec.h.

Referenced by main(), and bm::sparse_vector< unsigned, bm::bvector<> >::operator[]().

◆ empty()

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

return true if vector is empty

Returns
true if empty

Definition at line 848 of file bmsparsevec.h.

Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::operator[]().

◆ equal()

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

check if another sparse vector has the same content and size

Returns
true, if it is the same

Definition at line 1242 of file bmsparsevec.h.

Referenced by main(), and bm::sparse_vector< unsigned, bm::bvector<> >::operator[]().

◆ 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
number of exported elements
See also
decode

Decoder functor

Definition at line 746 of file bmsparsevec.h.

Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::plain().

◆ extract_plains()

template<class Val , class BV >
sparse_vector< Val, BV >::size_type bm::sparse_vector< Val, BV >::extract_plains ( 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 701 of file bmsparsevec.h.

Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::plain().

◆ 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

extract small window without use of masking vector

See also
decode

Definition at line 628 of file bmsparsevec.h.

Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::plain().

◆ free_plain()

template<class Val , class BV >
void bm::sparse_vector< Val, BV >::free_plain ( unsigned  i)

free memory in bit-plain

Definition at line 1087 of file bmsparsevec.h.

Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::plain().

◆ get()

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

get specified element without bounds checking

Parameters
idx- element index
Returns
value of the element

Definition at line 941 of file bmsparsevec.h.

◆ get_block()

template<class Val , class BV >
const bm::word_t * bm::sparse_vector< Val, BV >::get_block ( unsigned  p,
unsigned  i,
unsigned  j 
) const
protected

◆ get_plain()

template<class Val , class BV >
sparse_vector< Val, BV >::bvector_type_ptr bm::sparse_vector< Val, BV >::get_plain ( unsigned  i)

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

Definition at line 881 of file bmsparsevec.h.

Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::operator[]().

◆ import()

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

Import list of elements from a C-style array.

Parameters
arr- source array
size- source size
offset- target index in the sparse vector

Definition at line 538 of file bmsparsevec.h.

Referenced by convert_bv2sv(), and main().

◆ 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

Definition at line 1214 of file bmsparsevec.h.

Referenced by main(), and bm::sparse_vector< unsigned, bm::bvector<> >::operator[]().

◆ operator=() [1/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 130 of file bmsparsevec.h.

◆ operator=() [2/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 142 of file bmsparsevec.h.

◆ operator[]() [1/2]

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

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

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

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

Referenced by convert_bv2sv(), main(), and bm::sparse_vector< unsigned, bm::bvector<> >::operator[]().

◆ 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 plains of the vector.

Definition at line 1197 of file bmsparsevec.h.

Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::operator[]().

◆ plain() [1/2]

template<class Val, class BV>
bvector_type_ptr bm::sparse_vector< Val, BV >::plain ( unsigned  i)
inline

get access to bit-plain as is (can return NULL)

Definition at line 337 of file bmsparsevec.h.

◆ plain() [2/2]

template<class Val, class BV>
const bvector_type_ptr bm::sparse_vector< Val, BV >::plain ( unsigned  i) const
inline

Definition at line 338 of file bmsparsevec.h.

◆ plains()

template<class Val, class BV>
static unsigned bm::sparse_vector< Val, BV >::plains ( )
inlinestatic

get total number of bit-plains in the vector

Definition at line 332 of file bmsparsevec.h.

Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::operator=().

◆ 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

Definition at line 1020 of file bmsparsevec.h.

Referenced by main(), and bm::sparse_vector< unsigned, bm::bvector<> >::operator[]().

◆ resize()

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

resize vector

Parameters
sz- new size

Definition at line 857 of file bmsparsevec.h.

Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::operator=(), and bm::sparse_vector< unsigned, bm::bvector<> >::operator[]().

◆ 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

Definition at line 1008 of file bmsparsevec.h.

Referenced by convert_bv2sv(), and main().

◆ set_value()

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

set value without checking boundaries

Definition at line 1029 of file bmsparsevec.h.

Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::plain().

◆ size()

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

◆ swap()

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

◆ throw_range_error()

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

Definition at line 526 of file bmsparsevec.h.

Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::plain().


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