--- a/testing/web-platform/tests/tools/localpaths.py
+++ b/testing/web-platform/tests/tools/localpaths.py
@@ -7,13 +7,14 @@ repo_root = os.path.abspath(os.path.join
sys.path.insert(0, os.path.join(here))
sys.path.insert(0, os.path.join(here, "six"))
sys.path.insert(0, os.path.join(here, "html5lib"))
sys.path.insert(0, os.path.join(here, "wptserve"))
sys.path.insert(0, os.path.join(here, "pywebsocket"))
sys.path.insert(0, os.path.join(here, "third_party", "atomicwrites"))
sys.path.insert(0, os.path.join(here, "third_party", "attrs", "src"))
sys.path.insert(0, os.path.join(here, "third_party", "funcsigs"))
+sys.path.insert(0, os.path.join(here, "third_party", "more-itertools"))
sys.path.insert(0, os.path.join(here, "third_party", "pluggy"))
sys.path.insert(0, os.path.join(here, "third_party", "py"))
sys.path.insert(0, os.path.join(here, "third_party", "pytest"))
sys.path.insert(0, os.path.join(here, "webdriver"))
sys.path.insert(0, os.path.join(here, "wptrunner"))
new file mode 100644
--- /dev/null
+++ b/testing/web-platform/tests/tools/third_party/more-itertools/.gitattributes
@@ -0,0 +1,2 @@
+more_itertools/more.py merge=union
+more_itertools/tests/test_more.py merge=union
new file mode 100644
--- /dev/null
+++ b/testing/web-platform/tests/tools/third_party/more-itertools/.gitignore
@@ -0,0 +1,34 @@
+*.py[co]
+
+# Packages
+*.egg
+*.eggs
+*.egg-info
+dist
+build
+eggs
+parts
+bin
+var
+sdist
+develop-eggs
+.installed.cfg
+
+# Installer logs
+pip-log.txt
+
+# Unit test / coverage reports
+.coverage
+.tox
+.noseids
+
+# Docs by Sphinx
+_build
+
+# Environment
+.env
+
+# IDE files
+.idea
+.vscode
+.DS_Store
new file mode 100644
--- /dev/null
+++ b/testing/web-platform/tests/tools/third_party/more-itertools/.travis.yml
@@ -0,0 +1,26 @@
+sudo: false
+
+language: "python"
+
+python:
+ - "2.7"
+ - "3.4"
+ - "3.5"
+ - "3.6"
+ - "3.7-dev"
+ - "pypy-5.4.1"
+ - "pypy3"
+
+install:
+ - "pip install ."
+ - "pip install -U coveralls flake8"
+
+script:
+ - "coverage run --include='more_itertools/*.py' --omit='more_itertools/tests/*' setup.py test"
+ - "flake8 ."
+
+notifications:
+ email: false
+
+after_success:
+ - "coveralls"
new file mode 100644
--- /dev/null
+++ b/testing/web-platform/tests/tools/third_party/more-itertools/LICENSE
@@ -0,0 +1,19 @@
+Copyright (c) 2012 Erik Rose
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of
+this software and associated documentation files (the "Software"), to deal in
+the Software without restriction, including without limitation the rights to
+use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
+of the Software, and to permit persons to whom the Software is furnished to do
+so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
new file mode 100644
--- /dev/null
+++ b/testing/web-platform/tests/tools/third_party/more-itertools/MANIFEST.in
@@ -0,0 +1,8 @@
+include README.rst
+include LICENSE
+include docs/*.rst
+include docs/Makefile
+include docs/make.bat
+include docs/conf.py
+include fabfile.py
+include tox.ini
new file mode 100644
--- /dev/null
+++ b/testing/web-platform/tests/tools/third_party/more-itertools/README.rst
@@ -0,0 +1,59 @@
+==============
+More Itertools
+==============
+
+.. image:: https://coveralls.io/repos/github/erikrose/more-itertools/badge.svg?branch=master
+ :target: https://coveralls.io/github/erikrose/more-itertools?branch=master
+
+Python's ``itertools`` library is a gem - you can compose elegant solutions
+for a variety of problems with the functions it provides. In ``more-itertools``
+we collect additional building blocks, recipes, and routines for working with
+Python iterables.
+
+Getting started
+===============
+
+To get started, install the library with `pip <https://pip.pypa.io/en/stable/>`_:
+
+.. code-block:: shell
+
+ pip install more-itertools
+
+The recipes from the `itertools docs <https://docs.python.org/3/library/itertools.html#itertools-recipes>`_
+are included in the top-level package:
+
+.. code-block:: python
+
+ >>> from more_itertools import flatten
+ >>> iterable = [(0, 1), (2, 3)]
+ >>> list(flatten(iterable))
+ [0, 1, 2, 3]
+
+Several new recipes are available as well:
+
+.. code-block:: python
+
+ >>> from more_itertools import chunked
+ >>> iterable = [0, 1, 2, 3, 4, 5, 6, 7, 8]
+ >>> list(chunked(iterable, 3))
+ [[0, 1, 2], [3, 4, 5], [6, 7, 8]]
+
+ >>> from more_itertools import spy
+ >>> iterable = (x * x for x in range(1, 6))
+ >>> head, iterable = spy(iterable, n=3)
+ >>> list(head)
+ [1, 4, 9]
+ >>> list(iterable)
+ [1, 4, 9, 16, 25]
+
+
+
+For the full listing of functions, see the `API documentation <https://more-itertools.readthedocs.io/en/latest/api.html>`_.
+
+Development
+===========
+
+``more-itertools`` is maintained by `@erikrose <https://github.com/erikrose>`_
+and `@bbayles <https://github.com/bbayles>`_, with help from `many others <https://github.com/erikrose/more-itertools/graphs/contributors>`_.
+If you have a problem or suggestion, please file a bug or pull request in this
+repository. Thanks for contributing!
new file mode 100644
--- /dev/null
+++ b/testing/web-platform/tests/tools/third_party/more-itertools/docs/Makefile
@@ -0,0 +1,153 @@
+# Makefile for Sphinx documentation
+#
+
+# You can set these variables from the command line.
+SPHINXOPTS =
+SPHINXBUILD = sphinx-build
+PAPER =
+BUILDDIR = _build
+
+# 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
+
+help:
+ @echo "Please use \`make <target>' where <target> 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 " 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 " 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/more-itertools.qhcp"
+ @echo "To view the help file:"
+ @echo "# assistant -collectionFile $(BUILDDIR)/qthelp/more-itertools.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/more-itertools"
+ @echo "# ln -s $(BUILDDIR)/devhelp $$HOME/.local/share/devhelp/more-itertools"
+ @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."
+
+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."
new file mode 100644
--- /dev/null
+++ b/testing/web-platform/tests/tools/third_party/more-itertools/docs/api.rst
@@ -0,0 +1,234 @@
+=============
+API Reference
+=============
+
+.. automodule:: more_itertools
+
+Grouping
+========
+
+These tools yield groups of items from a source iterable.
+
+----
+
+**New itertools**
+
+.. autofunction:: chunked
+.. autofunction:: sliced
+.. autofunction:: distribute
+.. autofunction:: divide
+.. autofunction:: split_at
+.. autofunction:: split_before
+.. autofunction:: split_after
+.. autofunction:: bucket
+
+----
+
+**Itertools recipes**
+
+.. autofunction:: grouper
+.. autofunction:: partition
+
+
+Lookahead and lookback
+======================
+
+These tools peek at an iterable's values without advancing it.
+
+----
+
+**New itertools**
+
+
+.. autofunction:: spy
+.. autoclass:: peekable
+.. autoclass:: seekable
+
+
+Windowing
+=========
+
+These tools yield windows of items from an iterable.
+
+----
+
+**New itertools**
+
+.. autofunction:: windowed
+.. autofunction:: stagger
+
+----
+
+**Itertools recipes**
+
+.. autofunction:: pairwise
+
+
+Augmenting
+==========
+
+These tools yield items from an iterable, plus additional data.
+
+----
+
+**New itertools**
+
+.. autofunction:: count_cycle
+.. autofunction:: intersperse
+.. autofunction:: padded
+.. autofunction:: adjacent
+.. autofunction:: groupby_transform
+
+----
+
+**Itertools recipes**
+
+.. autofunction:: padnone
+.. autofunction:: ncycles
+
+
+Combining
+=========
+
+These tools combine multiple iterables.
+
+----
+
+**New itertools**
+
+.. autofunction:: collapse
+.. autofunction:: sort_together
+.. autofunction:: interleave
+.. autofunction:: interleave_longest
+.. autofunction:: collate(*iterables, key=lambda a: a, reverse=False)
+.. autofunction:: zip_offset(*iterables, offsets, longest=False, fillvalue=None)
+
+----
+
+**Itertools recipes**
+
+.. autofunction:: dotproduct
+.. autofunction:: flatten
+.. autofunction:: roundrobin
+.. autofunction:: prepend
+
+
+Summarizing
+===========
+
+These tools return summarized or aggregated data from an iterable.
+
+----
+
+**New itertools**
+
+.. autofunction:: ilen
+.. autofunction:: first(iterable[, default])
+.. autofunction:: one
+.. autofunction:: unique_to_each
+.. autofunction:: locate(iterable, pred=bool)
+.. autofunction:: consecutive_groups(iterable, ordering=lambda x: x)
+.. autofunction:: exactly_n(iterable, n, predicate=bool)
+.. autoclass:: run_length
+.. autofunction:: map_reduce
+
+----
+
+**Itertools recipes**
+
+.. autofunction:: all_equal
+.. autofunction:: first_true
+.. autofunction:: nth
+.. autofunction:: quantify(iterable, pred=bool)
+
+
+Selecting
+=========
+
+These tools yield certain items from an iterable.
+
+----
+
+**New itertools**
+
+.. autofunction:: islice_extended(start, stop, step)
+.. autofunction:: strip
+.. autofunction:: lstrip
+.. autofunction:: rstrip
+
+----
+
+**Itertools recipes**
+
+.. autofunction:: take
+.. autofunction:: tail
+.. autofunction:: unique_everseen
+.. autofunction:: unique_justseen
+
+
+Combinatorics
+=============
+
+These tools yield combinatorial arrangements of items from iterables.
+
+----
+
+**New itertools**
+
+.. autofunction:: distinct_permutations
+.. autofunction:: circular_shifts
+
+----
+
+**Itertools recipes**
+
+.. autofunction:: powerset
+.. autofunction:: random_product
+.. autofunction:: random_permutation
+.. autofunction:: random_combination
+.. autofunction:: random_combination_with_replacement
+.. autofunction:: nth_combination
+
+
+Wrapping
+========
+
+These tools provide wrappers to smooth working with objects that produce or
+consume iterables.
+
+----
+
+**New itertools**
+
+.. autofunction:: always_iterable
+.. autofunction:: consumer
+.. autofunction:: with_iter
+
+----
+
+**Itertools recipes**
+
+.. autofunction:: iter_except
+
+
+Others
+======
+
+**New itertools**
+
+.. autofunction:: numeric_range(start, stop, step)
+.. autofunction:: always_reversible
+.. autofunction:: side_effect
+.. autofunction:: iterate
+.. autofunction:: difference(iterable, func=operator.sub)
+.. autofunction:: make_decorator
+.. autoclass:: SequenceView
+
+----
+
+**Itertools recipes**
+
+.. autofunction:: consume
+.. autofunction:: accumulate(iterable, func=operator.add)
+.. autofunction:: tabulate
+.. autofunction:: repeatfunc
new file mode 100644
--- /dev/null
+++ b/testing/web-platform/tests/tools/third_party/more-itertools/docs/conf.py
@@ -0,0 +1,244 @@
+# -*- coding: utf-8 -*-
+#
+# more-itertools documentation build configuration file, created by
+# sphinx-quickstart on Mon Jun 25 20:42:39 2012.
+#
+# 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.
+
+import sys, os
+
+import sphinx_rtd_theme
+
+# 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.
+sys.path.insert(0, os.path.abspath('..'))
+
+# -- General configuration -----------------------------------------------------
+
+# If your documentation needs a minimal Sphinx version, state it here.
+#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.viewcode']
+
+# Add any paths that contain templates here, relative to this directory.
+templates_path = ['_templates']
+
+# The suffix of source filenames.
+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 = u'more-itertools'
+copyright = u'2012, Erik Rose'
+
+# 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 = '4.2.0'
+# The full version, including alpha/beta/rc tags.
+release = 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'
+
+# 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
+
+# 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 = []
+
+
+# -- 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 = 'sphinx_rtd_theme'
+
+# 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 = [sphinx_rtd_theme.get_html_theme_path()]
+
+# The name for this set of Sphinx documents. If None, it defaults to
+# "<project> v<release> 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
+
+# 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']
+
+# 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.
+#html_sidebars = {}
+
+# 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 <link> 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
+
+# Output file base name for HTML help builder.
+htmlhelp_basename = 'more-itertoolsdoc'
+
+
+# -- 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': '',
+}
+
+# Grouping the document tree into LaTeX files. List of tuples
+# (source start file, target name, title, author, documentclass [howto/manual]).
+latex_documents = [
+ ('index', 'more-itertools.tex', u'more-itertools Documentation',
+ u'Erik Rose', '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 --------------------------------------------
+
+# One entry per manual page. List of tuples
+# (source start file, name, description, authors, manual section).
+man_pages = [
+ ('index', 'more-itertools', u'more-itertools Documentation',
+ [u'Erik Rose'], 1)
+]
+
+# If true, show URL addresses after external links.
+#man_show_urls = False
+
+
+# -- 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', 'more-itertools', u'more-itertools Documentation',
+ u'Erik Rose', 'more-itertools', 'One line description of project.',
+ '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'
new file mode 100644
--- /dev/null
+++ b/testing/web-platform/tests/tools/third_party/more-itertools/docs/index.rst
@@ -0,0 +1,16 @@
+.. include:: ../README.rst
+
+Contents
+========
+
+.. toctree::
+ :maxdepth: 2
+
+ api
+
+.. toctree::
+ :maxdepth: 1
+
+ license
+ testing
+ versions
new file mode 100644
--- /dev/null
+++ b/testing/web-platform/tests/tools/third_party/more-itertools/docs/license.rst
@@ -0,0 +1,16 @@
+=======
+License
+=======
+
+more-itertools is under the MIT License. See the LICENSE file.
+
+Conditions for Contributors
+===========================
+
+By contributing to this software project, you are agreeing to the following
+terms and conditions for your contributions: First, you agree your
+contributions are submitted under the MIT license. Second, you represent you
+are authorized to make the contributions and grant the license. If your
+employer has rights to intellectual property that includes your contributions,
+you represent that you have received permission to make contributions and grant
+the required license on behalf of that employer.
new file mode 100644
--- /dev/null
+++ b/testing/web-platform/tests/tools/third_party/more-itertools/docs/make.bat
@@ -0,0 +1,190 @@
+@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 ^<target^>` where ^<target^> 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. 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
+)
+
+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\more-itertools.qhcp
+ echo.To view the help file:
+ echo.^> assistant -collectionFile %BUILDDIR%\qthelp\more-itertools.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" == "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
+)
+
+:end
new file mode 100644
--- /dev/null
+++ b/testing/web-platform/tests/tools/third_party/more-itertools/docs/testing.rst
@@ -0,0 +1,19 @@
+=======
+Testing
+=======
+
+To run install dependencies and run tests, use this command::
+
+ python setup.py test
+
+Multiple Python Versions
+========================
+
+To run the tests on all the versions of Python more-itertools supports, install
+tox::
+
+ pip install tox
+
+Then, run the tests::
+
+ tox
new file mode 100644
--- /dev/null
+++ b/testing/web-platform/tests/tools/third_party/more-itertools/docs/versions.rst
@@ -0,0 +1,237 @@
+===============
+Version History
+===============
+
+.. automodule:: more_itertools
+
+4.2.0
+-----
+
+* New itertools:
+ * :func:`map_reduce` (thanks to pylang)
+ * :func:`prepend` (from the `Python 3.7 docs <https://docs.python.org/3.7/library/itertools.html#itertools-recipes>`_)
+
+* Improvements to existing itertools:
+ * :func:`bucket` now complies with PEP 479 (thanks to irmen)
+
+* Other changes:
+ * Python 3.7 is now supported (thanks to irmen)
+ * Python 3.3 is no longer supported
+ * The test suite no longer requires third-party modules to run
+ * The API docs now include links to source code
+
+4.1.0
+-----
+
+* New itertools:
+ * :func:`split_at` (thanks to michael-celani)
+ * :func:`circular_shifts` (thanks to hiqua)
+ * :func:`make_decorator` - see the blog post `Yo, I heard you like decorators <https://sites.google.com/site/bbayles/index/decorator_factory>`_
+ for a tour (thanks to pylang)
+ * :func:`always_reversible` (thanks to michael-celani)
+ * :func:`nth_combination` (from the `Python 3.7 docs <https://docs.python.org/3.7/library/itertools.html#itertools-recipes>`_)
+
+* Improvements to existing itertools:
+ * :func:`seekable` now has an ``elements`` method to return cached items.
+ * The performance tradeoffs between :func:`roundrobin` and
+ :func:`interleave_longest` are now documented (thanks michael-celani,
+ pylang, and MSeifert04)
+
+4.0.1
+-----
+
+* No code changes - this release fixes how the docs display on PyPI.
+
+4.0.0
+-----
+
+* New itertools:
+ * :func:`consecutive_groups` (Based on the example in the `Python 2.4 docs <https://docs.python.org/release/2.4.4/lib/itertools-example.html>`_)
+ * :func:`seekable` (If you're looking for how to "reset" an iterator,
+ you're in luck!)
+ * :func:`exactly_n` (thanks to michael-celani)
+ * :func:`run_length.encode` and :func:`run_length.decode`
+ * :func:`difference`
+
+* Improvements to existing itertools:
+ * The number of items between filler elements in :func:`intersperse` can
+ now be specified (thanks to pylang)
+ * :func:`distinct_permutations` and :func:`peekable` got some minor
+ adjustments (thanks to MSeifert04)
+ * :func:`always_iterable` now returns an iterator object. It also now
+ allows different types to be considered iterable (thanks to jaraco)
+ * :func:`bucket` can now limit the keys it stores in memory
+ * :func:`one` now allows for custom exceptions (thanks to kalekundert)
+
+* Other changes:
+ * A few typos were fixed (thanks to EdwardBetts)
+ * All tests can now be run with ``python setup.py test``
+
+The major version update is due to the change in the return value of :func:`always_iterable`.
+It now always returns iterator objects:
+
+.. code-block:: python
+
+ >>> from more_itertools import always_iterable
+ # Non-iterable objects are wrapped with iter(tuple(obj))
+ >>> always_iterable(12345)
+ <tuple_iterator object at 0x7fb24c9488d0>
+ >>> list(always_iterable(12345))
+ [12345]
+ # Iterable objects are wrapped with iter()
+ >>> always_iterable([1, 2, 3, 4, 5])
+ <list_iterator object at 0x7fb24c948c50>
+
+3.2.0
+-----
+
+* New itertools:
+ * :func:`lstrip`, :func:`rstrip`, and :func:`strip`
+ (thanks to MSeifert04 and pylang)
+ * :func:`islice_extended`
+* Improvements to existing itertools:
+ * Some bugs with slicing :func:`peekable`-wrapped iterables were fixed
+
+3.1.0
+-----
+
+* New itertools:
+ * :func:`numeric_range` (Thanks to BebeSparkelSparkel and MSeifert04)
+ * :func:`count_cycle` (Thanks to BebeSparkelSparkel)
+ * :func:`locate` (Thanks to pylang and MSeifert04)
+* Improvements to existing itertools:
+ * A few itertools are now slightly faster due to some function
+ optimizations. (Thanks to MSeifert04)
+* The docs have been substantially revised with installation notes,
+ categories for library functions, links, and more. (Thanks to pylang)
+
+
+3.0.0
+-----
+
+* Removed itertools:
+ * ``context`` has been removed due to a design flaw - see below for
+ replacement options. (thanks to NeilGirdhar)
+* Improvements to existing itertools:
+ * ``side_effect`` now supports ``before`` and ``after`` keyword
+ arguments. (Thanks to yardsale8)
+* PyPy and PyPy3 are now supported.
+
+The major version change is due to the removal of the ``context`` function.
+Replace it with standard ``with`` statement context management:
+
+.. code-block:: python
+
+ # Don't use context() anymore
+ file_obj = StringIO()
+ consume(print(x, file=f) for f in context(file_obj) for x in u'123')
+
+ # Use a with statement instead
+ file_obj = StringIO()
+ with file_obj as f:
+ consume(print(x, file=f) for x in u'123')
+
+2.6.0
+-----
+
+* New itertools:
+ * ``adjacent`` and ``groupby_transform`` (Thanks to diazona)
+ * ``always_iterable`` (Thanks to jaraco)
+ * (Removed in 3.0.0) ``context`` (Thanks to yardsale8)
+ * ``divide`` (Thanks to mozbhearsum)
+* Improvements to existing itertools:
+ * ``ilen`` is now slightly faster. (Thanks to wbolster)
+ * ``peekable`` can now prepend items to an iterable. (Thanks to diazona)
+
+2.5.0
+-----
+
+* New itertools:
+ * ``distribute`` (Thanks to mozbhearsum and coady)
+ * ``sort_together`` (Thanks to clintval)
+ * ``stagger`` and ``zip_offset`` (Thanks to joshbode)
+ * ``padded``
+* Improvements to existing itertools:
+ * ``peekable`` now handles negative indexes and slices with negative
+ components properly.
+ * ``intersperse`` is now slightly faster. (Thanks to pylang)
+ * ``windowed`` now accepts a ``step`` keyword argument.
+ (Thanks to pylang)
+* Python 3.6 is now supported.
+
+2.4.1
+-----
+
+* Move docs 100% to readthedocs.io.
+
+2.4
+-----
+
+* New itertools:
+ * ``accumulate``, ``all_equal``, ``first_true``, ``partition``, and
+ ``tail`` from the itertools documentation.
+ * ``bucket`` (Thanks to Rosuav and cvrebert)
+ * ``collapse`` (Thanks to abarnet)
+ * ``interleave`` and ``interleave_longest`` (Thanks to abarnet)
+ * ``side_effect`` (Thanks to nvie)
+ * ``sliced`` (Thanks to j4mie and coady)
+ * ``split_before`` and ``split_after`` (Thanks to astronouth7303)
+ * ``spy`` (Thanks to themiurgo and mathieulongtin)
+* Improvements to existing itertools:
+ * ``chunked`` is now simpler and more friendly to garbage collection.
+ (Contributed by coady, with thanks to piskvorky)
+ * ``collate`` now delegates to ``heapq.merge`` when possible.
+ (Thanks to kmike and julianpistorius)
+ * ``peekable``-wrapped iterables are now indexable and sliceable.
+ Iterating through ``peekable``-wrapped iterables is also faster.
+ * ``one`` and ``unique_to_each`` have been simplified.
+ (Thanks to coady)
+
+
+2.3
+-----
+
+* Added ``one`` from ``jaraco.util.itertools``. (Thanks, jaraco!)
+* Added ``distinct_permutations`` and ``unique_to_each``. (Contributed by
+ bbayles)
+* Added ``windowed``. (Contributed by bbayles, with thanks to buchanae,
+ jaraco, and abarnert)
+* Simplified the implementation of ``chunked``. (Thanks, nvie!)
+* Python 3.5 is now supported. Python 2.6 is no longer supported.
+* Python 3 is now supported directly; there is no 2to3 step.
+
+2.2
+-----
+
+* Added ``iterate`` and ``with_iter``. (Thanks, abarnert!)
+
+2.1
+-----
+
+* Added (tested!) implementations of the recipes from the itertools
+ documentation. (Thanks, Chris Lonnen!)
+* Added ``ilen``. (Thanks for the inspiration, Matt Basta!)
+
+2.0
+-----
+
+* ``chunked`` now returns lists rather than tuples. After all, they're
+ homogeneous. This slightly backward-incompatible change is the reason for
+ the major version bump.
+* Added ``@consumer``.
+* Improved test machinery.
+
+1.1
+-----
+
+* Added ``first`` function.
+* Added Python 3 support.
+* Added a default arg to ``peekable.peek()``.
+* Noted how to easily test whether a peekable iterator is exhausted.
+* Rewrote documentation.
+
+1.0
+-----
+
+* Initial release, with ``collate``, ``peekable``, and ``chunked``. Could
+ really use better docs.
new file mode 100644
--- /dev/null
+++ b/testing/web-platform/tests/tools/third_party/more-itertools/more_itertools/__init__.py
@@ -0,0 +1,2 @@
+from more_itertools.more import * # noqa
+from more_itertools.recipes import * # noqa
new file mode 100644
--- /dev/null
+++ b/testing/web-platform/tests/tools/third_party/more-itertools/more_itertools/more.py
@@ -0,0 +1,2068 @@
+from __future__ import print_function
+
+from collections import Counter, defaultdict, deque
+from functools import partial, wraps
+from heapq import merge
+from itertools import (
+ chain,
+ compress,
+ count,
+ cycle,
+ dropwhile,
+ groupby,
+ islice,
+ repeat,
+ takewhile,
+ tee
+)
+from operator import itemgetter, lt, gt, sub
+from sys import maxsize, version_info
+try:
+ from collections.abc import Sequence
+except ImportError:
+ from collections import Sequence
+
+from six import binary_type, string_types, text_type
+from six.moves import filter, map, range, zip, zip_longest
+
+from .recipes import consume, flatten, take
+
+__all__ = [
+ 'adjacent',
+ 'always_iterable',
+ 'always_reversible',
+ 'bucket',
+ 'chunked',
+ 'circular_shifts',
+ 'collapse',
+ 'collate',
+ 'consecutive_groups',
+ 'consumer',
+ 'count_cycle',
+ 'difference',
+ 'distinct_permutations',
+ 'distribute',
+ 'divide',
+ 'exactly_n',
+ 'first',
+ 'groupby_transform',
+ 'ilen',
+ 'interleave_longest',
+ 'interleave',
+ 'intersperse',
+ 'islice_extended',
+ 'iterate',
+ 'locate',
+ 'lstrip',
+ 'make_decorator',
+ 'map_reduce',
+ 'numeric_range',
+ 'one',
+ 'padded',
+ 'peekable',
+ 'rstrip',
+ 'run_length',
+ 'seekable',
+ 'SequenceView',
+ 'side_effect',
+ 'sliced',
+ 'sort_together',
+ 'split_at',
+ 'split_after',
+ 'split_before',
+ 'spy',
+ 'stagger',
+ 'strip',
+ 'unique_to_each',
+ 'windowed',
+ 'with_iter',
+ 'zip_offset',
+]
+
+_marker = object()
+
+
+def chunked(iterable, n):
+ """Break *iterable* into lists of length *n*:
+
+ >>> list(chunked([1, 2, 3, 4, 5, 6], 3))
+ [[1, 2, 3], [4, 5, 6]]
+
+ If the length of *iterable* is not evenly divisible by *n*, the last
+ returned list will be shorter:
+
+ >>> list(chunked([1, 2, 3, 4, 5, 6, 7, 8], 3))
+ [[1, 2, 3], [4, 5, 6], [7, 8]]
+
+ To use a fill-in value instead, see the :func:`grouper` recipe.
+
+ :func:`chunked` is useful for splitting up a computation on a large number
+ of keys into batches, to be pickled and sent off to worker processes. One
+ example is operations on rows in MySQL, which does not implement
+ server-side cursors properly and would otherwise load the entire dataset
+ into RAM on the client.
+
+ """
+ return iter(partial(take, n, iter(iterable)), [])
+
+
+def first(iterable, default=_marker):
+ """Return the first item of *iterable*, or *default* if *iterable* is
+ empty.
+
+ >>> first([0, 1, 2, 3])
+ 0
+ >>> first([], 'some default')
+ 'some default'
+
+ If *default* is not provided and there are no items in the iterable,
+ raise ``ValueError``.
+
+ :func:`first` is useful when you have a generator of expensive-to-retrieve
+ values and want any arbitrary one. It is marginally shorter than
+ ``next(iter(iterable), default)``.
+
+ """
+ try:
+ return next(iter(iterable))
+ except StopIteration:
+ # I'm on the edge about raising ValueError instead of StopIteration. At
+ # the moment, ValueError wins, because the caller could conceivably
+ # want to do something different with flow control when I raise the
+ # exception, and it's weird to explicitly catch StopIteration.
+ if default is _marker:
+ raise ValueError('first() was called on an empty iterable, and no '
+ 'default value was provided.')
+ return default
+
+
+class peekable(object):
+ """Wrap an iterator to allow lookahead and prepending elements.
+
+ Call :meth:`peek` on the result to get the value that will be returned
+ by :func:`next`. This won't advance the iterator:
+
+ >>> p = peekable(['a', 'b'])
+ >>> p.peek()
+ 'a'
+ >>> next(p)
+ 'a'
+
+ Pass :meth:`peek` a default value to return that instead of raising
+ ``StopIteration`` when the iterator is exhausted.
+
+ >>> p = peekable([])
+ >>> p.peek('hi')
+ 'hi'
+
+ peekables also offer a :meth:`prepend` method, which "inserts" items
+ at the head of the iterable:
+
+ >>> p = peekable([1, 2, 3])
+ >>> p.prepend(10, 11, 12)
+ >>> next(p)
+ 10
+ >>> p.peek()
+ 11
+ >>> list(p)
+ [11, 12, 1, 2, 3]
+
+ peekables can be indexed. Index 0 is the item that will be returned by
+ :func:`next`, index 1 is the item after that, and so on:
+ The values up to the given index will be cached.
+
+ >>> p = peekable(['a', 'b', 'c', 'd'])
+ >>> p[0]
+ 'a'
+ >>> p[1]
+ 'b'
+ >>> next(p)
+ 'a'
+
+ Negative indexes are supported, but be aware that they will cache the
+ remaining items in the source iterator, which may require significant
+ storage.
+
+ To check whether a peekable is exhausted, check its truth value:
+
+ >>> p = peekable(['a', 'b'])
+ >>> if p: # peekable has items
+ ... list(p)
+ ['a', 'b']
+ >>> if not p: # peekable is exhaused
+ ... list(p)
+ []
+
+ """
+ def __init__(self, iterable):
+ self._it = iter(iterable)
+ self._cache = deque()
+
+ def __iter__(self):
+ return self
+
+ def __bool__(self):
+ try:
+ self.peek()
+ except StopIteration:
+ return False
+ return True
+
+ def __nonzero__(self):
+ # For Python 2 compatibility
+ return self.__bool__()
+
+ def peek(self, default=_marker):
+ """Return the item that will be next returned from ``next()``.
+
+ Return ``default`` if there are no items left. If ``default`` is not
+ provided, raise ``StopIteration``.
+
+ """
+ if not self._cache:
+ try:
+ self._cache.append(next(self._it))
+ except StopIteration:
+ if default is _marker:
+ raise
+ return default
+ return self._cache[0]
+
+ def prepend(self, *items):
+ """Stack up items to be the next ones returned from ``next()`` or
+ ``self.peek()``. The items will be returned in
+ first in, first out order::
+
+ >>> p = peekable([1, 2, 3])
+ >>> p.prepend(10, 11, 12)
+ >>> next(p)
+ 10
+ >>> list(p)
+ [11, 12, 1, 2, 3]
+
+ It is possible, by prepending items, to "resurrect" a peekable that
+ previously raised ``StopIteration``.
+
+ >>> p = peekable([])
+ >>> next(p)
+ Traceback (most recent call last):
+ ...
+ StopIteration
+ >>> p.prepend(1)
+ >>> next(p)
+ 1
+ >>> next(p)
+ Traceback (most recent call last):
+ ...
+ StopIteration
+
+ """
+ self._cache.extendleft(reversed(items))
+
+ def __next__(self):
+ if self._cache:
+ return self._cache.popleft()
+
+ return next(self._it)
+
+ next = __next__ # For Python 2 compatibility
+
+ def _get_slice(self, index):
+ # Normalize the slice's arguments
+ step = 1 if (index.step is None) else index.step
+ if step > 0:
+ start = 0 if (index.start is None) else index.start
+ stop = maxsize if (index.stop is None) else index.stop
+ elif step < 0:
+ start = -1 if (index.start is None) else index.start
+ stop = (-maxsize - 1) if (index.stop is None) else index.stop
+ else:
+ raise ValueError('slice step cannot be zero')
+
+ # If either the start or stop index is negative, we'll need to cache
+ # the rest of the iterable in order to slice from the right side.
+ if (start < 0) or (stop < 0):
+ self._cache.extend(self._it)
+ # Otherwise we'll need to find the rightmost index and cache to that
+ # point.
+ else:
+ n = min(max(start, stop) + 1, maxsize)
+ cache_len = len(self._cache)
+ if n >= cache_len:
+ self._cache.extend(islice(self._it, n - cache_len))
+
+ return list(self._cache)[index]
+
+ def __getitem__(self, index):
+ if isinstance(index, slice):
+ return self._get_slice(index)
+
+ cache_len = len(self._cache)
+ if index < 0:
+ self._cache.extend(self._it)
+ elif index >= cache_len:
+ self._cache.extend(islice(self._it, index + 1 - cache_len))
+
+ return self._cache[index]
+
+
+def _collate(*iterables, **kwargs):
+ """Helper for ``collate()``, called when the user is using the ``reverse``
+ or ``key`` keyword arguments on Python versions below 3.5.
+
+ """
+ key = kwargs.pop('key', lambda a: a)
+ reverse = kwargs.pop('reverse', False)
+
+ min_or_max = partial(max if reverse else min, key=itemgetter(0))
+ peekables = [peekable(it) for it in iterables]
+ peekables = [p for p in peekables if p] # Kill empties.
+ while peekables:
+ _, p = min_or_max((key(p.peek()), p) for p in peekables)
+ yield next(p)
+ peekables = [x for x in peekables if x]
+
+
+def collate(*iterables, **kwargs):
+ """Return a sorted merge of the items from each of several already-sorted
+ *iterables*.
+
+ >>> list(collate('ACDZ', 'AZ', 'JKL'))
+ ['A', 'A', 'C', 'D', 'J', 'K', 'L', 'Z', 'Z']
+
+ Works lazily, keeping only the next value from each iterable in memory. Use
+ :func:`collate` to, for example, perform a n-way mergesort of items that
+ don't fit in memory.
+
+ If a *key* function is specified, the iterables will be sorted according
+ to its result:
+
+ >>> key = lambda s: int(s) # Sort by numeric value, not by string
+ >>> list(collate(['1', '10'], ['2', '11'], key=key))
+ ['1', '2', '10', '11']
+
+
+ If the *iterables* are sorted in descending order, set *reverse* to
+ ``True``:
+
+ >>> list(collate([5, 3, 1], [4, 2, 0], reverse=True))
+ [5, 4, 3, 2, 1, 0]
+
+ If the elements of the passed-in iterables are out of order, you might get
+ unexpected results.
+
+ On Python 2.7, this function delegates to :func:`heapq.merge` if neither
+ of the keyword arguments are specified. On Python 3.5+, this function
+ is an alias for :func:`heapq.merge`.
+
+ """
+ if not kwargs:
+ return merge(*iterables)
+
+ return _collate(*iterables, **kwargs)
+
+
+# If using Python version 3.5 or greater, heapq.merge() will be faster than
+# collate - use that instead.
+if version_info >= (3, 5, 0):
+ _collate_docstring = collate.__doc__
+ collate = partial(merge)
+ collate.__doc__ = _collate_docstring
+
+
+def consumer(func):
+ """Decorator that automatically advances a PEP-342-style "reverse iterator"
+ to its first yield point so you don't have to call ``next()`` on it
+ manually.
+
+ >>> @consumer
+ ... def tally():
+ ... i = 0
+ ... while True:
+ ... print('Thing number %s is %s.' % (i, (yield)))
+ ... i += 1
+ ...
+ >>> t = tally()
+ >>> t.send('red')
+ Thing number 0 is red.
+ >>> t.send('fish')
+ Thing number 1 is fish.
+
+ Without the decorator, you would have to call ``next(t)`` before
+ ``t.send()`` could be used.
+
+ """
+ @wraps(func)
+ def wrapper(*args, **kwargs):
+ gen = func(*args, **kwargs)
+ next(gen)
+ return gen
+ return wrapper
+
+
+def ilen(iterable):
+ """Return the number of items in *iterable*.
+
+ >>> ilen(x for x in range(1000000) if x % 3 == 0)
+ 333334
+
+ This consumes the iterable, so handle with care.
+
+ """
+ # maxlen=1 only stores the last item in the deque
+ d = deque(enumerate(iterable, 1), maxlen=1)
+ # since we started enumerate at 1,
+ # the first item of the last pair will be the length of the iterable
+ # (assuming there were items)
+ return d[0][0] if d else 0
+
+
+def iterate(func, start):
+ """Return ``start``, ``func(start)``, ``func(func(start))``, ...
+
+ >>> from itertools import islice
+ >>> list(islice(iterate(lambda x: 2*x, 1), 10))
+ [1, 2, 4, 8, 16, 32, 64, 128, 256, 512]
+
+ """
+ while True:
+ yield start
+ start = func(start)
+
+
+def with_iter(context_manager):
+ """Wrap an iterable in a ``with`` statement, so it closes once exhausted.
+
+ For example, this will close the file when the iterator is exhausted::
+
+ upper_lines = (line.upper() for line in with_iter(open('foo')))
+
+ Any context manager which returns an iterable is a candidate for
+ ``with_iter``.
+
+ """
+ with context_manager as iterable:
+ for item in iterable:
+ yield item
+
+
+def one(iterable, too_short=None, too_long=None):
+ """Return the first item from *iterable*, which is expected to contain only
+ that item. Raise an exception if *iterable* is empty or has more than one
+ item.
+
+ :func:`one` is useful for ensuring that an iterable contains only one item.
+ For example, it can be used to retrieve the result of a database query
+ that is expected to return a single row.
+
+ If *iterable* is empty, ``ValueError`` will be raised. You may specify a
+ different exception with the *too_short* keyword:
+
+ >>> it = []
+ >>> one(it) # doctest: +IGNORE_EXCEPTION_DETAIL
+ Traceback (most recent call last):
+ ...
+ ValueError: too many items in iterable (expected 1)'
+ >>> too_short = IndexError('too few items')
+ >>> one(it, too_short=too_short) # doctest: +IGNORE_EXCEPTION_DETAIL
+ Traceback (most recent call last):
+ ...
+ IndexError: too few items
+
+ Similarly, if *iterable* contains more than one item, ``ValueError`` will
+ be raised. You may specify a different exception with the *too_long*
+ keyword:
+
+ >>> it = ['too', 'many']
+ >>> one(it) # doctest: +IGNORE_EXCEPTION_DETAIL
+ Traceback (most recent call last):
+ ...
+ ValueError: too many items in iterable (expected 1)'
+ >>> too_long = RuntimeError
+ >>> one(it, too_long=too_long) # doctest: +IGNORE_EXCEPTION_DETAIL
+ Traceback (most recent call last):
+ ...
+ RuntimeError
+
+ Note that :func:`one` attempts to advance *iterable* twice to ensure there
+ is only one item. If there is more than one, both items will be discarded.
+ See :func:`spy` or :func:`peekable` to check iterable contents less
+ destructively.
+
+ """
+ it = iter(iterable)
+
+ try:
+ value = next(it)
+ except StopIteration:
+ raise too_short or ValueError('too few items in iterable (expected 1)')
+
+ try:
+ next(it)
+ except StopIteration:
+ pass
+ else:
+ raise too_long or ValueError('too many items in iterable (expected 1)')
+
+ return value
+
+
+def distinct_permutations(iterable):
+ """Yield successive distinct permutations of the elements in *iterable*.
+
+ >>> sorted(distinct_permutations([1, 0, 1]))
+ [(0, 1, 1), (1, 0, 1), (1, 1, 0)]
+
+ Equivalent to ``set(permutations(iterable))``, except duplicates are not
+ generated and thrown away. For larger input sequences this is much more
+ efficient.
+
+ Duplicate permutations arise when there are duplicated elements in the
+ input iterable. The number of items returned is
+ `n! / (x_1! * x_2! * ... * x_n!)`, where `n` is the total number of
+ items input, and each `x_i` is the count of a distinct item in the input
+ sequence.
+
+ """
+ def perm_unique_helper(item_counts, perm, i):
+ """Internal helper function
+
+ :arg item_counts: Stores the unique items in ``iterable`` and how many
+ times they are repeated
+ :arg perm: The permutation that is being built for output
+ :arg i: The index of the permutation being modified
+
+ The output permutations are built up recursively; the distinct items
+ are placed until their repetitions are exhausted.
+ """
+ if i < 0:
+ yield tuple(perm)
+ else:
+ for item in item_counts:
+ if item_counts[item] <= 0:
+ continue
+ perm[i] = item
+ item_counts[item] -= 1
+ for x in perm_unique_helper(item_counts, perm, i - 1):
+ yield x
+ item_counts[item] += 1
+
+ item_counts = Counter(iterable)
+ length = sum(item_counts.values())
+
+ return perm_unique_helper(item_counts, [None] * length, length - 1)
+
+
+def intersperse(e, iterable, n=1):
+ """Intersperse filler element *e* among the items in *iterable*, leaving
+ *n* items between each filler element.
+
+ >>> list(intersperse('!', [1, 2, 3, 4, 5]))
+ [1, '!', 2, '!', 3, '!', 4, '!', 5]
+
+ >>> list(intersperse(None, [1, 2, 3, 4, 5], n=2))
+ [1, 2, None, 3, 4, None, 5]
+
+ """
+ if n == 0:
+ raise ValueError('n must be > 0')
+ elif n == 1:
+ # interleave(repeat(e), iterable) -> e, x_0, e, e, x_1, e, x_2...
+ # islice(..., 1, None) -> x_0, e, e, x_1, e, x_2...
+ return islice(interleave(repeat(e), iterable), 1, None)
+ else:
+ # interleave(filler, chunks) -> [e], [x_0, x_1], [e], [x_2, x_3]...
+ # islice(..., 1, None) -> [x_0, x_1], [e], [x_2, x_3]...
+ # flatten(...) -> x_0, x_1, e, x_2, x_3...
+ filler = repeat([e])
+ chunks = chunked(iterable, n)
+ return flatten(islice(interleave(filler, chunks), 1, None))
+
+
+def unique_to_each(*iterables):
+ """Return the elements from each of the input iterables that aren't in the
+ other input iterables.
+
+ For example, suppose you have a set of packages, each with a set of
+ dependencies::
+
+ {'pkg_1': {'A', 'B'}, 'pkg_2': {'B', 'C'}, 'pkg_3': {'B', 'D'}}
+
+ If you remove one package, which dependencies can also be removed?
+
+ If ``pkg_1`` is removed, then ``A`` is no longer necessary - it is not
+ associated with ``pkg_2`` or ``pkg_3``. Similarly, ``C`` is only needed for
+ ``pkg_2``, and ``D`` is only needed for ``pkg_3``::
+
+ >>> unique_to_each({'A', 'B'}, {'B', 'C'}, {'B', 'D'})
+ [['A'], ['C'], ['D']]
+
+ If there are duplicates in one input iterable that aren't in the others
+ they will be duplicated in the output. Input order is preserved::
+
+ >>> unique_to_each("mississippi", "missouri")
+ [['p', 'p'], ['o', 'u', 'r']]
+
+ It is assumed that the elements of each iterable are hashable.
+
+ """
+ pool = [list(it) for it in iterables]
+ counts = Counter(chain.from_iterable(map(set, pool)))
+ uniques = {element for element in counts if counts[element] == 1}
+ return [list(filter(uniques.__contains__, it)) for it in pool]
+
+
+def windowed(seq, n, fillvalue=None, step=1):
+ """Return a sliding window of width *n* over the given iterable.
+
+ >>> all_windows = windowed([1, 2, 3, 4, 5], 3)
+ >>> list(all_windows)
+ [(1, 2, 3), (2, 3, 4), (3, 4, 5)]
+
+ When the window is larger than the iterable, *fillvalue* is used in place
+ of missing values::
+
+ >>> list(windowed([1, 2, 3], 4))
+ [(1, 2, 3, None)]
+
+ Each window will advance in increments of *step*:
+
+ >>> list(windowed([1, 2, 3, 4, 5, 6], 3, fillvalue='!', step=2))
+ [(1, 2, 3), (3, 4, 5), (5, 6, '!')]
+
+ """
+ if n < 0:
+ raise ValueError('n must be >= 0')
+ if n == 0:
+ yield tuple()
+ return
+ if step < 1:
+ raise ValueError('step must be >= 1')
+
+ it = iter(seq)
+ window = deque([], n)
+ append = window.append
+
+ # Initial deque fill
+ for _ in range(n):
+ append(next(it, fillvalue))
+ yield tuple(window)
+
+ # Appending new items to the right causes old items to fall off the left
+ i = 0
+ for item in it:
+ append(item)
+ i = (i + 1) % step
+ if i % step == 0:
+ yield tuple(window)
+
+ # If there are items from the iterable in the window, pad with the given
+ # value and emit them.
+ if (i % step) and (step - i < n):
+ for _ in range(step - i):
+ append(fillvalue)
+ yield tuple(window)
+
+
+class bucket(object):
+ """Wrap *iterable* and return an object that buckets it iterable into
+ child iterables based on a *key* function.
+
+ >>> iterable = ['a1', 'b1', 'c1', 'a2', 'b2', 'c2', 'b3']
+ >>> s = bucket(iterable, key=lambda x: x[0])
+ >>> a_iterable = s['a']
+ >>> next(a_iterable)
+ 'a1'
+ >>> next(a_iterable)
+ 'a2'
+ >>> list(s['b'])
+ ['b1', 'b2', 'b3']
+
+ The original iterable will be advanced and its items will be cached until
+ they are used by the child iterables. This may require significant storage.
+
+ By default, attempting to select a bucket to which no items belong will
+ exhaust the iterable and cache all values.
+ If you specify a *validator* function, selected buckets will instead be
+ checked against it.
+
+ >>> from itertools import count
+ >>> it = count(1, 2) # Infinite sequence of odd numbers
+ >>> key = lambda x: x % 10 # Bucket by last digit
+ >>> validator = lambda x: x in {1, 3, 5, 7, 9} # Odd digits only
+ >>> s = bucket(it, key=key, validator=validator)
+ >>> 2 in s
+ False
+ >>> list(s[2])
+ []
+
+ """
+ def __init__(self, iterable, key, validator=None):
+ self._it = iter(iterable)
+ self._key = key
+ self._cache = defaultdict(deque)
+ self._validator = validator or (lambda x: True)
+
+ def __contains__(self, value):
+ if not self._validator(value):
+ return False
+
+ try:
+ item = next(self[value])
+ except StopIteration:
+ return False
+ else:
+ self._cache[value].appendleft(item)
+
+ return True
+
+ def _get_values(self, value):
+ """
+ Helper to yield items from the parent iterator that match *value*.
+ Items that don't match are stored in the local cache as they
+ are encountered.
+ """
+ while True:
+ # If we've cached some items that match the target value, emit
+ # the first one and evict it from the cache.
+ if self._cache[value]:
+ yield self._cache[value].popleft()
+ # Otherwise we need to advance the parent iterator to search for
+ # a matching item, caching the rest.
+ else:
+ while True:
+ try:
+ item = next(self._it)
+ except StopIteration:
+ return
+ item_value = self._key(item)
+ if item_value == value:
+ yield item
+ break
+ elif self._validator(item_value):
+ self._cache[item_value].append(item)
+
+ def __getitem__(self, value):
+ if not self._validator(value):
+ return iter(())
+
+ return self._get_values(value)
+
+
+def spy(iterable, n=1):
+ """Return a 2-tuple with a list containing the first *n* elements of
+ *iterable*, and an iterator with the same items as *iterable*.
+ This allows you to "look ahead" at the items in the iterable without
+ advancing it.
+
+ There is one item in the list by default:
+
+ >>> iterable = 'abcdefg'
+ >>> head, iterable = spy(iterable)
+ >>> head
+ ['a']
+ >>> list(iterable)
+ ['a', 'b', 'c', 'd', 'e', 'f', 'g']
+
+ You may use unpacking to retrieve items instead of lists:
+
+ >>> (head,), iterable = spy('abcdefg')
+ >>> head
+ 'a'
+ >>> (first, second), iterable = spy('abcdefg', 2)
+ >>> first
+ 'a'
+ >>> second
+ 'b'
+
+ The number of items requested can be larger than the number of items in
+ the iterable:
+
+ >>> iterable = [1, 2, 3, 4, 5]
+ >>> head, iterable = spy(iterable, 10)
+ >>> head
+ [1, 2, 3, 4, 5]
+ >>> list(iterable)
+ [1, 2, 3, 4, 5]
+
+ """
+ it = iter(iterable)
+ head = take(n, it)
+
+ return head, chain(head, it)
+
+
+def interleave(*iterables):
+ """Return a new iterable yielding from each iterable in turn,
+ until the shortest is exhausted.
+
+ >>> list(interleave([1, 2, 3], [4, 5], [6, 7, 8]))
+ [1, 4, 6, 2, 5, 7]
+
+ For a version that doesn't terminate after the shortest iterable is
+ exhausted, see :func:`interleave_longest`.
+
+ """
+ return chain.from_iterable(zip(*iterables))
+
+
+def interleave_longest(*iterables):
+ """Return a new iterable yielding from each iterable in turn,
+ skipping any that are exhausted.
+
+ >>> list(interleave_longest([1, 2, 3], [4, 5], [6, 7, 8]))
+ [1, 4, 6, 2, 5, 7, 3, 8]
+
+ This function produces the same output as :func:`roundrobin`, but may
+ perform better for some inputs (in particular when the number of iterables
+ is large).
+
+ """
+ i = chain.from_iterable(zip_longest(*iterables, fillvalue=_marker))
+ return (x for x in i if x is not _marker)
+
+
+def collapse(iterable, base_type=None, levels=None):
+ """Flatten an iterable with multiple levels of nesting (e.g., a list of
+ lists of tuples) into non-iterable types.
+
+ >>> iterable = [(1, 2), ([3, 4], [[5], [6]])]
+ >>> list(collapse(iterable))
+ [1, 2, 3, 4, 5, 6]
+
+ String types are not considered iterable and will not be collapsed.
+ To avoid collapsing other types, specify *base_type*:
+
+ >>> iterable = ['ab', ('cd', 'ef'), ['gh', 'ij']]
+ >>> list(collapse(iterable, base_type=tuple))
+ ['ab', ('cd', 'ef'), 'gh', 'ij']
+
+ Specify *levels* to stop flattening after a certain level:
+
+ >>> iterable = [('a', ['b']), ('c', ['d'])]
+ >>> list(collapse(iterable)) # Fully flattened
+ ['a', 'b', 'c', 'd']
+ >>> list(collapse(iterable, levels=1)) # Only one level flattened
+ ['a', ['b'], 'c', ['d']]
+
+ """
+ def walk(node, level):
+ if (
+ ((levels is not None) and (level > levels)) or
+ isinstance(node, string_types) or
+ ((base_type is not None) and isinstance(node, base_type))
+ ):
+ yield node
+ return
+
+ try:
+ tree = iter(node)
+ except TypeError:
+ yield node
+ return
+ else:
+ for child in tree:
+ for x in walk(child, level + 1):
+ yield x
+
+ for x in walk(iterable, 0):
+ yield x
+
+
+def side_effect(func, iterable, chunk_size=None, before=None, after=None):
+ """Invoke *func* on each item in *iterable* (or on each *chunk_size* group
+ of items) before yielding the item.
+
+ `func` must be a function that takes a single argument. Its return value
+ will be discarded.
+
+ *before* and *after* are optional functions that take no arguments. They
+ will be executed before iteration starts and after it ends, respectively.
+
+ `side_effect` can be used for logging, updating progress bars, or anything
+ that is not functionally "pure."
+
+ Emitting a status message:
+
+ >>> from more_itertools import consume
+ >>> func = lambda item: print('Received {}'.format(item))
+ >>> consume(side_effect(func, range(2)))
+ Received 0
+ Received 1
+
+ Operating on chunks of items:
+
+ >>> pair_sums = []
+ >>> func = lambda chunk: pair_sums.append(sum(chunk))
+ >>> list(side_effect(func, [0, 1, 2, 3, 4, 5], 2))
+ [0, 1, 2, 3, 4, 5]
+ >>> list(pair_sums)
+ [1, 5, 9]
+
+ Writing to a file-like object:
+
+ >>> from io import StringIO
+ >>> from more_itertools import consume
+ >>> f = StringIO()
+ >>> func = lambda x: print(x, file=f)
+ >>> before = lambda: print(u'HEADER', file=f)
+ >>> after = f.close
+ >>> it = [u'a', u'b', u'c']
+ >>> consume(side_effect(func, it, before=before, after=after))
+ >>> f.closed
+ True
+
+ """
+ try:
+ if before is not None:
+ before()
+
+ if chunk_size is None:
+ for item in iterable:
+ func(item)
+ yield item
+ else:
+ for chunk in chunked(iterable, chunk_size):
+ func(chunk)
+ for item in chunk:
+ yield item
+ finally:
+ if after is not None:
+ after()
+
+
+def sliced(seq, n):
+ """Yield slices of length *n* from the sequence *seq*.
+
+ >>> list(sliced((1, 2, 3, 4, 5, 6), 3))
+ [(1, 2, 3), (4, 5, 6)]
+
+ If the length of the sequence is not divisible by the requested slice
+ length, the last slice will be shorter.
+
+ >>> list(sliced((1, 2, 3, 4, 5, 6, 7, 8), 3))
+ [(1, 2, 3), (4, 5, 6), (7, 8)]
+
+ This function will only work for iterables that support slicing.
+ For non-sliceable iterables, see :func:`chunked`.
+
+ """
+ return takewhile(bool, (seq[i: i + n] for i in count(0, n)))
+
+
+def split_at(iterable, pred):
+ """Yield lists of items from *iterable*, where each list is delimited by
+ an item where callable *pred* returns ``True``. The lists do not include
+ the delimiting items.
+
+ >>> list(split_at('abcdcba', lambda x: x == 'b'))
+ [['a'], ['c', 'd', 'c'], ['a']]
+
+ >>> list(split_at(range(10), lambda n: n % 2 == 1))
+ [[0], [2], [4], [6], [8], []]
+ """
+ buf = []
+ for item in iterable:
+ if pred(item):
+ yield buf
+ buf = []
+ else:
+ buf.append(item)
+ yield buf
+
+
+def split_before(iterable, pred):
+ """Yield lists of items from *iterable*, where each list starts with an
+ item where callable *pred* returns ``True``:
+
+ >>> list(split_before('OneTwo', lambda s: s.isupper()))
+ [['O', 'n', 'e'], ['T', 'w', 'o']]
+
+ >>> list(split_before(range(10), lambda n: n % 3 == 0))
+ [[0, 1, 2], [3, 4, 5], [6, 7, 8], [9]]
+
+ """
+ buf = []
+ for item in iterable:
+ if pred(item) and buf:
+ yield buf
+ buf = []
+ buf.append(item)
+ yield buf
+
+
+def split_after(iterable, pred):
+ """Yield lists of items from *iterable*, where each list ends with an
+ item where callable *pred* returns ``True``:
+
+ >>> list(split_after('one1two2', lambda s: s.isdigit()))
+ [['o', 'n', 'e', '1'], ['t', 'w', 'o', '2']]
+
+ >>> list(split_after(range(10), lambda n: n % 3 == 0))
+ [[0], [1, 2, 3], [4, 5, 6], [7, 8, 9]]
+
+ """
+ buf = []
+ for item in iterable:
+ buf.append(item)
+ if pred(item) and buf:
+ yield buf
+ buf = []
+ if buf:
+ yield buf
+
+
+def padded(iterable, fillvalue=None, n=None, next_multiple=False):
+ """Yield the elements from *iterable*, followed by *fillvalue*, such that
+ at least *n* items are emitted.
+
+ >>> list(padded([1, 2, 3], '?', 5))
+ [1, 2, 3, '?', '?']
+
+ If *next_multiple* is ``True``, *fillvalue* will be emitted until the
+ number of items emitted is a multiple of *n*::
+
+ >>> list(padded([1, 2, 3, 4], n=3, next_multiple=True))
+ [1, 2, 3, 4, None, None]
+
+ If *n* is ``None``, *fillvalue* will be emitted indefinitely.
+
+ """
+ it = iter(iterable)
+ if n is None:
+ for item in chain(it, repeat(fillvalue)):
+ yield item
+ elif n < 1:
+ raise ValueError('n must be at least 1')
+ else:
+ item_count = 0
+ for item in it:
+ yield item
+ item_count += 1
+
+ remaining = (n - item_count) % n if next_multiple else n - item_count
+ for _ in range(remaining):
+ yield fillvalue
+
+
+def distribute(n, iterable):
+ """Distribute the items from *iterable* among *n* smaller iterables.
+
+ >>> group_1, group_2 = distribute(2, [1, 2, 3, 4, 5, 6])
+ >>> list(group_1)
+ [1, 3, 5]
+ >>> list(group_2)
+ [2, 4, 6]
+
+ If the length of *iterable* is not evenly divisible by *n*, then the
+ length of the returned iterables will not be identical:
+
+ >>> children = distribute(3, [1, 2, 3, 4, 5, 6, 7])
+ >>> [list(c) for c in children]
+ [[1, 4, 7], [2, 5], [3, 6]]
+
+ If the length of *iterable* is smaller than *n*, then the last returned
+ iterables will be empty:
+
+ >>> children = distribute(5, [1, 2, 3])
+ >>> [list(c) for c in children]
+ [[1], [2], [3], [], []]
+
+ This function uses :func:`itertools.tee` and may require significant
+ storage. If you need the order items in the smaller iterables to match the
+ original iterable, see :func:`divide`.
+
+ """
+ if n < 1:
+ raise ValueError('n must be at least 1')
+
+ children = tee(iterable, n)
+ return [islice(it, index, None, n) for index, it in enumerate(children)]
+
+
+def stagger(iterable, offsets=(-1, 0, 1), longest=False, fillvalue=None):
+ """Yield tuples whose elements are offset from *iterable*.
+ The amount by which the `i`-th item in each tuple is offset is given by
+ the `i`-th item in *offsets*.
+
+ >>> list(stagger([0, 1, 2, 3]))
+ [(None, 0, 1), (0, 1, 2), (1, 2, 3)]
+ >>> list(stagger(range(8), offsets=(0, 2, 4)))
+ [(0, 2, 4), (1, 3, 5), (2, 4, 6), (3, 5, 7)]
+
+ By default, the sequence will end when the final element of a tuple is the
+ last item in the iterable. To continue until the first element of a tuple
+ is the last item in the iterable, set *longest* to ``True``::
+
+ >>> list(stagger([0, 1, 2, 3], longest=True))
+ [(None, 0, 1), (0, 1, 2), (1, 2, 3), (2, 3, None), (3, None, None)]
+
+ By default, ``None`` will be used to replace offsets beyond the end of the
+ sequence. Specify *fillvalue* to use some other value.
+
+ """
+ children = tee(iterable, len(offsets))
+
+ return zip_offset(
+ *children, offsets=offsets, longest=longest, fillvalue=fillvalue
+ )
+
+
+def zip_offset(*iterables, **kwargs):
+ """``zip`` the input *iterables* together, but offset the `i`-th iterable
+ by the `i`-th item in *offsets*.
+
+ >>> list(zip_offset('0123', 'abcdef', offsets=(0, 1)))
+ [('0', 'b'), ('1', 'c'), ('2', 'd'), ('3', 'e')]
+
+ This can be used as a lightweight alternative to SciPy or pandas to analyze
+ data sets in which somes series have a lead or lag relationship.
+
+ By default, the sequence will end when the shortest iterable is exhausted.
+ To continue until the longest iterable is exhausted, set *longest* to
+ ``True``.
+
+ >>> list(zip_offset('0123', 'abcdef', offsets=(0, 1), longest=True))
+ [('0', 'b'), ('1', 'c'), ('2', 'd'), ('3', 'e'), (None, 'f')]
+
+ By default, ``None`` will be used to replace offsets beyond the end of the
+ sequence. Specify *fillvalue* to use some other value.
+
+ """
+ offsets = kwargs['offsets']
+ longest = kwargs.get('longest', False)
+ fillvalue = kwargs.get('fillvalue', None)
+
+ if len(iterables) != len(offsets):
+ raise ValueError("Number of iterables and offsets didn't match")
+
+ staggered = []
+ for it, n in zip(iterables, offsets):
+ if n < 0:
+ staggered.append(chain(repeat(fillvalue, -n), it))
+ elif n > 0:
+ staggered.append(islice(it, n, None))
+ else:
+ staggered.append(it)
+
+ if longest:
+ return zip_longest(*staggered, fillvalue=fillvalue)
+
+ return zip(*staggered)
+
+
+def sort_together(iterables, key_list=(0,), reverse=False):
+ """Return the input iterables sorted together, with *key_list* as the
+ priority for sorting. All iterables are trimmed to the length of the
+ shortest one.
+
+ This can be used like the sorting function in a spreadsheet. If each
+ iterable represents a column of data, the key list determines which
+ columns are used for sorting.
+
+ By default, all iterables are sorted using the ``0``-th iterable::
+
+ >>> iterables = [(4, 3, 2, 1), ('a', 'b', 'c', 'd')]
+ >>> sort_together(iterables)
+ [(1, 2, 3, 4), ('d', 'c', 'b', 'a')]
+
+ Set a different key list to sort according to another iterable.
+ Specifying mutliple keys dictates how ties are broken::
+
+ >>> iterables = [(3, 1, 2), (0, 1, 0), ('c', 'b', 'a')]
+ >>> sort_together(iterables, key_list=(1, 2))
+ [(2, 3, 1), (0, 0, 1), ('a', 'c', 'b')]
+
+ Set *reverse* to ``True`` to sort in descending order.
+
+ >>> sort_together([(1, 2, 3), ('c', 'b', 'a')], reverse=True)
+ [(3, 2, 1), ('a', 'b', 'c')]
+
+ """
+ return list(zip(*sorted(zip(*iterables),
+ key=itemgetter(*key_list),
+ reverse=reverse)))
+
+
+def divide(n, iterable):
+ """Divide the elements from *iterable* into *n* parts, maintaining
+ order.
+
+ >>> group_1, group_2 = divide(2, [1, 2, 3, 4, 5, 6])
+ >>> list(group_1)
+ [1, 2, 3]
+ >>> list(group_2)
+ [4, 5, 6]
+
+ If the length of *iterable* is not evenly divisible by *n*, then the
+ length of the returned iterables will not be identical:
+
+ >>> children = divide(3, [1, 2, 3, 4, 5, 6, 7])
+ >>> [list(c) for c in children]
+ [[1, 2, 3], [4, 5], [6, 7]]
+
+ If the length of the iterable is smaller than n, then the last returned
+ iterables will be empty:
+
+ >>> children = divide(5, [1, 2, 3])
+ >>> [list(c) for c in children]
+ [[1], [2], [3], [], []]
+
+ This function will exhaust the iterable before returning and may require
+ significant storage. If order is not important, see :func:`distribute`,
+ which does not first pull the iterable into memory.
+
+ """
+ if n < 1:
+ raise ValueError('n must be at least 1')
+
+ seq = tuple(iterable)
+ q, r = divmod(len(seq), n)
+
+ ret = []
+ for i in range(n):
+ start = (i * q) + (i if i < r else r)
+ stop = ((i + 1) * q) + (i + 1 if i + 1 < r else r)
+ ret.append(iter(seq[start:stop]))
+
+ return ret
+
+
+def always_iterable(obj, base_type=(text_type, binary_type)):
+ """If *obj* is iterable, return an iterator over its items::
+
+ >>> obj = (1, 2, 3)
+ >>> list(always_iterable(obj))
+ [1, 2, 3]
+
+ If *obj* is not iterable, return a one-item iterable containing *obj*::
+
+ >>> obj = 1
+ >>> list(always_iterable(obj))
+ [1]
+
+ If *obj* is ``None``, return an empty iterable:
+
+ >>> obj = None
+ >>> list(always_iterable(None))
+ []
+
+ By default, binary and text strings are not considered iterable::
+
+ >>> obj = 'foo'
+ >>> list(always_iterable(obj))
+ ['foo']
+
+ If *base_type* is set, objects for which ``isinstance(obj, base_type)``
+ returns ``True`` won't be considered iterable.
+
+ >>> obj = {'a': 1}
+ >>> list(always_iterable(obj)) # Iterate over the dict's keys
+ ['a']
+ >>> list(always_iterable(obj, base_type=dict)) # Treat dicts as a unit
+ [{'a': 1}]
+
+ Set *base_type* to ``None`` to avoid any special handling and treat objects
+ Python considers iterable as iterable:
+
+ >>> obj = 'foo'
+ >>> list(always_iterable(obj, base_type=None))
+ ['f', 'o', 'o']
+ """
+ if obj is None:
+ return iter(())
+
+ if (base_type is not None) and isinstance(obj, base_type):
+ return iter((obj,))
+
+ try:
+ return iter(obj)
+ except TypeError:
+ return iter((obj,))
+
+
+def adjacent(predicate, iterable, distance=1):
+ """Return an iterable over `(bool, item)` tuples where the `item` is
+ drawn from *iterable* and the `bool` indicates whether
+ that item satisfies the *predicate* or is adjacent to an item that does.
+
+ For example, to find whether items are adjacent to a ``3``::
+
+ >>> list(adjacent(lambda x: x == 3, range(6)))
+ [(False, 0), (False, 1), (True, 2), (True, 3), (True, 4), (False, 5)]
+
+ Set *distance* to change what counts as adjacent. For example, to find
+ whether items are two places away from a ``3``:
+
+ >>> list(adjacent(lambda x: x == 3, range(6), distance=2))
+ [(False, 0), (True, 1), (True, 2), (True, 3), (True, 4), (True, 5)]
+
+ This is useful for contextualizing the results of a search function.
+ For example, a code comparison tool might want to identify lines that
+ have changed, but also surrounding lines to give the viewer of the diff
+ context.
+
+ The predicate function will only be called once for each item in the
+ iterable.
+
+ See also :func:`groupby_transform`, which can be used with this function
+ to group ranges of items with the same `bool` value.
+
+ """
+ # Allow distance=0 mainly for testing that it reproduces results with map()
+ if distance < 0:
+ raise ValueError('distance must be at least 0')
+
+ i1, i2 = tee(iterable)
+ padding = [False] * distance
+ selected = chain(padding, map(predicate, i1), padding)
+ adjacent_to_selected = map(any, windowed(selected, 2 * distance + 1))
+ return zip(adjacent_to_selected, i2)
+
+
+def groupby_transform(iterable, keyfunc=None, valuefunc=None):
+ """An extension of :func:`itertools.groupby` that transforms the values of
+ *iterable* after grouping them.
+ *keyfunc* is a function used to compute a grouping key for each item.
+ *valuefunc* is a function for transforming the items after grouping.
+
+ >>> iterable = 'AaaABbBCcA'
+ >>> keyfunc = lambda x: x.upper()
+ >>> valuefunc = lambda x: x.lower()
+ >>> grouper = groupby_transform(iterable, keyfunc, valuefunc)
+ >>> [(k, ''.join(g)) for k, g in grouper]
+ [('A', 'aaaa'), ('B', 'bbb'), ('C', 'cc'), ('A', 'a')]
+
+ *keyfunc* and *valuefunc* default to identity functions if they are not
+ specified.
+
+ :func:`groupby_transform` is useful when grouping elements of an iterable
+ using a separate iterable as the key. To do this, :func:`zip` the iterables
+ and pass a *keyfunc* that extracts the first element and a *valuefunc*
+ that extracts the second element::
+
+ >>> from operator import itemgetter
+ >>> keys = [0, 0, 1, 1, 1, 2, 2, 2, 3]
+ >>> values = 'abcdefghi'
+ >>> iterable = zip(keys, values)
+ >>> grouper = groupby_transform(iterable, itemgetter(0), itemgetter(1))
+ >>> [(k, ''.join(g)) for k, g in grouper]
+ [(0, 'ab'), (1, 'cde'), (2, 'fgh'), (3, 'i')]
+
+ Note that the order of items in the iterable is significant.
+ Only adjacent items are grouped together, so if you don't want any
+ duplicate groups, you should sort the iterable by the key function.
+
+ """
+ valuefunc = (lambda x: x) if valuefunc is None else valuefunc
+ return ((k, map(valuefunc, g)) for k, g in groupby(iterable, keyfunc))
+
+
+def numeric_range(*args):
+ """An extension of the built-in ``range()`` function whose arguments can
+ be any orderable numeric type.
+
+ With only *stop* specified, *start* defaults to ``0`` and *step*
+ defaults to ``1``. The output items will match the type of *stop*:
+
+ >>> list(numeric_range(3.5))
+ [0.0, 1.0, 2.0, 3.0]
+
+ With only *start* and *stop* specified, *step* defaults to ``1``. The
+ output items will match the type of *start*:
+
+ >>> from decimal import Decimal
+ >>> start = Decimal('2.1')
+ >>> stop = Decimal('5.1')
+ >>> list(numeric_range(start, stop))
+ [Decimal('2.1'), Decimal('3.1'), Decimal('4.1')]
+
+ With *start*, *stop*, and *step* specified the output items will match
+ the type of ``start + step``:
+
+ >>> from fractions import Fraction
+ >>> start = Fraction(1, 2) # Start at 1/2
+ >>> stop = Fraction(5, 2) # End at 5/2
+ >>> step = Fraction(1, 2) # Count by 1/2
+ >>> list(numeric_range(start, stop, step))
+ [Fraction(1, 2), Fraction(1, 1), Fraction(3, 2), Fraction(2, 1)]
+
+ If *step* is zero, ``ValueError`` is raised. Negative steps are supported:
+
+ >>> list(numeric_range(3, -1, -1.0))
+ [3.0, 2.0, 1.0, 0.0]
+
+ Be aware of the limitations of floating point numbers; the representation
+ of the yielded numbers may be surprising.
+
+ """
+ argc = len(args)
+ if argc == 1:
+ stop, = args
+ start = type(stop)(0)
+ step = 1
+ elif argc == 2:
+ start, stop = args
+ step = 1
+ elif argc == 3:
+ start, stop, step = args
+ else:
+ err_msg = 'numeric_range takes at most 3 arguments, got {}'
+ raise TypeError(err_msg.format(argc))
+
+ values = (start + (step * n) for n in count())
+ if step > 0:
+ return takewhile(partial(gt, stop), values)
+ elif step < 0:
+ return takewhile(partial(lt, stop), values)
+ else:
+ raise ValueError('numeric_range arg 3 must not be zero')
+
+
+def count_cycle(iterable, n=None):
+ """Cycle through the items from *iterable* up to *n* times, yielding
+ the number of completed cycles along with each item. If *n* is omitted the
+ process repeats indefinitely.
+
+ >>> list(count_cycle('AB', 3))
+ [(0, 'A'), (0, 'B'), (1, 'A'), (1, 'B'), (2, 'A'), (2, 'B')]
+
+ """
+ iterable = tuple(iterable)
+ if not iterable:
+ return iter(())
+ counter = count() if n is None else range(n)
+ return ((i, item) for i in counter for item in iterable)
+
+
+def locate(iterable, pred=bool):
+ """Yield the index of each item in *iterable* for which *pred* returns
+ ``True``.
+
+ *pred* defaults to :func:`bool`, which will select truthy items:
+
+ >>> list(locate([0, 1, 1, 0, 1, 0, 0]))
+ [1, 2, 4]
+
+ Set *pred* to a custom function to, e.g., find the indexes for a particular
+ item:
+
+ >>> list(locate(['a', 'b', 'c', 'b'], lambda x: x == 'b'))
+ [1, 3]
+
+ Use with :func:`windowed` to find the indexes of a sub-sequence:
+
+ >>> from more_itertools import windowed
+ >>> iterable = [0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3]
+ >>> sub = [1, 2, 3]
+ >>> pred = lambda w: w == tuple(sub) # windowed() returns tuples
+ >>> list(locate(windowed(iterable, len(sub)), pred=pred))
+ [1, 5, 9]
+
+ Use with :func:`seekable` to find indexes and then retrieve the associated
+ items:
+
+ >>> from itertools import count
+ >>> from more_itertools import seekable
+ >>> source = (3 * n + 1 if (n % 2) else n // 2 for n in count())
+ >>> it = seekable(source)
+ >>> pred = lambda x: x > 100
+ >>> indexes = locate(it, pred=pred)
+ >>> i = next(indexes)
+ >>> it.seek(i)
+ >>> next(it)
+ 106
+
+ """
+ return compress(count(), map(pred, iterable))
+
+
+def lstrip(iterable, pred):
+ """Yield the items from *iterable*, but strip any from the beginning
+ for which *pred* returns ``True``.
+
+ For example, to remove a set of items from the start of an iterable:
+
+ >>> iterable = (None, False, None, 1, 2, None, 3, False, None)
+ >>> pred = lambda x: x in {None, False, ''}
+ >>> list(lstrip(iterable, pred))
+ [1, 2, None, 3, False, None]
+
+ This function is analogous to to :func:`str.lstrip`, and is essentially
+ an wrapper for :func:`itertools.dropwhile`.
+
+ """
+ return dropwhile(pred, iterable)
+
+
+def rstrip(iterable, pred):
+ """Yield the items from *iterable*, but strip any from the end
+ for which *pred* returns ``True``.
+
+ For example, to remove a set of items from the end of an iterable:
+
+ >>> iterable = (None, False, None, 1, 2, None, 3, False, None)
+ >>> pred = lambda x: x in {None, False, ''}
+ >>> list(rstrip(iterable, pred))
+ [None, False, None, 1, 2, None, 3]
+
+ This function is analogous to :func:`str.rstrip`.
+
+ """
+ cache = []
+ cache_append = cache.append
+ for x in iterable:
+ if pred(x):
+ cache_append(x)
+ else:
+ for y in cache:
+ yield y
+ del cache[:]
+ yield x
+
+
+def strip(iterable, pred):
+ """Yield the items from *iterable*, but strip any from the
+ beginning and end for which *pred* returns ``True``.
+
+ For example, to remove a set of items from both ends of an iterable:
+
+ >>> iterable = (None, False, None, 1, 2, None, 3, False, None)
+ >>> pred = lambda x: x in {None, False, ''}
+ >>> list(strip(iterable, pred))
+ [1, 2, None, 3]
+
+ This function is analogous to :func:`str.strip`.
+
+ """
+ return rstrip(lstrip(iterable, pred), pred)
+
+
+def islice_extended(iterable, *args):
+ """An extension of :func:`itertools.islice` that supports negative values
+ for *stop*, *start*, and *step*.
+
+ >>> iterable = iter('abcdefgh')
+ >>> list(islice_extended(iterable, -4, -1))
+ ['e', 'f', 'g']
+
+ Slices with negative values require some caching of *iterable*, but this
+ function takes care to minimize the amount of memory required.
+
+ For example, you can use a negative step with an infinite iterator:
+
+ >>> from itertools import count
+ >>> list(islice_extended(count(), 110, 99, -2))
+ [110, 108, 106, 104, 102, 100]
+
+ """
+ s = slice(*args)
+ start = s.start
+ stop = s.stop
+ if s.step == 0:
+ raise ValueError('step argument must be a non-zero integer or None.')
+ step = s.step or 1
+
+ it = iter(iterable)
+
+ if step > 0:
+ start = 0 if (start is None) else start
+
+ if (start < 0):
+ # Consume all but the last -start items
+ cache = deque(enumerate(it, 1), maxlen=-start)
+ len_iter = cache[-1][0] if cache else 0
+
+ # Adjust start to be positive
+ i = max(len_iter + start, 0)
+
+ # Adjust stop to be positive
+ if stop is None:
+ j = len_iter
+ elif stop >= 0:
+ j = min(stop, len_iter)
+ else:
+ j = max(len_iter + stop, 0)
+
+ # Slice the cache
+ n = j - i
+ if n <= 0:
+ return
+
+ for index, item in islice(cache, 0, n, step):
+ yield item
+ elif (stop is not None) and (stop < 0):
+ # Advance to the start position
+ next(islice(it, start, start), None)
+
+ # When stop is negative, we have to carry -stop items while
+ # iterating
+ cache = deque(islice(it, -stop), maxlen=-stop)
+
+ for index, item in enumerate(it):
+ cached_item = cache.popleft()
+ if index % step == 0:
+ yield cached_item
+ cache.append(item)
+ else:
+ # When both start and stop are positive we have the normal case
+ for item in islice(it, start, stop, step):
+ yield item
+ else:
+ start = -1 if (start is None) else start
+
+ if (stop is not None) and (stop < 0):
+ # Consume all but the last items
+ n = -stop - 1
+ cache = deque(enumerate(it, 1), maxlen=n)
+ len_iter = cache[-1][0] if cache else 0
+
+ # If start and stop are both negative they are comparable and
+ # we can just slice. Otherwise we can adjust start to be negative
+ # and then slice.
+ if start < 0:
+ i, j = start, stop
+ else:
+ i, j = min(start - len_iter, -1), None
+
+ for index, item in list(cache)[i:j:step]:
+ yield item
+ else:
+ # Advance to the stop position
+ if stop is not None:
+ m = stop + 1
+ next(islice(it, m, m), None)
+
+ # stop is positive, so if start is negative they are not comparable
+ # and we need the rest of the items.
+ if start < 0:
+ i = start
+ n = None
+ # stop is None and start is positive, so we just need items up to
+ # the start index.
+ elif stop is None:
+ i = None
+ n = start + 1
+ # Both stop and start are positive, so they are comparable.
+ else:
+ i = None
+ n = start - stop
+ if n <= 0:
+ return
+
+ cache = list(islice(it, n))
+
+ for item in cache[i::step]:
+ yield item
+
+
+def always_reversible(iterable):
+ """An extension of :func:`reversed` that supports all iterables, not
+ just those which implement the ``Reversible`` or ``Sequence`` protocols.
+
+ >>> print(*always_reversible(x for x in range(3)))
+ 2 1 0
+
+ If the iterable is already reversible, this function returns the
+ result of :func:`reversed()`. If the iterable is not reversible,
+ this function will cache the remaining items in the iterable and
+ yield them in reverse order, which may require significant storage.
+ """
+ try:
+ return reversed(iterable)
+ except TypeError:
+ return reversed(list(iterable))
+
+
+def consecutive_groups(iterable, ordering=lambda x: x):
+ """Yield groups of consecutive items using :func:`itertools.groupby`.
+ The *ordering* function determines whether two items are adjacent by
+ returning their position.
+
+ By default, the ordering function is the identity function. This is
+ suitable for finding runs of numbers:
+
+ >>> iterable = [1, 10, 11, 12, 20, 30, 31, 32, 33, 40]
+ >>> for group in consecutive_groups(iterable):
+ ... print(list(group))
+ [1]
+ [10, 11, 12]
+ [20]
+ [30, 31, 32, 33]
+ [40]
+
+ For finding runs of adjacent letters, try using the :meth:`index` method
+ of a string of letters:
+
+ >>> from string import ascii_lowercase
+ >>> iterable = 'abcdfgilmnop'
+ >>> ordering = ascii_lowercase.index
+ >>> for group in consecutive_groups(iterable, ordering):
+ ... print(list(group))
+ ['a', 'b', 'c', 'd']
+ ['f', 'g']
+ ['i']
+ ['l', 'm', 'n', 'o', 'p']
+
+ """
+ for k, g in groupby(
+ enumerate(iterable), key=lambda x: x[0] - ordering(x[1])
+ ):
+ yield map(itemgetter(1), g)
+
+
+def difference(iterable, func=sub):
+ """By default, compute the first difference of *iterable* using
+ :func:`operator.sub`.
+
+ >>> iterable = [0, 1, 3, 6, 10]
+ >>> list(difference(iterable))
+ [0, 1, 2, 3, 4]
+
+ This is the opposite of :func:`accumulate`'s default behavior:
+
+ >>> from more_itertools import accumulate
+ >>> iterable = [0, 1, 2, 3, 4]
+ >>> list(accumulate(iterable))
+ [0, 1, 3, 6, 10]
+ >>> list(difference(accumulate(iterable)))
+ [0, 1, 2, 3, 4]
+
+ By default *func* is :func:`operator.sub`, but other functions can be
+ specified. They will be applied as follows::
+
+ A, B, C, D, ... --> A, func(B, A), func(C, B), func(D, C), ...
+
+ For example, to do progressive division:
+
+ >>> iterable = [1, 2, 6, 24, 120] # Factorial sequence
+ >>> func = lambda x, y: x // y
+ >>> list(difference(iterable, func))
+ [1, 2, 3, 4, 5]
+
+ """
+ a, b = tee(iterable)
+ try:
+ item = next(b)
+ except StopIteration:
+ return iter([])
+ return chain([item], map(lambda x: func(x[1], x[0]), zip(a, b)))
+
+
+class SequenceView(Sequence):
+ """Return a read-only view of the sequence object *target*.
+
+ :class:`SequenceView` objects are analagous to Python's built-in
+ "dictionary view" types. They provide a dynamic view of a sequence's items,
+ meaning that when the sequence updates, so does the view.
+
+ >>> seq = ['0', '1', '2']
+ >>> view = SequenceView(seq)
+ >>> view
+ SequenceView(['0', '1', '2'])
+ >>> seq.append('3')
+ >>> view
+ SequenceView(['0', '1', '2', '3'])
+
+ Sequence views support indexing, slicing, and length queries. They act
+ like the underlying sequence, except they don't allow assignment:
+
+ >>> view[1]
+ '1'
+ >>> view[1:-1]
+ ['1', '2']
+ >>> len(view)
+ 4
+
+ Sequence views are useful as an alternative to copying, as they don't
+ require (much) extra storage.
+
+ """
+ def __init__(self, target):
+ if not isinstance(target, Sequence):
+ raise TypeError
+ self._target = target
+
+ def __getitem__(self, index):
+ return self._target[index]
+
+ def __len__(self):
+ return len(self._target)
+
+ def __repr__(self):
+ return '{}({})'.format(self.__class__.__name__, repr(self._target))
+
+
+class seekable(object):
+ """Wrap an iterator to allow for seeking backward and forward. This
+ progressively caches the items in the source iterable so they can be
+ re-visited.
+
+ Call :meth:`seek` with an index to seek to that position in the source
+ iterable.
+
+ To "reset" an iterator, seek to ``0``:
+
+ >>> from itertools import count
+ >>> it = seekable((str(n) for n in count()))
+ >>> next(it), next(it), next(it)
+ ('0', '1', '2')
+ >>> it.seek(0)
+ >>> next(it), next(it), next(it)
+ ('0', '1', '2')
+ >>> next(it)
+ '3'
+
+ You can also seek forward:
+
+ >>> it = seekable((str(n) for n in range(20)))
+ >>> it.seek(10)
+ >>> next(it)
+ '10'
+ >>> it.seek(20) # Seeking past the end of the source isn't a problem
+ >>> list(it)
+ []
+ >>> it.seek(0) # Resetting works even after hitting the end
+ >>> next(it), next(it), next(it)
+ ('0', '1', '2')
+
+ The cache grows as the source iterable progresses, so beware of wrapping
+ very large or infinite iterables.
+
+ You may view the contents of the cache with the :meth:`elements` method.
+ That returns a :class:`SequenceView`, a view that updates automatically:
+
+ >>> it = seekable((str(n) for n in range(10)))
+ >>> next(it), next(it), next(it)
+ ('0', '1', '2')
+ >>> elements = it.elements()
+ >>> elements
+ SequenceView(['0', '1', '2'])
+ >>> next(it)
+ '3'
+ >>> elements
+ SequenceView(['0', '1', '2', '3'])
+
+ """
+
+ def __init__(self, iterable):
+ self._source = iter(iterable)
+ self._cache = []
+ self._index = None
+
+ def __iter__(self):
+ return self
+
+ def __next__(self):
+ if self._index is not None:
+ try:
+ item = self._cache[self._index]
+ except IndexError:
+ self._index = None
+ else:
+ self._index += 1
+ return item
+
+ item = next(self._source)
+ self._cache.append(item)
+ return item
+
+ next = __next__
+
+ def elements(self):
+ return SequenceView(self._cache)
+
+ def seek(self, index):
+ self._index = index
+ remainder = index - len(self._cache)
+ if remainder > 0:
+ consume(self, remainder)
+
+
+class run_length(object):
+ """
+ :func:`run_length.encode` compresses an iterable with run-length encoding.
+ It yields groups of repeated items with the count of how many times they
+ were repeated:
+
+ >>> uncompressed = 'abbcccdddd'
+ >>> list(run_length.encode(uncompressed))
+ [('a', 1), ('b', 2), ('c', 3), ('d', 4)]
+
+ :func:`run_length.decode` decompresses an iterable that was previously
+ compressed with run-length encoding. It yields the items of the
+ decompressed iterable:
+
+ >>> compressed = [('a', 1), ('b', 2), ('c', 3), ('d', 4)]
+ >>> list(run_length.decode(compressed))
+ ['a', 'b', 'b', 'c', 'c', 'c', 'd', 'd', 'd', 'd']
+
+ """
+
+ @staticmethod
+ def encode(iterable):
+ return ((k, ilen(g)) for k, g in groupby(iterable))
+
+ @staticmethod
+ def decode(iterable):
+ return chain.from_iterable(repeat(k, n) for k, n in iterable)
+
+
+def exactly_n(iterable, n, predicate=bool):
+ """Return ``True`` if exactly ``n`` items in the iterable are ``True``
+ according to the *predicate* function.
+
+ >>> exactly_n([True, True, False], 2)
+ True
+ >>> exactly_n([True, True, False], 1)
+ False
+ >>> exactly_n([0, 1, 2, 3, 4, 5], 3, lambda x: x < 3)
+ True
+
+ The iterable will be advanced until ``n + 1`` truthy items are encountered,
+ so avoid calling it on infinite iterables.
+
+ """
+ return len(take(n + 1, filter(predicate, iterable))) == n
+
+
+def circular_shifts(iterable):
+ """Return a list of circular shifts of *iterable*.
+
+ >>> circular_shifts(range(4))
+ [(0, 1, 2, 3), (1, 2, 3, 0), (2, 3, 0, 1), (3, 0, 1, 2)]
+ """
+ lst = list(iterable)
+ return take(len(lst), windowed(cycle(lst), len(lst)))
+
+
+def make_decorator(wrapping_func, result_index=0):
+ """Return a decorator version of *wrapping_func*, which is a function that
+ modifies an iterable. *result_index* is the position in that function's
+ signature where the iterable goes.
+
+ This lets you use itertools on the "production end," i.e. at function
+ definition. This can augment what the function returns without changing the
+ function's code.
+
+ For example, to produce a decorator version of :func:`chunked`:
+
+ >>> from more_itertools import chunked
+ >>> chunker = make_decorator(chunked, result_index=0)
+ >>> @chunker(3)
+ ... def iter_range(n):
+ ... return iter(range(n))
+ ...
+ >>> list(iter_range(9))
+ [[0, 1, 2], [3, 4, 5], [6, 7, 8]]
+
+ To only allow truthy items to be returned:
+
+ >>> truth_serum = make_decorator(filter, result_index=1)
+ >>> @truth_serum(bool)
+ ... def boolean_test():
+ ... return [0, 1, '', ' ', False, True]
+ ...
+ >>> list(boolean_test())
+ [1, ' ', True]
+
+ The :func:`peekable` and :func:`seekable` wrappers make for practical
+ decorators:
+
+ >>> from more_itertools import peekable
+ >>> peekable_function = make_decorator(peekable)
+ >>> @peekable_function()
+ ... def str_range(*args):
+ ... return (str(x) for x in range(*args))
+ ...
+ >>> it = str_range(1, 20, 2)
+ >>> next(it), next(it), next(it)
+ ('1', '3', '5')
+ >>> it.peek()
+ '7'
+ >>> next(it)
+ '7'
+
+ """
+ # See https://sites.google.com/site/bbayles/index/decorator_factory for
+ # notes on how this works.
+ def decorator(*wrapping_args, **wrapping_kwargs):
+ def outer_wrapper(f):
+ def inner_wrapper(*args, **kwargs):
+ result = f(*args, **kwargs)
+ wrapping_args_ = list(wrapping_args)
+ wrapping_args_.insert(result_index, result)
+ return wrapping_func(*wrapping_args_, **wrapping_kwargs)
+
+ return inner_wrapper
+
+ return outer_wrapper
+
+ return decorator
+
+
+def map_reduce(iterable, keyfunc, valuefunc=None, reducefunc=None):
+ """Return a dictionary that maps the items in *iterable* to categories
+ defined by *keyfunc*, transforms them with *valuefunc*, and
+ then summarizes them by category with *reducefunc*.
+
+ *valuefunc* defaults to the identity function if it is unspecified.
+ If *reducefunc* is unspecified, no summarization takes place:
+
+ >>> keyfunc = lambda x: x.upper()
+ >>> result = map_reduce('abbccc', keyfunc)
+ >>> sorted(result.items())
+ [('A', ['a']), ('B', ['b', 'b']), ('C', ['c', 'c', 'c'])]
+
+ Specifying *valuefunc* transforms the categorized items:
+
+ >>> keyfunc = lambda x: x.upper()
+ >>> valuefunc = lambda x: 1
+ >>> result = map_reduce('abbccc', keyfunc, valuefunc)
+ >>> sorted(result.items())
+ [('A', [1]), ('B', [1, 1]), ('C', [1, 1, 1])]
+
+ Specifying *reducefunc* summarizes the categorized items:
+
+ >>> keyfunc = lambda x: x.upper()
+ >>> valuefunc = lambda x: 1
+ >>> reducefunc = sum
+ >>> result = map_reduce('abbccc', keyfunc, valuefunc, reducefunc)
+ >>> sorted(result.items())
+ [('A', 1), ('B', 2), ('C', 3)]
+
+ You may want to filter the input iterable before applying the map/reduce
+ proecdure:
+
+ >>> all_items = range(30)
+ >>> items = [x for x in all_items if 10 <= x <= 20] # Filter
+ >>> keyfunc = lambda x: x % 2 # Evens map to 0; odds to 1
+ >>> categories = map_reduce(items, keyfunc=keyfunc)
+ >>> sorted(categories.items())
+ [(0, [10, 12, 14, 16, 18, 20]), (1, [11, 13, 15, 17, 19])]
+ >>> summaries = map_reduce(items, keyfunc=keyfunc, reducefunc=sum)
+ >>> sorted(summaries.items())
+ [(0, 90), (1, 75)]
+
+ Note that all items in the iterable are gathered into a list before the
+ summarization step, which may require significant storage.
+
+ The returned object is a :obj:`collections.defaultdict` with the
+ ``default_factory`` set to ``None``, such that it behaves like a normal
+ dictionary.
+
+ """
+ valuefunc = (lambda x: x) if (valuefunc is None) else valuefunc
+
+ ret = defaultdict(list)
+ for item in iterable:
+ key = keyfunc(item)
+ value = valuefunc(item)
+ ret[key].append(value)
+
+ if reducefunc is not None:
+ for key, value_list in ret.items():
+ ret[key] = reducefunc(value_list)
+
+ ret.default_factory = None
+ return ret
new file mode 100644
--- /dev/null
+++ b/testing/web-platform/tests/tools/third_party/more-itertools/more_itertools/recipes.py
@@ -0,0 +1,565 @@
+"""Imported from the recipes section of the itertools documentation.
+
+All functions taken from the recipes section of the itertools library docs
+[1]_.
+Some backward-compatible usability improvements have been made.
+
+.. [1] http://docs.python.org/library/itertools.html#recipes
+
+"""
+from collections import deque
+from itertools import (
+ chain, combinations, count, cycle, groupby, islice, repeat, starmap, tee
+)
+import operator
+from random import randrange, sample, choice
+
+from six import PY2
+from six.moves import filter, filterfalse, map, range, zip, zip_longest
+
+__all__ = [
+ 'accumulate',
+ 'all_equal',
+ 'consume',
+ 'dotproduct',
+ 'first_true',
+ 'flatten',
+ 'grouper',
+ 'iter_except',
+ 'ncycles',
+ 'nth',
+ 'nth_combination',
+ 'padnone',
+ 'pairwise',
+ 'partition',
+ 'powerset',
+ 'prepend',
+ 'quantify',
+ 'random_combination_with_replacement',
+ 'random_combination',
+ 'random_permutation',
+ 'random_product',
+ 'repeatfunc',
+ 'roundrobin',
+ 'tabulate',
+ 'tail',
+ 'take',
+ 'unique_everseen',
+ 'unique_justseen',
+]
+
+
+def accumulate(iterable, func=operator.add):
+ """
+ Return an iterator whose items are the accumulated results of a function
+ (specified by the optional *func* argument) that takes two arguments.
+ By default, returns accumulated sums with :func:`operator.add`.
+
+ >>> list(accumulate([1, 2, 3, 4, 5])) # Running sum
+ [1, 3, 6, 10, 15]
+ >>> list(accumulate([1, 2, 3], func=operator.mul)) # Running product
+ [1, 2, 6]
+ >>> list(accumulate([0, 1, -1, 2, 3, 2], func=max)) # Running maximum
+ [0, 1, 1, 2, 3, 3]
+
+ This function is available in the ``itertools`` module for Python 3.2 and
+ greater.
+
+ """
+ it = iter(iterable)
+ try:
+ total = next(it)
+ except StopIteration:
+ return
+ else:
+ yield total
+
+ for element in it:
+ total = func(total, element)
+ yield total
+
+
+def take(n, iterable):
+ """Return first *n* items of the iterable as a list.
+
+ >>> take(3, range(10))
+ [0, 1, 2]
+ >>> take(5, range(3))
+ [0, 1, 2]
+
+ Effectively a short replacement for ``next`` based iterator consumption
+ when you want more than one item, but less than the whole iterator.
+
+ """
+ return list(islice(iterable, n))
+
+
+def tabulate(function, start=0):
+ """Return an iterator over the results of ``func(start)``,
+ ``func(start + 1)``, ``func(start + 2)``...
+
+ *func* should be a function that accepts one integer argument.
+
+ If *start* is not specified it defaults to 0. It will be incremented each
+ time the iterator is advanced.
+
+ >>> square = lambda x: x ** 2
+ >>> iterator = tabulate(square, -3)
+ >>> take(4, iterator)
+ [9, 4, 1, 0]
+
+ """
+ return map(function, count(start))
+
+
+def tail(n, iterable):
+ """Return an iterator over the last *n* items of *iterable*.
+
+ >>> t = tail(3, 'ABCDEFG')
+ >>> list(t)
+ ['E', 'F', 'G']
+
+ """
+ return iter(deque(iterable, maxlen=n))
+
+
+def consume(iterator, n=None):
+ """Advance *iterable* by *n* steps. If *n* is ``None``, consume it
+ entirely.
+
+ Efficiently exhausts an iterator without returning values. Defaults to
+ consuming the whole iterator, but an optional second argument may be
+ provided to limit consumption.
+
+ >>> i = (x for x in range(10))
+ >>> next(i)
+ 0
+ >>> consume(i, 3)
+ >>> next(i)
+ 4
+ >>> consume(i)
+ >>> next(i)
+ Traceback (most recent call last):
+ File "<stdin>", line 1, in <module>
+ StopIteration
+
+ If the iterator has fewer items remaining than the provided limit, the
+ whole iterator will be consumed.
+
+ >>> i = (x for x in range(3))
+ >>> consume(i, 5)
+ >>> next(i)
+ Traceback (most recent call last):
+ File "<stdin>", line 1, in <module>
+ StopIteration
+
+ """
+ # Use functions that consume iterators at C speed.
+ if n is None:
+ # feed the entire iterator into a zero-length deque
+ deque(iterator, maxlen=0)
+ else:
+ # advance to the empty slice starting at position n
+ next(islice(iterator, n, n), None)
+
+
+def nth(iterable, n, default=None):
+ """Returns the nth item or a default value.
+
+ >>> l = range(10)
+ >>> nth(l, 3)
+ 3
+ >>> nth(l, 20, "zebra")
+ 'zebra'
+
+ """
+ return next(islice(iterable, n, None), default)
+
+
+def all_equal(iterable):
+ """
+ Returns ``True`` if all the elements are equal to each other.
+
+ >>> all_equal('aaaa')
+ True
+ >>> all_equal('aaab')
+ False
+
+ """
+ g = groupby(iterable)
+ return next(g, True) and not next(g, False)
+
+
+def quantify(iterable, pred=bool):
+ """Return the how many times the predicate is true.
+
+ >>> quantify([True, False, True])
+ 2
+
+ """
+ return sum(map(pred, iterable))
+
+
+def padnone(iterable):
+ """Returns the sequence of elements and then returns ``None`` indefinitely.
+
+ >>> take(5, padnone(range(3)))
+ [0, 1, 2, None, None]
+
+ Useful for emulating the behavior of the built-in :func:`map` function.
+
+ See also :func:`padded`.
+
+ """
+ return chain(iterable, repeat(None))
+
+
+def ncycles(iterable, n):
+ """Returns the sequence elements *n* times
+
+ >>> list(ncycles(["a", "b"], 3))
+ ['a', 'b', 'a', 'b', 'a', 'b']
+
+ """
+ return chain.from_iterable(repeat(tuple(iterable), n))
+
+
+def dotproduct(vec1, vec2):
+ """Returns the dot product of the two iterables.
+
+ >>> dotproduct([10, 10], [20, 20])
+ 400
+
+ """
+ return sum(map(operator.mul, vec1, vec2))
+
+
+def flatten(listOfLists):
+ """Return an iterator flattening one level of nesting in a list of lists.
+
+ >>> list(flatten([[0, 1], [2, 3]]))
+ [0, 1, 2, 3]
+
+ See also :func:`collapse`, which can flatten multiple levels of nesting.
+
+ """
+ return chain.from_iterable(listOfLists)
+
+
+def repeatfunc(func, times=None, *args):
+ """Call *func* with *args* repeatedly, returning an iterable over the
+ results.
+
+ If *times* is specified, the iterable will terminate after that many
+ repetitions:
+
+ >>> from operator import add
+ >>> times = 4
+ >>> args = 3, 5
+ >>> list(repeatfunc(add, times, *args))
+ [8, 8, 8, 8]
+
+ If *times* is ``None`` the iterable will not terminate:
+
+ >>> from random import randrange
+ >>> times = None
+ >>> args = 1, 11
+ >>> take(6, repeatfunc(randrange, times, *args)) # doctest:+SKIP
+ [2, 4, 8, 1, 8, 4]
+
+ """
+ if times is None:
+ return starmap(func, repeat(args))
+ return starmap(func, repeat(args, times))
+
+
+def pairwise(iterable):
+ """Returns an iterator of paired items, overlapping, from the original
+
+ >>> take(4, pairwise(count()))
+ [(0, 1), (1, 2), (2, 3), (3, 4)]
+
+ """
+ a, b = tee(iterable)
+ next(b, None)
+ return zip(a, b)
+
+
+def grouper(n, iterable, fillvalue=None):
+ """Collect data into fixed-length chunks or blocks.
+
+ >>> list(grouper(3, 'ABCDEFG', 'x'))
+ [('A', 'B', 'C'), ('D', 'E', 'F'), ('G', 'x', 'x')]
+
+ """
+ args = [iter(iterable)] * n
+ return zip_longest(fillvalue=fillvalue, *args)
+
+
+def roundrobin(*iterables):
+ """Yields an item from each iterable, alternating between them.
+
+ >>> list(roundrobin('ABC', 'D', 'EF'))
+ ['A', 'D', 'E', 'B', 'F', 'C']
+
+ This function produces the same output as :func:`interleave_longest`, but
+ may perform better for some inputs (in particular when the number of
+ iterables is small).
+
+ """
+ # Recipe credited to George Sakkis
+ pending = len(iterables)
+ if PY2:
+ nexts = cycle(iter(it).next for it in iterables)
+ else:
+ nexts = cycle(iter(it).__next__ for it in iterables)
+ while pending:
+ try:
+ for next in nexts:
+ yield next()
+ except StopIteration:
+ pending -= 1
+ nexts = cycle(islice(nexts, pending))
+
+
+def partition(pred, iterable):
+ """
+ Returns a 2-tuple of iterables derived from the input iterable.
+ The first yields the items that have ``pred(item) == False``.
+ The second yields the items that have ``pred(item) == True``.
+
+ >>> is_odd = lambda x: x % 2 != 0
+ >>> iterable = range(10)
+ >>> even_items, odd_items = partition(is_odd, iterable)
+ >>> list(even_items), list(odd_items)
+ ([0, 2, 4, 6, 8], [1, 3, 5, 7, 9])
+
+ """
+ # partition(is_odd, range(10)) --> 0 2 4 6 8 and 1 3 5 7 9
+ t1, t2 = tee(iterable)
+ return filterfalse(pred, t1), filter(pred, t2)
+
+
+def powerset(iterable):
+ """Yields all possible subsets of the iterable.
+
+ >>> list(powerset([1,2,3]))
+ [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
+
+ """
+ s = list(iterable)
+ return chain.from_iterable(combinations(s, r) for r in range(len(s) + 1))
+
+
+def unique_everseen(iterable, key=None):
+ """
+ Yield unique elements, preserving order.
+
+ >>> list(unique_everseen('AAAABBBCCDAABBB'))
+ ['A', 'B', 'C', 'D']
+ >>> list(unique_everseen('ABBCcAD', str.lower))
+ ['A', 'B', 'C', 'D']
+
+ Sequences with a mix of hashable and unhashable items can be used.
+ The function will be slower (i.e., `O(n^2)`) for unhashable items.
+
+ """
+ seenset = set()
+ seenset_add = seenset.add
+ seenlist = []
+ seenlist_add = seenlist.append
+ if key is None:
+ for element in iterable:
+ try:
+ if element not in seenset:
+ seenset_add(element)
+ yield element
+ except TypeError:
+ if element not in seenlist:
+ seenlist_add(element)
+ yield element
+ else:
+ for element in iterable:
+ k = key(element)
+ try:
+ if k not in seenset:
+ seenset_add(k)
+ yield element
+ except TypeError:
+ if k not in seenlist:
+ seenlist_add(k)
+ yield element
+
+
+def unique_justseen(iterable, key=None):
+ """Yields elements in order, ignoring serial duplicates
+
+ >>> list(unique_justseen('AAAABBBCCDAABBB'))
+ ['A', 'B', 'C', 'D', 'A', 'B']
+ >>> list(unique_justseen('ABBCcAD', str.lower))
+ ['A', 'B', 'C', 'A', 'D']
+
+ """
+ return map(next, map(operator.itemgetter(1), groupby(iterable, key)))
+
+
+def iter_except(func, exception, first=None):
+ """Yields results from a function repeatedly until an exception is raised.
+
+ Converts a call-until-exception interface to an iterator interface.
+ Like ``iter(func, sentinel)``, but uses an exception instead of a sentinel
+ to end the loop.
+
+ >>> l = [0, 1, 2]
+ >>> list(iter_except(l.pop, IndexError))
+ [2, 1, 0]
+
+ """
+ try:
+ if first is not None:
+ yield first()
+ while 1:
+ yield func()
+ except exception:
+ pass
+
+
+def first_true(iterable, default=False, pred=None):
+ """
+ Returns the first true value in the iterable.
+
+ If no true value is found, returns *default*
+
+ If *pred* is not None, returns the first item for which
+ ``pred(item) == True`` .
+
+ >>> first_true(range(10))
+ 1
+ >>> first_true(range(10), pred=lambda x: x > 5)
+ 6
+ >>> first_true(range(10), default='missing', pred=lambda x: x > 9)
+ 'missing'
+
+ """
+ return next(filter(pred, iterable), default)
+
+
+def random_product(*args, **kwds):
+ """Draw an item at random from each of the input iterables.
+
+ >>> random_product('abc', range(4), 'XYZ') # doctest:+SKIP
+ ('c', 3, 'Z')
+
+ If *repeat* is provided as a keyword argument, that many items will be
+ drawn from each iterable.
+
+ >>> random_product('abcd', range(4), repeat=2) # doctest:+SKIP
+ ('a', 2, 'd', 3)
+
+ This equivalent to taking a random selection from
+ ``itertools.product(*args, **kwarg)``.
+
+ """
+ pools = [tuple(pool) for pool in args] * kwds.get('repeat', 1)
+ return tuple(choice(pool) for pool in pools)
+
+
+def random_permutation(iterable, r=None):
+ """Return a random *r* length permutation of the elements in *iterable*.
+
+ If *r* is not specified or is ``None``, then *r* defaults to the length of
+ *iterable*.
+
+ >>> random_permutation(range(5)) # doctest:+SKIP
+ (3, 4, 0, 1, 2)
+
+ This equivalent to taking a random selection from
+ ``itertools.permutations(iterable, r)``.
+
+ """
+ pool = tuple(iterable)
+ r = len(pool) if r is None else r
+ return tuple(sample(pool, r))
+
+
+def random_combination(iterable, r):
+ """Return a random *r* length subsequence of the elements in *iterable*.
+
+ >>> random_combination(range(5), 3) # doctest:+SKIP
+ (2, 3, 4)
+
+ This equivalent to taking a random selection from
+ ``itertools.combinations(iterable, r)``.
+
+ """
+ pool = tuple(iterable)
+ n = len(pool)
+ indices = sorted(sample(range(n), r))
+ return tuple(pool[i] for i in indices)
+
+
+def random_combination_with_replacement(iterable, r):
+ """Return a random *r* length subsequence of elements in *iterable*,
+ allowing individual elements to be repeated.
+
+ >>> random_combination_with_replacement(range(3), 5) # doctest:+SKIP
+ (0, 0, 1, 2, 2)
+
+ This equivalent to taking a random selection from
+ ``itertools.combinations_with_replacement(iterable, r)``.
+
+ """
+ pool = tuple(iterable)
+ n = len(pool)
+ indices = sorted(randrange(n) for i in range(r))
+ return tuple(pool[i] for i in indices)
+
+
+def nth_combination(iterable, r, index):
+ """Equivalent to ``list(combinations(iterable, r))[index]``.
+
+ The subsequences of *iterable* that are of length *r* can be ordered
+ lexicographically. :func:`nth_combination` computes the subsequence at
+ sort position *index* directly, without computing the previous
+ subsequences.
+
+ """
+ pool = tuple(iterable)
+ n = len(pool)
+ if (r < 0) or (r > n):
+ raise ValueError
+
+ c = 1
+ k = min(r, n - r)
+ for i in range(1, k + 1):
+ c = c * (n - k + i) // i
+
+ if index < 0:
+ index += c
+
+ if (index < 0) or (index >= c):
+ raise IndexError
+
+ result = []
+ while r:
+ c, n, r = c * r // n, n - 1, r - 1
+ while index >= c:
+ index -= c
+ c, n = c * (n - r) // n, n - 1
+ result.append(pool[-1 - n])
+
+ return tuple(result)
+
+
+def prepend(value, iterator):
+ """Yield *value*, followed by the elements in *iterator*.
+
+ >>> value = '0'
+ >>> iterator = ['1', '2', '3']
+ >>> list(prepend(value, iterator))
+ ['0', '1', '2', '3']
+
+ To prepend multiple values, see :func:`itertools.chain`.
+
+ """
+ return chain([value], iterator)
new file mode 100644
--- /dev/null
+++ b/testing/web-platform/tests/tools/third_party/more-itertools/more_itertools/tests/test_more.py
@@ -0,0 +1,1848 @@
+from __future__ import division, print_function, unicode_literals
+
+from decimal import Decimal
+from doctest import DocTestSuite
+from fractions import Fraction
+from functools import partial, reduce
+from heapq import merge
+from io import StringIO
+from itertools import (
+ chain,
+ count,
+ groupby,
+ islice,
+ permutations,
+ product,
+ repeat,
+)
+from operator import add, mul, itemgetter
+from unittest import TestCase
+
+from six.moves import filter, map, range, zip
+
+import more_itertools as mi
+
+
+def load_tests(loader, tests, ignore):
+ # Add the doctests
+ tests.addTests(DocTestSuite('more_itertools.more'))
+ return tests
+
+
+class CollateTests(TestCase):
+ """Unit tests for ``collate()``"""
+ # Also accidentally tests peekable, though that could use its own tests
+
+ def test_default(self):
+ """Test with the default `key` function."""
+ iterables = [range(4), range(7), range(3, 6)]
+ self.assertEqual(
+ sorted(reduce(list.__add__, [list(it) for it in iterables])),
+ list(mi.collate(*iterables))
+ )
+
+ def test_key(self):
+ """Test using a custom `key` function."""
+ iterables = [range(5, 0, -1), range(4, 0, -1)]
+ actual = sorted(
+ reduce(list.__add__, [list(it) for it in iterables]), reverse=True
+ )
+ expected = list(mi.collate(*iterables, key=lambda x: -x))
+ self.assertEqual(actual, expected)
+
+ def test_empty(self):
+ """Be nice if passed an empty list of iterables."""
+ self.assertEqual([], list(mi.collate()))
+
+ def test_one(self):
+ """Work when only 1 iterable is passed."""
+ self.assertEqual([0, 1], list(mi.collate(range(2))))
+
+ def test_reverse(self):
+ """Test the `reverse` kwarg."""
+ iterables = [range(4, 0, -1), range(7, 0, -1), range(3, 6, -1)]
+
+ actual = sorted(
+ reduce(list.__add__, [list(it) for it in iterables]), reverse=True
+ )
+ expected = list(mi.collate(*iterables, reverse=True))
+ self.assertEqual(actual, expected)
+
+ def test_alias(self):
+ self.assertNotEqual(merge.__doc__, mi.collate.__doc__)
+ self.assertNotEqual(partial.__doc__, mi.collate.__doc__)
+
+
+class ChunkedTests(TestCase):
+ """Tests for ``chunked()``"""
+
+ def test_even(self):
+ """Test when ``n`` divides evenly into the length of the iterable."""
+ self.assertEqual(
+ list(mi.chunked('ABCDEF', 3)), [['A', 'B', 'C'], ['D', 'E', 'F']]
+ )
+
+ def test_odd(self):
+ """Test when ``n`` does not divide evenly into the length of the
+ iterable.
+
+ """
+ self.assertEqual(
+ list(mi.chunked('ABCDE', 3)), [['A', 'B', 'C'], ['D', 'E']]
+ )
+
+
+class FirstTests(TestCase):
+ """Tests for ``first()``"""
+
+ def test_many(self):
+ """Test that it works on many-item iterables."""
+ # Also try it on a generator expression to make sure it works on
+ # whatever those return, across Python versions.
+ self.assertEqual(mi.first(x for x in range(4)), 0)
+
+ def test_one(self):
+ """Test that it doesn't raise StopIteration prematurely."""
+ self.assertEqual(mi.first([3]), 3)
+
+ def test_empty_stop_iteration(self):
+ """It should raise StopIteration for empty iterables."""
+ self.assertRaises(ValueError, lambda: mi.first([]))
+
+ def test_default(self):
+ """It should return the provided default arg for empty iterables."""
+ self.assertEqual(mi.first([], 'boo'), 'boo')
+
+
+class PeekableTests(TestCase):
+ """Tests for ``peekable()`` behavor not incidentally covered by testing
+ ``collate()``
+
+ """
+ def test_peek_default(self):
+ """Make sure passing a default into ``peek()`` works."""
+ p = mi.peekable([])
+ self.assertEqual(p.peek(7), 7)
+
+ def test_truthiness(self):
+ """Make sure a ``peekable`` tests true iff there are items remaining in
+ the iterable.
+
+ """
+ p = mi.peekable([])
+ self.assertFalse(p)
+
+ p = mi.peekable(range(3))
+ self.assertTrue(p)
+
+ def test_simple_peeking(self):
+ """Make sure ``next`` and ``peek`` advance and don't advance the
+ iterator, respectively.
+
+ """
+ p = mi.peekable(range(10))
+ self.assertEqual(next(p), 0)
+ self.assertEqual(p.peek(), 1)
+ self.assertEqual(next(p), 1)
+
+ def test_indexing(self):
+ """
+ Indexing into the peekable shouldn't advance the iterator.
+ """
+ p = mi.peekable('abcdefghijkl')
+
+ # The 0th index is what ``next()`` will return
+ self.assertEqual(p[0], 'a')
+ self.assertEqual(next(p), 'a')
+
+ # Indexing further into the peekable shouldn't advance the itertor
+ self.assertEqual(p[2], 'd')
+ self.assertEqual(next(p), 'b')
+
+ # The 0th index moves up with the iterator; the last index follows
+ self.assertEqual(p[0], 'c')
+ self.assertEqual(p[9], 'l')
+
+ self.assertEqual(next(p), 'c')
+ self.assertEqual(p[8], 'l')
+
+ # Negative indexing should work too
+ self.assertEqual(p[-2], 'k')
+ self.assertEqual(p[-9], 'd')
+ self.assertRaises(IndexError, lambda: p[-10])
+
+ def test_slicing(self):
+ """Slicing the peekable shouldn't advance the iterator."""
+ seq = list('abcdefghijkl')
+ p = mi.peekable(seq)
+
+ # Slicing the peekable should just be like slicing a re-iterable
+ self.assertEqual(p[1:4], seq[1:4])
+
+ # Advancing the iterator moves the slices up also
+ self.assertEqual(next(p), 'a')
+ self.assertEqual(p[1:4], seq[1:][1:4])
+
+ # Implicit starts and stop should work
+ self.assertEqual(p[:5], seq[1:][:5])
+ self.assertEqual(p[:], seq[1:][:])
+
+ # Indexing past the end should work
+ self.assertEqual(p[:100], seq[1:][:100])
+
+ # Steps should work, including negative
+ self.assertEqual(p[::2], seq[1:][::2])
+ self.assertEqual(p[::-1], seq[1:][::-1])
+
+ def test_slicing_reset(self):
+ """Test slicing on a fresh iterable each time"""
+ iterable = ['0', '1', '2', '3', '4', '5']
+ indexes = list(range(-4, len(iterable) + 4)) + [None]
+ steps = [1, 2, 3, 4, -1, -2, -3, 4]
+ for slice_args in product(indexes, indexes, steps):
+ it = iter(iterable)
+ p = mi.peekable(it)
+ next(p)
+ index = slice(*slice_args)
+ actual = p[index]
+ expected = iterable[1:][index]
+ self.assertEqual(actual, expected, slice_args)
+
+ def test_slicing_error(self):
+ iterable = '01234567'
+ p = mi.peekable(iter(iterable))
+
+ # Prime the cache
+ p.peek()
+ old_cache = list(p._cache)
+
+ # Illegal slice
+ with self.assertRaises(ValueError):
+ p[1:-1:0]
+
+ # Neither the cache nor the iteration should be affected
+ self.assertEqual(old_cache, list(p._cache))
+ self.assertEqual(list(p), list(iterable))
+
+ def test_passthrough(self):
+ """Iterating a peekable without using ``peek()`` or ``prepend()``
+ should just give the underlying iterable's elements (a trivial test but
+ useful to set a baseline in case something goes wrong)"""
+ expected = [1, 2, 3, 4, 5]
+ actual = list(mi.peekable(expected))
+ self.assertEqual(actual, expected)
+
+ # prepend() behavior tests
+
+ def test_prepend(self):
+ """Tests intersperesed ``prepend()`` and ``next()`` calls"""
+ it = mi.peekable(range(2))
+ actual = []
+
+ # Test prepend() before next()
+ it.prepend(10)
+ actual += [next(it), next(it)]
+
+ # Test prepend() between next()s
+ it.prepend(11)
+ actual += [next(it), next(it)]
+
+ # Test prepend() after source iterable is consumed
+ it.prepend(12)
+ actual += [next(it)]
+
+ expected = [10, 0, 11, 1, 12]
+ self.assertEqual(actual, expected)
+
+ def test_multi_prepend(self):
+ """Tests prepending multiple items and getting them in proper order"""
+ it = mi.peekable(range(5))
+ actual = [next(it), next(it)]
+ it.prepend(10, 11, 12)
+ it.prepend(20, 21)
+ actual += list(it)
+ expected = [0, 1, 20, 21, 10, 11, 12, 2, 3, 4]
+ self.assertEqual(actual, expected)
+
+ def test_empty(self):
+ """Tests prepending in front of an empty iterable"""
+ it = mi.peekable([])
+ it.prepend(10)
+ actual = list(it)
+ expected = [10]
+ self.assertEqual(actual, expected)
+
+ def test_prepend_truthiness(self):
+ """Tests that ``__bool__()`` or ``__nonzero__()`` works properly
+ with ``prepend()``"""
+ it = mi.peekable(range(5))
+ self.assertTrue(it)
+ actual = list(it)
+ self.assertFalse(it)
+ it.prepend(10)
+ self.assertTrue(it)
+ actual += [next(it)]
+ self.assertFalse(it)
+ expected = [0, 1, 2, 3, 4, 10]
+ self.assertEqual(actual, expected)
+
+ def test_multi_prepend_peek(self):
+ """Tests prepending multiple elements and getting them in reverse order
+ while peeking"""
+ it = mi.peekable(range(5))
+ actual = [next(it), next(it)]
+ self.assertEqual(it.peek(), 2)
+ it.prepend(10, 11, 12)
+ self.assertEqual(it.peek(), 10)
+ it.prepend(20, 21)
+ self.assertEqual(it.peek(), 20)
+ actual += list(it)
+ self.assertFalse(it)
+ expected = [0, 1, 20, 21, 10, 11, 12, 2, 3, 4]
+ self.assertEqual(actual, expected)
+
+ def test_prepend_after_stop(self):
+ """Test resuming iteration after a previous exhaustion"""
+ it = mi.peekable(range(3))
+ self.assertEqual(list(it), [0, 1, 2])
+ self.assertRaises(StopIteration, lambda: next(it))
+ it.prepend(10)
+ self.assertEqual(next(it), 10)
+ self.assertRaises(StopIteration, lambda: next(it))
+
+ def test_prepend_slicing(self):
+ """Tests interaction between prepending and slicing"""
+ seq = list(range(20))
+ p = mi.peekable(seq)
+
+ p.prepend(30, 40, 50)
+ pseq = [30, 40, 50] + seq # pseq for prepended_seq
+
+ # adapt the specific tests from test_slicing
+ self.assertEqual(p[0], 30)
+ self.assertEqual(p[1:8], pseq[1:8])
+ self.assertEqual(p[1:], pseq[1:])
+ self.assertEqual(p[:5], pseq[:5])
+ self.assertEqual(p[:], pseq[:])
+ self.assertEqual(p[:100], pseq[:100])
+ self.assertEqual(p[::2], pseq[::2])
+ self.assertEqual(p[::-1], pseq[::-1])
+
+ def test_prepend_indexing(self):
+ """Tests interaction between prepending and indexing"""
+ seq = list(range(20))
+ p = mi.peekable(seq)
+
+ p.prepend(30, 40, 50)
+
+ self.assertEqual(p[0], 30)
+ self.assertEqual(next(p), 30)
+ self.assertEqual(p[2], 0)
+ self.assertEqual(next(p), 40)
+ self.assertEqual(p[0], 50)
+ self.assertEqual(p[9], 8)
+ self.assertEqual(next(p), 50)
+ self.assertEqual(p[8], 8)
+ self.assertEqual(p[-2], 18)
+ self.assertEqual(p[-9], 11)
+ self.assertRaises(IndexError, lambda: p[-21])
+
+ def test_prepend_iterable(self):
+ """Tests prepending from an iterable"""
+ it = mi.peekable(range(5))
+ # Don't directly use the range() object to avoid any range-specific
+ # optimizations
+ it.prepend(*(x for x in range(5)))
+ actual = list(it)
+ expected = list(chain(range(5), range(5)))
+ self.assertEqual(actual, expected)
+
+ def test_prepend_many(self):
+ """Tests that prepending a huge number of elements works"""
+ it = mi.peekable(range(5))
+ # Don't directly use the range() object to avoid any range-specific
+ # optimizations
+ it.prepend(*(x for x in range(20000)))
+ actual = list(it)
+ expected = list(chain(range(20000), range(5)))
+ self.assertEqual(actual, expected)
+
+ def test_prepend_reversed(self):
+ """Tests prepending from a reversed iterable"""
+ it = mi.peekable(range(3))
+ it.prepend(*reversed((10, 11, 12)))
+ actual = list(it)
+ expected = [12, 11, 10, 0, 1, 2]
+ self.assertEqual(actual, expected)
+
+
+class ConsumerTests(TestCase):
+ """Tests for ``consumer()``"""
+
+ def test_consumer(self):
+ @mi.consumer
+ def eater():
+ while True:
+ x = yield # noqa
+
+ e = eater()
+ e.send('hi') # without @consumer, would raise TypeError
+
+
+class DistinctPermutationsTests(TestCase):
+ def test_distinct_permutations(self):
+ """Make sure the output for ``distinct_permutations()`` is the same as
+ set(permutations(it)).
+
+ """
+ iterable = ['z', 'a', 'a', 'q', 'q', 'q', 'y']
+ test_output = sorted(mi.distinct_permutations(iterable))
+ ref_output = sorted(set(permutations(iterable)))
+ self.assertEqual(test_output, ref_output)
+
+ def test_other_iterables(self):
+ """Make sure ``distinct_permutations()`` accepts a different type of
+ iterables.
+
+ """
+ # a generator
+ iterable = (c for c in ['z', 'a', 'a', 'q', 'q', 'q', 'y'])
+ test_output = sorted(mi.distinct_permutations(iterable))
+ # "reload" it
+ iterable = (c for c in ['z', 'a', 'a', 'q', 'q', 'q', 'y'])
+ ref_output = sorted(set(permutations(iterable)))
+ self.assertEqual(test_output, ref_output)
+
+ # an iterator
+ iterable = iter(['z', 'a', 'a', 'q', 'q', 'q', 'y'])
+ test_output = sorted(mi.distinct_permutations(iterable))
+ # "reload" it
+ iterable = iter(['z', 'a', 'a', 'q', 'q', 'q', 'y'])
+ ref_output = sorted(set(permutations(iterable)))
+ self.assertEqual(test_output, ref_output)
+
+
+class IlenTests(TestCase):
+ def test_ilen(self):
+ """Sanity-checks for ``ilen()``."""
+ # Non-empty
+ self.assertEqual(
+ mi.ilen(filter(lambda x: x % 10 == 0, range(101))), 11
+ )
+
+ # Empty
+ self.assertEqual(mi.ilen((x for x in range(0))), 0)
+
+ # Iterable with __len__
+ self.assertEqual(mi.ilen(list(range(6))), 6)
+
+
+class WithIterTests(TestCase):
+ def test_with_iter(self):
+ s = StringIO('One fish\nTwo fish')
+ initial_words = [line.split()[0] for line in mi.with_iter(s)]
+
+ # Iterable's items should be faithfully represented
+ self.assertEqual(initial_words, ['One', 'Two'])
+ # The file object should be closed
+ self.assertEqual(s.closed, True)
+
+
+class OneTests(TestCase):
+ def test_basic(self):
+ it = iter(['item'])
+ self.assertEqual(mi.one(it), 'item')
+
+ def test_too_short(self):
+ it = iter([])
+ self.assertRaises(ValueError, lambda: mi.one(it))
+ self.assertRaises(IndexError, lambda: mi.one(it, too_short=IndexError))
+
+ def test_too_long(self):
+ it = count()
+ self.assertRaises(ValueError, lambda: mi.one(it)) # burn 0 and 1
+ self.assertEqual(next(it), 2)
+ self.assertRaises(
+ OverflowError, lambda: mi.one(it, too_long=OverflowError)
+ )
+
+
+class IntersperseTest(TestCase):
+ """ Tests for intersperse() """
+
+ def test_even(self):
+ iterable = (x for x in '01')
+ self.assertEqual(
+ list(mi.intersperse(None, iterable)), ['0', None, '1']
+ )
+
+ def test_odd(self):
+ iterable = (x for x in '012')
+ self.assertEqual(
+ list(mi.intersperse(None, iterable)), ['0', None, '1', None, '2']
+ )
+
+ def test_nested(self):
+ element = ('a', 'b')
+ iterable = (x for x in '012')
+ actual = list(mi.intersperse(element, iterable))
+ expected = ['0', ('a', 'b'), '1', ('a', 'b'), '2']
+ self.assertEqual(actual, expected)
+
+ def test_not_iterable(self):
+ self.assertRaises(TypeError, lambda: mi.intersperse('x', 1))
+
+ def test_n(self):
+ for n, element, expected in [
+ (1, '_', ['0', '_', '1', '_', '2', '_', '3', '_', '4', '_', '5']),
+ (2, '_', ['0', '1', '_', '2', '3', '_', '4', '5']),
+ (3, '_', ['0', '1', '2', '_', '3', '4', '5']),
+ (4, '_', ['0', '1', '2', '3', '_', '4', '5']),
+ (5, '_', ['0', '1', '2', '3', '4', '_', '5']),
+ (6, '_', ['0', '1', '2', '3', '4', '5']),
+ (7, '_', ['0', '1', '2', '3', '4', '5']),
+ (3, ['a', 'b'], ['0', '1', '2', ['a', 'b'], '3', '4', '5']),
+ ]:
+ iterable = (x for x in '012345')
+ actual = list(mi.intersperse(element, iterable, n=n))
+ self.assertEqual(actual, expected)
+
+ def test_n_zero(self):
+ self.assertRaises(
+ ValueError, lambda: list(mi.intersperse('x', '012', n=0))
+ )
+
+
+class UniqueToEachTests(TestCase):
+ """Tests for ``unique_to_each()``"""
+
+ def test_all_unique(self):
+ """When all the input iterables are unique the output should match
+ the input."""
+ iterables = [[1, 2], [3, 4, 5], [6, 7, 8]]
+ self.assertEqual(mi.unique_to_each(*iterables), iterables)
+
+ def test_duplicates(self):
+ """When there are duplicates in any of the input iterables that aren't
+ in the rest, those duplicates should be emitted."""
+ iterables = ["mississippi", "missouri"]
+ self.assertEqual(
+ mi.unique_to_each(*iterables), [['p', 'p'], ['o', 'u', 'r']]
+ )
+
+ def test_mixed(self):
+ """When the input iterables contain different types the function should
+ still behave properly"""
+ iterables = ['x', (i for i in range(3)), [1, 2, 3], tuple()]
+ self.assertEqual(mi.unique_to_each(*iterables), [['x'], [0], [3], []])
+
+
+class WindowedTests(TestCase):
+ """Tests for ``windowed()``"""
+
+ def test_basic(self):
+ actual = list(mi.windowed([1, 2, 3, 4, 5], 3))
+ expected = [(1, 2, 3), (2, 3, 4), (3, 4, 5)]
+ self.assertEqual(actual, expected)
+
+ def test_large_size(self):
+ """
+ When the window size is larger than the iterable, and no fill value is
+ given,``None`` should be filled in.
+ """
+ actual = list(mi.windowed([1, 2, 3, 4, 5], 6))
+ expected = [(1, 2, 3, 4, 5, None)]
+ self.assertEqual(actual, expected)
+
+ def test_fillvalue(self):
+ """
+ When sizes don't match evenly, the given fill value should be used.
+ """
+ iterable = [1, 2, 3, 4, 5]
+
+ for n, kwargs, expected in [
+ (6, {}, [(1, 2, 3, 4, 5, '!')]), # n > len(iterable)
+ (3, {'step': 3}, [(1, 2, 3), (4, 5, '!')]), # using ``step``
+ ]:
+ actual = list(mi.windowed(iterable, n, fillvalue='!', **kwargs))
+ self.assertEqual(actual, expected)
+
+ def test_zero(self):
+ """When the window size is zero, an empty tuple should be emitted."""
+ actual = list(mi.windowed([1, 2, 3, 4, 5], 0))
+ expected = [tuple()]
+ self.assertEqual(actual, expected)
+
+ def test_negative(self):
+ """When the window size is negative, ValueError should be raised."""
+ with self.assertRaises(ValueError):
+ list(mi.windowed([1, 2, 3, 4, 5], -1))
+
+ def test_step(self):
+ """The window should advance by the number of steps provided"""
+ iterable = [1, 2, 3, 4, 5, 6, 7]
+ for n, step, expected in [
+ (3, 2, [(1, 2, 3), (3, 4, 5), (5, 6, 7)]), # n > step
+ (3, 3, [(1, 2, 3), (4, 5, 6), (7, None, None)]), # n == step
+ (3, 4, [(1, 2, 3), (5, 6, 7)]), # line up nicely
+ (3, 5, [(1, 2, 3), (6, 7, None)]), # off by one
+ (3, 6, [(1, 2, 3), (7, None, None)]), # off by two
+ (3, 7, [(1, 2, 3)]), # step past the end
+ (7, 8, [(1, 2, 3, 4, 5, 6, 7)]), # step > len(iterable)
+ ]:
+ actual = list(mi.windowed(iterable, n, step=step))
+ self.assertEqual(actual, expected)
+
+ # Step must be greater than or equal to 1
+ with self.assertRaises(ValueError):
+ list(mi.windowed(iterable, 3, step=0))
+
+
+class BucketTests(TestCase):
+ """Tests for ``bucket()``"""
+
+ def test_basic(self):
+ iterable = [10, 20, 30, 11, 21, 31, 12, 22, 23, 33]
+ D = mi.bucket(iterable, key=lambda x: 10 * (x // 10))
+
+ # In-order access
+ self.assertEqual(list(D[10]), [10, 11, 12])
+
+ # Out of order access
+ self.assertEqual(list(D[30]), [30, 31, 33])
+ self.assertEqual(list(D[20]), [20, 21, 22, 23])
+
+ self.assertEqual(list(D[40]), []) # Nothing in here!
+
+ def test_in(self):
+ iterable = [10, 20, 30, 11, 21, 31, 12, 22, 23, 33]
+ D = mi.bucket(iterable, key=lambda x: 10 * (x // 10))
+
+ self.assertTrue(10 in D)
+ self.assertFalse(40 in D)
+ self.assertTrue(20 in D)
+ self.assertFalse(21 in D)
+
+ # Checking in-ness shouldn't advance the iterator
+ self.assertEqual(next(D[10]), 10)
+
+ def test_validator(self):
+ iterable = count(0)
+ key = lambda x: int(str(x)[0]) # First digit of each number
+ validator = lambda x: 0 < x < 10 # No leading zeros
+ D = mi.bucket(iterable, key, validator=validator)
+ self.assertEqual(mi.take(3, D[1]), [1, 10, 11])
+ self.assertNotIn(0, D) # Non-valid entries don't return True
+ self.assertNotIn(0, D._cache) # Don't store non-valid entries
+ self.assertEqual(list(D[0]), [])
+
+
+class SpyTests(TestCase):
+ """Tests for ``spy()``"""
+
+ def test_basic(self):
+ original_iterable = iter('abcdefg')
+ head, new_iterable = mi.spy(original_iterable)
+ self.assertEqual(head, ['a'])
+ self.assertEqual(
+ list(new_iterable), ['a', 'b', 'c', 'd', 'e', 'f', 'g']
+ )
+
+ def test_unpacking(self):
+ original_iterable = iter('abcdefg')
+ (first, second, third), new_iterable = mi.spy(original_iterable, 3)
+ self.assertEqual(first, 'a')
+ self.assertEqual(second, 'b')
+ self.assertEqual(third, 'c')
+ self.assertEqual(
+ list(new_iterable), ['a', 'b', 'c', 'd', 'e', 'f', 'g']
+ )
+
+ def test_too_many(self):
+ original_iterable = iter('abc')
+ head, new_iterable = mi.spy(original_iterable, 4)
+ self.assertEqual(head, ['a', 'b', 'c'])
+ self.assertEqual(list(new_iterable), ['a', 'b', 'c'])
+
+ def test_zero(self):
+ original_iterable = iter('abc')
+ head, new_iterable = mi.spy(original_iterable, 0)
+ self.assertEqual(head, [])
+ self.assertEqual(list(new_iterable), ['a', 'b', 'c'])
+
+
+class InterleaveTests(TestCase):
+ def test_even(self):
+ actual = list(mi.interleave([1, 4, 7], [2, 5, 8], [3, 6, 9]))
+ expected = [1, 2, 3, 4, 5, 6, 7, 8, 9]
+ self.assertEqual(actual, expected)
+
+ def test_short(self):
+ actual = list(mi.interleave([1, 4], [2, 5, 7], [3, 6, 8]))
+ expected = [1, 2, 3, 4, 5, 6]
+ self.assertEqual(actual, expected)
+
+ def test_mixed_types(self):
+ it_list = ['a', 'b', 'c', 'd']
+ it_str = '12345'
+ it_inf = count()
+ actual = list(mi.interleave(it_list, it_str, it_inf))
+ expected = ['a', '1', 0, 'b', '2', 1, 'c', '3', 2, 'd', '4', 3]
+ self.assertEqual(actual, expected)
+
+
+class InterleaveLongestTests(TestCase):
+ def test_even(self):
+ actual = list(mi.interleave_longest([1, 4, 7], [2, 5, 8], [3, 6, 9]))
+ expected = [1, 2, 3, 4, 5, 6, 7, 8, 9]
+ self.assertEqual(actual, expected)
+
+ def test_short(self):
+ actual = list(mi.interleave_longest([1, 4], [2, 5, 7], [3, 6, 8]))
+ expected = [1, 2, 3, 4, 5, 6, 7, 8]
+ self.assertEqual(actual, expected)
+
+ def test_mixed_types(self):
+ it_list = ['a', 'b', 'c', 'd']
+ it_str = '12345'
+ it_gen = (x for x in range(3))
+ actual = list(mi.interleave_longest(it_list, it_str, it_gen))
+ expected = ['a', '1', 0, 'b', '2', 1, 'c', '3', 2, 'd', '4', '5']
+ self.assertEqual(actual, expected)
+
+
+class TestCollapse(TestCase):
+ """Tests for ``collapse()``"""
+
+ def test_collapse(self):
+ l = [[1], 2, [[3], 4], [[[5]]]]
+ self.assertEqual(list(mi.collapse(l)), [1, 2, 3, 4, 5])
+
+ def test_collapse_to_string(self):
+ l = [["s1"], "s2", [["s3"], "s4"], [[["s5"]]]]
+ self.assertEqual(list(mi.collapse(l)), ["s1", "s2", "s3", "s4", "s5"])
+
+ def test_collapse_flatten(self):
+ l = [[1], [2], [[3], 4], [[[5]]]]
+ self.assertEqual(list(mi.collapse(l, levels=1)), list(mi.flatten(l)))
+
+ def test_collapse_to_level(self):
+ l = [[1], 2, [[3], 4], [[[5]]]]
+ self.assertEqual(list(mi.collapse(l, levels=2)), [1, 2, 3, 4, [5]])
+ self.assertEqual(
+ list(mi.collapse(mi.collapse(l, levels=1), levels=1)),
+ list(mi.collapse(l, levels=2))
+ )
+
+ def test_collapse_to_list(self):
+ l = (1, [2], (3, [4, (5,)], 'ab'))
+ actual = list(mi.collapse(l, base_type=list))
+ expected = [1, [2], 3, [4, (5,)], 'ab']
+ self.assertEqual(actual, expected)
+
+
+class SideEffectTests(TestCase):
+ """Tests for ``side_effect()``"""
+
+ def test_individual(self):
+ # The function increments the counter for each call
+ counter = [0]
+
+ def func(arg):
+ counter[0] += 1
+
+ result = list(mi.side_effect(func, range(10)))
+ self.assertEqual(result, list(range(10)))
+ self.assertEqual(counter[0], 10)
+
+ def test_chunked(self):
+ # The function increments the counter for each call
+ counter = [0]
+
+ def func(arg):
+ counter[0] += 1
+
+ result = list(mi.side_effect(func, range(10), 2))
+ self.assertEqual(result, list(range(10)))
+ self.assertEqual(counter[0], 5)
+
+ def test_before_after(self):
+ f = StringIO()
+ collector = []
+
+ def func(item):
+ print(item, file=f)
+ collector.append(f.getvalue())
+
+ def it():
+ yield u'a'
+ yield u'b'
+ raise RuntimeError('kaboom')
+
+ before = lambda: print('HEADER', file=f)
+ after = f.close
+
+ try:
+ mi.consume(mi.side_effect(func, it(), before=before, after=after))
+ except RuntimeError:
+ pass
+
+ # The iterable should have been written to the file
+ self.assertEqual(collector, [u'HEADER\na\n', u'HEADER\na\nb\n'])
+
+ # The file should be closed even though something bad happened
+ self.assertTrue(f.closed)
+
+ def test_before_fails(self):
+ f = StringIO()
+ func = lambda x: print(x, file=f)
+
+ def before():
+ raise RuntimeError('ouch')
+
+ try:
+ mi.consume(
+ mi.side_effect(func, u'abc', before=before, after=f.close)
+ )
+ except RuntimeError:
+ pass
+
+ # The file should be closed even though something bad happened in the
+ # before function
+ self.assertTrue(f.closed)
+
+
+class SlicedTests(TestCase):
+ """Tests for ``sliced()``"""
+
+ def test_even(self):
+ """Test when the length of the sequence is divisible by *n*"""
+ seq = 'ABCDEFGHI'
+ self.assertEqual(list(mi.sliced(seq, 3)), ['ABC', 'DEF', 'GHI'])
+
+ def test_odd(self):
+ """Test when the length of the sequence is not divisible by *n*"""
+ seq = 'ABCDEFGHI'
+ self.assertEqual(list(mi.sliced(seq, 4)), ['ABCD', 'EFGH', 'I'])
+
+ def test_not_sliceable(self):
+ seq = (x for x in 'ABCDEFGHI')
+
+ with self.assertRaises(TypeError):
+ list(mi.sliced(seq, 3))
+
+
+class SplitAtTests(TestCase):
+ """Tests for ``split()``"""
+
+ def comp_with_str_split(self, str_to_split, delim):
+ pred = lambda c: c == delim
+ actual = list(map(''.join, mi.split_at(str_to_split, pred)))
+ expected = str_to_split.split(delim)
+ self.assertEqual(actual, expected)
+
+ def test_seperators(self):
+ test_strs = ['', 'abcba', 'aaabbbcccddd', 'e']
+ for s, delim in product(test_strs, 'abcd'):
+ self.comp_with_str_split(s, delim)
+
+
+class SplitBeforeTest(TestCase):
+ """Tests for ``split_before()``"""
+
+ def test_starts_with_sep(self):
+ actual = list(mi.split_before('xooxoo', lambda c: c == 'x'))
+ expected = [['x', 'o', 'o'], ['x', 'o', 'o']]
+ self.assertEqual(actual, expected)
+
+ def test_ends_with_sep(self):
+ actual = list(mi.split_before('ooxoox', lambda c: c == 'x'))
+ expected = [['o', 'o'], ['x', 'o', 'o'], ['x']]
+ self.assertEqual(actual, expected)
+
+ def test_no_sep(self):
+ actual = list(mi.split_before('ooo', lambda c: c == 'x'))
+ expected = [['o', 'o', 'o']]
+ self.assertEqual(actual, expected)
+
+
+class SplitAfterTest(TestCase):
+ """Tests for ``split_after()``"""
+
+ def test_starts_with_sep(self):
+ actual = list(mi.split_after('xooxoo', lambda c: c == 'x'))
+ expected = [['x'], ['o', 'o', 'x'], ['o', 'o']]
+ self.assertEqual(actual, expected)
+
+ def test_ends_with_sep(self):
+ actual = list(mi.split_after('ooxoox', lambda c: c == 'x'))
+ expected = [['o', 'o', 'x'], ['o', 'o', 'x']]
+ self.assertEqual(actual, expected)
+
+ def test_no_sep(self):
+ actual = list(mi.split_after('ooo', lambda c: c == 'x'))
+ expected = [['o', 'o', 'o']]
+ self.assertEqual(actual, expected)
+
+
+class PaddedTest(TestCase):
+ """Tests for ``padded()``"""
+
+ def test_no_n(self):
+ seq = [1, 2, 3]
+
+ # No fillvalue
+ self.assertEqual(mi.take(5, mi.padded(seq)), [1, 2, 3, None, None])
+
+ # With fillvalue
+ self.assertEqual(
+ mi.take(5, mi.padded(seq, fillvalue='')), [1, 2, 3, '', '']
+ )
+
+ def test_invalid_n(self):
+ self.assertRaises(ValueError, lambda: list(mi.padded([1, 2, 3], n=-1)))
+ self.assertRaises(ValueError, lambda: list(mi.padded([1, 2, 3], n=0)))
+
+ def test_valid_n(self):
+ seq = [1, 2, 3, 4, 5]
+
+ # No need for padding: len(seq) <= n
+ self.assertEqual(list(mi.padded(seq, n=4)), [1, 2, 3, 4, 5])
+ self.assertEqual(list(mi.padded(seq, n=5)), [1, 2, 3, 4, 5])
+
+ # No fillvalue
+ self.assertEqual(
+ list(mi.padded(seq, n=7)), [1, 2, 3, 4, 5, None, None]
+ )
+
+ # With fillvalue
+ self.assertEqual(
+ list(mi.padded(seq, fillvalue='', n=7)), [1, 2, 3, 4, 5, '', '']
+ )
+
+ def test_next_multiple(self):
+ seq = [1, 2, 3, 4, 5, 6]
+
+ # No need for padding: len(seq) % n == 0
+ self.assertEqual(
+ list(mi.padded(seq, n=3, next_multiple=True)), [1, 2, 3, 4, 5, 6]
+ )
+
+ # Padding needed: len(seq) < n
+ self.assertEqual(
+ list(mi.padded(seq, n=8, next_multiple=True)),
+ [1, 2, 3, 4, 5, 6, None, None]
+ )
+
+ # No padding needed: len(seq) == n
+ self.assertEqual(
+ list(mi.padded(seq, n=6, next_multiple=True)), [1, 2, 3, 4, 5, 6]
+ )
+
+ # Padding needed: len(seq) > n
+ self.assertEqual(
+ list(mi.padded(seq, n=4, next_multiple=True)),
+ [1, 2, 3, 4, 5, 6, None, None]
+ )
+
+ # With fillvalue
+ self.assertEqual(
+ list(mi.padded(seq, fillvalue='', n=4, next_multiple=True)),
+ [1, 2, 3, 4, 5, 6, '', '']
+ )
+
+
+class DistributeTest(TestCase):
+ """Tests for distribute()"""
+
+ def test_invalid_n(self):
+ self.assertRaises(ValueError, lambda: mi.distribute(-1, [1, 2, 3]))
+ self.assertRaises(ValueError, lambda: mi.distribute(0, [1, 2, 3]))
+
+ def test_basic(self):
+ iterable = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
+
+ for n, expected in [
+ (1, [iterable]),
+ (2, [[1, 3, 5, 7, 9], [2, 4, 6, 8, 10]]),
+ (3, [[1, 4, 7, 10], [2, 5, 8], [3, 6, 9]]),
+ (10, [[n] for n in range(1, 10 + 1)]),
+ ]:
+ self.assertEqual(
+ [list(x) for x in mi.distribute(n, iterable)], expected
+ )
+
+ def test_large_n(self):
+ iterable = [1, 2, 3, 4]
+ self.assertEqual(
+ [list(x) for x in mi.distribute(6, iterable)],
+ [[1], [2], [3], [4], [], []]
+ )
+
+
+class StaggerTest(TestCase):
+ """Tests for ``stagger()``"""
+
+ def test_default(self):
+ iterable = [0, 1, 2, 3]
+ actual = list(mi.stagger(iterable))
+ expected = [(None, 0, 1), (0, 1, 2), (1, 2, 3)]
+ self.assertEqual(actual, expected)
+
+ def test_offsets(self):
+ iterable = [0, 1, 2, 3]
+ for offsets, expected in [
+ ((-2, 0, 2), [('', 0, 2), ('', 1, 3)]),
+ ((-2, -1), [('', ''), ('', 0), (0, 1), (1, 2), (2, 3)]),
+ ((1, 2), [(1, 2), (2, 3)]),
+ ]:
+ all_groups = mi.stagger(iterable, offsets=offsets, fillvalue='')
+ self.assertEqual(list(all_groups), expected)
+
+ def test_longest(self):
+ iterable = [0, 1, 2, 3]
+ for offsets, expected in [
+ (
+ (-1, 0, 1),
+ [('', 0, 1), (0, 1, 2), (1, 2, 3), (2, 3, ''), (3, '', '')]
+ ),
+ ((-2, -1), [('', ''), ('', 0), (0, 1), (1, 2), (2, 3), (3, '')]),
+ ((1, 2), [(1, 2), (2, 3), (3, '')]),
+ ]:
+ all_groups = mi.stagger(
+ iterable, offsets=offsets, fillvalue='', longest=True
+ )
+ self.assertEqual(list(all_groups), expected)
+
+
+class ZipOffsetTest(TestCase):
+ """Tests for ``zip_offset()``"""
+
+ def test_shortest(self):
+ a_1 = [0, 1, 2, 3]
+ a_2 = [0, 1, 2, 3, 4, 5]
+ a_3 = [0, 1, 2, 3, 4, 5, 6, 7]
+ actual = list(
+ mi.zip_offset(a_1, a_2, a_3, offsets=(-1, 0, 1), fillvalue='')
+ )
+ expected = [('', 0, 1), (0, 1, 2), (1, 2, 3), (2, 3, 4), (3, 4, 5)]
+ self.assertEqual(actual, expected)
+
+ def test_longest(self):
+ a_1 = [0, 1, 2, 3]
+ a_2 = [0, 1, 2, 3, 4, 5]
+ a_3 = [0, 1, 2, 3, 4, 5, 6, 7]
+ actual = list(
+ mi.zip_offset(a_1, a_2, a_3, offsets=(-1, 0, 1), longest=True)
+ )
+ expected = [
+ (None, 0, 1),
+ (0, 1, 2),
+ (1, 2, 3),
+ (2, 3, 4),
+ (3, 4, 5),
+ (None, 5, 6),
+ (None, None, 7),
+ ]
+ self.assertEqual(actual, expected)
+
+ def test_mismatch(self):
+ iterables = [0, 1, 2], [2, 3, 4]
+ offsets = (-1, 0, 1)
+ self.assertRaises(
+ ValueError,
+ lambda: list(mi.zip_offset(*iterables, offsets=offsets))
+ )
+
+
+class SortTogetherTest(TestCase):
+ """Tests for sort_together()"""
+
+ def test_key_list(self):
+ """tests `key_list` including default, iterables include duplicates"""
+ iterables = [
+ ['GA', 'GA', 'GA', 'CT', 'CT', 'CT'],
+ ['May', 'Aug.', 'May', 'June', 'July', 'July'],
+ [97, 20, 100, 70, 100, 20]
+ ]
+
+ self.assertEqual(
+ mi.sort_together(iterables),
+ [
+ ('CT', 'CT', 'CT', 'GA', 'GA', 'GA'),
+ ('June', 'July', 'July', 'May', 'Aug.', 'May'),
+ (70, 100, 20, 97, 20, 100)
+ ]
+ )
+
+ self.assertEqual(
+ mi.sort_together(iterables, key_list=(0, 1)),
+ [
+ ('CT', 'CT', 'CT', 'GA', 'GA', 'GA'),
+ ('July', 'July', 'June', 'Aug.', 'May', 'May'),
+ (100, 20, 70, 20, 97, 100)
+ ]
+ )
+
+ self.assertEqual(
+ mi.sort_together(iterables, key_list=(0, 1, 2)),
+ [
+ ('CT', 'CT', 'CT', 'GA', 'GA', 'GA'),
+ ('July', 'July', 'June', 'Aug.', 'May', 'May'),
+ (20, 100, 70, 20, 97, 100)
+ ]
+ )
+
+ self.assertEqual(
+ mi.sort_together(iterables, key_list=(2,)),
+ [
+ ('GA', 'CT', 'CT', 'GA', 'GA', 'CT'),
+ ('Aug.', 'July', 'June', 'May', 'May', 'July'),
+ (20, 20, 70, 97, 100, 100)
+ ]
+ )
+
+ def test_invalid_key_list(self):
+ """tests `key_list` for indexes not available in `iterables`"""
+ iterables = [
+ ['GA', 'GA', 'GA', 'CT', 'CT', 'CT'],
+ ['May', 'Aug.', 'May', 'June', 'July', 'July'],
+ [97, 20, 100, 70, 100, 20]
+ ]
+
+ self.assertRaises(
+ IndexError, lambda: mi.sort_together(iterables, key_list=(5,))
+ )
+
+ def test_reverse(self):
+ """tests `reverse` to ensure a reverse sort for `key_list` iterables"""
+ iterables = [
+ ['GA', 'GA', 'GA', 'CT', 'CT', 'CT'],
+ ['May', 'Aug.', 'May', 'June', 'July', 'July'],
+ [97, 20, 100, 70, 100, 20]
+ ]
+
+ self.assertEqual(
+ mi.sort_together(iterables, key_list=(0, 1, 2), reverse=True),
+ [('GA', 'GA', 'GA', 'CT', 'CT', 'CT'),
+ ('May', 'May', 'Aug.', 'June', 'July', 'July'),
+ (100, 97, 20, 70, 100, 20)]
+ )
+
+ def test_uneven_iterables(self):
+ """tests trimming of iterables to the shortest length before sorting"""
+ iterables = [['GA', 'GA', 'GA', 'CT', 'CT', 'CT', 'MA'],
+ ['May', 'Aug.', 'May', 'June', 'July', 'July'],
+ [97, 20, 100, 70, 100, 20, 0]]
+
+ self.assertEqual(
+ mi.sort_together(iterables),
+ [
+ ('CT', 'CT', 'CT', 'GA', 'GA', 'GA'),
+ ('June', 'July', 'July', 'May', 'Aug.', 'May'),
+ (70, 100, 20, 97, 20, 100)
+ ]
+ )
+
+
+class DivideTest(TestCase):
+ """Tests for divide()"""
+
+ def test_invalid_n(self):
+ self.assertRaises(ValueError, lambda: mi.divide(-1, [1, 2, 3]))
+ self.assertRaises(ValueError, lambda: mi.divide(0, [1, 2, 3]))
+
+ def test_basic(self):
+ iterable = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
+
+ for n, expected in [
+ (1, [iterable]),
+ (2, [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10]]),
+ (3, [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]),
+ (10, [[n] for n in range(1, 10 + 1)]),
+ ]:
+ self.assertEqual(
+ [list(x) for x in mi.divide(n, iterable)], expected
+ )
+
+ def test_large_n(self):
+ iterable = [1, 2, 3, 4]
+ self.assertEqual(
+ [list(x) for x in mi.divide(6, iterable)],
+ [[1], [2], [3], [4], [], []]
+ )
+
+
+class TestAlwaysIterable(TestCase):
+ """Tests for always_iterable()"""
+ def test_single(self):
+ self.assertEqual(list(mi.always_iterable(1)), [1])
+
+ def test_strings(self):
+ for obj in ['foo', b'bar', u'baz']:
+ actual = list(mi.always_iterable(obj))
+ expected = [obj]
+ self.assertEqual(actual, expected)
+
+ def test_base_type(self):
+ dict_obj = {'a': 1, 'b': 2}
+ str_obj = '123'
+
+ # Default: dicts are iterable like they normally are
+ default_actual = list(mi.always_iterable(dict_obj))
+ default_expected = list(dict_obj)
+ self.assertEqual(default_actual, default_expected)
+
+ # Unitary types set: dicts are not iterable
+ custom_actual = list(mi.always_iterable(dict_obj, base_type=dict))
+ custom_expected = [dict_obj]
+ self.assertEqual(custom_actual, custom_expected)
+
+ # With unitary types set, strings are iterable
+ str_actual = list(mi.always_iterable(str_obj, base_type=None))
+ str_expected = list(str_obj)
+ self.assertEqual(str_actual, str_expected)
+
+ def test_iterables(self):
+ self.assertEqual(list(mi.always_iterable([0, 1])), [0, 1])
+ self.assertEqual(
+ list(mi.always_iterable([0, 1], base_type=list)), [[0, 1]]
+ )
+ self.assertEqual(
+ list(mi.always_iterable(iter('foo'))), ['f', 'o', 'o']
+ )
+ self.assertEqual(list(mi.always_iterable([])), [])
+
+ def test_none(self):
+ self.assertEqual(list(mi.always_iterable(None)), [])
+
+ def test_generator(self):
+ def _gen():
+ yield 0
+ yield 1
+
+ self.assertEqual(list(mi.always_iterable(_gen())), [0, 1])
+
+
+class AdjacentTests(TestCase):
+ def test_typical(self):
+ actual = list(mi.adjacent(lambda x: x % 5 == 0, range(10)))
+ expected = [(True, 0), (True, 1), (False, 2), (False, 3), (True, 4),
+ (True, 5), (True, 6), (False, 7), (False, 8), (False, 9)]
+ self.assertEqual(actual, expected)
+
+ def test_empty_iterable(self):
+ actual = list(mi.adjacent(lambda x: x % 5 == 0, []))
+ expected = []
+ self.assertEqual(actual, expected)
+
+ def test_length_one(self):
+ actual = list(mi.adjacent(lambda x: x % 5 == 0, [0]))
+ expected = [(True, 0)]
+ self.assertEqual(actual, expected)
+
+ actual = list(mi.adjacent(lambda x: x % 5 == 0, [1]))
+ expected = [(False, 1)]
+ self.assertEqual(actual, expected)
+
+ def test_consecutive_true(self):
+ """Test that when the predicate matches multiple consecutive elements
+ it doesn't repeat elements in the output"""
+ actual = list(mi.adjacent(lambda x: x % 5 < 2, range(10)))
+ expected = [(True, 0), (True, 1), (True, 2), (False, 3), (True, 4),
+ (True, 5), (True, 6), (True, 7), (False, 8), (False, 9)]
+ self.assertEqual(actual, expected)
+
+ def test_distance(self):
+ actual = list(mi.adjacent(lambda x: x % 5 == 0, range(10), distance=2))
+ expected = [(True, 0), (True, 1), (True, 2), (True, 3), (True, 4),
+ (True, 5), (True, 6), (True, 7), (False, 8), (False, 9)]
+ self.assertEqual(actual, expected)
+
+ actual = list(mi.adjacent(lambda x: x % 5 == 0, range(10), distance=3))
+ expected = [(True, 0), (True, 1), (True, 2), (True, 3), (True, 4),
+ (True, 5), (True, 6), (True, 7), (True, 8), (False, 9)]
+ self.assertEqual(actual, expected)
+
+ def test_large_distance(self):
+ """Test distance larger than the length of the iterable"""
+ iterable = range(10)
+ actual = list(mi.adjacent(lambda x: x % 5 == 4, iterable, distance=20))
+ expected = list(zip(repeat(True), iterable))
+ self.assertEqual(actual, expected)
+
+ actual = list(mi.adjacent(lambda x: False, iterable, distance=20))
+ expected = list(zip(repeat(False), iterable))
+ self.assertEqual(actual, expected)
+
+ def test_zero_distance(self):
+ """Test that adjacent() reduces to zip+map when distance is 0"""
+ iterable = range(1000)
+ predicate = lambda x: x % 4 == 2
+ actual = mi.adjacent(predicate, iterable, 0)
+ expected = zip(map(predicate, iterable), iterable)
+ self.assertTrue(all(a == e for a, e in zip(actual, expected)))
+
+ def test_negative_distance(self):
+ """Test that adjacent() raises an error with negative distance"""
+ pred = lambda x: x
+ self.assertRaises(
+ ValueError, lambda: mi.adjacent(pred, range(1000), -1)
+ )
+ self.assertRaises(
+ ValueError, lambda: mi.adjacent(pred, range(10), -10)
+ )
+
+ def test_grouping(self):
+ """Test interaction of adjacent() with groupby_transform()"""
+ iterable = mi.adjacent(lambda x: x % 5 == 0, range(10))
+ grouper = mi.groupby_transform(iterable, itemgetter(0), itemgetter(1))
+ actual = [(k, list(g)) for k, g in grouper]
+ expected = [
+ (True, [0, 1]),
+ (False, [2, 3]),
+ (True, [4, 5, 6]),
+ (False, [7, 8, 9]),
+ ]
+ self.assertEqual(actual, expected)
+
+ def test_call_once(self):
+ """Test that the predicate is only called once per item."""
+ already_seen = set()
+ iterable = range(10)
+
+ def predicate(item):
+ self.assertNotIn(item, already_seen)
+ already_seen.add(item)
+ return True
+
+ actual = list(mi.adjacent(predicate, iterable))
+ expected = [(True, x) for x in iterable]
+ self.assertEqual(actual, expected)
+
+
+class GroupByTransformTests(TestCase):
+ def assertAllGroupsEqual(self, groupby1, groupby2):
+ """Compare two groupby objects for equality, both keys and groups."""
+ for a, b in zip(groupby1, groupby2):
+ key1, group1 = a
+ key2, group2 = b
+ self.assertEqual(key1, key2)
+ self.assertListEqual(list(group1), list(group2))
+ self.assertRaises(StopIteration, lambda: next(groupby1))
+ self.assertRaises(StopIteration, lambda: next(groupby2))
+
+ def test_default_funcs(self):
+ """Test that groupby_transform() with default args mimics groupby()"""
+ iterable = [(x // 5, x) for x in range(1000)]
+ actual = mi.groupby_transform(iterable)
+ expected = groupby(iterable)
+ self.assertAllGroupsEqual(actual, expected)
+
+ def test_valuefunc(self):
+ iterable = [(int(x / 5), int(x / 3), x) for x in range(10)]
+
+ # Test the standard usage of grouping one iterable using another's keys
+ grouper = mi.groupby_transform(
+ iterable, keyfunc=itemgetter(0), valuefunc=itemgetter(-1)
+ )
+ actual = [(k, list(g)) for k, g in grouper]
+ expected = [(0, [0, 1, 2, 3, 4]), (1, [5, 6, 7, 8, 9])]
+ self.assertEqual(actual, expected)
+
+ grouper = mi.groupby_transform(
+ iterable, keyfunc=itemgetter(1), valuefunc=itemgetter(-1)
+ )
+ actual = [(k, list(g)) for k, g in grouper]
+ expected = [(0, [0, 1, 2]), (1, [3, 4, 5]), (2, [6, 7, 8]), (3, [9])]
+ self.assertEqual(actual, expected)
+
+ # and now for something a little different
+ d = dict(zip(range(10), 'abcdefghij'))
+ grouper = mi.groupby_transform(
+ range(10), keyfunc=lambda x: x // 5, valuefunc=d.get
+ )
+ actual = [(k, ''.join(g)) for k, g in grouper]
+ expected = [(0, 'abcde'), (1, 'fghij')]
+ self.assertEqual(actual, expected)
+
+ def test_no_valuefunc(self):
+ iterable = range(1000)
+
+ def key(x):
+ return x // 5
+
+ actual = mi.groupby_transform(iterable, key, valuefunc=None)
+ expected = groupby(iterable, key)
+ self.assertAllGroupsEqual(actual, expected)
+
+ actual = mi.groupby_transform(iterable, key) # default valuefunc
+ expected = groupby(iterable, key)
+ self.assertAllGroupsEqual(actual, expected)
+
+
+class NumericRangeTests(TestCase):
+ def test_basic(self):
+ for args, expected in [
+ ((4,), [0, 1, 2, 3]),
+ ((4.0,), [0.0, 1.0, 2.0, 3.0]),
+ ((1.0, 4), [1.0, 2.0, 3.0]),
+ ((1, 4.0), [1, 2, 3]),
+ ((1.0, 5), [1.0, 2.0, 3.0, 4.0]),
+ ((0, 20, 5), [0, 5, 10, 15]),
+ ((0, 20, 5.0), [0.0, 5.0, 10.0, 15.0]),
+ ((0, 10, 3), [0, 3, 6, 9]),
+ ((0, 10, 3.0), [0.0, 3.0, 6.0, 9.0]),
+ ((0, -5, -1), [0, -1, -2, -3, -4]),
+ ((0.0, -5, -1), [0.0, -1.0, -2.0, -3.0, -4.0]),
+ ((1, 2, Fraction(1, 2)), [Fraction(1, 1), Fraction(3, 2)]),
+ ((0,), []),
+ ((0.0,), []),
+ ((1, 0), []),
+ ((1.0, 0.0), []),
+ ((Fraction(2, 1),), [Fraction(0, 1), Fraction(1, 1)]),
+ ((Decimal('2.0'),), [Decimal('0.0'), Decimal('1.0')]),
+ ]:
+ actual = list(mi.numeric_range(*args))
+ self.assertEqual(actual, expected)
+ self.assertTrue(
+ all(type(a) == type(e) for a, e in zip(actual, expected))
+ )
+
+ def test_arg_count(self):
+ self.assertRaises(TypeError, lambda: list(mi.numeric_range()))
+ self.assertRaises(
+ TypeError, lambda: list(mi.numeric_range(0, 1, 2, 3))
+ )
+
+ def test_zero_step(self):
+ self.assertRaises(
+ ValueError, lambda: list(mi.numeric_range(1, 2, 0))
+ )
+
+
+class CountCycleTests(TestCase):
+ def test_basic(self):
+ expected = [
+ (0, 'a'), (0, 'b'), (0, 'c'),
+ (1, 'a'), (1, 'b'), (1, 'c'),
+ (2, 'a'), (2, 'b'), (2, 'c'),
+ ]
+ for actual in [
+ mi.take(9, mi.count_cycle('abc')), # n=None
+ list(mi.count_cycle('abc', 3)), # n=3
+ ]:
+ self.assertEqual(actual, expected)
+
+ def test_empty(self):
+ self.assertEqual(list(mi.count_cycle('')), [])
+ self.assertEqual(list(mi.count_cycle('', 2)), [])
+
+ def test_negative(self):
+ self.assertEqual(list(mi.count_cycle('abc', -3)), [])
+
+
+class LocateTests(TestCase):
+ def test_default_pred(self):
+ iterable = [0, 1, 1, 0, 1, 0, 0]
+ actual = list(mi.locate(iterable))
+ expected = [1, 2, 4]
+ self.assertEqual(actual, expected)
+
+ def test_no_matches(self):
+ iterable = [0, 0, 0]
+ actual = list(mi.locate(iterable))
+ expected = []
+ self.assertEqual(actual, expected)
+
+ def test_custom_pred(self):
+ iterable = ['0', 1, 1, '0', 1, '0', '0']
+ pred = lambda x: x == '0'
+ actual = list(mi.locate(iterable, pred))
+ expected = [0, 3, 5, 6]
+ self.assertEqual(actual, expected)
+
+
+class StripFunctionTests(TestCase):
+ def test_hashable(self):
+ iterable = list('www.example.com')
+ pred = lambda x: x in set('cmowz.')
+
+ self.assertEqual(list(mi.lstrip(iterable, pred)), list('example.com'))
+ self.assertEqual(list(mi.rstrip(iterable, pred)), list('www.example'))
+ self.assertEqual(list(mi.strip(iterable, pred)), list('example'))
+
+ def test_not_hashable(self):
+ iterable = [
+ list('http://'), list('www'), list('.example'), list('.com')
+ ]
+ pred = lambda x: x in [list('http://'), list('www'), list('.com')]
+
+ self.assertEqual(list(mi.lstrip(iterable, pred)), iterable[2:])
+ self.assertEqual(list(mi.rstrip(iterable, pred)), iterable[:3])
+ self.assertEqual(list(mi.strip(iterable, pred)), iterable[2: 3])
+
+ def test_math(self):
+ iterable = [0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2]
+ pred = lambda x: x <= 2
+
+ self.assertEqual(list(mi.lstrip(iterable, pred)), iterable[3:])
+ self.assertEqual(list(mi.rstrip(iterable, pred)), iterable[:-3])
+ self.assertEqual(list(mi.strip(iterable, pred)), iterable[3:-3])
+
+
+class IsliceExtendedTests(TestCase):
+ def test_all(self):
+ iterable = ['0', '1', '2', '3', '4', '5']
+ indexes = list(range(-4, len(iterable) + 4)) + [None]
+ steps = [1, 2, 3, 4, -1, -2, -3, 4]
+ for slice_args in product(indexes, indexes, steps):
+ try:
+ actual = list(mi.islice_extended(iterable, *slice_args))
+ except Exception as e:
+ self.fail((slice_args, e))
+
+ expected = iterable[slice(*slice_args)]
+ self.assertEqual(actual, expected, slice_args)
+
+ def test_zero_step(self):
+ with self.assertRaises(ValueError):
+ list(mi.islice_extended([1, 2, 3], 0, 1, 0))
+
+
+class ConsecutiveGroupsTest(TestCase):
+ def test_numbers(self):
+ iterable = [-10, -8, -7, -6, 1, 2, 4, 5, -1, 7]
+ actual = [list(g) for g in mi.consecutive_groups(iterable)]
+ expected = [[-10], [-8, -7, -6], [1, 2], [4, 5], [-1], [7]]
+ self.assertEqual(actual, expected)
+
+ def test_custom_ordering(self):
+ iterable = ['1', '10', '11', '20', '21', '22', '30', '31']
+ ordering = lambda x: int(x)
+ actual = [list(g) for g in mi.consecutive_groups(iterable, ordering)]
+ expected = [['1'], ['10', '11'], ['20', '21', '22'], ['30', '31']]
+ self.assertEqual(actual, expected)
+
+ def test_exotic_ordering(self):
+ iterable = [
+ ('a', 'b', 'c', 'd'),
+ ('a', 'c', 'b', 'd'),
+ ('a', 'c', 'd', 'b'),
+ ('a', 'd', 'b', 'c'),
+ ('d', 'b', 'c', 'a'),
+ ('d', 'c', 'a', 'b'),
+ ]
+ ordering = list(permutations('abcd')).index
+ actual = [list(g) for g in mi.consecutive_groups(iterable, ordering)]
+ expected = [
+ [('a', 'b', 'c', 'd')],
+ [('a', 'c', 'b', 'd'), ('a', 'c', 'd', 'b'), ('a', 'd', 'b', 'c')],
+ [('d', 'b', 'c', 'a'), ('d', 'c', 'a', 'b')],
+ ]
+ self.assertEqual(actual, expected)
+
+
+class DifferenceTest(TestCase):
+ def test_normal(self):
+ iterable = [10, 20, 30, 40, 50]
+ actual = list(mi.difference(iterable))
+ expected = [10, 10, 10, 10, 10]
+ self.assertEqual(actual, expected)
+
+ def test_custom(self):
+ iterable = [10, 20, 30, 40, 50]
+ actual = list(mi.difference(iterable, add))
+ expected = [10, 30, 50, 70, 90]
+ self.assertEqual(actual, expected)
+
+ def test_roundtrip(self):
+ original = list(range(100))
+ accumulated = mi.accumulate(original)
+ actual = list(mi.difference(accumulated))
+ self.assertEqual(actual, original)
+
+ def test_one(self):
+ self.assertEqual(list(mi.difference([0])), [0])
+
+ def test_empty(self):
+ self.assertEqual(list(mi.difference([])), [])
+
+
+class SeekableTest(TestCase):
+ def test_exhaustion_reset(self):
+ iterable = [str(n) for n in range(10)]
+
+ s = mi.seekable(iterable)
+ self.assertEqual(list(s), iterable) # Normal iteration
+ self.assertEqual(list(s), []) # Iterable is exhausted
+
+ s.seek(0)
+ self.assertEqual(list(s), iterable) # Back in action
+
+ def test_partial_reset(self):
+ iterable = [str(n) for n in range(10)]
+
+ s = mi.seekable(iterable)
+ self.assertEqual(mi.take(5, s), iterable[:5]) # Normal iteration
+
+ s.seek(1)
+ self.assertEqual(list(s), iterable[1:]) # Get the rest of the iterable
+
+ def test_forward(self):
+ iterable = [str(n) for n in range(10)]
+
+ s = mi.seekable(iterable)
+ self.assertEqual(mi.take(1, s), iterable[:1]) # Normal iteration
+
+ s.seek(3) # Skip over index 2
+ self.assertEqual(list(s), iterable[3:]) # Result is similar to slicing
+
+ s.seek(0) # Back to 0
+ self.assertEqual(list(s), iterable) # No difference in result
+
+ def test_past_end(self):
+ iterable = [str(n) for n in range(10)]
+
+ s = mi.seekable(iterable)
+ self.assertEqual(mi.take(1, s), iterable[:1]) # Normal iteration
+
+ s.seek(20)
+ self.assertEqual(list(s), []) # Iterable is exhausted
+
+ s.seek(0) # Back to 0
+ self.assertEqual(list(s), iterable) # No difference in result
+
+ def test_elements(self):
+ iterable = map(str, count())
+
+ s = mi.seekable(iterable)
+ mi.take(10, s)
+
+ elements = s.elements()
+ self.assertEqual(
+ [elements[i] for i in range(10)], [str(n) for n in range(10)]
+ )
+ self.assertEqual(len(elements), 10)
+
+ mi.take(10, s)
+ self.assertEqual(list(elements), [str(n) for n in range(20)])
+
+
+class SequenceViewTests(TestCase):
+ def test_init(self):
+ view = mi.SequenceView((1, 2, 3))
+ self.assertEqual(repr(view), "SequenceView((1, 2, 3))")
+ self.assertRaises(TypeError, lambda: mi.SequenceView({}))
+
+ def test_update(self):
+ seq = [1, 2, 3]
+ view = mi.SequenceView(seq)
+ self.assertEqual(len(view), 3)
+ self.assertEqual(repr(view), "SequenceView([1, 2, 3])")
+
+ seq.pop()
+ self.assertEqual(len(view), 2)
+ self.assertEqual(repr(view), "SequenceView([1, 2])")
+
+ def test_indexing(self):
+ seq = ('a', 'b', 'c', 'd', 'e', 'f')
+ view = mi.SequenceView(seq)
+ for i in range(-len(seq), len(seq)):
+ self.assertEqual(view[i], seq[i])
+
+ def test_slicing(self):
+ seq = ('a', 'b', 'c', 'd', 'e', 'f')
+ view = mi.SequenceView(seq)
+ n = len(seq)
+ indexes = list(range(-n - 1, n + 1)) + [None]
+ steps = list(range(-n, n + 1))
+ steps.remove(0)
+ for slice_args in product(indexes, indexes, steps):
+ i = slice(*slice_args)
+ self.assertEqual(view[i], seq[i])
+
+ def test_abc_methods(self):
+ # collections.Sequence should provide all of this functionality
+ seq = ('a', 'b', 'c', 'd', 'e', 'f', 'f')
+ view = mi.SequenceView(seq)
+
+ # __contains__
+ self.assertIn('b', view)
+ self.assertNotIn('g', view)
+
+ # __iter__
+ self.assertEqual(list(iter(view)), list(seq))
+
+ # __reversed__
+ self.assertEqual(list(reversed(view)), list(reversed(seq)))
+
+ # index
+ self.assertEqual(view.index('b'), 1)
+
+ # count
+ self.assertEqual(seq.count('f'), 2)
+
+
+class RunLengthTest(TestCase):
+ def test_encode(self):
+ iterable = (int(str(n)[0]) for n in count(800))
+ actual = mi.take(4, mi.run_length.encode(iterable))
+ expected = [(8, 100), (9, 100), (1, 1000), (2, 1000)]
+ self.assertEqual(actual, expected)
+
+ def test_decode(self):
+ iterable = [('d', 4), ('c', 3), ('b', 2), ('a', 1)]
+ actual = ''.join(mi.run_length.decode(iterable))
+ expected = 'ddddcccbba'
+ self.assertEqual(actual, expected)
+
+
+class ExactlyNTests(TestCase):
+ """Tests for ``exactly_n()``"""
+
+ def test_true(self):
+ """Iterable has ``n`` ``True`` elements"""
+ self.assertTrue(mi.exactly_n([True, False, True], 2))
+ self.assertTrue(mi.exactly_n([1, 1, 1, 0], 3))
+ self.assertTrue(mi.exactly_n([False, False], 0))
+ self.assertTrue(mi.exactly_n(range(100), 10, lambda x: x < 10))
+
+ def test_false(self):
+ """Iterable does not have ``n`` ``True`` elements"""
+ self.assertFalse(mi.exactly_n([True, False, False], 2))
+ self.assertFalse(mi.exactly_n([True, True, False], 1))
+ self.assertFalse(mi.exactly_n([False], 1))
+ self.assertFalse(mi.exactly_n([True], -1))
+ self.assertFalse(mi.exactly_n(repeat(True), 100))
+
+ def test_empty(self):
+ """Return ``True`` if the iterable is empty and ``n`` is 0"""
+ self.assertTrue(mi.exactly_n([], 0))
+ self.assertFalse(mi.exactly_n([], 1))
+
+
+class AlwaysReversibleTests(TestCase):
+ """Tests for ``always_reversible()``"""
+
+ def test_regular_reversed(self):
+ self.assertEqual(list(reversed(range(10))),
+ list(mi.always_reversible(range(10))))
+ self.assertEqual(list(reversed([1, 2, 3])),
+ list(mi.always_reversible([1, 2, 3])))
+ self.assertEqual(reversed([1, 2, 3]).__class__,
+ mi.always_reversible([1, 2, 3]).__class__)
+
+ def test_nonseq_reversed(self):
+ # Create a non-reversible generator from a sequence
+ with self.assertRaises(TypeError):
+ reversed(x for x in range(10))
+
+ self.assertEqual(list(reversed(range(10))),
+ list(mi.always_reversible(x for x in range(10))))
+ self.assertEqual(list(reversed([1, 2, 3])),
+ list(mi.always_reversible(x for x in [1, 2, 3])))
+ self.assertNotEqual(reversed((1, 2)).__class__,
+ mi.always_reversible(x for x in (1, 2)).__class__)
+
+
+class CircularShiftsTests(TestCase):
+ def test_empty(self):
+ # empty iterable -> empty list
+ self.assertEqual(list(mi.circular_shifts([])), [])
+
+ def test_simple_circular_shifts(self):
+ # test the a simple iterator case
+ self.assertEqual(
+ mi.circular_shifts(range(4)),
+ [(0, 1, 2, 3), (1, 2, 3, 0), (2, 3, 0, 1), (3, 0, 1, 2)]
+ )
+
+ def test_duplicates(self):
+ # test non-distinct entries
+ self.assertEqual(
+ mi.circular_shifts([0, 1, 0, 1]),
+ [(0, 1, 0, 1), (1, 0, 1, 0), (0, 1, 0, 1), (1, 0, 1, 0)]
+ )
+
+
+class MakeDecoratorTests(TestCase):
+ def test_basic(self):
+ slicer = mi.make_decorator(islice)
+
+ @slicer(1, 10, 2)
+ def user_function(arg_1, arg_2, kwarg_1=None):
+ self.assertEqual(arg_1, 'arg_1')
+ self.assertEqual(arg_2, 'arg_2')
+ self.assertEqual(kwarg_1, 'kwarg_1')
+ return map(str, count())
+
+ it = user_function('arg_1', 'arg_2', kwarg_1='kwarg_1')
+ actual = list(it)
+ expected = ['1', '3', '5', '7', '9']
+ self.assertEqual(actual, expected)
+
+ def test_result_index(self):
+ def stringify(*args, **kwargs):
+ self.assertEqual(args[0], 'arg_0')
+ iterable = args[1]
+ self.assertEqual(args[2], 'arg_2')
+ self.assertEqual(kwargs['kwarg_1'], 'kwarg_1')
+ return map(str, iterable)
+
+ stringifier = mi.make_decorator(stringify, result_index=1)
+
+ @stringifier('arg_0', 'arg_2', kwarg_1='kwarg_1')
+ def user_function(n):
+ return count(n)
+
+ it = user_function(1)
+ actual = mi.take(5, it)
+ expected = ['1', '2', '3', '4', '5']
+ self.assertEqual(actual, expected)
+
+ def test_wrap_class(self):
+ seeker = mi.make_decorator(mi.seekable)
+
+ @seeker()
+ def user_function(n):
+ return map(str, range(n))
+
+ it = user_function(5)
+ self.assertEqual(list(it), ['0', '1', '2', '3', '4'])
+
+ it.seek(0)
+ self.assertEqual(list(it), ['0', '1', '2', '3', '4'])
+
+
+class MapReduceTests(TestCase):
+ def test_default(self):
+ iterable = (str(x) for x in range(5))
+ keyfunc = lambda x: int(x) // 2
+ actual = sorted(mi.map_reduce(iterable, keyfunc).items())
+ expected = [(0, ['0', '1']), (1, ['2', '3']), (2, ['4'])]
+ self.assertEqual(actual, expected)
+
+ def test_valuefunc(self):
+ iterable = (str(x) for x in range(5))
+ keyfunc = lambda x: int(x) // 2
+ valuefunc = int
+ actual = sorted(mi.map_reduce(iterable, keyfunc, valuefunc).items())
+ expected = [(0, [0, 1]), (1, [2, 3]), (2, [4])]
+ self.assertEqual(actual, expected)
+
+ def test_reducefunc(self):
+ iterable = (str(x) for x in range(5))
+ keyfunc = lambda x: int(x) // 2
+ valuefunc = int
+ reducefunc = lambda value_list: reduce(mul, value_list, 1)
+ actual = sorted(
+ mi.map_reduce(iterable, keyfunc, valuefunc, reducefunc).items()
+ )
+ expected = [(0, 0), (1, 6), (2, 4)]
+ self.assertEqual(actual, expected)
+
+ def test_ret(self):
+ d = mi.map_reduce([1, 0, 2, 0, 1, 0], bool)
+ self.assertEqual(d, {False: [0, 0, 0], True: [1, 2, 1]})
+ self.assertRaises(KeyError, lambda: d[None].append(1))
new file mode 100644
--- /dev/null
+++ b/testing/web-platform/tests/tools/third_party/more-itertools/more_itertools/tests/test_recipes.py
@@ -0,0 +1,607 @@
+from doctest import DocTestSuite
+from unittest import TestCase
+
+from itertools import combinations
+from six.moves import range
+
+import more_itertools as mi
+
+
+def load_tests(loader, tests, ignore):
+ # Add the doctests
+ tests.addTests(DocTestSuite('more_itertools.recipes'))
+ return tests
+
+
+class AccumulateTests(TestCase):
+ """Tests for ``accumulate()``"""
+
+ def test_empty(self):
+ """Test that an empty input returns an empty output"""
+ self.assertEqual(list(mi.accumulate([])), [])
+
+ def test_default(self):
+ """Test accumulate with the default function (addition)"""
+ self.assertEqual(list(mi.accumulate([1, 2, 3])), [1, 3, 6])
+
+ def test_bogus_function(self):
+ """Test accumulate with an invalid function"""
+ with self.assertRaises(TypeError):
+ list(mi.accumulate([1, 2, 3], func=lambda x: x))
+
+ def test_custom_function(self):
+ """Test accumulate with a custom function"""
+ self.assertEqual(
+ list(mi.accumulate((1, 2, 3, 2, 1), func=max)), [1, 2, 3, 3, 3]
+ )
+
+
+class TakeTests(TestCase):
+ """Tests for ``take()``"""
+
+ def test_simple_take(self):
+ """Test basic usage"""
+ t = mi.take(5, range(10))
+ self.assertEqual(t, [0, 1, 2, 3, 4])
+
+ def test_null_take(self):
+ """Check the null case"""
+ t = mi.take(0, range(10))
+ self.assertEqual(t, [])
+
+ def test_negative_take(self):
+ """Make sure taking negative items results in a ValueError"""
+ self.assertRaises(ValueError, lambda: mi.take(-3, range(10)))
+
+ def test_take_too_much(self):
+ """Taking more than an iterator has remaining should return what the
+ iterator has remaining.
+
+ """
+ t = mi.take(10, range(5))
+ self.assertEqual(t, [0, 1, 2, 3, 4])
+
+
+class TabulateTests(TestCase):
+ """Tests for ``tabulate()``"""
+
+ def test_simple_tabulate(self):
+ """Test the happy path"""
+ t = mi.tabulate(lambda x: x)
+ f = tuple([next(t) for _ in range(3)])
+ self.assertEqual(f, (0, 1, 2))
+
+ def test_count(self):
+ """Ensure tabulate accepts specific count"""
+ t = mi.tabulate(lambda x: 2 * x, -1)
+ f = (next(t), next(t), next(t))
+ self.assertEqual(f, (-2, 0, 2))
+
+
+class TailTests(TestCase):
+ """Tests for ``tail()``"""
+
+ def test_greater(self):
+ """Length of iterable is greather than requested tail"""
+ self.assertEqual(list(mi.tail(3, 'ABCDEFG')), ['E', 'F', 'G'])
+
+ def test_equal(self):
+ """Length of iterable is equal to the requested tail"""
+ self.assertEqual(
+ list(mi.tail(7, 'ABCDEFG')), ['A', 'B', 'C', 'D', 'E', 'F', 'G']
+ )
+
+ def test_less(self):
+ """Length of iterable is less than requested tail"""
+ self.assertEqual(
+ list(mi.tail(8, 'ABCDEFG')), ['A', 'B', 'C', 'D', 'E', 'F', 'G']
+ )
+
+
+class ConsumeTests(TestCase):
+ """Tests for ``consume()``"""
+
+ def test_sanity(self):
+ """Test basic functionality"""
+ r = (x for x in range(10))
+ mi.consume(r, 3)
+ self.assertEqual(3, next(r))
+
+ def test_null_consume(self):
+ """Check the null case"""
+ r = (x for x in range(10))
+ mi.consume(r, 0)
+ self.assertEqual(0, next(r))
+
+ def test_negative_consume(self):
+ """Check that negative consumsion throws an error"""
+ r = (x for x in range(10))
+ self.assertRaises(ValueError, lambda: mi.consume(r, -1))
+
+ def test_total_consume(self):
+ """Check that iterator is totally consumed by default"""
+ r = (x for x in range(10))
+ mi.consume(r)
+ self.assertRaises(StopIteration, lambda: next(r))
+
+
+class NthTests(TestCase):
+ """Tests for ``nth()``"""
+
+ def test_basic(self):
+ """Make sure the nth item is returned"""
+ l = range(10)
+ for i, v in enumerate(l):
+ self.assertEqual(mi.nth(l, i), v)
+
+ def test_default(self):
+ """Ensure a default value is returned when nth item not found"""
+ l = range(3)
+ self.assertEqual(mi.nth(l, 100, "zebra"), "zebra")
+
+ def test_negative_item_raises(self):
+ """Ensure asking for a negative item raises an exception"""
+ self.assertRaises(ValueError, lambda: mi.nth(range(10), -3))
+
+
+class AllEqualTests(TestCase):
+ """Tests for ``all_equal()``"""
+
+ def test_true(self):
+ """Everything is equal"""
+ self.assertTrue(mi.all_equal('aaaaaa'))
+ self.assertTrue(mi.all_equal([0, 0, 0, 0]))
+
+ def test_false(self):
+ """Not everything is equal"""
+ self.assertFalse(mi.all_equal('aaaaab'))
+ self.assertFalse(mi.all_equal([0, 0, 0, 1]))
+
+ def test_tricky(self):
+ """Not everything is identical, but everything is equal"""
+ items = [1, complex(1, 0), 1.0]
+ self.assertTrue(mi.all_equal(items))
+
+ def test_empty(self):
+ """Return True if the iterable is empty"""
+ self.assertTrue(mi.all_equal(''))
+ self.assertTrue(mi.all_equal([]))
+
+ def test_one(self):
+ """Return True if the iterable is singular"""
+ self.assertTrue(mi.all_equal('0'))
+ self.assertTrue(mi.all_equal([0]))
+
+
+class QuantifyTests(TestCase):
+ """Tests for ``quantify()``"""
+
+ def test_happy_path(self):
+ """Make sure True count is returned"""
+ q = [True, False, True]
+ self.assertEqual(mi.quantify(q), 2)
+
+ def test_custom_predicate(self):
+ """Ensure non-default predicates return as expected"""
+ q = range(10)
+ self.assertEqual(mi.quantify(q, lambda x: x % 2 == 0), 5)
+
+
+class PadnoneTests(TestCase):
+ """Tests for ``padnone()``"""
+
+ def test_happy_path(self):
+ """wrapper iterator should return None indefinitely"""
+ r = range(2)
+ p = mi.padnone(r)
+ self.assertEqual([0, 1, None, None], [next(p) for _ in range(4)])
+
+
+class NcyclesTests(TestCase):
+ """Tests for ``nyclces()``"""
+
+ def test_happy_path(self):
+ """cycle a sequence three times"""
+ r = ["a", "b", "c"]
+ n = mi.ncycles(r, 3)
+ self.assertEqual(
+ ["a", "b", "c", "a", "b", "c", "a", "b", "c"],
+ list(n)
+ )
+
+ def test_null_case(self):
+ """asking for 0 cycles should return an empty iterator"""
+ n = mi.ncycles(range(100), 0)
+ self.assertRaises(StopIteration, lambda: next(n))
+
+ def test_pathalogical_case(self):
+ """asking for negative cycles should return an empty iterator"""
+ n = mi.ncycles(range(100), -10)
+ self.assertRaises(StopIteration, lambda: next(n))
+
+
+class DotproductTests(TestCase):
+ """Tests for ``dotproduct()``'"""
+
+ def test_happy_path(self):
+ """simple dotproduct example"""
+ self.assertEqual(400, mi.dotproduct([10, 10], [20, 20]))
+
+
+class FlattenTests(TestCase):
+ """Tests for ``flatten()``"""
+
+ def test_basic_usage(self):
+ """ensure list of lists is flattened one level"""
+ f = [[0, 1, 2], [3, 4, 5]]
+ self.assertEqual(list(range(6)), list(mi.flatten(f)))
+
+ def test_single_level(self):
+ """ensure list of lists is flattened only one level"""
+ f = [[0, [1, 2]], [[3, 4], 5]]
+ self.assertEqual([0, [1, 2], [3, 4], 5], list(mi.flatten(f)))
+
+
+class RepeatfuncTests(TestCase):
+ """Tests for ``repeatfunc()``"""
+
+ def test_simple_repeat(self):
+ """test simple repeated functions"""
+ r = mi.repeatfunc(lambda: 5)
+ self.assertEqual([5, 5, 5, 5, 5], [next(r) for _ in range(5)])
+
+ def test_finite_repeat(self):
+ """ensure limited repeat when times is provided"""
+ r = mi.repeatfunc(lambda: 5, times=5)
+ self.assertEqual([5, 5, 5, 5, 5], list(r))
+
+ def test_added_arguments(self):
+ """ensure arguments are applied to the function"""
+ r = mi.repeatfunc(lambda x: x, 2, 3)
+ self.assertEqual([3, 3], list(r))
+
+ def test_null_times(self):
+ """repeat 0 should return an empty iterator"""
+ r = mi.repeatfunc(range, 0, 3)
+ self.assertRaises(StopIteration, lambda: next(r))
+
+
+class PairwiseTests(TestCase):
+ """Tests for ``pairwise()``"""
+
+ def test_base_case(self):
+ """ensure an iterable will return pairwise"""
+ p = mi.pairwise([1, 2, 3])
+ self.assertEqual([(1, 2), (2, 3)], list(p))
+
+ def test_short_case(self):
+ """ensure an empty iterator if there's not enough values to pair"""
+ p = mi.pairwise("a")
+ self.assertRaises(StopIteration, lambda: next(p))
+
+
+class GrouperTests(TestCase):
+ """Tests for ``grouper()``"""
+
+ def test_even(self):
+ """Test when group size divides evenly into the length of
+ the iterable.
+
+ """
+ self.assertEqual(
+ list(mi.grouper(3, 'ABCDEF')), [('A', 'B', 'C'), ('D', 'E', 'F')]
+ )
+
+ def test_odd(self):
+ """Test when group size does not divide evenly into the length of the
+ iterable.
+
+ """
+ self.assertEqual(
+ list(mi.grouper(3, 'ABCDE')), [('A', 'B', 'C'), ('D', 'E', None)]
+ )
+
+ def test_fill_value(self):
+ """Test that the fill value is used to pad the final group"""
+ self.assertEqual(
+ list(mi.grouper(3, 'ABCDE', 'x')),
+ [('A', 'B', 'C'), ('D', 'E', 'x')]
+ )
+
+
+class RoundrobinTests(TestCase):
+ """Tests for ``roundrobin()``"""
+
+ def test_even_groups(self):
+ """Ensure ordered output from evenly populated iterables"""
+ self.assertEqual(
+ list(mi.roundrobin('ABC', [1, 2, 3], range(3))),
+ ['A', 1, 0, 'B', 2, 1, 'C', 3, 2]
+ )
+
+ def test_uneven_groups(self):
+ """Ensure ordered output from unevenly populated iterables"""
+ self.assertEqual(
+ list(mi.roundrobin('ABCD', [1, 2], range(0))),
+ ['A', 1, 'B', 2, 'C', 'D']
+ )
+
+
+class PartitionTests(TestCase):
+ """Tests for ``partition()``"""
+
+ def test_bool(self):
+ """Test when pred() returns a boolean"""
+ lesser, greater = mi.partition(lambda x: x > 5, range(10))
+ self.assertEqual(list(lesser), [0, 1, 2, 3, 4, 5])
+ self.assertEqual(list(greater), [6, 7, 8, 9])
+
+ def test_arbitrary(self):
+ """Test when pred() returns an integer"""
+ divisibles, remainders = mi.partition(lambda x: x % 3, range(10))
+ self.assertEqual(list(divisibles), [0, 3, 6, 9])
+ self.assertEqual(list(remainders), [1, 2, 4, 5, 7, 8])
+
+
+class PowersetTests(TestCase):
+ """Tests for ``powerset()``"""
+
+ def test_combinatorics(self):
+ """Ensure a proper enumeration"""
+ p = mi.powerset([1, 2, 3])
+ self.assertEqual(
+ list(p),
+ [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
+ )
+
+
+class UniqueEverseenTests(TestCase):
+ """Tests for ``unique_everseen()``"""
+
+ def test_everseen(self):
+ """ensure duplicate elements are ignored"""
+ u = mi.unique_everseen('AAAABBBBCCDAABBB')
+ self.assertEqual(
+ ['A', 'B', 'C', 'D'],
+ list(u)
+ )
+
+ def test_custom_key(self):
+ """ensure the custom key comparison works"""
+ u = mi.unique_everseen('aAbACCc', key=str.lower)
+ self.assertEqual(list('abC'), list(u))
+
+ def test_unhashable(self):
+ """ensure things work for unhashable items"""
+ iterable = ['a', [1, 2, 3], [1, 2, 3], 'a']
+ u = mi.unique_everseen(iterable)
+ self.assertEqual(list(u), ['a', [1, 2, 3]])
+
+ def test_unhashable_key(self):
+ """ensure things work for unhashable items with a custom key"""
+ iterable = ['a', [1, 2, 3], [1, 2, 3], 'a']
+ u = mi.unique_everseen(iterable, key=lambda x: x)
+ self.assertEqual(list(u), ['a', [1, 2, 3]])
+
+
+class UniqueJustseenTests(TestCase):
+ """Tests for ``unique_justseen()``"""
+
+ def test_justseen(self):
+ """ensure only last item is remembered"""
+ u = mi.unique_justseen('AAAABBBCCDABB')
+ self.assertEqual(list('ABCDAB'), list(u))
+
+ def test_custom_key(self):
+ """ensure the custom key comparison works"""
+ u = mi.unique_justseen('AABCcAD', str.lower)
+ self.assertEqual(list('ABCAD'), list(u))
+
+
+class IterExceptTests(TestCase):
+ """Tests for ``iter_except()``"""
+
+ def test_exact_exception(self):
+ """ensure the exact specified exception is caught"""
+ l = [1, 2, 3]
+ i = mi.iter_except(l.pop, IndexError)
+ self.assertEqual(list(i), [3, 2, 1])
+
+ def test_generic_exception(self):
+ """ensure the generic exception can be caught"""
+ l = [1, 2]
+ i = mi.iter_except(l.pop, Exception)
+ self.assertEqual(list(i), [2, 1])
+
+ def test_uncaught_exception_is_raised(self):
+ """ensure a non-specified exception is raised"""
+ l = [1, 2, 3]
+ i = mi.iter_except(l.pop, KeyError)
+ self.assertRaises(IndexError, lambda: list(i))
+
+ def test_first(self):
+ """ensure first is run before the function"""
+ l = [1, 2, 3]
+ f = lambda: 25
+ i = mi.iter_except(l.pop, IndexError, f)
+ self.assertEqual(list(i), [25, 3, 2, 1])
+
+
+class FirstTrueTests(TestCase):
+ """Tests for ``first_true()``"""
+
+ def test_something_true(self):
+ """Test with no keywords"""
+ self.assertEqual(mi.first_true(range(10)), 1)
+
+ def test_nothing_true(self):
+ """Test default return value."""
+ self.assertEqual(mi.first_true([0, 0, 0]), False)
+
+ def test_default(self):
+ """Test with a default keyword"""
+ self.assertEqual(mi.first_true([0, 0, 0], default='!'), '!')
+
+ def test_pred(self):
+ """Test with a custom predicate"""
+ self.assertEqual(
+ mi.first_true([2, 4, 6], pred=lambda x: x % 3 == 0), 6
+ )
+
+
+class RandomProductTests(TestCase):
+ """Tests for ``random_product()``
+
+ Since random.choice() has different results with the same seed across
+ python versions 2.x and 3.x, these tests use highly probably events to
+ create predictable outcomes across platforms.
+ """
+
+ def test_simple_lists(self):
+ """Ensure that one item is chosen from each list in each pair.
+ Also ensure that each item from each list eventually appears in
+ the chosen combinations.
+
+ Odds are roughly 1 in 7.1 * 10e16 that one item from either list will
+ not be chosen after 100 samplings of one item from each list. Just to
+ be safe, better use a known random seed, too.
+
+ """
+ nums = [1, 2, 3]
+ lets = ['a', 'b', 'c']
+ n, m = zip(*[mi.random_product(nums, lets) for _ in range(100)])
+ n, m = set(n), set(m)
+ self.assertEqual(n, set(nums))
+ self.assertEqual(m, set(lets))
+ self.assertEqual(len(n), len(nums))
+ self.assertEqual(len(m), len(lets))
+
+ def test_list_with_repeat(self):
+ """ensure multiple items are chosen, and that they appear to be chosen
+ from one list then the next, in proper order.
+
+ """
+ nums = [1, 2, 3]
+ lets = ['a', 'b', 'c']
+ r = list(mi.random_product(nums, lets, repeat=100))
+ self.assertEqual(2 * 100, len(r))
+ n, m = set(r[::2]), set(r[1::2])
+ self.assertEqual(n, set(nums))
+ self.assertEqual(m, set(lets))
+ self.assertEqual(len(n), len(nums))
+ self.assertEqual(len(m), len(lets))
+
+
+class RandomPermutationTests(TestCase):
+ """Tests for ``random_permutation()``"""
+
+ def test_full_permutation(self):
+ """ensure every item from the iterable is returned in a new ordering
+
+ 15 elements have a 1 in 1.3 * 10e12 of appearing in sorted order, so
+ we fix a seed value just to be sure.
+
+ """
+ i = range(15)
+ r = mi.random_permutation(i)
+ self.assertEqual(set(i), set(r))
+ if i == r:
+ raise AssertionError("Values were not permuted")
+
+ def test_partial_permutation(self):
+ """ensure all returned items are from the iterable, that the returned
+ permutation is of the desired length, and that all items eventually
+ get returned.
+
+ Sampling 100 permutations of length 5 from a set of 15 leaves a
+ (2/3)^100 chance that an item will not be chosen. Multiplied by 15
+ items, there is a 1 in 2.6e16 chance that at least 1 item will not
+ show up in the resulting output. Using a random seed will fix that.
+
+ """
+ items = range(15)
+ item_set = set(items)
+ all_items = set()
+ for _ in range(100):
+ permutation = mi.random_permutation(items, 5)
+ self.assertEqual(len(permutation), 5)
+ permutation_set = set(permutation)
+ self.assertLessEqual(permutation_set, item_set)
+ all_items |= permutation_set
+ self.assertEqual(all_items, item_set)
+
+
+class RandomCombinationTests(TestCase):
+ """Tests for ``random_combination()``"""
+
+ def test_psuedorandomness(self):
+ """ensure different subsets of the iterable get returned over many
+ samplings of random combinations"""
+ items = range(15)
+ all_items = set()
+ for _ in range(50):
+ combination = mi.random_combination(items, 5)
+ all_items |= set(combination)
+ self.assertEqual(all_items, set(items))
+
+ def test_no_replacement(self):
+ """ensure that elements are sampled without replacement"""
+ items = range(15)
+ for _ in range(50):
+ combination = mi.random_combination(items, len(items))
+ self.assertEqual(len(combination), len(set(combination)))
+ self.assertRaises(
+ ValueError, lambda: mi.random_combination(items, len(items) + 1)
+ )
+
+
+class RandomCombinationWithReplacementTests(TestCase):
+ """Tests for ``random_combination_with_replacement()``"""
+
+ def test_replacement(self):
+ """ensure that elements are sampled with replacement"""
+ items = range(5)
+ combo = mi.random_combination_with_replacement(items, len(items) * 2)
+ self.assertEqual(2 * len(items), len(combo))
+ if len(set(combo)) == len(combo):
+ raise AssertionError("Combination contained no duplicates")
+
+ def test_pseudorandomness(self):
+ """ensure different subsets of the iterable get returned over many
+ samplings of random combinations"""
+ items = range(15)
+ all_items = set()
+ for _ in range(50):
+ combination = mi.random_combination_with_replacement(items, 5)
+ all_items |= set(combination)
+ self.assertEqual(all_items, set(items))
+
+
+class NthCombinationTests(TestCase):
+ def test_basic(self):
+ iterable = 'abcdefg'
+ r = 4
+ for index, expected in enumerate(combinations(iterable, r)):
+ actual = mi.nth_combination(iterable, r, index)
+ self.assertEqual(actual, expected)
+
+ def test_long(self):
+ actual = mi.nth_combination(range(180), 4, 2000000)
+ expected = (2, 12, 35, 126)
+ self.assertEqual(actual, expected)
+
+
+class PrependTests(TestCase):
+ def test_basic(self):
+ value = 'a'
+ iterator = iter('bcdefg')
+ actual = list(mi.prepend(value, iterator))
+ expected = list('abcdefg')
+ self.assertEqual(actual, expected)
+
+ def test_multiple(self):
+ value = 'ab'
+ iterator = iter('cdefg')
+ actual = tuple(mi.prepend(value, iterator))
+ expected = ('ab',) + tuple('cdefg')
+ self.assertEqual(actual, expected)
new file mode 100644
--- /dev/null
+++ b/testing/web-platform/tests/tools/third_party/more-itertools/setup.cfg
@@ -0,0 +1,3 @@
+[flake8]
+exclude = ./docs/conf.py, .eggs/
+ignore = E731, E741, F999
new file mode 100644
--- /dev/null
+++ b/testing/web-platform/tests/tools/third_party/more-itertools/setup.py
@@ -0,0 +1,59 @@
+# Hack to prevent stupid error on exit of `python setup.py test`. (See
+# http://www.eby-sarna.com/pipermail/peak/2010-May/003357.html.)
+try:
+ import multiprocessing # noqa
+except ImportError:
+ pass
+from re import sub
+
+from setuptools import setup, find_packages
+
+
+def get_long_description():
+ # Fix display issues on PyPI caused by RST markup
+ readme = open('README.rst').read()
+
+ version_lines = []
+ with open('docs/versions.rst') as infile:
+ next(infile)
+ for line in infile:
+ line = line.rstrip().replace('.. automodule:: more_itertools', '')
+ version_lines.append(line)
+ version_history = '\n'.join(version_lines)
+ version_history = sub(r':func:`([a-zA-Z0-9._]+)`', r'\1', version_history)
+
+ ret = readme + '\n\n' + version_history
+ return ret
+
+
+setup(
+ name='more-itertools',
+ version='4.2.0',
+ description='More routines for operating on iterables, beyond itertools',
+ long_description=get_long_description(),
+ author='Erik Rose',
+ author_email='erikrose@grinchcentral.com',
+ license='MIT',
+ packages=find_packages(exclude=['ez_setup']),
+ install_requires=['six>=1.0.0,<2.0.0'],
+ test_suite='more_itertools.tests',
+ url='https://github.com/erikrose/more-itertools',
+ include_package_data=True,
+ classifiers=[
+ 'Development Status :: 5 - Production/Stable',
+ 'Intended Audience :: Developers',
+ 'Natural Language :: English',
+ 'License :: OSI Approved :: MIT License',
+ 'Programming Language :: Python :: 2',
+ 'Programming Language :: Python :: 2.7',
+ 'Programming Language :: Python :: 3',
+ 'Programming Language :: Python :: 3.2',
+ 'Programming Language :: Python :: 3.3',
+ 'Programming Language :: Python :: 3.4',
+ 'Programming Language :: Python :: 3.5',
+ 'Programming Language :: Python :: 3.6',
+ 'Programming Language :: Python :: 3.7',
+ 'Topic :: Software Development :: Libraries'],
+ keywords=['itertools', 'iterator', 'iteration', 'filter', 'peek',
+ 'peekable', 'collate', 'chunk', 'chunked'],
+)
new file mode 100644
--- /dev/null
+++ b/testing/web-platform/tests/tools/third_party/more-itertools/tox.ini
@@ -0,0 +1,5 @@
+[tox]
+envlist = py27, py34, py35, py36, py37
+
+[testenv]
+commands = {envbindir}/python -m unittest discover -v