roaringrel

Implementation of integer relations based on roaring bitmaps.

Entry

Type alias for an entry in a relation.

Rel

class Rel(shape, data=None)[source]

Bases: object

A low-level mutable data structure to store a finite relation between finite sets:

\[R \subseteq X_1 \times ... \times X_n\]

It presumes that the component sets \(X_1,...,X_n\) are finite zero-based contiguous integer ranges, in the form \(X_j = \lbrace 0,...,s_j-1 \rbrace\). The tuple \((s_1,...,s_n)\) of component set sizes is referred to as the shape of the relation \(R\), while the tuples \((x_1,...x_n) \in R\) are referred to as its entries.

Relations are implemented using 64-bit roaring bitmaps to store the underlying set of entries.

See Rel.__new__ for the constructor.

__and__(other)[source]

Returns the intersection of this relation and a given relation of same shape.

Raises:: ValueError – if the two relations have different shapes.
Parameters:: other (Rel)
Return type:: Rel

__contains__(entry)[source]

Whether the given entry is in the relation.

Parameters:: entry (Entry)
Return type:: bool

__eq__(other)[source]

Equality comparison between relations, as sets of entries.

Parameters:: other (typing.Any)
Return type:: bool

__iand__(other)[source]

Inplace version of Rel.__and__, mutating the lhs relation.

Parameters:: other (Rel)
Return type:: typing.Self

__invert__()[source]

Returns the relation’s complement within the set of all possible entries for the relation’s own shape.

Return type:: Rel

__ior__(other)[source]

Inplace version of Rel.__or__, mutating the lhs relation.

Parameters:: other (Rel)
Return type:: typing.Self

__isub__(other)[source]

Inplace version of Rel.__sub__, mutating the lhs relation.

Parameters:: other (Rel)
Return type:: typing.Self

__ixor__(other)[source]

Inplace version of Rel.__xor__, mutating the lhs relation.

Parameters:: other (Rel)
Return type:: typing.Self

__le__(other)[source]

Containment comparison between relations, as sets of entries.

Parameters:: other (typing.Any)
Return type:: bool

__lt__(other)[source]

Strict containment comparison between relations, as sets of entries.

Parameters:: other (typing.Any)
Return type:: bool

static __new__(cls, shape, data=None)[source]

Creates a relation with the given shape and initial data:

if data is a Rel instance, performs a copy of that relation;
if data is an iterable of entries, creates a relation with those entries;
if data is a BitMap64, creates a relation using the bitmap for the underlying set of entries;
if data is None (default), an empty relation is created.

Parameters:

shape (collections.abc.Iterable[int])
data (pyroaring.BitMap64 | collections.abc.Iterable[Entry] | None)

Return type:

typing.Self

__or__(other)[source]

Returns the union of this relation and a given relation of same shape.

Raises:: ValueError – if the two relations have different shapes.
Parameters:: other (Rel)
Return type:: Rel

__sub__(other)[source]

Returns the difference of this relation and a given relation of same shape.

Raises:: ValueError – if the two relations have different shapes.
Parameters:: other (Rel)
Return type:: Rel

__xor__(other)[source]

Returns the symmetric diff of this relation and a given relation of same shape.

Raises:: ValueError – if the two relations have different shapes.
Parameters:: other (Rel)
Return type:: Rel

add(entry)[source]

Adds the given entry to the relation.

Parameters:: entry (Entry)

copy()[source]

Returns a copy of the relation (independently mutable).

Return type:: Rel

difference_update(*entry_sets)[source]

Removes all entries from all given iterables from the relation.

Parameters:: entry_sets (collections.abc.Iterable[Entry]; variadic positional)

flip(entry)[source]

Removes the entry from the relation if it is in the relation; otherwise, adds the entry to the relation.

Parameters:: entry (Entry)

static iter_entries(shape)[source]

Iterates over all possible entries for the given shape.

Parameters:: shape (collections.abc.Iterable[int])
Return type:: collections.abc.Iterator[Entry]

remove(entry)[source]

Removes the given entry from the relation.

Raises:: KeyError – if the tuple is not in the relation.
Parameters:: entry (Entry)

property shape

The shape of the relation, i.e. the tuple of sizes for its component sets.

Return type:: tuple[int, …]

symmetric_difference_update(*entry_sets)[source]

Flips all entries from all given iterables within the relation. That is, removes from the relation all given entries which are in the relation, and adds to the relation all given entries which are not in the relation.

Note that the given entries are considered without repetition, so that multiple occurrences of the same entry in the given iterables don’t result in multiple flips.

Parameters:: entry_sets (collections.abc.Iterable[Entry]; variadic positional)

update(*entry_sets)[source]

Adds all entries from all given iterables to the relation.

Parameters:: entry_sets (collections.abc.Iterable[Entry]; variadic positional)

validate_entry(entry)[source]

Validates the given entry against the shape of the relation.

Raises:: ValueError – if the entry is not valid for the shape.
Parameters:: entry (Entry)

Shape

Type alias for the shape of a relation.