{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "2b544fa7",
   "metadata": {},
   "source": [
    "# Listes chaînées\n",
    "\n",
    "Le type `LinkedList` implémente les listes chaînées:\n",
    "- `None` représente la liste vide\n",
    "- `Cell(v, l)` est la liste débutant par la valeur `v` et de queue `l`\n",
    "\n",
    "Étant donnée une cellule `c = Cell(v, l)`:\n",
    "- `hd(c)` retourne la valeur `v` de `c`\n",
    "- `tl(c)` retourne la queue `l` de `c`\n",
    "\n",
    "La fonction `linkedListDisplay(l)` affiche la liste chaînée `l` sous forme graphique. La liste vide `None` est représentée par un point.\n",
    "\n",
    "Une représentation de la liste `l` sous forme de chaîne de caractères est donnée par la fonction `linkedListToStr(l)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "834fd3d5",
   "metadata": {},
   "outputs": [],
   "source": [
    "from utils import *"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d690dc16",
   "metadata": {},
   "source": [
    "## Définition de listes\n",
    "\n",
    "Écrire les définitions des listes chaînées `[]`, `[1]` et `[1, 2, 3]`, et afficher ces listes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4b399f91",
   "metadata": {},
   "outputs": [],
   "source": [
    "l_empty = None\n",
    "l_1 = Cell(1, None)\n",
    "l_123 = Cell(1, Cell(2, Cell(3, None)))\n",
    "\n",
    "linkedListDisplay(l_empty)\n",
    "linkedListDisplay(l_1)\n",
    "linkedListDisplay(l_123)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "56c774c7",
   "metadata": {},
   "source": [
    "## Longueur d'une liste"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "eb2be4c4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def listLengthIter(l: LinkedList) -> int:\n",
    "    \"\"\" Retourne la longueur de l, calculée avec un algorithme itératif \"\"\"\n",
    "    length: int = 0\n",
    "    while l is not None:\n",
    "        length += 1\n",
    "        l = tl(l)\n",
    "    return length\n",
    "\n",
    "def listLengthRec(l: LinkedList) -> int:\n",
    "    \"\"\" Retourne la longueur de l, calculée avec un algorithme récursif \"\"\"\n",
    "    if l is None:\n",
    "        return 0\n",
    "    return 1 + listLengthRec(tl(l))\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4c88bc24",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test des fonctions listLengthIter et listLengthRec\n",
    "\n",
    "# Liste vide\n",
    "assert listLengthIter(None) == 0\n",
    "assert listLengthRec(None) == 0\n",
    "\n",
    "# Liste [1, 2, 3, 4, 5]\n",
    "l = Cell(1, Cell(2, Cell(3, Cell(4, Cell(5, None)))))\n",
    "assert listLengthIter(l) == 5\n",
    "assert listLengthRec(l) == 5\n",
    "\n",
    "print('Ok')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d6243fd3",
   "metadata": {},
   "source": [
    "## Recherche d'une valeur dans une liste"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ed4d7e74",
   "metadata": {},
   "outputs": [],
   "source": [
    "def listFindIter(l: LinkedList, v: int) -> bool:\n",
    "    \"\"\" Retourne True si v est dans l, et False sinon, version itérative \"\"\"\n",
    "    while l is not None:\n",
    "        if hd(l) == v:\n",
    "            return True\n",
    "        l = tl(l)\n",
    "    return False\n",
    "\n",
    "def listFindRec(l: LinkedList, v: int) -> bool:\n",
    "    \"\"\" Retourne True si v est dans l, et False sinon, version récursive \"\"\"\n",
    "    if l is None:\n",
    "        return False\n",
    "    elif hd(l) == v:\n",
    "        return True\n",
    "    else:\n",
    "        return listFindRec(tl(l), v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f1c5f348",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test de la recherche dans une liste\n",
    "\n",
    "# Liste vide\n",
    "assert not listFindIter(None, 3)\n",
    "assert not listFindRec(None, 5)\n",
    "\n",
    "# Liste avec un élément, différent de la valeur\n",
    "l = Cell(8, None)\n",
    "assert not listFindIter(l, 12)\n",
    "assert not listFindRec(l, 28)\n",
    "\n",
    "# Liste avec un élément, égal à la valeur\n",
    "l = Cell(389, None)\n",
    "assert listFindIter(l, 389)\n",
    "assert listFindRec(l, 389)\n",
    "\n",
    "# Liste avec plusieurs éléments, sans la valeur recherchée\n",
    "l = newExplicitList([2, 4, 6, 8, 10])\n",
    "assert not listFindIter(l, 1)\n",
    "assert not listFindIter(l, 11)\n",
    "\n",
    "# Liste avec plusieurs éléments, dont la valeure recherchée\n",
    "l = newExplicitList([1, 4, 9, 16, 25])\n",
    "assert listFindIter(l, 9)\n",
    "assert listFindRec(l, 1)\n",
    "\n",
    "print('Ok')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9ff7c80d",
   "metadata": {},
   "source": [
    "## Somme des valeurs d'une liste"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "72fd7eda",
   "metadata": {},
   "outputs": [],
   "source": [
    "def listSumIter(l: LinkedList) -> int:\n",
    "    \"\"\" Retourne la somme des valeurs de l, calculée en itératif \"\"\"\n",
    "    s: int = 0\n",
    "    while l is not None:\n",
    "        s += l.hd()\n",
    "        l = l.tl()\n",
    "    return s\n",
    "\n",
    "def listSumRec(l: LinkedList) -> int:\n",
    "    \"\"\" Retourne la somme des valeurs de l, calculée en récursif \"\"\"\n",
    "    if l is None:\n",
    "        return 0\n",
    "    else:\n",
    "        return hd(l) + listSumRec(tl(l))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "512353d3",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test des fonctions listSumIter et listSumRec\n",
    "\n",
    "# Liste vide\n",
    "assert listSumIter(None) == 0\n",
    "assert listSumRec(None) == 0\n",
    "\n",
    "# Liste [3, 7, 5, 1, 8, 2, 9]\n",
    "l = Cell(3, Cell(7, Cell(5, Cell(1, Cell(8, Cell(2, Cell(9, None)))))))\n",
    "\n",
    "assert listSumIter(l) == 35\n",
    "assert listSumRec(l) == 35\n",
    "\n",
    "print('Ok')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "95ed339d",
   "metadata": {},
   "source": [
    "## Créer une liste aléatoire"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ce36d40e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def newRandomList(n: int) -> LinkedList:\n",
    "    \"\"\" Retourne une list chaînée de longueur n, où toutes les valeurs sont des entiers tirés pseudo-aléatoirement entre 0 et n \"\"\"\n",
    "    l: LinkedList = None\n",
    "    for _ in range(n):\n",
    "        l = Cell(random.randint(0, n), l)\n",
    "    return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "08437879",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test de la fonction newRandomList\n",
    "\n",
    "# Liste vide\n",
    "l = newRandomList(0)\n",
    "assert listLengthIter(l) == 0\n",
    "\n",
    "# Liste à un élément\n",
    "l = newRandomList(1)\n",
    "assert listLengthIter(l) == 1\n",
    "assert 0 <= hd(l) <= 1\n",
    "\n",
    "# Liste à plus d'un élément\n",
    "l = newRandomList(15)\n",
    "assert listLengthIter(l) == 15\n",
    "for v in l:\n",
    "    assert 0 <= v <= 15\n",
    "\n",
    "print('Ok')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e44e53ff",
   "metadata": {},
   "source": [
    "## Cloner une liste"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8b629ee5",
   "metadata": {},
   "outputs": [],
   "source": [
    "def cloneList(l: LinkedList) -> LinkedList:\n",
    "    if l is None:\n",
    "        return None\n",
    "    return Cell(hd(l), cloneList(tl(l)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6158a0b8",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test de la fonction cloneList\n",
    "\n",
    "## Liste vide\n",
    "assert cloneList(None) is None\n",
    "\n",
    "## Liste de taille 1\n",
    "l = Cell(1, None)\n",
    "lclone = cloneList(l)\n",
    "\n",
    "assert lclone is not None\n",
    "assert hd(lclone) == hd(l)\n",
    "assert tl(lclone) is None\n",
    "assert id(lclone) != id(l)\n",
    "\n",
    "## Liste de taille 5\n",
    "l = Cell(1, Cell(2, Cell(3, Cell(4, Cell(5, None)))))\n",
    "lclone = cloneList(l)\n",
    "\n",
    "assert lclone is not None\n",
    "assert listLengthIter(l) == listLengthIter(lclone)\n",
    "while l is not None:\n",
    "    assert hd(l) == hd(lclone)\n",
    "    assert id(l) != id(lclone)\n",
    "    l = tl(l)\n",
    "    lclone = tl(lclone)\n",
    "\n",
    "print('Ok')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9af0a08d",
   "metadata": {},
   "source": [
    "## Retirer une valeur d'une liste\n",
    "\n",
    "La fonction `listRemove` retourne un clone de la liste `l` privé des valeurs `v`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9bd50359",
   "metadata": {},
   "outputs": [],
   "source": [
    "def listRemove(l: LinkedList, v: int) -> LinkedList:\n",
    "    if l is None:\n",
    "        return None\n",
    "    elif hd(l) == v:\n",
    "        return listRemove(tl(l), v)\n",
    "    else:\n",
    "        return Cell(hd(l), listRemove(tl(l), v))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "eaf63053",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test de listRemove\n",
    "\n",
    "# Liste vide\n",
    "assert listRemove(None, 3) == None\n",
    "\n",
    "# Liste à un élément, égal à la valeur retirée\n",
    "assert listRemove(Cell(3, None), 3) == None\n",
    "\n",
    "# Liste à un élément, différent de la valeur retirée\n",
    "lactual = listRemove(Cell(2, None), 5)\n",
    "lexpected = Cell(2, None)\n",
    "assert linkedListEqual(lactual, lexpected)\n",
    "\n",
    "# Liste à plusieurs éléments, avec des occurrences de la valeur retirée\n",
    "l = Cell(1, Cell(2, Cell(1, Cell(1, Cell(3, Cell(4, Cell(1, None)))))))\n",
    "lactual = listRemove(l, 1)\n",
    "lexpected = Cell(2, Cell(3, Cell(4, None)))\n",
    "assert linkedListEqual(lactual, lexpected)\n",
    "\n",
    "# Liste à plusieurs éléments, différents de la valeur retirée\n",
    "l = Cell(4, Cell(7, Cell(-1, Cell(9, Cell(2, Cell(3, None))))))\n",
    "lactual = listRemove(l, 5)\n",
    "lexpected = Cell(4, Cell(7, Cell(-1, Cell(9, Cell(2, Cell(3, None))))))\n",
    "assert linkedListEqual(lactual, lexpected)\n",
    "\n",
    "print('Ok')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b6fe991e",
   "metadata": {},
   "source": [
    "# Concaténer deux listes\n",
    "\n",
    "Les fonctions `listConcatIter` et `listConcatRec` ne sont pas interchangeables:\n",
    "- `listConcatIter` ajoute `l2` en fin de `l1`\n",
    "- alors que `listConcatRec` ajoute `l2` à la fin d'un *clone* de `l1`\n",
    "\n",
    "**NB:** il suffit de modifier `c1: Cell = cloneList(l1)` pour que les deux fonctions ajoutent tous les deux `l2` à la fin d'un clone de `l1`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "36e72dfb",
   "metadata": {},
   "outputs": [],
   "source": [
    "def listConcatIter(l1: LinkedList, l2: LinkedList) -> LinkedList:\n",
    "    \"\"\" Retourne la liste obtenue en concaténant l2 à la suite de l1 par un algorithme itératif \"\"\"\n",
    "    if l1 is None:\n",
    "        return l2\n",
    "    # Recherche la dernière cellule de l1\n",
    "    c1: Cell = l1\n",
    "    while tl(c1) is not None:\n",
    "        c1 = tl(c1)\n",
    "    # l2 devient la queue de la dernière cellule\n",
    "    c1.set_tl(l2)\n",
    "    return l1\n",
    "\n",
    "def listConcatRec(l1: LinkedList, l2: LinkedList) -> LinkedList:\n",
    "    \"\"\" Retourne la liste obtenue en concaténant l2 à la suite d'un clone de l1 (vue inductive du type) \"\"\"\n",
    "    if l1 is None:\n",
    "        return l2\n",
    "    return Cell(hd(l1), listConcatRec(tl(l1), l2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d3da179a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test de concaténation de listes\n",
    "\n",
    "# Concaténation de deux listes vides\n",
    "assert listConcatIter(None, None) is None\n",
    "assert listConcatRec(None, None) is None\n",
    "\n",
    "# Concaténation d'une liste non vide à une liste vide\n",
    "l = Cell(1, Cell(2, None))\n",
    "\n",
    "lconcat = listConcatIter(None, l)\n",
    "assert linkedListEqual(l, lconcat)\n",
    "\n",
    "lconcat = listConcatRec(None, l)\n",
    "assert linkedListEqual(l, lconcat)\n",
    "\n",
    "# Concaténation d'une liste vide à une liste non vide\n",
    "l = Cell(1, Cell(2, Cell(3, Cell(4, None))))\n",
    "\n",
    "lconcat = listConcatIter(l, None)\n",
    "assert linkedListEqual(lconcat, l)\n",
    "\n",
    "lconcat = listConcatRec(l, None)\n",
    "assert linkedListEqual(lconcat, l)\n",
    "\n",
    "# Concatenation de deux listes non vides\n",
    "l1 = Cell(1, Cell(2, Cell(3, Cell(4, None))))\n",
    "l2 = Cell(5, Cell(6, Cell(7, None)))\n",
    "lexpected = Cell(1, Cell(2, Cell(3, Cell(4, Cell(5, Cell(6, Cell(7, None)))))))\n",
    "\n",
    "lconcat = listConcatIter(l1, l2)\n",
    "assert linkedListEqual(lconcat, lexpected)\n",
    "\n",
    "l1 = Cell(1, Cell(2, Cell(3, Cell(4, None))))\n",
    "l2 = Cell(5, Cell(6, Cell(7, None)))\n",
    "lexpected = Cell(1, Cell(2, Cell(3, Cell(4, Cell(5, Cell(6, Cell(7, None)))))))\n",
    "\n",
    "lconcat = listConcatRec(l1, l2)\n",
    "assert linkedListEqual(lconcat, lexpected)\n",
    "\n",
    "print('Ok')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5416b943",
   "metadata": {},
   "source": [
    "## Renverser une liste"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e635d8db",
   "metadata": {},
   "outputs": [],
   "source": [
    "def listReverseIter(l: LinkedList) -> LinkedList:\n",
    "    \"\"\" Retourne la liste obtenue en renversant l, en version itérative \"\"\"\n",
    "    lrev: LinkedList = None\n",
    "    while l is not None:\n",
    "        lrev = Cell(hd(l), lrev)\n",
    "        l = tl(l)\n",
    "    return lrev\n",
    "\n",
    "def listReverseRec(l: LinkedList) -> LinkedList:\n",
    "    \"\"\" Retourne la liste obtenue en renversant l, en version récursive \"\"\"\n",
    "    if l is None:\n",
    "        return None\n",
    "    return listConcatRec(listReverseRec(tl(l)), Cell(hd(l), None))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7188de00",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Tests de renversements de listes\n",
    "\n",
    "# Renversement d'une liste vide\n",
    "assert listReverseIter(None) is None\n",
    "assert listReverseRec(None) is None\n",
    "\n",
    "# Renversement d'une liste de taille 1\n",
    "l = Cell(1, None)\n",
    "lactual = listReverseIter(l)\n",
    "assert linkedListEqual(lactual, l)\n",
    "\n",
    "l = Cell(10, None)\n",
    "lactual = listReverseRec(l)\n",
    "assert linkedListEqual(lactual, l)\n",
    "\n",
    "# Renversement d'une liste avec plusieurs éléments\n",
    "l = Cell(23, Cell(45, Cell(678, Cell(90, None))))\n",
    "lexpected = Cell(90, Cell(678, Cell(45, Cell(23, None))))\n",
    "lactual = listReverseIter(l)\n",
    "assert linkedListEqual(lactual, lexpected)\n",
    "\n",
    "l = Cell(23, Cell(45, Cell(678, Cell(90, None))))\n",
    "lexpected = Cell(90, Cell(678, Cell(45, Cell(23, None))))\n",
    "lactual = listReverseRec(l)\n",
    "assert linkedListEqual(lactual, lexpected)\n",
    "\n",
    "print('Ok')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4ff0f50e",
   "metadata": {},
   "source": [
    "## Tri fusion (*merge sort*)\n",
    "\n",
    "**Principe:** pour trier une liste `l`,\n",
    "- *diviser* `l` en deux parties égales `l1` et `l2` (à 1 élément près)\n",
    "- trier `l1` et `l2` (plus petits problèmes)\n",
    "- *fusionner* `l1` et `l2`\n",
    "\n",
    "Pour partitionner `l`, on place un élément sur deux dans `l1` et les autres dans `l2`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b1e8d401",
   "metadata": {},
   "outputs": [],
   "source": [
    "def splitList(l: LinkedList) -> Tuple[LinkedList, LinkedList]:\n",
    "    \"\"\" Splits list l into two lists \"\"\"\n",
    "    if l is None:\n",
    "        return (None, None)\n",
    "    l1, l2 = splitList(tl(l))\n",
    "    return (Cell(hd(l), l2), l1)\n",
    "\n",
    "def mergeSortedLists(l1: LinkedList, l2: LinkedList) -> LinkedList:\n",
    "    \"\"\" Returns the sorted list obtained by mergeing two sorted lists l1 and l2 \"\"\"\n",
    "    if l1 is None:\n",
    "        return l2\n",
    "    elif l2 is None:\n",
    "        return l1\n",
    "    elif hd(l1) <= hd(l2):\n",
    "        return Cell(hd(l1), mergeSortedLists(tl(l1), l2))\n",
    "    else:\n",
    "        return Cell(hd(l2), mergeSortedLists(l1, tl(l2)))\n",
    "\n",
    "def listMergeSort(l: LinkedList) -> LinkedList:\n",
    "    \"\"\" Sorts l using merge sort \"\"\"\n",
    "    if l is None:\n",
    "        return None\n",
    "    if tl(l) is None:\n",
    "        return l\n",
    "    l1, l2 = splitList(l)\n",
    "    l1 = listMergeSort(l1)\n",
    "    l2 = listMergeSort(l2)\n",
    "    return mergeSortedLists(l1, l2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ffbce982",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Tests du tri fusion de listes\n",
    "\n",
    "# Liste vide\n",
    "assert listMergeSort(None) is None\n",
    "\n",
    "# Liste à un élément\n",
    "l = Cell(10, None)\n",
    "lactual = listMergeSort(l)\n",
    "lexpected = Cell(10, None)\n",
    "assert linkedListEqual(lactual, lexpected)\n",
    "\n",
    "# Liste à plusieurs éléments\n",
    "l = newExplicitList([0, 7, -1, 5, 9, 123, 72, 45, 87])\n",
    "lactual = listMergeSort(l)\n",
    "lexpected = newExplicitList([-1, 0, 5, 7, 9, 45, 72, 87, 123])\n",
    "assert linkedListEqual(lactual, lexpected)\n",
    "\n",
    "print(\"Ok\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1a0b32b6",
   "metadata": {},
   "source": [
    "## Tri rapide (*quick sort*)\n",
    "\n",
    "**Principe:** pour trier une liste `l`,\n",
    "- choisir un pivot, par exemple le premier élément de `l`\n",
    "- *diviser* `l` en trois parties: d'une part `lt`, les éléments `<` au pivot, d'autre part `eq` contenant les éléments `==` pivot, et enfin `gt` qui contient les valeurs `>` au pivot\n",
    "- trier `l1` et `l2` (plus petits problèmes)\n",
    "- *fusionner* `l1` et `l2`\n",
    "\n",
    "La fusion consiste simplement à concaténer `l1` et `l2` qui sont triées, et tous les éléments de `l1` sont plus petits que ceux de `l2`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a0e4f361",
   "metadata": {},
   "outputs": [],
   "source": [
    "def partitionList(l: LinkedList, pivot: int) -> Tuple[LinkedList, LinkedList, LinkedList]:\n",
    "    \"\"\" Splits l into three lists: the first one contains all values < pivot, the second one contains all values = pivot, whereas the third one contains all values > pivot \"\"\"\n",
    "    if l is None:\n",
    "        return (None, None, None)\n",
    "    else:\n",
    "        (lt, eq, gt) = partitionList(tl(l), pivot)\n",
    "        x: int = hd(l)\n",
    "        if x < pivot:\n",
    "            return (Cell(x, lt), eq, gt)\n",
    "        elif hd(l) == pivot:\n",
    "            return (lt, Cell(x, eq), gt)\n",
    "        else:\n",
    "            return (lt, eq, Cell(x, gt))\n",
    "\n",
    "def listQuickSort(l: LinkedList) -> LinkedList:\n",
    "    \"\"\" Sorts list l using quick sort \"\"\"\n",
    "    if l is None:\n",
    "        return None\n",
    "    elif tl(l) is None:\n",
    "        return l\n",
    "    else:\n",
    "        lt, eq, gt = partitionList(l, hd(l))\n",
    "        lt = listQuickSort(lt)\n",
    "        gt = listQuickSort(gt)\n",
    "        return listConcatIter(lt, listConcatIter(eq, gt))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "538cbec6",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Tests du tri rapide de listes\n",
    "\n",
    "# Liste vide\n",
    "assert listQuickSort(None) is None\n",
    "\n",
    "# Liste à un élément\n",
    "l = Cell(10, None)\n",
    "lactual = listQuickSort(l)\n",
    "lexpected = Cell(10, None)\n",
    "assert linkedListEqual(lactual, lexpected)\n",
    "\n",
    "# Liste à plusieurs éléments\n",
    "l = newExplicitList([0, 7, -1, 5, 9, 123, 72, 45, 87])\n",
    "lactual = listQuickSort(l)\n",
    "lexpected = newExplicitList([-1, 0, 5, 7, 9, 45, 72, 87, 123])\n",
    "assert linkedListEqual(lactual, lexpected)\n",
    "\n",
    "print(\"Ok\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "829e9295",
   "metadata": {},
   "source": [
    "## Insertion dans une liste triée"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "507ffae7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def listInsertSorted(l: LinkedList, v: int) -> LinkedList:\n",
    "    \"\"\" Inserts v in the sorted list l \"\"\"\n",
    "    if l is None:\n",
    "        return Cell(v, None)\n",
    "    elif v <= hd(l):\n",
    "        return Cell(v, l)\n",
    "    else:\n",
    "        return Cell(hd(l), listInsertSorted(tl(l), v))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cea1a624",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test de l'insertion dans une liste triée\n",
    "\n",
    "# Liste vide\n",
    "lactual = listInsertSorted(None, 45)\n",
    "lexpected = Cell(45, None)\n",
    "assert linkedListEqual(lactual, lexpected)\n",
    "\n",
    "# Liste à un élément, insertion en tête\n",
    "l = Cell(7, None)\n",
    "lactual = listInsertSorted(l, 3)\n",
    "lexpected = Cell(3, Cell(7, None))\n",
    "assert linkedListEqual(lactual, lexpected)\n",
    "\n",
    "# Liste à un élément, insertion en queue\n",
    "l = Cell(37, None)\n",
    "lactual = listInsertSorted(l, 219)\n",
    "lexpected = Cell(37, Cell(219, None))\n",
    "assert linkedListEqual(lactual, lexpected)\n",
    "\n",
    "# Liste à plusieurs éléments, insertion en tête\n",
    "l = newExplicitList([3, 5, 9, 15])\n",
    "lactual = listInsertSorted(l, 2)\n",
    "lexpected = newExplicitList([2, 3, 5, 9, 15])\n",
    "assert linkedListEqual(lactual, lexpected)\n",
    "\n",
    "# Liste à plusieurs éléments, insertion eau milieu\n",
    "l = newExplicitList([3, 5, 9, 15])\n",
    "lactual = listInsertSorted(l, 7)\n",
    "lexpected = newExplicitList([3, 5, 7, 9, 15])\n",
    "assert linkedListEqual(lactual, lexpected)\n",
    "\n",
    "# Liste à plusieurs éléments, insertion en fin\n",
    "l = newExplicitList([3, 5, 9, 15])\n",
    "lactual = listInsertSorted(l, 22)\n",
    "lexpected = newExplicitList([3, 5, 9, 15, 22])\n",
    "assert linkedListEqual(lactual, lexpected)\n",
    "\n",
    "print('Ok')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "defaultInterpreterPath: 3.14.8.final.0",
   "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.14.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}