------------------
Version 2 represents a significant update to the source base. The code has been
refactored and modernized to embrace Python 3 semantics while also using
`autodoc` in Sphinx for more maintainable documentation. The core design and
algorithms are all the same. Sorted Containers still supports and is tested on
Python 2 but primary development is now on Python 3.6.
Version 2 is developed on the `master` branch in the source repository and
Version 1 of Sorted Containers will be maintained on branch `v1`.
Version 3 of Sorted Containers will be released sometime after January 1, 2020
and will drop support for Python 2.
At a high-level, changes can be categorized in three ways:
1. :class:`SortedList` methods `__setitem__`, `append`, `extend`, and `insert`
all now raise :exc:`NotImplementedError`. Use `add` or `update`
instead. Though it's possible to implement these methods, they were
confusing, inefficient and wrongly used by some users. Sorted list
implementations that need the functionality are encouraged to do so through
subclassing. Branch `v1` contains a reference implementation.
2. :class:`SortedDict` now uses Python 3 semantics for dict views. The
`iterkeys`, `iteritems`, `itervalues`, `viewkeys`, `viewitems`, and
`viewvalues` methods have all been removed. Use the `keys`, `items`, or
`values` methods which now return sorted dict views. :class:`SortedKeysView`
has also replaced `SortedDict.iloc` as a better interface for indexing.
3. Method parameter names have changed to be more consistent with Python's
built-in data types: `val` has changed to `value`, `idx` has changed to
`index`, and `that` has changed to `other`.
**API Changes**
* :class:`SortedListWithKey` is deprecated. Use :class:`SortedKeyList` instead.
The name `SortedListWithKey` remains as an alias for `SortedKeyList`. The
alias will be removed in Version 3.
* `sortedcontainers.sortedlist.LOAD` has moved to
`SortedList.DEFAULT_LOAD_FACTOR` so that derived classes can customize the
value.
* `SortedList._half` and `SortedList._dual` have been removed. Use
`SortedList._load` instead.
* :func:`SortedList.add` parameter `val` renamed to `value`.
* :func:`SortedList.__contains__` parameter `val` renamed to `value`.
* :func:`SortedList.discard` parameter `val` renamed to `value`.
* :func:`SortedList.remove` parameter `val` renamed to `value`.
* :func:`SortedList.__delitem__` parameter `idx` renamed to `index`.
* :func:`SortedList.__getitem__` parameter `idx` renamed to `index`.
* :func:`SortedList.__setitem__` now raises :exc:`NotImplementedError`. Use
:func:`SortedList.__delitem__` and :func:`SortedList.add` instead.
* :func:`SortedList.bisect_left` parameter `val` renamed to `value`.
* :func:`SortedList.bisect_right` parameter `val` renamed to `value`.
* :func:`SortedList.bisect` parameter `val` renamed to `value`.
* :func:`SortedList.count` parameter `val` renamed to `value`.
* :func:`SortedList.append` now raises :exc:`NotImplementedError`. Use
:func:`SortedList.add` instead.
* :func:`SortedList.extend` now raises :exc:`NotImplementedError`. Use
:func:`SortedList.update` instead.
* :func:`SortedList.insert` now raises :exc:`NotImplementedError`. Use
:func:`SortedList.add` instead.
* :func:`SortedList.pop` parameter `idx` renamed to `index`.
* :func:`SortedList.index` parameter `val` renamed to `value`.
* :func:`SortedList.__add__` parameter `that` renamed to `other`.
* :func:`SortedList.__iadd__` parameter `that` renamed to `other`.
* :func:`SortedList.__mul__` parameter `that` renamed to `num`.
* :func:`SortedList.__imul__` parameter `that` renamed to `num`.
* `SortedList._make_cmp` renamed to `SortedList.__make_cmp`.
* :func:`SortedKeyList.add` parameter `val` renamed to `value`.
* :func:`SortedKeyList.__contains__` parameter `val` renamed to `value`.
* :func:`SortedKeyList.discard` parameter `val` renamed to `value`.
* :func:`SortedKeyList.remove` parameter `val` renamed to `value`.
* :func:`SortedKeyList.bisect_left` parameter `val` renamed to `value`.
* :func:`SortedKeyList.bisect_right` parameter `val` renamed to `value`.
* :func:`SortedKeyList.bisect` parameter `val` renamed to `value`.
* :func:`SortedKeyList.count` parameter `val` renamed to `value`.
* :func:`SortedKeyList.append` now raises :exc:`NotImplementedError`. Use
:func:`SortedKeyList.add` instead.
* :func:`SortedKeyList.extend` now raises :exc:`NotImplementedError`. Use
:func:`SortedKeyList.update` instead.
* :func:`SortedKeyList.insert` now raises :exc:`NotImplementedError`. Use
:func:`SortedKeyList.add` instead.
* :func:`SortedKeyList.index` parameter `val` renamed to `value`.
* :func:`SortedKeyList.__add__` parameter `that` renamed to `other`.
* :func:`SortedKeyList.__radd__` added.
* :func:`SortedKeyList.__iadd__` parameter `that` renamed to `other`.
* :func:`SortedKeyList.__mul__` parameter `that` renamed to `num`.
* :func:`SortedKeyList.__rmul__` added.
* :func:`SortedKeyList.__imul__` parameter `that` renamed to `num`.
* Removed `SortedDict.iloc`. Use :func:`SortedDict.keys` and
:class:`SortedKeysView` instead.
* :func:`SortedDict.fromkeys` parameter `seq` renamed to `iterable`.
* :func:`SortedDict.keys` now returns :class:`SortedKeysView`.
* :func:`SortedDict.items` now returns :class:`SortedItemsView`.
* :func:`SortedDict.values` now returns :class:`SortedValuesView`.
* Removed `SortedDict.viewkeys`. Use :func:`SortedDict.keys` instead.
* Removed `SortedDict.viewitems`. Use :func:`SortedDict.items` instead.
* Removed `SortedDict.viewvalues`. Use :func:`SortedDict.values` instead.
* `SortedDict.iterkeys` removed. Use :func:`SortedDict.keys` instead.
* `SortedDict.iteritems` removed. Use :func:`SortedDict.items` instead.
* `SortedDict.itervalues` removed. Use :func:`SortedDict.values` instead.
* `SortedDict.popitem` now accepts an optional `index` argument. Default
``-1``.
* `sorteddict.KeysView` renamed to :class:`SortedKeysView`.
* `sorteddict.ItemsView` renamed to :class:`SortedItemsView`.
* `sorteddict.ValuesView` renamed to :class:`SortedValuesView`.
* Sorted dict views rely on collections abstract base classes: dict views and
sequence. The :func:`SortedKeysView.__getitem__`,
:func:`SortedItemsView.__getitem__`, and :func:`SortedValuesView.__getitem__`
methods are implemented and optimized. All other mixin methods use the
default implementation provided by the base class. Prefer :class:`SortedDict`
methods to view methods when possible.
* `SortedSet._make_cmp` renamed to `SortedSet.__make_cmp`.
* :func:`SortedSet.symmetric_difference` parameter `that` renamed to `other`.
* :func:`SortedSet.symmetric_difference_update` parameter `that` renamed to
`other`.
**Miscellaneous**
* Sphinx `autodoc` now used for API documentation.
* All benchmarks now run on CPython 3.6 unless otherwise noted.
* Testing now uses `pytest` rather than `nose`.
* AppVeyor CI testing added.
* Updated versions of alternative implementations.