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