codekingpro/portable-devtools

1# From: https://github.com/ActiveState/code/blob/master/recipes/Python/576696_OrderedSet_with_Weakrefs/  # noqa2import typing as t3import weakref4 5 6class Link:7    """Representation of one item in a doubly-linked list."""8 9    __slots__ = ("prev", "next", "key", "__weakref__")10    prev: "Link"11    next: "Link"12    key: str13 14 15class OrderedSet(t.MutableSet[str]):16    """A set that remembers the order in which items were added."""17 18    # Big-O running times for all methods are the same as for regular sets.19    # The internal self.__map dictionary maps keys to links in a doubly linked20    # list. The circular doubly linked list starts and ends with a sentinel21    # element. The sentinel element never gets deleted (this simplifies the22    # algorithm). The prev/next links are weakref proxies (to prevent circular23    # references). Individual links are kept alive by the hard reference in24    # self.__map. Those hard references disappear when a key is deleted from25    # an OrderedSet.26 27    def __init__(self, iterable: t.Optional[t.Iterable[str]] = None):28        self.__root = root = Link()  # sentinel node for doubly linked list29        root.prev = root.next = root30        self.__map: t.MutableMapping[str, Link] = {}  # key --> link31        if iterable is not None:32            self |= iterable  # type: ignore33 34    def __len__(self) -> int:35        return len(self.__map)36 37    def __contains__(self, key: object) -> bool:38        return key in self.__map39 40    def add(self, key: str) -> None:41        # Store new key in a new link at the end of the linked list42        if key not in self.__map:43            self.__map[key] = link = Link()44            root = self.__root45            last = root.prev46            link.prev, link.next, link.key = last, root, key47            last.next = root.prev = weakref.proxy(link)48 49    def discard(self, key: str) -> None:50        # Remove an existing item using self.__map to find the link which is51        # then removed by updating the links in the predecessor and successors.52        if key in self.__map:53            link = self.__map.pop(key)54            link.prev.next = link.next55            link.next.prev = link.prev56 57    def __iter__(self) -> t.Generator[str, None, None]:58        # Traverse the linked list in order.59        root = self.__root60        curr = root.next61        while curr is not root:62            yield curr.key63            curr = curr.next64 65    def __reversed__(self) -> t.Generator[str, None, None]:66        # Traverse the linked list in reverse order.67        root = self.__root68        curr = root.prev69        while curr is not root:70            yield curr.key71            curr = curr.prev72 73    def pop(self, last: bool = True) -> str:74        if not self:75            raise KeyError("set is empty")76        key = next(reversed(self)) if last else next(iter(self))77        self.discard(key)78        return key79 80    def __repr__(self) -> str:81        if not self:82            return f"{self.__class__.__name__}()"83        return f"{self.__class__.__name__}({list(self)!r})"84 85    def __str__(self) -> str:86        return self.__repr__()87 88    def __eq__(self, other: object) -> bool:89        if isinstance(other, OrderedSet):90            return len(self) == len(other) and list(self) == list(other)91        other = t.cast(t.Iterable[str], other)92        return not self.isdisjoint(other)93