CoursMagistral_2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": "true"
   },
   "source": [
    "# Table of Contents\n",
    " <p><div class=\"lev1 toc-item\"><a href=\"#ALGO1-:-Introduction-à-l'algorithmique\" data-toc-modified-id=\"ALGO1-:-Introduction-à-l'algorithmique-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span><a href=\"https://perso.crans.org/besson/teach/info1_algo1_2019/\" target=\"_blank\">ALGO1 : Introduction à l'algorithmique</a></a></div><div class=\"lev1 toc-item\"><a href=\"#Cours-Magistral-2\" data-toc-modified-id=\"Cours-Magistral-2-2\"><span class=\"toc-item-num\">2&nbsp;&nbsp;</span>Cours Magistral 2</a></div><div class=\"lev2 toc-item\"><a href=\"#Structures-de-données-pour-représenter-un-ensemble-de-valeurs-distinctes\" data-toc-modified-id=\"Structures-de-données-pour-représenter-un-ensemble-de-valeurs-distinctes-21\"><span class=\"toc-item-num\">2.1&nbsp;&nbsp;</span>Structures de données pour représenter un ensemble de valeurs distinctes</a></div><div class=\"lev2 toc-item\"><a href=\"#Type-abstrait\" data-toc-modified-id=\"Type-abstrait-22\"><span class=\"toc-item-num\">2.2&nbsp;&nbsp;</span>Type abstrait</a></div><div class=\"lev2 toc-item\"><a href=\"#Implémentation-des-opérations-non-primitives-à-partir-des-opérations-primitives\" data-toc-modified-id=\"Implémentation-des-opérations-non-primitives-à-partir-des-opérations-primitives-23\"><span class=\"toc-item-num\">2.3&nbsp;&nbsp;</span>Implémentation des opérations non primitives à partir des opérations primitives</a></div><div class=\"lev2 toc-item\"><a href=\"#Tests-communs-aux-différentes-implémentations\" data-toc-modified-id=\"Tests-communs-aux-différentes-implémentations-24\"><span class=\"toc-item-num\">2.4&nbsp;&nbsp;</span>Tests communs aux différentes implémentations</a></div><div class=\"lev2 toc-item\"><a href=\"#Implémentation-naïve-avec-une-structure-linéaire-(liste,-tableau-etc)\" data-toc-modified-id=\"Implémentation-naïve-avec-une-structure-linéaire-(liste,-tableau-etc)-25\"><span class=\"toc-item-num\">2.5&nbsp;&nbsp;</span>Implémentation naïve avec une structure linéaire (liste, tableau etc)</a></div><div class=\"lev2 toc-item\"><a href=\"#Implémentation-native-avec-set-en-Python\" data-toc-modified-id=\"Implémentation-native-avec-set-en-Python-26\"><span class=\"toc-item-num\">2.6&nbsp;&nbsp;</span>Implémentation native avec <code>set</code> en Python</a></div><div class=\"lev2 toc-item\"><a href=\"#Bidouillage-1/1-:-implémentation-avec-des-entiers-32/64-bits\" data-toc-modified-id=\"Bidouillage-1/1-:-implémentation-avec-des-entiers-32/64-bits-27\"><span class=\"toc-item-num\">2.7&nbsp;&nbsp;</span>Bidouillage 1/1 : implémentation avec des entiers 32/64 bits</a></div><div class=\"lev2 toc-item\"><a href=\"#Bidouillage-2/2-:-implémentation-avec-des-entiers-en-précision-infinie-avec-Python\" data-toc-modified-id=\"Bidouillage-2/2-:-implémentation-avec-des-entiers-en-précision-infinie-avec-Python-28\"><span class=\"toc-item-num\">2.8&nbsp;&nbsp;</span>Bidouillage 2/2 : implémentation avec des entiers en précision infinie avec Python</a></div><div class=\"lev2 toc-item\"><a href=\"#Implémentation-avec-des-tables-de-hachage-?\" data-toc-modified-id=\"Implémentation-avec-des-tables-de-hachage-?-29\"><span class=\"toc-item-num\">2.9&nbsp;&nbsp;</span>Implémentation avec des tables de hachage ?</a></div><div class=\"lev3 toc-item\"><a href=\"#En-Python-:-set-~=-dict-avec-des-valeurs-&quot;inutiles&quot;\" data-toc-modified-id=\"En-Python-:-set-~=-dict-avec-des-valeurs-&quot;inutiles&quot;-291\"><span class=\"toc-item-num\">2.9.1&nbsp;&nbsp;</span>En Python : <code>set</code> ~= <code>dict</code> avec des valeurs \"inutiles\"</a></div><div class=\"lev3 toc-item\"><a href=\"#Présentation-de-l'idée-:\" data-toc-modified-id=\"Présentation-de-l'idée-:-292\"><span class=\"toc-item-num\">2.9.2&nbsp;&nbsp;</span>Présentation de l'idée :</a></div><div class=\"lev3 toc-item\"><a href=\"#Comment-stocker-les-plus-petits-ensembles-?\" data-toc-modified-id=\"Comment-stocker-les-plus-petits-ensembles-?-293\"><span class=\"toc-item-num\">2.9.3&nbsp;&nbsp;</span>Comment stocker les plus petits ensembles ?</a></div><div class=\"lev3 toc-item\"><a href=\"#Choix-de-la-fonction-de-hachage\" data-toc-modified-id=\"Choix-de-la-fonction-de-hachage-294\"><span class=\"toc-item-num\">2.9.4&nbsp;&nbsp;</span>Choix de la fonction de hachage</a></div><div class=\"lev3 toc-item\"><a href=\"#Pour-l'exemple-ici\" data-toc-modified-id=\"Pour-l'exemple-ici-295\"><span class=\"toc-item-num\">2.9.5&nbsp;&nbsp;</span>Pour l'exemple ici</a></div><div class=\"lev2 toc-item\"><a href=\"#Implémentation-avec-des-arbres-binaires-de-recherche-?\" data-toc-modified-id=\"Implémentation-avec-des-arbres-binaires-de-recherche-?-210\"><span class=\"toc-item-num\">2.10&nbsp;&nbsp;</span>Implémentation avec des arbres binaires de recherche ?</a></div><div class=\"lev3 toc-item\"><a href=\"#Un-nœud-d'un-arbre-binaire\" data-toc-modified-id=\"Un-nœud-d'un-arbre-binaire-2101\"><span class=\"toc-item-num\">2.10.1&nbsp;&nbsp;</span>Un nœud d'un arbre binaire</a></div><div class=\"lev3 toc-item\"><a href=\"#Un-arbre-binaire-de-recherche\" data-toc-modified-id=\"Un-arbre-binaire-de-recherche-2102\"><span class=\"toc-item-num\">2.10.2&nbsp;&nbsp;</span>Un arbre binaire de recherche</a></div><div class=\"lev3 toc-item\"><a href=\"#Ensemble-avec-un-Arbre-Binaire-de-Recherche\" data-toc-modified-id=\"Ensemble-avec-un-Arbre-Binaire-de-Recherche-2103\"><span class=\"toc-item-num\">2.10.3&nbsp;&nbsp;</span>Ensemble avec un Arbre Binaire de Recherche</a></div><div class=\"lev2 toc-item\"><a href=\"#Comparaison-des-différentes-implémentations\" data-toc-modified-id=\"Comparaison-des-différentes-implémentations-211\"><span class=\"toc-item-num\">2.11&nbsp;&nbsp;</span>Comparaison des différentes implémentations</a></div><div class=\"lev2 toc-item\"><a href=\"#Conclusion\" data-toc-modified-id=\"Conclusion-212\"><span class=\"toc-item-num\">2.12&nbsp;&nbsp;</span>Conclusion</a></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [ALGO1 : Introduction à l'algorithmique](https://perso.crans.org/besson/teach/info1_algo1_2019/)\n",
    "\n",
    "- [Page du cours](https://perso.crans.org/besson/teach/info1_algo1_2019/) : https://perso.crans.org/besson/teach/info1_algo1_2019/\n",
    "- Magistère d'Informatique de Rennes - ENS Rennes - Année 2019/2020\n",
    "- Intervenants :\n",
    "  + Cours : [Lilian Besson](https://perso.crans.org/besson/)\n",
    "  + Travaux dirigés : [Raphaël Truffet](http://perso.eleves.ens-rennes.fr/people/Raphael.Truffet/)\n",
    "- Références :\n",
    "  + [Open Data Structures](http://opendatastructures.org/ods-python.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Cours Magistral 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Structures de données pour représenter un ensemble de valeurs distinctes\n",
    "\n",
    "- Après avoir étudié comment représenter $<a_1,\\dots,a_n>$ une *séquence ordonnée* de valeurs $a_i$ dans un domaine $D$ (e.g., des entiers), on s'intéresse aujourd'hui à représenter un *ensemble non ordonné* de valeurs : $\\{a_1,\\dots,a_n\\}$.\n",
    "- On va utiliser des valeurs entières, par concision : $D=\\mathbb{N}$, `d = int`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Type abstrait\n",
    "- On fixe $D$ le domaine de nos valeurs, et `d` leur type.\n",
    "- On définit `Set<d>` le type abstrait des ensembles (collections non ordonnés) de valeurs de type `d`.\n",
    "\n",
    "On veut les opérations suivantes :\n",
    "\n",
    "    newEmptySet : () -> Set<d>          // créer un ensemble vide\n",
    "    len         : Set<d> -> int         // donner le nombre d'éléments de cet ensemble\n",
    "    contains    : Set<d> * d -> bool    // tester l'appartenance\n",
    "    add         : Set<d> * d -> Set<d>  // ajouter un élément à cet ensemble\n",
    "    pop         : Set<d> * d -> Set<d>  // retirer un élément à cet ensemble (s'il est présent)\n",
    "    values      : Set<d> -> List<d>     // retourne la liste de valeurs présentes dans l'ensemble"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut aussi vouloir les opérations suivantes, qui peuvent toutes s'implémenter avec les primitives ci-dessus :\n",
    "\n",
    "    isEmpty : Set<d> -> bool    // test si l'ensemble est vide\n",
    "    copy    : Set<d> -> Set<d>  // copie l'ensemble\n",
    "\n",
    "On peut aussi vouloir les opérations entre ensembles suivantes, qui peuvent toutes s'implémenter avec les primitives ci-dessus :\n",
    "\n",
    "    union                : Set<d> * Set<d> -> Set<d>\n",
    "    // contient les éléments présents dans au moins un des deux ensembles\n",
    "    \n",
    "    intersection         : Set<d> * Set<d> -> Set<d>\n",
    "    // contient les éléments présents dans les deux ensembles\n",
    "    \n",
    "    difference           : Set<d> * Set<d> -> Set<d>\n",
    "    // contient les éléments présents dans le premier mais pas le deuxième ensemble\n",
    "    \n",
    "    symmetric_difference : Set<d> * Set<d> -> Set<d>\n",
    "    // contient les éléments présents dans le premier mais pas le deuxième ensemble ou dans le deuxième mais pas le premier (xor)\n",
    "    \n",
    "    issubset             : Set<d> * Set<d> -> bool\n",
    "    // test si le premier ensemble est contenu dans le second\n",
    "    \n",
    "    issuperset           : Set<d> * Set<d> -> bool\n",
    "    // test si le premier ensemble est contenu dans le second"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "## Implémentation des opérations non primitives à partir des opérations primitives\n",
    "- Avec OCaml, on pourrait écrire un foncteur.\n",
    "- Avec Python, on va écrire une classe, et on pourra obtenir différentes implémentations complètes de la structure de données d'ensemble, à partir de différentes implémentations partielles des opérations primitives. C'est assez naïf : le code est indépendant de l'implémentation sous jacente de `add`/`pop` et de l'itérations :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "code_folding": [
     0
    ]
   },
   "outputs": [],
   "source": [
    "class SetIterator():\n",
    "    def __init__(self, a_set):\n",
    "        self.values = a_set.values()\n",
    "        self.maxcurrent = len(a_set)\n",
    "        self.current = 0\n",
    "    \n",
    "    def __iter__(self):\n",
    "        return self\n",
    "    \n",
    "    def __next__(self):\n",
    "        if self.current >= self.maxcurrent:\n",
    "            raise StopIteration\n",
    "        else:\n",
    "            self.current += 1\n",
    "            return self.values[self.current - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "code_folding": [
     22
    ]
   },
   "outputs": [],
   "source": [
    "class SetWithNonPrimOperations():    \n",
    "    def isEmpty(self):\n",
    "        return len(self) == 0\n",
    "\n",
    "    def __iter__(self):\n",
    "        return SetIterator(self)\n",
    "    \n",
    "    def copy(self):\n",
    "        \"\"\" A new set containing the same values.\"\"\"\n",
    "        new_set = self.__class__()\n",
    "        for value in self:\n",
    "            new_set.add(value)\n",
    "        return new_set\n",
    "    \n",
    "    def difference(self, other_set):\n",
    "        \"\"\" A new set containing the values in self but not other_set.\"\"\"\n",
    "        new_set = self.__class__()\n",
    "        for value in self:\n",
    "            if value not in other_set:\n",
    "                new_set.add(value)\n",
    "        return new_set\n",
    "    \n",
    "    def symmetric_difference(self, other_set):\n",
    "        \"\"\" A new set containing the values in self but not other_set and the values in other_set but not self (XOR).\"\"\"\n",
    "        new_set = self.__class__()\n",
    "        for value in self:\n",
    "            if value not in other_set:\n",
    "                new_set.add(value)\n",
    "        for value in other_set:\n",
    "            if value not in self:\n",
    "                new_set.add(value)\n",
    "        return new_set\n",
    "    \n",
    "    def intersection(self, other_set):\n",
    "        \"\"\" A new set containing the values in self and in other_set.\"\"\"\n",
    "        new_set = self.__class__()\n",
    "        for value in self:\n",
    "            if value in other_set:\n",
    "                new_set.add(value)\n",
    "        return new_set\n",
    "    \n",
    "    def union(self, other_set):\n",
    "        \"\"\" A new set containing the values in self or in other_set.\"\"\"\n",
    "        new_set = self.__class__()\n",
    "        for value in self:\n",
    "            new_set.add(value)\n",
    "        for value in other_set:\n",
    "            new_set.add(value)\n",
    "        return new_set\n",
    "\n",
    "    def isdisjoint(self, other_set):\n",
    "        \"\"\" True if all the values in self are not in other_set.\"\"\"\n",
    "        for value in self:\n",
    "            if value in other_set:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def issubset(self, other_set):\n",
    "        \"\"\" True if all the values in self are in other_set.\"\"\"\n",
    "        for value in self:\n",
    "            if value not in other_set:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def issuperset(self, other_set):\n",
    "        \"\"\" True if all the values in other_set are in self.\"\"\"\n",
    "        for value in other_set:\n",
    "            if value not in self:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def clear(self):\n",
    "        \"\"\" Remove (pop) all the values in self.\"\"\"\n",
    "        for value in self:\n",
    "            self.pop(value)\n",
    "    \n",
    "    def remove(self, value):\n",
    "        self.pop(value)\n",
    "    \n",
    "    def __contains__(self, value):\n",
    "        return self.contains(value)\n",
    "    \n",
    "    def __str__(self):\n",
    "        \"\"\" Represent the values of the set in a string {a1,...,an}.\"\"\"\n",
    "        str_list = str(self.values())\n",
    "        return \"{\" + str_list.strip(\"[]\") + \"}\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "## Tests communs aux différentes implémentations\n",
    "\n",
    "On écrit un petit test qui sera utilisé avec les différentes implémentations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def un_petit_test_avec_une_structure_densemble(SetClass):\n",
    "    ens = SetClass()\n",
    "    print(ens)\n",
    "    assert not ens\n",
    "    for x in range(10):\n",
    "        assert x not in ens\n",
    "        ens.add(x)\n",
    "        assert x in ens\n",
    "        print(ens)\n",
    "    # ens = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}\n",
    "    assert ens\n",
    "    assert str(ens) == \"{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}\"\n",
    "    print(\"S1 =\", ens)\n",
    "    for x in range(20, 30):\n",
    "        assert x not in ens\n",
    "    \n",
    "    ens2 = SetClass()\n",
    "    print(ens2)\n",
    "    for x in range(5, 10):\n",
    "        assert x not in ens2\n",
    "        ens2.add(x)\n",
    "        assert x in ens2\n",
    "        print(ens2)\n",
    "    # ens2 = {5, 6, 7, 8, 9}\n",
    "    assert str(ens2) == \"{5, 6, 7, 8, 9}\"\n",
    "    print(\"S2 =\", ens2)\n",
    "    assert ens2.issubset(ens)\n",
    "    assert ens.issuperset(ens2)\n",
    "    \n",
    "    assert [v for v in ens.intersection(ens2)] == [v for v in ens2]\n",
    "    assert [v for v in ens.intersection(ens2)] == [5, 6, 7, 8, 9]\n",
    "    assert [v for v in ens.difference(ens2)] == [0, 1, 2, 3, 4]\n",
    "    \n",
    "    ens3 = SetClass()\n",
    "    print(ens3)\n",
    "    for x in range(20, 25):\n",
    "        assert x not in ens3\n",
    "        ens3.add(x)\n",
    "        assert x in ens3\n",
    "        print(ens3)\n",
    "    assert len(ens3) == 5\n",
    "    for x in range(20, 25):\n",
    "        ens3.add(x)\n",
    "        assert x in ens3\n",
    "        print(ens3)\n",
    "    assert len(ens3) == 5\n",
    "    # ens3 = {20, 21, 22, 23, 24}\n",
    "    assert str(ens3) == \"{20, 21, 22, 23, 24}\"\n",
    "    print(\"S3 =\", ens3)\n",
    "\n",
    "    assert not ens.issubset(ens3)\n",
    "    assert not ens.issuperset(ens3)\n",
    "    assert not ens3.issubset(ens)\n",
    "    assert not ens3.issuperset(ens)\n",
    "    \n",
    "    assert not ens3.intersection(ens)\n",
    "    assert not ens.intersection(ens3)\n",
    "    \n",
    "    print(\"S1 union S2 =\", ens.union(ens2), \" = S2 union S1 =\", ens2.union(ens))\n",
    "    print(\"S1 union S3 =\", ens.union(ens3))\n",
    "    print(\"S2 union S3 =\", ens2.union(ens3))\n",
    "\n",
    "    print(\"S1 inter S2 =\", ens.intersection(ens2), \" != S2 inter S1 =\", ens2.intersection(ens))\n",
    "    print(\"S1 inter S3 =\", ens.intersection(ens3), \" != S3 inter S1 =\", ens3.intersection(ens))\n",
    "    print(\"S2 inter S3 =\", ens2.intersection(ens3), \" != S3 inter S2 =\", ens3.intersection(ens2))\n",
    "\n",
    "    print(\"S1 diff S2 =\", ens.difference(ens2), \" != S2 diff S1 =\", ens2.difference(ens))\n",
    "    print(\"S1 diff S3 =\", ens.difference(ens3), \" != S3 diff S1 =\", ens3.difference(ens))\n",
    "    print(\"S2 diff S3 =\", ens2.difference(ens3), \" != S3 diff S2 =\", ens3.difference(ens2))\n",
    "\n",
    "    print(\"S1 diff sym S2 =\", ens.symmetric_difference(ens2), \" != S2 diff sym S1 =\", ens2.symmetric_difference(ens))\n",
    "    print(\"S1 diff sym S3 =\", ens.symmetric_difference(ens3), \" != S3 diff sym S1 =\", ens3.symmetric_difference(ens))\n",
    "    print(\"S2 diff sym S3 =\", ens2.symmetric_difference(ens3), \" != S3 diff sym S2 =\", ens3.symmetric_difference(ens2))\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le deuxième test va juste être une suite d'ajout et de suppression de valeurs dans l'ensemble.\n",
    "\n",
    "Il servira pour mesurer l'efficacité temporelle des deux opérations de bases (`add`/`pop`), en fonction de l'amplitude des valeurs de l'ensemble (`max_value`/`min_value`), et de la taille de l'ensemble qui sera construit (`size`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def random_add_remove_test(SetClass, size=1000, max_value=10_000, min_value=-10_000):\n",
    "    ens = SetClass()\n",
    "    for _ in range(size):\n",
    "        x = random.randint(min_value, max_value)\n",
    "        ens.add(x)\n",
    "        assert x in ens\n",
    "    values = ens.values()\n",
    "    for _ in range(size):\n",
    "        x = random.choice(values)\n",
    "        if random.random() <= 0.5:\n",
    "            ens.add(x)\n",
    "            assert x in ens\n",
    "        else:\n",
    "            if x in ens:\n",
    "                ens.remove(x)\n",
    "            assert x not in ens"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implémentation naïve avec une structure linéaire (liste, tableau etc)\n",
    "- On utilise une liste ou un tableau (en Python, `list<d>`) pour stocker les valeurs.\n",
    "- Voyons les implémentations concrètes (les complexités sont discutées pour chacune plus bas)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SetWithList(SetWithNonPrimOperations):\n",
    "    def __init__(self):\n",
    "        self._values = []\n",
    "\n",
    "    def __len__(self):\n",
    "        \"\"\" Return n the current size of the set.\"\"\"\n",
    "        return len(self._values)\n",
    "\n",
    "    def contains(self, value):\n",
    "        \"\"\" Test if value is in the set.\n",
    "        \n",
    "        - Test linearly the equality with all values in the list.\n",
    "        - Takes O(n) time in worst case.\"\"\"\n",
    "        for other_value in self._values:\n",
    "            if other_value == value:\n",
    "                return True\n",
    "        return False\n",
    "        # equivalent to\n",
    "        # return value in self._values\n",
    "\n",
    "    def add(self, value):\n",
    "        \"\"\" Add value in the set if it is not present.\n",
    "        \n",
    "        - Takes O(n) time in worst case.\"\"\"\n",
    "        if value not in self:\n",
    "            self._values.append(value)\n",
    "\n",
    "    def pop(self, value):\n",
    "        \"\"\" Remove value in the set if it is present.\n",
    "        \n",
    "        - Takes O(n) time in worst case.\"\"\"\n",
    "        if value in self:  # O(n)\n",
    "            location = self._values.index(value)  # O(n), but happens only once\n",
    "            del self._values[location]  # O(n)\n",
    "    \n",
    "    def values(self):\n",
    "        \"\"\" Return a fresh list of the values of the set (not the actual list, to protect it).\n",
    "        \n",
    "        - Takes O(n) time in worst case.\"\"\"\n",
    "        return list(self._values)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On teste cette première structure :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{}\n",
      "{0}\n",
      "{0, 1}\n",
      "{0, 1, 2}\n",
      "{0, 1, 2, 3}\n",
      "{0, 1, 2, 3, 4}\n",
      "{0, 1, 2, 3, 4, 5}\n",
      "{0, 1, 2, 3, 4, 5, 6}\n",
      "{0, 1, 2, 3, 4, 5, 6, 7}\n",
      "{0, 1, 2, 3, 4, 5, 6, 7, 8}\n",
      "{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}\n",
      "S1 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}\n",
      "{}\n",
      "{5}\n",
      "{5, 6}\n",
      "{5, 6, 7}\n",
      "{5, 6, 7, 8}\n",
      "{5, 6, 7, 8, 9}\n",
      "S2 = {5, 6, 7, 8, 9}\n",
      "{}\n",
      "{20}\n",
      "{20, 21}\n",
      "{20, 21, 22}\n",
      "{20, 21, 22, 23}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "S3 = {20, 21, 22, 23, 24}\n",
      "S1 union S2 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}  = S2 union S1 = {5, 6, 7, 8, 9, 0, 1, 2, 3, 4}\n",
      "S1 union S3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20, 21, 22, 23, 24}\n",
      "S2 union S3 = {5, 6, 7, 8, 9, 20, 21, 22, 23, 24}\n",
      "S1 inter S2 = {5, 6, 7, 8, 9}  != S2 inter S1 = {5, 6, 7, 8, 9}\n",
      "S1 inter S3 = {}  != S3 inter S1 = {}\n",
      "S2 inter S3 = {}  != S3 inter S2 = {}\n",
      "S1 diff S2 = {0, 1, 2, 3, 4}  != S2 diff S1 = {}\n",
      "S1 diff S3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}  != S3 diff S1 = {20, 21, 22, 23, 24}\n",
      "S2 diff S3 = {5, 6, 7, 8, 9}  != S3 diff S2 = {20, 21, 22, 23, 24}\n",
      "S1 diff sym S2 = {0, 1, 2, 3, 4}  != S2 diff sym S1 = {0, 1, 2, 3, 4}\n",
      "S1 diff sym S3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20, 21, 22, 23, 24}  != S3 diff sym S1 = {20, 21, 22, 23, 24, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}\n",
      "S2 diff sym S3 = {5, 6, 7, 8, 9, 20, 21, 22, 23, 24}  != S3 diff sym S2 = {20, 21, 22, 23, 24, 5, 6, 7, 8, 9}\n"
     ]
    }
   ],
   "source": [
    "un_petit_test_avec_une_structure_densemble(SetWithList)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- On pourrait faire pareil avec n'importe quelle structure linéaire : liste simplement ou doublement chaînée, tableau dynamique (ce qu'on a fait avec `list` de Python), file/pile d'attente, etc.\n",
    "\n",
    "- Le bilan des complexités des opérations est le suivant (si $n=\\texttt{len}(S_1)$ et $m=\\texttt{len}(S_2)$) :\n",
    "\n",
    "| Opérations | Complexité pire cas | Complexité moyenne* |\n",
    "|------------|------------|------------|\n",
    "| `newEmptySet()` | $O(1)$ | $O(1)$ |\n",
    "| `len(S1)` | $O(n)$ | $O(n)$ |\n",
    "| `contains(S1, x)` | $O(n)$ | $O(n)$ |\n",
    "| `add(S1, x)` | $O(n)$ | $O(n)$ |\n",
    "| `pop(S1, x)` | $O(n)$ | $O(n)$ |\n",
    "| `values(S1)` | $O(n)$ | $O(n)$ |\n",
    "| `isEmpty(S1)` | $O(n)$ | $O(n)$ |\n",
    "| `copy(S1)` | $O(n)$ | $O(n)$ |\n",
    "| `union(S1, S2)` | $O(n + m)$ | $O(n + m)$ |\n",
    "| `intersection(S1, S2)` | $O(n + m)$ | $O(n + m)$ |\n",
    "| `difference(S1, S2)` | $O(n + m)$ | $O(n + m)$ |\n",
    "| `symmetric_difference(S1, S2)` | $O(n + m)$ | $O(n + m)$ |\n",
    "| `issubset(S1, S2)` | $O(n + m)$ | $O(n + m)$ |\n",
    "| `issuperset(S1, S2)` | $O(n + m)$ | $O(n + m)$ |\n",
    "\n",
    "> Il reste à définir ce que signifie complexité moyenne. Regardez par exemple dans [Introduction à l'Algorithmique, de Cormen et al]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.04 ms ± 68.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n",
      "987 µs ± 38.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n",
      "1.11 ms ± 201 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n",
      "1.33 ms ± 200 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit random_add_remove_test(SetWithList, size=100, max_value=100)\n",
    "%timeit random_add_remove_test(SetWithList, size=100, max_value=1000)\n",
    "%timeit random_add_remove_test(SetWithList, size=100, max_value=100000)\n",
    "%timeit random_add_remove_test(SetWithList, size=100, max_value=10000000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "75.1 ms ± 6.14 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n",
      "67 ms ± 2.23 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n",
      "66.7 ms ± 2.49 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n",
      "67.3 ms ± 1.78 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit random_add_remove_test(SetWithList, size=1000, max_value=100)\n",
    "%timeit random_add_remove_test(SetWithList, size=1000, max_value=1000)\n",
    "%timeit random_add_remove_test(SetWithList, size=1000, max_value=100000)\n",
    "%timeit random_add_remove_test(SetWithList, size=1000, max_value=10000000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4.79 s ± 906 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
      "4.22 s ± 369 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
      "6.63 s ± 439 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
      "6.58 s ± 59.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%timeit random_add_remove_test(SetWithList, size=10000, max_value=100)\n",
    "%timeit random_add_remove_test(SetWithList, size=10000, max_value=1000)\n",
    "%timeit random_add_remove_test(SetWithList, size=10000, max_value=100000)\n",
    "%timeit random_add_remove_test(SetWithList, size=10000, max_value=10000000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Plus `max_value` est grande, plus il y a de valeurs différentes, donc plus on a une liste qui sera longue, et donc plus les opérations coûtent cher."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "## Implémentation native avec `set` en Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "class NativeSet(set, SetWithNonPrimOperations):\n",
    "    def values(self):\n",
    "        return list(self)\n",
    "    # et c'est tout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{}\n",
      "{0}\n",
      "{0, 1}\n",
      "{0, 1, 2}\n",
      "{0, 1, 2, 3}\n",
      "{0, 1, 2, 3, 4}\n",
      "{0, 1, 2, 3, 4, 5}\n",
      "{0, 1, 2, 3, 4, 5, 6}\n",
      "{0, 1, 2, 3, 4, 5, 6, 7}\n",
      "{0, 1, 2, 3, 4, 5, 6, 7, 8}\n",
      "{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}\n",
      "S1 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}\n",
      "{}\n",
      "{5}\n",
      "{5, 6}\n",
      "{5, 6, 7}\n",
      "{8, 5, 6, 7}\n",
      "{5, 6, 7, 8, 9}\n",
      "S2 = {5, 6, 7, 8, 9}\n",
      "{}\n",
      "{20}\n",
      "{20, 21}\n",
      "{20, 21, 22}\n",
      "{20, 21, 22, 23}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "S3 = {20, 21, 22, 23, 24}\n",
      "S1 union S2 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}  = S2 union S1 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}\n",
      "S1 union S3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20, 21, 22, 23, 24}\n",
      "S2 union S3 = {5, 6, 7, 8, 9, 20, 21, 22, 23, 24}\n",
      "S1 inter S2 = {5, 6, 7, 8, 9}  != S2 inter S1 = {5, 6, 7, 8, 9}\n",
      "S1 inter S3 = set()  != S3 inter S1 = set()\n",
      "S2 inter S3 = set()  != S3 inter S2 = set()\n",
      "S1 diff S2 = {0, 1, 2, 3, 4}  != S2 diff S1 = set()\n",
      "S1 diff S3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}  != S3 diff S1 = {20, 21, 22, 23, 24}\n",
      "S2 diff S3 = {5, 6, 7, 8, 9}  != S3 diff S2 = {20, 21, 22, 23, 24}\n",
      "S1 diff sym S2 = {0, 1, 2, 3, 4}  != S2 diff sym S1 = {0, 1, 2, 3, 4}\n",
      "S1 diff sym S3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20, 21, 22, 23, 24}  != S3 diff sym S1 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20, 21, 22, 23, 24}\n",
      "S2 diff sym S3 = {5, 6, 7, 8, 9, 20, 21, 22, 23, 24}  != S3 diff sym S2 = {5, 6, 7, 8, 9, 20, 21, 22, 23, 24}\n"
     ]
    }
   ],
   "source": [
    "un_petit_test_avec_une_structure_densemble(NativeSet)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Le bilan des complexités des opérations est le suivant (si $n=\\texttt{len}(S_1)$ et $m=\\texttt{len}(S_2)$) :\n",
    "\n",
    "| Opérations | Complexité pire cas | Complexité moyenne* |\n",
    "|------------|------------|------------|\n",
    "| `newEmptySet()` | $O(1)$ | $O(1)$ |\n",
    "| `len(S1)` | $O(1)$ | $O(1)$ |\n",
    "| `contains(S1, x)` | $O(n)$ | $O(1)$ 🎉 |\n",
    "| `add(S1, x)` | $O(n)$ | $O(1)$ 🎉 |\n",
    "| `pop(S1, x)` | $O(n)$ | $O(1)$ 🎉 |\n",
    "| `values(S1)` | $O(n)$ | $O(n)$ |\n",
    "| `isEmpty(S1)` | $O(1)$ | $O(1)$ |\n",
    "| `copy(S1)` | $O(n)$ | $O(n)$ |\n",
    "| `union(S1, S2)` | $O(n + m)$ | $O(n + m)$ |\n",
    "| `intersection(S1, S2)` | $O(n m)$ | $O(\\min(n, m))$ 🎉 |\n",
    "| `difference(S1, S2)` | $O(n + m)$ | $O(n + m)$ |\n",
    "| `symmetric_difference(S1, S2)` | $O(n m)$ | $O(\\max(n, m))$ |\n",
    "| `issubset(S1, S2)` | $O(n m)$ | $O(\\min(n, m)))$ 🎉 |\n",
    "| `issuperset(S1, S2)` | $O(n m)$ | $O(\\min(n, m)))$ 🎉 |\n",
    "\n",
    "> Référence : https://stackoverflow.com/questions/3949310/ddg#3949350, https://hg.python.org/releasing/3.6/file/tip/Objects/setobject.c et https://wiki.python.org/moin/TimeComplexity#set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "216 µs ± 4 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n",
      "217 µs ± 6.07 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n",
      "206 µs ± 2.78 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n",
      "224 µs ± 14.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit random_add_remove_test(NativeSet, size=100, max_value=100)\n",
    "%timeit random_add_remove_test(NativeSet, size=100, max_value=1000)\n",
    "%timeit random_add_remove_test(NativeSet, size=100, max_value=1000_000)\n",
    "%timeit random_add_remove_test(NativeSet, size=100, max_value=1000_000_000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.33 ms ± 109 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n",
      "2.36 ms ± 252 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n",
      "2.66 ms ± 383 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n",
      "2.68 ms ± 653 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit random_add_remove_test(NativeSet, size=1000, max_value=100)\n",
    "%timeit random_add_remove_test(NativeSet, size=1000, max_value=1000)\n",
    "%timeit random_add_remove_test(NativeSet, size=1000, max_value=1000_000)\n",
    "%timeit random_add_remove_test(NativeSet, size=1000, max_value=1000_000_000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "24.9 ms ± 1.78 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n",
      "31.5 ms ± 6.33 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n",
      "26.1 ms ± 2.03 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n",
      "23.7 ms ± 1.44 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit random_add_remove_test(NativeSet, size=10_000, max_value=100)\n",
    "%timeit random_add_remove_test(NativeSet, size=10_000, max_value=1000)\n",
    "%timeit random_add_remove_test(NativeSet, size=10_000, max_value=1000_000)\n",
    "%timeit random_add_remove_test(NativeSet, size=10_000, max_value=1000_000_000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "228 ms ± 4.19 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
      "229 ms ± 6.61 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
      "254 ms ± 10.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
      "256 ms ± 19.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%timeit random_add_remove_test(NativeSet, size=100_000, max_value=100)\n",
    "%timeit random_add_remove_test(NativeSet, size=100_000, max_value=1000)\n",
    "%timeit random_add_remove_test(NativeSet, size=100_000, max_value=1000_000)\n",
    "%timeit random_add_remove_test(NativeSet, size=100_000, max_value=1000_000_000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.26 s ± 29.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
      "2.59 s ± 147 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
      "2.82 s ± 216 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
      "3.15 s ± 414 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%timeit random_add_remove_test(NativeSet, size=1000_000, max_value=100)\n",
    "%timeit random_add_remove_test(NativeSet, size=1000_000, max_value=1000)\n",
    "%timeit random_add_remove_test(NativeSet, size=1000_000, max_value=1000_000)\n",
    "%timeit random_add_remove_test(NativeSet, size=1000_000, max_value=1000_000_000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- On semble vérifier que l'implémentation native de Python est quasiment indépendante des valeurs stockées, dès qu'elles sont assez grandes.\n",
    "- Et que les complexités (amorties) des opérations `add`/`remove` sont quasiment indépendantes en la taille de l'ensemble ! (multiplier la taille $n$ par 10 multiplie presque le temps de calcul des $n$ opérations par 10). En fait, on voit qu'elles sont sous linéaires, mais pas constantes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "## Bidouillage 1/1 : implémentation avec des entiers 32/64 bits\n",
    "\n",
    "- Si on sait que les valeurs qu'on va ajouter dans nos ensembles sont comprises entre 0 et 31, on peut représenter un (petit) ensemble avec *un seul* entier 32 bits : si le $i$ème bit est à 1, c'est que $i$ est dans l'ensemble.\n",
    "- On peut faire pareil avec 64 bits.\n",
    "- En Python, les entiers sont à précision arbitraire, mais on peut utiliser `np.int32` pour avoir des entiers 32 bits natifs :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- On va voir comment utiliser les opérations bit à bit pour réaliser les opérations sur les ensembles. [Documentation ?](https://docs.scipy.org/doc/numpy/reference/routines.bitwise.html)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'0b0'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "'0b1'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "'0b10'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "'0b11'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "'0b1'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "'0b1'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "'0b11'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "'0b11'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "'0b1'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "'0b1'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "'0b111'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "'0b111'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "'0b1'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "'0b1'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "'0b1'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "'0b1'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "'0b10'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "'0b10'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "'0b10000000'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "'0b10000000'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bin(0b0)  # set {}\n",
    "bin(0b1)  # set {0}\n",
    "bin(0b10)  # set {1}\n",
    "bin(0b11)  # set {0, 1}\n",
    "\n",
    "bin(np.bitwise_and(0b11, 0b01))  # {0, 1} inter {1} = {1}\n",
    "bin(0b11 & 0b01)  # {0, 1} inter {1} = {1}\n",
    "bin(np.bitwise_or(0b01, 0b10))  # {0} union {1} = {0, 1}\n",
    "bin(0b01 | 0b10)  # {0} union {1} = {0, 1}\n",
    "\n",
    "bin(np.bitwise_xor(0b11, 0b10)) # {0, 1} /\\ {1} = {0} (symmetric difference)\n",
    "bin(0b11 ^ 0b10) # {0, 1} /\\ {1} = {0} (symmetric difference)\n",
    "bin(np.bitwise_xor(0b101, 0b10)) # {0, 2} /\\ {1} = {0, 1, 2} (symmetric difference)\n",
    "bin(0b101 ^ 0b10) # {0, 2} /\\ {1} = {0, 1, 2} (symmetric difference)\n",
    "\n",
    "bin(np.left_shift(1, 0))  # = {0}\n",
    "bin(1 << 0)  # = {0}\n",
    "bin(np.left_shift(1, 1))  # = {1}\n",
    "bin(1 << 1)  # = {1}\n",
    "bin(np.left_shift(1, 7))  # = {7}\n",
    "bin(1 << 7)  # = {7}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et voilà la classe"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import log2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SetWithInt(SetWithNonPrimOperations):\n",
    "    def __init__(self, zero=0):\n",
    "        \"\"\" Use zero=0 to use native int, zero=np.int32(0) or np.int64(0) to use 32/64 bits.\"\"\"\n",
    "        self.int = zero\n",
    "\n",
    "    def __len__(self):\n",
    "        \"\"\" Return n the current size of the set.\"\"\"\n",
    "        return len(self.values())\n",
    "\n",
    "    def contains(self, value):\n",
    "        \"\"\" Test if value is in the set.\n",
    "        \n",
    "        - Test one bit.\n",
    "        - This & means \"bitwise and\".\n",
    "        \"\"\"\n",
    "        return (self.int & (1 << value)) != 0\n",
    "\n",
    "    def add(self, value):\n",
    "        \"\"\" Add value in the set if it is not present.\n",
    "        \n",
    "        - This |= means x = x | y and | is the \"bitwise or\" operation.\"\"\"\n",
    "        self.int |= (1 << value)\n",
    "\n",
    "    def pop(self, value):\n",
    "        \"\"\" Remove value in the set if it is present.\n",
    "        \n",
    "        - This ^= means x = x ^ y and | is the \"bitwise xor\" operation.\"\"\"\n",
    "        self.int ^= (1 << value)\n",
    "    \n",
    "    def values(self):\n",
    "        \"\"\" Return a fresh list of the values of the set.\n",
    "        \n",
    "        - Takes O(n) time in worst case.\"\"\"\n",
    "        if self.int == 0:\n",
    "            return []\n",
    "        else:\n",
    "            n = 1 + int(log2(self.int))\n",
    "            return [ i for i in range(n) if i in self]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "SetWithInt32 = lambda: SetWithInt(np.int32(0))\n",
    "SetWithInt64 = lambda: SetWithInt(np.int64(0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On test :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{}\n",
      "{0}\n",
      "{0, 1}\n",
      "{0, 1, 2}\n",
      "{0, 1, 2, 3}\n",
      "{0, 1, 2, 3, 4}\n",
      "{0, 1, 2, 3, 4, 5}\n",
      "{0, 1, 2, 3, 4, 5, 6}\n",
      "{0, 1, 2, 3, 4, 5, 6, 7}\n",
      "{0, 1, 2, 3, 4, 5, 6, 7, 8}\n",
      "{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}\n",
      "S1 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}\n",
      "{}\n",
      "{5}\n",
      "{5, 6}\n",
      "{5, 6, 7}\n",
      "{5, 6, 7, 8}\n",
      "{5, 6, 7, 8, 9}\n",
      "S2 = {5, 6, 7, 8, 9}\n",
      "{}\n",
      "{20}\n",
      "{20, 21}\n",
      "{20, 21, 22}\n",
      "{20, 21, 22, 23}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "S3 = {20, 21, 22, 23, 24}\n",
      "S1 union S2 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}  = S2 union S1 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}\n",
      "S1 union S3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20, 21, 22, 23, 24}\n",
      "S2 union S3 = {5, 6, 7, 8, 9, 20, 21, 22, 23, 24}\n",
      "S1 inter S2 = {5, 6, 7, 8, 9}  != S2 inter S1 = {5, 6, 7, 8, 9}\n",
      "S1 inter S3 = {}  != S3 inter S1 = {}\n",
      "S2 inter S3 = {}  != S3 inter S2 = {}\n",
      "S1 diff S2 = {0, 1, 2, 3, 4}  != S2 diff S1 = {}\n",
      "S1 diff S3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}  != S3 diff S1 = {20, 21, 22, 23, 24}\n",
      "S2 diff S3 = {5, 6, 7, 8, 9}  != S3 diff S2 = {20, 21, 22, 23, 24}\n",
      "S1 diff sym S2 = {0, 1, 2, 3, 4}  != S2 diff sym S1 = {0, 1, 2, 3, 4}\n",
      "S1 diff sym S3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20, 21, 22, 23, 24}  != S3 diff sym S1 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20, 21, 22, 23, 24}\n",
      "S2 diff sym S3 = {5, 6, 7, 8, 9, 20, 21, 22, 23, 24}  != S3 diff sym S2 = {5, 6, 7, 8, 9, 20, 21, 22, 23, 24}\n"
     ]
    }
   ],
   "source": [
    "un_petit_test_avec_une_structure_densemble(SetWithInt32)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Parler de complexité n'aura pas de sens ici : on s'autorise seulement des ensembles ayant jusqu'à 32 valeurs.\n",
    "Donc $n\\leq32$, alors que les notations $O(n)$ (etc) sont des **notations asymptotiques** (ie. valables quand $n\\to\\infty$ !)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bidouillage 2/2 : implémentation avec des entiers en précision infinie avec Python\n",
    "- On ne verrait la différence que si on faisait des tests de la rapidité des opérations de bases, avec des valeurs $\\leq 31$ en comparaison de la structure utilisant des entiers natifs sur 32 bits.\n",
    "- On voit aussi la différence quant au fait que les ensembles représentés avec des entiers natifs 32/64 bits ne peuvent stocker que des valeurs entre 0 et 31 ou 63."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "SetWithIntInfinite = lambda: SetWithInt(int(0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{}\n",
      "{0}\n",
      "{0, 1}\n",
      "{0, 1, 2}\n",
      "{0, 1, 2, 3}\n",
      "{0, 1, 2, 3, 4}\n",
      "{0, 1, 2, 3, 4, 5}\n",
      "{0, 1, 2, 3, 4, 5, 6}\n",
      "{0, 1, 2, 3, 4, 5, 6, 7}\n",
      "{0, 1, 2, 3, 4, 5, 6, 7, 8}\n",
      "{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}\n",
      "S1 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}\n",
      "{}\n",
      "{5}\n",
      "{5, 6}\n",
      "{5, 6, 7}\n",
      "{5, 6, 7, 8}\n",
      "{5, 6, 7, 8, 9}\n",
      "S2 = {5, 6, 7, 8, 9}\n",
      "{}\n",
      "{20}\n",
      "{20, 21}\n",
      "{20, 21, 22}\n",
      "{20, 21, 22, 23}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "S3 = {20, 21, 22, 23, 24}\n",
      "S1 union S2 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}  = S2 union S1 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}\n",
      "S1 union S3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20, 21, 22, 23, 24}\n",
      "S2 union S3 = {5, 6, 7, 8, 9, 20, 21, 22, 23, 24}\n",
      "S1 inter S2 = {5, 6, 7, 8, 9}  != S2 inter S1 = {5, 6, 7, 8, 9}\n",
      "S1 inter S3 = {}  != S3 inter S1 = {}\n",
      "S2 inter S3 = {}  != S3 inter S2 = {}\n",
      "S1 diff S2 = {0, 1, 2, 3, 4}  != S2 diff S1 = {}\n",
      "S1 diff S3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}  != S3 diff S1 = {20, 21, 22, 23, 24}\n",
      "S2 diff S3 = {5, 6, 7, 8, 9}  != S3 diff S2 = {20, 21, 22, 23, 24}\n",
      "S1 diff sym S2 = {0, 1, 2, 3, 4}  != S2 diff sym S1 = {0, 1, 2, 3, 4}\n",
      "S1 diff sym S3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20, 21, 22, 23, 24}  != S3 diff sym S1 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20, 21, 22, 23, 24}\n",
      "S2 diff sym S3 = {5, 6, 7, 8, 9, 20, 21, 22, 23, 24}  != S3 diff sym S2 = {5, 6, 7, 8, 9, 20, 21, 22, 23, 24}\n"
     ]
    }
   ],
   "source": [
    "un_petit_test_avec_une_structure_densemble(SetWithIntInfinite)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.39 ms ± 80.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit random_add_remove_test(SetWithIntInfinite, size=1000, max_value=100, min_value=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4.09 ms ± 228 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n",
      "11.9 ms ± 875 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit random_add_remove_test(SetWithIntInfinite, size=1000, max_value=1000, min_value=0)\n",
    "%timeit random_add_remove_test(SetWithIntInfinite, size=1000, max_value=10000, min_value=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4.11 s ± 450 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
      "5.15 s ± 226 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%timeit random_add_remove_test(SetWithIntInfinite, size=1000_000, max_value=1000, min_value=0)\n",
    "%timeit random_add_remove_test(SetWithIntInfinite, size=1000_000, max_value=10000, min_value=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Avec cet implémentation, on ne peut raisonnablement pas stocker des valeurs trop grandes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "## Implémentation avec des tables de hachage ?\n",
    "\n",
    "### En Python : `set` ~= `dict` avec des valeurs \"inutiles\"\n",
    "L'implémentation standard des ensembles en Python, `set`, utilise en fait une implémentation très proche des `dict` de Python, avec des valeurs vides (et quelques optimisations).\n",
    "On va d'abord décrire le fonctionnement de tables de hachage simples, ne stockant que des valeurs (en fait, les clés des dictionnaires `dict`), et à la fin on expliquera rapidement comment généraliser au stockage de couples `(cle, valeur)`.\n",
    "\n",
    "### Présentation de l'idée :\n",
    "\n",
    "- On suppose que les valeurs que l'on va stocker dans l'ensemble sont dans un domaine $D$. Par exemple, $D = \\{0, \\dots, 1023\\}$.\n",
    "- On va se donner une fonction $f : D \\to \\{0, \\dots, m\\}$, qui soit simple à calculer. Par exemple, $m = 10$ et $f(x) = x \\mod 10 \\in\\{0,\\dots,9\\}$.\n",
    "- La table de hachage va consister en un premier tableau, de taille $m$, qui en position $i$ va pointer vers une autre structure d'ensemble (e.g., une structure linéaire ou même une autre table de hachage, dans le cas du hachage chaîné). Cette structure d'ensemble va servir à stocker toutes les valeurs qui ont pour image $i$ par la fonction $f$.\n",
    "\n",
    "<img width=\"55%\" src=\"figures/CM2_HashTableWithChaining.png\">\n",
    "\n",
    "Les opérations de base sur l'ensemble représenté par la table seront réalisées comme suit :\n",
    "\n",
    "- Lorsqu'on ajoute une valeur $v$ à la table :\n",
    "  + on calcule $j = f(v)$,\n",
    "  + on ajoute $v$ à l'ensemble en position $j$ du tableau :\n",
    "    * si c'est une liste chaînée par exemple, on créée une nouvelle liste contenant $v$ ou on ajoute $v$ à la fin de la liste chaînée,\n",
    "    * si c'est une autre table de hachage, on l'ajoute en utilisant la primitive de la table,\n",
    "    * etc\n",
    "\n",
    "- Lorsque l'on veut tester l'appartenance de $v$ à la table :\n",
    "  + on calcule $j = f(v)$ (le numéro de la cellule contenant $v$, on parle parfois aussi d'alvéole),\n",
    "  + on test si $v$ appartient à la liste / l'ensemble stocké en position $j$ du tableau.\n",
    "\n",
    "- La suppression fonctionne comme l'ajout."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Comment stocker les plus petits ensembles ?\n",
    "- A première vue, on est face à une idée stupide : pour stocker un ensemble, on en stocke $m$…\n",
    "- Mais si la fonction de hachage est bien faite, si elle envoie les données $x \\in D$ sur les $m$ différentes valeurs uniformément (en gros si $\\forall j\\in\\{0,\\dots,m\\}, \\# \\{ x \\in D : f(x) = j\\} \\simeq \\frac{1}{m}$)\n",
    "- Les opérations de base sur les sous ensembles (les alvéoles) sont en complexités (au pire cas) linéaires dans la taille de ces sous ensembles, ce qui dépend du remplissage actuel de la table."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Par exemple, avec $m = 20$, la fonction $f(x) = x \\mod 20$ et des valeurs qui sont des entiers aléatoirement tirés (cf. [cette page de démonstration](http://people.irisa.fr/Francois.Schwarzentruber/hash_tables_demo/)) :\n",
    "\n",
    "    0   |_|  --> []\n",
    "    1   |_|  --> [98281,92581,11221]\n",
    "    2   |_|  --> [91422,84022,65742,55322,59162]\n",
    "    3   |_|  --> [64583,43563]\n",
    "    4   |_|  --> []\n",
    "    5   |_|  --> [1665,1585]\n",
    "    6   |_|  --> [80986,80446,95966,28446,74726]\n",
    "    7   |_|  --> [40867,86987,47907]\n",
    "    8   |_|  --> [86268,31908,21688,59068,50448]\n",
    "    9   |_|  --> [65989,38369,69769]\n",
    "    10  |_|  --> [8670]\n",
    "    11  |_|  --> [27211,99291]\n",
    "    12  |_|  --> [43532]\n",
    "    13  |_|  --> [55033,3873,76353]\n",
    "    14  |_|  --> [74734]\n",
    "    15  |_|  --> [36075,62495,42015,75435,26415]\n",
    "    16  |_|  --> [85336,21856,18376,46436,64516]\n",
    "    17  |_|  --> [66117,95857]\n",
    "    18  |_|  --> [76438]\n",
    "    19  |_|  --> []\n",
    "\n",
    "Par exemples : \n",
    "- Ici, chercher l'appartenance de 76438 à l'ensemble se fera en deux opérations : calculer $f(76438)=18$, puis en cherchant (en une seule opération) $76438$ dans `T[18]=` $[76438]$.\n",
    "- Chercher $59068$ va trouver la cellule $f(59068) = 8$, qui contient 5 valeurs, et donc trouver $59068$ dans la liste $[86268,31908,21688,59068,50448]$ prend quatre opérations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Choix de la fonction de hachage\n",
    "- Il existe plein de fonction de hachage pour différentes utilisations.\n",
    "- Pour des entiers, on peut prendre $f(x) = x \\mod m$ et adapter $m$ en fonction des propriétés voulues par notre structure.\n",
    "  + Plus $m$ est grand, plus les opérations seront rapides mais plus on consomme de mémoire, inversement un plus petit $m$ réduit l'impact mémoire mais augmente l'impact temps.\n",
    "  + En fait, si nos entiers sont entre $0$ et $M$, on peut avoir les deux cas extrêmes suivants :\n",
    "    * la pire solution vis à vis du temps de calcul est d'utiliser $m = 1$, tous les entiers sont stockés dans la même liste. On a donc une complexité en $O(n)$ pour les opérations de base, cf. plus haut.\n",
    "    * la meilleure solution vis à vis du temps de calcul  est d'utiliser $m = M$, ie. la table de hachage est juste un vecteur de bit, où la case $j$ vaut $T[j]=[j]$ ssi $j$ est dans la table. Chaque entier est stocké dans sa propre liste, de taille vide ou de taille 1. On a donc une complexité en $O(1)$ pour les opérations de base, cf. plus haut.\n",
    "    * choisir un $m$ intermédiaire, par exemple $m = O(\\log(M))$, peut permettre de balancer entre les deux extrêmes.\n",
    "    \n",
    "- Pour des chaînes de caractères, on peut faire la somme des hachés de chaque caractères, modulo un certain nombre, ou n'importe quelle idée de ce genre.\n",
    "\n",
    "- Python utilise la fonction `hash()` :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Help on built-in function hash in module builtins:\n",
      "\n",
      "hash(obj, /)\n",
      "    Return the hash value for the given object.\n",
      "    \n",
      "    Two objects that compare equal must also have the same hash value, but the\n",
      "    reverse is not necessarily true.\n",
      "\n"
     ]
    }
   ],
   "source": [
    "help(hash)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "1048576"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "1061323352301500271"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hash(1)  # les entiers suffisamment petits sont hachés sur eux même\n",
    "hash(2**2399)\n",
    "hash(\"1\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2755244658530093468"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hash(\"Réfléchissez à l'impact écologique de TOUS les aspects de votre vie !\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Les détails d'implémentations de `hash` vont au delà de la portée de ce cours.\n",
    "- Voir [cette démonstration](http://people.irisa.fr/Francois.Schwarzentruber/hash_tables_demo/) pour des exemples de fonctions de hachage."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Pour l'exemple ici\n",
    "- Pour l'implémentation ici, on va utiliser la fonction `f(x) = hash(x) % m`, où `taille` sera un paramètre de la table.\n",
    "- L'avantage est que l'on pourra stocker n'importe quel objet Python (enfin, n'importe quel objet hachable, cf. [cette explication](https://stackoverflow.com/questions/14535730/what-does-hashable-mean-in-python)).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "def homemadeHash(m=1024):\n",
    "    def f(x):\n",
    "        return hash(x) % m\n",
    "    return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SetWithHashTable(SetWithNonPrimOperations):\n",
    "    \"\"\" Hash table with linked chaining: each cell uses a Python list to store the values.\"\"\"\n",
    "    sizeMax = 1024\n",
    "    \n",
    "    def __init__(self, size=sizeMax):\n",
    "        \"\"\" Create a new empty hash table.\"\"\"\n",
    "        self.size = size\n",
    "        self.hash = homemadeHash(size)\n",
    "        self.table = [ [] for _ in range(self.size) ]\n",
    "\n",
    "    def __len__(self):\n",
    "        \"\"\" Return n the current size of the set.\n",
    "        \n",
    "        - Takes O(m) time in all cases.\n",
    "        \"\"\"\n",
    "        return sum(len(cell) for cell in self.table)\n",
    "\n",
    "    def contains(self, value):\n",
    "        \"\"\" Test if value is in the set.\n",
    "        \n",
    "        - Takes O(k) for k the length of the cell containing the value.\n",
    "        \"\"\"\n",
    "        k = self.hash(value)\n",
    "        return value in self.table[k]\n",
    "    __contains__ = contains\n",
    "\n",
    "    def add(self, value):\n",
    "        \"\"\" Add value in the set if it is not present.\"\"\"\n",
    "        k = self.hash(value)\n",
    "        if value not in self.table[k]:\n",
    "            self.table[k].append(value)\n",
    "\n",
    "    def pop(self, value):\n",
    "        \"\"\" Remove value in the set if it is present.\"\"\"\n",
    "        k = self.hash(value)\n",
    "        if value in self.table[k]:\n",
    "            self.table[k].remove(value)\n",
    "    \n",
    "    def values(self):\n",
    "        \"\"\" Return a fresh list of the values of the set.\n",
    "        \n",
    "        - Takes O(n) time in worst case.\"\"\"\n",
    "        values = []\n",
    "        for cell in self.table:\n",
    "            for value in cell:\n",
    "                values.append(value)\n",
    "        return values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{}\n",
      "{0}\n",
      "{0, 1}\n",
      "{0, 1, 2}\n",
      "{0, 1, 2, 3}\n",
      "{0, 1, 2, 3, 4}\n",
      "{0, 1, 2, 3, 4, 5}\n",
      "{0, 1, 2, 3, 4, 5, 6}\n",
      "{0, 1, 2, 3, 4, 5, 6, 7}\n",
      "{0, 1, 2, 3, 4, 5, 6, 7, 8}\n",
      "{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}\n",
      "S1 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}\n",
      "{}\n",
      "{5}\n",
      "{5, 6}\n",
      "{5, 6, 7}\n",
      "{5, 6, 7, 8}\n",
      "{5, 6, 7, 8, 9}\n",
      "S2 = {5, 6, 7, 8, 9}\n",
      "{}\n",
      "{20}\n",
      "{20, 21}\n",
      "{20, 21, 22}\n",
      "{20, 21, 22, 23}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "S3 = {20, 21, 22, 23, 24}\n",
      "S1 union S2 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}  = S2 union S1 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}\n",
      "S1 union S3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20, 21, 22, 23, 24}\n",
      "S2 union S3 = {5, 6, 7, 8, 9, 20, 21, 22, 23, 24}\n",
      "S1 inter S2 = {5, 6, 7, 8, 9}  != S2 inter S1 = {5, 6, 7, 8, 9}\n",
      "S1 inter S3 = {}  != S3 inter S1 = {}\n",
      "S2 inter S3 = {}  != S3 inter S2 = {}\n",
      "S1 diff S2 = {0, 1, 2, 3, 4}  != S2 diff S1 = {}\n",
      "S1 diff S3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}  != S3 diff S1 = {20, 21, 22, 23, 24}\n",
      "S2 diff S3 = {5, 6, 7, 8, 9}  != S3 diff S2 = {20, 21, 22, 23, 24}\n",
      "S1 diff sym S2 = {0, 1, 2, 3, 4}  != S2 diff sym S1 = {0, 1, 2, 3, 4}\n",
      "S1 diff sym S3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20, 21, 22, 23, 24}  != S3 diff sym S1 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20, 21, 22, 23, 24}\n",
      "S2 diff sym S3 = {5, 6, 7, 8, 9, 20, 21, 22, 23, 24}  != S3 diff sym S2 = {5, 6, 7, 8, 9, 20, 21, 22, 23, 24}\n"
     ]
    }
   ],
   "source": [
    "un_petit_test_avec_une_structure_densemble(SetWithHashTable)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et maintenant quelques tests :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "211 µs ± 39.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n",
      "237 µs ± 13.8 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n",
      "4.14 ms ± 822 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n",
      "700 µs ± 151 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit random_add_remove_test(SetWithHashTable, size=10, max_value=10, min_value=0)\n",
    "%timeit random_add_remove_test(SetWithHashTable, size=10, max_value=1000, min_value=0)\n",
    "%timeit random_add_remove_test(SetWithHashTable, size=1000, max_value=10, min_value=0)\n",
    "%timeit random_add_remove_test(SetWithHashTable, size=100, max_value=100, min_value=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4.98 ms ± 1.04 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)\n",
      "6.52 ms ± 826 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n",
      "6.32 ms ± 706 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n",
      "6.76 ms ± 795 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit random_add_remove_test(SetWithHashTable, size=1000, max_value=1000, min_value=0)\n",
    "%timeit random_add_remove_test(SetWithHashTable, size=1000, max_value=1000_000, min_value=0)\n",
    "%timeit random_add_remove_test(SetWithHashTable, size=1000, max_value=1000_000_000, min_value=0)\n",
    "%timeit random_add_remove_test(SetWithHashTable, size=1000, max_value=1000_000_000_000, min_value=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La complexité (amortie) des opérations semble aussi indépendant de la taille des valeurs hachées (c'est logique, vu le modulo dans la fonction $f(x)$), et linéaire dans la taille des ensembles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.95 s ± 150 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%timeit random_add_remove_test(SetWithHashTable, size=1000_000, max_value=1000, min_value=0)\n",
    "#%timeit random_add_remove_test(SetWithHashTable, size=1000_000, max_value=1000_000, min_value=0)\n",
    "#%timeit random_add_remove_test(SetWithHashTable, size=1000_000, max_value=1000_000_000, min_value=0)\n",
    "#%timeit random_add_remove_test(SetWithHashTable, size=1000_000, max_value=1000_000_000_000, min_value=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On montre plus bas que cette implémentation \"maison\" en pure Python est raisonnablement efficace !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "## Implémentation avec des arbres binaires de recherche ?\n",
    "\n",
    "Pour plus de détails sur les arbres binaires de recherche, cf. le cours, le chapitre 12 du livre de référence \"Algorithmique\" de Cormen et al, et sur Internet.\n",
    "\n",
    "<img width=\"55%\" src=\"figures/CM2_BinarySearchTree.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Un nœud d'un arbre binaire\n",
    "\n",
    "- Un nœud contient une clé, `key`, et éventuellement une valeur associée,\n",
    "- Ainsi que des pointeurs vers d'autres nœuds (éventuellement) : parent, fils gauche (`left`) et fils droit (`right`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "class NodeTree():\n",
    "    def __init__(self, key, value=None, left=None, right=None, parent=None):\n",
    "        self.key = key\n",
    "        self.value = value\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.parent = parent\n",
    "    \n",
    "    def __str__(self):\n",
    "        if self.value is None:  # key is also the stored value\n",
    "            return \"{}\".format(self.key)\n",
    "        else:\n",
    "            return \"{}: {}\".format(self.key, self.value)\n",
    "\n",
    "    # --- First algorithm on this BST: compute the height ---\n",
    "    \n",
    "    def height(self):\n",
    "        \"\"\" Compute the height h of the Binary Search Tree.\n",
    "        \n",
    "        - Takes a time in O(n). Could be stored and take a time O(1) but it's useless.\"\"\"\n",
    "        h = 0\n",
    "        if self.left is not None:\n",
    "            h = max(h, 1 + self.left.height())\n",
    "        if self.right is not None:\n",
    "            h = max(h, 1 + self.right.height())\n",
    "        return h\n",
    "    \n",
    "    # --- Keys and values ---\n",
    "\n",
    "    def keys(self):\n",
    "        \"\"\" Extract the keys from the Binary Search Tree.\n",
    "        \n",
    "        - It is a generator, use list(self.keys()) to have a list.\n",
    "        - Takes a time in O(n) for n keys.\"\"\"\n",
    "        if self is not None:\n",
    "            if self.left is not None:\n",
    "                yield from self.left.keys()\n",
    "            yield self.key\n",
    "            if self.right is not None:\n",
    "                yield from self.right.keys()\n",
    "\n",
    "    def values(self):\n",
    "        \"\"\" Extract the values from the Binary Search Tree.\n",
    "        \n",
    "        - UIt is a generator, use list(self.keys()) to have a list.\n",
    "        - Takes a time in O(n) for n values.\"\"\"\n",
    "        if self is not None:\n",
    "            if self.left is not None:\n",
    "                yield from self.left.values()\n",
    "            yield self.value\n",
    "            if self.right is not None:\n",
    "                yield from self.right.values()\n",
    "    \n",
    "    # --- Search ---\n",
    "    \n",
    "    def search(self, key):\n",
    "        \"\"\" Search for the NodeTree(...) associated to the queried key. Returns None if not found.\n",
    "        \n",
    "        - Takes a time in O(h) = O(n) in worst case for n keys/values (if wrongly balanced).\"\"\"\n",
    "        if key is None or self.key is None:\n",
    "            raise KeyError\n",
    "        if self.key == key:\n",
    "            return self\n",
    "        elif key < self.key and self.left is not None:\n",
    "            return self.left.search(key)\n",
    "        elif key > self.key and self.right is not None:\n",
    "            return self.right.search(key)\n",
    "        raise KeyError\n",
    "\n",
    "    # --- Looking for minimum / successor ---\n",
    "    \n",
    "    def minimum(self):\n",
    "        \"\"\" Search for the NodeTree(...) associated to the minimum key.\n",
    "        \n",
    "        - Takes a time in O(h) = O(n) in worst case for n keys/values (if wrongly balanced).\"\"\"\n",
    "        if self.left is None:\n",
    "            return self\n",
    "        else:\n",
    "            return self.left.minimum()\n",
    "    \n",
    "    def successor(self, node):\n",
    "        \"\"\" Search for the NodeTree(...) successor of the queried node (ie. the node with smallest key >= node.key).\n",
    "        \n",
    "        - Takes a time in O(h) = O(n) in worst case for n keys/values (if wrongly balanced).\"\"\"\n",
    "        if node.right is not None:\n",
    "            return node.right.minimum()\n",
    "        x = node\n",
    "        y = x.parent\n",
    "        while y is not None and x == y.right():\n",
    "            x = y\n",
    "            y = x.parent\n",
    "        return y\n",
    "\n",
    "    # --- Looking for maximum / predecessor ---\n",
    "    \n",
    "    def maximum(self):\n",
    "        \"\"\" Search for the NodeTree(...) associated to the maximum key.\n",
    "        \n",
    "        - Takes a time in O(h) = O(n) in worst case for n keys/values (if wrongly balanced).\"\"\"\n",
    "        if self is None:\n",
    "            return self\n",
    "        else:\n",
    "            return self.right.maximum()\n",
    "    \n",
    "    def predecessor(self, node):\n",
    "        \"\"\" Search for the NodeTree(...) predecessor of the queried node (ie. the node with largest key <= node.key).\n",
    "        \n",
    "        - Takes a time in O(h) = O(n) in worst case for n keys/values (if wrongly balanced).\"\"\"\n",
    "        if node.left is not None:\n",
    "            return node.left.maximum()\n",
    "        x = node\n",
    "        y = x.parent\n",
    "        while y is not None and x == y.left():\n",
    "            x = y\n",
    "            y = x.parent\n",
    "        return y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les deux exemples de la figure se représentent comme ça :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Pour l'arbre équilibré de la figure (a) ci dessus :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "n_5 = NodeTree(5)\n",
    "n_3 = NodeTree(3)\n",
    "n_2 = NodeTree(2)\n",
    "n_5bis = NodeTree(5)\n",
    "n_7 = NodeTree(7)\n",
    "n_8 = NodeTree(8)\n",
    "\n",
    "n_5.left, n_5.right = n_3, n_7\n",
    "n_3.left, n_3.right = n_2, n_5bis\n",
    "n_7.right = n_8\n",
    "\n",
    "n_3.parent, n_7.parent = n_5, n_5\n",
    "n_2.parent, n_5bis.parent = n_3, n_3\n",
    "n_8.parent = n_7"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Pour l'arbre non équilibré de la figure (b) ci dessus :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "n_5 = NodeTree(5)\n",
    "n_3 = NodeTree(3)\n",
    "n_2 = NodeTree(2)\n",
    "n_5bis = NodeTree(5)\n",
    "n_7 = NodeTree(7)\n",
    "n_8 = NodeTree(8)\n",
    "\n",
    "n_2.right = n_3 ; n_3.parent = n_2\n",
    "n_3.right = n_7 ; n_7.parent = n_3\n",
    "n_7.left = n_5 ; n_5.parent = n_7\n",
    "n_5.left = n_5bis ; n_5bis.parent = n_5\n",
    "n_7.right = n_8 ; n_8.parent = n_7"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Un arbre binaire de recherche\n",
    "Et maintenant pour la classe :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "code_folding": []
   },
   "outputs": [],
   "source": [
    "class BinarySearchTree():\n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "        self.size = 0\n",
    "\n",
    "    # --- Looking for a (key,value) ---\n",
    "    \n",
    "    def get(self, key):\n",
    "        \"\"\" Search for the value associated to the queried key.\n",
    "        \n",
    "        - Takes a time in O(h) = O(n) in worst case for n keys/values (if wrongly balanced).\"\"\"\n",
    "        if self.root is None:\n",
    "            raise KeyError\n",
    "        node = self.root.search(key)\n",
    "        if node is not None:\n",
    "            return node.value\n",
    "        raise KeyError\n",
    "\n",
    "    def contains(self, value):\n",
    "        \"\"\" Test if value is in the set.\n",
    "        \n",
    "        - Takes O(h) for h the height of the BST.\n",
    "        \"\"\"\n",
    "        try:\n",
    "            _ = self.get(value)\n",
    "            return True\n",
    "        except KeyError:\n",
    "            return False\n",
    "    __contains__ = contains\n",
    "\n",
    "    # --- Looking for minimum / successor ---\n",
    "    \n",
    "    def minimum(self):\n",
    "        \"\"\" Search for the NodeTree(...) associated to the minimum key.\n",
    "        \n",
    "        - Takes a time in O(h) = O(n) in worst case for n keys/values (if wrongly balanced).\"\"\"\n",
    "        if self.root is not None:\n",
    "            return self.root.minimum()\n",
    "        raise KeyError\n",
    "    \n",
    "    def successor(self, node):\n",
    "        \"\"\" Search for the NodeTree(...) successor of the queried node (ie. the node with smallest key >= node.key).\n",
    "        \n",
    "        - Takes a time in O(h) = O(n) in worst case for n keys/values (if wrongly balanced).\"\"\"\n",
    "        if self.root is not None:\n",
    "            return self.root.successor(node)\n",
    "        raise KeyError\n",
    "\n",
    "    # --- Looking for maximum / predecessor ---\n",
    "    \n",
    "    def maximum(self):\n",
    "        \"\"\" Search for the NodeTree(...) associated to the maximum key.\n",
    "        \n",
    "        - Takes a time in O(h) = O(n) in worst case for n keys/values (if wrongly balanced).\"\"\"\n",
    "        if self.root is not None:\n",
    "            return self.root.maximum()\n",
    "        raise KeyError\n",
    "    \n",
    "    def predecessor(self, node):\n",
    "        \"\"\" Search for the NodeTree(...) predecessor of the queried node (ie. the node with largest key <= node.key).\n",
    "        \n",
    "        - Takes a time in O(h) = O(n) in worst case for n keys/values (if wrongly balanced).\"\"\"\n",
    "        if self.root is not None:\n",
    "            return self.root.predecessor(node)\n",
    "        raise KeyError\n",
    "\n",
    "    # --- Insertion ---\n",
    "    \n",
    "    def insert(self, key, value=None):\n",
    "        \"\"\" Insert a new key (or (key, value)) in the BST.\n",
    "        \n",
    "        - Takes a time in O(h) = O(n) in worst case for n keys/values (if wrongly balanced).\"\"\"\n",
    "        if key in self:\n",
    "            value_mapped = self.get(key)\n",
    "            if value == value_mapped:\n",
    "                return  # nothing to do, the pair (key, value) is already in the set!\n",
    "        self.size += 1\n",
    "        z = NodeTree(key, value=value)\n",
    "        y = None\n",
    "        x = self.root\n",
    "        while x is not None:\n",
    "            y = x\n",
    "            if z.key < x.key:\n",
    "                x = x.left\n",
    "            else:\n",
    "                x = x.right\n",
    "        z.parent = y\n",
    "        if y is None:  # the tree was empty!\n",
    "            self.root = z\n",
    "        elif z.key < y.key:\n",
    "            y.left = z\n",
    "        else:\n",
    "            y.right = z\n",
    "\n",
    "    # --- Supression/deletion: it is harder! ---\n",
    "    \n",
    "    def delete(self, key):\n",
    "        \"\"\" Delete the key in the BST.\n",
    "        \n",
    "        - Takes a time in O(h) = O(n) in worst case for n keys/values (if wrongly balanced).\"\"\"\n",
    "\n",
    "        if self.root is None:\n",
    "            raise KeyError\n",
    "        node_to_delete = self.root.search(key)\n",
    "        if node_to_delete is None:\n",
    "            raise KeyError\n",
    "\n",
    "        self.size -= 1\n",
    "        z = node_to_delete\n",
    "\n",
    "        # ligne 1-3 Cormen [Arbre-Supprimer]\n",
    "        if z.left is None or z.right is None:\n",
    "            y = z\n",
    "        else:\n",
    "            y = self.successor(z)\n",
    "        # ligne 4-6 Cormen [Arbre-Supprimer]\n",
    "        if y.left is not None:\n",
    "            x = y.left\n",
    "        else:\n",
    "            x = y.right\n",
    "        # ligne 7-8 Cormen [Arbre-Supprimer]\n",
    "        if x is not None:\n",
    "            x.parent = y.parent        \n",
    "        # ligne 9-13 Cormen [Arbre-Supprimer]\n",
    "        if y.parent is None:\n",
    "            self.root = x\n",
    "        elif y == y.parent.left:\n",
    "            y.parent.left = x\n",
    "        else:\n",
    "            y.parent.right = x\n",
    "        # ligne 14-16 Cormen [Arbre-Supprimer]\n",
    "        if y != z:\n",
    "            z.key, z.value = y.key, y.value\n",
    "        return y\n",
    "    \n",
    "    # --- Keys and values ---\n",
    "\n",
    "    def keys(self):\n",
    "        \"\"\" Extract the keys from the Binary Search Tree.\n",
    "        \n",
    "        - Takes a time in O(n) for n keys.\"\"\"\n",
    "        if self.root is not None:\n",
    "            return list(self.root.keys())\n",
    "        return []\n",
    "\n",
    "    def values(self):\n",
    "        \"\"\" Extract the values from the Binary Search Tree.\n",
    "        \n",
    "        - Takes a time in O(n) for n values.\"\"\"\n",
    "        if self.root is not None:\n",
    "            return list(self.root.values())\n",
    "        return []\n",
    "    \n",
    "    # --- Length, height ---\n",
    "    \n",
    "    def __len__(self):\n",
    "        return self.size\n",
    "\n",
    "    def height(self):\n",
    "        if self.root is not None:\n",
    "            return self.root.height()\n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "    # --- Draw the graph ---\n",
    "    \n",
    "    def to_nxgraph(self):\n",
    "        G = nx.DiGraph()\n",
    "        def go_down(node):\n",
    "            if node.left is not None:\n",
    "                G.add_node(node.left)\n",
    "                G.add_edge(node, node.left)\n",
    "                go_down(node.left)\n",
    "            if node.right is not None:\n",
    "                G.add_node(node.right)\n",
    "                G.add_edge(node, node.right)\n",
    "                go_down(node.right)\n",
    "        if self.root is not None:\n",
    "            G.add_node(self.root)\n",
    "            go_down(self.root)\n",
    "        return G\n",
    "    \n",
    "    def plot(self):\n",
    "        G = self.to_nxgraph()\n",
    "        pos = nx.drawing.nx_agraph.graphviz_layout(G, prog='dot')\n",
    "        return nx.draw(G, pos, with_labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dessiner l'ABR est facile, avec la bibliothèque [NetworkX](https://networkx.github.io/)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import networkx as nx    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Quelques exemples et quelques tests :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "keys = list(range(10))\n",
    "values = [ \"V{}\".format(key) for key in keys ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Clés de l'ABR = [] Valeurs de l'ABR = [] Hauteur de l'ABR = -1 Taille de l'ABR = 0\n",
      "Clés de l'ABR = [0] Valeurs de l'ABR = ['V0'] Hauteur de l'ABR = 0 Taille de l'ABR = 1\n",
      "Clés de l'ABR = [0, 1] Valeurs de l'ABR = ['V0', 'V1'] Hauteur de l'ABR = 1 Taille de l'ABR = 2\n",
      "Clés de l'ABR = [0, 1, 2] Valeurs de l'ABR = ['V0', 'V1', 'V2'] Hauteur de l'ABR = 2 Taille de l'ABR = 3\n",
      "Clés de l'ABR = [0, 1, 2, 3] Valeurs de l'ABR = ['V0', 'V1', 'V2', 'V3'] Hauteur de l'ABR = 3 Taille de l'ABR = 4\n",
      "Clés de l'ABR = [0, 1, 2, 3, 4] Valeurs de l'ABR = ['V0', 'V1', 'V2', 'V3', 'V4'] Hauteur de l'ABR = 4 Taille de l'ABR = 5\n",
      "Clés de l'ABR = [0, 1, 2, 3, 4, 5] Valeurs de l'ABR = ['V0', 'V1', 'V2', 'V3', 'V4', 'V5'] Hauteur de l'ABR = 5 Taille de l'ABR = 6\n",
      "Clés de l'ABR = [0, 1, 2, 3, 4, 5, 6] Valeurs de l'ABR = ['V0', 'V1', 'V2', 'V3', 'V4', 'V5', 'V6'] Hauteur de l'ABR = 6 Taille de l'ABR = 7\n",
      "Clés de l'ABR = [0, 1, 2, 3, 4, 5, 6, 7] Valeurs de l'ABR = ['V0', 'V1', 'V2', 'V3', 'V4', 'V5', 'V6', 'V7'] Hauteur de l'ABR = 7 Taille de l'ABR = 8\n",
      "Clés de l'ABR = [0, 1, 2, 3, 4, 5, 6, 7, 8] Valeurs de l'ABR = ['V0', 'V1', 'V2', 'V3', 'V4', 'V5', 'V6', 'V7', 'V8'] Hauteur de l'ABR = 8 Taille de l'ABR = 9\n",
      "Clés de l'ABR = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Valeurs de l'ABR = ['V0', 'V1', 'V2', 'V3', 'V4', 'V5', 'V6', 'V7', 'V8', 'V9'] Hauteur de l'ABR = 9 Taille de l'ABR = 10\n"
     ]
    }
   ],
   "source": [
    "BST = BinarySearchTree()\n",
    "\n",
    "for (k, v) in zip(keys, values):\n",
    "    print(\"Clés de l'ABR =\", list(BST.keys()), \"Valeurs de l'ABR =\", list(BST.values()), \"Hauteur de l'ABR =\", BST.height(), \"Taille de l'ABR =\", BST.size)\n",
    "    BST.insert(k, v)\n",
    "\n",
    "print(\"Clés de l'ABR =\", list(BST.keys()), \"Valeurs de l'ABR =\", list(BST.values()), \"Hauteur de l'ABR =\", BST.height(), \"Taille de l'ABR =\", BST.size)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/usr/local/lib/python3.6/dist-packages/networkx/drawing/nx_pylab.py:579: MatplotlibDeprecationWarning: \n",
      "The iterable function was deprecated in Matplotlib 3.1 and will be removed in 3.3. Use np.iterable instead.\n",
      "  if not cb.iterable(width):\n",
      "/usr/local/lib/python3.6/dist-packages/networkx/drawing/nx_pylab.py:676: MatplotlibDeprecationWarning: \n",
      "The iterable function was deprecated in Matplotlib 3.1 and will be removed in 3.3. Use np.iterable instead.\n",
      "  if cb.iterable(node_size):  # many node sizes\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3de3TU9YH//+dkJmSGmSRQkpBoAlViMkIIgtBWQAgJKxSvpVxKRa3iocdg23V/3XUtXr5fFb9gRTyroBu33VK8YBu61Wi6LhQSKWCXi4Qm5mKkuQGBBAhDLjPM7fdHymyzDYgknwkn83qc4znNez7vT9/vPz7nxfvzeV9MwWAwiIiISISIGugGiIiIhJOCT0REIoqCT0REIoqCT0REIoqCT0REIoqCT0REIoqCT0REIoqCT0REIoqCT0REIoqCT0REIoqCT0REIoqCT0REIoqCT0REIoqCT0REIoqCT0REIoqCT0REIoqCT0REIoqCT0REIoqCT0REIoqCT0REIoqCT0REIoqCT0REIoploBsgEkla2z0U7m+iqtmFy+0jzmrBmRzHwhtTGeGIGejmiUQEUzAYDA50I0QGu7LGNtaX1FJa0wKAxxcI/Wa1RBEEcjITyZ+ZzoS0YQPUSpHIoOATMdgbH9exqrgKt8/PxZ42kwmsFjMr5zlZ+o2vhq19IpFGrzpFDNQdepV0eQNfeG0wCF1eP6uKKwEUfiIG0eQWkT46deoU3/rWt7Db7YwePZq33noL6H69uaq46oKh1/FpKU0bHuB/v3Tp9Hj5Xt4NvPyLzQD8/ve/x+l0MnToUGbNmkV9fb2xHRIZ5BR8In20YsUKhgwZwvHjx3nzzTd56KGHqKioYH1JLW6f/4L1hmbcRMDTgafhTz3Kuw7vJ4iJP5m+SmtrK/Pnz+eZZ57h1KlTTJ48mcWLFxvcI5HBTd/4RPqgo6OD4cOHU15eTkZGBgD33HMPwxOT+dCe22MSS29O/u5lggE/Cbf+fais5berMTtGkDL3+3w/8TCFm99k9+7dof+/hIQEPvnkE5xOp3EdExnENOIT6YOamhosFkso9AAmTJhAycf7AfCdOUHDusX4zpzotb59fB6d1bsIeD0ABNwddNX+N47xeZiA9z/ay4QJE/7nerudMWPGUFFRYVynRAY5BZ9IH7S3txMXF9ejLD4+nlNtLjy+AJb4JEY98g6W+KRe61tTx2K2D6OrZg8AHVU7sQy/iiEjr8XtC3DiZBvx8fF/c/+zZ88a0yGRCKDgE+kDh8OBy+XqUeZyuYgaYrvke9izcmkv3w5AR/kOHFm5od+C0dZe7x8bG9uHVotENgWfSB9kZGTg8/n47LPPQmVlZWUkjU6/5Hs4xuXiri/Dc6QSz9Fq7ONmhX5LGX0dZWVlob87Ojr4/PPPGTduXP90QCQCKfhE+sButzN//nyefPJJOjo62LVrF++++y7zvrWIGMulPV6WYSOJSR1Ly7s/xXbNDZgdw4HuHV3m3n475eXlbNmyBbfbzdNPP012drYmtoj0gYJPpI82bNhAV1cXSUlJLFmyhFdffZUfLuh+Xek7c4KGtQsuOLnlPEdWHn7XCex//ZoTuD93Alu2bGHlypUMHz6cP/7xj2zevNnI7ogMelrOIGKQ5Zv2sbXy+EW3KbsQkwnmjB3Ja0sn93/DRCKcRnwiBlmRk47VYr6sulaLmfycS/9OKCKXTsEnYpAJacNYOc+JLfrLPWa26ChWznOSnapTGkSMoE2qRQx0fqNpnc4gcuXQNz6RMDjU1MaGklp2VLdgAty9nMc3KzOR/Jx0jfREDKbgEwmjk+0eCg80sW1vJVWH65k9YxrOlFgWTNIJ7CLhouATGQBFRUUUFBRQVFQ00E0RiTia3CISZp2dnbjdbnw+Hx0dHfj9Fz66SET6n0Z8ImFUVlbGDTfcgNlsJhDo/s734IMPUlBQMMAtE4kcGvGJhFFWVhajRo3C7/cTDAax2WwsXbp0oJslElEUfCJhZDabWbNmDVarFegOwhkzZgxwq0Qii151ioSZ3+8nJSWF1tZWSkpKFHwiYaYRn0iYmc1m/vEf/5HRo0cr9EQGgEZ8ImHU2u6hcH8TVc0uXG4fcVYLzuQ4Ft6odXwi4aLgEwmDssY21pfUUlrTAoCnl51bcjITyZ+ZzoQ07dwiYiQFn4jB3vi4Tnt1ilxBtEm1iIG6Q6+SLm/gC68NBqHL62dVcSWAwk/EIJrcItJHr7zyCpMnTyYmJobvfe97ofKyxjZWFVddMPQ8R6poWPttAue6epR3eQM8eFcejz37PADLly8nMzOTqKgofvGLXxjVDZGIoeAT6aOrrrqKxx9/nAceeKBH+fqSWty+C29HFnO1E3NsAp1Vu3qUn2upw9PawLERkwCYMGECGzZsYNKkSf3feJEIpFedIn00f/58APbt20dTUxPQPXuztKblot/0ABxZebSXb8eRPTtU1lG+Hdu1k9lz1MvJdg8rVqwACC16F5G+0YhPxACF+5tC/7th3WLcjRW9XmfPmoWnsRyfq3u2ZzAYoOPTUhzj8zABhQeaeq0nIpdPwSdigKpmV2jJwqhH3sGaNq7X6yxxiVhHjaejfAcA7roygj4vtjFTcPsCVB07G7Y2i0QKBZ+IAVxu3yVfax+fR3vFdqD7Naf9+hmYzJa/3MdrSPtEIpmCT8QAcdZL/3w+NGMq/rMncdcforNmD/bxeX91n2gjmicS0RR8In3k8/lwu934/X78fj9ut5vrEoYSY7m0xytqiJWhmdNo/eAlLPFJxKRcB3Tv6OJMieXcuXO43W6CwSBerxe32x06y09EvjwFn0gfPfvss9hsNlavXs0bb7yBzWaj/vebQr83rF2Au7H8ovdwZOXid53AnpUbKgsCCyalcsstt2Cz2di9ezfLly/HZrPx0UcfGdUdkUFPW5aJGGT5pn1srTz+hUsaemMywZyxI3lt6eT+b5hIhNOIT8QgK3LSsVrMl1XXajGTn5Pezy0SEVDwiRhmQtowVs5zYov+co+ZLTqKlfOcZKfqlAYRI2jnFhEDnd9oWqcziFw59I1PJAwONbWxoaSWHdUtmAB3L+fxzcpMJD8nXSM9EYMp+ETC6GS7h8IDTWzbW0nV4Xpmz5iGMyWWBZN0ArtIuCj4RAZAUVERBQUFFBUVDXRTRCKOJreIiEhE0YhPJIyOHj3K448/Tl1dHTU1NeTm5nLrrbeyePHigW6aSMTQrE6RMIqKimLTpk34fN2bWL/99ts4nc4BbpVIZNGrTpEwSk5OZtmyZVgs3f/mtNls/PCHPxzgVolEFgWfSJg99dRTREVFERUVxT//8z/jcDgGukkiEUXf+EQGwDe/+U22bdvG6dOnFXwiYaZvfCID4PXXX2fnzp0KPZEBoBGfSBi1tnso3N9EVbMLl9tHnNWCMzmOhTdqAbtIuCj4RMKgrLGN9SW1lNa0AODpZcuynMxE8memMyFNW5aJGEnBJ2KwNz6u0ybVIlcQfeMTMVB36FXS5Q184bXBIHR5/awqrgRQ+IkYRMsZRPrA4/GwbNkyRo8eTWxsLDfccAO/+93vgO7Xm6uKqy4Yep4jVTSs/TaBc109yru8AR68K4/Hnn2empoa7rzzThITE/nKV77CnDlzqK6uNrxfIoOZgk+kD3w+H2lpaZSWlnLmzBmeffZZFi1aRF1dHetLanH7/BesG3O1E3NsAp1Vu3qUn2upw9PawLERk2hra+OOO+6gurqa48eP87WvfY0777zT6G6JDGr6xifSz7Kzs3nk0Z+wuiq+xySW3pzZ/Su66g6S/N3nQmWnd/wc76mjpC1+kt2P5vaY7Xnq1ClGjBhBa2srI0aMMKwPIoOZRnwi/ej48ePU1NRQ7/9KqKxh3WLcjRW9Xm/PmoWnsRyfq3u2ZzAYoOPTUhzj8zABhQeaelz/0UcfkZycrNAT6QMFn0g/8Xq93H333dx33320xSSGRnujHnkHa9q4XutY4hKxjhpPR/kOANx1ZQR9XmxjpuD2Bag6djZ0bVNTEytWrODFF180vjMig5iCT6QfBAIB7rnnHoYMGcIrr7yCy+275Lr28Xm0V2wHoKN8O/brZ2Ayd0+4drm9ALS0tHDLLbeQn5/PkiVL+r8DIhFEwSfSR8FgkGXLlnH8+HG2bNlCdHQ0cdZLXyk0NGMq/rMncdcforNmD/bxeaHf4qzRnD59mltuuYU77riDlStXGtEFkYii4BPpo4ceeojKykqKioqw2WwAOJPjiLFc2uMVNcTK0MxptH7wEpb4JGJSrgO6d3QZHQdz5sxh2rRprF692rA+iEQSBZ9IH9TX1/Ov//qvHDx4kOTkZBwOR/fG07U7Q9c0rF2Au7H8ovdxZOXid53AnpUbKgsC0Q372Lt3L//+7/8eurfD4aChocGoLokMelrOIGKQ5Zv2sbXy+EW3KbsQkwnmjB3Ja0sn93/DRCKcRnwiBlmRk47VYr6sulaLmfyc9H5ukYiAgk/EMBPShrFynhNb9Jd7zGzRUayc5yQ7Vac0iBhBm1SLGOj8RtM6nUHkyqFvfCJhcKipjQ0lteyobsEEuHs5j29WZiL5Oeka6YkYTMEnEkYn2z0UHmhi295Kqg7XM3vGNJwpsSyYpBPYRcJFwScyAIqKiigoKKCoqGigmyIScTS5RSSMgsEgtbW1HDlyhPb2dmpqajh79uwXVxSRfqMRn0gYffLJJ0yaNAmr1YrX68VkMnHffffxb//2bwPdNJGIoeATCaNgMMi4ceOorKwEwGazsWvXLiZOnDjALROJHHrVKRJGJpOJtWvXYrVaAZg+fbpCTyTMNOITCbNgMMjo0aNpbGzkwIEDCj6RMNOITyTMTCYTTz31FDfeeKNCT2QAaMQnEkat7R4K9zdR1ezC5fYRZ7XgTI5j4Y1axycSLgo+kTAoa2xjfUktpTUtAHh62bklJzOR/JnpTEjTzi0iRlLwiRjsjY/rtFenyBVEm1SLGKg79Crp8ga+8NpgELq8flYVdy91UPiJGEOTW0T6aOnSpaSkpBAXF0dGRkZoMXpZYxuriqsuGHqeI1U0rP02gXNdPcq7vAEevCuPx559ntbWVqZNm8aIESMYNmwYN910E7t27TK8TyKDmUZ8In302GOP8bOf/YyYmBiqqqrIyclh4sSJ/OunQdw+/wXrxVztxBybQGfVLhzZs0Pl51rq8LQ2cGzEJBwOBz//+c+57rrrMJlMvPvuu9x+++2cOHECi0WPr8jl0IhPpI/GjRtHTEz3jEyTyYTJZOKTiipKa1ou+k0PwJGVR3v59h5lHeXbsV07mT1HvXT4TGRmZhIVFUUwGMRsNnP69GlOnTplVHdEBj0Fn0g/yM/PZ+jQoTidTlJSUmhPHB/6rWHdYtyNFb3Ws2fNwtNYjs/VPdszGAzQ8WkpjvF5mIDCA00AZGdnY7VaueOOO3jwwQdJSkoyvE8ig5WCT6QfbNiwgbNnz7Jz507mz5/P56fcoSULox55B2vauF7rWeISsY4aT0f5DgDcdWUEfV5sY6bg9gWoOtZ9csOhQ4dwuVy89dZbTJ8+PTydEhmkFHwi/cRsNjN9+nSamprY+7tfXXI9+/g82iu6X3d2lG/Hfv0MTObu73cutzd0ndVqZcmSJaxevZqysrL+bbxIBFHwifQzn8+H5+TRS75+aMZU/GdP4q4/RGfNHuzj80K/xVmj/+Z6r9fL4cOH+6WtIpFIwSfSBydOnGDz5s20t7fj9/v58MMPefvtt/nGzTOJsVza4xU1xMrQzGm0fvASlvgkYlKuA7p3dBlyqpY//OEPnDt3jq6uLtasWcPx48f5+te/bmS3RAY1BZ9IH5hMJl599VVSU1MZPnw4P/7xj3nppZd45offC13TsHYB7sbyi97HkZWL33UCe1ZuqCwITLsmnhUrVjBixAiuvvpqiouL+eCDD7jqqqsM6pHI4Kcty0QMsnzTPrZWHv/CJQ29MZlgztiRvLZ0cv83TCTCacQnYpAVOelYLebLqmu1mMnPSe/nFokIKPhEDDMhbRgr5zmxRX+5x8wWHcXKeU6yU3VKg4gRtOeRiIHObzSt0xlErhz6xicSBoea2thQUsuO6hZMgLuX8/hmZSaSn5OukZ6IwRR8ImF0st1D4YEmtu2tpOpwPbNnTMOZEsuCSTqBXSRcFHwiA6CoqIiCggKKiooGuikiEUeTW0REJKJoxCcSRnV1dTzwwAM0NzfT3NzMuHHjWLJkCfn5+QPdNJGIoRGfSBjFx8ezZ88eKisrOX36NH/84x/Rvz1FwkvBJxJGw4cP50c/+hHR0d2bT8fFxfHggw8OcKtEIouCTyTM/umf/omoqCiioqJ4+umnQ6e3i0h46BufyABYuHAh7733Hi6XS8EnEmYKPpEBcObMGcrLy5k2bdpAN0Uk4ij4RMKotd1D4f4mqppduNw+4qwWnMlxLLxRC9hFwkXBJxIGZY1trC+ppbSmBQBPL1uW5WQmkj8znQlp2rJMxEgKPhGDvfFxnTapFrmCaFanSD/57LPPsFqtLF26NFTWHXqVdHn/NvQ6Pi2lacMDoXV8wSB0ef08+345cV9J4P333+9x/dNPP43JZGLbtm2G90VkMFPwifSTFStWMGXKlNDfZY1trCquossb6PX6oRk3EfB04Gn4U4/yU9V76Tzn56qsb4TKPv/8c37961+TkpJiTONFIoiCT6QfbN68mWHDhpGXlxcqW19Si9vnv2Adk2UIdud02su39yjvKN+OfexMCv5QFypbsWIFa9asYciQIf3edpFIo+AT6SOXy8WTTz7Jiy++GCprbfdQWtOCt+0EDesW4ztzote69vF5dFbvIuD1ABBwd9BV+9/Ys/LYUd3CyXYPv/71r4mJiWHevHlh6Y/IYKcT2EX66IknnmDZsmWkpqaGygr3NwFgiU9i1CPvXLCuNXUsZvswumr2YB+XQ0fVTizDr2LIyGsxAW/8oYpXfvITtm7danQ3RCKGgk+kDw4ePMi2bdv45JNPepRXNbt6LFm4GHtWLu3l27uDr3wHjqxcoPuU9l++8gL33HMPX/3qV/u76SIRS686RfqgpKSEuro6Ro0aRXJyMi+88AJbtmxh06NLLvkejnG5uOvL8BypxHO0Gvu4WaHf6g79kX/5l38hOTmZ5ORkGhsbWbRoEWvWrDGiOyIRQev4RPqgs7MTl8sV+vuFF16grq6Or8zJ578Od13yfZrfegxf23GGJI4iaeH/CZXPHWPn/9zmDP09ZcoUXnzxRb75zW/icDj6pQ8ikUYjPpE+GDp0aGg0lpycjMPhwGq1MiljNDGWKHxnTtCwdsEFJ7ec58jKw+86gf0vrzmhe0eXiRlpPe5vNpsZPny4Qk+kDzTiEzFAa7uHaWu2X/J3vt7EWKLY/Wiu9vAU6Wca8YkYIMERw8yMREymy6tvMsGszESFnogBFHwiBlmRk47VYr6sulaLmfyc9H5ukYiAgk/EMBPShrFynhNb9Jd7zGzRUayc5yQ7Vac0iBhB6/hEDHT+lAWdziBy5dDkFpEwONTUxoaSWnZUt2Cie3H6eefP45uVmUh+TrpGeiIGU/CJhNHJdg+FB5rYtreSqsP1zJ4xDWdKLAsm6QR2kXBR8IkMgKKiIgoKCigqKhropohEHE1uEQkjr9dLSUkJZWVltLa2sn37dhobGwe6WSIRRSM+kTD605/+RHZ2NjabDa/Xi8lk4oEHHuC1114b6KaJRAwFn0iY3XTTTXz88ccAWK1WysrKyMjIGOBWiUQOveoUCbOf/vSnxMR0T2S59dZbFXoiYaYRn8gAyMzMpKamhurqagWfSJhpxCcyAFavXq3RnsgA0YhPJIxa2z0U7m+iqtmFy+0jzmrBmRzHwhu1jk8kXBR8ImFQ1tjG+pJaSmtaAHocV3R+55aczETyZ6YzIU07t4gYScEnYrA3Pq7TXp0iVxBtUi1ioO7Qq6TL+8UH0gaD0OX1s6q4EkDhJ2IQTW4R6aOcnBysVisOhwOHw0FmZibQ/XpzVXHVBUOv49NSmjY8wP9+6dLp8fK9vBt4+Rebqaurw2Qyhe7tcDh45plnDO+TyGCm4BPpB6+88grt7e20t7dTXV0NwPqSWtw+/wXrDM24iYCnA0/Dn3qUdx3eTxATfzJ9NVTW1tYWuv8TTzxhRBdEIoaCT8QAre0eSmtaLv5NzzIEu3M67eXbe5R3lG/HPnYmpbWnOd3hMbilIpFHwSfSDx577DESEhKYNm0aJSUlFO5vAsB35gQN6xbjO3Oi13r28Xl0Vu8i4O0OuIC7g67a/8YxPg8TUFzeDMDo0aNJTU3l/vvvp7W1NSx9EhmsFHwifbRmzRoOHz7MkSNHWL58ObfffjsfH6zA4wtgiU9i1CPvYIlP6rWuNXUsZvswumr2ANBRtRPL8KsYMvJa3L4AR93R7N27l/r6evbv38/Zs2e5++67w9k9kUFHyxlE+tncuXNpS8iiOW3WJV3ftuttPE2VjFz8NM1vPMrQ675O3NfnA5DnTOJn900JXdvc3ExKSgoul4vY2FhD2i8y2GnEJ9LPTCYTVsulP1qOcbm468vwHKnEc7Qa+7j/Ccw4a/Tf3BsgEPji5REi0jsFn0gftLW18eGHH+J2u/H5fLz55pt89NFHzJp9CzGXGH6WYSOJSR1Ly7s/xXbNDZgdw4HuHV1iTn9OdXU1gUCAkydP8sMf/pCcnBzi4+ON7JbIoKbgE+kDr9fL448/TmJiIgkJCbz88sv89re/ZcVdNwN/mdyydsEFJ7ec58jKw+86gT0rN1QWBK6N6WDu3LnExsaSlZVFTEwMb7/9tpFdEhn09I1PxCDLN+1ja+Xxiy5puBCTCeaMHclrSyf3f8NEIpxGfCIGWZGTjtVivqy6VouZ/Jz0fm6RiICCT8QwE9KGsXKeE1v0l3vMbNFRrJznJDtVpzSIGEGbVIsY6PxG0zqdQeTKoW98ImFwqKmNDSW17KhuwQS4ezmPb1ZmIvk56RrpiRhMwScSRifbPRQeaGLb3kqqDtcze8Y0nCmxLJikE9hFwkXBJzIAioqKKCgooKioaKCbIhJxNLlFREQiikZ8ImFUXV3NnXfeSVtbGy6Xi+TkZO6//36dsScSRprVKRJGqampHD16lLNnzwJw9OhRrrnmmgFulUhk0atOkTCy2+385Cc/ISameyJLQkICS5YsGeBWiUQWveoUCbOOjg4SExPxeDxs3LiRpUuXDnSTRCKKRnwiYWa321myZAkxMTEa7YkMAI34RMKotd1D4f4mKo+e4UTbWUZ+JQ5nchwLb9Q6PpFwUfCJhEFZYxvrS2oprWkBwNPLzi05mYnkz0xnQpp2bhExkoJPxGBvfFynvTpFriBaziBioO7Qq6TLG/jCa4NB6PL6WVVcCaDwEzGIJreI9IPNmzdz/fXXY7fbGTNmDDt37qSssY1VxVUXDD3PkSoa1n6bwLmuHuVd3gAP3pXHY88+D4Df7+fxxx/nqquuIjY2lokTJ9LW1mZ4n0QGK434RPpo69atPProo7zzzjt87Wtf49ixYwD83+21uH3+C9aLudqJOTaBzqpdOLJnh8rPtdThaW3g2IhJADz11FPs3r2bPXv2MGrUKCoqKrBarcZ2SmQQ0zc+kT6aOnUqy5YtY9myZaGy1nYP09Zs7zGJpTdndv+KrrqDJH/3uVDZ6R0/x3vqKGmLn6R4+UQmXJ9OWVkZY8aMMawPIpFErzpF+sDv97Nv3z5aWlpIT08nNTWVhx9+mLd214auaVi3GHdjRa/17Vmz8DSW43N1z/YMBgN0fFqKY3weJuDV3+7AYrFQWFhIcnIyGRkZrF+/PhxdExm09KpTpA+OHz+O1+ulsLCQnTt3Eh0dzZ133sl/H3kRj3M+AKMeeeeC9S1xiVhHjaejfAfxUxfhrisj6PNiGzMFty9ARU0dZ86coaamhj//+c989tln5OXlkZGRwd/93d+Fq5sig4pGfCJ9YLPZAPjBD35ASkoKCQkJ/MM//AOfH/jDJd/DPj6P9ortAHSUb8d+/QxM5u5/k54zmQF48sknsdlsZGdn853vfIfi4uJ+7olI5FDwifTB8OHDSU1NxWQyhcpMJhPmKNNFavU0NGMq/rMncdcforNmD/bxeaHfRo25PnTPv76/iFw+BZ9IH91///28/PLLnDhxgtOnT7Nu3Tom3zybGMulPV5RQ6wMzZxG6wcvYYlPIiblOqB7R5dvTBzLzTffzKpVq/B4PFRWVrJ582Zuu+02I7skMqgp+ET66IknnmDKlClkZGRw/fXXM3HiRApeXBX6vWHtAtyN5Re9hyMrF7/rBPas3FBZEFgwKZW3336b+vp6RowYwa233sozzzxDXl7ehW8mIhel5QwiBlm+aR9bK49fdJuyCzGZYM7Ykby2dHL/N0wkwmnEJ2KQFTnpWC3my6prtZjJz0nv5xaJCCj4RAwzIW0YK+c5sUV/ucfMFh3FynlOslN1SoOIEbSOT8RA5zea1ukMIlcOfeMTCYNDTW1sKKllR3ULJsDdy3l8szITyc9J10hPxGAKPpEwOtnuofBAE9v2VlJ1uJ7ZM6bhTIllwSSdwC4SLgo+kQFQVFREQUEBRUVFA90UkYijyS0iIhJRFHwiYdTe3s6bb77Jjh07aGpqYtOmTRw6dGigmyUSUfSqUySMampqyMzMJCYmBp/PR1RUFPn5+bz00ksD3TSRiKHgEwmzOXPmsHXrVoLBIFarlc8++4zU1NSBbpZIxNCrTpEwe/7554mOjsZkMnH33Xcr9ETCTCM+kQEwadIkDh48SENDg4JPJMy0c4vIAFi3bh1vvfWWQk9kAGjEJxJGre0eCvc3UdXswuX2EWe14EyOY+GNWsAuEi4KPpEwKGtsY31JLaU1LQB4etmyLCczkfyZ6UxI05ZlIkZS8IkY7I2P67RJtcgVRN/4RAzUHXqVdHkDX3htMAhdXj+riisBFH4iBtFyBpE+cjgcPf4zm8384Ac/oKyxjVXFVRcMPc+RKhrWfpvAua4e5V3eAA/elcdjzz7Pzp07/+b+JpOJLVu2hKNrIoOSgk+kj9rb20P/NTc3Y7PZWLhwIetLanH7/BesF4licsQAAAxSSURBVHO1E3NsAp1Vu3qUn2upw9PawLERk7j55pt73P/999/H4XAwd+5co7slMmgp+ET60ZYtW0hKSuL6iV+jtKblot/0ABxZebSXb+9R1lG+Hdu1k9lz1MvJdk+P3zZu3MiCBQuw2+393XSRiKHgE+lHGzdu5N5772XLgSOhsoZ1i3E3VvR6vT1rFp7Gcnyu7tmewWCAjk9LcYzPwwQUHmgKXdvR0UFhYSH33XefoX0QGewUfCL9pL6+ntLSUu677z6qml2hJQujHnkHa9q4XutY4hKxjhpPR/kOANx1ZQR9XmxjpuD2Bag6djZ07W9+8xsSEhKYOXOm8Z0RGcQUfCL9ZNOmTUyfPp1rrrkGl9t3yfXs4/Nor+h+3dlRvh379TMwmbsnXLvc3tB150eTJpOpfxsuEmEUfCL95Je//GXoNWSc9dJXCg3NmIr/7Enc9YforNmDfXxe6Lc4azQAjY2NlJSUcO+99/Zvo0UikIJPpB/s3r2bI0eOsHDhQgCcyXHEWC7t8YoaYmVo5jRaP3gJS3wSMSnXAd07ujhTYoHu0eTUqVMZM2aMMR0QiSAKPpF+sHHjRubPn09sbHdQLbjxfzafbli7AHdj+UXrO7Jy8btOYM/KDZUFgQWTuu/z16NJEekbbVkmYpDlm/axtfL4Fy5p6I3JBHPGjuS1pZP7v2EiEU4jPhGDrMhJx2oxX1Zdq8VMfk56P7dIREDBJ2KYCWnDWDnPiS36yz1mtugoVs5zkp2qUxpEjKBNqkUMdH6jaZ3OIHLl0Dc+kTA41NTGhpJadlS3YALcvZzHNyszkfycdI30RAym4BMJo5PtHgoPNLFtbyVVh+uZPWMazpRYFkzSCewi4aLgExkARUVFFBQUUFRUNNBNEYk4mtwiIiIRRSM+kTCqqKhg+vTpuN1uvF4vNpuN73//+7zwwgsD3TSRiKFZnSJhdN1112GxWHC73QD4/X6dtiASZnrVKRJGQ4YM4ZlnnsFqtQKQlpbGbbfdNsCtEoksetUpEmbnzp0jISGB9vZ23n33XW6//faBbpJIRNGITyTMhgwZwvLly4mPj9doT2QAaMQnEkat7R4K9zdR1eziTOc54ocOwZkcx8IbtY5PJFwUfCJhUNbYxvqSWkprWgDw9LJzS05mIvkz05mQpp1bRIyk4BMx2Bsf12mvTpEriJYziBioO/Qq6fIGvvDaYBC6vH5WFVcCKPxEDKLJLSJ9UFdXx7x58xg+fDjJyck8/PDD+Hw+oPv15qriql5Dz3e2lfo1d+A9fexvfqvf/DQ/euT/41BTGwcPHuTmm28mPj6e1NRUnnnmGcP7JDLYKfhE+iA/P5+kpCSOHTvGwYMHKS0tZcOGDQCsL6nF7fP3Ws8Sm4D1qxPoKN/eo9zfdZauw/uwjstlQ0kt3/3ud5kxYwanTp0K3fu9994zvF8ig5mCT6QP/vznP7No0SKsVivJycnMnTuXiooKWts9lNa0XPSbniMrj46KHT3KOis/InrEKKITv8qO6hbq6uq4++67MZvNjBkzhunTp1NRUWFwr0QGNwWfSB/8/d//PZs3b6azs5MjR47wu9/9jrlz51K4vwmAoz97mI6Kkl7r2jJuwt/lwt34P0HWXr4dx/g8AEzAzPn38ctf/hKv10t1dTV79uxh9uzZRndLZFBT8In0wYwZM6ioqCAuLo7U1FQmT57MXXfdRVWzC48vwFXLXsE+LqfXulHRMdgzp4ded3pPHeFc8+fYx3bv3en2BYjL+DqFhYXYbDacTifLli1jypQp4eqeyKCk4BO5TIFAgLlz5zJ//nw6OjpobW3l9OnTPProo7jcvku6h318Lp1VfyDoO0dH+Q5s10zEbO9ex+fvOst//L+HefLJJ3G73TQ2NvLhhx+GviGKyOVR8IlcplOnTtHQ0MDDDz9MTEwMI0aM4P7776e4uJg466WtFIpJHUeULZbOzz6mo2IH9r+85gTwtTUTZY7i3nvvxWKxkJqayne+8x2Ki4uN6pJIRFDwiVymhIQErrnmGl599VV8Ph9tbW1s3LiR7OxsnMlxxFi++PEymUzYs3I5veMXBDwdDE3/eug3R1IaUSZ46623CAQCNDc3884775CdnW1kt0QGPQWfSB/85je/4T//8z9JTEwkPT2d6Oho1q1bx4IbUwE4+m/5tP+vmZv/mz0rF7+rhaHX34zJEh0qj4oZypubf8W6desYPnw4N9xwA1lZWTz++OOG9klksNOWZSIGWb5pH1srj190ScOFmEwwZ+xIXls6uf8bJhLhNOITMciKnHSsFvNl1bVazOTnpPdzi0QEFHwihpmQNoyV85zYor/cY2aLjmLlPCfZqTqlQcQI2qRaxEDnN5rW6QwiVw594xMJg0NNbWwoqWVHdQsmuhenn3f+PL5ZmYnk56RrpCdiMAWfSBidbPdQeKCJbXsrqTpcz+wZ03CmxLJgkk5gFwkXBZ/IACgqKqKgoICioqKBbopIxNHkFhERiSga8YmE0alTp3j99depqKhg79693HvvvUydOpWZM2cOdNNEIoaCTySM6urquPbaawEIBoOYzWZ+/OMfs3r16gFumUjkUPCJhNmiRYvYsmULgUCAoUOHUl9fT0JCwkA3SyRi6BufSJg999xzmM1moqKieOihhxR6ImGmEZ/IAJg+fTp79uzh+PHjCj6RMNPOLSID4NVXX+W9995T6IkMAI34RMKotd1D4f4mqppduNw+4qwWnMlxLLxRC9hFwkXBJxIGZY1trC+ppbSmBQBPL1uW5WQmkj8znQlp2rJMxEgKPhGDvfFxnTapFrmC6BufiIG6Q6+SLm/gC68NBqHL62dVcSWAwk/EIFrOINJHlZWV5ObmEh8fT3p6Ov/xH/8BdL/eXFVcdcHQ8xypomHttwmc6+pR3uUN8OBdeTz27PNA976eWVlZOBwOpk6dyqeffmpsh0QGOQWfSB/4fD7uvPNObrvtNk6dOkVBQQFLly6lpqaG9SW1uH3+C9aNudqJOTaBzqpdPcrPtdThaW3g2IhJfPbZZ9x999289tprtLW1cfvtt3PHHXfg8/mM7prIoKVvfCJ9UF5ezje+8Q3Onj2LyWQC4JZbbmH8xBt5f8iMHpNYenNm96/oqjtI8nefC5Wd3vFzvKeOkrb4SR4YVs1H27fywQcfABAIBLDb7bz//vvk5eUZ1zGRQUwjPpF+FgwG+f3u/aG/G9Ytxt1Y0eu19qxZeBrL8bla/lI3QMenpTjG52ECPmk8zV//2zQYDBIMBikvLze0DyKDmYJPpA8yMzNJSkripz/9KV6vl//6r/+itLSU066zodHeqEfewZo2rtf6lrhErKPG01G+AwB3XRlBnxfbmCm4fQFiRt1AaWkpJSUlnDt3jueee45z587R2dkZtj6KDDYKPpE+iI6O5re//S0ffPABycnJrF27lkWLFhETn3jJ97CPz6O9YjsAHeXbsV8/A5O5e8K1ZUQqGzdu5OGHHyYlJYXW1lbGjh1LamqqIf0RiQT6xifSz6ZOnYpt3Cw+T5h6SdcHzrlpeuUekr79BCcKn2bkd/8fMSnXAfCtG65m3eIbQte2tbWRmprKvn37cDqdhrRfZLDTiE+kjw4dOoTb7aazs5MXXniBY8eOcdeiu4mxXNrjFTXEytDMabR+8BKW+KRQ6FktUThTYtm/fz9+v5+WlhaWL1/OHXfcodAT6QMFn0gfbdq0iZSUFJKSkvj973/P1q1bWXLTmNDvDWsX4G68+GQUR1YuftcJ7Fm5obIgsGBSKj/60Y8YNmwYmZmZDB8+nNdff92orohEBL3qFDHI8k372Fp5/KLblF2IyQRzxo7ktaWT+79hIhFOIz4Rg6zIScdqMV9WXavFTH5Oej+3SERAwSdimAlpw1g5z4kt+ss9ZrboKFbOc5KdqlMaRIygTapFDHR+o2mdziBy5dA3PpEwONTUxoaSWnZUt2AC3L2cxzcrM5H8nHSN9EQMpuATCaOT7R4KDzRRdewsLreXOGs0zpRYFkzSCewi4aLgExGRiKLJLSIiElEUfCIiElEUfCIiElEUfCIiElEUfCIiElEUfCIiElEUfCIiElEUfCIiElEUfCIiElEUfCIiElEUfCIiElEUfCIiElEUfCIiElEUfCIiElEUfCIiElEUfCIiElEUfCIiElEUfCIiElEUfCIiElEUfCIiElEUfCIiElH+f2uqnDDGt+SKAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "BST.plot()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Maintenant si l'ordre d'insertion des clés n'est plus monotone, on va éviter d'avoir un arbre binaire réduit à une chaîne."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Clés et valeurs = [(2, 'V2'), (8, 'V8'), (3, 'V3'), (5, 'V5'), (6, 'V6'), (4, 'V4'), (9, 'V9'), (0, 'V0'), (1, 'V1'), (7, 'V7')]\n",
      "Clés de l'ABR = [2] Valeurs de l'ABR = ['V2'] Hauteur de l'ABR = 0 Taille de l'ABR = 1\n",
      "Clés de l'ABR = [2, 8] Valeurs de l'ABR = ['V2', 'V8'] Hauteur de l'ABR = 1 Taille de l'ABR = 2\n",
      "Clés de l'ABR = [2, 3, 8] Valeurs de l'ABR = ['V2', 'V3', 'V8'] Hauteur de l'ABR = 2 Taille de l'ABR = 3\n",
      "Clés de l'ABR = [2, 3, 5, 8] Valeurs de l'ABR = ['V2', 'V3', 'V5', 'V8'] Hauteur de l'ABR = 3 Taille de l'ABR = 4\n",
      "Clés de l'ABR = [2, 3, 5, 6, 8] Valeurs de l'ABR = ['V2', 'V3', 'V5', 'V6', 'V8'] Hauteur de l'ABR = 4 Taille de l'ABR = 5\n",
      "Clés de l'ABR = [2, 3, 4, 5, 6, 8] Valeurs de l'ABR = ['V2', 'V3', 'V4', 'V5', 'V6', 'V8'] Hauteur de l'ABR = 4 Taille de l'ABR = 6\n",
      "Clés de l'ABR = [2, 3, 4, 5, 6, 8, 9] Valeurs de l'ABR = ['V2', 'V3', 'V4', 'V5', 'V6', 'V8', 'V9'] Hauteur de l'ABR = 4 Taille de l'ABR = 7\n",
      "Clés de l'ABR = [0, 2, 3, 4, 5, 6, 8, 9] Valeurs de l'ABR = ['V0', 'V2', 'V3', 'V4', 'V5', 'V6', 'V8', 'V9'] Hauteur de l'ABR = 4 Taille de l'ABR = 8\n",
      "Clés de l'ABR = [0, 1, 2, 3, 4, 5, 6, 8, 9] Valeurs de l'ABR = ['V0', 'V1', 'V2', 'V3', 'V4', 'V5', 'V6', 'V8', 'V9'] Hauteur de l'ABR = 4 Taille de l'ABR = 9\n",
      "Clés de l'ABR = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Valeurs de l'ABR = ['V0', 'V1', 'V2', 'V3', 'V4', 'V5', 'V6', 'V7', 'V8', 'V9'] Hauteur de l'ABR = 5 Taille de l'ABR = 10\n",
      "Valeur associée à 0 = V0\n",
      "Valeur associée à 1 = V1\n",
      "Valeur associée à 2 = V2\n",
      "Valeur associée à 3 = V3\n",
      "Valeur associée à 4 = V4\n",
      "Valeur associée à 5 = V5\n",
      "Valeur associée à 6 = V6\n",
      "Valeur associée à 7 = V7\n",
      "Valeur associée à 8 = V8\n",
      "Valeur associée à 9 = V9\n"
     ]
    }
   ],
   "source": [
    "BST = BinarySearchTree()\n",
    "\n",
    "keys_values = list(zip(keys, values))\n",
    "\n",
    "import random\n",
    "random.seed(1234)\n",
    "random.shuffle(keys_values)\n",
    "print(\"Clés et valeurs =\", keys_values)\n",
    "\n",
    "for (k, v) in keys_values:\n",
    "    BST.insert(k, v)\n",
    "    print(\"Clés de l'ABR =\", list(BST.keys()), \"Valeurs de l'ABR =\", list(BST.values()), \"Hauteur de l'ABR =\", BST.height(), \"Taille de l'ABR =\", BST.size)\n",
    "\n",
    "for k in keys:\n",
    "    print(\"Valeur associée à\", k, \"=\", BST.get(k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3deVyVZf7/8deBgxwEccEFCzO/KaDgQmq55kJm2WRm6mRqWZozLtPUZKLillta2eqSv5rKrNQZnDZjbNygcWsUE0XZ1BAxRdQIQc6Bwzm/P0gaJ/eAA+d+Px+PHo+873PffS67OG+u+7rv6zY5nU4nIiIiBuHh6gJEREQqk4JPREQMRcEnIiKGouATERFDUfCJiIihKPhERMRQFHwiImIoCj4RETEUBZ+IiBiKgk9ERAxFwSciIoai4BMREUNR8ImIiKEo+ERExFAUfCIiYigKPhERMRQFn4iIGIqCT0REDEXBJyIihqLgExERQ1HwiYiIoSj4RETEUMyuLkCqhtP5NmISskg5mUee1Y6/xUxooD+D2wcR4Oft6vJERMqNyel0Ol1dhLhO4rFclsQdIj4tBwCb3VG2z2L2wAn0DGnAuB7NadukjouqFBEpPwo+A/toZwbzYlOw2ku4Ui8wmcBi9iS6XyjDO91aafWJiFQEXeo0qNLQS6aw2HHVzzqdUFhcwrzYZACFn4hUa7q5xQ3ZbDZGjRpF06ZNqVWrFu3ateOf//xn2f7EY7nMi025ZOjZjqeQuehhHEWFv9p3ePkEJr7wEl98s5sHH3yQBg0aUK9ePfr27UtqamqFtklEpLwo+NyQ3W6nSZMmxMfH89NPPzF37lyGDBlCRkYGAEviDmG1l1zyWO+bQ/GsVZ/zKdsu2l6Uk0HxmUxqhHTngy0H6N+/P6mpqWRnZ3PHHXfw4IMPVnSzRETKheb4DKJNmzbMnDmTHn1/R9eFmy+6ieV//bT9bxRm7CXw0fll237c8h7FZ3+g4cPT8DZ7sD2qd9ndnmfPniUgIIDTp08TEBBQ4W0REfktNOIzgOzsbNLS0ggLCyMmIQuAzNd+j/XYgUt+3je8F7ZjSdjzSu/0dDodFByMx691JAAmIGZPVtnnv/nmGwIDAxV6IlItKPjcXHFxMcOGDePxxx8nNDSUlJN52OwObnl2DZYmYZc8xuzfAMstrSlI2gKANSMRp70Yn9s6lv7Z7iDlxDkAsrKyGD9+PK+++mrlNEhE5DdS8Lkxh8PBiBEjqFGjBosXLwYgz2q/pmN9W0eSf2AzAAVJm/FteRcmz19uAs6zFpOTk8M999zDuHHjGDp0aPk3QESkAij43JTT6WTUqFFkZ2ezdu1avLy8APC3XNsTLDWDu1By7gzWo/s4n7YD358vc15Qw17IPffcQ//+/YmOji73+kVEKoqCz02NHTuW5ORkvvzyS3x8fMq2hwb6422++v92jxoWaoZ05fRXr2Ou3RDvxi3K9nmVWPnnK3+ia9euLFiwoELqFxGpKAo+N3T06FGWL1/O3r17CQwMxM/PDz8/Pz766CPqnE3BZrORuWgQ1mNJVzyPX3hvSvJO4Rve+6LtecnbOJqyj/fff7/s3H5+fmRmZlZks0REyoUeZzCIb7/9lqioKE6dOkXzkQvZn+txxWXKLs+J4+geOtoSmTt3Li1btizvUkVEKpRGfG4uNTWVQYMG8fDDDzNixAj27dvHnKHdsZg9b+h8Pl5mYmaP4c4776RHjx488cQTZQ/Gi4hUBwo+N3XixAnGjh1L165d6dChA2lpaYwaNQqz2UzbJnWI7heKj9f1/e/38fIgul8odzQPZNKkSaSnpxMUFET79u15+umnyc7OrqDWiIiUHwWfm8nLy2P69OmEh4dTs2ZNUlNTmTx5MjVr1rzoc8M73Up0v5b4eHliMl35nCYT+Hh5Et2v5UULVNeuXZs5c+Zw8OBBTCYTrVq1Ytq0aeTm5lZAy0REyoeCz00UFRXx5ptv0qJFCzIzM9mzZw+LFi264moqwzvdypoxnejbqhHeZg8s/3O3p8XsgbfZg76tGrFmTKfLvpWhUaNGvPHGG+zZs4cffviB4OBgXnrpJc6fP1+eTRQRKRe6uaWaczgcrFmzhujoaEJDQ1mwYAFt2rS57vOcybcRsyeLlBPnyLMW42/xIrRxLQbdfv1vYE9OTmb69Ons2LGDadOmMXr06LLnCEVEXE3BV41t2LCBqKgozGYzCxcupFevXq4u6SK7d+8mOjqaQ4cOMXv2bIYOHYqHhy4yiIhrKfiqoT179jB58mQyMjKYP38+Dz/8MKarTdS5UFxcHFOmTKGgoIB58+bxu9/9rkrXKyLuTcFXjRw5coRp06axZcsWZsyYUa0uITqdTr788kuio6OpVasW8+fPp2fPnq4uS0QMSNedqoGcnBz+/Oc/c8cdd9CyZUvS09MZO3ZstQk9AJPJRP/+/dm7dy/jxo3jySefpG/fviQkJLi6NBExGAVfFZafn8+cOXMIDQ3F6XRy8OBBpk+fjp+fn6tLu2Genp4MHz6clJQUBgwYQP/+/Rk8eDApKSmuLk1EDELBVwUVFxfz9ttvExwczMGDB/nPf/7Dm2++ScOGDV1dWrmpUaMGY8eOJT09nQ4dOtC9e3dGjRql9T5FpMIp+KoQp9NJTExM6ZvSY2L48ssvWbVqFbfddpurS6swNWvWJCoqivT0dBo3bkxERATPPPMMp06dcnVpIuKmFHxVRHx8PJ06dWLevHksXryYDRs20L59e1eXVWnq1KnD3LlzOXjwIA6Hg5YtWzJjxgx++uknV5cmIm5Gwedi+/bt4/7772fkyJH8+c9/JiEhgXvuucewt/s3atSIN998k4SEBDIzM2nRogWvvPIKhYWFri5NRNyEgs9FMjMzGTlyJH369OGee+4hJSWFRx99VA94/+zWW2/lgw8+IC4ujh07dtCiRQuWL19OcXGxq0sTkWpO37KV7OzZs0ycOJGIiAiaNGlCWloaf/7zn/H2vr5lwYyiVatWrF27lk8//ZSYmBhatWrFqlWrcDgcri5NRKopBV8lKSwsZOHChYSEhHDu3DmSkpKYM2cOtWvXdnVp1ULHjh3ZsGEDy5cv54033iAiIoJ169ah9RdE5Hpp5ZYKZrfbWbFiBTNnziy7eSUkJMTVZVVrTqeTL774gujoaOrUqcP8+fO56667XF2WiFQTCr4KcmGJrilTphAQEMBLL71Ep06dXF2WWykpKeGTTz5h5syZhISEMH/+fCIiIlxdlohUcQq+CrB9+3YmTZpEbm4uCxYs4P777zfsXZqVoaioiHfffZe5c+fSvXt3Zs+erVG1iFyW5vjKUXJyMg899BCPPPIIo0ePJjExUW8iqAQ1atRg3LhxpKenExERQbdu3Rg9ejTHjh1zdWkiUgUp+MrB8ePHeeqpp7jrrrvo0qULqampjBw5Ek9PT1eXZii+vr5MnjyZtLQ0GjZsSLt27fjLX/5CTk6Oq0sTkSpEwfcb5ObmMnXqVNq0aUO9evVIS0vj+eefx8fHx9WlGVrdunWZP38+Bw4coLi4mJYtWzJr1izy8vJcXZqIVAEKvhtgs9l49dVXCQ4O5uTJk+zdu5eFCxdSt25dV5cm/yUwMJC33nqLXbt28f3339OiRQsWLVqkVWBEDE7Bdx1KSkpYuXIlISEhxMXFsXnzZt577z2aNGni6tLkCpo1a8aKFSvYvHkzW7duJTg4mHfeeQe73e7q0kTEBXRX5zVwOp18/fXXREVFUbNmTRYuXKjnxqqxb7/9lqlTp3Ls2DHmzJnD4MGDtVSciIEo+K5i165dREVF8cMPP/Diiy8yYMAA3aXpJjZt2sSUKVMoLi5m3rx53Hffffp/K2IACr7LOHToEFOnTmXbtm3MnDmTJ598ErPZ7OqypJw5nU4+++wzpk2bRr169XjxxRfp1q2bq8sSkQqk6zv/Izs7m/Hjx9OpUyfatWtHWloaY8aMUei5KZPJxEMPPcS+ffsYPXo0w4cP5/7772fv3r2uLk1EKoiC72fnzp1j1qxZtGrViho1apCSksLUqVPx9fV1dWlSCTw9PXn88cdJTU3lvvvu47777mPo0KGkp6e7ujQRKWeGD76ioiIWL15MixYtOHz4MLt37+a1116jfv36ri5NXMDb25sJEyZw6NAhWrduTZcuXRgzZgxZWVmuLk1Eyolhg8/hcLBmzRpatWrFunXrWL9+PStXrqRZs2auLk2qAF9fX6ZOnUpqair16tWjbdu2TJw4kdOnT7u6NBH5jQwZfJs2beKOO+7g5ZdfZvny5axfv5527dq5uiypgurVq8eCBQtISkqisLCQ0NBQXnjhBc6dO+fq0kTkBlWbuzpP59uIScgi5WQeeVY7/hYzoYH+DG4fRIDfpd9e/t133xEUFESDBg0A2Lt3L5MnT+bQoUPMmzdPz2/JdTty5AgzZ85kw4YNREVFMXbsWCwWC1B6Y5S3tzd16tS57PE30o9FpHxV+eBLPJbLkrhDxKeVLjRsszvK9lnMHjiBniENGNejOW2b/PKFc+zYMUJCQujTpw9vvPEG06ZNY+PGjUyfPp2nnnqKGjVqVHZTxI3s37+f6dOns2fPHmbOnMljjz3G7bffjpeXF7t27frVAuU32o9FpPxV6eD7aGcG82JTsNpLuFKVJhNYzJ5E9wtleKdbcTgcdO7cmYSEBEwmEzVr1uTZZ5/lueeeo1atWpXXAHF7O3fuLJsLPHPmDJ6enjz33HPMnj277DM32o9FpGJU2eAr/bJIprDYcfUP/8zHy4Pofi3J2PgRs2fPpri4GID27duze/fuiipVDM5utxMUFER2djZQ+n7AzZs307Vr19/UjxV+IhXDZRNcZ8+e5aGHHsLX15emTZvyySeflO1LPJbLvNiUS35ZFByMJ2vpk/xvXjsdJaQtGkrUax8wZ8kKSkpKypafSkhIIC4urkLbI8aUkZFB586dyc7OxmQy4enpSVFREZGRkXyXefay/dh+7jRHF/an+McTv9p3dPVs/vzsc+zLymXv3r10796d2rVrExQUxJw5cyqjWSJuzWXBN378eGrUqEF2djYff/wxY8eO5cCBAwAsiTuE1V5yyeNqBnfGYSvAlrn/ou2FRxIAE17NbqfnmJn4+Pjw8ssvs3//fv74xz8yefLkim6SGNC4ceMICQlh/fr1fPLJJwQFBfHEE0+wYMEClsUfuWw/Nteqj+XWthQkbb5oe0nhOQqP7MYS1pulcYd49NFHueuuuzh79izx8fEsXbqUL774ojKaJuK2XBJ8BQUFrF27ljlz5uDn50e3bt3o378/K1eu5HS+jfi0nMvOhZjMNfAN7Ub+/3xhFCRtxrdVDzB5snf3f2gV1prnnnuO8PBwXnnlFRITE0lJSamE1omRfP/99zz66KP07duXRx55hMGDB+Pl5cXw0WOv2I8B/MIjKTiw5aJt55O/wSvgFrwa3MqW1BwyMjIYNmwYnp6e3HbbbXTr1q3sF0QRuTEuCb60tDTMZjPBwcFl29q2bcuBAweIScii+KdTZL72e+w/nbrk8b6tIzmfug1HsQ0Ah7WAwkP/wa91JABFOUfxCfy/Xz7v68ttt92mLwwpd8888wyrV6/m/PnzHD9+nH/+85/ce++9xCSUrvTyw18nUHAg7pLH+gR3pqQwD+uxX/plftLmsn5sAnoMfJwPP/yQ4uJiUlNT2bFjB3fffXdFN0vErbkk+PLz8/H3979oW+3atTl37hwpJ/Nw+NbnlmfXYK7d8JLHW4Ja4elbh8K0HQAUpPwbc92bqNGoNOyKbYWc5+LHFS6cX6Q83XXXXRw4cAB/f3+CgoLo0KEDAwYMIOVkHja7g5tGLcY3rOclj/Xw8sY3pFvZ5c7is8cpOnm49MoFYLU78A++k5iYGHx8fAgNDWXUqFF07Nixspon4pZcEnx+fn7k5eVdtC0vL49atWqRZ722t2L7hvcuu9xZkLQFv/DeZfs8vCzk518cchfOL1JeHA4H9957LwMHDqSgoIDTp0/z448/EhUVde39uHVvzqdsxWkvoiBpCz7NIvD0LX2Or6TwHJ++OIEZM2ZgtVo5duwYX3/9NUuXLq3IZom4PZcEX3BwMHa7/aKV7xMTEwkLC8Pfcm2v//EL6431aCK248nYfkjFN6xX2T6vBk35KetQ2Z8LCgo4fPgwYWFh5dcIMbyzZ8+SmZnJhAkT8Pb2JiAggCeeeILY2Nhr7sfeQWF4+NTifPpOCg5swffny5wA9tyTeHh68Nhjj2E2mwkKCuKRRx4hNja2opokYgguCT5fX18GDhzIjBkzKCgoYNu2bXz++eeMGDGC0EB/vM1XL8tcpxHeQa3I+fxlfJq1w9Ovbtm+ui278uPxw6xduxar1crs2bNp06YNoaGhFdksMZj69evTrFkzli1bht1uJzc3lxUrVpT2tWvsxyaTCd/w3vy45QMctgJqNr+zbJ/Zvz724mL+8Ic/cPToUU6ePMmaNWto06ZNRTZLxO257HGGpUuXUlhYSMOGDRk6dCjLli0jLCyMQe2DSm9uWTTosje3XOAXHklJ3il8/+syJ4Cnb20+XrWG6Oho6taty7fffsvq1asrsjliUP/4xz9Yv349DRo0oHnz5nh5efHaa68xqH0QAD+8O478/7lz83/5hvemJC+Hmi27YzJ7lW338a/HH8ZN4O9//zvNmjUjKCiIvLw82rZtS25uboW2S8SdVcmVW8as3M2G5Owr3gp+OSYT9G3ViLeHdyj/wkSuQ3n2Y4fDQWJiIhs3bmTDhg3s2LGDsLAw+vTpw913302nTp3w9tYi1yLXokoGX+KxXB55ZyeFxZd++PdKfLw8WTOmE22CtNCvuFZF9mOr1cr27dvLgjA1NZVu3bpx9913c/fdd9O6deuylYtE5GJVMvjgt63VqTUOpaqorH589uxZtmzZUhaE586dKwvBu+++myZNmtxA9SLuqcoGH2hVe3EPrujH33//PZs2bWLjxo1s2rSJevXqlV0W7dmz5xXfGSji7qp08AHsy8pladwhtqTmYKL0od4LLrzHrFdIA8b1bK7Lm1JlubIfX2p+MDw8vGw02LlzZ72fUgylygffBWfybcTsyeKVd1fRtkNnmjQKILRxLQbdrjdXS/VxoR9v3J1M8uGj9Lmra6X3Y80PitFVm+C7oF27dnzwwQe0a9fO1aWI3LB169bx9ttvs27dOleXovlBMZxrW15CRNxWvXr1ePjhh3n44YeBX+YHv/76ayZNmkRAQEBZCGp+UNyByx5gF5GqqVmzZowePZrVq1eTnZ3NqlWraNq0KUuXLqVJkyZ07tyZ6dOnEx8fT1FRkavLFbluGvGJyGV5eHgQERFBREQEzz///EXzgxMnTtT8oFRLGvGJyDWzWCz07t2b+fPns2vXLjIyMhg1ahTp6ekMHDiQwMBAhg0bxvvvv8+xY8dcXa7IJWnEJyI37HrmB3v16kXt2rVdXLGIRnwiUo6uND8YFBRUNj/4zTffaH5QXEYjPhGpEFeaH3zuuecumh/s06cP4eHhmh+USqERn4hUiivNDz700EM0btxY84NSKTTiExGX0PyguIpGfCJSJWh+UCqLRnwiUuVc6/zghTdOaH5QrodGfCJS5V1ufjAtLe1X84NZWVmuLleqOI34RKTaudT84MaNG381P9inTx969uyp+UG5iEZ8IlLtNWvWjKeeeupX84NLliwpmx+cMWOG5gcF0IhPRNyM5gflajTiExG3dq3zgx988IHmBw1CIz4RMZTLPT+4fv16nn/+ec0PGoBGfCJiaJd7flDzg+5LIz4RkZ9pftAYNOITEbkMzQ+6J434RESukeYH3YNGfCIiN0jzg9VTtRnxJScnc/ToUfLy8ti2bRtnz56lR48eeHp6uro0kWtms9mIj48nISGBU6dOsX79ekJCQmjWrJmrS5PfSPOD1YfJ6XQ6XV3EtejXrx+bNm3CbrdjsViw2WxkZ2cTEBDg6tJErtnBgwcJCwujZs2aFBUVYTKZGDVqFMuWLXN1aVLBzp49y5YtW9i4cSMbNmwgPz+fyMjIsiAMCgpydYmGUW2Cb+vWrfTt25fz58/j6enJI488wkcffeTqskSuW/fu3dm6dStQevPE/v37ad68uYurksp2YX5w48aNbNq0SfODlajaBB9A586d2blzJzVq1CAlJUWXh6Ra2rlzJz179sRmszFkyBDWrFnj6pLExRwOB4mJiWWjwR07dhAeHl42GuzUqRM1atRwdZluo1oF39atW+nevTv33XcfsbGxri5H5IaFhYVx8OBB0tPTNdqTX/nv+cENGzZofrCcVavgA+jVqxevv/46bdu2dXUpIjfsq6++4t133+XTTz91dSlSDWh+sHxVm+A7nW8jJiGLlJN55Fnt+FvMhAb6M7h9EAF+3q4uT+SaqB9LeagK84PVuS9X+eBLPJbLkrhDxKflAGCzO8r2WcweOIGeIQ0Y16M5bZvUcVGVIlemfiwVpbLnB92hL1fp4PtoZwbzYlOw2ku4UpUmE1jMnkT3C2V4p1srrT6Ra6F+LJWpIucH3aUvV9ngK/0LTqaw2HH1D//Mx8uD6H4tq+RftBiT+rG42vXMDz799NPk5OSwYsWKX40S3akvu2zJssWLF9OhQwe8vb0ZOXLkRfsSj+UyLzblkn/BtuMpZC56GEdR4a/2HV4+gYkvvMS+rFzGjBlDSEgIHh4efPDBBxXUChEYPnw4jRs3xt/fn+DgYN59913gyv0YLt+XC4sdjB4QyZS5L3H69Gm6du1KQEAAderUoXPnzmzbtq3C2yTu48L6osuWLePQoUPs2LGDXr16sX79eiIiIggNDWXChAm89dZbLFu2jNWrV1O7dm0+/vjjsnOUx3fyl19+SXh4OH5+fnTp0oWDBw9WaLuvxGXBd9NNNzFt2jSefPLJX+1bEncIq73kksd53xyKZ636nE+5+Ie/KCeD4jOZ1AjpztK4Q7Rt25alS5dy++23V0j9IhdMmTKFjIwM8vLy+OKLL5g2bRoJCQlX7Mdw5b5sO53JiYDb8fPz47333iMnJ4cff/yRqKgoHnjgAex2e0U3S9zUpdYXDQoKYtKkSWX9qqioiBEjRrB582bgt38nv7h6M8OGDePtt98mNzeXBx54gP79+7usH7ss+AYOHMiAAQN+teTY6Xwb8Wk5V7x+7BceSX7S5ou2FSRtxuf/OuDh48+W1BweeXw0kZGRWCyWiihfpExYWBje3qV3sZlMJkwmE98dSLlqP4Yr9+UdPxRTYDeVXblwOp14enry448/cvbs2YpqjhjIhfVFf/e73+F0OjGbS5dvNpvNOJ1OhgwZUi7fyZs2buTOzl3p1q0bZrOZqKgojh8/Tnx8fEU277Kq3NsZYhJK32mV+drvsR47cMnP+Ib3wnYsCXte6V1FTqeDgoPx+LWOBMAExOzRu7Gk8owbN46aNWsSGhpK48aNyW/Qumzfjfbl/+7Hbdq0wWKx0L9/f0aPHk3Dhg0rvE1iLE6nk9DQUMaNG8f7779Ply5d6NatW7l9J5/46ZdLoU6nE6fTSVJSUsU26jKqXPClnMzDZndwy7NrsDQJu+RnzP4NsNzSmoKkLQBYMxJx2ovxua1j6Z/tDlJOnKu0mkWWLl3KuXPn+Pe//83AgQM5fNZadpv3jfbl/+7H+/btIy8vj08++YRu3bpVTqPEMEJCQrj55psZMWIEr7/+OvXr12fXrl0UFhaWy3ey+ZY2pO79lri4OIqKipg/fz5FRUWcP3++0tr436pc8OVZr+2ar2/rSPIPlA6tC5I249vyLkyev7xlKc9aXCH1iVyOp6cn3bp1Iysri13//Ns1H3elvvzf/dhisTB06FAWLFhAYmJi+RYvhubl5cVnn33GV199RWBgIIsWLWLIkCEEBQWVy3eyV0ATuo+eyYQJE2jcuDGnT5+mVatWLltxpsoFn7/l2l4RWDO4CyXnzmA9uo/zaTvw/XlI/ct5vCqiPJGrstvt2M78cM2fv1JfvlQ/Li4u5siRI+VSq8gFbdq0IT4+njNnzvD1119z5MgR7rjjjnL7Tm7b/V6SkpI4c+YML7zwAhkZGXTs2LEimnJVLgs+u92O1WqlpKSEkpISrFYrdrud0EB/vM1XL8ujhoWaIV05/dXrmGs3xLtxi7J9FrMHzet7Y7VacTqdFBcXY7VacTiu/fkTkWtx6tQpVq9eTX5+PiUlJXz99desWrWKTt17XFM/hsv3ZYvZgxpnD7F161aKioooLCxk4cKFZGdnc+edd1Zks8SA9u3bh9Vq5fz587zyyiucOHGCkSNHltt3sk/eUUpKSsjJyWHMmDH079+f0NDQimzS5Wt1yX8VmDt3Lj4+PixYsICPPvoIHx8f5s6dy6D2pUPfzEWDsB678sSnX3hvSvJO4Rve+6LtTuCTWX/Ax8eH7du3M2bMGHx8fPjmm28qqjliUCaTiWXLlhEUFETdunWZOHEir7/+OnOeHln2mRvty06ga7PajB8/noCAAG6++WZiY2P56quvuOmmmyqoRWJUK1eupHHjxjRs2JBNmzaxYcMGvL29y+07efN7C6lTpw4hISHUrVuXd955p6KaclVVcuWWMSt3syE5+6q3gl+KyQR9WzXi7eEdyr8wkeugfizuwt36cpWb4wMY37M5FrPnDR1rMXsyrqfebyaup34s7sLd+nKVDL62TeoQ3S8UH6/rK690XbhQ2gRVzRXBxVjUj8VduFtf9pw1a9YsVxdxKW2C6lDHx4sdR85ScpXxtckEPl6eVXIxVDE29WNxF+7Ul6vkHN9/25eVy9K4Q2xJzcFE6cPpF1x491OvkAaM69m8yv1WIXKB+rG4C3foy1U++C44k28jZk8WKSfOkWctxt/iRWjjWgy6veq/7Vfkggv9eOPuZJIPH6XPXV3Vj6Vaqs7fydUm+ETcybp163j77bdZt26dq0sRMZwqeXOLiIhIRVHwiYiIoSj4RETEUBR8IiJiKAo+ERExFAWfiIgYioJPREQMRcEnIiKGouATERFDUfCJiIihKPhERMRQFHwiImIoCj4RETEUBZ+IiBiKgk9ERAxFwTy6n5YAABh5SURBVCciIoai4BMREUNR8ImIiKEo+ERExFAUfCIiYigKPhERMRQFn4iIGIrJ6XQ6XV2EiFFkZmbyxz/+kR9++IGsrCzatWvH4MGD+cMf/uDq0kQMQyM+kUrk5+fH5s2bSUxM5MyZM3zzzTcUFha6uiwRQ1HwiVSievXq8fTTT+Pl5QWUBuEf//hHF1clYiwKPpFKFhUVhYeHBx4eHsyYMQOLxeLqkkQMRXN8Ii4waNAgvvjiC/Ly8hR8IpVMwSfiArm5uezZs4fevXu7uhQRw1HwiVSi0/k2YhKySDmZR57Vjr/FTGigP4PbBxHg5+3q8kQMQcEnUgkSj+WyJO4Q8Wk5ANjsjrJ9FrMHTqBnSAPG9WhO2yZ1XFSliDEo+EQq2Ec7M5gXm4LVXsKVftpMJrCYPYnuF8rwTrdWWn0iRmN2dQEi7qw09JIpLHZc9bNOJxQWlzAvNhlA4SdSQfQ4g8hv1LNnTywWC35+fvj5+RESEgKUXt6cF5ty2dArOBhP1tIn+d+LLudtxYyMbMdbH6wmIyMDk8lUdm4/Pz/mzJlT4W0ScWcKPpFysHjxYvLz88nPzyc1NRWAJXGHsNpLLntMzeDOOGwF2DL3X7S98EgCTkzsN91ati03N7fs/NOnT6+IJogYhoJPpAKczrcRn5Zz5Tk9cw18Q7uRn7T5ou0FSZvxbdWD+EM/8mOBrYIrFTEeBZ9IOZgyZQr169ena9euxMXFEZOQBYD9p1NkvvZ77D+duuRxvq0jOZ+6DUdxacA5rAUUHvoPfq0jMQGxSScBaNq0KUFBQTzxxBOcPn26Utok4q4UfCK/0cKFCzly5AjHjx9nzJgxPPDAA+zcewCb3YG5dkNueXYN5toNL3msJagVnr51KEzbAUBByr8x172JGo3+D6vdwQ9WL3bt2sXRo0dJSEjg3LlzDBs2rDKbJ+J29DiDSDm79957ya0fzskmva7p87nbVmHLSqbR72dz8qMoara4E/87BwIQGdqQvz7eseyzJ0+epHHjxuTl5VGrVq0KqV/E3WnEJ1LOTCYTFvO1/2j5hfXGejQR2/FkbD+k4hv2S2D6W7x+dW4Ah+Pqj0eIyKUp+ER+g9zcXL7++musVit2u52PP/6Yb775hl5334P3NYafuU4jvINakfP5y/g0a4enX12gdEUX7x8Pk5qaisPh4MyZMzz99NP07NmT2rVrV2SzRNyagk/kNyguLmbatGk0aNCA+vXr89Zbb/HZZ58RXteBzWYrvbll0aDL3txygV94JCV5p/AN/2XR6qLiYuoVHufee++lVq1ahIeH4+3tzapVqyq6WSJuTXN8IuUoISGByZMnc/ToUYJHvcKBnzyv+EjD5ZiAm5w5pLzzHE8++SSTJ08mICCg3OsVMSKN+ETKwZEjR3j00Uf53e9+x8CBAzlw4ADzHr0Li9nzhs5n8fJk2YQB7N+/n/z8fEJCQpgzZw7nzp0r58pFjEfBJ/IbnDp1iqeffpqOHTvSsmVL0tPTGTt2LF5eXrRtUofofqH4eF3fj5mPlwfR/UJpE1SHm266iWXLlrFz505SUlJo0aIFr7/+OlartYJaJOL+FHwiNyA/P585c+bQsmVLAJKTk5k+fTp+fn4XfW54p1uJ7tcSHy9Pfr4h87JMJvDx8iS6X8tfLVDdvHlzPv74Y/71r3+xefNmQkJCeO+997Db7eXZLBFD0ByfyHUoLi7mr3/9K7Nnz6ZHjx7MnTuX22677arH7cvKZWncIbak5mACrJd4H1+vkAaM69mcNkFXfx/f9u3bmTp1KtnZ2cyZM4eBAwfi4aHfY0WuhYJP5Bo4nU7Wrl3L1KlTueWWW1i4cCHt27e/7vOcybcRsyeLlBPnyLMW42/xIrRxLQbdfv1vYHc6nfzrX/9i6tSpAMyfP5977rmn7Fk/Ebk0BZ/IVcTHxzNp0iSKi4tZuHAhffr0cXVJF3E4HKxdu5bp06cTGBjIiy++SOfOnV1dlkiVpeATuYx9+/YxZcoUkpOTmTt3Lo888kiVvpxot9v58MMPmTVrFu3atWPu3Lm0adPG1WWJVDlV96dYxEUyMzMZOXIkffr0oW/fviQnJ/Poo49W6dADMJvNPPnkk6SlpdG7d2/uuecehg0bxuHDh11dmkiVUrV/kkUq0ZkzZ5g4cSIRERE0adKE9PR0nn76aby9r2/uzdUsFgvPPPMM6enphISEcOeddzJ27Fh++OEHV5cmUiUo+MTwCgsLWbhwIaGhoRQUFJCUlMScOXPw9/d3dWm/Sa1atZgxYwYpKSn4+voSHh5OVFQUZ8+edXVpIi6l4BPDstvt/PWvf6VFixbs2rWLrVu3smzZMho3buzq0spV/fr1eeWVV9i3bx+5ubkEBwczd+5c8vPzXV2aiEso+MRwnE4nX3zxBW3btuXDDz8kJiaGmJgYQkJCXF1ahQoKCmL58uXs2LGDAwcO0KJFC958801sNpurSxOpVLqrUwxl+/btREVFkZuby4IFC+jXr59hn3vbu3cv0dHRHDhwgFmzZjFixAg8PW9sbVGR6kTBJ4aQnJzM1KlTSUhIYM6cOQwfPlxf8j/bunUrU6dO5fTp02WrwBj1lwExBgWfuLXjx48za9YsPvvsM6KiopgwYQIWi8XVZVU5TqeT9evXM3XqVMxmM/Pnz+fuu+9WAIpb0hyfuKWffvqJqVOn0qZNGwICAkhLS2PixIkKvcswmUzcd999JCQk8PzzzzNhwgR69+7Nzp07XV2aSLlT8IlbsdlsvPrqq7Ro0YKTJ0+yd+9eFixYQN26dV1dWrXg4eHBkCFDOHDgAMOGDWPw4ME8+OCDJCUlubo0kXKj4BO3UFJSwsqVKwkJCSE+Pp4tW7bw3nvv0aRJE1eXVi2ZzWZGjx5Neno6PXr0IDIykhEjRnDkyBFXlybymyn4pFq7MDd1++23s2zZMlauXMnnn39OWFiYq0tzCxaLhb/85S+kp6fTvHlzOnbsyPjx4zlx4oSrSxO5YQo+qbZ27dpFZGQkzz77LC+88ALbtm2je/furi7LLfn7+zNz5kxSU1OxWCyEhYUxefJkfvzxR1eXJnLdFHxS7aSnpzNkyBAGDBjA0KFD2b9/PwMGDNAdiJWgfv36LFq0iMTERM6cOUNwcDDz58+noKDA1aWJXDMFn1Qb2dnZjB8/ns6dOxMREUF6ejpPPfUUZrPZ1aUZTpMmTXjnnXfYtm0b+/bto3nz5ixevFirwEi1oOCTKu/cuXPMnDmTVq1a4e3tTWpqKlOmTKFmzZquLs3wgoODWb16NbGxscTGxhIaGsqKFSsoKSlxdWkil6XgkyqrqKiIxYsX06JFC77//nsSEhJ49dVXCQgIcHVp8j8iIiKIjY3lww8/5J133qFNmzZ8+umnaH0MqYq0cotUOQ6Hg7/97W9ER0cTHBzMggULaNu2ravLkmvkdDqJjY0lOjoab29v5s+fT2RkpKvLEimj4JMqZdOmTURFRWEymVi4cCG9e/d2dUlygy78AjN9+nSaNm3K/PnzueOOO1xdloiCT6qG7777jsmTJ3P48GHmz5/P4MGDdZemmyguLub9999n9uzZdOzYkblz5+o5S3EpzfGJS33//fcMHz6cfv368eCDD5KcnMyQIUMUem7Ey8uLMWPGkJ6eTteuXenVqxePP/44GRkZri5NDErBJy5x+vRpnnnmGTp06ECLFi1IT09n3LhxeHl5ubo0qSA+Pj5MnDiR9PR0mjZtSvv27fnTn/7EyZMnXV2aGIyCTypVQUEB8+bNIzQ0lJKSEg4ePMjMmTPx8/NzdWlSSWrXrs3s2bNJTk7GbDYTFhbG1KlTyc3NdXVpYhAKPqkUdrud5cuXExwczP79+9m5cydvvfUWjRo1cnVp4iINGzbktdde47vvvuPUqVO0aNGCBQsWaBUYqXAKPqlQTqeTf/zjH4SFhfG3v/2Nzz//nNWrV9O8eXNXlyZVxC233MK7777L1q1b2bNnDy1atGDJkiUUFRW5ujRxU7qrUyrMN998w6RJk7DZbCxcuJA+ffrophW5qoSEBKKjo0lLS+OFF17g0UcfxdPT09VliRtR8MlFTufbiEnIIuVkHnlWO/4WM6GB/gxuH0SAn/clj8nIyGDz5s08+eSTACQlJTFlyhSSkpKYO3cuQ4cOxcNDFxfk+sTHxzNlyhTy8vKYN28e/fv3x2QyUVBQwIYNGxgwYMAVj7+RvizGoOATABKP5bIk7hDxaTkA2OyOsn0WswdOoGdIA8b1aE7bJnXK9tntdiIiIkhOTuZf//oXK1euJDY2lilTpjB27Fi8vfUFIzfO6XTy1VdfER0djY+PD/Pnz2fLli3MnTuXL774ggceeOBXx9xoXxbjUPAJH+3MYF5sClZ7CVfqDSYTWMyeRPcLZXinWwGYNm0ar776KlarFU9PT6Kionj++eepXbt25RQvhuBwOFi9ejXR0dFkZmbicDjw9/cnJSWFxo0bl33ut/RlMQ4Fn8GVflEkU1jsuPqHf+bj5UF0v5Y0sR2lT58+FBcXA+Dt7c2WLVvo3LlzRZUrBjd+/Hj+3//7f9jtdkwmE+3atWP37t14eHj8pr6s8DMWTbwYSHp6OhaLheHDhwOll4TmxaZc9oui4GA8WUuf/NUK++dtxYyMbMdDj40pCz2z2UxJSQldunRh48aNFdsQMawVK1Zgt9uB0sug3333HfPmzbtiX7YdTyFz0cM4igp/te/w8glMfOEl9mXlUlJSwrRp07jpppuoVasWERERerbQTSn4DGT8+PF07Nix7M9L4g5htV/+vWk1gzvjsBVgy9x/0fbCIwk4MTFw1gcUFhZSUlJCSkoKoaGhF112EilPGzZsoF69eqxfv56srCy+/fZbNm7cyPPPP3/Fvux9cyietepzPmXbRduLcjIoPpNJjZDuLI07xMyZM9m+fTs7duwgLy+PlStXYrFYKqNpUsn06mqDWL16NXXq1KFLly4cOnSI0/k24tNyrjwPYq6Bb2g38pM2Y2napmx7QdJmfFv14N9Hcimwm7BYPBg/fjwLFy5k3LhxldAaMaKZM2cyc+ZM+vbtC8DNN98McE192S88kvykzfi1ubtsW0HSZnz+rwMePv5s3HuEk2+/TmJiIk2bNgUgPDy84hojLqURnwHk5eUxY8YMXn311bJtMQlZANh/OkXma7/H/tOpSx7r2zqS86nbcBTbAHBYCyg89B/8WkdiAmL2ZPH3v/8db29v+vXrV+FtEWMqKSlh9+7d5OTk0Lx5c4KCgpgwYQKFhYVlfTnztd9jPXbgksf7hvfCdiwJe17pnZ5Op4OCg/H4tS59T2DRqQwcJg9iYmIIDAwkODiYJUuWVE7jpNJpxGcA06dPZ9SoUQQFBZVtSzmZh83uwFy7Ibc8u+ayx1qCWuHpW4fCtB34hvWkIOXfmOveRI1G/4fV7mDfkZP8a95UNmzYUBlNEYPKzs6muLiYmJgY/v3vf+Pl5cWDDz7I3LlzKWgzCJvdccV+bPZvgOWW1hQkbaF2lyFYMxJx2ovxua300n9hbg6F+edIS0vj+++/Jz09ncjISIKDg+nTp09lNVMqiUZ8bm7v3r1s3LiRZ5999qLteVb7NZ/DN7w3+UmbAShI2oJf+C8vh41fvZQRI0Zw6623lku9Ipfi4+MDwJ/+9CcaN25M/fr1+ctf/kJsbOw192Xf1pHkH7jQjzfj2/IuTJ6lv/ubzDUAmDFjBj4+PrRp04ZHHnmE2NjYCmiNuJqCz83FxcWRkZHBLbfcQmBgIK+88gpr165l3azHrvkcfmG9sR5NxHY8GdsPqfiG9Srbl52ymzfffJPAwEACAwM5duwYQ4YMYeHChRXRHDGounXrEhQUdNGSdxf+3d9ybReuagZ3oeTcGaxH93E+bQe+P1/mBPBq2Oyic/7vv4t70XN8bu78+fPk5eWV/fmVV14hIyODO0dM4t3dZy5a1eJKTn4yBXtuNjUa3ELDwbOA0lUwnrqjAcM6/nIJtWPHjrz66qvcd999etWQlKsZM2bwz3/+k6+++govLy/69+9Pz549ufnukby2Me2a+vLpr17HenQfHjUs3DR6adl2i9mDki9m0rtTBG+++SZHjhyhR48erFq1isjIyCucUaojjfjcXM2aNctGY4GBgfj5+WGxWHgisi3w880tiwZd9uaWC/zCIynJO4Xvf13mdAIje7W+6Pyenp7UrVtXoSflbvr06XTs2JHg4GBatmxJREQE0dHRDGpf+otX5qJBWI8lXfEcfuG9f9WPobQvf/r31Rw9epSAgADuv/9+5syZo9BzUxrxGdiYlbvZkJx9xdvAL8dkgr6tGvH28A7lX5jIdVJfluuhEZ+Bje/ZHIv5xl73YjF7Mq6n3qknVYP6slwPBZ+BtW1Sh+h+ofh4XV83KF3fMJQ2QVrZXqoG9WW5HnqOz+AuLM6rFe2lulNflmulOT4BYF9WLkvjDrElNQcTYL3EO8x6hTRgXM/m+u1YqjT1ZbkaBZ9c5Ey+jZg9WaScOEeetRh/ixehjWsx6Ha9tVqqlwt9efabf6VX33408PdTXxZAwScibq5hw4YkJSXRsGFDV5ciVYRubhEREUNR8ImIiKEo+ERExFAUfCIiYigKPhERMRQFn4iIGIqCT0REDEXBJyIihqLgExERQ1HwiYiIoSj4RETEUBR8IiJiKAo+ERExFAWfiIgYioJPREQMRcEnIiKGouATERFDUfCJiIihKPhERMRQFHwiImIoCj4RETEUBZ+IiBiK2dUFiIhUhFWrVpGRkcH58+d54403CAwMZMKECZhMJleXJi5mcjqdTlcXISJS3rp27cqOHTtwOp2YTCbq1atHdnY2np6eri5NXEyXOkXELb344ov4+PgA4OPjwwsvvKDQE0AjPhFxY3feeSf/+c9/qFu3LidOnMDb29vVJUkVoBGfiLitl19+GYBJkyYp9KSMRnwi4tbGjx/Pyy+/TM2aNV1dilQRCj4RcUun823EJGSRcjKPPKsdf4uZ0EB/BrcPIsBPoz8jU/CJiFtJPJbLkrhDxKflAGCzO8r2WcweOIGeIQ0Y16M5bZvUcVGV4koKPhFxGx/tzGBebApWewlX+mYzmcBi9iS6XyjDO91aafVJ1aAH2EXELZSGXjKFxY6rftbphMLiEubFJgMo/AxGd3WKSLXg5+d30T+enp786U9/Akovb86LTblk6NmOp5C56GEcRYW/2nd4+QQmvvASH6yN/dX5TSYTa9eurfB2SeVT8IlItZCfn1/2z8mTJ/Hx8WHw4MEALIk7hNVecsnjvG8OxbNWfc6nbLtoe1FOBsVnMqkR0p2dhQ0vOv+6devw8/Pj3nvvrfB2SeVT8IlItbN27VoaNmxI9+7dOZ1vIz4t54pzen7hkeQnbb5oW0HSZnz+rwMePv5sSc3hTL6tbN+KFSsYNGgQvr6+FdUEcSEFn4hUOytWrOCxxx7DZDIRk5AFQOZrv8d67MAlP+8b3gvbsSTseaV3ejqdDgoOxuPXOhIAExCzp/Q8BQUFxMTE8Pjjj1d8Q8QlFHwiUq0cPXqU+Pj4smBKOZmHze7glmfXYGkSdsljzP4NsNzSmoKkLQBYMxJx2ovxua1j6Z/tDlJOnAPgH//4B/Xr16dHjx6V0BpxBQWfiFQrK1eupFu3bjRr1gyAPKv9mo7zbR1J/oHSy50FSZvxbXkXJs9fbmzPsxYDF48mxT0p+ESkWvnwww8vugzpb7m2p7JqBneh5NwZrEf3cT5tB74/X+b85TxeHDt2jLi4OB577LFyrVmqFgWfiFQb27dv5/jx42V3cwKEBvrjbb76V5lHDQs1Q7py+qvXMdduiHfjFmX7LGYPQhvXYuXKlXTp0oXbbrutQuqXqkHBJyLVxooVKxg4cCC1atUq2zaofRAAmYsGYT2WdMXj/cJ7U5J3Ct/w3hdtdwKDbg/61WhS3JOWLBORam/Myt1sSM6+4iMNl2MyQd9WjXh7eIfyL0yqJI34RKTaG9+zORbzjb1d3WL2ZFzP5uVckVRlCj4RqfbaNqlDdL9QfLyu7yvNx8uD6H6htAnSWxqMRItUi4hbuLDQtN7OIFejOT4RcSv7snJZGneILak5mCh9OP2CC+/j6xXSgHE9m2ukZ1AKPhFxS2fybcTsySLlxDnyrMX4W7wIbVyLQbfrDexGp+ATERFD0c0tIiJiKAo+ERExFAWfiIgYioJPREQMRcEnIiKGouATERFDUfCJiIihKPhERMRQFHwiImIoCj4RETEUBZ+IiBiKgk9ERAxFwSciIoai4BMREUNR8ImIiKEo+ERExFAUfCIiYigKPhERMRQFn4iIGIqCT0REDEXBJyIihvL/AT8V2S28tdPeAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "BST.plot()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On voit ici que si on insert les clés dans un ordre \"aléatoire\" (ie. un ordre qui a peu de chance de donner un cas trop dégénéré), l'arbre binaire ne sera *pas* réduit à une chaîne et il aura une hauteur bien plus faible que sa taille."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ensemble avec un Arbre Binaire de Recherche\n",
    "\n",
    "C'est très simple, on va stocker les valeurs de l'ensemble dans les clés de l'ABR et on utilise des valeurs vides.\n",
    "\n",
    "L'objectif est d'avoir une complexité en $\\mathcal{O}(\\log(n))$ pour l'ajout, l'appartenance et le retrait de valeurs, si les valeurs ajoutées sont insérées dans un ordre aléatoire.\n",
    "Comme pour la table de hachage, la complexité au pire des cas restera linéaire en $\\Omega(n)$ (si on construit un ABR réduit à une chaîne linéaire, comme l'exemple plus haut)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SetWithBinarySearchTree(BinarySearchTree, SetWithNonPrimOperations):\n",
    "    \"\"\" A set storing its values in a Binary Search Tree.\"\"\"\n",
    "    \n",
    "    def values(self):  # hack: we only use keys as values\n",
    "        return self.keys()\n",
    "\n",
    "    def add(self, value):\n",
    "        \"\"\" Add value in the set if it is not present.\"\"\"\n",
    "        key, value = value, None\n",
    "        return self.insert(key, value=value)\n",
    "\n",
    "    def pop(self, value):\n",
    "        \"\"\" Remove value in the set if it is present.\"\"\"\n",
    "        return self.delete(value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et pour la dernière structure implémentée ici, on teste :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{}\n",
      "{0}\n",
      "{0, 1}\n",
      "{0, 1, 2}\n",
      "{0, 1, 2, 3}\n",
      "{0, 1, 2, 3, 4}\n",
      "{0, 1, 2, 3, 4, 5}\n",
      "{0, 1, 2, 3, 4, 5, 6}\n",
      "{0, 1, 2, 3, 4, 5, 6, 7}\n",
      "{0, 1, 2, 3, 4, 5, 6, 7, 8}\n",
      "{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}\n",
      "S1 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}\n",
      "{}\n",
      "{5}\n",
      "{5, 6}\n",
      "{5, 6, 7}\n",
      "{5, 6, 7, 8}\n",
      "{5, 6, 7, 8, 9}\n",
      "S2 = {5, 6, 7, 8, 9}\n",
      "{}\n",
      "{20}\n",
      "{20, 21}\n",
      "{20, 21, 22}\n",
      "{20, 21, 22, 23}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "{20, 21, 22, 23, 24}\n",
      "S3 = {20, 21, 22, 23, 24}\n",
      "S1 union S2 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}  = S2 union S1 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}\n",
      "S1 union S3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20, 21, 22, 23, 24}\n",
      "S2 union S3 = {5, 6, 7, 8, 9, 20, 21, 22, 23, 24}\n",
      "S1 inter S2 = {5, 6, 7, 8, 9}  != S2 inter S1 = {5, 6, 7, 8, 9}\n",
      "S1 inter S3 = {}  != S3 inter S1 = {}\n",
      "S2 inter S3 = {}  != S3 inter S2 = {}\n",
      "S1 diff S2 = {0, 1, 2, 3, 4}  != S2 diff S1 = {}\n",
      "S1 diff S3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}  != S3 diff S1 = {20, 21, 22, 23, 24}\n",
      "S2 diff S3 = {5, 6, 7, 8, 9}  != S3 diff S2 = {20, 21, 22, 23, 24}\n",
      "S1 diff sym S2 = {0, 1, 2, 3, 4}  != S2 diff sym S1 = {0, 1, 2, 3, 4}\n",
      "S1 diff sym S3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20, 21, 22, 23, 24}  != S3 diff sym S1 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20, 21, 22, 23, 24}\n",
      "S2 diff sym S3 = {5, 6, 7, 8, 9, 20, 21, 22, 23, 24}  != S3 diff sym S2 = {5, 6, 7, 8, 9, 20, 21, 22, 23, 24}\n"
     ]
    }
   ],
   "source": [
    "un_petit_test_avec_une_structure_densemble(SetWithBinarySearchTree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et maintenant quelques tests :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "101 µs ± 2.49 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n",
      "117 µs ± 5.99 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n",
      "9.9 ms ± 692 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n",
      "1.54 ms ± 55.2 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit random_add_remove_test(SetWithBinarySearchTree, size=10, max_value=10, min_value=0)\n",
    "%timeit random_add_remove_test(SetWithBinarySearchTree, size=10, max_value=1000, min_value=0)\n",
    "%timeit random_add_remove_test(SetWithBinarySearchTree, size=1000, max_value=10, min_value=0)\n",
    "%timeit random_add_remove_test(SetWithBinarySearchTree, size=100, max_value=100, min_value=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.93 ms ± 211 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n",
      "27.1 ms ± 2.24 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n",
      "379 ms ± 44.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
      "6.02 s ± 603 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%timeit random_add_remove_test(SetWithBinarySearchTree, size=100, max_value=1000_000, min_value=-1000_000)\n",
    "%timeit random_add_remove_test(SetWithBinarySearchTree, size=1000, max_value=1000_000, min_value=-1000_000)\n",
    "%timeit random_add_remove_test(SetWithBinarySearchTree, size=10000, max_value=1000_000, min_value=-1000_000)\n",
    "%timeit random_add_remove_test(SetWithBinarySearchTree, size=100000, max_value=1000_000, min_value=-1000_000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Comparaison des différentes implémentations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "- Pour la classe <class '__main__.NativeSet'>\n",
      "2.78 ms ± 366 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n",
      "\n",
      "- Pour la classe <class '__main__.SetWithList'>\n",
      "82.2 ms ± 7.48 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n",
      "\n",
      "- Pour la classe <class '__main__.SetWithInt'>\n",
      "29.1 s ± 918 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
      "\n",
      "- Pour la classe <class '__main__.SetWithHashTable'>\n",
      "3.98 ms ± 91.5 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n",
      "\n",
      "- Pour la classe <class '__main__.SetWithBinarySearchTree'>\n",
      "28.7 ms ± 5.31 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "print(\"\\n- Pour la classe\", NativeSet)\n",
    "%timeit random_add_remove_test(NativeSet, size=1000, max_value=1000_000, min_value=0)\n",
    "print(\"\\n- Pour la classe\", SetWithList)\n",
    "%timeit random_add_remove_test(SetWithList, size=1000, max_value=1000_000, min_value=0)\n",
    "print(\"\\n- Pour la classe\", SetWithInt)\n",
    "%timeit random_add_remove_test(SetWithInt, size=1000, max_value=1000_000, min_value=0)\n",
    "print(\"\\n- Pour la classe\", SetWithHashTable)\n",
    "%timeit random_add_remove_test(SetWithHashTable, size=1000, max_value=1000_000, min_value=0)\n",
    "print(\"\\n- Pour la classe\", SetWithBinarySearchTree)\n",
    "%timeit random_add_remove_test(SetWithBinarySearchTree, size=1000, max_value=1000_000, min_value=0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "- Pour la classe <class '__main__.NativeSet'>\n",
      "22.4 ms ± 1.07 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n",
      "\n",
      "- Pour la classe <class '__main__.SetWithList'>\n",
      "6.75 s ± 109 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
      "\n",
      "- Pour la classe <class '__main__.SetWithHashTable'>\n",
      "48.5 ms ± 6.88 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n",
      "\n",
      "- Pour la classe <class '__main__.SetWithBinarySearchTree'>\n",
      "347 ms ± 16.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "print(\"\\n- Pour la classe\", NativeSet)\n",
    "%timeit random_add_remove_test(NativeSet, size=10_000, max_value=1000_000, min_value=0)\n",
    "print(\"\\n- Pour la classe\", SetWithList)\n",
    "%timeit random_add_remove_test(SetWithList, size=10_000, max_value=1000_000, min_value=0)\n",
    "print(\"\\n- Pour la classe\", SetWithHashTable)\n",
    "%timeit random_add_remove_test(SetWithHashTable, size=10_000, max_value=1000_000, min_value=0)\n",
    "print(\"\\n- Pour la classe\", SetWithBinarySearchTree)\n",
    "%timeit random_add_remove_test(SetWithBinarySearchTree, size=10_000, max_value=1000_000, min_value=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "- Pour la classe <class '__main__.NativeSet'>\n",
      "45.8 ms ± 1.66 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n",
      "\n",
      "- Pour la classe <class '__main__.SetWithList'>\n",
      "27.3 s ± 749 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
      "\n",
      "- Pour la classe <class '__main__.SetWithHashTable'>\n",
      "104 ms ± 3.27 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n",
      "\n",
      "- Pour la classe <class '__main__.SetWithBinarySearchTree'>\n",
      "779 ms ± 36.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "print(\"\\n- Pour la classe\", NativeSet)\n",
    "%timeit random_add_remove_test(NativeSet, size=20_000, max_value=1000_000, min_value=0)\n",
    "print(\"\\n- Pour la classe\", SetWithList)\n",
    "%timeit random_add_remove_test(SetWithList, size=20_000, max_value=1000_000, min_value=0)\n",
    "print(\"\\n- Pour la classe\", SetWithHashTable)\n",
    "%timeit random_add_remove_test(SetWithHashTable, size=20_000, max_value=1000_000, min_value=0)\n",
    "print(\"\\n- Pour la classe\", SetWithBinarySearchTree)\n",
    "%timeit random_add_remove_test(SetWithBinarySearchTree, size=20_000, max_value=1000_000, min_value=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "- Pour la classe <class '__main__.NativeSet'>\n",
      "72.3 ms ± 15.1 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n",
      "\n",
      "- Pour la classe <class '__main__.SetWithList'>\n",
      "58.8 s ± 1.05 s per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
      "\n",
      "- Pour la classe <class '__main__.SetWithHashTable'>\n",
      "217 ms ± 59.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
      "\n",
      "- Pour la classe <class '__main__.SetWithBinarySearchTree'>\n",
      "2.18 s ± 394 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "print(\"\\n- Pour la classe\", NativeSet)\n",
    "%timeit random_add_remove_test(NativeSet, size=30_000, max_value=1000_000, min_value=0)\n",
    "print(\"\\n- Pour la classe\", SetWithList)\n",
    "%timeit random_add_remove_test(SetWithList, size=30_000, max_value=1000_000, min_value=0)\n",
    "print(\"\\n- Pour la classe\", SetWithHashTable)\n",
    "%timeit random_add_remove_test(SetWithHashTable, size=30_000, max_value=1000_000, min_value=0)\n",
    "print(\"\\n- Pour la classe\", SetWithBinarySearchTree)\n",
    "%timeit random_add_remove_test(SetWithBinarySearchTree, size=30_000, max_value=1000_000, min_value=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On voit que notre implémentation \"maison\" avec des tables de hachage est quasiment aussi efficace que l'implémentation native (en C !) de Python avec la classe `set` (qui utilise aussi une table de hachage, mais écrite en C !)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusion\n",
    "\n",
    "C'est bon pour aujourd'hui !"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  },
  "toc": {
   "colors": {
    "hover_highlight": "#DAA520",
    "running_highlight": "#FF0000",
    "selected_highlight": "#FFD700"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "356.867px",
    "width": "446.667px"
   },
   "navigate_menu": true,
   "number_sections": true,
   "sideBar": false,
   "threshold": 4,
   "toc_cell": true,
   "toc_position": {
    "height": "368.717px",
    "left": "1639.25px",
    "right": "20px",
    "top": "120px",
    "width": "251.25px"
   },
   "toc_section_display": "block",
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "position": {
    "height": "247.85px",
    "left": "829.5px",
    "right": "20px",
    "top": "307px",
    "width": "470.5px"
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  },
  "widgets": {
   "application/vnd.jupyter.widget-state+json": {
    "state": {
     "038a808e883447f29c7d1ac0b392a0d3": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "HBoxModel",
      "state": {
       "children": [
        "IPY_MODEL_4aaf5ca76a38467087582b42de1f6a1e",
        "IPY_MODEL_d614664cf99743889aa9b084525990d8"
       ],
       "layout": "IPY_MODEL_c02a451e0731469ea91cc39abbf14c48"
      }
     },
     "03fa6285b902493bbc52e73542eb6bd3": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "HTMLModel",
      "state": {
       "layout": "IPY_MODEL_14d24c174ecb4428af82666854e1ed83",
       "style": "IPY_MODEL_108a32808a0b43bda9b869081b96b80b",
       "value": "100% 12/12 [00:00&lt;00:00, 15.79it/s]"
      }
     },
     "040769e561d949e39b17361d682bb4a8": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "IntProgressModel",
      "state": {
       "bar_style": "success",
       "layout": "IPY_MODEL_61ab17aa9e4540939240cce1f8b4c32e",
       "max": 31,
       "style": "IPY_MODEL_7a2861a1cfdb45bdac48eb59c8b660bc",
       "value": 31
      }
     },
     "043afb832aa3492482fd973bb9d9bd7a": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "ProgressStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "0ae749625db249539e573bdfcd6fa23c": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "0c7b9244ca3d4cfca64cc68c62c676ef": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "HBoxModel",
      "state": {
       "children": [
        "IPY_MODEL_2ac95f4aedb04f5a9a5fa5361f2b5d49",
        "IPY_MODEL_fb9bace579f64af4b7ebb87789031257"
       ],
       "layout": "IPY_MODEL_2c2f47043664427b9fe40d9dab59f5be"
      }
     },
     "0f40caa17b6f45b19f9b67db6af682c3": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "IntProgressModel",
      "state": {
       "bar_style": "success",
       "layout": "IPY_MODEL_432a0f81101043fc812406cb9699cf55",
       "max": 12,
       "style": "IPY_MODEL_6d05a0207eb44be8a8194d7672bc3dc3",
       "value": 12
      }
     },
     "0f5c61300af74d9c87b2e169a8d59564": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "ProgressStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "108a32808a0b43bda9b869081b96b80b": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "DescriptionStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "1099c3fb624b4608ac4d8274ff57ff46": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "DescriptionStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "1135c69a55d04878a6716a594f46043e": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "1156627bae864085bbc3167c5b2a5cb3": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "DescriptionStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "14d24c174ecb4428af82666854e1ed83": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "17c69c17ec8344d2aeee5ae6dee93ce6": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "19ca5418edce46e0985b6f1868b3938d": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "HTMLModel",
      "state": {
       "layout": "IPY_MODEL_5cae48b866984d99a1e15f8822d57ed9",
       "style": "IPY_MODEL_a194ac9f28564a6a805b24a1a742838c",
       "value": "100% 7/7 [01:56&lt;00:00, 28.35s/it]"
      }
     },
     "1b4f155261eb469da0da9cbb96741044": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "HBoxModel",
      "state": {
       "children": [
        "IPY_MODEL_27199a9b964f4b8f94946e1a80cee138",
        "IPY_MODEL_7a4cd3a8b19d4fe58ed4d6d8f4ecae0e"
       ],
       "layout": "IPY_MODEL_db91f69593764d1fbc8593c6264df3a7"
      }
     },
     "211f4c9ceba64de0b46c4e32ce02a19a": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "ProgressStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "27199a9b964f4b8f94946e1a80cee138": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "IntProgressModel",
      "state": {
       "bar_style": "danger",
       "layout": "IPY_MODEL_5d84ecdf55794062bc15794cd6d48d87",
       "max": 12,
       "style": "IPY_MODEL_cc2ce2b0abab4704b0d580cdd7897c24",
       "value": 8
      }
     },
     "281631f2651241d896b1300b748f94cc": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "IntProgressModel",
      "state": {
       "bar_style": "success",
       "layout": "IPY_MODEL_9a939ec092234106b3bbf13266650f29",
       "max": 29,
       "style": "IPY_MODEL_aa66c2d953c84ef9902875ccbc9c994e",
       "value": 29
      }
     },
     "2ac95f4aedb04f5a9a5fa5361f2b5d49": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "IntProgressModel",
      "state": {
       "bar_style": "success",
       "layout": "IPY_MODEL_3705518094ba492db64884c7d9934ddf",
       "max": 31,
       "style": "IPY_MODEL_211f4c9ceba64de0b46c4e32ce02a19a",
       "value": 31
      }
     },
     "2b5f53a0083041e88ab8b35fbcb6adec": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "2bbce2307fd74e7fb6b48d80cf8b147a": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "HTMLModel",
      "state": {
       "layout": "IPY_MODEL_4c3a4ac37bb349259fa3840a25b52a9f",
       "style": "IPY_MODEL_bc47080108594d6398376ec90247fd7f",
       "value": "100% 29/29 [01:42&lt;00:00,  7.61s/it]"
      }
     },
     "2c2f47043664427b9fe40d9dab59f5be": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "2f4fa306f59d47a0a4c1fb41de63ccc6": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "HBoxModel",
      "state": {
       "children": [
        "IPY_MODEL_312e2c5fb4744ee9aca6e5cba42c05f8",
        "IPY_MODEL_03fa6285b902493bbc52e73542eb6bd3"
       ],
       "layout": "IPY_MODEL_616c61e0e1774e4dba06565d10df95e7"
      }
     },
     "30e0a8eb04c8484caeb06471a6b297b1": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "ProgressStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "312e2c5fb4744ee9aca6e5cba42c05f8": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "IntProgressModel",
      "state": {
       "bar_style": "success",
       "layout": "IPY_MODEL_f504214792524c2cbbb8997e99aa7714",
       "max": 12,
       "style": "IPY_MODEL_30e0a8eb04c8484caeb06471a6b297b1",
       "value": 12
      }
     },
     "3151f3436ad948f79765fcfb5cb64831": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "HBoxModel",
      "state": {
       "children": [
        "IPY_MODEL_ac9c8dcde2c14dbaa1173c31993a8425",
        "IPY_MODEL_7b16d9396fa8440d8b26d4309aac9dae"
       ],
       "layout": "IPY_MODEL_ac4b2cd6abad4fbe9129ad2b39f79d1c"
      }
     },
     "3191d73e3295402c9256a8e48a55fcde": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "HBoxModel",
      "state": {
       "children": [
        "IPY_MODEL_3cf71691ed3a45788e854120454ffb91",
        "IPY_MODEL_19ca5418edce46e0985b6f1868b3938d"
       ],
       "layout": "IPY_MODEL_1135c69a55d04878a6716a594f46043e"
      }
     },
     "3288f5a70453437e8314c7c34446ad83": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "3705518094ba492db64884c7d9934ddf": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "3cf71691ed3a45788e854120454ffb91": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "IntProgressModel",
      "state": {
       "bar_style": "success",
       "layout": "IPY_MODEL_b79ec55a28294c6bbf956dfc8e61c6d2",
       "max": 7,
       "style": "IPY_MODEL_f1361377c3184fb688b28bfe61451e86",
       "value": 7
      }
     },
     "432a0f81101043fc812406cb9699cf55": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "43cd3c30e9ed40589af0a84e4ad8165a": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "HTMLModel",
      "state": {
       "layout": "IPY_MODEL_3288f5a70453437e8314c7c34446ad83",
       "style": "IPY_MODEL_1156627bae864085bbc3167c5b2a5cb3",
       "value": "100% 31/31 [03:22&lt;00:00, 13.89s/it]"
      }
     },
     "488d7a0878974888921fe30c7a8ccce6": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "4aaf5ca76a38467087582b42de1f6a1e": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "IntProgressModel",
      "state": {
       "bar_style": "success",
       "layout": "IPY_MODEL_d86d424d7d2040bea285a821eb3ffaf6",
       "max": 54,
       "style": "IPY_MODEL_fc2e0e50b4024f2089000a027350ad62",
       "value": 54
      }
     },
     "4c3a4ac37bb349259fa3840a25b52a9f": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "4cd9f8c1d14a460592573b5d5f4d1e68": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "DescriptionStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "5724b7c6629e42db98f82141d3346d3f": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "HTMLModel",
      "state": {
       "layout": "IPY_MODEL_0ae749625db249539e573bdfcd6fa23c",
       "style": "IPY_MODEL_8ebb3008c95c416489b9db29d758008c",
       "value": "100% 29/29 [00:16&lt;00:00,  1.18s/it]"
      }
     },
     "5aba36f9297242688598109bc09046de": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "DescriptionStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "5cae48b866984d99a1e15f8822d57ed9": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "5d84ecdf55794062bc15794cd6d48d87": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "5f7e65435bd74f0eb6a1c412dfb425cc": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "DescriptionStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "616c61e0e1774e4dba06565d10df95e7": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "61ab17aa9e4540939240cce1f8b4c32e": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "63d4d742d31e49eb9f408d4b1d5205a8": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "HBoxModel",
      "state": {
       "children": [
        "IPY_MODEL_281631f2651241d896b1300b748f94cc",
        "IPY_MODEL_5724b7c6629e42db98f82141d3346d3f"
       ],
       "layout": "IPY_MODEL_6ec3aa7a23a64d20995bdf93351224f2"
      }
     },
     "646c3ac9c11944748551fbf8c83663b1": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "IntProgressModel",
      "state": {
       "bar_style": "success",
       "layout": "IPY_MODEL_488d7a0878974888921fe30c7a8ccce6",
       "max": 29,
       "style": "IPY_MODEL_ae8a07808b3e45859f3cd921f129124b",
       "value": 29
      }
     },
     "67b4ef9809f6494c8230ffa837fb5f2d": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "6d05a0207eb44be8a8194d7672bc3dc3": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "ProgressStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "6ec3aa7a23a64d20995bdf93351224f2": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "774238a7f4bc4bc39881b33452244ce3": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "7a2861a1cfdb45bdac48eb59c8b660bc": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "ProgressStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "7a4cd3a8b19d4fe58ed4d6d8f4ecae0e": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "HTMLModel",
      "state": {
       "layout": "IPY_MODEL_a6d7e8cc772f4b44ba43a23a407e7c12",
       "style": "IPY_MODEL_4cd9f8c1d14a460592573b5d5f4d1e68",
       "value": " 67% 8/12 [01:42&lt;01:34, 23.63s/it]"
      }
     },
     "7ab2be73db8c40cc896e0249bd3ea500": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "DescriptionStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "7b16d9396fa8440d8b26d4309aac9dae": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "HTMLModel",
      "state": {
       "layout": "IPY_MODEL_b7ee7f0454ef43edba44cdb7eff62621",
       "style": "IPY_MODEL_7ab2be73db8c40cc896e0249bd3ea500",
       "value": "100% 54/54 [07:16&lt;00:00, 17.43s/it]"
      }
     },
     "875b2a51333945eaa1b8cc990026d552": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "HBoxModel",
      "state": {
       "children": [
        "IPY_MODEL_040769e561d949e39b17361d682bb4a8",
        "IPY_MODEL_43cd3c30e9ed40589af0a84e4ad8165a"
       ],
       "layout": "IPY_MODEL_cb8738fbc3d54b8ea12d23b970356248"
      }
     },
     "89bf37d725d0422ead1e32f25f1ff7a8": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "HBoxModel",
      "state": {
       "children": [
        "IPY_MODEL_646c3ac9c11944748551fbf8c83663b1",
        "IPY_MODEL_2bbce2307fd74e7fb6b48d80cf8b147a"
       ],
       "layout": "IPY_MODEL_17c69c17ec8344d2aeee5ae6dee93ce6"
      }
     },
     "8ebb3008c95c416489b9db29d758008c": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "DescriptionStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "9a939ec092234106b3bbf13266650f29": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "a194ac9f28564a6a805b24a1a742838c": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "DescriptionStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "a34f3e8def0649618235b0c8d9648d99": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "DescriptionStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "a6d7e8cc772f4b44ba43a23a407e7c12": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "aa66c2d953c84ef9902875ccbc9c994e": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "ProgressStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "ac4b2cd6abad4fbe9129ad2b39f79d1c": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "ac9c8dcde2c14dbaa1173c31993a8425": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "IntProgressModel",
      "state": {
       "bar_style": "success",
       "layout": "IPY_MODEL_f6042c224cb04d4d80e76e24bcd752f0",
       "max": 54,
       "style": "IPY_MODEL_043afb832aa3492482fd973bb9d9bd7a",
       "value": 54
      }
     },
     "acc45206458d480a9f2ef27c9c8ef1df": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "HTMLModel",
      "state": {
       "layout": "IPY_MODEL_2b5f53a0083041e88ab8b35fbcb6adec",
       "style": "IPY_MODEL_5f7e65435bd74f0eb6a1c412dfb425cc",
       "value": " 61% 27/44 [01:11&lt;01:07,  4.00s/it]"
      }
     },
     "ae8a07808b3e45859f3cd921f129124b": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "ProgressStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "b79ec55a28294c6bbf956dfc8e61c6d2": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "b7ee7f0454ef43edba44cdb7eff62621": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "bc47080108594d6398376ec90247fd7f": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "DescriptionStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "bdc29d95eb5b4ef9aa958372545ee719": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "c00586e1eccf461c9b0429e0ccfc324c": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "HBoxModel",
      "state": {
       "children": [
        "IPY_MODEL_c268087693ac4caea7ff5672e655a9d2",
        "IPY_MODEL_acc45206458d480a9f2ef27c9c8ef1df"
       ],
       "layout": "IPY_MODEL_d92aa9b32b694dcaabc8203167d6a20e"
      }
     },
     "c02a451e0731469ea91cc39abbf14c48": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "c071aba1cd534b049eee2f1809f94fec": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "c268087693ac4caea7ff5672e655a9d2": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "IntProgressModel",
      "state": {
       "layout": "IPY_MODEL_67b4ef9809f6494c8230ffa837fb5f2d",
       "max": 44,
       "style": "IPY_MODEL_0f5c61300af74d9c87b2e169a8d59564",
       "value": 27
      }
     },
     "c7666e83442f44259d58a3b1f3b48341": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "HTMLModel",
      "state": {
       "layout": "IPY_MODEL_fb350532137b4401810ece19b5140a35",
       "style": "IPY_MODEL_a34f3e8def0649618235b0c8d9648d99",
       "value": "100% 12/12 [00:03&lt;00:00,  2.07it/s]"
      }
     },
     "cb8738fbc3d54b8ea12d23b970356248": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "cc2ce2b0abab4704b0d580cdd7897c24": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "ProgressStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "d614664cf99743889aa9b084525990d8": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "HTMLModel",
      "state": {
       "layout": "IPY_MODEL_c071aba1cd534b049eee2f1809f94fec",
       "style": "IPY_MODEL_5aba36f9297242688598109bc09046de",
       "value": "100% 54/54 [01:11&lt;00:00,  2.69s/it]"
      }
     },
     "d86d424d7d2040bea285a821eb3ffaf6": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "d92aa9b32b694dcaabc8203167d6a20e": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "db91f69593764d1fbc8593c6264df3a7": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "f1361377c3184fb688b28bfe61451e86": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "ProgressStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "f504214792524c2cbbb8997e99aa7714": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "f52bb86c1e564d5381ea1b9792d4ee48": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "HBoxModel",
      "state": {
       "children": [
        "IPY_MODEL_0f40caa17b6f45b19f9b67db6af682c3",
        "IPY_MODEL_c7666e83442f44259d58a3b1f3b48341"
       ],
       "layout": "IPY_MODEL_bdc29d95eb5b4ef9aa958372545ee719"
      }
     },
     "f6042c224cb04d4d80e76e24bcd752f0": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "fb350532137b4401810ece19b5140a35": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.1.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "fb9bace579f64af4b7ebb87789031257": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "HTMLModel",
      "state": {
       "layout": "IPY_MODEL_774238a7f4bc4bc39881b33452244ce3",
       "style": "IPY_MODEL_1099c3fb624b4608ac4d8274ff57ff46",
       "value": "100% 31/31 [20:02&lt;00:00, 89.74s/it]"
      }
     },
     "fc2e0e50b4024f2089000a027350ad62": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.4.0",
      "model_name": "ProgressStyleModel",
      "state": {
       "description_width": ""
      }
     }
    },
    "version_major": 2,
    "version_minor": 0
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}