Truth table data structures

Dynamic truth table

The header <kitty/dynamic_truth_table.hpp> implements a dynamic truth table. A dynamic truth table can be initialized with a number of variables that is computed at runtime.

The class kitty::dynamic_truth_table provides the following public member functions.

Function

Description

dynamic_truth_table(num_vars)

Standard constructor.

construct()

Constructs a new dynamic truth table instance with the same number of variables.

num_vars()

Returns number of variables.

num_blocks()

Returns number of blocks.

num_bits()

Returns number of bits.

begin()

Begin iterator to bits.

end()

End iterator to bits.

rbegin()

Reverse begin iterator to bits.

rend()

Reverse end iterator to bits.

cbegin()

Constant begin iterator to bits.

cend()

Constant end iterator to bits.

crbegin()

Constant reverse begin iterator to bits.

crend()

Constant reverse end iterator to bits.

operator=(other)

Assignment operator.

mask_bits()

Masks the number of valid truth table bits.

struct kitty::dynamic_truth_table

Truth table in which number of variables is known at runtime.

Public Functions

inline explicit dynamic_truth_table(uint32_t num_vars)

Standard constructor.

The number of variables provided to the truth table can be computed at runtime. However, once the truth table is constructed its number of variables cannot change anymore.

The constructor computes the number of blocks and resizes the vector accordingly.

Parameters

num_vars – Number of variables

inline dynamic_truth_table()

Empty constructor.

Creates an empty truth table. It has 0 variables, but no bits, i.e., it is different from a truth table for the constant function. This constructor is only used for convenience, if algorithms require the existence of default constructable classes.

inline dynamic_truth_table construct() const

Constructs a new dynamic truth table instance with the same number of variables.

inline auto num_vars() const noexcept

Returns number of variables.

inline auto num_blocks() const noexcept

Returns number of blocks.

inline auto num_bits() const noexcept

Returns number of bits.

inline auto begin() noexcept

Begin iterator to bits.

inline auto end() noexcept

End iterator to bits.

inline auto begin() const noexcept

Begin iterator to bits.

inline auto end() const noexcept

End iterator to bits.

inline auto rbegin() noexcept

Reverse begin iterator to bits.

inline auto rend() noexcept

Reverse end iterator to bits.

inline auto cbegin() const noexcept

Constant begin iterator to bits.

inline auto cend() const noexcept

Constant end iterator to bits.

inline auto crbegin() const noexcept

Constant reverse begin iterator to bits.

inline auto crend() const noexcept

Constant teverse end iterator to bits.

template<class TT, typename = std::enable_if_t<is_truth_table<TT>::value && is_complete_truth_table<TT>::value>>
inline dynamic_truth_table &operator=(const TT &other)

Assign other truth table.

This replaces the current truth table with another truth table. The truth table type has to be complete. The vector of bits is resized accordingly.

Parameters

other – Other truth table

inline void mask_bits() noexcept

Masks the number of valid truth table bits.

If the truth table has less than 6 variables, it may not use all the bits. This operation makes sure to zero out all non-valid bits.

Static truth table

The header <kitty/static_truth_table.hpp> implements a static truth table. A static truth table must be initialized with a number of variables that is computed at compile time. It performs much faster than the dynamic truth table. Also it is optimized for a small number of variables, i.e., up to 6 variables. Then a truth table fits into a single block of 64 bits. The interface makes this optimization intransparent to the user.

The class kitty::static_truth_table provides the following public member functions.

Function

Description

static_truth_table()

Standard constructor.

construct()

Constructs a new static truth table instance with the same number of variables.

num_vars()

Returns number of variables.

num_blocks()

Returns number of blocks.

num_bits()

Returns number of bits.

begin()

Begin iterator to bits.

end()

End iterator to bits.

rbegin()

Reverse begin iterator to bits.

rend()

Reverse end iterator to bits.

cbegin()

Constant begin iterator to bits.

cend()

Constant end iterator to bits.

crbegin()

Constant reverse begin iterator to bits.

crend()

Constant reverse end iterator to bits.

operator=(other)

Assignment operator.

mask_bits()

Masks the number of valid truth table bits.

template<uint32_t NumVars, bool = (NumVars <= 6)>
struct static_truth_table

Truth table in which number of variables is known at compile time.

We dispatch on the Boolean template parameter to distinguish between a small truth table (up to 6 variables) and a large truth table (more than 6 variables). A small truth table fits into a single block and therefore dedicated optimizations are possible.

Partial truth table

The header <kitty/partial_truth_table.hpp> implements a partial truth table. Unlike dynamic truth tables and static truth tables, which are known as “complete truth table” types, the length of a partial truth table is not limited to a power of 2. A partial truth table can be initialized with an arbitrary number of bits.

The class kitty::partial_truth_table provides the following public member functions.

Function

Description

partial_truth_table(num_bits)

Standard constructor.

construct()

Constructs a new partial truth table instance with the same number of bits.

num_blocks()

Returns number of blocks.

num_bits()

Returns number of bits.

begin()

Begin iterator to bits.

end()

End iterator to bits.

rbegin()

Reverse begin iterator to bits.

rend()

Reverse end iterator to bits.

cbegin()

Constant begin iterator to bits.

cend()

Constant end iterator to bits.

crbegin()

Constant reverse begin iterator to bits.

crend()

Constant reverse end iterator to bits.

operator=(other)

Assignment operator.

mask_bits()

Masks the number of valid truth table bits.

resize(num_bits)

Resize the truth table to have the given number of bits.

add_bit(bit)

Add a bit to the end of the truth table.

add_bits(bits)

Add several bits to the end of the truth table.

copy_bits(from, to)

Overwrite the value at position from to position to.

erase_bit_swap(position)

Erase the bit at the given position by swapping with the last bit and shrinking the truth table.

erase_bit_shift(position)

Erase the bit at the given position and shift all the following bits.

struct kitty::partial_truth_table

Truth table with resizable, arbitrary number of bits

Public Functions

inline explicit partial_truth_table(uint32_t num_bits)

Standard constructor.

Parameters

num_bits – Number of bits in use initially

inline partial_truth_table()

Empty constructor.

Creates an empty truth table. It has no bit in use. This constructor is only used for convenience, if algorithms require the existence of default constructable classes.

inline partial_truth_table construct() const

Constructs a new partial truth table instance with the same number of bits and blocks.

inline auto num_blocks() const noexcept

Returns number of (allocated) blocks.

inline auto num_bits() const noexcept

Returns number of (used) bits.

inline auto begin() noexcept

Begin iterator to bits.

inline auto end() noexcept

End iterator to bits.

inline auto begin() const noexcept

Begin iterator to bits.

inline auto end() const noexcept

End iterator to bits.

inline auto rbegin() noexcept

Reverse begin iterator to bits.

inline auto rend() noexcept

Reverse end iterator to bits.

inline auto cbegin() const noexcept

Constant begin iterator to bits.

inline auto cend() const noexcept

Constant end iterator to bits.

inline auto crbegin() const noexcept

Constant reverse begin iterator to bits.

inline auto crend() const noexcept

Constant teverse end iterator to bits.

template<class TT, typename = std::enable_if_t<is_truth_table<TT>::value>>
inline partial_truth_table &operator=(const TT &other)

Assign other truth table.

This replaces the current truth table with another truth table. The truth table type is arbitrary. The vector of bits is resized accordingly.

Parameters

other – Other truth table

inline void mask_bits() noexcept

Masks the number of valid truth table bits.

If not all the bits in the last block are used up, we block out the remaining bits (fill with zero). Bits are used from LSB.

inline void resize(int num_bits) noexcept

Resize the truth table to have the given number of bits.

If the desired length is larger than the current length, zeros will be filled up in the end of the truth table. If the desired length is shorter than the current length, extra bits in the end of the truth table will be discarded.

Parameters

num_bits – Desired length (number of bits)

inline void add_bit(bool bit) noexcept

Add a bit to the end of the truth table.

Parameters

bit – Bit to be added

inline void add_bits(std::vector<bool> &bits) noexcept

Add several bits to the end of the truth table.

Parameters

bits – Bits to be added

inline void add_bits(uint64_t bits, int num_bits = 64) noexcept

Add several bits to the end of the truth table.

Parameters
  • bits – Bits to be added

  • num_bits – Number of bits in bits to be added (counted from LSB)

inline void copy_bit(uint32_t from, uint32_t to)

Overwrite the value at position from to position to.

Parameters
  • from – Position of the bit to be copied

  • to – Position of the bit to be overwritten

inline void erase_bit_swap(uint32_t position)

Erase the bit at the given position by swapping with the last bit and shrinking the truth table.

This method is faster than erase_bit but do not keep the order of the bits.

Parameters

position – Position of the bit to be erased

inline void erase_bit_shift(uint32_t position)

Erase the bit at the given position and shift all the following bits.

This method keeps the order of the bits but is slower and do not keep the position of the bits.

Parameters

position – Position of the bit to be erased