{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Travaux pratiques - Structures de données\n",
    "\n",
    "**AVERTISSEMENT**\n",
    "**Pour l'exécution correcte des fragments de code suivant, il est fondamental d'exécuter le fragment suivant :**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%maven org.assertj:assertj-core:3.10.0\n",
    "    \n",
    "import static org.assertj.core.api.Assertions.*;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Manipulation de tableaux\n",
    "\n",
    "Implémenter une méthode qui accepte deux paramètres `m` et `n` de type `int` et qui crée une matrice de dimensions `m` x `n`. La valeur de la cellule de coordonnées `[i][j]` est `i + j`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Manipulation de listes\n",
    "### 4.1 Itération\n",
    "#### 4.1.1 Somme\n",
    "Soit une liste d’entiers. Implémenter une méthode sum() qui retourne la somme des éléments de la liste."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "ename": "EvalException",
     "evalue": "\nExpecting:\n <-1>\nto be equal to:\n <9>\nbut was not.",
     "output_type": "error",
     "traceback": [
      "\u001b[1m\u001b[31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1m\u001b[31mjava.lang.AssertionError: \u001b[0m",
      "\u001b[1m\u001b[31mExpecting:\u001b[0m",
      "\u001b[1m\u001b[31m <-1>\u001b[0m",
      "\u001b[1m\u001b[31mto be equal to:\u001b[0m",
      "\u001b[1m\u001b[31m <9>\u001b[0m",
      "\u001b[1m\u001b[31mbut was not.\u001b[0m",
      "\u001b[1m\u001b[31m\tat .(#22:1)\u001b[0m"
     ]
    }
   ],
   "source": [
    "List integers = Arrays.asList(-2, 3, 5, 6, 9, -25, 12, 1);\n",
    "\n",
    "public int sum(List integers) {\n",
    "     return -1;\n",
    "}\n",
    "\n",
    "assertThat(sum(integers)).isEqualTo(9);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 4.1.2 Groupement\n",
    "Implémenter une méthode `group()` qui retourne les éléments d’une liste groupés par type. Le groupement se fait selon les règles suivantes :\n",
    "\n",
    "* Le premier groupe comprend les chaînes de caractères,\n",
    "* Le deuxième groupe les éléments de type Integer,\n",
    "*  La troisième tous les autres.\n",
    "\n",
    "Chaque groupe est géré par un type `Collection`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "ename": "EvalException",
     "evalue": "\nExpected size:<3> but was:<9> in:\n<[2,\n    1,\n    \"banana\",\n    null,\n    \"apple\",\n    \"orange\",\n    3,\n    java.lang.Object@462eeaa8,\n    2018-07-30]>",
     "output_type": "error",
     "traceback": [
      "\u001b[1m\u001b[31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1m\u001b[31mjava.lang.AssertionError: \u001b[0m",
      "\u001b[1m\u001b[31mExpected size:<3> but was:<9> in:\u001b[0m",
      "\u001b[1m\u001b[31m<[2,\u001b[0m",
      "\u001b[1m\u001b[31m    1,\u001b[0m",
      "\u001b[1m\u001b[31m    \"banana\",\u001b[0m",
      "\u001b[1m\u001b[31m    null,\u001b[0m",
      "\u001b[1m\u001b[31m    \"apple\",\u001b[0m",
      "\u001b[1m\u001b[31m    \"orange\",\u001b[0m",
      "\u001b[1m\u001b[31m    3,\u001b[0m",
      "\u001b[1m\u001b[31m    java.lang.Object@462eeaa8,\u001b[0m",
      "\u001b[1m\u001b[31m    2018-07-30]>\u001b[0m",
      "\u001b[1m\u001b[31m\tat .(#29:1)\u001b[0m"
     ]
    }
   ],
   "source": [
    "import java.time.LocalDate;\n",
    "\n",
    "LocalDate date = LocalDate.now();\n",
    "Object object = new Object();\n",
    "List items = new ArrayList(Arrays.asList(2, 1, \"banana\", null, \"apple\", \"orange\", 3, object, date));\n",
    "\n",
    "public void group(List items) {\n",
    "}\n",
    "\n",
    "group(items);\n",
    "\n",
    "assertThat(items).hasSize(3);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 4.2 Comparateurs\n",
    "\n",
    "Implémenter une méthode `sortWithSetComparator()` qui trie une liste avec un comparateur explicite en utilisant l’ordre suivant :\n",
    "\n",
    "1. Les entiers, puis dans l’ordre naturel des entiers,\n",
    "1. Les chaînes de caractères, puis dans l’ordre naturel des chaînes de caractères,\n",
    "1. Les éléments qui ne sont pas de type `Object`,\n",
    "1. Les éléments de type `Object`,\n",
    "1. Enfin, les valeurs `null`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "org.assertj.core.api.ListAssert@1"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import java.time.LocalDate;\n",
    "\n",
    "LocalDate date = LocalDate.now();\n",
    "Object object = new Object();\n",
    "List items = new ArrayList(Arrays.asList(2, 1, \"banana\", null, \"apple\", \"orange\", 3, object, date));\n",
    "\n",
    "public void sortWithSetComparator(List items, Comparator comparator) {\n",
    "}\n",
    "\n",
    "public class MyComparator implements Comparator {\n",
    "\n",
    "    @Override\n",
    "    public int compare(Object item1, Object item2) {\n",
    "         return 0;\n",
    "    }\n",
    "}\n",
    "\n",
    "sortWithSetComparator(items, new MyComparator());\n",
    "\n",
    "\n",
    "assertThat(items).hasSize(9);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.2.2 Chaînage de comparateurs\n",
    "Soit le code suivant :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "ename": "EvalException",
     "evalue": "\nActual and expected have the same elements but not in the same order, at index 0 actual element was:\n  <REPL.$JShell$34$Person@3b303c7d>\nwhereas expected element was:\n  <REPL.$JShell$34$Person@257071e2>\n",
     "output_type": "error",
     "traceback": [
      "\u001b[1m\u001b[31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1m\u001b[31mjava.lang.AssertionError: \u001b[0m",
      "\u001b[1m\u001b[31mActual and expected have the same elements but not in the same order, at index 0 actual element was:\u001b[0m",
      "\u001b[1m\u001b[31m  <REPL.$JShell$34$Person@3b303c7d>\u001b[0m",
      "\u001b[1m\u001b[31mwhereas expected element was:\u001b[0m",
      "\u001b[1m\u001b[31m  <REPL.$JShell$34$Person@257071e2>\u001b[0m",
      "\u001b[1m\u001b[31m\u001b[0m",
      "\u001b[1m\u001b[31m\tat .(#44:1)\u001b[0m"
     ]
    }
   ],
   "source": [
    "public class Person {\n",
    "    private final String firstName;\n",
    "    private final String lastName;\n",
    "    public Person(String firstName, String lastName) {\n",
    "        this.firstName = firstName;\n",
    "        this.lastName = lastName;\n",
    "    }\n",
    "    public String getFirstName() {\n",
    "        return firstName;\n",
    "    }\n",
    "    public String getLastName() {\n",
    "        return lastName;\n",
    "    }    \n",
    "}\n",
    "\n",
    "public class ByFirstNameComparator implements Comparator<String> {\n",
    "    @Override\n",
    "    public int compare(String item1, String item2) {\n",
    "         return item1.compareTo(item2);\n",
    "    }\n",
    "}\n",
    "\n",
    "public class ByLastNameComparator implements Comparator<String> {\n",
    "    @Override\n",
    "    public int compare(String item1, String item2) {\n",
    "         return item1.compareTo(item2);\n",
    "    }\n",
    "}\n",
    "\n",
    "public class ByLastNameThenFirstNameComparator implements Comparator<Person> {\n",
    "    @Override\n",
    "    public int compare(Person person1, Person person2) {\n",
    "         return 0;\n",
    "    }\n",
    "}\n",
    "\n",
    "Person john = new Person(\"John\", \"Doe\");\n",
    "Person jane = new Person(\"Jane\", \"Doe\");\n",
    "Person gosling = new Person(\"James\", \"Gosling\");\n",
    "\n",
    "List persons = new ArrayList(Arrays.asList(john, jane, gosling));\n",
    "Collections.shuffle(persons);\n",
    "\n",
    "Collections.sort(persons, new ByLastNameThenFirstNameComparator());\n",
    "\n",
    "assertThat(persons).containsExactly(jane, john, gosling);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En réutilisant les classes existantes, créer une implémentation de comparateur `ByLastNameThenFirstNameComparator` qui compare deux instances de Person :\n",
    "\n",
    "1. Par leur attribut `lastName`,\n",
    "1. Puis en cas d’égalité par leur attribut `firstName`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 4.2.3 Tri par ordre naturel\n",
    "Implémenter une méthode `sortWithNaturalOrder()` qui trie la liste passée en paramètre dans l’ordre naturel des éléments. Tester la méthode avec la liste suivante :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "ename": "EvalException",
     "evalue": "java.base/java.lang.Integer cannot be cast to java.base/java.lang.String",
     "output_type": "error",
     "traceback": [
      "\u001b[1m\u001b[31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1m\u001b[31mjava.lang.ClassCastException: java.base/java.lang.Integer cannot be cast to java.base/java.lang.String\u001b[0m",
      "\u001b[1m\u001b[31m\tat java.base/java.lang.String.compareTo(String.java:123)\u001b[0m",
      "\u001b[1m\u001b[31m\tat java.base/java.util.ComparableTimSort.countRunAndMakeAscending(ComparableTimSort.java:321)\u001b[0m",
      "\u001b[1m\u001b[31m\tat java.base/java.util.ComparableTimSort.sort(ComparableTimSort.java:188)\u001b[0m",
      "\u001b[1m\u001b[31m\tat java.base/java.util.Arrays.sort(Arrays.java:1314)\u001b[0m",
      "\u001b[1m\u001b[31m\tat java.base/java.util.Arrays.sort(Arrays.java:1508)\u001b[0m",
      "\u001b[1m\u001b[31m\tat java.base/java.util.ArrayList.sort(ArrayList.java:1587)\u001b[0m",
      "\u001b[1m\u001b[31m\tat java.base/java.util.Collections.sort(Collections.java:141)\u001b[0m",
      "\u001b[1m\u001b[31m\tat .sortWithNaturalOrder(#45:1)\u001b[0m",
      "\u001b[1m\u001b[31m\tat .(#46:1)\u001b[0m"
     ]
    }
   ],
   "source": [
    "import java.time.LocalDate;\n",
    "\n",
    "LocalDate date = LocalDate.now();\n",
    "Object object = new Object();\n",
    "List items = new ArrayList(Arrays.asList(2, 1, \"banana\", null, \"apple\", \"orange\", 3, object, date));\n",
    "\n",
    "public void sortWithNaturalOrder(List items) {\n",
    "    Collections.sort(items);\n",
    "}\n",
    "\n",
    "sortWithNaturalOrder(items);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Quel est le résultat obtenu ?\n",
    "1. Expliquer la raison.\n",
    "1. Proposer une solution pour corriger le problème."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 4.3 Tri par ordre naturel - système de fichiers\n",
    "\n",
    "Implémenter une méthode `listDirectory()` qui accepte en paramètre le chemin vers un répertoire et retourne la liste triée des enfants de ce répertoire.\n",
    "\n",
    "1. Appeler la méthode en passant un répertoire avec un nombre conséquent d’enfants.\n",
    "1. Constater l’orde utilisé.\n",
    "1. Chercher la confirmation à l’aide de la JavaDoc."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "public String[] listDirectory(File path) {\n",
    "    return new String[0];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Manipulation de sets\n",
    "Soit la classe Person suivante :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.3\n",
      "2.false\n"
     ]
    }
   ],
   "source": [
    "public class Person {\n",
    "    private final String name;\n",
    "    private final String avs;\n",
    "    public Person(String name, String avs) {\n",
    "        this.name = name;\n",
    "        this.avs = avs;\n",
    "    }\n",
    "}\n",
    "\n",
    "Person p1 = new Person(\"John Doe\", \"756-1234-5678-97\");\n",
    "Person p2 = new Person(\"John Doe\", \"756-1234-5678-97\");\n",
    "Person p3 = new Person(\"Jane Doe\", \"111-11-111-113\");\n",
    "Set persons = new HashSet(Arrays.asList(p1, p2, p3));\n",
    "System.out.println(\"1.\" + persons.size());\n",
    "System.out.println(\"2.\" + p1.equals(p2));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En surchargeant uniquement les méthodes adéquates dans la classe Person, faire en sorte que le résultat de l’exécution du code précédent soit :\n",
    "\n",
    "1. `2`\n",
    "2. `true`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6 Manipulation de dictionnaires\n",
    "\n",
    "Soit le code suivant :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "public class Wrapper {\n",
    "    private final int id;\n",
    "    public Wrapper(int id) {\n",
    "        this.id = id;\n",
    "    }\n",
    "\n",
    "    @Override\n",
    "    public boolean equals(Object o) {\n",
    "        return o instanceof Wrapper && this.id == ((Wrapper) o).id;\n",
    "    }\n",
    "\n",
    "    @Override\n",
    "    public int hashCode() {\n",
    "        return 1;                      // (1)\n",
    "    }\n",
    "}\n",
    "\n",
    "Map map = new HashMap();               // (2)\n",
    "int limit = 10_000_000;                // (3)\n",
    "for (int i = 0; i < limit; i++) {\n",
    "    Wrapper w = new Wrapper(i);\n",
    "    map.put(w, w);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Expliquer le problème posé par le code. Le corriger.\n",
    "1. Quels sont le(s) paramètre(s) à passer dans le constructeur de la `HashMap` pour optimiser le temps d’exécution du code ? Justifier.\n",
    "1. En quoi la réponse à la question précédent diffère si la valeur de la variable `limit` n’est pas connue ?"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Java",
   "language": "java",
   "name": "java"
  },
  "language_info": {
   "codemirror_mode": "java",
   "file_extension": ".java",
   "mimetype": "text/x-java-source",
   "name": "Java",
   "pygments_lexer": "java",
   "version": "9.0.4+11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}