Cube data structure

The header <kitty/cube.hpp> implements a cube data structure to represent a cube with up to 32 literals. This data structure is used by algorithms that find 2-level representations for truth tables, e.g., isop and esop_from_optimum_pkrm.

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

Function

Description

cube()

Constructs the empty cube

cube(bits, mask)

Constructs a cube from bits and mask

cube(str)

Constructs a cube from a string

num_literals()

Returns number of literals

difference(that)

Returns the difference to another cube

distance(that)

Returns the distance to another cube

operator==(that)

Checks whether two cubes are equivalent

operator!=(that)

Checks whether two cubes are not equivalent

operator<(that)

Default comparison operator

operator~()

Returns the negated cube

merge(that)

Merges two cubes of distance-1

add_literal(var_index, polarity)

Add literal to cube

remove_literal(var_index)

Removes literal from cube

nth_var_cube(var_index)

Constructs the elementary cube representing a single variable

pos_cube(k)

Constructs the elementary cube containing the first k positive literals

neg_cube(k)

Constructs the elementary cube containing the first k negative literals

print(length, os)

Prints a cube

get_bit(index)

Gets bit at index

get_mask(index)

Gets mask at index

set_bit(index)

Sets bit at index

set_mask(index)

Sets mask at index

clear_bit(index)

Clears bit at index

clear_mask(index)

Clears mask at index

flip_bit(index)

Flips bit at index

flip_mask(index)

Flips mask at index

Function
Description

print_cubes(cubes, length, os)

Prints all cubes in a vector.

You can use kitty::hash<cube> to hash cubes, e.g., in a hash map or set.

class kitty::cube

Public Functions

inline cube()

Constructs the empty cube.

Represents the one-cube

inline cube(uint32_t bits, uint32_t mask)

Constructs a cube from bits and mask.

For a valid cube and to be consistent in the ternary values, we assume that whenever a bit in the care bitmask is set to 0, also the polarity bitmask must be 0.

Parameters
  • bits – Polarity bitmask of variables (0: negative, 1: positive)

  • mask – Care bitmask of variables (1: part of cube, 0: not part of cube)

inline cube(const std::string &str)

Constructs a cube from a string.

Each character corresponds to one literal in the cube. Only up to first 32 characters of the string will be considered, since this data structure cannot represent cubes with more than 32 literals. A ‘1’ in the string corresponds to a postive literal, a ‘0’ corresponds to a negative literal. All other characters represent don’t care, but it is customary to use ‘-‘.

Parameters

str – String representing a cube

inline int num_literals() const

Returns number of literals.

inline int difference(const cube &that) const

Returns the difference to another cube.

inline int distance(const cube &that) const

Returns the distance to another cube.

inline bool operator==(const cube &that) const

Checks whether two cubes are equivalent.

inline bool operator!=(const cube &that) const

Checks whether two cubes are not equivalent.

inline bool operator<(const cube &that) const

Default comparison operator.

inline cube operator~() const

Returns the negated cube.

inline cube merge(const cube &that) const

Merges two cubes of distance-1.

inline void add_literal(uint8_t var_index, bool polarity = true)

Adds literal to cube.

inline void remove_literal(uint8_t var_index)

Removes literal from cube.

inline void print(unsigned length = 32u, std::ostream &os = std::cout) const

Prints a cube.

inline bool get_bit(uint8_t index) const

Gets bit at index.

inline bool get_mask(uint8_t index) const

Gets mask at index.

inline void set_bit(uint8_t index)

Sets bit at index.

inline void set_mask(uint8_t index)

Sets mask at index.

inline void clear_bit(uint8_t index)

Clears bit at index.

inline void clear_mask(uint8_t index)

Clears mask at index.

inline void flip_bit(uint8_t index)

Flips bit at index.

inline void flip_mask(uint8_t index)

Flips mask at index.

template<class Fn>
inline void foreach_minterm(uint8_t length, Fn &&fn) const

Iterates over all minterms in the cube.

The callback function takes a cube as input, which is actually a minterm (i.e., all variables are set), and returns a boolean. The loop terminates when the callback returns false.

Parameters
  • length – Number of variables in the cube

  • fn – Callback function on each minterm

Public Static Functions

static inline cube nth_var_cube(uint8_t var_index)

Constructs the elementary cube representing a single variable.

static inline cube pos_cube(uint8_t k)

Constructs the elementary cube containing the first k positive literals.

static inline cube neg_cube(uint8_t k)

Constructs the elementary cube containing the first k negative literals.