File à priorité

Version imprimable

14/08/2006, 13h12
Premium

File à priorité

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

Citation:

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
14/08/2006, 14h32
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.

;)
14/08/2006, 16h07
Premium

Citation:

Envoyé par 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.

;)

Salut,

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

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

Code:

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 :aie: 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é

14/08/2006, 17h32
Premium

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

Citation:

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

Citation:

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 ?
14/08/2006, 18h11
had35

Citation:

Envoyé par Premium

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.

Citation:

Envoyé par Premium

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().

Citation:

Envoyé par Premium

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.

Citation:

Envoyé par 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:

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();
     }
}

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 ?

En faisant tout simplement :

Code:

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 :aie:

15/08/2006, 14h38
had35

Tu as peut-être remarqué qu'il y a une autre erreur dans la classe TonIterateur. Je récupère l'ensemble des clés (keySet()) de la SortedMap, alors que c'est l'ensemble des valeurs qui nous intéresse (values()).
15/08/2006, 15h11
Premium

Est-ce que tu pourrais m'expliquer le code que tu avais écrit?
Je ne comprends pas très bien comment ça fonctionne.
Si tu pouvais mettre des commentaires dans le code ou m'expliquer ?
Merci

Bon, j'ai ajouté des commentaires. Il faut que tu saisisse bien qu'un itérateur permet de parcourir une collection. Ici, TonIterateur permettra de parcourir la SortedMap qui contient elle-même plusieurs collections triées par priorité (j'ai considéré que le nombre le plus petit correspondait à la priorité la plus forte) :

Code:

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
28
29
30
31
32
33
34
35
36
37
38
private class TonIterateur implements Iterator<String> {
     private LinkedList<String> list = null; //ne sert à rien, tu peux l'enlever
     private ListIterator<String> listIterator; //liste en cours de lecture correspondant à un niveau de priorité
     private final Iterator<? extends LinkedList<String>> mapIterator;//permet de parcours les listes dans l'ordre de priorité

     private TonIterateur(SortedMap<Integer, ? extends LinkedList<String> map) {
          mapIterator = map.values().iterator();//c'est là que j'avais fait une erreur
          listIterator = mapIterator.next().iterator();
     }

     /*
      * Doit indiquer s'il reste des éléments dans la SortedMap
      */
     public boolean hasNext() {
          if(listIterator.hasNext())
               return true; //on retourne true si la liste en cours a encore des éléments

          else if(!mapIterator.hasNext())//sinon on vérifie que la SortedMap a encore des listes non lues
                    return false; //s'il n'y en a plus, c'est qu'on a parcouru toute la SortedMap

          else {//S'il y a encore une liste, on réinitialise listIterator pour la lire
               listIterator = mapIterator.next().iterator(); //il y a peut-être une autre erreur qui se niche ici car mapIterator.next() est aussi appelé dans next()
               return list.hasNext();
          }
     }

     /*
      * Doit nous retourner l'élément suivant en tenant compte des critères de priorité
      * et d'ordre d'ajout
      */
     public String next() {
          if(! listIterator.hasNext()) //Si on a atteint la fin d'une liste
               listIterator = mapIterator.next()..iterator(); //on passe à la suivante

          return listIterator.next();//dans tous les cas, on retourne l'élément suivant de la liste en cours
     }
}

Je n'ai pas tenu compte du fait que tu voulais une liste FIFO. Il faudra donc sans doute que tu adaptes encore le code.