bernsteinbear.com
this repo has no description
1#!/usr/bin/env python3
2# Copyright (c) Facebook, Inc. and its affiliates. (http://www.facebook.com)
3
4from builtins import (
5 _index,
6 _non_heaptype,
7 _sequence_repr,
8)
9
10from _builtins import (
11 _builtin,
12 _deque_guard,
13 _dict_guard,
14 _int_guard,
15 _object_type_hasattr,
16 _repr_enter,
17 _repr_leave,
18 _tuple_check,
19 _tuple_getitem,
20 _type,
21 _unimplemented,
22)
23
24
25_Unbound = _Unbound # noqa: F821
26
27
28class OrderedDict(dict):
29 "Dictionary that remembers insertion order"
30 # NOTE: This OrderedDict implementation deviates from CPython's: instaed of keeping
31 # the ordering as a linked list, this implementation harnesses the ordering
32 # maintained by `dict`.
33
34 def move_to_end(self, key, last=True):
35 value = self.pop(key)
36 if not last:
37 _unimplemented()
38 self[key] = value
39
40 def __repr__(self):
41 return _sequence_repr(f"{self.__class__.__name__}([", self.items(), "])")
42
43
44class _deque_iterator(bootstrap=True):
45 def __iter__(self):
46 return self
47
48 def __length_hint__(self):
49 _builtin()
50
51 @staticmethod
52 def __new__(cls, deq, index=0):
53 _builtin()
54
55 def __next__(self):
56 _builtin()
57
58 def __reduce__(self):
59 _builtin()
60
61
62class _deque_reverse_iterator(bootstrap=True):
63 def __iter__(self):
64 return self
65
66 def __length_hint__(self):
67 _builtin()
68
69 @staticmethod
70 def __new__(cls, deq, index=0):
71 _builtin()
72
73 def __next__(self):
74 _builtin()
75
76 def __reduce__(self):
77 _builtin()
78
79
80def _deque_delitem(self, index):
81 _builtin()
82
83
84def _deque_getitem(self, index):
85 _builtin()
86
87
88def _deque_set_maxlen(self, maxlen):
89 _builtin()
90
91
92def _deque_setitem(self, index, value):
93 _builtin()
94
95
96class _tuplegetter(metaclass=_non_heaptype):
97 __slots__ = ("_index", "_doc")
98
99 @property
100 def __doc__(self):
101 return self._doc
102
103 @__doc__.setter
104 def __doc__(self, value):
105 self._doc = value
106
107 def __get__(self, instance, owner):
108 if not _tuple_check(instance):
109 if instance is None:
110 return self
111 raise TypeError(
112 f"descriptor for index '{self._index}' for tuple subclasses doesn't apply to '{_type(instance).__name__}' object"
113 )
114 return _tuple_getitem(instance, self._index)
115
116 @staticmethod
117 def __new__(cls, index, doc):
118 result = super().__new__(cls)
119 result._index = _index(index)
120 result._doc = doc
121 return result
122
123
124class defaultdict(dict):
125 def __copy__(self):
126 _unimplemented()
127
128 def __init__(self, default_factory=None, *args, **kwargs):
129 super().__init__(*args, **kwargs)
130 if default_factory is not None and not callable(default_factory):
131 raise TypeError("default_factory must be callable or None")
132 self.default_factory = default_factory
133
134 def __getitem__(self, key):
135 _dict_guard(self)
136 result = dict.get(self, key, _Unbound)
137 if result is _Unbound:
138 return _type(self).__missing__(self, key)
139 return result
140
141 def __missing__(self, key):
142 default_factory = self.default_factory
143 if default_factory is None:
144 raise KeyError(key)
145 value = default_factory()
146 dict.__setitem__(self, key, value)
147 return value
148
149 def __reduce__(self):
150 _unimplemented()
151
152 def __repr__(self):
153 return f"defaultdict({self.default_factory!r}, {dict.__repr__(self)})"
154
155 def copy(self):
156 _unimplemented()
157
158
159class deque(bootstrap=True):
160 def __add__(self, other):
161 _unimplemented()
162
163 def __bool__(self):
164 _deque_guard(self)
165 return len(self) > 0
166
167 def __contains__(self, value):
168 _deque_guard(self)
169 for item in self:
170 if item is value or item == value:
171 return True
172 return False
173
174 def __copy__(self):
175 _deque_guard(self)
176 return self.__class__(self, self.maxlen)
177
178 def __delitem__(self, index):
179 result = _deque_delitem(self, index)
180 if result is not _Unbound:
181 return result
182 if _object_type_hasattr(index, "__index__"):
183 return _deque_delitem(self, _index(index))
184 raise TypeError(
185 f"sequence index must be integer, not '{_type(index).__name__}'"
186 )
187
188 # TODO(emacs): Make comparison more efficient, perhaps by checking length
189 # first.
190 def __eq__(self, other):
191 _deque_guard(self)
192 if isinstance(other, deque):
193 return list(self) == list(other)
194 else:
195 return NotImplemented
196
197 def __ge__(self, other):
198 _deque_guard(self)
199 if isinstance(other, deque):
200 return list(self) >= list(other)
201 else:
202 return NotImplemented
203
204 def __getitem__(self, index):
205 "$intrinsic$"
206 result = _deque_getitem(self, index)
207 if result is not _Unbound:
208 return result
209 if _object_type_hasattr(index, "__index__"):
210 return _deque_getitem(self, _index(index))
211 raise TypeError(
212 f"sequence index must be integer, not '{_type(index).__name__}'"
213 )
214
215 def __gt__(self, other):
216 _deque_guard(self)
217 if isinstance(other, deque):
218 return list(self) > list(other)
219 else:
220 return NotImplemented
221
222 __hash__ = None
223
224 def __iadd__(self, other):
225 _deque_guard(self)
226 deque.extend(self, other)
227 return self
228
229 def __init__(self, iterable=(), maxlen=None):
230 _deque_guard(self)
231 deque.clear(self)
232 _deque_set_maxlen(self, maxlen)
233 self.extend(iterable)
234
235 def __iter__(self):
236 _builtin()
237
238 def __le__(self, other):
239 _deque_guard(self)
240 if isinstance(other, deque):
241 return list(self) <= list(other)
242 else:
243 return NotImplemented
244
245 def __len__(self):
246 _builtin()
247
248 def __lt__(self, other):
249 _deque_guard(self)
250 if isinstance(other, deque):
251 return list(self) < list(other)
252 else:
253 return NotImplemented
254
255 def __mul__(self, n):
256 _unimplemented()
257
258 def __ne__(self, other):
259 _deque_guard(self)
260 if isinstance(other, deque):
261 return list(self) != list(other)
262 else:
263 return NotImplemented
264
265 @staticmethod
266 def __new__(cls, iterable=(), *args, **kw):
267 _builtin()
268
269 def __reduce__(self):
270 _unimplemented()
271
272 def __reduce_ex__(self, proto):
273 _unimplemented()
274
275 def __repr__(self):
276 _deque_guard(self)
277 if _repr_enter(self):
278 return "[...]"
279 if self.maxlen is not None:
280 result = f"deque({list(self)!r}, maxlen={self.maxlen})"
281 else:
282 result = f"deque({list(self)!r})"
283 _repr_leave(self)
284 return result
285
286 def __reversed__(self):
287 _builtin()
288
289 def __rmul__(self, n):
290 _unimplemented()
291
292 def __setitem__(self, index, value):
293 "$intrinsic$"
294 result = _deque_setitem(self, index, value)
295 if result is not _Unbound:
296 return result
297 if _object_type_hasattr(index, "__index__"):
298 return _deque_setitem(self, _index(index), value)
299 raise TypeError(
300 f"sequence index must be integer, not '{_type(index).__name__}'"
301 )
302
303 def append(self, x):
304 _builtin()
305
306 def appendleft(self, x):
307 _builtin()
308
309 def clear(self):
310 _builtin()
311
312 def count(self, value):
313 _deque_guard(self)
314 c = 0
315 for item in self:
316 if item is value or item == value:
317 c += 1
318 return c
319
320 def extend(self, iterable):
321 _deque_guard(self)
322 if iterable is self:
323 iterable = list(iterable)
324 for elem in iterable:
325 deque.append(self, elem)
326
327 def extendleft(self, iterable):
328 _deque_guard(self)
329 if iterable is self:
330 iterable = list(iterable)
331 for elem in iterable:
332 deque.appendleft(self, elem)
333
334 def index(self, value):
335 _unimplemented()
336
337 def insert(self, value):
338 _unimplemented()
339
340 def pop(self):
341 _builtin()
342
343 def popleft(self):
344 _builtin()
345
346 def remove(self, value):
347 _deque_guard(self)
348 i = 0
349 try:
350 for i in range(len(self)): # noqa: B007
351 self_value = self[0]
352 if self_value is value or self_value == value:
353 deque.popleft(self)
354 return
355 deque.append(self, deque.popleft(self))
356 i += 1
357 raise ValueError("deque.remove(x): x not in deque")
358 finally:
359 deque.rotate(self, i)
360
361 def reverse(self):
362 _builtin()
363
364 def rotate(self, n=1):
365 _deque_guard(self)
366 _int_guard(n)
367 length = len(self)
368 if length <= 1:
369 return
370 halflen = length >> 1
371 if n > halflen or n < -halflen:
372 n %= length
373 if n > halflen:
374 n -= length
375 elif n < -halflen:
376 n += length
377 while n > 0:
378 deque.appendleft(self, deque.pop(self))
379 n -= 1
380 while n < 0:
381 deque.append(self, deque.popleft(self))
382 n += 1