Discussion :

[Premium]

Bonjour,

j'aurais besoin d'aide pour coder la fonction 6) car je n'y arrive pas.
Quelqu'un pourrait-il m'indiquer la manière de procéder?

Merci

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

[had35]

L'idée, c'est que tu as une structure à deux dimensions. Mais cet aspect doit être encapsulé.

Il faut récupérer d'abord l'itérateur de la SortedMap (keySet().iterator()) dans laquelle chaque pair a pour clé un nombre correspondant à la priorité dans la file d'attente et une valeur correspondant à une liste.

On récupère donc les listes leur ordre de priorité, et pour chacune d'entre elles on récupère l'objet ListIterator qui nous fournira les objets référencés dans l'ordre de leur ajout. La classe interne qui implemente Iterator doit donc avoir une variable d'instance pour l'objet ListIterator courant.

[Premium]

L'idée, c'est que tu as une structure à deux dimensions. Mais cet aspect doit être encapsulé.

Il faut récupérer d'abord l'itérateur de la SortedMap (keySet().iterator()) dans laquelle chaque pair a pour clé un nombre correspondant à la priorité dans la file d'attente et une valeur correspondant à une liste.

On récupère donc les listes leur ordre de priorité, et pour chacune d'entre elles on récupère l'objet ListIterator qui nous fournira les objets référencés dans l'ordre de leur ajout. La classe interne qui implemente Iterator doit donc avoir une variable d'instance pour l'objet ListIterator courant.

Salut,

est-ce que tu pourrais m'indiquer comment ça se passe au niveau du code ?

[had35]

La partie qui relève de ton problème n°6 doit être résolu avec la classe interne qui implémente Iterator :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
private class TonIterateur implements Iterator<String> {
     private LinkedList<String> list = null;
     private ListIterator<String> listIterator;
     private final Iterator<? extends LinkedList<String>> mapIterator;
 
     private TonIterateur(SortedMap<Integer, ? extends LinkedList<String> map) {
          mapIterator = map.keySet().iterator();
          listIterator = mapIterator.next().iterator();
     }
     public boolean hasNext() {
          if(listIterator.hasNext())
               return true;
          else if(!mapIterator.hasNext())
                    return false;
          else {
               listIterator = mapIterator.next().iterator();
               return list.hasNext();
          }
     }
 
     public String next() {
          if(! listIterator.hasNext())
               listIterator = mapIterator.next().keySet().iterator();
          return listIterator.next();
     }
}

Ca donne un truc comme ça. Il se peut qu'il y ait des étourderies car j'ai écris le code dans l'éditeur de texte du site Mais l'idée est là.

[EDIT] En l'occurrence, il y avait au moins une erreur pour l'initialisation de listIterator que j'ai corrigé

[Premium]

Merci had35 pour le code
Je voudrais savoir que signifie ? extends ... dans Iterator<? extends LinkedList<String>>

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.

Le fait de dire qu'une classe implémente Iterable, cela signifie qu'on peut utiliser les boucles for each, c'est bien cela ?
Si c'est le cas, je voudrais savoir pourquoi il m'est possible d'utiliser les for each pour des tableaux d'entier, ... sans avoir à indiquer que la classe implémente Iterable

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

Il me suffit de remplacer tous les String et Integer par un E et un F (par example) dans tous le code ?

[had35]

Je voudrais savoir que signifie ? extends ... dans Iterator<? extends LinkedList<String>>

C'est une syntaxe qui permet de spécifier une relation d'héritage pour le type générique, ainsi tu peux passer en argument une instance de LinkedList<String> ou d'une sous-classe.

Le fait de dire qu'une classe implémente Iterable, cela signifie qu'on peut utiliser les boucles for each, c'est bien cela ?
Si c'est le cas, je voudrais savoir pourquoi il m'est possible d'utiliser les for each pour des tableaux d'entier, ... sans avoir à indiquer que la classe implémente Iterable

La possibilité d'utiliser foreach avec les classes iterables est accessoire et relève de la syntaxe du langage. L'essentiel (l'architecture du code) est beaucoup plus simple : Iterable est une interface qui déclare une méthode iterator().

Il me suffit de remplacer tous les String et Integer par un E et un F (par example) dans tous le code ?

Ce que tu veux dire, c'est si tu peux adapter le code pour en faire une classe template ? Oui, sans problème.

[Premium]

La partie qui relève de ton problème n°6 doit être résolu avec la classe interne qui implémente Iterator :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
private class TonIterateur implements Iterator<String> {
     private LinkedList<String> list = null;
     private ListIterator<String> listIterator;
     private final Iterator<? extends LinkedList<String>> mapIterator;
 
     private TonIterateur(SortedMap<Integer, ? extends LinkedList<String> map) {
          mapIterator = map.keySet().iterator();
          listIterator = mapIterator.next().iterator();
     }
     public boolean hasNext() {
          if(listIterator.hasNext())
               return true;
          else if(!mapIterator.hasNext())
                    return false;
          else {
               listIterator = mapIterator.next().iterator();
               return list.hasNext();
          }
     }
 
     public String next() {
          if(! listIterator.hasNext())
               listIterator = mapIterator.next().keySet().iterator();
          return listIterator.next();
     }
}

Ca donne un truc comme ça. Il se peut qu'il y ait des étourderies car j'ai écris le code dans l'éditeur de texte du site Mais l'idée est là.

[EDIT] En l'occurrence, il y avait au moins une erreur pour l'initialisation de listIterator que j'ai corrigé

Tu as implémenté les méthodes de la classe Iterator<String>, c'est à dire next et hasNext mais comment implémente-t-on la méthode iterator() qui est demandé dans l'exo ?

[had35]

En faisant tout simplement :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
public class TaFile implements Iterable<T> {
     private SortedMap<Integer, ? extends LinkedList<T> map; //contient les éléments de la file

     public Iterator<T> iterator() {
          return new TonIterateur(map);
     }

     private class TonIterateur implements Iterator<T> {
          [...]
     }
}

Je crois que tu as besoins de jeter un petit coup d'oeil aux tutoriaux Java