[ovs-dev] [PATCH v2] Add multi-column index support for the Python IDL

twilson at redhat.com twilson at redhat.com
Fri Apr 13 00:24:27 UTC 2018


From: Terry Wilson <twilson at redhat.com>

This adds multi-column index support for the Python IDL that is
similar to the feature in the C IDL. Since it adds sortedcontainers
as a dependency and some distros don't yet package it, the library
is copied in-tree and used if sortedcontainers is not installed.

Signed-off-by: Terry Wilson <twilson at redhat.com>
---
 python/automake.mk                               |    8 +-
 python/ovs/compat/__init__.py                    |    0
 python/ovs/compat/sortedcontainers/LICENSE       |   13 +
 python/ovs/compat/sortedcontainers/__init__.py   |   52 +
 python/ovs/compat/sortedcontainers/sorteddict.py |  741 +++++++
 python/ovs/compat/sortedcontainers/sortedlist.py | 2508 ++++++++++++++++++++++
 python/ovs/compat/sortedcontainers/sortedset.py  |  327 +++
 python/ovs/db/custom_index.py                    |  154 ++
 python/ovs/db/idl.py                             |   55 +-
 python/setup.py                                  |    1 +
 tests/test-ovsdb.py                              |    7 +-
 11 files changed, 3850 insertions(+), 16 deletions(-)
 create mode 100644 python/ovs/compat/__init__.py
 create mode 100644 python/ovs/compat/sortedcontainers/LICENSE
 create mode 100644 python/ovs/compat/sortedcontainers/__init__.py
 create mode 100644 python/ovs/compat/sortedcontainers/sorteddict.py
 create mode 100644 python/ovs/compat/sortedcontainers/sortedlist.py
 create mode 100644 python/ovs/compat/sortedcontainers/sortedset.py
 create mode 100644 python/ovs/db/custom_index.py

diff --git a/python/automake.mk b/python/automake.mk
index 9b5d3d8..458a2c3 100644
--- a/python/automake.mk
+++ b/python/automake.mk
@@ -10,9 +10,15 @@ ovstest_pyfiles = \
 
 ovs_pyfiles = \
 	python/ovs/__init__.py \
+	python/ovs/compat/__init__.py \
+	python/ovs/compat/sortedcontainers/__init__.py \
+	python/ovs/compat/sortedcontainers/sortedlist.py \
+	python/ovs/compat/sortedcontainers/sorteddict.py \
+	python/ovs/compat/sortedcontainers/sortedset.py \
 	python/ovs/daemon.py \
 	python/ovs/fcntl_win.py \
 	python/ovs/db/__init__.py \
+	python/ovs/db/custom_index.py \
 	python/ovs/db/data.py \
 	python/ovs/db/error.py \
 	python/ovs/db/idl.py \
@@ -36,7 +42,6 @@ ovs_pyfiles = \
 	python/ovs/version.py \
 	python/ovs/vlog.py \
 	python/ovs/winutils.py
-
 # These python files are used at build time but not runtime,
 # so they are not installed.
 EXTRA_DIST += \
@@ -46,6 +51,7 @@ EXTRA_DIST += \
 
 # PyPI support.
 EXTRA_DIST += \
+	python/ovs/compat/sortedcontainers/LICENSE \
 	python/README.rst \
 	python/setup.py
 
diff --git a/python/ovs/compat/__init__.py b/python/ovs/compat/__init__.py
new file mode 100644
index 0000000..e69de29
diff --git a/python/ovs/compat/sortedcontainers/LICENSE b/python/ovs/compat/sortedcontainers/LICENSE
new file mode 100644
index 0000000..8794014
--- /dev/null
+++ b/python/ovs/compat/sortedcontainers/LICENSE
@@ -0,0 +1,13 @@
+Copyright 2014-2016 Grant Jenks
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+    http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
diff --git a/python/ovs/compat/sortedcontainers/__init__.py b/python/ovs/compat/sortedcontainers/__init__.py
new file mode 100644
index 0000000..392adfa
--- /dev/null
+++ b/python/ovs/compat/sortedcontainers/__init__.py
@@ -0,0 +1,52 @@
+"""Sorted Container Types: SortedList, SortedDict, SortedSet
+
+SortedContainers 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
+different implementations, most using C-extensions without great documentation
+and benchmarking.
+
+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)
+    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
+testing has 100% coverage with unit tests and hours of stress.
+
+:copyright: (c) 2016 by Grant Jenks.
+:license: Apache 2.0, see LICENSE for more details.
+
+"""
+
+
+from .sortedlist import SortedList, SortedListWithKey
+from .sortedset import SortedSet
+from .sorteddict import SortedDict
+
+__all__ = ['SortedList', 'SortedSet', 'SortedDict', 'SortedListWithKey']
+
+__title__ = 'sortedcontainers'
+__version__ = '1.5.9'
+__build__ = 0x010509
+__author__ = 'Grant Jenks'
+__license__ = 'Apache 2.0'
+__copyright__ = 'Copyright 2016 Grant Jenks'
diff --git a/python/ovs/compat/sortedcontainers/sorteddict.py b/python/ovs/compat/sortedcontainers/sorteddict.py
new file mode 100644
index 0000000..5d425fe
--- /dev/null
+++ b/python/ovs/compat/sortedcontainers/sorteddict.py
@@ -0,0 +1,741 @@
+"""Sorted dictionary implementation.
+
+"""
+
+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
+
+from .sortedlist import SortedList, recursive_repr, SortedListWithKey
+from .sortedset import SortedSet
+
+NONE = object()
+
+
+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)
+
+
+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.
+
+    """
+    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.
+
+        """
+        # pylint: disable=super-init-not-called
+        if args and (args[0] is None or callable(args[0])):
+            self._key = args[0]
+            args = args[1:]
+        else:
+            self._key = None
+
+        if self._key is None:
+            self._list = SortedList()
+        else:
+            self._list = SortedListWithKey(key=self._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.
+
+        _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_pop = _list.pop
+        self._list_remove = _list.remove
+        self._list_update = _list.update
+        self.irange = _list.irange
+        self.islice = _list.islice
+        self._reset = _list._reset  # pylint: disable=protected-access
+
+        if self._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."""
+        return self._key
+
+    def clear(self):
+        """Remove all elements from the dictionary."""
+        self._clear()
+        self._list_clear()
+
+    def __delitem__(self, key):
+        """
+        Remove ``d[key]`` from *d*.  Raises a KeyError if *key* is not in the
+        dictionary.
+        """
+        self._delitem(key)
+        self._list_remove(key)
+
+    def __iter__(self):
+        """
+        Return an iterator over the sorted keys of the dictionary.
+
+        Iterating the Mapping while adding or deleting keys may raise a
+        `RuntimeError` or fail to iterate over all entries.
+        """
+        return iter(self._list)
+
+    def __reversed__(self):
+        """
+        Return a reversed iterator over the sorted keys of the dictionary.
+
+        Iterating the Mapping while adding or deleting keys may raise a
+        `RuntimeError` or fail to iterate over all entries.
+        """
+        return reversed(self._list)
+
+    def __setitem__(self, key, value):
+        """Set `d[key]` to *value*."""
+        if key not in self:
+            self._list_add(key)
+        self._setitem(key, value)
+
+    def copy(self):
+        """Return a shallow copy of the sorted dictionary."""
+        return self.__class__(self._key, self._iteritems())
+
+    __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).
+
+        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)
+
+    _iteritems = iteritems
+
+    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.
+
+        Iterating the Mapping while adding or deleting keys may raise a
+        `RuntimeError` or fail to iterate over all entries.
+        """
+        return iter(self._list)
+
+    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.
+
+        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)
+
+    _itervalues = itervalues
+
+    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.
+        """
+        if key in self:
+            self._list_remove(key)
+            return self._pop(key)
+        else:
+            if default is NONE:
+                raise KeyError(key)
+            else:
+                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`.
+        """
+        if not self:
+            raise KeyError('popitem(): dictionary is empty')
+
+        key = self._list_pop(-1 if last else 0)
+        value = self._pop(key)
+
+        return (key, value)
+
+    def peekitem(self, index=-1):
+        """Return (key, value) item pair at index.
+
+        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.
+
+        If index is out of range, raise IndexError.
+
+        """
+        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``.
+        """
+        if key in self:
+            return self[key]
+
+        self._setitem(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* 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())
+            return
+
+        if not kwargs and len(args) == 1 and isinstance(args[0], dict):
+            pairs = args[0]
+        else:
+            pairs = dict(*args, **kwargs)
+
+        if (10 * len(pairs)) > len(self):
+            self._dict_update(pairs)
+            self._list_clear()
+            self._list_update(self._iter())
+        else:
+            for key in pairs:
+                self[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 viewitems(self):
+            "Return ``ItemsView`` of dictionary (key, value) item pairs."
+            return ItemsView(self)
+
+    def __reduce__(self):
+        return (self.__class__, (self._key, list(self._iteritems())))
+
+    @recursive_repr
+    def __repr__(self):
+        _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)
+
+    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)
+
+
+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.
+
+    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()
+    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.
+
+        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.
+
+        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))
+
+
+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.
+
+    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.
+
+        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.
+
+        Supports slice notation and negative indexes.
+        """
+        _dict, _list = self._dict, self._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.
+
+        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.
+
+        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))
+
+
+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.
+    """
+    # 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.
+
+        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.
+
+        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))
diff --git a/python/ovs/compat/sortedcontainers/sortedlist.py b/python/ovs/compat/sortedcontainers/sortedlist.py
new file mode 100644
index 0000000..8aec6bb
--- /dev/null
+++ b/python/ovs/compat/sortedcontainers/sortedlist.py
@@ -0,0 +1,2508 @@
+"""Sorted list implementation.
+
+"""
+# pylint: disable=redefined-builtin, ungrouped-imports
+
+from __future__ import print_function
+
+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 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
+    try:
+        from thread import get_ident
+    except ImportError:
+        from dummy_thread import get_ident
+else:
+    from functools import reduce
+    try:
+        from _thread import get_ident
+    except ImportError:
+        from _dummy_thread import get_ident # pylint: disable=import-error
+
+LOAD = 1000
+
+def recursive_repr(func):
+    """Decorator to prevent infinite repr recursion."""
+    repr_running = set()
+
+    @wraps(func)
+    def wrapper(self):
+        "Return ellipsis on recursive re-entry to function."
+        key = id(self), get_ident()
+
+        if key in repr_running:
+            return '...'
+
+        repr_running.add(key)
+
+        try:
+            return func(self)
+        finally:
+            repr_running.discard(key)
+
+    return wrapper
+
+class SortedList(MutableSequence):
+    """
+    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.
+
+        An optional *iterable* provides an initial series of items to populate
+        the SortedList.
+        """
+        self._len = 0
+        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.
+
+        An optional *iterable* provides an initial series of items to populate
+        the SortedList.
+
+        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)
+            else:
+                raise TypeError('inherit SortedListWithKey for key argument')
+
+    @property
+    def key(self):
+        """Key function used to extract comparison key for sorting."""
+        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.
+        """
+        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."""
+        self._len = 0
+        del self._lists[:]
+        del self._maxes[:]
+        del self._index[:]
+
+    _clear = clear
+
+    def add(self, val):
+        """Add the element *val* to the list."""
+        _lists = self._lists
+        _maxes = self._maxes
+
+        if _maxes:
+            pos = bisect_right(_maxes, val)
+
+            if pos == len(_maxes):
+                pos -= 1
+                _lists[pos].append(val)
+                _maxes[pos] = val
+            else:
+                insort(_lists[pos], val)
+
+            self._expand(pos)
+        else:
+            _lists.append([val])
+            _maxes.append(val)
+
+        self._len += 1
+
+    def _expand(self, pos):
+        """Splits sublists that are more than double the load level.
+
+        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.
+
+        """
+        _lists = self._lists
+        _index = self._index
+
+        if len(_lists[pos]) > self._dual:
+            _maxes = self._maxes
+            _load = self._load
+
+            _lists_pos = _lists[pos]
+            half = _lists_pos[_load:]
+            del _lists_pos[_load:]
+            _maxes[pos] = _lists_pos[-1]
+
+            _lists.insert(pos + 1, half)
+            _maxes.insert(pos + 1, half[-1])
+
+            del _index[:]
+        else:
+            if _index:
+                child = self._offset + pos
+                while child:
+                    _index[child] += 1
+                    child = (child - 1) >> 1
+                _index[0] += 1
+
+    def update(self, iterable):
+        """Update the list by adding all elements from *iterable*."""
+        _lists = self._lists
+        _maxes = self._maxes
+        values = sorted(iterable)
+
+        if _maxes:
+            if len(values) * 4 >= self._len:
+                values.extend(chain.from_iterable(_lists))
+                values.sort()
+                self._clear()
+            else:
+                _add = self.add
+                for val in values:
+                    _add(val)
+                return
+
+        _load = self._load
+        _lists.extend(values[pos:(pos + _load)]
+                      for pos in range(0, len(values), _load))
+        _maxes.extend(sublist[-1] for sublist in _lists)
+        self._len = len(values)
+        del self._index[:]
+
+    _update = update
+
+    def __contains__(self, val):
+        """Return True if and only if *val* is an element in the list."""
+        _maxes = self._maxes
+
+        if not _maxes:
+            return False
+
+        pos = bisect_left(_maxes, val)
+
+        if pos == len(_maxes):
+            return False
+
+        _lists = self._lists
+        idx = bisect_left(_lists[pos], val)
+
+        return _lists[pos][idx] == val
+
+    def discard(self, val):
+        """
+        Remove the first occurrence of *val*.
+
+        If *val* is not a member, does nothing.
+        """
+        _maxes = self._maxes
+
+        if not _maxes:
+            return
+
+        pos = bisect_left(_maxes, val)
+
+        if pos == len(_maxes):
+            return
+
+        _lists = self._lists
+        idx = bisect_left(_lists[pos], val)
+
+        if _lists[pos][idx] == val:
+            self._delete(pos, idx)
+
+    def remove(self, val):
+        """
+        Remove first occurrence of *val*.
+
+        Raises ValueError if *val* is not present.
+        """
+        # pylint: disable=arguments-differ
+        _maxes = self._maxes
+
+        if not _maxes:
+            raise ValueError('{0!r} not in list'.format(val))
+
+        pos = bisect_left(_maxes, val)
+
+        if pos == len(_maxes):
+            raise ValueError('{0!r} not in list'.format(val))
+
+        _lists = self._lists
+        idx = bisect_left(_lists[pos], val)
+
+        if _lists[pos][idx] == val:
+            self._delete(pos, idx)
+        else:
+            raise ValueError('{0!r} not in list'.format(val))
+
+    def _delete(self, pos, idx):
+        """Delete the item 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.
+        """
+        _lists = self._lists
+        _maxes = self._maxes
+        _index = self._index
+
+        _lists_pos = _lists[pos]
+
+        del _lists_pos[idx]
+        self._len -= 1
+
+        len_lists_pos = len(_lists_pos)
+
+        if len_lists_pos > self._half:
+
+            _maxes[pos] = _lists_pos[-1]
+
+            if _index:
+                child = self._offset + pos
+                while child > 0:
+                    _index[child] -= 1
+                    child = (child - 1) >> 1
+                _index[0] -= 1
+
+        elif len(_lists) > 1:
+
+            if not pos:
+                pos += 1
+
+            prev = pos - 1
+            _lists[prev].extend(_lists[pos])
+            _maxes[prev] = _lists[prev][-1]
+
+            del _lists[pos]
+            del _maxes[pos]
+            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.
+
+        Most queries require the index be built. Details of the index are
+        described in self._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.
+
+        Left-child nodes are always at odd indices and right-child nodes are
+        always at even indices.
+
+        When traversing up from a right-child node, increment the total by the
+        left-child node.
+
+        The final index is the sum from traversal and the index in the sublist.
+
+        For example, using the index from self._build_index:
+
+        _index = 14 5 9 3 2 4 5
+        _offset = 3
+
+        Tree:
+
+                 14
+              5      9
+            3   2  4   5
+
+        Converting 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
+           the parent.
+
+        2. At node 9, position 2, we recognize the node as a right-child node
+           and accumulate the left-child in our total. Total is now 5 and we
+           traverse to the parent at position 0.
+
+        3. Iteration ends at the root.
+
+        Computing the index is the sum of the total and beta: 5 + 3 = 8.
+        """
+        if not pos:
+            return idx
+
+        _index = self._index
+
+        if not _index:
+            self._build_index()
+
+        total = 0
+
+        # Increment pos to point in the index to len(self._lists[pos]).
+
+        pos += self._offset
+
+        # Iterate until reaching the root of the index tree at pos = 0.
+
+        while pos:
+
+            # Right-child nodes are at odd indices. At such indices
+            # account the total below the left child node.
+
+            if not pos & 1:
+                total += _index[pos - 1]
+
+            # Advance pos to the parent node.
+
+            pos = (pos - 1) >> 1
+
+        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.
+
+        Most queries require the index be built. Details of the index are
+        described in self._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.
+
+        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
+        and traversal moves to the right sub-tree.
+
+        At a child node, the indexing pair is computed from the relative
+        position of the child node as compared with the offset and the remaining
+        index.
+
+        For example, using the index from self._build_index:
+
+        _index = 14 5 9 3 2 4 5
+        _offset = 3
+
+        Tree:
+
+                 14
+              5      9
+            3   2  4   5
+
+        Indexing position 8 involves iterating like so:
+
+        1. Starting at the root, position 0, 8 is compared with the left-child
+           node (5) which it is greater than. When greater the index is
+           decremented and the position is updated to the right child node.
+
+        2. At node 9 with index 3, we again compare the index to the left-child
+           node with value 4. Because the index is the less than the left-child
+           node, we simply traverse to the left.
+
+        3. At node 4 with index 3, we recognize that we are at a leaf node and
+           stop iterating.
+
+        4. To compute the sublist index, we subtract the offset from the index
+           of the leaf node: 5 - 3 = 2. To compute the index in the sublist, we
+           simply use the index remaining from iteration. In this case, 3.
+
+        The final index pair from our example is (2, 3) which corresponds to
+        index 8 in the sorted list.
+        """
+        if idx < 0:
+            last_len = len(self._lists[-1])
+
+            if (-idx) <= last_len:
+                return len(self._lists) - 1, last_len + idx
+
+            idx += self._len
+
+            if idx < 0:
+                raise IndexError('list index out of range')
+        elif idx >= self._len:
+            raise IndexError('list index out of range')
+
+        if idx < len(self._lists[0]):
+            return 0, idx
+
+        _index = self._index
+
+        if not _index:
+            self._build_index()
+
+        pos = 0
+        child = 1
+        len_index = len(_index)
+
+        while child < len_index:
+            index_child = _index[child]
+
+            if idx < index_child:
+                pos = child
+            else:
+                idx -= index_child
+                pos = child + 1
+
+            child = (pos << 1) + 1
+
+        return (pos - self._offset, idx)
+
+    def _build_index(self):
+        """Build an 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:
+
+        [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.
+
+        [0]: 3 2 4 5
+
+        Each row after that is the sum of consecutive pairs of the previous row:
+
+        [1]: 5 9
+        [2]: 14
+
+        Finally, the index is built by concatenating these lists together:
+
+        _index = 14 5 9 3 2 4 5
+
+        An offset storing the start of the first row is also stored:
+
+        _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.
+        """
+        row0 = list(map(len, self._lists))
+
+        if len(row0) == 1:
+            self._index[:] = row0
+            self._offset = 0
+            return
+
+        head = iter(row0)
+        tail = iter(head)
+        row1 = list(starmap(add, zip(head, tail)))
+
+        if len(row0) & 1:
+            row1.append(row0[-1])
+
+        if len(row1) == 1:
+            self._index[:] = row1 + row0
+            self._offset = 1
+            return
+
+        size = 2 ** (int(log_e(len(row1) - 1, 2)) + 1)
+        row1.extend(repeat(0, size - len(row1)))
+        tree = [row0, row1]
+
+        while len(tree[-1]) > 1:
+            head = iter(tree[-1])
+            tail = iter(head)
+            row = list(starmap(add, zip(head, tail)))
+            tree.append(row)
+
+        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)
+
+            if step == 1 and start < stop:
+                if start == 0 and stop == self._len:
+                    return self._clear()
+                elif self._len <= 8 * (stop - start):
+                    values = self._getitem(slice(None, start))
+                    if stop < self._len:
+                        values += self._getitem(slice(stop, None))
+                    self._clear()
+                    return self._update(values)
+
+            indices = range(start, stop, step)
+
+            # Delete items from greatest index to least so
+            # that the indices remain valid throughout iteration.
+
+            if step > 0:
+                indices = reversed(indices)
+
+            _pos, _delete = self._pos, self._delete
+
+            for index in indices:
+                pos, idx = _pos(index)
+                _delete(pos, idx)
+        else:
+            pos, idx = self._pos(idx)
+            self._delete(pos, idx)
+
+    _delitem = __delitem__
+
+    def __getitem__(self, idx):
+        """Return the element at *idx*. Supports slicing."""
+        _lists = self._lists
+
+        if isinstance(idx, slice):
+            start, stop, step = idx.indices(self._len)
+
+            if step == 1 and start < stop:
+                if start == 0 and stop == self._len:
+                    return reduce(iadd, self._lists, [])
+
+                start_pos, start_idx = self._pos(start)
+
+                if stop == self._len:
+                    stop_pos = len(_lists) - 1
+                    stop_idx = len(_lists[stop_pos])
+                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)
+                result += _lists[stop_pos][:stop_idx]
+
+                return result
+
+            if step == -1 and start > stop:
+                result = self._getitem(slice(stop + 1, start + 1))
+                result.reverse()
+                return result
+
+            # Return a list because a negative step could
+            # reverse the order of the items and this could
+            # be the desired behavior.
+
+            indices = range(start, stop, step)
+            return list(self._getitem(index) for index in indices)
+        else:
+            if self._len:
+                if idx == 0:
+                    return _lists[0][0]
+                elif idx == -1:
+                    return _lists[-1][-1]
+            else:
+                raise IndexError('list index out of range')
+
+            if 0 <= idx < len(_lists[0]):
+                return _lists[0][idx]
+
+            len_last = len(_lists[-1])
+
+            if -len_last < idx < 0:
+                return _lists[-1][len_last + idx]
+
+            pos, idx = self._pos(idx)
+            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)
+
+                except ValueError:
+
+                    # Roll back changes from log.
+
+                    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.
+
+                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)
+            _check_order(index, value)
+            _lists[pos][loc] = value
+            if len(_lists[pos]) == (loc + 1):
+                _maxes[pos] = value
+
+    def __iter__(self):
+        """
+        Return an iterator over the Sequence.
+
+        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.
+
+        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
+
+        SortedList 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.
+
+        Implemented to override MutableSequence.reverse which provides an
+        erroneous default implementation.
+
+        """
+        raise NotImplementedError('.reverse() not defined')
+
+    def islice(self, start=None, stop=None, reverse=False):
+
+        """
+        Returns an iterator that slices `self` from `start` to `stop` index,
+        inclusive and exclusive respectively.
+
+        When `reverse` is `True`, values are yielded from the iterator in
+        reverse order.
+
+        Both `start` and `stop` default to `None` which is automatically
+        inclusive of the beginning and end.
+        """
+        _len = self._len
+
+        if not _len:
+            return iter(())
+
+        start, stop, _ = slice(start, stop).indices(self._len)
+
+        if start >= stop:
+            return iter(())
+
+        _pos = self._pos
+
+        min_pos, min_idx = _pos(start)
+
+        if stop == _len:
+            max_pos = len(self._lists) - 1
+            max_idx = len(self._lists[-1])
+        else:
+            max_pos, max_idx = _pos(stop)
+
+        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.
+
+        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:
+            return chain(
+                reversed(_lists[max_pos][:max_idx]),
+                reversed(_lists[min_pos][min_idx:]),
+            )
+        elif not reverse:
+            return chain(
+                _lists[min_pos][min_idx:],
+                chain.from_iterable(_lists[(min_pos + 1):max_pos]),
+                _lists[max_pos][:max_idx],
+            )
+
+        temp = map(reversed, reversed(_lists[(min_pos + 1):max_pos]))
+        return chain(
+            reversed(_lists[max_pos][:max_idx]),
+            chain.from_iterable(temp),
+            reversed(_lists[min_pos][min_idx:]),
+        )
+
+    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.
+
+        Both `minimum` and `maximum` default to `None` which is automatically
+        inclusive of the start and end of the list, respectively.
+
+        When `reverse` is `True` the values are yielded from the iterator in
+        reverse order; `reverse` defaults to `False`.
+        """
+        _maxes = self._maxes
+
+        if not _maxes:
+            return iter(())
+
+        _lists = self._lists
+
+        # Calculate the minimum (pos, idx) pair. By default this location
+        # will be inclusive in our calculation.
+
+        if minimum is None:
+            min_pos = 0
+            min_idx = 0
+        else:
+            if inclusive[0]:
+                min_pos = bisect_left(_maxes, minimum)
+
+                if min_pos == len(_maxes):
+                    return iter(())
+
+                min_idx = bisect_left(_lists[min_pos], minimum)
+            else:
+                min_pos = bisect_right(_maxes, minimum)
+
+                if min_pos == len(_maxes):
+                    return iter(())
+
+                min_idx = bisect_right(_lists[min_pos], minimum)
+
+        # Calculate the maximum (pos, idx) pair. By default this location
+        # will be exclusive in our calculation.
+
+        if maximum is None:
+            max_pos = len(_maxes) - 1
+            max_idx = len(_lists[max_pos])
+        else:
+            if inclusive[1]:
+                max_pos = bisect_right(_maxes, maximum)
+
+                if max_pos == len(_maxes):
+                    max_pos -= 1
+                    max_idx = len(_lists[max_pos])
+                else:
+                    max_idx = bisect_right(_lists[max_pos], maximum)
+            else:
+                max_pos = bisect_left(_maxes, maximum)
+
+                if max_pos == len(_maxes):
+                    max_pos -= 1
+                    max_idx = len(_lists[max_pos])
+                else:
+                    max_idx = bisect_left(_lists[max_pos], maximum)
+
+        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
+
+    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.
+        """
+        _maxes = self._maxes
+
+        if not _maxes:
+            return 0
+
+        pos = bisect_left(_maxes, val)
+
+        if pos == len(_maxes):
+            return self._len
+
+        idx = bisect_left(self._lists[pos], val)
+
+        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.
+        """
+        _maxes = self._maxes
+
+        if not _maxes:
+            return 0
+
+        pos = bisect_right(_maxes, val)
+
+        if pos == len(_maxes):
+            return self._len
+
+        idx = bisect_right(self._lists[pos], val)
+
+        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
+        _maxes = self._maxes
+
+        if not _maxes:
+            return 0
+
+        pos_left = bisect_left(_maxes, val)
+
+        if pos_left == len(_maxes):
+            return 0
+
+        _lists = self._lists
+        idx_left = bisect_left(_lists[pos_left], val)
+        pos_right = bisect_right(_maxes, val)
+
+        if pos_right == len(_maxes):
+            return self._len - self._loc(pos_left, idx_left)
+
+        idx_right = bisect_right(_lists[pos_right], val)
+
+        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)
+
+    __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
+        _maxes = self._maxes
+
+        if not _maxes:
+            _maxes.append(val)
+            _lists.append([val])
+            self._len = 1
+            return
+
+        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)
+
+        _maxes[pos] = val
+        _lists[pos].append(val)
+        self._len += 1
+        self._expand(pos)
+
+    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)
+
+        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')
+
+        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)
+
+            if len(_lists[-1]) < self._half:
+                _lists[-1].extend(values[:_load])
+                _maxes[-1] = _lists[-1][-1]
+                offset = _load
+
+        len_lists = len(_lists)
+
+        for idx in range(offset, len(values), _load):
+            _lists.append(values[idx:(idx + _load)])
+            _maxes.append(_lists[-1][-1])
+
+        _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[:]
+
+        self._len += len(values)
+
+    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
+
+        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
+
+        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
+
+        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
+
+        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
+
+        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)
+
+    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:
+            val = _lists[0][0]
+            self._delete(0, 0)
+            return val
+
+        if idx == -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)
+            return val
+
+        len_last = len(_lists[-1])
+
+        if -len_last < idx < 0:
+            pos = len(_lists) - 1
+            loc = len_last + idx
+            val = _lists[pos][loc]
+            self._delete(pos, loc)
+            return val
+
+        pos, idx = self._pos(idx)
+        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.
+        """
+        # pylint: disable=arguments-differ
+        _len = self._len
+
+        if not _len:
+            raise ValueError('{0!r} is not in list'.format(val))
+
+        if start is None:
+            start = 0
+        if start < 0:
+            start += _len
+        if start < 0:
+            start = 0
+
+        if stop is None:
+            stop = _len
+        if stop < 0:
+            stop += _len
+        if stop > _len:
+            stop = _len
+
+        if stop <= start:
+            raise ValueError('{0!r} is not in list'.format(val))
+
+        _maxes = self._maxes
+        pos_left = bisect_left(_maxes, val)
+
+        if pos_left == len(_maxes):
+            raise ValueError('{0!r} is not in list'.format(val))
+
+        _lists = self._lists
+        idx_left = bisect_left(_lists[pos_left], val)
+
+        if _lists[pos_left][idx_left] != val:
+            raise ValueError('{0!r} is not in list'.format(val))
+
+        stop -= 1
+        left = self._loc(pos_left, idx_left)
+
+        if start <= left:
+            if left <= stop:
+                return left
+        else:
+            right = self._bisect_right(val) - 1
+
+            if start <= right:
+                return start
+
+        raise ValueError('{0!r} is not in list'.format(val))
+
+    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)
+        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*.
+        """
+        self._update(that)
+        return self
+
+    def __mul__(self, that):
+        """
+        Return a new sorted list containing *that* shallow copies of each item
+        in SortedList.
+        """
+        values = reduce(iadd, self._lists, []) * that
+        return self.__class__(values)
+
+    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
+
+    def _make_cmp(self, seq_op, doc):
+        "Make comparator method."
+        def comparer(self, that):
+            "Compare method for sorted list and sequence."
+            # pylint: disable=protected-access
+            if not isinstance(that, Sequence):
+                return NotImplemented
+
+            self_len = self._len
+            len_that = len(that)
+
+            if self_len != len_that:
+                if seq_op is op.eq:
+                    return False
+                if seq_op is op.ne:
+                    return True
+
+            for alpha, beta in zip(self, that):
+                if alpha != beta:
+                    return seq_op(alpha, beta)
+
+            return seq_op(self_len, len_that)
+
+        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)
+
+        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))
+
+    def _check(self):
+        try:
+            # Check load parameters.
+
+            assert self._load >= 4
+            assert self._half == (self._load >> 1)
+            assert self._dual == (self._load << 1)
+
+            # Check empty sorted list case.
+
+            if self._maxes == []:
+                assert self._lists == []
+                return
+
+            assert self._maxes and self._lists
+
+            # Check all sublists are sorted.
+
+            assert all(sublist[pos - 1] <= sublist[pos]
+                       for sublist in self._lists
+                       for pos in range(1, len(sublist)))
+
+            # 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]
+
+            # Check length of _maxes and _lists match.
+
+            assert len(self._maxes) == len(self._lists)
+
+            # Check _maxes is a map of _lists.
+
+            assert all(self._maxes[pos] == self._lists[pos][-1]
+                       for pos in range(len(self._maxes)))
+
+            # Check load level is less than _dual.
+
+            assert all(len(sublist) <= self._dual for sublist in self._lists)
+
+            # Check load level is greater than _half 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.
+
+            if self._index:
+                assert len(self._index) == self._offset + len(self._lists)
+                assert self._len == self._index[0]
+
+                def test_offset_pos(pos):
+                    "Test positional indexing offset."
+                    from_index = self._index[self._offset + pos]
+                    return from_index == len(self._lists[pos])
+
+                assert all(test_offset_pos(pos)
+                           for pos in range(len(self._lists)))
+
+                for pos in range(self._offset):
+                    child = (pos << 1) + 1
+                    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
+
+        except:
+            import sys
+            import traceback
+
+            traceback.print_exc(file=sys.stdout)
+
+            print('len', self._len)
+            print('load', self._load, self._half, self._dual)
+            print('offset', self._offset)
+            print('len_index', len(self._index))
+            print('index', self._index)
+            print('len_maxes', len(self._maxes))
+            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.
+    """
+    # 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.
+
+        An optional *iterable* provides an initial series of items to populate
+        the SortedListWithKey.
+
+        An 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.
+        """
+        # pylint: disable=super-init-not-called
+        self._len = 0
+        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."""
+        return self._key
+
+    def clear(self):
+        """Remove all the elements from the list."""
+        self._len = 0
+        del self._lists[:]
+        del self._keys[:]
+        del self._maxes[:]
+        del self._index[:]
+
+    _clear = clear
+
+    def add(self, val):
+        """Add the element *val* to the list."""
+        _lists = self._lists
+        _keys = self._keys
+        _maxes = self._maxes
+
+        key = self._key(val)
+
+        if _maxes:
+            pos = bisect_right(_maxes, key)
+
+            if pos == len(_maxes):
+                pos -= 1
+                _lists[pos].append(val)
+                _keys[pos].append(key)
+                _maxes[pos] = key
+            else:
+                idx = bisect_right(_keys[pos], key)
+                _lists[pos].insert(idx, val)
+                _keys[pos].insert(idx, key)
+
+            self._expand(pos)
+        else:
+            _lists.append([val])
+            _keys.append([key])
+            _maxes.append(key)
+
+        self._len += 1
+
+    def _expand(self, pos):
+        """Splits sublists that are more than double the load level.
+
+        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.
+
+        """
+        _lists = self._lists
+        _keys = self._keys
+        _index = self._index
+
+        if len(_keys[pos]) > self._dual:
+            _maxes = self._maxes
+            _load = self._load
+
+            _lists_pos = _lists[pos]
+            _keys_pos = _keys[pos]
+            half = _lists_pos[_load:]
+            half_keys = _keys_pos[_load:]
+            del _lists_pos[_load:]
+            del _keys_pos[_load:]
+            _maxes[pos] = _keys_pos[-1]
+
+            _lists.insert(pos + 1, half)
+            _keys.insert(pos + 1, half_keys)
+            _maxes.insert(pos + 1, half_keys[-1])
+
+            del _index[:]
+        else:
+            if _index:
+                child = self._offset + pos
+                while child:
+                    _index[child] += 1
+                    child = (child - 1) >> 1
+                _index[0] += 1
+
+    def update(self, iterable):
+        """Update the list by adding all elements from *iterable*."""
+        _lists = self._lists
+        _keys = self._keys
+        _maxes = self._maxes
+        values = sorted(iterable, key=self._key)
+
+        if _maxes:
+            if len(values) * 4 >= self._len:
+                values.extend(chain.from_iterable(_lists))
+                values.sort(key=self._key)
+                self._clear()
+            else:
+                _add = self.add
+                for val in values:
+                    _add(val)
+                return
+
+        _load = self._load
+        _lists.extend(values[pos:(pos + _load)]
+                      for pos in range(0, len(values), _load))
+        _keys.extend(list(map(self._key, _list)) for _list in _lists)
+        _maxes.extend(sublist[-1] for sublist in _keys)
+        self._len = len(values)
+        del self._index[:]
+
+    _update = update
+
+    def __contains__(self, val):
+        """Return True if and only if *val* is an element in the list."""
+        _maxes = self._maxes
+
+        if not _maxes:
+            return False
+
+        key = self._key(val)
+        pos = bisect_left(_maxes, key)
+
+        if pos == len(_maxes):
+            return False
+
+        _lists = self._lists
+        _keys = self._keys
+
+        idx = bisect_left(_keys[pos], key)
+
+        len_keys = len(_keys)
+        len_sublist = len(_keys[pos])
+
+        while True:
+            if _keys[pos][idx] != key:
+                return False
+            if _lists[pos][idx] == val:
+                return True
+            idx += 1
+            if idx == len_sublist:
+                pos += 1
+                if pos == len_keys:
+                    return False
+                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.
+        """
+        _maxes = self._maxes
+
+        if not _maxes:
+            return
+
+        key = self._key(val)
+        pos = bisect_left(_maxes, key)
+
+        if pos == len(_maxes):
+            return
+
+        _lists = self._lists
+        _keys = self._keys
+        idx = bisect_left(_keys[pos], key)
+        len_keys = len(_keys)
+        len_sublist = len(_keys[pos])
+
+        while True:
+            if _keys[pos][idx] != key:
+                return
+            if _lists[pos][idx] == val:
+                self._delete(pos, idx)
+                return
+            idx += 1
+            if idx == len_sublist:
+                pos += 1
+                if pos == len_keys:
+                    return
+                len_sublist = len(_keys[pos])
+                idx = 0
+
+    def remove(self, val):
+        """
+        Remove first occurrence of *val*.
+
+        Raises ValueError if *val* is not present.
+        """
+        _maxes = self._maxes
+
+        if not _maxes:
+            raise ValueError('{0!r} not in list'.format(val))
+
+        key = self._key(val)
+        pos = bisect_left(_maxes, key)
+
+        if pos == len(_maxes):
+            raise ValueError('{0!r} not in list'.format(val))
+
+        _lists = self._lists
+        _keys = self._keys
+        idx = bisect_left(_keys[pos], key)
+        len_keys = len(_keys)
+        len_sublist = len(_keys[pos])
+
+        while True:
+            if _keys[pos][idx] != key:
+                raise ValueError('{0!r} not in list'.format(val))
+            if _lists[pos][idx] == val:
+                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))
+                len_sublist = len(_keys[pos])
+                idx = 0
+
+    def _delete(self, pos, idx):
+        """
+        Delete the item 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.
+        """
+        _lists = self._lists
+        _keys = self._keys
+        _maxes = self._maxes
+        _index = self._index
+        keys_pos = _keys[pos]
+        lists_pos = _lists[pos]
+
+        del keys_pos[idx]
+        del lists_pos[idx]
+        self._len -= 1
+
+        len_keys_pos = len(keys_pos)
+
+        if len_keys_pos > self._half:
+
+            _maxes[pos] = keys_pos[-1]
+
+            if _index:
+                child = self._offset + pos
+                while child > 0:
+                    _index[child] -= 1
+                    child = (child - 1) >> 1
+                _index[0] -= 1
+
+        elif len(_keys) > 1:
+
+            if not pos:
+                pos += 1
+
+            prev = pos - 1
+            _keys[prev].extend(_keys[pos])
+            _lists[prev].extend(_lists[pos])
+            _maxes[prev] = _keys[prev][-1]
+
+            del _lists[pos]
+            del _keys[pos]
+            del _maxes[pos]
+            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.
+
+        Both `minimum` and `maximum` default to `None` which is automatically
+        inclusive of the start and end of the list, respectively.
+
+        When `reverse` is `True` the values are yielded from the iterator in
+        reverse order; `reverse` defaults to `False`.
+        """
+        minimum = self._key(minimum) if minimum is not None else None
+        maximum = self._key(maximum) if maximum is not None else None
+        return self._irange_key(
+            min_key=minimum, max_key=maximum,
+            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`.
+
+        Both `min_key` and `max_key` default to `None` which is automatically
+        inclusive of the start and end of the list, respectively.
+
+        When `reverse` is `True` the values are yielded from the iterator in
+        reverse order; `reverse` defaults to `False`.
+        """
+        _maxes = self._maxes
+
+        if not _maxes:
+            return iter(())
+
+        _keys = self._keys
+
+        # Calculate the minimum (pos, idx) pair. By default this location
+        # will be inclusive in our calculation.
+
+        if min_key is None:
+            min_pos = 0
+            min_idx = 0
+        else:
+            if inclusive[0]:
+                min_pos = bisect_left(_maxes, min_key)
+
+                if min_pos == len(_maxes):
+                    return iter(())
+
+                min_idx = bisect_left(_keys[min_pos], min_key)
+            else:
+                min_pos = bisect_right(_maxes, min_key)
+
+                if min_pos == len(_maxes):
+                    return iter(())
+
+                min_idx = bisect_right(_keys[min_pos], min_key)
+
+        # Calculate the maximum (pos, idx) pair. By default this location
+        # will be exclusive in our calculation.
+
+        if max_key is None:
+            max_pos = len(_maxes) - 1
+            max_idx = len(_keys[max_pos])
+        else:
+            if inclusive[1]:
+                max_pos = bisect_right(_maxes, max_key)
+
+                if max_pos == len(_maxes):
+                    max_pos -= 1
+                    max_idx = len(_keys[max_pos])
+                else:
+                    max_idx = bisect_right(_keys[max_pos], max_key)
+            else:
+                max_pos = bisect_left(_maxes, max_key)
+
+                if max_pos == len(_maxes):
+                    max_pos -= 1
+                    max_idx = len(_keys[max_pos])
+                else:
+                    max_idx = bisect_left(_keys[max_pos], max_key)
+
+        return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)
+
+    _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):
+        """
+        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_right(self._key(val))
+
+    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.
+        """
+        _maxes = self._maxes
+
+        if not _maxes:
+            return 0
+
+        pos = bisect_left(_maxes, key)
+
+        if pos == len(_maxes):
+            return self._len
+
+        idx = bisect_left(self._keys[pos], key)
+
+        return self._loc(pos, idx)
+
+    _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.
+        """
+        _maxes = self._maxes
+
+        if not _maxes:
+            return 0
+
+        pos = bisect_right(_maxes, key)
+
+        if pos == len(_maxes):
+            return self._len
+
+        idx = bisect_right(self._keys[pos], key)
+
+        return self._loc(pos, idx)
+
+    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."""
+        _maxes = self._maxes
+
+        if not _maxes:
+            return 0
+
+        key = self._key(val)
+        pos = bisect_left(_maxes, key)
+
+        if pos == len(_maxes):
+            return 0
+
+        _lists = self._lists
+        _keys = self._keys
+        idx = bisect_left(_keys[pos], key)
+        total = 0
+        len_keys = len(_keys)
+        len_sublist = len(_keys[pos])
+
+        while True:
+            if _keys[pos][idx] != key:
+                return total
+            if _lists[pos][idx] == val:
+                total += 1
+            idx += 1
+            if idx == len_sublist:
+                pos += 1
+                if pos == len_keys:
+                    return total
+                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
+
+        if key < _keys[pos][-1]:
+            msg = '{0!r} not in sort order at index {1}'.format(val, self._len)
+            raise ValueError(msg)
+
+        _lists[pos].append(val)
+        _keys[pos].append(key)
+        _maxes[pos] = key
+        self._len += 1
+        self._expand(pos)
+
+    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))
+
+        if any(keys[pos - 1] > keys[pos]
+               for pos in range(1, len(keys))):
+            raise ValueError('given sequence not in sort order')
+
+        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)
+
+            if len(_keys[-1]) < self._half:
+                _lists[-1].extend(values[:_load])
+                _keys[-1].extend(keys[:_load])
+                _maxes[-1] = _keys[-1][-1]
+                offset = _load
+
+        len_keys = len(_keys)
+
+        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])
+
+        _index = self._index
+
+        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[:]
+
+        self._len += len(values)
+
+    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))
+
+        if start is None:
+            start = 0
+        if start < 0:
+            start += _len
+        if start < 0:
+            start = 0
+
+        if stop is None:
+            stop = _len
+        if stop < 0:
+            stop += _len
+        if stop > _len:
+            stop = _len
+
+        if stop <= start:
+            raise ValueError('{0!r} is not in list'.format(val))
+
+        _maxes = self._maxes
+        key = self._key(val)
+        pos = bisect_left(_maxes, key)
+
+        if pos == len(_maxes):
+            raise ValueError('{0!r} is not in list'.format(val))
+
+        stop -= 1
+        _lists = self._lists
+        _keys = self._keys
+        idx = bisect_left(_keys[pos], key)
+        len_keys = len(_keys)
+        len_sublist = len(_keys[pos])
+
+        while True:
+            if _keys[pos][idx] != key:
+                raise ValueError('{0!r} is not in list'.format(val))
+            if _lists[pos][idx] == val:
+                loc = self._loc(pos, idx)
+                if start <= loc <= stop:
+                    return loc
+                elif loc > stop:
+                    break
+            idx += 1
+            if idx == len_sublist:
+                pos += 1
+                if pos == len_keys:
+                    raise ValueError('{0!r} is not in list'.format(val))
+                len_sublist = len(_keys[pos])
+                idx = 0
+
+        raise ValueError('{0!r} is not in list'.format(val))
+
+    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)
+        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.
+        """
+        values = reduce(iadd, self._lists, []) * that
+        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 __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)
+
+    def _check(self):
+        try:
+            # Check load parameters.
+
+            assert self._load >= 4
+            assert self._half == (self._load >> 1)
+            assert self._dual == (self._load << 1)
+
+            # Check empty sorted list case.
+
+            if self._maxes == []:
+                assert self._keys == []
+                assert self._lists == []
+                return
+
+            assert self._maxes and self._keys and 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)))
+
+            # 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)))
+
+            # Check _maxes is a map of _keys.
+
+            assert all(self._maxes[pos] == self._keys[pos][-1]
+                       for pos in range(len(self._maxes)))
+
+            # Check load level is less than _dual.
+
+            assert all(len(sublist) <= self._dual for sublist in self._lists)
+
+            # Check load level is greater than _half 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.
+
+            if self._index:
+                assert len(self._index) == self._offset + len(self._lists)
+                assert self._len == self._index[0]
+
+                def test_offset_pos(pos):
+                    "Test positional indexing offset."
+                    from_index = self._index[self._offset + pos]
+                    return from_index == len(self._lists[pos])
+
+                assert all(test_offset_pos(pos)
+                           for pos in range(len(self._lists)))
+
+                for pos in range(self._offset):
+                    child = (pos << 1) + 1
+                    if self._index[pos] == 0:
+                        assert child >= len(self._index)
+                    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
+
+        except:
+            import sys
+            import traceback
+
+            traceback.print_exc(file=sys.stdout)
+
+            print('len', self._len)
+            print('load', self._load, self._half, self._dual)
+            print('offset', self._offset)
+            print('len_index', len(self._index))
+            print('index', self._index)
+            print('len_maxes', len(self._maxes))
+            print('maxes', self._maxes)
+            print('len_keys', len(self._keys))
+            print('keys', self._keys)
+            print('len_lists', len(self._lists))
+            print('lists', self._lists)
+
+            raise
diff --git a/python/ovs/compat/sortedcontainers/sortedset.py b/python/ovs/compat/sortedcontainers/sortedset.py
new file mode 100644
index 0000000..6d82b38
--- /dev/null
+++ b/python/ovs/compat/sortedcontainers/sortedset.py
@@ -0,0 +1,327 @@
+"""Sorted set implementation.
+
+"""
+
+from collections import Set, MutableSet, Sequence
+from itertools import chain
+import operator as op
+
+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.
+
+    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.
+
+        An optional *iterable* provides an initial series of items to populate
+        the `SortedSet`.
+
+        An 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.
+        """
+        self._key = key
+
+        if not hasattr(self, '_set'):
+            self._set = set()
+
+        _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)
+
+        _list = self._list
+        self.bisect_left = _list.bisect_left
+        self.bisect = _list.bisect
+        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
+
+        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
+
+        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."""
+        sorted_set = object.__new__(cls)
+        sorted_set._set = values  # pylint: disable=protected-access
+        sorted_set.__init__(key=key)
+        return sorted_set
+
+    def __contains__(self, value):
+        """Return True if and only if *value* is an element in the set."""
+        return value in self._set
+
+    def __getitem__(self, index):
+        """
+        Return the element at position *index*.
+
+        Supports slice notation and negative indexes.
+        """
+        return self._list[index]
+
+    def __delitem__(self, index):
+        """
+        Remove the element at position *index*.
+
+        Supports slice notation and negative indexes.
+        """
+        _set = self._set
+        _list = self._list
+        if isinstance(index, slice):
+            values = _list[index]
+            _set.difference_update(values)
+        else:
+            value = _list[index]
+            _set.remove(value)
+        del _list[index]
+
+    def _make_cmp(self, set_op, 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)
+            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)
+
+        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')
+
+    def __len__(self):
+        """Return the number of elements in the set."""
+        return len(self._set)
+
+    def __iter__(self):
+        """
+        Return an iterator over the Set. Elements are iterated in their sorted
+        order.
+
+        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.
+
+        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."""
+        _set = self._set
+        if value not in _set:
+            _set.add(value)
+            self._list.add(value)
+
+    def clear(self):
+        """Remove all elements from the set."""
+        self._set.clear()
+        self._list.clear()
+
+    def copy(self):
+        """Create a shallow copy of the 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 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.
+        """
+        _set = self._set
+        if value in _set:
+            _set.remove(value)
+            self._list.discard(value)
+
+    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.
+        """
+        # 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.
+        """
+        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*.
+        """
+        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*.
+        """
+        _set = self._set
+        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
+            for value in values:
+                _discard(value)
+        return self
+
+    __isub__ = difference_update
+
+    def intersection(self, *iterables):
+        """
+        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)
+
+    __and__ = intersection
+    __rand__ = __and__
+
+    def intersection_update(self, *iterables):
+        """
+        Update the set, keeping only elements found in it and all *iterables*.
+        """
+        _set = self._set
+        _list = self._list
+        _set.intersection_update(*iterables)
+        _list.clear()
+        _list.update(_set)
+        return self
+
+    __iand__ = intersection_update
+
+    def symmetric_difference(self, that):
+        """
+        Return a new set with elements in either *self* or *that* but not both.
+        """
+        diff = self._set.symmetric_difference(that)
+        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.
+        """
+        _set = self._set
+        _list = self._list
+        _set.symmetric_difference_update(that)
+        _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 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*."""
+        _set = self._set
+        values = set(chain(*iterables))
+        if (4 * len(values)) > len(_set):
+            _list = self._list
+            _set.update(values)
+            _list.clear()
+            _list.update(_set)
+        else:
+            _add = self.add
+            for value in values:
+                _add(value)
+        return self
+
+    __ior__ = update
+    _update = update
+
+    def __reduce__(self):
+        return (type(self), (self._set, self._key))
+
+    @recursive_repr
+    def __repr__(self):
+        _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)
+
+    def _check(self):
+        # pylint: disable=protected-access
+        self._list._check()
+        assert len(self._set) == len(self._list)
+        _set = self._set
+        assert all(val in _set for val in self._list)
diff --git a/python/ovs/db/custom_index.py b/python/ovs/db/custom_index.py
new file mode 100644
index 0000000..587caf5
--- /dev/null
+++ b/python/ovs/db/custom_index.py
@@ -0,0 +1,154 @@
+import collections
+import functools
+import operator
+try:
+    from UserDict import IterableUserDict as DictBase
+except ImportError:
+    from collections import UserDict as DictBase
+
+try:
+    import sortedcontainers
+except ImportError:
+    from ovs.compat import sortedcontainers
+
+from ovs.db import data
+
+OVSDB_INDEX_ASC = "ASC"
+OVSDB_INDEX_DESC = "DESC"
+ColumnIndex = collections.namedtuple('ColumnIndex',
+                                     ['column', 'direction', 'key'])
+
+
+class MultiColumnIndex(object):
+    def __init__(self, name):
+        self.name = name
+        self.columns = []
+        self.clear()
+
+    def __repr__(self):
+        return "{}(name={})".format(self.__class__.__name__, self.name)
+
+    def __str__(self):
+        return repr(self) + " columns={} values={}".format(
+            self.columns, [str(v) for v in self.values])
+
+    def add_column(self, column, direction=OVSDB_INDEX_ASC, key=None):
+        self.columns.append(ColumnIndex(column, direction,
+                             key or operator.attrgetter(column)))
+
+    def add_columns(self, *columns):
+        self.columns.extend(ColumnIndex(col, OVSDB_INDEX_ASC,
+                                        operator.attrgetter(col))
+                            for col in columns)
+
+    def _cmp(self, a, b):
+        for col, direction, key in self.columns:
+            aval, bval = key(a), key(b)
+            if aval == bval:
+                continue
+            result = (aval > bval) - (aval < bval)
+            return result if direction == OVSDB_INDEX_ASC else -result
+        return 0
+
+    def index_entry_from_row(self, row):
+        return row._table.rows.IndexEntry(
+            uuid=row.uuid,
+            **{c.column: getattr(row, c.column) for c in self.columns})
+
+    def add(self, row):
+        if not all(hasattr(row, col.column) for col in self.columns):
+            # This is a new row, but it hasn't had the necessary columns set
+            # We'll add it later
+            return
+        self.values.add(self.index_entry_from_row(row))
+
+    def remove(self, row):
+        self.values.remove(self.index_entry_from_row(row))
+
+    def clear(self):
+        self.values = sortedcontainers.SortedListWithKey(
+            key=functools.cmp_to_key(self._cmp))
+
+    def irange(self, start, end):
+        return iter(r._table.rows[r.uuid]
+                    for r in self.values.irange(start, end))
+
+    def __iter__(self):
+        return iter(r._table.rows[r.uuid] for r in self.values)
+
+
+class IndexedRows(DictBase, object):
+    def __init__(self, table, *args, **kwargs):
+        super(IndexedRows, self).__init__(*args, **kwargs)
+        self.table = table
+        self.indexes = {}
+        self.IndexEntry = IndexEntryClass(table)
+
+    def index_create(self, name):
+        if name in self.indexes:
+            raise ValueError("An index named {} already exists".format(name))
+        index = self.indexes[name] = MultiColumnIndex(name)
+        return index
+
+    def __setitem__(self, key, item):
+        self.data[key] = item
+        for index in self.indexes.values():
+            index.add(item)
+
+    def __delitem__(self, key):
+        val = self.data[key]
+        del self.data[key]
+        for index in self.indexes.values():
+            index.remove(val)
+
+    def clear(self):
+        self.data.clear()
+        for index in self.indexes.values():
+            index.clear()
+
+    # Nothing uses the methods below, though they'd be easy to implement
+    def update(self, dict=None, **kwargs):
+        raise NotImplementedError()
+
+    def setdefault(self, key, failobj=None):
+        raise NotImplementedError()
+
+    def pop(self, key, *args):
+        raise NotImplementedError()
+
+    def popitem(self):
+        raise NotImplementedError()
+
+    @classmethod
+    def fromkeys(cls, iterable, value=None):
+        raise NotImplementedError()
+
+
+def IndexEntryClass(table):
+    """Create a class used represent Rows in indexes
+
+    ovs.db.idl.Row, being inherently tied to transaction processing and being
+    initialized with dicts of Datums, is not really useable as an object to
+    pass to and store in indexes. This method will create a class named after
+    the table's name that is initialized with that Table Row's default values.
+    For example:
+
+    Port = IndexEntryClass(idl.tables['Port'])
+
+    will create a Port class. This class can then be used to search custom
+    indexes. For example:
+
+    for port in idx.iranage(Port(name="test1"), Port(name="test9")):
+       ...
+    """
+
+    def defaults_uuid_to_row(atom, base):
+        return atom.value
+
+    columns = ['uuid'] + list(table.columns.keys())
+    cls = collections.namedtuple(table.name, columns)
+    cls._table = table
+    cls.__new__.__defaults__ = (None,) + tuple(
+        data.Datum.default(c.type).to_python(defaults_uuid_to_row)
+        for c in table.columns.values())
+    return cls
diff --git a/python/ovs/db/idl.py b/python/ovs/db/idl.py
index 5a4d129..564977c 100644
--- a/python/ovs/db/idl.py
+++ b/python/ovs/db/idl.py
@@ -22,6 +22,7 @@ import ovs.jsonrpc
 import ovs.ovsuuid
 import ovs.poller
 import ovs.vlog
+from ovs.db import custom_index
 from ovs.db import error
 
 import six
@@ -148,11 +149,23 @@ class Idl(object):
                 if not hasattr(column, 'alert'):
                     column.alert = True
             table.need_table = False
-            table.rows = {}
+            table.rows = custom_index.IndexedRows(table)
             table.idl = self
             table.condition = [True]
             table.cond_changed = False
 
+    def index_create(self, table, name):
+        """Create a named multi-column index on a table"""
+        return self.tables[table].rows.index_create(name)
+
+    def index_irange(self, table, name, start, end):
+        """Return items in a named index between start/end inclusive"""
+        return self.tables[table].rows.indexes[name].irange(start, end)
+
+    def index_equal(self, table, name, value):
+        """Return items in a named index matching a value"""
+        return self.tables[table].rows.indexes[name].irange(value, value)
+
     def close(self):
         """Closes the connection to the database.  The IDL will no longer
         update."""
@@ -359,7 +372,7 @@ class Idl(object):
         for table in six.itervalues(self.tables):
             if table.rows:
                 changed = True
-                table.rows = {}
+                table.rows = custom_index.IndexedRows(table)
 
         if changed:
             self.change_seqno += 1
@@ -511,8 +524,9 @@ class Idl(object):
             else:
                 row_update = row_update['initial']
             self.__add_default(table, row_update)
-            if self.__row_update(table, row, row_update):
-                changed = True
+            changed = self.__row_update(table, row, row_update)
+            table.rows[uuid] = row
+            if changed:
                 self.notify(ROW_CREATE, row)
         elif "modify" in row_update:
             if not row:
@@ -542,15 +556,19 @@ class Idl(object):
                           % (uuid, table.name))
         elif not old:
             # Insert row.
+            op = ROW_CREATE
             if not row:
                 row = self.__create_row(table, uuid)
                 changed = True
             else:
                 # XXX rate-limit
+                op = ROW_UPDATE
                 vlog.warn("cannot add existing row %s to table %s"
                           % (uuid, table.name))
-            if self.__row_update(table, row, new):
-                changed = True
+            changed |= self.__row_update(table, row, new)
+            if op == ROW_CREATE:
+                table.rows[uuid] = row
+            if changed:
                 self.notify(ROW_CREATE, row)
         else:
             op = ROW_UPDATE
@@ -561,8 +579,10 @@ class Idl(object):
                 # XXX rate-limit
                 vlog.warn("cannot modify missing row %s in table %s"
                           % (uuid, table.name))
-            if self.__row_update(table, row, new):
-                changed = True
+            changed |= self.__row_update(table, row, new)
+            if op == ROW_CREATE:
+                table.rows[uuid] = row
+            if changed:
                 self.notify(op, row, Row.from_json(self, table, uuid, old))
         return changed
 
@@ -638,8 +658,7 @@ class Idl(object):
         data = {}
         for column in six.itervalues(table.columns):
             data[column.name] = ovs.db.data.Datum.default(column.type)
-        row = table.rows[uuid] = Row(self, table, uuid, data)
-        return row
+        return Row(self, table, uuid, data)
 
     def __error(self):
         self._session.force_reconnect()
@@ -844,7 +863,17 @@ class Row(object):
             vlog.err("attempting to write bad value to column %s (%s)"
                      % (column_name, e))
             return
+        # Remove prior version of the Row from the index if it has the indexed
+        # column set, and the column changing is an indexed column
+        if hasattr(self, column_name):
+            for idx in self._table.rows.indexes.values():
+                if column_name in (c.column for c in idx.columns):
+                    idx.remove(self)
         self._idl.txn._write(self, column, datum)
+        for idx in self._table.rows.indexes.values():
+            # Only update the index if indexed columns change
+            if column_name in (c.column for c in idx.columns):
+                idx.add(self)
 
     def addvalue(self, column_name, key):
         self._idl.txn._txn_rows[self.uuid] = self
@@ -972,8 +1001,8 @@ class Row(object):
             del self._idl.txn._txn_rows[self.uuid]
         else:
             self._idl.txn._txn_rows[self.uuid] = self
-        self.__dict__["_changes"] = None
         del self._table.rows[self.uuid]
+        self.__dict__["_changes"] = None
 
     def fetch(self, column_name):
         self._idl.txn._fetch(self, column_name)
@@ -1145,6 +1174,10 @@ class Transaction(object):
 
         for row in six.itervalues(self._txn_rows):
             if row._changes is None:
+                # If we add the deleted row back to rows with _changes == None
+                # then __getattr__ will not work for the indexes
+                row.__dict__["_changes"] = {}
+                row.__dict__["_mutations"] = {}
                 row._table.rows[row.uuid] = row
             elif row._data is None:
                 del row._table.rows[row.uuid]
diff --git a/python/setup.py b/python/setup.py
index a5872ab..0e86834 100644
--- a/python/setup.py
+++ b/python/setup.py
@@ -81,6 +81,7 @@ setup_args = dict(
     ext_modules=[setuptools.Extension("ovs._json", sources=["ovs/_json.c"],
                                       libraries=['openvswitch'])],
     cmdclass={'build_ext': try_build_ext},
+    install_requires=['sortedcontainers'],
 )
 
 try:
diff --git a/tests/test-ovsdb.py b/tests/test-ovsdb.py
index fc42a2d..8aca35b 100644
--- a/tests/test-ovsdb.py
+++ b/tests/test-ovsdb.py
@@ -289,10 +289,7 @@ def idltest_find_simple2(idl, i):
 
 
 def idltest_find_simple3(idl, i):
-    for row in six.itervalues(idl.tables["simple3"].rows):
-        if row.name == i:
-            return row
-    return None
+    return next(idl.index_equal("simple3", "simple3_by_name", i), None)
 
 
 def idl_set(idl, commands, step):
@@ -579,6 +576,8 @@ def do_idl(schema_file, remote, *commands):
     else:
         schema_helper.register_all()
     idl = ovs.db.idl.Idl(remote, schema_helper)
+    if "simple3" in idl.tables:
+        idl.index_create("simple3", "simple3_by_name")
 
     if commands:
         error, stream = ovs.stream.Stream.open_block(
-- 
1.8.3.1



More information about the dev mailing list