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;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])
The
FIFOSet
represents sets that keep the FIFO order.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 a
FIFOSet
instance.The initializer can take 0 or 1 argument that should be iterable.
- additem(value: _T, last: bool = True) None
Add value to the set either at the beginning or at the end.
- 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 isFalse
.
- class FIFOSetFactory(*args, **kwds)
The
FIFOSetFactory
class provides a_from_iterable()
method.This method is used by builtin set classes when set operations are executed.
- class IterableSet(*args, **kwds)
The
IterableSet
class implements some basic operations.This allow sub-classes to only implement the
__iter__()
method.- isdisjoint(other)
Return True if two sets have a null intersection.
- class FiniteSubSet(universe: FiniteUniverse[_T], iterable: Optional[Iterable[_T]] = None)
The
FiniteSubSet
class represents subsets of a finite universe.Instances stores membership using a compact array of intervals represented by an array of int. For example, using the
abcdef
universe, theabde
subset will be represented by[0,2,3,5]
meaning:from element
0
(included) to element2
(excluded) of universefrom element
3
(included) to element5
(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(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(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: Optional[Iterable[_T]] = None) None
Initialise a
FiniteSubSet
instance.- Parameters:
universe (
FiniteUniverse[_T]
) – A finite universe.- Keyword Arguments:
iterable (
Iterable[_T]
, optional) – An optional iterable.
- classmethod from_intervals(universe: FiniteUniverse[_T], intervals: Optional[Iterable[Tuple[int, int]]] = None) FiniteSubSet[_T]
Initialise a
FiniteSubSet
instance.- Parameters:
universe (
FiniteUniverse[_T]
) – A finite universe.- Keyword Arguments:
intervals (
Iterable[Tuple[int, int]]
, optional) – An optional iterable of intervals.
New in version 0.5.0.
- intervals() Iterator[Tuple[int, int]]
Get an iterator over the intervals.
- Returns:
An iterator over the intervals.
- Return type:
New in version 0.5.0.
- ranges() Iterator[range]
Get an iterator over the ranges.
- Returns:
An iterator over the ranges.
- Return type:
New in version 0.5.0.
- subsets(strict: Optional[bool] = None) Iterator[FiniteSubSet[_T]]
Get an iterator over the subset of this set (including itself).
- Keyword Arguments:
strict (bool, optional) – Are the subsets strict?
- Returns:
An iterator over the subsets.
- Return type:
New in version 0.5.0.
- supersets(strict: Optional[bool] = None) Iterator[FiniteSubSet[_T]]
Get an iterator over the supersets of this set (including itself).
- Keyword Arguments:
strict (bool, optional) – Are the subsets strict?
- Returns:
An iterator over the supersets.
- Return type:
New in version 0.5.0.
- property universe: FiniteUniverse[_T]
Get the underlying universe.
- Returns:
The underlying universe.
- Return type:
- class FiniteUniverse(iterable: Iterable[_T])
The
FiniteUniverse
class is used to represent finite universe.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(list(singleton) for singleton in universe.singletons()) [['a'], ['b'], ['c']] >>> list(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: Any) int
Get the total number of occurrences of value.
- Parameters:
value (Any) – The value whose count is requested.
- Returns:
1 if the value is in the universe, else 0.
- Return type:
- property empty: FiniteSubSet[_T]
Get the empty subset of this universe.
- Returns:
The empty subset.
- Return type:
New in version 0.5.0.
- index(value: Any, start: Optional[int] = None, stop: Optional[int] = None) int
Get the index of a value.
- Parameters:
value (_T) – The value whose index is requested.
- Keyword Arguments:
- Raises:
TypeError – If the value is not hashable.
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: Optional[int] = None, sup: Optional[int] = None) Iterator[FiniteSubSet[_T]]
Get an iterator over the parts of this universe.
- Keyword Arguments:
- Returns:
An iterator over the selected parts of this universe
- Return type:
New in version 0.5.0.
- singletons() Iterator[FiniteSubSet[_T]]
Get an iterator over the singletons of this universe.
- Returns:
An iterator over the singletons of this universe
- Return type:
New in version 0.5.0.
- property whole: FiniteSubSet[_T]
Get the whole of this universe.
- Returns:
The whole subset.
- Return type:
New in version 0.5.0.
- class IntegerSet(intervals: Optional[Iterable[Tuple[int, int]]] = None)
The
IntegerSet
class represents subsets of a integers.Instances stores membership using a compact array of intervals represented by an array of int. For example, the
{0,1,3,4}
subset will be represented by[0,2,3,5]
meaning:from element
0
(included) to element2
(excluded)from element
3
(included) to element5
(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
New in version 0.5.0.
- __init__(intervals: Optional[Iterable[Tuple[int, int]]] = None)
Initialise an
IntegerSet
instance.- Parameters:
intervals (
Iterable[Tuple[int, int]]
, optional) – An optional iterable of intervals.
- classmethod from_iterable(iterable: Optional[Iterable[int]] = None) IntegerSet
Initialise a
IntegerSet
instance.- Keyword Arguments:
iterable (
Iterable[int]
, optional) – An optional iterable of integers.
- intervals() Iterator[Tuple[int, int]]
Get an iterator over the intervals.
- Returns:
An iterator over the intervals.
- Return type:
New in version 0.5.0.