Une
file à priorités gère des objets ayant un certain niveau de priorité (un entier positif ou nul). PLusieurs objets peuvent avoir un même niveau de priorité. Les objets de même priorité sont gérés par une file d'attente
FIFO. Dans cette file, ils sont classésselon leur ordre d'arrivée. Les objets seront de type String.
On utilisera pour gérer chaque file d'attente représentant les objets ayant un certain niveau de priorité, une
LinkedList<String>. Les éléments avec la plus haute priorité sortent de la file à priorité en premier. En cas d'égalité de priorité, le premier entré est le premier sorti. Par exemple, si les éléments suivants sont entrés dans une file à priorités q avec les priorités donné comme premier argument,
q.add(1,"Maxime");
q.add(3,"Pierre");
q.add(4,"Paul");
q.add(1,"Alexandre");
ils sont enlevés dans l'ordre suivant :
"Paul", "Pierre", "Maxime", "Alexandre"
On se propose d'implémenter une file à priorité dans une classe dont le nom est
MultiLevelQueue et qui contient un membre d'une classe implémentant
SortedMap<Integer, LinkedList<String>>, (par exmple
TreeMap<Integer, LinkedList<String>>). La clé de la table (ou map) est la priorité, et la valeur associée à la clé est une file d'attente FIFO contenant les objets qui ont cette priorité.
Par exemple, les insertions précédentes donnent à la file à priorité la forme schématique suivante, par ordre de priorité décroissante,
priorité : file d'attente FIFO (premier entré à gauche)
--------------------------
4: [Paul]
3: [Pierre]
1: [Maxime, Alexandre]
1)Ecrire un constructeur
MultiLevelQueue()qui initialise une file à priorité vide.
2)Ecrire une méthode
List<String> get(int priority) qui renvoie la liste des éléments dont la priorité est donnée en argument.
3)Ecrire une méthode
void add(int priority, String item) qui ajoute un objet item de priorité
priority.
4)Reprendre le cas précédent en traitant le cas ou priority a une valeur interdite (<0). On utilisera une exception appropriée.
5)Ecrire une méthode String remove() qui enlève un retourne l'élément qui doit sortir. La méthode retourne null si la file à priorité est vide.
Attention : les file d'attente dans
TreeMap sont non vides. Ainsi, si l'on retire le dernier élement d'une file d'attente de priorité priority, on retire aussi l'entrée de la clé priority de TreeMap.
6)Ecrire une méthode
iterator() pour les files à priorités, avec une classe interne anonyme impélmentant
Iterator<String>, qui fournit une itérateur pour une file à priorité. (On pourra créer une classe nommée si l'on ne connait pas les classes anonymes).
On pourra utiliser des itérateurs d'ensembles de type
Iterator<Integer> et des itérateurs de listes de type
ListIterator<String>.
L'itérateur devra donner les éléments dans
l'ordre croissant de priorité. A niveau de priorité égal, l'ordre sera premier entré, premier sorti. Sur l'exemple on obtiendra l'ordre suivant :
Maxime Alexandre Pierre Paul
On implémentera la méthode
void remove() pour dire qu'elle n'est pas supportée.
7)On ajoute le fait que la classe MultiLevelQueue() implémente l'interface
Iterable<String>. Comment peut-on utiliser cette propriété? Donner un exemple.
8)Générifier les codes précédents pour que, dans la file à priorité, les priorités soient des clés qui ne sont pas obligatoirement Integer, et les éléments dans les files FIFO ne sont plus obligatoirement des String
Partager