Ubuntu-fr

Robinho

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

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

gene69

Re : File à priorité

http://fr.wikipedia.org/wiki/Tri_par_tas
http://java.sun.com/j2se/1.4.2/docs/api … rator.html

apres c'est du java... j'ai pas envie de m'y plonger.

Ce que j'aime dans l'algorythmie c'est l'emploie de mot français. Ca permet de comprendre ce qu'on fait sans avoir à réfléchir à ce que l'on fait.

bonne chance pour ton exercice.

---

Quand le berger est lâche, le loup chie de la laine.
A (draft) guide to UFO Alien-Invasion

Robinho

Re : File à priorité

Bonjour,

voici ce que j'ai fait mais ça n'est pas bon
Si quelqu'un pouvait m'indiquer comment faire ?

Merci

public class MultiLevelQueue{
  private SortedMap<Integer, LinkedList<String>> map;
   
   class MonIterateur implements Iterator<String> {
     private Iterator<String> itString;
     private ListIterator<String> listIterator;

     private MonIterateur() {
          listIterator = map.values().iterator();
     }
     public boolean hasNext() {
          return listIterator.hasNext();
     }

     public String next() {
          if(listIterator.hasNext())
             String s = listIterator.next();
             return s;
     }
  }
}

gene69

Re : File à priorité

je comprend pas bien la méthode next revoie une chaine et pas un objet...

MonIterateur() ne renvoie rien? même pas une exception?

     public String next() {
          if(listIterator.hasNext())
             String s = listIterator.next();
             return s;
}

nononononon
pourquoi creer une chaine intermédiare?

public String next() {
          if(listIterator.hasNext()){
             return listIterator.next();
          }
          else { 
            throw NoIteratorException e
          } 
}

---

Quand le berger est lâche, le loup chie de la laine.
A (draft) guide to UFO Alien-Invasion