roaringrel

Implementation of integer relations based on roaring bitmaps.

Entry

type Entry = tuple[int, ...]

Type alias for an entry in a relation (see Rel).

Entries passed to the methods of Rel are normalised rather than validated: see Entry normalisation for the exact contract.

Rel

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

Entry normalisation. This class is designed for use in performance-critical code, so entries are normalised rather than validated: no method which takes entries ever rejects them. An entry is converted into the index of its slot as follows:

the element in position \(j\) is reduced modulo the component set size \(s_j\), so that negative elements index from the end of the component set (as is usual in Python) and out-of-range elements wrap around;
if the entry is shorter than the shape, the missing trailing elements are taken to be zero;
if the entry is longer than the shape, the surplus elements are ignored.

Because every integer is reduced into the range of its own component set, this is a total operation: no entry whatsoever can take a relation outside of its own shape, and the invariants of the data structure hold for arbitrary integer input. An out-of-range entry silently addresses a well-defined different entry, it does not corrupt the relation.

Callers which cannot guarantee that their entries are in range should check them with Rel.validate_entry, which exists for exactly this purpose and is never called internally. Validation is therefore entirely opt-in, and code which understands the tradeoff above pays nothing for it.

Equality, ordering and hashing. Relations of different shape are never equal, but they are not ordered either: Rel.__eq__ returns False on a shape mismatch, whereas Rel.__lt__ and Rel.__le__ raise ValueError. This is deliberate. Equality is total, because unrelated objects are simply unequal, while containment between relations of different shape is a question about incomparable domains, which is much more likely to indicate a bug in the caller than a meaningful query.

Relations are mutable, and therefore unhashable: defining Rel.__eq__ without object.__hash__ is what makes them so, by the same convention that applies to set and list. Use frozenset of the entries where a hashable snapshot of a relation is required.

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

The entry is normalised, not validated: see Entry normalisation. An entry which is out of range is therefore not reported as absent, it is taken to be the entry it normalises to.

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

__eq__(other)[source]

Equality comparison between relations, as sets of entries.

Relations of different shape are never equal, but no error is raised: unlike the containment comparisons, equality is total. Note that defining this method makes relations unhashable, as befits a mutable container.

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

__getnewargs__()[source]

Returns the arguments to Rel.__new__ used to unpickle the relation, namely its shape. The entries are restored separately, by Rel.__setstate__.

Return type:: tuple[Shape]

__getstate__()[source]

Returns the state used to pickle the relation, as the serialised form of the underlying bitmap. The shape is not part of the state, because it is already restored by Rel.__getnewargs__.

Return type:: bytes

__iand__(other)[source]

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

Parameters:: other (Rel)
Return type:: 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:: Self

__isub__(other)[source]

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

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

__iter__()[source]

Iterates over all entries in the relation.

Return type:: Iterator[Entry]

__ixor__(other)[source]

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

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

__le__(other)[source]

Containment comparison between relations, as sets of entries.

Unlike Rel.__eq__, this raises on a shape mismatch rather than returning False: see Rel.__lt__.

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

__len__()[source]

Returns the number of entries in the relation.

Return type:: int

__lt__(other)[source]

Strict containment comparison between relations, as sets of entries.

Unlike Rel.__eq__, this raises on a shape mismatch rather than returning False: containment between relations over different domains is much more likely to indicate a bug than a meaningful query.

Raises:: ValueError – if the two relations have different shapes.
Parameters:: other (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.

Entries taken from an iterable are normalised, as described in Entry normalisation. Indices taken from a Rel or a bitmap are validated instead, because they bypass normalisation entirely: this permits a relation to be reinterpreted under any shape large enough to hold its indices, while ruling out indices which would fall outside the new shape.

Raises:

ValueError – if any component set size is not strictly positive.
ValueError – if a given relation or bitmap contains an index which is out of range for the given shape.
NotImplementedError – if the product of the component set sizes is too large to be indexed by a 64-bit bitmap.

Parameters:

shape (Iterable[int])
data (BitMap64 | Iterable[Entry] | None)

Return type:

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

__setstate__(state)[source]

Restores the entries of a relation being unpickled, from the state returned by Rel.__getstate__. The shape and strides have already been set by Rel.__new__, via Rel.__getnewargs__.

Parameters:: state (bytes)
Return type:: None

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

The entry is normalised, not validated: see Entry normalisation.

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

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.

Entries are normalised, not validated: see Entry normalisation.

Parameters:: entry_sets (Iterable[Entry]; variadic positional)
Return type:: None

flip(entry)[source]

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

The entry is normalised, not validated: see Entry normalisation.

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

static iter_entries(shape)[source]

Iterates over all possible entries for the given shape.

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

remove(entry)[source]

Removes the given entry from the relation.

The entry is normalised, not validated: see Entry normalisation.

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

property shape

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

Return type:: Shape

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. Because entries are normalised rather than validated (see Entry normalisation), entries which normalise to the same slot count as repetitions of each other.

Parameters:: entry_sets (Iterable[Entry]; variadic positional)
Return type:: None

update(*entry_sets)[source]

Adds all entries from all given iterables to the relation.

Entries are normalised, not validated: see Entry normalisation.

Parameters:: entry_sets (Iterable[Entry]; variadic positional)
Return type:: None

validate_entry(entry)[source]

Validates the given entry against the shape of the relation.

This method is never called internally: the methods of this class normalise entries instead of validating them, as described in Entry normalisation. It is provided as a convenience for callers which cannot otherwise guarantee that an entry is in range, and which would rather have an error than address a different entry by accident. Validating every entry is significantly more expensive than the operations it guards, so it is left to the caller to decide where that cost is worth paying.

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

Shape

type Shape = tuple[int, ...]: Type alias for the shape of a relation (see Rel).