nvwa::bool_array Class Reference

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

#include <bool_array.h>

Collaboration diagram for nvwa::bool_array:

Classes
class	_Element
	Class to represent a reference to an array element.
Public Types
typedef unsigned long	size_type
	Type of array indices.
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.
	bool_array (const void *ptr, size_type size)
	Constructs a bool_array from a given bitmap.
	~bool_array ()
	Destroys the bool_array and releases memory.
	bool_array (const bool_array &rhs)
	Copy-constructor.
bool_array &	operator= (const bool_array &rhs)
	Assignment operator.
bool	create (size_type size) noexcept
	Creates the packed boolean array with a specific size.
void	initialize (bool value) noexcept
	Initializes all array elements to a specific value optimally.
reference	operator[] (size_type pos)
	Creates a reference to an array element.
const_reference	operator[] (size_type pos) const
	Creates a const reference to an array element.
bool	at (size_type pos) const
	Reads the boolean value of an array element at a specified position.
void	reset (size_type pos)
	Resets an array element to `false` at a specified position.
void	set (size_type pos)
	Sets an array element to `true` at a specified position.
size_type	size () const noexcept
	Gets the size of the bool_array.
size_type	count () const noexcept
	Counts elements with a `true` value.
size_type	count (size_type begin, size_type end=npos) const
	Counts elements with a `true` value in a specified range.
size_type	find (bool value, size_type offset=0) const
	Searches for the specified boolean value.
size_type	find (bool value, size_type offset, size_type count) const
	Searches for the specified boolean value.
size_type	find_until (bool value, size_type begin, size_type end) const
	Searches for the specified boolean value.
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.
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.
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.
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.
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.
Static Public Attributes
static const size_type	npos = (size_type)-1
	Constant representing `not found'.

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

typedef _Element<const byte> nvwa::bool_array::const_reference

Type of const reference.

typedef _Element<byte> nvwa::bool_array::reference

Type of reference.

typedef unsigned long nvwa::bool_array::size_type

Type of array indices.

Constructor & Destructor Documentation

nvwa::bool_array::bool_array ( ) [inline]

Constructs an empty bool_array.

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

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

nvwa::bool_array::~bool_array ( ) [inline]

Destroys the bool_array and releases memory.

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

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

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

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

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

Counts elements with a true value.

Returns:: the count of true elements

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

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.

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

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

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

void nvwa::bool_array::flip ( )

Changes all true elements to false, and false ones to true.

size_t nvwa::bool_array::get_num_bytes_from_bits ( size_type num_bits ) [inline, static]

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

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

Initializes all array elements to a specific value optimally.

Parameters:

value

the boolean value to assign to all elements

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

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

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

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

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

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

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

bool_array::size_type nvwa::bool_array::size ( ) const [inline]

Gets the size of the bool_array.

Returns:: the number of bits of the bool_array

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

Exchanges the content of this bool_array with another.

Parameters:

rhs

another bool_array to exchange content with

Member Data Documentation

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:

nvwa::bool_array Class Reference

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation