BitMagic-C++
Public Types | Public Member Functions | Protected Member Functions | Static Protected Member Functions | Protected Attributes
bm::base_sparse_vector< Val, BV, MAX_SIZE > Class Template Reference

Base class for bit-transposed sparse vector construction. More...

#include <bmbmatrix.h>

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

Public Types

enum  bit_plains { sv_plains = (sizeof(Val) * 8 * MAX_SIZE + 1), sv_value_plains = (sizeof(Val) * 8 * MAX_SIZE) }
 
enum  vector_capacity { max_vector_size = MAX_SIZE }
 
typedef Val value_type
 
typedef BV bvector_type
 
typedef BV::size_type size_type
 
typedef bvector_typebvector_type_ptr
 
typedef const bvector_typebvector_type_const_ptr
 
typedef const value_typeconst_reference
 
typedef BV::allocator_type allocator_type
 
typedef bvector_type::allocation_policy allocation_policy_type
 
typedef bvector_type::enumerator bvector_enumerator_type
 
typedef allocator_type::allocator_pool_type allocator_pool_type
 
typedef bm::basic_bmatrix< BV > bmatrix_type
 

Public Member Functions

 base_sparse_vector ()
 
 base_sparse_vector (bm::null_support null_able, allocation_policy_type ap, size_type bv_max_size, const allocator_type &alloc)
 
 base_sparse_vector (const base_sparse_vector< Val, BV, MAX_SIZE > &bsv)
 
 base_sparse_vector (base_sparse_vector< Val, BV, MAX_SIZE > &&bsv) BMNOEXEPT
 
void swap (base_sparse_vector< Val, BV, MAX_SIZE > &bsv) BMNOEXEPT
 
size_type size () const
 
void resize (size_type new_size)
 
void clear_range (size_type left, size_type right, bool set_null)
 
void clear () BMNOEXEPT
 resize to zero, free memory More...
 
bool empty () const
 
void optimize (bm::word_t *temp_block=0, typename bvector_type::optmode opt_mode=bvector_type::opt_compress, typename bvector_type::statistics *stat=0)
 run memory optimization for all bit-vector rows More...
 
void calc_stat (typename bvector_type::statistics *st) const
 Calculates memory statistics. More...
 
bool equal (const base_sparse_vector< Val, BV, MAX_SIZE > &sv, bm::null_support null_able=bm::use_null) const
 check if another sparse vector has the same content and size More...
 
Various traits
bool is_nullable () const
 check if container supports NULL(unassigned) values More...
 
const bvector_typeget_null_bvector () const
 Get bit-vector of assigned values or NULL (if not constructed that way) More...
 
bool is_null (size_type idx) const
 test if specified element is NULL More...
 

Protected Member Functions

void copy_from (const base_sparse_vector< Val, BV, MAX_SIZE > &bsv)
 
void clear_value_plains_from (unsigned plain_idx, size_type idx)
 
void insert_clear_value_plains_from (unsigned plain_idx, size_type idx)
 
void erase_column (size_type idx)
 
void insert_null (size_type idx, bool not_null)
 

Static Protected Member Functions

static unsigned value_bits ()
 Number of total bit-plains in the value type. More...
 
static unsigned null_plain ()
 plain index for the "NOT NULL" flag1s plain More...
 

Protected Attributes

bmatrix_type bmatr_
 bit-transposed matrix More...
 
size_type size_
 array size More...
 
unsigned effective_plains_
 

Access to internals

bvector_type_ptr get_plain (unsigned i)
 get access to bit-plain, function checks and creates a plain More...
 
bvector_type_const_ptr get_plain (unsigned i) const
 get read-only access to bit-plain More...
 
unsigned effective_plains () const
 Number of effective bit-plains in the value type. 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
 
bvector_typeget_null_bvect ()
 
void free_plain (unsigned i)
 free memory in bit-plain More...
 
bm::id64_t get_plains_mask (unsigned element_idx) const
 
static unsigned plains ()
 get total number of bit-plains in the vector More...
 
static unsigned stored_plains ()
 Number of stored bit-plains (value plains + extra. More...
 

Detailed Description

template<typename Val, typename BV, unsigned MAX_SIZE>
class bm::base_sparse_vector< Val, BV, MAX_SIZE >

Base class for bit-transposed sparse vector construction.

Definition at line 244 of file bmbmatrix.h.

Member Typedef Documentation

◆ allocation_policy_type

template<typename Val, typename BV, unsigned MAX_SIZE>
typedef bvector_type::allocation_policy bm::base_sparse_vector< Val, BV, MAX_SIZE >::allocation_policy_type

Definition at line 265 of file bmbmatrix.h.

◆ allocator_pool_type

template<typename Val, typename BV, unsigned MAX_SIZE>
typedef allocator_type::allocator_pool_type bm::base_sparse_vector< Val, BV, MAX_SIZE >::allocator_pool_type

Definition at line 267 of file bmbmatrix.h.

◆ allocator_type

template<typename Val, typename BV, unsigned MAX_SIZE>
typedef BV::allocator_type bm::base_sparse_vector< Val, BV, MAX_SIZE >::allocator_type

Definition at line 264 of file bmbmatrix.h.

◆ bmatrix_type

template<typename Val, typename BV, unsigned MAX_SIZE>
typedef bm::basic_bmatrix<BV> bm::base_sparse_vector< Val, BV, MAX_SIZE >::bmatrix_type

Definition at line 268 of file bmbmatrix.h.

◆ bvector_enumerator_type

template<typename Val, typename BV, unsigned MAX_SIZE>
typedef bvector_type::enumerator bm::base_sparse_vector< Val, BV, MAX_SIZE >::bvector_enumerator_type

Definition at line 266 of file bmbmatrix.h.

◆ bvector_type

template<typename Val, typename BV, unsigned MAX_SIZE>
typedef BV bm::base_sparse_vector< Val, BV, MAX_SIZE >::bvector_type

Definition at line 259 of file bmbmatrix.h.

◆ bvector_type_const_ptr

template<typename Val, typename BV, unsigned MAX_SIZE>
typedef const bvector_type* bm::base_sparse_vector< Val, BV, MAX_SIZE >::bvector_type_const_ptr

Definition at line 262 of file bmbmatrix.h.

◆ bvector_type_ptr

template<typename Val, typename BV, unsigned MAX_SIZE>
typedef bvector_type* bm::base_sparse_vector< Val, BV, MAX_SIZE >::bvector_type_ptr

Definition at line 261 of file bmbmatrix.h.

◆ const_reference

template<typename Val, typename BV, unsigned MAX_SIZE>
typedef const value_type& bm::base_sparse_vector< Val, BV, MAX_SIZE >::const_reference

Definition at line 263 of file bmbmatrix.h.

◆ size_type

template<typename Val, typename BV, unsigned MAX_SIZE>
typedef BV::size_type bm::base_sparse_vector< Val, BV, MAX_SIZE >::size_type

Definition at line 260 of file bmbmatrix.h.

◆ value_type

template<typename Val, typename BV, unsigned MAX_SIZE>
typedef Val bm::base_sparse_vector< Val, BV, MAX_SIZE >::value_type

Definition at line 258 of file bmbmatrix.h.

Member Enumeration Documentation

◆ bit_plains

template<typename Val, typename BV, unsigned MAX_SIZE>
enum bm::base_sparse_vector::bit_plains
Enumerator
sv_plains 
sv_value_plains 

Definition at line 247 of file bmbmatrix.h.

◆ vector_capacity

template<typename Val, typename BV, unsigned MAX_SIZE>
enum bm::base_sparse_vector::vector_capacity
Enumerator
max_vector_size 

Definition at line 253 of file bmbmatrix.h.

Constructor & Destructor Documentation

◆ base_sparse_vector() [1/4]

template<class Val , class BV , unsigned MAX_SIZE>
bm::base_sparse_vector< Val, BV, MAX_SIZE >::base_sparse_vector ( )

Definition at line 1081 of file bmbmatrix.h.

◆ base_sparse_vector() [2/4]

template<class Val , class BV , unsigned MAX_SIZE>
bm::base_sparse_vector< Val, BV, MAX_SIZE >::base_sparse_vector ( bm::null_support  null_able,
allocation_policy_type  ap,
size_type  bv_max_size,
const allocator_type alloc 
)

Definition at line 1091 of file bmbmatrix.h.

◆ base_sparse_vector() [3/4]

template<class Val, class BV, unsigned MAX_SIZE>
bm::base_sparse_vector< Val, BV, MAX_SIZE >::base_sparse_vector ( const base_sparse_vector< Val, BV, MAX_SIZE > &  bsv)

Definition at line 1110 of file bmbmatrix.h.

◆ base_sparse_vector() [4/4]

template<typename Val, typename BV, unsigned MAX_SIZE>
bm::base_sparse_vector< Val, BV, MAX_SIZE >::base_sparse_vector ( base_sparse_vector< Val, BV, MAX_SIZE > &&  bsv)
inline

move-ctor

Definition at line 282 of file bmbmatrix.h.

Member Function Documentation

◆ calc_stat()

template<class Val , class BV , unsigned MAX_SIZE>
void bm::base_sparse_vector< Val, BV, MAX_SIZE >::calc_stat ( typename bvector_type::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 1320 of file bmbmatrix.h.

◆ clear()

template<class Val , class BV , unsigned MAX_SIZE>
void bm::base_sparse_vector< Val, BV, MAX_SIZE >::clear ( )

resize to zero, free memory

Definition at line 1169 of file bmbmatrix.h.

◆ clear_range()

template<typename Val, typename BV, unsigned MAX_SIZE>
void bm::base_sparse_vector< Val, BV, MAX_SIZE >::clear_range ( size_type  left,
size_type  right,
bool  set_null 
)

Definition at line 1185 of file bmbmatrix.h.

◆ clear_value_plains_from()

template<class Val , class BV , unsigned MAX_SIZE>
void bm::base_sparse_vector< Val, BV, MAX_SIZE >::clear_value_plains_from ( unsigned  plain_idx,
size_type  idx 
)
protected

clear column in all value plains

Parameters
plain_idx- row (plain index to start from)
idx- bit (column) to clear

Definition at line 1351 of file bmbmatrix.h.

◆ copy_from()

template<class Val, class BV, unsigned MAX_SIZE>
void bm::base_sparse_vector< Val, BV, MAX_SIZE >::copy_from ( const base_sparse_vector< Val, BV, MAX_SIZE > &  bsv)
protected

Definition at line 1121 of file bmbmatrix.h.

◆ effective_plains()

template<typename Val, typename BV, unsigned MAX_SIZE>
unsigned bm::base_sparse_vector< Val, BV, MAX_SIZE >::effective_plains ( ) const
inline

Number of effective bit-plains in the value type.

Definition at line 360 of file bmbmatrix.h.

◆ empty()

template<typename Val, typename BV, unsigned MAX_SIZE>
bool bm::base_sparse_vector< Val, BV, MAX_SIZE >::empty ( ) const
inline

return true if empty

Definition at line 303 of file bmbmatrix.h.

◆ equal()

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

check if another sparse vector has the same content and size

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

Definition at line 1392 of file bmbmatrix.h.

◆ erase_column()

template<class Val , class BV , unsigned MAX_SIZE>
void bm::base_sparse_vector< Val, BV, MAX_SIZE >::erase_column ( size_type  idx)
protected

erase bit (column) from all plains

Parameters
idx- bit (column) to erase

Definition at line 1379 of file bmbmatrix.h.

◆ free_plain()

template<typename Val, typename BV, unsigned MAX_SIZE>
void bm::base_sparse_vector< Val, BV, MAX_SIZE >::free_plain ( unsigned  i)
inline

free memory in bit-plain

Definition at line 373 of file bmbmatrix.h.

◆ get_null_bvect()

template<typename Val, typename BV, unsigned MAX_SIZE>
bvector_type* bm::base_sparse_vector< Val, BV, MAX_SIZE >::get_null_bvect ( )
inline

◆ get_null_bvector()

template<typename Val, typename BV, unsigned MAX_SIZE>
const bvector_type* bm::base_sparse_vector< Val, BV, MAX_SIZE >::get_null_bvector ( ) const
inline

Get bit-vector of assigned values or NULL (if not constructed that way)

Definition at line 319 of file bmbmatrix.h.

Referenced by bm::base_sparse_vector< Val, BV, 1 >::equal(), generate_random_subset(), and print_sorted().

◆ get_plain() [1/2]

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

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

Returns
bit-vector for the bit plain

Definition at line 1252 of file bmbmatrix.h.

◆ get_plain() [2/2]

template<typename Val, typename BV, unsigned MAX_SIZE>
bvector_type_const_ptr bm::base_sparse_vector< Val, BV, MAX_SIZE >::get_plain ( unsigned  i) const
inline

get read-only access to bit-plain

Returns
bit-vector for the bit plain or NULL

Definition at line 348 of file bmbmatrix.h.

◆ get_plains_mask()

template<class Val , class BV , unsigned MAX_SIZE>
bm::id64_t bm::base_sparse_vector< Val, BV, MAX_SIZE >::get_plains_mask ( unsigned  element_idx) const

return mask of allocated bit-plains 1 in the mask - means bit-plain N is present returns 64-bit unsigned mask for sub 64-bit types (like int) unallocated mask bits will be zero extended

Returns
64-bit mask

Definition at line 1268 of file bmbmatrix.h.

◆ insert_clear_value_plains_from()

template<class Val , class BV , unsigned MAX_SIZE>
void bm::base_sparse_vector< Val, BV, MAX_SIZE >::insert_clear_value_plains_from ( unsigned  plain_idx,
size_type  idx 
)
protected

insert false (clear) column in all value plains

Parameters
plain_idx- row (plain index to start from)
idx- bit (column) to clear insert

Definition at line 1365 of file bmbmatrix.h.

◆ insert_null()

template<class Val , class BV , unsigned MAX_SIZE>
void bm::base_sparse_vector< Val, BV, MAX_SIZE >::insert_null ( size_type  idx,
bool  not_null 
)
protected

insert (NOT) NULL value

Definition at line 1240 of file bmbmatrix.h.

◆ is_null()

template<class Val , class BV , unsigned MAX_SIZE>
bool bm::base_sparse_vector< Val, BV, MAX_SIZE >::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 1231 of file bmbmatrix.h.

Referenced by bm::sparse_vector< Val, BV >::const_iterator::is_null(), and print_svector().

◆ is_nullable()

template<typename Val, typename BV, unsigned MAX_SIZE>
bool bm::base_sparse_vector< Val, BV, MAX_SIZE >::is_nullable ( ) const
inline

check if container supports NULL(unassigned) values

Definition at line 313 of file bmbmatrix.h.

◆ null_plain()

template<typename Val, typename BV, unsigned MAX_SIZE>
static unsigned bm::base_sparse_vector< Val, BV, MAX_SIZE >::null_plain ( )
inlinestaticprotected

plain index for the "NOT NULL" flag1s plain

Definition at line 460 of file bmbmatrix.h.

◆ optimize()

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

run memory optimization for all bit-vector rows

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 1290 of file bmbmatrix.h.

◆ plain() [1/2]

template<typename Val, typename BV, unsigned MAX_SIZE>
bvector_type_ptr bm::base_sparse_vector< Val, BV, MAX_SIZE >::plain ( unsigned  i)
inline

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

Definition at line 365 of file bmbmatrix.h.

◆ plain() [2/2]

template<typename Val, typename BV, unsigned MAX_SIZE>
const bvector_type_ptr bm::base_sparse_vector< Val, BV, MAX_SIZE >::plain ( unsigned  i) const
inline

Definition at line 366 of file bmbmatrix.h.

◆ plains()

template<typename Val, typename BV, unsigned MAX_SIZE>
static unsigned bm::base_sparse_vector< Val, BV, MAX_SIZE >::plains ( )
inlinestatic

get total number of bit-plains in the vector

Definition at line 353 of file bmbmatrix.h.

◆ resize()

template<class Val , class BV , unsigned MAX_SIZE>
void bm::base_sparse_vector< Val, BV, MAX_SIZE >::resize ( size_type  new_size)

Definition at line 1213 of file bmbmatrix.h.

◆ size()

template<typename Val, typename BV, unsigned MAX_SIZE>
size_type bm::base_sparse_vector< Val, BV, MAX_SIZE >::size ( ) const
inline

◆ stored_plains()

template<typename Val, typename BV, unsigned MAX_SIZE>
static unsigned bm::base_sparse_vector< Val, BV, MAX_SIZE >::stored_plains ( )
inlinestatic

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

Definition at line 356 of file bmbmatrix.h.

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

◆ swap()

template<class Val, class BV, unsigned MAX_SIZE>
void bm::base_sparse_vector< Val, BV, MAX_SIZE >::swap ( base_sparse_vector< Val, BV, MAX_SIZE > &  bsv)

Definition at line 1154 of file bmbmatrix.h.

◆ value_bits()

template<typename Val, typename BV, unsigned MAX_SIZE>
static unsigned bm::base_sparse_vector< Val, BV, MAX_SIZE >::value_bits ( )
inlinestaticprotected

Number of total bit-plains in the value type.

Definition at line 454 of file bmbmatrix.h.

Field Documentation

◆ bmatr_

template<typename Val, typename BV, unsigned MAX_SIZE>
bmatrix_type bm::base_sparse_vector< Val, BV, MAX_SIZE >::bmatr_
protected

bit-transposed matrix

Definition at line 462 of file bmbmatrix.h.

Referenced by bm::base_sparse_vector< Val, BV, 1 >::copy_from(), and bm::base_sparse_vector< Val, BV, 1 >::equal().

◆ effective_plains_

template<typename Val, typename BV, unsigned MAX_SIZE>
unsigned bm::base_sparse_vector< Val, BV, MAX_SIZE >::effective_plains_
protected

Definition at line 464 of file bmbmatrix.h.

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

◆ size_

template<typename Val, typename BV, unsigned MAX_SIZE>
size_type bm::base_sparse_vector< Val, BV, MAX_SIZE >::size_
protected

array size

Definition at line 463 of file bmbmatrix.h.


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