Python code coverage for Lib/_collections_abc.py

#	count	content
1	n/a	# Copyright 2007 Google, Inc. All Rights Reserved.
2	n/a	# Licensed to PSF under a Contributor Agreement.
3	n/a
4	n/a	"""Abstract Base Classes (ABCs) for collections, according to PEP 3119.
5	n/a
6	n/a	Unit tests are in test_collections.
7	n/a	"""
8	n/a
9	n/a	from abc import ABCMeta, abstractmethod
10	n/a	import sys
11	n/a
12	n/a	__all__ = ["Awaitable", "Coroutine",
13	n/a	"AsyncIterable", "AsyncIterator", "AsyncGenerator",
14	n/a	"Hashable", "Iterable", "Iterator", "Generator", "Reversible",
15	n/a	"Sized", "Container", "Callable", "Collection",
16	n/a	"Set", "MutableSet",
17	n/a	"Mapping", "MutableMapping",
18	n/a	"MappingView", "KeysView", "ItemsView", "ValuesView",
19	n/a	"Sequence", "MutableSequence",
20	n/a	"ByteString",
21	n/a	]
22	n/a
23	n/a	# This module has been renamed from collections.abc to _collections_abc to
24	n/a	# speed up interpreter startup. Some of the types such as MutableMapping are
25	n/a	# required early but collections module imports a lot of other modules.
26	n/a	# See issue #19218
27	n/a	__name__ = "collections.abc"
28	n/a
29	n/a	# Private list of types that we want to register with the various ABCs
30	n/a	# so that they will pass tests like:
31	n/a	# it = iter(somebytearray)
32	n/a	# assert isinstance(it, Iterable)
33	n/a	# Note: in other implementations, these types might not be distinct
34	n/a	# and they may have their own implementation specific types that
35	n/a	# are not included on this list.
36	n/a	bytes_iterator = type(iter(b''))
37	n/a	bytearray_iterator = type(iter(bytearray()))
38	n/a	#callable_iterator = ???
39	n/a	dict_keyiterator = type(iter({}.keys()))
40	n/a	dict_valueiterator = type(iter({}.values()))
41	n/a	dict_itemiterator = type(iter({}.items()))
42	n/a	list_iterator = type(iter([]))
43	n/a	list_reverseiterator = type(iter(reversed([])))
44	n/a	range_iterator = type(iter(range(0)))
45	n/a	longrange_iterator = type(iter(range(1 << 1000)))
46	n/a	set_iterator = type(iter(set()))
47	n/a	str_iterator = type(iter(""))
48	n/a	tuple_iterator = type(iter(()))
49	n/a	zip_iterator = type(iter(zip()))
50	n/a	## views ##
51	n/a	dict_keys = type({}.keys())
52	n/a	dict_values = type({}.values())
53	n/a	dict_items = type({}.items())
54	n/a	## misc ##
55	n/a	mappingproxy = type(type.__dict__)
56	n/a	generator = type((lambda: (yield))())
57	n/a	## coroutine ##
58	n/a	async def _coro(): pass
59	n/a	_coro = _coro()
60	n/a	coroutine = type(_coro)
61	n/a	_coro.close() # Prevent ResourceWarning
62	n/a	del _coro
63	n/a	## asynchronous generator ##
64	n/a	async def _ag(): yield
65	n/a	_ag = _ag()
66	n/a	async_generator = type(_ag)
67	n/a	del _ag
68	n/a
69	n/a
70	n/a	### ONE-TRICK PONIES ###
71	n/a
72	n/a	def _check_methods(C, *methods):
73	n/a	mro = C.__mro__
74	n/a	for method in methods:
75	n/a	for B in mro:
76	n/a	if method in B.__dict__:
77	n/a	if B.__dict__[method] is None:
78	n/a	return NotImplemented
79	n/a	break
80	n/a	else:
81	n/a	return NotImplemented
82	n/a	return True
83	n/a
84	n/a	class Hashable(metaclass=ABCMeta):
85	n/a
86	n/a	__slots__ = ()
87	n/a
88	n/a	@abstractmethod
89	n/a	def __hash__(self):
90	n/a	return 0
91	n/a
92	n/a	@classmethod
93	n/a	def __subclasshook__(cls, C):
94	n/a	if cls is Hashable:
95	n/a	return _check_methods(C, "__hash__")
96	n/a	return NotImplemented
97	n/a
98	n/a
99	n/a	class Awaitable(metaclass=ABCMeta):
100	n/a
101	n/a	__slots__ = ()
102	n/a
103	n/a	@abstractmethod
104	n/a	def __await__(self):
105	n/a	yield
106	n/a
107	n/a	@classmethod
108	n/a	def __subclasshook__(cls, C):
109	n/a	if cls is Awaitable:
110	n/a	return _check_methods(C, "__await__")
111	n/a	return NotImplemented
112	n/a
113	n/a
114	n/a	class Coroutine(Awaitable):
115	n/a
116	n/a	__slots__ = ()
117	n/a
118	n/a	@abstractmethod
119	n/a	def send(self, value):
120	n/a	"""Send a value into the coroutine.
121	n/a	Return next yielded value or raise StopIteration.
122	n/a	"""
123	n/a	raise StopIteration
124	n/a
125	n/a	@abstractmethod
126	n/a	def throw(self, typ, val=None, tb=None):
127	n/a	"""Raise an exception in the coroutine.
128	n/a	Return next yielded value or raise StopIteration.
129	n/a	"""
130	n/a	if val is None:
131	n/a	if tb is None:
132	n/a	raise typ
133	n/a	val = typ()
134	n/a	if tb is not None:
135	n/a	val = val.with_traceback(tb)
136	n/a	raise val
137	n/a
138	n/a	def close(self):
139	n/a	"""Raise GeneratorExit inside coroutine.
140	n/a	"""
141	n/a	try:
142	n/a	self.throw(GeneratorExit)
143	n/a	except (GeneratorExit, StopIteration):
144	n/a	pass
145	n/a	else:
146	n/a	raise RuntimeError("coroutine ignored GeneratorExit")
147	n/a
148	n/a	@classmethod
149	n/a	def __subclasshook__(cls, C):
150	n/a	if cls is Coroutine:
151	n/a	return _check_methods(C, '__await__', 'send', 'throw', 'close')
152	n/a	return NotImplemented
153	n/a
154	n/a
155	n/a	Coroutine.register(coroutine)
156	n/a
157	n/a
158	n/a	class AsyncIterable(metaclass=ABCMeta):
159	n/a
160	n/a	__slots__ = ()
161	n/a
162	n/a	@abstractmethod
163	n/a	def __aiter__(self):
164	n/a	return AsyncIterator()
165	n/a
166	n/a	@classmethod
167	n/a	def __subclasshook__(cls, C):
168	n/a	if cls is AsyncIterable:
169	n/a	return _check_methods(C, "__aiter__")
170	n/a	return NotImplemented
171	n/a
172	n/a
173	n/a	class AsyncIterator(AsyncIterable):
174	n/a
175	n/a	__slots__ = ()
176	n/a
177	n/a	@abstractmethod
178	n/a	async def __anext__(self):
179	n/a	"""Return the next item or raise StopAsyncIteration when exhausted."""
180	n/a	raise StopAsyncIteration
181	n/a
182	n/a	def __aiter__(self):
183	n/a	return self
184	n/a
185	n/a	@classmethod
186	n/a	def __subclasshook__(cls, C):
187	n/a	if cls is AsyncIterator:
188	n/a	return _check_methods(C, "__anext__", "__aiter__")
189	n/a	return NotImplemented
190	n/a
191	n/a
192	n/a	class AsyncGenerator(AsyncIterator):
193	n/a
194	n/a	__slots__ = ()
195	n/a
196	n/a	async def __anext__(self):
197	n/a	"""Return the next item from the asynchronous generator.
198	n/a	When exhausted, raise StopAsyncIteration.
199	n/a	"""
200	n/a	return await self.asend(None)
201	n/a
202	n/a	@abstractmethod
203	n/a	async def asend(self, value):
204	n/a	"""Send a value into the asynchronous generator.
205	n/a	Return next yielded value or raise StopAsyncIteration.
206	n/a	"""
207	n/a	raise StopAsyncIteration
208	n/a
209	n/a	@abstractmethod
210	n/a	async def athrow(self, typ, val=None, tb=None):
211	n/a	"""Raise an exception in the asynchronous generator.
212	n/a	Return next yielded value or raise StopAsyncIteration.
213	n/a	"""
214	n/a	if val is None:
215	n/a	if tb is None:
216	n/a	raise typ
217	n/a	val = typ()
218	n/a	if tb is not None:
219	n/a	val = val.with_traceback(tb)
220	n/a	raise val
221	n/a
222	n/a	async def aclose(self):
223	n/a	"""Raise GeneratorExit inside coroutine.
224	n/a	"""
225	n/a	try:
226	n/a	await self.athrow(GeneratorExit)
227	n/a	except (GeneratorExit, StopAsyncIteration):
228	n/a	pass
229	n/a	else:
230	n/a	raise RuntimeError("asynchronous generator ignored GeneratorExit")
231	n/a
232	n/a	@classmethod
233	n/a	def __subclasshook__(cls, C):
234	n/a	if cls is AsyncGenerator:
235	n/a	return _check_methods(C, '__aiter__', '__anext__',
236	n/a	'asend', 'athrow', 'aclose')
237	n/a	return NotImplemented
238	n/a
239	n/a
240	n/a	AsyncGenerator.register(async_generator)
241	n/a
242	n/a
243	n/a	class Iterable(metaclass=ABCMeta):
244	n/a
245	n/a	__slots__ = ()
246	n/a
247	n/a	@abstractmethod
248	n/a	def __iter__(self):
249	n/a	while False:
250	n/a	yield None
251	n/a
252	n/a	@classmethod
253	n/a	def __subclasshook__(cls, C):
254	n/a	if cls is Iterable:
255	n/a	return _check_methods(C, "__iter__")
256	n/a	return NotImplemented
257	n/a
258	n/a
259	n/a	class Iterator(Iterable):
260	n/a
261	n/a	__slots__ = ()
262	n/a
263	n/a	@abstractmethod
264	n/a	def __next__(self):
265	n/a	'Return the next item from the iterator. When exhausted, raise StopIteration'
266	n/a	raise StopIteration
267	n/a
268	n/a	def __iter__(self):
269	n/a	return self
270	n/a
271	n/a	@classmethod
272	n/a	def __subclasshook__(cls, C):
273	n/a	if cls is Iterator:
274	n/a	return _check_methods(C, '__iter__', '__next__')
275	n/a	return NotImplemented
276	n/a
277	n/a	Iterator.register(bytes_iterator)
278	n/a	Iterator.register(bytearray_iterator)
279	n/a	#Iterator.register(callable_iterator)
280	n/a	Iterator.register(dict_keyiterator)
281	n/a	Iterator.register(dict_valueiterator)
282	n/a	Iterator.register(dict_itemiterator)
283	n/a	Iterator.register(list_iterator)
284	n/a	Iterator.register(list_reverseiterator)
285	n/a	Iterator.register(range_iterator)
286	n/a	Iterator.register(longrange_iterator)
287	n/a	Iterator.register(set_iterator)
288	n/a	Iterator.register(str_iterator)
289	n/a	Iterator.register(tuple_iterator)
290	n/a	Iterator.register(zip_iterator)
291	n/a
292	n/a
293	n/a	class Reversible(Iterable):
294	n/a
295	n/a	__slots__ = ()
296	n/a
297	n/a	@abstractmethod
298	n/a	def __reversed__(self):
299	n/a	while False:
300	n/a	yield None
301	n/a
302	n/a	@classmethod
303	n/a	def __subclasshook__(cls, C):
304	n/a	if cls is Reversible:
305	n/a	return _check_methods(C, "__reversed__", "__iter__")
306	n/a	return NotImplemented
307	n/a
308	n/a
309	n/a	class Generator(Iterator):
310	n/a
311	n/a	__slots__ = ()
312	n/a
313	n/a	def __next__(self):
314	n/a	"""Return the next item from the generator.
315	n/a	When exhausted, raise StopIteration.
316	n/a	"""
317	n/a	return self.send(None)
318	n/a
319	n/a	@abstractmethod
320	n/a	def send(self, value):
321	n/a	"""Send a value into the generator.
322	n/a	Return next yielded value or raise StopIteration.
323	n/a	"""
324	n/a	raise StopIteration
325	n/a
326	n/a	@abstractmethod
327	n/a	def throw(self, typ, val=None, tb=None):
328	n/a	"""Raise an exception in the generator.
329	n/a	Return next yielded value or raise StopIteration.
330	n/a	"""
331	n/a	if val is None:
332	n/a	if tb is None:
333	n/a	raise typ
334	n/a	val = typ()
335	n/a	if tb is not None:
336	n/a	val = val.with_traceback(tb)
337	n/a	raise val
338	n/a
339	n/a	def close(self):
340	n/a	"""Raise GeneratorExit inside generator.
341	n/a	"""
342	n/a	try:
343	n/a	self.throw(GeneratorExit)
344	n/a	except (GeneratorExit, StopIteration):
345	n/a	pass
346	n/a	else:
347	n/a	raise RuntimeError("generator ignored GeneratorExit")
348	n/a
349	n/a	@classmethod
350	n/a	def __subclasshook__(cls, C):
351	n/a	if cls is Generator:
352	n/a	return _check_methods(C, '__iter__', '__next__',
353	n/a	'send', 'throw', 'close')
354	n/a	return NotImplemented
355	n/a
356	n/a	Generator.register(generator)
357	n/a
358	n/a
359	n/a	class Sized(metaclass=ABCMeta):
360	n/a
361	n/a	__slots__ = ()
362	n/a
363	n/a	@abstractmethod
364	n/a	def __len__(self):
365	n/a	return 0
366	n/a
367	n/a	@classmethod
368	n/a	def __subclasshook__(cls, C):
369	n/a	if cls is Sized:
370	n/a	return _check_methods(C, "__len__")
371	n/a	return NotImplemented
372	n/a
373	n/a
374	n/a	class Container(metaclass=ABCMeta):
375	n/a
376	n/a	__slots__ = ()
377	n/a
378	n/a	@abstractmethod
379	n/a	def __contains__(self, x):
380	n/a	return False
381	n/a
382	n/a	@classmethod
383	n/a	def __subclasshook__(cls, C):
384	n/a	if cls is Container:
385	n/a	return _check_methods(C, "__contains__")
386	n/a	return NotImplemented
387	n/a
388	n/a	class Collection(Sized, Iterable, Container):
389	n/a
390	n/a	__slots__ = ()
391	n/a
392	n/a	@classmethod
393	n/a	def __subclasshook__(cls, C):
394	n/a	if cls is Collection:
395	n/a	return _check_methods(C, "__len__", "__iter__", "__contains__")
396	n/a	return NotImplemented
397	n/a
398	n/a	class Callable(metaclass=ABCMeta):
399	n/a
400	n/a	__slots__ = ()
401	n/a
402	n/a	@abstractmethod
403	n/a	def __call__(self, args, *kwds):
404	n/a	return False
405	n/a
406	n/a	@classmethod
407	n/a	def __subclasshook__(cls, C):
408	n/a	if cls is Callable:
409	n/a	return _check_methods(C, "__call__")
410	n/a	return NotImplemented
411	n/a
412	n/a
413	n/a	### SETS ###
414	n/a
415	n/a
416	n/a	class Set(Collection):
417	n/a
418	n/a	"""A set is a finite, iterable container.
419	n/a
420	n/a	This class provides concrete generic implementations of all
421	n/a	methods except for __contains__, __iter__ and __len__.
422	n/a
423	n/a	To override the comparisons (presumably for speed, as the
424	n/a	semantics are fixed), redefine __le__ and __ge__,
425	n/a	then the other operations will automatically follow suit.
426	n/a	"""
427	n/a
428	n/a	__slots__ = ()
429	n/a
430	n/a	def __le__(self, other):
431	n/a	if not isinstance(other, Set):
432	n/a	return NotImplemented
433	n/a	if len(self) > len(other):
434	n/a	return False
435	n/a	for elem in self:
436	n/a	if elem not in other:
437	n/a	return False
438	n/a	return True
439	n/a
440	n/a	def __lt__(self, other):
441	n/a	if not isinstance(other, Set):
442	n/a	return NotImplemented
443	n/a	return len(self) < len(other) and self.__le__(other)
444	n/a
445	n/a	def __gt__(self, other):
446	n/a	if not isinstance(other, Set):
447	n/a	return NotImplemented
448	n/a	return len(self) > len(other) and self.__ge__(other)
449	n/a
450	n/a	def __ge__(self, other):
451	n/a	if not isinstance(other, Set):
452	n/a	return NotImplemented
453	n/a	if len(self) < len(other):
454	n/a	return False
455	n/a	for elem in other:
456	n/a	if elem not in self:
457	n/a	return False
458	n/a	return True
459	n/a
460	n/a	def __eq__(self, other):
461	n/a	if not isinstance(other, Set):
462	n/a	return NotImplemented
463	n/a	return len(self) == len(other) and self.__le__(other)
464	n/a
465	n/a	@classmethod
466	n/a	def _from_iterable(cls, it):
467	n/a	'''Construct an instance of the class from any iterable input.
468	n/a
469	n/a	Must override this method if the class constructor signature
470	n/a	does not accept an iterable for an input.
471	n/a	'''
472	n/a	return cls(it)
473	n/a
474	n/a	def __and__(self, other):
475	n/a	if not isinstance(other, Iterable):
476	n/a	return NotImplemented
477	n/a	return self._from_iterable(value for value in other if value in self)
478	n/a
479	n/a	__rand__ = __and__
480	n/a
481	n/a	def isdisjoint(self, other):
482	n/a	'Return True if two sets have a null intersection.'
483	n/a	for value in other:
484	n/a	if value in self:
485	n/a	return False
486	n/a	return True
487	n/a
488	n/a	def __or__(self, other):
489	n/a	if not isinstance(other, Iterable):
490	n/a	return NotImplemented
491	n/a	chain = (e for s in (self, other) for e in s)
492	n/a	return self._from_iterable(chain)
493	n/a
494	n/a	__ror__ = __or__
495	n/a
496	n/a	def __sub__(self, other):
497	n/a	if not isinstance(other, Set):
498	n/a	if not isinstance(other, Iterable):
499	n/a	return NotImplemented
500	n/a	other = self._from_iterable(other)
501	n/a	return self._from_iterable(value for value in self
502	n/a	if value not in other)
503	n/a
504	n/a	def __rsub__(self, other):
505	n/a	if not isinstance(other, Set):
506	n/a	if not isinstance(other, Iterable):
507	n/a	return NotImplemented
508	n/a	other = self._from_iterable(other)
509	n/a	return self._from_iterable(value for value in other
510	n/a	if value not in self)
511	n/a
512	n/a	def __xor__(self, other):
513	n/a	if not isinstance(other, Set):
514	n/a	if not isinstance(other, Iterable):
515	n/a	return NotImplemented
516	n/a	other = self._from_iterable(other)
517	n/a	return (self - other) \| (other - self)
518	n/a
519	n/a	__rxor__ = __xor__
520	n/a
521	n/a	def _hash(self):
522	n/a	"""Compute the hash value of a set.
523	n/a
524	n/a	Note that we don't define __hash__: not all sets are hashable.
525	n/a	But if you define a hashable set type, its __hash__ should
526	n/a	call this function.
527	n/a
528	n/a	This must be compatible __eq__.
529	n/a
530	n/a	All sets ought to compare equal if they contain the same
531	n/a	elements, regardless of how they are implemented, and
532	n/a	regardless of the order of the elements; so there's not much
533	n/a	freedom for __eq__ or __hash__. We match the algorithm used
534	n/a	by the built-in frozenset type.
535	n/a	"""
536	n/a	MAX = sys.maxsize
537	n/a	MASK = 2 * MAX + 1
538	n/a	n = len(self)
539	n/a	h = 1927868237 * (n + 1)
540	n/a	h &= MASK
541	n/a	for x in self:
542	n/a	hx = hash(x)
543	n/a	h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167
544	n/a	h &= MASK
545	n/a	h = h * 69069 + 907133923
546	n/a	h &= MASK
547	n/a	if h > MAX:
548	n/a	h -= MASK + 1
549	n/a	if h == -1:
550	n/a	h = 590923713
551	n/a	return h
552	n/a
553	n/a	Set.register(frozenset)
554	n/a
555	n/a
556	n/a	class MutableSet(Set):
557	n/a	"""A mutable set is a finite, iterable container.
558	n/a
559	n/a	This class provides concrete generic implementations of all
560	n/a	methods except for __contains__, __iter__, __len__,
561	n/a	add(), and discard().
562	n/a
563	n/a	To override the comparisons (presumably for speed, as the
564	n/a	semantics are fixed), all you have to do is redefine __le__ and
565	n/a	then the other operations will automatically follow suit.
566	n/a	"""
567	n/a
568	n/a	__slots__ = ()
569	n/a
570	n/a	@abstractmethod
571	n/a	def add(self, value):
572	n/a	"""Add an element."""
573	n/a	raise NotImplementedError
574	n/a
575	n/a	@abstractmethod
576	n/a	def discard(self, value):
577	n/a	"""Remove an element. Do not raise an exception if absent."""
578	n/a	raise NotImplementedError
579	n/a
580	n/a	def remove(self, value):
581	n/a	"""Remove an element. If not a member, raise a KeyError."""
582	n/a	if value not in self:
583	n/a	raise KeyError(value)
584	n/a	self.discard(value)
585	n/a
586	n/a	def pop(self):
587	n/a	"""Return the popped value. Raise KeyError if empty."""
588	n/a	it = iter(self)
589	n/a	try:
590	n/a	value = next(it)
591	n/a	except StopIteration:
592	n/a	raise KeyError
593	n/a	self.discard(value)
594	n/a	return value
595	n/a
596	n/a	def clear(self):
597	n/a	"""This is slow (creates N new iterators!) but effective."""
598	n/a	try:
599	n/a	while True:
600	n/a	self.pop()
601	n/a	except KeyError:
602	n/a	pass
603	n/a
604	n/a	def __ior__(self, it):
605	n/a	for value in it:
606	n/a	self.add(value)
607	n/a	return self
608	n/a
609	n/a	def __iand__(self, it):
610	n/a	for value in (self - it):
611	n/a	self.discard(value)
612	n/a	return self
613	n/a
614	n/a	def __ixor__(self, it):
615	n/a	if it is self:
616	n/a	self.clear()
617	n/a	else:
618	n/a	if not isinstance(it, Set):
619	n/a	it = self._from_iterable(it)
620	n/a	for value in it:
621	n/a	if value in self:
622	n/a	self.discard(value)
623	n/a	else:
624	n/a	self.add(value)
625	n/a	return self
626	n/a
627	n/a	def __isub__(self, it):
628	n/a	if it is self:
629	n/a	self.clear()
630	n/a	else:
631	n/a	for value in it:
632	n/a	self.discard(value)
633	n/a	return self
634	n/a
635	n/a	MutableSet.register(set)
636	n/a
637	n/a
638	n/a	### MAPPINGS ###
639	n/a
640	n/a
641	n/a	class Mapping(Collection):
642	n/a
643	n/a	__slots__ = ()
644	n/a
645	n/a	"""A Mapping is a generic container for associating key/value
646	n/a	pairs.
647	n/a
648	n/a	This class provides concrete generic implementations of all
649	n/a	methods except for __getitem__, __iter__, and __len__.
650	n/a
651	n/a	"""
652	n/a
653	n/a	@abstractmethod
654	n/a	def __getitem__(self, key):
655	n/a	raise KeyError
656	n/a
657	n/a	def get(self, key, default=None):
658	n/a	'D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.'
659	n/a	try:
660	n/a	return self[key]
661	n/a	except KeyError:
662	n/a	return default
663	n/a
664	n/a	def __contains__(self, key):
665	n/a	try:
666	n/a	self[key]
667	n/a	except KeyError:
668	n/a	return False
669	n/a	else:
670	n/a	return True
671	n/a
672	n/a	def keys(self):
673	n/a	"D.keys() -> a set-like object providing a view on D's keys"
674	n/a	return KeysView(self)
675	n/a
676	n/a	def items(self):
677	n/a	"D.items() -> a set-like object providing a view on D's items"
678	n/a	return ItemsView(self)
679	n/a
680	n/a	def values(self):
681	n/a	"D.values() -> an object providing a view on D's values"
682	n/a	return ValuesView(self)
683	n/a
684	n/a	def __eq__(self, other):
685	n/a	if not isinstance(other, Mapping):
686	n/a	return NotImplemented
687	n/a	return dict(self.items()) == dict(other.items())
688	n/a
689	n/a	__reversed__ = None
690	n/a
691	n/a	Mapping.register(mappingproxy)
692	n/a
693	n/a
694	n/a	class MappingView(Sized):
695	n/a
696	n/a	__slots__ = '_mapping',
697	n/a
698	n/a	def __init__(self, mapping):
699	n/a	self._mapping = mapping
700	n/a
701	n/a	def __len__(self):
702	n/a	return len(self._mapping)
703	n/a
704	n/a	def __repr__(self):
705	n/a	return '{0.__class__.__name__}({0._mapping!r})'.format(self)
706	n/a
707	n/a
708	n/a	class KeysView(MappingView, Set):
709	n/a
710	n/a	__slots__ = ()
711	n/a
712	n/a	@classmethod
713	n/a	def _from_iterable(self, it):
714	n/a	return set(it)
715	n/a
716	n/a	def __contains__(self, key):
717	n/a	return key in self._mapping
718	n/a
719	n/a	def __iter__(self):
720	n/a	yield from self._mapping
721	n/a
722	n/a	KeysView.register(dict_keys)
723	n/a
724	n/a
725	n/a	class ItemsView(MappingView, Set):
726	n/a
727	n/a	__slots__ = ()
728	n/a
729	n/a	@classmethod
730	n/a	def _from_iterable(self, it):
731	n/a	return set(it)
732	n/a
733	n/a	def __contains__(self, item):
734	n/a	key, value = item
735	n/a	try:
736	n/a	v = self._mapping[key]
737	n/a	except KeyError:
738	n/a	return False
739	n/a	else:
740	n/a	return v is value or v == value
741	n/a
742	n/a	def __iter__(self):
743	n/a	for key in self._mapping:
744	n/a	yield (key, self._mapping[key])
745	n/a
746	n/a	ItemsView.register(dict_items)
747	n/a
748	n/a
749	n/a	class ValuesView(MappingView):
750	n/a
751	n/a	__slots__ = ()
752	n/a
753	n/a	def __contains__(self, value):
754	n/a	for key in self._mapping:
755	n/a	v = self._mapping[key]
756	n/a	if v is value or v == value:
757	n/a	return True
758	n/a	return False
759	n/a
760	n/a	def __iter__(self):
761	n/a	for key in self._mapping:
762	n/a	yield self._mapping[key]
763	n/a
764	n/a	ValuesView.register(dict_values)
765	n/a
766	n/a
767	n/a	class MutableMapping(Mapping):
768	n/a
769	n/a	__slots__ = ()
770	n/a
771	n/a	"""A MutableMapping is a generic container for associating
772	n/a	key/value pairs.
773	n/a
774	n/a	This class provides concrete generic implementations of all
775	n/a	methods except for __getitem__, __setitem__, __delitem__,
776	n/a	__iter__, and __len__.
777	n/a
778	n/a	"""
779	n/a
780	n/a	@abstractmethod
781	n/a	def __setitem__(self, key, value):
782	n/a	raise KeyError
783	n/a
784	n/a	@abstractmethod
785	n/a	def __delitem__(self, key):
786	n/a	raise KeyError
787	n/a
788	n/a	__marker = object()
789	n/a
790	n/a	def pop(self, key, default=__marker):
791	n/a	'''D.pop(k[,d]) -> v, remove specified key and return the corresponding value.
792	n/a	If key is not found, d is returned if given, otherwise KeyError is raised.
793	n/a	'''
794	n/a	try:
795	n/a	value = self[key]
796	n/a	except KeyError:
797	n/a	if default is self.__marker:
798	n/a	raise
799	n/a	return default
800	n/a	else:
801	n/a	del self[key]
802	n/a	return value
803	n/a
804	n/a	def popitem(self):
805	n/a	'''D.popitem() -> (k, v), remove and return some (key, value) pair
806	n/a	as a 2-tuple; but raise KeyError if D is empty.
807	n/a	'''
808	n/a	try:
809	n/a	key = next(iter(self))
810	n/a	except StopIteration:
811	n/a	raise KeyError
812	n/a	value = self[key]
813	n/a	del self[key]
814	n/a	return key, value
815	n/a
816	n/a	def clear(self):
817	n/a	'D.clear() -> None. Remove all items from D.'
818	n/a	try:
819	n/a	while True:
820	n/a	self.popitem()
821	n/a	except KeyError:
822	n/a	pass
823	n/a
824	n/a	def update(args, *kwds):
825	n/a	''' D.update([E, ]**F) -> None. Update D from mapping/iterable E and F.
826	n/a	If E present and has a .keys() method, does: for k in E: D[k] = E[k]
827	n/a	If E present and lacks .keys() method, does: for (k, v) in E: D[k] = v
828	n/a	In either case, this is followed by: for k, v in F.items(): D[k] = v
829	n/a	'''
830	n/a	if not args:
831	n/a	raise TypeError("descriptor 'update' of 'MutableMapping' object "
832	n/a	"needs an argument")
833	n/a	self, *args = args
834	n/a	if len(args) > 1:
835	n/a	raise TypeError('update expected at most 1 arguments, got %d' %
836	n/a	len(args))
837	n/a	if args:
838	n/a	other = args[0]
839	n/a	if isinstance(other, Mapping):
840	n/a	for key in other:
841	n/a	self[key] = other[key]
842	n/a	elif hasattr(other, "keys"):
843	n/a	for key in other.keys():
844	n/a	self[key] = other[key]
845	n/a	else:
846	n/a	for key, value in other:
847	n/a	self[key] = value
848	n/a	for key, value in kwds.items():
849	n/a	self[key] = value
850	n/a
851	n/a	def setdefault(self, key, default=None):
852	n/a	'D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D'
853	n/a	try:
854	n/a	return self[key]
855	n/a	except KeyError:
856	n/a	self[key] = default
857	n/a	return default
858	n/a
859	n/a	MutableMapping.register(dict)
860	n/a
861	n/a
862	n/a	### SEQUENCES ###
863	n/a
864	n/a
865	n/a	class Sequence(Reversible, Collection):
866	n/a
867	n/a	"""All the operations on a read-only sequence.
868	n/a
869	n/a	Concrete subclasses must override __new__ or __init__,
870	n/a	__getitem__, and __len__.
871	n/a	"""
872	n/a
873	n/a	__slots__ = ()
874	n/a
875	n/a	@abstractmethod
876	n/a	def __getitem__(self, index):
877	n/a	raise IndexError
878	n/a
879	n/a	def __iter__(self):
880	n/a	i = 0
881	n/a	try:
882	n/a	while True:
883	n/a	v = self[i]
884	n/a	yield v
885	n/a	i += 1
886	n/a	except IndexError:
887	n/a	return
888	n/a
889	n/a	def __contains__(self, value):
890	n/a	for v in self:
891	n/a	if v is value or v == value:
892	n/a	return True
893	n/a	return False
894	n/a
895	n/a	def __reversed__(self):
896	n/a	for i in reversed(range(len(self))):
897	n/a	yield self[i]
898	n/a
899	n/a	def index(self, value, start=0, stop=None):
900	n/a	'''S.index(value, [start, [stop]]) -> integer -- return first index of value.
901	n/a	Raises ValueError if the value is not present.
902	n/a	'''
903	n/a	if start is not None and start < 0:
904	n/a	start = max(len(self) + start, 0)
905	n/a	if stop is not None and stop < 0:
906	n/a	stop += len(self)
907	n/a
908	n/a	i = start
909	n/a	while stop is None or i < stop:
910	n/a	try:
911	n/a	if self[i] == value:
912	n/a	return i
913	n/a	except IndexError:
914	n/a	break
915	n/a	i += 1
916	n/a	raise ValueError
917	n/a
918	n/a	def count(self, value):
919	n/a	'S.count(value) -> integer -- return number of occurrences of value'
920	n/a	return sum(1 for v in self if v == value)
921	n/a
922	n/a	Sequence.register(tuple)
923	n/a	Sequence.register(str)
924	n/a	Sequence.register(range)
925	n/a	Sequence.register(memoryview)
926	n/a
927	n/a
928	n/a	class ByteString(Sequence):
929	n/a
930	n/a	"""This unifies bytes and bytearray.
931	n/a
932	n/a	XXX Should add all their methods.
933	n/a	"""
934	n/a
935	n/a	__slots__ = ()
936	n/a
937	n/a	ByteString.register(bytes)
938	n/a	ByteString.register(bytearray)
939	n/a
940	n/a
941	n/a	class MutableSequence(Sequence):
942	n/a
943	n/a	__slots__ = ()
944	n/a
945	n/a	"""All the operations on a read-write sequence.
946	n/a
947	n/a	Concrete subclasses must provide __new__ or __init__,
948	n/a	__getitem__, __setitem__, __delitem__, __len__, and insert().
949	n/a
950	n/a	"""
951	n/a
952	n/a	@abstractmethod
953	n/a	def __setitem__(self, index, value):
954	n/a	raise IndexError
955	n/a
956	n/a	@abstractmethod
957	n/a	def __delitem__(self, index):
958	n/a	raise IndexError
959	n/a
960	n/a	@abstractmethod
961	n/a	def insert(self, index, value):
962	n/a	'S.insert(index, value) -- insert value before index'
963	n/a	raise IndexError
964	n/a
965	n/a	def append(self, value):
966	n/a	'S.append(value) -- append value to the end of the sequence'
967	n/a	self.insert(len(self), value)
968	n/a
969	n/a	def clear(self):
970	n/a	'S.clear() -> None -- remove all items from S'
971	n/a	try:
972	n/a	while True:
973	n/a	self.pop()
974	n/a	except IndexError:
975	n/a	pass
976	n/a
977	n/a	def reverse(self):
978	n/a	'S.reverse() -- reverse IN PLACE'
979	n/a	n = len(self)
980	n/a	for i in range(n//2):
981	n/a	self[i], self[n-i-1] = self[n-i-1], self[i]
982	n/a
983	n/a	def extend(self, values):
984	n/a	'S.extend(iterable) -- extend sequence by appending elements from the iterable'
985	n/a	for v in values:
986	n/a	self.append(v)
987	n/a
988	n/a	def pop(self, index=-1):
989	n/a	'''S.pop([index]) -> item -- remove and return item at index (default last).
990	n/a	Raise IndexError if list is empty or index is out of range.
991	n/a	'''
992	n/a	v = self[index]
993	n/a	del self[index]
994	n/a	return v
995	n/a
996	n/a	def remove(self, value):
997	n/a	'''S.remove(value) -- remove first occurrence of value.
998	n/a	Raise ValueError if the value is not present.
999	n/a	'''
1000	n/a	del self[self.index(value)]
1001	n/a
1002	n/a	def __iadd__(self, values):
1003	n/a	self.extend(values)
1004	n/a	return self
1005	n/a
1006	n/a	MutableSequence.register(list)
1007	n/a	MutableSequence.register(bytearray) # Multiply inheriting, see ByteString