[ovs-dev] Update bundled sortedcontainers to 2.4.0

This is needed since the current bundled version doesn't work on Python
3.10+.

Signed-off-by: Timothy Redaelli <tredaelli@redhat.com>
---
 python/ovs/compat/sortedcontainers/LICENSE    |    2 +-
 .../ovs/compat/sortedcontainers/__init__.py   |   70 +-
 .../ovs/compat/sortedcontainers/sorteddict.py | 1233 +++++----
 .../ovs/compat/sortedcontainers/sortedlist.py | 2409 +++++++++--------
 .../ovs/compat/sortedcontainers/sortedset.py  |  636 ++++-
 5 files changed, 2494 insertions(+), 1856 deletions(-)

On 7/2/21 12:17 PM, Timothy Redaelli wrote:
> This is needed since the current bundled version doesn't work on Python
> 3.10+.

Make sense.

Terry, could you, please, take a look?

I also wonder if we need to apply this patch to stable branches.
Thoughts?

Best regards, Ilya Maximets.

> 
> Signed-off-by: Timothy Redaelli <tredaelli@redhat.com>
> ---
>  python/ovs/compat/sortedcontainers/LICENSE    |    2 +-
>  .../ovs/compat/sortedcontainers/__init__.py   |   70 +-
>  .../ovs/compat/sortedcontainers/sorteddict.py | 1233 +++++----
>  .../ovs/compat/sortedcontainers/sortedlist.py | 2409 +++++++++--------
>  .../ovs/compat/sortedcontainers/sortedset.py  |  636 ++++-
>  5 files changed, 2494 insertions(+), 1856 deletions(-)
> 
> diff --git a/python/ovs/compat/sortedcontainers/LICENSE b/python/ovs/compat/sortedcontainers/LICENSE
> index 8794014e0..668d8ecd6 100644
> --- a/python/ovs/compat/sortedcontainers/LICENSE
> +++ b/python/ovs/compat/sortedcontainers/LICENSE
> @@ -1,4 +1,4 @@
> -Copyright 2014-2016 Grant Jenks
> +Copyright 2014-2019 Grant Jenks
>  
>  Licensed under the Apache License, Version 2.0 (the "License");
>  you may not use this file except in compliance with the License.
> diff --git a/python/ovs/compat/sortedcontainers/__init__.py b/python/ovs/compat/sortedcontainers/__init__.py
> index 392adfad6..a141dd1de 100644
> --- a/python/ovs/compat/sortedcontainers/__init__.py
> +++ b/python/ovs/compat/sortedcontainers/__init__.py
> @@ -1,9 +1,8 @@
> -"""Sorted Container Types: SortedList, SortedDict, SortedSet
> +"""Sorted Containers -- Sorted List, Sorted Dict, Sorted Set
>  
> -SortedContainers is an Apache2 licensed containers library, written in
> +Sorted Containers is an Apache2 licensed containers library, written in
>  pure-Python, and fast as C-extensions.
>  
> -
>  Python's standard library is great until you need a sorted collections
>  type. Many will attest that you can get really far without one, but the moment
>  you **really need** a sorted list, dict, or set, you're faced with a dozen
> @@ -14,39 +13,62 @@ In Python, we can do better. And we can do it in pure-Python!
>  
>  ::
>  
> -    >>> from sortedcontainers import SortedList, SortedDict, SortedSet
> -    >>> sl = SortedList(xrange(10000000))
> -    >>> 1234567 in sl
> -    True
> -    >>> sl[7654321]
> -    7654321
> -    >>> sl.add(1234567)
> -    >>> sl.count(1234567)
> +    >>> from sortedcontainers import SortedList
> +    >>> sl = SortedList(['e', 'a', 'c', 'd', 'b'])
> +    >>> sl
> +    SortedList(['a', 'b', 'c', 'd', 'e'])
> +    >>> sl *= 1000000
> +    >>> sl.count('c')
> +    1000000
> +    >>> sl[-3:]
> +    ['e', 'e', 'e']
> +    >>> from sortedcontainers import SortedDict
> +    >>> sd = SortedDict({'c': 3, 'a': 1, 'b': 2})
> +    >>> sd
> +    SortedDict({'a': 1, 'b': 2, 'c': 3})
> +    >>> sd.popitem(index=-1)
> +    ('c', 3)
> +    >>> from sortedcontainers import SortedSet
> +    >>> ss = SortedSet('abracadabra')
> +    >>> ss
> +    SortedSet(['a', 'b', 'c', 'd', 'r'])
> +    >>> ss.bisect_left('c')
>      2
> -    >>> sl *= 3
> -    >>> len(sl)
> -    30000003
>  
> -SortedContainers takes all of the work out of Python sorted types - making your
> -deployment and use of Python easy. There's no need to install a C compiler or
> -pre-build and distribute custom extensions. Performance is a feature and
> +Sorted Containers takes all of the work out of Python sorted types - making
> +your deployment and use of Python easy. There's no need to install a C compiler
> +or pre-build and distribute custom extensions. Performance is a feature and
>  testing has 100% coverage with unit tests and hours of stress.
>  
> -:copyright: (c) 2016 by Grant Jenks.
> +:copyright: (c) 2014-2019 by Grant Jenks.
>  :license: Apache 2.0, see LICENSE for more details.
>  
>  """
>  
>  
> -from .sortedlist import SortedList, SortedListWithKey
> +from .sortedlist import SortedList, SortedKeyList, SortedListWithKey
>  from .sortedset import SortedSet
> -from .sorteddict import SortedDict
> +from .sorteddict import (
> +    SortedDict,
> +    SortedKeysView,
> +    SortedItemsView,
> +    SortedValuesView,
> +)
>  
> -__all__ = ['SortedList', 'SortedSet', 'SortedDict', 'SortedListWithKey']
> +__all__ = [
> +    'SortedList',
> +    'SortedKeyList',
> +    'SortedListWithKey',
> +    'SortedDict',
> +    'SortedKeysView',
> +    'SortedItemsView',
> +    'SortedValuesView',
> +    'SortedSet',
> +]
>  
>  __title__ = 'sortedcontainers'
> -__version__ = '1.5.9'
> -__build__ = 0x010509
> +__version__ = '2.4.0'
> +__build__ = 0x020400
>  __author__ = 'Grant Jenks'
>  __license__ = 'Apache 2.0'
> -__copyright__ = 'Copyright 2016 Grant Jenks'
> +__copyright__ = '2014-2019, Grant Jenks'
> diff --git a/python/ovs/compat/sortedcontainers/sorteddict.py b/python/ovs/compat/sortedcontainers/sorteddict.py
> index 5d425fee6..910f26088 100644
> --- a/python/ovs/compat/sortedcontainers/sorteddict.py
> +++ b/python/ovs/compat/sortedcontainers/sorteddict.py
> @@ -1,342 +1,563 @@
> -"""Sorted dictionary implementation.
> +"""Sorted Dict
> +==============
> +
> +:doc:`Sorted Containers<index>` is an Apache2 licensed Python sorted
> +collections library, written in pure-Python, and fast as C-extensions. The
> +:doc:`introduction<introduction>` is the best way to get started.
> +
> +Sorted dict implementations:
> +
> +.. currentmodule:: sortedcontainers
> +
> +* :class:`SortedDict`
> +* :class:`SortedKeysView`
> +* :class:`SortedItemsView`
> +* :class:`SortedValuesView`
>  
>  """
>  
> -from collections import Set, Sequence
> -from collections import KeysView as AbstractKeysView
> -from collections import ValuesView as AbstractValuesView
> -from collections import ItemsView as AbstractItemsView
> -from sys import hexversion
> +import sys
> +import warnings
> +
> +from itertools import chain
>  
> -from .sortedlist import SortedList, recursive_repr, SortedListWithKey
> +from .sortedlist import SortedList, recursive_repr
>  from .sortedset import SortedSet
>  
> -NONE = object()
> +###############################################################################
> +# BEGIN Python 2/3 Shims
> +###############################################################################
>  
> +try:
> +    from collections.abc import (
> +        ItemsView, KeysView, Mapping, ValuesView, Sequence
> +    )
> +except ImportError:
> +    from collections import ItemsView, KeysView, Mapping, ValuesView, Sequence
>  
> -class _IlocWrapper(object):
> -    "Positional indexing support for sorted dictionary objects."
> -    # pylint: disable=protected-access, too-few-public-methods
> -    def __init__(self, _dict):
> -        self._dict = _dict
> -    def __len__(self):
> -        return len(self._dict)
> -    def __getitem__(self, index):
> -        """
> -        Very efficiently return the key at index *index* in iteration. Supports
> -        negative indices and slice notation. Raises IndexError on invalid
> -        *index*.
> -        """
> -        return self._dict._list[index]
> -    def __delitem__(self, index):
> -        """
> -        Remove the ``sdict[sdict.iloc[index]]`` from *sdict*. Supports negative
> -        indices and slice notation. Raises IndexError on invalid *index*.
> -        """
> -        _dict = self._dict
> -        _list = _dict._list
> -        _delitem = _dict._delitem
> -
> -        if isinstance(index, slice):
> -            keys = _list[index]
> -            del _list[index]
> -            for key in keys:
> -                _delitem(key)
> -        else:
> -            key = _list[index]
> -            del _list[index]
> -            _delitem(key)
> +###############################################################################
> +# END Python 2/3 Shims
> +###############################################################################
>  
>  
>  class SortedDict(dict):
> -    """SortedDict provides the same methods as a dict.  Additionally, SortedDict
> -    efficiently maintains its keys in sorted order. Consequently, the keys
> -    method will return the keys in sorted order, the popitem method will remove
> -    the item with the highest key, etc.
> +    """Sorted dict is a sorted mutable mapping.
> +
> +    Sorted dict keys are maintained in sorted order. The design of sorted dict
> +    is simple: sorted dict inherits from dict to store items and maintains a
> +    sorted list of keys.
> +
> +    Sorted dict keys must be hashable and comparable. The hash and total
> +    ordering of keys must not change while they are stored in the sorted dict.
> +
> +    Mutable mapping methods:
> +
> +    * :func:`SortedDict.__getitem__` (inherited from dict)
> +    * :func:`SortedDict.__setitem__`
> +    * :func:`SortedDict.__delitem__`
> +    * :func:`SortedDict.__iter__`
> +    * :func:`SortedDict.__len__` (inherited from dict)
> +
> +    Methods for adding items:
> +
> +    * :func:`SortedDict.setdefault`
> +    * :func:`SortedDict.update`
> +
> +    Methods for removing items:
> +
> +    * :func:`SortedDict.clear`
> +    * :func:`SortedDict.pop`
> +    * :func:`SortedDict.popitem`
> +
> +    Methods for looking up items:
> +
> +    * :func:`SortedDict.__contains__` (inherited from dict)
> +    * :func:`SortedDict.get` (inherited from dict)
> +    * :func:`SortedDict.peekitem`
> +
> +    Methods for views:
> +
> +    * :func:`SortedDict.keys`
> +    * :func:`SortedDict.items`
> +    * :func:`SortedDict.values`
> +
> +    Methods for miscellany:
> +
> +    * :func:`SortedDict.copy`
> +    * :func:`SortedDict.fromkeys`
> +    * :func:`SortedDict.__reversed__`
> +    * :func:`SortedDict.__eq__` (inherited from dict)
> +    * :func:`SortedDict.__ne__` (inherited from dict)
> +    * :func:`SortedDict.__repr__`
> +    * :func:`SortedDict._check`
> +
> +    Sorted list methods available (applies to keys):
> +
> +    * :func:`SortedList.bisect_left`
> +    * :func:`SortedList.bisect_right`
> +    * :func:`SortedList.count`
> +    * :func:`SortedList.index`
> +    * :func:`SortedList.irange`
> +    * :func:`SortedList.islice`
> +    * :func:`SortedList._reset`
> +
> +    Additional sorted list methods available, if key-function used:
> +
> +    * :func:`SortedKeyList.bisect_key_left`
> +    * :func:`SortedKeyList.bisect_key_right`
> +    * :func:`SortedKeyList.irange_key`
> +
> +    Sorted dicts may only be compared for equality and inequality.
>  
>      """
>      def __init__(self, *args, **kwargs):
> -        """SortedDict provides the same methods as a dict.  Additionally, SortedDict
> -        efficiently maintains its keys in sorted order. Consequently, the keys
> -        method will return the keys in sorted order, the popitem method will
> -        remove the item with the highest key, etc.
> -
> -        An optional *key* argument defines a callable that, like the `key`
> -        argument to Python's `sorted` function, extracts a comparison key from
> -        each dict key. If no function is specified, the default compares the
> -        dict keys directly. The `key` argument must be provided as a positional
> -        argument and must come before all other arguments.
> -
> -        An optional *iterable* argument provides an initial series of items to
> -        populate the SortedDict.  Each item in the series must itself contain
> -        two items.  The first is used as a key in the new dictionary, and the
> -        second as the key's value. If a given key is seen more than once, the
> -        last value associated with it is retained in the new dictionary.
> -
> -        If keyword arguments are given, the keywords themselves with their
> -        associated values are added as items to the dictionary. If a key is
> -        specified both in the positional argument and as a keyword argument, the
> -        value associated with the keyword is retained in the dictionary. For
> -        example, these all return a dictionary equal to ``{"one": 2, "two":
> -        3}``:
> -
> -        * ``SortedDict(one=2, two=3)``
> -        * ``SortedDict({'one': 2, 'two': 3})``
> -        * ``SortedDict(zip(('one', 'two'), (2, 3)))``
> -        * ``SortedDict([['two', 3], ['one', 2]])``
> -
> -        The first example only works for keys that are valid Python
> -        identifiers; the others work with any valid keys.
> +        """Initialize sorted dict instance.
> +
> +        Optional key-function argument defines a callable that, like the `key`
> +        argument to the built-in `sorted` function, extracts a comparison key
> +        from each dictionary key. If no function is specified, the default
> +        compares the dictionary keys directly. The key-function argument must
> +        be provided as a positional argument and must come before all other
> +        arguments.
> +
> +        Optional iterable argument provides an initial sequence of pairs to
> +        initialize the sorted dict. Each pair in the sequence defines the key
> +        and corresponding value. If a key is seen more than once, the last
> +        value associated with it is stored in the new sorted dict.
> +
> +        Optional mapping argument provides an initial mapping of items to
> +        initialize the sorted dict.
> +
> +        If keyword arguments are given, the keywords themselves, with their
> +        associated values, are added as items to the dictionary. If a key is
> +        specified both in the positional argument and as a keyword argument,
> +        the value associated with the keyword is stored in the
> +        sorted dict.
> +
> +        Sorted dict keys must be hashable, per the requirement for Python's
> +        dictionaries. Keys (or the result of the key-function) must also be
> +        comparable, per the requirement for sorted lists.
> +
> +        >>> d = {'alpha': 1, 'beta': 2}
> +        >>> SortedDict([('alpha', 1), ('beta', 2)]) == d
> +        True
> +        >>> SortedDict({'alpha': 1, 'beta': 2}) == d
> +        True
> +        >>> SortedDict(alpha=1, beta=2) == d
> +        True
>  
>          """
> -        # pylint: disable=super-init-not-called
>          if args and (args[0] is None or callable(args[0])):
> -            self._key = args[0]
> +            _key = self._key = args[0]
>              args = args[1:]
>          else:
> -            self._key = None
> +            _key = self._key = None
>  
> -        if self._key is None:
> -            self._list = SortedList()
> -        else:
> -            self._list = SortedListWithKey(key=self._key)
> +        self._list = SortedList(key=_key)
>  
> -        # Cache function pointers to dict methods.
> -
> -        _dict = super(SortedDict, self)
> -        self._dict = _dict
> -        self._clear = _dict.clear
> -        self._delitem = _dict.__delitem__
> -        self._iter = _dict.__iter__
> -        self._pop = _dict.pop
> -        self._setdefault = _dict.setdefault
> -        self._setitem = _dict.__setitem__
> -        self._dict_update = _dict.update
> -
> -        # Cache function pointers to SortedList methods.
> +        # Reaching through ``self._list`` repeatedly adds unnecessary overhead
> +        # so cache references to sorted list methods.
>  
>          _list = self._list
>          self._list_add = _list.add
> -        self.bisect_left = _list.bisect_left
> -        self.bisect = _list.bisect_right
> -        self.bisect_right = _list.bisect_right
>          self._list_clear = _list.clear
> -        self.index = _list.index
> +        self._list_iter = _list.__iter__
> +        self._list_reversed = _list.__reversed__
>          self._list_pop = _list.pop
>          self._list_remove = _list.remove
>          self._list_update = _list.update
> +
> +        # Expose some sorted list methods publicly.
> +
> +        self.bisect_left = _list.bisect_left
> +        self.bisect = _list.bisect_right
> +        self.bisect_right = _list.bisect_right
> +        self.index = _list.index
>          self.irange = _list.irange
>          self.islice = _list.islice
> -        self._reset = _list._reset  # pylint: disable=protected-access
> +        self._reset = _list._reset
>  
> -        if self._key is not None:
> +        if _key is not None:
>              self.bisect_key_left = _list.bisect_key_left
>              self.bisect_key_right = _list.bisect_key_right
>              self.bisect_key = _list.bisect_key
>              self.irange_key = _list.irange_key
>  
> -        self.iloc = _IlocWrapper(self)
> -
>          self._update(*args, **kwargs)
>  
> +
>      @property
>      def key(self):
> -        """Key function used to extract comparison key for sorting."""
> +        """Function used to extract comparison key from keys.
> +
> +        Sorted dict compares keys directly when the key function is none.
> +
> +        """
>          return self._key
>  
> +
> +    @property
> +    def iloc(self):
> +        """Cached reference of sorted keys view.
> +
> +        Deprecated in version 2 of Sorted Containers. Use
> +        :func:`SortedDict.keys` instead.
> +
> +        """
> +        # pylint: disable=attribute-defined-outside-init
> +        try:
> +            return self._iloc
> +        except AttributeError:
> +            warnings.warn(
> +                'sorted_dict.iloc is deprecated.'
> +                ' Use SortedDict.keys() instead.',
> +                DeprecationWarning,
> +                stacklevel=2,
> +            )
> +            _iloc = self._iloc = SortedKeysView(self)
> +            return _iloc
> +
> +
>      def clear(self):
> -        """Remove all elements from the dictionary."""
> -        self._clear()
> +
> +        """Remove all items from sorted dict.
> +
> +        Runtime complexity: `O(n)`
> +
> +        """
> +        dict.clear(self)
>          self._list_clear()
>  
> +
>      def __delitem__(self, key):
> +        """Remove item from sorted dict identified by `key`.
> +
> +        ``sd.__delitem__(key)`` <==> ``del sd[key]``
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
> +        >>> del sd['b']
> +        >>> sd
> +        SortedDict({'a': 1, 'c': 3})
> +        >>> del sd['z']
> +        Traceback (most recent call last):
> +          ...
> +        KeyError: 'z'
> +
> +        :param key: `key` for item lookup
> +        :raises KeyError: if key not found
> +
>          """
> -        Remove ``d[key]`` from *d*.  Raises a KeyError if *key* is not in the
> -        dictionary.
> -        """
> -        self._delitem(key)
> +        dict.__delitem__(self, key)
>          self._list_remove(key)
>  
> +
>      def __iter__(self):
> -        """
> -        Return an iterator over the sorted keys of the dictionary.
> +        """Return an iterator over the keys of the sorted dict.
> +
> +        ``sd.__iter__()`` <==> ``iter(sd)``
> +
> +        Iterating the sorted dict while adding or deleting items may raise a
> +        :exc:`RuntimeError` or fail to iterate over all keys.
>  
> -        Iterating the Mapping while adding or deleting keys may raise a
> -        `RuntimeError` or fail to iterate over all entries.
>          """
> -        return iter(self._list)
> +        return self._list_iter()
> +
>  
>      def __reversed__(self):
> -        """
> -        Return a reversed iterator over the sorted keys of the dictionary.
> +        """Return a reverse iterator over the keys of the sorted dict.
> +
> +        ``sd.__reversed__()`` <==> ``reversed(sd)``
> +
> +        Iterating the sorted dict while adding or deleting items may raise a
> +        :exc:`RuntimeError` or fail to iterate over all keys.
>  
> -        Iterating the Mapping while adding or deleting keys may raise a
> -        `RuntimeError` or fail to iterate over all entries.
>          """
> -        return reversed(self._list)
> +        return self._list_reversed()
> +
>  
>      def __setitem__(self, key, value):
> -        """Set `d[key]` to *value*."""
> +        """Store item in sorted dict with `key` and corresponding `value`.
> +
> +        ``sd.__setitem__(key, value)`` <==> ``sd[key] = value``
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> sd = SortedDict()
> +        >>> sd['c'] = 3
> +        >>> sd['a'] = 1
> +        >>> sd['b'] = 2
> +        >>> sd
> +        SortedDict({'a': 1, 'b': 2, 'c': 3})
> +
> +        :param key: key for item
> +        :param value: value for item
> +
> +        """
>          if key not in self:
>              self._list_add(key)
> -        self._setitem(key, value)
> +        dict.__setitem__(self, key, value)
> +
> +    _setitem = __setitem__
> +
> +
> +    def __or__(self, other):
> +        if not isinstance(other, Mapping):
> +            return NotImplemented
> +        items = chain(self.items(), other.items())
> +        return self.__class__(self._key, items)
> +
> +
> +    def __ror__(self, other):
> +        if not isinstance(other, Mapping):
> +            return NotImplemented
> +        items = chain(other.items(), self.items())
> +        return self.__class__(self._key, items)
> +
> +
> +    def __ior__(self, other):
> +        self._update(other)
> +        return self
> +
>  
>      def copy(self):
> -        """Return a shallow copy of the sorted dictionary."""
> -        return self.__class__(self._key, self._iteritems())
> +        """Return a shallow copy of the sorted dict.
> +
> +        Runtime complexity: `O(n)`
> +
> +        :return: new sorted dict
> +
> +        """
> +        return self.__class__(self._key, self.items())
>  
>      __copy__ = copy
>  
> +
>      @classmethod
> -    def fromkeys(cls, seq, value=None):
> -        """
> -        Create a new dictionary with keys from *seq* and values set to *value*.
> -        """
> -        return cls((key, value) for key in seq)
> -
> -    if hexversion < 0x03000000:
> -        def items(self):
> -            """
> -            Return a list of the dictionary's items (``(key, value)`` pairs).
> -            """
> -            return list(self._iteritems())
> -    else:
> -        def items(self):
> -            """
> -            Return a new ItemsView of the dictionary's items.  In addition to
> -            the methods provided by the built-in `view` the ItemsView is
> -            indexable (e.g. ``d.items()[5]``).
> -            """
> -            return ItemsView(self)
> -
> -    def iteritems(self):
> -        """
> -        Return an iterator over the items (``(key, value)`` pairs).
> +    def fromkeys(cls, iterable, value=None):
> +        """Return a new sorted dict initailized from `iterable` and `value`.
>  
> -        Iterating the Mapping while adding or deleting keys may raise a
> -        `RuntimeError` or fail to iterate over all entries.
> -        """
> -        return iter((key, self[key]) for key in self._list)
> +        Items in the sorted dict have keys from `iterable` and values equal to
> +        `value`.
>  
> -    _iteritems = iteritems
> +        Runtime complexity: `O(n*log(n))`
>  
> -    if hexversion < 0x03000000:
> -        def keys(self):
> -            """Return a SortedSet of the dictionary's keys."""
> -            return SortedSet(self._list, key=self._key)
> -    else:
> -        def keys(self):
> -            """
> -            Return a new KeysView of the dictionary's keys.  In addition to the
> -            methods provided by the built-in `view` the KeysView is indexable
> -            (e.g. ``d.keys()[5]``).
> -            """
> -            return KeysView(self)
> -
> -    def iterkeys(self):
> -        """
> -        Return an iterator over the sorted keys of the Mapping.
> +        :return: new sorted dict
>  
> -        Iterating the Mapping while adding or deleting keys may raise a
> -        `RuntimeError` or fail to iterate over all entries.
>          """
> -        return iter(self._list)
> +        return cls((key, value) for key in iterable)
> +
> +
> +    def keys(self):
> +        """Return new sorted keys view of the sorted dict's keys.
> +
> +        See :class:`SortedKeysView` for details.
> +
> +        :return: new sorted keys view
>  
> -    if hexversion < 0x03000000:
> -        def values(self):
> -            """Return a list of the dictionary's values."""
> -            return list(self._itervalues())
> -    else:
> -        def values(self):
> -            """
> -            Return a new :class:`ValuesView` of the dictionary's values.
> -            In addition to the methods provided by the built-in `view` the
> -            ValuesView is indexable (e.g., ``d.values()[5]``).
> -            """
> -            return ValuesView(self)
> -
> -    def itervalues(self):
>          """
> -        Return an iterator over the values of the Mapping.
> +        return SortedKeysView(self)
> +
> +
> +    def items(self):
> +        """Return new sorted items view of the sorted dict's items.
> +
> +        See :class:`SortedItemsView` for details.
> +
> +        :return: new sorted items view
>  
> -        Iterating the Mapping while adding or deleting keys may raise a
> -        `RuntimeError` or fail to iterate over all entries.
>          """
> -        return iter(self[key] for key in self._list)
> +        return SortedItemsView(self)
> +
>  
> -    _itervalues = itervalues
> +    def values(self):
> +        """Return new sorted values view of the sorted dict's values.
> +
> +        See :class:`SortedValuesView` for details.
> +
> +        :return: new sorted values view
>  
> -    def pop(self, key, default=NONE):
>          """
> -        If *key* is in the dictionary, remove it and return its value,
> -        else return *default*. If *default* is not given and *key* is not in
> -        the dictionary, a KeyError is raised.
> +        return SortedValuesView(self)
> +
> +
> +    if sys.hexversion < 0x03000000:
> +        def __make_raise_attributeerror(original, alternate):
> +            # pylint: disable=no-self-argument
> +            message = (
> +                'SortedDict.{original}() is not implemented.'
> +                ' Use SortedDict.{alternate}() instead.'
> +            ).format(original=original, alternate=alternate)
> +            def method(self):
> +                # pylint: disable=missing-docstring,unused-argument
> +                raise AttributeError(message)
> +            method.__name__ = original  # pylint: disable=non-str-assignment-to-dunder-name
> +            method.__doc__ = message
> +            return property(method)
> +
> +        iteritems = __make_raise_attributeerror('iteritems', 'items')
> +        iterkeys = __make_raise_attributeerror('iterkeys', 'keys')
> +        itervalues = __make_raise_attributeerror('itervalues', 'values')
> +        viewitems = __make_raise_attributeerror('viewitems', 'items')
> +        viewkeys = __make_raise_attributeerror('viewkeys', 'keys')
> +        viewvalues = __make_raise_attributeerror('viewvalues', 'values')
> +
> +
> +    class _NotGiven(object):
> +        # pylint: disable=too-few-public-methods
> +        def __repr__(self):
> +            return '<not-given>'
> +
> +    __not_given = _NotGiven()
> +
> +    def pop(self, key, default=__not_given):
> +        """Remove and return value for item identified by `key`.
> +
> +        If the `key` is not found then return `default` if given. If `default`
> +        is not given then raise :exc:`KeyError`.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
> +        >>> sd.pop('c')
> +        3
> +        >>> sd.pop('z', 26)
> +        26
> +        >>> sd.pop('y')
> +        Traceback (most recent call last):
> +          ...
> +        KeyError: 'y'
> +
> +        :param key: `key` for item
> +        :param default: `default` value if key not found (optional)
> +        :return: value for item
> +        :raises KeyError: if `key` not found and `default` not given
> +
>          """
>          if key in self:
>              self._list_remove(key)
> -            return self._pop(key)
> +            return dict.pop(self, key)
>          else:
> -            if default is NONE:
> +            if default is self.__not_given:
>                  raise KeyError(key)
> -            else:
> -                return default
> +            return default
>  
> -    def popitem(self, last=True):
> -        """
> -        Remove and return a ``(key, value)`` pair from the dictionary. If
> -        last=True (default) then remove the *greatest* `key` from the
> -        diciontary. Else, remove the *least* key from the dictionary.
>  
> -        If the dictionary is empty, calling `popitem` raises a
> -        KeyError`.
> +    def popitem(self, index=-1):
> +        """Remove and return ``(key, value)`` pair at `index` from sorted dict.
> +
> +        Optional argument `index` defaults to -1, the last item in the sorted
> +        dict. Specify ``index=0`` for the first item in the sorted dict.
> +
> +        If the sorted dict is empty, raises :exc:`KeyError`.
> +
> +        If the `index` is out of range, raises :exc:`IndexError`.
> +
> +        Runtime complexity: `O(log(n))`
> +
> +        >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
> +        >>> sd.popitem()
> +        ('c', 3)
> +        >>> sd.popitem(0)
> +        ('a', 1)
> +        >>> sd.popitem(100)
> +        Traceback (most recent call last):
> +          ...
> +        IndexError: list index out of range
> +
> +        :param int index: `index` of item (default -1)
> +        :return: key and value pair
> +        :raises KeyError: if sorted dict is empty
> +        :raises IndexError: if `index` out of range
> +
>          """
>          if not self:
>              raise KeyError('popitem(): dictionary is empty')
>  
> -        key = self._list_pop(-1 if last else 0)
> -        value = self._pop(key)
> -
> +        key = self._list_pop(index)
> +        value = dict.pop(self, key)
>          return (key, value)
>  
> +
>      def peekitem(self, index=-1):
> -        """Return (key, value) item pair at index.
> +        """Return ``(key, value)`` pair at `index` in sorted dict.
> +
> +        Optional argument `index` defaults to -1, the last item in the sorted
> +        dict. Specify ``index=0`` for the first item in the sorted dict.
>  
> -        Unlike ``popitem``, the sorted dictionary is not modified. Index
> -        defaults to -1, the last/greatest key in the dictionary. Specify
> -        ``index=0`` to lookup the first/least key in the dictiony.
> +        Unlike :func:`SortedDict.popitem`, the sorted dict is not modified.
>  
> -        If index is out of range, raise IndexError.
> +        If the `index` is out of range, raises :exc:`IndexError`.
> +
> +        Runtime complexity: `O(log(n))`
> +
> +        >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
> +        >>> sd.peekitem()
> +        ('c', 3)
> +        >>> sd.peekitem(0)
> +        ('a', 1)
> +        >>> sd.peekitem(100)
> +        Traceback (most recent call last):
> +          ...
> +        IndexError: list index out of range
> +
> +        :param int index: index of item (default -1)
> +        :return: key and value pair
> +        :raises IndexError: if `index` out of range
>  
>          """
>          key = self._list[index]
>          return key, self[key]
>  
> +
>      def setdefault(self, key, default=None):
> -        """
> -        If *key* is in the dictionary, return its value.  If not, insert *key*
> -        with a value of *default* and return *default*.  *default* defaults to
> -        ``None``.
> +        """Return value for item identified by `key` in sorted dict.
> +
> +        If `key` is in the sorted dict then return its value. If `key` is not
> +        in the sorted dict then insert `key` with value `default` and return
> +        `default`.
> +
> +        Optional argument `default` defaults to none.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> sd = SortedDict()
> +        >>> sd.setdefault('a', 1)
> +        1
> +        >>> sd.setdefault('a', 10)
> +        1
> +        >>> sd
> +        SortedDict({'a': 1})
> +
> +        :param key: key for item
> +        :param default: value for item (default None)
> +        :return: value for item identified by `key`
> +
>          """
>          if key in self:
>              return self[key]
> -
> -        self._setitem(key, default)
> +        dict.__setitem__(self, key, default)
>          self._list_add(key)
>          return default
>  
> +
>      def update(self, *args, **kwargs):
> -        """
> -        Update the dictionary with the key/value pairs from *other*, overwriting
> -        existing keys.
> +        """Update sorted dict with items from `args` and `kwargs`.
> +
> +        Overwrites existing items.
> +
> +        Optional arguments `args` and `kwargs` may be a mapping, an iterable of
> +        pairs or keyword arguments. See :func:`SortedDict.__init__` for
> +        details.
> +
> +        :param args: mapping or iterable of pairs
> +        :param kwargs: keyword arguments mapping
>  
> -        *update* accepts either another dictionary object or an iterable of
> -        key/value pairs (as a tuple or other iterable of length two).  If
> -        keyword arguments are specified, the dictionary is then updated with
> -        those key/value pairs: ``d.update(red=1, blue=2)``.
>          """
>          if not self:
> -            self._dict_update(*args, **kwargs)
> -            self._list_update(self._iter())
> +            dict.update(self, *args, **kwargs)
> +            self._list_update(dict.__iter__(self))
>              return
>  
>          if not kwargs and len(args) == 1 and isinstance(args[0], dict):
> @@ -345,397 +566,247 @@ class SortedDict(dict):
>              pairs = dict(*args, **kwargs)
>  
>          if (10 * len(pairs)) > len(self):
> -            self._dict_update(pairs)
> +            dict.update(self, pairs)
>              self._list_clear()
> -            self._list_update(self._iter())
> +            self._list_update(dict.__iter__(self))
>          else:
>              for key in pairs:
> -                self[key] = pairs[key]
> +                self._setitem(key, pairs[key])
>  
>      _update = update
>  
> -    if hexversion >= 0x02070000:
> -        def viewkeys(self):
> -            "Return ``KeysView`` of dictionary keys."
> -            return KeysView(self)
>  
> -        def viewvalues(self):
> -            "Return ``ValuesView`` of dictionary values."
> -            return ValuesView(self)
> +    def __reduce__(self):
> +        """Support for pickle.
>  
> -        def viewitems(self):
> -            "Return ``ItemsView`` of dictionary (key, value) item pairs."
> -            return ItemsView(self)
> +        The tricks played with caching references in
> +        :func:`SortedDict.__init__` confuse pickle so customize the reducer.
>  
> -    def __reduce__(self):
> -        return (self.__class__, (self._key, list(self._iteritems())))
> +        """
> +        items = dict.copy(self)
> +        return (type(self), (self._key, items))
>  
> -    @recursive_repr
> +
> +    @recursive_repr()
>      def __repr__(self):
> +        """Return string representation of sorted dict.
> +
> +        ``sd.__repr__()`` <==> ``repr(sd)``
> +
> +        :return: string representation
> +
> +        """
>          _key = self._key
> -        name = type(self).__name__
> -        key = '' if _key is None else '{0!r}, '.format(_key)
> -        func = '{0!r}: {1!r}'.format
> -        items = ', '.join(func(key, self[key]) for key in self._list)
> -        return '{0}({1}{{{2}}})'.format(name, key, items)
> +        type_name = type(self).__name__
> +        key_arg = '' if _key is None else '{0!r}, '.format(_key)
> +        item_format = '{0!r}: {1!r}'.format
> +        items = ', '.join(item_format(key, self[key]) for key in self._list)
> +        return '{0}({1}{{{2}}})'.format(type_name, key_arg, items)
> +
>  
>      def _check(self):
> -        # pylint: disable=protected-access
> -        self._list._check()
> -        assert len(self) == len(self._list)
> -        assert all(key in self for key in self._list)
> +        """Check invariants of sorted dict.
>  
> +        Runtime complexity: `O(n)`
>  
> -class KeysView(AbstractKeysView, Set, Sequence):
> -    """
> -    A KeysView object is a dynamic view of the dictionary's keys, which
> -    means that when the dictionary's keys change, the view reflects
> -    those changes.
> +        """
> +        _list = self._list
> +        _list._check()
> +        assert len(self) == len(_list)
> +        assert all(key in self for key in _list)
> +
> +
> +def _view_delitem(self, index):
> +    """Remove item at `index` from sorted dict.
> +
> +    ``view.__delitem__(index)`` <==> ``del view[index]``
> +
> +    Supports slicing.
> +
> +    Runtime complexity: `O(log(n))` -- approximate.
> +
> +    >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
> +    >>> view = sd.keys()
> +    >>> del view[0]
> +    >>> sd
> +    SortedDict({'b': 2, 'c': 3})
> +    >>> del view[-1]
> +    >>> sd
> +    SortedDict({'b': 2})
> +    >>> del view[:]
> +    >>> sd
> +    SortedDict({})
> +
> +    :param index: integer or slice for indexing
> +    :raises IndexError: if index out of range
>  
> -    The KeysView class implements the Set and Sequence Abstract Base Classes.
>      """
> -    # pylint: disable=too-many-ancestors
> -    if hexversion < 0x03000000:
> -        def __init__(self, sorted_dict):
> -            """
> -            Initialize a KeysView from a SortedDict container as *sorted_dict*.
> -            """
> -            # pylint: disable=super-init-not-called, protected-access
> -            self._list = sorted_dict._list
> -            self._view = sorted_dict._dict.viewkeys()
> +    _mapping = self._mapping
> +    _list = _mapping._list
> +    dict_delitem = dict.__delitem__
> +    if isinstance(index, slice):
> +        keys = _list[index]
> +        del _list[index]
> +        for key in keys:
> +            dict_delitem(_mapping, key)
>      else:
> -        def __init__(self, sorted_dict):
> -            """
> -            Initialize a KeysView from a SortedDict container as *sorted_dict*.
> -            """
> -            # pylint: disable=super-init-not-called, protected-access
> -            self._list = sorted_dict._list
> -            self._view = sorted_dict._dict.keys()
> -    def __len__(self):
> -        """Return the number of entries in the dictionary."""
> -        return len(self._view)
> -    def __contains__(self, key):
> -        """
> -        Return True if and only if *key* is one of the underlying dictionary's
> -        keys.
> -        """
> -        return key in self._view
> -    def __iter__(self):
> -        """
> -        Return an iterable over the keys in the dictionary. Keys are iterated
> -        over in their sorted order.
> +        key = _list.pop(index)
> +        dict_delitem(_mapping, key)
> +
> +
> +class SortedKeysView(KeysView, Sequence):
> +    """Sorted keys view is a dynamic view of the sorted dict's keys.
> +
> +    When the sorted dict's keys change, the view reflects those changes.
> +
> +    The keys view implements the set and sequence abstract base classes.
> +
> +    """
> +    __slots__ = ()
> +
> +
> +    @classmethod
> +    def _from_iterable(cls, it):
> +        return SortedSet(it)
> +
>  
> -        Iterating views while adding or deleting entries in the dictionary may
> -        raise a `RuntimeError` or fail to iterate over all entries.
> -        """
> -        return iter(self._list)
>      def __getitem__(self, index):
> -        """Return the key at position *index*."""
> -        return self._list[index]
> -    def __reversed__(self):
> -        """
> -        Return a reversed iterable over the keys in the dictionary. Keys are
> -        iterated over in their reverse sort order.
> +        """Lookup key at `index` in sorted keys views.
> +
> +        ``skv.__getitem__(index)`` <==> ``skv[index]``
> +
> +        Supports slicing.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
> +        >>> skv = sd.keys()
> +        >>> skv[0]
> +        'a'
> +        >>> skv[-1]
> +        'c'
> +        >>> skv[:]
> +        ['a', 'b', 'c']
> +        >>> skv[100]
> +        Traceback (most recent call last):
> +          ...
> +        IndexError: list index out of range
> +
> +        :param index: integer or slice for indexing
> +        :return: key or list of keys
> +        :raises IndexError: if index out of range
>  
> -        Iterating views while adding or deleting entries in the dictionary may
> -        raise a RuntimeError or fail to iterate over all entries.
> -        """
> -        return reversed(self._list)
> -    def index(self, value, start=None, stop=None):
> -        """
> -        Return the smallest *k* such that `keysview[k] == value` and `start <= k
> -        < end`.  Raises `KeyError` if *value* is not present.  *stop* defaults
> -        to the end of the set.  *start* defaults to the beginning.  Negative
> -        indexes are supported, as for slice indices.
>          """
> -        # pylint: disable=arguments-differ
> -        return self._list.index(value, start, stop)
> -    def count(self, value):
> -        """Return the number of occurrences of *value* in the set."""
> -        return 1 if value in self._view else 0
> -    def __eq__(self, that):
> -        """Test set-like equality with *that*."""
> -        return self._view == that
> -    def __ne__(self, that):
> -        """Test set-like inequality with *that*."""
> -        return self._view != that
> -    def __lt__(self, that):
> -        """Test whether self is a proper subset of *that*."""
> -        return self._view < that
> -    def __gt__(self, that):
> -        """Test whether self is a proper superset of *that*."""
> -        return self._view > that
> -    def __le__(self, that):
> -        """Test whether self is contained within *that*."""
> -        return self._view <= that
> -    def __ge__(self, that):
> -        """Test whether *that* is contained within self."""
> -        return self._view >= that
> -    def __and__(self, that):
> -        """Return a SortedSet of the intersection of self and *that*."""
> -        return SortedSet(self._view & that)
> -    def __or__(self, that):
> -        """Return a SortedSet of the union of self and *that*."""
> -        return SortedSet(self._view | that)
> -    def __sub__(self, that):
> -        """Return a SortedSet of the difference of self and *that*."""
> -        return SortedSet(self._view - that)
> -    def __xor__(self, that):
> -        """Return a SortedSet of the symmetric difference of self and *that*."""
> -        return SortedSet(self._view ^ that)
> -    if hexversion < 0x03000000:
> -        def isdisjoint(self, that):
> -            """Return True if and only if *that* is disjoint with self."""
> -            # pylint: disable=arguments-differ
> -            return not any(key in self._list for key in that)
> -    else:
> -        def isdisjoint(self, that):
> -            """Return True if and only if *that* is disjoint with self."""
> -            # pylint: disable=arguments-differ
> -            return self._view.isdisjoint(that)
> -    @recursive_repr
> -    def __repr__(self):
> -        return 'SortedDict_keys({0!r})'.format(list(self))
> +        return self._mapping._list[index]
>  
>  
> -class ValuesView(AbstractValuesView, Sequence):
> -    """
> -    A ValuesView object is a dynamic view of the dictionary's values, which
> -    means that when the dictionary's values change, the view reflects those
> -    changes.
> +    __delitem__ = _view_delitem
> +
> +
> +class SortedItemsView(ItemsView, Sequence):
> +    """Sorted items view is a dynamic view of the sorted dict's items.
> +
> +    When the sorted dict's items change, the view reflects those changes.
> +
> +    The items view implements the set and sequence abstract base classes.
>  
> -    The ValuesView class implements the Sequence Abstract Base Class.
>      """
> -    # pylint: disable=too-many-ancestors
> -    if hexversion < 0x03000000:
> -        def __init__(self, sorted_dict):
> -            """
> -            Initialize a ValuesView from a SortedDict container as
> -            *sorted_dict*.
> -            """
> -            # pylint: disable=super-init-not-called, protected-access
> -            self._dict = sorted_dict
> -            self._list = sorted_dict._list
> -            self._view = sorted_dict._dict.viewvalues()
> -    else:
> -        def __init__(self, sorted_dict):
> -            """
> -            Initialize a ValuesView from a SortedDict container as
> -            *sorted_dict*.
> -            """
> -            # pylint: disable=super-init-not-called, protected-access
> -            self._dict = sorted_dict
> -            self._list = sorted_dict._list
> -            self._view = sorted_dict._dict.values()
> -    def __len__(self):
> -        """Return the number of entries in the dictionary."""
> -        return len(self._dict)
> -    def __contains__(self, value):
> -        """
> -        Return True if and only if *value* is in the underlying Mapping's
> -        values.
> -        """
> -        return value in self._view
> -    def __iter__(self):
> -        """
> -        Return an iterator over the values in the dictionary.  Values are
> -        iterated over in sorted order of the keys.
> +    __slots__ = ()
> +
> +
> +    @classmethod
> +    def _from_iterable(cls, it):
> +        return SortedSet(it)
> +
>  
> -        Iterating views while adding or deleting entries in the dictionary may
> -        raise a `RuntimeError` or fail to iterate over all entries.
> -        """
> -        _dict = self._dict
> -        return iter(_dict[key] for key in self._list)
>      def __getitem__(self, index):
> -        """
> -        Efficiently return value at *index* in iteration.
> +        """Lookup item at `index` in sorted items view.
> +
> +        ``siv.__getitem__(index)`` <==> ``siv[index]``
> +
> +        Supports slicing.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
> +        >>> siv = sd.items()
> +        >>> siv[0]
> +        ('a', 1)
> +        >>> siv[-1]
> +        ('c', 3)
> +        >>> siv[:]
> +        [('a', 1), ('b', 2), ('c', 3)]
> +        >>> siv[100]
> +        Traceback (most recent call last):
> +          ...
> +        IndexError: list index out of range
> +
> +        :param index: integer or slice for indexing
> +        :return: item or list of items
> +        :raises IndexError: if index out of range
>  
> -        Supports slice notation and negative indexes.
>          """
> -        _dict, _list = self._dict, self._list
> +        _mapping = self._mapping
> +        _mapping_list = _mapping._list
> +
>          if isinstance(index, slice):
> -            return [_dict[key] for key in _list[index]]
> -        return _dict[_list[index]]
> -    def __reversed__(self):
> -        """
> -        Return a reverse iterator over the values in the dictionary.  Values are
> -        iterated over in reverse sort order of the keys.
> +            keys = _mapping_list[index]
> +            return [(key, _mapping[key]) for key in keys]
>  
> -        Iterating views while adding or deleting entries in the dictionary may
> -        raise a `RuntimeError` or fail to iterate over all entries.
> -        """
> -        _dict = self._dict
> -        return iter(_dict[key] for key in reversed(self._list))
> -    def index(self, value):
> -        """
> -        Return index of *value* in self.
> +        key = _mapping_list[index]
> +        return key, _mapping[key]
>  
> -        Raises ValueError if *value* is not found.
> -        """
> -        # pylint: disable=arguments-differ
> -        for idx, val in enumerate(self):
> -            if value == val:
> -                return idx
> -        raise ValueError('{0!r} is not in dict'.format(value))
> -    if hexversion < 0x03000000:
> -        def count(self, value):
> -            """Return the number of occurrences of *value* in self."""
> -            return sum(1 for val in self._dict.itervalues() if val == value)
> -    else:
> -        def count(self, value):
> -            """Return the number of occurrences of *value* in self."""
> -            return sum(1 for val in self._dict.values() if val == value)
> -    def __lt__(self, that):
> -        raise TypeError
> -    def __gt__(self, that):
> -        raise TypeError
> -    def __le__(self, that):
> -        raise TypeError
> -    def __ge__(self, that):
> -        raise TypeError
> -    def __and__(self, that):
> -        raise TypeError
> -    def __or__(self, that):
> -        raise TypeError
> -    def __sub__(self, that):
> -        raise TypeError
> -    def __xor__(self, that):
> -        raise TypeError
> -    @recursive_repr
> -    def __repr__(self):
> -        return 'SortedDict_values({0!r})'.format(list(self))
>  
> +    __delitem__ = _view_delitem
>  
> -class ItemsView(AbstractItemsView, Set, Sequence):
> -    """
> -    An ItemsView object is a dynamic view of the dictionary's ``(key,
> -    value)`` pairs, which means that when the dictionary changes, the
> -    view reflects those changes.
>  
> -    The ItemsView class implements the Set and Sequence Abstract Base Classes.
> -    However, the set-like operations (``&``, ``|``, ``-``, ``^``) will only
> -    operate correctly if all of the dictionary's values are hashable.
> +class SortedValuesView(ValuesView, Sequence):
> +    """Sorted values view is a dynamic view of the sorted dict's values.
> +
> +    When the sorted dict's values change, the view reflects those changes.
> +
> +    The values view implements the sequence abstract base class.
> +
>      """
> -    # pylint: disable=too-many-ancestors
> -    if hexversion < 0x03000000:
> -        def __init__(self, sorted_dict):
> -            """
> -            Initialize an ItemsView from a SortedDict container as
> -            *sorted_dict*.
> -            """
> -            # pylint: disable=super-init-not-called, protected-access
> -            self._dict = sorted_dict
> -            self._list = sorted_dict._list
> -            self._view = sorted_dict._dict.viewitems()
> -    else:
> -        def __init__(self, sorted_dict):
> -            """
> -            Initialize an ItemsView from a SortedDict container as
> -            *sorted_dict*.
> -            """
> -            # pylint: disable=super-init-not-called, protected-access
> -            self._dict = sorted_dict
> -            self._list = sorted_dict._list
> -            self._view = sorted_dict._dict.items()
> -    def __len__(self):
> -        """Return the number of entries in the dictionary."""
> -        return len(self._view)
> -    def __contains__(self, key):
> -        """
> -        Return True if and only if *key* is one of the underlying dictionary's
> -        items.
> -        """
> -        return key in self._view
> -    def __iter__(self):
> -        """
> -        Return an iterable over the items in the dictionary. Items are iterated
> -        over in their sorted order.
> +    __slots__ = ()
> +
>  
> -        Iterating views while adding or deleting entries in the dictionary may
> -        raise a `RuntimeError` or fail to iterate over all entries.
> -        """
> -        _dict = self._dict
> -        return iter((key, _dict[key]) for key in self._list)
>      def __getitem__(self, index):
> -        """Return the item as position *index*."""
> -        _dict, _list = self._dict, self._list
> -        if isinstance(index, slice):
> -            return [(key, _dict[key]) for key in _list[index]]
> -        key = _list[index]
> -        return (key, _dict[key])
> -    def __reversed__(self):
> -        """
> -        Return a reversed iterable over the items in the dictionary. Items are
> -        iterated over in their reverse sort order.
> +        """Lookup value at `index` in sorted values view.
> +
> +        ``siv.__getitem__(index)`` <==> ``siv[index]``
> +
> +        Supports slicing.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
> +        >>> svv = sd.values()
> +        >>> svv[0]
> +        1
> +        >>> svv[-1]
> +        3
> +        >>> svv[:]
> +        [1, 2, 3]
> +        >>> svv[100]
> +        Traceback (most recent call last):
> +          ...
> +        IndexError: list index out of range
> +
> +        :param index: integer or slice for indexing
> +        :return: value or list of values
> +        :raises IndexError: if index out of range
>  
> -        Iterating views while adding or deleting entries in the dictionary may
> -        raise a RuntimeError or fail to iterate over all entries.
> -        """
> -        _dict = self._dict
> -        return iter((key, _dict[key]) for key in reversed(self._list))
> -    def index(self, key, start=None, stop=None):
> -        """
> -        Return the smallest *k* such that `itemssview[k] == key` and `start <= k
> -        < end`.  Raises `KeyError` if *key* is not present.  *stop* defaults
> -        to the end of the set.  *start* defaults to the beginning.  Negative
> -        indexes are supported, as for slice indices.
>          """
> -        # pylint: disable=arguments-differ
> -        temp, value = key
> -        pos = self._list.index(temp, start, stop)
> -        if value == self._dict[temp]:
> -            return pos
> -        else:
> -            raise ValueError('{0!r} is not in dict'.format(key))
> -    def count(self, item):
> -        """Return the number of occurrences of *item* in the set."""
> -        # pylint: disable=arguments-differ
> -        key, value = item
> -        return 1 if key in self._dict and self._dict[key] == value else 0
> -    def __eq__(self, that):
> -        """Test set-like equality with *that*."""
> -        return self._view == that
> -    def __ne__(self, that):
> -        """Test set-like inequality with *that*."""
> -        return self._view != that
> -    def __lt__(self, that):
> -        """Test whether self is a proper subset of *that*."""
> -        return self._view < that
> -    def __gt__(self, that):
> -        """Test whether self is a proper superset of *that*."""
> -        return self._view > that
> -    def __le__(self, that):
> -        """Test whether self is contained within *that*."""
> -        return self._view <= that
> -    def __ge__(self, that):
> -        """Test whether *that* is contained within self."""
> -        return self._view >= that
> -    def __and__(self, that):
> -        """Return a SortedSet of the intersection of self and *that*."""
> -        return SortedSet(self._view & that)
> -    def __or__(self, that):
> -        """Return a SortedSet of the union of self and *that*."""
> -        return SortedSet(self._view | that)
> -    def __sub__(self, that):
> -        """Return a SortedSet of the difference of self and *that*."""
> -        return SortedSet(self._view - that)
> -    def __xor__(self, that):
> -        """Return a SortedSet of the symmetric difference of self and *that*."""
> -        return SortedSet(self._view ^ that)
> -    if hexversion < 0x03000000:
> -        def isdisjoint(self, that):
> -            """Return True if and only if *that* is disjoint with self."""
> -            # pylint: disable=arguments-differ
> -            _dict = self._dict
> -            for key, value in that:
> -                if key in _dict and _dict[key] == value:
> -                    return False
> -            return True
> -    else:
> -        def isdisjoint(self, that):
> -            """Return True if and only if *that* is disjoint with self."""
> -            # pylint: disable=arguments-differ
> -            return self._view.isdisjoint(that)
> -    @recursive_repr
> -    def __repr__(self):
> -        return 'SortedDict_items({0!r})'.format(list(self))
> +        _mapping = self._mapping
> +        _mapping_list = _mapping._list
> +
> +        if isinstance(index, slice):
> +            keys = _mapping_list[index]
> +            return [_mapping[key] for key in keys]
> +
> +        key = _mapping_list[index]
> +        return _mapping[key]
> +
> +
> +    __delitem__ = _view_delitem
> diff --git a/python/ovs/compat/sortedcontainers/sortedlist.py b/python/ovs/compat/sortedcontainers/sortedlist.py
> index ba5556692..5f283fbb0 100644
> --- a/python/ovs/compat/sortedcontainers/sortedlist.py
> +++ b/python/ovs/compat/sortedcontainers/sortedlist.py
> @@ -1,20 +1,44 @@
> -"""Sorted list implementation.
> +"""Sorted List
> +==============
> +
> +:doc:`Sorted Containers<index>` is an Apache2 licensed Python sorted
> +collections library, written in pure-Python, and fast as C-extensions. The
> +:doc:`introduction<introduction>` is the best way to get started.
> +
> +Sorted list implementations:
> +
> +.. currentmodule:: sortedcontainers
> +
> +* :class:`SortedList`
> +* :class:`SortedKeyList`
>  
>  """
> -# pylint: disable=redefined-builtin, ungrouped-imports
> +# pylint: disable=too-many-lines
> +
> +import sys
> +import traceback
>  
>  from bisect import bisect_left, bisect_right, insort
> -from collections import Sequence, MutableSequence
> -from functools import wraps
>  from itertools import chain, repeat, starmap
> -from math import log as log_e
> -import operator as op
> -from operator import iadd, add
> +from math import log
> +from operator import add, eq, ne, gt, ge, lt, le, iadd
> +from textwrap import dedent
> +
> +###############################################################################
> +# BEGIN Python 2/3 Shims
> +###############################################################################
> +
> +try:
> +    from collections.abc import Sequence, MutableSequence
> +except ImportError:
> +    from collections import Sequence, MutableSequence
> +
> +from functools import wraps
>  from sys import hexversion
>  
>  if hexversion < 0x03000000:
> -    from itertools import izip as zip  # pylint: disable=no-name-in-module
> -    from itertools import imap as map  # pylint: disable=no-name-in-module
> +    from itertools import imap as map  # pylint: disable=redefined-builtin
> +    from itertools import izip as zip  # pylint: disable=redefined-builtin
>      try:
>          from thread import get_ident
>      except ImportError:
> @@ -24,145 +48,258 @@ else:
>      try:
>          from _thread import get_ident
>      except ImportError:
> -        from _dummy_thread import get_ident # pylint: disable=import-error
> +        from _dummy_thread import get_ident
>  
> -LOAD = 1000
>  
> -def recursive_repr(func):
> -    """Decorator to prevent infinite repr recursion."""
> -    repr_running = set()
> +def recursive_repr(fillvalue='...'):
> +    "Decorator to make a repr function return fillvalue for a recursive call."
> +    # pylint: disable=missing-docstring
> +    # Copied from reprlib in Python 3
> +    # https://hg.python.org/cpython/file/3.6/Lib/reprlib.py
>  
> -    @wraps(func)
> -    def wrapper(self):
> -        "Return ellipsis on recursive re-entry to function."
> -        key = id(self), get_ident()
> +    def decorating_function(user_function):
> +        repr_running = set()
>  
> -        if key in repr_running:
> -            return '...'
> +        @wraps(user_function)
> +        def wrapper(self):
> +            key = id(self), get_ident()
> +            if key in repr_running:
> +                return fillvalue
> +            repr_running.add(key)
> +            try:
> +                result = user_function(self)
> +            finally:
> +                repr_running.discard(key)
> +            return result
>  
> -        repr_running.add(key)
> +        return wrapper
>  
> -        try:
> -            return func(self)
> -        finally:
> -            repr_running.discard(key)
> +    return decorating_function
> +
> +###############################################################################
> +# END Python 2/3 Shims
> +###############################################################################
>  
> -    return wrapper
>  
>  class SortedList(MutableSequence):
> +    """Sorted list is a sorted mutable sequence.
> +
> +    Sorted list values are maintained in sorted order.
> +
> +    Sorted list values must be comparable. The total ordering of values must
> +    not change while they are stored in the sorted list.
> +
> +    Methods for adding values:
> +
> +    * :func:`SortedList.add`
> +    * :func:`SortedList.update`
> +    * :func:`SortedList.__add__`
> +    * :func:`SortedList.__iadd__`
> +    * :func:`SortedList.__mul__`
> +    * :func:`SortedList.__imul__`
> +
> +    Methods for removing values:
> +
> +    * :func:`SortedList.clear`
> +    * :func:`SortedList.discard`
> +    * :func:`SortedList.remove`
> +    * :func:`SortedList.pop`
> +    * :func:`SortedList.__delitem__`
> +
> +    Methods for looking up values:
> +
> +    * :func:`SortedList.bisect_left`
> +    * :func:`SortedList.bisect_right`
> +    * :func:`SortedList.count`
> +    * :func:`SortedList.index`
> +    * :func:`SortedList.__contains__`
> +    * :func:`SortedList.__getitem__`
> +
> +    Methods for iterating values:
> +
> +    * :func:`SortedList.irange`
> +    * :func:`SortedList.islice`
> +    * :func:`SortedList.__iter__`
> +    * :func:`SortedList.__reversed__`
> +
> +    Methods for miscellany:
> +
> +    * :func:`SortedList.copy`
> +    * :func:`SortedList.__len__`
> +    * :func:`SortedList.__repr__`
> +    * :func:`SortedList._check`
> +    * :func:`SortedList._reset`
> +
> +    Sorted lists use lexicographical ordering semantics when compared to other
> +    sequences.
> +
> +    Some methods of mutable sequences are not supported and will raise
> +    not-implemented error.
> +
>      """
> -    SortedList provides most of the same methods as a list but keeps the items
> -    in sorted order.
> -    """
> -    # pylint: disable=too-many-ancestors
> -    def __init__(self, iterable=None):
> -        """
> -        SortedList provides most of the same methods as a list but keeps the
> -        items in sorted order.
> +    DEFAULT_LOAD_FACTOR = 1000
> +
> +
> +    def __init__(self, iterable=None, key=None):
> +        """Initialize sorted list instance.
> +
> +        Optional `iterable` argument provides an initial iterable of values to
> +        initialize the sorted list.
> +
> +        Runtime complexity: `O(n*log(n))`
> +
> +        >>> sl = SortedList()
> +        >>> sl
> +        SortedList([])
> +        >>> sl = SortedList([3, 1, 2, 5, 4])
> +        >>> sl
> +        SortedList([1, 2, 3, 4, 5])
> +
> +        :param iterable: initial values (optional)
>  
> -        An optional *iterable* provides an initial series of items to populate
> -        the SortedList.
>          """
> +        assert key is None
>          self._len = 0
> +        self._load = self.DEFAULT_LOAD_FACTOR
>          self._lists = []
>          self._maxes = []
>          self._index = []
> -        self._load = LOAD
> -        self._half = LOAD >> 1
> -        self._dual = LOAD << 1
>          self._offset = 0
>  
>          if iterable is not None:
>              self._update(iterable)
>  
> +
>      def __new__(cls, iterable=None, key=None):
> -        """
> -        SortedList provides most of the same methods as a list but keeps the
> -        items in sorted order.
> +        """Create new sorted list or sorted-key list instance.
> +
> +        Optional `key`-function argument will return an instance of subtype
> +        :class:`SortedKeyList`.
>  
> -        An optional *iterable* provides an initial series of items to populate
> -        the SortedList.
> +        >>> sl = SortedList()
> +        >>> isinstance(sl, SortedList)
> +        True
> +        >>> sl = SortedList(key=lambda x: -x)
> +        >>> isinstance(sl, SortedList)
> +        True
> +        >>> isinstance(sl, SortedKeyList)
> +        True
> +
> +        :param iterable: initial values (optional)
> +        :param key: function used to extract comparison key (optional)
> +        :return: sorted list or sorted-key list instance
>  
> -        An optional *key* argument will return an instance of subtype
> -        SortedListWithKey.
>          """
>          # pylint: disable=unused-argument
>          if key is None:
>              return object.__new__(cls)
>          else:
>              if cls is SortedList:
> -                return object.__new__(SortedListWithKey)
> +                return object.__new__(SortedKeyList)
>              else:
> -                raise TypeError('inherit SortedListWithKey for key argument')
> +                raise TypeError('inherit SortedKeyList for key argument')
> +
>  
>      @property
> -    def key(self):
> -        """Key function used to extract comparison key for sorting."""
> +    def key(self):  # pylint: disable=useless-return
> +        """Function used to extract comparison key from values.
> +
> +        Sorted list compares values directly so the key function is none.
> +
> +        """
>          return None
>  
> +
>      def _reset(self, load):
> -        """
> -        Reset sorted list load.
> -
> -        The *load* specifies the load-factor of the list. The default load
> -        factor of '1000' works well for lists from tens to tens of millions of
> -        elements.  Good practice is to use a value that is the cube root of the
> -        list size.  With billions of elements, the best load factor depends on
> -        your usage.  It's best to leave the load factor at the default until
> -        you start benchmarking.
> +        """Reset sorted list load factor.
> +
> +        The `load` specifies the load-factor of the list. The default load
> +        factor of 1000 works well for lists from tens to tens-of-millions of
> +        values. Good practice is to use a value that is the cube root of the
> +        list size. With billions of elements, the best load factor depends on
> +        your usage. It's best to leave the load factor at the default until you
> +        start benchmarking.
> +
> +        See :doc:`implementation` and :doc:`performance-scale` for more
> +        information.
> +
> +        Runtime complexity: `O(n)`
> +
> +        :param int load: load-factor for sorted list sublists
> +
>          """
>          values = reduce(iadd, self._lists, [])
>          self._clear()
>          self._load = load
> -        self._half = load >> 1
> -        self._dual = load << 1
>          self._update(values)
>  
> +
>      def clear(self):
> -        """Remove all the elements from the list."""
> +        """Remove all values from sorted list.
> +
> +        Runtime complexity: `O(n)`
> +
> +        """
>          self._len = 0
>          del self._lists[:]
>          del self._maxes[:]
>          del self._index[:]
> +        self._offset = 0
>  
>      _clear = clear
>  
> -    def add(self, val):
> -        """Add the element *val* to the list."""
> +
> +    def add(self, value):
> +        """Add `value` to sorted list.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> sl = SortedList()
> +        >>> sl.add(3)
> +        >>> sl.add(1)
> +        >>> sl.add(2)
> +        >>> sl
> +        SortedList([1, 2, 3])
> +
> +        :param value: value to add to sorted list
> +
> +        """
>          _lists = self._lists
>          _maxes = self._maxes
>  
>          if _maxes:
> -            pos = bisect_right(_maxes, val)
> +            pos = bisect_right(_maxes, value)
>  
>              if pos == len(_maxes):
>                  pos -= 1
> -                _lists[pos].append(val)
> -                _maxes[pos] = val
> +                _lists[pos].append(value)
> +                _maxes[pos] = value
>              else:
> -                insort(_lists[pos], val)
> +                insort(_lists[pos], value)
>  
>              self._expand(pos)
>          else:
> -            _lists.append([val])
> -            _maxes.append(val)
> +            _lists.append([value])
> +            _maxes.append(value)
>  
>          self._len += 1
>  
> +
>      def _expand(self, pos):
> -        """Splits sublists that are more than double the load level.
> +        """Split sublists with length greater than double the load-factor.
>  
>          Updates the index when the sublist length is less than double the load
>          level. This requires incrementing the nodes in a traversal from the
> -        leaf node to the root. For an example traversal see self._loc.
> +        leaf node to the root. For an example traversal see
> +        ``SortedList._loc``.
>  
>          """
> +        _load = self._load
>          _lists = self._lists
>          _index = self._index
>  
> -        if len(_lists[pos]) > self._dual:
> +        if len(_lists[pos]) > (_load << 1):
>              _maxes = self._maxes
> -            _load = self._load
>  
>              _lists_pos = _lists[pos]
>              half = _lists_pos[_load:]
> @@ -181,15 +318,28 @@ class SortedList(MutableSequence):
>                      child = (child - 1) >> 1
>                  _index[0] += 1
>  
> +
>      def update(self, iterable):
> -        """Update the list by adding all elements from *iterable*."""
> +        """Update sorted list by adding all values from `iterable`.
> +
> +        Runtime complexity: `O(k*log(n))` -- approximate.
> +
> +        >>> sl = SortedList()
> +        >>> sl.update([3, 1, 2])
> +        >>> sl
> +        SortedList([1, 2, 3])
> +
> +        :param iterable: iterable of values to add
> +
> +        """
>          _lists = self._lists
>          _maxes = self._maxes
>          values = sorted(iterable)
>  
>          if _maxes:
>              if len(values) * 4 >= self._len:
> -                values.extend(chain.from_iterable(_lists))
> +                _lists.append(values)
> +                values = reduce(iadd, _lists, [])
>                  values.sort()
>                  self._clear()
>              else:
> @@ -207,78 +357,123 @@ class SortedList(MutableSequence):
>  
>      _update = update
>  
> -    def __contains__(self, val):
> -        """Return True if and only if *val* is an element in the list."""
> +
> +    def __contains__(self, value):
> +        """Return true if `value` is an element of the sorted list.
> +
> +        ``sl.__contains__(value)`` <==> ``value in sl``
> +
> +        Runtime complexity: `O(log(n))`
> +
> +        >>> sl = SortedList([1, 2, 3, 4, 5])
> +        >>> 3 in sl
> +        True
> +
> +        :param value: search for value in sorted list
> +        :return: true if `value` in sorted list
> +
> +        """
>          _maxes = self._maxes
>  
>          if not _maxes:
>              return False
>  
> -        pos = bisect_left(_maxes, val)
> +        pos = bisect_left(_maxes, value)
>  
>          if pos == len(_maxes):
>              return False
>  
>          _lists = self._lists
> -        idx = bisect_left(_lists[pos], val)
> +        idx = bisect_left(_lists[pos], value)
>  
> -        return _lists[pos][idx] == val
> +        return _lists[pos][idx] == value
>  
> -    def discard(self, val):
> -        """
> -        Remove the first occurrence of *val*.
>  
> -        If *val* is not a member, does nothing.
> +    def discard(self, value):
> +        """Remove `value` from sorted list if it is a member.
> +
> +        If `value` is not a member, do nothing.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> sl = SortedList([1, 2, 3, 4, 5])
> +        >>> sl.discard(5)
> +        >>> sl.discard(0)
> +        >>> sl == [1, 2, 3, 4]
> +        True
> +
> +        :param value: `value` to discard from sorted list
> +
>          """
>          _maxes = self._maxes
>  
>          if not _maxes:
>              return
>  
> -        pos = bisect_left(_maxes, val)
> +        pos = bisect_left(_maxes, value)
>  
>          if pos == len(_maxes):
>              return
>  
>          _lists = self._lists
> -        idx = bisect_left(_lists[pos], val)
> +        idx = bisect_left(_lists[pos], value)
>  
> -        if _lists[pos][idx] == val:
> +        if _lists[pos][idx] == value:
>              self._delete(pos, idx)
>  
> -    def remove(self, val):
> -        """
> -        Remove first occurrence of *val*.
>  
> -        Raises ValueError if *val* is not present.
> +    def remove(self, value):
> +        """Remove `value` from sorted list; `value` must be a member.
> +
> +        If `value` is not a member, raise ValueError.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> sl = SortedList([1, 2, 3, 4, 5])
> +        >>> sl.remove(5)
> +        >>> sl == [1, 2, 3, 4]
> +        True
> +        >>> sl.remove(0)
> +        Traceback (most recent call last):
> +          ...
> +        ValueError: 0 not in list
> +
> +        :param value: `value` to remove from sorted list
> +        :raises ValueError: if `value` is not in sorted list
> +
>          """
> -        # pylint: disable=arguments-differ
>          _maxes = self._maxes
>  
>          if not _maxes:
> -            raise ValueError('{0!r} not in list'.format(val))
> +            raise ValueError('{0!r} not in list'.format(value))
>  
> -        pos = bisect_left(_maxes, val)
> +        pos = bisect_left(_maxes, value)
>  
>          if pos == len(_maxes):
> -            raise ValueError('{0!r} not in list'.format(val))
> +            raise ValueError('{0!r} not in list'.format(value))
>  
>          _lists = self._lists
> -        idx = bisect_left(_lists[pos], val)
> +        idx = bisect_left(_lists[pos], value)
>  
> -        if _lists[pos][idx] == val:
> +        if _lists[pos][idx] == value:
>              self._delete(pos, idx)
>          else:
> -            raise ValueError('{0!r} not in list'.format(val))
> +            raise ValueError('{0!r} not in list'.format(value))
> +
>  
>      def _delete(self, pos, idx):
> -        """Delete the item at the given (pos, idx).
> +        """Delete value at the given `(pos, idx)`.
>  
>          Combines lists that are less than half the load level.
>  
>          Updates the index when the sublist length is more than half the load
> -        level. This requires decrementing the nodes in a traversal from the leaf
> -        node to the root. For an example traversal see self._loc.
> +        level. This requires decrementing the nodes in a traversal from the
> +        leaf node to the root. For an example traversal see
> +        ``SortedList._loc``.
> +
> +        :param int pos: lists index
> +        :param int idx: sublist index
> +
>          """
>          _lists = self._lists
>          _maxes = self._maxes
> @@ -291,8 +486,7 @@ class SortedList(MutableSequence):
>  
>          len_lists_pos = len(_lists_pos)
>  
> -        if len_lists_pos > self._half:
> -
> +        if len_lists_pos > (self._load >> 1):
>              _maxes[pos] = _lists_pos[-1]
>  
>              if _index:
> @@ -301,9 +495,7 @@ class SortedList(MutableSequence):
>                      _index[child] -= 1
>                      child = (child - 1) >> 1
>                  _index[0] -= 1
> -
>          elif len(_lists) > 1:
> -
>              if not pos:
>                  pos += 1
>  
> @@ -316,26 +508,24 @@ class SortedList(MutableSequence):
>              del _index[:]
>  
>              self._expand(prev)
> -
>          elif len_lists_pos:
> -
>              _maxes[pos] = _lists_pos[-1]
> -
>          else:
> -
>              del _lists[pos]
>              del _maxes[pos]
>              del _index[:]
>  
> +
>      def _loc(self, pos, idx):
> -        """Convert an index pair (alpha, beta) into a single index that corresponds to
> -        the position of the value in the sorted list.
> +        """Convert an index pair (lists index, sublist index) into a single
> +        index number that corresponds to the position of the value in the
> +        sorted list.
>  
> -        Most queries require the index be built. Details of the index are
> -        described in self._build_index.
> +        Many queries require the index be built. Details of the index are
> +        described in ``SortedList._build_index``.
>  
>          Indexing requires traversing the tree from a leaf node to the root. The
> -        parent of each node is easily computable at (pos - 1) // 2.
> +        parent of each node is easily computable at ``(pos - 1) // 2``.
>  
>          Left-child nodes are always at odd indices and right-child nodes are
>          always at even indices.
> @@ -345,19 +535,19 @@ class SortedList(MutableSequence):
>  
>          The final index is the sum from traversal and the index in the sublist.
>  
> -        For example, using the index from self._build_index:
> +        For example, using the index from ``SortedList._build_index``::
>  
> -        _index = 14 5 9 3 2 4 5
> -        _offset = 3
> +            _index = 14 5 9 3 2 4 5
> +            _offset = 3
>  
> -        Tree:
> +        Tree::
>  
>                   14
>                5      9
>              3   2  4   5
>  
> -        Converting index pair (2, 3) into a single index involves iterating like
> -        so:
> +        Converting an index pair (2, 3) into a single index involves iterating
> +        like so:
>  
>          1. Starting at the leaf node: offset + alpha = 3 + 2 = 5. We identify
>             the node as a left-child node. At such nodes, we simply traverse to
> @@ -369,7 +559,12 @@ class SortedList(MutableSequence):
>  
>          3. Iteration ends at the root.
>  
> -        Computing the index is the sum of the total and beta: 5 + 3 = 8.
> +        The index is then the sum of the total and sublist index: 5 + 3 = 8.
> +
> +        :param int pos: lists index
> +        :param int idx: sublist index
> +        :return: index in sorted list
> +
>          """
>          if not pos:
>              return idx
> @@ -401,16 +596,18 @@ class SortedList(MutableSequence):
>  
>          return total + idx
>  
> +
>      def _pos(self, idx):
> -        """Convert an index into a pair (alpha, beta) that can be used to access
> -        the corresponding _lists[alpha][beta] position.
> +        """Convert an index into an index pair (lists index, sublist index)
> +        that can be used to access the corresponding lists position.
>  
> -        Most queries require the index be built. Details of the index are
> -        described in self._build_index.
> +        Many queries require the index be built. Details of the index are
> +        described in ``SortedList._build_index``.
>  
> -        Indexing requires traversing the tree to a leaf node. Each node has
> -        two children which are easily computable. Given an index, pos, the
> -        left-child is at pos * 2 + 1 and the right-child is at pos * 2 + 2.
> +        Indexing requires traversing the tree to a leaf node. Each node has two
> +        children which are easily computable. Given an index, pos, the
> +        left-child is at ``pos * 2 + 1`` and the right-child is at ``pos * 2 +
> +        2``.
>  
>          When the index is less than the left-child, traversal moves to the
>          left sub-tree. Otherwise, the index is decremented by the left-child
> @@ -420,12 +617,12 @@ class SortedList(MutableSequence):
>          position of the child node as compared with the offset and the remaining
>          index.
>  
> -        For example, using the index from self._build_index:
> +        For example, using the index from ``SortedList._build_index``::
>  
> -        _index = 14 5 9 3 2 4 5
> -        _offset = 3
> +            _index = 14 5 9 3 2 4 5
> +            _offset = 3
>  
> -        Tree:
> +        Tree::
>  
>                   14
>                5      9
> @@ -450,6 +647,10 @@ class SortedList(MutableSequence):
>  
>          The final index pair from our example is (2, 3) which corresponds to
>          index 8 in the sorted list.
> +
> +        :param int idx: index in sorted list
> +        :return: (lists index, sublist index) pair
> +
>          """
>          if idx < 0:
>              last_len = len(self._lists[-1])
> @@ -489,39 +690,42 @@ class SortedList(MutableSequence):
>  
>          return (pos - self._offset, idx)
>  
> +
>      def _build_index(self):
> -        """Build an index for indexing the sorted list.
> +        """Build a positional index for indexing the sorted list.
>  
>          Indexes are represented as binary trees in a dense array notation
>          similar to a binary heap.
>  
> -        For example, given a _lists representation storing integers:
> +        For example, given a lists representation storing integers::
>  
> -        [0]: 1 2 3
> -        [1]: 4 5
> -        [2]: 6 7 8 9
> -        [3]: 10 11 12 13 14
> +            0: [1, 2, 3]
> +            1: [4, 5]
> +            2: [6, 7, 8, 9]
> +            3: [10, 11, 12, 13, 14]
>  
>          The first transformation maps the sub-lists by their length. The
> -        first row of the index is the length of the sub-lists.
> +        first row of the index is the length of the sub-lists::
>  
> -        [0]: 3 2 4 5
> +            0: [3, 2, 4, 5]
>  
> -        Each row after that is the sum of consecutive pairs of the previous row:
> +        Each row after that is the sum of consecutive pairs of the previous
> +        row::
>  
> -        [1]: 5 9
> -        [2]: 14
> +            1: [5, 9]
> +            2: [14]
>  
> -        Finally, the index is built by concatenating these lists together:
> +        Finally, the index is built by concatenating these lists together::
>  
> -        _index = 14 5 9 3 2 4 5
> +            _index = [14, 5, 9, 3, 2, 4, 5]
>  
> -        An offset storing the start of the first row is also stored:
> +        An offset storing the start of the first row is also stored::
>  
> -        _offset = 3
> +            _offset = 3
>  
>          When built, the index can be used for efficient indexing into the list.
> -        See the comment and notes on self._pos for details.
> +        See the comment and notes on ``SortedList._pos`` for details.
> +
>          """
>          row0 = list(map(len, self._lists))
>  
> @@ -542,7 +746,7 @@ class SortedList(MutableSequence):
>              self._offset = 1
>              return
>  
> -        size = 2 ** (int(log_e(len(row1) - 1, 2)) + 1)
> +        size = 2 ** (int(log(len(row1) - 1, 2)) + 1)
>          row1.extend(repeat(0, size - len(row1)))
>          tree = [row0, row1]
>  
> @@ -555,10 +759,30 @@ class SortedList(MutableSequence):
>          reduce(iadd, reversed(tree), self._index)
>          self._offset = size * 2 - 1
>  
> -    def __delitem__(self, idx):
> -        """Remove the element at *idx*. Supports slicing."""
> -        if isinstance(idx, slice):
> -            start, stop, step = idx.indices(self._len)
> +
> +    def __delitem__(self, index):
> +        """Remove value at `index` from sorted list.
> +
> +        ``sl.__delitem__(index)`` <==> ``del sl[index]``
> +
> +        Supports slicing.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> sl = SortedList('abcde')
> +        >>> del sl[2]
> +        >>> sl
> +        SortedList(['a', 'b', 'd', 'e'])
> +        >>> del sl[:2]
> +        >>> sl
> +        SortedList(['d', 'e'])
> +
> +        :param index: integer or slice for indexing
> +        :raises IndexError: if index out of range
> +
> +        """
> +        if isinstance(index, slice):
> +            start, stop, step = index.indices(self._len)
>  
>              if step == 1 and start < stop:
>                  if start == 0 and stop == self._len:
> @@ -584,23 +808,53 @@ class SortedList(MutableSequence):
>                  pos, idx = _pos(index)
>                  _delete(pos, idx)
>          else:
> -            pos, idx = self._pos(idx)
> +            pos, idx = self._pos(index)
>              self._delete(pos, idx)
>  
> -    _delitem = __delitem__
>  
> -    def __getitem__(self, idx):
> -        """Return the element at *idx*. Supports slicing."""
> +    def __getitem__(self, index):
> +        """Lookup value at `index` in sorted list.
> +
> +        ``sl.__getitem__(index)`` <==> ``sl[index]``
> +
> +        Supports slicing.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> sl = SortedList('abcde')
> +        >>> sl[1]
> +        'b'
> +        >>> sl[-1]
> +        'e'
> +        >>> sl[2:5]
> +        ['c', 'd', 'e']
> +
> +        :param index: integer or slice for indexing
> +        :return: value or list of values
> +        :raises IndexError: if index out of range
> +
> +        """
>          _lists = self._lists
>  
> -        if isinstance(idx, slice):
> -            start, stop, step = idx.indices(self._len)
> +        if isinstance(index, slice):
> +            start, stop, step = index.indices(self._len)
>  
>              if step == 1 and start < stop:
> +                # Whole slice optimization: start to stop slices the whole
> +                # sorted list.
> +
>                  if start == 0 and stop == self._len:
>                      return reduce(iadd, self._lists, [])
>  
>                  start_pos, start_idx = self._pos(start)
> +                start_list = _lists[start_pos]
> +                stop_idx = start_idx + stop - start
> +
> +                # Small slice optimization: start index and stop index are
> +                # within the start list.
> +
> +                if len(start_list) >= stop_idx:
> +                    return start_list[start_idx:stop_idx]
>  
>                  if stop == self._len:
>                      stop_pos = len(_lists) - 1
> @@ -608,9 +862,6 @@ class SortedList(MutableSequence):
>                  else:
>                      stop_pos, stop_idx = self._pos(stop)
>  
> -                if start_pos == stop_pos:
> -                    return _lists[start_pos][start_idx:stop_idx]
> -
>                  prefix = _lists[start_pos][start_idx:]
>                  middle = _lists[(start_pos + 1):stop_pos]
>                  result = reduce(iadd, middle, prefix)
> @@ -631,221 +882,104 @@ class SortedList(MutableSequence):
>              return list(self._getitem(index) for index in indices)
>          else:
>              if self._len:
> -                if idx == 0:
> +                if index == 0:
>                      return _lists[0][0]
> -                elif idx == -1:
> +                elif index == -1:
>                      return _lists[-1][-1]
>              else:
>                  raise IndexError('list index out of range')
>  
> -            if 0 <= idx < len(_lists[0]):
> -                return _lists[0][idx]
> +            if 0 <= index < len(_lists[0]):
> +                return _lists[0][index]
>  
>              len_last = len(_lists[-1])
>  
> -            if -len_last < idx < 0:
> -                return _lists[-1][len_last + idx]
> +            if -len_last < index < 0:
> +                return _lists[-1][len_last + index]
>  
> -            pos, idx = self._pos(idx)
> +            pos, idx = self._pos(index)
>              return _lists[pos][idx]
>  
>      _getitem = __getitem__
>  
> -    def _check_order(self, idx, val):
> -        _len = self._len
> -        _lists = self._lists
> -
> -        pos, loc = self._pos(idx)
> -
> -        if idx < 0:
> -            idx += _len
> -
> -        # Check that the inserted value is not less than the
> -        # previous value.
> -
> -        if idx > 0:
> -            idx_prev = loc - 1
> -            pos_prev = pos
> -
> -            if idx_prev < 0:
> -                pos_prev -= 1
> -                idx_prev = len(_lists[pos_prev]) - 1
> -
> -            if _lists[pos_prev][idx_prev] > val:
> -                msg = '{0!r} not in sort order at index {1}'.format(val, idx)
> -                raise ValueError(msg)
> -
> -        # Check that the inserted value is not greater than
> -        # the previous value.
> -
> -        if idx < (_len - 1):
> -            idx_next = loc + 1
> -            pos_next = pos
> -
> -            if idx_next == len(_lists[pos_next]):
> -                pos_next += 1
> -                idx_next = 0
> -
> -            if _lists[pos_next][idx_next] < val:
> -                msg = '{0!r} not in sort order at index {1}'.format(val, idx)
> -                raise ValueError(msg)
>  
>      def __setitem__(self, index, value):
> -        """Replace item at position *index* with *value*.
> -
> -        Supports slice notation. Raises :exc:`ValueError` if the sort order
> -        would be violated. When used with a slice and iterable, the
> -        :exc:`ValueError` is raised before the list is mutated if the sort
> -        order would be violated by the operation.
> -
> -        """
> -        _lists = self._lists
> -        _maxes = self._maxes
> -        _check_order = self._check_order
> -        _pos = self._pos
> -
> -        if isinstance(index, slice):
> -            _len = self._len
> -            start, stop, step = index.indices(_len)
> -            indices = range(start, stop, step)
> -
> -            # Copy value to avoid aliasing issues with self and cases where an
> -            # iterator is given.
> -
> -            values = tuple(value)
> -
> -            if step != 1:
> -                if len(values) != len(indices):
> -                    raise ValueError(
> -                        'attempt to assign sequence of size %s'
> -                        ' to extended slice of size %s'
> -                        % (len(values), len(indices)))
> -
> -                # Keep a log of values that are set so that we can
> -                # roll back changes if ordering is violated.
> -
> -                log = []
> -                _append = log.append
> -
> -                for idx, val in zip(indices, values):
> -                    pos, loc = _pos(idx)
> -                    _append((idx, _lists[pos][loc], val))
> -                    _lists[pos][loc] = val
> -                    if len(_lists[pos]) == (loc + 1):
> -                        _maxes[pos] = val
> -
> -                try:
> -                    # Validate ordering of new values.
> -
> -                    for idx, _, newval in log:
> -                        _check_order(idx, newval)
> +        """Raise not-implemented error.
>  
> -                except ValueError:
> +        ``sl.__setitem__(index, value)`` <==> ``sl[index] = value``
>  
> -                    # Roll back changes from log.
> +        :raises NotImplementedError: use ``del sl[index]`` and
> +            ``sl.add(value)`` instead
>  
> -                    for idx, oldval, _ in log:
> -                        pos, loc = _pos(idx)
> -                        _lists[pos][loc] = oldval
> -                        if len(_lists[pos]) == (loc + 1):
> -                            _maxes[pos] = oldval
> -
> -                    raise
> -            else:
> -                if start == 0 and stop == _len:
> -                    self._clear()
> -                    return self._update(values)
> -
> -                if stop < start:
> -                    # When calculating indices, stop may be less than start.
> -                    # For example: ...[5:3:1] results in slice(5, 3, 1) which
> -                    # is a valid but not useful stop index.
> -                    stop = start
> -
> -                if values:
> -
> -                    # Check that given values are ordered properly.
> -
> -                    alphas = iter(values)
> -                    betas = iter(values)
> -                    next(betas)
> -                    pairs = zip(alphas, betas)
> -
> -                    if not all(alpha <= beta for alpha, beta in pairs):
> -                        raise ValueError('given values not in sort order')
> -
> -                    # Check ordering in context of sorted list.
> -
> -                    if start and self._getitem(start - 1) > values[0]:
> -                        message = '{0!r} not in sort order at index {1}'.format(
> -                            values[0], start)
> -                        raise ValueError(message)
> -
> -                    if stop != _len and self._getitem(stop) < values[-1]:
> -                        message = '{0!r} not in sort order at index {1}'.format(
> -                            values[-1], stop)
> -                        raise ValueError(message)
> -
> -                # Delete the existing values.
> +        """
> +        message = 'use ``del sl[index]`` and ``sl.add(value)`` instead'
> +        raise NotImplementedError(message)
>  
> -                self._delitem(index)
>  
> -                # Insert the new values.
> +    def __iter__(self):
> +        """Return an iterator over the sorted list.
>  
> -                _insert = self.insert
> -                for idx, val in enumerate(values):
> -                    _insert(start + idx, val)
> -        else:
> -            pos, loc = _pos(index)
> -            _check_order(index, value)
> -            _lists[pos][loc] = value
> -            if len(_lists[pos]) == (loc + 1):
> -                _maxes[pos] = value
> +        ``sl.__iter__()`` <==> ``iter(sl)``
>  
> -    def __iter__(self):
> -        """
> -        Return an iterator over the Sequence.
> +        Iterating the sorted list while adding or deleting values may raise a
> +        :exc:`RuntimeError` or fail to iterate over all values.
>  
> -        Iterating the Sequence while adding or deleting values may raise a
> -        `RuntimeError` or fail to iterate over all entries.
>          """
>          return chain.from_iterable(self._lists)
>  
> +
>      def __reversed__(self):
> -        """
> -        Return an iterator to traverse the Sequence in reverse.
> +        """Return a reverse iterator over the sorted list.
> +
> +        ``sl.__reversed__()`` <==> ``reversed(sl)``
> +
> +        Iterating the sorted list while adding or deleting values may raise a
> +        :exc:`RuntimeError` or fail to iterate over all values.
>  
> -        Iterating the Sequence while adding or deleting values may raise a
> -        `RuntimeError` or fail to iterate over all entries.
>          """
>          return chain.from_iterable(map(reversed, reversed(self._lists)))
>  
> +
>      def reverse(self):
> -        """Raise NotImplementedError
> +        """Raise not-implemented error.
>  
> -        SortedList maintains values in ascending sort order. Values may not be
> +        Sorted list maintains values in ascending sort order. Values may not be
>          reversed in-place.
>  
> -        Use ``reversed(sorted_list)`` for a reverse iterator over values in
> -        descending sort order.
> +        Use ``reversed(sl)`` for an iterator over values in descending sort
> +        order.
>  
> -        Implemented to override MutableSequence.reverse which provides an
> +        Implemented to override `MutableSequence.reverse` which provides an
>          erroneous default implementation.
>  
> +        :raises NotImplementedError: use ``reversed(sl)`` instead
> +
>          """
> -        raise NotImplementedError('.reverse() not defined')
> +        raise NotImplementedError('use ``reversed(sl)`` instead')
>  
> -    def islice(self, start=None, stop=None, reverse=False):
>  
> -        """
> -        Returns an iterator that slices `self` from `start` to `stop` index,
> -        inclusive and exclusive respectively.
> +    def islice(self, start=None, stop=None, reverse=False):
> +        """Return an iterator that slices sorted list from `start` to `stop`.
>  
> -        When `reverse` is `True`, values are yielded from the iterator in
> -        reverse order.
> +        The `start` and `stop` index are treated inclusive and exclusive,
> +        respectively.
>  
>          Both `start` and `stop` default to `None` which is automatically
> -        inclusive of the beginning and end.
> +        inclusive of the beginning and end of the sorted list.
> +
> +        When `reverse` is `True` the values are yielded from the iterator in
> +        reverse order; `reverse` defaults to `False`.
> +
> +        >>> sl = SortedList('abcdefghij')
> +        >>> it = sl.islice(2, 6)
> +        >>> list(it)
> +        ['c', 'd', 'e', 'f']
> +
> +        :param int start: start index (inclusive)
> +        :param int stop: stop index (exclusive)
> +        :param bool reverse: yield values in reverse order
> +        :return: iterator
> +
>          """
>          _len = self._len
>  
> @@ -869,60 +1003,97 @@ class SortedList(MutableSequence):
>  
>          return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)
>  
> +
>      def _islice(self, min_pos, min_idx, max_pos, max_idx, reverse):
> -        """
> -        Returns an iterator that slices `self` using two index pairs,
> -        `(min_pos, min_idx)` and `(max_pos, max_idx)`; the first inclusive
> -        and the latter exclusive. See `_pos` for details on how an index
> -        is converted to an index pair.
> +        """Return an iterator that slices sorted list using two index pairs.
> +
> +        The index pairs are (min_pos, min_idx) and (max_pos, max_idx), the
> +        first inclusive and the latter exclusive. See `_pos` for details on how
> +        an index is converted to an index pair.
>  
>          When `reverse` is `True`, values are yielded from the iterator in
>          reverse order.
> +
>          """
>          _lists = self._lists
>  
>          if min_pos > max_pos:
>              return iter(())
> -        elif min_pos == max_pos and not reverse:
> -            return iter(_lists[min_pos][min_idx:max_idx])
> -        elif min_pos == max_pos and reverse:
> -            return reversed(_lists[min_pos][min_idx:max_idx])
> -        elif min_pos + 1 == max_pos and not reverse:
> -            return chain(_lists[min_pos][min_idx:], _lists[max_pos][:max_idx])
> -        elif min_pos + 1 == max_pos and reverse:
> +
> +        if min_pos == max_pos:
> +            if reverse:
> +                indices = reversed(range(min_idx, max_idx))
> +                return map(_lists[min_pos].__getitem__, indices)
> +
> +            indices = range(min_idx, max_idx)
> +            return map(_lists[min_pos].__getitem__, indices)
> +
> +        next_pos = min_pos + 1
> +
> +        if next_pos == max_pos:
> +            if reverse:
> +                min_indices = range(min_idx, len(_lists[min_pos]))
> +                max_indices = range(max_idx)
> +                return chain(
> +                    map(_lists[max_pos].__getitem__, reversed(max_indices)),
> +                    map(_lists[min_pos].__getitem__, reversed(min_indices)),
> +                )
> +
> +            min_indices = range(min_idx, len(_lists[min_pos]))
> +            max_indices = range(max_idx)
>              return chain(
> -                reversed(_lists[max_pos][:max_idx]),
> -                reversed(_lists[min_pos][min_idx:]),
> +                map(_lists[min_pos].__getitem__, min_indices),
> +                map(_lists[max_pos].__getitem__, max_indices),
>              )
> -        elif not reverse:
> +
> +        if reverse:
> +            min_indices = range(min_idx, len(_lists[min_pos]))
> +            sublist_indices = range(next_pos, max_pos)
> +            sublists = map(_lists.__getitem__, reversed(sublist_indices))
> +            max_indices = range(max_idx)
>              return chain(
> -                _lists[min_pos][min_idx:],
> -                chain.from_iterable(_lists[(min_pos + 1):max_pos]),
> -                _lists[max_pos][:max_idx],
> +                map(_lists[max_pos].__getitem__, reversed(max_indices)),
> +                chain.from_iterable(map(reversed, sublists)),
> +                map(_lists[min_pos].__getitem__, reversed(min_indices)),
>              )
>  
> -        temp = map(reversed, reversed(_lists[(min_pos + 1):max_pos]))
> +        min_indices = range(min_idx, len(_lists[min_pos]))
> +        sublist_indices = range(next_pos, max_pos)
> +        sublists = map(_lists.__getitem__, sublist_indices)
> +        max_indices = range(max_idx)
>          return chain(
> -            reversed(_lists[max_pos][:max_idx]),
> -            chain.from_iterable(temp),
> -            reversed(_lists[min_pos][min_idx:]),
> +            map(_lists[min_pos].__getitem__, min_indices),
> +            chain.from_iterable(sublists),
> +            map(_lists[max_pos].__getitem__, max_indices),
>          )
>  
> +
>      def irange(self, minimum=None, maximum=None, inclusive=(True, True),
>                 reverse=False):
> -        """
> -        Create an iterator of values between `minimum` and `maximum`.
> -
> -        `inclusive` is a pair of booleans that indicates whether the minimum
> -        and maximum ought to be included in the range, respectively. The
> -        default is (True, True) such that the range is inclusive of both
> -        minimum and maximum.
> +        """Create an iterator of values between `minimum` and `maximum`.
>  
>          Both `minimum` and `maximum` default to `None` which is automatically
> -        inclusive of the start and end of the list, respectively.
> +        inclusive of the beginning and end of the sorted list.
> +
> +        The argument `inclusive` is a pair of booleans that indicates whether
> +        the minimum and maximum ought to be included in the range,
> +        respectively. The default is ``(True, True)`` such that the range is
> +        inclusive of both minimum and maximum.
>  
>          When `reverse` is `True` the values are yielded from the iterator in
>          reverse order; `reverse` defaults to `False`.
> +
> +        >>> sl = SortedList('abcdefghij')
> +        >>> it = sl.irange('c', 'f')
> +        >>> list(it)
> +        ['c', 'd', 'e', 'f']
> +
> +        :param minimum: minimum value to start iterating
> +        :param maximum: maximum value to stop iterating
> +        :param inclusive: pair of booleans
> +        :param bool reverse: yield values in reverse order
> +        :return: iterator
> +
>          """
>          _maxes = self._maxes
>  
> @@ -979,286 +1150,263 @@ class SortedList(MutableSequence):
>  
>          return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)
>  
> +
>      def __len__(self):
> -        """Return the number of elements in the list."""
> -        return self._len
> +        """Return the size of the sorted list.
> +
> +        ``sl.__len__()`` <==> ``len(sl)``
> +
> +        :return: size of sorted list
>  
> -    def bisect_left(self, val):
>          """
> -        Similar to the *bisect* module in the standard library, this returns an
> -        appropriate index to insert *val*. If *val* is already present, the
> -        insertion point will be before (to the left of) any existing entries.
> +        return self._len
> +
> +
> +    def bisect_left(self, value):
> +        """Return an index to insert `value` in the sorted list.
> +
> +        If the `value` is already present, the insertion point will be before
> +        (to the left of) any existing values.
> +
> +        Similar to the `bisect` module in the standard library.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> sl = SortedList([10, 11, 12, 13, 14])
> +        >>> sl.bisect_left(12)
> +        2
> +
> +        :param value: insertion index of value in sorted list
> +        :return: index
> +
>          """
>          _maxes = self._maxes
>  
>          if not _maxes:
>              return 0
>  
> -        pos = bisect_left(_maxes, val)
> +        pos = bisect_left(_maxes, value)
>  
>          if pos == len(_maxes):
>              return self._len
>  
> -        idx = bisect_left(self._lists[pos], val)
> -
> +        idx = bisect_left(self._lists[pos], value)
>          return self._loc(pos, idx)
>  
> -    def bisect_right(self, val):
> -        """
> -        Same as *bisect_left*, but if *val* is already present, the insertion
> -        point will be after (to the right of) any existing entries.
> +
> +    def bisect_right(self, value):
> +        """Return an index to insert `value` in the sorted list.
> +
> +        Similar to `bisect_left`, but if `value` is already present, the
> +        insertion point will be after (to the right of) any existing values.
> +
> +        Similar to the `bisect` module in the standard library.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> sl = SortedList([10, 11, 12, 13, 14])
> +        >>> sl.bisect_right(12)
> +        3
> +
> +        :param value: insertion index of value in sorted list
> +        :return: index
> +
>          """
>          _maxes = self._maxes
>  
>          if not _maxes:
>              return 0
>  
> -        pos = bisect_right(_maxes, val)
> +        pos = bisect_right(_maxes, value)
>  
>          if pos == len(_maxes):
>              return self._len
>  
> -        idx = bisect_right(self._lists[pos], val)
> -
> +        idx = bisect_right(self._lists[pos], value)
>          return self._loc(pos, idx)
>  
>      bisect = bisect_right
>      _bisect_right = bisect_right
>  
> -    def count(self, val):
> -        """Return the number of occurrences of *val* in the list."""
> -        # pylint: disable=arguments-differ
> +
> +    def count(self, value):
> +        """Return number of occurrences of `value` in the sorted list.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> sl = SortedList([1, 2, 2, 3, 3, 3, 4, 4, 4, 4])
> +        >>> sl.count(3)
> +        3
> +
> +        :param value: value to count in sorted list
> +        :return: count
> +
> +        """
>          _maxes = self._maxes
>  
>          if not _maxes:
>              return 0
>  
> -        pos_left = bisect_left(_maxes, val)
> +        pos_left = bisect_left(_maxes, value)
>  
>          if pos_left == len(_maxes):
>              return 0
>  
>          _lists = self._lists
> -        idx_left = bisect_left(_lists[pos_left], val)
> -        pos_right = bisect_right(_maxes, val)
> +        idx_left = bisect_left(_lists[pos_left], value)
> +        pos_right = bisect_right(_maxes, value)
>  
>          if pos_right == len(_maxes):
>              return self._len - self._loc(pos_left, idx_left)
>  
> -        idx_right = bisect_right(_lists[pos_right], val)
> +        idx_right = bisect_right(_lists[pos_right], value)
>  
>          if pos_left == pos_right:
>              return idx_right - idx_left
>  
>          right = self._loc(pos_right, idx_right)
>          left = self._loc(pos_left, idx_left)
> -
>          return right - left
>  
> +
>      def copy(self):
> -        """Return a shallow copy of the sorted list."""
> -        return self.__class__(self)
> +        """Return a shallow copy of the sorted list.
>  
> -    __copy__ = copy
> +        Runtime complexity: `O(n)`
> +
> +        :return: new sorted list
>  
> -    def append(self, val):
> -        """
> -        Append the element *val* to the list. Raises a ValueError if the *val*
> -        would violate the sort order.
>          """
> -        # pylint: disable=arguments-differ
> -        _lists = self._lists
> -        _maxes = self._maxes
> +        return self.__class__(self)
>  
> -        if not _maxes:
> -            _maxes.append(val)
> -            _lists.append([val])
> -            self._len = 1
> -            return
> +    __copy__ = copy
>  
> -        pos = len(_lists) - 1
>  
> -        if val < _lists[pos][-1]:
> -            msg = '{0!r} not in sort order at index {1}'.format(val, self._len)
> -            raise ValueError(msg)
> +    def append(self, value):
> +        """Raise not-implemented error.
>  
> -        _maxes[pos] = val
> -        _lists[pos].append(val)
> -        self._len += 1
> -        self._expand(pos)
> +        Implemented to override `MutableSequence.append` which provides an
> +        erroneous default implementation.
>  
> -    def extend(self, values):
> -        """
> -        Extend the list by appending all elements from the *values*. Raises a
> -        ValueError if the sort order would be violated.
> -        """
> -        _lists = self._lists
> -        _maxes = self._maxes
> -        _load = self._load
> -
> -        if not isinstance(values, list):
> -            values = list(values)
> +        :raises NotImplementedError: use ``sl.add(value)`` instead
>  
> -        if not values:
> -            return
> -
> -        if any(values[pos - 1] > values[pos]
> -               for pos in range(1, len(values))):
> -            raise ValueError('given sequence not in sort order')
> +        """
> +        raise NotImplementedError('use ``sl.add(value)`` instead')
>  
> -        offset = 0
>  
> -        if _maxes:
> -            if values[0] < _lists[-1][-1]:
> -                msg = '{0!r} not in sort order at index {1}'.format(values[0], self._len)
> -                raise ValueError(msg)
> +    def extend(self, values):
> +        """Raise not-implemented error.
>  
> -            if len(_lists[-1]) < self._half:
> -                _lists[-1].extend(values[:_load])
> -                _maxes[-1] = _lists[-1][-1]
> -                offset = _load
> +        Implemented to override `MutableSequence.extend` which provides an
> +        erroneous default implementation.
>  
> -        len_lists = len(_lists)
> +        :raises NotImplementedError: use ``sl.update(values)`` instead
>  
> -        for idx in range(offset, len(values), _load):
> -            _lists.append(values[idx:(idx + _load)])
> -            _maxes.append(_lists[-1][-1])
> +        """
> +        raise NotImplementedError('use ``sl.update(values)`` instead')
>  
> -        _index = self._index
>  
> -        if len_lists == len(_lists):
> -            len_index = len(_index)
> -            if len_index > 0:
> -                len_values = len(values)
> -                child = len_index - 1
> -                while child:
> -                    _index[child] += len_values
> -                    child = (child - 1) >> 1
> -                _index[0] += len_values
> -        else:
> -            del _index[:]
> +    def insert(self, index, value):
> +        """Raise not-implemented error.
>  
> -        self._len += len(values)
> +        :raises NotImplementedError: use ``sl.add(value)`` instead
>  
> -    def insert(self, idx, val):
> -        """
> -        Insert the element *val* into the list at *idx*. Raises a ValueError if
> -        the *val* at *idx* would violate the sort order.
>          """
> -        # pylint: disable=arguments-differ
> -        _len = self._len
> -        _lists = self._lists
> -        _maxes = self._maxes
> +        raise NotImplementedError('use ``sl.add(value)`` instead')
>  
> -        if idx < 0:
> -            idx += _len
> -        if idx < 0:
> -            idx = 0
> -        if idx > _len:
> -            idx = _len
>  
> -        if not _maxes:
> -            # The idx must be zero by the inequalities above.
> -            _maxes.append(val)
> -            _lists.append([val])
> -            self._len = 1
> -            return
> +    def pop(self, index=-1):
> +        """Remove and return value at `index` in sorted list.
>  
> -        if not idx:
> -            if val > _lists[0][0]:
> -                msg = '{0!r} not in sort order at index {1}'.format(val, 0)
> -                raise ValueError(msg)
> -            else:
> -                _lists[0].insert(0, val)
> -                self._expand(0)
> -                self._len += 1
> -                return
> +        Raise :exc:`IndexError` if the sorted list is empty or index is out of
> +        range.
>  
> -        if idx == _len:
> -            pos = len(_lists) - 1
> -            if _lists[pos][-1] > val:
> -                msg = '{0!r} not in sort order at index {1}'.format(val, _len)
> -                raise ValueError(msg)
> -            else:
> -                _lists[pos].append(val)
> -                _maxes[pos] = _lists[pos][-1]
> -                self._expand(pos)
> -                self._len += 1
> -                return
> +        Negative indices are supported.
>  
> -        pos, idx = self._pos(idx)
> -        idx_before = idx - 1
> -        if idx_before < 0:
> -            pos_before = pos - 1
> -            idx_before = len(_lists[pos_before]) - 1
> -        else:
> -            pos_before = pos
> +        Runtime complexity: `O(log(n))` -- approximate.
>  
> -        before = _lists[pos_before][idx_before]
> -        if before <= val <= _lists[pos][idx]:
> -            _lists[pos].insert(idx, val)
> -            self._expand(pos)
> -            self._len += 1
> -        else:
> -            msg = '{0!r} not in sort order at index {1}'.format(val, idx)
> -            raise ValueError(msg)
> +        >>> sl = SortedList('abcde')
> +        >>> sl.pop()
> +        'e'
> +        >>> sl.pop(2)
> +        'c'
> +        >>> sl
> +        SortedList(['a', 'b', 'd'])
> +
> +        :param int index: index of value (default -1)
> +        :return: value
> +        :raises IndexError: if index is out of range
>  
> -    def pop(self, idx=-1):
> -        """
> -        Remove and return item at *idx* (default last).  Raises IndexError if
> -        list is empty or index is out of range.  Negative indices are supported,
> -        as for slice indices.
>          """
> -        # pylint: disable=arguments-differ
>          if not self._len:
>              raise IndexError('pop index out of range')
>  
>          _lists = self._lists
>  
> -        if idx == 0:
> +        if index == 0:
>              val = _lists[0][0]
>              self._delete(0, 0)
>              return val
>  
> -        if idx == -1:
> +        if index == -1:
>              pos = len(_lists) - 1
>              loc = len(_lists[pos]) - 1
>              val = _lists[pos][loc]
>              self._delete(pos, loc)
>              return val
>  
> -        if 0 <= idx < len(_lists[0]):
> -            val = _lists[0][idx]
> -            self._delete(0, idx)
> +        if 0 <= index < len(_lists[0]):
> +            val = _lists[0][index]
> +            self._delete(0, index)
>              return val
>  
>          len_last = len(_lists[-1])
>  
> -        if -len_last < idx < 0:
> +        if -len_last < index < 0:
>              pos = len(_lists) - 1
> -            loc = len_last + idx
> +            loc = len_last + index
>              val = _lists[pos][loc]
>              self._delete(pos, loc)
>              return val
>  
> -        pos, idx = self._pos(idx)
> +        pos, idx = self._pos(index)
>          val = _lists[pos][idx]
>          self._delete(pos, idx)
> -
>          return val
>  
> -    def index(self, val, start=None, stop=None):
> -        """
> -        Return the smallest *k* such that L[k] == val and i <= k < j`.  Raises
> -        ValueError if *val* is not present.  *stop* defaults to the end of the
> -        list. *start* defaults to the beginning. Negative indices are supported,
> -        as for slice indices.
> +
> +    def index(self, value, start=None, stop=None):
> +        """Return first index of value in sorted list.
> +
> +        Raise ValueError if `value` is not present.
> +
> +        Index must be between `start` and `stop` for the `value` to be
> +        considered present. The default value, None, for `start` and `stop`
> +        indicate the beginning and end of the sorted list.
> +
> +        Negative indices are supported.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> sl = SortedList('abcde')
> +        >>> sl.index('d')
> +        3
> +        >>> sl.index('z')
> +        Traceback (most recent call last):
> +          ...
> +        ValueError: 'z' is not in list
> +
> +        :param value: value in sorted list
> +        :param int start: start index (default None, start of sorted list)
> +        :param int stop: stop index (default None, end of sorted list)
> +        :return: index of value
> +        :raises ValueError: if value is not present
> +
>          """
> -        # pylint: disable=arguments-differ
>          _len = self._len
>  
>          if not _len:
> -            raise ValueError('{0!r} is not in list'.format(val))
> +            raise ValueError('{0!r} is not in list'.format(value))
>  
>          if start is None:
>              start = 0
> @@ -1275,19 +1423,19 @@ class SortedList(MutableSequence):
>              stop = _len
>  
>          if stop <= start:
> -            raise ValueError('{0!r} is not in list'.format(val))
> +            raise ValueError('{0!r} is not in list'.format(value))
>  
>          _maxes = self._maxes
> -        pos_left = bisect_left(_maxes, val)
> +        pos_left = bisect_left(_maxes, value)
>  
>          if pos_left == len(_maxes):
> -            raise ValueError('{0!r} is not in list'.format(val))
> +            raise ValueError('{0!r} is not in list'.format(value))
>  
>          _lists = self._lists
> -        idx_left = bisect_left(_lists[pos_left], val)
> +        idx_left = bisect_left(_lists[pos_left], value)
>  
> -        if _lists[pos_left][idx_left] != val:
> -            raise ValueError('{0!r} is not in list'.format(val))
> +        if _lists[pos_left][idx_left] != value:
> +            raise ValueError('{0!r} is not in list'.format(value))
>  
>          stop -= 1
>          left = self._loc(pos_left, idx_left)
> @@ -1296,153 +1444,220 @@ class SortedList(MutableSequence):
>              if left <= stop:
>                  return left
>          else:
> -            right = self._bisect_right(val) - 1
> +            right = self._bisect_right(value) - 1
>  
>              if start <= right:
>                  return start
>  
> -        raise ValueError('{0!r} is not in list'.format(val))
> +        raise ValueError('{0!r} is not in list'.format(value))
> +
> +
> +    def __add__(self, other):
> +        """Return new sorted list containing all values in both sequences.
> +
> +        ``sl.__add__(other)`` <==> ``sl + other``
> +
> +        Values in `other` do not need to be in sorted order.
> +
> +        Runtime complexity: `O(n*log(n))`
> +
> +        >>> sl1 = SortedList('bat')
> +        >>> sl2 = SortedList('cat')
> +        >>> sl1 + sl2
> +        SortedList(['a', 'a', 'b', 'c', 't', 't'])
> +
> +        :param other: other iterable
> +        :return: new sorted list
>  
> -    def __add__(self, that):
> -        """
> -        Return a new sorted list containing all the elements in *self* and
> -        *that*. Elements in *that* do not need to be properly ordered with
> -        respect to *self*.
>          """
>          values = reduce(iadd, self._lists, [])
> -        values.extend(that)
> +        values.extend(other)
>          return self.__class__(values)
>  
> -    def __iadd__(self, that):
> -        """
> -        Update *self* to include all values in *that*. Elements in *that* do not
> -        need to be properly ordered with respect to *self*.
> +    __radd__ = __add__
> +
> +
> +    def __iadd__(self, other):
> +        """Update sorted list with values from `other`.
> +
> +        ``sl.__iadd__(other)`` <==> ``sl += other``
> +
> +        Values in `other` do not need to be in sorted order.
> +
> +        Runtime complexity: `O(k*log(n))` -- approximate.
> +
> +        >>> sl = SortedList('bat')
> +        >>> sl += 'cat'
> +        >>> sl
> +        SortedList(['a', 'a', 'b', 'c', 't', 't'])
> +
> +        :param other: other iterable
> +        :return: existing sorted list
> +
>          """
> -        self._update(that)
> +        self._update(other)
>          return self
>  
> -    def __mul__(self, that):
> -        """
> -        Return a new sorted list containing *that* shallow copies of each item
> -        in SortedList.
> +
> +    def __mul__(self, num):
> +        """Return new sorted list with `num` shallow copies of values.
> +
> +        ``sl.__mul__(num)`` <==> ``sl * num``
> +
> +        Runtime complexity: `O(n*log(n))`
> +
> +        >>> sl = SortedList('abc')
> +        >>> sl * 3
> +        SortedList(['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c'])
> +
> +        :param int num: count of shallow copies
> +        :return: new sorted list
> +
>          """
> -        values = reduce(iadd, self._lists, []) * that
> +        values = reduce(iadd, self._lists, []) * num
>          return self.__class__(values)
>  
> -    def __imul__(self, that):
> -        """
> -        Increase the length of the list by appending *that* shallow copies of
> -        each item.
> +    __rmul__ = __mul__
> +
> +
> +    def __imul__(self, num):
> +        """Update the sorted list with `num` shallow copies of values.
> +
> +        ``sl.__imul__(num)`` <==> ``sl *= num``
> +
> +        Runtime complexity: `O(n*log(n))`
> +
> +        >>> sl = SortedList('abc')
> +        >>> sl *= 3
> +        >>> sl
> +        SortedList(['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c'])
> +
> +        :param int num: count of shallow copies
> +        :return: existing sorted list
> +
>          """
> -        values = reduce(iadd, self._lists, []) * that
> +        values = reduce(iadd, self._lists, []) * num
>          self._clear()
>          self._update(values)
>          return self
>  
> -    def _make_cmp(self, seq_op, doc):
> +
> +    def __make_cmp(seq_op, symbol, doc):
>          "Make comparator method."
> -        def comparer(self, that):
> +        def comparer(self, other):
>              "Compare method for sorted list and sequence."
> -            # pylint: disable=protected-access
> -            if not isinstance(that, Sequence):
> +            if not isinstance(other, Sequence):
>                  return NotImplemented
>  
>              self_len = self._len
> -            len_that = len(that)
> +            len_other = len(other)
>  
> -            if self_len != len_that:
> -                if seq_op is op.eq:
> +            if self_len != len_other:
> +                if seq_op is eq:
>                      return False
> -                if seq_op is op.ne:
> +                if seq_op is ne:
>                      return True
>  
> -            for alpha, beta in zip(self, that):
> +            for alpha, beta in zip(self, other):
>                  if alpha != beta:
>                      return seq_op(alpha, beta)
>  
> -            return seq_op(self_len, len_that)
> +            return seq_op(self_len, len_other)
> +
> +        seq_op_name = seq_op.__name__
> +        comparer.__name__ = '__{0}__'.format(seq_op_name)
> +        doc_str = """Return true if and only if sorted list is {0} `other`.
> +
> +        ``sl.__{1}__(other)`` <==> ``sl {2} other``
> +
> +        Comparisons use lexicographical order as with sequences.
> +
> +        Runtime complexity: `O(n)`
>  
> -        comparer.__name__ = '__{0}__'.format(seq_op.__name__)
> -        doc_str = 'Return `True` if and only if Sequence is {0} `that`.'
> -        comparer.__doc__ = doc_str.format(doc)
> +        :param other: `other` sequence
> +        :return: true if sorted list is {0} `other`
>  
> +        """
> +        comparer.__doc__ = dedent(doc_str.format(doc, seq_op_name, symbol))
>          return comparer
>  
> -    __eq__ = _make_cmp(None, op.eq, 'equal to')
> -    __ne__ = _make_cmp(None, op.ne, 'not equal to')
> -    __lt__ = _make_cmp(None, op.lt, 'less than')
> -    __gt__ = _make_cmp(None, op.gt, 'greater than')
> -    __le__ = _make_cmp(None, op.le, 'less than or equal to')
> -    __ge__ = _make_cmp(None, op.ge, 'greater than or equal to')
>  
> -    @recursive_repr
> -    def __repr__(self):
> -        """Return string representation of sequence."""
> -        return '{0}({1!r})'.format(type(self).__name__, list(self))
> +    __eq__ = __make_cmp(eq, '==', 'equal to')
> +    __ne__ = __make_cmp(ne, '!=', 'not equal to')
> +    __lt__ = __make_cmp(lt, '<', 'less than')
> +    __gt__ = __make_cmp(gt, '>', 'greater than')
> +    __le__ = __make_cmp(le, '<=', 'less than or equal to')
> +    __ge__ = __make_cmp(ge, '>=', 'greater than or equal to')
> +    __make_cmp = staticmethod(__make_cmp)
>  
> -    def _check(self):
> -        try:
> -            # Check load parameters.
>  
> -            assert self._load >= 4
> -            assert self._half == (self._load >> 1)
> -            assert self._dual == (self._load << 1)
> +    def __reduce__(self):
> +        values = reduce(iadd, self._lists, [])
> +        return (type(self), (values,))
>  
> -            # Check empty sorted list case.
>  
> -            if self._maxes == []:
> -                assert self._lists == []
> -                return
> +    @recursive_repr()
> +    def __repr__(self):
> +        """Return string representation of sorted list.
>  
> -            assert self._maxes and self._lists
> +        ``sl.__repr__()`` <==> ``repr(sl)``
>  
> -            # Check all sublists are sorted.
> +        :return: string representation
>  
> -            assert all(sublist[pos - 1] <= sublist[pos]
> -                       for sublist in self._lists
> -                       for pos in range(1, len(sublist)))
> +        """
> +        return '{0}({1!r})'.format(type(self).__name__, list(self))
>  
> -            # Check beginning/end of sublists are sorted.
>  
> -            for pos in range(1, len(self._lists)):
> -                assert self._lists[pos - 1][-1] <= self._lists[pos][0]
> +    def _check(self):
> +        """Check invariants of sorted list.
>  
> -            # Check length of _maxes and _lists match.
> +        Runtime complexity: `O(n)`
>  
> +        """
> +        try:
> +            assert self._load >= 4
>              assert len(self._maxes) == len(self._lists)
> +            assert self._len == sum(len(sublist) for sublist in self._lists)
>  
> -            # Check _maxes is a map of _lists.
> +            # Check all sublists are sorted.
>  
> -            assert all(self._maxes[pos] == self._lists[pos][-1]
> -                       for pos in range(len(self._maxes)))
> +            for sublist in self._lists:
> +                for pos in range(1, len(sublist)):
> +                    assert sublist[pos - 1] <= sublist[pos]
>  
> -            # Check load level is less than _dual.
> +            # Check beginning/end of sublists are sorted.
>  
> -            assert all(len(sublist) <= self._dual for sublist in self._lists)
> +            for pos in range(1, len(self._lists)):
> +                assert self._lists[pos - 1][-1] <= self._lists[pos][0]
>  
> -            # Check load level is greater than _half for all
> -            # but the last sublist.
> +            # Check _maxes index is the last value of each sublist.
>  
> -            assert all(len(self._lists[pos]) >= self._half
> -                       for pos in range(0, len(self._lists) - 1))
> +            for pos in range(len(self._maxes)):
> +                assert self._maxes[pos] == self._lists[pos][-1]
>  
> -            # Check length.
> +            # Check sublist lengths are less than double load-factor.
>  
> -            assert self._len == sum(len(sublist) for sublist in self._lists)
> +            double = self._load << 1
> +            assert all(len(sublist) <= double for sublist in self._lists)
> +
> +            # Check sublist lengths are greater than half load-factor for all
> +            # but the last sublist.
>  
> -            # Check index.
> +            half = self._load >> 1
> +            for pos in range(0, len(self._lists) - 1):
> +                assert len(self._lists[pos]) >= half
>  
>              if self._index:
> -                assert len(self._index) == self._offset + len(self._lists)
>                  assert self._len == self._index[0]
> +                assert len(self._index) == self._offset + len(self._lists)
> +
> +                # Check index leaf nodes equal length of sublists.
>  
> -                def test_offset_pos(pos):
> -                    "Test positional indexing offset."
> -                    from_index = self._index[self._offset + pos]
> -                    return from_index == len(self._lists[pos])
> +                for pos in range(len(self._lists)):
> +                    leaf = self._index[self._offset + pos]
> +                    assert leaf == len(self._lists[pos])
>  
> -                assert all(test_offset_pos(pos)
> -                           for pos in range(len(self._lists)))
> +                # Check index branch nodes are the sum of their children.
>  
>                  for pos in range(self._offset):
>                      child = (pos << 1) + 1
> @@ -1452,16 +1667,11 @@ class SortedList(MutableSequence):
>                          assert self._index[pos] == self._index[child]
>                      else:
>                          child_sum = self._index[child] + self._index[child + 1]
> -                        assert self._index[pos] == child_sum
> -
> +                        assert child_sum == self._index[pos]
>          except:
> -            import sys
> -            import traceback
> -
>              traceback.print_exc(file=sys.stdout)
> -
>              print('len', self._len)
> -            print('load', self._load, self._half, self._dual)
> +            print('load', self._load)
>              print('offset', self._offset)
>              print('len_index', len(self._index))
>              print('index', self._index)
> @@ -1469,55 +1679,92 @@ class SortedList(MutableSequence):
>              print('maxes', self._maxes)
>              print('len_lists', len(self._lists))
>              print('lists', self._lists)
> -
>              raise
>  
> +
>  def identity(value):
>      "Identity function."
>      return value
>  
> -class SortedListWithKey(SortedList):
> -    """
> -    SortedListWithKey provides most of the same methods as a list but keeps
> -    the items in sorted order.
> +
> +class SortedKeyList(SortedList):
> +    """Sorted-key list is a subtype of sorted list.
> +
> +    The sorted-key list maintains values in comparison order based on the
> +    result of a key function applied to every value.
> +
> +    All the same methods that are available in :class:`SortedList` are also
> +    available in :class:`SortedKeyList`.
> +
> +    Additional methods provided:
> +
> +    * :attr:`SortedKeyList.key`
> +    * :func:`SortedKeyList.bisect_key_left`
> +    * :func:`SortedKeyList.bisect_key_right`
> +    * :func:`SortedKeyList.irange_key`
> +
> +    Some examples below use:
> +
> +    >>> from operator import neg
> +    >>> neg
> +    <built-in function neg>
> +    >>> neg(1)
> +    -1
> +
>      """
> -    # pylint: disable=too-many-ancestors,abstract-method
>      def __init__(self, iterable=None, key=identity):
> -        """SortedListWithKey provides most of the same methods as list but keeps the
> -        items in sorted order.
> +        """Initialize sorted-key list instance.
>  
> -        An optional *iterable* provides an initial series of items to populate
> -        the SortedListWithKey.
> +        Optional `iterable` argument provides an initial iterable of values to
> +        initialize the sorted-key list.
>  
> -        An optional *key* argument defines a callable that, like the `key`
> +        Optional `key` argument defines a callable that, like the `key`
>          argument to Python's `sorted` function, extracts a comparison key from
> -        each element. The default is the identity function.
> +        each value. The default is the identity function.
> +
> +        Runtime complexity: `O(n*log(n))`
> +
> +        >>> from operator import neg
> +        >>> skl = SortedKeyList(key=neg)
> +        >>> skl
> +        SortedKeyList([], key=<built-in function neg>)
> +        >>> skl = SortedKeyList([3, 1, 2], key=neg)
> +        >>> skl
> +        SortedKeyList([3, 2, 1], key=<built-in function neg>)
> +
> +        :param iterable: initial values (optional)
> +        :param key: function used to extract comparison key (optional)
> +
>          """
> -        # pylint: disable=super-init-not-called
> +        self._key = key
>          self._len = 0
> +        self._load = self.DEFAULT_LOAD_FACTOR
>          self._lists = []
>          self._keys = []
>          self._maxes = []
>          self._index = []
> -        self._key = key
> -        self._load = LOAD
> -        self._half = LOAD >> 1
> -        self._dual = LOAD << 1
>          self._offset = 0
>  
>          if iterable is not None:
>              self._update(iterable)
>  
> +
>      def __new__(cls, iterable=None, key=identity):
>          return object.__new__(cls)
>  
> +
>      @property
>      def key(self):
> -        """Key function used to extract comparison key for sorting."""
> +        "Function used to extract comparison key from values."
>          return self._key
>  
> +
>      def clear(self):
> -        """Remove all the elements from the list."""
> +        """Remove all values from sorted-key list.
> +
> +        Runtime complexity: `O(n)`
> +
> +        """
>          self._len = 0
>          del self._lists[:]
>          del self._keys[:]
> @@ -1526,48 +1773,65 @@ class SortedListWithKey(SortedList):
>  
>      _clear = clear
>  
> -    def add(self, val):
> -        """Add the element *val* to the list."""
> +
> +    def add(self, value):
> +        """Add `value` to sorted-key list.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> from operator import neg
> +        >>> skl = SortedKeyList(key=neg)
> +        >>> skl.add(3)
> +        >>> skl.add(1)
> +        >>> skl.add(2)
> +        >>> skl
> +        SortedKeyList([3, 2, 1], key=<built-in function neg>)
> +
> +        :param value: value to add to sorted-key list
> +
> +        """
>          _lists = self._lists
>          _keys = self._keys
>          _maxes = self._maxes
>  
> -        key = self._key(val)
> +        key = self._key(value)
>  
>          if _maxes:
>              pos = bisect_right(_maxes, key)
>  
>              if pos == len(_maxes):
>                  pos -= 1
> -                _lists[pos].append(val)
> +                _lists[pos].append(value)
>                  _keys[pos].append(key)
>                  _maxes[pos] = key
>              else:
>                  idx = bisect_right(_keys[pos], key)
> -                _lists[pos].insert(idx, val)
> +                _lists[pos].insert(idx, value)
>                  _keys[pos].insert(idx, key)
>  
>              self._expand(pos)
>          else:
> -            _lists.append([val])
> +            _lists.append([value])
>              _keys.append([key])
>              _maxes.append(key)
>  
>          self._len += 1
>  
> +
>      def _expand(self, pos):
> -        """Splits sublists that are more than double the load level.
> +        """Split sublists with length greater than double the load-factor.
>  
>          Updates the index when the sublist length is less than double the load
>          level. This requires incrementing the nodes in a traversal from the
> -        leaf node to the root. For an example traversal see self._loc.
> +        leaf node to the root. For an example traversal see
> +        ``SortedList._loc``.
>  
>          """
>          _lists = self._lists
>          _keys = self._keys
>          _index = self._index
>  
> -        if len(_keys[pos]) > self._dual:
> +        if len(_keys[pos]) > (self._load << 1):
>              _maxes = self._maxes
>              _load = self._load
>  
> @@ -1592,8 +1856,21 @@ class SortedListWithKey(SortedList):
>                      child = (child - 1) >> 1
>                  _index[0] += 1
>  
> +
>      def update(self, iterable):
> -        """Update the list by adding all elements from *iterable*."""
> +        """Update sorted-key list by adding all values from `iterable`.
> +
> +        Runtime complexity: `O(k*log(n))` -- approximate.
> +
> +        >>> from operator import neg
> +        >>> skl = SortedKeyList(key=neg)
> +        >>> skl.update([3, 1, 2])
> +        >>> skl
> +        SortedKeyList([3, 2, 1], key=<built-in function neg>)
> +
> +        :param iterable: iterable of values to add
> +
> +        """
>          _lists = self._lists
>          _keys = self._keys
>          _maxes = self._maxes
> @@ -1601,7 +1878,8 @@ class SortedListWithKey(SortedList):
>  
>          if _maxes:
>              if len(values) * 4 >= self._len:
> -                values.extend(chain.from_iterable(_lists))
> +                _lists.append(values)
> +                values = reduce(iadd, _lists, [])
>                  values.sort(key=self._key)
>                  self._clear()
>              else:
> @@ -1620,14 +1898,29 @@ class SortedListWithKey(SortedList):
>  
>      _update = update
>  
> -    def __contains__(self, val):
> -        """Return True if and only if *val* is an element in the list."""
> +
> +    def __contains__(self, value):
> +        """Return true if `value` is an element of the sorted-key list.
> +
> +        ``skl.__contains__(value)`` <==> ``value in skl``
> +
> +        Runtime complexity: `O(log(n))`
> +
> +        >>> from operator import neg
> +        >>> skl = SortedKeyList([1, 2, 3, 4, 5], key=neg)
> +        >>> 3 in skl
> +        True
> +
> +        :param value: search for value in sorted-key list
> +        :return: true if `value` in sorted-key list
> +
> +        """
>          _maxes = self._maxes
>  
>          if not _maxes:
>              return False
>  
> -        key = self._key(val)
> +        key = self._key(value)
>          pos = bisect_left(_maxes, key)
>  
>          if pos == len(_maxes):
> @@ -1644,7 +1937,7 @@ class SortedListWithKey(SortedList):
>          while True:
>              if _keys[pos][idx] != key:
>                  return False
> -            if _lists[pos][idx] == val:
> +            if _lists[pos][idx] == value:
>                  return True
>              idx += 1
>              if idx == len_sublist:
> @@ -1654,18 +1947,30 @@ class SortedListWithKey(SortedList):
>                  len_sublist = len(_keys[pos])
>                  idx = 0
>  
> -    def discard(self, val):
> -        """
> -        Remove the first occurrence of *val*.
>  
> -        If *val* is not a member, does nothing.
> +    def discard(self, value):
> +        """Remove `value` from sorted-key list if it is a member.
> +
> +        If `value` is not a member, do nothing.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> from operator import neg
> +        >>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg)
> +        >>> skl.discard(1)
> +        >>> skl.discard(0)
> +        >>> skl == [5, 4, 3, 2]
> +        True
> +
> +        :param value: `value` to discard from sorted-key list
> +
>          """
>          _maxes = self._maxes
>  
>          if not _maxes:
>              return
>  
> -        key = self._key(val)
> +        key = self._key(value)
>          pos = bisect_left(_maxes, key)
>  
>          if pos == len(_maxes):
> @@ -1680,7 +1985,7 @@ class SortedListWithKey(SortedList):
>          while True:
>              if _keys[pos][idx] != key:
>                  return
> -            if _lists[pos][idx] == val:
> +            if _lists[pos][idx] == value:
>                  self._delete(pos, idx)
>                  return
>              idx += 1
> @@ -1691,22 +1996,38 @@ class SortedListWithKey(SortedList):
>                  len_sublist = len(_keys[pos])
>                  idx = 0
>  
> -    def remove(self, val):
> -        """
> -        Remove first occurrence of *val*.
>  
> -        Raises ValueError if *val* is not present.
> +    def remove(self, value):
> +        """Remove `value` from sorted-key list; `value` must be a member.
> +
> +        If `value` is not a member, raise ValueError.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> from operator import neg
> +        >>> skl = SortedKeyList([1, 2, 3, 4, 5], key=neg)
> +        >>> skl.remove(5)
> +        >>> skl == [4, 3, 2, 1]
> +        True
> +        >>> skl.remove(0)
> +        Traceback (most recent call last):
> +          ...
> +        ValueError: 0 not in list
> +
> +        :param value: `value` to remove from sorted-key list
> +        :raises ValueError: if `value` is not in sorted-key list
> +
>          """
>          _maxes = self._maxes
>  
>          if not _maxes:
> -            raise ValueError('{0!r} not in list'.format(val))
> +            raise ValueError('{0!r} not in list'.format(value))
>  
> -        key = self._key(val)
> +        key = self._key(value)
>          pos = bisect_left(_maxes, key)
>  
>          if pos == len(_maxes):
> -            raise ValueError('{0!r} not in list'.format(val))
> +            raise ValueError('{0!r} not in list'.format(value))
>  
>          _lists = self._lists
>          _keys = self._keys
> @@ -1716,27 +2037,32 @@ class SortedListWithKey(SortedList):
>  
>          while True:
>              if _keys[pos][idx] != key:
> -                raise ValueError('{0!r} not in list'.format(val))
> -            if _lists[pos][idx] == val:
> +                raise ValueError('{0!r} not in list'.format(value))
> +            if _lists[pos][idx] == value:
>                  self._delete(pos, idx)
>                  return
>              idx += 1
>              if idx == len_sublist:
>                  pos += 1
>                  if pos == len_keys:
> -                    raise ValueError('{0!r} not in list'.format(val))
> +                    raise ValueError('{0!r} not in list'.format(value))
>                  len_sublist = len(_keys[pos])
>                  idx = 0
>  
> +
>      def _delete(self, pos, idx):
> -        """
> -        Delete the item at the given (pos, idx).
> +        """Delete value at the given `(pos, idx)`.
>  
>          Combines lists that are less than half the load level.
>  
>          Updates the index when the sublist length is more than half the load
> -        level. This requires decrementing the nodes in a traversal from the leaf
> -        node to the root. For an example traversal see self._loc.
> +        level. This requires decrementing the nodes in a traversal from the
> +        leaf node to the root. For an example traversal see
> +        ``SortedList._loc``.
> +
> +        :param int pos: lists index
> +        :param int idx: sublist index
> +
>          """
>          _lists = self._lists
>          _keys = self._keys
> @@ -1751,8 +2077,7 @@ class SortedListWithKey(SortedList):
>  
>          len_keys_pos = len(keys_pos)
>  
> -        if len_keys_pos > self._half:
> -
> +        if len_keys_pos > (self._load >> 1):
>              _maxes[pos] = keys_pos[-1]
>  
>              if _index:
> @@ -1761,9 +2086,7 @@ class SortedListWithKey(SortedList):
>                      _index[child] -= 1
>                      child = (child - 1) >> 1
>                  _index[0] -= 1
> -
>          elif len(_keys) > 1:
> -
>              if not pos:
>                  pos += 1
>  
> @@ -1778,220 +2101,78 @@ class SortedListWithKey(SortedList):
>              del _index[:]
>  
>              self._expand(prev)
> -
>          elif len_keys_pos:
> -
>              _maxes[pos] = keys_pos[-1]
> -
>          else:
> -
>              del _lists[pos]
>              del _keys[pos]
>              del _maxes[pos]
>              del _index[:]
>  
> -    def _check_order(self, idx, key, val):
> -        # pylint: disable=arguments-differ
> -        _len = self._len
> -        _keys = self._keys
> -
> -        pos, loc = self._pos(idx)
> -
> -        if idx < 0:
> -            idx += _len
> -
> -        # Check that the inserted value is not less than the
> -        # previous value.
> -
> -        if idx > 0:
> -            idx_prev = loc - 1
> -            pos_prev = pos
> -
> -            if idx_prev < 0:
> -                pos_prev -= 1
> -                idx_prev = len(_keys[pos_prev]) - 1
> -
> -            if _keys[pos_prev][idx_prev] > key:
> -                msg = '{0!r} not in sort order at index {1}'.format(val, idx)
> -                raise ValueError(msg)
> -
> -        # Check that the inserted value is not greater than
> -        # the previous value.
> -
> -        if idx < (_len - 1):
> -            idx_next = loc + 1
> -            pos_next = pos
> -
> -            if idx_next == len(_keys[pos_next]):
> -                pos_next += 1
> -                idx_next = 0
> -
> -            if _keys[pos_next][idx_next] < key:
> -                msg = '{0!r} not in sort order at index {1}'.format(val, idx)
> -                raise ValueError(msg)
> -
> -    def __setitem__(self, index, value):
> -        """Replace the item at position *index* with *value*.
> -
> -        Supports slice notation. Raises a :exc:`ValueError` if the sort order
> -        would be violated. When used with a slice and iterable, the
> -        :exc:`ValueError` is raised before the list is mutated if the sort
> -        order would be violated by the operation.
> -
> -        """
> -        # pylint: disable=too-many-locals
> -        _lists = self._lists
> -        _keys = self._keys
> -        _maxes = self._maxes
> -        _check_order = self._check_order
> -        _pos = self._pos
> -
> -        if isinstance(index, slice):
> -            _len = self._len
> -            start, stop, step = index.indices(_len)
> -            indices = range(start, stop, step)
> -
> -            # Copy value to avoid aliasing issues with self and cases where an
> -            # iterator is given.
> -
> -            values = tuple(value)
> -
> -            if step != 1:
> -                if len(values) != len(indices):
> -                    raise ValueError(
> -                        'attempt to assign sequence of size %s'
> -                        ' to extended slice of size %s'
> -                        % (len(values), len(indices)))
> -
> -                # Keep a log of values that are set so that we can
> -                # roll back changes if ordering is violated.
> -
> -                log = []
> -                _append = log.append
> -
> -                for idx, val in zip(indices, values):
> -                    pos, loc = _pos(idx)
> -                    key = self._key(val)
> -                    _append((idx, _keys[pos][loc], key, _lists[pos][loc], val))
> -                    _keys[pos][loc] = key
> -                    _lists[pos][loc] = val
> -                    if len(_keys[pos]) == (loc + 1):
> -                        _maxes[pos] = key
> -
> -                try:
> -                    # Validate ordering of new values.
> -
> -                    for idx, oldkey, newkey, oldval, newval in log:
> -                        _check_order(idx, newkey, newval)
> -
> -                except ValueError:
> -
> -                    # Roll back changes from log.
> -
> -                    for idx, oldkey, newkey, oldval, newval in log:
> -                        pos, loc = _pos(idx)
> -                        _keys[pos][loc] = oldkey
> -                        _lists[pos][loc] = oldval
> -                        if len(_keys[pos]) == (loc + 1):
> -                            _maxes[pos] = oldkey
> -
> -                    raise
> -            else:
> -                if start == 0 and stop == self._len:
> -                    self._clear()
> -                    return self._update(values)
> -
> -                if stop < start:
> -                    # When calculating indices, stop may be less than start.
> -                    # For example: ...[5:3:1] results in slice(5, 3, 1) which
> -                    # is a valid but not useful stop index.
> -                    stop = start
> -
> -                if values:
> -
> -                    # Check that given values are ordered properly.
> -
> -                    keys = tuple(map(self._key, values))
> -                    alphas = iter(keys)
> -                    betas = iter(keys)
> -                    next(betas)
> -                    pairs = zip(alphas, betas)
> -
> -                    if not all(alpha <= beta for alpha, beta in pairs):
> -                        raise ValueError('given values not in sort order')
> -
> -                    # Check ordering in context of sorted list.
> -
> -                    if start:
> -                        pos, loc = _pos(start - 1)
> -                        if _keys[pos][loc] > keys[0]:
> -                            msg = '{0!r} not in sort order at index {1}'.format(
> -                                values[0], start)
> -                            raise ValueError(msg)
> -
> -                    if stop != _len:
> -                        pos, loc = _pos(stop)
> -                        if _keys[pos][loc] < keys[-1]:
> -                            msg = '{0!r} not in sort order at index {1}'.format(
> -                                values[-1], stop)
> -                            raise ValueError(msg)
> -
> -                # Delete the existing values.
> -
> -                self._delitem(index)
> -
> -                # Insert the new values.
> -
> -                _insert = self.insert
> -                for idx, val in enumerate(values):
> -                    _insert(start + idx, val)
> -        else:
> -            pos, loc = _pos(index)
> -            key = self._key(value)
> -            _check_order(index, key, value)
> -            _lists[pos][loc] = value
> -            _keys[pos][loc] = key
> -            if len(_lists[pos]) == (loc + 1):
> -                _maxes[pos] = key
>  
>      def irange(self, minimum=None, maximum=None, inclusive=(True, True),
>                 reverse=False):
> -        """
> -        Create an iterator of values between `minimum` and `maximum`.
> -
> -        `inclusive` is a pair of booleans that indicates whether the minimum
> -        and maximum ought to be included in the range, respectively. The
> -        default is (True, True) such that the range is inclusive of both
> -        minimum and maximum.
> +        """Create an iterator of values between `minimum` and `maximum`.
>  
>          Both `minimum` and `maximum` default to `None` which is automatically
> -        inclusive of the start and end of the list, respectively.
> +        inclusive of the beginning and end of the sorted-key list.
> +
> +        The argument `inclusive` is a pair of booleans that indicates whether
> +        the minimum and maximum ought to be included in the range,
> +        respectively. The default is ``(True, True)`` such that the range is
> +        inclusive of both minimum and maximum.
>  
>          When `reverse` is `True` the values are yielded from the iterator in
>          reverse order; `reverse` defaults to `False`.
> +
> +        >>> from operator import neg
> +        >>> skl = SortedKeyList([11, 12, 13, 14, 15], key=neg)
> +        >>> it = skl.irange(14.5, 11.5)
> +        >>> list(it)
> +        [14, 13, 12]
> +
> +        :param minimum: minimum value to start iterating
> +        :param maximum: maximum value to stop iterating
> +        :param inclusive: pair of booleans
> +        :param bool reverse: yield values in reverse order
> +        :return: iterator
> +
>          """
> -        minimum = self._key(minimum) if minimum is not None else None
> -        maximum = self._key(maximum) if maximum is not None else None
> +        min_key = self._key(minimum) if minimum is not None else None
> +        max_key = self._key(maximum) if maximum is not None else None
>          return self._irange_key(
> -            min_key=minimum, max_key=maximum,
> +            min_key=min_key, max_key=max_key,
>              inclusive=inclusive, reverse=reverse,
>          )
>  
> +
>      def irange_key(self, min_key=None, max_key=None, inclusive=(True, True),
>                     reverse=False):
> -        """
> -        Create an iterator of values between `min_key` and `max_key`.
> -
> -        `inclusive` is a pair of booleans that indicates whether the min_key
> -        and max_key ought to be included in the range, respectively. The
> -        default is (True, True) such that the range is inclusive of both
> -        `min_key` and `max_key`.
> +        """Create an iterator of values between `min_key` and `max_key`.
>  
>          Both `min_key` and `max_key` default to `None` which is automatically
> -        inclusive of the start and end of the list, respectively.
> +        inclusive of the beginning and end of the sorted-key list.
> +
> +        The argument `inclusive` is a pair of booleans that indicates whether
> +        the minimum and maximum ought to be included in the range,
> +        respectively. The default is ``(True, True)`` such that the range is
> +        inclusive of both minimum and maximum.
>  
>          When `reverse` is `True` the values are yielded from the iterator in
>          reverse order; `reverse` defaults to `False`.
> +
> +        >>> from operator import neg
> +        >>> skl = SortedKeyList([11, 12, 13, 14, 15], key=neg)
> +        >>> it = skl.irange_key(-14, -12)
> +        >>> list(it)
> +        [14, 13, 12]
> +
> +        :param min_key: minimum key to start iterating
> +        :param max_key: maximum key to stop iterating
> +        :param inclusive: pair of booleans
> +        :param bool reverse: yield values in reverse order
> +        :return: iterator
> +
>          """
>          _maxes = self._maxes
>  
> @@ -2050,29 +2231,71 @@ class SortedListWithKey(SortedList):
>  
>      _irange_key = irange_key
>  
> -    def bisect_left(self, val):
> -        """
> -        Similar to the *bisect* module in the standard library, this returns an
> -        appropriate index to insert *val*. If *val* is already present, the
> -        insertion point will be before (to the left of) any existing entries.
> -        """
> -        return self._bisect_key_left(self._key(val))
>  
> -    def bisect_right(self, val):
> +    def bisect_left(self, value):
> +        """Return an index to insert `value` in the sorted-key list.
> +
> +        If the `value` is already present, the insertion point will be before
> +        (to the left of) any existing values.
> +
> +        Similar to the `bisect` module in the standard library.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> from operator import neg
> +        >>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg)
> +        >>> skl.bisect_left(1)
> +        4
> +
> +        :param value: insertion index of value in sorted-key list
> +        :return: index
> +
>          """
> -        Same as *bisect_left*, but if *val* is already present, the insertion
> -        point will be after (to the right of) any existing entries.
> +        return self._bisect_key_left(self._key(value))
> +
> +
> +    def bisect_right(self, value):
> +        """Return an index to insert `value` in the sorted-key list.
> +
> +        Similar to `bisect_left`, but if `value` is already present, the
> +        insertion point will be after (to the right of) any existing values.
> +
> +        Similar to the `bisect` module in the standard library.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> from operator import neg
> +        >>> skl = SortedList([5, 4, 3, 2, 1], key=neg)
> +        >>> skl.bisect_right(1)
> +        5
> +
> +        :param value: insertion index of value in sorted-key list
> +        :return: index
> +
>          """
> -        return self._bisect_key_right(self._key(val))
> +        return self._bisect_key_right(self._key(value))
>  
>      bisect = bisect_right
>  
> +
>      def bisect_key_left(self, key):
> -        """
> -        Similar to the *bisect* module in the standard library, this returns an
> -        appropriate index to insert a value with a given *key*. If values with
> -        *key* are already present, the insertion point will be before (to the
> -        left of) any existing entries.
> +        """Return an index to insert `key` in the sorted-key list.
> +
> +        If the `key` is already present, the insertion point will be before (to
> +        the left of) any existing keys.
> +
> +        Similar to the `bisect` module in the standard library.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> from operator import neg
> +        >>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg)
> +        >>> skl.bisect_key_left(-1)
> +        4
> +
> +        :param key: insertion index of key in sorted-key list
> +        :return: index
> +
>          """
>          _maxes = self._maxes
>  
> @@ -2090,10 +2313,25 @@ class SortedListWithKey(SortedList):
>  
>      _bisect_key_left = bisect_key_left
>  
> +
>      def bisect_key_right(self, key):
> -        """
> -        Same as *bisect_key_left*, but if *key* is already present, the insertion
> -        point will be after (to the right of) any existing entries.
> +        """Return an index to insert `key` in the sorted-key list.
> +
> +        Similar to `bisect_key_left`, but if `key` is already present, the
> +        insertion point will be after (to the right of) any existing keys.
> +
> +        Similar to the `bisect` module in the standard library.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> from operator import neg
> +        >>> skl = SortedList([5, 4, 3, 2, 1], key=neg)
> +        >>> skl.bisect_key_right(-1)
> +        5
> +
> +        :param key: insertion index of key in sorted-key list
> +        :return: index
> +
>          """
>          _maxes = self._maxes
>  
> @@ -2112,14 +2350,27 @@ class SortedListWithKey(SortedList):
>      bisect_key = bisect_key_right
>      _bisect_key_right = bisect_key_right
>  
> -    def count(self, val):
> -        """Return the number of occurrences of *val* in the list."""
> +
> +    def count(self, value):
> +        """Return number of occurrences of `value` in the sorted-key list.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> from operator import neg
> +        >>> skl = SortedKeyList([4, 4, 4, 4, 3, 3, 3, 2, 2, 1], key=neg)
> +        >>> skl.count(2)
> +        2
> +
> +        :param value: value to count in sorted-key list
> +        :return: count
> +
> +        """
>          _maxes = self._maxes
>  
>          if not _maxes:
>              return 0
>  
> -        key = self._key(val)
> +        key = self._key(value)
>          pos = bisect_left(_maxes, key)
>  
>          if pos == len(_maxes):
> @@ -2135,7 +2386,7 @@ class SortedListWithKey(SortedList):
>          while True:
>              if _keys[pos][idx] != key:
>                  return total
> -            if _lists[pos][idx] == val:
> +            if _lists[pos][idx] == value:
>                  total += 1
>              idx += 1
>              if idx == len_sublist:
> @@ -2145,176 +2396,53 @@ class SortedListWithKey(SortedList):
>                  len_sublist = len(_keys[pos])
>                  idx = 0
>  
> -    def copy(self):
> -        """Return a shallow copy of the sorted list."""
> -        return self.__class__(self, key=self._key)
> -
> -    __copy__ = copy
>  
> -    def append(self, val):
> -        """
> -        Append the element *val* to the list. Raises a ValueError if the *val*
> -        would violate the sort order.
> -        """
> -        # pylint: disable=arguments-differ
> -        _lists = self._lists
> -        _keys = self._keys
> -        _maxes = self._maxes
> -        key = self._key(val)
> -
> -        if not _maxes:
> -            _maxes.append(key)
> -            _keys.append([key])
> -            _lists.append([val])
> -            self._len = 1
> -            return
> -
> -        pos = len(_keys) - 1
> +    def copy(self):
> +        """Return a shallow copy of the sorted-key list.
>  
> -        if key < _keys[pos][-1]:
> -            msg = '{0!r} not in sort order at index {1}'.format(val, self._len)
> -            raise ValueError(msg)
> +        Runtime complexity: `O(n)`
>  
> -        _lists[pos].append(val)
> -        _keys[pos].append(key)
> -        _maxes[pos] = key
> -        self._len += 1
> -        self._expand(pos)
> +        :return: new sorted-key list
>  
> -    def extend(self, values):
>          """
> -        Extend the list by appending all elements from the *values*. Raises a
> -        ValueError if the sort order would be violated.
> -        """
> -        _lists = self._lists
> -        _keys = self._keys
> -        _maxes = self._maxes
> -        _load = self._load
> -
> -        if not isinstance(values, list):
> -            values = list(values)
> -
> -        keys = list(map(self._key, values))
> +        return self.__class__(self, key=self._key)
>  
> -        if any(keys[pos - 1] > keys[pos]
> -               for pos in range(1, len(keys))):
> -            raise ValueError('given sequence not in sort order')
> +    __copy__ = copy
>  
> -        offset = 0
>  
> -        if _maxes:
> -            if keys[0] < _keys[-1][-1]:
> -                msg = '{0!r} not in sort order at index {1}'.format(values[0], self._len)
> -                raise ValueError(msg)
> +    def index(self, value, start=None, stop=None):
> +        """Return first index of value in sorted-key list.
>  
> -            if len(_keys[-1]) < self._half:
> -                _lists[-1].extend(values[:_load])
> -                _keys[-1].extend(keys[:_load])
> -                _maxes[-1] = _keys[-1][-1]
> -                offset = _load
> +        Raise ValueError if `value` is not present.
>  
> -        len_keys = len(_keys)
> +        Index must be between `start` and `stop` for the `value` to be
> +        considered present. The default value, None, for `start` and `stop`
> +        indicate the beginning and end of the sorted-key list.
>  
> -        for idx in range(offset, len(keys), _load):
> -            _lists.append(values[idx:(idx + _load)])
> -            _keys.append(keys[idx:(idx + _load)])
> -            _maxes.append(_keys[-1][-1])
> +        Negative indices are supported.
>  
> -        _index = self._index
> +        Runtime complexity: `O(log(n))` -- approximate.
>  
> -        if len_keys == len(_keys):
> -            len_index = len(_index)
> -            if len_index > 0:
> -                len_values = len(values)
> -                child = len_index - 1
> -                while child:
> -                    _index[child] += len_values
> -                    child = (child - 1) >> 1
> -                _index[0] += len_values
> -        else:
> -            del _index[:]
> +        >>> from operator import neg
> +        >>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg)
> +        >>> skl.index(2)
> +        3
> +        >>> skl.index(0)
> +        Traceback (most recent call last):
> +          ...
> +        ValueError: 0 is not in list
>  
> -        self._len += len(values)
> +        :param value: value in sorted-key list
> +        :param int start: start index (default None, start of sorted-key list)
> +        :param int stop: stop index (default None, end of sorted-key list)
> +        :return: index of value
> +        :raises ValueError: if value is not present
>  
> -    def insert(self, idx, val):
> -        """
> -        Insert the element *val* into the list at *idx*. Raises a ValueError if
> -        the *val* at *idx* would violate the sort order.
> -        """
> -        _len = self._len
> -        _lists = self._lists
> -        _keys = self._keys
> -        _maxes = self._maxes
> -
> -        if idx < 0:
> -            idx += _len
> -        if idx < 0:
> -            idx = 0
> -        if idx > _len:
> -            idx = _len
> -
> -        key = self._key(val)
> -
> -        if not _maxes:
> -            self._len = 1
> -            _lists.append([val])
> -            _keys.append([key])
> -            _maxes.append(key)
> -            return
> -
> -        if not idx:
> -            if key > _keys[0][0]:
> -                msg = '{0!r} not in sort order at index {1}'.format(val, 0)
> -                raise ValueError(msg)
> -            else:
> -                self._len += 1
> -                _lists[0].insert(0, val)
> -                _keys[0].insert(0, key)
> -                self._expand(0)
> -                return
> -
> -        if idx == _len:
> -            pos = len(_keys) - 1
> -            if _keys[pos][-1] > key:
> -                msg = '{0!r} not in sort order at index {1}'.format(val, _len)
> -                raise ValueError(msg)
> -            else:
> -                self._len += 1
> -                _lists[pos].append(val)
> -                _keys[pos].append(key)
> -                _maxes[pos] = _keys[pos][-1]
> -                self._expand(pos)
> -                return
> -
> -        pos, idx = self._pos(idx)
> -        idx_before = idx - 1
> -        if idx_before < 0:
> -            pos_before = pos - 1
> -            idx_before = len(_keys[pos_before]) - 1
> -        else:
> -            pos_before = pos
> -
> -        before = _keys[pos_before][idx_before]
> -        if before <= key <= _keys[pos][idx]:
> -            self._len += 1
> -            _lists[pos].insert(idx, val)
> -            _keys[pos].insert(idx, key)
> -            self._expand(pos)
> -        else:
> -            msg = '{0!r} not in sort order at index {1}'.format(val, idx)
> -            raise ValueError(msg)
> -
> -    def index(self, val, start=None, stop=None):
> -        """
> -        Return the smallest *k* such that L[k] == val and i <= k < j`.  Raises
> -        ValueError if *val* is not present.  *stop* defaults to the end of the
> -        list. *start* defaults to the beginning. Negative indices are supported,
> -        as for slice indices.
>          """
>          _len = self._len
>  
>          if not _len:
> -            raise ValueError('{0!r} is not in list'.format(val))
> +            raise ValueError('{0!r} is not in list'.format(value))
>  
>          if start is None:
>              start = 0
> @@ -2331,14 +2459,14 @@ class SortedListWithKey(SortedList):
>              stop = _len
>  
>          if stop <= start:
> -            raise ValueError('{0!r} is not in list'.format(val))
> +            raise ValueError('{0!r} is not in list'.format(value))
>  
>          _maxes = self._maxes
> -        key = self._key(val)
> +        key = self._key(value)
>          pos = bisect_left(_maxes, key)
>  
>          if pos == len(_maxes):
> -            raise ValueError('{0!r} is not in list'.format(val))
> +            raise ValueError('{0!r} is not in list'.format(value))
>  
>          stop -= 1
>          _lists = self._lists
> @@ -2349,8 +2477,8 @@ class SortedListWithKey(SortedList):
>  
>          while True:
>              if _keys[pos][idx] != key:
> -                raise ValueError('{0!r} is not in list'.format(val))
> -            if _lists[pos][idx] == val:
> +                raise ValueError('{0!r} is not in list'.format(value))
> +            if _lists[pos][idx] == value:
>                  loc = self._loc(pos, idx)
>                  if start <= loc <= stop:
>                      return loc
> @@ -2360,139 +2488,148 @@ class SortedListWithKey(SortedList):
>              if idx == len_sublist:
>                  pos += 1
>                  if pos == len_keys:
> -                    raise ValueError('{0!r} is not in list'.format(val))
> +                    raise ValueError('{0!r} is not in list'.format(value))
>                  len_sublist = len(_keys[pos])
>                  idx = 0
>  
> -        raise ValueError('{0!r} is not in list'.format(val))
> +        raise ValueError('{0!r} is not in list'.format(value))
> +
> +
> +    def __add__(self, other):
> +        """Return new sorted-key list containing all values in both sequences.
> +
> +        ``skl.__add__(other)`` <==> ``skl + other``
> +
> +        Values in `other` do not need to be in sorted-key order.
> +
> +        Runtime complexity: `O(n*log(n))`
> +
> +        >>> from operator import neg
> +        >>> skl1 = SortedKeyList([5, 4, 3], key=neg)
> +        >>> skl2 = SortedKeyList([2, 1, 0], key=neg)
> +        >>> skl1 + skl2
> +        SortedKeyList([5, 4, 3, 2, 1, 0], key=<built-in function neg>)
> +
> +        :param other: other iterable
> +        :return: new sorted-key list
>  
> -    def __add__(self, that):
> -        """
> -        Return a new sorted list containing all the elements in *self* and
> -        *that*. Elements in *that* do not need to be properly ordered with
> -        respect to *self*.
>          """
>          values = reduce(iadd, self._lists, [])
> -        values.extend(that)
> +        values.extend(other)
>          return self.__class__(values, key=self._key)
>  
> -    def __mul__(self, that):
> -        """
> -        Return a new sorted list containing *that* shallow copies of each item
> -        in SortedListWithKey.
> +    __radd__ = __add__
> +
> +
> +    def __mul__(self, num):
> +        """Return new sorted-key list with `num` shallow copies of values.
> +
> +        ``skl.__mul__(num)`` <==> ``skl * num``
> +
> +        Runtime complexity: `O(n*log(n))`
> +
> +        >>> from operator import neg
> +        >>> skl = SortedKeyList([3, 2, 1], key=neg)
> +        >>> skl * 2
> +        SortedKeyList([3, 3, 2, 2, 1, 1], key=<built-in function neg>)
> +
> +        :param int num: count of shallow copies
> +        :return: new sorted-key list
> +
>          """
> -        values = reduce(iadd, self._lists, []) * that
> +        values = reduce(iadd, self._lists, []) * num
>          return self.__class__(values, key=self._key)
>  
> -    def __imul__(self, that):
> -        """
> -        Increase the length of the list by appending *that* shallow copies of
> -        each item.
> -        """
> -        values = reduce(iadd, self._lists, []) * that
> -        self._clear()
> -        self._update(values)
> -        return self
>  
> -    @recursive_repr
> +    def __reduce__(self):
> +        values = reduce(iadd, self._lists, [])
> +        return (type(self), (values, self.key))
> +
> +
> +    @recursive_repr()
>      def __repr__(self):
> -        """Return string representation of sequence."""
> -        name = type(self).__name__
> -        values = list(self)
> -        _key = self._key
> -        return '{0}({1!r}, key={2!r})'.format(name, values, _key)
> +        """Return string representation of sorted-key list.
>  
> -    def _check(self):
> -        try:
> -            # Check load parameters.
> +        ``skl.__repr__()`` <==> ``repr(skl)``
>  
> -            assert self._load >= 4
> -            assert self._half == (self._load >> 1)
> -            assert self._dual == (self._load << 1)
> +        :return: string representation
>  
> -            # Check empty sorted list case.
> +        """
> +        type_name = type(self).__name__
> +        return '{0}({1!r}, key={2!r})'.format(type_name, list(self), self._key)
>  
> -            if self._maxes == []:
> -                assert self._keys == []
> -                assert self._lists == []
> -                return
>  
> -            assert self._maxes and self._keys and self._lists
> +    def _check(self):
> +        """Check invariants of sorted-key list.
> +
> +        Runtime complexity: `O(n)`
> +
> +        """
> +        try:
> +            assert self._load >= 4
> +            assert len(self._maxes) == len(self._lists) == len(self._keys)
> +            assert self._len == sum(len(sublist) for sublist in self._lists)
>  
>              # Check all sublists are sorted.
>  
> -            assert all(sublist[pos - 1] <= sublist[pos]
> -                       for sublist in self._keys
> -                       for pos in range(1, len(sublist)))
> +            for sublist in self._keys:
> +                for pos in range(1, len(sublist)):
> +                    assert sublist[pos - 1] <= sublist[pos]
>  
>              # Check beginning/end of sublists are sorted.
>  
>              for pos in range(1, len(self._keys)):
>                  assert self._keys[pos - 1][-1] <= self._keys[pos][0]
>  
> -            # Check length of _maxes and _lists match.
> -
> -            assert len(self._maxes) == len(self._lists) == len(self._keys)
> -
>              # Check _keys matches _key mapped to _lists.
>  
> -            assert all(len(val_list) == len(key_list)
> -                       for val_list, key_list in zip(self._lists, self._keys))
> -            assert all(self._key(val) == key for val, key in
> -                       zip((_val for _val_list in self._lists for _val in _val_list),
> -                           (_key for _key_list in self._keys for _key in _key_list)))
> +            for val_sublist, key_sublist in zip(self._lists, self._keys):
> +                assert len(val_sublist) == len(key_sublist)
> +                for val, key in zip(val_sublist, key_sublist):
> +                    assert self._key(val) == key
>  
> -            # Check _maxes is a map of _keys.
> +            # Check _maxes index is the last value of each sublist.
>  
> -            assert all(self._maxes[pos] == self._keys[pos][-1]
> -                       for pos in range(len(self._maxes)))
> +            for pos in range(len(self._maxes)):
> +                assert self._maxes[pos] == self._keys[pos][-1]
>  
> -            # Check load level is less than _dual.
> +            # Check sublist lengths are less than double load-factor.
>  
> -            assert all(len(sublist) <= self._dual for sublist in self._lists)
> +            double = self._load << 1
> +            assert all(len(sublist) <= double for sublist in self._lists)
>  
> -            # Check load level is greater than _half for all
> +            # Check sublist lengths are greater than half load-factor for all
>              # but the last sublist.
>  
> -            assert all(len(self._lists[pos]) >= self._half
> -                       for pos in range(0, len(self._lists) - 1))
> -
> -            # Check length.
> -
> -            assert self._len == sum(len(sublist) for sublist in self._lists)
> -
> -            # Check index.
> +            half = self._load >> 1
> +            for pos in range(0, len(self._lists) - 1):
> +                assert len(self._lists[pos]) >= half
>  
>              if self._index:
> -                assert len(self._index) == self._offset + len(self._lists)
>                  assert self._len == self._index[0]
> +                assert len(self._index) == self._offset + len(self._lists)
>  
> -                def test_offset_pos(pos):
> -                    "Test positional indexing offset."
> -                    from_index = self._index[self._offset + pos]
> -                    return from_index == len(self._lists[pos])
> +                # Check index leaf nodes equal length of sublists.
>  
> -                assert all(test_offset_pos(pos)
> -                           for pos in range(len(self._lists)))
> +                for pos in range(len(self._lists)):
> +                    leaf = self._index[self._offset + pos]
> +                    assert leaf == len(self._lists[pos])
> +
> +                # Check index branch nodes are the sum of their children.
>  
>                  for pos in range(self._offset):
>                      child = (pos << 1) + 1
> -                    if self._index[pos] == 0:
> -                        assert child >= len(self._index)
> +                    if child >= len(self._index):
> +                        assert self._index[pos] == 0
>                      elif child + 1 == len(self._index):
>                          assert self._index[pos] == self._index[child]
>                      else:
>                          child_sum = self._index[child] + self._index[child + 1]
> -                        assert self._index[pos] == child_sum
> -
> +                        assert child_sum == self._index[pos]
>          except:
> -            import sys
> -            import traceback
> -
>              traceback.print_exc(file=sys.stdout)
> -
>              print('len', self._len)
> -            print('load', self._load, self._half, self._dual)
> +            print('load', self._load)
>              print('offset', self._offset)
>              print('len_index', len(self._index))
>              print('index', self._index)
> @@ -2502,5 +2639,7 @@ class SortedListWithKey(SortedList):
>              print('keys', self._keys)
>              print('len_lists', len(self._lists))
>              print('lists', self._lists)
> -
>              raise
> +
> +
> +SortedListWithKey = SortedKeyList
> diff --git a/python/ovs/compat/sortedcontainers/sortedset.py b/python/ovs/compat/sortedcontainers/sortedset.py
> index 6d82b387b..be2b8999c 100644
> --- a/python/ovs/compat/sortedcontainers/sortedset.py
> +++ b/python/ovs/compat/sortedcontainers/sortedset.py
> @@ -1,50 +1,153 @@
> -"""Sorted set implementation.
> +"""Sorted Set
> +=============
> +
> +:doc:`Sorted Containers<index>` is an Apache2 licensed Python sorted
> +collections library, written in pure-Python, and fast as C-extensions. The
> +:doc:`introduction<introduction>` is the best way to get started.
> +
> +Sorted set implementations:
> +
> +.. currentmodule:: sortedcontainers
> +
> +* :class:`SortedSet`
>  
>  """
>  
> -from collections import Set, MutableSet, Sequence
>  from itertools import chain
> -import operator as op
> +from operator import eq, ne, gt, ge, lt, le
> +from textwrap import dedent
> +
> +from .sortedlist import SortedList, recursive_repr
> +
> +###############################################################################
> +# BEGIN Python 2/3 Shims
> +###############################################################################
> +
> +try:
> +    from collections.abc import MutableSet, Sequence, Set
> +except ImportError:
> +    from collections import MutableSet, Sequence, Set
> +
> +###############################################################################
> +# END Python 2/3 Shims
> +###############################################################################
>  
> -from .sortedlist import SortedList, recursive_repr, SortedListWithKey
>  
>  class SortedSet(MutableSet, Sequence):
> -    """
> -    A `SortedSet` provides the same methods as a `set`.  Additionally, a
> -    `SortedSet` maintains its items in sorted order, allowing the `SortedSet` to
> -    be indexed.
> +    """Sorted set is a sorted mutable set.
> +
> +    Sorted set values are maintained in sorted order. The design of sorted set
> +    is simple: sorted set uses a set for set-operations and maintains a sorted
> +    list of values.
> +
> +    Sorted set values must be hashable and comparable. The hash and total
> +    ordering of values must not change while they are stored in the sorted set.
> +
> +    Mutable set methods:
> +
> +    * :func:`SortedSet.__contains__`
> +    * :func:`SortedSet.__iter__`
> +    * :func:`SortedSet.__len__`
> +    * :func:`SortedSet.add`
> +    * :func:`SortedSet.discard`
> +
> +    Sequence methods:
> +
> +    * :func:`SortedSet.__getitem__`
> +    * :func:`SortedSet.__delitem__`
> +    * :func:`SortedSet.__reversed__`
> +
> +    Methods for removing values:
> +
> +    * :func:`SortedSet.clear`
> +    * :func:`SortedSet.pop`
> +    * :func:`SortedSet.remove`
> +
> +    Set-operation methods:
> +
> +    * :func:`SortedSet.difference`
> +    * :func:`SortedSet.difference_update`
> +    * :func:`SortedSet.intersection`
> +    * :func:`SortedSet.intersection_update`
> +    * :func:`SortedSet.symmetric_difference`
> +    * :func:`SortedSet.symmetric_difference_update`
> +    * :func:`SortedSet.union`
> +    * :func:`SortedSet.update`
> +
> +    Methods for miscellany:
> +
> +    * :func:`SortedSet.copy`
> +    * :func:`SortedSet.count`
> +    * :func:`SortedSet.__repr__`
> +    * :func:`SortedSet._check`
> +
> +    Sorted list methods available:
> +
> +    * :func:`SortedList.bisect_left`
> +    * :func:`SortedList.bisect_right`
> +    * :func:`SortedList.index`
> +    * :func:`SortedList.irange`
> +    * :func:`SortedList.islice`
> +    * :func:`SortedList._reset`
> +
> +    Additional sorted list methods available, if key-function used:
> +
> +    * :func:`SortedKeyList.bisect_key_left`
> +    * :func:`SortedKeyList.bisect_key_right`
> +    * :func:`SortedKeyList.irange_key`
> +
> +    Sorted set comparisons use subset and superset relations. Two sorted sets
> +    are equal if and only if every element of each sorted set is contained in
> +    the other (each is a subset of the other). A sorted set is less than
> +    another sorted set if and only if the first sorted set is a proper subset
> +    of the second sorted set (is a subset, but is not equal). A sorted set is
> +    greater than another sorted set if and only if the first sorted set is a
> +    proper superset of the second sorted set (is a superset, but is not equal).
>  
> -    Unlike a `set`, a `SortedSet` requires items be hashable and comparable.
>      """
> -    # pylint: disable=too-many-ancestors
>      def __init__(self, iterable=None, key=None):
> -        """
> -        A `SortedSet` provides the same methods as a `set`.  Additionally, a
> -        `SortedSet` maintains its items in sorted order, allowing the
> -        `SortedSet` to be indexed.
> +        """Initialize sorted set instance.
>  
> -        An optional *iterable* provides an initial series of items to populate
> -        the `SortedSet`.
> +        Optional `iterable` argument provides an initial iterable of values to
> +        initialize the sorted set.
>  
> -        An optional *key* argument defines a callable that, like the `key`
> +        Optional `key` argument defines a callable that, like the `key`
>          argument to Python's `sorted` function, extracts a comparison key from
> -        each set item. If no function is specified, the default compares the
> -        set items directly.
> +        each value. The default, none, compares values directly.
> +
> +        Runtime complexity: `O(n*log(n))`
> +
> +        >>> ss = SortedSet([3, 1, 2, 5, 4])
> +        >>> ss
> +        SortedSet([1, 2, 3, 4, 5])
> +        >>> from operator import neg
> +        >>> ss = SortedSet([3, 1, 2, 5, 4], neg)
> +        >>> ss
> +        SortedSet([5, 4, 3, 2, 1], key=<built-in function neg>)
> +
> +        :param iterable: initial values (optional)
> +        :param key: function used to extract comparison key (optional)
> +
>          """
>          self._key = key
>  
> +        # SortedSet._fromset calls SortedSet.__init__ after initializing the
> +        # _set attribute. So only create a new set if the _set attribute is not
> +        # already present.
> +
>          if not hasattr(self, '_set'):
>              self._set = set()
>  
> +        self._list = SortedList(self._set, key=key)
> +
> +        # Expose some set methods publicly.
> +
>          _set = self._set
>          self.isdisjoint = _set.isdisjoint
>          self.issubset = _set.issubset
>          self.issuperset = _set.issuperset
>  
> -        if key is None:
> -            self._list = SortedList(self._set)
> -        else:
> -            self._list = SortedListWithKey(self._set, key=key)
> +        # Expose some sorted list methods publicly.
>  
>          _list = self._list
>          self.bisect_left = _list.bisect_left
> @@ -53,7 +156,7 @@ class SortedSet(MutableSet, Sequence):
>          self.index = _list.index
>          self.irange = _list.irange
>          self.islice = _list.islice
> -        self._reset = _list._reset  # pylint: disable=protected-access
> +        self._reset = _list._reset
>  
>          if key is not None:
>              self.bisect_key_left = _list.bisect_key_left
> @@ -64,36 +167,93 @@ class SortedSet(MutableSet, Sequence):
>          if iterable is not None:
>              self._update(iterable)
>  
> -    @property
> -    def key(self):
> -        """Key function used to extract comparison key for sorting."""
> -        return self._key
>  
>      @classmethod
>      def _fromset(cls, values, key=None):
> -        """Initialize sorted set from existing set."""
> +        """Initialize sorted set from existing set.
> +
> +        Used internally by set operations that return a new set.
> +
> +        """
>          sorted_set = object.__new__(cls)
> -        sorted_set._set = values  # pylint: disable=protected-access
> +        sorted_set._set = values
>          sorted_set.__init__(key=key)
>          return sorted_set
>  
> +
> +    @property
> +    def key(self):
> +        """Function used to extract comparison key from values.
> +
> +        Sorted set compares values directly when the key function is none.
> +
> +        """
> +        return self._key
> +
> +
>      def __contains__(self, value):
> -        """Return True if and only if *value* is an element in the set."""
> +        """Return true if `value` is an element of the sorted set.
> +
> +        ``ss.__contains__(value)`` <==> ``value in ss``
> +
> +        Runtime complexity: `O(1)`
> +
> +        >>> ss = SortedSet([1, 2, 3, 4, 5])
> +        >>> 3 in ss
> +        True
> +
> +        :param value: search for value in sorted set
> +        :return: true if `value` in sorted set
> +
> +        """
>          return value in self._set
>  
> +
>      def __getitem__(self, index):
> -        """
> -        Return the element at position *index*.
> +        """Lookup value at `index` in sorted set.
> +
> +        ``ss.__getitem__(index)`` <==> ``ss[index]``
> +
> +        Supports slicing.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> ss = SortedSet('abcde')
> +        >>> ss[2]
> +        'c'
> +        >>> ss[-1]
> +        'e'
> +        >>> ss[2:5]
> +        ['c', 'd', 'e']
> +
> +        :param index: integer or slice for indexing
> +        :return: value or list of values
> +        :raises IndexError: if index out of range
>  
> -        Supports slice notation and negative indexes.
>          """
>          return self._list[index]
>  
> +
>      def __delitem__(self, index):
> -        """
> -        Remove the element at position *index*.
> +        """Remove value at `index` from sorted set.
> +
> +        ``ss.__delitem__(index)`` <==> ``del ss[index]``
> +
> +        Supports slicing.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> ss = SortedSet('abcde')
> +        >>> del ss[2]
> +        >>> ss
> +        SortedSet(['a', 'b', 'd', 'e'])
> +        >>> del ss[:2]
> +        >>> ss
> +        SortedSet(['d', 'e'])
> +
> +        :param index: integer or slice for indexing
> +        :raises IndexError: if index out of range
>  
> -        Supports slice notation and negative indexes.
>          """
>          _set = self._set
>          _list = self._list
> @@ -105,149 +265,316 @@ class SortedSet(MutableSet, Sequence):
>              _set.remove(value)
>          del _list[index]
>  
> -    def _make_cmp(self, set_op, doc):
> +
> +    def __make_cmp(set_op, symbol, doc):
>          "Make comparator method."
> -        def comparer(self, that):
> -            "Compare method for sorted set and set-like object."
> -            # pylint: disable=protected-access
> -            if isinstance(that, SortedSet):
> -                return set_op(self._set, that._set)
> -            elif isinstance(that, Set):
> -                return set_op(self._set, that)
> +        def comparer(self, other):
> +            "Compare method for sorted set and set."
> +            if isinstance(other, SortedSet):
> +                return set_op(self._set, other._set)
> +            elif isinstance(other, Set):
> +                return set_op(self._set, other)
>              return NotImplemented
>  
> -        comparer.__name__ = '__{0}__'.format(set_op.__name__)
> -        doc_str = 'Return True if and only if Set is {0} `that`.'
> -        comparer.__doc__ = doc_str.format(doc)
> +        set_op_name = set_op.__name__
> +        comparer.__name__ = '__{0}__'.format(set_op_name)
> +        doc_str = """Return true if and only if sorted set is {0} `other`.
> +
> +        ``ss.__{1}__(other)`` <==> ``ss {2} other``
> +
> +        Comparisons use subset and superset semantics as with sets.
> +
> +        Runtime complexity: `O(n)`
> +
> +        :param other: `other` set
> +        :return: true if sorted set is {0} `other`
>  
> +        """
> +        comparer.__doc__ = dedent(doc_str.format(doc, set_op_name, symbol))
>          return comparer
>  
> -    __eq__ = _make_cmp(None, op.eq, 'equal to')
> -    __ne__ = _make_cmp(None, op.ne, 'not equal to')
> -    __lt__ = _make_cmp(None, op.lt, 'a proper subset of')
> -    __gt__ = _make_cmp(None, op.gt, 'a proper superset of')
> -    __le__ = _make_cmp(None, op.le, 'a subset of')
> -    __ge__ = _make_cmp(None, op.ge, 'a superset of')
> +
> +    __eq__ = __make_cmp(eq, '==', 'equal to')
> +    __ne__ = __make_cmp(ne, '!=', 'not equal to')
> +    __lt__ = __make_cmp(lt, '<', 'a proper subset of')
> +    __gt__ = __make_cmp(gt, '>', 'a proper superset of')
> +    __le__ = __make_cmp(le, '<=', 'a subset of')
> +    __ge__ = __make_cmp(ge, '>=', 'a superset of')
> +    __make_cmp = staticmethod(__make_cmp)
> +
>  
>      def __len__(self):
> -        """Return the number of elements in the set."""
> +        """Return the size of the sorted set.
> +
> +        ``ss.__len__()`` <==> ``len(ss)``
> +
> +        :return: size of sorted set
> +
> +        """
>          return len(self._set)
>  
> +
>      def __iter__(self):
> -        """
> -        Return an iterator over the Set. Elements are iterated in their sorted
> -        order.
> +        """Return an iterator over the sorted set.
> +
> +        ``ss.__iter__()`` <==> ``iter(ss)``
> +
> +        Iterating the sorted set while adding or deleting values may raise a
> +        :exc:`RuntimeError` or fail to iterate over all values.
>  
> -        Iterating the Set while adding or deleting values may raise a
> -        `RuntimeError` or fail to iterate over all entries.
>          """
>          return iter(self._list)
>  
> +
>      def __reversed__(self):
> -        """
> -        Return an iterator over the Set. Elements are iterated in their reverse
> -        sorted order.
> +        """Return a reverse iterator over the sorted set.
> +
> +        ``ss.__reversed__()`` <==> ``reversed(ss)``
> +
> +        Iterating the sorted set while adding or deleting values may raise a
> +        :exc:`RuntimeError` or fail to iterate over all values.
>  
> -        Iterating the Set while adding or deleting values may raise a
> -        `RuntimeError` or fail to iterate over all entries.
>          """
>          return reversed(self._list)
>  
> +
>      def add(self, value):
> -        """Add the element *value* to the set."""
> +        """Add `value` to sorted set.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> ss = SortedSet()
> +        >>> ss.add(3)
> +        >>> ss.add(1)
> +        >>> ss.add(2)
> +        >>> ss
> +        SortedSet([1, 2, 3])
> +
> +        :param value: value to add to sorted set
> +
> +        """
>          _set = self._set
>          if value not in _set:
>              _set.add(value)
>              self._list.add(value)
>  
> +    _add = add
> +
> +
>      def clear(self):
> -        """Remove all elements from the set."""
> +        """Remove all values from sorted set.
> +
> +        Runtime complexity: `O(n)`
> +
> +        """
>          self._set.clear()
>          self._list.clear()
>  
> +
>      def copy(self):
> -        """Create a shallow copy of the sorted set."""
> +        """Return a shallow copy of the sorted set.
> +
> +        Runtime complexity: `O(n)`
> +
> +        :return: new sorted set
> +
> +        """
>          return self._fromset(set(self._set), key=self._key)
>  
>      __copy__ = copy
>  
> +
>      def count(self, value):
> -        """Return the number of occurrences of *value* in the set."""
> +        """Return number of occurrences of `value` in the sorted set.
> +
> +        Runtime complexity: `O(1)`
> +
> +        >>> ss = SortedSet([1, 2, 3, 4, 5])
> +        >>> ss.count(3)
> +        1
> +
> +        :param value: value to count in sorted set
> +        :return: count
> +
> +        """
>          return 1 if value in self._set else 0
>  
> +
>      def discard(self, value):
> -        """
> -        Remove the first occurrence of *value*.  If *value* is not a member,
> -        does nothing.
> +        """Remove `value` from sorted set if it is a member.
> +
> +        If `value` is not a member, do nothing.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> ss = SortedSet([1, 2, 3, 4, 5])
> +        >>> ss.discard(5)
> +        >>> ss.discard(0)
> +        >>> ss == set([1, 2, 3, 4])
> +        True
> +
> +        :param value: `value` to discard from sorted set
> +
>          """
>          _set = self._set
>          if value in _set:
>              _set.remove(value)
> -            self._list.discard(value)
> +            self._list.remove(value)
> +
> +    _discard = discard
> +
>  
>      def pop(self, index=-1):
> -        """
> -        Remove and return item at *index* (default last).  Raises IndexError if
> -        set is empty or index is out of range.  Negative indexes are supported,
> -        as for slice indices.
> +        """Remove and return value at `index` in sorted set.
> +
> +        Raise :exc:`IndexError` if the sorted set is empty or index is out of
> +        range.
> +
> +        Negative indices are supported.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> ss = SortedSet('abcde')
> +        >>> ss.pop()
> +        'e'
> +        >>> ss.pop(2)
> +        'c'
> +        >>> ss
> +        SortedSet(['a', 'b', 'd'])
> +
> +        :param int index: index of value (default -1)
> +        :return: value
> +        :raises IndexError: if index is out of range
> +
>          """
>          # pylint: disable=arguments-differ
>          value = self._list.pop(index)
>          self._set.remove(value)
>          return value
>  
> +
>      def remove(self, value):
> -        """
> -        Remove first occurrence of *value*.  Raises ValueError if
> -        *value* is not present.
> +        """Remove `value` from sorted set; `value` must be a member.
> +
> +        If `value` is not a member, raise :exc:`KeyError`.
> +
> +        Runtime complexity: `O(log(n))` -- approximate.
> +
> +        >>> ss = SortedSet([1, 2, 3, 4, 5])
> +        >>> ss.remove(5)
> +        >>> ss == set([1, 2, 3, 4])
> +        True
> +        >>> ss.remove(0)
> +        Traceback (most recent call last):
> +          ...
> +        KeyError: 0
> +
> +        :param value: `value` to remove from sorted set
> +        :raises KeyError: if `value` is not in sorted set
> +
>          """
>          self._set.remove(value)
>          self._list.remove(value)
>  
> +
>      def difference(self, *iterables):
> -        """
> -        Return a new set with elements in the set that are not in the
> -        *iterables*.
> +        """Return the difference of two or more sets as a new sorted set.
> +
> +        The `difference` method also corresponds to operator ``-``.
> +
> +        ``ss.__sub__(iterable)`` <==> ``ss - iterable``
> +
> +        The difference is all values that are in this sorted set but not the
> +        other `iterables`.
> +
> +        >>> ss = SortedSet([1, 2, 3, 4, 5])
> +        >>> ss.difference([4, 5, 6, 7])
> +        SortedSet([1, 2, 3])
> +
> +        :param iterables: iterable arguments
> +        :return: new sorted set
> +
>          """
>          diff = self._set.difference(*iterables)
>          return self._fromset(diff, key=self._key)
>  
>      __sub__ = difference
> -    __rsub__ = __sub__
> +
>  
>      def difference_update(self, *iterables):
> -        """
> -        Update the set, removing elements found in keeping only elements
> -        found in any of the *iterables*.
> +        """Remove all values of `iterables` from this sorted set.
> +
> +        The `difference_update` method also corresponds to operator ``-=``.
> +
> +        ``ss.__isub__(iterable)`` <==> ``ss -= iterable``
> +
> +        >>> ss = SortedSet([1, 2, 3, 4, 5])
> +        >>> _ = ss.difference_update([4, 5, 6, 7])
> +        >>> ss
> +        SortedSet([1, 2, 3])
> +
> +        :param iterables: iterable arguments
> +        :return: itself
> +
>          """
>          _set = self._set
> +        _list = self._list
>          values = set(chain(*iterables))
>          if (4 * len(values)) > len(_set):
> -            _list = self._list
>              _set.difference_update(values)
>              _list.clear()
>              _list.update(_set)
>          else:
> -            _discard = self.discard
> +            _discard = self._discard
>              for value in values:
>                  _discard(value)
>          return self
>  
>      __isub__ = difference_update
>  
> +
>      def intersection(self, *iterables):
> +        """Return the intersection of two or more sets as a new sorted set.
> +
> +        The `intersection` method also corresponds to operator ``&``.
> +
> +        ``ss.__and__(iterable)`` <==> ``ss & iterable``
> +
> +        The intersection is all values that are in this sorted set and each of
> +        the other `iterables`.
> +
> +        >>> ss = SortedSet([1, 2, 3, 4, 5])
> +        >>> ss.intersection([4, 5, 6, 7])
> +        SortedSet([4, 5])
> +
> +        :param iterables: iterable arguments
> +        :return: new sorted set
> +
>          """
> -        Return a new set with elements common to the set and all *iterables*.
> -        """
> -        comb = self._set.intersection(*iterables)
> -        return self._fromset(comb, key=self._key)
> +        intersect = self._set.intersection(*iterables)
> +        return self._fromset(intersect, key=self._key)
>  
>      __and__ = intersection
>      __rand__ = __and__
>  
> +
>      def intersection_update(self, *iterables):
> -        """
> -        Update the set, keeping only elements found in it and all *iterables*.
> +        """Update the sorted set with the intersection of `iterables`.
> +
> +        The `intersection_update` method also corresponds to operator ``&=``.
> +
> +        ``ss.__iand__(iterable)`` <==> ``ss &= iterable``
> +
> +        Keep only values found in itself and all `iterables`.
> +
> +        >>> ss = SortedSet([1, 2, 3, 4, 5])
> +        >>> _ = ss.intersection_update([4, 5, 6, 7])
> +        >>> ss
> +        SortedSet([4, 5])
> +
> +        :param iterables: iterable arguments
> +        :return: itself
> +
>          """
>          _set = self._set
>          _list = self._list
> @@ -258,42 +585,100 @@ class SortedSet(MutableSet, Sequence):
>  
>      __iand__ = intersection_update
>  
> -    def symmetric_difference(self, that):
> -        """
> -        Return a new set with elements in either *self* or *that* but not both.
> +
> +    def symmetric_difference(self, other):
> +        """Return the symmetric difference with `other` as a new sorted set.
> +
> +        The `symmetric_difference` method also corresponds to operator ``^``.
> +
> +        ``ss.__xor__(other)`` <==> ``ss ^ other``
> +
> +        The symmetric difference is all values tha are in exactly one of the
> +        sets.
> +
> +        >>> ss = SortedSet([1, 2, 3, 4, 5])
> +        >>> ss.symmetric_difference([4, 5, 6, 7])
> +        SortedSet([1, 2, 3, 6, 7])
> +
> +        :param other: `other` iterable
> +        :return: new sorted set
> +
>          """
> -        diff = self._set.symmetric_difference(that)
> +        diff = self._set.symmetric_difference(other)
>          return self._fromset(diff, key=self._key)
>  
>      __xor__ = symmetric_difference
>      __rxor__ = __xor__
>  
> -    def symmetric_difference_update(self, that):
> -        """
> -        Update the set, keeping only elements found in either *self* or *that*,
> -        but not in both.
> +
> +    def symmetric_difference_update(self, other):
> +        """Update the sorted set with the symmetric difference with `other`.
> +
> +        The `symmetric_difference_update` method also corresponds to operator
> +        ``^=``.
> +
> +        ``ss.__ixor__(other)`` <==> ``ss ^= other``
> +
> +        Keep only values found in exactly one of itself and `other`.
> +
> +        >>> ss = SortedSet([1, 2, 3, 4, 5])
> +        >>> _ = ss.symmetric_difference_update([4, 5, 6, 7])
> +        >>> ss
> +        SortedSet([1, 2, 3, 6, 7])
> +
> +        :param other: `other` iterable
> +        :return: itself
> +
>          """
>          _set = self._set
>          _list = self._list
> -        _set.symmetric_difference_update(that)
> +        _set.symmetric_difference_update(other)
>          _list.clear()
>          _list.update(_set)
>          return self
>  
>      __ixor__ = symmetric_difference_update
>  
> +
>      def union(self, *iterables):
> -        """
> -        Return a new SortedSet with elements from the set and all *iterables*.
> +        """Return new sorted set with values from itself and all `iterables`.
> +
> +        The `union` method also corresponds to operator ``|``.
> +
> +        ``ss.__or__(iterable)`` <==> ``ss | iterable``
> +
> +        >>> ss = SortedSet([1, 2, 3, 4, 5])
> +        >>> ss.union([4, 5, 6, 7])
> +        SortedSet([1, 2, 3, 4, 5, 6, 7])
> +
> +        :param iterables: iterable arguments
> +        :return: new sorted set
> +
>          """
>          return self.__class__(chain(iter(self), *iterables), key=self._key)
>  
>      __or__ = union
>      __ror__ = __or__
>  
> +
>      def update(self, *iterables):
> -        """Update the set, adding elements from all *iterables*."""
> +        """Update the sorted set adding values from all `iterables`.
> +
> +        The `update` method also corresponds to operator ``|=``.
> +
> +        ``ss.__ior__(iterable)`` <==> ``ss |= iterable``
> +
> +        >>> ss = SortedSet([1, 2, 3, 4, 5])
> +        >>> _ = ss.update([4, 5, 6, 7])
> +        >>> ss
> +        SortedSet([1, 2, 3, 4, 5, 6, 7])
> +
> +        :param iterables: iterable arguments
> +        :return: itself
> +
> +        """
>          _set = self._set
> +        _list = self._list
>          values = set(chain(*iterables))
>          if (4 * len(values)) > len(_set):
>              _list = self._list
> @@ -301,7 +686,7 @@ class SortedSet(MutableSet, Sequence):
>              _list.clear()
>              _list.update(_set)
>          else:
> -            _add = self.add
> +            _add = self._add
>              for value in values:
>                  _add(value)
>          return self
> @@ -309,19 +694,40 @@ class SortedSet(MutableSet, Sequence):
>      __ior__ = update
>      _update = update
>  
> +
>      def __reduce__(self):
> +        """Support for pickle.
> +
> +        The tricks played with exposing methods in :func:`SortedSet.__init__`
> +        confuse pickle so customize the reducer.
> +
> +        """
>          return (type(self), (self._set, self._key))
>  
> -    @recursive_repr
> +
> +    @recursive_repr()
>      def __repr__(self):
> +        """Return string representation of sorted set.
> +
> +        ``ss.__repr__()`` <==> ``repr(ss)``
> +
> +        :return: string representation
> +
> +        """
>          _key = self._key
>          key = '' if _key is None else ', key={0!r}'.format(_key)
> -        name = type(self).__name__
> -        return '{0}({1!r}{2})'.format(name, list(self), key)
> +        type_name = type(self).__name__
> +        return '{0}({1!r}{2})'.format(type_name, list(self), key)
> +
>  
>      def _check(self):
> -        # pylint: disable=protected-access
> -        self._list._check()
> -        assert len(self._set) == len(self._list)
> +        """Check invariants of sorted set.
> +
> +        Runtime complexity: `O(n)`
> +
> +        """
>          _set = self._set
> -        assert all(val in _set for val in self._list)
> +        _list = self._list
> +        _list._check()
> +        assert len(_set) == len(_list)
> +        assert all(value in _set for value in _list)
>

On 7/2/21 12:47 PM, Ilya Maximets wrote:
> On 7/2/21 12:17 PM, Timothy Redaelli wrote:
>> This is needed since the current bundled version doesn't work on Python
>> 3.10+.
> 
> Make sense.
> 
> Terry, could you, please, take a look?
> 
> I also wonder if we need to apply this patch to stable branches.
> Thoughts?
> 
> Best regards, Ilya Maximets.
> 
>>
>> Signed-off-by: Timothy Redaelli <tredaelli@redhat.com>
>> ---
>>  python/ovs/compat/sortedcontainers/LICENSE    |    2 +-
>>  .../ovs/compat/sortedcontainers/__init__.py   |   70 +-
>>  .../ovs/compat/sortedcontainers/sorteddict.py | 1233 +++++----
>>  .../ovs/compat/sortedcontainers/sortedlist.py | 2409 +++++++++--------
>>  .../ovs/compat/sortedcontainers/sortedset.py  |  636 ++++-
>>  5 files changed, 2494 insertions(+), 1856 deletions(-)
>>

I looked through this patch again and it looks good to me.
Applied to master.

Best regards, Ilya Maximets.