RE/flex Bits class for dynamic bit vectors. More...

#include <bits.h>

Classes
struct	Bitref
	References a single bit, returned by operator[]. More...

Public Member Functions
	Bits ()
	Construct an empty bit vector. More...

	Bits (const Bits &bits)
	Copy constructor. More...

	Bits (size_t n)
	Construct a bit vector and set n'th bit. More...

	Bits (size_t n1, size_t n2)
	Construct a bit vector and set a range of bits n1'th to n2'th. More...

	~Bits ()
	Destroy bits. More...

Bits &	operator= (const Bits &bits)
	Assign bits. More...

Bitref	operator[] (size_t n)
	Reference n'th bit in the bit vector to assign a value to that bit. More...

bool	operator[] (size_t n) const
	Returns n'th bit. More...

Bits &	insert (size_t n)
	Insert and set a bit in the bit vector. More...

Bits &	erase (size_t n)
	Erase a bit in the bit vector. More...

Bits &	flip (size_t n)
	Flips a bit in the bit vector. More...

Bits &	insert (size_t n1, size_t n2)
	Insert and set a range of bits in the bit vector. More...

Bits &	erase (size_t n1, size_t n2)
	Erase a range of bits in the bit vector. More...

Bits &	flip (size_t n1, size_t n2)
	Flip a range of bits in the bit vector. More...

Bits &	lshift ()
	Bit-shift left by one. More...

Bits &	rshift ()
	Bit-shift right by one. More...

Bits &	operator\|= (const Bits &bits)
	Bit-or (set union) the bit vector with the given bits. More...

Bits &	operator&= (const Bits &bits)
	Bit-and (set intersection) the bit vector with the given bits. More...

Bits &	operator^= (const Bits &bits)
	Bit-xor the bit vector with the given bits. More...

Bits &	operator-= (const Bits &bits)
	Bit-delete (set minus) the bit vector with the given bits. More...

Bits	operator\| (const Bits &bits) const
	Bit-or (set union) of two bit vectors. More...

Bits	operator& (const Bits &bits) const
	Bit-and (set intersection) of two bit vectors. More...

Bits	operator^ (const Bits &bits) const
	Bit-xor of two bit vectors. More...

Bits	operator- (const Bits &bits) const
	Bit-delete (set minus) of two bit vectors. More...

Bits	operator~ () const
	Complement of the bit vector with all bits flipped. More...

bool	operator== (const Bits &bits) const
	Returns true if bit vectors are equal. More...

bool	operator!= (const Bits &bits) const
	Returns true if bit vectors are unequal. More...

bool	operator< (const Bits &bits) const
	Returns true if the bit vector is lexicographically less than the given right-hand side bits. More...

bool	operator> (const Bits &bits) const
	Returns true if the bit vector is lexicographically greater than the given right-hand side bits. More...

bool	operator<= (const Bits &bits) const
	Returns true if the bit vector is lexicographically less-or-equal to the given right-hand side bits. More...

bool	operator>= (const Bits &bits) const
	Returns true if the bit vector is lexicographically greater-or-equal to the given right-hand side bits. More...

bool	all () const
	Returns true if all bits are set. More...

bool	any () const
	Returns true if any bit is set. More...

Bits &	clear ()
	Erase all bits. More...

Bits &	flip ()
	Flip all bits. More...

Bits &	reserve (size_t len)
	Reserves space in the bit vector for len bits without changing its current content. More...

size_t	size () const
	Returns the current length of the bit vector. More...

size_t	count () const
	Returns the number of bits set. More...

bool	intersects (const Bits &bits) const
	Returns true if the bit vector intersects with the given bits, false if the bit vectors are disjoint. More...

bool	contains (const Bits &bits) const
	Returns true if the given bits are a subset of the bit vector, i.e. for each bit in bits, the corresponding bit in the bit vector is set. More...

size_t	find_first (size_t n=0) const
	Returns the position of the first bit set in the bit vector, or Bits::npos if none. More...

size_t	find_next (size_t n) const
	Returns the next position of a bit set in the bit vector, or Bits::npos if none. More...

void	swap (Bits &bits)
	Swap bit vectors. More...

Static Public Attributes
static const size_t	npos = static_cast<size_t>(-1)

Private Member Functions
void	alloc (size_t len)
	On-demand allocator. More...

Private Attributes
size_t	len_
	number of words More...

uint64_t *	vec_
	array of words More...

Detailed Description

RE/flex Bits class for dynamic bit vectors.

Dynamic bit vectors are stored in Bits objects, which can be manipulated with the usual bit-operations (| (bitor), & (bitand), ^ (bitxor)). Supports comparison relations on bit vectors, check if all bits set, check if any bits are set, flip bits, shift bits left or right, count bits, check if a bit vectors intersects another, check if a bit vector contains another. find_first bit, find_next bit.

Example:

reflex::Bits digit('0', '9'); // bits '0' (48th bit) to '9' (57th bit)
reflex::Bits upper('A', 'Z'); // bits 'A' (65th bit) to 'Z' (92th bit)
reflex::Bits lower('a', 'z'); // bits 'a' (97th bit) to 'z' (122th bit)
if (upper.intersects(lower) == false)
  std::cout << "upper and lower are disjoint\n";
reflex::Bits alnum = digit | upper | lower;
if (alnum.contains(digit) == true)
  std::cout << "digit is a subset of alnum\n";
if (alnum['_'] == false)
  std::cout << "_ is not in alnum\n";
alnum['_'] = true;
if (alnum['_'] == true)
  std::cout << "_ is in updated alnum\n";
std::cout << alnum.count() << " bits in alnum\n";
for (size_t i = alnum.find_first(); i != reflex::Bits::npos; i = alnum.find_next(i))
  std::cout << (char)i;

Output:

upper and lower are disjoint
digit is a subset of alnum
_ is not in alnum
_ is in updated alnum
63 bits in alnum
0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz

Constructor & Destructor Documentation

reflex::Bits::Bits ( )

inline

Construct an empty bit vector.

reflex::Bits::Bits ( const Bits & bits )

inline

Copy constructor.

Parameters

bits	bits to copy

reflex::Bits::Bits ( size_t n )

inline

Construct a bit vector and set n'th bit.

Parameters

n	n'th bit to set

reflex::Bits::Bits	(	size_t	n1,
		size_t	n2
	)

inline

Construct a bit vector and set a range of bits n1'th to n2'th.

Parameters

n1	first bit to set
n2	last bit to set

reflex::Bits::~Bits ( )

inline

Destroy bits.

Member Function Documentation

bool reflex::Bits::all ( ) const

inline

Returns true if all bits are set.

Returns: true if all bits set, false otherwise.

void reflex::Bits::alloc ( size_t len )

inlineprivate

On-demand allocator.

Parameters

len	number of words required

bool reflex::Bits::any ( ) const

inline

Returns true if any bit is set.

Returns: true if any bit set, false if none.

Bits& reflex::Bits::clear ( )

inline

Erase all bits.

Returns: reference to this object.

bool reflex::Bits::contains ( const Bits & bits ) const

inline

Returns true if the given bits are a subset of the bit vector, i.e. for each bit in bits, the corresponding bit in the bit vector is set.

Returns: true if bits is a subset.

Parameters

bits bits

size_t reflex::Bits::count ( ) const

inline

Returns the number of bits set.

Returns: number of 1 bits.

Bits& reflex::Bits::erase ( size_t n )

inline

Erase a bit in the bit vector.

Returns: reference to this object.

Parameters

n	n'th bit to erase

Bits& reflex::Bits::erase	(	size_t	n1,
		size_t	n2
	)

inline

Erase a range of bits in the bit vector.

Returns: reference to this object.

Parameters

n1	first bit to erase
n2	last bit to erase

size_t reflex::Bits::find_first ( size_t n = 0 ) const

inline

Returns the position of the first bit set in the bit vector, or Bits::npos if none.

Returns: first position or Bits::npos.

Parameters

n	internal parameter (do not use)

size_t reflex::Bits::find_next ( size_t n ) const

inline

Returns the next position of a bit set in the bit vector, or Bits::npos if none.

Returns: next position or Bits::npos.

Parameters

n	the current position to search from

Bits& reflex::Bits::flip ( size_t n )

inline

Flips a bit in the bit vector.

Returns: reference to this object.

Parameters

n	n'th bit to flip

Bits& reflex::Bits::flip	(	size_t	n1,
		size_t	n2
	)

inline

Flip a range of bits in the bit vector.

Returns: reference to this object.

Parameters

n1	first bit to flip
n2	last bit to flip

Bits& reflex::Bits::flip ( )

inline

Flip all bits.

Returns: reference to this object.

Bits& reflex::Bits::insert ( size_t n )

inline

Insert and set a bit in the bit vector.

Returns: reference to this object.

Parameters

n	n'th bit to set

Bits& reflex::Bits::insert	(	size_t	n1,
		size_t	n2
	)

inline

Insert and set a range of bits in the bit vector.

Returns: reference to this object.

Parameters

n1	first bit to set
n2	last bit to set

bool reflex::Bits::intersects ( const Bits & bits ) const

inline

Returns true if the bit vector intersects with the given bits, false if the bit vectors are disjoint.

Returns: true if bits intersect or false if disjoint.

Parameters

bits bits

Bits& reflex::Bits::lshift ( )

inline

Bit-shift left by one.

bool reflex::Bits::operator!= ( const Bits & bits ) const

inline

Returns true if bit vectors are unequal.

Returns: true (unequal) or false (equal).

Parameters

bits rhs bits

Bits reflex::Bits::operator& ( const Bits & bits ) const

inline

Bit-and (set intersection) of two bit vectors.

Returns: bit vector of the result.

Parameters

bits bits

Bits& reflex::Bits::operator&= ( const Bits & bits )

inline

Bit-and (set intersection) the bit vector with the given bits.

Returns: reference to this object.

Parameters

bits bits

Bits reflex::Bits::operator- ( const Bits & bits ) const

inline

Bit-delete (set minus) of two bit vectors.

Returns: bit vector of the result.

Parameters

bits bits

Bits& reflex::Bits::operator-= ( const Bits & bits )

inline

Bit-delete (set minus) the bit vector with the given bits.

Returns: reference to this object.

Parameters

bits bits

bool reflex::Bits::operator< ( const Bits & bits ) const

inline

Returns true if the bit vector is lexicographically less than the given right-hand side bits.

Returns: true (less) or false (greater-or-equal).

Parameters

bits rhs bits

bool reflex::Bits::operator<= ( const Bits & bits ) const

inline

Returns true if the bit vector is lexicographically less-or-equal to the given right-hand side bits.

Returns: true (less-or-equal) or false (greater).

Parameters

bits rhs bits

Bits& reflex::Bits::operator= ( const Bits & bits )

inline

Assign bits.

Returns: reference to this object.

Parameters

bits	bits to copy

bool reflex::Bits::operator== ( const Bits & bits ) const

inline

Returns true if bit vectors are equal.

Returns: true (equal) or false (unequal).

Parameters

bits rhs bits

bool reflex::Bits::operator> ( const Bits & bits ) const

inline

Returns true if the bit vector is lexicographically greater than the given right-hand side bits.

Returns: true (greater) or false (less-or-equal).

Parameters

bits rhs bits

bool reflex::Bits::operator>= ( const Bits & bits ) const

inline

Returns true if the bit vector is lexicographically greater-or-equal to the given right-hand side bits.

Returns: true (greater-or-equal) or false (less).

Parameters

bits rhs bits

Bitref reflex::Bits::operator[] ( size_t n )

inline

Reference n'th bit in the bit vector to assign a value to that bit.

Returns: bit reference to assign.

Parameters

n n'th bit

bool reflex::Bits::operator[] ( size_t n ) const

inline

Returns n'th bit.

Returns: true if n'th bit is set, false otherwise.

Parameters

n	n'th bit to return

Bits reflex::Bits::operator^ ( const Bits & bits ) const

inline

Bit-xor of two bit vectors.

Returns: bit vector of the result.

Parameters

bits bits

Bits& reflex::Bits::operator^= ( const Bits & bits )

inline

Bit-xor the bit vector with the given bits.

Returns: reference to this object.

Parameters

bits bits

Bits reflex::Bits::operator| ( const Bits & bits ) const

inline

Bit-or (set union) of two bit vectors.

Returns: bit vector of the result.

Parameters

bits bits

Bits& reflex::Bits::operator|= ( const Bits & bits )

inline

Bit-or (set union) the bit vector with the given bits.

Returns: reference to this object.

Parameters

bits bits

Bits reflex::Bits::operator~ ( ) const

inline

Complement of the bit vector with all bits flipped.

Returns: bit vector of the result.

Bits& reflex::Bits::reserve ( size_t len )

inline

Reserves space in the bit vector for len bits without changing its current content.

Returns: reference to this object.

Parameters

len	number of bits to reserve

Bits& reflex::Bits::rshift ( )

inline

Bit-shift right by one.

size_t reflex::Bits::size ( ) const

inline

Returns the current length of the bit vector.

Returns: number of bits.

void reflex::Bits::swap ( Bits & bits )

inline

Swap bit vectors.

Parameters

bits bits

Member Data Documentation

size_t reflex::Bits::len_

private

number of words

const size_t reflex::Bits::npos = static_cast<size_t>(-1)

static

npos returned by find_first() and find_next()

uint64_t* reflex::Bits::vec_

private

array of words

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

bits.h

Classes

Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation