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

Ternary truth table¶

The header <kitty/ternary_truth_table.hpp> implements a truth table with don’t cares. That is, a truth table in which some output values are ignored, either because they are not of any interest or because they are unknown. A ternary truth table is composed by two truth tables of the same type: one representing the bits and the other representing the care. A don’t care is represented as a 0 in the bit truth table and a 0 in the care truth table.

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

Function	Description
`ternary_truth_table(num_bits)`	Standard constructor.
`ternary_truth_table()`	Empty constructor.
`ternary_truth_table(bits, care)`	Construct from bits and care.
`ternary_truth_table(bits)`	Construct from a binary truth table.
`construct()`	Constructs a new partial truth table instance with the same number of bits.
`num_vars()`	Returns number of variables.
`num_blocks()`	Returns number of blocks.
`num_bits()`	Returns number of bits.
`begin_bits()`	Begin iterator to bits.
`end_bits()`	End iterator to bits.
`rbegin_bits()`	Reverse begin iterator to bits.
`rend_bits()`	Reverse end iterator to bits.
`cbegin_bits()`	Constant begin iterator to bits.
`cend_bits()`	Constant end iterator to bits.
`crbegin_bits()`	Constant reverse begin iterator to bits.
`crend_bits()`	Constant reverse end iterator to bits.
`begin_care()`	Begin iterator to care.
`end_care()`	End iterator to care.
`rbegin_care()`	Reverse begin iterator to care.
`rend_care()`	Reverse end iterator to care.
`cbegin_care()`	Constant begin iterator to care.
`cend_care()`	Constant end iterator to care.
`crbegin_care()`	Constant reverse begin iterator to care.
`crend_care()`	Constant reverse end iterator to care.
`operator=(other)`	Assign other ternary truth table or binary truth table with all bits
`mask_bits()`	Masks valid truth table bits.

template<class TT> struct kitty::ternary_truth_table

Public Functions

inline explicit ternary_truth_table(uint32_t n)¶

Standard constructor.

Initialize the truth table using the constructor of the inner truth table type.

Parameters: n – Number of variables or number of bits (when TT = partial_truth_table)

inline ternary_truth_table()¶

Empty constructor.

Creates an empty truth table by calling the empty constructor of the inner truth table type.

inline ternary_truth_table(TT const &bits, TT const &care)¶

Construct from bits and care.

When care bit is 0, bits bit must be 0, meaning a don’t care bit.

Parameters

bits – Bits truth table.
care – Care truth table.

inline ternary_truth_table(TT const &binary)¶

Construct from a binary truth table.

Initialize the truth table as equivalent to a binary truth table. (All bits are cared.)

Parameters: binary – Binary truth table.

inline ternary_truth_table<TT> construct() const¶: Constructs a new ternary_truth_table instance of the same size.

template<typename = std::enable_if_t<is_complete_truth_table<TT>::value>> 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_bits() noexcept¶: Begin iterator to bits.

inline auto end_bits() noexcept¶: End iterator to bits.

inline auto begin_bits() const noexcept¶: Begin iterator to bits.

inline auto end_bits() const noexcept¶: End iterator to bits.

inline auto rbegin_bits() noexcept¶: Reverse begin iterator to bits.

inline auto rend_bits() noexcept¶: Reverse end iterator to bits.

inline auto cbegin_bits() const noexcept¶: Constant begin iterator to bits.

inline auto cend_bits() const noexcept¶: Constant end iterator to bits.

inline auto crbegin_bits() const noexcept¶: Constant reverse begin iterator to bits.

inline auto crend_bits() const noexcept¶: Constant teverse end iterator to bits.

inline auto begin_care() noexcept¶: Begin iterator to care.

inline auto end_care() noexcept¶: End iterator to care.

inline auto begin_care() const noexcept¶: Begin iterator to care.

inline auto end_care() const noexcept¶: End iterator to care.

inline auto rbegin_care() noexcept¶: Reverse begin iterator to care.

inline auto rend_care() noexcept¶: Reverse end iterator to care.

inline auto cbegin_care() const noexcept¶: Constant begin iterator to care.

inline auto cend_care() const noexcept¶: Constant end iterator to care.

inline auto crbegin_care() const noexcept¶: Constant reverse begin iterator to care.

inline auto crend_care() const noexcept¶: Constant teverse end iterator to care.

template<class TT2> inline ternary_truth_table<TT> &operator=(const ternary_truth_table<TT2> &other)¶

Assign other truth table.

This replaces the current truth table with another truth table. The other truth table must also be ternary, and the inner type of the other truth table must be assignable to the inner type of this truth table.

Parameters: other – Other truth table

template<class TT2> inline ternary_truth_table<TT> &operator=(TT const &other)¶

Assigned by a binary truth table.

Replaces with a truth table equivalent to a binary truth table. (All bits are cared.)

Parameters: other – Binary truth table.

inline void mask_bits() noexcept¶

Masks valid truth table bits.

This operation makes sure to zero out all unused bits.

Quaternary truth table¶

The header <kitty/quaternary_truth_table.hpp> implements a truth table with don’t cares and don’t knows. That is, a truth table in which some output values are ignored, either because they are not of any interest or because they are unknown. A quaternary truth table is composed by two truth tables of the same type: one representing the onset and the other representing the offset. A don’t care (“-”) is represented as two 1 in both the onset and offset truth tables. A don’t know (“x”) is represented as two 0 in both the onset and offset truth tables.

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

template<class TT> struct kitty::quaternary_truth_table

Public Functions

inline explicit quaternary_truth_table(uint32_t n)¶

Standard constructor.

Initialize the truth table using the constructor of the inner truth table type.

Parameters: n – Number of variables or number of bits (when TT = partial_truth_table)

inline quaternary_truth_table()¶

Empty constructor.

Creates an empty truth table by calling the empty constructor of the inner truth table type.

inline quaternary_truth_table(TT const &onset, TT const &offset)¶

Construct from onset and offset.

Meanings of the values of (offset, onset) at each bit position: 00 is a don’t-know (x) or not involved in the cube, 01 is a positive literal (1), 10 is a negative literal (0), and 11 is a don’t-care (-), meaning that both 0 and 1 are accepted.

Parameters

onset – Onset truth table.
offset – Offset truth table.

inline quaternary_truth_table(TT const &binary)¶

Construct from a binary truth table.

Initialize the truth table as equivalent to a binary truth table. (All bits are cared and known, being either 0 or 1, without any - or x.)

Parameters: binary – Binary truth table.

inline quaternary_truth_table<TT> construct() const¶: Constructs a new quaternary_truth_table instance of the same size.

template<typename = std::enable_if_t<is_complete_truth_table<TT>::value>> 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_onset() noexcept¶: Begin iterator to onset.

inline auto end_onset() noexcept¶: End iterator to onset.

inline auto begin_onset() const noexcept¶: Begin iterator to onset.

inline auto end_onset() const noexcept¶: End iterator to onset.

inline auto rbegin_onset() noexcept¶: Reverse begin iterator to onset.

inline auto rend_onset() noexcept¶: Reverse end iterator to onset.

inline auto cbegin_onset() const noexcept¶: Constant begin iterator to onset.

inline auto cend_onset() const noexcept¶: Constant end iterator to onset.

inline auto crbegin_onset() const noexcept¶: Constant reverse begin iterator to onset.

inline auto crend_onset() const noexcept¶: Constant teverse end iterator to onset.

inline auto begin_offset() noexcept¶: Begin iterator to offset.

inline auto end_offset() noexcept¶: End iterator to offset.

inline auto begin_offset() const noexcept¶: Begin iterator to offset.

inline auto end_offset() const noexcept¶: End iterator to offset.

inline auto rbegin_offset() noexcept¶: Reverse begin iterator to offset.

inline auto rend_offset() noexcept¶: Reverse end iterator to offset.

inline auto cbegin_offset() const noexcept¶: Constant begin iterator to offset.

inline auto cend_offset() const noexcept¶: Constant end iterator to offset.

inline auto crbegin_offset() const noexcept¶: Constant reverse begin iterator to offset.

inline auto crend_offset() const noexcept¶: Constant teverse end iterator to offset.

template<class TT2> inline quaternary_truth_table<TT> &operator=(const quaternary_truth_table<TT2> &other)¶

Assign other truth table.

This replaces the current truth table with another truth table. The other truth table must also be quaternary, and the inner type of the other truth table must be assignable to the inner type of this truth table.

Parameters: other – Other truth table

template<class TT2> inline quaternary_truth_table<TT> &operator=(TT const &other)¶

Assigned by a binary truth table.

Replaces with a truth table equivalent to a binary truth table. (All bits are cared and known, being either 0 or 1, without any - or x.)

Parameters: other – Binary truth table.

inline void mask_bits() noexcept¶

Masks valid truth table bits.

This operation makes sure to zero out all unused bits.