Intermediate changes

1 files changed, 236 insertions, 0 deletions

diff --git a/contrib/python/sortedcontainers/py3/README.rst b/contrib/python/sortedcontainers/py3/README.rst
new file mode 100644
index 0000000000..3e808386e7
--- /dev/null
+++ b/contrib/python/sortedcontainers/py3/README.rst
@@ -0,0 +1,236 @@
+Python Sorted Containers
+========================
+
+`Sorted Containers`_ 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, sorted dict, or sorted 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!
+
+.. code-block:: python
+
+    >>> from sortedcontainers import SortedList
+    >>> sl = SortedList(['e', 'a', 'c', 'd', 'b'])
+    >>> sl
+    SortedList(['a', 'b', 'c', 'd', 'e'])
+    >>> sl *= 10_000_000
+    >>> sl.count('c')
+    10000000
+    >>> sl[-3:]
+    ['e', 'e', 'e']
+    >>> from sortedcontainers import SortedDict
+    >>> sd = SortedDict({'c': 3, 'a': 1, 'b': 2})
+    >>> sd
+    SortedDict({'a': 1, 'b': 2, 'c': 3})
+    >>> sd.popitem(index=-1)
+    ('c', 3)
+    >>> from sortedcontainers import SortedSet
+    >>> ss = SortedSet('abracadabra')
+    >>> ss
+    SortedSet(['a', 'b', 'c', 'd', 'r'])
+    >>> ss.bisect_left('c')
+    2
+
+All of the operations shown above run in faster than linear time. The above
+demo also takes nearly a gigabyte of memory to run. When the sorted list is
+multiplied by ten million, it stores ten million references to each of "a"
+through "e". Each reference requires eight bytes in the sorted
+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.
+
+`Sorted Containers`_ 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.
+
+.. _`Sorted Containers`: http://www.grantjenks.com/docs/sortedcontainers/
+.. _`sorted collections library`: http://www.grantjenks.com/docs/sortedcontainers/
+
+Testimonials
+------------
+
+**Alex Martelli**, `Fellow of the Python Software Foundation`_
+
+"Good stuff! ... I like the `simple, effective implementation`_ idea of
+splitting the sorted containers into smaller "fragments" to avoid the O(N)
+insertion costs."
+
+**Jeff Knupp**, `author of Writing Idiomatic Python and Python Trainer`_
+
+"That last part, "fast as C-extensions," was difficult to believe. I would need
+some sort of `Performance Comparison`_ to be convinced this is true. The author
+includes this in the docs. It is."
+
+**Kevin Samuel**, `Python and Django Trainer`_
+
+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.
+
+**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.
+
+`Sorted Containers`_ is used in popular open source projects such as:
+`Zipline`_, an algorithmic trading library from Quantopian; `Angr`_, a binary
+analysis platform from UC Santa Barbara; `Trio`_, an async I/O library; and
+`Dask Distributed`_, a distributed computation library supported by Continuum
+Analytics.
+
+.. _`Fellow of the Python Software Foundation`: https://en.wikipedia.org/wiki/Alex_Martelli
+.. _`simple, effective implementation`: http://www.grantjenks.com/docs/sortedcontainers/implementation.html
+.. _`author of Writing Idiomatic Python and Python Trainer`: https://jeffknupp.com/
+.. _`Python and Django Trainer`: https://www.elephorm.com/formateur/kevin-samuel
+.. _`Python Sorted Collections`: http://www.qtrac.eu/pysorted.html
+.. _`Zipline`: https://github.com/quantopian/zipline
+.. _`Angr`: https://github.com/angr/angr
+.. _`Trio`: https://github.com/python-trio/trio
+.. _`Dask Distributed`: https://github.com/dask/distributed
+
+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 older blist and bintrees modules)
+- Feature-rich (e.g. get the five largest keys in a sorted dict: d.keys()[-5:])
+- Pragmatic design (e.g. SortedSet is a Python set with a SortedList index)
+- Developed on Python 3.7
+- Tested on CPython 2.7, 3.2, 3.3, 3.4, 3.5, 3.6, 3.7 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
+----------
+
+Installing `Sorted Containers`_ is simple with `pip
+<https://pypi.org/project/pip/>`_::
+
+    $ pip install sortedcontainers
+
+You can access documentation in the interpreter with Python's built-in `help`
+function. The `help` works on modules, classes and methods in `Sorted
+Containers`_.
+
+.. code-block:: python
+
+    >>> import sortedcontainers
+    >>> help(sortedcontainers)
+    >>> from sortedcontainers import SortedDict
+    >>> help(SortedDict)
+    >>> help(SortedDict.popitem)
+
+Documentation
+-------------
+
+Complete documentation for `Sorted Containers`_ is available at
+http://www.grantjenks.com/docs/sortedcontainers/
+
+User Guide
+..........
+
+The user guide provides an introduction to `Sorted Containers`_ and extensive
+performance comparisons and analysis.
+
+- `Introduction`_
+- `Performance Comparison`_
+- `Load Factor Performance Comparison`_
+- `Runtime Performance Comparison`_
+- `Simulated Workload Performance Comparison`_
+- `Performance at Scale`_
+
+.. _`Introduction`: http://www.grantjenks.com/docs/sortedcontainers/introduction.html
+.. _`Performance Comparison`: http://www.grantjenks.com/docs/sortedcontainers/performance.html
+.. _`Load Factor Performance Comparison`: http://www.grantjenks.com/docs/sortedcontainers/performance-load.html
+.. _`Runtime Performance Comparison`: http://www.grantjenks.com/docs/sortedcontainers/performance-runtime.html
+.. _`Simulated Workload Performance Comparison`: http://www.grantjenks.com/docs/sortedcontainers/performance-workload.html
+.. _`Performance at Scale`: http://www.grantjenks.com/docs/sortedcontainers/performance-scale.html
+
+Community Guide
+...............
+
+The community guide provides information on the development of `Sorted
+Containers`_ along with support, implementation, and history details.
+
+- `Development and Support`_
+- `Implementation Details`_
+- `Release History`_
+
+.. _`Development and Support`: http://www.grantjenks.com/docs/sortedcontainers/development.html
+.. _`Implementation Details`: http://www.grantjenks.com/docs/sortedcontainers/implementation.html
+.. _`Release History`: http://www.grantjenks.com/docs/sortedcontainers/history.html
+
+API Documentation
+.................
+
+The API documentation provides information on specific functions, classes, and
+modules in the `Sorted Containers`_ package.
+
+- `Sorted List`_
+- `Sorted Dict`_
+- `Sorted Set`_
+
+.. _`Sorted List`: http://www.grantjenks.com/docs/sortedcontainers/sortedlist.html
+.. _`Sorted Dict`: http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html
+.. _`Sorted Set`: http://www.grantjenks.com/docs/sortedcontainers/sortedset.html
+
+Talks
+-----
+
+- `Python Sorted Collections | PyCon 2016 Talk`_
+- `SF Python Holiday Party 2015 Lightning Talk`_
+- `DjangoCon 2015 Lightning Talk`_
+
+.. _`Python Sorted Collections | PyCon 2016 Talk`: http://www.grantjenks.com/docs/sortedcontainers/pycon-2016-talk.html
+.. _`SF Python Holiday Party 2015 Lightning Talk`: http://www.grantjenks.com/docs/sortedcontainers/sf-python-2015-lightning-talk.html
+.. _`DjangoCon 2015 Lightning Talk`: http://www.grantjenks.com/docs/sortedcontainers/djangocon-2015-lightning-talk.html
+
+Resources
+---------
+
+- `Sorted Containers Documentation`_
+- `Sorted Containers at PyPI`_
+- `Sorted Containers at Github`_
+- `Sorted Containers Issue Tracker`_
+
+.. _`Sorted Containers Documentation`: http://www.grantjenks.com/docs/sortedcontainers/
+.. _`Sorted Containers at PyPI`: https://pypi.org/project/sortedcontainers/
+.. _`Sorted Containers at Github`: https://github.com/grantjenks/python-sortedcontainers
+.. _`Sorted Containers Issue Tracker`: https://github.com/grantjenks/python-sortedcontainers/issues
+
+Sorted Containers License
+-------------------------
+
+Copyright 2014-2019 Grant Jenks
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+    http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.