diff -Nru sortedcontainers-1.5.9/appveyor.yml sortedcontainers-2.0.4/appveyor.yml
--- sortedcontainers-1.5.9/appveyor.yml 1970-01-01 00:00:00.000000000 +0000
+++ sortedcontainers-2.0.4/appveyor.yml 2018-06-07 05:34:49.000000000 +0000
@@ -0,0 +1,22 @@
+environment:
+
+ matrix:
+
+ - PYTHON: "C:\\Python27"
+ - PYTHON: "C:\\Python34"
+ - PYTHON: "C:\\Python35"
+ - PYTHON: "C:\\Python36"
+ - PYTHON: "C:\\Python27-x64"
+ - PYTHON: "C:\\Python34-x64"
+ - PYTHON: "C:\\Python35-x64"
+ - PYTHON: "C:\\Python36-x64"
+
+install:
+
+ - "%PYTHON%\\python.exe -m pip install tox"
+
+build: off
+
+test_script:
+
+ - "%PYTHON%\\python.exe -m tox -e py"
diff -Nru sortedcontainers-1.5.9/debian/changelog sortedcontainers-2.0.4/debian/changelog
--- sortedcontainers-1.5.9/debian/changelog 2018-04-22 03:00:27.000000000 +0000
+++ sortedcontainers-2.0.4/debian/changelog 2018-06-08 02:09:30.000000000 +0000
@@ -1,3 +1,18 @@
+sortedcontainers (2.0.4-1) unstable; urgency=medium
+
+ * New upstrem release
+ * debian/patches/0001-dont-breach-privacy-github-stars-counter-iframe.patch
+ - patch dropped, no longer required
+ * debian/copyright
+ - update upstream copyright years notice
+ - remove notice for docs/_themes/, directory removed upstream
+ * debian/patches/0001-privacy-breach.patch
+ - more privacy breaches to fix
+ * debian/control
+ - add pytest to b-d, needed by tests
+
+ -- Sandro Tosi Thu, 07 Jun 2018 22:09:30 -0400
+
sortedcontainers (1.5.9-1) unstable; urgency=medium
[ Ondřej Nový ]
diff -Nru sortedcontainers-1.5.9/debian/control sortedcontainers-2.0.4/debian/control
--- sortedcontainers-1.5.9/debian/control 2018-04-22 03:00:27.000000000 +0000
+++ sortedcontainers-2.0.4/debian/control 2018-06-08 02:09:30.000000000 +0000
@@ -3,7 +3,7 @@
Priority: optional
Maintainer: Sandro Tosi
Uploaders: Debian Python Modules Team
-Build-Depends: debhelper (>= 10), python-all, python3-all, dh-python, python-setuptools, python3-setuptools, python-nose, python3-nose, python-sphinx (>= 1.4), texlive-latex-base
+Build-Depends: debhelper (>= 10), python-all, python3-all, dh-python, python-setuptools, python3-setuptools, python-nose, python3-nose, python-sphinx (>= 1.4), texlive-latex-base, python-pytest, python3-pytest
Standards-Version: 4.1.4
Homepage: http://www.grantjenks.com/docs/sortedcontainers/
Vcs-Git: https://salsa.debian.org/python-team/modules/sortedcontainers.git
diff -Nru sortedcontainers-1.5.9/debian/copyright sortedcontainers-2.0.4/debian/copyright
--- sortedcontainers-1.5.9/debian/copyright 2018-04-22 03:00:27.000000000 +0000
+++ sortedcontainers-2.0.4/debian/copyright 2018-06-08 02:09:30.000000000 +0000
@@ -3,7 +3,7 @@
Source: https://github.com/grantjenks/sorted_containers
Files: *
-Copyright: Copyright 2014-2016 Grant Jenks
+Copyright: Copyright 2014-2018 Grant Jenks
License: Apache-2.0
License: Apache-2.0
@@ -13,41 +13,3 @@
Files: debian/*
Copyright: 2015-2018 Sandro Tosi
License: Apache-2.0
-
-Files: docs/_themes/*
-Copyright: Copyright (c) 2014 by Grant Jenks.
- Copyright (c) 2010 by Armin Ronacher.
-License:
- Redistribution and use in source and binary forms of the theme, with or
- without modification, are permitted provided that the following conditions
- are met:
- .
- * Redistributions of source code must retain the above copyright
- notice, this list of conditions and the following disclaimer.
- .
- * Redistributions in binary form must reproduce the above
- copyright notice, this list of conditions and the following
- disclaimer in the documentation and/or other materials provided
- with the distribution.
- .
- * The names of the contributors may not be used to endorse or
- promote products derived from this software without specific
- prior written permission.
- .
- We kindly ask you to only use these themes in an unmodified manner just
- for Flask and Flask-related products, not for unrelated projects. If you
- like the visual style and want to use it for your own projects, please
- consider making some larger changes to the themes (such as changing
- font faces, sizes, colors or margins).
- .
- THIS THEME IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
- AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
- LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
- CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
- SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
- INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
- CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
- ARISING IN ANY WAY OUT OF THE USE OF THIS THEME, EVEN IF ADVISED OF THE
- POSSIBILITY OF SUCH DAMAGE.
diff -Nru sortedcontainers-1.5.9/debian/patches/0001-dont-breach-privacy-github-stars-counter-iframe.patch sortedcontainers-2.0.4/debian/patches/0001-dont-breach-privacy-github-stars-counter-iframe.patch
--- sortedcontainers-1.5.9/debian/patches/0001-dont-breach-privacy-github-stars-counter-iframe.patch 2018-04-22 03:00:27.000000000 +0000
+++ sortedcontainers-2.0.4/debian/patches/0001-dont-breach-privacy-github-stars-counter-iframe.patch 1970-01-01 00:00:00.000000000 +0000
@@ -1,41 +0,0 @@
-From: Sandro Tosi
-Date: Sat, 21 Apr 2018 22:56:58 -0400
-Subject: dont-breach-privacy-github-stars-counter-iframe
-
----
- docs/_templates/sidebarintro.html | 5 -----
- docs/_templates/sidebarlogo.html | 5 -----
- 2 files changed, 10 deletions(-)
-
-diff --git a/docs/_templates/sidebarintro.html b/docs/_templates/sidebarintro.html
-index 02f667a..33fbb48 100644
---- a/docs/_templates/sidebarintro.html
-+++ b/docs/_templates/sidebarintro.html
-@@ -4,11 +4,6 @@
-
-
-
--
--
--
--
-
- SortedContainers provides sorted container types, written in
- pure-Python and fast as C-extensions.
-diff --git a/docs/_templates/sidebarlogo.html b/docs/_templates/sidebarlogo.html
-index a68279f..4b27034 100644
---- a/docs/_templates/sidebarlogo.html
-+++ b/docs/_templates/sidebarlogo.html
-@@ -4,11 +4,6 @@
-
-
-
--
--
--
--
-
- SortedContainers provides sorted container types, written in
- pure-Python and fast as C-extensions.
diff -Nru sortedcontainers-1.5.9/debian/patches/0001-privacy-breach.patch sortedcontainers-2.0.4/debian/patches/0001-privacy-breach.patch
--- sortedcontainers-1.5.9/debian/patches/0001-privacy-breach.patch 1970-01-01 00:00:00.000000000 +0000
+++ sortedcontainers-2.0.4/debian/patches/0001-privacy-breach.patch 2018-06-08 02:09:30.000000000 +0000
@@ -0,0 +1,43 @@
+From: Sandro Tosi
+Date: Thu, 7 Jun 2018 22:00:03 -0400
+Subject: privacy-breach
+
+---
+ README.rst | 6 ------
+ docs/conf.py | 4 ----
+ 2 files changed, 10 deletions(-)
+
+diff --git a/README.rst b/README.rst
+index 80581d8..5bd6a9a 100644
+--- a/README.rst
++++ b/README.rst
+@@ -114,12 +114,6 @@ Features
+ - Developed on Python 3.6
+ - Tested on CPython 2.7, 3.2, 3.3, 3.4, 3.5, 3.6 and PyPy, PyPy3
+
+-.. image:: https://api.travis-ci.org/grantjenks/python-sortedcontainers.svg?branch=master
+- :target: http://www.grantjenks.com/docs/sortedcontainers/
+-
+-.. image:: https://ci.appveyor.com/api/projects/status/github/grantjenks/python-sortedcontainers?branch=master&svg=true
+- :target: http://www.grantjenks.com/docs/sortedcontainers/
+-
+ Quickstart
+ ----------
+
+diff --git a/docs/conf.py b/docs/conf.py
+index 0e1d568..86f069f 100644
+--- a/docs/conf.py
++++ b/docs/conf.py
+@@ -87,12 +87,8 @@ html_theme_options = {
+ 'logo': 'gj-logo.png',
+ 'logo_name': True,
+ 'logo_text_align': 'center',
+- 'analytics_id': 'UA-19364636-2',
+ 'show_powered_by': False,
+ 'show_related': True,
+- 'github_user': 'grantjenks',
+- 'github_repo': 'python-sortedcontainers',
+- 'github_type': 'star',
+ }
+
+ # Add any paths that contain custom static files (such as style sheets) here,
diff -Nru sortedcontainers-1.5.9/debian/patches/series sortedcontainers-2.0.4/debian/patches/series
--- sortedcontainers-1.5.9/debian/patches/series 2018-04-22 03:00:27.000000000 +0000
+++ sortedcontainers-2.0.4/debian/patches/series 2018-06-08 02:09:30.000000000 +0000
@@ -1 +1 @@
-0001-dont-breach-privacy-github-stars-counter-iframe.patch
+0001-privacy-breach.patch
diff -Nru sortedcontainers-1.5.9/docs/conf.py sortedcontainers-2.0.4/docs/conf.py
--- sortedcontainers-1.5.9/docs/conf.py 2017-12-08 21:13:29.000000000 +0000
+++ sortedcontainers-2.0.4/docs/conf.py 2018-06-07 05:34:49.000000000 +0000
@@ -1,272 +1,185 @@
# -*- coding: utf-8 -*-
#
-# sortedcontainers documentation build configuration file, created by
-# sphinx-quickstart on Tue Feb 04 10:02:59 2014.
+# Configuration file for the Sphinx documentation builder.
#
-# This file is execfile()d with the current directory set to its
-# containing dir.
-#
-# Note that not all possible configuration values are present in this
-# autogenerated file.
-#
-# All configuration values have a default; values that are commented out
-# serve to show the default.
+# This file does only contain a selection of the most common options. For a
+# full list see the documentation:
+# http://www.sphinx-doc.org/en/master/config
-import sys
-import os
+# -- Path setup --------------------------------------------------------------
# If extensions (or modules to document with autodoc) are in another directory,
# add these directories to sys.path here. If the directory is relative to the
# documentation root, use os.path.abspath to make it absolute, like shown here.
+
+import os
+import sys
sys.path.insert(0, os.path.abspath('..'))
import sortedcontainers
-# -- General configuration ------------------------------------------------
+
+# -- Project information -----------------------------------------------------
+
+project = 'Sorted Containers'
+copyright = sortedcontainers.__copyright__
+author = sortedcontainers.__author__
+
+# The short X.Y version
+version = sortedcontainers.__version__
+# The full version, including alpha/beta/rc tags
+release = sortedcontainers.__version__
+
+
+# -- General configuration ---------------------------------------------------
# If your documentation needs a minimal Sphinx version, state it here.
-#needs_sphinx = '1.0'
+#
+# needs_sphinx = '1.0'
# Add any Sphinx extension module names here, as strings. They can be
# extensions coming with Sphinx (named 'sphinx.ext.*') or your custom
# ones.
extensions = [
'sphinx.ext.autodoc',
- 'sphinx.ext.coverage',
- 'sphinx.ext.viewcode',
+ 'sphinx.ext.todo',
'sphinx.ext.imgmath',
+ 'sphinx.ext.viewcode',
]
# Add any paths that contain templates here, relative to this directory.
templates_path = ['_templates']
-# The suffix of source filenames.
+# The suffix(es) of source filenames.
+# You can specify multiple suffix as a list of string:
+#
+# source_suffix = ['.rst', '.md']
source_suffix = '.rst'
-# The encoding of source files.
-#source_encoding = 'utf-8-sig'
-
# The master toctree document.
master_doc = 'index'
-# General information about the project.
-project = sortedcontainers.__title__
-copyright = u'2015, Grant Jenks'
-
-# The version info for the project you're documenting, acts as replacement for
-# |version| and |release|, also used in various other places throughout the
-# built documents.
-#
-# The short X.Y version.
-version = sortedcontainers.__version__[:-2]
-# The full version, including alpha/beta/rc tags.
-release = sortedcontainers.__version__
-
# The language for content autogenerated by Sphinx. Refer to documentation
# for a list of supported languages.
-#language = None
-
-# There are two options for replacing |today|: either, you set today to some
-# non-false value, then it is used:
-#today = ''
-# Else, today_fmt is used as the format for a strftime call.
-#today_fmt = '%B %d, %Y'
+#
+# This is also used if you do content translation via gettext catalogs.
+# Usually you set "language" from the command line for these cases.
+language = None
# List of patterns, relative to source directory, that match files and
# directories to ignore when looking for source files.
-exclude_patterns = ['_build']
-
-# The reST default role (used for this markup: `text`) to use for all
-# documents.
-#default_role = None
-
-# If true, '()' will be appended to :func: etc. cross-reference text.
-#add_function_parentheses = True
-
-# If true, the current module name will be prepended to all description
-# unit titles (such as .. function::).
-#add_module_names = True
-
-# If true, sectionauthor and moduleauthor directives will be shown in the
-# output. They are ignored by default.
-#show_authors = False
+# This pattern also affects html_static_path and html_extra_path .
+exclude_patterns = ['_build', 'Thumbs.db', '.DS_Store']
# The name of the Pygments (syntax highlighting) style to use.
pygments_style = 'sphinx'
-# A list of ignored prefixes for module index sorting.
-#modindex_common_prefix = []
-
-# If true, keep warnings as "system message" paragraphs in the built documents.
-#keep_warnings = False
-
-# -- Options for HTML output ----------------------------------------------
+# -- Options for HTML output -------------------------------------------------
# The theme to use for HTML and HTML Help pages. See the documentation for
# a list of builtin themes.
-html_theme = 'default'
+html_theme = 'alabaster'
# Theme options are theme-specific and customize the look and feel of a theme
# further. For a list of options available for each theme, see the
# documentation.
-#html_theme_options = {}
-
-# Add any paths that contain custom themes here, relative to this directory.
-#html_theme_path = []
-
-# The name for this set of Sphinx documents. If None, it defaults to
-# " v documentation".
-#html_title = None
-
-# A shorter title for the navigation bar. Default is the same as html_title.
-#html_short_title = None
-
-# The name of an image file (relative to this directory) to place at the top
-# of the sidebar.
-#html_logo = None
-
-# The name of an image file (within the static path) to use as favicon of the
-# docs. This file should be a Windows icon file (.ico) being 16x16 or 32x32
-# pixels large.
-#html_favicon = None
+html_theme_options = {
+ 'logo': 'gj-logo.png',
+ 'logo_name': True,
+ 'logo_text_align': 'center',
+ 'analytics_id': 'UA-19364636-2',
+ 'show_powered_by': False,
+ 'show_related': True,
+ 'github_user': 'grantjenks',
+ 'github_repo': 'python-sortedcontainers',
+ 'github_type': 'star',
+}
# Add any paths that contain custom static files (such as style sheets) here,
# relative to this directory. They are copied after the builtin static files,
# so a file named "default.css" will overwrite the builtin "default.css".
html_static_path = ['_static']
-# Add any extra paths that contain custom files (such as robots.txt or
-# .htaccess) here, relative to this directory. These files are copied
-# directly to the root of the documentation.
-#html_extra_path = []
-
-# If not '', a 'Last updated on:' timestamp is inserted at every page bottom,
-# using the given strftime format.
-#html_last_updated_fmt = '%b %d, %Y'
-
-# If true, SmartyPants will be used to convert quotes and dashes to
-# typographically correct entities.
-#html_use_smartypants = True
-
-# Custom sidebar templates, maps document names to template names.
+# Custom sidebar templates, must be a dictionary that maps document names
+# to template names.
+#
+# The default sidebars (for documents that don't match any pattern) are
+# defined by theme itself. Builtin themes are using these templates by
+# default: ``['localtoc.html', 'relations.html', 'sourcelink.html',
+# 'searchbox.html']``.
html_sidebars = {
- 'index': ['sidebarintro.html', 'sourcelink.html', 'searchbox.html'],
- '**': ['sidebarlogo.html', 'localtoc.html', 'relations.html',
- 'sourcelink.html', 'searchbox.html']
+ '**': [
+ 'about.html',
+ 'gumroad.html',
+ 'localtoc.html',
+ 'relations.html',
+ 'searchbox.html',
+ ]
}
-# Additional templates that should be rendered to pages, maps page names to
-# template names.
-#html_additional_pages = {}
-
-# If false, no module index is generated.
-#html_domain_indices = True
-
-# If false, no index is generated.
-#html_use_index = True
-
-# If true, the index is split into individual pages for each letter.
-#html_split_index = False
-
-# If true, links to the reST sources are added to the pages.
-#html_show_sourcelink = True
-
-# If true, "Created using Sphinx" is shown in the HTML footer. Default is True.
-#html_show_sphinx = True
-
-# If true, "(C) Copyright ..." is shown in the HTML footer. Default is True.
-#html_show_copyright = True
-# If true, an OpenSearch description file will be output, and all pages will
-# contain a tag referring to it. The value of this option must be the
-# base URL from which the finished HTML is served.
-#html_use_opensearch = ''
-
-# This is the file name suffix for HTML files (e.g. ".xhtml").
-#html_file_suffix = None
+# -- Options for HTMLHelp output ---------------------------------------------
# Output file base name for HTML help builder.
-htmlhelp_basename = 'sortedcontainersdoc'
+htmlhelp_basename = 'SortedContainersDoc'
-# -- Options for LaTeX output ---------------------------------------------
+# -- Options for LaTeX output ------------------------------------------------
latex_elements = {
-# The paper size ('letterpaper' or 'a4paper').
-#'papersize': 'letterpaper',
-
-# The font size ('10pt', '11pt' or '12pt').
-#'pointsize': '10pt',
-
-# Additional stuff for the LaTeX preamble.
-#'preamble': '',
+ # The paper size ('letterpaper' or 'a4paper').
+ #
+ # 'papersize': 'letterpaper',
+
+ # The font size ('10pt', '11pt' or '12pt').
+ #
+ # 'pointsize': '10pt',
+
+ # Additional stuff for the LaTeX preamble.
+ #
+ # 'preamble': '',
+
+ # Latex figure (float) alignment
+ #
+ # 'figure_align': 'htbp',
}
# Grouping the document tree into LaTeX files. List of tuples
# (source start file, target name, title,
# author, documentclass [howto, manual, or own class]).
latex_documents = [
- ('index', 'sortedcontainers.tex', u'sortedcontainers Documentation',
- u'Grant Jenks', 'manual'),
+ (master_doc, 'SortedContainers.tex', 'SortedContainers Documentation',
+ 'Grant Jenks', 'manual'),
]
-# The name of an image file (relative to this directory) to place at the top of
-# the title page.
-#latex_logo = None
-
-# For "manual" documents, if this is true, then toplevel headings are parts,
-# not chapters.
-#latex_use_parts = False
-
-# If true, show page references after internal links.
-#latex_show_pagerefs = False
-
-# If true, show URL addresses after external links.
-#latex_show_urls = False
-# Documents to append as an appendix to all manuals.
-#latex_appendices = []
-
-# If false, no module index is generated.
-#latex_domain_indices = True
-
-
-# -- Options for manual page output ---------------------------------------
+# -- Options for manual page output ------------------------------------------
# One entry per manual page. List of tuples
# (source start file, name, description, authors, manual section).
man_pages = [
- ('index', 'sortedcontainers', u'sortedcontainers Documentation',
- [u'Grant Jenks'], 1)
+ (master_doc, 'sortedcontainers', 'SortedContainers Documentation',
+ [author], 1)
]
-# If true, show URL addresses after external links.
-#man_show_urls = False
-
-# -- Options for Texinfo output -------------------------------------------
+# -- Options for Texinfo output ----------------------------------------------
# Grouping the document tree into Texinfo files. List of tuples
# (source start file, target name, title, author,
# dir menu entry, description, category)
texinfo_documents = [
- ('index', 'sortedcontainers', u'sortedcontainers Documentation',
- u'Grant Jenks', 'sortedcontainers', 'Sorted container data types.',
- 'Miscellaneous'),
+ (master_doc, 'SortedContainers', 'SortedContainers Documentation',
+ author, 'SortedContainers',
+ 'Python sorted collections library:'
+ ' sorted list, sorted dict, and sorted set.',
+ 'Miscellaneous'),
]
-# Documents to append as an appendix to all manuals.
-#texinfo_appendices = []
-
-# If false, no module index is generated.
-#texinfo_domain_indices = True
-# How to display URL addresses: 'footnote', 'no', or 'inline'.
-#texinfo_show_urls = 'footnote'
+# -- Extension configuration -------------------------------------------------
-# If true, do not generate a @detailmenu in the "Top" node's menu.
-#texinfo_no_detailmenu = False
+# -- Options for todo extension ----------------------------------------------
-sys.path.append(os.path.abspath('_themes'))
-html_theme_path = ['_themes']
-html_theme = 'gj'
+# If true, `todo` and `todoList` produce output, else they produce nothing.
+todo_include_todos = True
diff -Nru sortedcontainers-1.5.9/docs/development.rst sortedcontainers-2.0.4/docs/development.rst
--- sortedcontainers-1.5.9/docs/development.rst 2017-12-08 21:13:29.000000000 +0000
+++ sortedcontainers-2.0.4/docs/development.rst 2018-06-07 05:34:49.000000000 +0000
@@ -4,13 +4,14 @@
Collaborators are welcome!
#. Check for open issues or open a fresh issue to start a discussion around a
- bug. There is a Contributor Friendly tag for issues that should be used by
- people who are not very familiar with the codebase yet.
-#. Fork `the repository `_ on
- GitHub and start making your changes to a new branch.
+ bug.
+#. Fork the `repository`_ on GitHub and start making your changes to a new
+ branch.
#. Write a test which shows that the bug was fixed.
#. Send a pull request and bug the maintainer until it gets merged and
- published. :)
+ published :)
+
+.. _`repository`: https://github.com/grantjenks/python-sortedcontainers
Development Lead
----------------
@@ -27,121 +28,136 @@
Get the Code
------------
-SortedContainers is actively developed on GitHub, where the code is
-`always available `_.
-
-You can either clone the public repository::
-
- $ git clone git://github.com/grantjenks/sorted_containers.git
-
-Download the `tarball `_::
-
- $ curl -OL https://github.com/grantjenks/sorted_containers/tarball/master
+:doc:`Sorted Containers` is actively developed on GitHub, where the code
+is `open source`_. The recommended way to get a copy of the source repository
+is to clone the repository from GitHub::
-Or, download the `zipball `_::
+ $ git clone git://github.com/grantjenks/python-sortedcontainers.git
- $ curl -OL https://github.com/grantjenks/sorted_containers/zipball/master
+.. _`open source`: https://github.com/grantjenks/python-sortedcontainers
Development Dependencies
------------------------
-Install development dependencies with `pip `_::
+Install development dependencies with `pip`_::
$ pip install -r requirements.txt
This includes everything for building/running tests, benchmarks and
documentation.
-Note that installing the Banyan module on Windows requires `patching the source
-`_ in a couple places.
+Some alternative implementations, such as `banyan`, may have issues when
+installing on Windows. You can still develop :doc:`Sorted Containers`
+without these packages. They will be omitted from benchmarking.
+
+.. _`pip`: https://pypi.org/project/pip/
Testing
-------
-Testing uses `tox `_. If you don't want to
-install all the development requirements, then, after downloading, you can
-simply run::
+Testing uses `tox`_. If you don't want to install all the development
+requirements, then, after downloading, you can simply run::
$ python setup.py test
-The test argument to setup.py will download a minimal testing infrastructure
+The test argument to `setup.py` will download a minimal testing infrastructure
and run the tests.
::
- $ tox
- GLOB sdist-make: /repos/sorted_containers/setup.py
- py26 inst-nodeps: /repos/sorted_containers/.tox/dist/sortedcontainers-0.8.0.zip
- py26 runtests: PYTHONHASHSEED='1205144536'
- py26 runtests: commands[0] | nosetests
- ...
- ----------------------------------------------------------------------
- Ran 150 tests in 7.080s
-
- OK
- py27 inst-nodeps: /repos/sorted_containers/.tox/dist/sortedcontainers-0.8.0.zip
- py27 runtests: PYTHONHASHSEED='1205144536'
- py27 runtests: commands[0] | nosetests
- ...
- ----------------------------------------------------------------------
- Ran 150 tests in 6.670s
-
- OK
- py32 inst-nodeps: /repos/sorted_containers/.tox/dist/sortedcontainers-0.8.0.zip
- py32 runtests: PYTHONHASHSEED='1205144536'
- py32 runtests: commands[0] | nosetests
- ...
- ----------------------------------------------------------------------
- Ran 150 tests in 10.254s
-
- OK
- py33 inst-nodeps: /repos/sorted_containers/.tox/dist/sortedcontainers-0.8.0.zip
- py33 runtests: PYTHONHASHSEED='1205144536'
- py33 runtests: commands[0] | nosetests
- ...
- ----------------------------------------------------------------------
- Ran 150 tests in 10.485s
-
- OK
- py34 inst-nodeps: /repos/sorted_containers/.tox/dist/sortedcontainers-0.8.0.zip
- py34 runtests: PYTHONHASHSEED='1205144536'
- py34 runtests: commands[0] | nosetests
- ...
- ----------------------------------------------------------------------
- Ran 150 tests in 11.350s
-
- OK
- ___________________ summary _______________________
- py26: commands succeeded
- py27: commands succeeded
- py32: commands succeeded
- py33: commands succeeded
- py34: commands succeeded
- congratulations :)
+ $ python setup.py test
+ running test
+ running egg_info
+ writing sortedcontainers.egg-info/PKG-INFO
+ writing dependency_links to sortedcontainers.egg-info/dependency_links.txt
+ writing top-level names to sortedcontainers.egg-info/top_level.txt
+ reading manifest file 'sortedcontainers.egg-info/SOURCES.txt'
+ reading manifest template 'MANIFEST.in'
+ writing manifest file 'sortedcontainers.egg-info/SOURCES.txt'
+ running build_ext
+ GLOB sdist-make: /Users/grantj/repos/python-sortedcontainers/setup.py
+ py36 inst-nodeps: /Users/grantj/repos/python-sortedcontainers/.tox/dist/sortedcontainers-1.5.10.zip
+ py36 installed: attrs==18.1.0,more-itertools==4.1.0,pluggy==0.6.0,py==1.5.3,pytest==3.5.1,six==1.11.0,sortedcontainers==1.5.10
+ py36 runtests: PYTHONHASHSEED='365015869'
+ py36 runtests: commands[0] | python -m pytest
+ ================================================= test session starts =================================================
+ platform darwin -- Python 3.6.5, pytest-3.5.1, py-1.5.3, pluggy-0.6.0
+ rootdir: /Users/grantj/repos/python-sortedcontainers, inifile: tox.ini
+ collected 357 items
+
+ docs/introduction.rst . [ 0%]
+ sortedcontainers/__init__.py . [ 0%]
+ sortedcontainers/sorteddict.py ........... [ 3%]
+ sortedcontainers/sortedlist.py ..................................... [ 14%]
+ sortedcontainers/sortedset.py ................. [ 18%]
+ tests/benchmark_splits_fill.py . [ 19%]
+ tests/sortedcollection.py . [ 19%]
+ tests/test_coverage_sorteddict.py ................................................... [ 33%]
+ tests/test_coverage_sortedkeylist_modulo.py ................................................................... [ 52%]
+ tests/test_coverage_sortedkeylist_negate.py ....................................................... [ 68%]
+ tests/test_coverage_sortedlist.py .......................................................... [ 84%]
+ tests/test_coverage_sortedset.py .................................................. [ 98%]
+ tests/test_stress_sorteddict.py .. [ 98%]
+ tests/test_stress_sortedkeylist.py . [ 99%]
+ tests/test_stress_sortedlist.py . [ 99%]
+ tests/test_stress_sortedset.py .. [100%]
+
+ ============================================= 357 passed in 10.86 seconds =============================================
+ lint inst-nodeps: /Users/grantj/repos/python-sortedcontainers/.tox/dist/sortedcontainers-1.5.10.zip
+ lint installed: astroid==1.6.4,isort==4.3.4,lazy-object-proxy==1.3.1,mccabe==0.6.1,pylint==1.9.0,six==1.11.0,sortedcontainers==1.5.10,wrapt==1.10.11
+ lint runtests: PYTHONHASHSEED='365015869'
+ lint runtests: commands[0] | pylint sortedcontainers
+ Using config file /Users/grantj/repos/python-sortedcontainers/.pylintrc
+
+ --------------------------------------------------------------------
+ Your code has been rated at 10.00/10 (previous run: 10.00/10, +0.00)
+
+ _______________________________________________________ summary _______________________________________________________
+ py36: commands succeeded
+ lint: commands succeeded
-Coverage testing uses `nose `_:
+Coverage testing uses `pytest-cov`_:
::
- $ nosetests --with-coverage
- ...................................................
- Name Stmts Miss Cover Missing
- -----------------------------------------------------------
- sortedcontainers 4 0 100%
- sortedcontainers.sorteddict 220 10 95% 18, 21, 96, 106, 115, 149, 158, 183, 220, 253
- sortedcontainers.sortedlist 452 1 99% 16
- sortedcontainers.sortedset 163 10 94% 51, 62, 65, 70, 75, 80, 84, 86, 88, 90
- -----------------------------------------------------------
- TOTAL 839 21 97%
- ----------------------------------------------------------------------
- Ran 146 tests in 15.447s
+ $ python -m pytest --cov sortedcontainers --cov-report term-missing --cov-branch
+ ================================================= test session starts =================================================
+ platform darwin -- Python 3.6.5, pytest-3.5.0, py-1.5.3, pluggy-0.6.0
+ rootdir: /Users/grantj/repos/python-sortedcontainers, inifile: tox.ini
+ plugins: cov-2.5.1, hypothesis-3.55.3
+ collected 357 items
+
+ docs/introduction.rst . [ 0%]
+ sortedcontainers/__init__.py . [ 0%]
+ sortedcontainers/sorteddict.py ........... [ 3%]
+ sortedcontainers/sortedlist.py ..................................... [ 14%]
+ sortedcontainers/sortedset.py ................. [ 18%]
+ tests/benchmark_splits_fill.py . [ 19%]
+ tests/sortedcollection.py . [ 19%]
+ tests/test_coverage_sorteddict.py ................................................... [ 33%]
+ tests/test_coverage_sortedkeylist_modulo.py ................................................................... [ 52%]
+ tests/test_coverage_sortedkeylist_negate.py ....................................................... [ 68%]
+ tests/test_coverage_sortedlist.py .......................................................... [ 84%]
+ tests/test_coverage_sortedset.py .................................................. [ 98%]
+ tests/test_stress_sorteddict.py .. [ 98%]
+ tests/test_stress_sortedkeylist.py . [ 99%]
+ tests/test_stress_sortedlist.py . [ 99%]
+ tests/test_stress_sortedset.py .. [100%]
+
+ ---------- coverage: platform darwin, python 3.6.5-final-0 -----------
+ Name Stmts Miss Branch BrPart Cover Missing
+ ----------------------------------------------------------------------------
+ sortedcontainers/__init__.py 10 0 0 0 100%
+ sortedcontainers/sorteddict.py 159 0 40 0 100%
+ sortedcontainers/sortedlist.py 1001 8 420 3 99% 34-39, 44-45, 33->34, 785->787, 1429->1437
+ sortedcontainers/sortedset.py 179 0 26 0 100%
+ ----------------------------------------------------------------------------
+ TOTAL 1349 8 486 3 99%
- OK
+It's normal to see coverage a little less than 100%. Some code is specific to
+the Python runtime.
-It's normal not to see 100% coverage. Some code is specific to the Python
-runtime.
-
-Stress testing is also based on nose but can be run independently as a
+Stress testing is also based on pytest but can be run independently as a
module. Stress tests are kept in the tests directory and prefixed with
test_stress. Stress tests accept two arguments: an iteration count and random
seed value. For example, to run stress on the SortedList data type:
@@ -155,7 +171,7 @@
Exiting after 0:00:00.846000
If stress exits normally then it worked successfully. Some stress is run by tox
-and nose but the iteration count is limited at 1,000. More rigorous testing
+and pytest but the iteration count is limited at 1,000. More rigorous testing
requires increasing the iteration count to millions. At that level, it's best
to just let it run overnight. Stress testing will stop at the first failure.
@@ -163,8 +179,8 @@
------------------
Running and plotting benchmarks is a two step process. Each is a Python script
-in the tests directory. To run the benchmarks for SortedList, plot the results,
-and save the resulting graphs, run:
+in the tests directory. To run the benchmarks for :class:`SortedList`, plot the
+results, and save the resulting graphs, run:
::
@@ -172,7 +188,7 @@
$ python -m tests.benchmark_plot tests/results_sortedlist.txt SortedList --save
Each script has a handful of useful arguments. Use ``--help`` to display
-those. Consult the source for details. The file ``tests/benchmark_plot.py``
+those. Consult the source for details. The file `tests/benchmark_plot.py`
contains notes about benchmarking different Python runtimes against each other.
If you simply want to run the benchmarks to observe the performance on your
@@ -180,30 +196,37 @@
::
- $ curl -OL https://github.com/grantjenks/sorted_containers/zipball/master
+ $ curl -OL https://github.com/grantjenks/python-sortedcontainers/zipball/master
$ unzip master
- $ cd grantjenks-sorted_containers-[GITHASH]/
+ $ cd grantjenks-python-sortedcontainers-[GITHASH]/
$ export PYTHONPATH=`pwd`
$ python -m tests.benchmark_sortedlist
$ python -m tests.benchmark_sorteddict
$ python -m tests.benchmark_sortedset
The benchmarks will warn if some packages are not importable. This limits the
-possible comparisons. In all cases, you can install missing packages from PyPI.
+possible comparisons. See `requirements.txt` for the package names than can be
+installed from PyPI.
Tested Runtimes
---------------
-SortedContainers actively tests against the following versions of Python:
+:doc:`Sorted Containers` actively tests against the following versions
+of Python:
-* CPython 2.6
* CPython 2.7
* CPython 3.2
* CPython 3.3
* CPython 3.4
* CPython 3.5
-* PyPy v5.1
-* PyPy3 v2.4
-
-Life will feel much saner if you use `virtualenv `_
-to manage each of the runtimes.
+* CPython 3.6
+* PyPy
+* PyPy3
+
+Life will feel much saner if you use `venv`_ or `virtualenv`_ and `tox`_ to
+manage and test each of the runtimes.
+
+.. _`tox`: https://pypi.org/project/tox/
+.. _`pytest-cov`: https://pypi.org/project/pytest-cov/
+.. _`venv`: https://docs.python.org/3/library/venv.html
+.. _`virtualenv`: https://pypi.org/project/virtualenv/
diff -Nru sortedcontainers-1.5.9/docs/djangocon-2015-lightning-talk.rst sortedcontainers-2.0.4/docs/djangocon-2015-lightning-talk.rst
--- sortedcontainers-1.5.9/docs/djangocon-2015-lightning-talk.rst 2017-12-08 21:13:29.000000000 +0000
+++ sortedcontainers-2.0.4/docs/djangocon-2015-lightning-talk.rst 2018-06-07 05:34:49.000000000 +0000
@@ -45,11 +45,12 @@
Red-Black and AVL. All of those are implemented in C or C++. Then I discovered
a Skip-list implementation that was slower but pure-Python.
-All I can say in five minutes is SortedContainers doesn't use any of these
-exactly. It's kind of like a B-tree but only half-heartedly. It relies entirely
-on the bisect module. While it's slow to program in Python, the interpreter is
-written in C. So if you think of it as programming the interpreter, you're
-effectively writing C code. It turns out lists are fast; trees, not so much.
+All I can say in five minutes is :doc:`Sorted Containers` doesn't use
+any of these exactly. It's kind of like a B-tree but only half-heartedly. It
+relies entirely on the bisect module. While it's slow to program in Python, the
+interpreter is written in C. So if you think of it as programming the
+interpreter, you're effectively writing C code. It turns out lists are fast;
+trees, not so much.
Listen to what these smart people have to say about it:
@@ -70,6 +71,6 @@
never had it before” has worn thin. It is time that Python offered a full range
of collection classes out of the box, including sorted ones.
-Ladies and gentlemen, the SortedContainers library. Thank you.
+Ladies and gentlemen, the :doc:`Sorted Containers` library. Thank you.
.. _`Accompanying Slides`: http://bit.ly/socoin5
diff -Nru sortedcontainers-1.5.9/docs/implementation.rst sortedcontainers-2.0.4/docs/implementation.rst
--- sortedcontainers-1.5.9/docs/implementation.rst 2017-12-08 21:13:29.000000000 +0000
+++ sortedcontainers-2.0.4/docs/implementation.rst 2018-06-07 05:34:49.000000000 +0000
@@ -1,25 +1,25 @@
Implementation Details
======================
-The :doc:`SortedContainers` internal implementation is based on a couple
-observations. The first is that Python lists are fast, *really fast*. They have
-great characteristics for memory management and random access. The second is
-that bisect.insort is fast. This is somewhat counter-intuitive since it
-involves shifting a series of items in a list. But modern processors do this
-really well. A lot of time has been spent optimizing mem-copy/mem-move-like
-operations both in hardware and software.
-
-But using only one list and bisect.insort would produce sluggish behavior for
-lengths exceeding ten thousand. So the implementation of
-:doc:`SortedList` uses a list of lists to store elements. In this
-way, inserting or deleting is most often performed on a short list. Only rarely
-does a new list need to be added or deleted.
-
-:doc:`SortedList` maintains three internal variables: ``_lists``,
-``_maxes``, and ``_index``. The first is simply the list of lists; each member
-is a sorted sublist of elements. The second contains the maximum element in
-each of the sublists. This is used for fast binary-search. The last maintains a
-tree of pair-wise sums of the lengths of the lists.
+The :doc:`Sorted Containers` internal implementation is based on a
+couple observations. The first is that Python's `list` is fast, *really
+fast*. Lists have great characteristics for memory management and random
+access. The second is that `bisect.insort` is fast. This is somewhat
+counter-intuitive since it involves shifting a series of items in a list. But
+modern processors do this really well. A lot of time has been spent optimizing
+mem-copy/mem-move-like operations both in hardware and software.
+
+But using only one list and `bisect.insort` would produce sluggish behavior for
+lengths exceeding ten thousand. So the implementation of :doc:`sortedlist` uses
+a list of lists to store elements. In this way, inserting or deleting is most
+often performed on a short list. Only rarely does a new list need to be added
+or deleted.
+
+:doc:`sortedlist` maintains three internal variables: `_lists`, `_maxes`, and
+`_index`. The first is simply the list of lists, each member is a sorted
+sublist of elements. The second contains the maximum element in each of the
+sublists. This is used for fast binary-search. The last maintains a tree of
+pair-wise sums of the lengths of the lists.
Lists are kept balanced using the load factor. If a sublist's length exceeds
double the load then it is split in two. Likewise at half the load it is
@@ -29,10 +29,10 @@
you will probably exhaust the memory of your machine before that point.)
Experimentation is also recommended. A :doc:`load factor performance
comparison` is also provided. For more in-depth analysis,
-read :doc:`Performance at Scale` which benchmarks
-:doc:`SortedContainers` with ten billion elements.
+read :doc:`performance-scale` which benchmarks :doc:`Sorted Containers`
+with ten billion elements.
-Finding an element is a two step process. First the ``_maxes`` list, also known
+Finding an element is a two step process. First the `_maxes` list, also known
as the "maxes" index, is bisected which yields the position of a sorted
sublist. Then that sublist is bisected for the location of the element.
@@ -55,12 +55,12 @@
realities of today's software and hardware. For a more in-depth analysis, read
:doc:`Performance at Scale`.
-Indexing uses the ``_index`` list which operates as a tree of pair-wise sums of
+Indexing uses the `_index` list which operates as a tree of pair-wise sums of
the lengths of the lists. The tree is maintained as a dense binary tree. It's
-easiest to explain with an example. Suppose ``_lists`` contains sublists with
+easiest to explain with an example. Suppose `_lists` contains sublists with
these lengths (in this example, we assume the load factor is 4)::
- map(len, _lists) -> [3, 5, 4, 5, 6]
+ list(map(len, _lists)) -> [3, 5, 4, 5, 6]
Given these lengths, the first row in the index is the pair-wise sums::
@@ -79,12 +79,10 @@
With this list, we can efficiently compute the index of an item in a sublist
and, vice-versa, find an item given an index. Details of the algorithms to do
-so are contained in the docstring for ``SortedList._loc`` and
-``SortedList._pos``.
-
+so are contained in the docstring for `SortedList._loc` and `SortedList._pos`.
For example, indexing requires traversing the tree to a leaf node. Each node
-has two children which are easily computable. Given an index, ``pos``, the
+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
@@ -125,7 +123,7 @@
Maintaining the position index in this way has several advantages:
* It's easy to traverse to children/parent. The children of a position in the
- ``_index`` are at ``(pos * 2) + 1`` and ``(pos * 2) + 2``. The parent is at
+ `_index` are at ``(pos * 2) + 1`` and ``(pos * 2) + 2``. The parent is at
``(pos - 1) // 2``. We can even identify left/right-children easily. Each
left-child is at an odd index and each right-child is at an even index.
@@ -136,7 +134,7 @@
all be done within C-routines in the Python interpreter.
* It's space efficient. The whole index is no more than twice the size of the
- length of the ``_lists`` and contains only integers.
+ length of the `_lists` and contains only integers.
* It's easy to update. Adding or removing an item involves incrementing or
decrementing only ``log2(len(_index))`` items in the index. The only caveat
@@ -148,5 +146,5 @@
not know. Until shown otherwise, I would like to refer to it as the "Jenks"
index.
-Each sorted container has a function named ``_check`` for verifying
+Each sorted container has a function named `_check` for verifying
consistency. This function details the data-type invariants.
diff -Nru sortedcontainers-1.5.9/docs/index.rst sortedcontainers-2.0.4/docs/index.rst
--- sortedcontainers-1.5.9/docs/index.rst 2017-12-08 21:13:29.000000000 +0000
+++ sortedcontainers-2.0.4/docs/index.rst 2018-06-07 05:34:49.000000000 +0000
@@ -1,121 +1,7 @@
-SortedContainers
-================
-
-`SortedContainers`_ is an Apache2 licensed sorted collections 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!
-
-::
-
- >>> sl = sortedcontainers.SortedList(range(int(1e7)))
- >>> 1234567 in sl
- True
- >>> sl[7654321]
- 7654321
- >>> sl.add(1234567)
- >>> sl.count(1234567)
- 2
- >>> sl *= 3
- >>> len(sl)
- 30000003
-
-*Note:* The snippet above requires at least a half gigabyte of memory. In
-64-bit versions of CPython an integer requires about 24 bytes. SortedList will
-add about 8 bytes per object stored in the container. That's pretty hard to
-beat as it's the cost of a pointer to each object. It's also 66% less overhead
-than a typical binary tree implementation (e.g. red-black tree, avl tree, aa
-tree, splay tree, treap, etc.) for which every node must also store two
-pointers to children nodes.
-
-`SortedContainers`_ takes all of the work out of Python sorted collections --
-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.
-
-Testimonials
-------------
-
-**Alex Martelli**, `Wikipedia`_
-
-Good stuff! ... I like the :doc:`simple, effective implementation
-` idea of splitting the sorted containers into smaller
-"fragments" to avoid the O(N) insertion costs.
-
-.. _`Wikipedia`: http://en.wikipedia.org/wiki/Alex_Martelli
-
-**Jeff Knupp**, `Review of SortedContainers`_
-
-That last part, "fast as C-extensions," was difficult to believe. I would need
-some sort of :doc:`performance comparison ` to be convinced this
-is true. The author includes this in the docs. It is.
-
-.. _`JeffKnupp.com`: http://jeffknupp.com/
-.. _`Review of SortedContainers`: http://reviews.jeffknupp.com/reviews/sortedcontainers/3/
-
-**Kevin Samuel**, `Formations Python`_
-
-I'm quite amazed, not just by the code quality (it's incredibly
-readable and has more comment than code, wow), but the actual
-amount of work you put at stuff that is *not* code:
-documentation, benchmarking, implementation explanations. Even
-the git log is clean and the unit tests run out of the box on
-Python 2 and 3.
-
-.. _`Formations Python`: http://formationspython.com/
-
-**Mark Summerfield**, a short plea for `Python Sorted Collections`_
-
-Python's "batteries included" standard library seems to have a battery
-missing. And the argument that "we never had it before" has worn thin. It is
-time that Python offered a full range of collection classes out of the box,
-including sorted ones.
-
-.. _`Python Sorted Collections`: http://www.qtrac.eu/pysorted.html
-
-Features
---------
-
-- Pure-Python
-- Fully documented
-- Benchmark comparison (alternatives, runtimes, load-factors)
-- 100% test coverage
-- Hours of stress testing
-- Performance matters (often faster than C implementations)
-- Compatible API (nearly identical to popular blist and rbtree modules)
-- Feature-rich (e.g. get the five largest keys in a sorted dict: d.iloc[-5:])
-- Pragmatic design (e.g. SortedSet is a Python set with a SortedList index)
-- Developed on Python 2.7
-- Tested on CPython 2.7, 3.2, 3.3, 3.4, 3.5, 3.6 and PyPy, PyPy3
-
-Quickstart
-----------
-
-Installing `SortedContainers`_ is simple with
-`pip `_::
-
- $ pip install sortedcontainers
-
-You can access documentation in the interpreter with Python's built-in help
-function:
-
- >>> from sortedcontainers import SortedList, SortedSet, SortedDict
- >>> help(SortedList)
-
-User Guide
-----------
-
-For those wanting more details, this part of the documentation describes
-introduction, implementation, performance, and development.
+.. include:: ../README.rst
.. toctree::
- :maxdepth: 1
+ :hidden:
introduction
performance
@@ -126,72 +12,9 @@
performance-scale
development
history
-
-API Documentation
------------------
-
-If you are looking for information on a specific function, class or method,
-this part of the documentation is for you.
-
-.. toctree::
- :maxdepth: 1
-
sortedlist
- sortedlistwithkey
sorteddict
sortedset
-
-Talks
------
-
-.. toctree::
- :maxdepth: 1
-
pycon-2016-talk
sf-python-2015-lightning-talk
djangocon-2015-lightning-talk
-
-Useful Links
-------------
-
-- `SortedContainers Documentation`_
-- `SortedContainers at PyPI`_
-- `SortedContainers at Github`_
-- `SortedContainers Issue Tracker`_
-
-.. _`SortedContainers Documentation`: http://www.grantjenks.com/docs/sortedcontainers/
-.. _`SortedContainers at PyPI`: https://pypi.python.org/pypi/sortedcontainers
-.. _`SortedContainers at Github`: https://github.com/grantjenks/sorted_containers
-.. _`SortedContainers Issue Tracker`: https://github.com/grantjenks/sorted_containers/issues
-
-Indices and Utilities
----------------------
-
-* :ref:`genindex`
-* :ref:`search`
-
-.. _`apache2`:
-
-Apache2 License
----------------
-
-A large number of open source projects you find today are `GPL Licensed`_.
-A project that is released as GPL cannot be used in any commercial product
-without the product itself also being offered as open source.
-
-The MIT, BSD, ISC, and Apache2 licenses are great alternatives to the GPL
-that allow your open-source software to be used freely in proprietary,
-closed-source software.
-
-`SortedContainers`_ is released under terms of the `Apache2 License`_.
-
-.. _`GPL Licensed`: http://www.opensource.org/licenses/gpl-license.php
-.. _`Apache2 License`: http://opensource.org/licenses/Apache-2.0
-
-
-SortedContainers License
-------------------------
-
-.. include:: ../LICENSE
-
-.. _`SortedContainers`: http://www.grantjenks.com/docs/sortedcontainers/
diff -Nru sortedcontainers-1.5.9/docs/introduction.rst sortedcontainers-2.0.4/docs/introduction.rst
--- sortedcontainers-1.5.9/docs/introduction.rst 2017-12-08 21:13:29.000000000 +0000
+++ sortedcontainers-2.0.4/docs/introduction.rst 2018-06-07 05:34:49.000000000 +0000
@@ -1,320 +1,796 @@
-SortedContainers Introduction
-=============================
+Sorted Containers Introduction
+==============================
-Installation
-------------
+.. currentmodule:: sortedcontainers
-This part of the documentation covers the installation of
-:doc:`SortedContainers`. The first step to using any software package
-is getting it properly installed.
+.. contents::
+ :local:
-Distribute & Pip
-................
-Installing :doc:`SortedContainers` is simple with `pip
-`_::
+Installation
+------------
- $ pip install sortedcontainers
+The first step to using any software library is getting it properly installed.
+There are several ways to install :doc:`Sorted Containers`.
-or, with `easy_install `_::
+The recommended way to install :doc:`Sorted Containers` is using the
+`pip`_ command::
- $ easy_install sortedcontainers
+ $ python3 -m pip install sortedcontainers
-But you should prefer pip when available.
+You may also choose instead to use the newer `pipenv`_ command::
-Get the Code
-............
+ $ pipenv install sortedcontainers
-:doc:`SortedContainers` is actively developed on GitHub, where the code
-is `always available `_.
+These commands will install the latest version of :doc:`Sorted
+Containers` from the `Python Package Index`_.
-You can either clone the public repository::
+:doc:`Sorted Containers` is actively developed on GitHub, where the code
+is `open source`_. You may choose to install directly from the source
+repository. First, you will need a copy of the sources. The recommended way to
+get a copy of the source repository is to clone the repository from GitHub::
- $ git clone git://github.com/grantjenks/sorted_containers.git
+ $ git clone git://github.com/grantjenks/python-sortedcontainers.git
-Download the `tarball `_::
+You may also choose instead to download the `Sorted Containers tarball`_ or
+download the `Sorted Containers zipball`_.
- $ curl -OL https://github.com/grantjenks/sorted_containers/tarball/master
+Once you have a copy of the sources, you can embed it in your Python package,
+or install it into your site-packages using the command::
-Or, download the `zipball `_::
+ $ python3 setup.py install
- $ curl -OL https://github.com/grantjenks/sorted_containers/zipball/master
+:doc:`Sorted Containers` is available in Debian distributions as
+`python3-sortedcontainers` and `python-sortedcontainers`.
-Once you have a copy of the source, you can embed it in your Python package,
-or install it into your site-packages easily::
+:doc:`Sorted Containers` is looking for a CentOS/RPM package
+maintainer. If you can help, please open an issue in the `Sorted Containers
+Issue Tracker`_.
- $ python setup.py install
+.. _`pip`: https://pypi.org/project/pip/
+.. _`pipenv`: https://pypi.org/project/pipenv/
+.. _`Python Package Index`: https://pypi.org/project/sortedcontainers/
+.. _`open source`: https://github.com/grantjenks/python-sortedcontainers
+.. _`Sorted Containers tarball`: https://github.com/grantjenks/python-sortedcontainers/tarball/master
+.. _`Sorted Containers zipball`: https://github.com/grantjenks/python-sortedcontainers/zipball/master
+.. _`Sorted Containers Issue Tracker`: https://github.com/grantjenks/python-sortedcontainers/issues
-:doc:`SortedContainers` is also available in Debian distributions as
-`python-sortedcontainers` and `python3-sortedcontainers`.
-SortedList
-----------
+Sorted List
+-----------
-SortedList is a sequence data type that always maintains its values in
-ascending sort order. As with Python's built-in list data type, SortedList
-supports duplicate elements and fast random-access indexing.
+At the core of :doc:`Sorted Containers` is the mutable sequence data
+type :class:`SortedList`. The :class:`SortedList` maintains its values in
+ascending sort order. As with Python's built-in list data type,
+:class:`SortedList` supports duplicate elements and fast random-access
+indexing.
>>> from sortedcontainers import SortedList
- >>> l = SortedList()
+ >>> sl = SortedList()
-Elements may be added to a SortedList using either :ref:`add `
-or :ref:`update `. When doing so, the list remains sorted.
-
- >>> l.update([0, 4, 1, 3, 2])
- >>> l
- SortedList([0, 1, 2, 3, 4])
- >>> l.index(3)
- 3
- >>> l.add(5)
- >>> l[-1]
+Values may be added to a :class:`SortedList` using either
+:func:`SortedList.update` or :func:`SortedList.add`. When doing so, the list
+remains sorted.
+
+ >>> sl.update([5, 1, 3, 4, 2])
+ >>> sl
+ SortedList([1, 2, 3, 4, 5])
+ >>> sl.add(0)
+ >>> sl
+ SortedList([0, 1, 2, 3, 4, 5])
+
+Several methods may be used to remove elements by value or by index. The
+methods :func:`SortedList.discard` and :func:`SortedList.remove` remove
+elements by value. And the methods :func:`SortedList.pop` and
+:func:`SortedList.__delitem__` remove elements by index. All values may be
+removed using :func:`SortedList.clear`.
+
+ >>> sl.remove(0)
+ >>> sl.discard(1)
+ >>> sl
+ SortedList([2, 3, 4, 5])
+ >>> sl.pop()
5
-
-Elements may also be inserted into a SortedList using :ref:`append
-`, :ref:`__setitem__ `, :ref:`insert
-`, or :ref:`extend `. These functions
-follow the programmer's directive to insert the element(s) at a specific
-location. Inserting an element out of order in this way will cause a
-ValueError.
-
- >>> l[:] = [0, 1, 2, 3, 4]
- >>> l.append(5)
- >>> l.insert(0, 0)
- >>> l.extend(range(6, 10))
- >>> print(','.join(map(str, l)))
- 0,0,1,2,3,4,5,6,7,8,9
- >>> l.insert(10, 5)
- ValueError
-
-Removing elements from a SortedList is done with :ref:`discard
-`, :ref:`remove `, :ref:`__delitem__
-`, or :ref:`pop `. These functions work
-identically to their list counterparts.
-
- >>> l[:] = range(10)
- >>> del l[-9:-3:3]
- >>> l.discard(0)
- >>> l.remove(5)
- >>> l.pop()
- 9
- >>> len(l)
+ >>> del sl[1]
+ >>> sl
+ SortedList([2, 4])
+ >>> sl.clear()
+
+Because :class:`SortedList` is sorted, it supports efficient lookups by value
+or by index. When accessing values by index, the :class:`SortedList` can be
+used as an `order statistic tree`_. Rather than performing a linear scan,
+values can be found in logarithmic time by repeatedly bisecting the internal
+tree structure. Methods for looking up values are
+:func:`SortedList.__contains__`, :func:`SortedList.count`,
+:func:`SortedList.index`, :func:`SortedList.bisect_left`,
+:func:`SortedList.bisect_right`, and :func:`SortedList.__getitem__`.
+
+ >>> sl = SortedList('abbcccddddeeeee')
+ >>> 'f' in sl
+ False
+ >>> sl.count('e')
5
+ >>> sl.index('c')
+ 3
+ >>> sl[3]
+ 'c'
+ >>> sl.bisect_left('d')
+ 6
+ >>> sl.bisect_right('d')
+ 10
+ >>> sl[6:10]
+ ['d', 'd', 'd', 'd']
-Because the SortedList maintains its elements in sorted order, several
-functions can be computed efficiently using binary-search. Those functions are
-:ref:`index `, :ref:`count `, :ref:`bisect
-`, :ref:`bisect_left `, and
-:ref:`bisect_right `.
-
- >>> l.clear()
- >>> l.update(range(1000000))
- >>> l.index(123456)
- 123456
- >>> l.count(654321)
- 1
- >>> l.bisect(123456.7)
- 123457
-
-SortedList does not support in-place :ref:`reverse `
-because values are always maintained in ascending sort order. To reverse a
-SortedList you may either request a :ref:`reversed `
-iterator or use negative indexing.
-
- >>> l[:] = range(5)
- >>> l.reverse()
- NotImplementedError: .reverse() not defined
- >>> list(reversed(l))
- [4, 3, 2, 1, 0]
- >>> l[-3:]
- [2, 3, 4]
-
-SortedList also works efficiently with other sequence data
-types. :ref:`Addition `, :ref:`multiplication
-`, and :ref:`comparison ` works as with
-other sequences.
-
- >>> l[:] = range(10)
- >>> l += range(10)
- >>> l *= 2
- >>> l >= [0, 0, 0, 0]
- True
- >>> del l[::4]
- >>> del l[::3]
- >>> del l[::2]
- >>> l == range(10)
- True
-
-SortedList adds two more functions to the list API: :ref:`islice
-` and :ref:`irange `. Each returns an
-iterator and slices the SortedList: `islice` according to traditional Python
-slicing rules, `start` to `stop`, inclusive and exclusive respectively; and
-`irange` from the `minimum` to `maximum`, both inclusive by default. Each
-method also accepts a `reverse` argument so that items are yielded from the
-iterator in reverse.
-
- >>> l[:] = range(10)
- >>> tuple(l.islice(3, 6, reverse=True))
- (5, 4, 3)
- >>> tuple(l.irange(2, 7, inclusive=(True, True)))
- (2, 3, 4, 5, 6, 7)
-
-For more details, refer to the :doc:`SortedList API documentation
-`.
-
-SortedListWithKey
------------------
-
-The :doc:`SortedContainers` project also maintains a specialized
-SortedList-like type that accepts a key-parameter as found with Python's
-built-in *sorted* function. A SortedListWithKey provides the same
-functionality as a SortedList but maintains the order of contained values based
-on the applied key-function. This simplifies the pattern of boxing/un-boxing
-which would otherwise be required.
+Several methods can be used to iterate values in a :class:`SortedList`. There
+are the typical sequence iterators: :func:`SortedList.__iter__` and
+:func:`SortedList.__reversed__`. There are also methods for iterating by value
+or by index using :func:`SortedList.irange` and
+:func:`SortedList.islice`. These methods produce iterators that are faster than
+repeatedly indexing the :class:`SortedList`.
+
+ >>> sl = SortedList('acegi')
+ >>> list(iter(sl))
+ ['a', 'c', 'e', 'g', 'i']
+ >>> list(reversed(sl))
+ ['i', 'g', 'e', 'c', 'a']
+ >>> list(sl.irange('b', 'h'))
+ ['c', 'e', 'g']
+ >>> list(sl.islice(1, 4))
+ ['c', 'e', 'g']
+
+A :class:`SortedList` also supports the typical sequence operators
+:func:`SortedList.__add__` and :func:`SortedList.__mul__` as well as their
+in-place counterparts.
+
+ >>> sl = SortedList('abc')
+ >>> sl + sl
+ SortedList(['a', 'a', 'b', 'b', 'c', 'c'])
+ >>> sl * 3
+ SortedList(['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c'])
+ >>> sl += 'de'
+ >>> sl
+ SortedList(['a', 'b', 'c', 'd', 'e'])
+ >>> sl *= 2
+ >>> sl
+ SortedList(['a', 'a', 'b', 'b', 'c', 'c', 'd', 'd', 'e', 'e'])
+
+Although :class:`SortedList` implements most of the mutable sequence methods,
+there are five which are not implemented. Each of these methods assigns a value
+at an index which is not supported by :class:`SortedList`.
+
+ >>> sl = SortedList('abcde')
+ >>> sl[2] = 'c'
+ Traceback (most recent call last):
+ ...
+ NotImplementedError: use ``del sl[index]`` and ``sl.add(value)`` instead
+ >>> sl.reverse()
+ Traceback (most recent call last):
+ ...
+ NotImplementedError: use ``reversed(sl)`` instead
+ >>> sl.append('f')
+ Traceback (most recent call last):
+ ...
+ NotImplementedError: use ``sl.add(value)`` instead
+ >>> sl.extend(['f', 'g', 'h'])
+ Traceback (most recent call last):
+ ...
+ NotImplementedError: use ``sl.update(values)`` instead
+ >>> sl.insert(5, 'f')
+ Traceback (most recent call last):
+ ...
+ NotImplementedError: use ``sl.add(value)`` instead
+
+Comparison with :class:`SortedList` uses lexicographical ordering as with other
+sequence types.
+
+Refer to the :doc:`Sorted List documentation` for additional
+parameters, more examples, and descriptions of runtime complexity.
+
+.. _`order statistic tree`: https://en.wikipedia.org/wiki/Order_statistic_tree
+
+
+Sorted-key List
+---------------
+
+The :doc:`Sorted Containers` project also maintains a specialized
+sorted-list-like type that accepts a key-parameter as found in Python's
+built-in `sorted` function. :class:`SortedKeyList` provides the same
+functionality as :class:`SortedList` but maintains the order of contained
+values based on the applied key-function. This simplifies the pattern of boxing
+and un-boxing which would otherwise be required.
- >>> from sortedcontainers import SortedListWithKey
- >>> l = SortedListWithKey(key=lambda val: -val)
+ >>> from operator import neg
+ >>> from sortedcontainers import SortedKeyList
+ >>> skl = SortedKeyList(key=neg)
The key function extracts a comparison key for ordering items in the list. In
-our example above we apply the negation operator. Doing so would maintain a
-list of integers in reverse.
+our example above we apply the negation operator. In the example above, a
+sorted list of integers would be ordered in descending sort order.
-You can also construct a SortedListWithKey using the SortedList type by passing
-a key-function to the constructor.
+You can also construct a :class:`SortedKeyList` using the :class:`SortedList`
+type by passing a key-function to the initializer.
>>> from sortedcontainers import SortedList
- >>> from operator import neg
- >>> values = SortedList(range(4), key=neg)
- >>> repr(values)
- SortedListWithKey([3, 2, 1, 0], key=, load=1000)
- >>> type(values)
-
+ >>> values = SortedList([1, 2, 3, 4, 5], key=neg)
+ >>> values
+ SortedKeyList([5, 4, 3, 2, 1], key=)
>>> isinstance(values, SortedList)
True
+ >>> issubclass(SortedKeyList, SortedList)
+ True
+ >>> values.key
+
-For more details, refer to the :doc:`SortedListWithKey API documentation
-`.
+:class:`SortedKeyList` adds three additional methods to the :class:`SortedList`
+type. They are :func:`SortedKeyList.bisect_key_left`,
+:func:`SortedKeyList.bisect_key_right`, and :func:`SortedKeyList.irange_key`.
+Each of these methods accepts the key rather than the value for its
+:class:`SortedList` counterpart.
+
+ >>> skl = SortedKeyList([1, 2, 3, 4, 5], key=neg)
+ >>> skl
+ SortedKeyList([5, 4, 3, 2, 1], key=)
+ >>> skl.bisect_key_left(-4.5)
+ 1
+ >>> skl.bisect_key_right(-1.5)
+ 4
+ >>> list(skl.irange_key(-4.5, -1.5))
+ [4, 3, 2]
+
+Refer to the :doc:`Sorted List documentation` for additional
+parameters, more examples, and descriptions of runtime complexity.
+
+
+Caveats
+-------
+
+:doc:`Sorted Containers` data types have three requirements:
+
+1. The comparison value or key must have a `total ordering`_.
+
+2. The comparison value or key must not change while the value is stored in the
+ sorted container.
+
+3. If the key-function parameter is used, then equal values must have equal
+ keys.
+
+If any of these three requirements are violated then the warranty of
+:doc:`Sorted Containers` is void and it will not behave correctly. While
+it may be possible to design useful data types that do not have these
+requirements, these are the caveats of :doc:`Sorted Containers` and they
+match those of :doc:`alternative implementations`. Each of these
+requirements allow for optimizations and together they are an attempt to find
+the right tradeoff between functionality and performance.
+
+Let's look at some examples of what works and what doesn't. In Python, all
+objects inherit from ``object`` which provides a default implementation of
+equality. In pseudocode, the object type looks something like:
+
+ >>> class Object:
+ ... def __eq__(self, other):
+ ... return id(self) == id(other)
+
+The default implementation defines equality in terms of identity. Note that
+`Object` does not define comparison methods like less-than or
+greater-than. While Python objects are comparable by default in Python 2, the
+feature was removed in Python 3. Instances of `object` can *not* be stored in a
+:class:`SortedList`.
+
+We can extend this example by creating our own `Record` data type with `name`
+and `rank` attributes.
+
+ >>> class Record(object):
+ ... def __init__(self, name, rank):
+ ... self.name = name
+ ... self.rank = rank
+ ... def __eq__(self, other):
+ ... return self.name == other.name
+
+The `Record` type defines equality in terms of its `name` attribute which may
+be thought of as a record identifier. Each `Record` also has a `rank` which
+would be useful for ranking records in sorted order. The `Record` type does not
+define comparison operators and so can *not* be stored in a
+:class:`SortedList`.
+
+ >>> alice1 = Record('alice', 1)
+ >>> bob2 = Record('bob', 2)
+ >>> carol3 = Record('carol', 3)
+
+Since the `rank` attribute is intended for ordering records, the key-function
+presents a tempting but invalid use for ordering records::
+
+ >>> get_rank = lambda record: record.rank
+ >>> sl = SortedList([alice1, bob2, carol3], key=get_rank)
+
+Although the sorted list now appears to work, the requirements have been
+invalidated. Specifically #3, since it is now possible for equal values to have
+inequal keys::
-SortedDict
-----------
+ >>> bob4 = Record('bob', 4)
+ >>> bob2 == bob4 # Equal values.
+ True
+ >>> get_rank(bob2) == get_rank(bob4)
+ False
+ >>> # ^-- Equal values should have equal keys.
+ >>> bob4 in sl # <-- Here's the problem. BAD!
+ False
+
+In the example above, `bob4` can not be found in `sl` because although `bob2`
+and `bob4` are equal, the corresponding keys are not equal. The mistake is a
+bit easier to see without the key-function. The key-function defined
+comparisons between records like so::
+
+ >>> class Record(object):
+ ... def __init__(self, name, rank):
+ ... self.name = name
+ ... self.rank = rank
+ ... def __eq__(self, other):
+ ... return self.name == other.name
+ ... def __lt__(self, other):
+ ... return self.rank < other.rank
+
+Written as above, equality between objects is more clearly seen as unrelated to
+ordering between objects. This is the most common mistake made when using
+:doc:`Sorted Containers`. The `Record` type now also violates
+requirement #1 because equal instances can also be strictly less than each
+other::
+
+ >>> bob2 = Record('bob', 2)
+ >>> bob4 = Record('bob', 4)
+ >>> bob2 == bob4
+ True
+ >>> bob2 < bob4 # <-- Here's the problem. BAD!
+ True
+
+In the above example, `bob2` and `bob4` are equal to each other while `bob2` is
+also strictly less than `bob4`. The `Record` type therefore does not have a
+`total ordering`_. In pseudocode the three requirements for a `total ordering`_
+are:
+
+I. If ``a <= b and b <= a`` then ``a == b``.
+
+II. And if ``a <= b and b <= c`` then ``a <= c``.
+
+III. And ``a <= b or b <= a``.
+
+Intuitively, a `total ordering`_ is best understood through integer and string
+types. Each of these common types defines a `total ordering`_ and can be used
+for comparisons in :doc:`Sorted Containers`. Of the built-in types in
+Python, these have a `total ordering`_:
+
+1. Integers
+
+2. Strings and bytes.
+
+3. All foating-point numbers except ``float('nan')``.
+
+4. Sequences like `list` and `tuple` of values with a total ordering.
+
+There are also some built-in Python types and values which lack a total
+ordering:
+
+1. Sets and frozensets (not a total ordering).
+
+2. ``float('nan')`` (not a total ordering).
+
+3. Mapping types (not comparable, changed in Python 3).
+
+The best way to fix the `Record` type is to define equality and comparison in
+terms of the same fields.
+
+ >>> class Record(object):
+ ... def __init__(self, name, rank):
+ ... self.name = name
+ ... self.rank = rank
+ ... def _cmp_key(self):
+ ... return (self.rank, self.name)
+ ... def __eq__(self, other):
+ ... return self._cmp_key() == other._cmp_key()
+ ... def __lt__(self, other):
+ ... return self._cmp_key() < other._cmp_key()
-A SortedDict is a container of key-value pairs in which an order is imposed on
-the keys according to their ordered relation to each other. As with Python's
-built-in ``dict`` data type, SortedDict supports fast insertion, deletion, and
-lookup by key. Iterating a SortedDict yields the keys in sorted order. The API
-strives to be as similar to the built-in ``dict`` type as possible.
+The example above uses a comparison-key method named `_cmp_key` and the
+lexicographical ordering semantics of tuples to define equality and comparison
+in terms of the `rank` and `name` fields. It would also be possible to omit the
+`Record.__lt__` method and instead use a key-function which called
+`record._cmp_key()`. But the key-function will take more memory and be slower
+as it uses a :class:`SortedKeyList` which stores a reference to the key for
+every value.
+
+The `Record` example above is complicated by equality defined as those objects
+with equal names. When using equality inherited from `object`, that is, defined
+in terms of instance identity, the situation is simplified. For example:
+
+ >>> class Record(object):
+ ... def __init__(self, name, rank):
+ ... self.name = name
+ ... self.rank = rank
+ ... def __lt__(self, other):
+ ... return self.rank < other.rank
+
+The `Record` type now can be stored in :class:`SortedList` because equality
+based on instance identity guarantees the `rank` attributes are equal so long
+as its value has a `total ordering`_.
+
+ >>> alice1 = Record('alice', 1)
+ >>> bob2 = Record('bob', 2)
+ >>> carol3 = Record('carol', 3)
+ >>> bob4 = Record('bob', 4)
+ >>> bob2 != bob4 # <-- Different instances, so unequal. GOOD!
+ True
+ >>> sl = SortedList([alice1, bob2, carol3, bob4])
+ >>> bob2 in sl
+ True
+ >>> bob4 in sl
+ True
+
+The above example displays that all three requirements are followed:
+
+1. The comparison key, `rank`, is an integer, which has a `total ordering`_.
+
+2. The comparison key does not change while the value is stored in the sorted
+ container.
+
+3. Equal `Record` instances have equal `rank` attributes based on instance
+ identity.
+
+These examples can be summarized in two pieces of advice:
+
+1. If the data type defines its own equality, that is ``__eq__``, then make
+ sure the comparison methods or key-function define a `total ordering`_ and
+ equal values have equal comparison keys.
+
+2. If the data type does not define equality then it inherits equality from
+ `object` and uses instance identity. Compare objects using comparison
+ methods like ``__lt__`` or the key-function. The compared values must have a
+ `total ordering`_.
+
+Another invalid use case of :class:`SortedKeyList` occurs when the key-function
+returns a different comparison key for a given value while the value is stored
+in the sorted container.
+
+ >>> from random import random
+ >>> key_func = lambda value: random()
+ >>> sl = SortedList([1, 2, 3, 4, 5], key=key_func)
+ >>> # ^-- Corrupt sorted list.
+ >>> 3 in sl
+ False
+ >>> key_func(1) == key_func(1) # <-- Here's the problem. BAD!
+ False
+
+The example above violates two requirements of sorted lists: equal values must
+have equal keys and the key function must return the same key for the given
+value while the value is stored in the sorted container. The `random`
+key-function does not reliably return the same key for a given value. The order
+of values in a sorted container can be made arbitrary and reliable by changing
+the key-function like so:
+
+ >>> from random import seed
+ >>> def key_func(value):
+ ... "Key-function for arbitrary but reliable order."
+ ... seed(value)
+ ... return random()
+
+Another way the problem above manifests itself is when the comparison key of an
+object is mutated while the object is stored in the :class:`SortedList`. Using
+the `Record` definition from above:
+
+ >>> class Record(object):
+ ... def __init__(self, name, rank):
+ ... self.name = name
+ ... self.rank = rank
+ ... def __lt__(self, other):
+ ... return self.rank < other.rank
+ >>> alice1 = Record('alice', 1)
+ >>> bob2 = Record('bob', 2)
+ >>> carol3 = Record('carol', 3)
+ >>> sl = SortedList([alice1, bob2, carol3])
+ >>> bob2 in sl
+ True
+
+Python objects are typically mutable so while the above example works and is
+correct, there's nothing preventing a modification to the `rank` of a `Record`.
+If the `rank` is modified while the `Record` instance is stored in the
+:class:`SortedList`, then the container is corrupted.
+
+ >>> bob2.rank = 20 # <-- Here's the problem. BAD!
+ >>> bob2 in sl
+ False
+
+The `Record` instance `bob2` can no longer be found in the :class:`SortedList`
+because modifying the `rank` changed its sort order position without updating
+its position in `sl`. To modify the sorted order position, :func:`remove
+` the value, update it, and then :func:`add
+` the value back again.
+
+Similar limitations also apply to Python's `dict` data type which can be
+corrupted by modifying the hash of a key while the item is stored in the
+`dict`. The hashing protocol also requires that equal keys have equal hashes.
+
+One final caveat: indexing a sorted list is fast but not as fast as indexing
+Python's built-in list data type. The runtime complexity for indexing a sorted
+list is `O(log(n))` while it is `O(1)` for Python's built-in list data type.
+Indexing a sorted list requires building and maintaining a positional index
+which is not built if not necessary. The index is fast and light on memory
+overhead but avoid positional indexing if able. Indexing at the front or back,
+indexes like `0` and `-1`, is optimized and will not require the positional
+index.
+
+.. _`total ordering`: https://en.wikipedia.org/wiki/Total_order
+
+
+Sorted Dict
+-----------
+
+Built atop Python's built-in `dict` data type and :class:`SortedList` is the
+mutable mapping data type :class:`SortedDict`. Sorted dict keys are maintained
+in sorted order. The design of :class:`SortedDict` is simple: sorted dict
+inherits from `dict` to store items and maintains a sorted list of
+keys. :class:`SortedDict` keys must be hashable and comparable. The hash and
+total ordering of keys must not change while they are stored in the
+:class:`SortedDict`.
>>> from sortedcontainers import SortedDict
- >>> d = SortedDict()
- >>> d.update(alice=518, bob=285, carol=925, dave=376, ellen=874)
- >>> print(''.join(key[0] for key in d))
- abcde
- >>> d['frank'] = 102
- >>> d['bob'] = 341
- >>> del d['frank']
- >>> 'ellen' in d
+ >>> sd = SortedDict()
+
+Items may be added to a :class:`SortedDict` using
+:func:`SortedDict.__setitem__`, :func:`SortedDict.update` or
+:func:`SortedDict.setdefault`. When doing so, the keys remain sorted.
+
+ >>> sd['e'] = 5
+ >>> sd['b'] = 2
+ >>> sd
+ SortedDict({'b': 2, 'e': 5})
+ >>> sd.update({'d': 4, 'c': 3})
+ >>> sd
+ SortedDict({'b': 2, 'c': 3, 'd': 4, 'e': 5})
+ >>> sd.setdefault('a', 1)
+ 1
+ >>> sd
+ SortedDict({'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5})
+
+Several methods may be used to remove items by key or by index. The methods
+:func:`SortedDict.__delitem__` and :func:`SortedDict.pop` remove items by
+key. And the method :func:`SortedDict.popitem` removes items by index.
+
+ >>> del sd['d']
+ >>> sd.pop('c')
+ 3
+ >>> sd.popitem(index=-1)
+ ('e', 5)
+ >>> sd
+ SortedDict({'a': 1, 'b': 2})
+
+Because :class:`SortedDict` uses both `dict` and :class:`SortedList`, there are
+many methods for looking up keys from each type. The mapping interface supports
+:func:`SortedDict.__getitem__`, :func:`SortedDict.__contains__`,
+:func:`SortedDict.get`, and :func:`SortedDict.peekitem`.
+
+ >>> sd['b']
+ 2
+ >>> 'c' in sd
+ False
+ >>> sd.get('z') is None
True
- >>> d.get('frank', 0)
- 0
- >>> d.pop()
- 'ellen'
+ >>> sd.peekitem(index=-1)
+ ('b', 2)
-SortedDict also supports key, value, and item iteration/views according to the
-Python version. (Python 2.7 and higher supports views while Python 2.6 supports
-only iteration.) View operations like :ref:`and `,
-:ref:`or `, :ref:`sub `, and
-:ref:`xor ` return a SortedSet container.
-
- >>> d.clear()
- >>> d.update(list(enumerate('0123456789')))
- >>> keys = d.keys()
- >>> len(keys)
- 10
- >>> d[-1] = '-1'
- >>> len(keys)
- 11
- >>> s = SortedDict([(1, '1'), (2, '2'), (3, '3'), (10, '10')])
- >>> s.keys() & keys
- SortedSet([1, 2, 3])
-
-In addition to the normal dictionary operations, SortedDict supports fast
-:ref:`indexing with iloc` and :ref:`key index
-lookup`. Using indexing, you can quickly lookup the nth key
-in iteration. These utilities are not common in other implementations but can
-be extremely useful. Indexing also supports slice notation.
+The sequence interface supports the same lookup methods as those provided by
+:class:`SortedList`.
- >>> d = SortedDict(b=2, d=4, c=3, e=5, a=1)
- >>> d.iloc[0]
- 'a'
- >>> d.iloc[-1]
- 'e'
- >>> d.iloc[-3:]
- ['c', 'd', 'e']
- >>> d.index('c')
+ >>> sd.bisect_right('b')
2
+ >>> sd.index('a')
+ 0
+ >>> list(sd.irange('a', 'z'))
+ ['a', 'b']
-SortedDict's contructor supports two additional positional arguments. These
-must occur before any sequences, mappings or keyword arguments used to
-initialize the SortedDict. The first positional argument is an optional
-callable `key` used to extract a comparison key from the SortedDict's keys. The
-second positional argument is an optional integer representing the load-factor.
+The keys, items, and values views also support both set semantics and sequence
+semantics with optimized methods for lookups by index.
-For example, to contruct a mapping with integer keys in descending order and a
-load-factor of 100:
+ >>> keys = sd.keys()
+ >>> keys[0]
+ 'a'
+ >>> items = sd.items()
+ >>> items[-1]
+ ('b', 2)
+ >>> values = sd.values()
+ >>> values[:]
+ [1, 2]
+
+The :class:`SortedDict` initializer supports one additional position argument.
+The positional argument must come before any sequences, mappings, or keyword
+arguments used to initialize the items in a :class:`SortedDict`. The first
+positional argument is an optional callable key-function used to extract a
+comparison key from the keys of the :class:`SortedDict`. For example, to
+construct a :class:`SortedDict` with integer keys in descending order:
+
+ >>> sd = SortedDict(neg, enumerate('abc', start=1))
+ >>> sd
+ SortedDict(, {3: 'c', 2: 'b', 1: 'a'})
+ >>> keys = sd.keys()
+ >>> list(keys)
+ [3, 2, 1]
+
+Because :class:`SortedDict` inherits from `dict`, the `__missing__` method can
+be used to give missing keys a default value. Customizing the `__missing__`
+method creates a kind of `defaultdict` like that in the `collections` module.
+
+ >>> class DefaultSortedDict(SortedDict):
+ ... def __missing__(self, key):
+ ... return 0
+ >>> dsd = DefaultSortedDict()
+ >>> dsd['z']
+ 0
- >>> from operator import neg
- >>> d = SortedDict(neg, 100, enumerate(range(4)))
- >>> d
- SortedDict(, 100, {3: 3, 2: 2, 1: 1, 0: 0})
+Refer to the :doc:`Sorted Dict documentation` for additional
+parameters, more examples, and descriptions of runtime complexity.
-For more details, refer to the :doc:`SortedDict API documentation
-`.
-SortedSet
----------
+Sorted Set
+----------
-A :doc:`SortedSet` is a collection of distinct objects in which an
-order is imposed on the members according to their sorted relation to each
-other. The API is similar to the :doc:`SortedList` and built-in
-``set`` type. Iterating a SortedSet yields the items in sorted order.
+Standing on the shoulder's of Python's built-in `set` data type and
+:class:`SortedList` is the mutable set data type :class:`SortedSet`. Sorted set
+values are maintained in sorted order. The design of :class:`SortedSet` is
+simple: sorted set uses Python's built-in `set` for set-operations and
+maintains a sorted list of values. Values stored in a :class:`SortedSet` must
+be hashable and comparable. The hash and total ordering of values must not
+change while they are stored in the :class:`SortedSet`.
>>> from sortedcontainers import SortedSet
- >>> s = SortedSet([3, 1, 0, 2])
- >>> list(s)
- [0, 1, 2, 3]
-
-Like the built-in set container type, SortedSet supports
-:ref:`difference`,
-:ref:`intersection`,
-:ref:`symmetric_difference`, and
-:ref:`union` operations along with their ``*_update``
-counterparts.
-
- >>> s.clear()
- >>> s.add(-1)
- >>> s.update(xrange(10))
- >>> 5 in s
- True
- >>> s - [1, 2, 3]
- SortedSet([-1, 0, 4, 5, 6, 7, 8, 9])
- >>> s & [-3, -2, -1, 0]
- SortedSet([-1, 0])
- >>> s > [1, 2, 3]
- True
-
-Adding and removing elements works the same as with the SortedList container
-although positional updates are not permitted. Unlike the built-in ``set``
-type, SortedSet has full indexing support for
-:ref:`set[index]` and :ref:`del
-set[index]` operations.
-
- >>> s.clear()
- >>> s.update(xrange(100))
- >>> s[5]
+ >>> ss = SortedSet()
+
+:class:`SortedSet` implements optimized versions of the core mutable set
+methods: :func:`SortedSet.__contains__`, :func:`SortedSet.add`,
+:func:`SortedSet.update`, :func:`SortedSet.discard`, and the more strict
+:func:`SortedSet.remove`.
+
+ >>> ss.add('c')
+ >>> ss.add('a')
+ >>> ss.add('b')
+ >>> ss
+ SortedSet(['a', 'b', 'c'])
+ >>> 'c' in ss
+ True
+ >>> ss.discard('a')
+ >>> ss.remove('b')
+ >>> _ = ss.update('def')
+ >>> ss
+ SortedSet(['c', 'd', 'e', 'f'])
+
+:class:`SortedSet` also behaves like a sequence with
+:func:`SortedSet.__getitem__` and :func:`SortedSet.__reversed__` methods. And
+includes the mutable sequence methods :func:`SortedSet.__delitem__` and
+:func:`SortedSet.pop`.
+
+ >>> ss[0]
+ 'c'
+ >>> list(reversed(ss))
+ ['f', 'e', 'd', 'c']
+ >>> del ss[0]
+ >>> ss.pop(index=-1)
+ 'f'
+ >>> ss
+ SortedSet(['d', 'e'])
+
+Set-operation methods like :func:`SortedSet.difference`,
+:func:`SortedSet.intersection`, :func:`SortedSet.symmetric_difference`, and
+:func:`SortedSet.union`, as well as their in-place counterparts and operators
+are all supported.
+
+ >>> abcd = SortedSet('abcd')
+ >>> cdef = SortedSet('cdef')
+ >>> abcd.difference(cdef)
+ SortedSet(['a', 'b'])
+ >>> abcd.intersection(cdef)
+ SortedSet(['c', 'd'])
+ >>> abcd.symmetric_difference(cdef)
+ SortedSet(['a', 'b', 'e', 'f'])
+ >>> abcd.union(cdef)
+ SortedSet(['a', 'b', 'c', 'd', 'e', 'f'])
+ >>> abcd | cdef
+ SortedSet(['a', 'b', 'c', 'd', 'e', 'f'])
+ >>> abcd |= cdef
+ >>> abcd
+ SortedSet(['a', 'b', 'c', 'd', 'e', 'f'])
+
+Several :class:`SortedList` methods are also exposed on :class:`SortedSet`
+objects like :func:`SortedList.bisect`, :func:`SortedList.index`,
+:func:`SortedList.irange`, and :func:`SortedList.islice` just as with
+:class:`SortedDict`.
+
+ >>> ss = SortedSet('abcdef')
+ >>> ss.bisect('d')
+ 4
+ >>> ss.index('f')
5
- >>> s[2:10:2]
- SortedSet([2, 4, 6, 8])
- >>> del s[3:15:3]
- >>> len(s)
- 96
+ >>> list(ss.irange('b', 'e'))
+ ['b', 'c', 'd', 'e']
+ >>> list(ss.islice(-3))
+ ['d', 'e', 'f']
+
+Like :class:`SortedList` an additional `key` parameter can be used to
+initialize the :class:`SortedSet` with a callable which is used to extract a
+comparison key.
+
+ >>> ss = SortedSet([1, 2, 3], key=neg)
+ >>> ss
+ SortedSet([3, 2, 1], key=)
+
+Sorted set comparisons use subset and superset relations. Two sorted sets are
+equal if and only if every element of each sorted set is contained in the other
+(each is a subset of the other). A sorted set is less than another sorted set
+if and only if the first sorted set is a proper subset of the second sorted set
+(is a subset, but is not equal). A sorted set is greater than another sorted
+set if and only if the first sorted set is a proper superset of the second
+sorted set (is a superset, but is not equal). The comparison semantics of
+sorted sets do not define a total ordering.
+
+Refer to the :doc:`Sorted Set documentation` for additional
+parameters, more examples, and descriptions of runtime complexity.
+
+
+Migrating
+---------
-For more details, refer to the :doc:`SortedSet API documentation`.
+The :doc:`performance comparison` page documents several
+alternative implementations of the sorted types described. Some of those
+projects have deprecated themselves and now recommend :doc:`Sorted
+Containers` instead. When migrating from other projects, there are a
+couple of things to keep in mind.
+
+:doc:`Sorted Containers` went through a major version change between
+version one and version two. The goal of the change was to adopt Python 3
+semantics wherever possible:
+
+1. Several :class:`SortedList` methods now raise :exc:`NotImplementedError`:
+ :func:`SortedList.__setitem__`, :func:`SortedList.append`, and
+ :func:`SortedList.extend`. Use :func:`SortedList.add` or
+ :func:`SortedList.update` instead.
+
+2. :class:`SortedDict` has adopted the Python 3 semantics of `dict` views as
+ the default. The :func:`SortedDict.keys`, :func:`SortedDict.items`, and
+ :func:`SortedDict.values` methods now return views with support for
+ optimized indexing. The view objects also implement set and sequence
+ protocol methods. Prefer using the :class:`SortedDict` methods directly for
+ better performance.
+
+3. Some type and parameter names were changed. `SortedListWithKey` was renamed
+ to `SortedKeyList` but an alias remains for compatibility. Several methods
+ which accepted a `val` parameter now accept `value` for better readability.
+
+The :doc:`history` documents all the changes made in every version in the
+history of the project. The :ref:`Version 2` release notes detail all the
+changes made.
+
+The `blist`_ project remains the most similar as its API was the original
+inspiration for :doc:`Sorted Containers`. The main difference has always
+been the :func:`SortedList.pop` method. The `blist`_ project pops the first
+element by default while :doc:`Sorted Containers` pops the last element
+and matches the API of Python's built-in `list` data type. The sorted dict data
+type in `blist`_ also continues to use the old Python 2 semantics for `dict`
+views.
+
+The `bintrees`_ project now recommends using :doc:`Sorted Containers`
+instead and has stopped development. The API differs significantly but the
+supported functionality is the same. The `Tree` object in `bintrees`_ is most
+similar to :class:`SortedDict`. All of the mapping methods and set methods are
+available using either :class:`SortedDict` or :class:`SortedKeysView`. The
+slicing methods and previous/successor iterator methods correspond to
+:func:`SortedDict.irange` and the heap methods correspond to indexing with
+views like :func:`SortedKeysView.__getitem__`.
+
+The `banyan`_ project has data types similar to :class:`SortedDict` and
+:class:`SortedSet`. Most methods have a direct counterpart in :doc:`Sorted
+Containers`. But the frozen sorted dict and frozen sorted set data types
+have no direct comparison. The functionality of hashing can be implemented by
+inheriting and defining the `__hash__` method. Do so with care, because the
+instance is still mutable. The `banyan`_ project also supports tree
+augmentation which can be useful in implementing interval trees or segment
+trees. There is no support for tree argumentation in :doc:`Sorted
+Containers`.
+
+.. _`blist`: https://pypi.org/project/blist/
+.. _`bintrees`: https://pypi.org/project/bintrees/
+.. _`banyan`: https://pypi.org/project/Banyan/
diff -Nru sortedcontainers-1.5.9/docs/make.bat sortedcontainers-2.0.4/docs/make.bat
--- sortedcontainers-1.5.9/docs/make.bat 2017-12-08 21:13:29.000000000 +0000
+++ sortedcontainers-2.0.4/docs/make.bat 2018-06-07 05:34:49.000000000 +0000
@@ -1,242 +1,36 @@
-@ECHO OFF
-
-REM Command file for Sphinx documentation
-
-if "%SPHINXBUILD%" == "" (
- set SPHINXBUILD=sphinx-build
-)
-set BUILDDIR=_build
-set ALLSPHINXOPTS=-d %BUILDDIR%/doctrees %SPHINXOPTS% .
-set I18NSPHINXOPTS=%SPHINXOPTS% .
-if NOT "%PAPER%" == "" (
- set ALLSPHINXOPTS=-D latex_paper_size=%PAPER% %ALLSPHINXOPTS%
- set I18NSPHINXOPTS=-D latex_paper_size=%PAPER% %I18NSPHINXOPTS%
-)
-
-if "%1" == "" goto help
-
-if "%1" == "help" (
- :help
- echo.Please use `make ^` where ^ is one of
- echo. html to make standalone HTML files
- echo. dirhtml to make HTML files named index.html in directories
- echo. singlehtml to make a single large HTML file
- echo. pickle to make pickle files
- echo. json to make JSON files
- echo. htmlhelp to make HTML files and a HTML help project
- echo. qthelp to make HTML files and a qthelp project
- echo. devhelp to make HTML files and a Devhelp project
- echo. epub to make an epub
- echo. latex to make LaTeX files, you can set PAPER=a4 or PAPER=letter
- echo. text to make text files
- echo. man to make manual pages
- echo. texinfo to make Texinfo files
- echo. gettext to make PO message catalogs
- echo. changes to make an overview over all changed/added/deprecated items
- echo. xml to make Docutils-native XML files
- echo. pseudoxml to make pseudoxml-XML files for display purposes
- echo. linkcheck to check all external links for integrity
- echo. doctest to run all doctests embedded in the documentation if enabled
- goto end
-)
-
-if "%1" == "clean" (
- for /d %%i in (%BUILDDIR%\*) do rmdir /q /s %%i
- del /q /s %BUILDDIR%\*
- goto end
-)
-
-
-%SPHINXBUILD% 2> nul
-if errorlevel 9009 (
- echo.
- echo.The 'sphinx-build' command was not found. Make sure you have Sphinx
- echo.installed, then set the SPHINXBUILD environment variable to point
- echo.to the full path of the 'sphinx-build' executable. Alternatively you
- echo.may add the Sphinx directory to PATH.
- echo.
- echo.If you don't have Sphinx installed, grab it from
- echo.http://sphinx-doc.org/
- exit /b 1
-)
-
-if "%1" == "html" (
- %SPHINXBUILD% -b html %ALLSPHINXOPTS% %BUILDDIR%/html
- if errorlevel 1 exit /b 1
- echo.
- echo.Build finished. The HTML pages are in %BUILDDIR%/html.
- goto end
-)
-
-if "%1" == "dirhtml" (
- %SPHINXBUILD% -b dirhtml %ALLSPHINXOPTS% %BUILDDIR%/dirhtml
- if errorlevel 1 exit /b 1
- echo.
- echo.Build finished. The HTML pages are in %BUILDDIR%/dirhtml.
- goto end
-)
-
-if "%1" == "singlehtml" (
- %SPHINXBUILD% -b singlehtml %ALLSPHINXOPTS% %BUILDDIR%/singlehtml
- if errorlevel 1 exit /b 1
- echo.
- echo.Build finished. The HTML pages are in %BUILDDIR%/singlehtml.
- goto end
-)
-
-if "%1" == "pickle" (
- %SPHINXBUILD% -b pickle %ALLSPHINXOPTS% %BUILDDIR%/pickle
- if errorlevel 1 exit /b 1
- echo.
- echo.Build finished; now you can process the pickle files.
- goto end
-)
-
-if "%1" == "json" (
- %SPHINXBUILD% -b json %ALLSPHINXOPTS% %BUILDDIR%/json
- if errorlevel 1 exit /b 1
- echo.
- echo.Build finished; now you can process the JSON files.
- goto end
-)
-
-if "%1" == "htmlhelp" (
- %SPHINXBUILD% -b htmlhelp %ALLSPHINXOPTS% %BUILDDIR%/htmlhelp
- if errorlevel 1 exit /b 1
- echo.
- echo.Build finished; now you can run HTML Help Workshop with the ^
-.hhp project file in %BUILDDIR%/htmlhelp.
- goto end
-)
-
-if "%1" == "qthelp" (
- %SPHINXBUILD% -b qthelp %ALLSPHINXOPTS% %BUILDDIR%/qthelp
- if errorlevel 1 exit /b 1
- echo.
- echo.Build finished; now you can run "qcollectiongenerator" with the ^
-.qhcp project file in %BUILDDIR%/qthelp, like this:
- echo.^> qcollectiongenerator %BUILDDIR%\qthelp\sortedcontainers.qhcp
- echo.To view the help file:
- echo.^> assistant -collectionFile %BUILDDIR%\qthelp\sortedcontainers.ghc
- goto end
-)
-
-if "%1" == "devhelp" (
- %SPHINXBUILD% -b devhelp %ALLSPHINXOPTS% %BUILDDIR%/devhelp
- if errorlevel 1 exit /b 1
- echo.
- echo.Build finished.
- goto end
-)
-
-if "%1" == "epub" (
- %SPHINXBUILD% -b epub %ALLSPHINXOPTS% %BUILDDIR%/epub
- if errorlevel 1 exit /b 1
- echo.
- echo.Build finished. The epub file is in %BUILDDIR%/epub.
- goto end
-)
-
-if "%1" == "latex" (
- %SPHINXBUILD% -b latex %ALLSPHINXOPTS% %BUILDDIR%/latex
- if errorlevel 1 exit /b 1
- echo.
- echo.Build finished; the LaTeX files are in %BUILDDIR%/latex.
- goto end
-)
-
-if "%1" == "latexpdf" (
- %SPHINXBUILD% -b latex %ALLSPHINXOPTS% %BUILDDIR%/latex
- cd %BUILDDIR%/latex
- make all-pdf
- cd %BUILDDIR%/..
- echo.
- echo.Build finished; the PDF files are in %BUILDDIR%/latex.
- goto end
-)
-
-if "%1" == "latexpdfja" (
- %SPHINXBUILD% -b latex %ALLSPHINXOPTS% %BUILDDIR%/latex
- cd %BUILDDIR%/latex
- make all-pdf-ja
- cd %BUILDDIR%/..
- echo.
- echo.Build finished; the PDF files are in %BUILDDIR%/latex.
- goto end
-)
-
-if "%1" == "text" (
- %SPHINXBUILD% -b text %ALLSPHINXOPTS% %BUILDDIR%/text
- if errorlevel 1 exit /b 1
- echo.
- echo.Build finished. The text files are in %BUILDDIR%/text.
- goto end
-)
-
-if "%1" == "man" (
- %SPHINXBUILD% -b man %ALLSPHINXOPTS% %BUILDDIR%/man
- if errorlevel 1 exit /b 1
- echo.
- echo.Build finished. The manual pages are in %BUILDDIR%/man.
- goto end
-)
-
-if "%1" == "texinfo" (
- %SPHINXBUILD% -b texinfo %ALLSPHINXOPTS% %BUILDDIR%/texinfo
- if errorlevel 1 exit /b 1
- echo.
- echo.Build finished. The Texinfo files are in %BUILDDIR%/texinfo.
- goto end
-)
-
-if "%1" == "gettext" (
- %SPHINXBUILD% -b gettext %I18NSPHINXOPTS% %BUILDDIR%/locale
- if errorlevel 1 exit /b 1
- echo.
- echo.Build finished. The message catalogs are in %BUILDDIR%/locale.
- goto end
-)
-
-if "%1" == "changes" (
- %SPHINXBUILD% -b changes %ALLSPHINXOPTS% %BUILDDIR%/changes
- if errorlevel 1 exit /b 1
- echo.
- echo.The overview file is in %BUILDDIR%/changes.
- goto end
-)
-
-if "%1" == "linkcheck" (
- %SPHINXBUILD% -b linkcheck %ALLSPHINXOPTS% %BUILDDIR%/linkcheck
- if errorlevel 1 exit /b 1
- echo.
- echo.Link check complete; look for any errors in the above output ^
-or in %BUILDDIR%/linkcheck/output.txt.
- goto end
-)
-
-if "%1" == "doctest" (
- %SPHINXBUILD% -b doctest %ALLSPHINXOPTS% %BUILDDIR%/doctest
- if errorlevel 1 exit /b 1
- echo.
- echo.Testing of doctests in the sources finished, look at the ^
-results in %BUILDDIR%/doctest/output.txt.
- goto end
-)
-
-if "%1" == "xml" (
- %SPHINXBUILD% -b xml %ALLSPHINXOPTS% %BUILDDIR%/xml
- if errorlevel 1 exit /b 1
- echo.
- echo.Build finished. The XML files are in %BUILDDIR%/xml.
- goto end
-)
-
-if "%1" == "pseudoxml" (
- %SPHINXBUILD% -b pseudoxml %ALLSPHINXOPTS% %BUILDDIR%/pseudoxml
- if errorlevel 1 exit /b 1
- echo.
- echo.Build finished. The pseudo-XML files are in %BUILDDIR%/pseudoxml.
- goto end
-)
-
-:end
+@ECHO OFF
+
+pushd %~dp0
+
+REM Command file for Sphinx documentation
+
+if "%SPHINXBUILD%" == "" (
+ set SPHINXBUILD=sphinx-build
+)
+set SOURCEDIR=.
+set BUILDDIR=_build
+set SPHINXPROJ=SortedContainers
+
+if "%1" == "" goto help
+
+%SPHINXBUILD% >NUL 2>NUL
+if errorlevel 9009 (
+ echo.
+ echo.The 'sphinx-build' command was not found. Make sure you have Sphinx
+ echo.installed, then set the SPHINXBUILD environment variable to point
+ echo.to the full path of the 'sphinx-build' executable. Alternatively you
+ echo.may add the Sphinx directory to PATH.
+ echo.
+ echo.If you don't have Sphinx installed, grab it from
+ echo.http://sphinx-doc.org/
+ exit /b 1
+)
+
+%SPHINXBUILD% -M %1 %SOURCEDIR% %BUILDDIR% %SPHINXOPTS%
+goto end
+
+:help
+%SPHINXBUILD% -M help %SOURCEDIR% %BUILDDIR% %SPHINXOPTS%
+
+:end
+popd
diff -Nru sortedcontainers-1.5.9/docs/Makefile sortedcontainers-2.0.4/docs/Makefile
--- sortedcontainers-1.5.9/docs/Makefile 2017-12-08 21:13:29.000000000 +0000
+++ sortedcontainers-2.0.4/docs/Makefile 2018-06-07 05:34:49.000000000 +0000
@@ -1,177 +1,20 @@
-# Makefile for Sphinx documentation
+# Minimal makefile for Sphinx documentation
#
# You can set these variables from the command line.
SPHINXOPTS =
SPHINXBUILD = sphinx-build
-PAPER =
+SPHINXPROJ = SortedContainers
+SOURCEDIR = .
BUILDDIR = _build
-# User-friendly check for sphinx-build
-ifeq ($(shell which $(SPHINXBUILD) >/dev/null 2>&1; echo $$?), 1)
-$(error The '$(SPHINXBUILD)' command was not found. Make sure you have Sphinx installed, then set the SPHINXBUILD environment variable to point to the full path of the '$(SPHINXBUILD)' executable. Alternatively you can add the directory with the executable to your PATH. If you don't have Sphinx installed, grab it from http://sphinx-doc.org/)
-endif
-
-# Internal variables.
-PAPEROPT_a4 = -D latex_paper_size=a4
-PAPEROPT_letter = -D latex_paper_size=letter
-ALLSPHINXOPTS = -d $(BUILDDIR)/doctrees $(PAPEROPT_$(PAPER)) $(SPHINXOPTS) .
-# the i18n builder cannot share the environment and doctrees with the others
-I18NSPHINXOPTS = $(PAPEROPT_$(PAPER)) $(SPHINXOPTS) .
-
-.PHONY: help clean html dirhtml singlehtml pickle json htmlhelp qthelp devhelp epub latex latexpdf text man changes linkcheck doctest gettext
-
+# Put it first so that "make" without argument is like "make help".
help:
- @echo "Please use \`make ' where is one of"
- @echo " html to make standalone HTML files"
- @echo " dirhtml to make HTML files named index.html in directories"
- @echo " singlehtml to make a single large HTML file"
- @echo " pickle to make pickle files"
- @echo " json to make JSON files"
- @echo " htmlhelp to make HTML files and a HTML help project"
- @echo " qthelp to make HTML files and a qthelp project"
- @echo " devhelp to make HTML files and a Devhelp project"
- @echo " epub to make an epub"
- @echo " latex to make LaTeX files, you can set PAPER=a4 or PAPER=letter"
- @echo " latexpdf to make LaTeX files and run them through pdflatex"
- @echo " latexpdfja to make LaTeX files and run them through platex/dvipdfmx"
- @echo " text to make text files"
- @echo " man to make manual pages"
- @echo " texinfo to make Texinfo files"
- @echo " info to make Texinfo files and run them through makeinfo"
- @echo " gettext to make PO message catalogs"
- @echo " changes to make an overview of all changed/added/deprecated items"
- @echo " xml to make Docutils-native XML files"
- @echo " pseudoxml to make pseudoxml-XML files for display purposes"
- @echo " linkcheck to check all external links for integrity"
- @echo " doctest to run all doctests embedded in the documentation (if enabled)"
-
-clean:
- rm -rf $(BUILDDIR)/*
-
-html:
- $(SPHINXBUILD) -b html $(ALLSPHINXOPTS) $(BUILDDIR)/html
- @echo
- @echo "Build finished. The HTML pages are in $(BUILDDIR)/html."
-
-dirhtml:
- $(SPHINXBUILD) -b dirhtml $(ALLSPHINXOPTS) $(BUILDDIR)/dirhtml
- @echo
- @echo "Build finished. The HTML pages are in $(BUILDDIR)/dirhtml."
-
-singlehtml:
- $(SPHINXBUILD) -b singlehtml $(ALLSPHINXOPTS) $(BUILDDIR)/singlehtml
- @echo
- @echo "Build finished. The HTML page is in $(BUILDDIR)/singlehtml."
-
-pickle:
- $(SPHINXBUILD) -b pickle $(ALLSPHINXOPTS) $(BUILDDIR)/pickle
- @echo
- @echo "Build finished; now you can process the pickle files."
-
-json:
- $(SPHINXBUILD) -b json $(ALLSPHINXOPTS) $(BUILDDIR)/json
- @echo
- @echo "Build finished; now you can process the JSON files."
-
-htmlhelp:
- $(SPHINXBUILD) -b htmlhelp $(ALLSPHINXOPTS) $(BUILDDIR)/htmlhelp
- @echo
- @echo "Build finished; now you can run HTML Help Workshop with the" \
- ".hhp project file in $(BUILDDIR)/htmlhelp."
-
-qthelp:
- $(SPHINXBUILD) -b qthelp $(ALLSPHINXOPTS) $(BUILDDIR)/qthelp
- @echo
- @echo "Build finished; now you can run "qcollectiongenerator" with the" \
- ".qhcp project file in $(BUILDDIR)/qthelp, like this:"
- @echo "# qcollectiongenerator $(BUILDDIR)/qthelp/sortedcontainers.qhcp"
- @echo "To view the help file:"
- @echo "# assistant -collectionFile $(BUILDDIR)/qthelp/sortedcontainers.qhc"
-
-devhelp:
- $(SPHINXBUILD) -b devhelp $(ALLSPHINXOPTS) $(BUILDDIR)/devhelp
- @echo
- @echo "Build finished."
- @echo "To view the help file:"
- @echo "# mkdir -p $$HOME/.local/share/devhelp/sortedcontainers"
- @echo "# ln -s $(BUILDDIR)/devhelp $$HOME/.local/share/devhelp/sortedcontainers"
- @echo "# devhelp"
-
-epub:
- $(SPHINXBUILD) -b epub $(ALLSPHINXOPTS) $(BUILDDIR)/epub
- @echo
- @echo "Build finished. The epub file is in $(BUILDDIR)/epub."
-
-latex:
- $(SPHINXBUILD) -b latex $(ALLSPHINXOPTS) $(BUILDDIR)/latex
- @echo
- @echo "Build finished; the LaTeX files are in $(BUILDDIR)/latex."
- @echo "Run \`make' in that directory to run these through (pdf)latex" \
- "(use \`make latexpdf' here to do that automatically)."
-
-latexpdf:
- $(SPHINXBUILD) -b latex $(ALLSPHINXOPTS) $(BUILDDIR)/latex
- @echo "Running LaTeX files through pdflatex..."
- $(MAKE) -C $(BUILDDIR)/latex all-pdf
- @echo "pdflatex finished; the PDF files are in $(BUILDDIR)/latex."
-
-latexpdfja:
- $(SPHINXBUILD) -b latex $(ALLSPHINXOPTS) $(BUILDDIR)/latex
- @echo "Running LaTeX files through platex and dvipdfmx..."
- $(MAKE) -C $(BUILDDIR)/latex all-pdf-ja
- @echo "pdflatex finished; the PDF files are in $(BUILDDIR)/latex."
-
-text:
- $(SPHINXBUILD) -b text $(ALLSPHINXOPTS) $(BUILDDIR)/text
- @echo
- @echo "Build finished. The text files are in $(BUILDDIR)/text."
-
-man:
- $(SPHINXBUILD) -b man $(ALLSPHINXOPTS) $(BUILDDIR)/man
- @echo
- @echo "Build finished. The manual pages are in $(BUILDDIR)/man."
-
-texinfo:
- $(SPHINXBUILD) -b texinfo $(ALLSPHINXOPTS) $(BUILDDIR)/texinfo
- @echo
- @echo "Build finished. The Texinfo files are in $(BUILDDIR)/texinfo."
- @echo "Run \`make' in that directory to run these through makeinfo" \
- "(use \`make info' here to do that automatically)."
-
-info:
- $(SPHINXBUILD) -b texinfo $(ALLSPHINXOPTS) $(BUILDDIR)/texinfo
- @echo "Running Texinfo files through makeinfo..."
- make -C $(BUILDDIR)/texinfo info
- @echo "makeinfo finished; the Info files are in $(BUILDDIR)/texinfo."
-
-gettext:
- $(SPHINXBUILD) -b gettext $(I18NSPHINXOPTS) $(BUILDDIR)/locale
- @echo
- @echo "Build finished. The message catalogs are in $(BUILDDIR)/locale."
-
-changes:
- $(SPHINXBUILD) -b changes $(ALLSPHINXOPTS) $(BUILDDIR)/changes
- @echo
- @echo "The overview file is in $(BUILDDIR)/changes."
-
-linkcheck:
- $(SPHINXBUILD) -b linkcheck $(ALLSPHINXOPTS) $(BUILDDIR)/linkcheck
- @echo
- @echo "Link check complete; look for any errors in the above output " \
- "or in $(BUILDDIR)/linkcheck/output.txt."
-
-doctest:
- $(SPHINXBUILD) -b doctest $(ALLSPHINXOPTS) $(BUILDDIR)/doctest
- @echo "Testing of doctests in the sources finished, look at the " \
- "results in $(BUILDDIR)/doctest/output.txt."
+ @$(SPHINXBUILD) -M help "$(SOURCEDIR)" "$(BUILDDIR)" $(SPHINXOPTS) $(O)
-xml:
- $(SPHINXBUILD) -b xml $(ALLSPHINXOPTS) $(BUILDDIR)/xml
- @echo
- @echo "Build finished. The XML files are in $(BUILDDIR)/xml."
+.PHONY: help Makefile
-pseudoxml:
- $(SPHINXBUILD) -b pseudoxml $(ALLSPHINXOPTS) $(BUILDDIR)/pseudoxml
- @echo
- @echo "Build finished. The pseudo-XML files are in $(BUILDDIR)/pseudoxml."
+# Catch-all target: route all unknown targets to Sphinx using the new
+# "make mode" option. $(O) is meant as a shortcut for $(SPHINXOPTS).
+%: Makefile
+ @$(SPHINXBUILD) -M $@ "$(SOURCEDIR)" "$(BUILDDIR)" $(SPHINXOPTS) $(O)
\ No newline at end of file
diff -Nru sortedcontainers-1.5.9/docs/performance-load.rst sortedcontainers-2.0.4/docs/performance-load.rst
--- sortedcontainers-1.5.9/docs/performance-load.rst 2017-12-08 21:13:29.000000000 +0000
+++ sortedcontainers-2.0.4/docs/performance-load.rst 2018-06-07 05:34:49.000000000 +0000
@@ -1,26 +1,26 @@
Load Factor Performance Comparison
==================================
-:doc:`SortedContainers` uses a segmented-list data structure similar to
+:doc:`Sorted Containers` uses a segmented-list data structure similar to
a B-tree limited to two levels of nodes. As part of the implementation, a load
factor is used to determine how many values should be stored in each node. This
page compares three load factors on containers with as many as ten of million
elements.
No single load factor is universally superior. The best load factor for your
-purposes will depend on your usage pattern. Originally,
-:doc:`SortedContainers` used a load factor of 100 but that changed in
-release 0.8.5 mainly due to the SortedList.delitem_ benchmark which is most
-dramatically impacted. Most benchmarks perform slightly better with a load
-factor of 100 but each is competitive with alternate loads. For an in-depth
-analysis of the load factor read :doc:`Performance at
+purposes will depend on your usage pattern. Originally, :doc:`Sorted
+Containers` used a load factor of 100 but that changed in release 0.8.5
+to 1,000 due to the :ref:`SortedList.__delitem__` benchmark
+which was dramatically impacted. Most benchmarks perform slightly better with a
+load factor of 100 but each is competitive with alternate loads. For an
+in-depth analysis of the load factor read :doc:`Performance at
Scale`.
Performance of competing implementations are benchmarked against the CPython
-2.7 runtime. An :doc:`implementation performance comparison` is
+3.6 runtime. An :doc:`implementation performance comparison` is
also included with data from popular sorted collections packages.
-Because :doc:`SortedContainers` is pure-Python, its performance also
+Because :doc:`Sorted Containers` is pure-Python, its performance also
depends directly on the Python runtime. A :doc:`runtime performance
comparison` is also included with data from popular Python
runtimes.
@@ -30,37 +30,38 @@
performance comparison` contains examples with
comparisons to other implementations, load factors, and runtimes.
-SortedList
-----------
+.. currentmodule:: sortedcontainers
+
+Sorted List
+-----------
-Graphs comparing :doc:`SortedList` performance.
+Graphs comparing :doc:`sortedlist` performance.
__init__
........
-Initializing with a list of random numbers.
+Initializing with a list of random numbers using :func:`SortedList.__init__`.
.. image:: _static/SortedList_load-init.png
add
...
-Randomly adding values using :ref:`SortedList.add`.
+Randomly adding values using :func:`SortedList.add`.
.. image:: _static/SortedList_load-add.png
contains
........
-Randomly testing membership using
-:ref:`SortedList.__contains__`.
+Randomly testing membership using :func:`SortedList.__contains__`.
.. image:: _static/SortedList_load-contains.png
count
.....
-Counting objects at random using :ref:`SortedList.count`.
+Counting objects at random using :func:`SortedList.count`.
.. image:: _static/SortedList_load-count.png
@@ -69,72 +70,69 @@
.. _SortedList.delitem:
-Deleting objects at random using
-:ref:`SortedList.__delitem__`.
+Deleting objects at random using :func:`SortedList.__delitem__`.
.. image:: _static/SortedList_load-delitem.png
__getitem__
...........
-Retrieving ojbects by index using
-:ref:`SortedList.__getitem__`.
+Retrieving ojbects by index using :func:`SortedList.__getitem__`.
.. image:: _static/SortedList_load-getitem.png
index
.....
-Finding the index of an object using :ref:`SortedList.index`.
+Finding the index of an object using :func:`SortedList.index`.
.. image:: _static/SortedList_load-index.png
iter
....
-Iterating a SortedList using :ref:`SortedList.__iter__`.
+Iterating a SortedList using :func:`SortedList.__iter__`.
.. image:: _static/SortedList_load-iter.png
pop
...
-Removing the last object using :ref:`SortedList.pop`.
+Removing the last object using :func:`SortedList.pop`.
.. image:: _static/SortedList_load-pop.png
remove
......
-Remove an object at random using :ref:`SortedList.remove`.
+Remove an object at random using :func:`SortedList.remove`.
.. image:: _static/SortedList_load-remove.png
update_large
............
-Updating a SortedList with a large iterable using
-:ref:`SortedList.update`.
+Updating a SortedList with a large iterable using :func:`SortedList.update`.
.. image:: _static/SortedList_load-update_large.png
update_small
............
-Updating a SortedList with a small iterable using
-:ref:`SortedList.update`.
+Updating a SortedList with a small iterable using :func:`SortedList.update`.
.. image:: _static/SortedList_load-update_small.png
-SortedDict
-----------
+Sorted Dict
+-----------
-Graphs comparing :doc:`SortedDict` performance.
+Graphs comparing :doc:`sorteddict` performance.
__init__
........
-Initializing with a list of pairs of random numbers.
+Initializing with a list of pairs of random numbers using
+:func:`SortedDict.__init__`.
.. image:: _static/SortedDict_load-init.png
@@ -142,39 +140,35 @@
............
Given a key at random, test whether the key is in the dictionary using
-:ref:`SortedDict.__contains__`.
+:func:`SortedDict.__contains__`.
.. image:: _static/SortedDict_load-contains.png
__getitem__
...........
-Given a key at random, retrieve the value using
-:ref:`SortedDict.__getitem__`.
+Given a key at random, retrieve the value using :func:`SortedDict.__getitem__`.
.. image:: _static/SortedDict_load-getitem.png
__setitem__
...........
-Given a key at random, set the value using
-:ref:`SortedDict.__setitem__`.
+Given a key at random, set the value using :func:`SortedDict.__setitem__`.
.. image:: _static/SortedDict_load-setitem.png
__delitem__
...........
-Given a key at random, delete the value using
-:ref:`SortedDict.__delitem__`.
+Given a key at random, delete the value using :func:`SortedDict.__delitem__`.
.. image:: _static/SortedDict_load-delitem.png
iter
....
-Iterate the keys of a SortedDict using
-:ref:`SortedDict.__iter__`.
+Iterate the keys of a SortedDict using :func:`SortedDict.__iter__`.
.. image:: _static/SortedDict_load-iter.png
@@ -182,294 +176,277 @@
................
Given an existing key at random, set the value using
-:ref:`SortedDict.__setitem__`.
+:func:`SortedDict.__setitem__`.
.. image:: _static/SortedDict_load-setitem_existing.png
-SortedSet
----------
+Sorted Set
+----------
-Graphs comparing :doc:`SortedSet` performance.
+Graphs comparing :doc:`sortedset` performance.
__init__
........
-Initializing with a list of random numbers.
+Initializing with a list of random numbers using :func:`SortedSet.__init__`.
.. image:: _static/SortedSet_load-init.png
add
...
-Randomly add values using :ref:`SortedSet.add`.
+Randomly add values using :func:`SortedSet.add`.
.. image:: _static/SortedSet_load-add.png
contains
........
-Randomly test membership using
-:ref:`SortedSet.__contains__`.
+Randomly test membership using :func:`SortedSet.__contains__`.
.. image:: _static/SortedSet_load-contains.png
difference_large
................
-Set difference using :ref:`SortedSet.difference`.
+Set difference using :func:`SortedSet.difference`.
.. image:: _static/SortedSet_load-difference_large.png
difference_medium
.................
-Set difference using :ref:`SortedSet.difference`.
+Set difference using :func:`SortedSet.difference`.
.. image:: _static/SortedSet_load-difference_medium.png
difference_small
................
-Set difference using :ref:`SortedSet.difference`.
+Set difference using :func:`SortedSet.difference`.
.. image:: _static/SortedSet_load-difference_small.png
difference_tiny
...............
-Set difference using :ref:`SortedSet.difference`.
+Set difference using :func:`SortedSet.difference`.
.. image:: _static/SortedSet_load-difference_tiny.png
difference_update_large
.......................
-Set difference using
-:ref:`SortedSet.difference_update`.
+Set difference using :func:`SortedSet.difference_update`.
.. image:: _static/SortedSet_load-difference_update_large.png
difference_update_medium
........................
-Set difference using
-:ref:`SortedSet.difference_update`.
+Set difference using :func:`SortedSet.difference_update`.
.. image:: _static/SortedSet_load-difference_update_medium.png
difference_update_small
.......................
-Set difference using
-:ref:`SortedSet.difference_update`.
+Set difference using :func:`SortedSet.difference_update`.
.. image:: _static/SortedSet_load-difference_update_small.png
difference_update_tiny
......................
-Set difference using
-:ref:`SortedSet.difference_update`.
+Set difference using :func:`SortedSet.difference_update`.
.. image:: _static/SortedSet_load-difference_update_tiny.png
intersection_large
..................
-Set intersection using :ref:`SortedSet.intersection`.
+Set intersection using :func:`SortedSet.intersection`.
.. image:: _static/SortedSet_load-intersection_large.png
intersection_medium
...................
-Set intersection using :ref:`SortedSet.intersection`.
+Set intersection using :func:`SortedSet.intersection`.
.. image:: _static/SortedSet_load-intersection_medium.png
intersection_small
..................
-Set intersection using :ref:`SortedSet.intersection`.
+Set intersection using :func:`SortedSet.intersection`.
.. image:: _static/SortedSet_load-intersection_small.png
intersection_tiny
.................
-Set intersection using :ref:`SortedSet.intersection`.
+Set intersection using :func:`SortedSet.intersection`.
.. image:: _static/SortedSet_load-intersection_tiny.png
intersection_update_large
.........................
-Set intersection using
-:ref:`SortedSet.intersection_update`.
+Set intersection using :func:`SortedSet.intersection_update`.
.. image:: _static/SortedSet_load-intersection_update_large.png
intersection_update_medium
..........................
-Set intersection using
-:ref:`SortedSet.intersection_update`.
+Set intersection using :func:`SortedSet.intersection_update`.
.. image:: _static/SortedSet_load-intersection_update_medium.png
intersection_update_small
.........................
-Set intersection using
-:ref:`SortedSet.intersection_update`.
+Set intersection using :func:`SortedSet.intersection_update`.
.. image:: _static/SortedSet_load-intersection_update_small.png
intersection_update_tiny
........................
-Set intersection using
-:ref:`SortedSet.intersection_update`.
+Set intersection using :func:`SortedSet.intersection_update`.
.. image:: _static/SortedSet_load-intersection_update_tiny.png
iter
....
-Iterating a set using :ref:`iter(SortedSet)`.
+Iterating a set using :func:`iter(SortedSet)`.
.. image:: _static/SortedSet_load-iter.png
pop
...
-Remove the last item in a set using :ref:`SortedSet.pop`.
+Remove the last item in a set using :func:`SortedSet.pop`.
.. image:: _static/SortedSet_load-pop.png
remove
......
-Remove an item at random using :ref:`SortedSet.remove`.
+Remove an item at random using :func:`SortedSet.remove`.
.. image:: _static/SortedSet_load-remove.png
union_large
...........
-Set union using :ref:`SortedSet.union`.
+Set union using :func:`SortedSet.union`.
.. image:: _static/SortedSet_load-union_large.png
union_medium
............
-Set union using :ref:`SortedSet.union`.
+Set union using :func:`SortedSet.union`.
.. image:: _static/SortedSet_load-union_medium.png
union_small
...........
-Set union using :ref:`SortedSet.union`.
+Set union using :func:`SortedSet.union`.
.. image:: _static/SortedSet_load-union_small.png
union_tiny
..........
-Set union using :ref:`SortedSet.union`.
+Set union using :func:`SortedSet.union`.
.. image:: _static/SortedSet_load-union_tiny.png
update_large
............
-Set update using :ref:`SortedSet.update`.
+Set update using :func:`SortedSet.update`.
.. image:: _static/SortedSet_load-update_large.png
update_medium
.............
-Set update using :ref:`SortedSet.update`.
+Set update using :func:`SortedSet.update`.
.. image:: _static/SortedSet_load-update_medium.png
update_small
............
-Set update using :ref:`SortedSet.update`.
+Set update using :func:`SortedSet.update`.
.. image:: _static/SortedSet_load-update_small.png
update_tiny
...........
-Set update using :ref:`SortedSet.update`.
+Set update using :func:`SortedSet.update`.
.. image:: _static/SortedSet_load-update_tiny.png
symmetric_difference_large
..........................
-Set symmetric-difference using
-:ref:`SortedSet.symmetric_difference`.
+Set symmetric-difference using :func:`SortedSet.symmetric_difference`.
.. image:: _static/SortedSet_load-symmetric_difference_large.png
symmetric_difference_medium
...........................
-Set symmetric-difference using
-:ref:`SortedSet.symmetric_difference`.
+Set symmetric-difference using :func:`SortedSet.symmetric_difference`.
.. image:: _static/SortedSet_load-symmetric_difference_medium.png
symmetric_difference_small
..........................
-Set symmetric-difference using
-:ref:`SortedSet.symmetric_difference`.
+Set symmetric-difference using :func:`SortedSet.symmetric_difference`.
.. image:: _static/SortedSet_load-symmetric_difference_small.png
symmetric_difference_tiny
.........................
-Set symmetric-difference using
-:ref:`SortedSet.symmetric_difference`.
+Set symmetric-difference using :func:`SortedSet.symmetric_difference`.
.. image:: _static/SortedSet_load-symmetric_difference_tiny.png
symm_diff_update_large
......................
-Set symmetric-difference using
-:ref:`SortedSet.symmetric_difference_update`.
+Set symmetric-difference using :func:`SortedSet.symmetric_difference_update`.
.. image:: _static/SortedSet_load-symmetric_difference_update_large.png
symm_diff_update_medium
.......................
-Set symmetric-difference using
-:ref:`SortedSet.symmetric_difference_update`.
+Set symmetric-difference using :func:`SortedSet.symmetric_difference_update`.
.. image:: _static/SortedSet_load-symmetric_difference_update_medium.png
symm_diff_update_small
......................
-Set symmetric-difference using
-:ref:`SortedSet.symmetric_difference_update`.
+Set symmetric-difference using :func:`SortedSet.symmetric_difference_update`.
.. image:: _static/SortedSet_load-symmetric_difference_update_small.png
symm_diff_update_tiny
.....................
-Set symmetric-difference using
-:ref:`SortedSet.symmetric_difference_update`.
+Set symmetric-difference using :func:`SortedSet.symmetric_difference_update`.
.. image:: _static/SortedSet_load-symmetric_difference_update_tiny.png
diff -Nru sortedcontainers-1.5.9/docs/performance.rst sortedcontainers-2.0.4/docs/performance.rst
--- sortedcontainers-1.5.9/docs/performance.rst 2017-12-08 21:13:29.000000000 +0000
+++ sortedcontainers-2.0.4/docs/performance.rst 2018-06-07 05:34:49.000000000 +0000
@@ -4,106 +4,115 @@
Measuring performance is a difficult task. All the benchmarks on this page are
synthetic in the sense that they test one function repeatedly. Measurements in
live systems are much harder to produce reliably. So take the following data
-with a grain of salt. That being said, a stated feature of
-:doc:`SortedContainers` is performance so we would be remiss not to
-produce this page with comparisons.
+with a grain of salt. That being said, a stated feature of :doc:`Sorted
+Containers` is performance so we would be remiss not to produce this
+page with comparisons.
The source for all benchmarks can be found under the "tests" directory in the
-files prefixed "benchmark." Measurements are made from the min, max, and mean
-of 5 repetitions. In the graphs below, the line follows the mean and at each
-point, the min/max displays the bounds. Note that the axes are log-log so
-properly reading two different lines would describe one metric as "X times"
-faster rather than "X seconds" faster. In all graphs, lower is
-better. Measurements are made by powers of ten: 100 through 1,000,000.
-
-Measurements up to 10,000,000,000 elements have been successfully tested and
-benchmarks. Read :doc:`Performance at Scale` for
-details. Only a couple implementations (including SortedContainers) are capable
-of handling so many elements. The major limiting factor at that size is
+files prefixed "benchmark." Measurements are made from the min, max, and median
+of 5 repetitions. In the graphs below, the line follows the median at each
+point. Note that the axes are log-log so properly reading two different lines
+would describe one metric as "X times" faster rather than "X seconds"
+faster. In all graphs, lower is better. Measurements are made by powers of ten:
+100 through 10,000,000.
+
+Measurements up to ten billion elements have been successfully tested and
+benchmarked. Read :doc:`performance-scale` for details. Only a couple
+implementations (including :doc:`Sorted Containers`) are capable of
+handling so many elements. The major limiting factor at that size is
memory. Consider the simple case of storing CPython's integers in a
-SortedList. Each integer object requires ~24 bytes so one hundred million
-elements will require about three gigabytes of memory. If the implemenation
-adds significant overhead then most systems will run out of memory. For all
-datasets which may be kept in memory, :doc:`SortedContainers` is an
-excellent choice.
+:doc:`sortedlist`. Each integer object requires ~24 bytes so one hundred
+million elements will require about three gigabytes of memory. If the
+implementation adds significant overhead then most systems will run out of
+memory. For all datasets which may be kept in memory, :doc:`Sorted
+Containers` is an excellent choice.
-A good effort has been made to find competing implementations. Six in total
+A good effort has been made to find competing implementations. Seven in total
were found with various list, set, and dict implementations.
-rbtree
- Provides a fast, C-implementation for dict and set data types.
- `rbtree on PyPI `_
-
-blist
- Provides list, dict, and set containers based on the blist data-type.
- Implemented in Python and C.
- `blist on PyPI `_
-
-treap
- Uses Cython for improved performance and provides a dict container.
- `treap on PyPI `_
-
-bintrees
- Provides several tree-based implementations for dict and set containers.
- Fastest were AVL and Red-Black trees. Extends the conventional API to
- provide set operations for the dict type. Implemented in C.
- `bintrees on PyPI `_
-
-banyan
- Provides a fast, C-implementation for dict and set data types. Offers some
- features also found in sortedcontainers like accessing the n-th item in a
- set or dict.
- `banyan on PyPI `_
-
-skiplistcollections
- Pure-Python implementation based on skip-lists providing a limited API
- for dict and set types.
- `skiplistcollections on PyPI `_
-
-sortedcollection
- Pure-Python implementation of sorted list based solely on a list.
- Feature-poor and inefficient for writes but included because it is written
- by Raymond Hettinger and linked from the official Python docs.
- `sortedcollection on ActiveState `_
-
-Several competing implementations were omitted because they were not easily
-installable or failed to build.
-
-ruamel.ordereddict.sorteddict
- C-implementation that only supports Python 2. Performance was measured in
- correspondence with the module author. Performance was generally very good
- except for ``__delitem__``. At scale, deleting entries became exceedingly
- slow.
- `ruamel.ordereddict on PyPI `_
-
-rbtree from NewCenturyComputers
- Pure-Python tree-based implementation. Not sure when this was last updated.
- Unlikely to be fast.
- `rbtree from NewCenturyComputers `_
-
-python-avl-tree from Github user pgrafov
- Pure-Python tree-based implementation. Last updated in 2010. Unlikely
- to be fast.
- `python-avl-tree from Github user pgrafov `_
-
-pyavl
- C-implementation for AVL tree-based dict and set containers. Claims to be
- fast. Lacking documentation and failed to build.
- `pyavl on PyPI `_
+1. *blist* -- Provides list, dict, and set containers based on the blist
+ data-type. Uses a `B-Tree`_ data structure. Implemented in Python and C. BSD
+ License. Last updated March, 2014. `blist on PyPI`_
+
+2. *bintrees* -- Provides several tree-based implementations for dict and set
+ containers. Fastest were AVL-Tree and Red-Black-Tree data
+ structures.. Extends the conventional API to provide set operations for the
+ dict type. Now deprecated in favor of :doc:`Sorted Containers`
+ Implemented in C. MIT License. Last updated April, 2017. `bintrees on
+ PyPI`_
+
+3. *sortedmap* -- Provides a fast, C++ implemenation for dict data types. Uses
+ the C++ standard library `std::map` data structure which is usually a
+ red-black tree. Last updated February, 2016. `sortedmap on PyPI`_
+
+4. *banyan* -- Provides a fast, C++ implementation for dict and set data
+ types. Offers some features also found in sortedcontainers like accessing
+ the n-th item in a set or dict. Uses sources from the `tree implementation`_
+ in GNU libstdc++. GPLv3 License. Last updated April, 2013. `banyan on PyPI`_
+
+5. *treap* -- Uses Cython for improved performance and provides a dict
+ container. Apache V2 License. Last updated June, 2017. `treap on PyPI`_
+
+6. *skiplistcollections* -- Pure-Python implementation based on skip-lists
+ providing a limited API for dict and set types. MIT License. Last updated
+ January, 2014. `skiplistcollections on PyPI`_
+
+7. *sortedcollection* -- Pure-Python implementation of sorted list based solely
+ on a list. Feature-poor and inefficient for writes but included because it
+ is written by Raymond Hettinger and linked from the official Python
+ docs. MIT License. Last updated April, 2011. `sortedcollection recipe`_
+
+Several alternative implementations were omitted for reasons documented below:
+
+A. *rbtree* -- C-implementation that only supports Python 2. Provides a fast,
+ C-implementation for dict and set data types. GPLv3 License. Last updated
+ March, 2012. `rbtree on PyPI`_
+
+B. *ruamel.ordereddict.sorteddict* -- C-implementation that only supports
+ Python 2. Performance was measured in correspondence with the module
+ author. Performance was generally very good except for ``__delitem__``. At
+ scale, deleting entries became exceedingly slow. MIT License. Last updated
+ July, 2017. `ruamel.ordereddict on PyPI`_
+
+C. *pyskiplist* -- Pure-Python skip-list based implementation supporting a
+ sorted-list-like interface. Now deprecated in favor of :doc:`Sorted
+ Containers`. MIT License. Last updated July, 2015. `pyskiplist on
+ PyPI`_
+
+D. *sorteddict* -- Pure-Python lazily-computed sorted dict implementation. Now
+ deprecated in favor of :doc:`Sorted Containers`. GPLv3 License. Last
+ updated September, 2007. `sorteddict on PyPI`_
+
+E. *rbtree from NewCenturyComputers* -- Pure-Python tree-based
+ implementation. Not sure when this was last updated. Unlikely to be
+ fast. Unknown license. Unknown last update. `rbtree from
+ NewCenturyComputers`_
+
+F. *python-avl-tree from GitHub user pgrafov* -- Pure-Python tree-based
+ implementation. Unlikely to be fast. MIT License. Last updated
+ October, 2010. `python-avl-tree from GitHub user pgrafov`_
+
+G. *pyavl* -- C-implementation for AVL tree-based dict and set
+ containers. Claims to be fast. Lacking documentation and failed to
+ build. Public Domain License. Last updated December, 2008. `pyavl on PyPI`_
+
+H. *skiplist* -- C-implementation of sorted list based on skip-list data
+ structure. Only supports Python 2. Zlib/libpng License. Last updated
+ Septemeber, 2013. `skiplist from Bitbucket user mojaves`_
-The most similar module to :doc:`SortedContainers` is
+The most similar module to :doc:`Sorted Containers` is
skiplistcollections given that each is implemented in Python. But as is
-displayed below, :doc:`SortedContainers` is several times faster and
-provides a richer API. Often the pure-Python implementation in SortedContainers
-is faster even than the C-implementation counterparts. Where it lacks,
-performance is generally on the same magnitude.
+displayed below, Sorted Containers is several times faster and provides a
+richer API. Often the pure-Python implementation in Sorted Containers is faster
+even than the C-implementation counterparts. Where it lacks, performance is
+generally on the same magnitude.
-Because :doc:`SortedContainers` is implemented in pure-Python, its
+Because :doc:`Sorted Containers` is implemented in pure-Python, its
performance depends directly on the Python runtime. A :doc:`runtime performance
comparison` is also included with data from popular
runtimes.
-:doc:`SortedContainers` uses a segmented-list data structure similar to
+:doc:`Sorted Containers` uses a segmented-list data structure similar to
a B-tree limited to two levels of nodes. As part of the implementation, a load
factor is used to determine how many values should be stored in each node. This
can have a significant impact on performance and a :doc:`load factor
@@ -114,117 +123,150 @@
performance comparison` contains examples with
comparisons to other implementations, load factors, and runtimes.
-A couple final notes about the graphs below. Missing data indicates the
-benchmark either took too long or failed. The set operations with tiny, small,
-medium, and large variations indicate the size of the container involved in the
+Some final notes about the graphs below. Missing data indicates the benchmark
+either took too long or failed. The set operations with tiny, small, medium,
+and large variations indicate the size of the container involved in the
right-hand-side of the operation: tiny is exactly 10 elements; small is 10% of
-the size of the left-hand-side; medium is 50%; and large is 100%. The
-sortedcontainers module uses a different algorithm based on the size of the
+the size of the left-hand-side; medium is 50%; and large is 100%. :doc:`Sorted
+Containers` uses a different algorithm based on the size of the
right-hand-side of the operation for a dramatic improvement in performance.
-SortedList
-----------
+The legends of the graphs below correlate the underlying data structure used
+the Python project. The correlation is as follows:
+
+.. currentmodule:: sortedcontainers
+
+====================== ==================================
+Data Structure Project
+====================== ==================================
+:class:`SortedList` :doc:`Sorted Containers`
+:class:`SortedKeyList` :doc:`Sorted Containers`
+B-Tree `blist on PyPI`_
+List `sortedcollection recipe`_
+AVL-Tree `bintrees on PyPI`_
+RB-Tree `banyan on PyPI`_
+Skip-List `skiplistcollections on PyPI`_
+std::map `sortedmap on PyPI`_
+Treap `treap on PyPI`_
+====================== ==================================
+
+.. _`B-Tree`: https://en.wikipedia.org/wiki/B-tree
+.. _`blist on PyPI`: https://pypi.org/project/blist/
+.. _`bintrees on PyPI`: https://pypi.org/project/bintrees/
+.. _`sortedmap on PyPI`: https://pypi.org/project/sortedmap/
+.. _`sorteddict on PyPI`: https://pypi.org/project/sorteddict/
+.. _`pyskiplist on PyPI`: https://pypi.org/project/pyskiplist/
+.. _`banyan on PyPI`: https://pypi.org/project/Banyan/
+.. _`treap on PyPI`: https://pypi.org/project/treap/
+.. _`skiplistcollections on PyPI`: https://pypi.org/project/skiplistcollections/
+.. _`sortedcollection recipe`: http://code.activestate.com/recipes/577197-sortedcollection/
+.. _`rbtree on PyPI`: https://pypi.org/project/rbtree/
+.. _`ruamel.ordereddict on PyPI`: https://pypi.org/project/ruamel.ordereddict/
+.. _`rbtree from NewCenturyComputers`: http://newcenturycomputers.net/projects/rbtree.html
+.. _`python-avl-tree from GitHub user pgrafov`: https://github.com/pgrafov/python-avl-tree
+.. _`pyavl on PyPI`: https://pypi.org/project/pyavl/
+.. _`skiplist from Bitbucket user mojaves`: https://bitbucket.org/mojaves/pyskiplist/
+.. _`tree implementation`: https://gcc.gnu.org/onlinedocs/libstdc%2B%2B/ext/pb_ds/tree_based_containers.html
-Graphs comparing :doc:`SortedList` performance.
+Sorted List
+-----------
+
+Graphs comparing :doc:`sortedlist` performance.
__init__
........
-Initializing with a list of random numbers.
+Initializing with a list of random numbers using :func:`SortedList.__init__`.
.. image:: _static/SortedList-init.png
add
...
-Randomly adding values using :ref:`SortedList.add`.
+Randomly adding values using :func:`SortedList.add`.
.. image:: _static/SortedList-add.png
contains
........
-Randomly testing membership using
-:ref:`SortedList.__contains__`.
+Randomly testing membership using :func:`SortedList.__contains__`.
.. image:: _static/SortedList-contains.png
count
.....
-Counting objects at random using :ref:`SortedList.count`.
+Counting objects at random using :func:`SortedList.count`.
.. image:: _static/SortedList-count.png
__delitem__
...........
-Deleting objects at random using
-:ref:`SortedList.__delitem__`.
+Deleting objects at random using :func:`SortedList.__delitem__`.
.. image:: _static/SortedList-delitem.png
__getitem__
...........
-Retrieving ojbects by index using
-:ref:`SortedList.__getitem__`.
+Retrieving ojbects by index using :func:`SortedList.__getitem__`.
.. image:: _static/SortedList-getitem.png
index
.....
-Finding the index of an object using :ref:`SortedList.index`.
+Finding the index of an object using :func:`SortedList.index`.
.. image:: _static/SortedList-index.png
iter
....
-Iterating a SortedList using :ref:`SortedList.__iter__`.
+Iterating a SortedList using :func:`SortedList.__iter__`.
.. image:: _static/SortedList-iter.png
pop
...
-Removing the last object using :ref:`SortedList.pop`.
+Removing the last object using :func:`SortedList.pop`.
.. image:: _static/SortedList-pop.png
remove
......
-Remove an object at random using :ref:`SortedList.remove`.
+Remove an object at random using :func:`SortedList.remove`.
.. image:: _static/SortedList-remove.png
update_large
............
-Updating a SortedList with a large iterable using
-:ref:`SortedList.update`.
+Updating a SortedList with a large iterable using :func:`SortedList.update`.
.. image:: _static/SortedList-update_large.png
update_small
............
-Updating a SortedList with a small iterable using
-:ref:`SortedList.update`.
+Updating a SortedList with a small iterable using :func:`SortedList.update`.
.. image:: _static/SortedList-update_small.png
-SortedDict
-----------
+Sorted Dict
+-----------
-Graphs comparing :doc:`SortedDict` performance.
+Graphs comparing :doc:`sorteddict` performance.
__init__
........
-Initializing with a list of pairs of random numbers.
+Initializing with a list of pairs of random numbers using
+:func:`SortedDict.__init__`.
.. image:: _static/SortedDict-init.png
@@ -232,39 +274,35 @@
............
Given a key at random, test whether the key is in the dictionary using
-:ref:`SortedDict.__contains__`.
+:func:`SortedDict.__contains__`.
.. image:: _static/SortedDict-contains.png
__getitem__
...........
-Given a key at random, retrieve the value using
-:ref:`SortedDict.__getitem__`.
+Given a key at random, retrieve the value using :func:`SortedDict.__getitem__`.
.. image:: _static/SortedDict-getitem.png
__setitem__
...........
-Given a key at random, set the value using
-:ref:`SortedDict.__setitem__`.
+Given a key at random, set the value using :func:`SortedDict.__setitem__`.
.. image:: _static/SortedDict-setitem.png
__delitem__
...........
-Given a key at random, delete the value using
-:ref:`SortedDict.__delitem__`.
+Given a key at random, delete the value using :func:`SortedDict.__delitem__`.
.. image:: _static/SortedDict-delitem.png
iter
....
-Iterate the keys of a SortedDict using
-:ref:`SortedDict.__iter__`.
+Iterate the keys of a SortedDict using :func:`SortedDict.__iter__`.
.. image:: _static/SortedDict-iter.png
@@ -272,294 +310,277 @@
................
Given an existing key at random, set the value using
-:ref:`SortedDict.__setitem__`.
+:func:`SortedDict.__setitem__`.
.. image:: _static/SortedDict-setitem_existing.png
-SortedSet
----------
+Sorted Set
+----------
-Graphs comparing :doc:`SortedSet` performance.
+Graphs comparing :doc:`sortedset` performance.
__init__
........
-Initializing with a list of random numbers.
+Initializing with a list of random numbers using :func:`SortedSet.__init__`.
.. image:: _static/SortedSet-init.png
add
...
-Randomly add values using :ref:`SortedSet.add`.
+Randomly add values using :func:`SortedSet.add`.
.. image:: _static/SortedSet-add.png
contains
........
-Randomly test membership using
-:ref:`SortedSet.__contains__`.
+Randomly test membership using :func:`SortedSet.__contains__`.
.. image:: _static/SortedSet-contains.png
difference_large
................
-Set difference using :ref:`SortedSet.difference`.
+Set difference using :func:`SortedSet.difference`.
.. image:: _static/SortedSet-difference_large.png
difference_medium
.................
-Set difference using :ref:`SortedSet.difference`.
+Set difference using :func:`SortedSet.difference`.
.. image:: _static/SortedSet-difference_medium.png
difference_small
................
-Set difference using :ref:`SortedSet.difference`.
+Set difference using :func:`SortedSet.difference`.
.. image:: _static/SortedSet-difference_small.png
difference_tiny
...............
-Set difference using :ref:`SortedSet.difference`.
+Set difference using :func:`SortedSet.difference`.
.. image:: _static/SortedSet-difference_tiny.png
difference_update_large
.......................
-Set difference using
-:ref:`SortedSet.difference_update`.
+Set difference using :func:`SortedSet.difference_update`.
.. image:: _static/SortedSet-difference_update_large.png
difference_update_medium
........................
-Set difference using
-:ref:`SortedSet.difference_update`.
+Set difference using :func:`SortedSet.difference_update`.
.. image:: _static/SortedSet-difference_update_medium.png
difference_update_small
.......................
-Set difference using
-:ref:`SortedSet.difference_update`.
+Set difference using :func:`SortedSet.difference_update`.
.. image:: _static/SortedSet-difference_update_small.png
difference_update_tiny
......................
-Set difference using
-:ref:`SortedSet.difference_update`.
+Set difference using :func:`SortedSet.difference_update`.
.. image:: _static/SortedSet-difference_update_tiny.png
intersection_large
..................
-Set intersection using :ref:`SortedSet.intersection`.
+Set intersection using :func:`SortedSet.intersection`.
.. image:: _static/SortedSet-intersection_large.png
intersection_medium
...................
-Set intersection using :ref:`SortedSet.intersection`.
+Set intersection using :func:`SortedSet.intersection`.
.. image:: _static/SortedSet-intersection_medium.png
intersection_small
..................
-Set intersection using :ref:`SortedSet.intersection`.
+Set intersection using :func:`SortedSet.intersection`.
.. image:: _static/SortedSet-intersection_small.png
intersection_tiny
.................
-Set intersection using :ref:`SortedSet.intersection`.
+Set intersection using :func:`SortedSet.intersection`.
.. image:: _static/SortedSet-intersection_tiny.png
intersection_update_large
.........................
-Set intersection using
-:ref:`SortedSet.intersection_update`.
+Set intersection using :func:`SortedSet.intersection_update`.
.. image:: _static/SortedSet-intersection_update_large.png
intersection_update_medium
..........................
-Set intersection using
-:ref:`SortedSet.intersection_update`.
+Set intersection using :func:`SortedSet.intersection_update`.
.. image:: _static/SortedSet-intersection_update_medium.png
intersection_update_small
.........................
-Set intersection using
-:ref:`SortedSet.intersection_update`.
+Set intersection using :func:`SortedSet.intersection_update`.
.. image:: _static/SortedSet-intersection_update_small.png
intersection_update_tiny
........................
-Set intersection using
-:ref:`SortedSet.intersection_update`.
+Set intersection using :func:`SortedSet.intersection_update`.
.. image:: _static/SortedSet-intersection_update_tiny.png
iter
....
-Iterating a set using :ref:`iter(SortedSet)`.
+Iterating a set using :func:`SortedSet.__iter__`.
.. image:: _static/SortedSet-iter.png
pop
...
-Remove the last item in a set using :ref:`SortedSet.pop