galactic.algebras.set.core#
Defines core set data structures for universes and FIFO sets.
Classes
FIFO Sets:
FrozenFIFOSetfor creating immutable FIFO setsFIFOSetfor creating mutable FIFO sets
Universes and Subsets:
IndexRangefor representing universes of integersUniversefor creating universes of hashable valuesSubSetfor creating subsets of universes
- class FrozenFIFOSet(*elements)#
Bases:
Set[_T]Represents an immutable set that preserves FIFO order.
Initialize an instance with zero or one argument, which should be iterable.
Examples
>>> from galactic.algebras.set.core import FrozenFIFOSet >>> a = FrozenFIFOSet[int]([3, 5, 1, 2, 6, 2]) >>> a <galactic.algebras.set.core.FrozenFIFOSet object at 0x...> >>> list(a) [3, 5, 1, 2, 6] >>> list(a | FrozenFIFOSet[int]([1, 5, 7 ,8, 9])) [3, 5, 1, 2, 6, 7, 8, 9]
Notes
This class is a frozen version of
FIFOSet. It is immutable and does not allow any modifications after creation. It is useful for creating immutable sets that maintain the order of insertion, which can be used in contexts where immutability is required, such as in functional programming paradigms or when using sets as keys in dictionaries.It is based on
collections.OrderedDictto maintain the order of insertion while providing set-like behavior.The class implements the
collections.abc.Setinterface, allowing it to be used as a set in Python. It provides methods for checking membership, iterating over the elements, and performing set operations like union, intersection, difference, and symmetric difference.
- __hash__()#
Compute the hash value of the set.
- Returns:
The hash value of the set
- Return type:
Notes
The hash value is computed based on the elements of the set and is cached for efficiency.
- __copy__()#
Create a shallow copy of this set.
- Returns:
A shallow copy of this set
- Return type:
Self
- copy()#
Compute a copy of this set.
- Returns:
A copy of this set
- Return type:
Self
- __contains__(elem)#
Check if an element belongs to the set.
- __iter__()#
Iterate over the elements in the set.
- __len__()#
Get the number of elements in the set.
- Returns:
The number of elements in the set
- Return type:
- property head: _T#
Get the first element of the set.
- Returns:
The first element
- Return type:
_T
- Raises:
KeyError – If the set is empty
- property tail: _T#
Get the last element of the set.
- Returns:
The last element
- Return type:
_T
- Raises:
KeyError – If the set is empty
- __reversed__()#
Iterate over the elements in the set in reverse order.
- isdisjoint(other)#
Check if the set has no elements in common with another iterable.
- issubset(other)#
Check if the set is a subset of another iterable.
- issuperset(other)#
Check if the set is a superset of another iterable.
- union(*others)#
Compute the union of the set and the provided iterables.
- intersection(*others)#
Compute the intersection of the set and the provided iterables.
- difference(*others)#
Compute the difference between the set and the provided iterables.
- class FIFOSet(*elements)#
Bases:
FrozenFIFOSet[_T],MutableSet[_T]Represents a mutable set that preserves FIFO order.
Examples
>>> from galactic.algebras.set.core import FIFOSet >>> a = FIFOSet[int]([3, 5, 1, 2, 6, 2]) >>> a <galactic.algebras.set.core.FIFOSet object at 0x...> >>> list(a) [3, 5, 1, 2, 6] >>> list(a | FIFOSet[int]([1, 5, 7 ,8, 9])) [3, 5, 1, 2, 6, 7, 8, 9]
Notes
This class is a mutable version of
FrozenFIFOSet. It allows adding, removing, and modifying elements while preserving the order of insertion.It is based on
collections.OrderedDictto maintain the order of insertion while providing set-like behavior.The class implements the
collections.abc.MutableSetinterface, allowing it to be used as a mutable set in Python. It provides methods for adding, removing, and modifying elements, as well as performing set operations like union, intersection, difference, and symmetric difference.It also provides methods for moving elements to the beginning or end of the set, allowing for flexible manipulation of the order of elements.
It is useful for scenarios where the order of insertion matters, such as in queues or ordered sets, while still providing the functionality of a set.
It is particularly useful in applications where the order of elements needs to be preserved, such as in task scheduling, event handling, or maintaining a history of actions.
It is also useful in scenarios where elements need to be added or removed frequently while maintaining the order of insertion, such as in caching mechanisms or maintaining a list of recently used items.
- add(elem)#
Add an element to the set.
- remove(elem)#
Remove an element from the set if it exists.
- discard(elem)#
Discard an element from the set.
- pop()#
Remove and return the first element from the set.
- Returns:
The removed element
- Return type:
TypeVar(_T)
- update(*others)#
Update a set with the union of itself and others.
- intersection_update(*others)#
Update a set with the intersection of itself and others.
- difference_update(*others)#
Update a set with the difference of itself and others.
- symmetric_difference_update(other)#
Update a set with the symmetric difference of itself and the other.
- move_to_end(elem, last=True)#
Move an existing element to the beginning or end of the set.
- additem(elem, last=True)#
Add an element to the set at the beginning or end.
- class IndexRange(length=0)#
-
Represents a continuous universe of integers starting at 0.
- Parameters:
length (
int, default:0) – The length of the universe
Examples
>>> from galactic.algebras.set.core import IndexRange >>> universe = IndexRange(10) >>> universe <galactic.algebras.set.core.IndexRange object at 0x...> >>> list(universe) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] >>> list(reversed(universe)) [9, 8, 7, 6, 5, 4, 3, 2, 1, 0] >>> universe.index(2) 2 >>> universe.count(2) 1 >>> universe.count(10) 0
Notes
The IndexRange class represents a universe of integers starting from 0 up to a specified length.
It supports basic collection operations like containment, length, and iteration.
The universe can be indexed using integers or slices, and it raises an IndexError if an index is out of range.
The index method returns the index of an element, and the count method returns the number of occurrences of an element in the universe.
Hint
The IndexRange class is useful for representing sets of integers starting from 0, allowing for efficient membership testing and set operations.
- __hash__()#
Get the hash of the universe.
- Returns:
The hash of the universe
- Return type:
Notes
The hash is computed based on the length of the universe.
- __contains__(elem)#
Test if an element is in the universe.
- __iter__()#
Get an iterator over the universe.
- __reversed__()#
Get a reversed iterator over the universe.
- __getitem__(index)#
- Overloads:
self, index (int) → int
self, index (slice) → Sequence[int]
Get an element or a slice from the universe.
- index(elem, start=None, stop=None)#
Get the index of an element.
- Parameters:
- Returns:
The index requested
- Return type:
- Raises:
ValueError – If the element is not in the universe or not found in the interval
- class Universe(*elements)#
Bases:
Sequence[_T]Represents a universe of elements.
Examples
>>> from galactic.algebras.set.core import Universe >>> universe = Universe[str]("abc") >>> universe <galactic.algebras.set.core.Universe object at 0x...> >>> list(universe) ['a', 'b', 'c'] >>> list(reversed(universe)) ['c', 'b', 'a'] >>> universe.index('c') 2 >>> universe.count('c') 1 >>> universe.count('g') 0
Notes
The universe is a sequence of elements that can be indexed and iterated over.
The elements are stored in a tuple, and an index is maintained for fast lookups.
The universe is immutable after creation, and its elements are unique.
The universe can be used to create subsets using the SubSet class.
The universe supports basic collection operations like containment, length, and iteration.
Hint
The Universe class is useful for representing a set of elements that can be indexed and iterated over, allowing for efficient membership testing and set operations.
- __hash__()#
Get the hash of the universe.
- Returns:
The hash of the universe
- Return type:
Notes
The hash is computed based on the elements of the universe. It is cached after the first computation for efficiency.
- __contains__(elem)#
Test if an element is in the universe.
- __iter__()#
Get an iterator over the universe.
- __reversed__()#
Get a reversed iterator over the universe.
- __getitem__(index)#
- Overloads:
self, index (int) → _T
self, index (slice) → Sequence[_T]
Get an element or a slice from the universe.
- index(elem, start=None, stop=None)#
Get the index of an element.
- Parameters:
- Returns:
The index requested
- Return type:
- Raises:
ValueError – If the element is not in the universe or not found in the interval
- class SubSet(universe, *elements, bitmap=None)#
Bases:
Generic[_T]Represents a subset of a universe.
Membership is stored using a compact bitmap.
- Parameters:
Examples
>>> from galactic.algebras.set.core import Universe, SubSet >>> from pprint import pprint >>> universe = Universe[str]("abcdef") >>> universe <galactic.algebras.set.core.Universe object at 0x...> >>> set1 = SubSet[str](universe, "abde") >>> set1 <galactic.algebras.set.core.SubSet object at 0x...> >>> 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 = SubSet[str](universe, "bdef") >>> set2 <galactic.algebras.set.core.SubSet object at 0x...> >>> list(set2.bitmap) [1, 3, 4, 5] >>> list(set1 | set2) ['a', 'b', 'd', 'e', 'f'] >>> list((set1 | set2).bitmap) [0, 1, 3, 4, 5] >>> 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']]
Notes
The SubSet class represents a subset of a universe.
It uses a bitmap to efficiently store membership information.
The universe is a sequence of elements, and the subset can be created from elements or an existing bitmap.
The subset supports basic set operations like union, intersection, difference, and symmetric difference.
It also supports set comparison operations like subset, superset, and disjointness.
The subset can be iterated over, and it provides methods to generate all subsets and supersets.
The SubSet class is generic and can be used with any type of elements.
The universe must be a sequence, and the elements must be present in the universe.
Hint
The SubSet class is useful for representing sets of elements from a larger universe, allowing for efficient membership testing and set operations.
- __hash__()#
Get the hash of the subset.
- Returns:
The hash of the subset
- Return type:
Notes
The hash is computed based on the universe and the bitmap representation. It is cached after the first computation for efficiency.
- __eq__(other)#
Test for equality between this set and another.
- __contains__(elem)#
Test if an element is in the set.
- __iter__()#
Get an iterator over the set.
- __ne__(other)#
Test for inequality between this set and another.
- __lt__(other)#
Test if the set is less than the other.
- Parameters:
other (
object) – Another subset- Returns:
True if the set is less than the other
- Return type:
- Raises:
ValueError – If the universes of the sets are different
Notes
If other is not an instance of self type, this method returns NotImplemented.
- __le__(other)#
Test if the set is less than or equal to the other.
- Parameters:
other (
object) – Another subset- Returns:
True if the set is less than or equal to the other
- Return type:
- Raises:
ValueError – If the universes of the sets are different
Notes
If other is not an instance of self type, this method returns NotImplemented.
- __gt__(other)#
Test if the set is greater than the other.
- Parameters:
other (
object) – Another subset- Returns:
True if the set is greater than the other
- Return type:
- Raises:
ValueError – If the universes of the sets are different
Notes
If other is not an instance of self type, this method returns NotImplemented.
- __ge__(other)#
Test if the set is greater than or equal to the other.
- Parameters:
other (
Self) – Another subset- Returns:
True if the set is greater than or equal to the other
- Return type:
- Raises:
ValueError – If the universes of the sets are different
Notes
If other is not an instance of self type, this method returns NotImplemented.
- isdisjoint(other)#
Test if the set is disjoint from the other.
- Parameters:
other (
Self) – Another subset- Returns:
True if the set is disjoint from the other
- Return type:
- Raises:
ValueError – If the universes of the sets are different
TypeError – If other is not an instance of self type
- issubset(other)#
Test if the set is a subset of the other.
- Parameters:
other (
Self) – Another subset- Returns:
True if the set is a subset of the other
- Return type:
- Raises:
ValueError – If the universes of the sets are different
TypeError – If other is not an instance of self type
- issuperset(other)#
Test if the set is a superset of the other.
- Parameters:
other (
Self) – Another subset- Returns:
True if the set is a superset of the other.
- Return type:
- Raises:
ValueError – If the universes of the sets are different
TypeError – If other is not an instance of self type
- __or__(other)#
Compute the union of the set and the other.
- Parameters:
other (
object) – Another subset- Returns:
The union of the set and the other
- Return type:
Self
Notes
If other is not an instance of self type, this method returns NotImplemented.
- __and__(other)#
Compute the intersection between the set and the other.
- Parameters:
other (
object) – Another subset- Returns:
The intersection between the set and the other
- Return type:
Self- Raises:
ValueError – If the universes of the sets are different
Notes
If other is not an instance of self type, this method returns NotImplemented.
- __sub__(other)#
Compute the difference between the set and the other.
- Parameters:
other (
object) – Another subset- Returns:
The difference between the set and the other
- Return type:
Self- Raises:
ValueError – If the universes of the sets are different
Notes
If other is not an instance of self type, this method returns NotImplemented.
- __xor__(other)#
Compute the symmetric difference between the set and the other.
- Parameters:
other (
object) – Another subset- Returns:
The symmetric difference between the set and the other
- Return type:
Self- Raises:
ValueError – If the universes of the sets are different
Notes
If other is not an instance of self type, this method returns NotImplemented.
- __invert__()#
Compute the complement of the set.
- Returns:
The complement of the set
- Return type:
Self
- union(*others)#
Compute the union of the set and the others.
- Parameters:
*others (
Self) – A sequence of subsets- Returns:
The union of the set and the others
- Return type:
Self- Raises:
ValueError – If the universes of the sets are different
TypeError – If any other is not an instance of self type
- intersection(*others)#
Compute the intersection between the set and the others.
- Parameters:
*others (
Self) – A sequence of iterable- Returns:
The intersection between the set and the others
- Return type:
Self- Raises:
ValueError – If the universes of the sets are different
TypeError – If any other is not an instance of self type
- difference(*others)#
Compute the difference between the set and the others.
- Parameters:
*others (
Self) – A sequence of iterable- Returns:
The difference between the set and the others
- Return type:
Self- Raises:
ValueError – If the universes of the sets are different
TypeError – If any other is not an instance of self type
- symmetric_difference(other)#
Compute the symmetric difference between the set and the other.
- Parameters:
other (
Self) – An iterable of elements- Returns:
The symmetric difference between the set and the other
- Return type:
Self- Raises:
ValueError – If the universes of the sets are different
TypeError – If any other is not an instance of self type
- subsets(strict=None)#
Get an iterator over the subset of this set (including itself).
- supersets(strict=None)#
Get an iterator over the supersets of this set (including itself).
- property bitmap: AbstractBitMap#
Get the underlying bitmap.
- Returns:
The underlying bitmap
- Return type:
AbstractBitMap