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

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 cube

Public Functions

cube()

Constructs the empty cube.

Represents the one-cube

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)

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

int num_literals() const

Returns number of literals.

int difference(const cube &that) const

Returns the difference to another cube.

int distance(const cube &that) const

Returns the distance to another cube.

bool operator==(const cube &that) const

Checks whether two cubes are equivalent.

bool operator!=(const cube &that) const

Checks whether two cubes are not equivalent.

bool operator<(const cube &that) const

Default comparison operator.

cube merge(const cube &that) const

Merges two cubes of distance-1.

void add_literal(uint8_t var_index, bool polarity = true)

Adds literal to cube.

void remove_literal(uint8_t var_index)

Removes literal from cube.

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

Prints a cube.

bool get_bit(uint8_t index) const

Gets bit at index.

bool get_mask(uint8_t index) const

Gets mask at index.

void set_bit(uint8_t index)

Sets bit at index.

void set_mask(uint8_t index)

Sets mask at index.

void clear_bit(uint8_t index)

Clears bit at index.

void clear_mask(uint8_t index)

Clears mask at index.

void flip_bit(uint8_t index)

Flips bit at index.

void flip_mask(uint8_t index)

Flips mask at index.

Public Static Functions

static cube nth_var_cube(uint8_t var_index)

Constructs the elementary cube representing a single variable.

static cube pos_cube(uint8_t k)

Constructs the elementary cube containing the first k positive literals.

static cube neg_cube(uint8_t k)

Constructs the elementary cube containing the first k negative literals.