Ordered Set implementation in Python

__sets.py

import collections
import itertools
from collections import abc
from typing import Any, Dict, Iterable, Iterator, Optional, Tuple

_sentinel = object()


def _merge_in(
    target: Dict[Any, Any],
    iterable: Optional[Iterable[Any]] = None,
    sentinel: Any = _sentinel,
) -> Dict[Any, Any]:
    if iterable is not None:
        for value in iterable:
            target.setdefault(value, sentinel)
    return target


class OrderedSet(abc.Set, abc.Hashable):
    __slots__: list[str] = ["_data"]

    def __init__(self, iterable: Optional[Iterable[Any]] = None) -> None:
        self._data: Dict[Any, Any] = _merge_in(collections.OrderedDict(), iterable)

    def __hash__(self) -> int:
        return hash(tuple(self))

    def __contains__(self, value: Any) -> bool:
        return value in self._data

    def __len__(self) -> int:
        return len(self._data)

    def __iter__(self) -> Iterator[Any]:
        yield from self._data.keys()

    def __setstate__(self, items: Iterable[Any]) -> None:
        self.__init__(iterable=iter(items))

    def __getstate__(self) -> Tuple[Any, ...]:
        return tuple(self)

    def __repr__(self) -> str:
        return f"{type(self).__name__}({list(self)})"

    def copy(self) -> "OrderedSet":
        return self._from_iterable(iter(self))

    def intersection(self, *sets: "OrderedSet") -> "OrderedSet":

        def absorb_it(sets: Tuple["OrderedSet", ...]) -> Iterator[Any]:
            for value in iter(self):
                matches = 0
                for s in sets:
                    if value in s:
                        matches += 1
                    else:
                        break
                if matches == len(sets):
                    yield value

        return self._from_iterable(absorb_it(sets))

    def issuperset(self, other: Iterable[Any]) -> bool:
        return all(value in self for value in other)

    def issubset(self, other: Iterable[Any]) -> bool:
        return all(value in other for value in iter(self))

    def difference(self, *sets: "OrderedSet") -> "OrderedSet":

        def absorb_it(sets: Tuple["OrderedSet", ...]) -> Iterator[Any]:
            for value in iter(self):
                seen = False
                for s in sets:
                    if value in s:
                        seen = True
                        break
                if not seen:
                    yield value

        return self._from_iterable(absorb_it(sets))

    def union(self, *sets: "OrderedSet") -> "OrderedSet":
        return self._from_iterable(itertools.chain(iter(self), *sets))


if __name__ == "__main__":
    ordered_set = OrderedSet([1, 2, 3, 4])
    print("Initial OrderedSet:", ordered_set)
    print("Hash of the OrderedSet:", hash(ordered_set))
    print("Is 3 in the OrderedSet?", 3 in ordered_set)
    print("Length of the OrderedSet:", len(ordered_set))
    print("Iterating over the OrderedSet:")
    for element in ordered_set:
        print(element)
    ordered_set_copy: OrderedSet = ordered_set.copy()
    print("Copy of the OrderedSet:", ordered_set_copy)
    other_set = OrderedSet([3, 4, 5, 6])
    intersection_set: OrderedSet = ordered_set.intersection(other_set)
    print("Intersection with [3, 4, 5, 6]:", intersection_set)
    print("Is the OrderedSet a superset of [1, 2]?", ordered_set.issuperset([1, 2]))
    print("Is the OrderedSet a subset of [1, 2, 3, 4, 5]?",ordered_set.issubset([1, 2, 3, 4, 5]))
    difference_set: OrderedSet = ordered_set.difference(other_set)
    print("Difference with [3, 4, 5, 6]:", difference_set)
    union_set: OrderedSet = ordered_set.union(other_set)
    print("Union with [3, 4, 5, 6]:", union_set)
    state: Tuple[Any, ...] = ordered_set.__getstate__()
    print("OrderedSet state:", state)
    new_ordered_set = OrderedSet()
    new_ordered_set.__setstate__(state)
    print("New OrderedSet from state:", new_ordered_set)
    print("String representation of the OrderedSet:", repr(ordered_set))

_sets.py

import collections
import itertools
from collections import abc
from typing import Any, Dict, Iterable, Iterator, Optional, Tuple

_sentinel = object()


def _merge_in(
    target: Dict[Any, Any],
    iterable: Optional[Iterable[Any]] = None,
    sentinel: Any = _sentinel,
) -> Dict[Any, Any]:
    """Merges iterable into the target and returns the target.

    Args:
        target (Dict[Any, Any]): The target dictionary to merge into.
        iterable (Optional[Iterable[Any]], optional): The iterable to merge into the target. Defaults to None.
        sentinel (Any, optional): The sentinel value to use when merging. Defaults to _sentinel.

    Returns:
        Dict[Any, Any]: The merged target dictionary.
    """
    if iterable is not None:
        for value in iterable:
            target.setdefault(value, sentinel)
    return target


class OrderedSet(abc.Set, abc.Hashable):
    """
    An ordered set implementation that maintains the order of elements
    while providing set-like functionality.

    Args:
        iterable (Optional[Iterable[Any]]): An optional iterable to initialize the set.

    Attributes:
        _data (Dict[Any, Any]): The internal data structure that stores the elements.

    """

    __slots__: list[str] = ["_data"]

    def __init__(self, iterable: Optional[Iterable[Any]] = None) -> None:
        """
        Args:
            iterable (Optional[Iterable[Any]]): An iterable object to initialize the set with. Defaults to None.
        """
        self._data: Dict[Any, Any] = _merge_in(collections.OrderedDict(), iterable)

    def __hash__(self) -> int:
        """
        Calculate the hash value of the object.

        Returns:
            int: The hash value of the object.
        """
        return hash(tuple(self))

    def __contains__(self, value: Any) -> bool:
        """
        Check if the set contains a specific value.

        Args:
            value (Any): The value to check for.

        Returns:
            bool: True if the set contains the value, False otherwise.
        """
        return value in self._data

    def __len__(self) -> int:
        """
        Returns the number of elements in the set.

        Returns:
            int: The number of elements in the set.
        """
        return len(self._data)

    def __iter__(self) -> Iterator[Any]:
        """
        Returns an iterator over the keys in the set.

        Yields:
            Any: The keys in the set.
        """
        yield from self._data.keys()

    def __setstate__(self, items: Iterable[Any]) -> None:
        """
        Reconstructs the object from its serialized state.

        Args:
            items (Iterable[Any]): The items to be used to reconstruct the object.

        Returns:
            None
        """
        self.__init__(iterable=iter(items))

    def __getstate__(self) -> Tuple[Any, ...]:
        """
        Returns a tuple representation of the object's state.

        Returns:
            Tuple[Any, ...]: A tuple containing the object's state.
        """
        return tuple(self)

    def __repr__(self) -> str:
        """
        Returns a string representation of the object.

        The returned string includes the name of the class and a list of elements in the set.

        Returns:
            str: A string representation of the object.
        """
        return f"{type(self).__name__}({list(self)})"

    def copy(self) -> "OrderedSet":
        """
        Return a shallow copy of the OrderedSet.

        Returns:
            A new OrderedSet object that is a shallow copy of the original OrderedSet.
        """
        return self._from_iterable(iter(self))

    def intersection(self, *sets: "OrderedSet") -> "OrderedSet":
        """Return the intersection of two or more sets as a new set.

        Args:
            *sets: Two or more sets to find the intersection of.

        Returns:
            OrderedSet: A new set containing elements that are common to all of the sets.
        """

        def absorb_it(sets: Tuple["OrderedSet", ...]) -> Iterator[Any]:
            """
            Generator function that yields values from the current set that are present in all the given sets.

            Args:
                sets (Tuple[OrderedSet, ...]): A tuple of sets to compare the values with.

            Yields:
                Any: The values from the current set that are present in all the given sets.
            """
            for value in iter(self):
                matches = 0
                for s in sets:
                    if value in s:
                        matches += 1
                    else:
                        break
                if matches == len(sets):
                    yield value

        return self._from_iterable(absorb_it(sets))

    def issuperset(self, other: Iterable[Any]) -> bool:
        """
        Check whether this set is a superset of another iterable.

        Args:
            other (Iterable[Any]): The iterable to compare against.

        Returns:
            bool: True if this set is a superset of the other iterable, False otherwise.
        """
        return all(value in self for value in other)

    def issubset(self, other: Iterable[Any]) -> bool:
        """
        Check whether this set is a subset of another iterable.

        Args:
            other (Iterable[Any]): The iterable to compare against.

        Returns:
            bool: True if this set is a subset of the other iterable, False otherwise.
        """
        return all(value in other for value in iter(self))

    def difference(self, *sets: "OrderedSet") -> "OrderedSet":
        """
        Return a new OrderedSet with elements that are in this set but not
        in any of the input sets.

        Args:
            *sets (OrderedSet): One or more OrderedSet instances to compute
            the difference with.

        Returns:
            OrderedSet: A new OrderedSet containing elements that are in this
            set but not in any of the input sets.
        """

        def absorb_it(sets: Tuple["OrderedSet", ...]) -> Iterator[Any]:
            """
            Generate an iterator yielding elements from the input set that are
            not present in any of the provided sets.

            Args:
                sets (Tuple[OrderedSet, ...]): A tuple of OrderedSet instances
                to check for element presence.

            Yields:
                Iterator[Any]: An iterator yielding elements from the input set
                that are not present in any of the provided sets.
            """

            for value in iter(self):
                seen = False
                for s in sets:
                    if value in s:
                        seen = True
                        break
                if not seen:
                    yield value

        return self._from_iterable(absorb_it(sets))

    def union(self, *sets: "OrderedSet") -> "OrderedSet":
        return self._from_iterable(itertools.chain(iter(self), *sets))


if __name__ == "__main__":
    # fmt: off
    ordered_set = OrderedSet([1, 2, 3, 4])
    print("Initial OrderedSet:", ordered_set)
    print("Hash of the OrderedSet:", hash(ordered_set))
    print("Is 3 in the OrderedSet?", 3 in ordered_set)
    print("Length of the OrderedSet:", len(ordered_set))
    print("Iterating over the OrderedSet:")
    for element in ordered_set:
        print(element)
    ordered_set_copy: OrderedSet = ordered_set.copy()
    print("Copy of the OrderedSet:", ordered_set_copy)
    other_set = OrderedSet([3, 4, 5, 6])
    intersection_set: OrderedSet = ordered_set.intersection(other_set)
    print("Intersection with [3, 4, 5, 6]:", intersection_set)
    print("Is the OrderedSet a superset of [1, 2]?", ordered_set.issuperset([1, 2]))
    print("Is the OrderedSet a subset of [1, 2, 3, 4, 5]?", ordered_set.issubset([1, 2, 3, 4, 5]))
    difference_set: OrderedSet = ordered_set.difference(other_set)
    print("Difference with [3, 4, 5, 6]:", difference_set)
    union_set: OrderedSet = ordered_set.union(other_set)
    print("Union with [3, 4, 5, 6]:", union_set)
    state: Tuple[Any, ...] = ordered_set.__getstate__()
    print("OrderedSet state:", state)
    new_ordered_set = OrderedSet()
    new_ordered_set.__setstate__(state)
    print("New OrderedSet from state:", new_ordered_set)
    print("String representation of the OrderedSet:", repr(ordered_set))
    # fmt: on

out.txt

Initial OrderedSet: OrderedSet([1, 2, 3, 4])
Hash of the OrderedSet: 590899387183067792
Is 3 in the OrderedSet? True
Length of the OrderedSet: 4
Iterating over the OrderedSet:
1
2
3
4
Copy of the OrderedSet: OrderedSet([1, 2, 3, 4])
Intersection with [3, 4, 5, 6]: OrderedSet([3, 4])
Is the OrderedSet a superset of [1, 2]? True
Is the OrderedSet a subset of [1, 2, 3, 4, 5]? True
Difference with [3, 4, 5, 6]: OrderedSet([1, 2])
Union with [3, 4, 5, 6]: OrderedSet([1, 2, 3, 4, 5, 6])
OrderedSet state: (1, 2, 3, 4)
New OrderedSet from state: OrderedSet([1, 2, 3, 4])
String representation of the OrderedSet: OrderedSet([1, 2, 3, 4])