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 


Standard constructor. 

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

Returns number of variables. 

Returns number of blocks. 

Returns number of bits. 

Begin iterator to bits. 

End iterator to bits. 

Reverse begin iterator to bits. 

Reverse end iterator to bits. 

Constant begin iterator to bits. 

Constant end iterator to bits. 

Constant reverse begin iterator to bits. 

Constant reverse end iterator to bits. 

Assignment operator. 

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 nonvalid bits.

inline explicit dynamic_truth_table(uint32_t num_vars)¶
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 


Standard constructor. 

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

Returns number of variables. 

Returns number of blocks. 

Returns number of bits. 

Begin iterator to bits. 

End iterator to bits. 

Reverse begin iterator to bits. 

Reverse end iterator to bits. 

Constant begin iterator to bits. 

Constant end iterator to bits. 

Constant reverse begin iterator to bits. 

Constant reverse end iterator to bits. 

Assignment operator. 

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 


Standard constructor. 

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

Returns number of blocks. 

Returns number of bits. 

Begin iterator to bits. 

End iterator to bits. 

Reverse begin iterator to bits. 

Reverse end iterator to bits. 

Constant begin iterator to bits. 

Constant end iterator to bits. 

Constant reverse begin iterator to bits. 

Constant reverse end iterator to bits. 

Assignment operator. 

Masks the number of valid truth table bits. 

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

Add a bit to the end of the truth table. 

Add several bits to the end of the truth table. 

Overwrite the value at position from to position to. 

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

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 positionto
. 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

inline explicit partial_truth_table(uint32_t num_bits)¶