BitMagic-C++
Public Types | Protected Member Functions | Static Protected Member Functions | Protected Attributes | Friends
bm::basic_bmatrix< BV > Class Template Reference
BitMagic Library

Basic dense bit-matrix class. More...

#include <bmbmatrix.h>

Collaboration diagram for bm::basic_bmatrix< BV >:
Collaboration graph
[legend]

Public Types

typedef BV bvector_type
 
typedef bvector_type * bvector_type_ptr
 
typedef const bvector_type * bvector_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 <br>
 basic_bmatrix (size_type rsize, allocation_policy_type ap=allocation_policy_type(), size_type bv_max_size=bm::id_max, const allocator_type &alloc=allocator_type())
  More...
 
 ~basic_bmatrix () BMNOEXCEPT
 
 basic_bmatrix (const basic_bmatrix< BV > &bbm)
  More...
 
basic_bmatrix< BV > & operator= (const basic_bmatrix< BV > &bbm)
  More...
 
 basic_bmatrix (basic_bmatrix< BV > &&bbm) BMNOEXCEPT
  More...
 
basic_bmatrix< BV > & operator= (basic_bmatrix< BV > &&bbm) BMNOEXCEPT
  More...
 
void set_allocator_pool (allocator_pool_type *pool_ptr) BMNOEXCEPT
  More...
 
allocator_pool_type * get_allocator_pool () const BMNOEXCEPT
  More...
 
content manipulation <br>
void swap (basic_bmatrix< BV > &bbm) BMNOEXCEPT
  More...
 
void copy_from (const basic_bmatrix< BV > &bbm)
  More...
 
void freeze ()
  More...
 
row access <br>
const bvector_type * row (size_type i) const BMNOEXCEPT
  More...
 
bvector_type_const_ptr get_row (size_type i) const BMNOEXCEPT
  More...
 
bvector_type * get_row (size_type i) BMNOEXCEPT
  More...
 
size_type rows () const BMNOEXCEPT
  More...
 
size_type rows_not_null () const BMNOEXCEPT
  More...
 
size_type calc_effective_rows_not_null () const BMNOEXCEPT
  More...
 
bvector_type_ptr construct_row (size_type row)
  More...
 
bvector_type_ptr construct_row (size_type row, const bvector_type &bv)
  More...
 
void destruct_row (size_type row)
  More...
 
void clear_row (size_type row, bool free_mem)
  More...
 
size_type get_null_idx () const BMNOEXCEPT
 return index of the NULL vector More...
 
void set_null_idx (size_type null_idx) BMNOEXCEPT
 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 () BMNOEXCEPT
 Free all rows. More...
 
octet access and transposition <br>
void set_octet (size_type pos, size_type octet_idx, unsigned char octet)
  More...
 
void insert_octet (size_type pos, size_type octet_idx, unsigned char octet)
  More...
 
unsigned char get_octet (size_type pos, size_type octet_idx) const BMNOEXCEPT
  More...
 
int compare_octet (size_type pos, size_type octet_idx, char octet) const BMNOEXCEPT
  More...
 
size_type octet_size () const BMNOEXCEPT
  More...
 
Utility functions <br>
const bm::word_t * get_block (size_type p, unsigned i, unsigned j) const BMNOEXCEPT
 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 BMNOEXCEPT
  More...
 
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)
  More...
 
void calc_stat (typename bvector_type::statistics &st, size_type rsize) const BMNOEXCEPT
  More...
 
void erase_column (size_type idx, bool erase_null)
  More...
 
void insert_column (size_type idx, size_type row_from)
  More...
 
void clear_column (size_type idx, size_type row_from)
  More...
 
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...
 

Protected Member Functions

bvector_type * construct_bvector (const bvector_type *bv) const
  More...
 
void destruct_bvector (bvector_type *bv) const
 

Static Protected Member Functions

static void throw_bad_alloc ()
 

Protected Attributes

size_type bv_size_
  More...
 
allocator_type alloc_
  More...
 
allocation_policy_type ap_
  More...
 
allocator_pool_type * pool_
  More...
 
bvector_type_ptr * bv_rows_
  More...
 
size_type rsize_
  More...
 
size_type null_idx_
 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.

Constructor & Destructor Documentation

◆ basic_bmatrix() [1/3]

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

Definition at line 694 of file bmbmatrix.h.

References bm::basic_bmatrix< BV >::allocate_rows().

◆ basic_bmatrix() [2/3]

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

copy-ctor

Definition at line 720 of file bmbmatrix.h.

References bm::basic_bmatrix< BV >::copy_from().

◆ basic_bmatrix() [3/3]

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

move-ctor

Definition at line 735 of file bmbmatrix.h.

Member Function Documentation

◆ allocate_rows()

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

allocate matrix rows of bit-vectors (new rows are NULLs)

Definition at line 854 of file bmbmatrix.h.

References BM_ASSERT.

Referenced by bm::basic_bmatrix< BV >::basic_bmatrix(), and bm::str_sparse_vector< CharType, BV, STR_SIZE >::import_no_check().

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

Referenced by bm::base_sparse_vector< Val, BV, MAX_SIZE >::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 948 of file bmbmatrix.h.

References bm::use_null.

Referenced by bm::base_sparse_vector< Val, BV, MAX_SIZE >::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

get number of assigned avlue rows without \ NULLs bvector

Definition at line 930 of file bmbmatrix.h.

◆ calc_stat()

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

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

References bm::bv_statistics::add().

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

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

References BM_ASSERT.

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

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

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

References bm::bvector< Alloc >::init().

◆ construct_row() [1/2]

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

Make sure row is constructed, return bit-vector

Definition at line 1004 of file bmbmatrix.h.

References BM_ASSERT, and construct_bvector().

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

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

References BM_ASSERT, and construct_bvector().

◆ copy_from()

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

Copy content

Definition at line 790 of file bmbmatrix.h.

References bm::basic_bmatrix< BV >::alloc_, bm::basic_bmatrix< BV >::ap_, bm::basic_bmatrix< BV >::bv_rows_, bm::basic_bmatrix< BV >::bv_size_, construct_bvector(), bm::basic_bmatrix< BV >::null_idx_, and bm::basic_bmatrix< BV >::rsize_.

Referenced by bm::basic_bmatrix< BV >::basic_bmatrix(), and bm::basic_bmatrix< BV >::operator=().

◆ destruct_row()

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

destruct/deallocate row

Definition at line 1036 of file bmbmatrix.h.

References BM_ASSERT.

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

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

◆ free_rows()

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

Free all rows.

Definition at line 896 of file bmbmatrix.h.

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

◆ freeze()

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

Freeze content into read-only mode drop editing overhead

Definition at line 1456 of file bmbmatrix.h.

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

◆ get_allocator_pool()

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

Definition at line 105 of file bmbmatrix.h.

References bm::basic_bmatrix< BV >::pool_.

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

◆ get_block()

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

Get low level internal access to.

Definition at line 1115 of file bmbmatrix.h.

◆ get_half_octet()

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

Definition at line 1366 of file bmbmatrix.h.

References BM_IS_GAP, BMGAP_PTR, FULL_BLOCK_FAKE_ADDR, bm::gap_test_unr(), bm::set_array_mask, bm::set_array_shift, bm::set_block_mask, bm::set_block_shift, bm::set_word_mask, bm::set_word_shift, bm::test_4bits(), and bm::test_4gaps().

◆ get_null_idx()

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

return index of the NULL vector

Definition at line 161 of file bmbmatrix.h.

References bm::basic_bmatrix< BV >::null_idx_.

Referenced by bm::base_sparse_vector< Val, BV, MAX_SIZE >::copy_from(), bm::base_sparse_vector< Val, BV, MAX_SIZE >::get_null_bvect(), bm::base_sparse_vector< Val, BV, MAX_SIZE >::get_null_bvector(), bm::base_sparse_vector< Val, BV, MAX_SIZE >::is_nullable(), bm::sparse_vector< Val, BV >::join_null_slice(), and bm::base_sparse_vector< Val, BV, MAX_SIZE >::merge_matr().

◆ get_octet()

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

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

References BM_IS_GAP, BMGAP_PTR, FULL_BLOCK_FAKE_ADDR, bm::gap_test_unr(), bm::set_array_mask, bm::set_array_shift, 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().

◆ get_row() [1/2]

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

Get row bit-vector. Can return NULL

Definition at line 771 of file bmbmatrix.h.

References BM_ASSERT.

◆ get_row() [2/2]

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

Get row bit-vector. Can return NULL

Definition at line 761 of file bmbmatrix.h.

References BM_ASSERT.

Referenced by bm::str_sparse_vector< CharType, BV, STR_SIZE >::decode_substr(), bm::base_sparse_vector< Val, BV, MAX_SIZE >::get_null_bvect(), bm::base_sparse_vector< Val, BV, MAX_SIZE >::get_null_bvector(), bm::base_sparse_vector< Val, BV, MAX_SIZE >::merge_matr(), and bm::base_sparse_vector< Val, BV, MAX_SIZE >::slice().

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

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

References BM_ASSERT.

◆ octet_size()

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

Return number of octet currently allocated rows in the matrix

Definition at line 886 of file bmbmatrix.h.

◆ operator=() [1/2]

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

move assignmment operator

Definition at line 92 of file bmbmatrix.h.

References bm::basic_bmatrix< BV >::free_rows(), and bm::basic_bmatrix< BV >::swap().

◆ operator=() [2/2]

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

Definition at line 81 of file bmbmatrix.h.

References bm::basic_bmatrix< BV >::copy_from().

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

References bm::bv_statistics::add(), BM_DECLARE_TEMP_BLOCK, and bm::bv_statistics::reset().

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

References bm::get_block_coord().

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

◆ row()

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

Get row bit-vector. Can return NULL

Definition at line 751 of file bmbmatrix.h.

References BM_ASSERT.

Referenced by bm::base_sparse_vector< Val, BV, MAX_SIZE >::copy_from(), bm::base_sparse_vector< Val, BV, MAX_SIZE >::copy_range_slices(), bm::base_sparse_vector< Val, BV, MAX_SIZE >::get_slice(), and bm::sparse_vector< Val, BV >::join().

◆ rows()

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

get number of value rows

Definition at line 139 of file bmbmatrix.h.

References bm::basic_bmatrix< BV >::rsize_.

Referenced by bm::base_sparse_vector< Val, BV, MAX_SIZE >::copy_from(), bm::base_sparse_vector< Val, BV, MAX_SIZE >::copy_range_slices(), bm::sparse_vector< Val, BV >::join(), bm::base_sparse_vector< Val, BV, MAX_SIZE >::merge_matr(), and bm::str_sparse_vector< CharType, BV, STR_SIZE >::remap_from_impl().

◆ rows_not_null()

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

get number of value rows without (not) NULLs bvector

Definition at line 142 of file bmbmatrix.h.

References bm::basic_bmatrix< BV >::null_idx_, and bm::basic_bmatrix< BV >::rsize_.

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)

Definition at line 914 of file bmbmatrix.h.

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

◆ set_null_idx()

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

set index of the NULL vector

Definition at line 780 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 1139 of file bmbmatrix.h.

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

◆ swap()

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

Swap content

Definition at line 973 of file bmbmatrix.h.

References bm::xor_swap().

Referenced by bm::base_sparse_vector< Val, BV, MAX_SIZE >::base_sparse_vector(), and bm::basic_bmatrix< BV >::operator=().

Field Documentation

◆ alloc_

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

Definition at line 318 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 319 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_
protected

Definition at line 322 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 317 of file bmbmatrix.h.

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

◆ null_idx_

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

Index of the NULL row.

Definition at line 324 of file bmbmatrix.h.

Referenced by bm::basic_bmatrix< BV >::copy_from(), bm::basic_bmatrix< BV >::get_null_idx(), bm::base_sparse_vector< Val, BV, MAX_SIZE >::mark_null_idx(), and bm::basic_bmatrix< BV >::rows_not_null().

◆ pool_

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

Definition at line 320 of file bmbmatrix.h.

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

◆ rsize_

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

Definition at line 323 of file bmbmatrix.h.

Referenced by bm::basic_bmatrix< BV >::copy_from(), bm::basic_bmatrix< BV >::rows(), and bm::basic_bmatrix< BV >::rows_not_null().

The documentation for this class was generated from the following file:
Generated by doxygen 1.9.2