Class to represent a packed boolean array. More...

#include <bool_array.h>

Classes
class	_Element
	Class to represent a reference to an array element. More...

Public Types
typedef unsigned long	size_type
	Type of array indices. More...

typedef _Element< byte >	reference
	Type of reference.

typedef _Element< const byte >	const_reference
	Type of const reference.

Public Member Functions
	bool_array () noexcept
	Constructs an empty bool_array.

	bool_array (size_type size)
	Constructs a bool_array with a specific size. More...

	bool_array (const void *ptr, size_type size)
	Constructs a bool_array from a given bitmap. More...

	~bool_array ()
	Destroys the bool_array and releases memory.

	bool_array (const bool_array &rhs)
	Copy-constructor. More...

bool_array &	operator= (const bool_array &rhs)
	Assignment operator. More...

bool	create (size_type size) noexcept
	Creates the packed boolean array with a specific size. More...

void	initialize (bool value) noexcept
	Initializes all array elements to a specific value optimally. More...

reference	operator[] (size_type pos)
	Creates a reference to an array element. More...

const_reference	operator[] (size_type pos) const
	Creates a const reference to an array element. More...

bool	at (size_type pos) const
	Reads the boolean value of an array element at a specified position. More...

void	reset (size_type pos)
	Resets an array element to `false` at a specified position. More...

void	set (size_type pos)
	Sets an array element to `true` at a specified position. More...

size_type	size () const noexcept
	Gets the size of the bool_array. More...

size_type	count () const noexcept
	Counts elements with a `true` value. More...

size_type	count (size_type begin, size_type end=npos) const
	Counts elements with a `true` value in a specified range. More...

size_type	find (bool value, size_type offset=0) const
	Searches for the specified boolean value. More...

size_type	find (bool value, size_type offset, size_type count) const
	Searches for the specified boolean value. More...

size_type	find_until (bool value, size_type begin, size_type end) const
	Searches for the specified boolean value. More...

void	flip () noexcept
	Changes all `true` elements to `false`, and `false` ones to `true`.

void	swap (bool_array &rhs) noexcept
	Exchanges the content of this bool_array with another. More...

void	merge_and (const bool_array &rhs, size_type begin=0, size_type end=npos, size_type offset=0)
	Merges elements of another bool_array with a logical AND. More...

void	merge_or (const bool_array &rhs, size_type begin=0, size_type end=npos, size_type offset=0)
	Merges elements of another bool_array with a logical OR. More...

void	copy_to_bitmap (void *dest, size_type begin=0, size_type end=npos)
	Copies the bool_array content as bitmap to a specified buffer. More...

Static Public Member Functions
static size_t	get_num_bytes_from_bits (size_type num_bits)
	Converts the number of bits to number of bytes. More...

Static Public Attributes
static const size_type	npos = (size_type)-1
	Constant representing `not found'. More...

Private Types
typedef unsigned char	byte
	Private definition of byte to avoid polluting the global namespace. More...

Private Member Functions
byte	get_8bits (size_type offset, size_type end) const
	Retreive contiguous 8 bits from the bool_array. More...

Static Private Attributes
static byte	_S_bit_count [256]
	Array that contains pre-calculated values how many 1-bits there are in a given byte.

static byte	_S_bit_ordinal [256]
	Array that contains pre-calculated values which the first 1-bit is for a given byte. More...

Detailed Description

Class to represent a packed boolean array.

This was first written in April 1995, before I knew of any existing implementation of this kind of classes. Of course, the C++ Standard Template Library now demands an implementation of packed boolean array as vector<bool>, but the code here should still be useful for the following reasons:

Some compilers (like MSVC 6) did not implement this specialization (and they may not have a bit_vector either);
I included some additional member functions, like initialize, count, and find, which should be useful;
My tests show that the code here is significantly FASTER than vector<bool> (and the normal boolean array) under MSVC versions 6/8/9 and GCC versions before 4.3 (while the vector<bool> implementations of MSVC 7.1 and GCC 4.3 have performance similar to that of bool_array).

Member Typedef Documentation

◆ byte

typedef unsigned char nvwa::bool_array::byte

private

Private definition of byte to avoid polluting the global namespace.

◆ size_type

typedef unsigned long nvwa::bool_array::size_type

Type of array indices.

Constructor & Destructor Documentation

◆ bool_array() [1/3]

nvwa::bool_array::bool_array ( size_type size )

explicit

Constructs a bool_array with a specific size.

Parameters

size	size of the array

Exceptions

out_of_range	size equals `0`
bad_alloc	memory is insufficient

◆ bool_array() [2/3]

nvwa::bool_array::bool_array	(	const void *	ptr,
		size_type	size
	)

Constructs a bool_array from a given bitmap.

Parameters

ptr	pointer to a bitmap
size	size of the array

Exceptions

out_of_range	size equals `0`
bad_alloc	memory is insufficient

◆ bool_array() [3/3]

nvwa::bool_array::bool_array ( const bool_array & rhs )

Copy-constructor.

Parameters

rhs	the bool_array to copy from

Exceptions

bad_alloc memory is insufficient

Member Function Documentation

◆ at()

bool nvwa::bool_array::at ( size_type pos ) const

inline

Reads the boolean value of an array element at a specified position.

Parameters

pos	position of the array element to access

Returns: the boolean value of the accessed array element

Exceptions

out_of_range pos is greater than the size of the array

◆ copy_to_bitmap()

void nvwa::bool_array::copy_to_bitmap	(	void *	dest,
		size_type	begin = `0`,
		size_type	end = `npos`
	)

Copies the bool_array content as bitmap to a specified buffer.

The caller needs to ensure the destination buffer is big enough.

Parameters

dest	address of the destination buffer
begin	beginning of the range
end	end of the range (exclusive)

Exceptions

out_of_range bad range for the source or the destination

◆ count() [1/2]

bool_array::size_type nvwa::bool_array::count ( ) const

noexcept

Counts elements with a true value.

Returns: the count of true elements

◆ count() [2/2]

bool_array::size_type nvwa::bool_array::count	(	size_type	begin,
		size_type	end = `npos`
	)		const

Counts elements with a true value in a specified range.

Parameters

begin	beginning of the range
end	end of the range (exclusive)

Returns: the count of true elements

Exceptions

out_of_range the range [begin, end) is invalid

◆ create()

bool nvwa::bool_array::create ( size_type size )

noexcept

Creates the packed boolean array with a specific size.

Parameters

size	size of the array

Returns: false if size equals 0 or is too big, or if memory is insufficient; true if size has a suitable value and memory allocation is successful.

◆ find() [1/2]

bool_array::size_type nvwa::bool_array::find	(	bool	value,
		size_type	offset = `0`
	)		const

inline

Searches for the specified boolean value.

This function seaches from the specified position (default to beginning) to the end.

Parameters

offset	the position at which the search is to begin
value	the boolean value to find

Returns: position of the first value found if successful; npos otherwise

◆ find() [2/2]

bool_array::size_type nvwa::bool_array::find	(	bool	value,
		size_type	offset,
		size_type	count
	)		const

inline

Searches for the specified boolean value.

This function accepts a range expressed in {position, count}.

Parameters

offset	the position at which the search is to begin
count	the number of bits to search
value	the boolean value to find

Returns: position of the first value found if successful; npos otherwise

Exceptions

out_of_range offset and/or count is too big

◆ find_until()

bool_array::size_type nvwa::bool_array::find_until	(	bool	value,
		size_type	begin,
		size_type	end
	)		const

Searches for the specified boolean value.

This function accepts a range expressed in [begin, end).

Parameters

begin	the position at which the search is to begin
end	the end position (exclusive) to stop searching
value	the boolean value to find

Returns: position of the first value found if successful; npos otherwise

Exceptions

out_of_range the range [begin, end) is invalid

◆ get_8bits()

bool_array::byte nvwa::bool_array::get_8bits	(	size_type	offset,
		size_type	end
	)		const

private

Retreive contiguous 8 bits from the bool_array.

If fewer than 8 bits are available, the extra bits are undefined.

Parameters

offset	beginning position to retrieve the bits
end	end position beyond whose byte no bits will be taken

◆ get_num_bytes_from_bits()

size_t nvwa::bool_array::get_num_bytes_from_bits ( size_type num_bits )

inlinestatic

Converts the number of bits to number of bytes.

Parameters

num_bits number of bits

Returns: number of bytes needed to store num_bits bits

◆ initialize()

void nvwa::bool_array::initialize ( bool value )

noexcept

Initializes all array elements to a specific value optimally.

Parameters

value the boolean value to assign to all elements

◆ merge_and()

void nvwa::bool_array::merge_and	(	const bool_array &	rhs,
		size_type	begin = `0`,
		size_type	end = `npos`,
		size_type	offset = `0`
	)

Merges elements of another bool_array with a logical AND.

Parameters

rhs	another bool_array to merge
begin	beginning of the range in rhs
end	end of the range (exclusive) in rhs
offset	position to merge in this bool_array

Exceptions

out_of_range bad range for the source or the destination

◆ merge_or()

void nvwa::bool_array::merge_or	(	const bool_array &	rhs,
		size_type	begin = `0`,
		size_type	end = `npos`,
		size_type	offset = `0`
	)

Merges elements of another bool_array with a logical OR.

Parameters

rhs	another bool_array to merge
begin	beginning of the range in rhs
end	end of the range (exclusive) in rhs
offset	position to merge in this bool_array

Exceptions

out_of_range bad range for the source or the destination

◆ operator=()

bool_array & nvwa::bool_array::operator= ( const bool_array & rhs )

Assignment operator.

Parameters

rhs	the bool_array to copy from

Exceptions

bad_alloc memory is insufficient

◆ operator[]() [1/2]

bool_array::reference nvwa::bool_array::operator[] ( size_type pos )

inline

Creates a reference to an array element.

Parameters

pos	position of the array element to access

Returns: reference to the specified element

◆ operator[]() [2/2]

bool_array::const_reference nvwa::bool_array::operator[] ( size_type pos ) const

inline

Creates a const reference to an array element.

Parameters

pos	position of the array element to access

Returns: const reference to the specified element

◆ reset()

void nvwa::bool_array::reset ( size_type pos )

inline

Resets an array element to false at a specified position.

Parameters

pos	position of the array element to access

Exceptions

out_of_range pos is greater than the size of the array

◆ set()

void nvwa::bool_array::set ( size_type pos )

inline

Sets an array element to true at a specified position.

Parameters

pos	position of the array element to access

Exceptions

out_of_range pos is greater than the size of the array

◆ size()

bool_array::size_type nvwa::bool_array::size ( ) const

inlinenoexcept

Gets the size of the bool_array.

Returns: the number of bits of the bool_array

◆ swap()

void nvwa::bool_array::swap ( bool_array & rhs )

noexcept

Exchanges the content of this bool_array with another.

Parameters

rhs	another bool_array to exchange content with

Member Data Documentation

◆ _S_bit_ordinal

bool_array::byte nvwa::bool_array::_S_bit_ordinal

staticprivate

Array that contains pre-calculated values which the first 1-bit is for a given byte.

The first element indicates an invalid value (there are only 0-bits).

◆ npos

const size_type nvwa::bool_array::npos = (size_type)-1

static

Constant representing `not found'.

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

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Private Types

Private Member Functions

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ byte

◆ size_type

Constructor & Destructor Documentation

◆ bool_array() [1/3]

◆ bool_array() [2/3]

◆ bool_array() [3/3]

Member Function Documentation

◆ at()

◆ copy_to_bitmap()

◆ count() [1/2]

◆ count() [2/2]

◆ create()

◆ find() [1/2]

◆ find() [2/2]

◆ find_until()

◆ get_8bits()

◆ get_num_bytes_from_bits()

◆ initialize()

◆ merge_and()

◆ merge_or()

◆ operator=()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ reset()

◆ set()

◆ size()

◆ swap()

Member Data Documentation

◆ _S_bit_ordinal

◆ npos