From: Terry Wilson <twil...@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 <twil...@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 _______________________________________________ dev mailing list d...@openvswitch.org https://mail.openvswitch.org/mailman/listinfo/ovs-dev