1 | # 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 |
|
6 | DON'T USE THIS MODULE DIRECTLY! The classes here should be imported
|
7 | via collections; they are defined here only to alleviate certain
|
8 | bootstrapping issues. Unit tests are in test_collections.
|
9 | """
|
10 |
|
11 | from abc import ABCMeta, abstractmethod
|
12 | import sys
|
13 |
|
14 | __all__ = ["Hashable", "Iterable", "Iterator",
|
15 | "Sized", "Container", "Callable",
|
16 | "Set", "MutableSet",
|
17 | "Mapping", "MutableMapping",
|
18 | "MappingView", "KeysView", "ItemsView", "ValuesView",
|
19 | "Sequence", "MutableSequence",
|
20 | ]
|
21 |
|
22 | ### ONE-TRICK PONIES ###
|
23 |
|
24 | def _hasattr(C, attr):
|
25 | try:
|
26 | return any(attr in B.__dict__ for B in C.__mro__)
|
27 | except AttributeError:
|
28 | # Old-style class
|
29 | return hasattr(C, attr)
|
30 |
|
31 |
|
32 | class Hashable:
|
33 | __metaclass__ = ABCMeta
|
34 |
|
35 | @abstractmethod
|
36 | def __hash__(self):
|
37 | return 0
|
38 |
|
39 | @classmethod
|
40 | def __subclasshook__(cls, C):
|
41 | if cls is Hashable:
|
42 | try:
|
43 | for B in C.__mro__:
|
44 | if "__hash__" in B.__dict__:
|
45 | if B.__dict__["__hash__"]:
|
46 | return True
|
47 | break
|
48 | except AttributeError:
|
49 | # Old-style class
|
50 | if getattr(C, "__hash__", None):
|
51 | return True
|
52 | return NotImplemented
|
53 |
|
54 |
|
55 | class Iterable:
|
56 | __metaclass__ = ABCMeta
|
57 |
|
58 | @abstractmethod
|
59 | def __iter__(self):
|
60 | while False:
|
61 | yield None
|
62 |
|
63 | @classmethod
|
64 | def __subclasshook__(cls, C):
|
65 | if cls is Iterable:
|
66 | if _hasattr(C, "__iter__"):
|
67 | return True
|
68 | return NotImplemented
|
69 |
|
70 | Iterable.register(str)
|
71 |
|
72 |
|
73 | class Iterator(Iterable):
|
74 |
|
75 | @abstractmethod
|
76 | def next(self):
|
77 | 'Return the next item from the iterator. When exhausted, raise StopIteration'
|
78 | raise StopIteration
|
79 |
|
80 | def __iter__(self):
|
81 | return self
|
82 |
|
83 | @classmethod
|
84 | def __subclasshook__(cls, C):
|
85 | if cls is Iterator:
|
86 | if _hasattr(C, "next") and _hasattr(C, "__iter__"):
|
87 | return True
|
88 | return NotImplemented
|
89 |
|
90 |
|
91 | class Sized:
|
92 | __metaclass__ = ABCMeta
|
93 |
|
94 | @abstractmethod
|
95 | def __len__(self):
|
96 | return 0
|
97 |
|
98 | @classmethod
|
99 | def __subclasshook__(cls, C):
|
100 | if cls is Sized:
|
101 | if _hasattr(C, "__len__"):
|
102 | return True
|
103 | return NotImplemented
|
104 |
|
105 |
|
106 | class Container:
|
107 | __metaclass__ = ABCMeta
|
108 |
|
109 | @abstractmethod
|
110 | def __contains__(self, x):
|
111 | return False
|
112 |
|
113 | @classmethod
|
114 | def __subclasshook__(cls, C):
|
115 | if cls is Container:
|
116 | if _hasattr(C, "__contains__"):
|
117 | return True
|
118 | return NotImplemented
|
119 |
|
120 |
|
121 | class Callable:
|
122 | __metaclass__ = ABCMeta
|
123 |
|
124 | @abstractmethod
|
125 | def __call__(self, *args, **kwds):
|
126 | return False
|
127 |
|
128 | @classmethod
|
129 | def __subclasshook__(cls, C):
|
130 | if cls is Callable:
|
131 | if _hasattr(C, "__call__"):
|
132 | return True
|
133 | return NotImplemented
|
134 |
|
135 |
|
136 | ### SETS ###
|
137 |
|
138 |
|
139 | class Set(Sized, Iterable, Container):
|
140 | """A set is a finite, iterable container.
|
141 |
|
142 | This class provides concrete generic implementations of all
|
143 | methods except for __contains__, __iter__ and __len__.
|
144 |
|
145 | To override the comparisons (presumably for speed, as the
|
146 | semantics are fixed), redefine __le__ and __ge__,
|
147 | then the other operations will automatically follow suit.
|
148 | """
|
149 |
|
150 | def __le__(self, other):
|
151 | if not isinstance(other, Set):
|
152 | return NotImplemented
|
153 | if len(self) > len(other):
|
154 | return False
|
155 | for elem in self:
|
156 | if elem not in other:
|
157 | return False
|
158 | return True
|
159 |
|
160 | def __lt__(self, other):
|
161 | if not isinstance(other, Set):
|
162 | return NotImplemented
|
163 | return len(self) < len(other) and self.__le__(other)
|
164 |
|
165 | def __gt__(self, other):
|
166 | if not isinstance(other, Set):
|
167 | return NotImplemented
|
168 | return len(self) > len(other) and self.__ge__(other)
|
169 |
|
170 | def __ge__(self, other):
|
171 | if not isinstance(other, Set):
|
172 | return NotImplemented
|
173 | if len(self) < len(other):
|
174 | return False
|
175 | for elem in other:
|
176 | if elem not in self:
|
177 | return False
|
178 | return True
|
179 |
|
180 | def __eq__(self, other):
|
181 | if not isinstance(other, Set):
|
182 | return NotImplemented
|
183 | return len(self) == len(other) and self.__le__(other)
|
184 |
|
185 | def __ne__(self, other):
|
186 | return not (self == other)
|
187 |
|
188 | @classmethod
|
189 | def _from_iterable(cls, it):
|
190 | '''Construct an instance of the class from any iterable input.
|
191 |
|
192 | Must override this method if the class constructor signature
|
193 | does not accept an iterable for an input.
|
194 | '''
|
195 | return cls(it)
|
196 |
|
197 | def __and__(self, other):
|
198 | if not isinstance(other, Iterable):
|
199 | return NotImplemented
|
200 | return self._from_iterable(value for value in other if value in self)
|
201 |
|
202 | __rand__ = __and__
|
203 |
|
204 | def isdisjoint(self, other):
|
205 | 'Return True if two sets have a null intersection.'
|
206 | for value in other:
|
207 | if value in self:
|
208 | return False
|
209 | return True
|
210 |
|
211 | def __or__(self, other):
|
212 | if not isinstance(other, Iterable):
|
213 | return NotImplemented
|
214 | chain = (e for s in (self, other) for e in s)
|
215 | return self._from_iterable(chain)
|
216 |
|
217 | __ror__ = __or__
|
218 |
|
219 | def __sub__(self, other):
|
220 | if not isinstance(other, Set):
|
221 | if not isinstance(other, Iterable):
|
222 | return NotImplemented
|
223 | other = self._from_iterable(other)
|
224 | return self._from_iterable(value for value in self
|
225 | if value not in other)
|
226 |
|
227 | def __rsub__(self, other):
|
228 | if not isinstance(other, Set):
|
229 | if not isinstance(other, Iterable):
|
230 | return NotImplemented
|
231 | other = self._from_iterable(other)
|
232 | return self._from_iterable(value for value in other
|
233 | if value not in self)
|
234 |
|
235 | def __xor__(self, other):
|
236 | if not isinstance(other, Set):
|
237 | if not isinstance(other, Iterable):
|
238 | return NotImplemented
|
239 | other = self._from_iterable(other)
|
240 | return (self - other) | (other - self)
|
241 |
|
242 | __rxor__ = __xor__
|
243 |
|
244 | # Sets are not hashable by default, but subclasses can change this
|
245 | __hash__ = None
|
246 |
|
247 | def _hash(self):
|
248 | """Compute the hash value of a set.
|
249 |
|
250 | Note that we don't define __hash__: not all sets are hashable.
|
251 | But if you define a hashable set type, its __hash__ should
|
252 | call this function.
|
253 |
|
254 | This must be compatible __eq__.
|
255 |
|
256 | All sets ought to compare equal if they contain the same
|
257 | elements, regardless of how they are implemented, and
|
258 | regardless of the order of the elements; so there's not much
|
259 | freedom for __eq__ or __hash__. We match the algorithm used
|
260 | by the built-in frozenset type.
|
261 | """
|
262 | MAX = sys.maxint
|
263 | MASK = 2 * MAX + 1
|
264 | n = len(self)
|
265 | h = 1927868237 * (n + 1)
|
266 | h &= MASK
|
267 | for x in self:
|
268 | hx = hash(x)
|
269 | h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167
|
270 | h &= MASK
|
271 | h = h * 69069 + 907133923
|
272 | h &= MASK
|
273 | if h > MAX:
|
274 | h -= MASK + 1
|
275 | if h == -1:
|
276 | h = 590923713
|
277 | return h
|
278 |
|
279 | Set.register(frozenset)
|
280 |
|
281 |
|
282 | class MutableSet(Set):
|
283 | """A mutable set is a finite, iterable container.
|
284 |
|
285 | This class provides concrete generic implementations of all
|
286 | methods except for __contains__, __iter__, __len__,
|
287 | add(), and discard().
|
288 |
|
289 | To override the comparisons (presumably for speed, as the
|
290 | semantics are fixed), all you have to do is redefine __le__ and
|
291 | then the other operations will automatically follow suit.
|
292 | """
|
293 |
|
294 | @abstractmethod
|
295 | def add(self, value):
|
296 | """Add an element."""
|
297 | raise NotImplementedError
|
298 |
|
299 | @abstractmethod
|
300 | def discard(self, value):
|
301 | """Remove an element. Do not raise an exception if absent."""
|
302 | raise NotImplementedError
|
303 |
|
304 | def remove(self, value):
|
305 | """Remove an element. If not a member, raise a KeyError."""
|
306 | if value not in self:
|
307 | raise KeyError(value)
|
308 | self.discard(value)
|
309 |
|
310 | def pop(self):
|
311 | """Return the popped value. Raise KeyError if empty."""
|
312 | it = iter(self)
|
313 | try:
|
314 | value = next(it)
|
315 | except StopIteration:
|
316 | raise KeyError
|
317 | self.discard(value)
|
318 | return value
|
319 |
|
320 | def clear(self):
|
321 | """This is slow (creates N new iterators!) but effective."""
|
322 | try:
|
323 | while True:
|
324 | self.pop()
|
325 | except KeyError:
|
326 | pass
|
327 |
|
328 | def __ior__(self, it):
|
329 | for value in it:
|
330 | self.add(value)
|
331 | return self
|
332 |
|
333 | def __iand__(self, it):
|
334 | for value in (self - it):
|
335 | self.discard(value)
|
336 | return self
|
337 |
|
338 | def __ixor__(self, it):
|
339 | if it is self:
|
340 | self.clear()
|
341 | else:
|
342 | if not isinstance(it, Set):
|
343 | it = self._from_iterable(it)
|
344 | for value in it:
|
345 | if value in self:
|
346 | self.discard(value)
|
347 | else:
|
348 | self.add(value)
|
349 | return self
|
350 |
|
351 | def __isub__(self, it):
|
352 | if it is self:
|
353 | self.clear()
|
354 | else:
|
355 | for value in it:
|
356 | self.discard(value)
|
357 | return self
|
358 |
|
359 | MutableSet.register(set)
|
360 |
|
361 |
|
362 | ### MAPPINGS ###
|
363 |
|
364 |
|
365 | class Mapping(Sized, Iterable, Container):
|
366 |
|
367 | """A Mapping is a generic container for associating key/value
|
368 | pairs.
|
369 |
|
370 | This class provides concrete generic implementations of all
|
371 | methods except for __getitem__, __iter__, and __len__.
|
372 |
|
373 | """
|
374 |
|
375 | @abstractmethod
|
376 | def __getitem__(self, key):
|
377 | raise KeyError
|
378 |
|
379 | def get(self, key, default=None):
|
380 | 'D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.'
|
381 | try:
|
382 | return self[key]
|
383 | except KeyError:
|
384 | return default
|
385 |
|
386 | def __contains__(self, key):
|
387 | try:
|
388 | self[key]
|
389 | except KeyError:
|
390 | return False
|
391 | else:
|
392 | return True
|
393 |
|
394 | def iterkeys(self):
|
395 | 'D.iterkeys() -> an iterator over the keys of D'
|
396 | return iter(self)
|
397 |
|
398 | def itervalues(self):
|
399 | 'D.itervalues() -> an iterator over the values of D'
|
400 | for key in self:
|
401 | yield self[key]
|
402 |
|
403 | def iteritems(self):
|
404 | 'D.iteritems() -> an iterator over the (key, value) items of D'
|
405 | for key in self:
|
406 | yield (key, self[key])
|
407 |
|
408 | def keys(self):
|
409 | "D.keys() -> list of D's keys"
|
410 | return list(self)
|
411 |
|
412 | def items(self):
|
413 | "D.items() -> list of D's (key, value) pairs, as 2-tuples"
|
414 | return [(key, self[key]) for key in self]
|
415 |
|
416 | def values(self):
|
417 | "D.values() -> list of D's values"
|
418 | return [self[key] for key in self]
|
419 |
|
420 | # Mappings are not hashable by default, but subclasses can change this
|
421 | __hash__ = None
|
422 |
|
423 | def __eq__(self, other):
|
424 | if not isinstance(other, Mapping):
|
425 | return NotImplemented
|
426 | return dict(self.items()) == dict(other.items())
|
427 |
|
428 | def __ne__(self, other):
|
429 | return not (self == other)
|
430 |
|
431 | class MappingView(Sized):
|
432 |
|
433 | def __init__(self, mapping):
|
434 | self._mapping = mapping
|
435 |
|
436 | def __len__(self):
|
437 | return len(self._mapping)
|
438 |
|
439 | def __repr__(self):
|
440 | return '{0.__class__.__name__}({0._mapping!r})'.format(self)
|
441 |
|
442 |
|
443 | class KeysView(MappingView, Set):
|
444 |
|
445 | @classmethod
|
446 | def _from_iterable(self, it):
|
447 | return set(it)
|
448 |
|
449 | def __contains__(self, key):
|
450 | return key in self._mapping
|
451 |
|
452 | def __iter__(self):
|
453 | for key in self._mapping:
|
454 | yield key
|
455 |
|
456 | KeysView.register(type({}.viewkeys()))
|
457 |
|
458 | class ItemsView(MappingView, Set):
|
459 |
|
460 | @classmethod
|
461 | def _from_iterable(self, it):
|
462 | return set(it)
|
463 |
|
464 | def __contains__(self, item):
|
465 | key, value = item
|
466 | try:
|
467 | v = self._mapping[key]
|
468 | except KeyError:
|
469 | return False
|
470 | else:
|
471 | return v == value
|
472 |
|
473 | def __iter__(self):
|
474 | for key in self._mapping:
|
475 | yield (key, self._mapping[key])
|
476 |
|
477 | ItemsView.register(type({}.viewitems()))
|
478 |
|
479 | class ValuesView(MappingView):
|
480 |
|
481 | def __contains__(self, value):
|
482 | for key in self._mapping:
|
483 | if value == self._mapping[key]:
|
484 | return True
|
485 | return False
|
486 |
|
487 | def __iter__(self):
|
488 | for key in self._mapping:
|
489 | yield self._mapping[key]
|
490 |
|
491 | ValuesView.register(type({}.viewvalues()))
|
492 |
|
493 | class MutableMapping(Mapping):
|
494 |
|
495 | """A MutableMapping is a generic container for associating
|
496 | key/value pairs.
|
497 |
|
498 | This class provides concrete generic implementations of all
|
499 | methods except for __getitem__, __setitem__, __delitem__,
|
500 | __iter__, and __len__.
|
501 |
|
502 | """
|
503 |
|
504 | @abstractmethod
|
505 | def __setitem__(self, key, value):
|
506 | raise KeyError
|
507 |
|
508 | @abstractmethod
|
509 | def __delitem__(self, key):
|
510 | raise KeyError
|
511 |
|
512 | __marker = object()
|
513 |
|
514 | def pop(self, key, default=__marker):
|
515 | '''D.pop(k[,d]) -> v, remove specified key and return the corresponding value.
|
516 | If key is not found, d is returned if given, otherwise KeyError is raised.
|
517 | '''
|
518 | try:
|
519 | value = self[key]
|
520 | except KeyError:
|
521 | if default is self.__marker:
|
522 | raise
|
523 | return default
|
524 | else:
|
525 | del self[key]
|
526 | return value
|
527 |
|
528 | def popitem(self):
|
529 | '''D.popitem() -> (k, v), remove and return some (key, value) pair
|
530 | as a 2-tuple; but raise KeyError if D is empty.
|
531 | '''
|
532 | try:
|
533 | key = next(iter(self))
|
534 | except StopIteration:
|
535 | raise KeyError
|
536 | value = self[key]
|
537 | del self[key]
|
538 | return key, value
|
539 |
|
540 | def clear(self):
|
541 | 'D.clear() -> None. Remove all items from D.'
|
542 | try:
|
543 | while True:
|
544 | self.popitem()
|
545 | except KeyError:
|
546 | pass
|
547 |
|
548 | def update(*args, **kwds):
|
549 | ''' D.update([E, ]**F) -> None. Update D from mapping/iterable E and F.
|
550 | If E present and has a .keys() method, does: for k in E: D[k] = E[k]
|
551 | If E present and lacks .keys() method, does: for (k, v) in E: D[k] = v
|
552 | In either case, this is followed by: for k, v in F.items(): D[k] = v
|
553 | '''
|
554 | if not args:
|
555 | raise TypeError("descriptor 'update' of 'MutableMapping' object "
|
556 | "needs an argument")
|
557 | self = args[0]
|
558 | args = args[1:]
|
559 | if len(args) > 1:
|
560 | raise TypeError('update expected at most 1 arguments, got %d' %
|
561 | len(args))
|
562 | if args:
|
563 | other = args[0]
|
564 | if isinstance(other, Mapping):
|
565 | for key in other:
|
566 | self[key] = other[key]
|
567 | elif hasattr(other, "keys"):
|
568 | for key in other.keys():
|
569 | self[key] = other[key]
|
570 | else:
|
571 | for key, value in other:
|
572 | self[key] = value
|
573 | for key, value in kwds.items():
|
574 | self[key] = value
|
575 |
|
576 | def setdefault(self, key, default=None):
|
577 | 'D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D'
|
578 | try:
|
579 | return self[key]
|
580 | except KeyError:
|
581 | self[key] = default
|
582 | return default
|
583 |
|
584 | MutableMapping.register(dict)
|
585 |
|
586 |
|
587 | ### SEQUENCES ###
|
588 |
|
589 |
|
590 | class Sequence(Sized, Iterable, Container):
|
591 | """All the operations on a read-only sequence.
|
592 |
|
593 | Concrete subclasses must override __new__ or __init__,
|
594 | __getitem__, and __len__.
|
595 | """
|
596 |
|
597 | @abstractmethod
|
598 | def __getitem__(self, index):
|
599 | raise IndexError
|
600 |
|
601 | def __iter__(self):
|
602 | i = 0
|
603 | try:
|
604 | while True:
|
605 | v = self[i]
|
606 | yield v
|
607 | i += 1
|
608 | except IndexError:
|
609 | return
|
610 |
|
611 | def __contains__(self, value):
|
612 | for v in self:
|
613 | if v == value:
|
614 | return True
|
615 | return False
|
616 |
|
617 | def __reversed__(self):
|
618 | for i in reversed(range(len(self))):
|
619 | yield self[i]
|
620 |
|
621 | def index(self, value):
|
622 | '''S.index(value) -> integer -- return first index of value.
|
623 | Raises ValueError if the value is not present.
|
624 | '''
|
625 | for i, v in enumerate(self):
|
626 | if v == value:
|
627 | return i
|
628 | raise ValueError
|
629 |
|
630 | def count(self, value):
|
631 | 'S.count(value) -> integer -- return number of occurrences of value'
|
632 | return sum(1 for v in self if v == value)
|
633 |
|
634 | Sequence.register(tuple)
|
635 | Sequence.register(basestring)
|
636 | Sequence.register(buffer)
|
637 | Sequence.register(xrange)
|
638 |
|
639 |
|
640 | class MutableSequence(Sequence):
|
641 |
|
642 | """All the operations on a read-only sequence.
|
643 |
|
644 | Concrete subclasses must provide __new__ or __init__,
|
645 | __getitem__, __setitem__, __delitem__, __len__, and insert().
|
646 |
|
647 | """
|
648 |
|
649 | @abstractmethod
|
650 | def __setitem__(self, index, value):
|
651 | raise IndexError
|
652 |
|
653 | @abstractmethod
|
654 | def __delitem__(self, index):
|
655 | raise IndexError
|
656 |
|
657 | @abstractmethod
|
658 | def insert(self, index, value):
|
659 | 'S.insert(index, object) -- insert object before index'
|
660 | raise IndexError
|
661 |
|
662 | def append(self, value):
|
663 | 'S.append(object) -- append object to the end of the sequence'
|
664 | self.insert(len(self), value)
|
665 |
|
666 | def reverse(self):
|
667 | 'S.reverse() -- reverse *IN PLACE*'
|
668 | n = len(self)
|
669 | for i in range(n//2):
|
670 | self[i], self[n-i-1] = self[n-i-1], self[i]
|
671 |
|
672 | def extend(self, values):
|
673 | 'S.extend(iterable) -- extend sequence by appending elements from the iterable'
|
674 | for v in values:
|
675 | self.append(v)
|
676 |
|
677 | def pop(self, index=-1):
|
678 | '''S.pop([index]) -> item -- remove and return item at index (default last).
|
679 | Raise IndexError if list is empty or index is out of range.
|
680 | '''
|
681 | v = self[index]
|
682 | del self[index]
|
683 | return v
|
684 |
|
685 | def remove(self, value):
|
686 | '''S.remove(value) -- remove first occurrence of value.
|
687 | Raise ValueError if the value is not present.
|
688 | '''
|
689 | del self[self.index(value)]
|
690 |
|
691 | def __iadd__(self, values):
|
692 | self.extend(values)
|
693 | return self
|
694 |
|
695 | MutableSequence.register(list)
|