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


.. index::
    python built-in types



..
    `student grade data type <ex:student_grade>`_
    `project group data type <ex:project_groups>`_


.. _`sec:std_struct`:

Basic built-in types 
--------------------


Roles
^^^^^

+ :python:`list`: Stores an ordered, mutable (changeable), and indexed collection of elements.
+ :python:`tuple`: Stores an ordered, immutable (unchangeable), and indexed collection of elements. 
+ :python:`dict`: Stores a key-value pair collection that is ordered (insertion order since Python >=3.7), mutable, and indexed by unique hashable keys.
+ :python:`set`: Stores an unordered collection of unique hashable elements (duplicates are not allowed).
+ :python:`string`: Stores a sequence of characters used to represent and store text-based ordered, immutable (unchangeable), and indexed data.


.. _`sec:std_struct_methods`:

Main methods
^^^^^^^^^^^^

+-------------------------+-------------------------+-------------------------+---------------------------+
| List                    | Tuple                   | Dict                    | Set                       |
+=========================+=========================+=========================+===========================+
| ``append()``            | ``count()``             | ``clear()``             | ``add()``                 |
| :math:`O(1)`            | :math:`O(n)`            | :math:`O(1)`            | :math:`O(1)`              |
+-------------------------+-------------------------+-------------------------+---------------------------+
| ``clear()``             | ``index()``             | ``copy()``              | ``clear()``               |
| :math:`O(n)`            | :math:`O(n)`            | :math:`O(n)`            | :math:`O(n)`              |
+-------------------------+-------------------------+-------------------------+---------------------------+
| ``copy()``              |                         | ``fromkeys()``          | ``copy()``                |
| :math:`O(n)`            |                         | :math:`O(n)`            | :math:`O(n)`              |
+-------------------------+-------------------------+-------------------------+---------------------------+
| ``count()``             |                         | ``get()``               | ``difference()``          |
| :math:`O(n)`            |                         | :math:`O(1)`            | :math:`O(|s|)`            |
+-------------------------+-------------------------+-------------------------+---------------------------+
| ``extend()``            |                         | ``items()``             | ``difference_update()``   |
| :math:`O(k)`            |                         | :math:`O(n)`            | :math:`O(|s|)`            |
+-------------------------+-------------------------+-------------------------+---------------------------+
| ``index()``             |                         | ``keys()``              | ``discard()``             |
| :math:`O(n)`            |                         | :math:`O(n)`            | :math:`O(1)`              |
+-------------------------+-------------------------+-------------------------+---------------------------+
| ``insert()``            |                         | ``pop()``               | ``intersection()``        |
| :math:`O(n)`            |                         | :math:`O(1)`            | :math:`O(\min(|s|, |t|))` |
+-------------------------+-------------------------+-------------------------+---------------------------+
| ``pop()``               |                         | ``popitem()``           | ``intersection_update()`` |
| :math:`O(1),  O(n)`     |                         | :math:`O(1)`            | :math:`O(\min(|s|, |t|))` |
+-------------------------+-------------------------+-------------------------+---------------------------+
| ``remove()``            |                         | ``update()``            | ``isdisjoint()``          |
| :math:`O(n)`            |                         | :math:`O(n)`            | :math:`O(\min(|s|, |t|))` |
+-------------------------+-------------------------+-------------------------+---------------------------+
| ``reverse()``           |                         | ``values()``            | ``issubset()``            |
| :math:`O(n)`            |                         | :math:`O(n)`            | :math:`O(|s|)`            |
+-------------------------+-------------------------+-------------------------+---------------------------+
| ``sort()``              |                         |                         | ``issuperset()``          |
| :math:`O(n \log n)`     |                         |                         | :math:`O(|s|)`            |
+-------------------------+-------------------------+-------------------------+---------------------------+
|                         |                         |                         | ``pop()``                 |
|                         |                         |                         | :math:`O(1)`              |
+-------------------------+-------------------------+-------------------------+---------------------------+
|                         |                         |                         | ``remove()``              |
|                         |                         |                         | :math:`O(1)`              |
+-------------------------+-------------------------+-------------------------+---------------------------+
|                         |                         |                         | ``union()``               |
|                         |                         |                         | :math:`O(|s| + |t|)`      |
+-------------------------+-------------------------+-------------------------+---------------------------+
|                         |                         |                         | ``update()``              |
|                         |                         |                         | :math:`O(|t|)`            |
+-------------------------+-------------------------+-------------------------+---------------------------+

The time complexity notation means for a problem of size :math:`n`:

+ :math:`O(1)`: Constant time  
+ :math:`O(n)`: Linear time  
+ :math:`O(n \log n)`: Log-linear time  
+ :math:`|s|`: set size

Looping tips
^^^^^^^^^^^^

+ To get the index when iterating over a sequence use :python:`enumerate`.
+ To iterate simultaneously on two sequences, use :python:`zip`.
+ To iterate over a dict use the ``items`` method.
+ Never modify a dict or a set by adding or discarding elements while looping over it, 
  however, you can change values. 




.. admonition:: Exercise (easy)

    1. what would be the most appropriate standard structure to store and query student number (unique int) - grade (int)  data
       in order to efficiently find a given student grade, add or remove a student?
    2. what issue can you anticipate if the data is now name (str) - grade (int)?
    3. how would you check if an entry student number - grade has been entered for a given student? 
       Make sure your proposals work even if the student is not present. 
       What is the best solution if one is also interested in the student's grade? 
       Write the code and test it. 
    4. can one use a tuple of ints as a dict key or in a set, what about a list of ints? Why?

.. _`ex:student_grade`:

.. collapse:: Correction

    1. 'efficiently' suggests that the number of students might be large. 
       Student numbers are unique and hashable (they can act as keys). 
       A dict ``{student_number: grade, ...}̀`` is appropriate: query / add / remove in constant time.
    2. A name, even though it could act as a key, is not unique. 
       Adding a new student with the same name would result in the loss of the initial student grade.
    3. 
       .. literalinclude:: ../../../../src/tools_methods/basics/std_structures.py
               :pyobject: is_graded
               :name: is_graded
               :linenos:       
               :caption: src

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

       .. literalinclude:: ../../../../tests/tools_methods/basics/test_std_structures.py
               :pyobject: test_is_graded_present
               :name: test_is_graded_present
               :linenos:
               :caption: tests 

       .. literalinclude:: ../../../../tests/tools_methods/basics/test_std_structures.py
               :pyobject: test_is_graded_absent
               :name: test_is_graded_absent
               :linenos:  
               :caption: tests   

       .. literalinclude:: ../../../../tests/tools_methods/basics/test_std_structures.py
               :pyobject: test_get_student_grade_present
               :name: test_get_student_grade_present
               :linenos:
               :caption: tests 

       .. literalinclude:: ../../../../tests/tools_methods/basics/test_std_structures.py
               :pyobject: test_get_student_grade_absent
               :name: test_get_student_grade_absent
               :linenos:
               :caption: tests 

    4. Yes, because it is hashable. No for the opposite reason.





.. admonition:: Exercise (intermediate)

    .. code-block:: rst

    .. figure:: student_group_graph.png 
        :width: 300
        :alt: student_group_graph

        Example of a student group repartition

    Students (int) belong to project groups (int). A group is constituted of at least one student. Each student belongs to at least one group. 

    1. what structure would you suggest to efficiently both query all students belonging to a given group and if a given student belongs to a given group? 
    2. then, how would you obtain a structure which gives you the groups to which every student belongs? Write the code and test it.
    3. how would you test if a group has no student in common with an other group?

.. _`ex:project_groups`:

.. collapse:: Correction

    1. 'efficiently' suggests that the number of students and groups might be large. 
       A dict of sets  ``{group: {student_number_0, ...}, ...}̀`` allows to first get the students of a group as a set in constant time, 
       and then check the presence of a student in constant time.
    2. 
       .. 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 

       .. literalinclude:: ../../../../tests/tools_methods/basics/test_std_structures.py
               :pyobject: test_inverse_to_group_affiliation_of_students
               :name: test_inverse_to_group_affiliation_of_students
               :linenos:  
               :caption: tests

    3. A possibility:
    
       .. literalinclude:: ../../../../src/tools_methods/basics/std_structures.py
               :pyobject: has_no_common_student_between_groups
               :name: has_no_common_student_between_groups
               :linenos:    
               :caption: src 

       .. literalinclude:: ../../../../tests/tools_methods/basics/test_std_structures.py
               :pyobject: test_no_student_in_common_between_groups_true
               :name: test_no_student_in_common_between_groups_true
               :linenos:  
               :caption: tests

       .. literalinclude:: ../../../../tests/tools_methods/basics/test_std_structures.py
               :pyobject: test_no_student_in_common_between_groups_false
               :name: test_no_student_in_common_between_groups_false
               :linenos:  
               :caption: tests