Sets

The galactic.algebras.set module defines several set classes.

IntegerSet for creating compact sets of integer;
FiniteUniverse for creating finite universe;
FiniteSubSet for creating subset of finite universe;
FIFOSet for creating FIFOSet;
FrozenFIFOSet for creating FrozenFIFOSet;
IterableSet which is a mixin class for iterable sets;
FIFOSetFactory for giving the ability to create sets for set operations.

class FIFOSet(*args: Iterable[_T])

FIFOSet represents sets that keep the FIFO order.

It implements the MutableSet[_T] class.

Examples

>>> from galactic.algebras.set import FIFOSet
>>> a = FIFOSet[int]([3, 5, 1, 2, 6, 2])
>>> list(a)
[3, 5, 1, 2, 6]
>>> list(a | FIFOSet[int]([1, 5, 7 ,8, 9]))
[3, 5, 1, 2, 6, 7, 8, 9]

__init__(*args: Iterable[_T]) → None

Initialise an instance.

The initializer can take 0 or 1 argument that should be iterable.

Parameters:

*args (Iterable[_T]) – An iterable.

Raises:

TypeError – If two or more arguments are given.
TypeError – If the argument is not iterable.

add(value: _T) → None

Add value to the set.

Parameters:: value (_T) – The value to add.

additem(value: _T, last: bool = True) → None

Add value to the set either at the beginning or at the end.

Parameters:

value (_T) – The value to add.
last (bool) – Where to add.

clear() → None: Clear the FIFOSet.

discard(value: _T) → None

Discard value from the set if it is present.

Parameters:: value (_T) – The value to remove.

isdisjoint(other): Return True if two sets have a null intersection.

move_to_end(value: _T, last: bool = True) → None

Move an existing value to either end of a FIFOSet.

The value is moved to the right end if last is True (the default) or to the beginning if last is False.

Parameters:

value (_T) – The value to move
last (bool) – Where to move

pop() → _T

Remove and return the first value of a FIFOSet.

Returns:: The value removed.
Return type:: _T

popitem(last: bool = False) → _T

Remove and return an existing value from either end of a FIFOSet.

Parameters:: last (bool) – Where to remove
Returns:: The value removed.
Return type:: _T
Raises:: KeyError – if the FIFOSet is empty.

remove(value: _T) → None

Remove value from the set if it is present.

Parameters:: value (_T) – The value to remove.

class FrozenFIFOSet(*args: Iterable[_T])

FrozenFIFOSet represents frozen sets that keep the FIFO order.

It implements the AbstractSet[_T] class.

Examples

>>> from galactic.algebras.set import FrozenFIFOSet
>>> a = FrozenFIFOSet[int]([3, 5, 1, 2, 6, 2])
>>> list(a)
[3, 5, 1, 2, 6]
>>> list(a | FrozenFIFOSet[int]([1, 5, 7 ,8, 9]))
[3, 5, 1, 2, 6, 7, 8, 9]

__hash__()

Compute the hash value of a set.

Note that we don’t define __hash__: not all sets are hashable. But if you define a hashable set type, its __hash__ should call this function.

This must be compatible __eq__.

All sets ought to compare equal if they contain the same elements, regardless of how they are implemented, and regardless of the order of the elements; so there’s not much freedom for __eq__ or __hash__. We match the algorithm used by the built-in frozenset type.

__init__(*args: Iterable[_T]) → None

Initialise an instance.

The initializer can take 0 or 1 argument that should be iterable.

Parameters:

*args (Iterable[_T]) – An iterable.

Raises:

TypeError – If two or more arguments are given.
TypeError – If the argument is not iterable.

isdisjoint(other): Return True if two sets have a null intersection.

class FIFOSetFactory

FIFOSetFactory provides a _from_iterable() method.

This method is used by builtin set classes when set operations are executed.

Notes

See https://docs.python.org/fr/3/library/collections.abc.html.

class FrozenFIFOSetFactory

FrozenFIFOSetFactory provides a _from_iterable() method.

This method is used by builtin set classes when set operations are executed.

Notes

See https://docs.python.org/fr/3/library/collections.abc.html.

class IterableSet

IterableSet implements some basic operations.

This allows subclasses to only implement the __iter__() method.

isdisjoint(other): Return True if two sets have a null intersection.

class FiniteSubSet(universe: FiniteUniverse[_T], iterable: Iterable[_T] | None = None)

FiniteSubSet represents subsets of a finite universe.

It implements the AbstractSet[_T] class.

Instances stores membership using a compact array of intervals represented by an array of int. For example, using the abcdef universe, the abde subset will be represented by [0,2,3,5] meaning:

from element 0 (included) to element 2 (excluded) of universe
from element 3 (included) to element 5 (excluded) of universe

Examples

>>> from galactic.algebras.set import FiniteUniverse, FiniteSubSet
>>> from pprint import pprint
>>> universe = FiniteUniverse[str]("abcdef")
>>> set1 = FiniteSubSet[str].from_intervals(universe, [(0, 2), (3, 5)])
>>> list(set1.universe)
['a', 'b', 'c', 'd', 'e', 'f']
>>> len(set1)
4
>>> "a" in set1
True
>>> "f" in set1
False
>>> list(~set1)
['c', 'f']
>>> set2 = FiniteSubSet[str](universe, "bdef")
>>> list(set2.intervals())
[(1, 2), (3, 6)]
>>> list(set1 | set2)
['a', 'b', 'd', 'e', 'f']
>>> list((set1 | set2).intervals())
[(0, 2), (3, 6)]
>>> list(set1 & set2)
['b', 'd', 'e']
>>> list(set1 ^ set2)
['a', 'f']
>>> set1 & set2 <= set1
True
>>> set1 | set2 >= set1
True
>>> set1.isdisjoint(set2)
False
>>> pprint([list(subset) for subset in set1.subsets()])
[[],
 ['a'],
 ['b'],
 ['d'],
 ['e'],
 ['a', 'b'],
 ['a', 'd'],
 ['a', 'e'],
 ['b', 'd'],
 ['b', 'e'],
 ['d', 'e'],
 ['a', 'b', 'd'],
 ['a', 'b', 'e'],
 ['a', 'd', 'e'],
 ['b', 'd', 'e'],
 ['a', 'b', 'd', 'e']]
>>> pprint([list(superset) for superset in set1.supersets(strict=True)])
[['a', 'b', 'c', 'd', 'e'],
 ['a', 'b', 'd', 'e', 'f'],
 ['a', 'b', 'c', 'd', 'e', 'f']]

__init__(universe: FiniteUniverse[_T], iterable: Iterable[_T] | None = None) → None

Initialise a FiniteSubSet instance.

Parameters:

universe (FiniteUniverse[_T]) – A finite universe.
iterable (Iterable[_T], optional) – An optional iterable.

classmethod from_intervals(universe: FiniteUniverse[_T], intervals: Iterable[Tuple[int, int]] | None = None) → FiniteSubSet[_T]

Initialise a FiniteSubSet instance.

Parameters:

universe (FiniteUniverse[_T]) – A finite universe.
intervals (Iterable[Tuple[int, int]], optional) – An optional iterable of intervals.

Returns:

The new set.

Return type:

FiniteSubSet[_T]

Raises:

ValueError – If a mark is outside of the universe.

intervals() → Iterator[Tuple[int, int]]

Get an iterator over the intervals.

Returns:: An iterator over the intervals.
Return type:: Iterator[Tuple[int, int]]

isdisjoint(other: Iterable[object]) → bool

Get the disjointness with another set.

Parameters:: other (Iterable[object]) – An iterable of values.
Returns:: True if the set has no elements in common with the other. Sets are disjoint if and only if their intersection is the empty set.
Return type:: bool

ranges() → Iterator[range]

Get an iterator over the ranges.

Returns:: An iterator over the ranges.
Return type:: Iterator[range]

subsets(strict: bool | None = None) → Iterator[FiniteSubSet[_T]]

Get an iterator over the subset of this set (including itself).

Parameters:: strict (bool, optional) – Are the subsets strict?
Returns:: An iterator over the subsets.
Return type:: Iterator[FiniteSubSet[_T]]

supersets(strict: bool | None = None) → Iterator[FiniteSubSet[_T]]

Get an iterator over the supersets of this set (including itself).

Parameters:: strict (bool, optional) – Are the subsets strict?
Returns:: An iterator over the supersets.
Return type:: Iterator[FiniteSubSet[_T]]

property universe: FiniteUniverse[_T]

Get the underlying universe.

Returns:: The underlying universe.
Return type:: FiniteUniverse[T]

class FiniteUniverse(iterable: Iterable[_T])

FiniteUniverse is used to represent finite universe.

It implements the AbstractSet[_T] and the Sequence[_T] classes.

Examples

>>> from galactic.algebras.set import FiniteUniverse
>>> universe = FiniteUniverse[str]("abc")
>>> list(universe)
['a', 'b', 'c']
>>> list(reversed(universe))
['c', 'b', 'a']
>>> universe.index('c')
2
>>> universe.count('c')
1
>>> universe.count('g')
0
>>> list(universe.whole)
['a', 'b', 'c']
>>> [list(singleton) for singleton in universe.singletons()]
[['a'], ['b'], ['c']]
>>> [list(subset) for subset in universe.parts()]
[[], ['a'], ['b'], ['c'], ['a', 'b'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']]

__init__(iterable: Iterable[_T]) → None

Initialise a FiniteUniverse instance.

Parameters:: iterable (Iterable[_T]) – An iterable of hashable values.

count(value: object) → int

Get the total number of occurrences of value.

Parameters:: value (object) – The value whose count is requested.
Returns:: 1 if the value is in the universe, else 0.
Return type:: int

property empty: FiniteSubSet[_T]

Get the empty subset of this universe.

Returns:: The empty subset.
Return type:: FiniteSubSet[_T]

index(value: _T, start: int | None = None, stop: int | None = None) → int

Get the index of a value.

Parameters:

value (_T) – The value whose index is requested.
start (int, optional) – Where to start.
stop (int, optional) – Where to stop.

Returns:

The index requested.

Return type:

int

Raises:

ValueError – If the value is not in the universe or not found in the interval.

isdisjoint(other): Return True if two sets have a null intersection.

parts(inf: int | None = None, sup: int | None = None) → Iterator[FiniteSubSet[_T]]

Get an iterator over the parts of this universe.

Parameters:

inf (int, optional) – The lower cardinality of the produced parts.
sup (int, optional) – The upper cardinality of the produced parts.

Returns:

An iterator over the selected parts of this universe

Return type:

Iterator[FiniteSubSet[_T]]

singletons() → Iterator[FiniteSubSet[_T]]

Get an iterator over the singletons of this universe.

Returns:: An iterator over the singletons of this universe
Return type:: Iterator[FiniteSubSet[_T]]

property whole: FiniteSubSet[_T]

Get the whole of this universe.

Returns:: The whole subset.
Return type:: FiniteSubSet[_T]

class IntegerSet(intervals: Iterable[Tuple[int, int]] | None = None)

IntegerSet represents subsets of set of integers.

It implements the AbstractSet[int] class.

Instances store membership using a compact array of intervals represented by an array of int. It uses inversion lists as inner data structures.

For example, the {0,1,3,4} subset will be represented by [0,2,3,5] meaning:

from element 0 (included) to element 2 (excluded)
from element 3 (included) to element 5 (excluded)

Examples

>>> from galactic.algebras.set import IntegerSet
>>> set1 = IntegerSet([(0, 2), (3, 5)])
>>> list(set1)
[0, 1, 3, 4]
>>> len(set1)
4
>>> 0 in set1
True
>>> 5 in set1
False
>>> set2 = IntegerSet([(1, 2), (3, 6)])
>>> list(set2)
[1, 3, 4, 5]
>>> list(set1 | set2)
[0, 1, 3, 4, 5]
>>> list(set1 & set2)
[1, 3, 4]
>>> list(set1 ^ set2)
[0, 5]
>>> set1 & set2 <= set1
True
>>> set1 | set2 >= set1
True
>>> set1.isdisjoint(set2)
False

__init__(intervals: Iterable[Tuple[int, int]] | None = None) → None

Initialise an IntegerSet instance.

Parameters:: intervals (Iterable[Tuple[int, int]], optional) – An optional iterable of intervals.
Raises:: ValueError – If the intervals are not sorted or if an interval is empty.

classmethod from_iterable(iterable: Iterable[int] | None = None) → Self

Initialise a IntegerSet instance.

Parameters:: iterable (Iterable[int], optional) – An optional iterable of integers.
Returns:: A new set.
Return type:: Self

intervals() → Iterator[Tuple[int, int]]

Get an iterator over the intervals.

Returns:: An iterator over the intervals.
Return type:: Iterator[Tuple[int, int]]

isdisjoint(other: Iterable[object]) → bool

Get the disjointness with another set.

Parameters:: other (Iterable[object]) – An iterable of values.
Returns:: True if the set has no elements in common with the other. Sets are disjoint if and only if their intersection is the empty set.
Return type:: bool

ranges() → Iterator[range]

Get an iterator over the ranges.

Returns:: An iterator over the ranges.
Return type:: Iterator[range]