_collections_abc.py revision b9da9bc0a04b718e8395e2e88c3053ab944579b7 
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
6DON'T USE THIS MODULE DIRECTLY!  The classes here should be imported
7via collections; they are defined here only to alleviate certain
8bootstrapping issues.  Unit tests are in test_collections.
9"""
10
11from abc import ABCMeta, abstractmethod
12
13__all__ = ["Hashable", "Iterable", "Iterator",
14           "Sized", "Container", "Callable",
15           "Set", "MutableSet",
16           "Mapping", "MutableMapping",
17           "MappingView", "KeysView", "ItemsView", "ValuesView",
18           "Sequence", "MutableSequence",
19           "ByteString",
20           "bytearray_iterator", "bytes_iterator", "dict_itemiterator",
21           "dict_items", "dict_keyiterator", "dict_keys", "dict_proxy",
22           "dict_valueiterator", "dict_values", "list_iterator",
23           "list_reverseiterator", "range_iterator", "set_iterator",
24           "str_iterator", "tuple_iterator", "zip_iterator",
25           ]
26
27
28### collection related types which are not exposed through builtin ###
29## iterators ##
30bytes_iterator = type(iter(b''))
31bytearray_iterator = type(iter(bytearray()))
32#callable_iterator = ???
33dict_keyiterator = type(iter({}.keys()))
34dict_valueiterator = type(iter({}.values()))
35dict_itemiterator = type(iter({}.items()))
36list_iterator = type(iter([]))
37list_reverseiterator = type(iter(reversed([])))
38range_iterator = type(iter(range(0)))
39set_iterator = type(iter(set()))
40str_iterator = type(iter(""))
41tuple_iterator = type(iter(()))
42zip_iterator = type(iter(zip()))
43## views ##
44dict_keys = type({}.keys())
45dict_values = type({}.values())
46dict_items = type({}.items())
47## misc ##
48dict_proxy = type(type.__dict__)
49
50
51### ONE-TRICK PONIES ###
52
53class Hashable(metaclass=ABCMeta):
54
55    @abstractmethod
56    def __hash__(self):
57        return 0
58
59    @classmethod
60    def __subclasshook__(cls, C):
61        if cls is Hashable:
62            for B in C.__mro__:
63                if "__hash__" in B.__dict__:
64                    if B.__dict__["__hash__"]:
65                        return True
66                    break
67        return NotImplemented
68
69
70class Iterable(metaclass=ABCMeta):
71
72    @abstractmethod
73    def __iter__(self):
74        while False:
75            yield None
76
77    @classmethod
78    def __subclasshook__(cls, C):
79        if cls is Iterable:
80            if any("__iter__" in B.__dict__ for B in C.__mro__):
81                return True
82        return NotImplemented
83
84
85class Iterator(metaclass=ABCMeta):
86
87    @abstractmethod
88    def __next__(self):
89        raise StopIteration
90
91    def __iter__(self):
92        return self
93
94    @classmethod
95    def __subclasshook__(cls, C):
96        if cls is Iterator:
97            if any("__next__" in B.__dict__ for B in C.__mro__):
98                return True
99        return NotImplemented
100
101Iterator.register(bytes_iterator)
102Iterator.register(bytearray_iterator)
103#Iterator.register(callable_iterator)
104Iterator.register(dict_keyiterator)
105Iterator.register(dict_valueiterator)
106Iterator.register(dict_itemiterator)
107Iterator.register(list_iterator)
108Iterator.register(list_reverseiterator)
109Iterator.register(range_iterator)
110Iterator.register(set_iterator)
111Iterator.register(str_iterator)
112Iterator.register(tuple_iterator)
113Iterator.register(zip_iterator)
114
115class Sized(metaclass=ABCMeta):
116
117    @abstractmethod
118    def __len__(self):
119        return 0
120
121    @classmethod
122    def __subclasshook__(cls, C):
123        if cls is Sized:
124            if any("__len__" in B.__dict__ for B in C.__mro__):
125                return True
126        return NotImplemented
127
128
129class Container(metaclass=ABCMeta):
130
131    @abstractmethod
132    def __contains__(self, x):
133        return False
134
135    @classmethod
136    def __subclasshook__(cls, C):
137        if cls is Container:
138            if any("__contains__" in B.__dict__ for B in C.__mro__):
139                return True
140        return NotImplemented
141
142
143class Callable(metaclass=ABCMeta):
144
145    @abstractmethod
146    def __contains__(self, x):
147        return False
148
149    @classmethod
150    def __subclasshook__(cls, C):
151        if cls is Callable:
152            if any("__call__" in B.__dict__ for B in C.__mro__):
153                return True
154        return NotImplemented
155
156
157### SETS ###
158
159
160class Set(metaclass=ABCMeta):
161
162    """A set is a finite, iterable container.
163
164    This class provides concrete generic implementations of all
165    methods except for __contains__, __iter__ and __len__.
166
167    To override the comparisons (presumably for speed, as the
168    semantics are fixed), all you have to do is redefine __le__ and
169    then the other operations will automatically follow suit.
170    """
171
172    @abstractmethod
173    def __contains__(self, value):
174        return False
175
176    @abstractmethod
177    def __iter__(self):
178        while False:
179            yield None
180
181    @abstractmethod
182    def __len__(self):
183        return 0
184
185    def __le__(self, other):
186        if not isinstance(other, Set):
187            return NotImplemented
188        if len(self) > len(other):
189            return False
190        for elem in self:
191            if elem not in other:
192                return False
193        return True
194
195    def __lt__(self, other):
196        if not isinstance(other, Set):
197            return NotImplemented
198        return len(self) < len(other) and self.__le__(other)
199
200    def __eq__(self, other):
201        if not isinstance(other, Set):
202            return NotImplemented
203        return len(self) == len(other) and self.__le__(other)
204
205    @classmethod
206    def _from_iterable(cls, it):
207        return frozenset(it)
208
209    def __and__(self, other):
210        if not isinstance(other, Iterable):
211            return NotImplemented
212        return self._from_iterable(value for value in other if value in self)
213
214    def isdisjoint(self, other):
215        for value in other:
216            if value in self:
217                return False
218        return True
219
220    def __or__(self, other):
221        if not isinstance(other, Iterable):
222            return NotImplemented
223        return self._from_iterable(itertools.chain(self, other))
224
225    def __sub__(self, other):
226        if not isinstance(other, Set):
227            if not isinstance(other, Iterable):
228                return NotImplemented
229            other = self._from_iterable(other)
230        return self._from_iterable(value for value in self
231                                   if value not in other)
232
233    def __xor__(self, other):
234        if not isinstance(other, Set):
235            if not isinstance(other, Iterable):
236                return NotImplemented
237            other = self._from_iterable(other)
238        return (self - other) | (other - self)
239
240    def _hash(self):
241        """Compute the hash value of a set.
242
243        Note that we don't define __hash__: not all sets are hashable.
244        But if you define a hashable set type, its __hash__ should
245        call this function.
246
247        This must be compatible __eq__.
248
249        All sets ought to compare equal if they contain the same
250        elements, regardless of how they are implemented, and
251        regardless of the order of the elements; so there's not much
252        freedom for __eq__ or __hash__.  We match the algorithm used
253        by the built-in frozenset type.
254        """
255        MAX = sys.maxsize
256        MASK = 2 * MAX + 1
257        n = len(self)
258        h = 1927868237 * (n + 1)
259        h &= MASK
260        for x in self:
261            hx = hash(x)
262            h ^= (hx ^ (hx << 16) ^ 89869747)  * 3644798167
263            h &= MASK
264        h = h * 69069 + 907133923
265        h &= MASK
266        if h > MAX:
267            h -= MASK + 1
268        if h == -1:
269            h = 590923713
270        return h
271
272Set.register(frozenset)
273
274
275class MutableSet(Set):
276
277    @abstractmethod
278    def add(self, value):
279        """Return True if it was added, False if already there."""
280        raise NotImplementedError
281
282    @abstractmethod
283    def discard(self, value):
284        """Return True if it was deleted, False if not there."""
285        raise NotImplementedError
286
287    def remove(self, value):
288        """Remove an element. If not a member, raise a KeyError."""
289        if value not in self:
290            raise KeyError(value)
291        self.discard(value)
292
293    def pop(self):
294        """Return the popped value.  Raise KeyError if empty."""
295        it = iter(self)
296        try:
297            value = it.__next__()
298        except StopIteration:
299            raise KeyError
300        self.discard(value)
301        return value
302
303    def clear(self):
304        """This is slow (creates N new iterators!) but effective."""
305        try:
306            while True:
307                self.pop()
308        except KeyError:
309            pass
310
311    def __ior__(self, it: Iterable):
312        for value in it:
313            self.add(value)
314        return self
315
316    def __iand__(self, c: Container):
317        for value in self:
318            if value not in c:
319                self.discard(value)
320        return self
321
322    def __ixor__(self, it: Iterable):
323        if not isinstance(it, Set):
324            it = self._from_iterable(it)
325        for value in it:
326            if value in self:
327                self.discard(value)
328            else:
329                self.add(value)
330        return self
331
332    def __isub__(self, it: Iterable):
333        for value in it:
334            self.discard(value)
335        return self
336
337MutableSet.register(set)
338
339
340### MAPPINGS ###
341
342
343class Mapping(metaclass=ABCMeta):
344
345    @abstractmethod
346    def __getitem__(self, key):
347        raise KeyError
348
349    def get(self, key, default=None):
350        try:
351            return self[key]
352        except KeyError:
353            return default
354
355    def __contains__(self, key):
356        try:
357            self[key]
358        except KeyError:
359            return False
360        else:
361            return True
362
363    @abstractmethod
364    def __len__(self):
365        return 0
366
367    @abstractmethod
368    def __iter__(self):
369        while False:
370            yield None
371
372    def keys(self):
373        return KeysView(self)
374
375    def items(self):
376        return ItemsView(self)
377
378    def values(self):
379        return ValuesView(self)
380
381    def __eq__(self, other):
382        return set(self) == set(other)
383
384    def __ne__(self, other):
385        return set(self) == set(other)
386
387class MappingView(metaclass=ABCMeta):
388
389    def __init__(self, mapping):
390        self._mapping = mapping
391
392    def __len__(self):
393        return len(self._mapping)
394
395
396class KeysView(MappingView, Set):
397
398    def __contains__(self, key):
399        return key in self._mapping
400
401    def __iter__(self):
402        for key in self._mapping:
403            yield key
404
405KeysView.register(dict_keys)
406
407
408class ItemsView(MappingView, Set):
409
410    def __contains__(self, item):
411        key, value = item
412        try:
413            v = self._mapping[key]
414        except KeyError:
415            return False
416        else:
417            return v == value
418
419    def __iter__(self):
420        for key in self._mapping:
421            yield (key, self._mapping[key])
422
423ItemsView.register(dict_items)
424
425
426class ValuesView(MappingView):
427
428    def __contains__(self, value):
429        for key in self._mapping:
430            if value == self._mapping[key]:
431                return True
432        return False
433
434    def __iter__(self):
435        for key in self._mapping:
436            yield self._mapping[key]
437
438ValuesView.register(dict_values)
439
440
441class MutableMapping(Mapping):
442
443    @abstractmethod
444    def __setitem__(self, key, value):
445        raise KeyError
446
447    @abstractmethod
448    def __delitem__(self, key):
449        raise KeyError
450
451    __marker = object()
452
453    def pop(self, key, default=__marker):
454        try:
455            value = self[key]
456        except KeyError:
457            if default is self.__marker:
458                raise
459            return default
460        else:
461            del self[key]
462            return value
463
464    def popitem(self):
465        try:
466            key = next(iter(self))
467        except StopIteration:
468            raise KeyError
469        value = self[key]
470        del self[key]
471        return key, value
472
473    def clear(self):
474        try:
475            while True:
476                self.popitem()
477        except KeyError:
478            pass
479
480    def update(self, other=(), **kwds):
481        if isinstance(other, Mapping):
482            for key in other:
483                self[key] = other[key]
484        elif hasattr(other, "keys"):
485            for key in other.keys():
486                self[key] = other[key]
487        else:
488            for key, value in other:
489                self[key] = value
490        for key, value in kwds.items():
491            self[key] = value
492
493    def setdefault(self, key, default=None):
494        try:
495            return self[key]
496        except KeyError:
497            self[key] = default
498        return default
499
500MutableMapping.register(dict)
501
502
503### SEQUENCES ###
504
505
506class Sequence(metaclass=ABCMeta):
507
508    """All the operations on a read-only sequence.
509
510    Concrete subclasses must override __new__ or __init__,
511    __getitem__, and __len__.
512    """
513
514    @abstractmethod
515    def __getitem__(self, index):
516        raise IndexError
517
518    @abstractmethod
519    def __len__(self):
520        return 0
521
522    def __iter__(self):
523        i = 0
524        while True:
525            try:
526                v = self[i]
527            except IndexError:
528                break
529            yield v
530            i += 1
531
532    def __contains__(self, value):
533        for v in self:
534            if v == value:
535                return True
536        return False
537
538    def __reversed__(self):
539        for i in reversed(range(len(self))):
540            yield self[i]
541
542    def index(self, value):
543        for i, v in enumerate(self):
544            if v == value:
545                return i
546        raise ValueError
547
548    def count(self, value):
549        return sum(1 for v in self if v == value)
550
551Sequence.register(tuple)
552Sequence.register(str)
553
554
555class ByteString(Sequence):
556
557    """This unifies bytes and bytearray.
558
559    XXX Should add all their methods.
560    """
561
562ByteString.register(bytes)
563ByteString.register(bytearray)
564
565
566class MutableSequence(Sequence):
567
568    @abstractmethod
569    def __setitem__(self, index, value):
570        raise IndexError
571
572    @abstractmethod
573    def __delitem__(self, index):
574        raise IndexError
575
576    @abstractmethod
577    def insert(self, index, value):
578        raise IndexError
579
580    def append(self, value):
581        self.insert(len(self), value)
582
583    def reverse(self):
584        n = len(self)
585        for i in range(n//2):
586            self[i], self[n-i-1] = self[n-i-1], self[i]
587
588    def extend(self, values):
589        for v in values:
590            self.append(v)
591
592    def pop(self, index=-1):
593        v = self[index]
594        del self[index]
595        return v
596
597    def remove(self, value):
598        del self[self.index(value)]
599
600    def __iadd__(self, values):
601        self.extend(values)
602
603MutableSequence.register(list)
604MutableSequence.register(bytearray)  # Multiply inheriting, see ByteString
605