bm::bvector< Alloc > Class Template Reference

bitvector with runtime compression of bits. More...

#include <vs10/bm/bm.h>

Data Structures
class	counted_enumerator
	Constant input iterator designed to enumerate "ON" bits counted_enumerator keeps bitcount, ie number of ON bits starting from the position 0 in the bit string up to the currently enumerated bit. More...
class	enumerator
	Constant input iterator designed to enumerate "ON" bits. More...
class	insert_iterator
	Output iterator iterator designed to set "ON" bits based on input sequence of integers (bit indeces). More...
class	iterator_base
	Base class for all iterators. More...
class	reference
	Class reference implements an object for bit assignment. More...
struct	statistics
	Statistical information about bitset's memory allocation details. More...
Public Types
enum	optmode {   opt_free_0 = 1, opt_free_01 = 2, opt_compress = 3, opt_free_0 = 1,   opt_free_01 = 2, opt_compress = 3 }
	Optimization mode Every next level means additional checks (better compression vs time) More...
enum	optmode {   opt_free_0 = 1, opt_free_01 = 2, opt_compress = 3, opt_free_0 = 1,   opt_free_01 = 2, opt_compress = 3 }
	Optimization mode Every next level means additional checks (better compression vs time) More...
typedef Alloc	allocator_type
typedef blocks_manager< Alloc >	blocks_manager_type
typedef bm::id_t	size_type
	Type used to count bits in the bit vector.
typedef bool	const_reference
typedef Alloc	allocator_type
typedef blocks_manager< Alloc >	blocks_manager_type
typedef bm::id_t	size_type
	Type used to count bits in the bit vector.
typedef bool	const_reference
Public Member Functions
	bvector (strategy strat=BM_BIT, const gap_word_t *glevel_len=bm::gap_len_table< true >::_len, size_type bv_size=bm::id_max, const Alloc &alloc=Alloc())
	Constructs bvector class.
	bvector (size_type bv_size, strategy strat=BM_BIT, const gap_word_t *glevel_len=bm::gap_len_table< true >::_len, const Alloc &alloc=Alloc())
	Constructs bvector class.
	bvector (const bvector< Alloc > &bvect)
bvector &	operator= (const bvector< Alloc > &bvect)
reference	operator[] (bm::id_t n)
bool	operator[] (bm::id_t n) const
void	operator&= (const bvector< Alloc > &bvect)
void	operator^= (const bvector< Alloc > &bvect)
void	operator|= (const bvector< Alloc > &bvect)
void	operator-= (const bvector< Alloc > &bvect)
bool	operator< (const bvector< Alloc > &bvect) const
bool	operator<= (const bvector< Alloc > &bvect) const
bool	operator> (const bvector< Alloc > &bvect) const
bool	operator>= (const bvector< Alloc > &bvect) const
bool	operator== (const bvector< Alloc > &bvect) const
bool	operator!= (const bvector< Alloc > &bvect) const
bvector< Alloc >	operator~ () const
Alloc	get_allocator () const
bool	set_bit (bm::id_t n, bool val=true)
	Sets bit n.
bool	set_bit_and (bm::id_t n, bool val=true)
	Sets bit n using bit AND with the provided value.
bool	set_bit_conditional (bm::id_t n, bool val, bool condition)
	Sets bit n only if current value is equal to the condition.
bvector< Alloc > &	set (bm::id_t n, bool val=true)
	Sets bit n if val is true, clears bit n if val is false.
bvector< Alloc > &	set ()
	Sets every bit in this bitset to 1.
bvector< Alloc > &	set_range (bm::id_t left, bm::id_t right, bool value=true)
	Sets all bits in the specified closed interval [left,right] Interval must be inside the bvector's size. This method DOES NOT resize vector.
insert_iterator	inserter ()
void	clear_bit (bm::id_t n)
	Clears bit n.
void	clear (bool free_mem=false)
	Clears every bit in the bitvector.
bvector< Alloc > &	reset ()
	Clears every bit in the bitvector.
bm::id_t	count () const
	Returns count of bits which are 1.
size_type	capacity () const
	Returns bvector's capacity (number of bits it can store)
size_type	size () const
	return current size of the vector (bits)
void	resize (size_type new_size)
	Change size of the bvector.
unsigned	count_blocks (unsigned *arr) const
	Computes bitcount values for all bvector blocks.
bm::id_t	count_range (bm::id_t left, bm::id_t right, unsigned *block_count_arr=0) const
	Returns count of 1 bits in the given diapason.
bm::id_t	recalc_count ()
void	forget_count ()
bvector< Alloc > &	invert ()
	Inverts all bits.
bool	get_bit (bm::id_t n) const
	returns true if bit n is set and false is bit n is 0.
bool	test (bm::id_t n) const
	returns true if bit n is set and false is bit n is 0.
bool	any () const
	Returns true if any bits in this bitset are set, and otherwise returns false.
bool	none () const
	Returns true if no bits are set, otherwise returns false.
bvector< Alloc > &	flip (bm::id_t n)
	Flips bit n.
bvector< Alloc > &	flip ()
	Flips all bits.
void	swap (bvector< Alloc > &bv)
	Exchanges content of bv and this bitvector.
bm::id_t	get_first () const
	Gets number of first bit which is ON.
bm::id_t	get_next (bm::id_t prev) const
	Finds the number of the next bit ON.
bm::id_t	extract_next (bm::id_t prev)
	Finds the number of the next bit ON and sets it to 0.
void	calc_stat (struct bm::bvector< Alloc >::statistics *st) const
	Calculates bitvector statistics.
bm::bvector< Alloc > &	bit_or (const bm::bvector< Alloc > &vect)
	Logical OR operation.
bm::bvector< Alloc > &	bit_and (const bm::bvector< Alloc > &vect)
	Logical AND operation.
bm::bvector< Alloc > &	bit_xor (const bm::bvector< Alloc > &vect)
	Logical XOR operation.
bm::bvector< Alloc > &	bit_sub (const bm::bvector< Alloc > &vect)
	Logical SUB operation.
void	set_new_blocks_strat (strategy strat)
	Sets new blocks allocation strategy.
strategy	get_new_blocks_strat () const
	Returns blocks allocation strategy.
void	optimize (bm::word_t *temp_block=0, optmode opt_mode=opt_compress, statistics *stat=0)
	Optimize memory bitvector's memory allocation.
void	optimize_gap_size ()
	Optimize sizes of GAP blocks.
void	set_gap_levels (const gap_word_t *glevel_len)
	Sets new GAP lengths table. All GAP blocks will be reallocated to match the new scheme.
int	compare (const bvector< Alloc > &bvect) const
	Lexicographical comparison with a bitvector.
bm::word_t *	allocate_tempblock () const
	Allocates temporary block of memory.
void	free_tempblock (bm::word_t *block) const
	Frees temporary block of memory.
enumerator	first () const
	Returns enumerator pointing on the first non-zero bit.
enumerator	end () const
	Returns enumerator pointing on the next bit after the last.
const bm::word_t *	get_block (unsigned nb) const
void	combine_operation (const bm::bvector< Alloc > &bvect, bm::operation opcode)
void	combine_operation_with_block (unsigned nb, const bm::word_t *arg_blk, int arg_gap, bm::operation opcode)
const blocks_manager_type &	get_blocks_manager () const
blocks_manager_type &	get_blocks_manager ()
	bvector (strategy strat=BM_BIT, const gap_word_t *glevel_len=bm::gap_len_table< true >::_len, size_type bv_size=bm::id_max, const Alloc &alloc=Alloc())
	Constructs bvector class.
	bvector (size_type bv_size, strategy strat=BM_BIT, const gap_word_t *glevel_len=bm::gap_len_table< true >::_len, const Alloc &alloc=Alloc())
	Constructs bvector class.
	bvector (const bvector< Alloc > &bvect)
bvector &	operator= (const bvector< Alloc > &bvect)
reference	operator[] (bm::id_t n)
bool	operator[] (bm::id_t n) const
void	operator&= (const bvector< Alloc > &bvect)
void	operator^= (const bvector< Alloc > &bvect)
void	operator|= (const bvector< Alloc > &bvect)
void	operator-= (const bvector< Alloc > &bvect)
bool	operator< (const bvector< Alloc > &bvect) const
bool	operator<= (const bvector< Alloc > &bvect) const
bool	operator> (const bvector< Alloc > &bvect) const
bool	operator>= (const bvector< Alloc > &bvect) const
bool	operator== (const bvector< Alloc > &bvect) const
bool	operator!= (const bvector< Alloc > &bvect) const
bvector< Alloc >	operator~ () const
Alloc	get_allocator () const
bool	set_bit (bm::id_t n, bool val=true)
	Sets bit n.
bool	set_bit_and (bm::id_t n, bool val=true)
	Sets bit n using bit AND with the provided value.
bool	set_bit_conditional (bm::id_t n, bool val, bool condition)
	Sets bit n only if current value is equal to the condition.
bvector< Alloc > &	set (bm::id_t n, bool val=true)
	Sets bit n if val is true, clears bit n if val is false.
bvector< Alloc > &	set ()
	Sets every bit in this bitset to 1.
bvector< Alloc > &	set_range (bm::id_t left, bm::id_t right, bool value=true)
	Sets all bits in the specified closed interval [left,right] Interval must be inside the bvector's size. This method DOES NOT resize vector.
insert_iterator	inserter ()
void	clear_bit (bm::id_t n)
	Clears bit n.
void	clear (bool free_mem=false)
	Clears every bit in the bitvector.
bvector< Alloc > &	reset ()
	Clears every bit in the bitvector.
bm::id_t	count () const
	Returns count of bits which are 1.
size_type	capacity () const
	Returns bvector's capacity (number of bits it can store)
size_type	size () const
	return current size of the vector (bits)
void	resize (size_type new_size)
	Change size of the bvector.
unsigned	count_blocks (unsigned *arr) const
	Computes bitcount values for all bvector blocks.
bm::id_t	count_range (bm::id_t left, bm::id_t right, unsigned *block_count_arr=0) const
	Returns count of 1 bits in the given diapason.
bm::id_t	recalc_count ()
void	forget_count ()
bvector< Alloc > &	invert ()
	Inverts all bits.
bool	get_bit (bm::id_t n) const
	returns true if bit n is set and false is bit n is 0.
bool	test (bm::id_t n) const
	returns true if bit n is set and false is bit n is 0.
bool	any () const
	Returns true if any bits in this bitset are set, and otherwise returns false.
bool	none () const
	Returns true if no bits are set, otherwise returns false.
bvector< Alloc > &	flip (bm::id_t n)
	Flips bit n.
bvector< Alloc > &	flip ()
	Flips all bits.
void	swap (bvector< Alloc > &bv)
	Exchanges content of bv and this bitvector.
bm::id_t	get_first () const
bm::id_t	get_next (bm::id_t prev) const
bm::id_t	extract_next (bm::id_t prev)
void	calc_stat (struct bm::bvector< Alloc >::statistics *st) const
	Calculates bitvector statistics.
bm::bvector< Alloc > &	bit_or (const bm::bvector< Alloc > &vect)
	Logical OR operation.
bm::bvector< Alloc > &	bit_and (const bm::bvector< Alloc > &vect)
	Logical AND operation.
bm::bvector< Alloc > &	bit_xor (const bm::bvector< Alloc > &vect)
	Logical XOR operation.
bm::bvector< Alloc > &	bit_sub (const bm::bvector< Alloc > &vect)
	Logical SUB operation.
void	set_new_blocks_strat (strategy strat)
	Sets new blocks allocation strategy.
strategy	get_new_blocks_strat () const
	Returns blocks allocation strategy.
void	optimize (bm::word_t *temp_block=0, optmode opt_mode=opt_compress, statistics *stat=0)
	Optimize memory bitvector's memory allocation.
void	optimize_gap_size ()
	Optimize sizes of GAP blocks.
void	set_gap_levels (const gap_word_t *glevel_len)
	Sets new GAP lengths table. All GAP blocks will be reallocated to match the new scheme.
int	compare (const bvector< Alloc > &bvect) const
	Lexicographical comparison with a bitvector.
bm::word_t *	allocate_tempblock () const
	Allocates temporary block of memory.
void	free_tempblock (bm::word_t *block) const
	Frees temporary block of memory.
enumerator	first () const
	Returns enumerator pointing on the first non-zero bit.
enumerator	end () const
const bm::word_t *	get_block (unsigned nb) const
void	combine_operation (const bm::bvector< Alloc > &bvect, bm::operation opcode)
void	combine_operation_with_block (unsigned nb, const bm::word_t *arg_blk, int arg_gap, bm::operation opcode)
const blocks_manager_type &	get_blocks_manager () const
blocks_manager_type &	get_blocks_manager ()
Private Member Functions
bm::id_t	check_or_next (bm::id_t prev) const
bm::id_t	check_or_next_extract (bm::id_t prev)
	check if specified bit is 1, and set it to 0 if specified bit is 0, scan for the next 1 and returns it if no 1 found returns 0
bool	set_bit_no_check (bm::id_t n, bool val)
	Set specified bit without checking preconditions (size, etc)
bool	and_bit_no_check (bm::id_t n, bool val)
	AND specified bit without checking preconditions (size, etc)
bool	set_bit_conditional_impl (bm::id_t n, bool val, bool condition)
void	combine_operation_with_block (unsigned nb, unsigned gap, bm::word_t *blk, const bm::word_t *arg_blk, int arg_gap, bm::operation opcode)
void	combine_count_operation_with_block (unsigned nb, const bm::word_t *arg_blk, int arg_gap, bm::operation opcode)
void	extend_gap_block (unsigned nb, gap_word_t *blk)
	Extends GAP block to the next level or converts it to bit block.
void	set_range_no_check (bm::id_t left, bm::id_t right, bool value)
	Set range without validity checking.
bm::id_t	check_or_next (bm::id_t prev) const
bm::id_t	check_or_next_extract (bm::id_t prev)
	check if specified bit is 1, and set it to 0 if specified bit is 0, scan for the next 1 and returns it if no 1 found returns 0
bool	set_bit_no_check (bm::id_t n, bool val)
	Set specified bit without checking preconditions (size, etc)
bool	and_bit_no_check (bm::id_t n, bool val)
	AND specified bit without checking preconditions (size, etc)
bool	set_bit_conditional_impl (bm::id_t n, bool val, bool condition)
void	combine_operation_with_block (unsigned nb, unsigned gap, bm::word_t *blk, const bm::word_t *arg_blk, int arg_gap, bm::operation opcode)
void	combine_count_operation_with_block (unsigned nb, const bm::word_t *arg_blk, int arg_gap, bm::operation opcode)
void	extend_gap_block (unsigned nb, gap_word_t *blk)
	Extends GAP block to the next level or converts it to bit block.
void	set_range_no_check (bm::id_t left, bm::id_t right, bool value)
	Set range without validity checking.
Private Attributes
blocks_manager_type	blockman_
	bitblocks manager
strategy	new_blocks_strat_
	block allocation strategy
size_type	size_
	size in bits
Friends
class	iterator_base
class	enumerator

---

Detailed Description

template<class Alloc>
class bm::bvector< Alloc >

bitvector with runtime compression of bits.

Definition at line 120 of file bm.h.

---

Member Typedef Documentation

template<class Alloc>

typedef Alloc bm::bvector< Alloc >::allocator_type

Definition at line 124 of file bm.h.

template<class Alloc>

typedef Alloc bm::bvector< Alloc >::allocator_type

Definition at line 124 of file bm.h.

template<class Alloc>

typedef blocks_manager<Alloc> bm::bvector< Alloc >::blocks_manager_type

Definition at line 125 of file bm.h.

template<class Alloc>

typedef blocks_manager<Alloc> bm::bvector< Alloc >::blocks_manager_type

Definition at line 125 of file bm.h.

template<class Alloc>

typedef bool bm::bvector< Alloc >::const_reference

Definition at line 225 of file bm.h.

template<class Alloc>

typedef bool bm::bvector< Alloc >::const_reference

Definition at line 225 of file bm.h.

template<class Alloc>

typedef bm::id_t bm::bvector< Alloc >::size_type

Type used to count bits in the bit vector.

Definition at line 127 of file bm.h.

template<class Alloc>

typedef bm::id_t bm::bvector< Alloc >::size_type

Type used to count bits in the bit vector.

Definition at line 127 of file bm.h.

---

Member Enumeration Documentation

template<class Alloc>

enum bm::bvector::optmode

Optimization mode Every next level means additional checks (better compression vs time)

See also:

optimize

Enumerator:

opt_free_0	Free unused 0 blocks.
opt_free_01	Free unused 0 and 1 blocks.
opt_compress	compress blocks when possible
opt_free_0	Free unused 0 blocks.
opt_free_01	Free unused 0 and 1 blocks.
opt_compress	compress blocks when possible

Definition at line 1350 of file bm.h.

template<class Alloc>

enum bm::bvector::optmode

Optimization mode Every next level means additional checks (better compression vs time)

See also:

optimize

Enumerator:

opt_free_0	Free unused 0 blocks.
opt_free_01	Free unused 0 and 1 blocks.
opt_compress	compress blocks when possible
opt_free_0	Free unused 0 blocks.
opt_free_01	Free unused 0 and 1 blocks.
opt_compress	compress blocks when possible

Definition at line 1350 of file bm.h.

---

Constructor & Destructor Documentation

template<class Alloc>

bm::bvector< Alloc >::bvector	(	strategy	strat = BM_BIT,
		const gap_word_t *	glevel_len = bm::gap_len_table<true>::_len,
		size_type	bv_size = bm::id_max,
		const Alloc &	alloc = Alloc()
	)		[inline]

Constructs bvector class.

Parameters:

strat	- operation mode strategy, BM_BIT - default strategy, bvector use plain bitset blocks, (performance oriented strategy). BM_GAP - memory effitent strategy, bvector allocates blocks as array of intervals(gaps) and convert blocks into plain bitsets only when enthropy grows.
glevel_len	pointer on C-style array keeping GAP block sizes. (Put bm::gap_len_table_min<true>::_len for GAP memory saving mode)
bv_size	bvector size (number of bits addressable by bvector), bm::id_max means "no limits" (recommended). bit vector allocates this space dynamically on demand.

See also:

bm::gap_len_table bm::gap_len_table_min set_new_blocks_strat

Definition at line 839 of file bm.h.

template<class Alloc>

bm::bvector< Alloc >::bvector	(	size_type	bv_size,
		strategy	strat = BM_BIT,
		const gap_word_t *	glevel_len = bm::gap_len_table<true>::_len,
		const Alloc &	alloc = Alloc()
	)		[inline]

Constructs bvector class.

Definition at line 851 of file bm.h.

template<class Alloc>

bm::bvector< Alloc >::bvector

(

const bvector< Alloc > &

bvect

)

[inline]

Definition at line 861 of file bm.h.

template<class Alloc>

bm::bvector< Alloc >::bvector	(	strategy	strat = BM_BIT,
		const gap_word_t *	glevel_len = bm::gap_len_table<true>::_len,
		size_type	bv_size = bm::id_max,
		const Alloc &	alloc = Alloc()
	)		[inline]

Constructs bvector class.

Parameters:

strat	- operation mode strategy, BM_BIT - default strategy, bvector use plain bitset blocks, (performance oriented strategy). BM_GAP - memory effitent strategy, bvector allocates blocks as array of intervals(gaps) and convert blocks into plain bitsets only when enthropy grows.
glevel_len	pointer on C-style array keeping GAP block sizes. (Put bm::gap_len_table_min<true>::_len for GAP memory saving mode)
bv_size	bvector size (number of bits addressable by bvector), bm::id_max means "no limits" (recommended). bit vector allocates this space dynamically on demand.

See also:

bm::gap_len_table bm::gap_len_table_min set_new_blocks_strat

Definition at line 839 of file bm.h.

template<class Alloc>

bm::bvector< Alloc >::bvector	(	size_type	bv_size,
		strategy	strat = BM_BIT,
		const gap_word_t *	glevel_len = bm::gap_len_table<true>::_len,
		const Alloc &	alloc = Alloc()
	)		[inline]

Constructs bvector class.

Definition at line 851 of file bm.h.

template<class Alloc>

bm::bvector< Alloc >::bvector

(

const bvector< Alloc > &

bvect

)

[inline]

Definition at line 861 of file bm.h.

---

Member Function Documentation

template<class Alloc>

bm::word_t* bm::bvector< Alloc >::allocate_tempblock

(

)

const [inline]

Allocates temporary block of memory.

Temp block can be passed to bvector functions requiring some temp memory for their operation. (like serialize)

Note:

method is marked const, but it's not quite true, since it can in some cases modify the state of the block allocator (if it has a state). (Can be important in MT programs).

See also:

free_tempblock

Definition at line 1411 of file bm.h.

References bm::bvector< Alloc >::blockman_, and bm::blocks_manager< Alloc >::get_allocator().

template<class Alloc>

bm::word_t* bm::bvector< Alloc >::allocate_tempblock

(

)

const [inline]

Allocates temporary block of memory.

Temp block can be passed to bvector functions requiring some temp memory for their operation. (like serialize)

Note:

method is marked const, but it's not quite true, since it can in some cases modify the state of the block allocator (if it has a state). (Can be important in MT programs).

See also:

free_tempblock

Definition at line 1411 of file bm.h.

References bm::bvector< Alloc >::blockman_, and bm::blocks_manager< Alloc >::get_allocator().

template<class Alloc >

bool bm::bvector< Alloc >::and_bit_no_check	(	bm::id_t	n,
		bool	val
	)		[private]

AND specified bit without checking preconditions (size, etc)

Definition at line 2284 of file bm.h.

References BMCOUNT_ADJ, BMCOUNT_DEC, BMCOUNT_INC, BMGAP_PTR, bm::gap_limit(), bm::gap_set_value(), bm::gap_test(), bm::set_block_mask, bm::set_block_shift, bm::set_word_mask, and bm::set_word_shift.

Referenced by bm::bvector< Alloc >::set_bit_and().

template<class Alloc>

bool bm::bvector< Alloc >::and_bit_no_check	(	bm::id_t	n,
		bool	val
	)		[private]

AND specified bit without checking preconditions (size, etc)

template<class Alloc>

bool bm::bvector< Alloc >::any

(

)

const [inline]

Returns true if any bits in this bitset are set, and otherwise returns false.

Returns:

true if any bit is set

Definition at line 1174 of file bm.h.

References bm::bvector< Alloc >::blockman_, bm::blocks_manager< Alloc >::effective_top_block_size(), bm::for_each_nzblock_if(), and bm::blocks_manager< Alloc >::get_rootblock().

Referenced by bm::bvector< Alloc >::none().

template<class Alloc>

bool bm::bvector< Alloc >::any

(

)

const [inline]

Returns true if any bits in this bitset are set, and otherwise returns false.

Returns:

true if any bit is set

Definition at line 1174 of file bm.h.

References bm::bvector< Alloc >::blockman_, bm::blocks_manager< Alloc >::effective_top_block_size(), bm::for_each_nzblock_if(), and bm::blocks_manager< Alloc >::get_rootblock().

template<class Alloc>

bm::bvector<Alloc>& bm::bvector< Alloc >::bit_and

(

const bm::bvector< Alloc > &

vect

)

[inline]

Logical AND operation.

Parameters:

vect	- Argument vector.

Definition at line 1293 of file bm.h.

References bm::BM_AND, BMCOUNT_VALID, and bm::bvector< Alloc >::combine_operation().

Referenced by bm::operator&(), and bm::bvector< Alloc >::operator&=().

template<class Alloc>

bm::bvector<Alloc>& bm::bvector< Alloc >::bit_and

(

const bm::bvector< Alloc > &

vect

)

[inline]

Logical AND operation.

Parameters:

vect	- Argument vector.

Definition at line 1293 of file bm.h.

References bm::BM_AND, BMCOUNT_VALID, and bm::bvector< Alloc >::combine_operation().

template<class Alloc>

bm::bvector<Alloc>& bm::bvector< Alloc >::bit_or

(

const bm::bvector< Alloc > &

vect

)

[inline]

Logical OR operation.

Parameters:

vect	- Argument vector.

Definition at line 1282 of file bm.h.

References bm::BM_OR, BMCOUNT_VALID, and bm::bvector< Alloc >::combine_operation().

Referenced by bm::bvector< Alloc >::operator=(), bm::operator|(), and bm::bvector< Alloc >::operator|=().

template<class Alloc>

bm::bvector<Alloc>& bm::bvector< Alloc >::bit_or

(

const bm::bvector< Alloc > &

vect

)

[inline]

Logical OR operation.

Parameters:

vect	- Argument vector.

Definition at line 1282 of file bm.h.

References bm::BM_OR, BMCOUNT_VALID, and bm::bvector< Alloc >::combine_operation().

template<class Alloc>

bm::bvector<Alloc>& bm::bvector< Alloc >::bit_sub

(

const bm::bvector< Alloc > &

vect

)

[inline]

Logical SUB operation.

Parameters:

vect	- Argument vector.

Definition at line 1315 of file bm.h.

References bm::BM_SUB, BMCOUNT_VALID, and bm::bvector< Alloc >::combine_operation().

Referenced by bm::operator-(), and bm::bvector< Alloc >::operator-=().

template<class Alloc>

bm::bvector<Alloc>& bm::bvector< Alloc >::bit_sub

(

const bm::bvector< Alloc > &

vect

)

[inline]

Logical SUB operation.

Parameters:

vect	- Argument vector.

Definition at line 1315 of file bm.h.

References bm::BM_SUB, BMCOUNT_VALID, and bm::bvector< Alloc >::combine_operation().

template<class Alloc>

bm::bvector<Alloc>& bm::bvector< Alloc >::bit_xor

(

const bm::bvector< Alloc > &

vect

)

[inline]

Logical XOR operation.

Parameters:

vect	- Argument vector.

Definition at line 1304 of file bm.h.

References bm::BM_XOR, BMCOUNT_VALID, and bm::bvector< Alloc >::combine_operation().

Referenced by bm::operator^(), and bm::bvector< Alloc >::operator^=().

template<class Alloc>

bm::bvector<Alloc>& bm::bvector< Alloc >::bit_xor

(

const bm::bvector< Alloc > &

vect

)

[inline]

Logical XOR operation.

Parameters:

vect	- Argument vector.

Definition at line 1304 of file bm.h.

References bm::BM_XOR, BMCOUNT_VALID, and bm::bvector< Alloc >::combine_operation().

template<typename Alloc >

void bm::bvector< Alloc >::calc_stat

(

struct bm::bvector< Alloc >::statistics *

st

)

const

Calculates bitvector 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 2044 of file bm.h.

References bm::bv_statistics::bit_blocks, BM_IS_GAP, BMGAP_PTR, bm::bv_statistics::gap_blocks, bm::gap_capacity(), bm::bv_statistics::gap_length, bm::gap_length(), bm::bv_statistics::gap_levels, bm::gap_levels, IS_VALID_ADDR, bm::bv_statistics::max_serialize_mem, bm::bv_statistics::memory_used, bm::set_array_size, and bm::set_block_size.

template<class Alloc>

void bm::bvector< Alloc >::calc_stat

(

struct bm::bvector< Alloc >::statistics *

st

)

const

Calculates bitvector 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

template<class Alloc>

size_type bm::bvector< Alloc >::capacity

(

)

const [inline]

Returns bvector's capacity (number of bits it can store)

Definition at line 1081 of file bm.h.

References bm::bvector< Alloc >::blockman_, and bm::blocks_manager< Alloc >::capacity().

template<class Alloc>

size_type bm::bvector< Alloc >::capacity

(

)

const [inline]

Returns bvector's capacity (number of bits it can store)

Definition at line 1081 of file bm.h.

References bm::bvector< Alloc >::blockman_, and bm::blocks_manager< Alloc >::capacity().

template<class Alloc>

bm::id_t bm::bvector< Alloc >::check_or_next

(

bm::id_t

prev

)

const [private]

template<class Alloc >

bm::id_t bm::bvector< Alloc >::check_or_next

(

bm::id_t

prev

)

const [private]

Definition at line 2355 of file bm.h.

References bm::bit_find_in_block(), BM_IS_GAP, BMGAP_PTR, bm::gap_find_in_block(), IS_FULL_BLOCK, bm::set_array_shift, bm::set_blkblk_mask, bm::set_block_mask, bm::set_block_shift, and bm::set_total_blocks.

Referenced by bm::bvector< Alloc >::get_first(), and bm::bvector< Alloc >::get_next().

template<class Alloc>

bm::id_t bm::bvector< Alloc >::check_or_next_extract

(

bm::id_t

prev

)

[private]

check if specified bit is 1, and set it to 0 if specified bit is 0, scan for the next 1 and returns it if no 1 found returns 0

template<class Alloc >

bm::id_t bm::bvector< Alloc >::check_or_next_extract

(

bm::id_t

prev

)

[private]

check if specified bit is 1, and set it to 0 if specified bit is 0, scan for the next 1 and returns it if no 1 found returns 0

Definition at line 2418 of file bm.h.

References bm::bit_find_in_block(), BM_IS_GAP, BMCOUNT_DEC, BMGAP_PTR, bm::gap_find_in_block(), bm::gap_limit(), bm::gap_set_value(), IS_FULL_BLOCK, bm::set_array_shift, bm::set_blkblk_mask, bm::set_block_mask, bm::set_block_shift, bm::set_total_blocks, bm::set_word_mask, and bm::set_word_shift.

Referenced by bm::bvector< Alloc >::extract_next().

template<class Alloc>

void bm::bvector< Alloc >::clear

(

bool

free_mem = false

)

[inline]

Clears every bit in the bitvector.

Parameters:

free_mem

if "true" (default) bvector frees the memory, otherwise sets blocks to 0.

Definition at line 1055 of file bm.h.

References bm::bvector< Alloc >::blockman_, BMCOUNT_SET, and bm::blocks_manager< Alloc >::set_all_zero().

template<class Alloc>

void bm::bvector< Alloc >::clear

(

bool

free_mem = false

)

[inline]

Clears every bit in the bitvector.

Parameters:

free_mem

if "true" (default) bvector frees the memory, otherwise sets blocks to 0.

Definition at line 1055 of file bm.h.

References bm::bvector< Alloc >::blockman_, BMCOUNT_SET, and bm::blocks_manager< Alloc >::set_all_zero().

Referenced by bm::bvector< Alloc >::operator=(), and bm::bvector< Alloc >::reset().

template<class Alloc>

void bm::bvector< Alloc >::clear_bit

(

bm::id_t

n

)

[inline]

Clears bit n.

Parameters:

n	- bit's index to be cleaned.

Definition at line 1043 of file bm.h.

Referenced by DynamicVector< T, long >::erase().

template<class Alloc>

void bm::bvector< Alloc >::clear_bit

(

bm::id_t

n

)

[inline]

Clears bit n.

Parameters:

n	- bit's index to be cleaned.

Definition at line 1043 of file bm.h.

template<class Alloc>

void bm::bvector< Alloc >::combine_count_operation_with_block	(	unsigned	nb,
		const bm::word_t *	arg_blk,
		int	arg_gap,
		bm::operation	opcode
	)		[inline, private]

Definition at line 1500 of file bm.h.

References BM_IS_GAP, and bm::bvector< Alloc >::get_block().

Referenced by bm::bvector< Alloc >::combine_count_operation_with_block().

template<class Alloc>

void bm::bvector< Alloc >::combine_count_operation_with_block	(	unsigned	nb,
		const bm::word_t *	arg_blk,
		int	arg_gap,
		bm::operation	opcode
	)		[inline, private]

Definition at line 1500 of file bm.h.

References BM_IS_GAP, bm::bvector< Alloc >::combine_count_operation_with_block(), and bm::bvector< Alloc >::get_block().

template<class Alloc>

void bm::bvector< Alloc >::combine_operation	(	const bm::bvector< Alloc > &	bvect,
		bm::operation	opcode
	)

template<class Alloc >

void bm::bvector< Alloc >::combine_operation	(	const bm::bvector< Alloc > &	bvect,
		bm::operation	opcode
	)

Definition at line 2511 of file bm.h.

References bm::bvector< Alloc >::blockman_, bm::BM_AND, BM_IS_GAP, bm::set_array_size, and bm::bvector< Alloc >::size_.

Referenced by bm::bvector< Alloc >::bit_and(), bm::bvector< Alloc >::bit_or(), bm::bvector< Alloc >::bit_sub(), and bm::bvector< Alloc >::bit_xor().

template<class Alloc >

void bm::bvector< Alloc >::combine_operation_with_block	(	unsigned	nb,
		unsigned	gap,
		bm::word_t *	blk,
		const bm::word_t *	arg_blk,
		int	arg_gap,
		bm::operation	opcode
	)		[private]

Definition at line 2639 of file bm.h.

References bm::all_bits_mask, bm::bit_block_copy(), bm::bit_operation_and(), bm::bit_operation_or(), bm::bit_operation_sub(), bm::bit_operation_xor(), bm::BM_AND, bm::BM_GAP, bm::BM_OR, bm::BM_SUB, bm::BM_XOR, BMGAP_PTR, BMSET_PTRGAP, bm::gap_bit_count(), bm::gap_calc_level(), bm::gap_convert_to_arr(), bm::gap_convert_to_bitset_smart(), bm::gap_equiv_len, bm::gap_is_all_zero(), bm::gap_length(), bm::gap_level(), bm::gap_limit(), bm::gap_max_bits, bm::operation_functions< T >::gap_op_to_bit(), bm::operation_functions< T >::gap_operation(), bm::gap_set_value(), IS_FULL_BLOCK, IS_VALID_ADDR, bm::or_bit_block(), bm::set_block_size, bm::set_gap_level(), bm::test_bit(), VECT_ANDNOT_ARR_2_MASK, and VECT_XOR_ARR_2_MASK.

Referenced by bm::bvector< Alloc >::combine_operation_with_block().

template<class Alloc>

void bm::bvector< Alloc >::combine_operation_with_block	(	unsigned	nb,
		unsigned	gap,
		bm::word_t *	blk,
		const bm::word_t *	arg_blk,
		int	arg_gap,
		bm::operation	opcode
	)		[private]

template<class Alloc>

void bm::bvector< Alloc >::combine_operation_with_block	(	unsigned	nb,
		const bm::word_t *	arg_blk,
		int	arg_gap,
		bm::operation	opcode
	)		[inline]

Definition at line 1490 of file bm.h.

References BM_IS_GAP, bm::bvector< Alloc >::combine_operation_with_block(), and bm::bvector< Alloc >::get_block().

template<class Alloc>

void bm::bvector< Alloc >::combine_operation_with_block	(	unsigned	nb,
		const bm::word_t *	arg_blk,
		int	arg_gap,
		bm::operation	opcode
	)		[inline]

Definition at line 1490 of file bm.h.

References BM_IS_GAP, bm::bvector< Alloc >::combine_operation_with_block(), and bm::bvector< Alloc >::get_block().

template<class Alloc>

int bm::bvector< Alloc >::compare

(

const bvector< Alloc > &

bvect

)

const

Lexicographical comparison with a bitvector.

Function compares current bitvector with the provided argument bit by bit and returns -1 if our bitvector less than the argument, 1 - greater, 0 - equal.

template<typename Alloc >

int bm::bvector< Alloc >::compare

(

const bvector< Alloc > &

bvect

)

const

Lexicographical comparison with a bitvector.

Function compares current bitvector with the provided argument bit by bit and returns -1 if our bitvector less than the argument, 1 - greater, 0 - equal.

Definition at line 1914 of file bm.h.

References bm::bit_is_all_zero(), bm::bitcmp(), bm::bvector< Alloc >::blockman_, BM_IS_GAP, BMGAP_PTR, bm::gap_convert_to_bitset(), bm::gap_is_all_zero(), bm::gap_max_bits, bm::gapcmp(), bm::set_array_size, bm::set_block_size, and bm::set_block_size_op.

Referenced by bm::bvector< Alloc >::operator!=(), bm::bvector< Alloc >::operator<(), bm::bvector< Alloc >::operator<=(), bm::bvector< Alloc >::operator==(), bm::bvector< Alloc >::operator>(), and bm::bvector< Alloc >::operator>=().

template<class Alloc>

bm::id_t bm::bvector< Alloc >::count

(

)

const

Returns count of bits which are 1.

Returns:

Total number of bits ON.

template<typename Alloc >

bm::id_t bm::bvector< Alloc >::count

(

)

const

Returns count of bits which are 1.

Returns:

Total number of bits ON.

Definition at line 1647 of file bm.h.

References BMCOUNT_SET, bm::blocks_manager< Alloc >::block_count_func::count(), and bm::for_each_nzblock2().

Referenced by Interpretation::filter(), and bm::bvector< Alloc >::recalc_count().

template<class Alloc>

unsigned bm::bvector< Alloc >::count_blocks

(

unsigned *

arr

)

const [inline]

Computes bitcount values for all bvector blocks.

Parameters:

arr	- pointer on array of block bit counts

Returns:

Index of the last block counted. This number +1 gives you number of arr elements initialized during the function call.

Definition at line 1106 of file bm.h.

References bm::bvector< Alloc >::blockman_, bm::blocks_manager< Alloc >::effective_top_block_size(), bm::for_each_nzblock(), bm::blocks_manager< Alloc >::get_rootblock(), and bm::blocks_manager< Alloc >::block_count_arr_func::last_block().

template<class Alloc>

unsigned bm::bvector< Alloc >::count_blocks

(

unsigned *

arr

)

const [inline]

Computes bitcount values for all bvector blocks.

Parameters:

arr	- pointer on array of block bit counts

Returns:

Index of the last block counted. This number +1 gives you number of arr elements initialized during the function call.

Definition at line 1106 of file bm.h.

References bm::bvector< Alloc >::blockman_, bm::blocks_manager< Alloc >::effective_top_block_size(), bm::for_each_nzblock(), bm::blocks_manager< Alloc >::get_rootblock(), and bm::blocks_manager< Alloc >::block_count_arr_func::last_block().

template<class Alloc>

bm::id_t bm::bvector< Alloc >::count_range	(	bm::id_t	left,
		bm::id_t	right,
		unsigned *	block_count_arr = 0
	)		const

Returns count of 1 bits in the given diapason.

Parameters:

left	- index of first bit start counting from
right	- index of last bit
block_count_arr	- optional parameter (bitcount by bvector blocks) calculated by count_blocks method. Used to improve performance of wide range searches

Returns:

Total number of bits ON.

template<typename Alloc >

bm::id_t bm::bvector< Alloc >::count_range	(	bm::id_t	left,
		bm::id_t	right,
		unsigned *	block_count_arr = 0
	)		const

Returns count of 1 bits in the given diapason.

Parameters:

left	- index of first bit start counting from
right	- index of last bit
block_count_arr	- optional parameter (bitcount by bvector blocks) calculated by count_blocks method. Used to improve performance of wide range searches

Returns:

Total number of bits ON.

Definition at line 1687 of file bm.h.

References bm::bit_block_calc_count_range(), bm::bits_in_block, BM_IS_GAP, BMGAP_PTR, bm::blocks_manager< Alloc >::block_count_func::count(), bm::gap_bit_count_range(), bm::set_block_mask, and bm::set_block_shift.

template<class Alloc>

enumerator bm::bvector< Alloc >::end

(

)

const [inline]

Definition at line 1446 of file bm.h.

template<class Alloc>

bvector::enumerator bm::bvector< Alloc >::end

(

)

const [inline]

Returns enumerator pointing on the next bit after the last.

Definition at line 1446 of file bm.h.

Referenced by AnnotatedGroundProgram::computeAdditionalDependencies(), Interpretation::filter(), Interpretation::getInterpretationWithoutExternalAtomAuxiliaries(), hash_value(), AnswerSetPrinterCallback::operator()(), CSVAnswerSetPrinterCallback::operator()(), Interpretation::print(), Interpretation::printAsFacts(), Interpretation::printAsNumber(), Interpretation::printWithoutPrefix(), and GenPluginAtom1::retrieve().

template<class Alloc>

void bm::bvector< Alloc >::extend_gap_block	(	unsigned	nb,
		gap_word_t *	blk
	)		[inline, private]

Extends GAP block to the next level or converts it to bit block.

Parameters:

nb	- Block's linear index.
blk	- Blocks's pointer

Definition at line 1516 of file bm.h.

References bm::bvector< Alloc >::blockman_, and bm::blocks_manager< Alloc >::extend_gap_block().

template<class Alloc>

void bm::bvector< Alloc >::extend_gap_block	(	unsigned	nb,
		gap_word_t *	blk
	)		[inline, private]

Extends GAP block to the next level or converts it to bit block.

Parameters:

nb	- Block's linear index.
blk	- Blocks's pointer

Definition at line 1516 of file bm.h.

References bm::bvector< Alloc >::blockman_, and bm::blocks_manager< Alloc >::extend_gap_block().

template<class Alloc>

bm::id_t bm::bvector< Alloc >::extract_next

(

bm::id_t

prev

)

[inline]

Finds the number of the next bit ON and sets it to 0.

Parameters:

prev	- Index of the previously found bit.

Returns:

Index of the next bit which is ON or 0 if not found.

See also:

get_first, get_next,

Definition at line 1259 of file bm.h.

References bm::bvector< Alloc >::check_or_next_extract(), and bm::id_max.

template<class Alloc>

bm::id_t bm::bvector< Alloc >::extract_next

(

bm::id_t

prev

)

[inline]

Definition at line 1259 of file bm.h.

References bm::bvector< Alloc >::check_or_next_extract(), and bm::id_max.

template<class Alloc>

enumerator bm::bvector< Alloc >::first

(

)

const [inline]

Returns enumerator pointing on the first non-zero bit.

Definition at line 1436 of file bm.h.

template<class Alloc>

enumerator bm::bvector< Alloc >::first

(

)

const [inline]

Returns enumerator pointing on the first non-zero bit.

Definition at line 1436 of file bm.h.

Referenced by AnnotatedGroundProgram::computeAdditionalDependencies(), Interpretation::filter(), Interpretation::getInterpretationWithoutExternalAtomAuxiliaries(), hash_value(), AnswerSetPrinterCallback::operator()(), CSVAnswerSetPrinterCallback::operator()(), Interpretation::print(), Interpretation::printAsFacts(), Interpretation::printAsNumber(), Interpretation::printWithoutPrefix(), GenPluginAtom1::retrieve(), and bm::bvector< Alloc >::enumerator::search_in_gapblock().

template<class Alloc>

bvector<Alloc>& bm::bvector< Alloc >::flip

(

bm::id_t

n

)

[inline]

Flips bit n.

Returns:

*this

Definition at line 1201 of file bm.h.

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

template<class Alloc>

bvector<Alloc>& bm::bvector< Alloc >::flip

(

bm::id_t

n

)

[inline]

Flips bit n.

Returns:

*this

Definition at line 1201 of file bm.h.

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

template<class Alloc>

bvector<Alloc>& bm::bvector< Alloc >::flip

(

)

[inline]

Flips all bits.

Returns:

*this

Definition at line 1211 of file bm.h.

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

template<class Alloc>

bvector<Alloc>& bm::bvector< Alloc >::flip

(

)

[inline]

Flips all bits.

Returns:

*this

Definition at line 1211 of file bm.h.

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

template<class Alloc>

void bm::bvector< Alloc >::forget_count

(

)

[inline]

Disables count cache. Next call to count() or recalc_count() restores count caching.

Note:

Works only if BMCOUNTOPT enabled(defined). Othewise does nothing.

Definition at line 1142 of file bm.h.

References BMCOUNT_VALID.

template<class Alloc>

void bm::bvector< Alloc >::forget_count

(

)

[inline]

Disables count cache. Next call to count() or recalc_count() restores count caching.

Note:

Works only if BMCOUNTOPT enabled(defined). Othewise does nothing.

Definition at line 1142 of file bm.h.

References BMCOUNT_VALID.

template<class Alloc>

void bm::bvector< Alloc >::free_tempblock

(

bm::word_t *

block

)

const [inline]

Frees temporary block of memory.

Note:

method is marked const, but it's not quite true, since it can in some cases modify the state of the block allocator (if it has a state). (Can be important in MT programs).

See also:

allocate_tempblock

Definition at line 1426 of file bm.h.

References bm::bvector< Alloc >::blockman_, and bm::blocks_manager< Alloc >::get_allocator().

template<class Alloc>

void bm::bvector< Alloc >::free_tempblock

(

bm::word_t *

block

)

const [inline]

Frees temporary block of memory.

Note:

method is marked const, but it's not quite true, since it can in some cases modify the state of the block allocator (if it has a state). (Can be important in MT programs).

See also:

allocate_tempblock

Definition at line 1426 of file bm.h.

References bm::bvector< Alloc >::blockman_, and bm::blocks_manager< Alloc >::get_allocator().

template<class Alloc>

Alloc bm::bvector< Alloc >::get_allocator

(

)

const [inline]

Definition at line 945 of file bm.h.

References bm::bvector< Alloc >::blockman_, and bm::blocks_manager< Alloc >::get_allocator().

template<class Alloc>

Alloc bm::bvector< Alloc >::get_allocator

(

)

const [inline]

Definition at line 945 of file bm.h.

References bm::bvector< Alloc >::blockman_, and bm::blocks_manager< Alloc >::get_allocator().

template<typename Alloc >

bool bm::bvector< Alloc >::get_bit

(

bm::id_t

n

)

const

returns true if bit n is set and false is bit n is 0.

Parameters:

n	- Index of the bit to check.

Returns:

Bit value (1 or 0)

Definition at line 1804 of file bm.h.

References BM_IS_GAP, BMGAP_PTR, bm::gap_test(), bm::set_block_mask, bm::set_block_shift, bm::set_word_mask, and bm::set_word_shift.

Referenced by DynamicVector< T, long >::find(), bm::bvector< Alloc >::flip(), bm::bvector< Alloc >::operator[](), and bm::bvector< Alloc >::test().

template<class Alloc>

bool bm::bvector< Alloc >::get_bit

(

bm::id_t

n

)

const

returns true if bit n is set and false is bit n is 0.

Parameters:

n	- Index of the bit to check.

Returns:

Bit value (1 or 0)

template<class Alloc>

const bm::word_t* bm::bvector< Alloc >::get_block

(

unsigned

nb

)

const [inline]

Definition at line 1453 of file bm.h.

References bm::bvector< Alloc >::blockman_, and bm::blocks_manager< Alloc >::get_block().

template<class Alloc>

const bm::word_t* bm::bvector< Alloc >::get_block

(

unsigned

nb

)

const [inline]

Definition at line 1453 of file bm.h.

References bm::bvector< Alloc >::blockman_, and bm::blocks_manager< Alloc >::get_block().

Referenced by bm::bvector< Alloc >::combine_count_operation_with_block(), and bm::bvector< Alloc >::combine_operation_with_block().

template<class Alloc>

const blocks_manager_type& bm::bvector< Alloc >::get_blocks_manager

(

)

const [inline]

Definition at line 1529 of file bm.h.

References bm::bvector< Alloc >::blockman_.

template<class Alloc>

const blocks_manager_type& bm::bvector< Alloc >::get_blocks_manager

(

)

const [inline]

Definition at line 1529 of file bm.h.

References bm::bvector< Alloc >::blockman_.

template<class Alloc>

blocks_manager_type& bm::bvector< Alloc >::get_blocks_manager

(

)

[inline]

Definition at line 1534 of file bm.h.

References bm::bvector< Alloc >::blockman_.

template<class Alloc>

blocks_manager_type& bm::bvector< Alloc >::get_blocks_manager

(

)

[inline]

Definition at line 1534 of file bm.h.

References bm::bvector< Alloc >::blockman_.

template<class Alloc>

bm::id_t bm::bvector< Alloc >::get_first

(

)

const [inline]

Gets number of first bit which is ON.

Returns:

Index of the first 1 bit.

See also:

get_next, extract_next

Definition at line 1238 of file bm.h.

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

template<class Alloc>

bm::id_t bm::bvector< Alloc >::get_first

(

)

const [inline]

Definition at line 1238 of file bm.h.

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

template<class Alloc>

strategy bm::bvector< Alloc >::get_new_blocks_strat

(

)

const [inline]

Returns blocks allocation strategy.

Returns:

- Strategy code 0 - bitblocks allocation only. 1 - Blocks mutation mode (adaptive algorithm)

See also:

set_new_blocks_strat

Definition at line 1339 of file bm.h.

References bm::bvector< Alloc >::new_blocks_strat_.

template<class Alloc>

strategy bm::bvector< Alloc >::get_new_blocks_strat

(

)

const [inline]

Returns blocks allocation strategy.

Returns:

- Strategy code 0 - bitblocks allocation only. 1 - Blocks mutation mode (adaptive algorithm)

See also:

set_new_blocks_strat

Definition at line 1339 of file bm.h.

References bm::bvector< Alloc >::new_blocks_strat_.

template<class Alloc>

bm::id_t bm::bvector< Alloc >::get_next

(

bm::id_t

prev

)

const [inline]

Finds the number of the next bit ON.

Parameters:

prev	- Index of the previously found bit.

Returns:

Index of the next bit which is ON or 0 if not found.

See also:

get_first, extract_next

Definition at line 1247 of file bm.h.

References bm::bvector< Alloc >::check_or_next(), and bm::id_max.

template<class Alloc>

bm::id_t bm::bvector< Alloc >::get_next

(

bm::id_t

prev

)

const [inline]

Definition at line 1247 of file bm.h.

References bm::bvector< Alloc >::check_or_next(), and bm::id_max.

template<class Alloc>

insert_iterator bm::bvector< Alloc >::inserter

(

)

[inline]

Function erturns insert iterator for this bitvector

Definition at line 1033 of file bm.h.

template<class Alloc>

insert_iterator bm::bvector< Alloc >::inserter

(

)

[inline]

Function erturns insert iterator for this bitvector

Definition at line 1033 of file bm.h.

template<typename Alloc >

bvector< Alloc > & bm::bvector< Alloc >::invert

(

)

Inverts all bits.

Definition at line 1781 of file bm.h.

References BMCOUNT_VALID, bm::for_each_block(), and bm::id_max.

Referenced by bm::bvector< Alloc >::flip(), and bm::bvector< Alloc >::operator~().

template<class Alloc>

bvector<Alloc>& bm::bvector< Alloc >::invert

(

)

Inverts all bits.

template<class Alloc>

bool bm::bvector< Alloc >::none

(

)

const [inline]

Returns true if no bits are set, otherwise returns false.

Definition at line 1192 of file bm.h.

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

template<class Alloc>

bool bm::bvector< Alloc >::none

(

)

const [inline]

Returns true if no bits are set, otherwise returns false.

Definition at line 1192 of file bm.h.

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

template<class Alloc>

bool bm::bvector< Alloc >::operator!=

(

const bvector< Alloc > &

bvect

)

const [inline]

Definition at line 935 of file bm.h.

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

template<class Alloc>

bool bm::bvector< Alloc >::operator!=

(

const bvector< Alloc > &

bvect

)

const [inline]

Definition at line 935 of file bm.h.

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

template<class Alloc>

void bm::bvector< Alloc >::operator&=

(

const bvector< Alloc > &

bvect

)

[inline]

Definition at line 890 of file bm.h.

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

template<class Alloc>

void bm::bvector< Alloc >::operator&=

(

const bvector< Alloc > &

bvect

)

[inline]

Definition at line 890 of file bm.h.

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

template<class Alloc>

void bm::bvector< Alloc >::operator-=

(

const bvector< Alloc > &

bvect

)

[inline]

Definition at line 905 of file bm.h.

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

template<class Alloc>

void bm::bvector< Alloc >::operator-=

(

const bvector< Alloc > &

bvect

)

[inline]

Definition at line 905 of file bm.h.

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

template<class Alloc>

bool bm::bvector< Alloc >::operator<

(

const bvector< Alloc > &

bvect

)

const [inline]

Definition at line 910 of file bm.h.

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

template<class Alloc>

bool bm::bvector< Alloc >::operator<

(

const bvector< Alloc > &

bvect

)

const [inline]

Definition at line 910 of file bm.h.

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

template<class Alloc>

bool bm::bvector< Alloc >::operator<=

(

const bvector< Alloc > &

bvect

)

const [inline]

Definition at line 915 of file bm.h.

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

template<class Alloc>

bool bm::bvector< Alloc >::operator<=

(

const bvector< Alloc > &

bvect

)

const [inline]

Definition at line 915 of file bm.h.

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

template<class Alloc>

bvector& bm::bvector< Alloc >::operator=

(

const bvector< Alloc > &

bvect

)

[inline]

Definition at line 869 of file bm.h.

References bm::bvector< Alloc >::bit_or(), bm::bvector< Alloc >::clear(), and bm::bvector< Alloc >::resize().

template<class Alloc>

bvector& bm::bvector< Alloc >::operator=

(

const bvector< Alloc > &

bvect

)

[inline]

Definition at line 869 of file bm.h.

References bm::bvector< Alloc >::bit_or(), bm::bvector< Alloc >::clear(), bm::bvector< Alloc >::resize(), and bm::bvector< Alloc >::size().

template<class Alloc>

bool bm::bvector< Alloc >::operator==

(

const bvector< Alloc > &

bvect

)

const [inline]

Definition at line 930 of file bm.h.

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

template<class Alloc>

bool bm::bvector< Alloc >::operator==

(

const bvector< Alloc > &

bvect

)

const [inline]

Definition at line 930 of file bm.h.

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

template<class Alloc>

bool bm::bvector< Alloc >::operator>

(

const bvector< Alloc > &

bvect

)

const [inline]

Definition at line 920 of file bm.h.

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

template<class Alloc>

bool bm::bvector< Alloc >::operator>

(

const bvector< Alloc > &

bvect

)

const [inline]

Definition at line 920 of file bm.h.

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

template<class Alloc>

bool bm::bvector< Alloc >::operator>=

(

const bvector< Alloc > &

bvect

)

const [inline]

Definition at line 925 of file bm.h.

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

template<class Alloc>

bool bm::bvector< Alloc >::operator>=

(

const bvector< Alloc > &

bvect

)

const [inline]

Definition at line 925 of file bm.h.

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

template<class Alloc>

reference bm::bvector< Alloc >::operator[]

(

bm::id_t

n

)

[inline]

Definition at line 877 of file bm.h.

References bm::bvector< Alloc >::size_.

template<class Alloc>

reference bm::bvector< Alloc >::operator[]

(

bm::id_t

n

)

[inline]

Definition at line 877 of file bm.h.

References bm::bvector< Alloc >::size_.

template<class Alloc>

bool bm::bvector< Alloc >::operator[]

(

bm::id_t

n

)

const [inline]

Definition at line 884 of file bm.h.

References bm::bvector< Alloc >::get_bit(), and bm::bvector< Alloc >::size_.

template<class Alloc>

bool bm::bvector< Alloc >::operator[]

(

bm::id_t

n

)

const [inline]

Definition at line 884 of file bm.h.

References bm::bvector< Alloc >::get_bit(), and bm::bvector< Alloc >::size_.

template<class Alloc>

void bm::bvector< Alloc >::operator^=

(

const bvector< Alloc > &

bvect

)

[inline]

Definition at line 895 of file bm.h.

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

template<class Alloc>

void bm::bvector< Alloc >::operator^=

(

const bvector< Alloc > &

bvect

)

[inline]

Definition at line 895 of file bm.h.

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

template<class Alloc>

void bm::bvector< Alloc >::operator|=

(

const bvector< Alloc > &

bvect

)

[inline]

Definition at line 900 of file bm.h.

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

template<class Alloc>

void bm::bvector< Alloc >::operator|=

(

const bvector< Alloc > &

bvect

)

[inline]

Definition at line 900 of file bm.h.

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

template<class Alloc>

bvector<Alloc> bm::bvector< Alloc >::operator~

(

)

const [inline]

Definition at line 940 of file bm.h.

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

template<class Alloc>

bvector<Alloc> bm::bvector< Alloc >::operator~

(

)

const [inline]

Definition at line 940 of file bm.h.

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

template<class Alloc>

void bm::bvector< Alloc >::optimize	(	bm::word_t *	temp_block = 0,
		optmode	opt_mode = opt_compress,
		statistics *	stat = 0
	)

Optimize memory bitvector's memory allocation.

Function analyze all blocks in the bitvector, compresses blocks with a regular structure, frees some memory. This function is recommended after a bulk modification of the bitvector using set_bit, clear_bit or logical operations.

Optionally function can calculate vector post optimization statistics

See also:

optmode, optimize_gap_size

template<typename Alloc >

void bm::bvector< Alloc >::optimize	(	bm::word_t *	temp_block = 0,
		optmode	opt_mode = opt_compress,
		statistics *	stat = 0
	)

Optimize memory bitvector's memory allocation.

Function analyze all blocks in the bitvector, compresses blocks with a regular structure, frees some memory. This function is recommended after a bulk modification of the bitvector using set_bit, clear_bit or logical operations.

Optionally function can calculate vector post optimization statistics

See also:

optmode, optimize_gap_size

Definition at line 1838 of file bm.h.

References bm::bv_statistics::bit_blocks, bm::for_each_nzblock(), bm::bv_statistics::gap_blocks, bm::bv_statistics::gap_levels, bm::gap_levels, bm::bv_statistics::max_serialize_mem, and bm::bv_statistics::memory_used.

template<typename Alloc >

void bm::bvector< Alloc >::optimize_gap_size

(

)

Optimize sizes of GAP blocks.

This method runs an analysis to find optimal GAP levels for the specific vector. Current GAP compression algorithm uses several fixed GAP sizes. By default bvector uses some reasonable preset.

Definition at line 1880 of file bm.h.

References bm::gap_levels, and bm::improve_gap_levels().

template<class Alloc>

void bm::bvector< Alloc >::optimize_gap_size

(

)

Optimize sizes of GAP blocks.

This method runs an analysis to find optimal GAP levels for the specific vector. Current GAP compression algorithm uses several fixed GAP sizes. By default bvector uses some reasonable preset.

template<class Alloc>

bm::id_t bm::bvector< Alloc >::recalc_count

(

)

[inline]

Definition at line 1129 of file bm.h.

References BMCOUNT_VALID, and bm::bvector< Alloc >::count().

template<class Alloc>

bm::id_t bm::bvector< Alloc >::recalc_count

(

)

[inline]

Definition at line 1129 of file bm.h.

References BMCOUNT_VALID, and bm::bvector< Alloc >::count().

Referenced by bm::bvector< Alloc >::swap().

template<class Alloc>

bvector<Alloc>& bm::bvector< Alloc >::reset

(

)

[inline]

Clears every bit in the bitvector.

Returns:

*this;

Definition at line 1065 of file bm.h.

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

template<class Alloc>

bvector<Alloc>& bm::bvector< Alloc >::reset

(

)

[inline]

Clears every bit in the bitvector.

Returns:

*this;

Definition at line 1065 of file bm.h.

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

template<typename Alloc >

void bm::bvector< Alloc >::resize

(

size_type

new_size

)

Change size of the bvector.

Parameters:

new_size

- new size in bits

Definition at line 1669 of file bm.h.

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

template<class Alloc>

void bm::bvector< Alloc >::resize

(

size_type

new_size

)

Change size of the bvector.

Parameters:

new_size

- new size in bits

template<class Alloc>

bvector<Alloc>& bm::bvector< Alloc >::set	(	bm::id_t	n,
		bool	val = true
	)		[inline]

Sets bit n if val is true, clears bit n if val is false.

Parameters:

n	- index of the bit to be set
val	- new bit value

Returns:

*this

Definition at line 996 of file bm.h.

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

template<class Alloc>

bvector<Alloc>& bm::bvector< Alloc >::set	(	bm::id_t	n,
		bool	val = true
	)		[inline]

Sets bit n if val is true, clears bit n if val is false.

Parameters:

n	- index of the bit to be set
val	- new bit value

Returns:

*this

Definition at line 996 of file bm.h.

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

Referenced by Interpretation::filter(), and PredicateMask::updateMask().

template<class Alloc>

bvector<Alloc>& bm::bvector< Alloc >::set

(

)

[inline]

Sets every bit in this bitset to 1.

Returns:

*this

Definition at line 1008 of file bm.h.

References BMCOUNT_VALID, bm::bvector< Alloc >::set_range(), and bm::bvector< Alloc >::size_.

template<class Alloc>

bvector<Alloc>& bm::bvector< Alloc >::set

(

)

[inline]

Sets every bit in this bitset to 1.

Returns:

*this

Definition at line 1008 of file bm.h.

References BMCOUNT_VALID, bm::bvector< Alloc >::set_range(), and bm::bvector< Alloc >::size_.

template<class Alloc>

bool bm::bvector< Alloc >::set_bit	(	bm::id_t	n,
		bool	val = true
	)		[inline]

Sets bit n.

Parameters:

n	- index of the bit to be set.
val	- new bit value

Returns:

TRUE if bit was changed

Definition at line 957 of file bm.h.

References bm::bvector< Alloc >::set_bit_no_check(), and bm::bvector< Alloc >::size_.

template<class Alloc>

bool bm::bvector< Alloc >::set_bit	(	bm::id_t	n,
		bool	val = true
	)		[inline]

Sets bit n.

Parameters:

n	- index of the bit to be set.
val	- new bit value

Returns:

TRUE if bit was changed

Definition at line 957 of file bm.h.

References bm::bvector< Alloc >::set_bit_no_check(), and bm::bvector< Alloc >::size_.

Referenced by DynamicVector< T, long >::operator[](), and bm::bvector< Alloc >::set().

template<class Alloc>

bool bm::bvector< Alloc >::set_bit_and	(	bm::id_t	n,
		bool	val = true
	)		[inline]

Sets bit n using bit AND with the provided value.

Parameters:

n	- index of the bit to be set.
val	- new bit value

Returns:

TRUE if bit was changed

Definition at line 969 of file bm.h.

References bm::bvector< Alloc >::and_bit_no_check(), and bm::bvector< Alloc >::size_.

template<class Alloc>

bool bm::bvector< Alloc >::set_bit_and	(	bm::id_t	n,
		bool	val = true
	)		[inline]

Sets bit n using bit AND with the provided value.

Parameters:

n	- index of the bit to be set.
val	- new bit value

Returns:

TRUE if bit was changed

Definition at line 969 of file bm.h.

References bm::bvector< Alloc >::and_bit_no_check(), and bm::bvector< Alloc >::size_.

template<class Alloc>

bool bm::bvector< Alloc >::set_bit_conditional	(	bm::id_t	n,
		bool	val,
		bool	condition
	)		[inline]

Sets bit n only if current value is equal to the condition.

Parameters:

n	- index of the bit to be set.
val	- new bit value
condition	- expected current value

Returns:

TRUE if bit was changed

Definition at line 982 of file bm.h.

References bm::bvector< Alloc >::set_bit_conditional_impl(), and bm::bvector< Alloc >::size_.

template<class Alloc>

bool bm::bvector< Alloc >::set_bit_conditional	(	bm::id_t	n,
		bool	val,
		bool	condition
	)		[inline]

Sets bit n only if current value is equal to the condition.

Parameters:

n	- index of the bit to be set.
val	- new bit value
condition	- expected current value

Returns:

TRUE if bit was changed

Definition at line 982 of file bm.h.

References bm::bvector< Alloc >::set_bit_conditional_impl(), and bm::bvector< Alloc >::size_.

template<class Alloc>

bool bm::bvector< Alloc >::set_bit_conditional_impl	(	bm::id_t	n,
		bool	val,
		bool	condition
	)		[private]

template<class Alloc >

bool bm::bvector< Alloc >::set_bit_conditional_impl	(	bm::id_t	n,
		bool	val,
		bool	condition
	)		[private]

Definition at line 2202 of file bm.h.

References BMCOUNT_ADJ, BMCOUNT_DEC, BMCOUNT_INC, BMGAP_PTR, bm::gap_limit(), bm::gap_set_value(), bm::gap_test(), bm::set_block_mask, bm::set_block_shift, bm::set_word_mask, and bm::set_word_shift.

Referenced by bm::bvector< Alloc >::set_bit_conditional().

template<class Alloc>

bool bm::bvector< Alloc >::set_bit_no_check	(	bm::id_t	n,
		bool	val
	)		[private]

Set specified bit without checking preconditions (size, etc)

template<class Alloc >

bool bm::bvector< Alloc >::set_bit_no_check	(	bm::id_t	n,
		bool	val
	)		[private]

Set specified bit without checking preconditions (size, etc)

Definition at line 2130 of file bm.h.

References BMCOUNT_ADJ, BMCOUNT_DEC, BMCOUNT_INC, BMGAP_PTR, bm::gap_limit(), bm::gap_set_value(), bm::set_block_mask, bm::set_block_shift, bm::set_word_mask, and bm::set_word_shift.

Referenced by bm::bvector< Alloc >::set_bit().

template<typename Alloc >

void bm::bvector< Alloc >::set_gap_levels

(

const gap_word_t *

glevel_len

)

Sets new GAP lengths table. All GAP blocks will be reallocated to match the new scheme.

Parameters:

glevel_len

- pointer on C-style array keeping GAP block sizes.

Definition at line 1901 of file bm.h.

References bm::bvector< Alloc >::blockman_, bm::blocks_manager< Alloc >::blocks_root(), bm::for_each_nzblock(), bm::blocks_manager< Alloc >::set_glen(), and bm::blocks_manager< Alloc >::top_block_size().

template<class Alloc>

void bm::bvector< Alloc >::set_gap_levels

(

const gap_word_t *

glevel_len

)

Sets new GAP lengths table. All GAP blocks will be reallocated to match the new scheme.

Parameters:

glevel_len

- pointer on C-style array keeping GAP block sizes.

template<class Alloc>

void bm::bvector< Alloc >::set_new_blocks_strat

(

strategy

strat

)

[inline]

Sets new blocks allocation strategy.

Parameters:

strat

- Strategy code 0 - bitblocks allocation only. 1 - Blocks mutation mode (adaptive algorithm)

Definition at line 1328 of file bm.h.

References bm::bvector< Alloc >::new_blocks_strat_.

template<class Alloc>

void bm::bvector< Alloc >::set_new_blocks_strat

(

strategy

strat

)

[inline]

Sets new blocks allocation strategy.

Parameters:

strat

- Strategy code 0 - bitblocks allocation only. 1 - Blocks mutation mode (adaptive algorithm)

Definition at line 1328 of file bm.h.

References bm::bvector< Alloc >::new_blocks_strat_.

template<typename Alloc >

bvector< Alloc > & bm::bvector< Alloc >::set_range	(	bm::id_t	left,
		bm::id_t	right,
		bool	value = true
	)

Sets all bits in the specified closed interval [left,right] Interval must be inside the bvector's size. This method DOES NOT resize vector.

Parameters:

left	- interval start
right	- interval end (closed interval)
value	- value to set interval in

Returns:

*this

Definition at line 1624 of file bm.h.

References BMCOUNT_VALID.

Referenced by bm::bvector< Alloc >::set().

template<class Alloc>

bvector<Alloc>& bm::bvector< Alloc >::set_range	(	bm::id_t	left,
		bm::id_t	right,
		bool	value = true
	)

Sets all bits in the specified closed interval [left,right] Interval must be inside the bvector's size. This method DOES NOT resize vector.

Parameters:

left	- interval start
right	- interval end (closed interval)
value	- value to set interval in

Returns:

*this

template<class Alloc >

void bm::bvector< Alloc >::set_range_no_check	(	bm::id_t	left,
		bm::id_t	right,
		bool	value
	)		[private]

Set range without validity checking.

Definition at line 2947 of file bm.h.

References bm::bits_in_block, bm::BM_AND, BM_IS_GAP, bm::BM_OR, FULL_BLOCK_ADDR, IS_FULL_BLOCK, bm::set_block_mask, and bm::set_block_shift.

template<class Alloc>

void bm::bvector< Alloc >::set_range_no_check	(	bm::id_t	left,
		bm::id_t	right,
		bool	value
	)		[private]

Set range without validity checking.

template<class Alloc>

size_type bm::bvector< Alloc >::size

(

)

const [inline]

return current size of the vector (bits)

Definition at line 1089 of file bm.h.

References bm::bvector< Alloc >::size_.

template<class Alloc>

size_type bm::bvector< Alloc >::size

(

)

const [inline]

return current size of the vector (bits)

Definition at line 1089 of file bm.h.

References bm::bvector< Alloc >::size_.

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

template<class Alloc>

void bm::bvector< Alloc >::swap

(

bvector< Alloc > &

bv

)

[inline]

Exchanges content of bv and this bitvector.

Definition at line 1218 of file bm.h.

References bm::bvector< Alloc >::blockman_, BMCOUNT_VALID, bm::bvector< Alloc >::recalc_count(), bm::bvector< Alloc >::size_, bm::blocks_manager< Alloc >::swap(), and bm::xor_swap().

template<class Alloc>

void bm::bvector< Alloc >::swap

(

bvector< Alloc > &

bv

)

[inline]

Exchanges content of bv and this bitvector.

Definition at line 1218 of file bm.h.

References bm::bvector< Alloc >::blockman_, BMCOUNT_VALID, bm::bvector< Alloc >::size_, bm::blocks_manager< Alloc >::swap(), and bm::xor_swap().

template<class Alloc>

bool bm::bvector< Alloc >::test

(

bm::id_t

n

)

const [inline]

returns true if bit n is set and false is bit n is 0.

Parameters:

n	- Index of the bit to check.

Returns:

Bit value (1 or 0)

Definition at line 1165 of file bm.h.

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

template<class Alloc>

bool bm::bvector< Alloc >::test

(

bm::id_t

n

)

const [inline]

returns true if bit n is set and false is bit n is 0.

Parameters:

n	- Index of the bit to check.

Returns:

Bit value (1 or 0)

Definition at line 1165 of file bm.h.

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

---

Friends And Related Function Documentation

template<class Alloc>

enumerator [friend]

Definition at line 784 of file bm.h.

template<class Alloc>

iterator_base [friend]

Definition at line 783 of file bm.h.

---

Field Documentation

template<class Alloc>

blocks_manager_type bm::bvector< Alloc >::blockman_ [private]

bitblocks manager

Definition at line 1549 of file bm.h.

Referenced by bm::bvector< Alloc >::allocate_tempblock(), bm::bvector< Alloc >::any(), bm::bvector< Alloc >::capacity(), bm::bvector< Alloc >::clear(), bm::bvector< Alloc >::combine_operation(), bm::bvector< Alloc >::compare(), bm::bvector< Alloc >::count_blocks(), bm::bvector< Alloc >::extend_gap_block(), bm::bvector< Alloc >::free_tempblock(), bm::bvector< Alloc >::get_allocator(), bm::bvector< Alloc >::get_block(), bm::bvector< Alloc >::get_blocks_manager(), bm::bvector< Alloc >::set_gap_levels(), and bm::bvector< Alloc >::swap().

template<class Alloc>

strategy bm::bvector< Alloc >::new_blocks_strat_ [private]

block allocation strategy

Definition at line 1550 of file bm.h.

Referenced by bm::bvector< Alloc >::get_new_blocks_strat(), and bm::bvector< Alloc >::set_new_blocks_strat().

template<class Alloc>

size_type bm::bvector< Alloc >::size_ [private]

size in bits

Definition at line 1551 of file bm.h.

Referenced by bm::bvector< Alloc >::combine_operation(), bm::bvector< Alloc >::operator[](), bm::bvector< Alloc >::set(), bm::bvector< Alloc >::set_bit(), bm::bvector< Alloc >::set_bit_and(), bm::bvector< Alloc >::set_bit_conditional(), bm::bvector< Alloc >::size(), and bm::bvector< Alloc >::swap().

---

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

• vs10/bm/bm.h
• vs12/bm/bm.h