:mod:`collections` --- High-performance container datatypes

===========================================================

.. module:: collections

   :synopsis: High-performance datatypes

.. moduleauthor:: Raymond Hettinger <python@rcn.com>

.. sectionauthor:: Raymond Hettinger <python@rcn.com>

.. versionadded:: 2.4

.. testsetup:: *

   from collections import *

   import itertools

   __name__ = '<doctest>'

This module implements high-performance container datatypes.  Currently,

there are two datatypes, :class:`deque` and :class:`defaultdict`, and

one datatype factory function, :func:`namedtuple`.

.. versionchanged:: 2.5

   Added :class:`defaultdict`.

.. versionchanged:: 2.6

   Added :func:`namedtuple`.

The specialized containers provided in this module provide alternatives

to Python's general purpose built-in containers, :class:`dict`,

:class:`list`, :class:`set`, and :class:`tuple`.

Besides the containers provided here, the optional :mod:`bsddb`

module offers the ability to create in-memory or file based ordered

dictionaries with string keys using the :meth:`bsddb.btopen` method.

In addition to containers, the collections module provides some ABCs

(abstract base classes) that can be used to test whether a class

provides a particular interface, for example, is it hashable or

a mapping.

.. versionchanged:: 2.6

   Added abstract base classes.

ABCs - abstract base classes

----------------------------

The collections module offers the following ABCs:

=========================  =====================  ======================  ====================================================

ABC                        Inherits               Abstract Methods        Mixin Methods

=========================  =====================  ======================  ====================================================

:class:`Container`                                ``__contains__``

:class:`Hashable`                                 ``__hash__``

:class:`Iterable`                                 ``__iter__``

:class:`Iterator`          :class:`Iterable`      ``__next__``            ``__iter__``

:class:`Sized`          			  ``__len__``

:class:`Callable`                                 ``__call__``

:class:`Sequence`          :class:`Sized`,        ``__getitem__``         ``__contains__``. ``__iter__``, ``__reversed__``.

                           :class:`Iterable`,     and ``__len__``         ``index``, and ``count``

                           :class:`Container`     

:class:`MutableSequnce`    :class:`Sequence`      ``__getitem__``         Inherited Sequence methods and

                                                  ``__delitem__``,        ``append``, ``reverse``, ``extend``, ``pop``,

                                                  ``insert``,             ``remove``, and ``__iadd__``

                                                  and ``__len__``

:class:`Set`               :class:`Sized`,        ``__len__``,            ``__le__``, ``__lt__``, ``__eq__``, ``__ne__``,

                           :class:`Iterable`,     ``__iter__``, and       ``__gt__``, ``__ge__``, ``__and__``, ``__or__``

                           :class:`Container`     ``__contains__``        ``__sub__``, ``__xor__``, and ``isdisjoint``

:class:`MutableSet`        :class:`Set`           ``add`` and             Inherited Set methods and

                                                  ``discard``             ``clear``, ``pop``, ``remove``, ``__ior__``,

                                                                          ``__iand__``, ``__ixor__``, and ``__isub__``

:class:`Mapping`           :class:`Sized`,        ``__getitem__``,        ``__contains__``, ``keys``, ``items``, ``values``,

                           :class:`Iterable`,     ``__len__``. and        ``get``, ``__eq__``, and ``__ne__``

                           :class:`Container`     ``__iter__``

:class:`MutableMapping`    :class:`Mapping`       ``__getitem__``         Inherited Mapping methods and

                                                  ``__setitem__``,        ``pop``, ``popitem``, ``clear``, ``update``,

                                                  ``__delitem__``,        and ``setdefault``

						  ``__iter__``, and

                                                  ``__len__``

:class:`MappingView`       :class:`Sized`                                 ``__len__``

:class:`KeysView`          :class:`MappingView`,                          ``__contains__``,

                           :class:`Set`                                   ``__iter__``

:class:`ItemsView`         :class:`MappingView`,                          ``__contains__``,

                           :class:`Set`                                   ``__iter__``

:class:`ValuesView`        :class:`MappingView`                           ``__contains__``, ``__iter__``

=========================  =====================  ======================  ====================================================

These ABCs allow us to ask classes or instances if they provide

particular functionality, for example::

    size = None

    if isinstance(myvar, collections.Sized):

	size = len(myvar)

Several of the ABCs are also useful as mixins that make it easier to develop

classes supporting container APIs.  For example, to write a class supporting

the full :class:`Set` API, it only necessary to supply the three underlying

abstract methods: :meth:`__contains__`, :meth:`__iter__`, and :meth:`__len__`.

The ABC supplies the remaining methods such as :meth:`__and__` and

:meth:`isdisjoint` ::

    class ListBasedSet(collections.Set):

         ''' Alternate set implementation favoring space over speed

             and not requiring the set elements to be hashable. '''

         def __init__(self, iterable):

             self.elements = lst = []

             for value in iterable:

                 if value not in lst:

                     lst.append(value)

         def __iter__(self):

             return iter(self.elements)

         def __contains__(self, value):

             return value in self.elements

         def __len__(self):

             return len(self.elements)

    s1 = ListBasedSet('abcdef')

    s2 = ListBasedSet('defghi')

    overlap = s1 & s2            # The __and__() method is supported automatically

Notes on using :class:`Set` and :class:`MutableSet` as a mixin:

(1)

   Since some set operations create new sets, the default mixin methods need

   a way to create new instances from an iterable. The class constructor is

   assumed to have a signature in the form ``ClassName(iterable)``.

   That assumption is factored-out to an internal classmethod called

   :meth:`_from_iterable` which calls ``cls(iterable)`` to produce a new set.

   If the :class:`Set` mixin is being used in a class with a different

   constructor signature, you will need to override :meth:`from_iterable`

   with a classmethod that can construct new instances from

   an iterable argument.

(2)

   To override the comparisons (presumably for speed, as the

   semantics are fixed), redefine :meth:`__le__` and

   then the other operations will automatically follow suit.

(3)

   The :class:`Set` mixin provides a :meth:`_hash` method to compute a hash value

   for the set; however, :meth:`__hash__` is not defined because not all sets

   are hashable or immutable.  To add set hashabilty using mixins,

   inherit from both :meth:`Set` and :meth:`Hashable`, then define

   ``__hash__ = Set._hash``.

(For more about ABCs, see the :mod:`abc` module and :pep:`3119`.)

.. _deque-objects:

:class:`deque` objects

----------------------

.. class:: deque([iterable[, maxlen]])

   Returns a new deque object initialized left-to-right (using :meth:`append`) with

   data from *iterable*.  If *iterable* is not specified, the new deque is empty.

   Deques are a generalization of stacks and queues (the name is pronounced "deck"

   and is short for "double-ended queue").  Deques support thread-safe, memory

   efficient appends and pops from either side of the deque with approximately the

   same O(1) performance in either direction.

   Though :class:`list` objects support similar operations, they are optimized for

   fast fixed-length operations and incur O(n) memory movement costs for

   ``pop(0)`` and ``insert(0, v)`` operations which change both the size and

   position of the underlying data representation.

   .. versionadded:: 2.4

   If *maxlen* is not specified or is *None*, deques may grow to an

   arbitrary length.  Otherwise, the deque is bounded to the specified maximum

   length.  Once a bounded length deque is full, when new items are added, a

   corresponding number of items are discarded from the opposite end.  Bounded

   length deques provide functionality similar to the ``tail`` filter in

   Unix. They are also useful for tracking transactions and other pools of data

   where only the most recent activity is of interest.

   .. versionchanged:: 2.6

      Added *maxlen* parameter.

   Deque objects support the following methods:

   .. method:: append(x)

      Add *x* to the right side of the deque.

   .. method:: appendleft(x)

      Add *x* to the left side of the deque.

   .. method:: clear()

      Remove all elements from the deque leaving it with length 0.

   .. method:: extend(iterable)

      Extend the right side of the deque by appending elements from the iterable

      argument.

   .. method:: extendleft(iterable)

      Extend the left side of the deque by appending elements from *iterable*.

      Note, the series of left appends results in reversing the order of

      elements in the iterable argument.

   .. method:: pop()

      Remove and return an element from the right side of the deque. If no

      elements are present, raises an :exc:`IndexError`.

   .. method:: popleft()

      Remove and return an element from the left side of the deque. If no

      elements are present, raises an :exc:`IndexError`.

   .. method:: remove(value)

      Removed the first occurrence of *value*.  If not found, raises a

      :exc:`ValueError`.

      .. versionadded:: 2.5

   .. method:: rotate(n)

      Rotate the deque *n* steps to the right.  If *n* is negative, rotate to

      the left.  Rotating one step to the right is equivalent to:

      ``d.appendleft(d.pop())``.

In addition to the above, deques support iteration, pickling, ``len(d)``,

``reversed(d)``, ``copy.copy(d)``, ``copy.deepcopy(d)``, membership testing with

the :keyword:`in` operator, and subscript references such as ``d[-1]``.  Indexed

access is O(1) at both ends but slows to O(n) in the middle.  For fast random

access, use lists instead.

Example:

.. doctest::

   >>> from collections import deque

   >>> d = deque('ghi')                 # make a new deque with three items

   >>> for elem in d:                   # iterate over the deque's elements

   ...     print elem.upper()

   G

   H

   I

   >>> d.append('j')                    # add a new entry to the right side

   >>> d.appendleft('f')                # add a new entry to the left side

   >>> d                                # show the representation of the deque

   deque(['f', 'g', 'h', 'i', 'j'])

   >>> d.pop()                          # return and remove the rightmost item

   'j'

   >>> d.popleft()                      # return and remove the leftmost item

   'f'

   >>> list(d)                          # list the contents of the deque

   ['g', 'h', 'i']

   >>> d[0]                             # peek at leftmost item

   'g'

   >>> d[-1]                            # peek at rightmost item

   'i'

   >>> list(reversed(d))                # list the contents of a deque in reverse

   ['i', 'h', 'g']

   >>> 'h' in d                         # search the deque

   True

   >>> d.extend('jkl')                  # add multiple elements at once

   >>> d

   deque(['g', 'h', 'i', 'j', 'k', 'l'])

   >>> d.rotate(1)                      # right rotation

   >>> d

   deque(['l', 'g', 'h', 'i', 'j', 'k'])

   >>> d.rotate(-1)                     # left rotation

   >>> d

   deque(['g', 'h', 'i', 'j', 'k', 'l'])

   >>> deque(reversed(d))               # make a new deque in reverse order

   deque(['l', 'k', 'j', 'i', 'h', 'g'])

   >>> d.clear()                        # empty the deque

   >>> d.pop()                          # cannot pop from an empty deque

   Traceback (most recent call last):

     File "<pyshell#6>", line 1, in -toplevel-

       d.pop()

   IndexError: pop from an empty deque

   >>> d.extendleft('abc')              # extendleft() reverses the input order

   >>> d

   deque(['c', 'b', 'a'])

.. _deque-recipes:

:class:`deque` Recipes

^^^^^^^^^^^^^^^^^^^^^^

This section shows various approaches to working with deques.

The :meth:`rotate` method provides a way to implement :class:`deque` slicing and

deletion.  For example, a pure python implementation of ``del d[n]`` relies on

the :meth:`rotate` method to position elements to be popped::

   def delete_nth(d, n):

       d.rotate(-n)

       d.popleft()

       d.rotate(n)

To implement :class:`deque` slicing, use a similar approach applying

:meth:`rotate` to bring a target element to the left side of the deque. Remove

old entries with :meth:`popleft`, add new entries with :meth:`extend`, and then

reverse the rotation.

With minor variations on that approach, it is easy to implement Forth style

stack manipulations such as ``dup``, ``drop``, ``swap``, ``over``, ``pick``,

``rot``, and ``roll``.

Multi-pass data reduction algorithms can be succinctly expressed and efficiently

coded by extracting elements with multiple calls to :meth:`popleft`, applying

a reduction function, and calling :meth:`append` to add the result back to the

deque.

For example, building a balanced binary tree of nested lists entails reducing

two adjacent nodes into one by grouping them in a list:

   >>> def maketree(iterable):

   ...     d = deque(iterable)

   ...     while len(d) > 1:

   ...         pair = [d.popleft(), d.popleft()]

   ...         d.append(pair)

   ...     return list(d)

   ...

   >>> print maketree('abcdefgh')

   [[[['a', 'b'], ['c', 'd']], [['e', 'f'], ['g', 'h']]]]

Bounded length deques provide functionality similar to the ``tail`` filter

in Unix::

   def tail(filename, n=10):

       'Return the last n lines of a file'

       return deque(open(filename), n)

.. _defaultdict-objects:

:class:`defaultdict` objects

----------------------------

.. class:: defaultdict([default_factory[, ...]])

   Returns a new dictionary-like object.  :class:`defaultdict` is a subclass of the

   builtin :class:`dict` class.  It overrides one method and adds one writable

   instance variable.  The remaining functionality is the same as for the

   :class:`dict` class and is not documented here.

   The first argument provides the initial value for the :attr:`default_factory`

   attribute; it defaults to ``None``. All remaining arguments are treated the same

   as if they were passed to the :class:`dict` constructor, including keyword

   arguments.

   .. versionadded:: 2.5

   :class:`defaultdict` objects support the following method in addition to the

   standard :class:`dict` operations:

   .. method:: defaultdict.__missing__(key)

      If the :attr:`default_factory` attribute is ``None``, this raises a

      :exc:`KeyError` exception with the *key* as argument.

      If :attr:`default_factory` is not ``None``, it is called without arguments

      to provide a default value for the given *key*, this value is inserted in

      the dictionary for the *key*, and returned.

      If calling :attr:`default_factory` raises an exception this exception is

      propagated unchanged.

      This method is called by the :meth:`__getitem__` method of the

      :class:`dict` class when the requested key is not found; whatever it

      returns or raises is then returned or raised by :meth:`__getitem__`.

   :class:`defaultdict` objects support the following instance variable:

   .. attribute:: defaultdict.default_factory

      This attribute is used by the :meth:`__missing__` method; it is

      initialized from the first argument to the constructor, if present, or to

      ``None``, if absent.

.. _defaultdict-examples:

:class:`defaultdict` Examples

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Using :class:`list` as the :attr:`default_factory`, it is easy to group a

sequence of key-value pairs into a dictionary of lists:

   >>> s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]

   >>> d = defaultdict(list)

   >>> for k, v in s:

   ...     d[k].append(v)

   ...

   >>> d.items()

   [('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]

When each key is encountered for the first time, it is not already in the

mapping; so an entry is automatically created using the :attr:`default_factory`

function which returns an empty :class:`list`.  The :meth:`list.append`

operation then attaches the value to the new list.  When keys are encountered

again, the look-up proceeds normally (returning the list for that key) and the

:meth:`list.append` operation adds another value to the list. This technique is

simpler and faster than an equivalent technique using :meth:`dict.setdefault`:

   >>> d = {}

   >>> for k, v in s:

   ...     d.setdefault(k, []).append(v)

   ...

   >>> d.items()

   [('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]

Setting the :attr:`default_factory` to :class:`int` makes the

:class:`defaultdict` useful for counting (like a bag or multiset in other

languages):

   >>> s = 'mississippi'

   >>> d = defaultdict(int)

   >>> for k in s:

   ...     d[k] += 1

   ...

   >>> d.items()

   [('i', 4), ('p', 2), ('s', 4), ('m', 1)]

When a letter is first encountered, it is missing from the mapping, so the

:attr:`default_factory` function calls :func:`int` to supply a default count of

zero.  The increment operation then builds up the count for each letter.

The function :func:`int` which always returns zero is just a special case of

constant functions.  A faster and more flexible way to create constant functions

is to use :func:`itertools.repeat` which can supply any constant value (not just

zero):

   >>> def constant_factory(value):

   ...     return itertools.repeat(value).next

   >>> d = defaultdict(constant_factory('<missing>'))

   >>> d.update(name='John', action='ran')

   >>> '%(name)s %(action)s to %(object)s' % d

   'John ran to <missing>'

Setting the :attr:`default_factory` to :class:`set` makes the

:class:`defaultdict` useful for building a dictionary of sets:

   >>> s = [('red', 1), ('blue', 2), ('red', 3), ('blue', 4), ('red', 1), ('blue', 4)]

   >>> d = defaultdict(set)

   >>> for k, v in s:

   ...     d[k].add(v)

   ...

   >>> d.items()

   [('blue', set([2, 4])), ('red', set([1, 3]))]

.. _named-tuple-factory:

:func:`namedtuple` Factory Function for Tuples with Named Fields

----------------------------------------------------------------

Named tuples assign meaning to each position in a tuple and allow for more readable,

self-documenting code.  They can be used wherever regular tuples are used, and

they add the ability to access fields by name instead of position index.

.. function:: namedtuple(typename, fieldnames, [verbose])

   Returns a new tuple subclass named *typename*.  The new subclass is used to

   create tuple-like objects that have fields accessible by attribute lookup as

   well as being indexable and iterable.  Instances of the subclass also have a

   helpful docstring (with typename and fieldnames) and a helpful :meth:`__repr__`

   method which lists the tuple contents in a ``name=value`` format.

   The *fieldnames* are a single string with each fieldname separated by whitespace

   and/or commas, for example ``'x y'`` or ``'x, y'``.  Alternatively, *fieldnames*

   can be a sequence of strings such as ``['x', 'y']``.

   Any valid Python identifier may be used for a fieldname except for names

   starting with an underscore.  Valid identifiers consist of letters, digits,

   and underscores but do not start with a digit or underscore and cannot be

   a :mod:`keyword` such as *class*, *for*, *return*, *global*, *pass*, *print*,

   or *raise*.

   If *verbose* is true, the class definition is printed just before being built.

   Named tuple instances do not have per-instance dictionaries, so they are

   lightweight and require no more memory than regular tuples.

   .. versionadded:: 2.6

Example:

.. doctest::

   :options: +NORMALIZE_WHITESPACE

   >>> Point = namedtuple('Point', 'x y', verbose=True)

   class Point(tuple):

           'Point(x, y)'

   <BLANKLINE>

           __slots__ = ()

   <BLANKLINE>

           _fields = ('x', 'y')

   <BLANKLINE>

           def __new__(cls, x, y):