dlinear::BitIncrementIterator Class Reference

BitIncrementIterator class. More...

#include <BitIncrementIterator.h>

Public Member Functions
	BitIncrementIterator (std::size_t n)
	Construct a new BitIncrementIterator object.
	BitIncrementIterator (std::vector< bool > starting_value)
	Construct a new BitIncrementIterator object.
bool	IsFixed (std::size_t i) const
	Check if the bit at position i is fixed.
void	Set (std::size_t i, bool value, bool force=false)
	Set the i 't bit of the vector to value.
void	SetFixed (std::size_t i, bool fixed)
	Set whether the i 'th bit of the vector is fixed.
bool	Learn (std::size_t i)
	Learn the value of the bit at position i by inverting the bit.
bool	Learn (std::size_t i, bool value)
	Learn the value of the bit at position i by setting the bit to value.

Private Member Functions
void	ResetNonFixedRight (std::size_t start_pos=0)
	Reset all the non-fixed bits to the right of start_pos to their starting value.
void	ResetNonFixedLeft (std::size_t start_pos)
	Reset all the non-fixed bits to the left of start_pos to their starting value.
void	ResetNonFixed ()
	Reset all the non-fixed bits in the vector to their starting value.
bool	IsDone () const
	Check if the iterator is done.
void	UpdateVector (std::size_t i, bool value)
	After a Learn operation to set the i 'th bit to value, update the vector.

Private Attributes
std::vector< bool >	vector_
	The bit vector that will assume all the possible values.
std::vector< bool >	fixed_
	Vector to indicate the fixed bits.
std::vector< bool >	starting_vector_
	Vector to store the starting value of the iterator.
std::vector< bool >	ending_vector_
	Vector to store the ending value of the iterator.

Detailed Description

BitIncrementIterator class.

The BitIncrementIterator class is an abstraction used to iterate over all the possible bit vectors of a given size. It stores a vector of booleans and each time it is incremented, it changes the vector to the next possible bit vector. The result simulates the increment operation of a binary number. If the iterator is incremented when boolean vector if filled with true, the vector itself is cleared and the iterator is considered done.

// Example usage:
for (BitIncrementIterator it(3); it; ++it) {
  for (bool b : *it) {
    std::cout << b;
  }
  std::cout << ", ";
}
std::cout << std::endl;
// Output:
// 000, 001, 010, 011, 100, 101, 110, 111,

The default behaviour of this class ensures full-exploration-guarantee: all possible configuration the bit vector can be in will be explored. Using any Learn method will continue to maintain the guarantee over the now halved configuration space, but some previously visited configuration may appear again.

// Example learn:
BitIncrementIterator it(3);
it.Learn(1, true); // Fix the second bit to 1
for (; it; ++it) {
  for (bool b : *it) {
    std::cout << b;
  }
  std::cout << ", ";
}
std::cout << std::endl;
// Output:
// 010, 011, 110, 111,

Warning

Any manual alteration of the vector invalidates the guarantee.

Definition at line 58 of file BitIncrementIterator.h.

Constructor & Destructor Documentation

BitIncrementIterator() [1/2]

dlinear::BitIncrementIterator::BitIncrementIterator ( std::size_t n )

inlineexplicit

Construct a new BitIncrementIterator object.

The vector is initialized with n bits set to false. If n is 0, the vector is empty and is considered done immediately.

Parameters

n	number of bits in the vector

Definition at line 73 of file BitIncrementIterator.h.

BitIncrementIterator() [2/2]

dlinear::BitIncrementIterator::BitIncrementIterator ( std::vector< bool > starting_value )

explicit

Construct a new BitIncrementIterator object.

The vector is initialized with the value of starting_value. After enumerating all possible boolean vectors, the iterator will terminate and the vector will be cleared.

Parameters

starting_value

vector of booleans to initialize the iterator with

Definition at line 35 of file BitIncrementIterator.cpp.

Member Function Documentation

IsDone()

bool dlinear::BitIncrementIterator::IsDone ( ) const

nodiscardprivate

Check if the iterator is done.

This happens when the vector is filled with true in every non-fixed position.

Returns

true if the iterator is done

false if the iterator is not done

Definition at line 102 of file BitIncrementIterator.cpp.

IsFixed()

bool dlinear::BitIncrementIterator::IsFixed ( std::size_t i ) const

inlinenodiscard

Check if the bit at position i is fixed.

A bit is fixed if it is set to a specific value using the Learn method. A fixed bit's value cannot be changed anymore by the increment operation.

Parameters

i	index of the bit to check. The index must be in the range [0, n), big endian order.

Returns

true if the bit is fixed

false if the bit is not fixed

Exceptions

std::out_of_range

if i is out of range

Definition at line 110 of file BitIncrementIterator.h.

Learn() [1/2]

bool dlinear::BitIncrementIterator::Learn

(

std::size_t

i

)

Learn the value of the bit at position i by inverting the bit.

Invert the bit at position i and fix it to the new value. A fixed bit's value cannot be changed anymore by the increment operation.

Note

Other vector's values may change to maintain the full-exploration-guarantee. If you want to avoid this behaviour, use Set and SetFixed manually.

Some previously visited configuration may appear again.

Parameters

i	index of the bit to check. The index must be in the range [0, n), big endian order.

Returns

true if the bit has been fixed

false if the bit was already fixed

Exceptions

std::out_of_range

if i is out of range

Learn() [2/2]

bool dlinear::BitIncrementIterator::Learn	(	std::size_t	i,
		bool	value )

Learn the value of the bit at position i by setting the bit to value.

Set the value of the bit at position i to value and fix it to the new value. A fixed bit's value cannot be changed anymore by the increment operation.

Note

Other vector's values may change to maintain the full-exploration-guarantee. If you want to avoid this behaviour, use Set and SetFixed manually.

Some previously visited configuration may appear again.

Parameters

i	index of the bit to check. The index must be in the range [0, n), big endian order.
value	value to set the bit to

Returns

true if the bit has now value value

false if the bit was already fixed and therefore not changed

Exceptions

std::out_of_range

if i is out of range

ResetNonFixedLeft()

void dlinear::BitIncrementIterator::ResetNonFixedLeft ( std::size_t start_pos )

private

Reset all the non-fixed bits to the left of start_pos to their starting value.

Parameters

start_pos

starting position. The index must be in the range [0, n), big endian order.

Definition at line 116 of file BitIncrementIterator.cpp.

ResetNonFixedRight()

void dlinear::BitIncrementIterator::ResetNonFixedRight ( std::size_t start_pos = 0 )

private

Reset all the non-fixed bits to the right of start_pos to their starting value.

Parameters

start_pos

starting position. The index must be in the range [0, n), big endian order.

Definition at line 110 of file BitIncrementIterator.cpp.

Set()

void dlinear::BitIncrementIterator::Set ( std::size_t i, bool value, bool force = false )

inline

Set the i 't bit of the vector to value.

If the bit was fixed, no operation will be performed unless force is specified.

Warning

Using this method means losing the full-exploration-guarantee.

Parameters

i	index of the bit to change
value	new value of the bit
force	whether to ignore if the bit is fixed. This will not change it's fixed status

Definition at line 121 of file BitIncrementIterator.h.

SetFixed()

void dlinear::BitIncrementIterator::SetFixed ( std::size_t i, bool fixed )

inline

Set whether the i 'th bit of the vector is fixed.

Warning

Using this method means losing the full-exploration-guarantee.

Parameters

i	index of the bit to make fixed or un-fixed
fixed	whether the bit should be fixed or not

Definition at line 130 of file BitIncrementIterator.h.

UpdateVector()

void dlinear::BitIncrementIterator::UpdateVector ( std::size_t i, bool value )

private

After a Learn operation to set the i 'th bit to value, update the vector.

Set the i 'th bit to value, potentially modifying the vector in order to ensure a full exploration.

Parameters

i	index of the bit to set
value	new value of the bit

Definition at line 128 of file BitIncrementIterator.cpp.

---

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

• dlinear/util/BitIncrementIterator.h
• dlinear/util/BitIncrementIterator.cpp