2007 google inc licensed to psf under a contributor agreement abstract base classes abcs for collections according to pep 3119 unit tests are in testcollections maintenance notes abcs are different from other standard library modules in that they specify compliance tests in general once an abc has been published new methods either abstract or concrete cannot be added though classes that inherit from an abc would automatically receive a new mixin method registered classes would become noncompliant and violate the contract promised by isinstancesomeobj someabc though irritating the correct procedure for adding new abstract or mixin methods is to create a new abc as a subclass of the previous abc for example union intersection and difference cannot be added to set but could go into a new abc that extends set because they are so hard to change new abcs should have their apis carefully thought through prior to publication since abcmeta only checks for the presence of methods it is possible to alter the signature of a method by adding optional arguments or changing parameters names this is still a bit dubious but at least it won t cause isinstance to return an incorrect result this module has been renamed from collections abc to collectionsabc to speed up interpreter startup some of the types such as mutablemapping are required early but collections module imports a lot of other modules see issue 19218 private list of types that we want to register with the various abcs so that they will pass tests like it itersomebytearray assert isinstanceit iterable note in other implementations these types might not be distinct and they may have their own implementation specific types that are not included on this list callableiterator views misc coroutine asynchronous generator onetrick ponies send a value into the coroutine return next yielded value or raise stopiteration raise an exception in the coroutine return next yielded value or raise stopiteration raise generatorexit inside coroutine return the next item or raise stopasynciteration when exhausted raise stopasynciteration def aiterself return self classmethod def subclasshookcls c if cls is asynciterator return checkmethodsc anext aiter return notimplemented class asyncgeneratorasynciterator slots async def anextself return await self asendnone abstractmethod async def asendself value raise stopasynciteration abstractmethod async def athrowself typ valnone tbnone if val is none if tb is none raise typ val typ if tb is not none val val withtracebacktb raise val async def acloseself try await self athrowgeneratorexit except generatorexit stopasynciteration pass else raise runtimeerrorasynchronous generator ignored generatorexit classmethod def subclasshookcls c if cls is asyncgenerator return checkmethodsc aiter anext asend athrow aclose return notimplemented asyncgenerator registerasyncgenerator class iterablemetaclassabcmeta slots abstractmethod def iterself while false yield none classmethod def subclasshookcls c if cls is iterable return checkmethodsc iter return notimplemented classgetitem classmethodgenericalias class iteratoriterable slots abstractmethod def nextself return the next item from the iterator when exhausted raise stopiteration raise stopiteration def iterself return self classmethod def subclasshookcls c if cls is iterator return checkmethodsc iter next return notimplemented iterator registerbytesiterator iterator registerbytearrayiterator iterator registercallableiterator iterator registerdictkeyiterator iterator registerdictvalueiterator iterator registerdictitemiterator iterator registerlistiterator iterator registerlistreverseiterator iterator registerrangeiterator iterator registerlongrangeiterator iterator registersetiterator iterator registerstriterator iterator registertupleiterator iterator registerzipiterator class reversibleiterable slots abstractmethod def reversedself while false yield none classmethod def subclasshookcls c if cls is reversible return checkmethodsc reversed iter return notimplemented class generatoriterator slots def nextself return self sendnone abstractmethod def sendself value raise stopiteration abstractmethod def throwself typ valnone tbnone if val is none if tb is none raise typ val typ if tb is not none val val withtracebacktb raise val def closeself try self throwgeneratorexit except generatorexit stopiteration pass else raise runtimeerrorgenerator ignored generatorexit classmethod def subclasshookcls c if cls is generator return checkmethodsc iter next send throw close return notimplemented generator registergenerator class sizedmetaclassabcmeta slots abstractmethod def lenself return 0 classmethod def subclasshookcls c if cls is sized return checkmethodsc len return notimplemented class containermetaclassabcmeta slots abstractmethod def containsself x return false classmethod def subclasshookcls c if cls is container return checkmethodsc contains return notimplemented classgetitem classmethodgenericalias class collectionsized iterable container slots classmethod def subclasshookcls c if cls is collection return checkmethodsc len iter contains return notimplemented class buffermetaclassabcmeta slots abstractmethod def bufferself flags int memoryview raise notimplementederror classmethod def subclasshookcls c if cls is buffer return checkmethodsc buffer return notimplemented class callablegenericaliasgenericalias slots def newcls origin args if not isinstanceargs tuple and lenargs 2 raise typeerror callable must be used as callablearg result targs tresult args if isinstancetargs tuple list args targs tresult elif not isparamexprtargs raise typeerrorfexpected a list of types an ellipsis fparamspec or concatenate got targs return super newcls origin args def reprself if lenself args 2 and isparamexprself args0 return super repr return f collections abc callable f jointyperepra for a in self args 1 f typereprself args1 def reduceself args self args if not lenargs 2 and isparamexprargs0 args listargs 1 args1 return callablegenericalias callable args def getitemself item called during typevar substitution returns the custom subclass rather than the default types genericalias object most of the code is copied from typing s genericalias and the builtin types genericalias if not isinstanceitem tuple item item newargs super getitemitem args args0 occurs due to things like zint str bool from pep 612 if not isinstancenewargs0 tuple list tresult newargs1 targs newargs 1 newargs targs tresult return callablegenericaliascallable tuplenewargs def isparamexprobj if obj is ellipsis return true if isinstanceobj list return true obj typeobj names paramspec concatenategenericalias return obj module typing and anyobj name name for name in names def typereprobj if isinstanceobj type if obj module builtins return obj qualname return f obj module obj qualname if obj is ellipsis return if isinstanceobj functiontype return obj name return reprobj class callablemetaclassabcmeta slots abstractmethod def callself args kwds return false classmethod def subclasshookcls c if cls is callable return checkmethodsc call return notimplemented classgetitem classmethodcallablegenericalias sets class setcollection slots def leself other if not isinstanceother set return notimplemented if lenself lenother return false for elem in self if elem not in other return false return true def ltself other if not isinstanceother set return notimplemented return lenself lenother and self leother def gtself other if not isinstanceother set return notimplemented return lenself lenother and self geother def geself other if not isinstanceother set return notimplemented if lenself lenother return false for elem in other if elem not in self return false return true def eqself other if not isinstanceother set return notimplemented return lenself lenother and self leother classmethod def fromiterablecls it return clsit def andself other if not isinstanceother iterable return notimplemented return self fromiterablevalue for value in other if value in self rand and def isdisjointself other return true if two sets have a null intersection for value in other if value in self return false return true def orself other if not isinstanceother iterable return notimplemented chain e for s in self other for e in s return self fromiterablechain ror or def subself other if not isinstanceother set if not isinstanceother iterable return notimplemented other self fromiterableother return self fromiterablevalue for value in self if value not in other def rsubself other if not isinstanceother set if not isinstanceother iterable return notimplemented other self fromiterableother return self fromiterablevalue for value in other if value not in self def xorself other if not isinstanceother set if not isinstanceother iterable return notimplemented other self fromiterableother return self other other self rxor xor def hashself max sys maxsize mask 2 max 1 n lenself h 1927868237 n 1 h mask for x in self hx hashx h hx hx 16 89869747 3644798167 h mask h h 11 h 25 h h 69069 907133923 h mask if h max h mask 1 if h 1 h 590923713 return h set registerfrozenset class mutablesetset slots abstractmethod def addself value remove an element do not raise an exception if absent raise notimplementederror def removeself value return the popped value raise keyerror if empty it iterself try value nextit except stopiteration raise keyerror from none self discardvalue return value def clearself mappings a mapping is a generic container for associating keyvalue pairs this class provides concrete generic implementations of all methods except for getitem iter and len tell abcmeta new that this class should have tpflagsmapping set a mutablemapping is a generic container for associating keyvalue pairs this class provides concrete generic implementations of all methods except for getitem setitem delitem iter and len d popk d v remove specified key and return the corresponding value if key is not found d is returned if given otherwise keyerror is raised d popitem k v remove and return some key value pair as a 2tuple but raise keyerror if d is empty d updatee f none update d from mappingiterable e and f if e present and has a keys method does for k in e dk ek if e present and lacks keys method does for k v in e dk v in either case this is followed by for k v in f items dk v sequences all the operations on a readonly sequence concrete subclasses must override new or init getitem and len tell abcmeta new that this class should have tpflagssequence set s indexvalue start stop integer return first index of value raises valueerror if the value is not present supporting start and stop arguments is optional but recommended this unifies bytes and bytearray xxx should add all their methods all the operations on a readwrite sequence concrete subclasses must provide new or init getitem setitem delitem len and insert s popindex item remove and return item at index default last raise indexerror if list is empty or index is out of range s removevalue remove first occurrence of value raise valueerror if the value is not present 2007 google inc licensed to psf under a contributor agreement abstract base classes abcs for collections according to pep 3119 unit tests are in test_collections maintenance notes abcs are different from other standard library modules in that they specify compliance tests in general once an abc has been published new methods either abstract or concrete cannot be added though classes that inherit from an abc would automatically receive a new mixin method registered classes would become non compliant and violate the contract promised by isinstance someobj someabc though irritating the correct procedure for adding new abstract or mixin methods is to create a new abc as a subclass of the previous abc for example union intersection and difference cannot be added to set but could go into a new abc that extends set because they are so hard to change new abcs should have their apis carefully thought through prior to publication since abcmeta only checks for the presence of methods it is possible to alter the signature of a method by adding optional arguments or changing parameters names this is still a bit dubious but at least it won t cause isinstance to return an incorrect result this module has been renamed from collections abc to _collections_abc to speed up interpreter startup some of the types such as mutablemapping are required early but collections module imports a lot of other modules see issue 19218 private list of types that we want to register with the various abcs so that they will pass tests like it iter somebytearray assert isinstance it iterable note in other implementations these types might not be distinct and they may have their own implementation specific types that are not included on this list callable_iterator views misc coroutine prevent resourcewarning asynchronous generator one trick ponies send a value into the coroutine return next yielded value or raise stopiteration raise an exception in the coroutine return next yielded value or raise stopiteration raise generatorexit inside coroutine return the next item or raise stopasynciteration when exhausted return the next item from the asynchronous generator when exhausted raise stopasynciteration send a value into the asynchronous generator return next yielded value or raise stopasynciteration raise an exception in the asynchronous generator return next yielded value or raise stopasynciteration raise generatorexit inside coroutine iterator register callable_iterator return the next item from the generator when exhausted raise stopiteration send a value into the generator return next yielded value or raise stopiteration raise an exception in the generator return next yielded value or raise stopiteration raise generatorexit inside generator represent callable argtypes resulttype this sets __args__ to a tuple containing the flattened argtypes followed by resulttype example callable int str float sets __args__ to int str float called during typevar substitution returns the custom subclass rather than the default types genericalias object most of the code is copied from typing s _genericalias and the builtin types genericalias args 0 occurs due to things like z int str bool from pep 612 checks if obj matches either a list of types paramspec or _concatenategenericalias from typing py return the repr of an object special casing types internal helper copied from mod typing since collections abc shouldn t depend on that module keep this roughly in sync with the typing version sets 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 redefine __le__ and __ge__ then the other operations will automatically follow suit construct an instance of the class from any iterable input must override this method if the class constructor signature does not accept an iterable for an input 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 a mutable set is a finite iterable container this class provides concrete generic implementations of all methods except for __contains__ __iter__ __len__ add and discard 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 add an element remove an element do not raise an exception if absent remove an element if not a member raise a keyerror return the popped value raise keyerror if empty this is slow creates n new iterators but effective mappings a mapping is a generic container for associating key value pairs this class provides concrete generic implementations of all methods except for __getitem__ __iter__ and __len__ tell abcmeta __new__ that this class should have tpflags_mapping set py_tpflags_mapping a mutablemapping is a generic container for associating key value pairs this class provides concrete generic implementations of all methods except for __getitem__ __setitem__ __delitem__ __iter__ and __len__ d pop k d v remove specified key and return the corresponding value if key is not found d is returned if given otherwise keyerror is raised d popitem k v remove and return some key value pair as a 2 tuple but raise keyerror if d is empty d update e f none update d from mapping iterable e and f if e present and has a keys method does for k in e d k e k if e present and lacks keys method does for k v in e d k v in either case this is followed by for k v in f items d k v sequences all the operations on a read only sequence concrete subclasses must override __new__ or __init__ __getitem__ and __len__ tell abcmeta __new__ that this class should have tpflags_sequence set py_tpflags_sequence s index value start stop integer return first index of value raises valueerror if the value is not present supporting start and stop arguments is optional but recommended this unifies bytes and bytearray xxx should add all their methods all the operations on a read write sequence concrete subclasses must provide __new__ or __init__ __getitem__ __setitem__ __delitem__ __len__ and insert s pop index item remove and return item at index default last raise indexerror if list is empty or index is out of range s remove value remove first occurrence of value raise valueerror if the value is not present multiply inheriting see bytestring
from abc import ABCMeta, abstractmethod
import sys

GenericAlias = type(list[int])
EllipsisType = type(...)
def _f(): pass
FunctionType = type(_f)
del _f

__all__ = ["Awaitable", "Coroutine",
           "AsyncIterable", "AsyncIterator", "AsyncGenerator",
           "Hashable", "Iterable", "Iterator", "Generator", "Reversible",
           "Sized", "Container", "Callable", "Collection",
           "Set", "MutableSet",
           "Mapping", "MutableMapping",
           "MappingView", "KeysView", "ItemsView", "ValuesView",
           "Sequence", "MutableSequence",
           "ByteString", "Buffer",
           ]





__name__ = "collections.abc"








bytes_iterator = type(iter(b''))
bytearray_iterator = type(iter(bytearray()))

dict_keyiterator = type(iter({}.keys()))
dict_valueiterator = type(iter({}.values()))
dict_itemiterator = type(iter({}.items()))
list_iterator = type(iter([]))
list_reverseiterator = type(iter(reversed([])))
range_iterator = type(iter(range(0)))
longrange_iterator = type(iter(range(1 << 1000)))
set_iterator = type(iter(set()))
str_iterator = type(iter(""))
tuple_iterator = type(iter(()))
zip_iterator = type(iter(zip()))

dict_keys = type({}.keys())
dict_values = type({}.values())
dict_items = type({}.items())

mappingproxy = type(type.__dict__)
generator = type((lambda: (yield))())

async def _coro(): pass
_coro = _coro()
coroutine = type(_coro)
_coro.close()  
del _coro

async def _ag(): yield
_ag = _ag()
async_generator = type(_ag)
del _ag




def _check_methods(C, *methods):
    mro = C.__mro__
    for method in methods:
        for B in mro:
            if method in B.__dict__:
                if B.__dict__[method] is None:
                    return NotImplemented
                break
        else:
            return NotImplemented
    return True

class Hashable(metaclass=ABCMeta):

    __slots__ = ()

    @abstractmethod
    def __hash__(self):
        return 0

    @classmethod
    def __subclasshook__(cls, C):
        if cls is Hashable:
            return _check_methods(C, "__hash__")
        return NotImplemented


class Awaitable(metaclass=ABCMeta):

    __slots__ = ()

    @abstractmethod
    def __await__(self):
        yield

    @classmethod
    def __subclasshook__(cls, C):
        if cls is Awaitable:
            return _check_methods(C, "__await__")
        return NotImplemented

    __class_getitem__ = classmethod(GenericAlias)


class Coroutine(Awaitable):

    __slots__ = ()

    @abstractmethod
    def send(self, value):
        
        raise StopIteration

    @abstractmethod
    def throw(self, typ, val=None, tb=None):
        
        if val is None:
            if tb is None:
                raise typ
            val = typ()
        if tb is not None:
            val = val.with_traceback(tb)
        raise val

    def close(self):
        
        try:
            self.throw(GeneratorExit)
        except (GeneratorExit, StopIteration):
            pass
        else:
            raise RuntimeError("coroutine ignored GeneratorExit")

    @classmethod
    def __subclasshook__(cls, C):
        if cls is Coroutine:
            return _check_methods(C, '__await__', 'send', 'throw', 'close')
        return NotImplemented


Coroutine.register(coroutine)


class AsyncIterable(metaclass=ABCMeta):

    __slots__ = ()

    @abstractmethod
    def __aiter__(self):
        return AsyncIterator()

    @classmethod
    def __subclasshook__(cls, C):
        if cls is AsyncIterable:
            return _check_methods(C, "__aiter__")
        return NotImplemented

    __class_getitem__ = classmethod(GenericAlias)


class AsyncIterator(AsyncIterable):

    __slots__ = ()

    @abstractmethod
    async def __anext__(self):
        
        raise StopAsyncIteration

    def __aiter__(self):
        return self

    @classmethod
    def __subclasshook__(cls, C):
        if cls is AsyncIterator:
            return _check_methods(C, "__anext__", "__aiter__")
        return NotImplemented


class AsyncGenerator(AsyncIterator):

    __slots__ = ()

    async def __anext__(self):
        
        return await self.asend(None)

    @abstractmethod
    async def asend(self, value):
        
        raise StopAsyncIteration

    @abstractmethod
    async def athrow(self, typ, val=None, tb=None):
        
        if val is None:
            if tb is None:
                raise typ
            val = typ()
        if tb is not None:
            val = val.with_traceback(tb)
        raise val

    async def aclose(self):
        
        try:
            await self.athrow(GeneratorExit)
        except (GeneratorExit, StopAsyncIteration):
            pass
        else:
            raise RuntimeError("asynchronous generator ignored GeneratorExit")

    @classmethod
    def __subclasshook__(cls, C):
        if cls is AsyncGenerator:
            return _check_methods(C, '__aiter__', '__anext__',
                                  'asend', 'athrow', 'aclose')
        return NotImplemented


AsyncGenerator.register(async_generator)


class Iterable(metaclass=ABCMeta):

    __slots__ = ()

    @abstractmethod
    def __iter__(self):
        while False:
            yield None

    @classmethod
    def __subclasshook__(cls, C):
        if cls is Iterable:
            return _check_methods(C, "__iter__")
        return NotImplemented

    __class_getitem__ = classmethod(GenericAlias)


class Iterator(Iterable):

    __slots__ = ()

    @abstractmethod
    def __next__(self):
        'Return the next item from the iterator. When exhausted, raise StopIteration'
        raise StopIteration

    def __iter__(self):
        return self

    @classmethod
    def __subclasshook__(cls, C):
        if cls is Iterator:
            return _check_methods(C, '__iter__', '__next__')
        return NotImplemented


Iterator.register(bytes_iterator)
Iterator.register(bytearray_iterator)

Iterator.register(dict_keyiterator)
Iterator.register(dict_valueiterator)
Iterator.register(dict_itemiterator)
Iterator.register(list_iterator)
Iterator.register(list_reverseiterator)
Iterator.register(range_iterator)
Iterator.register(longrange_iterator)
Iterator.register(set_iterator)
Iterator.register(str_iterator)
Iterator.register(tuple_iterator)
Iterator.register(zip_iterator)


class Reversible(Iterable):

    __slots__ = ()

    @abstractmethod
    def __reversed__(self):
        while False:
            yield None

    @classmethod
    def __subclasshook__(cls, C):
        if cls is Reversible:
            return _check_methods(C, "__reversed__", "__iter__")
        return NotImplemented


class Generator(Iterator):

    __slots__ = ()

    def __next__(self):
        
        return self.send(None)

    @abstractmethod
    def send(self, value):
        
        raise StopIteration

    @abstractmethod
    def throw(self, typ, val=None, tb=None):
        
        if val is None:
            if tb is None:
                raise typ
            val = typ()
        if tb is not None:
            val = val.with_traceback(tb)
        raise val

    def close(self):
        
        try:
            self.throw(GeneratorExit)
        except (GeneratorExit, StopIteration):
            pass
        else:
            raise RuntimeError("generator ignored GeneratorExit")

    @classmethod
    def __subclasshook__(cls, C):
        if cls is Generator:
            return _check_methods(C, '__iter__', '__next__',
                                  'send', 'throw', 'close')
        return NotImplemented


Generator.register(generator)


class Sized(metaclass=ABCMeta):

    __slots__ = ()

    @abstractmethod
    def __len__(self):
        return 0

    @classmethod
    def __subclasshook__(cls, C):
        if cls is Sized:
            return _check_methods(C, "__len__")
        return NotImplemented


class Container(metaclass=ABCMeta):

    __slots__ = ()

    @abstractmethod
    def __contains__(self, x):
        return False

    @classmethod
    def __subclasshook__(cls, C):
        if cls is Container:
            return _check_methods(C, "__contains__")
        return NotImplemented

    __class_getitem__ = classmethod(GenericAlias)


class Collection(Sized, Iterable, Container):

    __slots__ = ()

    @classmethod
    def __subclasshook__(cls, C):
        if cls is Collection:
            return _check_methods(C,  "__len__", "__iter__", "__contains__")
        return NotImplemented


class Buffer(metaclass=ABCMeta):

    __slots__ = ()

    @abstractmethod
    def __buffer__(self, flags: int, /) -> memoryview:
        raise NotImplementedError

    @classmethod
    def __subclasshook__(cls, C):
        if cls is Buffer:
            return _check_methods(C, "__buffer__")
        return NotImplemented


class _CallableGenericAlias(GenericAlias):
    

    __slots__ = ()

    def __new__(cls, origin, args):
        if not (isinstance(args, tuple) and len(args) == 2):
            raise TypeError(
                "Callable must be used as Callable[[arg, ...], result].")
        t_args, t_result = args
        if isinstance(t_args, (tuple, list)):
            args = (*t_args, t_result)
        elif not _is_param_expr(t_args):
            raise TypeError(f"Expected a list of types, an ellipsis, "
                            f"ParamSpec, or Concatenate. Got {t_args}")
        return super().__new__(cls, origin, args)

    def __repr__(self):
        if len(self.__args__) == 2 and _is_param_expr(self.__args__[0]):
            return super().__repr__()
        return (f'collections.abc.Callable'
                f'[[{", ".join([_type_repr(a) for a in self.__args__[:-1]])}], '
                f'{_type_repr(self.__args__[-1])}]')

    def __reduce__(self):
        args = self.__args__
        if not (len(args) == 2 and _is_param_expr(args[0])):
            args = list(args[:-1]), args[-1]
        return _CallableGenericAlias, (Callable, args)

    def __getitem__(self, item):
        
        
        
        
        if not isinstance(item, tuple):
            item = (item,)

        new_args = super().__getitem__(item).__args__

        
        if not isinstance(new_args[0], (tuple, list)):
            t_result = new_args[-1]
            t_args = new_args[:-1]
            new_args = (t_args, t_result)
        return _CallableGenericAlias(Callable, tuple(new_args))

def _is_param_expr(obj):
    
    if obj is Ellipsis:
        return True
    if isinstance(obj, list):
        return True
    obj = type(obj)
    names = ('ParamSpec', '_ConcatenateGenericAlias')
    return obj.__module__ == 'typing' and any(obj.__name__ == name for name in names)

def _type_repr(obj):
    
    if isinstance(obj, type):
        if obj.__module__ == 'builtins':
            return obj.__qualname__
        return f'{obj.__module__}.{obj.__qualname__}'
    if obj is Ellipsis:
        return '...'
    if isinstance(obj, FunctionType):
        return obj.__name__
    return repr(obj)


class Callable(metaclass=ABCMeta):

    __slots__ = ()

    @abstractmethod
    def __call__(self, *args, **kwds):
        return False

    @classmethod
    def __subclasshook__(cls, C):
        if cls is Callable:
            return _check_methods(C, "__call__")
        return NotImplemented

    __class_getitem__ = classmethod(_CallableGenericAlias)





class Set(Collection):
    

    __slots__ = ()

    def __le__(self, other):
        if not isinstance(other, Set):
            return NotImplemented
        if len(self) > len(other):
            return False
        for elem in self:
            if elem not in other:
                return False
        return True

    def __lt__(self, other):
        if not isinstance(other, Set):
            return NotImplemented
        return len(self) < len(other) and self.__le__(other)

    def __gt__(self, other):
        if not isinstance(other, Set):
            return NotImplemented
        return len(self) > len(other) and self.__ge__(other)

    def __ge__(self, other):
        if not isinstance(other, Set):
            return NotImplemented
        if len(self) < len(other):
            return False
        for elem in other:
            if elem not in self:
                return False
        return True

    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 cls(it)

    def __and__(self, other):
        if not isinstance(other, Iterable):
            return NotImplemented
        return self._from_iterable(value for value in other if value in self)

    __rand__ = __and__

    def isdisjoint(self, other):
        'Return True if two sets have a null intersection.'
        for value in other:
            if value in self:
                return False
        return True

    def __or__(self, other):
        if not isinstance(other, Iterable):
            return NotImplemented
        chain = (e for s in (self, other) for e in s)
        return self._from_iterable(chain)

    __ror__ = __or__

    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 __rsub__(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 other
                                   if value not in self)

    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)

    __rxor__ = __xor__

    def _hash(self):
        
        MAX = sys.maxsize
        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 >> 11) ^ (h >> 25)
        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):
    

    __slots__ = ()

    @abstractmethod
    def add(self, value):
        
        raise NotImplementedError

    @abstractmethod
    def discard(self, value):
        
        raise NotImplementedError

    def remove(self, value):
        
        if value not in self:
            raise KeyError(value)
        self.discard(value)

    def pop(self):
        
        it = iter(self)
        try:
            value = next(it)
        except StopIteration:
            raise KeyError from None
        self.discard(value)
        return value

    def clear(self):
        
        try:
            while True:
                self.pop()
        except KeyError:
            pass

    def __ior__(self, it):
        for value in it:
            self.add(value)
        return self

    def __iand__(self, it):
        for value in (self - it):
            self.discard(value)
        return self

    def __ixor__(self, it):
        if it is self:
            self.clear()
        else:
            if not isinstance(it, Set):
                it = self._from_iterable(it)
            for value in it:
                if value in self:
                    self.discard(value)
                else:
                    self.add(value)
        return self

    def __isub__(self, it):
        if it is self:
            self.clear()
        else:
            for value in it:
                self.discard(value)
        return self


MutableSet.register(set)




class Mapping(Collection):
    

    __slots__ = ()

    
    __abc_tpflags__ = 1 << 6 

    @abstractmethod
    def __getitem__(self, key):
        raise KeyError

    def get(self, key, default=None):
        'D.get(k[,d]) -> D[k] if k in D, else d.  d defaults to None.'
        try:
            return self[key]
        except KeyError:
            return default

    def __contains__(self, key):
        try:
            self[key]
        except KeyError:
            return False
        else:
            return True

    def keys(self):
        "D.keys() -> a set-like object providing a view on D's keys"
        return KeysView(self)

    def items(self):
        "D.items() -> a set-like object providing a view on D's items"
        return ItemsView(self)

    def values(self):
        "D.values() -> an object providing a view on D's values"
        return ValuesView(self)

    def __eq__(self, other):
        if not isinstance(other, Mapping):
            return NotImplemented
        return dict(self.items()) == dict(other.items())

    __reversed__ = None

Mapping.register(mappingproxy)


class MappingView(Sized):

    __slots__ = '_mapping',

    def __init__(self, mapping):
        self._mapping = mapping

    def __len__(self):
        return len(self._mapping)

    def __repr__(self):
        return '{0.__class__.__name__}({0._mapping!r})'.format(self)

    __class_getitem__ = classmethod(GenericAlias)


class KeysView(MappingView, Set):

    __slots__ = ()

    @classmethod
    def _from_iterable(cls, it):
        return set(it)

    def __contains__(self, key):
        return key in self._mapping

    def __iter__(self):
        yield from self._mapping


KeysView.register(dict_keys)


class ItemsView(MappingView, Set):

    __slots__ = ()

    @classmethod
    def _from_iterable(cls, it):
        return set(it)

    def __contains__(self, item):
        key, value = item
        try:
            v = self._mapping[key]
        except KeyError:
            return False
        else:
            return v is value or v == value

    def __iter__(self):
        for key in self._mapping:
            yield (key, self._mapping[key])


ItemsView.register(dict_items)


class ValuesView(MappingView, Collection):

    __slots__ = ()

    def __contains__(self, value):
        for key in self._mapping:
            v = self._mapping[key]
            if v is value or v == value:
                return True
        return False

    def __iter__(self):
        for key in self._mapping:
            yield self._mapping[key]


ValuesView.register(dict_values)


class MutableMapping(Mapping):
    

    __slots__ = ()

    @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 from None
        value = self[key]
        del self[key]
        return key, value

    def clear(self):
        'D.clear() -> None.  Remove all items from D.'
        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

    def setdefault(self, key, default=None):
        'D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D'
        try:
            return self[key]
        except KeyError:
            self[key] = default
        return default


MutableMapping.register(dict)




class Sequence(Reversible, Collection):
    

    __slots__ = ()

    
    __abc_tpflags__ = 1 << 5 

    @abstractmethod
    def __getitem__(self, index):
        raise IndexError

    def __iter__(self):
        i = 0
        try:
            while True:
                v = self[i]
                yield v
                i += 1
        except IndexError:
            return

    def __contains__(self, value):
        for v in self:
            if v is value or v == value:
                return True
        return False

    def __reversed__(self):
        for i in reversed(range(len(self))):
            yield self[i]

    def index(self, value, start=0, stop=None):
        
        if start is not None and start < 0:
            start = max(len(self) + start, 0)
        if stop is not None and stop < 0:
            stop += len(self)

        i = start
        while stop is None or i < stop:
            try:
                v = self[i]
            except IndexError:
                break
            if v is value or v == value:
                return i
            i += 1
        raise ValueError

    def count(self, value):
        'S.count(value) -> integer -- return number of occurrences of value'
        return sum(1 for v in self if v is value or v == value)

Sequence.register(tuple)
Sequence.register(str)
Sequence.register(range)
Sequence.register(memoryview)

class _DeprecateByteStringMeta(ABCMeta):
    def __new__(cls, name, bases, namespace, **kwargs):
        if name != "ByteString":
            import warnings

            warnings._deprecated(
                "collections.abc.ByteString",
                remove=(3, 14),
            )
        return super().__new__(cls, name, bases, namespace, **kwargs)

    def __instancecheck__(cls, instance):
        import warnings

        warnings._deprecated(
            "collections.abc.ByteString",
            remove=(3, 14),
        )
        return super().__instancecheck__(instance)

class ByteString(Sequence, metaclass=_DeprecateByteStringMeta):
    

    __slots__ = ()

ByteString.register(bytes)
ByteString.register(bytearray)


class MutableSequence(Sequence):
    

    __slots__ = ()

    @abstractmethod
    def __setitem__(self, index, value):
        raise IndexError

    @abstractmethod
    def __delitem__(self, index):
        raise IndexError

    @abstractmethod
    def insert(self, index, value):
        'S.insert(index, value) -- insert value before index'
        raise IndexError

    def append(self, value):
        'S.append(value) -- append value to the end of the sequence'
        self.insert(len(self), value)

    def clear(self):
        'S.clear() -> None -- remove all items from S'
        try:
            while True:
                self.pop()
        except IndexError:
            pass

    def reverse(self):
        'S.reverse() -- reverse *IN PLACE*'
        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):
        'S.extend(iterable) -- extend sequence by appending elements from the iterable'
        if values is self:
            values = list(values)
        for v in values:
            self.append(v)

    def pop(self, index=-1):
        
        v = self[index]
        del self[index]
        return v

    def remove(self, value):
        
        del self[self.index(value)]

    def __iadd__(self, values):
        self.extend(values)
        return self


MutableSequence.register(list)
MutableSequence.register(bytearray)