Coverage for /var/srv/projects/api.amasfac.comuna18.com/tmp/venv/lib/python3.9/site-packages/uritemplate/orderedset.py: 29%
57 statements
« prev ^ index » next coverage.py v6.4.4, created at 2023-07-17 14:22 -0600
« prev ^ index » next coverage.py v6.4.4, created at 2023-07-17 14:22 -0600
1# From: https://github.com/ActiveState/code/blob/master/recipes/Python/576696_OrderedSet_with_Weakrefs/ # noqa
2import typing as t
3import weakref
6class Link:
7 """Representation of one item in a doubly-linked list."""
9 __slots__ = ("prev", "next", "key", "__weakref__")
10 prev: "Link"
11 next: "Link"
12 key: str
15class OrderedSet(t.MutableSet[str]):
16 """A set that remembers the order in which items were added."""
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 linked
20 # list. The circular doubly linked list starts and ends with a sentinel
21 # element. The sentinel element never gets deleted (this simplifies the
22 # algorithm). The prev/next links are weakref proxies (to prevent circular
23 # references). Individual links are kept alive by the hard reference in
24 # self.__map. Those hard references disappear when a key is deleted from
25 # an OrderedSet.
27 def __init__(self, iterable: t.Optional[t.Iterable[str]] = None):
28 self.__root = root = Link() # sentinel node for doubly linked list
29 root.prev = root.next = root
30 self.__map: t.MutableMapping[str, Link] = {} # key --> link
31 if iterable is not None:
32 self |= iterable # type: ignore
34 def __len__(self) -> int:
35 return len(self.__map)
37 def __contains__(self, key: object) -> bool:
38 return key in self.__map
40 def add(self, key: str) -> None:
41 # Store new key in a new link at the end of the linked list
42 if key not in self.__map:
43 self.__map[key] = link = Link()
44 root = self.__root
45 last = root.prev
46 link.prev, link.next, link.key = last, root, key
47 last.next = root.prev = weakref.proxy(link)
49 def discard(self, key: str) -> None:
50 # Remove an existing item using self.__map to find the link which is
51 # 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.next
55 link.next.prev = link.prev
57 def __iter__(self) -> t.Generator[str, None, None]:
58 # Traverse the linked list in order.
59 root = self.__root
60 curr = root.next
61 while curr is not root:
62 yield curr.key
63 curr = curr.next
65 def __reversed__(self) -> t.Generator[str, None, None]:
66 # Traverse the linked list in reverse order.
67 root = self.__root
68 curr = root.prev
69 while curr is not root:
70 yield curr.key
71 curr = curr.prev
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 key
80 def __repr__(self) -> str:
81 if not self:
82 return f"{self.__class__.__name__}()"
83 return f"{self.__class__.__name__}({list(self)!r})"
85 def __str__(self) -> str:
86 return self.__repr__()
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)