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 dynamic_truth_table

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

Public Functions

dynamic_truth_table(int 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

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.

dynamic_truth_table construct() const

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

auto num_vars() const

Returns number of variables.

auto num_blocks() const

Returns number of blocks.

auto num_bits() const

Returns number of bits.

auto begin()

Begin iterator to bits.

auto end()

End iterator to bits.

auto begin() const

Begin iterator to bits.

auto end() const

End iterator to bits.

auto rbegin()

Reverse begin iterator to bits.

auto rend()

Reverse end iterator to bits.

auto cbegin() const

Constant begin iterator to bits.

auto cend() const

Constant end iterator to bits.

auto crbegin() const

Constant reverse begin iterator to bits.

auto crend() const

Constant teverse end iterator to bits.

template<class TT, typename = std::enable_if_t<is_truth_table<TT>::value>>
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 is arbitrary. The vector of bits is resized accordingly.

Parameters
  • other: Other truth table

void mask_bits()

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.

struct

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.