1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
|
from __future__ import annotations
from collections.abc import MutableSet, Set as AbstractSet
from typing import (
Any,
cast,
Dict,
Generic,
Iterable,
Iterator,
List,
Optional,
Tuple,
Type,
TypeVar,
)
T = TypeVar("T")
T_co = TypeVar("T_co", covariant=True)
__all__ = ["OrderedSet"]
# Using Generic[T] bc py38 does not support type parameterized MutableSet
class OrderedSet(MutableSet, Generic[T]):
"""
Insertion ordered set, similar to OrderedDict.
"""
__slots__ = ("_dict",)
def __init__(self, iterable: Optional[Iterable[T]] = None):
self._dict = dict.fromkeys(iterable, None) if iterable is not None else {}
@staticmethod
def _from_dict(dict_inp: Dict[T, None]) -> OrderedSet[T]:
s: OrderedSet[T] = OrderedSet()
s._dict = dict_inp
return s
#
# Required overriden abstract methods
#
def __contains__(self, elem: object) -> bool:
return elem in self._dict
def __iter__(self) -> Iterator[T]:
return iter(self._dict)
def __len__(self) -> int:
return len(self._dict)
def add(self, elem: T) -> None:
self._dict[elem] = None
def discard(self, elem: T) -> None:
self._dict.pop(elem, None)
def clear(self) -> None:
# overridden because MutableSet impl is slow
self._dict.clear()
# Unimplemented set() methods in _collections_abc.MutableSet
@classmethod
def _wrap_iter_in_set(cls, other: Any) -> Any:
"""
Wrap non-Set Iterables in OrderedSets
Some of the magic methods are more strict on input types than
the public apis, so we need to wrap inputs in sets.
"""
if not isinstance(other, AbstractSet) and isinstance(other, Iterable):
return cls(other)
else:
return other
def pop(self) -> T:
if not self:
raise KeyError("pop from an empty set")
return self._dict.popitem()[0]
def copy(self) -> OrderedSet[T]:
return OrderedSet._from_dict(self._dict.copy())
def difference(self, *others: Iterable[T]) -> OrderedSet[T]:
res = self.copy()
res.difference_update(*others)
return res
def difference_update(self, *others: Iterable[T]) -> None:
for other in others:
self -= other # type: ignore[operator, arg-type]
def update(self, *others: Iterable[T]) -> None:
for other in others:
self |= other # type: ignore[operator, arg-type]
def intersection(self, *others: Iterable[T]) -> OrderedSet[T]:
res = self.copy()
for other in others:
if other is not self:
res &= other # type: ignore[operator, arg-type]
return res
def intersection_update(self, *others: Iterable[T]) -> None:
for other in others:
self &= other # type: ignore[operator, arg-type]
def issubset(self, other: Iterable[T]) -> bool:
return self <= self._wrap_iter_in_set(other)
def issuperset(self, other: Iterable[T]) -> bool:
return self >= self._wrap_iter_in_set(other)
def symmetric_difference(self, other: Iterable[T]) -> OrderedSet[T]:
return self ^ other # type: ignore[operator, arg-type]
def symmetric_difference_update(self, other: Iterable[T]) -> None:
self ^= other # type: ignore[operator, arg-type]
def union(self, *others: Iterable[T]) -> OrderedSet[T]:
res = self.copy()
for other in others:
if other is self:
continue
res |= other # type: ignore[operator, arg-type]
return res
# Specify here for correct type inference, otherwise would
# return AbstractSet[T]
def __sub__(self, other: AbstractSet[T_co]) -> OrderedSet[T]:
# following cpython set impl optimization
if isinstance(other, OrderedSet) and (len(self) * 4) > len(other):
out = self.copy()
out -= other
return out
return cast(OrderedSet[T], super().__sub__(other))
def __ior__(self, other: Iterable[T]) -> OrderedSet[T]: # type: ignore[misc, override] # noqa: PYI034
if isinstance(other, OrderedSet):
self._dict.update(other._dict)
return self
return super().__ior__(other) # type: ignore[arg-type]
def __eq__(self, other: AbstractSet[T]) -> bool: # type: ignore[misc, override]
if isinstance(other, OrderedSet):
return self._dict == other._dict
return super().__eq__(other) # type: ignore[arg-type]
def __ne__(self, other: AbstractSet[T]) -> bool: # type: ignore[misc, override]
if isinstance(other, OrderedSet):
return self._dict != other._dict
return super().__ne__(other) # type: ignore[arg-type]
def __or__(self, other: AbstractSet[T_co]) -> OrderedSet[T]:
return cast(OrderedSet[T], super().__or__(other))
def __and__(self, other: AbstractSet[T_co]) -> OrderedSet[T]:
# MutableSet impl will iterate over other, iter over smaller of two sets
if isinstance(other, OrderedSet) and len(self) < len(other):
return other & self
return cast(OrderedSet[T], super().__and__(other))
def __xor__(self, other: AbstractSet[T_co]) -> OrderedSet[T]:
return cast(OrderedSet[T], super().__xor__(other))
def __repr__(self) -> str:
return f"{self.__class__.__name__}({list(self)})"
def __getstate__(self) -> List[T]:
return list(self._dict.keys())
def __setstate__(self, state: List[T]) -> None:
self._dict = dict.fromkeys(state, None)
def __reduce__(self) -> Tuple[Type[OrderedSet[T]], Tuple[List[T]]]:
return (OrderedSet, (list(self),))
|
