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
|
# NOTE: from https://github.com/LuminosoInsight/ordered-set/blob/master/ordered_set.py
import itertools
from collections.abc import (
Iterable,
Iterator,
Mapping,
MutableSequence,
MutableSet,
Sequence,
)
from typing import Any, TypeVar
T = TypeVar('T')
class OrderedSet(MutableSet[T], Sequence[T]):
def __init__(self, iterable: Iterable[T] | None = None):
if iterable is not None:
self._map = dict.fromkeys(iterable)
else:
self._map = {}
self._list_cache: Sequence[T] | None = None
def __hash__(self):
return self._map.__hash__()
def __len__(self):
return len(self._map)
def __getitem__(self, i):
if self._list_cache is None:
self._list_cache = list(self._map.keys())
return self._list_cache[i]
def copy(self) -> 'OrderedSet[T]':
return self.__class__(self)
def __getstate__(self):
if len(self) == 0:
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:
return key in self._map
def add(self, value: T): # pylint: disable=W0221
self._map[value] = len(self._map)
self._list_cache = None
def update(self, sequence: Iterable[T]):
self._map.update(dict.fromkeys(sequence))
self._list_cache = None
def pop(self) -> T:
key = next(iter(self._map.keys()))
self._map.pop(key)
self._list_cache = None
return key
def discard(self, value: T): # pylint: disable=W0221
self._map.pop(value, None)
self._list_cache = None
def clear(self):
self._map = {}
self._list_cache = None
def __iter__(self) -> Iterator[T]:
return iter(self._map.keys())
def __repr__(self) -> str:
return '{{{}}}'.format(', '.join(repr(e) for e in self))
def __eq__(self, other: Any) -> bool:
return all(item in other for item in self)
def union(self, *other: Iterable[T]) -> 'OrderedSet[T]':
# do not split `str`
outer = tuple(
[o] if not isinstance(o, set | Mapping | MutableSequence) else o
for o in other
)
inner = itertools.chain([self], *outer)
items = itertools.chain.from_iterable(inner)
return type(self)(itertools.chain(items))
def __and__(self, other: Iterable[Iterable[T]]) -> 'OrderedSet[T]':
return self.intersection(other)
def intersection(self, *other: Iterable[Iterable[T]]) -> 'OrderedSet[T]':
common = set.intersection(*other) # type: ignore[var-annotated, arg-type]
items = (item for item in self if item in common)
return type(self)(items)
def difference(self, *other: Iterable[T]) -> 'OrderedSet[T]':
other = set.union(*other) # type: ignore[assignment, arg-type]
items = (item for item in self if item not in other)
return type(self)(items)
def issubset(self, other: set[T]) -> bool:
return all(item in other for item in self)
def issuperset(self, other: set[T]) -> bool:
if len(self) < len(other): # Fast check for obvious cases
return False
return all(item in self for item in other)
def symmetric_difference(self, other: set[T]) -> 'OrderedSet[T]':
cls = type(self)
diff1 = cls(self).difference(other)
diff2 = cls(other).difference(self)
return cls().union(diff1, diff2)
def difference_update(self, *other: Iterable[T]):
self._map = dict.fromkeys(self.difference(*other))
def intersection_update(self, *other: Iterable[Iterable[T]]):
self._map = dict.fromkeys(self.intersection(*other))
def symmetric_difference_update(self, *other: Iterable[T]):
self._map = dict.fromkeys(self.difference(*other))
|
