| # 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) |