Unité IN3S02 - TP5
Enoncé

Durée : 3 h

1- OBJECTIFS

• Savoir définir et gérer des listes chaînées
• Savoir utiliser un itérateur pour parcourir une collection d'objets

2- TRAVAIL A REALISER

Nota : le travail demandé doit être terminé, en séance ou en hors séance.

2.1- Créer un répertoire de travail

Créer un répertoire IN3S02-tp5 à la racine de votre compte. C'est dans ce répertoire que devront être stockés tous les programmes Java et exercices relevant de ce tp.

2.2- Exercice : projet "queue"

Une file d'attente est une liste d'attente à discipline "premier entré = premier sorti", qui est typiquement utilisée comme mémoire tampon de communication entre deux processus fonctionnant en asynchronisme à des vitesses différentes.

                      --------------------------
   ajouts  -->       |     |     |     |     |     |        --> retraits
                      --------------------------

L'ordre des éléments dans une file d'attente ordinaire est l'ordre d'arrivée dans la file d'attente.

Soient ajouter et retirer les fonctions qui permettent d'ajouter, respectivement retirer, un élément d'une liste d'attente et renvoient la file d'attente ainsi modifiée. Le comportement d'une file d'attente se caractérise par les propriétés logiques suivantes (spécification fonctionnelle, pas en syntaxe Java !) :

• Quels que soient f une file d'attente et e un élément :
• précondition(retirer(f)) = non estVide(f)
• estVide(f) = ( longueur(f) = 0 )
• longueur(ajouter(f, e)) = longueur(f) + 1
• si ( non estVide(f) ) alors longueur(retirer(f)) = longueur(f) - 1
• retirer(ajouter(f, e)) = si ( estVide(f) ) alors file vide sinon ajouter(retirer(f),e)

On se propose de définir et gérer une file d'attente d'élements de type Object. La liste d'attente sera implantée sous forme d'une liste chaînée de type LinkedList.

2.2.1- File d'attente simple

Dans BlueJ, créer un nouveau projet de nom queue dans le répertoire IN3S02-tp5 prélablement défini.

Prendre connaissance de la classe LinkedList (y compris des méthodes héritées) puis écrire en Java une classe Queue répondant aux spécifications suivantes :

• finalité : représenter une liste d'attente
• attribut : un champ list de type LinkedList
• constructeur : génère une file d'attente vide
• méthodes :
• une fonction length qui renvoie la longueur de la file d'attente
• une fonction isEmpty qui renvoie true ssi la file d'attente est vide
• une procédure add qui ajoute à la file d'attente un objet de type Object passé en paramètre
• un fonction retrieve qui extrait et renvoie le premier élément de la file d'attente, ou null si elle est vide
• une procédure clear qui vide la liste d'attente
• une procédure print qui affiche les éléments de la liste d'attente par rang croissant sous la forme : "rang : élément". Pour parcourir la liste, on utilisera un itérateur de type ListIterator (voir méthode listIterator de la classe LinkedList)
• une procédure createRandomQueue qui produit une file d'attente courante d'éléments de type String, chaque élément étant ainsi défini : rang de création + "#" + entier naturel aléatoire. Le nombre d'éléments sera fourni en paramètre à la procédure. Cette méthode servira pour les tests et la mise au point. Elle utilisera la méthode add préalablement définie

Compiler et tester.

2.2.2- File d'attente avec priorités 

On se propose de compléter la classe Queue préalablement définie afin que l'on puisse gérer des files d'attente avec priorités.

Avant de la modifier le classe Queue, la sauvegarder dans SimpleQueue.java

Dans une file d'attente avec priorités, chaque élément est doté d'une priorité qui est susceptible d'affecter son rang dans la liste d'attente. L'ordre des éléments dans une file d'attente avec priorités dépend non seulement de leur ordre d'arrivée dans la file mais également de leur priorité.

Supposons les priorités codées par un entier naturel, la priorité maximale étant 0. Soient deux éléments e1 et e2 de priorités respectives p1 et p2, arrivés aux instants respectifs t1 et t2.  Leur rang relatif dans la liste d'attente est défini par :
rang(e1) < rang(e2)   ssi   ( p1 < p2 ) ou ( (p1 = p2) et (t1 < t2) )

Ecrire en Java une classe Data répondant aux spécifications suivantes :

• finalité : repésenter un couple {objet, priorité}
• attributs : un champ object de type Object et un champ priority de type entier
• constructeur : initialise les champs aux valeurs de ses paramètres
• méthodes : fonctions d'accès et modificateurs permettant de gérer la valeur chaque attribut

Modifier la classe Queue afin de pouvoir gérer une liste d'attente avec priorités d'objets de type Data. Ces modifications concernent principalement les méthodes suivantes :

• méthode add : prend en paramètres un objet de type Object et sa priorité, en constitue un objet de type Data, et l'insère dans la file d'attente de façon à satisfaire la relation d'ordre définie ci-dessus. Pour parcourir la liste, on utilisera un itérateur de type ListIterator.
• méthode retrieve : extrait le premier objet de la file d'attente et renvoie l'élément de type Object qu'il contient, ou null si la file d'attente est vide
• méthode print : affiche les éléments de la liste d'attente par rang croissant sous la forme : "rang : priorité élément".
• méthode createRandomQueue : produit une file d'attente courante d'éléments de type String, chaque élément ayant pour valeur son rang de création et une priorité tirée aléatoirement dans le segment [0,4] ; le nombre d'éléments sera fourni en paramètre à la procédure.

Compiler et tester.

2.2.3- Terminer l'exercice

Sauvegarder le projet queue et le fermer.

2.4- Terminer la séance

Si pas fait antérieurement, sauvegarder les projets ouverts, puis fermer BlueJ.

Si besoin, envoyer par mél à votre binôme, en fichiers attachés, tous les programmes *.java développés sous IN3S02-tp5.

Se déloger.