1
# Copyright 2007 Google, Inc. All Rights Reserved.
2
# Licensed to PSF under a Contributor Agreement.
4
"""Abstract Base Classes (ABCs) for collections, according to PEP 3119.
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.
11
from abc import ABCMeta, abstractmethod
14
__all__ = ["Hashable", "Iterable", "Iterator",
15
"Sized", "Container", "Callable",
17
"Mapping", "MutableMapping",
18
"MappingView", "KeysView", "ItemsView", "ValuesView",
19
"Sequence", "MutableSequence",
22
### ONE-TRICK PONIES ###
24
def _hasattr(C, attr):
26
return any(attr in B.__dict__ for B in C.__mro__)
27
except AttributeError:
29
return hasattr(C, attr)
33
__metaclass__ = ABCMeta
40
def __subclasshook__(cls, C):
44
if "__hash__" in B.__dict__:
45
if B.__dict__["__hash__"]:
48
except AttributeError:
50
if getattr(C, "__hash__", None):
56
__metaclass__ = ABCMeta
64
def __subclasshook__(cls, C):
66
if _hasattr(C, "__iter__"):
70
Iterable.register(str)
73
class Iterator(Iterable):
77
'Return the next item from the iterator. When exhausted, raise StopIteration'
84
def __subclasshook__(cls, C):
86
if _hasattr(C, "next") and _hasattr(C, "__iter__"):
92
__metaclass__ = ABCMeta
99
def __subclasshook__(cls, C):
101
if _hasattr(C, "__len__"):
103
return NotImplemented
107
__metaclass__ = ABCMeta
110
def __contains__(self, x):
114
def __subclasshook__(cls, C):
116
if _hasattr(C, "__contains__"):
118
return NotImplemented
122
__metaclass__ = ABCMeta
125
def __call__(self, *args, **kwds):
129
def __subclasshook__(cls, C):
131
if _hasattr(C, "__call__"):
133
return NotImplemented
139
class Set(Sized, Iterable, Container):
140
"""A set is a finite, iterable container.
142
This class provides concrete generic implementations of all
143
methods except for __contains__, __iter__ and __len__.
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.
150
def __le__(self, other):
151
if not isinstance(other, Set):
152
return NotImplemented
153
if len(self) > len(other):
156
if elem not in other:
160
def __lt__(self, other):
161
if not isinstance(other, Set):
162
return NotImplemented
163
return len(self) < len(other) and self.__le__(other)
165
def __gt__(self, other):
166
if not isinstance(other, Set):
167
return NotImplemented
168
return len(self) > len(other) and self.__ge__(other)
170
def __ge__(self, other):
171
if not isinstance(other, Set):
172
return NotImplemented
173
if len(self) < len(other):
180
def __eq__(self, other):
181
if not isinstance(other, Set):
182
return NotImplemented
183
return len(self) == len(other) and self.__le__(other)
185
def __ne__(self, other):
186
return not (self == other)
189
def _from_iterable(cls, it):
190
'''Construct an instance of the class from any iterable input.
192
Must override this method if the class constructor signature
193
does not accept an iterable for an input.
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)
204
def isdisjoint(self, other):
205
'Return True if two sets have a null intersection.'
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)
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)
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)
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)
244
# Sets are not hashable by default, but subclasses can change this
248
"""Compute the hash value of a set.
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
254
This must be compatible __eq__.
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.
265
h = 1927868237 * (n + 1)
269
h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167
271
h = h * 69069 + 907133923
279
Set.register(frozenset)
282
class MutableSet(Set):
283
"""A mutable set is a finite, iterable container.
285
This class provides concrete generic implementations of all
286
methods except for __contains__, __iter__, __len__,
287
add(), and discard().
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.
295
def add(self, value):
296
"""Add an element."""
297
raise NotImplementedError
300
def discard(self, value):
301
"""Remove an element. Do not raise an exception if absent."""
302
raise NotImplementedError
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)
311
"""Return the popped value. Raise KeyError if empty."""
315
except StopIteration:
321
"""This is slow (creates N new iterators!) but effective."""
328
def __ior__(self, it):
333
def __iand__(self, it):
334
for value in (self - it):
338
def __ixor__(self, it):
342
if not isinstance(it, Set):
343
it = self._from_iterable(it)
351
def __isub__(self, it):
359
MutableSet.register(set)
365
class Mapping(Sized, Iterable, Container):
367
"""A Mapping is a generic container for associating key/value
370
This class provides concrete generic implementations of all
371
methods except for __getitem__, __iter__, and __len__.
376
def __getitem__(self, key):
379
def get(self, key, default=None):
380
'D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.'
386
def __contains__(self, key):
395
'D.iterkeys() -> an iterator over the keys of D'
398
def itervalues(self):
399
'D.itervalues() -> an iterator over the values of D'
404
'D.iteritems() -> an iterator over the (key, value) items of D'
406
yield (key, self[key])
409
"D.keys() -> list of D's keys"
413
"D.items() -> list of D's (key, value) pairs, as 2-tuples"
414
return [(key, self[key]) for key in self]
417
"D.values() -> list of D's values"
418
return [self[key] for key in self]
420
# Mappings are not hashable by default, but subclasses can change this
423
def __eq__(self, other):
424
if not isinstance(other, Mapping):
425
return NotImplemented
426
return dict(self.items()) == dict(other.items())
428
def __ne__(self, other):
429
return not (self == other)
431
class MappingView(Sized):
433
def __init__(self, mapping):
434
self._mapping = mapping
437
return len(self._mapping)
440
return '{0.__class__.__name__}({0._mapping!r})'.format(self)
443
class KeysView(MappingView, Set):
446
def _from_iterable(self, it):
449
def __contains__(self, key):
450
return key in self._mapping
453
for key in self._mapping:
456
KeysView.register(type({}.viewkeys()))
458
class ItemsView(MappingView, Set):
461
def _from_iterable(self, it):
464
def __contains__(self, item):
467
v = self._mapping[key]
474
for key in self._mapping:
475
yield (key, self._mapping[key])
477
ItemsView.register(type({}.viewitems()))
479
class ValuesView(MappingView):
481
def __contains__(self, value):
482
for key in self._mapping:
483
if value == self._mapping[key]:
488
for key in self._mapping:
489
yield self._mapping[key]
491
ValuesView.register(type({}.viewvalues()))
493
class MutableMapping(Mapping):
495
"""A MutableMapping is a generic container for associating
498
This class provides concrete generic implementations of all
499
methods except for __getitem__, __setitem__, __delitem__,
500
__iter__, and __len__.
505
def __setitem__(self, key, value):
509
def __delitem__(self, key):
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.
521
if default is self.__marker:
529
'''D.popitem() -> (k, v), remove and return some (key, value) pair
530
as a 2-tuple; but raise KeyError if D is empty.
533
key = next(iter(self))
534
except StopIteration:
541
'D.clear() -> None. Remove all items from D.'
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
555
raise TypeError("descriptor 'update' of 'MutableMapping' object "
560
raise TypeError('update expected at most 1 arguments, got %d' %
564
if isinstance(other, Mapping):
566
self[key] = other[key]
567
elif hasattr(other, "keys"):
568
for key in other.keys():
569
self[key] = other[key]
571
for key, value in other:
573
for key, value in kwds.items():
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'
584
MutableMapping.register(dict)
590
class Sequence(Sized, Iterable, Container):
591
"""All the operations on a read-only sequence.
593
Concrete subclasses must override __new__ or __init__,
594
__getitem__, and __len__.
598
def __getitem__(self, index):
611
def __contains__(self, value):
617
def __reversed__(self):
618
for i in reversed(range(len(self))):
621
def index(self, value):
622
'''S.index(value) -> integer -- return first index of value.
623
Raises ValueError if the value is not present.
625
for i, v in enumerate(self):
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)
634
Sequence.register(tuple)
635
Sequence.register(basestring)
636
Sequence.register(buffer)
637
Sequence.register(xrange)
640
class MutableSequence(Sequence):
642
"""All the operations on a read-only sequence.
644
Concrete subclasses must provide __new__ or __init__,
645
__getitem__, __setitem__, __delitem__, __len__, and insert().
650
def __setitem__(self, index, value):
654
def __delitem__(self, index):
658
def insert(self, index, value):
659
'S.insert(index, object) -- insert object before index'
662
def append(self, value):
663
'S.append(object) -- append object to the end of the sequence'
664
self.insert(len(self), value)
667
'S.reverse() -- reverse *IN PLACE*'
669
for i in range(n//2):
670
self[i], self[n-i-1] = self[n-i-1], self[i]
672
def extend(self, values):
673
'S.extend(iterable) -- extend sequence by appending elements from the iterable'
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.
685
def remove(self, value):
686
'''S.remove(value) -- remove first occurrence of value.
687
Raise ValueError if the value is not present.
689
del self[self.index(value)]
691
def __iadd__(self, values):
695
MutableSequence.register(list)
1
# Copyright 2007 Google, Inc. All Rights Reserved.
2
# Licensed to PSF under a Contributor Agreement.
4
"""Abstract Base Classes (ABCs) for collections, according to PEP 3119.
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.
11
from abc import ABCMeta, abstractmethod
14
__all__ = ["Hashable", "Iterable", "Iterator",
15
"Sized", "Container", "Callable",
17
"Mapping", "MutableMapping",
18
"MappingView", "KeysView", "ItemsView", "ValuesView",
19
"Sequence", "MutableSequence",
22
### ONE-TRICK PONIES ###
24
def _hasattr(C, attr):
26
return any(attr in B.__dict__ for B in C.__mro__)
27
except AttributeError:
29
return hasattr(C, attr)
33
__metaclass__ = ABCMeta
40
def __subclasshook__(cls, C):
44
if "__hash__" in B.__dict__:
45
if B.__dict__["__hash__"]:
48
except AttributeError:
50
if getattr(C, "__hash__", None):
56
__metaclass__ = ABCMeta
64
def __subclasshook__(cls, C):
66
if _hasattr(C, "__iter__"):
70
Iterable.register(str)
73
class Iterator(Iterable):
77
'Return the next item from the iterator. When exhausted, raise StopIteration'
84
def __subclasshook__(cls, C):
86
if _hasattr(C, "next") and _hasattr(C, "__iter__"):
92
__metaclass__ = ABCMeta
99
def __subclasshook__(cls, C):
101
if _hasattr(C, "__len__"):
103
return NotImplemented
107
__metaclass__ = ABCMeta
110
def __contains__(self, x):
114
def __subclasshook__(cls, C):
116
if _hasattr(C, "__contains__"):
118
return NotImplemented
122
__metaclass__ = ABCMeta
125
def __call__(self, *args, **kwds):
129
def __subclasshook__(cls, C):
131
if _hasattr(C, "__call__"):
133
return NotImplemented
139
class Set(Sized, Iterable, Container):
140
"""A set is a finite, iterable container.
142
This class provides concrete generic implementations of all
143
methods except for __contains__, __iter__ and __len__.
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.
150
def __le__(self, other):
151
if not isinstance(other, Set):
152
return NotImplemented
153
if len(self) > len(other):
156
if elem not in other:
160
def __lt__(self, other):
161
if not isinstance(other, Set):
162
return NotImplemented
163
return len(self) < len(other) and self.__le__(other)
165
def __gt__(self, other):
166
if not isinstance(other, Set):
167
return NotImplemented
168
return len(self) > len(other) and self.__ge__(other)
170
def __ge__(self, other):
171
if not isinstance(other, Set):
172
return NotImplemented
173
if len(self) < len(other):
180
def __eq__(self, other):
181
if not isinstance(other, Set):
182
return NotImplemented
183
return len(self) == len(other) and self.__le__(other)
185
def __ne__(self, other):
186
return not (self == other)
189
def _from_iterable(cls, it):
190
'''Construct an instance of the class from any iterable input.
192
Must override this method if the class constructor signature
193
does not accept an iterable for an input.
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)
204
def isdisjoint(self, other):
205
'Return True if two sets have a null intersection.'
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)
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)
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)
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)
244
# Sets are not hashable by default, but subclasses can change this
248
"""Compute the hash value of a set.
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
254
This must be compatible __eq__.
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.
265
h = 1927868237 * (n + 1)
269
h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167
271
h = h * 69069 + 907133923
279
Set.register(frozenset)
282
class MutableSet(Set):
283
"""A mutable set is a finite, iterable container.
285
This class provides concrete generic implementations of all
286
methods except for __contains__, __iter__, __len__,
287
add(), and discard().
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.
295
def add(self, value):
296
"""Add an element."""
297
raise NotImplementedError
300
def discard(self, value):
301
"""Remove an element. Do not raise an exception if absent."""
302
raise NotImplementedError
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)
311
"""Return the popped value. Raise KeyError if empty."""
315
except StopIteration:
321
"""This is slow (creates N new iterators!) but effective."""
328
def __ior__(self, it):
333
def __iand__(self, it):
334
for value in (self - it):
338
def __ixor__(self, it):
342
if not isinstance(it, Set):
343
it = self._from_iterable(it)
351
def __isub__(self, it):
359
MutableSet.register(set)
365
class Mapping(Sized, Iterable, Container):
367
"""A Mapping is a generic container for associating key/value
370
This class provides concrete generic implementations of all
371
methods except for __getitem__, __iter__, and __len__.
376
def __getitem__(self, key):
379
def get(self, key, default=None):
380
'D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.'
386
def __contains__(self, key):
395
'D.iterkeys() -> an iterator over the keys of D'
398
def itervalues(self):
399
'D.itervalues() -> an iterator over the values of D'
404
'D.iteritems() -> an iterator over the (key, value) items of D'
406
yield (key, self[key])
409
"D.keys() -> list of D's keys"
413
"D.items() -> list of D's (key, value) pairs, as 2-tuples"
414
return [(key, self[key]) for key in self]
417
"D.values() -> list of D's values"
418
return [self[key] for key in self]
420
# Mappings are not hashable by default, but subclasses can change this
423
def __eq__(self, other):
424
if not isinstance(other, Mapping):
425
return NotImplemented
426
return dict(self.items()) == dict(other.items())
428
def __ne__(self, other):
429
return not (self == other)
431
class MappingView(Sized):
433
def __init__(self, mapping):
434
self._mapping = mapping
437
return len(self._mapping)
440
return '{0.__class__.__name__}({0._mapping!r})'.format(self)
443
class KeysView(MappingView, Set):
446
def _from_iterable(self, it):
449
def __contains__(self, key):
450
return key in self._mapping
453
for key in self._mapping:
456
KeysView.register(type({}.viewkeys()))
458
class ItemsView(MappingView, Set):
461
def _from_iterable(self, it):
464
def __contains__(self, item):
467
v = self._mapping[key]
474
for key in self._mapping:
475
yield (key, self._mapping[key])
477
ItemsView.register(type({}.viewitems()))
479
class ValuesView(MappingView):
481
def __contains__(self, value):
482
for key in self._mapping:
483
if value == self._mapping[key]:
488
for key in self._mapping:
489
yield self._mapping[key]
491
ValuesView.register(type({}.viewvalues()))
493
class MutableMapping(Mapping):
495
"""A MutableMapping is a generic container for associating
498
This class provides concrete generic implementations of all
499
methods except for __getitem__, __setitem__, __delitem__,
500
__iter__, and __len__.
505
def __setitem__(self, key, value):
509
def __delitem__(self, key):
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.
521
if default is self.__marker:
529
'''D.popitem() -> (k, v), remove and return some (key, value) pair
530
as a 2-tuple; but raise KeyError if D is empty.
533
key = next(iter(self))
534
except StopIteration:
541
'D.clear() -> None. Remove all items from D.'
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
555
raise TypeError("descriptor 'update' of 'MutableMapping' object "
560
raise TypeError('update expected at most 1 arguments, got %d' %
564
if isinstance(other, Mapping):
566
self[key] = other[key]
567
elif hasattr(other, "keys"):
568
for key in other.keys():
569
self[key] = other[key]
571
for key, value in other:
573
for key, value in kwds.items():
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'
584
MutableMapping.register(dict)
590
class Sequence(Sized, Iterable, Container):
591
"""All the operations on a read-only sequence.
593
Concrete subclasses must override __new__ or __init__,
594
__getitem__, and __len__.
598
def __getitem__(self, index):
611
def __contains__(self, value):
617
def __reversed__(self):
618
for i in reversed(range(len(self))):
621
def index(self, value):
622
'''S.index(value) -> integer -- return first index of value.
623
Raises ValueError if the value is not present.
625
for i, v in enumerate(self):
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)
634
Sequence.register(tuple)
635
Sequence.register(basestring)
636
Sequence.register(buffer)
637
Sequence.register(xrange)
640
class MutableSequence(Sequence):
642
"""All the operations on a read-only sequence.
644
Concrete subclasses must provide __new__ or __init__,
645
__getitem__, __setitem__, __delitem__, __len__, and insert().
650
def __setitem__(self, index, value):
654
def __delitem__(self, index):
658
def insert(self, index, value):
659
'S.insert(index, object) -- insert object before index'
662
def append(self, value):
663
'S.append(object) -- append object to the end of the sequence'
664
self.insert(len(self), value)
667
'S.reverse() -- reverse *IN PLACE*'
669
for i in range(n//2):
670
self[i], self[n-i-1] = self[n-i-1], self[i]
672
def extend(self, values):
673
'S.extend(iterable) -- extend sequence by appending elements from the iterable'
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.
685
def remove(self, value):
686
'''S.remove(value) -- remove first occurrence of value.
687
Raise ValueError if the value is not present.
689
del self[self.index(value)]
691
def __iadd__(self, values):
695
MutableSequence.register(list)
added
removed
python/Lib/_abcoll.py
