summaryrefslogtreecommitdiffstats
path: root/Lib/_abcoll.py
diff options
context:
space:
mode:
authorGuido van Rossum <guido@python.org>2007-06-13 18:07:49 (GMT)
committerGuido van Rossum <guido@python.org>2007-06-13 18:07:49 (GMT)
commitcd16bf640405065e4702539632ce577536207d88 (patch)
treef4aaa3bdd36bc4811f4441e2a0e4d3dd7957c891 /Lib/_abcoll.py
parent6374bb5a699a6e21214bec2bbe2e527fd219b8ba (diff)
downloadcpython-cd16bf640405065e4702539632ce577536207d88.zip
cpython-cd16bf640405065e4702539632ce577536207d88.tar.gz
cpython-cd16bf640405065e4702539632ce577536207d88.tar.bz2
Merged revisions 55817-55961 via svnmerge from
svn+ssh://pythondev@svn.python.org/python/branches/p3yk ................ r55837 | guido.van.rossum | 2007-06-08 16:04:42 -0700 (Fri, 08 Jun 2007) | 2 lines PEP 3119 -- the abc module. ................ r55838 | guido.van.rossum | 2007-06-08 17:38:55 -0700 (Fri, 08 Jun 2007) | 2 lines Implement part of PEP 3119 -- One Trick Ponies. ................ r55847 | guido.van.rossum | 2007-06-09 08:28:06 -0700 (Sat, 09 Jun 2007) | 2 lines Different way to do one trick ponies, allowing registration (per PEP strawman). ................ r55849 | guido.van.rossum | 2007-06-09 18:06:38 -0700 (Sat, 09 Jun 2007) | 3 lines Make sure that the magic looking for __hash__ (etc.) doesn't apply to real subclasses of Hashable. ................ r55852 | guido.van.rossum | 2007-06-10 08:29:51 -0700 (Sun, 10 Jun 2007) | 2 lines Add some more examples, e.g. generators and dict views. ................ r55853 | guido.van.rossum | 2007-06-10 08:31:59 -0700 (Sun, 10 Jun 2007) | 2 lines keys() and items() *are* containers -- just values() isn't. ................ r55864 | georg.brandl | 2007-06-10 15:29:40 -0700 (Sun, 10 Jun 2007) | 2 lines PEP 3127: new octal literals, binary literals. ................ r55865 | georg.brandl | 2007-06-10 15:31:37 -0700 (Sun, 10 Jun 2007) | 2 lines Some octal literal fixes in Tools. ................ r55866 | georg.brandl | 2007-06-10 15:37:43 -0700 (Sun, 10 Jun 2007) | 2 lines Tokenizer changes for PEP 3127. ................ r55867 | georg.brandl | 2007-06-10 15:37:55 -0700 (Sun, 10 Jun 2007) | 2 lines Some docs for PEP 3127. ................ r55868 | georg.brandl | 2007-06-10 15:44:39 -0700 (Sun, 10 Jun 2007) | 2 lines Missed a place in intobject.c. Is that used anymore anyway? ................ r55871 | neal.norwitz | 2007-06-10 18:31:49 -0700 (Sun, 10 Jun 2007) | 182 lines Merged revisions 55729-55868 via svnmerge from svn+ssh://pythondev@svn.python.org/python/trunk ........ r55731 | neal.norwitz | 2007-06-01 00:29:12 -0700 (Fri, 01 Jun 2007) | 7 lines SF 1668596/1720897: distutils now copies data files even if package_dir is empty. This needs to be backported. I'm too tired tonight. It would be great if someone backports this if the buildbots are ok with it. Otherwise, I will try to get to it tomorrow. ........ r55732 | georg.brandl | 2007-06-01 04:33:33 -0700 (Fri, 01 Jun 2007) | 2 lines Bug #1722484: remove docstrings again when running with -OO. ........ r55735 | georg.brandl | 2007-06-01 12:20:27 -0700 (Fri, 01 Jun 2007) | 2 lines Fix wrong issue number. ........ r55739 | brett.cannon | 2007-06-01 20:02:29 -0700 (Fri, 01 Jun 2007) | 3 lines Have configure raise an error when building on AtheOS. Code specific to AtheOS will be removed in Python 2.7. ........ r55746 | neal.norwitz | 2007-06-02 11:33:53 -0700 (Sat, 02 Jun 2007) | 1 line Update expected birthday of 2.6 ........ r55751 | neal.norwitz | 2007-06-03 13:32:50 -0700 (Sun, 03 Jun 2007) | 10 lines Backout the original 'fix' to 1721309 which had no effect. Different versions of Berkeley DB handle this differently. The comments and bug report should have the details. Memory is allocated in 4.4 (and presumably earlier), but not in 4.5. Thus 4.5 has the free error, but not earlier versions. Mostly update comments, plus make the free conditional. This fix was already applied to the 2.5 branch. ........ r55752 | brett.cannon | 2007-06-03 16:13:41 -0700 (Sun, 03 Jun 2007) | 6 lines Make _strptime.TimeRE().pattern() use ``\s+`` for matching whitespace instead of ``\s*``. This prevents patterns from "stealing" bits from other patterns in order to make a match work. Closes bug #1730389. Will be backported. ........ r55766 | hyeshik.chang | 2007-06-05 11:16:52 -0700 (Tue, 05 Jun 2007) | 4 lines Fix build on FreeBSD. Bluetooth HCI API in FreeBSD is quite different from Linux's. Just fix the build for now but the code doesn't support the complete capability of HCI on FreeBSD yet. ........ r55770 | hyeshik.chang | 2007-06-05 11:58:51 -0700 (Tue, 05 Jun 2007) | 4 lines Bug #1728403: Fix a bug that CJKCodecs StreamReader hangs when it reads a file that ends with incomplete sequence and sizehint argument for .read() is specified. ........ r55775 | hyeshik.chang | 2007-06-05 12:28:15 -0700 (Tue, 05 Jun 2007) | 2 lines Fix for Windows: close a temporary file before trying to delete it. ........ r55783 | guido.van.rossum | 2007-06-05 14:24:47 -0700 (Tue, 05 Jun 2007) | 2 lines Patch by Tim Delany (missing DECREF). SF #1731330. ........ r55785 | collin.winter | 2007-06-05 17:17:35 -0700 (Tue, 05 Jun 2007) | 3 lines Patch #1731049: make threading.py use a proper "raise" when checking internal state, rather than assert statements (which get stripped out by -O). ........ r55786 | facundo.batista | 2007-06-06 08:13:37 -0700 (Wed, 06 Jun 2007) | 4 lines FTP.ntransfercmd method now uses create_connection when passive, using the timeout received in connection time. ........ r55792 | facundo.batista | 2007-06-06 10:15:23 -0700 (Wed, 06 Jun 2007) | 7 lines Added an optional timeout parameter to function urllib2.urlopen, with tests in test_urllib2net.py (must have network resource enabled to execute them). Also modified test_urllib2.py because testing mock classes must take it into acount. Docs are also updated. ........ r55793 | thomas.heller | 2007-06-06 13:19:19 -0700 (Wed, 06 Jun 2007) | 1 line Build _ctypes and _ctypes_test in the ReleaseAMD64 configuration. ........ r55802 | georg.brandl | 2007-06-07 06:23:24 -0700 (Thu, 07 Jun 2007) | 3 lines Disallow function calls like foo(None=1). Backport from py3k rev. 55708 by Guido. ........ r55804 | georg.brandl | 2007-06-07 06:30:24 -0700 (Thu, 07 Jun 2007) | 2 lines Make reindent.py executable. ........ r55805 | georg.brandl | 2007-06-07 06:34:10 -0700 (Thu, 07 Jun 2007) | 2 lines Patch #1667860: Fix UnboundLocalError in urllib2. ........ r55821 | kristjan.jonsson | 2007-06-07 16:53:49 -0700 (Thu, 07 Jun 2007) | 1 line Fixing changes to getbuildinfo.c that broke linux builds ........ r55828 | thomas.heller | 2007-06-08 09:10:27 -0700 (Fri, 08 Jun 2007) | 1 line Make this test work with older Python releases where struct has no 't' format character. ........ r55829 | martin.v.loewis | 2007-06-08 10:29:20 -0700 (Fri, 08 Jun 2007) | 3 lines Bug #1733488: Fix compilation of bufferobject.c on AIX. Will backport to 2.5. ........ r55831 | thomas.heller | 2007-06-08 11:20:09 -0700 (Fri, 08 Jun 2007) | 2 lines [ 1715718 ] x64 clean compile patch for _ctypes, by Kristj?n Valur with small modifications. ........ r55832 | thomas.heller | 2007-06-08 12:01:06 -0700 (Fri, 08 Jun 2007) | 1 line Fix gcc warnings intruduced by passing Py_ssize_t to PyErr_Format calls. ........ r55833 | thomas.heller | 2007-06-08 12:08:31 -0700 (Fri, 08 Jun 2007) | 2 lines Fix wrong documentation, and correct the punktuation. Closes [1700455]. ........ r55834 | thomas.heller | 2007-06-08 12:14:23 -0700 (Fri, 08 Jun 2007) | 1 line Fix warnings by using proper function prototype. ........ r55839 | neal.norwitz | 2007-06-08 20:36:34 -0700 (Fri, 08 Jun 2007) | 7 lines Prevent expandtabs() on string and unicode objects from causing a segfault when a large width is passed on 32-bit platforms. Found by Google. It would be good for people to review this especially carefully and verify I don't have an off by one error and there is no other way to cause overflow. ........ r55841 | neal.norwitz | 2007-06-08 21:48:22 -0700 (Fri, 08 Jun 2007) | 1 line Use macro version of GET_SIZE to avoid Coverity warning (#150) about a possible error. ........ r55842 | martin.v.loewis | 2007-06-09 00:42:52 -0700 (Sat, 09 Jun 2007) | 3 lines Patch #1733960: Allow T_LONGLONG to accept ints. Will backport to 2.5. ........ r55843 | martin.v.loewis | 2007-06-09 00:58:05 -0700 (Sat, 09 Jun 2007) | 2 lines Fix Windows build. ........ r55845 | martin.v.loewis | 2007-06-09 03:10:26 -0700 (Sat, 09 Jun 2007) | 2 lines Provide LLONG_MAX for S390. ........ r55854 | thomas.heller | 2007-06-10 08:59:17 -0700 (Sun, 10 Jun 2007) | 4 lines First version of build scripts for Windows/AMD64 (no external components are built yet, and 'kill_python' is disabled). ........ r55855 | thomas.heller | 2007-06-10 10:55:51 -0700 (Sun, 10 Jun 2007) | 3 lines For now, disable the _bsddb, _sqlite3, _ssl, _testcapi, _tkinter modules in the ReleaseAMD64 configuration because they do not compile. ........ r55856 | thomas.heller | 2007-06-10 11:27:54 -0700 (Sun, 10 Jun 2007) | 1 line Need to set the environment variables, otherwise devenv.com is not found. ........ r55860 | thomas.heller | 2007-06-10 14:01:17 -0700 (Sun, 10 Jun 2007) | 1 line Revert commit 55855. ........ ................ r55880 | neal.norwitz | 2007-06-10 22:07:36 -0700 (Sun, 10 Jun 2007) | 5 lines Fix the refleak counter on test_collections. The ABC metaclass creates a registry which must be cleared on each run. Otherwise, there *seem* to be refleaks when there really aren't any. (The class is held within the registry even though it's no longer needed.) ................ r55884 | neal.norwitz | 2007-06-10 22:46:33 -0700 (Sun, 10 Jun 2007) | 1 line These tests have been removed, so they are no longer needed here ................ r55886 | georg.brandl | 2007-06-11 00:26:37 -0700 (Mon, 11 Jun 2007) | 3 lines Optimize access to True and False in the compiler (if True) and the peepholer (LOAD_NAME True). ................ r55905 | georg.brandl | 2007-06-11 10:02:26 -0700 (Mon, 11 Jun 2007) | 5 lines Remove __oct__ and __hex__ and use __index__ for converting non-ints before formatting in a base. Add a bin() builtin. ................ r55906 | georg.brandl | 2007-06-11 10:04:44 -0700 (Mon, 11 Jun 2007) | 2 lines int(x, 0) does not "guess". ................ r55907 | georg.brandl | 2007-06-11 10:05:47 -0700 (Mon, 11 Jun 2007) | 2 lines Add a comment to explain that nb_oct and nb_hex are nonfunctional. ................ r55908 | guido.van.rossum | 2007-06-11 10:49:18 -0700 (Mon, 11 Jun 2007) | 2 lines Get rid of unused imports and comment. ................ r55910 | guido.van.rossum | 2007-06-11 13:05:17 -0700 (Mon, 11 Jun 2007) | 2 lines _Abstract.__new__ now requires either no arguments or __init__ overridden. ................ r55911 | guido.van.rossum | 2007-06-11 13:07:49 -0700 (Mon, 11 Jun 2007) | 7 lines Move the collections ABCs to a separate file, _abcoll.py, in order to avoid needing to import _collections.so during the bootstrap (this will become apparent in the next submit of os.py). Add (plain and mutable) ABCs for Set, Mapping, Sequence. ................ r55912 | guido.van.rossum | 2007-06-11 13:09:31 -0700 (Mon, 11 Jun 2007) | 2 lines Rewrite the _Environ class to use the new collections ABCs. ................ r55913 | guido.van.rossum | 2007-06-11 13:59:45 -0700 (Mon, 11 Jun 2007) | 72 lines Merged revisions 55869-55912 via svnmerge from svn+ssh://pythondev@svn.python.org/python/trunk ........ r55869 | neal.norwitz | 2007-06-10 17:42:11 -0700 (Sun, 10 Jun 2007) | 1 line Add Atul Varma for patch # 1667860 ........ r55870 | neal.norwitz | 2007-06-10 18:22:03 -0700 (Sun, 10 Jun 2007) | 1 line Ignore valgrind problems on Ubuntu from ld ........ r55872 | neal.norwitz | 2007-06-10 18:48:46 -0700 (Sun, 10 Jun 2007) | 2 lines Ignore config.status.lineno which seems new (new autoconf?) ........ r55873 | neal.norwitz | 2007-06-10 19:14:39 -0700 (Sun, 10 Jun 2007) | 1 line Prevent these tests from running on Win64 since they don\'t apply there either ........ r55874 | neal.norwitz | 2007-06-10 19:16:10 -0700 (Sun, 10 Jun 2007) | 5 lines Fix a bug when there was a newline in the string expandtabs was called on. This also catches another condition that can overflow. Will backport. ........ r55879 | neal.norwitz | 2007-06-10 21:52:37 -0700 (Sun, 10 Jun 2007) | 1 line Prevent hang if the port cannot be opened. ........ r55881 | neal.norwitz | 2007-06-10 22:28:45 -0700 (Sun, 10 Jun 2007) | 4 lines Add all of the distuils modules that don't seem to have explicit tests. :-( Move an import in mworkscompiler so that this module can be imported on any platform. Hopefully this works on all platforms. ........ r55882 | neal.norwitz | 2007-06-10 22:35:10 -0700 (Sun, 10 Jun 2007) | 4 lines SF #1734732, lower case the module names per PEP 8. Will backport. ........ r55885 | neal.norwitz | 2007-06-10 23:16:48 -0700 (Sun, 10 Jun 2007) | 4 lines Not sure why this only fails sometimes on Unix machines. Better to disable it and only import msvccompiler on Windows since that's the only place it can work anyways. ........ r55887 | neal.norwitz | 2007-06-11 00:29:43 -0700 (Mon, 11 Jun 2007) | 4 lines Bug #1734723: Fix repr.Repr() so it doesn't ignore the maxtuple attribute. Will backport ........ r55889 | neal.norwitz | 2007-06-11 00:36:24 -0700 (Mon, 11 Jun 2007) | 1 line Reflow long line ........ r55896 | thomas.heller | 2007-06-11 08:58:33 -0700 (Mon, 11 Jun 2007) | 3 lines Use "O&" in calls to PyArg_Parse when we need a 'void*' instead of "k" or "K" codes. ........ r55901 | facundo.batista | 2007-06-11 09:27:08 -0700 (Mon, 11 Jun 2007) | 5 lines Added versionchanged flag to all the methods which received a new optional timeout parameter, and a versionadded flag to the socket.create_connection function. ........ ................ r55914 | guido.van.rossum | 2007-06-11 14:19:50 -0700 (Mon, 11 Jun 2007) | 3 lines New super() implementation, for PEP 3135 (though the PEP is not yet updated to this design, and small tweaks may still be made later). ................ r55923 | guido.van.rossum | 2007-06-11 21:15:24 -0700 (Mon, 11 Jun 2007) | 4 lines I'm guessing this module broke when Neal ripped out the types module -- it used 'list' both as a local variable and as the built-in list type. Renamed the local variable since that was easier. ................ r55924 | guido.van.rossum | 2007-06-11 21:20:05 -0700 (Mon, 11 Jun 2007) | 5 lines Change all occurrences of super(<thisclass>, <firstarg>) to super(). Seems to have worked, all the tests still pass. Exception: test_descr and test_descrtut, which have tons of these and are there to test the various usages. ................ r55939 | collin.winter | 2007-06-12 13:57:33 -0700 (Tue, 12 Jun 2007) | 1 line Patch #1735485: remove StandardError from the exception hierarchy. ................ r55954 | neal.norwitz | 2007-06-12 21:56:32 -0700 (Tue, 12 Jun 2007) | 51 lines Merged revisions 55913-55950 via svnmerge from svn+ssh://pythondev@svn.python.org/python/trunk ........ r55926 | marc-andre.lemburg | 2007-06-12 02:09:58 -0700 (Tue, 12 Jun 2007) | 3 lines Apply patch #1734945 to support TurboLinux as distribution. ........ r55927 | marc-andre.lemburg | 2007-06-12 02:26:49 -0700 (Tue, 12 Jun 2007) | 3 lines Add patch #1726668: Windows Vista support. ........ r55929 | thomas.heller | 2007-06-12 08:36:22 -0700 (Tue, 12 Jun 2007) | 1 line Checkout, but do not yet try to build, exernal sources. ........ r55930 | thomas.heller | 2007-06-12 09:08:27 -0700 (Tue, 12 Jun 2007) | 6 lines Add bufferoverflowU.lib to the libraries needed by _ssl (is this the right thing to do?). Set the /XP64 /RETAIL build enviroment in the makefile when building ReleaseAMD64. ........ r55931 | thomas.heller | 2007-06-12 09:23:19 -0700 (Tue, 12 Jun 2007) | 5 lines Revert this change, since it breaks the win32 build: Add bufferoverflowU.lib to the libraries needed by _ssl (is this the right thing to do?). ........ r55934 | thomas.heller | 2007-06-12 10:28:31 -0700 (Tue, 12 Jun 2007) | 3 lines Specify the bufferoverflowU.lib to the makefile on the command line (for ReleaseAMD64 builds). ........ r55937 | thomas.heller | 2007-06-12 12:02:59 -0700 (Tue, 12 Jun 2007) | 3 lines Add bufferoverflowU.lib to PCBuild\_bsddb.vcproj. Build sqlite3.dll and bsddb. ........ r55938 | thomas.heller | 2007-06-12 12:56:12 -0700 (Tue, 12 Jun 2007) | 2 lines Don't rebuild Berkeley DB if not needed (this was committed by accident). ........ r55948 | martin.v.loewis | 2007-06-12 20:42:19 -0700 (Tue, 12 Jun 2007) | 3 lines Provide PY_LLONG_MAX on all systems having long long. Will backport to 2.5. ........ ................ r55959 | guido.van.rossum | 2007-06-13 09:22:41 -0700 (Wed, 13 Jun 2007) | 2 lines Fix a compilation warning. ................
Diffstat (limited to 'Lib/_abcoll.py')
-rw-r--r--Lib/_abcoll.py535
1 files changed, 535 insertions, 0 deletions
diff --git a/Lib/_abcoll.py b/Lib/_abcoll.py
new file mode 100644
index 0000000..cd1c9ce
--- /dev/null
+++ b/Lib/_abcoll.py
@@ -0,0 +1,535 @@
+# 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 ceratin
+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(bytes)
+
+
+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: Iterable):
+ for value in it:
+ self.add(value)
+ return self
+
+ def __iand__(self, c: Container):
+ for value in self:
+ if value not in c:
+ self.discard(value)
+ return self
+
+ def __ixor__(self, it: Iterable):
+ # 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: Iterable):
+ 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)
+MutableSequence.register(bytes)