# Copyright 2007 Google, Inc. All Rights Reserved. | |
# Licensed to PSF under a Contributor Agreement. | |
"""Abstract Base Classes (ABCs) for collections, according to PEP 3119. | |
DON'T USE THIS MODULE DIRECTLY! The classes here should be imported | |
via collections; they are defined here only to alleviate certain | |
bootstrapping issues. Unit tests are in test_collections. | |
""" | |
from abc import ABCMeta, abstractmethod | |
import sys | |
__all__ = ["Hashable", "Iterable", "Iterator", | |
"Sized", "Container", "Callable", | |
"Set", "MutableSet", | |
"Mapping", "MutableMapping", | |
"MappingView", "KeysView", "ItemsView", "ValuesView", | |
"Sequence", "MutableSequence", | |
] | |
### ONE-TRICK PONIES ### | |
def _hasattr(C, attr): | |
try: | |
return any(attr in B.__dict__ for B in C.__mro__) | |
except AttributeError: | |
# Old-style class | |
return hasattr(C, attr) | |
class Hashable: | |
__metaclass__ = ABCMeta | |
@abstractmethod | |
def __hash__(self): | |
return 0 | |
@classmethod | |
def __subclasshook__(cls, C): | |
if cls is Hashable: | |
try: | |
for B in C.__mro__: | |
if "__hash__" in B.__dict__: | |
if B.__dict__["__hash__"]: | |
return True | |
break | |
except AttributeError: | |
# Old-style class | |
if getattr(C, "__hash__", None): | |
return True | |
return NotImplemented | |
class Iterable: | |
__metaclass__ = ABCMeta | |
@abstractmethod | |
def __iter__(self): | |
while False: | |
yield None | |
@classmethod | |
def __subclasshook__(cls, C): | |
if cls is Iterable: | |
if _hasattr(C, "__iter__"): | |
return True | |
return NotImplemented | |
Iterable.register(str) | |
class Iterator(Iterable): | |
@abstractmethod | |
def next(self): | |
raise StopIteration | |
def __iter__(self): | |
return self | |
@classmethod | |
def __subclasshook__(cls, C): | |
if cls is Iterator: | |
if _hasattr(C, "next") and _hasattr(C, "__iter__"): | |
return True | |
return NotImplemented | |
class Sized: | |
__metaclass__ = ABCMeta | |
@abstractmethod | |
def __len__(self): | |
return 0 | |
@classmethod | |
def __subclasshook__(cls, C): | |
if cls is Sized: | |
if _hasattr(C, "__len__"): | |
return True | |
return NotImplemented | |
class Container: | |
__metaclass__ = ABCMeta | |
@abstractmethod | |
def __contains__(self, x): | |
return False | |
@classmethod | |
def __subclasshook__(cls, C): | |
if cls is Container: | |
if _hasattr(C, "__contains__"): | |
return True | |
return NotImplemented | |
class Callable: | |
__metaclass__ = ABCMeta | |
@abstractmethod | |
def __call__(self, *args, **kwds): | |
return False | |
@classmethod | |
def __subclasshook__(cls, C): | |
if cls is Callable: | |
if _hasattr(C, "__call__"): | |
return True | |
return NotImplemented | |
### SETS ### | |
class Set(Sized, Iterable, Container): | |
"""A set is a finite, iterable container. | |
This class provides concrete generic implementations of all | |
methods except for __contains__, __iter__ and __len__. | |
To override the comparisons (presumably for speed, as the | |
semantics are fixed), all you have to do is redefine __le__ and | |
then the other operations will automatically follow suit. | |
""" | |
def __le__(self, other): | |
if not isinstance(other, Set): | |
return NotImplemented | |
if len(self) > len(other): | |
return False | |
for elem in self: | |
if elem not in other: | |
return False | |
return True | |
def __lt__(self, other): | |
if not isinstance(other, Set): | |
return NotImplemented | |
return len(self) < len(other) and self.__le__(other) | |
def __gt__(self, other): | |
if not isinstance(other, Set): | |
return NotImplemented | |
return other < self | |
def __ge__(self, other): | |
if not isinstance(other, Set): | |
return NotImplemented | |
return other <= self | |
def __eq__(self, other): | |
if not isinstance(other, Set): | |
return NotImplemented | |
return len(self) == len(other) and self.__le__(other) | |
def __ne__(self, other): | |
return not (self == other) | |
@classmethod | |
def _from_iterable(cls, it): | |
'''Construct an instance of the class from any iterable input. | |
Must override this method if the class constructor signature | |
does not accept an iterable for an input. | |
''' | |
return cls(it) | |
def __and__(self, other): | |
if not isinstance(other, Iterable): | |
return NotImplemented | |
return self._from_iterable(value for value in other if value in self) | |
def isdisjoint(self, other): | |
for value in other: | |
if value in self: | |
return False | |
return True | |
def __or__(self, other): | |
if not isinstance(other, Iterable): | |
return NotImplemented | |
chain = (e for s in (self, other) for e in s) | |
return self._from_iterable(chain) | |
def __sub__(self, other): | |
if not isinstance(other, Set): | |
if not isinstance(other, Iterable): | |
return NotImplemented | |
other = self._from_iterable(other) | |
return self._from_iterable(value for value in self | |
if value not in other) | |
def __xor__(self, other): | |
if not isinstance(other, Set): | |
if not isinstance(other, Iterable): | |
return NotImplemented | |
other = self._from_iterable(other) | |
return (self - other) | (other - self) | |
# Sets are not hashable by default, but subclasses can change this | |
__hash__ = None | |
def _hash(self): | |
"""Compute the hash value of a set. | |
Note that we don't define __hash__: not all sets are hashable. | |
But if you define a hashable set type, its __hash__ should | |
call this function. | |
This must be compatible __eq__. | |
All sets ought to compare equal if they contain the same | |
elements, regardless of how they are implemented, and | |
regardless of the order of the elements; so there's not much | |
freedom for __eq__ or __hash__. We match the algorithm used | |
by the built-in frozenset type. | |
""" | |
MAX = sys.maxint | |
MASK = 2 * MAX + 1 | |
n = len(self) | |
h = 1927868237 * (n + 1) | |
h &= MASK | |
for x in self: | |
hx = hash(x) | |
h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167 | |
h &= MASK | |
h = h * 69069 + 907133923 | |
h &= MASK | |
if h > MAX: | |
h -= MASK + 1 | |
if h == -1: | |
h = 590923713 | |
return h | |
Set.register(frozenset) | |
class MutableSet(Set): | |
@abstractmethod | |
def add(self, value): | |
"""Add an element.""" | |
raise NotImplementedError | |
@abstractmethod | |
def discard(self, value): | |
"""Remove an element. Do not raise an exception if absent.""" | |
raise NotImplementedError | |
def remove(self, value): | |
"""Remove an element. If not a member, raise a KeyError.""" | |
if value not in self: | |
raise KeyError(value) | |
self.discard(value) | |
def pop(self): | |
"""Return the popped value. Raise KeyError if empty.""" | |
it = iter(self) | |
try: | |
value = next(it) | |
except StopIteration: | |
raise KeyError | |
self.discard(value) | |
return value | |
def clear(self): | |
"""This is slow (creates N new iterators!) but effective.""" | |
try: | |
while True: | |
self.pop() | |
except KeyError: | |
pass | |
def __ior__(self, it): | |
for value in it: | |
self.add(value) | |
return self | |
def __iand__(self, it): | |
for value in (self - it): | |
self.discard(value) | |
return self | |
def __ixor__(self, it): | |
if it is self: | |
self.clear() | |
else: | |
if not isinstance(it, Set): | |
it = self._from_iterable(it) | |
for value in it: | |
if value in self: | |
self.discard(value) | |
else: | |
self.add(value) | |
return self | |
def __isub__(self, it): | |
if it is self: | |
self.clear() | |
else: | |
for value in it: | |
self.discard(value) | |
return self | |
MutableSet.register(set) | |
### MAPPINGS ### | |
class Mapping(Sized, Iterable, Container): | |
@abstractmethod | |
def __getitem__(self, key): | |
raise KeyError | |
def get(self, key, default=None): | |
try: | |
return self[key] | |
except KeyError: | |
return default | |
def __contains__(self, key): | |
try: | |
self[key] | |
except KeyError: | |
return False | |
else: | |
return True | |
def iterkeys(self): | |
return iter(self) | |
def itervalues(self): | |
for key in self: | |
yield self[key] | |
def iteritems(self): | |
for key in self: | |
yield (key, self[key]) | |
def keys(self): | |
return list(self) | |
def items(self): | |
return [(key, self[key]) for key in self] | |
def values(self): | |
return [self[key] for key in self] | |
# Mappings are not hashable by default, but subclasses can change this | |
__hash__ = None | |
def __eq__(self, other): | |
if not isinstance(other, Mapping): | |
return NotImplemented | |
return dict(self.items()) == dict(other.items()) | |
def __ne__(self, other): | |
return not (self == other) | |
class MappingView(Sized): | |
def __init__(self, mapping): | |
self._mapping = mapping | |
def __len__(self): | |
return len(self._mapping) | |
def __repr__(self): | |
return '{0.__class__.__name__}({0._mapping!r})'.format(self) | |
class KeysView(MappingView, Set): | |
@classmethod | |
def _from_iterable(self, it): | |
return set(it) | |
def __contains__(self, key): | |
return key in self._mapping | |
def __iter__(self): | |
for key in self._mapping: | |
yield key | |
class ItemsView(MappingView, Set): | |
@classmethod | |
def _from_iterable(self, it): | |
return set(it) | |
def __contains__(self, item): | |
key, value = item | |
try: | |
v = self._mapping[key] | |
except KeyError: | |
return False | |
else: | |
return v == value | |
def __iter__(self): | |
for key in self._mapping: | |
yield (key, self._mapping[key]) | |
class ValuesView(MappingView): | |
def __contains__(self, value): | |
for key in self._mapping: | |
if value == self._mapping[key]: | |
return True | |
return False | |
def __iter__(self): | |
for key in self._mapping: | |
yield self._mapping[key] | |
class MutableMapping(Mapping): | |
@abstractmethod | |
def __setitem__(self, key, value): | |
raise KeyError | |
@abstractmethod | |
def __delitem__(self, key): | |
raise KeyError | |
__marker = object() | |
def pop(self, key, default=__marker): | |
try: | |
value = self[key] | |
except KeyError: | |
if default is self.__marker: | |
raise | |
return default | |
else: | |
del self[key] | |
return value | |
def popitem(self): | |
try: | |
key = next(iter(self)) | |
except StopIteration: | |
raise KeyError | |
value = self[key] | |
del self[key] | |
return key, value | |
def clear(self): | |
try: | |
while True: | |
self.popitem() | |
except KeyError: | |
pass | |
def update(*args, **kwds): | |
if len(args) > 2: | |
raise TypeError("update() takes at most 2 positional " | |
"arguments ({} given)".format(len(args))) | |
elif not args: | |
raise TypeError("update() takes at least 1 argument (0 given)") | |
self = args[0] | |
other = args[1] if len(args) >= 2 else () | |
if isinstance(other, Mapping): | |
for key in other: | |
self[key] = other[key] | |
elif hasattr(other, "keys"): | |
for key in other.keys(): | |
self[key] = other[key] | |
else: | |
for key, value in other: | |
self[key] = value | |
for key, value in kwds.items(): | |
self[key] = value | |
def setdefault(self, key, default=None): | |
try: | |
return self[key] | |
except KeyError: | |
self[key] = default | |
return default | |
MutableMapping.register(dict) | |
### SEQUENCES ### | |
class Sequence(Sized, Iterable, Container): | |
"""All the operations on a read-only sequence. | |
Concrete subclasses must override __new__ or __init__, | |
__getitem__, and __len__. | |
""" | |
@abstractmethod | |
def __getitem__(self, index): | |
raise IndexError | |
def __iter__(self): | |
i = 0 | |
try: | |
while True: | |
v = self[i] | |
yield v | |
i += 1 | |
except IndexError: | |
return | |
def __contains__(self, value): | |
for v in self: | |
if v == value: | |
return True | |
return False | |
def __reversed__(self): | |
for i in reversed(range(len(self))): | |
yield self[i] | |
def index(self, value): | |
for i, v in enumerate(self): | |
if v == value: | |
return i | |
raise ValueError | |
def count(self, value): | |
return sum(1 for v in self if v == value) | |
Sequence.register(tuple) | |
Sequence.register(basestring) | |
Sequence.register(buffer) | |
Sequence.register(xrange) | |
class MutableSequence(Sequence): | |
@abstractmethod | |
def __setitem__(self, index, value): | |
raise IndexError | |
@abstractmethod | |
def __delitem__(self, index): | |
raise IndexError | |
@abstractmethod | |
def insert(self, index, value): | |
raise IndexError | |
def append(self, value): | |
self.insert(len(self), value) | |
def reverse(self): | |
n = len(self) | |
for i in range(n//2): | |
self[i], self[n-i-1] = self[n-i-1], self[i] | |
def extend(self, values): | |
for v in values: | |
self.append(v) | |
def pop(self, index=-1): | |
v = self[index] | |
del self[index] | |
return v | |
def remove(self, value): | |
del self[self.index(value)] | |
def __iadd__(self, values): | |
self.extend(values) | |
return self | |
MutableSequence.register(list) |