Backport of _abccoll.py by Benjamin Arangueren, issue 1383.

With some changes of my own thrown in (e.g. backport of r58107).

1 files changed, 544 insertions, 0 deletions

diff --git a/Lib/_abcoll.py b/Lib/_abcoll.py
new file mode 100644
index 0000000..ac967b2
--- /dev/null
+++ b/Lib/_abcoll.py
@@ -0,0 +1,544 @@
+# 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
+
+__all__ = ["Hashable", "Iterable", "Iterator",
+           "Sized", "Container", "Callable",
+           "Set", "MutableSet",
+           "Mapping", "MutableMapping",
+           "MappingView", "KeysView", "ItemsView", "ValuesView",
+           "Sequence", "MutableSequence",
+           ]
+
+### ONE-TRICK PONIES ###
+
+class Hashable:
+    __metaclass__ = ABCMeta
+
+    @abstractmethod
+    def __hash__(self):
+        return 0
+
+    @classmethod
+    def __subclasshook__(cls, C):
+        if cls is Hashable:
+            for B in C.__mro__:
+                if "__hash__" in B.__dict__:
+                    if B.__dict__["__hash__"]:
+                        return True
+                    break
+        return NotImplemented
+
+
+class Iterable:
+    __metaclass__ = ABCMeta
+
+    @abstractmethod
+    def __iter__(self):
+        while False:
+            yield None
+
+    @classmethod
+    def __subclasshook__(cls, C):
+        if cls is Iterable:
+            if any("__iter__" in B.__dict__ for B in C.__mro__):
+                return True
+        return NotImplemented
+
+Iterable.register(str)
+
+
+class Iterator:
+    __metaclass__ = ABCMeta
+
+    @abstractmethod
+    def __next__(self):
+        raise StopIteration
+
+    def __iter__(self):
+        return self
+
+    @classmethod
+    def __subclasshook__(cls, C):
+        if cls is Iterator:
+            if any("next" in B.__dict__ for B in C.__mro__):
+                return True
+        return NotImplemented
+
+
+class Sized:
+    __metaclass__ = ABCMeta
+
+    @abstractmethod
+    def __len__(self):
+        return 0
+
+    @classmethod
+    def __subclasshook__(cls, C):
+        if cls is Sized:
+            if any("__len__" in B.__dict__ for B in C.__mro__):
+                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 any("__contains__" in B.__dict__ for B in C.__mro__):
+                return True
+        return NotImplemented
+
+
+class Callable:
+    __metaclass__ = ABCMeta
+
+    @abstractmethod
+    def __contains__(self, x):
+        return False
+
+    @classmethod
+    def __subclasshook__(cls, C):
+        if cls is Callable:
+            if any("__call__" in B.__dict__ for B in C.__mro__):
+                return True
+        return NotImplemented
+
+
+### SETS ###
+
+
+class Set:
+    __metaclass__ = ABCMeta
+
+    """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.
+    """
+
+    @abstractmethod
+    def __contains__(self, value):
+        return False
+
+    @abstractmethod
+    def __iter__(self):
+        while False:
+            yield None
+
+    @abstractmethod
+    def __len__(self):
+        return 0
+
+    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 __eq__(self, other):
+        if not isinstance(other, Set):
+            return NotImplemented
+        return len(self) == len(other) and self.__le__(other)
+
+    @classmethod
+    def _from_iterable(cls, it):
+        return frozenset(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 __or__(self, other):
+        if not isinstance(other, Iterable):
+            return NotImplemented
+        return self._from_iterable(itertools.chain(self, other))
+
+    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)
+
+    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):
+        """Return True if it was added, False if already there."""
+        raise NotImplementedError
+
+    @abstractmethod
+    def discard(self, value):
+        """Return True if it was deleted, False if not there."""
+        raise NotImplementedError
+
+    def pop(self):
+        """Return the popped value.  Raise KeyError if empty."""
+        it = iter(self)
+        try:
+            value = it.__next__()
+        except StopIteration:
+            raise KeyError
+        self.discard(value)
+        return value
+
+    def toggle(self, value):
+        """Return True if it was added, False if deleted."""
+        # XXX This implementation is not thread-safe
+        if value in self:
+            self.discard(value)
+            return False
+        else:
+            self.add(value)
+            return True
+
+    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, c):
+        for value in self:
+            if value not in c:
+                self.discard(value)
+        return self
+
+    def __ixor__(self, it):
+        # This calls toggle(), so if that is overridded, we call the override
+        for value in it:
+            self.toggle(it)
+        return self
+
+    def __isub__(self, it):
+        for value in it:
+            self.discard(value)
+        return self
+
+MutableSet.register(set)
+
+
+### MAPPINGS ###
+
+
+class Mapping:
+    __metaclass__ = ABCMeta
+
+    @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
+
+    @abstractmethod
+    def __len__(self):
+        return 0
+
+    @abstractmethod
+    def __iter__(self):
+        while False:
+            yield None
+
+    def keys(self):
+        return KeysView(self)
+
+    def items(self):
+        return ItemsView(self)
+
+    def values(self):
+        return ValuesView(self)
+
+
+class MappingView:
+    __metaclass__ = ABCMeta
+
+    def __init__(self, mapping):
+        self._mapping = mapping
+
+    def __len__(self):
+        return len(self._mapping)
+
+
+class KeysView(MappingView, Set):
+
+    def __contains__(self, key):
+        return key in self._mapping
+
+    def __iter__(self):
+        for key in self._mapping:
+            yield key
+
+KeysView.register(type({}.keys()))
+
+
+class ItemsView(MappingView, Set):
+
+    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])
+
+ItemsView.register(type({}.items()))
+
+
+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]
+
+ValuesView.register(type({}.values()))
+
+
+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(self, other=(), **kwds):
+        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
+
+MutableMapping.register(dict)
+
+
+### SEQUENCES ###
+
+
+class Sequence:
+    __metaclass__ = ABCMeta
+
+    """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
+
+    @abstractmethod
+    def __len__(self):
+        return 0
+
+    def __iter__(self):
+        i = 0
+        while True:
+            try:
+                v = self[i]
+            except IndexError:
+                break
+            yield v
+            i += 1
+
+    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)
+
+
+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)
+
+MutableSequence.register(list)