BitMagic-C++
bm::basic_bmatrix< BV > Class Template Reference

Basic dense bit-matrix class. More...

#include <bmbmatrix.h>

Collaboration diagram for bm::basic_bmatrix< BV >:

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
 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())
 ~basic_bmatrix () BMNOEXCEPT
 basic_bmatrix (const basic_bmatrix< BV > &bbm)
basic_bmatrix< BV > & operator= (const basic_bmatrix< BV > &bbm)
 basic_bmatrix (basic_bmatrix< BV > &&bbm) BMNOEXCEPT
basic_bmatrix< BV > & operator= (basic_bmatrix< BV > &&bbm) BMNOEXCEPT
void set_allocator_pool (allocator_pool_type *pool_ptr) BMNOEXCEPT
content manipulation
void swap (basic_bmatrix< BV > &bbm) BMNOEXCEPT
void copy_from (const basic_bmatrix< BV > &bbm)
row access
const bvector_type * row (size_type i) const BMNOEXCEPT
bvector_type_const_ptr get_row (size_type i) const BMNOEXCEPT
bvector_type * get_row (size_type i) BMNOEXCEPT
size_type rows () const BMNOEXCEPT
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)
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 BMNOEXCEPT
int compare_octet (size_type pos, size_type octet_idx, char octet) const BMNOEXCEPT
Utility function
bool test_4rows (unsigned i) const BMNOEXCEPT
 Test if 4 rows from i are not NULL.
const bm::word_t * get_block (size_type p, unsigned i, unsigned j) const BMNOEXCEPT
 Get low level internal access to.
unsigned get_half_octet (size_type pos, size_type row_idx) const BMNOEXCEPT
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
void optimize_block (block_idx_type nb)

Protected Member Functions

void allocate_rows (size_type rsize)
void free_rows () BMNOEXCEPT
bvector_type * construct_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_type * pool_
bvector_type_ptr * bv_rows_
size_type rsize_

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 53 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 60 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 61 of file bmbmatrix.h.

◆ allocator_type

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

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

◆ bvector_type

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

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

◆ bvector_type_ptr

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

Definition at line 57 of file bmbmatrix.h.

◆ octet_type

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

Definition at line 64 of file bmbmatrix.h.

◆ size_type

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

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

References alloc_, allocate_rows(), ap_, bv_rows_, bv_size_, pool_, and rsize_.

Referenced by basic_bmatrix(), basic_bmatrix(), copy_from(), operator=(), operator=(), and swap().

◆ ~basic_bmatrix()

template<typename BV>
bm::basic_bmatrix< BV >::~basic_bmatrix ( )

Definition at line 523 of file bmbmatrix.h.

References BMNOEXCEPT, and free_rows().

◆ basic_bmatrix() [2/3]

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

copy-ctor

Definition at line 531 of file bmbmatrix.h.

References alloc_, ap_, basic_bmatrix(), bv_rows_, bv_size_, copy_from(), pool_, and rsize_.

◆ basic_bmatrix() [3/3]

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

move-ctor

Definition at line 545 of file bmbmatrix.h.

References alloc_, ap_, basic_bmatrix(), BMNOEXCEPT, bv_rows_, bv_size_, pool_, rsize_, and swap().

Member Function Documentation

◆ allocate_rows()

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

Definition at line 643 of file bmbmatrix.h.

References alloc_, BM_ASSERT, bv_rows_, rsize_, and throw_bad_alloc().

Referenced by basic_bmatrix().

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

References BMNOEXCEPT, and get_octet().

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

References alloc_, ap_, and bv_size_.

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

References BM_ASSERT, bv_rows_, construct_bvector(), row(), and rsize_.

Referenced by insert_octet(), and set_octet().

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

References BM_ASSERT, bv_rows_, construct_bvector(), row(), and rsize_.

◆ copy_from()

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

Copy content

Definition at line 610 of file bmbmatrix.h.

References alloc_, ap_, basic_bmatrix(), bv_rows_, bv_size_, construct_bvector(), free_rows(), rsize_, and throw_bad_alloc().

Referenced by basic_bmatrix(), and operator=().

◆ destruct_bvector()

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

Definition at line 790 of file bmbmatrix.h.

Referenced by destruct_row(), and free_rows().

◆ destruct_row()

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

Definition at line 749 of file bmbmatrix.h.

References BM_ASSERT, bv_rows_, destruct_bvector(), row(), and rsize_.

◆ free_rows()

template<typename BV>
void bm::basic_bmatrix< BV >::free_rows ( )
protected

Definition at line 664 of file bmbmatrix.h.

References alloc_, BMNOEXCEPT, bv_rows_, destruct_bvector(), and rsize_.

Referenced by copy_from(), operator=(), and ~basic_bmatrix().

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

References BMNOEXCEPT, and row().

Referenced by get_half_octet(), and get_octet().

◆ get_half_octet()

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

References BM_IS_GAP, BMGAP_PTR, BMNOEXCEPT, FULL_BLOCK_FAKE_ADDR, bm::gap_test_unr(), get_block(), 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 compare_octet().

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

References BM_ASSERT, BMNOEXCEPT, bv_rows_, and rsize_.

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

References BM_ASSERT, BMNOEXCEPT, bv_rows_, and rsize_.

Referenced by insert_octet(), bm::sparse_vector< Val, BV >::merge(), optimize(), optimize_block(), and set_octet().

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

References BM_ASSERT, construct_row(), get_row(), row(), and rsize_.

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

References basic_bmatrix(), BMNOEXCEPT, free_rows(), and swap().

◆ operator=() [2/2]

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

Definition at line 79 of file bmbmatrix.h.

References basic_bmatrix(), and 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 1082 of file bmbmatrix.h.

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

◆ optimize_block()

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

Optimize block in all planes

Definition at line 1112 of file bmbmatrix.h.

References bm::get_block_coord(), get_row(), and rsize_.

◆ row()

◆ rows()

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

get number of value rows

Definition at line 132 of file bmbmatrix.h.

References BMNOEXCEPT, and rsize_.

◆ set_allocator_pool()

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

Definition at line 101 of file bmbmatrix.h.

References BMNOEXCEPT, and pool_.

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

References BM_ASSERT, construct_row(), get_row(), row(), and rsize_.

◆ swap()

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

Swap content

Definition at line 685 of file bmbmatrix.h.

References alloc_, ap_, basic_bmatrix(), BMNOEXCEPT, bv_rows_, bv_size_, pool_, rsize_, and bm::xor_swap().

Referenced by basic_bmatrix(), and operator=().

◆ test_4rows()

template<typename BV>
bool bm::basic_bmatrix< BV >::test_4rows ( unsigned i) const

Test if 4 rows from i are not NULL.

Definition at line 589 of file bmbmatrix.h.

References BM_ASSERT, BMNOEXCEPT, bv_rows_, and rsize_.

◆ throw_bad_alloc()

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

Definition at line 233 of file bmbmatrix.h.

References throw_bad_alloc().

Referenced by allocate_rows(), copy_from(), and throw_bad_alloc().

Field Documentation

◆ alloc_

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

◆ ap_

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

◆ bv_rows_

◆ bv_size_

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

◆ pool_

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

Definition at line 240 of file bmbmatrix.h.

Referenced by basic_bmatrix(), basic_bmatrix(), basic_bmatrix(), set_allocator_pool(), and swap().

◆ rsize_


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