TD 8

Tri fusion en place et généricité

Votre opinion sur le cours de ce lundi :	Votre opinion sur le TD de la semaine dernière :

Préambule

Création d'un projet dédié au TD8

Lancez Visual Studio Code (VS Code par la suite), par exemple en exécutant la commande code dans le terminal, ou en cliquant sur un raccourci; la touche [Alt] fait apparaître / disparaître la barre du menu horizontale.
Dans VS Code tapez la combinaison de touches [Ctrl]+[Shift]+[P] (ou [Alt]+[V] puis cliquez sur command Palette) puis tapez «java: create» dans la barre qui apparaît et sélectionnez Create Java Project et l'option No build tools.
Une fenêtre s'ouvre et vous invite à choisir votre espace de travail.
Indiquez le nom de votre projet (TD8) dans la barre de texte.

Activer assert dans votre machine virtuelle Java

Vérifier que les assert's sont activés en exécutant le programme TestAssert.java. En cas de problème, suivez la procédure ci-dessous dans Visual Studio Code: tapez la combinaison de touches [Ctrl]+[,] (la second touche c'est `virgule'), indiquez vm args dans la barre de recherche. L'item Java>Debug>settings: Vm Args apparaît avec une barre de texte dans laquelle vous devez écrire -ea (pour enable asserts).

Consignes de programmation

Nommez les classes, variables et méthodes exactement comme le demande l'énoncé.

Pour des questions relatives à la syntaxe de Java, consultez ce mémento.

Documentation

Pour obtenir la description d'une classe Java standard, consultez internet. Il suffit souvent d'effectuer une recherche en indiquant Java suivi du nom de la classe dont vous souhaitez la documentation (e.g. Java LinkedList ou Java Array).

La documentation officielle (internet) est ici : Java 11.

Avertissement : tout votre code doit être écrit dans le fichier TD8.java

Afin de minimiser les risques d'erreurs de manipulation lors des dépôts de fichiers, toutes les classes que vous avez à modifier sont réunies dans un même fichier TD8.java que vous devez déposer après chaque question.

On rappelle néanmoins qu'en dehors de circonstances exceptionnelles, on écrit plutôt des classes différentes dans des fichiers différents, tant pour la lisibilité du code que pour l'efficacité de la compilation.

But

Implémenter le tri fusion en place de listes chaînées génériques, et l'appliquer au calcul de la distribution des mots d'un texte (fonction qui renvoie le nombre d'apparitions d'un mot dans un texte), et au calcul d'une valeur médiane d'un ensemble de valeurs numériques.

À télécharger

Extraire le contenu du fichier src.zip dans le répertoire src du projet.
Extraire le contenu du fichier text.zip à la racine du projet.

1 Listes chaînées

La classe Singly<E>, écrite dans le fichier TD8.java, implémente les listes chaînées d'objets de la classe E. On choisit de représenter la liste vide par la valeur null. Chaque objet a deux champs publics :

E element, le contenu d'un maillon de la chaîne ;
Singly<E> next, le reste de la chaîne.

La classe Singly<E> offre un constructeur

Singly(E element, Singly<E> next)

ainsi que d'autres méthodes utilisées dans les tests, que vous pouvez ignorer.

Question 1 : Complétez les méthodes

static<E> int length(Singly<E> l) qui renvoie la longueur de son argument.

StackOverflowError

static<E> Singly<E> split(Singly<E> l) qui coupe la liste non vide l en deux moitiés égales et renvoie la seconde moitié. En particulier, la taille de la liste l passée en argument est réduite de moitié. Par convention, si la longueur de la chaîne est impaire, la première moitié contient un élément de plus que la seconde.
La méthode split travaille en place : on parcourt la moitié de la liste et on renvoie le contenu du champ next de l'élément sur lequel on s'est arrêté, tout en mettant la valeur de ce même champ à null, ce qui a pour effet de « couper » la liste.
Là encore, on écrira une boucle plutôt qu'une méthode récursive.

Testez votre code en exécutant le fichier Test1.java.

Déposez le fichier TD8.java :

2 Tri fusion en place de listes chaînées de chaînes de caractères

Nous allons maintenant manipuler des listes de chaînes de caractères, autrement dit des objets de la classe Singly<String>.

2.1 Principe du tri fusion en place

La fusion en place (merge) de deux listes chaînées ordonnées l1 et l2 se fait sans créer ni détruire de cellules. Comme le suggère l'illustration qui suit, l'algorithme ne fait que modifier, au besoin, les pointeurs qui indiquent les cellules suivantes. En particulier, les listes l1 et l2 sont détruites.

2.2 Implémentation

Les listes chaînées l1 et l2 sont deux « réserves » dont on « prend » les éléments pour les « mettre » dans une liste auxiliaire result (c'est-à-dire un pointeur vers la tête de la liste qu'il faudra renvoyer). L'algorithme est donc le suivant :

Initialisation :

Si l'une des « réserves » est vide on renvoie l'autre,
sinon, on initialise une liste chaînée result dans laquelle on « met » le plus petit des éléments l1.element et l2.element. On crée aussi une variable last qui, au début de chaque itération, doit pointer vers le dernier maillon de la liste result.

Itération :

Tant qu'aucune des « réserves » n'est vide, on « prend » le plus petit des éléments l1.element et l2.element pour le « mettre » à la fin de la liste result,
et dès que l'une des deux « réserves » est vide, on s'arrête en renvoyant la concaténation de la liste result et de l'autre « réserve ».

Indication : « prendre » le premier élément d'une liste x pour le « mettre » à la fin d'une liste result dont le dernier maillon est pointé par last se fait en modifiant quatre pointeurs, comme le suggère le dessin ci-dessous. En particulier, vous ne devez pas créer de nouvelles cellules, c'est-à-dire ne pas utiliser d'instructions new Singly<String>.

Attention : bien que logiquement équivalents, les tests length(l) == 0 et l == null n'ont pas la même complexité algorithmique: faites le bon choix!

Question 2.2 : Dans la classe MergeSortString complétez les méthodes statiques suivantes :

static Singly<String> merge(Singly<String> l1, Singly<String> l2) réalise la fusion de deux listes chaînées ordonnées selon l'algorithme décrit ci-dessus. En particulier, les deux listes passées en argument sont détruites. On rappelle que les chaînes de caractères doivent être comparées au moyen de la méthode compareTo. Pour ne pas provoquer de débordement de pile (i.e. StackOverflowError), on écrira une boucle plutôt qu'une méthode récursive.

static Singly<String> sort(Singly<String> l) effectue le tri fusion en place de la liste passée en argument. Cette dernière est donc détruite. Cette fois, on peut sans problème écrire une méthode récursive, car la taille de la liste est divisée par deux à chaque fois.

Notez que cette classe ne contient que des méthodes statiques.

Exécutez le fichier Test22.java qui teste les méthodes merge et sort.

Déposez le fichier TD8.java :

2.3 Application : nombres d'apparitions des mots dans un texte

Chaque objet de la classe Occurrence possède les champs :

String word
int count

Question 2.3 : Dans la classe Occurrence, complétez la méthode

static Singly<Occurrence> count(Singly<String> l)

qui renvoie la liste des mots présents dans une liste avec leur multiplicité. On commencera par trier la liste passée en argument, afin que les mots identiques se retrouvent consécutifs. Aucun ordre n'est spécifié concernant la liste renvoyée. Testez votre code en exécutant le fichier Test23.java.

Déposez le fichier TD8.java :

3 Tri fusion en place de listes chaînées quelconques

On peut trier les éléments d'une liste dès lors qu'ils sont totalement ordonnés, autrement dit dès que leur classe implémente l'interface Comparable.

3.1 Implémentation générique

Question 3.1 : Adapter le code de la classe MergeSortString pour compléter les méthodes suivantes dans la classe MergeSort :

static<E extends Comparable<E>> Singly<E> merge(Singly<E> l1, Singly<E> l2)
static<E extends Comparable<E>> Singly<E> sort(Singly<E> l)

Exécutez le programme contenu dans le fichier Test31.java pour tester les méthodes génériques merge et sort.

Déposez le fichier TD8.java :

3.2 Application : les mots les plus fréquents

Question 3.2 : À l'aide de la méthode générique sort (qui trie les éléments d'une liste dans l'ordre croissant) complétez les méthodes suivantes dans la classe Occurrence :

static Singly<Occurrence> sortedCount(Singly<String> l) qui renvoie la liste des mots présents dans le texte avec leur multiplicité de sorte que les mots les plus fréquents (c'est-à-dire ceux de plus grande multiplicité) soient en début de liste. En outre, à multiplicité égale, on veut que les mots apparaissent dans l'ordre lexicographique.

Pour cela il faut compléter, dans la classe Occurrence, la méthode

public int compareTo(Occurrence that) qui renvoie une valeur strictement négative (resp. positive) lorsque this est strictement plus « petit » (resp. « grand ») que that, et zéro uniquement lorsque this et that sont égaux. Il faut ici interpréter « petit/grand » en fonction de l'ordre dans lequel on veut que les occurrences soient rangées dans la liste.

Attention : l'entête class Occurrence implements Comparable<Occurrence> indique au compilateur que les objets de la classe Occurrence sont ordonnés.

Testez votre code en exécutant le programme contenu dans le fichier Test32.java. L'exécution du test nécessite quelques secondes.

Déposez le fichier modifié TD8.java :

3.3 Application : valeur médiane d'une liste de flottants

On se propose d'appliquer maintenant notre tri générique dans un contexte différent.

Un flottant m est une valeur médiane d'une liste de flottants lorsque :

la moitié (au moins) des éléments de la liste est supérieure ou égale à m et
la moitié (au moins) des éléments de la liste est inférieure ou égale à m.

On donne la classe Pair.java.

Question 3.3 : Dans la classe Median, complétez la méthode

static Pair<Double> median (Singly<Double> data)

qui renvoie l'intervalle des médianes possibles sous la forme d'une paire. Si la liste est vide, la méthode renvoie la paire dont les deux composantes sont égales à la valeur spéciale Double.NaN (un acronyme pour «Not a Number»). Testez votre code en exécutant le programme contenu dans le fichier Test33.java.

Déposez le fichier TD8.java :