.. role:: python(code)
   :language: python


.. index::
   collections

..
   `defaultdict <ex:defaultdict>`_
   `heapq <ex:heapq>`_


.. _`sec:collections`:

Collections
-----------

The module `collections <https://docs.python.org/3/library/collections.html#>`_  gathers some useful structures.

deque
^^^^^

A :python:`list` pops its last element in constant time. 
However, popping the first element costs linear time. 
The :python:`collections.deque` has a :python:`pop_left` method to pop the first element in constant time.

defaultdict
^^^^^^^^^^^

Imagine that you are building a :python:`dict[..., list[...]]`. 
:python:`collections.defaultdict` allows you to append/extend a value of this dict without prior initialization. 

.. admonition:: Exercise (easy)

   Simplify the code of the exercise about :ref:`project groups <ex:project_groups>` 

   .. literalinclude:: ../../../../src/tools_methods/basics/std_structures.py
      :pyobject: inverse_to_group_affiliation_of_students
      :name: inverse_to_group_affiliation_of_students_
      :linenos:    
      :caption: src 

.. _`ex:defaultdict`:

.. collapse:: Correction

   .. literalinclude:: ../../../../src/tools_methods/useful_modules/other_collections.py
      :pyobject: inverse_to_group_affiliation_of_students
      :name: inverse_to_group_affiliation_of_students__
      :linenos:    
      :caption: src 


Heapq
-----

A  `heap <https://docs.python.org/3/library/heapq.html>`_ is a structure where an order is efficiently maintained between elements, 
and where the smallest element can be efficiently popped :python:`heapq.heappop`. 
The initial list has to be transformed in place in a heap with :python:`heapq.heapify`. 

.. code-block:: python
    :linenos:

    import heapq

    values = [4, 1, 3, 2]
    heapq.heapify(values)
    print(values)
    while values:
        print(heapq.heappop(values))  # 1 2 3 4


Remember that tuples are compared from left to right. 
The usual pattern to use :python:`heapq` as a priority queue is to push elements as: ``(priority, tie_breaker, item)``. 
The ``tie_breaker`` is usually the number of pushed elements.
A priority queue is useful when new items are added while processing. 
If no new items are added, an initial sort on the priority is sufficient. 

.. admonition:: Exercise (easy)

   When 'processing' the following priority queue, if the considered ``item`` is uppercase, 
   re-submit this item in lowercase value and same priority. 
   The 'processing' consists in yielding the item.
   Write a test and implement.

   .. code-block:: python
 
      [
         (500, 0, "b"),
         (500, 1, "a"),
         (300, 2, "c"),
         (400, 3, "D"),
         (400, 4, "e"),
      ]      


.. _`ex:heapq`:

.. collapse:: Correction

   .. literalinclude:: ../../../../src/tools_methods/useful_modules/other_collections.py
      :pyobject: process
      :name: process
      :linenos:    
      :caption: src 

   .. literalinclude:: ../../../../tests/tools_methods/useful_modules/test_other_collections.py
      :pyobject: test_process
      :name: test_process
      :linenos:    
      :caption: src