two version of R2R are here HEAD master

3 files changed, 1241 insertions, 0 deletions

diff --git a/.venv/lib/python3.12/site-packages/orderly_set/__init__.py b/.venv/lib/python3.12/site-packages/orderly_set/__init__.py
new file mode 100644
index 00000000..24dc27e9
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/orderly_set/__init__.py
@@ -0,0 +1,9 @@
+from orderly_set.sets import OrderedSet, StableSet, StableSetEq, OrderlySet, SortedSet  # NOQA
+
+__all__ = [
+    "OrderedSet",
+    "StableSet",
+    "StableSetEq",
+    "OrderlySet",
+    "SortedSet",
+]
diff --git a/.venv/lib/python3.12/site-packages/orderly_set/py.typed b/.venv/lib/python3.12/site-packages/orderly_set/py.typed
new file mode 100644
index 00000000..e69de29b
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/orderly_set/py.typed
diff --git a/.venv/lib/python3.12/site-packages/orderly_set/sets.py b/.venv/lib/python3.12/site-packages/orderly_set/sets.py
new file mode 100644
index 00000000..899251d7
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/orderly_set/sets.py
@@ -0,0 +1,1232 @@
+import itertools
+import itertools as it
+from typing import (
+    AbstractSet,
+    Any,
+    Dict,
+    Iterable,
+    Iterator,
+    List,
+    MutableSet,
+    Optional,
+    Sequence,
+    Set,
+    TypeVar,
+    Union,
+    overload,
+)
+
+SLICE_ALL = slice(None)
+
+T = TypeVar("T")
+
+# SetLike[T] is either a set of elements of type T, or a sequence, which
+# we will convert to a StableSet or to an OrderedSet by adding its elements in order.
+SetLike = Union[AbstractSet[T], Sequence[T]]
+SetInitializer = Union[AbstractSet[T], Sequence[T], Iterable[T]]
+
+
+def _is_atomic(obj: object) -> bool:
+    """
+    Returns True for objects which are iterable but should not be iterated in
+    the context of indexing a StableSet or an OrderedSet.
+
+    When we index by an iterable, usually that means we're being asked to look
+    up a list of things.
+
+    However, in the case of the .index() method, we shouldn't handle strings
+    and tuples like other iterables. They're not sequences of things to look
+    up, they're the single, atomic thing we're trying to find.
+
+    As an example, oset.index('hello') should give the index of 'hello' in an
+    StableSet of strings. It shouldn't give the indexes of each individual
+    character.
+    """
+    return isinstance(obj, (str, tuple))
+
+
+class StableSet(MutableSet[T], Sequence[T]):
+    """
+    A StableSet is a custom MutableSet that remembers its insertion order.
+    Featuring: Fast O(1) insertion, deletion, iteration and membership testing.
+    But slow O(N) Index Lookup.
+
+    StableSet is meant to be a drop-in replacement for `set` when iteration in insertion order
+    is the only additional requirement over the built-in `set`.
+
+    Equality: StableSet, like `set` and `dict_keys` [dict.keys()], and unlike OrderdSet,
+    disregards the items order when checking equality.
+    Like `set` it may be equal only to other instances of AbstractSet
+    (like `set`, `dict_keys` or StableSet).
+
+    This implementation of StableSet is based on the built-in dict type.
+    In Python 3.6 and later, the built-in dict type is inherently ordered.
+    If you ignore the dictionary values, that also gives you a simple ordered set,
+    with fast O(1) insertion, deletion, iteration and membership testing.
+    However, dict does not provide the list-like random access features of StableSet.
+    So we have to convert it to a list in O(N) to look up the index of an entry
+    or look up an entry by its index.
+
+    Example:
+        >>> StableSet([1, 1, 2, 3, 2])
+        StableSet([1, 2, 3])
+    """
+
+    __slots__ = ("_map", "_is_mutable")
+
+    _map: Dict[T, Any]
+
+    def __init__(self, initial: Optional[SetInitializer[T]] = None):
+        self._map = dict.fromkeys(initial) if initial else {}
+        self._is_mutable = True
+
+    def __len__(self) -> int:
+        """
+        Returns the number of unique elements in the ordered set
+
+        Example:
+            >>> len(StableSet([]))
+            0
+            >>> len(StableSet([1, 2]))
+            2
+        """
+        return self._map.__len__()
+
+    @overload
+    def __getitem__(self, index: slice) -> "StableSet[T]":
+        ...
+
+    @overload
+    def __getitem__(self, index: Sequence[int]) -> List[T]:
+        ...
+
+    @overload
+    def __getitem__(self, index: int) -> T:
+        ...
+
+    # concrete implementation
+    def __getitem__(self, index):
+        """
+        Get the item at a given index.
+
+        If `index` is a slice, you will get back that slice of items, as a
+        new StableSet.
+
+        If `index` is a list or a similar iterable, you'll get a list of
+        items corresponding to those indices. This is similar to NumPy's
+        "fancy indexing". The result is not a StableSet because you may ask
+        for duplicate indices, and the number of elements returned should be
+        the number of elements asked for.
+
+        Example:
+            >>> oset = StableSet([1, 2, 3])
+            >>> oset[1]
+            2
+        """
+        if isinstance(index, int):
+            if index < 0:
+                index = len(self._map) + index
+            try:
+                return next(itertools.islice(self._map.keys(), index, index + 1))
+            except StopIteration:
+                raise IndexError(f"index {index} out of range")
+        elif isinstance(index, slice) and index == SLICE_ALL:
+            return self.copy()
+        items = list(self._map.keys())
+        if isinstance(index, Iterable):
+            return [items[i] for i in index]
+        elif isinstance(index, slice) or hasattr(index, "__index__"):
+            result = items[index]
+            if isinstance(result, list):
+                return self.__class__(result)
+            else:
+                return result
+        else:
+            raise TypeError(f"Don't know how to index a StableSet by {index}")
+
+    # Define the gritty details of how a StableSet is serialized as a pickle.
+    # We leave off type annotations, because the only code that should interact
+    # with this is a generalized tool such as pickle.
+    def __getstate__(self):
+        if len(self) == 0:
+            # In pickle, the state can't be an empty list.
+            # We need to return a truthy value, or else __setstate__ won't be run.
+            #
+            # This could have been done more gracefully by always putting the state
+            # in a tuple, but this way is backwards- and forwards- compatible with
+            # previous versions of StableSet.
+            return (None,)
+        else:
+            return list(self)
+
+    def __setstate__(self, state):
+        if state == (None,):
+            self.__init__([])
+        else:
+            self.__init__(state)
+
+    def __contains__(self, key: Any) -> bool:
+        """
+        Test if the item is in this ordered set.
+
+        Example:
+            >>> 1 in StableSet([1, 3, 2])
+            True
+            >>> 5 in StableSet([1, 3, 2])
+            False
+        """
+        # return key in self._map
+        return self._map.__contains__(key)
+
+    def __iter__(self) -> Iterator[T]:
+        """
+        Example:
+            >>> list(iter(StableSet([1, 2, 3])))
+            [1, 2, 3]
+        """
+        # return iter(self._map.keys())
+        return self._map.keys().__iter__()
+
+    def __reversed__(self) -> Iterator[T]:
+        """
+        Supported from Python >= 3.8
+        Example:
+            >>> list(reversed(StableSet([1, 2, 3])))
+            [3, 2, 1]
+        """
+        return reversed(self._map.keys())
+
+    def __repr__(self) -> str:
+        if not self:
+            return f"{self.__class__.__name__}()"
+        return f"{self.__class__.__name__}({list(self)!r})"
+
+    __str__ = __repr__
+
+    def __and__(self, other: SetLike[T]) -> "StableSet[T]":
+        # the parent implementation of this is backwards
+        return self.intersection(other)
+
+    # sub, or, xor that support ordering
+    # (left hand and right hand - as the operands order does matter)
+    # based on the implementations of the super class (Set(Collection)),
+    # see _collections_abc.py
+    def __sub__(self, other):
+        cls = type(
+            self
+            if isinstance(self, StableSet)
+            else other
+            if isinstance(other, StableSet)
+            else StableSet
+        )
+        if not isinstance(other, Set):
+            if not isinstance(other, Iterable):
+                return NotImplemented
+            other = cls(other)
+        return cls(value for value in self if value not in other)
+
+    def __rsub__(self, other):
+        cls = type(
+            self
+            if isinstance(self, StableSet)
+            else other
+            if isinstance(other, StableSet)
+            else StableSet
+        )
+        if not isinstance(other, Set):
+            if not isinstance(other, Iterable):
+                return NotImplemented
+            other = cls(other)
+        return cls(value for value in other if value not in self)
+
+
+    def __or__(self, other):
+        cls = type(
+            self
+            if isinstance(self, StableSet)
+            else other
+            if isinstance(other, StableSet)
+            else StableSet
+        )
+        if not isinstance(other, Iterable):
+            return NotImplemented
+        chain = (e for s in (self, other) for e in s)
+        return cls(chain)
+
+    def __ror__(self, other):
+        cls = type(
+            self
+            if isinstance(self, StableSet)
+            else other
+            if isinstance(other, StableSet)
+            else StableSet
+        )
+        if not isinstance(other, Iterable):
+            return NotImplemented
+        chain = (e for s in (other, self) for e in s)
+        return cls(chain)
+
+    def __xor__(self, other):
+        if not isinstance(other, Iterable):
+            return NotImplemented
+        return (self - other) | (other - self)
+
+    def __rxor__(self, other):
+        if not isinstance(other, Iterable):
+            return NotImplemented
+        return (other - self) | (self - other)
+
+    def __eq__(self, other):
+        if not isinstance(other, Iterable):
+            return False
+        if len(self._map) != len(other):
+            return False
+        if isinstance(other, StableSet):
+            return self._map == other._map
+        if not isinstance(other, list):
+            other = list(other)
+        return list(self._map.keys()) == other
+
+    def clear(self) -> None:
+        """
+        Remove all items from this StableSet.
+        """
+        if self._is_mutable is False:
+            raise ValueError("This object is not mutable.")
+
+        self._map.clear()
+
+    def copy(self) -> "StableSet[T]":
+        """
+        Return a shallow copy of this object.
+
+        Example:
+            >>> this = StableSet([1, 2, 3])
+            >>> other = this.copy()
+            >>> this == other
+            True
+            >>> this is other
+            False
+        """
+        return self.__class__(self)
+
+    # Technically type-incompatible with MutableSet, because we return an
+    # int instead of nothing. This is also one of the things that makes
+    # StableSet convenient to use.
+    def add(self, key: T) -> int:
+        """
+        Add `key` as an item to this StableSet, then return its index.
+
+        If `key` is already in the StableSet, return the index it already
+        had.
+
+        Example:
+            >>> oset = StableSet()
+            >>> oset.append(3)
+            0
+            >>> print(oset)
+            StableSet([3])
+        """
+        if self._is_mutable is False:
+            raise ValueError("This object is not mutable.")
+
+        self._map[key] = None
+        return len(self._map) - 1
+
+    append = add
+
+    def update(self, sequence: SetLike[T]) -> int:
+        """
+        Update the set with the given iterable sequence, then return the index
+        of the last element inserted.
+
+        Example:
+            >>> oset = StableSet([1, 2, 3])
+            >>> oset.update([3, 1, 5, 1, 4])
+            4
+            >>> print(oset)
+            StableSet([1, 2, 3, 5, 4])
+        """
+        if self._is_mutable is False:
+            raise ValueError("This object is not mutable.")
+
+        other_map = dict.fromkeys(sequence)
+        self._map.update(other_map)
+        return len(self._map) - 1
+
+    @overload
+    def index(self, key: Sequence[T]) -> List[int]:  # NOQA
+        ...
+
+    @overload
+    def index(self, key: T) -> int:  # NOQA
+        ...
+
+    # concrete implementation
+    def index(self, key):  # NOQA
+        """
+        Get the index of a given entry, raising an IndexError if it's not present
+
+        `key` can be an iterable of entries that is not a string, in which case
+        this returns a list of indices.
+
+        Example:
+            >>> oset = StableSet([1, 2, 3])
+            >>> oset.index(2)
+            1
+        """
+        try:
+            if isinstance(key, Iterable) and not _is_atomic(key):
+                return [self.index(subkey) for subkey in key]
+            for index, item in enumerate(self._map.keys()):
+                if item == key:
+                    return index
+            raise KeyError(key)
+            # return list(self._map.keys()).index(key)
+        except ValueError:
+            raise KeyError(key)
+
+    # Provide some compatibility with pd.Index
+    get_loc = index
+    get_indexer = index
+
+    def pop(self, index: int = -1) -> T:
+        """
+        Remove and return item at index (default last).
+
+        Raises KeyError if the set is empty.
+        Raises IndexError if index is out of range.
+
+        Example:
+            >>> oset = StableSet([1, 2, 3])
+            >>> oset.pop()
+            3
+        """
+        if self._is_mutable is False:
+            raise ValueError("This object is not mutable.")
+
+        if not self._map:
+            raise KeyError("Set is empty")
+        if index == -1:
+            elem, _ = self._map.popitem()
+            return elem
+        elif index == 0:
+            elem = next(iter(self._map.keys()))
+        else:
+            elem = next(itertools.islice(self._map.keys(), index, index + 1))
+        self._map.pop(elem)
+        return elem
+
+    def popitem(self, last: bool = True):
+        """Remove and return an item from the set.
+        Items are returned in LIFO order if last is true or FIFO order if false.
+        """
+        if self._is_mutable is False:
+            raise ValueError("This object is not mutable.")
+
+        if not self._map:
+            raise KeyError("Set is empty")
+        if last:
+            elem, _ = self._map.popitem()
+            return elem
+        elem = next(iter(self._map.keys()))
+        self._map.pop(elem)
+        return elem
+
+    def move_to_end(self, key) -> None:
+        """Move an existing element to the end.
+        Raise KeyError if the element does not exist.
+        """
+        if self._is_mutable is False:
+            raise ValueError("This object is not mutable.")
+
+        self._map.pop(key)
+        self._map[key] = None
+
+    def discard(self, key: T) -> None:
+        """
+        Remove an element.  Do not raise an exception if absent.
+
+        The MutableSet mixin uses this to implement the .remove() method, which
+        *does* raise an error when asked to remove a non-existent item.
+
+        Example:
+            >>> oset = StableSet([1, 2, 3])
+            >>> oset.discard(2)
+            >>> print(oset)
+            StableSet([1, 3])
+            >>> oset.discard(2)
+            >>> print(oset)
+            StableSet([1, 3])
+        """
+        if self._is_mutable is False:
+            raise ValueError("This object is not mutable.")
+
+        self._map.pop(key, None)
+
+    def union(self, *sets: SetLike[T]) -> "StableSet[T]":
+        """
+        Combines all unique items.
+        Each item order is defined by its first appearance.
+
+        Example:
+            >>> oset = StableSet.union(StableSet([3, 1, 4, 1, 5]), [1, 3], [2, 0])
+            >>> print(oset)
+            StableSet([3, 1, 4, 5, 2, 0])
+            >>> oset.union([8, 9])
+            StableSet([3, 1, 4, 5, 2, 0, 8, 9])
+            >>> oset | {10}
+            StableSet([3, 1, 4, 5, 2, 0, 10])
+        """
+        cls = type(self if isinstance(self, StableSet) else StableSet)
+        containers = map(list, it.chain([self], sets))  # type: ignore
+        items = it.chain.from_iterable(containers)
+        return cls(items)  # type: ignore
+
+    def intersection(self, *sets: SetLike[T]) -> "StableSet[T]":
+        """
+        Returns elements in common between all sets. Order is defined only
+        by the first set.
+
+        Example:
+            >>> oset = StableSet.intersection(StableSet([0, 1, 2, 3]), [1, 2, 3])
+            >>> print(oset)
+            StableSet([1, 2, 3])
+            >>> oset.intersection([2, 4, 5], [1, 2, 3, 4])
+            StableSet([2])
+            >>> oset.intersection()
+            StableSet([1, 2, 3])
+        """
+        cls = type(self if isinstance(self, StableSet) else StableSet)
+        items: SetInitializer[T] = self
+        if sets:
+            common = set.intersection(*map(set, sets))  # type: ignore
+            items = (item for item in self if item in common)
+        return cls(items)
+
+    def difference(self, *sets: SetLike[T]) -> "StableSet[T]":
+        """
+        Returns all elements that are in this set but not the others.
+
+        Example:
+            >>> StableSet([1, 2, 3]).difference(StableSet([2]))
+            StableSet([1, 3])
+            >>> StableSet([1, 2, 3]).difference(StableSet([2]), StableSet([3]))
+            StableSet([1])
+            >>> StableSet([1, 2, 3]) - StableSet([2])
+            StableSet([1, 3])
+            >>> StableSet([1, 2, 3]).difference()
+            StableSet([1, 2, 3])
+        """
+        cls = type(self if isinstance(self, StableSet) else StableSet)
+        items: SetInitializer[T] = self
+        if sets:
+            other = set.union(*map(set, sets))  # type: ignore
+            items = (item for item in self if item not in other)
+        return cls(items)
+
+    def symmetric_difference(self, other: SetLike[T]) -> "StableSet[T]":
+        """
+        Return the symmetric difference of two StableSets as a new set.
+        That is, the new set will contain all elements that are in exactly
+        one of the sets.
+
+        Their order will be preserved, with elements from `self` preceding
+        elements from `other`.
+
+        Example:
+            >>> this = StableSet([1, 4, 3, 5, 7])
+            >>> other = StableSet([9, 7, 1, 3, 2])
+            >>> this.symmetric_difference(other)
+            StableSet([4, 5, 9, 2])
+        """
+        cls = type(
+            self
+            if isinstance(self, StableSet)
+            else other
+            if isinstance(other, StableSet)
+            else StableSet
+        )
+        diff1 = cls(self).difference(other)
+        diff2 = cls(other).difference(self)
+        return diff1.union(diff2)
+
+    def difference_update(self, *sets: SetLike[T]) -> None:
+        """
+        Update this StableSet to remove items from one or more other sets.
+
+        Example:
+            >>> this = StableSet([1, 2, 3])
+            >>> this.difference_update(StableSet([2, 4]))
+            >>> print(this)
+            StableSet([1, 3])
+
+            >>> this = StableSet([1, 2, 3, 4, 5])
+            >>> this.difference_update(StableSet([2, 4]), StableSet([1, 4, 6]))
+            >>> print(this)
+            StableSet([3, 5])
+        """
+        if self._is_mutable is False:
+            raise ValueError("This object is not mutable.")
+
+        items_to_remove = set()  # type: Set[T]
+        for other in sets:
+            items_as_set = set(other)  # type: Set[T]
+            items_to_remove |= items_as_set
+        self._map = dict.fromkeys(
+            [item for item in self._map if item not in items_to_remove]
+        )
+
+    def intersection_update(self, other: SetLike[T]) -> None:
+        """
+        Update this StableSet to keep only items in another set, preserving
+        their order in this set.
+
+        Example:
+            >>> this = StableSet([1, 4, 3, 5, 7])
+            >>> other = StableSet([9, 7, 1, 3, 2])
+            >>> this.intersection_update(other)
+            >>> print(this)
+            StableSet([1, 3, 7])
+        """
+        if self._is_mutable is False:
+            raise ValueError("This object is not mutable.")
+        other = set(other)
+        self._map = dict.fromkeys([item for item in self._map if item in other])
+
+    def symmetric_difference_update(self, other: SetLike[T]) -> None:
+        """
+        Update this StableSet to remove items from another set, then
+        add items from the other set that were not present in this set.
+
+        Example:
+            >>> this = StableSet([1, 4, 3, 5, 7])
+            >>> other = StableSet([9, 7, 1, 3, 2])
+            >>> this.symmetric_difference_update(other)
+            >>> print(this)
+            StableSet([4, 5, 9, 2])
+        """
+        items_to_add = [item for item in other if item not in self]
+        items_to_remove = set(other)
+        self._map = dict.fromkeys(
+            [item for item in self._map if item not in items_to_remove] + items_to_add
+        )
+
+    def issubset(self, other: SetLike[T]) -> bool:
+        """
+        Report whether another set contains this set.
+
+        Example:
+            >>> StableSet([1, 2, 3]).issubset({1, 2})
+            False
+            >>> StableSet([1, 2, 3]).issubset({1, 2, 3, 4})
+            True
+            >>> StableSet([1, 2, 3]).issubset({1, 4, 3, 5})
+            False
+        """
+        if len(self) > len(other):  # Fast check for obvious cases
+            return False
+        return all(item in other for item in self)
+
+    def issuperset(self, other: SetLike[T]) -> bool:
+        """
+        Report whether this set contains another set.
+
+        Example:
+            >>> StableSet([1, 2]).issuperset([1, 2, 3])
+            False
+            >>> StableSet([1, 2, 3, 4]).issuperset({1, 2, 3})
+            True
+            >>> StableSet([1, 4, 3, 5]).issuperset({1, 2, 3})
+            False
+        """
+        if len(self) < len(other):  # Fast check for obvious cases
+            return False
+        return all(item in self for item in other)
+
+    def isorderedsubset(self: SetLike, other: SetLike, non_consecutive: bool = False):
+        if len(self) > len(other):
+            return False
+        if non_consecutive:
+            i = 0
+            self_len = len(self)
+            for other_item in other:
+                if other_item == self[i]:
+                    i += 1
+                    if i == self_len:
+                        return True
+            return False
+        else:
+            for self_item, other_item in zip(self, other):
+                if not self_item == other_item:
+                    return False
+            return True
+
+    def isorderedsuperset(self, other: SetLike, non_consecutive: bool = False):
+        return StableSet.isorderedsubset(other, self, non_consecutive)
+
+    def get(self):
+        return next(iter(self._map))
+
+    def freeze(self):
+        """
+        Once this function is run, the object becomes immutable
+        """
+        self._is_mutable = False
+
+
+class OrderlySet(StableSet[T]):
+    """
+    OrderlySet keeps the order when adding but if you do difference, subtraction, etc, you lose the order.
+    The new results will have a random order but they will keep that order.
+    """
+
+    def __sub__(self, other):
+        other = other if isinstance(other, (set, frozenset)) else set(other)
+        result = set(self) - other
+        return OrderlySet(result)
+
+    def __rsub__(self, other):
+        other = other if isinstance(other, (set, frozenset)) else set(other)
+        result = other - set(self)
+        return OrderlySet(result)
+
+    def __xor__(self, other):
+        other = other if isinstance(other, (set, frozenset)) else set(other)
+        result = set(self) ^ other
+        return OrderlySet(result)
+
+    __rxor__ = __xor__
+
+    def __eq__(self, other):
+        if not isinstance(other, Iterable):
+            return False
+        if len(self._map) != len(other):
+            return False
+        if isinstance(other, StableSet):
+            return self._map == other._map
+        if not isinstance(other, (set, frozenset)):
+            other = set(other)
+        return set(self._map.keys()) == other
+
+    def __ge__(self, other):
+        if not isinstance(other, Iterable):
+            return False
+        if len(self._map) < len(other):
+            return False
+        if not isinstance(other, (set, frozenset)):
+            other = set(other)
+        return set(self._map.keys()) >= other
+
+    def __gt__(self, other):
+        if not isinstance(other, Iterable):
+            return False
+        if len(self._map) <= len(other):
+            return False
+        if not isinstance(other, (set, frozenset)):
+            other = set(other)
+        return set(self._map.keys()) > other
+
+    def __le__(self, other):
+        if not isinstance(other, Iterable):
+            return False
+        if len(self._map) > len(other):
+            return False
+        if not isinstance(other, (set, frozenset)):
+            other = set(other)
+        return set(self._map.keys()) <= other
+
+    def __lt__(self, other):
+        if not isinstance(other, Iterable):
+            return False
+        if len(self._map) >= len(other):
+            return False
+        if not isinstance(other, (set, frozenset)):
+            other = set(other)
+        return set(self._map.keys()) < other
+
+
+class StableSetEq(StableSet[T]):
+    """
+    StableSetEq is a StableSet with a modified quality operator.
+
+    StableSetEq, like `set` and `dict_keys` [dict.keys()], and unlike OrderdSet,
+    disregards the items order when checking equality.
+    Unlike StableSet, `set`, or `dict_keys` - A StableSetEq can also equal be equal to a Sequence:
+    `StableSet([1, 2]) == [1, 2]` and `StableSet([1, 2]) == [2, 1]`; but `set([1, 2]) != [1, 2]`
+    """
+
+    def __eq__(self, other: Any) -> bool:
+        """
+        Returns true even if the containers don't have the same items in order.
+
+        Example:
+            >>> oset = StableSetEq([1, 3, 2])
+            >>> oset == [1, 3, 2]
+            True
+            >>> oset == [1, 2, 3]
+            True
+            >>> oset == [2, 3]
+            False
+            >>> oset == StableSetEq([3, 2, 1])
+            True
+        """
+        if not isinstance(other, AbstractSet):
+            try:
+                other = set(other)
+            except TypeError:
+                # If `other` can't be converted into a set, it's not equal.
+                return False
+        return self._map.keys() == other
+
+    def __le__(self, other: SetLike[T]):
+        return len(self) <= len(other) and (
+            self._map.keys() <= other
+            if isinstance(other, AbstractSet)
+            else self._map.keys() <= set(other)
+        )
+
+    def __lt__(self, other: SetLike[T]):
+        return len(self) < len(other) and (
+            self._map.keys() < other
+            if isinstance(other, AbstractSet)
+            else self._map.keys() < set(other)
+        )
+
+    def __ge__(self, other: SetLike[T]):
+        return len(self) >= len(other) and (
+            self._map.keys() >= other
+            if isinstance(other, AbstractSet)
+            else self._map.keys() >= set(other)
+        )
+
+    def __gt__(self, other: SetLike[T]):
+        return len(self) > len(other) and (
+            self._map.keys() > other
+            if isinstance(other, AbstractSet)
+            else self._map.keys() > set(other)
+        )
+
+
+class OrderedSet(StableSet[T]):
+    """
+    An OrderedSet is a mutable data structure that is a hybrid of a list and a set.
+    It remembers its insertion order so that every entry has an index that can be looked up.
+    Featuring: O(1) Index lookup, insertion, iteration and membership testing.
+    But slow O(N) Deletion.
+    Using OrderedSet over StableSet is advised only if you require fast Index lookup -
+    Otherwise using StableSet is advised as it is much faster and has a smaller memory footprint.
+
+    In some aspects OrderedSet behaves like a `set` and in other aspects it behaves like a list.
+
+    Equality: OrderedSet, like `list` and `odict_keys` [OrderdDict.keys()], and unlike OrderdSet,
+    regards the items order when checking equality.
+    Unlike `set`, An OrderedSet can also equal be equal to a Sequence:
+    `StableSet([1, 2]) == [1, 2]` and `StableSet([1, 2]) != [2, 1]`; but `set([1, 2]) != [1, 2]`
+
+    The original implementation of OrderedSet was a recipe posted by Raymond Hettiger,
+    https://code.activestate.com/recipes/576694-orderedset/
+    Released under the MIT license.
+    Hettiger's implementation kept its content in a doubly-linked list referenced by a dict.
+    As a result, looking up an item by its index was an O(N) operation, while deletion was O(1).
+    This version makes different trade-offs for the sake of efficient lookups.
+    Its content is a standard Python list instead of a doubly-linked list.
+    This provides O(1) lookups by index at the expense of O(N) deletion,
+    as well as slightly faster iteration.
+
+    Example:
+        >>> OrderedSet([1, 1, 2, 3, 2])
+        OrderedSet([1, 2, 3])
+    """
+
+    __slots__ = ("_items",)
+
+    _items: List[T]
+
+    def __init__(self, initial: Optional[SetInitializer[T]] = None):
+        self._items = []
+        self._map = {}
+        if initial is not None:
+            # In terms of duck-typing, the default __ior__ is compatible with
+            # the types we use, but it doesn't expect all the types we
+            # support as values for `initial`.
+            self |= initial  # type: ignore
+
+    def __getitem__(self, index):
+        if isinstance(index, int):
+            return self._items[index]
+        elif isinstance(index, slice) and index == SLICE_ALL:
+            return self.copy()
+        elif isinstance(index, Iterable):
+            return [self._items[i] for i in index]
+        elif isinstance(index, slice) or hasattr(index, "__index__"):
+            result = self._items[index]
+            if isinstance(result, list):
+                return self.__class__(result)
+            else:
+                return result
+        else:
+            raise TypeError("Don't know how to index an OrderedSet by %r" % index)
+
+    def __eq__(self, other: Any) -> bool:
+        """
+        Returns true if the containers have the same items.
+        If `other` is a Sequence, then order is checked, otherwise it is ignored.
+
+        Example:
+            >>> oset = OrderedSet([1, 3, 2])
+            >>> oset == [1, 3, 2]
+            True
+            >>> oset == [1, 2, 3]
+            False
+            >>> oset == [2, 3]
+            False
+            >>> oset == OrderedSet([3, 2, 1])
+            False
+        """
+        if isinstance(other, Sequence):
+            # Check that this OrderedSet contains the same elements, in the
+            # same order, as the other object.
+            return len(self) == len(other) and self._items == list(other)
+        try:
+            other_as_set = set(other)
+        except TypeError:
+            # If `other` can't be converted into a set, it's not equal.
+            return False
+        else:
+            return self._map.keys() == other_as_set
+
+    def __le__(self, other: SetLike[T]):
+        return len(self) <= len(other) and (
+            self._map.keys() <= other
+            if isinstance(other, AbstractSet)
+            else self._items <= other
+            if isinstance(other, list)
+            else self._items <= list(other)
+        )
+
+    def __lt__(self, other: SetLike[T]):
+        return len(self) < len(other) and (
+            self._map.keys() < other
+            if isinstance(other, AbstractSet)
+            else self._items < other
+            if isinstance(other, list)
+            else self._items < list(other)
+        )
+
+    def __ge__(self, other: SetLike[T]):
+        return len(self) >= len(other) and (
+            self._map.keys() >= other
+            if isinstance(other, AbstractSet)
+            else self._items >= other
+            if isinstance(other, list)
+            else self._items >= list(other)
+        )
+
+    def __gt__(self, other: SetLike[T]):
+        return len(self) > len(other) and (
+            self._map.keys() > other
+            if isinstance(other, AbstractSet)
+            else self._items > other
+            if isinstance(other, list)
+            else self._items > list(other)
+        )
+
+    def clear(self) -> None:
+        del self._items[:]
+        self._map.clear()
+
+    def add(self, key: T) -> int:
+        if key not in self._map:
+            self._map[key] = len(self._items)
+            self._items.append(key)
+        return self._map[key]
+
+    def update(self, sequence: SetLike[T]) -> int:
+        item_index = 0
+        for item in sequence:
+            item_index = self.add(item)
+        return item_index
+
+    def index(self, key):
+        if isinstance(key, Iterable) and not _is_atomic(key):
+            return [self.index(subkey) for subkey in key]
+        return self._map[key]
+
+    def pop(self, index: int = -1) -> T:
+        if not self._items:
+            raise KeyError("Set is empty")
+        elem = self._items[index]
+        del self._items[index]
+        del self._map[elem]
+        return elem
+
+    def popitem(self, last: bool = True):
+        if not self._items:
+            raise KeyError("Set is empty")
+        index = -1 if last else 0
+        elem = self._items[index]
+        del self._items[index]
+        del self._map[elem]
+        return elem
+
+    def move_to_end(self, key):
+        if key in self:
+            self.discard(key)
+            self.add(key)
+        else:
+            raise KeyError(key)
+
+    def discard(self, key: T) -> None:
+        if key in self:
+            i = self._map[key]
+            del self._items[i]
+            del self._map[key]
+            for k, v in self._map.items():
+                if v >= i:
+                    self._map[k] = v - 1
+
+    def _update_items(self, items: list) -> None:
+        """
+        Replace the 'items' list of this OrderedSet with a new one, updating
+        self._map accordingly.
+        """
+        self._items = items
+        self._map = {item: idx for (idx, item) in enumerate(items)}
+
+    def difference_update(self, *sets: SetLike[T]) -> None:
+        items_to_remove = set()  # type: Set[T]
+        for other in sets:
+            items_as_set = set(other)  # type: Set[T]
+            items_to_remove |= items_as_set
+        self._update_items(
+            [item for item in self._items if item not in items_to_remove]
+        )
+
+    def intersection_update(self, other: SetLike[T]) -> None:
+        other = set(other)
+        self._update_items([item for item in self._items if item in other])
+
+    def symmetric_difference_update(self, other: SetLike[T]) -> None:
+        items_to_add = [item for item in other if item not in self]
+        items_to_remove = set(other)
+        self._update_items(
+            [item for item in self._items if item not in items_to_remove] + items_to_add
+        )
+
+
+class SortedSet:
+
+    def __init__(self, *args, set_=None, **kwargs):
+        self._sorted = None
+        if set_:
+            self.set_ = set_
+        else:
+            self.set_ = set(*args, **kwargs)
+
+    def __iter__(self):
+        yield from self._get_sorted()
+
+    def __str__(self) -> str:
+        if not self:
+            return f"{self.__class__.__name__}()"
+        return f"{self.__class__.__name__}({self._get_sorted()!r})"
+
+
+    __repr__ = __str__
+
+    def _get_sorted(self, reverse=False):
+        if self._sorted is None:
+            try:
+                self._sorted = sorted(self.set_, reverse=reverse)
+            except Exception:
+                self._sorted = sorted(self.set_, key=lambda x: str(x), reverse=reverse)
+        return self._sorted
+
+    def get(self):
+        """
+        Get a random element
+        """
+        return next(iter(self.set_))
+
+    def __and__(self, other):
+        # Intersection
+        result = self.set_ & other
+        return SortedSet(set_=result)
+
+    intersection = __and__
+
+    __rand__ = __and__
+
+    def intersection_update(self, other):
+        self.set_.intersection_update(other)
+
+    def __or__(self, other):
+        # Union
+        result = self.set_ | other
+        return SortedSet(set_=result)
+
+    union = __ror__ = __or__
+
+    def __sub__(self, other):
+        # Difference
+        result = self.set_ - other
+        return SortedSet(set_=result)
+
+    difference = __sub__
+
+    def difference_update(self, *sets):
+        self._sorted = None
+        self.set_.difference_update(*sets)
+
+    def isdisjoint(self, other):
+        return self.set_.isdisjoint(other)
+
+    def __xor__(self, other):
+        # Symmetric difference
+        result = self.set_ ^ other
+        return SortedSet(set_=result)
+
+    symmetric_difference = __rxor__ = __xor__
+
+    def symmetric_difference_update(self, other):
+        self._sorted = None
+        self.set_.symmetric_difference_update(other)
+
+    def __rsub__(self, other):
+        result = other - self.set_
+        return SortedSet(set_=result)
+
+    def add(self, item):
+        self._sorted = None
+        self.set_.add(item)
+
+    def clear(self):
+        self._sorted = None
+        self.set_.clear()
+
+    def discard(self, key):
+        self._sorted = None
+        self.set_.discard(key)
+
+    def copy(self):
+        return SortedSet(set_=set(self.set_))
+
+    def __le__(self, other):
+        return self.set_.issubset(other)
+
+    issubset = __le__
+
+    def __lt__(self, other):
+        return self.set_ < other
+
+    def __ge__(self, other):
+        return self.set_.issuperset(other)
+
+    issuperset = __ge__
+
+    def __gt__(self, other):
+        return self.set_ > other
+
+    def remove(self, key):
+        self._sorted = None
+        self.set_.remove(key)
+
+    def update(self, sequence):
+        self._sorted = None
+        self.set_.update(sequence)
+
+    def __len__(self):
+        return len(self.set_) if self.set_ else 0
+
+    def __eq__(self, other):
+        if not isinstance(other, Iterable):
+            return False
+        if len(self.set_) != len(other):
+            return False
+        if isinstance(other, SortedSet):
+            return self.set_ == other.set_
+        if not isinstance(other, (set, frozenset)):
+            other = set(other)
+        return self.set_ == other
+
+    def __reversed__(self):
+        if self._sorted is None:
+            self._get_sorted()
+        return reversed(self._sorted)
+
+    def __getitem__(self, index):
+        items = self._get_sorted()
+
+        if isinstance(index, int):
+            return items[index]
+        elif isinstance(index, slice) and index == SLICE_ALL:
+            return self.copy()
+        if isinstance(index, Iterable):
+            return [items[i] for i in index]
+        elif isinstance(index, slice) or hasattr(index, "__index__"):
+            result = items[index]
+            if isinstance(result, list):
+                return self.__class__(result)
+            else:
+                return result
+        else:
+            raise TypeError(f"Don't know how to index a SortedSet by {index}")
+
+    def index(self, key):  # NOQA
+        """
+        Get the index of a given entry, raising an IndexError if it's not present
+
+        `key` can be an iterable of entries that is not a string, in which case
+        this returns a list of indices.
+
+        Example:
+            >>> oset = StableSet([1, 2, 3])
+            >>> oset.index(2)
+            1
+        """
+        items = self._get_sorted()
+        try:
+            if isinstance(key, Iterable) and not _is_atomic(key):
+                return [self.index(subkey) for subkey in key]
+            for index, item in enumerate(items):
+                if item == key:
+                    return index
+            raise KeyError(key)
+            # return list(self._map.keys()).index(key)
+        except ValueError:
+            raise KeyError(key)
+
+    # Provide some compatibility with pd.Index
+    get_loc = index
+    get_indexer = index
+
+    def pop(self, index=None):
+        if index is None:
+            self._sorted = None
+            return self.set_.pop()
+        items = self._get_sorted()
+        result = items.pop(index)
+        self.set_.remove(result)
+        return result
+
+    def isorderedsubset(self: SetLike, other: SetLike, non_consecutive: bool = False):
+        if len(self) > len(other):
+            return False
+        if non_consecutive:
+            i = 0
+            self_len = len(self)
+            for other_item in other:
+                if other_item == self[i]:
+                    i += 1
+                    if i == self_len:
+                        return True
+            return False
+        else:
+            for self_item, other_item in zip(self, other):
+                if not self_item == other_item:
+                    return False
+            return True
+
+    def isorderedsuperset(self, other: SetLike, non_consecutive: bool = False):
+        return StableSet.isorderedsubset(other, self, non_consecutive)