Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/uritemplate/orderedset.py: 49%

1# From: https://github.com/ActiveState/code/blob/master/recipes/Python/576696_OrderedSet_with_Weakrefs/ # noqa 

2import typing as t 

3import weakref 

4 

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: str 

13 

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 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. 

26 

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 

33 

34 def __len__(self) -> int: 

35 return len(self.__map) 

36 

37 def __contains__(self, key: object) -> bool: 

38 return key in self.__map 

39 

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) 

48 

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 

56 

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 

64 

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 

72 

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 

79 

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)