10a8c90248264a8b26970b4473770bcc3df8515fJosh Gao# Copyright 2007 Google, Inc. All Rights Reserved. 20a8c90248264a8b26970b4473770bcc3df8515fJosh Gao# Licensed to PSF under a Contributor Agreement. 30a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 40a8c90248264a8b26970b4473770bcc3df8515fJosh Gao"""Abstract Base Classes (ABCs) for collections, according to PEP 3119. 50a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 60a8c90248264a8b26970b4473770bcc3df8515fJosh GaoDON'T USE THIS MODULE DIRECTLY! The classes here should be imported 70a8c90248264a8b26970b4473770bcc3df8515fJosh Gaovia collections; they are defined here only to alleviate certain 80a8c90248264a8b26970b4473770bcc3df8515fJosh Gaobootstrapping issues. Unit tests are in test_collections. 90a8c90248264a8b26970b4473770bcc3df8515fJosh Gao""" 100a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 110a8c90248264a8b26970b4473770bcc3df8515fJosh Gaofrom abc import ABCMeta, abstractmethod 120a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoimport sys 130a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 140a8c90248264a8b26970b4473770bcc3df8515fJosh Gao__all__ = ["Hashable", "Iterable", "Iterator", 150a8c90248264a8b26970b4473770bcc3df8515fJosh Gao "Sized", "Container", "Callable", 160a8c90248264a8b26970b4473770bcc3df8515fJosh Gao "Set", "MutableSet", 170a8c90248264a8b26970b4473770bcc3df8515fJosh Gao "Mapping", "MutableMapping", 180a8c90248264a8b26970b4473770bcc3df8515fJosh Gao "MappingView", "KeysView", "ItemsView", "ValuesView", 190a8c90248264a8b26970b4473770bcc3df8515fJosh Gao "Sequence", "MutableSequence", 200a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ] 210a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 220a8c90248264a8b26970b4473770bcc3df8515fJosh Gao### ONE-TRICK PONIES ### 230a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 240a8c90248264a8b26970b4473770bcc3df8515fJosh Gaodef _hasattr(C, attr): 250a8c90248264a8b26970b4473770bcc3df8515fJosh Gao try: 260a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return any(attr in B.__dict__ for B in C.__mro__) 270a8c90248264a8b26970b4473770bcc3df8515fJosh Gao except AttributeError: 280a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Old-style class 290a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return hasattr(C, attr) 300a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 310a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 320a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoclass Hashable: 330a8c90248264a8b26970b4473770bcc3df8515fJosh Gao __metaclass__ = ABCMeta 340a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 350a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @abstractmethod 360a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __hash__(self): 370a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return 0 380a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 390a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @classmethod 400a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __subclasshook__(cls, C): 410a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if cls is Hashable: 420a8c90248264a8b26970b4473770bcc3df8515fJosh Gao try: 430a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for B in C.__mro__: 440a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if "__hash__" in B.__dict__: 450a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if B.__dict__["__hash__"]: 460a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return True 470a8c90248264a8b26970b4473770bcc3df8515fJosh Gao break 480a8c90248264a8b26970b4473770bcc3df8515fJosh Gao except AttributeError: 490a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Old-style class 500a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if getattr(C, "__hash__", None): 510a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return True 520a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return NotImplemented 530a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 540a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 550a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoclass Iterable: 560a8c90248264a8b26970b4473770bcc3df8515fJosh Gao __metaclass__ = ABCMeta 570a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 580a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @abstractmethod 590a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __iter__(self): 600a8c90248264a8b26970b4473770bcc3df8515fJosh Gao while False: 610a8c90248264a8b26970b4473770bcc3df8515fJosh Gao yield None 620a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 630a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @classmethod 640a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __subclasshook__(cls, C): 650a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if cls is Iterable: 660a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if _hasattr(C, "__iter__"): 670a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return True 680a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return NotImplemented 690a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 700a8c90248264a8b26970b4473770bcc3df8515fJosh GaoIterable.register(str) 710a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 720a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 730a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoclass Iterator(Iterable): 740a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 750a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @abstractmethod 760a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def next(self): 770a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'Return the next item from the iterator. When exhausted, raise StopIteration' 780a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise StopIteration 790a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 800a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __iter__(self): 810a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return self 820a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 830a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @classmethod 840a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __subclasshook__(cls, C): 850a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if cls is Iterator: 860a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if _hasattr(C, "next") and _hasattr(C, "__iter__"): 870a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return True 880a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return NotImplemented 890a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 900a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 910a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoclass Sized: 920a8c90248264a8b26970b4473770bcc3df8515fJosh Gao __metaclass__ = ABCMeta 930a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 940a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @abstractmethod 950a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __len__(self): 960a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return 0 970a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 980a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @classmethod 990a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __subclasshook__(cls, C): 1000a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if cls is Sized: 1010a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if _hasattr(C, "__len__"): 1020a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return True 1030a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return NotImplemented 1040a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1050a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1060a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoclass Container: 1070a8c90248264a8b26970b4473770bcc3df8515fJosh Gao __metaclass__ = ABCMeta 1080a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1090a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @abstractmethod 1100a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __contains__(self, x): 1110a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return False 1120a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1130a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @classmethod 1140a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __subclasshook__(cls, C): 1150a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if cls is Container: 1160a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if _hasattr(C, "__contains__"): 1170a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return True 1180a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return NotImplemented 1190a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1200a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1210a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoclass Callable: 1220a8c90248264a8b26970b4473770bcc3df8515fJosh Gao __metaclass__ = ABCMeta 1230a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1240a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @abstractmethod 1250a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __call__(self, *args, **kwds): 1260a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return False 1270a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1280a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @classmethod 1290a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __subclasshook__(cls, C): 1300a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if cls is Callable: 1310a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if _hasattr(C, "__call__"): 1320a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return True 1330a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return NotImplemented 1340a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1350a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1360a8c90248264a8b26970b4473770bcc3df8515fJosh Gao### SETS ### 1370a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1380a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1390a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoclass Set(Sized, Iterable, Container): 1400a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """A set is a finite, iterable container. 1410a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1420a8c90248264a8b26970b4473770bcc3df8515fJosh Gao This class provides concrete generic implementations of all 1430a8c90248264a8b26970b4473770bcc3df8515fJosh Gao methods except for __contains__, __iter__ and __len__. 1440a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1450a8c90248264a8b26970b4473770bcc3df8515fJosh Gao To override the comparisons (presumably for speed, as the 1460a8c90248264a8b26970b4473770bcc3df8515fJosh Gao semantics are fixed), all you have to do is redefine __le__ and 1470a8c90248264a8b26970b4473770bcc3df8515fJosh Gao then the other operations will automatically follow suit. 1480a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """ 1490a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1500a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __le__(self, other): 1510a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if not isinstance(other, Set): 1520a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return NotImplemented 1530a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if len(self) > len(other): 1540a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return False 1550a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for elem in self: 1560a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if elem not in other: 1570a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return False 1580a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return True 1590a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1600a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __lt__(self, other): 1610a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if not isinstance(other, Set): 1620a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return NotImplemented 1630a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return len(self) < len(other) and self.__le__(other) 1640a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1650a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __gt__(self, other): 1660a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if not isinstance(other, Set): 1670a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return NotImplemented 1680a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return other < self 1690a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1700a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __ge__(self, other): 1710a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if not isinstance(other, Set): 1720a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return NotImplemented 1730a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return other <= self 1740a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1750a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __eq__(self, other): 1760a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if not isinstance(other, Set): 1770a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return NotImplemented 1780a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return len(self) == len(other) and self.__le__(other) 1790a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1800a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __ne__(self, other): 1810a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return not (self == other) 1820a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1830a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @classmethod 1840a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def _from_iterable(cls, it): 1850a8c90248264a8b26970b4473770bcc3df8515fJosh Gao '''Construct an instance of the class from any iterable input. 1860a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1870a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Must override this method if the class constructor signature 1880a8c90248264a8b26970b4473770bcc3df8515fJosh Gao does not accept an iterable for an input. 1890a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ''' 1900a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return cls(it) 1910a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1920a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __and__(self, other): 1930a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if not isinstance(other, Iterable): 1940a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return NotImplemented 1950a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return self._from_iterable(value for value in other if value in self) 1960a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1970a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def isdisjoint(self, other): 1980a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'Return True if two sets have a null intersection.' 1990a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for value in other: 2000a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if value in self: 2010a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return False 2020a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return True 2030a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2040a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __or__(self, other): 2050a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if not isinstance(other, Iterable): 2060a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return NotImplemented 2070a8c90248264a8b26970b4473770bcc3df8515fJosh Gao chain = (e for s in (self, other) for e in s) 2080a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return self._from_iterable(chain) 2090a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2100a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __sub__(self, other): 2110a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if not isinstance(other, Set): 2120a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if not isinstance(other, Iterable): 2130a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return NotImplemented 2140a8c90248264a8b26970b4473770bcc3df8515fJosh Gao other = self._from_iterable(other) 2150a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return self._from_iterable(value for value in self 2160a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if value not in other) 2170a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2180a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __xor__(self, other): 2190a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if not isinstance(other, Set): 2200a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if not isinstance(other, Iterable): 2210a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return NotImplemented 2220a8c90248264a8b26970b4473770bcc3df8515fJosh Gao other = self._from_iterable(other) 2230a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return (self - other) | (other - self) 2240a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2250a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Sets are not hashable by default, but subclasses can change this 2260a8c90248264a8b26970b4473770bcc3df8515fJosh Gao __hash__ = None 2270a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2280a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def _hash(self): 2290a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """Compute the hash value of a set. 2300a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2310a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Note that we don't define __hash__: not all sets are hashable. 2320a8c90248264a8b26970b4473770bcc3df8515fJosh Gao But if you define a hashable set type, its __hash__ should 2330a8c90248264a8b26970b4473770bcc3df8515fJosh Gao call this function. 2340a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2350a8c90248264a8b26970b4473770bcc3df8515fJosh Gao This must be compatible __eq__. 2360a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2370a8c90248264a8b26970b4473770bcc3df8515fJosh Gao All sets ought to compare equal if they contain the same 2380a8c90248264a8b26970b4473770bcc3df8515fJosh Gao elements, regardless of how they are implemented, and 2390a8c90248264a8b26970b4473770bcc3df8515fJosh Gao regardless of the order of the elements; so there's not much 2400a8c90248264a8b26970b4473770bcc3df8515fJosh Gao freedom for __eq__ or __hash__. We match the algorithm used 2410a8c90248264a8b26970b4473770bcc3df8515fJosh Gao by the built-in frozenset type. 2420a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """ 2430a8c90248264a8b26970b4473770bcc3df8515fJosh Gao MAX = sys.maxint 2440a8c90248264a8b26970b4473770bcc3df8515fJosh Gao MASK = 2 * MAX + 1 2450a8c90248264a8b26970b4473770bcc3df8515fJosh Gao n = len(self) 2460a8c90248264a8b26970b4473770bcc3df8515fJosh Gao h = 1927868237 * (n + 1) 2470a8c90248264a8b26970b4473770bcc3df8515fJosh Gao h &= MASK 2480a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for x in self: 2490a8c90248264a8b26970b4473770bcc3df8515fJosh Gao hx = hash(x) 2500a8c90248264a8b26970b4473770bcc3df8515fJosh Gao h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167 2510a8c90248264a8b26970b4473770bcc3df8515fJosh Gao h &= MASK 2520a8c90248264a8b26970b4473770bcc3df8515fJosh Gao h = h * 69069 + 907133923 2530a8c90248264a8b26970b4473770bcc3df8515fJosh Gao h &= MASK 2540a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if h > MAX: 2550a8c90248264a8b26970b4473770bcc3df8515fJosh Gao h -= MASK + 1 2560a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if h == -1: 2570a8c90248264a8b26970b4473770bcc3df8515fJosh Gao h = 590923713 2580a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return h 2590a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2600a8c90248264a8b26970b4473770bcc3df8515fJosh GaoSet.register(frozenset) 2610a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2620a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2630a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoclass MutableSet(Set): 2640a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """A mutable set is a finite, iterable container. 2650a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2660a8c90248264a8b26970b4473770bcc3df8515fJosh Gao This class provides concrete generic implementations of all 2670a8c90248264a8b26970b4473770bcc3df8515fJosh Gao methods except for __contains__, __iter__, __len__, 2680a8c90248264a8b26970b4473770bcc3df8515fJosh Gao add(), and discard(). 2690a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2700a8c90248264a8b26970b4473770bcc3df8515fJosh Gao To override the comparisons (presumably for speed, as the 2710a8c90248264a8b26970b4473770bcc3df8515fJosh Gao semantics are fixed), all you have to do is redefine __le__ and 2720a8c90248264a8b26970b4473770bcc3df8515fJosh Gao then the other operations will automatically follow suit. 2730a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """ 2740a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2750a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @abstractmethod 2760a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def add(self, value): 2770a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """Add an element.""" 2780a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise NotImplementedError 2790a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2800a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @abstractmethod 2810a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def discard(self, value): 2820a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """Remove an element. Do not raise an exception if absent.""" 2830a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise NotImplementedError 2840a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2850a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def remove(self, value): 2860a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """Remove an element. If not a member, raise a KeyError.""" 2870a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if value not in self: 2880a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise KeyError(value) 2890a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self.discard(value) 2900a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2910a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def pop(self): 2920a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """Return the popped value. Raise KeyError if empty.""" 2930a8c90248264a8b26970b4473770bcc3df8515fJosh Gao it = iter(self) 2940a8c90248264a8b26970b4473770bcc3df8515fJosh Gao try: 2950a8c90248264a8b26970b4473770bcc3df8515fJosh Gao value = next(it) 2960a8c90248264a8b26970b4473770bcc3df8515fJosh Gao except StopIteration: 2970a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise KeyError 2980a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self.discard(value) 2990a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return value 3000a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3010a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def clear(self): 3020a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """This is slow (creates N new iterators!) but effective.""" 3030a8c90248264a8b26970b4473770bcc3df8515fJosh Gao try: 3040a8c90248264a8b26970b4473770bcc3df8515fJosh Gao while True: 3050a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self.pop() 3060a8c90248264a8b26970b4473770bcc3df8515fJosh Gao except KeyError: 3070a8c90248264a8b26970b4473770bcc3df8515fJosh Gao pass 3080a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3090a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __ior__(self, it): 3100a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for value in it: 3110a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self.add(value) 3120a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return self 3130a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3140a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __iand__(self, it): 3150a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for value in (self - it): 3160a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self.discard(value) 3170a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return self 3180a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3190a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __ixor__(self, it): 3200a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if it is self: 3210a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self.clear() 3220a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 3230a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if not isinstance(it, Set): 3240a8c90248264a8b26970b4473770bcc3df8515fJosh Gao it = self._from_iterable(it) 3250a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for value in it: 3260a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if value in self: 3270a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self.discard(value) 3280a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 3290a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self.add(value) 3300a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return self 3310a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3320a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __isub__(self, it): 3330a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if it is self: 3340a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self.clear() 3350a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 3360a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for value in it: 3370a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self.discard(value) 3380a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return self 3390a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3400a8c90248264a8b26970b4473770bcc3df8515fJosh GaoMutableSet.register(set) 3410a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3420a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3430a8c90248264a8b26970b4473770bcc3df8515fJosh Gao### MAPPINGS ### 3440a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3450a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3460a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoclass Mapping(Sized, Iterable, Container): 3470a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3480a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """A Mapping is a generic container for associating key/value 3490a8c90248264a8b26970b4473770bcc3df8515fJosh Gao pairs. 3500a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3510a8c90248264a8b26970b4473770bcc3df8515fJosh Gao This class provides concrete generic implementations of all 3520a8c90248264a8b26970b4473770bcc3df8515fJosh Gao methods except for __getitem__, __iter__, and __len__. 3530a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3540a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """ 3550a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3560a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @abstractmethod 3570a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __getitem__(self, key): 3580a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise KeyError 3590a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3600a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def get(self, key, default=None): 3610a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.' 3620a8c90248264a8b26970b4473770bcc3df8515fJosh Gao try: 3630a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return self[key] 3640a8c90248264a8b26970b4473770bcc3df8515fJosh Gao except KeyError: 3650a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return default 3660a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3670a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __contains__(self, key): 3680a8c90248264a8b26970b4473770bcc3df8515fJosh Gao try: 3690a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self[key] 3700a8c90248264a8b26970b4473770bcc3df8515fJosh Gao except KeyError: 3710a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return False 3720a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 3730a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return True 3740a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3750a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def iterkeys(self): 3760a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'D.iterkeys() -> an iterator over the keys of D' 3770a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return iter(self) 3780a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3790a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def itervalues(self): 3800a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'D.itervalues() -> an iterator over the values of D' 3810a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for key in self: 3820a8c90248264a8b26970b4473770bcc3df8515fJosh Gao yield self[key] 3830a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3840a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def iteritems(self): 3850a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'D.iteritems() -> an iterator over the (key, value) items of D' 3860a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for key in self: 3870a8c90248264a8b26970b4473770bcc3df8515fJosh Gao yield (key, self[key]) 3880a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3890a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def keys(self): 3900a8c90248264a8b26970b4473770bcc3df8515fJosh Gao "D.keys() -> list of D's keys" 3910a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return list(self) 3920a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3930a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def items(self): 3940a8c90248264a8b26970b4473770bcc3df8515fJosh Gao "D.items() -> list of D's (key, value) pairs, as 2-tuples" 3950a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return [(key, self[key]) for key in self] 3960a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3970a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def values(self): 3980a8c90248264a8b26970b4473770bcc3df8515fJosh Gao "D.values() -> list of D's values" 3990a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return [self[key] for key in self] 4000a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4010a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Mappings are not hashable by default, but subclasses can change this 4020a8c90248264a8b26970b4473770bcc3df8515fJosh Gao __hash__ = None 4030a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4040a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __eq__(self, other): 4050a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if not isinstance(other, Mapping): 4060a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return NotImplemented 4070a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return dict(self.items()) == dict(other.items()) 4080a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4090a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __ne__(self, other): 4100a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return not (self == other) 4110a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4120a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoclass MappingView(Sized): 4130a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4140a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __init__(self, mapping): 4150a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self._mapping = mapping 4160a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4170a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __len__(self): 4180a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return len(self._mapping) 4190a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4200a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __repr__(self): 4210a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return '{0.__class__.__name__}({0._mapping!r})'.format(self) 4220a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4230a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4240a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoclass KeysView(MappingView, Set): 4250a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4260a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @classmethod 4270a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def _from_iterable(self, it): 4280a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return set(it) 4290a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4300a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __contains__(self, key): 4310a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return key in self._mapping 4320a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4330a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __iter__(self): 4340a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for key in self._mapping: 4350a8c90248264a8b26970b4473770bcc3df8515fJosh Gao yield key 4360a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4370a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4380a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoclass ItemsView(MappingView, Set): 4390a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4400a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @classmethod 4410a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def _from_iterable(self, it): 4420a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return set(it) 4430a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4440a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __contains__(self, item): 4450a8c90248264a8b26970b4473770bcc3df8515fJosh Gao key, value = item 4460a8c90248264a8b26970b4473770bcc3df8515fJosh Gao try: 4470a8c90248264a8b26970b4473770bcc3df8515fJosh Gao v = self._mapping[key] 4480a8c90248264a8b26970b4473770bcc3df8515fJosh Gao except KeyError: 4490a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return False 4500a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 4510a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return v == value 4520a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4530a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __iter__(self): 4540a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for key in self._mapping: 4550a8c90248264a8b26970b4473770bcc3df8515fJosh Gao yield (key, self._mapping[key]) 4560a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4570a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4580a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoclass ValuesView(MappingView): 4590a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4600a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __contains__(self, value): 4610a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for key in self._mapping: 4620a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if value == self._mapping[key]: 4630a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return True 4640a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return False 4650a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4660a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __iter__(self): 4670a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for key in self._mapping: 4680a8c90248264a8b26970b4473770bcc3df8515fJosh Gao yield self._mapping[key] 4690a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4700a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4710a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoclass MutableMapping(Mapping): 4720a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4730a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """A MutableMapping is a generic container for associating 4740a8c90248264a8b26970b4473770bcc3df8515fJosh Gao key/value pairs. 4750a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4760a8c90248264a8b26970b4473770bcc3df8515fJosh Gao This class provides concrete generic implementations of all 4770a8c90248264a8b26970b4473770bcc3df8515fJosh Gao methods except for __getitem__, __setitem__, __delitem__, 4780a8c90248264a8b26970b4473770bcc3df8515fJosh Gao __iter__, and __len__. 4790a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4800a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """ 4810a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4820a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @abstractmethod 4830a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __setitem__(self, key, value): 4840a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise KeyError 4850a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4860a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @abstractmethod 4870a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __delitem__(self, key): 4880a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise KeyError 4890a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4900a8c90248264a8b26970b4473770bcc3df8515fJosh Gao __marker = object() 4910a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4920a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def pop(self, key, default=__marker): 4930a8c90248264a8b26970b4473770bcc3df8515fJosh Gao '''D.pop(k[,d]) -> v, remove specified key and return the corresponding value. 4940a8c90248264a8b26970b4473770bcc3df8515fJosh Gao If key is not found, d is returned if given, otherwise KeyError is raised. 4950a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ''' 4960a8c90248264a8b26970b4473770bcc3df8515fJosh Gao try: 4970a8c90248264a8b26970b4473770bcc3df8515fJosh Gao value = self[key] 4980a8c90248264a8b26970b4473770bcc3df8515fJosh Gao except KeyError: 4990a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if default is self.__marker: 5000a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise 5010a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return default 5020a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 5030a8c90248264a8b26970b4473770bcc3df8515fJosh Gao del self[key] 5040a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return value 5050a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5060a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def popitem(self): 5070a8c90248264a8b26970b4473770bcc3df8515fJosh Gao '''D.popitem() -> (k, v), remove and return some (key, value) pair 5080a8c90248264a8b26970b4473770bcc3df8515fJosh Gao as a 2-tuple; but raise KeyError if D is empty. 5090a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ''' 5100a8c90248264a8b26970b4473770bcc3df8515fJosh Gao try: 5110a8c90248264a8b26970b4473770bcc3df8515fJosh Gao key = next(iter(self)) 5120a8c90248264a8b26970b4473770bcc3df8515fJosh Gao except StopIteration: 5130a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise KeyError 5140a8c90248264a8b26970b4473770bcc3df8515fJosh Gao value = self[key] 5150a8c90248264a8b26970b4473770bcc3df8515fJosh Gao del self[key] 5160a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return key, value 5170a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5180a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def clear(self): 5190a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'D.clear() -> None. Remove all items from D.' 5200a8c90248264a8b26970b4473770bcc3df8515fJosh Gao try: 5210a8c90248264a8b26970b4473770bcc3df8515fJosh Gao while True: 5220a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self.popitem() 5230a8c90248264a8b26970b4473770bcc3df8515fJosh Gao except KeyError: 5240a8c90248264a8b26970b4473770bcc3df8515fJosh Gao pass 5250a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5260a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def update(*args, **kwds): 5270a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ''' D.update([E, ]**F) -> None. Update D from mapping/iterable E and F. 5280a8c90248264a8b26970b4473770bcc3df8515fJosh Gao If E present and has a .keys() method, does: for k in E: D[k] = E[k] 5290a8c90248264a8b26970b4473770bcc3df8515fJosh Gao If E present and lacks .keys() method, does: for (k, v) in E: D[k] = v 5300a8c90248264a8b26970b4473770bcc3df8515fJosh Gao In either case, this is followed by: for k, v in F.items(): D[k] = v 5310a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ''' 5320a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if len(args) > 2: 5330a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise TypeError("update() takes at most 2 positional " 5340a8c90248264a8b26970b4473770bcc3df8515fJosh Gao "arguments ({} given)".format(len(args))) 5350a8c90248264a8b26970b4473770bcc3df8515fJosh Gao elif not args: 5360a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise TypeError("update() takes at least 1 argument (0 given)") 5370a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self = args[0] 5380a8c90248264a8b26970b4473770bcc3df8515fJosh Gao other = args[1] if len(args) >= 2 else () 5390a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5400a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if isinstance(other, Mapping): 5410a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for key in other: 5420a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self[key] = other[key] 5430a8c90248264a8b26970b4473770bcc3df8515fJosh Gao elif hasattr(other, "keys"): 5440a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for key in other.keys(): 5450a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self[key] = other[key] 5460a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 5470a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for key, value in other: 5480a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self[key] = value 5490a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for key, value in kwds.items(): 5500a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self[key] = value 5510a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5520a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def setdefault(self, key, default=None): 5530a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D' 5540a8c90248264a8b26970b4473770bcc3df8515fJosh Gao try: 5550a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return self[key] 5560a8c90248264a8b26970b4473770bcc3df8515fJosh Gao except KeyError: 5570a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self[key] = default 5580a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return default 5590a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5600a8c90248264a8b26970b4473770bcc3df8515fJosh GaoMutableMapping.register(dict) 5610a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5620a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5630a8c90248264a8b26970b4473770bcc3df8515fJosh Gao### SEQUENCES ### 5640a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5650a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5660a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoclass Sequence(Sized, Iterable, Container): 5670a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """All the operations on a read-only sequence. 5680a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5690a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Concrete subclasses must override __new__ or __init__, 5700a8c90248264a8b26970b4473770bcc3df8515fJosh Gao __getitem__, and __len__. 5710a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """ 5720a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5730a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @abstractmethod 5740a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __getitem__(self, index): 5750a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise IndexError 5760a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5770a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __iter__(self): 5780a8c90248264a8b26970b4473770bcc3df8515fJosh Gao i = 0 5790a8c90248264a8b26970b4473770bcc3df8515fJosh Gao try: 5800a8c90248264a8b26970b4473770bcc3df8515fJosh Gao while True: 5810a8c90248264a8b26970b4473770bcc3df8515fJosh Gao v = self[i] 5820a8c90248264a8b26970b4473770bcc3df8515fJosh Gao yield v 5830a8c90248264a8b26970b4473770bcc3df8515fJosh Gao i += 1 5840a8c90248264a8b26970b4473770bcc3df8515fJosh Gao except IndexError: 5850a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return 5860a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5870a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __contains__(self, value): 5880a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for v in self: 5890a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if v == value: 5900a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return True 5910a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return False 5920a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5930a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __reversed__(self): 5940a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for i in reversed(range(len(self))): 5950a8c90248264a8b26970b4473770bcc3df8515fJosh Gao yield self[i] 5960a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5970a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def index(self, value): 5980a8c90248264a8b26970b4473770bcc3df8515fJosh Gao '''S.index(value) -> integer -- return first index of value. 5990a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Raises ValueError if the value is not present. 6000a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ''' 6010a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for i, v in enumerate(self): 6020a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if v == value: 6030a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return i 6040a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise ValueError 6050a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6060a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def count(self, value): 6070a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'S.count(value) -> integer -- return number of occurrences of value' 6080a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return sum(1 for v in self if v == value) 6090a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6100a8c90248264a8b26970b4473770bcc3df8515fJosh GaoSequence.register(tuple) 6110a8c90248264a8b26970b4473770bcc3df8515fJosh GaoSequence.register(basestring) 6120a8c90248264a8b26970b4473770bcc3df8515fJosh GaoSequence.register(buffer) 6130a8c90248264a8b26970b4473770bcc3df8515fJosh GaoSequence.register(xrange) 6140a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6150a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6160a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoclass MutableSequence(Sequence): 6170a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6180a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """All the operations on a read-only sequence. 6190a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6200a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Concrete subclasses must provide __new__ or __init__, 6210a8c90248264a8b26970b4473770bcc3df8515fJosh Gao __getitem__, __setitem__, __delitem__, __len__, and insert(). 6220a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6230a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """ 6240a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6250a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @abstractmethod 6260a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __setitem__(self, index, value): 6270a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise IndexError 6280a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6290a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @abstractmethod 6300a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __delitem__(self, index): 6310a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise IndexError 6320a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6330a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @abstractmethod 6340a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def insert(self, index, value): 6350a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'S.insert(index, object) -- insert object before index' 6360a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise IndexError 6370a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6380a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def append(self, value): 6390a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'S.append(object) -- append object to the end of the sequence' 6400a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self.insert(len(self), value) 6410a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6420a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def reverse(self): 6430a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'S.reverse() -- reverse *IN PLACE*' 6440a8c90248264a8b26970b4473770bcc3df8515fJosh Gao n = len(self) 6450a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for i in range(n//2): 6460a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self[i], self[n-i-1] = self[n-i-1], self[i] 6470a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6480a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def extend(self, values): 6490a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'S.extend(iterable) -- extend sequence by appending elements from the iterable' 6500a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for v in values: 6510a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self.append(v) 6520a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6530a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def pop(self, index=-1): 6540a8c90248264a8b26970b4473770bcc3df8515fJosh Gao '''S.pop([index]) -> item -- remove and return item at index (default last). 6550a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Raise IndexError if list is empty or index is out of range. 6560a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ''' 6570a8c90248264a8b26970b4473770bcc3df8515fJosh Gao v = self[index] 6580a8c90248264a8b26970b4473770bcc3df8515fJosh Gao del self[index] 6590a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return v 6600a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6610a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def remove(self, value): 6620a8c90248264a8b26970b4473770bcc3df8515fJosh Gao '''S.remove(value) -- remove first occurrence of value. 6630a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Raise ValueError if the value is not present. 6640a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ''' 6650a8c90248264a8b26970b4473770bcc3df8515fJosh Gao del self[self.index(value)] 6660a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6670a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __iadd__(self, values): 6680a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self.extend(values) 6690a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return self 6700a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6710a8c90248264a8b26970b4473770bcc3df8515fJosh GaoMutableSequence.register(list) 672