blob: ba6a9b8e902577787d1d77728241a182f2f403b1 [file] [log] [blame]
Guido van Rossumcd16bf62007-06-13 18:07:49 +00001# Copyright 2007 Google, Inc. All Rights Reserved.
2# Licensed to PSF under a Contributor Agreement.
3
4"""Abstract Base Classes (ABCs) for collections, according to PEP 3119.
5
Raymond Hettinger158c9c22011-02-22 00:41:50 +00006Unit tests are in test_collections.
Guido van Rossumcd16bf62007-06-13 18:07:49 +00007"""
8
9from abc import ABCMeta, abstractmethod
Benjamin Peterson41181742008-07-02 20:22:54 +000010import sys
Guido van Rossumcd16bf62007-06-13 18:07:49 +000011
Yury Selivanove0104ae2015-05-14 12:19:16 -040012__all__ = ["Awaitable", "Coroutine", "AsyncIterable", "AsyncIterator",
Yury Selivanov75445082015-05-11 22:57:16 -040013 "Hashable", "Iterable", "Iterator", "Generator",
Guido van Rossumcd16bf62007-06-13 18:07:49 +000014 "Sized", "Container", "Callable",
15 "Set", "MutableSet",
16 "Mapping", "MutableMapping",
17 "MappingView", "KeysView", "ItemsView", "ValuesView",
18 "Sequence", "MutableSequence",
Guido van Rossumd05eb002007-11-21 22:26:24 +000019 "ByteString",
Guido van Rossumcd16bf62007-06-13 18:07:49 +000020 ]
21
Christian Heimesbf235bd2013-10-13 02:21:33 +020022# This module has been renamed from collections.abc to _collections_abc to
23# speed up interpreter startup. Some of the types such as MutableMapping are
24# required early but collections module imports a lot of other modules.
25# See issue #19218
26__name__ = "collections.abc"
27
Raymond Hettinger02184282012-04-05 13:31:12 -070028# Private list of types that we want to register with the various ABCs
29# so that they will pass tests like:
30# it = iter(somebytearray)
31# assert isinstance(it, Iterable)
32# Note: in other implementations, these types many not be distinct
33# and they make have their own implementation specific types that
34# are not included on this list.
Christian Heimesf83be4e2007-11-28 09:44:38 +000035bytes_iterator = type(iter(b''))
36bytearray_iterator = type(iter(bytearray()))
37#callable_iterator = ???
38dict_keyiterator = type(iter({}.keys()))
39dict_valueiterator = type(iter({}.values()))
40dict_itemiterator = type(iter({}.items()))
41list_iterator = type(iter([]))
42list_reverseiterator = type(iter(reversed([])))
43range_iterator = type(iter(range(0)))
44set_iterator = type(iter(set()))
45str_iterator = type(iter(""))
46tuple_iterator = type(iter(()))
47zip_iterator = type(iter(zip()))
48## views ##
49dict_keys = type({}.keys())
50dict_values = type({}.values())
51dict_items = type({}.items())
Christian Heimes0db38532007-11-29 16:21:13 +000052## misc ##
Victor Stinner7b17a4e2012-04-20 01:41:36 +020053mappingproxy = type(type.__dict__)
Raymond Hettingerbd60e8d2015-05-09 01:07:23 -040054generator = type((lambda: (yield))())
Yury Selivanov5376ba92015-06-22 12:19:30 -040055## coroutine ##
56async def _coro(): pass
57_coro = _coro()
58coroutine = type(_coro)
59_coro.close() # Prevent ResourceWarning
60del _coro
Christian Heimesf83be4e2007-11-28 09:44:38 +000061
62
Guido van Rossumcd16bf62007-06-13 18:07:49 +000063### ONE-TRICK PONIES ###
64
65class Hashable(metaclass=ABCMeta):
66
Raymond Hettingerc46759a2011-03-22 11:46:25 -070067 __slots__ = ()
68
Guido van Rossumcd16bf62007-06-13 18:07:49 +000069 @abstractmethod
70 def __hash__(self):
71 return 0
72
73 @classmethod
74 def __subclasshook__(cls, C):
75 if cls is Hashable:
76 for B in C.__mro__:
77 if "__hash__" in B.__dict__:
78 if B.__dict__["__hash__"]:
79 return True
80 break
81 return NotImplemented
82
83
Yury Selivanov56fc6142015-05-29 09:01:29 -040084class _AwaitableMeta(ABCMeta):
Yury Selivanov75445082015-05-11 22:57:16 -040085
86 def __instancecheck__(cls, instance):
Yury Selivanov5376ba92015-06-22 12:19:30 -040087 # This hook is needed because we can't add
88 # '__await__' method to generator objects, and
89 # we can't register GeneratorType on Awaitable.
90 # NB: 0x100 = CO_ITERABLE_COROUTINE
91 # (We don't want to import 'inspect' module, as
92 # a dependency for 'collections.abc')
93 if (instance.__class__ is generator and
94 instance.gi_code.co_flags & 0x100):
Yury Selivanov75445082015-05-11 22:57:16 -040095 return True
Yury Selivanov75445082015-05-11 22:57:16 -040096 return super().__instancecheck__(instance)
97
98
Yury Selivanov56fc6142015-05-29 09:01:29 -040099class Awaitable(metaclass=_AwaitableMeta):
100
101 __slots__ = ()
102
103 @abstractmethod
104 def __await__(self):
105 yield
106
107 @classmethod
108 def __subclasshook__(cls, C):
109 if cls is Awaitable:
110 for B in C.__mro__:
111 if "__await__" in B.__dict__:
112 if B.__dict__["__await__"]:
113 return True
114 break
115 return NotImplemented
116
117
118class Coroutine(Awaitable):
Yury Selivanov75445082015-05-11 22:57:16 -0400119
120 __slots__ = ()
121
122 @abstractmethod
123 def send(self, value):
124 """Send a value into the coroutine.
125 Return next yielded value or raise StopIteration.
126 """
127 raise StopIteration
128
129 @abstractmethod
130 def throw(self, typ, val=None, tb=None):
131 """Raise an exception in the coroutine.
132 Return next yielded value or raise StopIteration.
133 """
134 if val is None:
135 if tb is None:
136 raise typ
137 val = typ()
138 if tb is not None:
139 val = val.with_traceback(tb)
140 raise val
141
142 def close(self):
143 """Raise GeneratorExit inside coroutine.
144 """
145 try:
146 self.throw(GeneratorExit)
147 except (GeneratorExit, StopIteration):
148 pass
149 else:
150 raise RuntimeError("coroutine ignored GeneratorExit")
151
Yury Selivanov75445082015-05-11 22:57:16 -0400152 @classmethod
153 def __subclasshook__(cls, C):
Yury Selivanov56fc6142015-05-29 09:01:29 -0400154 if cls is Coroutine:
155 mro = C.__mro__
156 for method in ('__await__', 'send', 'throw', 'close'):
157 for base in mro:
158 if method in base.__dict__:
159 break
160 else:
161 return NotImplemented
162 return True
Yury Selivanov75445082015-05-11 22:57:16 -0400163 return NotImplemented
164
Yury Selivanov75445082015-05-11 22:57:16 -0400165
Yury Selivanov5376ba92015-06-22 12:19:30 -0400166Coroutine.register(coroutine)
167
168
Yury Selivanove0104ae2015-05-14 12:19:16 -0400169class AsyncIterable(metaclass=ABCMeta):
170
171 __slots__ = ()
172
173 @abstractmethod
174 async def __aiter__(self):
175 return AsyncIterator()
176
177 @classmethod
178 def __subclasshook__(cls, C):
179 if cls is AsyncIterable:
180 if any("__aiter__" in B.__dict__ for B in C.__mro__):
181 return True
182 return NotImplemented
183
184
185class AsyncIterator(AsyncIterable):
186
187 __slots__ = ()
188
189 @abstractmethod
190 async def __anext__(self):
191 """Return the next item or raise StopAsyncIteration when exhausted."""
192 raise StopAsyncIteration
193
194 async def __aiter__(self):
195 return self
196
197 @classmethod
198 def __subclasshook__(cls, C):
199 if cls is AsyncIterator:
200 if (any("__anext__" in B.__dict__ for B in C.__mro__) and
201 any("__aiter__" in B.__dict__ for B in C.__mro__)):
202 return True
203 return NotImplemented
204
205
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000206class Iterable(metaclass=ABCMeta):
207
Raymond Hettingerc46759a2011-03-22 11:46:25 -0700208 __slots__ = ()
209
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000210 @abstractmethod
211 def __iter__(self):
212 while False:
213 yield None
214
215 @classmethod
216 def __subclasshook__(cls, C):
217 if cls is Iterable:
218 if any("__iter__" in B.__dict__ for B in C.__mro__):
219 return True
220 return NotImplemented
221
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000222
Raymond Hettinger74b64952008-02-09 02:53:48 +0000223class Iterator(Iterable):
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000224
Raymond Hettingerc46759a2011-03-22 11:46:25 -0700225 __slots__ = ()
226
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000227 @abstractmethod
228 def __next__(self):
Raymond Hettinger153866e2013-03-24 15:20:29 -0700229 'Return the next item from the iterator. When exhausted, raise StopIteration'
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000230 raise StopIteration
231
232 def __iter__(self):
233 return self
234
235 @classmethod
236 def __subclasshook__(cls, C):
237 if cls is Iterator:
Raymond Hettingeread22222010-11-29 03:56:12 +0000238 if (any("__next__" in B.__dict__ for B in C.__mro__) and
239 any("__iter__" in B.__dict__ for B in C.__mro__)):
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000240 return True
241 return NotImplemented
242
Christian Heimesf83be4e2007-11-28 09:44:38 +0000243Iterator.register(bytes_iterator)
244Iterator.register(bytearray_iterator)
245#Iterator.register(callable_iterator)
246Iterator.register(dict_keyiterator)
247Iterator.register(dict_valueiterator)
248Iterator.register(dict_itemiterator)
249Iterator.register(list_iterator)
250Iterator.register(list_reverseiterator)
251Iterator.register(range_iterator)
252Iterator.register(set_iterator)
253Iterator.register(str_iterator)
254Iterator.register(tuple_iterator)
255Iterator.register(zip_iterator)
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000256
Raymond Hettingerbd60e8d2015-05-09 01:07:23 -0400257
258class Generator(Iterator):
259
260 __slots__ = ()
261
262 def __next__(self):
263 """Return the next item from the generator.
264 When exhausted, raise StopIteration.
265 """
266 return self.send(None)
267
268 @abstractmethod
269 def send(self, value):
270 """Send a value into the generator.
271 Return next yielded value or raise StopIteration.
272 """
273 raise StopIteration
274
275 @abstractmethod
276 def throw(self, typ, val=None, tb=None):
277 """Raise an exception in the generator.
278 Return next yielded value or raise StopIteration.
279 """
280 if val is None:
281 if tb is None:
282 raise typ
283 val = typ()
284 if tb is not None:
285 val = val.with_traceback(tb)
286 raise val
287
288 def close(self):
289 """Raise GeneratorExit inside generator.
290 """
291 try:
292 self.throw(GeneratorExit)
293 except (GeneratorExit, StopIteration):
294 pass
295 else:
296 raise RuntimeError("generator ignored GeneratorExit")
297
298 @classmethod
299 def __subclasshook__(cls, C):
300 if cls is Generator:
301 mro = C.__mro__
302 for method in ('__iter__', '__next__', 'send', 'throw', 'close'):
303 for base in mro:
304 if method in base.__dict__:
305 break
306 else:
307 return NotImplemented
308 return True
309 return NotImplemented
310
311
312Generator.register(generator)
313
314
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000315class Sized(metaclass=ABCMeta):
316
Raymond Hettingerc46759a2011-03-22 11:46:25 -0700317 __slots__ = ()
318
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000319 @abstractmethod
320 def __len__(self):
321 return 0
322
323 @classmethod
324 def __subclasshook__(cls, C):
325 if cls is Sized:
326 if any("__len__" in B.__dict__ for B in C.__mro__):
327 return True
328 return NotImplemented
329
330
331class Container(metaclass=ABCMeta):
332
Raymond Hettingerc46759a2011-03-22 11:46:25 -0700333 __slots__ = ()
334
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000335 @abstractmethod
336 def __contains__(self, x):
337 return False
338
339 @classmethod
340 def __subclasshook__(cls, C):
341 if cls is Container:
342 if any("__contains__" in B.__dict__ for B in C.__mro__):
343 return True
344 return NotImplemented
345
346
347class Callable(metaclass=ABCMeta):
348
Raymond Hettingerc46759a2011-03-22 11:46:25 -0700349 __slots__ = ()
350
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000351 @abstractmethod
Christian Heimes78644762008-03-04 23:39:23 +0000352 def __call__(self, *args, **kwds):
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000353 return False
354
355 @classmethod
356 def __subclasshook__(cls, C):
357 if cls is Callable:
358 if any("__call__" in B.__dict__ for B in C.__mro__):
359 return True
360 return NotImplemented
361
362
363### SETS ###
364
365
Raymond Hettinger74b64952008-02-09 02:53:48 +0000366class Set(Sized, Iterable, Container):
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000367
368 """A set is a finite, iterable container.
369
370 This class provides concrete generic implementations of all
371 methods except for __contains__, __iter__ and __len__.
372
373 To override the comparisons (presumably for speed, as the
Raymond Hettinger11cda472014-07-03 00:31:30 +0100374 semantics are fixed), redefine __le__ and __ge__,
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000375 then the other operations will automatically follow suit.
376 """
377
Raymond Hettingerc46759a2011-03-22 11:46:25 -0700378 __slots__ = ()
379
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000380 def __le__(self, other):
381 if not isinstance(other, Set):
382 return NotImplemented
383 if len(self) > len(other):
384 return False
385 for elem in self:
386 if elem not in other:
387 return False
388 return True
389
390 def __lt__(self, other):
391 if not isinstance(other, Set):
392 return NotImplemented
393 return len(self) < len(other) and self.__le__(other)
394
Raymond Hettinger71909422008-02-09 00:08:16 +0000395 def __gt__(self, other):
396 if not isinstance(other, Set):
397 return NotImplemented
Raymond Hettingerdd5e53a2014-05-26 00:09:04 -0700398 return len(self) > len(other) and self.__ge__(other)
Raymond Hettinger71909422008-02-09 00:08:16 +0000399
400 def __ge__(self, other):
401 if not isinstance(other, Set):
402 return NotImplemented
Raymond Hettingerdd5e53a2014-05-26 00:09:04 -0700403 if len(self) < len(other):
404 return False
405 for elem in other:
406 if elem not in self:
407 return False
408 return True
Raymond Hettinger71909422008-02-09 00:08:16 +0000409
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000410 def __eq__(self, other):
411 if not isinstance(other, Set):
412 return NotImplemented
413 return len(self) == len(other) and self.__le__(other)
414
415 @classmethod
416 def _from_iterable(cls, it):
Raymond Hettinger8284c4a2008-02-06 20:47:09 +0000417 '''Construct an instance of the class from any iterable input.
418
419 Must override this method if the class constructor signature
Raymond Hettinger7aebb642008-02-09 03:25:08 +0000420 does not accept an iterable for an input.
Raymond Hettinger8284c4a2008-02-06 20:47:09 +0000421 '''
Raymond Hettinger7aebb642008-02-09 03:25:08 +0000422 return cls(it)
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000423
424 def __and__(self, other):
425 if not isinstance(other, Iterable):
426 return NotImplemented
427 return self._from_iterable(value for value in other if value in self)
428
Raymond Hettingerdd5e53a2014-05-26 00:09:04 -0700429 __rand__ = __and__
430
Christian Heimes190d79e2008-01-30 11:58:22 +0000431 def isdisjoint(self, other):
Raymond Hettinger153866e2013-03-24 15:20:29 -0700432 'Return True if two sets have a null intersection.'
Christian Heimes190d79e2008-01-30 11:58:22 +0000433 for value in other:
434 if value in self:
435 return False
436 return True
437
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000438 def __or__(self, other):
439 if not isinstance(other, Iterable):
440 return NotImplemented
Christian Heimes78644762008-03-04 23:39:23 +0000441 chain = (e for s in (self, other) for e in s)
442 return self._from_iterable(chain)
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000443
Raymond Hettingerdd5e53a2014-05-26 00:09:04 -0700444 __ror__ = __or__
445
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000446 def __sub__(self, other):
447 if not isinstance(other, Set):
448 if not isinstance(other, Iterable):
449 return NotImplemented
450 other = self._from_iterable(other)
451 return self._from_iterable(value for value in self
452 if value not in other)
453
Raymond Hettingerdd5e53a2014-05-26 00:09:04 -0700454 def __rsub__(self, other):
455 if not isinstance(other, Set):
456 if not isinstance(other, Iterable):
457 return NotImplemented
458 other = self._from_iterable(other)
459 return self._from_iterable(value for value in other
460 if value not in self)
461
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000462 def __xor__(self, other):
463 if not isinstance(other, Set):
464 if not isinstance(other, Iterable):
465 return NotImplemented
466 other = self._from_iterable(other)
467 return (self - other) | (other - self)
468
Raymond Hettingerdd5e53a2014-05-26 00:09:04 -0700469 __rxor__ = __xor__
470
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000471 def _hash(self):
472 """Compute the hash value of a set.
473
474 Note that we don't define __hash__: not all sets are hashable.
475 But if you define a hashable set type, its __hash__ should
476 call this function.
477
478 This must be compatible __eq__.
479
480 All sets ought to compare equal if they contain the same
481 elements, regardless of how they are implemented, and
482 regardless of the order of the elements; so there's not much
483 freedom for __eq__ or __hash__. We match the algorithm used
484 by the built-in frozenset type.
485 """
Christian Heimesa37d4c62007-12-04 23:02:19 +0000486 MAX = sys.maxsize
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000487 MASK = 2 * MAX + 1
488 n = len(self)
489 h = 1927868237 * (n + 1)
490 h &= MASK
491 for x in self:
492 hx = hash(x)
493 h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167
494 h &= MASK
495 h = h * 69069 + 907133923
496 h &= MASK
497 if h > MAX:
498 h -= MASK + 1
499 if h == -1:
500 h = 590923713
501 return h
502
503Set.register(frozenset)
504
505
506class MutableSet(Set):
Raymond Hettinger153866e2013-03-24 15:20:29 -0700507 """A mutable set is a finite, iterable container.
508
509 This class provides concrete generic implementations of all
510 methods except for __contains__, __iter__, __len__,
511 add(), and discard().
512
513 To override the comparisons (presumably for speed, as the
514 semantics are fixed), all you have to do is redefine __le__ and
515 then the other operations will automatically follow suit.
516 """
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000517
Raymond Hettingerc46759a2011-03-22 11:46:25 -0700518 __slots__ = ()
519
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000520 @abstractmethod
521 def add(self, value):
Benjamin Peterson058e31e2009-01-16 03:54:08 +0000522 """Add an element."""
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000523 raise NotImplementedError
524
525 @abstractmethod
526 def discard(self, value):
Benjamin Peterson058e31e2009-01-16 03:54:08 +0000527 """Remove an element. Do not raise an exception if absent."""
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000528 raise NotImplementedError
529
Christian Heimes190d79e2008-01-30 11:58:22 +0000530 def remove(self, value):
531 """Remove an element. If not a member, raise a KeyError."""
532 if value not in self:
533 raise KeyError(value)
534 self.discard(value)
535
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000536 def pop(self):
537 """Return the popped value. Raise KeyError if empty."""
538 it = iter(self)
539 try:
Raymond Hettingerae650182009-01-28 23:33:59 +0000540 value = next(it)
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000541 except StopIteration:
542 raise KeyError
543 self.discard(value)
544 return value
545
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000546 def clear(self):
547 """This is slow (creates N new iterators!) but effective."""
548 try:
549 while True:
550 self.pop()
551 except KeyError:
552 pass
553
Raymond Hettingerb3d89a42011-01-12 20:37:47 +0000554 def __ior__(self, it):
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000555 for value in it:
556 self.add(value)
557 return self
558
Raymond Hettingerb3d89a42011-01-12 20:37:47 +0000559 def __iand__(self, it):
Raymond Hettinger3f10a952009-04-01 19:05:50 +0000560 for value in (self - it):
561 self.discard(value)
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000562 return self
563
Raymond Hettingerb3d89a42011-01-12 20:37:47 +0000564 def __ixor__(self, it):
Daniel Stutzbach31da5b22010-08-24 20:49:57 +0000565 if it is self:
566 self.clear()
567 else:
568 if not isinstance(it, Set):
569 it = self._from_iterable(it)
570 for value in it:
571 if value in self:
572 self.discard(value)
573 else:
574 self.add(value)
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000575 return self
576
Raymond Hettingerb3d89a42011-01-12 20:37:47 +0000577 def __isub__(self, it):
Daniel Stutzbach31da5b22010-08-24 20:49:57 +0000578 if it is self:
579 self.clear()
580 else:
581 for value in it:
582 self.discard(value)
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000583 return self
584
585MutableSet.register(set)
586
587
588### MAPPINGS ###
589
590
Raymond Hettinger74b64952008-02-09 02:53:48 +0000591class Mapping(Sized, Iterable, Container):
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000592
Raymond Hettingerc46759a2011-03-22 11:46:25 -0700593 __slots__ = ()
594
Raymond Hettinger153866e2013-03-24 15:20:29 -0700595 """A Mapping is a generic container for associating key/value
596 pairs.
597
598 This class provides concrete generic implementations of all
599 methods except for __getitem__, __iter__, and __len__.
600
601 """
602
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000603 @abstractmethod
604 def __getitem__(self, key):
605 raise KeyError
606
607 def get(self, key, default=None):
Raymond Hettinger153866e2013-03-24 15:20:29 -0700608 'D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.'
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000609 try:
610 return self[key]
611 except KeyError:
612 return default
613
614 def __contains__(self, key):
615 try:
616 self[key]
617 except KeyError:
618 return False
619 else:
620 return True
621
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000622 def keys(self):
Raymond Hettinger153866e2013-03-24 15:20:29 -0700623 "D.keys() -> a set-like object providing a view on D's keys"
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000624 return KeysView(self)
625
626 def items(self):
Raymond Hettinger153866e2013-03-24 15:20:29 -0700627 "D.items() -> a set-like object providing a view on D's items"
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000628 return ItemsView(self)
629
630 def values(self):
Raymond Hettinger153866e2013-03-24 15:20:29 -0700631 "D.values() -> an object providing a view on D's values"
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000632 return ValuesView(self)
633
Raymond Hettingerb9da9bc2008-02-04 20:44:31 +0000634 def __eq__(self, other):
Benjamin Peterson4ad6bd52010-05-21 20:55:22 +0000635 if not isinstance(other, Mapping):
636 return NotImplemented
637 return dict(self.items()) == dict(other.items())
Raymond Hettingerb9da9bc2008-02-04 20:44:31 +0000638
Victor Stinner7b17a4e2012-04-20 01:41:36 +0200639Mapping.register(mappingproxy)
640
Christian Heimes2202f872008-02-06 14:31:34 +0000641
Raymond Hettingerbfd06122008-02-09 10:04:32 +0000642class MappingView(Sized):
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000643
Raymond Hettinger3170d1c2014-05-03 19:06:32 -0700644 __slots__ = '_mapping',
645
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000646 def __init__(self, mapping):
647 self._mapping = mapping
648
649 def __len__(self):
650 return len(self._mapping)
651
Raymond Hettinger89fc2b72009-02-27 07:47:32 +0000652 def __repr__(self):
653 return '{0.__class__.__name__}({0._mapping!r})'.format(self)
654
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000655
656class KeysView(MappingView, Set):
657
Raymond Hettinger3170d1c2014-05-03 19:06:32 -0700658 __slots__ = ()
659
Raymond Hettinger9117c752010-08-22 07:44:24 +0000660 @classmethod
661 def _from_iterable(self, it):
662 return set(it)
663
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000664 def __contains__(self, key):
665 return key in self._mapping
666
667 def __iter__(self):
Philip Jenvey4993cc02012-10-01 12:53:43 -0700668 yield from self._mapping
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000669
Christian Heimesf83be4e2007-11-28 09:44:38 +0000670KeysView.register(dict_keys)
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000671
672
673class ItemsView(MappingView, Set):
674
Raymond Hettinger3170d1c2014-05-03 19:06:32 -0700675 __slots__ = ()
676
Raymond Hettinger9117c752010-08-22 07:44:24 +0000677 @classmethod
678 def _from_iterable(self, it):
679 return set(it)
680
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000681 def __contains__(self, item):
682 key, value = item
683 try:
684 v = self._mapping[key]
685 except KeyError:
686 return False
687 else:
688 return v == value
689
690 def __iter__(self):
691 for key in self._mapping:
692 yield (key, self._mapping[key])
693
Christian Heimesf83be4e2007-11-28 09:44:38 +0000694ItemsView.register(dict_items)
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000695
696
697class ValuesView(MappingView):
698
Raymond Hettinger3170d1c2014-05-03 19:06:32 -0700699 __slots__ = ()
700
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000701 def __contains__(self, value):
702 for key in self._mapping:
703 if value == self._mapping[key]:
704 return True
705 return False
706
707 def __iter__(self):
708 for key in self._mapping:
709 yield self._mapping[key]
710
Christian Heimesf83be4e2007-11-28 09:44:38 +0000711ValuesView.register(dict_values)
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000712
713
714class MutableMapping(Mapping):
715
Raymond Hettingerc46759a2011-03-22 11:46:25 -0700716 __slots__ = ()
717
Raymond Hettinger153866e2013-03-24 15:20:29 -0700718 """A MutableMapping is a generic container for associating
719 key/value pairs.
720
721 This class provides concrete generic implementations of all
722 methods except for __getitem__, __setitem__, __delitem__,
723 __iter__, and __len__.
724
725 """
726
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000727 @abstractmethod
728 def __setitem__(self, key, value):
729 raise KeyError
730
731 @abstractmethod
732 def __delitem__(self, key):
733 raise KeyError
734
735 __marker = object()
736
737 def pop(self, key, default=__marker):
Raymond Hettinger153866e2013-03-24 15:20:29 -0700738 '''D.pop(k[,d]) -> v, remove specified key and return the corresponding value.
739 If key is not found, d is returned if given, otherwise KeyError is raised.
740 '''
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000741 try:
742 value = self[key]
743 except KeyError:
744 if default is self.__marker:
745 raise
746 return default
747 else:
748 del self[key]
749 return value
750
751 def popitem(self):
Raymond Hettinger153866e2013-03-24 15:20:29 -0700752 '''D.popitem() -> (k, v), remove and return some (key, value) pair
753 as a 2-tuple; but raise KeyError if D is empty.
754 '''
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000755 try:
756 key = next(iter(self))
757 except StopIteration:
758 raise KeyError
759 value = self[key]
760 del self[key]
761 return key, value
762
763 def clear(self):
Raymond Hettinger153866e2013-03-24 15:20:29 -0700764 'D.clear() -> None. Remove all items from D.'
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000765 try:
766 while True:
767 self.popitem()
768 except KeyError:
769 pass
770
Mark Dickinsonb214e902010-07-11 18:53:06 +0000771 def update(*args, **kwds):
Raymond Hettinger153866e2013-03-24 15:20:29 -0700772 ''' D.update([E, ]**F) -> None. Update D from mapping/iterable E and F.
773 If E present and has a .keys() method, does: for k in E: D[k] = E[k]
774 If E present and lacks .keys() method, does: for (k, v) in E: D[k] = v
775 In either case, this is followed by: for k, v in F.items(): D[k] = v
776 '''
Serhiy Storchakaae5cb212014-11-27 16:25:51 +0200777 if not args:
778 raise TypeError("descriptor 'update' of 'MutableMapping' object "
779 "needs an argument")
780 self, *args = args
781 if len(args) > 1:
782 raise TypeError('update expected at most 1 arguments, got %d' %
783 len(args))
784 if args:
785 other = args[0]
786 if isinstance(other, Mapping):
787 for key in other:
788 self[key] = other[key]
789 elif hasattr(other, "keys"):
790 for key in other.keys():
791 self[key] = other[key]
792 else:
793 for key, value in other:
794 self[key] = value
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000795 for key, value in kwds.items():
796 self[key] = value
797
Raymond Hettingerb9da9bc2008-02-04 20:44:31 +0000798 def setdefault(self, key, default=None):
Raymond Hettinger153866e2013-03-24 15:20:29 -0700799 'D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D'
Raymond Hettingerb9da9bc2008-02-04 20:44:31 +0000800 try:
801 return self[key]
802 except KeyError:
803 self[key] = default
804 return default
805
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000806MutableMapping.register(dict)
807
808
809### SEQUENCES ###
810
811
Raymond Hettinger74b64952008-02-09 02:53:48 +0000812class Sequence(Sized, Iterable, Container):
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000813
814 """All the operations on a read-only sequence.
815
816 Concrete subclasses must override __new__ or __init__,
817 __getitem__, and __len__.
818 """
819
Raymond Hettingerc46759a2011-03-22 11:46:25 -0700820 __slots__ = ()
821
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000822 @abstractmethod
823 def __getitem__(self, index):
824 raise IndexError
825
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000826 def __iter__(self):
827 i = 0
Raymond Hettinger71909422008-02-09 00:08:16 +0000828 try:
829 while True:
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000830 v = self[i]
Raymond Hettinger71909422008-02-09 00:08:16 +0000831 yield v
832 i += 1
833 except IndexError:
834 return
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000835
836 def __contains__(self, value):
837 for v in self:
838 if v == value:
839 return True
840 return False
841
842 def __reversed__(self):
843 for i in reversed(range(len(self))):
844 yield self[i]
845
Raymond Hettingerec219ba2015-05-22 19:29:22 -0700846 def index(self, value, start=0, stop=None):
847 '''S.index(value, [start, [stop]]) -> integer -- return first index of value.
Raymond Hettinger153866e2013-03-24 15:20:29 -0700848 Raises ValueError if the value is not present.
849 '''
Raymond Hettingerec219ba2015-05-22 19:29:22 -0700850 if start is not None and start < 0:
851 start = max(len(self) + start, 0)
852 if stop is not None and stop < 0:
853 stop += len(self)
854
855 i = start
856 while stop is None or i < stop:
857 try:
858 if self[i] == value:
859 return i
860 except IndexError:
861 break
862 i += 1
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000863 raise ValueError
864
865 def count(self, value):
Raymond Hettinger153866e2013-03-24 15:20:29 -0700866 'S.count(value) -> integer -- return number of occurrences of value'
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000867 return sum(1 for v in self if v == value)
868
869Sequence.register(tuple)
Guido van Rossum3172c5d2007-10-16 18:12:55 +0000870Sequence.register(str)
Raymond Hettinger9aa53c22009-02-24 11:25:35 +0000871Sequence.register(range)
Nick Coghlan45163cc2013-10-02 22:31:47 +1000872Sequence.register(memoryview)
Guido van Rossumd05eb002007-11-21 22:26:24 +0000873
874
875class ByteString(Sequence):
876
877 """This unifies bytes and bytearray.
878
879 XXX Should add all their methods.
880 """
881
Raymond Hettingerc46759a2011-03-22 11:46:25 -0700882 __slots__ = ()
883
Guido van Rossumd05eb002007-11-21 22:26:24 +0000884ByteString.register(bytes)
885ByteString.register(bytearray)
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000886
887
888class MutableSequence(Sequence):
889
Raymond Hettingerc46759a2011-03-22 11:46:25 -0700890 __slots__ = ()
891
Guido van Rossum840c3102013-07-25 11:55:41 -0700892 """All the operations on a read-write sequence.
Raymond Hettinger153866e2013-03-24 15:20:29 -0700893
894 Concrete subclasses must provide __new__ or __init__,
895 __getitem__, __setitem__, __delitem__, __len__, and insert().
896
897 """
898
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000899 @abstractmethod
900 def __setitem__(self, index, value):
901 raise IndexError
902
903 @abstractmethod
904 def __delitem__(self, index):
905 raise IndexError
906
907 @abstractmethod
908 def insert(self, index, value):
Raymond Hettinger153866e2013-03-24 15:20:29 -0700909 'S.insert(index, value) -- insert value before index'
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000910 raise IndexError
911
912 def append(self, value):
Raymond Hettinger153866e2013-03-24 15:20:29 -0700913 'S.append(value) -- append value to the end of the sequence'
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000914 self.insert(len(self), value)
915
Eli Bendersky9479d1a2011-03-04 05:34:58 +0000916 def clear(self):
Raymond Hettinger153866e2013-03-24 15:20:29 -0700917 'S.clear() -> None -- remove all items from S'
Eli Bendersky9479d1a2011-03-04 05:34:58 +0000918 try:
919 while True:
920 self.pop()
921 except IndexError:
922 pass
923
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000924 def reverse(self):
Raymond Hettinger153866e2013-03-24 15:20:29 -0700925 'S.reverse() -- reverse *IN PLACE*'
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000926 n = len(self)
927 for i in range(n//2):
928 self[i], self[n-i-1] = self[n-i-1], self[i]
929
930 def extend(self, values):
Raymond Hettinger153866e2013-03-24 15:20:29 -0700931 'S.extend(iterable) -- extend sequence by appending elements from the iterable'
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000932 for v in values:
933 self.append(v)
934
935 def pop(self, index=-1):
Raymond Hettinger153866e2013-03-24 15:20:29 -0700936 '''S.pop([index]) -> item -- remove and return item at index (default last).
937 Raise IndexError if list is empty or index is out of range.
938 '''
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000939 v = self[index]
940 del self[index]
941 return v
942
943 def remove(self, value):
Raymond Hettinger153866e2013-03-24 15:20:29 -0700944 '''S.remove(value) -- remove first occurrence of value.
945 Raise ValueError if the value is not present.
946 '''
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000947 del self[self.index(value)]
948
949 def __iadd__(self, values):
950 self.extend(values)
Raymond Hettingerc384b222009-05-18 15:35:26 +0000951 return self
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000952
953MutableSequence.register(list)
Guido van Rossumd05eb002007-11-21 22:26:24 +0000954MutableSequence.register(bytearray) # Multiply inheriting, see ByteString