NCBI C++ ToolKit
Public Types | Protected Member Functions | Static Protected Member Functions | Protected Attributes | Friends | List of all members
bm::basic_bmatrix< BV > Class Template Reference

Search Toolkit Book for bm::basic_bmatrix

Basic dense bit-matrix class. More...

#include <util/bitset/bmbmatrix.h>

+ Inheritance diagram for bm::basic_bmatrix< BV >:

Public Types

typedef BV bvector_type
 
typedef bvector_typebvector_type_ptr
 
typedef const bvector_typebvector_type_const_ptr
 
typedef BV::allocator_type allocator_type
 
typedef bvector_type::allocation_policy allocation_policy_type
 
typedef allocator_type::allocator_pool_type allocator_pool_type
 
typedef bvector_type::size_type size_type
 
typedef bvector_type::block_idx_type block_idx_type
 
typedef unsigned char octet_type
 

Public Member Functions

Construction, assignment
 basic_bmatrix (size_type rsize, bool is_dynamic=true, allocation_policy_type ap=allocation_policy_type(), size_type bv_max_size=bm::id_max, const allocator_type &alloc=allocator_type())
 
 ~basic_bmatrix () noexcept
 
 basic_bmatrix (const basic_bmatrix< BV > &bbm)
 
basic_bmatrix< BV > & operator= (const basic_bmatrix< BV > &bbm)
 
 basic_bmatrix (basic_bmatrix< BV > &&bbm) noexcept
 
basic_bmatrix< BV > & operator= (basic_bmatrix< BV > &&bbm) noexcept
 
void set_allocator_pool (allocator_pool_type *pool_ptr) noexcept
 
allocator_pool_typeget_allocator_pool () const noexcept
 
content manipulation
void swap (basic_bmatrix< BV > &bbm) noexcept
 
void copy_from (const basic_bmatrix< BV > &bbm)
 
void freeze ()
 
row access
const bvector_typerow (size_type i) const noexcept
 
bvector_type_const_ptr get_row (size_type i) const noexcept
 
bvector_typeget_row (size_type i) noexcept
 
size_type rows () const noexcept
 
size_type rows_not_null () const noexcept
 
size_type calc_effective_rows_not_null () const noexcept
 
bvector_type_ptr construct_row (size_type row)
 
bvector_type_ptr construct_row (size_type row, const bvector_type &bv)
 
void destruct_row (size_type row)
 
void clear_row (size_type row, bool free_mem)
 
size_type get_null_idx () const noexcept
 return index of the NULL vector More...
 
void set_null_idx (size_type null_idx) noexcept
 set index of the NULL vector More...
 
void allocate_rows (size_type rsize)
 allocate matrix rows of bit-vectors (new rows are NULLs) More...
 
void free_rows () noexcept
 Free all rows. More...
 
octet access and transposition
void set_octet (size_type pos, size_type octet_idx, unsigned char octet)
 
void insert_octet (size_type pos, size_type octet_idx, unsigned char octet)
 
unsigned char get_octet (size_type pos, size_type octet_idx) const noexcept
 
int compare_octet (size_type pos, size_type octet_idx, char octet) const noexcept
 
size_type octet_size () const noexcept
 
Utility functions
const bm::word_tget_block (size_type p, unsigned i, unsigned j) const noexcept
 Get low level internal access to. More...
 
void clear_slices_range (unsigned slice_from, unsigned slize_until, size_type idx)
 Clear bit-planes bit. More...
 
unsigned get_half_octet (size_type pos, size_type row_idx) const noexcept
 
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 optimize_block (block_idx_type nb, typename BV::optmode opt_mode)
 
void calc_stat (typename bvector_type::statistics &st, size_type rsize) const noexcept
 
void erase_column (size_type idx, bool erase_null)
 
void insert_column (size_type idx, size_type row_from)
 
void clear_column (size_type idx, size_type row_from)
 
void swap_columns (size_type idx1, size_type idx2)
 
void bit_sub_rows (const bvector_type &bv, bool use_null)
 Set SUB (MINUS) operation on all existing rows. More...
 
void bit_and_rows (const bvector_type &bv)
 Set AND (intersect) operation on all existing rows. More...
 
bool is_dynamic () const noexcept
 Return if matrix is dynamic resizable. More...
 
bool is_same_structure (const basic_bmatrix< BV > &bbm) const noexcept
 Debugging function to check if two matrixes have the same rows created. More...
 

Protected Member Functions

bvector_typeconstruct_bvector (const bvector_type *bv) const
 
void destruct_bvector (bvector_type *bv) const
 

Static Protected Member Functions

static void throw_bad_alloc ()
 

Protected Attributes

size_type bv_size_
 
allocator_type alloc_
 
allocation_policy_type ap_
 
allocator_pool_typepool_ = 0
 
bvector_type_ptrbv_rows_ = 0
 
size_type rsize_ = 0
 
bool is_dynamic_ = true
 if rsize is dynamic (variable length) More...
 
size_type null_idx_ = 0
 Index of the NULL row. More...
 

Friends

template<typename Val , typename BVect , unsigned MAX_SIZE>
class base_sparse_vector
 

Detailed Description

template<typename BV>
class bm::basic_bmatrix< BV >

Basic dense bit-matrix class.

Container of row-major bit-vectors, forming a bit-matrix. This class uses dense form of row storage. It is applicable as a build block for other sparse containers and succinct data structures, implementing high level abstractions.

Definition at line 55 of file bmbmatrix.h.

Member Typedef Documentation

◆ allocation_policy_type

template<typename BV >
typedef bvector_type::allocation_policy bm::basic_bmatrix< BV >::allocation_policy_type

Definition at line 62 of file bmbmatrix.h.

◆ allocator_pool_type

template<typename BV >
typedef allocator_type::allocator_pool_type bm::basic_bmatrix< BV >::allocator_pool_type

Definition at line 63 of file bmbmatrix.h.

◆ allocator_type

template<typename BV >
typedef BV::allocator_type bm::basic_bmatrix< BV >::allocator_type

Definition at line 61 of file bmbmatrix.h.

◆ block_idx_type

template<typename BV >
typedef bvector_type::block_idx_type bm::basic_bmatrix< BV >::block_idx_type

Definition at line 65 of file bmbmatrix.h.

◆ bvector_type

template<typename BV >
typedef BV bm::basic_bmatrix< BV >::bvector_type

Definition at line 58 of file bmbmatrix.h.

◆ bvector_type_const_ptr

template<typename BV >
typedef const bvector_type* bm::basic_bmatrix< BV >::bvector_type_const_ptr

Definition at line 60 of file bmbmatrix.h.

◆ bvector_type_ptr

template<typename BV >
typedef bvector_type* bm::basic_bmatrix< BV >::bvector_type_ptr

Definition at line 59 of file bmbmatrix.h.

◆ octet_type

template<typename BV >
typedef unsigned char bm::basic_bmatrix< BV >::octet_type

Definition at line 66 of file bmbmatrix.h.

◆ size_type

template<typename BV >
typedef bvector_type::size_type bm::basic_bmatrix< BV >::size_type

Definition at line 64 of file bmbmatrix.h.

Constructor & Destructor Documentation

◆ basic_bmatrix() [1/3]

template<typename BV >
bm::basic_bmatrix< BV >::basic_bmatrix ( size_type  rsize,
bool  is_dynamic = true,
allocation_policy_type  ap = allocation_policy_type(),
size_type  bv_max_size = bm::id_max,
const allocator_type alloc = allocator_type() 
)

◆ ~basic_bmatrix()

template<typename BV >
bm::basic_bmatrix< BV >::~basic_bmatrix
noexcept

Definition at line 734 of file bmbmatrix.h.

◆ basic_bmatrix() [2/3]

template<typename BV >
bm::basic_bmatrix< BV >::basic_bmatrix ( const basic_bmatrix< BV > &  bbm)

copy-ctor

Definition at line 742 of file bmbmatrix.h.

References bm::basic_bmatrix< BV >::copy_from(), and bm::basic_bmatrix< BV >::is_dynamic_.

◆ basic_bmatrix() [3/3]

template<typename BV >
bm::basic_bmatrix< BV >::basic_bmatrix ( basic_bmatrix< BV > &&  bbm)
noexcept

move-ctor

Definition at line 754 of file bmbmatrix.h.

References swap().

Member Function Documentation

◆ allocate_rows()

template<typename BV >
void bm::basic_bmatrix< BV >::allocate_rows ( size_type  rsize)

◆ bit_and_rows()

template<typename BV >
void bm::basic_bmatrix< BV >::bit_and_rows ( const bvector_type bv)

Set AND (intersect) operation on all existing rows.

Parameters
bv- argument vector row[i] &= bv

Definition at line 1012 of file bmbmatrix.h.

References i.

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

◆ bit_sub_rows()

template<typename BV >
void bm::basic_bmatrix< BV >::bit_sub_rows ( const bvector_type bv,
bool  use_null 
)

Set SUB (MINUS) operation on all existing rows.

Parameters
bv- argument vector row[i] -= bv
use_null- if true clear the NULL vector as well

Definition at line 999 of file bmbmatrix.h.

References i, and bm::use_null.

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

◆ calc_effective_rows_not_null()

template<typename BV >
basic_bmatrix< BV >::size_type bm::basic_bmatrix< BV >::calc_effective_rows_not_null
noexcept

get number of assigned avlue rows without \ NULLs bvector

Definition at line 981 of file bmbmatrix.h.

References i.

◆ calc_stat()

template<typename BV >
void bm::basic_bmatrix< BV >::calc_stat ( typename bvector_type::statistics &  st,
size_type  rsize 
) const
noexcept

Compute memory statistics

Parameters
st[out] - statistics object
rsize- row size (for cases when operation is limited not to touch the NULL bit-vector)

Definition at line 1584 of file bmbmatrix.h.

References i, and row.

Referenced by bm::base_sparse_vector< Val, BV, MAX_SIZE >::calc_stat().

◆ clear_column()

template<typename BV >
void bm::basic_bmatrix< BV >::clear_column ( size_type  idx,
size_type  row_from 
)

Clear value (set 0) into a range of rows

Parameters
idx- index (of column) / element of bit-vectors
row_from- row to start from

Definition at line 859 of file bmbmatrix.h.

References i.

Referenced by bm::base_sparse_vector< Val, BV, MAX_SIZE >::clear_value_planes_from().

◆ clear_row()

template<typename BV >
void bm::basic_bmatrix< BV >::clear_row ( size_type  row,
bool  free_mem 
)

clear row bit-vector

Definition at line 1103 of file bmbmatrix.h.

References BM_ASSERT, and row.

Referenced by bm::base_sparse_vector< Val, BV, MAX_SIZE >::clear_all().

◆ clear_slices_range()

template<typename BV >
void bm::basic_bmatrix< BV >::clear_slices_range ( unsigned  slice_from,
unsigned  slize_until,
size_type  idx 
)

Clear bit-planes bit.

Parameters
slice_from- clear from [from, until)
slice_until- clear until (open interval!)
idx- bit index

Definition at line 1180 of file bmbmatrix.h.

◆ compare_octet()

template<typename BV >
int bm::basic_bmatrix< BV >::compare_octet ( size_type  pos,
size_type  octet_idx,
char  octet 
) const
noexcept

Compare vector[pos] with octet

It uses regulat comparison of chars to comply with the (signed) char sort order.

Parameters
pos- column position in the matrix
octet_idx- octet based row position (1 octet - 8 rows)
octet- octet value to compare
Returns
0 - equal, -1 - less(vect[pos] < octet), 1 - greater

Definition at line 1445 of file bmbmatrix.h.

References rapidjson::value.

◆ construct_bvector()

template<typename BV >
basic_bmatrix< BV >::bvector_type * bm::basic_bmatrix< BV >::construct_bvector ( const bvector_type bv) const
protected

Definition at line 1122 of file bmbmatrix.h.

References malloc().

◆ construct_row() [1/2]

template<typename BV >
basic_bmatrix< BV >::bvector_type_ptr bm::basic_bmatrix< BV >::construct_row ( size_type  row)

◆ construct_row() [2/2]

template<typename BV >
basic_bmatrix< BV >::bvector_type_ptr bm::basic_bmatrix< BV >::construct_row ( size_type  row,
const bvector_type bv 
)

Make sure row is copy-constructed, return bit-vector

Definition at line 1073 of file bmbmatrix.h.

References BM_ASSERT, and row.

◆ copy_from()

template<typename BV >
void bm::basic_bmatrix< BV >::copy_from ( const basic_bmatrix< BV > &  bbm)

◆ destruct_bvector()

template<typename BV >
void bm::basic_bmatrix< BV >::destruct_bvector ( bvector_type bv) const
protected

Definition at line 1155 of file bmbmatrix.h.

References free().

◆ destruct_row()

template<typename BV >
void bm::basic_bmatrix< BV >::destruct_row ( size_type  row)

◆ erase_column()

template<typename BV >
void bm::basic_bmatrix< BV >::erase_column ( size_type  idx,
bool  erase_null 
)

Erase column/element

Parameters
idx- index (of column) / element of bit-vectors to erase
erase_null- erase all including NULL vector (true)

Definition at line 836 of file bmbmatrix.h.

References i.

Referenced by bm::base_sparse_vector< Val, BV, MAX_SIZE >::erase_column().

◆ free_rows()

template<typename BV >
void bm::basic_bmatrix< BV >::free_rows
noexcept

Free all rows.

Definition at line 923 of file bmbmatrix.h.

References i.

Referenced by bm::basic_bmatrix< bm::bvector<> >::operator=().

◆ freeze()

template<typename BV >
void bm::basic_bmatrix< BV >::freeze

Freeze content into read-only mode drop editing overhead

Definition at line 1574 of file bmbmatrix.h.

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

◆ get_allocator_pool()

template<typename BV >
allocator_pool_type* bm::basic_bmatrix< BV >::get_allocator_pool ( ) const
inlinenoexcept

◆ get_block()

template<typename BV >
const bm::word_t * bm::basic_bmatrix< BV >::get_block ( size_type  p,
unsigned  i,
unsigned  j 
) const
noexcept

Get low level internal access to.

Definition at line 1169 of file bmbmatrix.h.

References i, and row.

◆ get_half_octet()

template<typename BV >
unsigned bm::basic_bmatrix< BV >::get_half_octet ( size_type  pos,
size_type  row_idx 
) const
noexcept

◆ get_null_idx()

template<typename BV >
size_type bm::basic_bmatrix< BV >::get_null_idx ( ) const
inlinenoexcept

◆ get_octet()

template<typename BV >
unsigned char bm::basic_bmatrix< BV >::get_octet ( size_type  pos,
size_type  octet_idx 
) const
noexcept

return octet from the matrix

Parameters
pos- column position in the matrix
octet_idx- octet based row position (1 octet - 8 rows)

Definition at line 1295 of file bmbmatrix.h.

References BM_IS_GAP, BMGAP_PTR, bm::check_any_fullb(), FULL_BLOCK_FAKE_ADDR, bm::gap_test_unr(), bm::get_block_coord(), bm::set_block_mask, bm::set_block_shift, bm::set_word_mask, and bm::set_word_shift.

Referenced by bm::str_sparse_vector< CharType, BV, STR_SIZE >::get(), and TestBasicMatrix().

◆ get_row() [1/2]

template<typename BV >
const basic_bmatrix< BV >::bvector_type * bm::basic_bmatrix< BV >::get_row ( size_type  i) const
noexcept

◆ get_row() [2/2]

template<typename BV >
basic_bmatrix< BV >::bvector_type * bm::basic_bmatrix< BV >::get_row ( size_type  i)
noexcept

Get row bit-vector. Can return NULL

Definition at line 787 of file bmbmatrix.h.

References BM_ASSERT, and i.

◆ insert_column()

template<typename BV >
void bm::basic_bmatrix< BV >::insert_column ( size_type  idx,
size_type  row_from 
)

Insert value 0 into a range of rows

Parameters
idx- index (of column) / element of bit-vectors to erase
row_from- row to start from

Definition at line 848 of file bmbmatrix.h.

References i.

Referenced by bm::base_sparse_vector< Val, BV, MAX_SIZE >::insert_clear_value_planes_from().

◆ insert_octet()

template<typename BV >
void bm::basic_bmatrix< BV >::insert_octet ( size_type  pos,
size_type  octet_idx,
unsigned char  octet 
)

Bit-transpose and insert an octet and assign it to a bit-matrix

Parameters
pos- column position in the matrix
octet_idx- octet based row position (1 octet - 8 rows)
octet- value to assign

Definition at line 1232 of file bmbmatrix.h.

References BM_ASSERT, and row.

◆ is_dynamic()

template<typename BV >
bool bm::basic_bmatrix< BV >::is_dynamic ( ) const
inlinenoexcept

Return if matrix is dynamic resizable.

Definition at line 310 of file bmbmatrix.h.

Referenced by bm::basic_bmatrix< BV >::basic_bmatrix().

◆ is_same_structure()

template<typename BV >
bool bm::basic_bmatrix< BV >::is_same_structure ( const basic_bmatrix< BV > &  bbm) const
noexcept

Debugging function to check if two matrixes have the same rows created.

Returns
true - if the same

Definition at line 941 of file bmbmatrix.h.

References BM_ASSERT, and i.

◆ octet_size()

template<typename BV >
basic_bmatrix< BV >::size_type bm::basic_bmatrix< BV >::octet_size
noexcept

Return number of octet currently allocated rows in the matrix

Definition at line 913 of file bmbmatrix.h.

◆ operator=() [1/2]

template<typename BV >
basic_bmatrix<BV>& bm::basic_bmatrix< BV >::operator= ( basic_bmatrix< BV > &&  bbm)
inlinenoexcept

move assignmment operator

Definition at line 93 of file bmbmatrix.h.

◆ operator=() [2/2]

template<typename BV >
basic_bmatrix<BV>& bm::basic_bmatrix< BV >::operator= ( const basic_bmatrix< BV > &  bbm)
inline

Definition at line 82 of file bmbmatrix.h.

◆ optimize()

template<typename BV >
void bm::basic_bmatrix< BV >::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 re-allocs
opt_mode- requested compression depth
stat- memory allocation statistics after optimization

Definition at line 1547 of file bmbmatrix.h.

References BM_DECLARE_TEMP_BLOCK.

Referenced by bm::base_sparse_vector< Val, BV, MAX_SIZE >::optimize(), and TestBasicMatrix().

◆ optimize_block()

template<typename BV >
void bm::basic_bmatrix< BV >::optimize_block ( block_idx_type  nb,
typename BV::optmode  opt_mode 
)

Optimize block in all planes

Definition at line 1601 of file bmbmatrix.h.

References bm::get_block_coord(), and i.

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

◆ row()

template<typename BV >
const basic_bmatrix< BV >::bvector_type * bm::basic_bmatrix< BV >::row ( size_type  i) const
noexcept

◆ rows()

template<typename BV >
size_type bm::basic_bmatrix< BV >::rows ( ) const
inlinenoexcept

◆ rows_not_null()

template<typename BV >
size_type bm::basic_bmatrix< BV >::rows_not_null ( ) const
inlinenoexcept

get number of value rows without (not) NULLs bvector

Definition at line 143 of file bmbmatrix.h.

Referenced by bm::str_sparse_vector< CharType, BV, STR_SIZE >::decode_substr().

◆ set_allocator_pool()

template<typename BV >
void bm::basic_bmatrix< BV >::set_allocator_pool ( allocator_pool_type pool_ptr)
noexcept

Definition at line 965 of file bmbmatrix.h.

References i.

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

◆ set_null_idx()

template<typename BV >
void bm::basic_bmatrix< BV >::set_null_idx ( size_type  null_idx)
noexcept

set index of the NULL vector

Definition at line 796 of file bmbmatrix.h.

References BM_ASSERT.

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

◆ set_octet()

template<typename BV >
void bm::basic_bmatrix< BV >::set_octet ( size_type  pos,
size_type  octet_idx,
unsigned char  octet 
)

Bit-transpose an octet and assign it to a bit-matrix

Parameters
pos- column position in the matrix
octet_idx- octet based row position (1 octet - 8 rows)
octet- value to assign

Definition at line 1193 of file bmbmatrix.h.

References row.

Referenced by bm::str_sparse_vector< CharType, BV, STR_SIZE >::assign(), and TestBasicMatrix().

◆ swap()

template<typename BV >
void bm::basic_bmatrix< BV >::swap ( basic_bmatrix< BV > &  bbm)
noexcept

◆ swap_columns()

template<typename BV >
void bm::basic_bmatrix< BV >::swap_columns ( size_type  idx1,
size_type  idx2 
)

Swap columns (bits in all rows)

Parameters
idx1- column index 1
idx2- column index 2

Definition at line 870 of file bmbmatrix.h.

References i.

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

◆ throw_bad_alloc()

template<typename BV >
static void bm::basic_bmatrix< BV >::throw_bad_alloc ( )
inlinestaticprotected

Definition at line 326 of file bmbmatrix.h.

Friends And Related Function Documentation

◆ base_sparse_vector

template<typename BV >
template<typename Val , typename BVect , unsigned MAX_SIZE>
friend class base_sparse_vector
friend

Definition at line 329 of file bmbmatrix.h.

Member Data Documentation

◆ alloc_

template<typename BV >
allocator_type bm::basic_bmatrix< BV >::alloc_
protected

Definition at line 333 of file bmbmatrix.h.

Referenced by bm::basic_bmatrix< BV >::copy_from().

◆ ap_

template<typename BV >
allocation_policy_type bm::basic_bmatrix< BV >::ap_
protected

Definition at line 334 of file bmbmatrix.h.

Referenced by bm::basic_bmatrix< BV >::copy_from().

◆ bv_rows_

template<typename BV >
bvector_type_ptr* bm::basic_bmatrix< BV >::bv_rows_ = 0
protected

Definition at line 337 of file bmbmatrix.h.

Referenced by bm::basic_bmatrix< BV >::copy_from().

◆ bv_size_

template<typename BV >
size_type bm::basic_bmatrix< BV >::bv_size_
protected

Definition at line 332 of file bmbmatrix.h.

Referenced by bm::basic_bmatrix< BV >::copy_from().

◆ is_dynamic_

template<typename BV >
bool bm::basic_bmatrix< BV >::is_dynamic_ = true
protected

if rsize is dynamic (variable length)

Definition at line 339 of file bmbmatrix.h.

Referenced by bm::basic_bmatrix< BV >::basic_bmatrix(), and bm::basic_bmatrix< bm::bvector<> >::is_dynamic().

◆ null_idx_

template<typename BV >
size_type bm::basic_bmatrix< BV >::null_idx_ = 0
protected

◆ pool_

template<typename BV >
allocator_pool_type* bm::basic_bmatrix< BV >::pool_ = 0
protected

Definition at line 335 of file bmbmatrix.h.

Referenced by bm::basic_bmatrix< bm::bvector<> >::get_allocator_pool().

◆ rsize_

template<typename BV >
size_type bm::basic_bmatrix< BV >::rsize_ = 0
protected

The documentation for this class was generated from the following file:
Modified on Wed May 29 18:42:27 2024 by modify_doxy.py rev. 669887