_collections_abc.py 24.6 KB
Newer Older
1 2 3 4 5
# Copyright 2007 Google, Inc. All Rights Reserved.
# Licensed to PSF under a Contributor Agreement.

"""Abstract Base Classes (ABCs) for collections, according to PEP 3119.

6
Unit tests are in test_collections.
7 8 9
"""

from abc import ABCMeta, abstractmethod
Benjamin Peterson's avatar
Benjamin Peterson committed
10
import sys
11

12
__all__ = ["Awaitable", "Coroutine", "AsyncIterable", "AsyncIterator",
13
           "Hashable", "Iterable", "Iterator", "Generator", "Reversible",
14 15 16 17 18
           "Sized", "Container", "Callable",
           "Set", "MutableSet",
           "Mapping", "MutableMapping",
           "MappingView", "KeysView", "ItemsView", "ValuesView",
           "Sequence", "MutableSequence",
19
           "ByteString",
20 21
           ]

22 23 24 25 26 27
# 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
__name__ = "collections.abc"

28 29 30 31 32 33 34
# 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 many not be distinct
# and they make have their own implementation specific types that
# are not included on this list.
35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
bytes_iterator = type(iter(b''))
bytearray_iterator = type(iter(bytearray()))
#callable_iterator = ???
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)))
set_iterator = type(iter(set()))
str_iterator = type(iter(""))
tuple_iterator = type(iter(()))
zip_iterator = type(iter(zip()))
## views ##
dict_keys = type({}.keys())
dict_values = type({}.values())
dict_items = type({}.items())
52
## misc ##
53
mappingproxy = type(type.__dict__)
54
generator = type((lambda: (yield))())
55 56 57 58 59 60
## coroutine ##
async def _coro(): pass
_coro = _coro()
coroutine = type(_coro)
_coro.close()  # Prevent ResourceWarning
del _coro
61 62


63 64 65 66
### ONE-TRICK PONIES ###

class Hashable(metaclass=ABCMeta):

67 68
    __slots__ = ()

69 70 71 72 73 74 75 76 77 78 79 80 81 82 83
    @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


84
class Awaitable(metaclass=ABCMeta):
85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103

    __slots__ = ()

    @abstractmethod
    def __await__(self):
        yield

    @classmethod
    def __subclasshook__(cls, C):
        if cls is Awaitable:
            for B in C.__mro__:
                if "__await__" in B.__dict__:
                    if B.__dict__["__await__"]:
                        return True
                    break
        return NotImplemented


class Coroutine(Awaitable):
104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138

    __slots__ = ()

    @abstractmethod
    def send(self, value):
        """Send a value into the coroutine.
        Return next yielded value or raise StopIteration.
        """
        raise StopIteration

    @abstractmethod
    def throw(self, typ, val=None, tb=None):
        """Raise an exception in the coroutine.
        Return next yielded value or raise StopIteration.
        """
        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):
        """Raise GeneratorExit inside coroutine.
        """
        try:
            self.throw(GeneratorExit)
        except (GeneratorExit, StopIteration):
            pass
        else:
            raise RuntimeError("coroutine ignored GeneratorExit")

    @classmethod
    def __subclasshook__(cls, C):
139 140 141 142 143 144 145 146 147
        if cls is Coroutine:
            mro = C.__mro__
            for method in ('__await__', 'send', 'throw', 'close'):
                for base in mro:
                    if method in base.__dict__:
                        break
                else:
                    return NotImplemented
            return True
148 149 150
        return NotImplemented


151 152 153
Coroutine.register(coroutine)


154 155 156 157 158
class AsyncIterable(metaclass=ABCMeta):

    __slots__ = ()

    @abstractmethod
159
    def __aiter__(self):
160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178
        return AsyncIterator()

    @classmethod
    def __subclasshook__(cls, C):
        if cls is AsyncIterable:
            if any("__aiter__" in B.__dict__ for B in C.__mro__):
                return True
        return NotImplemented


class AsyncIterator(AsyncIterable):

    __slots__ = ()

    @abstractmethod
    async def __anext__(self):
        """Return the next item or raise StopAsyncIteration when exhausted."""
        raise StopAsyncIteration

179
    def __aiter__(self):
180 181 182 183 184 185 186 187 188 189 190
        return self

    @classmethod
    def __subclasshook__(cls, C):
        if cls is AsyncIterator:
            if (any("__anext__" in B.__dict__ for B in C.__mro__) and
                any("__aiter__" in B.__dict__ for B in C.__mro__)):
                return True
        return NotImplemented


191 192
class Iterable(metaclass=ABCMeta):

193 194
    __slots__ = ()

195 196 197 198 199 200 201 202 203 204 205 206 207
    @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


Raymond Hettinger's avatar
Raymond Hettinger committed
208
class Iterator(Iterable):
209

210 211
    __slots__ = ()

212 213
    @abstractmethod
    def __next__(self):
214
        'Return the next item from the iterator. When exhausted, raise StopIteration'
215 216 217 218 219 220 221 222
        raise StopIteration

    def __iter__(self):
        return self

    @classmethod
    def __subclasshook__(cls, C):
        if cls is Iterator:
223 224
            if (any("__next__" in B.__dict__ for B in C.__mro__) and
                any("__iter__" in B.__dict__ for B in C.__mro__)):
225 226 227
                return True
        return NotImplemented

228 229 230 231 232 233 234 235 236 237 238 239 240
Iterator.register(bytes_iterator)
Iterator.register(bytearray_iterator)
#Iterator.register(callable_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(set_iterator)
Iterator.register(str_iterator)
Iterator.register(tuple_iterator)
Iterator.register(zip_iterator)
241

242

243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261
class Reversible(Iterable):

    __slots__ = ()

    @abstractmethod
    def __reversed__(self):
        return NotImplemented

    @classmethod
    def __subclasshook__(cls, C):
        if cls is Reversible:
            for B in C.__mro__:
                if "__reversed__" in B.__dict__:
                    if B.__dict__["__reversed__"] is not None:
                        return True
                    break
        return NotImplemented


262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318
class Generator(Iterator):

    __slots__ = ()

    def __next__(self):
        """Return the next item from the generator.
        When exhausted, raise StopIteration.
        """
        return self.send(None)

    @abstractmethod
    def send(self, value):
        """Send a value into the generator.
        Return next yielded value or raise StopIteration.
        """
        raise StopIteration

    @abstractmethod
    def throw(self, typ, val=None, tb=None):
        """Raise an exception in the generator.
        Return next yielded value or raise StopIteration.
        """
        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):
        """Raise GeneratorExit inside generator.
        """
        try:
            self.throw(GeneratorExit)
        except (GeneratorExit, StopIteration):
            pass
        else:
            raise RuntimeError("generator ignored GeneratorExit")

    @classmethod
    def __subclasshook__(cls, C):
        if cls is Generator:
            mro = C.__mro__
            for method in ('__iter__', '__next__', 'send', 'throw', 'close'):
                for base in mro:
                    if method in base.__dict__:
                        break
                else:
                    return NotImplemented
            return True
        return NotImplemented


Generator.register(generator)


319 320
class Sized(metaclass=ABCMeta):

321 322
    __slots__ = ()

323 324 325 326 327 328 329 330 331 332 333 334 335 336
    @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):

337 338
    __slots__ = ()

339 340 341 342 343 344 345 346 347 348 349 350 351 352
    @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):

353 354
    __slots__ = ()

355
    @abstractmethod
356
    def __call__(self, *args, **kwds):
357 358 359 360 361 362 363 364 365 366 367 368 369
        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 ###


Raymond Hettinger's avatar
Raymond Hettinger committed
370
class Set(Sized, Iterable, Container):
371 372 373 374 375 376 377

    """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
378
    semantics are fixed), redefine __le__ and __ge__,
379 380 381
    then the other operations will automatically follow suit.
    """

382 383
    __slots__ = ()

384 385 386 387 388 389 390 391 392 393 394 395 396 397 398
    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)

399 400 401
    def __gt__(self, other):
        if not isinstance(other, Set):
            return NotImplemented
402
        return len(self) > len(other) and self.__ge__(other)
403 404 405 406

    def __ge__(self, other):
        if not isinstance(other, Set):
            return NotImplemented
407 408 409 410 411 412
        if len(self) < len(other):
            return False
        for elem in other:
            if elem not in self:
                return False
        return True
413

414 415 416 417 418 419 420
    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):
421 422 423
        '''Construct an instance of the class from any iterable input.

        Must override this method if the class constructor signature
424
        does not accept an iterable for an input.
425
        '''
426
        return cls(it)
427 428 429 430 431 432

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

433 434
    __rand__ = __and__

435
    def isdisjoint(self, other):
436
        'Return True if two sets have a null intersection.'
437 438 439 440 441
        for value in other:
            if value in self:
                return False
        return True

442 443 444
    def __or__(self, other):
        if not isinstance(other, Iterable):
            return NotImplemented
445 446
        chain = (e for s in (self, other) for e in s)
        return self._from_iterable(chain)
447

448 449
    __ror__ = __or__

450 451 452 453 454 455 456 457
    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)

458 459 460 461 462 463 464 465
    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)

466 467 468 469 470 471 472
    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)

473 474
    __rxor__ = __xor__

475 476 477 478 479 480 481 482 483 484 485 486 487 488 489
    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.
        """
490
        MAX = sys.maxsize
491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510
        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):
511 512 513 514 515 516 517 518 519 520
    """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.
    """
521

522 523
    __slots__ = ()

524 525
    @abstractmethod
    def add(self, value):
Benjamin Peterson's avatar
Benjamin Peterson committed
526
        """Add an element."""
527 528 529 530
        raise NotImplementedError

    @abstractmethod
    def discard(self, value):
Benjamin Peterson's avatar
Benjamin Peterson committed
531
        """Remove an element.  Do not raise an exception if absent."""
532 533
        raise NotImplementedError

534 535 536 537 538 539
    def remove(self, value):
        """Remove an element. If not a member, raise a KeyError."""
        if value not in self:
            raise KeyError(value)
        self.discard(value)

540 541 542 543
    def pop(self):
        """Return the popped value.  Raise KeyError if empty."""
        it = iter(self)
        try:
544
            value = next(it)
545 546 547 548 549 550 551 552 553 554 555 556 557
        except StopIteration:
            raise KeyError
        self.discard(value)
        return value

    def clear(self):
        """This is slow (creates N new iterators!) but effective."""
        try:
            while True:
                self.pop()
        except KeyError:
            pass

558
    def __ior__(self, it):
559 560 561 562
        for value in it:
            self.add(value)
        return self

563
    def __iand__(self, it):
564 565
        for value in (self - it):
            self.discard(value)
566 567
        return self

568
    def __ixor__(self, it):
569 570 571 572 573 574 575 576 577 578
        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)
579 580
        return self

581
    def __isub__(self, it):
582 583 584 585 586
        if it is self:
            self.clear()
        else:
            for value in it:
                self.discard(value)
587 588 589 590 591 592 593 594
        return self

MutableSet.register(set)


### MAPPINGS ###


Raymond Hettinger's avatar
Raymond Hettinger committed
595
class Mapping(Sized, Iterable, Container):
596

597 598
    __slots__ = ()

599 600 601 602 603 604 605 606
    """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__.

    """

607 608 609 610 611
    @abstractmethod
    def __getitem__(self, key):
        raise KeyError

    def get(self, key, default=None):
612
        'D.get(k[,d]) -> D[k] if k in D, else d.  d defaults to None.'
613 614 615 616 617 618 619 620 621 622 623 624 625 626
        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):
627
        "D.keys() -> a set-like object providing a view on D's keys"
628 629 630
        return KeysView(self)

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

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

638
    def __eq__(self, other):
639 640 641
        if not isinstance(other, Mapping):
            return NotImplemented
        return dict(self.items()) == dict(other.items())
642

643 644
Mapping.register(mappingproxy)

Christian Heimes's avatar
Christian Heimes committed
645

646
class MappingView(Sized):
647

648 649
    __slots__ = '_mapping',

650 651 652 653 654 655
    def __init__(self, mapping):
        self._mapping = mapping

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

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

659 660 661

class KeysView(MappingView, Set):

662 663
    __slots__ = ()

664 665 666 667
    @classmethod
    def _from_iterable(self, it):
        return set(it)

668 669 670 671
    def __contains__(self, key):
        return key in self._mapping

    def __iter__(self):
Philip Jenvey's avatar
Philip Jenvey committed
672
        yield from self._mapping
673

674
KeysView.register(dict_keys)
675 676 677 678


class ItemsView(MappingView, Set):

679 680
    __slots__ = ()

681 682 683 684
    @classmethod
    def _from_iterable(self, it):
        return set(it)

685 686 687 688 689 690 691
    def __contains__(self, item):
        key, value = item
        try:
            v = self._mapping[key]
        except KeyError:
            return False
        else:
692
            return v is value or v == value
693 694 695 696 697

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

698
ItemsView.register(dict_items)
699 700 701 702


class ValuesView(MappingView):

703 704
    __slots__ = ()

705 706
    def __contains__(self, value):
        for key in self._mapping:
707 708
            v = self._mapping[key]
            if v is value or v == value:
709 710 711 712 713 714 715
                return True
        return False

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

716
ValuesView.register(dict_values)
717 718 719 720


class MutableMapping(Mapping):

721 722
    __slots__ = ()

723 724 725 726 727 728 729 730 731
    """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__.

    """

732 733 734 735 736 737 738 739 740 741 742
    @abstractmethod
    def __setitem__(self, key, value):
        raise KeyError

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

    __marker = object()

    def pop(self, key, default=__marker):
743 744 745
        '''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.
        '''
746 747 748 749 750 751 752 753 754 755 756
        try:
            value = self[key]
        except KeyError:
            if default is self.__marker:
                raise
            return default
        else:
            del self[key]
            return value

    def popitem(self):
757 758 759
        '''D.popitem() -> (k, v), remove and return some (key, value) pair
           as a 2-tuple; but raise KeyError if D is empty.
        '''
760 761 762 763 764 765 766 767 768
        try:
            key = next(iter(self))
        except StopIteration:
            raise KeyError
        value = self[key]
        del self[key]
        return key, value

    def clear(self):
769
        'D.clear() -> None.  Remove all items from D.'
770 771 772 773 774 775
        try:
            while True:
                self.popitem()
        except KeyError:
            pass

776
    def update(*args, **kwds):
777 778 779 780 781
        ''' 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
        '''
782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799
        if not args:
            raise TypeError("descriptor 'update' of 'MutableMapping' object "
                            "needs an argument")
        self, *args = args
        if len(args) > 1:
            raise TypeError('update expected at most 1 arguments, got %d' %
                            len(args))
        if args:
            other = args[0]
            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
800 801 802
        for key, value in kwds.items():
            self[key] = value

803
    def setdefault(self, key, default=None):
804
        'D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D'
805 806 807 808 809 810
        try:
            return self[key]
        except KeyError:
            self[key] = default
        return default

811 812 813 814 815 816
MutableMapping.register(dict)


### SEQUENCES ###


817
class Sequence(Sized, Reversible, Container):
818 819 820 821 822 823 824

    """All the operations on a read-only sequence.

    Concrete subclasses must override __new__ or __init__,
    __getitem__, and __len__.
    """

825 826
    __slots__ = ()

827 828 829 830 831 832
    @abstractmethod
    def __getitem__(self, index):
        raise IndexError

    def __iter__(self):
        i = 0
833 834
        try:
            while True:
835
                v = self[i]
836 837 838 839
                yield v
                i += 1
        except IndexError:
            return
840 841 842

    def __contains__(self, value):
        for v in self:
843
            if v is value or v == value:
844 845 846 847 848 849 850
                return True
        return False

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

851 852
    def index(self, value, start=0, stop=None):
        '''S.index(value, [start, [stop]]) -> integer -- return first index of value.
853 854
           Raises ValueError if the value is not present.
        '''
855 856 857 858 859 860 861 862 863 864 865 866 867
        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:
                if self[i] == value:
                    return i
            except IndexError:
                break
            i += 1
868 869 870
        raise ValueError

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

Sequence.register(tuple)
875
Sequence.register(str)
876
Sequence.register(range)
877
Sequence.register(memoryview)
878 879 880 881 882 883 884 885 886


class ByteString(Sequence):

    """This unifies bytes and bytearray.

    XXX Should add all their methods.
    """

887 888
    __slots__ = ()

889 890
ByteString.register(bytes)
ByteString.register(bytearray)
891 892 893 894


class MutableSequence(Sequence):

895 896
    __slots__ = ()

897
    """All the operations on a read-write sequence.
898 899 900 901 902 903

    Concrete subclasses must provide __new__ or __init__,
    __getitem__, __setitem__, __delitem__, __len__, and insert().

    """

904 905 906 907 908 909 910 911 912 913
    @abstractmethod
    def __setitem__(self, index, value):
        raise IndexError

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

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

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

921
    def clear(self):
922
        'S.clear() -> None -- remove all items from S'
923 924 925 926 927 928
        try:
            while True:
                self.pop()
        except IndexError:
            pass

929
    def reverse(self):
930
        'S.reverse() -- reverse *IN PLACE*'
931 932 933 934 935
        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):
936
        'S.extend(iterable) -- extend sequence by appending elements from the iterable'
937 938 939 940
        for v in values:
            self.append(v)

    def pop(self, index=-1):
941 942 943
        '''S.pop([index]) -> item -- remove and return item at index (default last).
           Raise IndexError if list is empty or index is out of range.
        '''
944 945 946 947 948
        v = self[index]
        del self[index]
        return v

    def remove(self, value):
949 950 951
        '''S.remove(value) -- remove first occurrence of value.
           Raise ValueError if the value is not present.
        '''
952 953 954 955
        del self[self.index(value)]

    def __iadd__(self, values):
        self.extend(values)
956
        return self
957 958

MutableSequence.register(list)
959
MutableSequence.register(bytearray)  # Multiply inheriting, see ByteString