implémenter un Iterator spécial

**aertys** · 18/11/2018, 18h10

bonjour,

je dois rendre un TP avant ce soir minuit. Il y a 14 questions et je n'en suis qu'à la question 2.
Je n'ai pas eu de cours sur ce sujet et galère

Définissez une classe HashMultiSetIterator qui implante Iterator<T> en respectant les spécifications suivantes (nous conseillons de définir HashMultiSetIterator comme une classe interne à HashMultiSet<T>
- Si un élément e apparaît n fois dans un multi-ensemble, alors l’itérateur retournera l’élément e pour les n prochains appels à next(), avant de passer à l’élément suivant.
- Afin d’élaborer notre itérateur de multi-ensembles, nous nous appuierons par délégation sur un itérateur parcourant la collection Map<T,Integer> au cœur de l’implantation de HashMultiSet<T>.
Un appel à next() de l’itérateur de multi-ensemble ne se
traduira pas systématiquement par un appel à next() de l’itérateur sous-jacent : il faut tenir compte des nombres d’occurrences.

voici ce que j'ai fait pour la question 1 :

Code java :

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
package pobj.multiset;
 
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
 
public interface MultiSet<T> {
	public boolean add(T e, int count);
	public boolean add(T e);
	public boolean remove(Object e);
	public boolean remove(Object e, int count);
	public int count(T o);
	public void clear();
	public int size();
}
 
public class HashMultiSet<T> implements MultiSet<T> {
 
    /**
     * Contient les donnees du multi ensemble.
     */
    private Map<T, Integer> memory;
 
    /**
     * Constructeur par defaut.
     */
    public HashMultiSet() {
        memory = new HashMap<T, Integer>();
    }
 
 
    /**
     * Constructeur par copie.
     * @param data donnees a copier
     */
    public HashMultiSet(Collection<T> data) {
        memory = new HashMap<T, Integer>();
 
        //nous parcourons la collection, et mettons a jour notre multi-ensemble
        for(T element : data){
 
            Integer newOccur = 1;
            Integer occur = memory.get(element);
            if(occur != null){
                //si un element est deja connu, alors nous mettons a jour son nombre d'occurence
                //pour cela on recupere d'abord son occurence actuelle (qui n'est pas nulle)
                newOccur = newOccur + occur;
            }
            //sinon cela veut dire que c'est un nouvel element
            //donc on met une occurence (par defaut newOccur vaut 1);
 
            memory.put(element, newOccur);
        }
    }
 
    /**
     * {@inheritDoc}
     */
    @Override
    public boolean add(T e, int count) {
        //on recupere d'abord le nombre d'occurence deja stockee
        Integer occur = memory.get(e);
        Integer newOccur = count;
 
        if(occur!= null) {
            newOccur = newOccur + occur;
        }
 
        memory.put(e, newOccur);
        return true;
    }
 
    /**
     * {@inheritDoc}
     */
    @Override
    public boolean add(T e) {
        //on recupere d'abord le nombre d'occurence deja stockee
        Integer occur = memory.get(e);
        Integer newOccur = 1;
        if(occur!= null) {
            newOccur += occur;
        }
        memory.put(e, newOccur);
 
        return true;
    }
 
 
    /**
     * {@inheritDoc}
     */
    @Override
    public boolean remove(Object e) {
        //on recupere d'abord le nombre d'occurence deja stockee
        Integer occur = memory.get(e);
        boolean result = false;
 
        //seulement si le nombre d'occurence existe et qu'il est positif, on procede a la mise a jour
        if(occur != null) {
            //si il n'y avait qu'une occurence initialement, alors on suppriment l'element
            if(occur == 1){
                memory.remove(e);
 
                //on met a jour le "flag" result pour dire que l'operation s'est bien passee.
                result = true;
            }
            else if(occur > 1){
                //on decremente le nombre d'occurence
                occur--;
 
                //on n'oublie pas de mettre a jour l'occurence
                //voir "Alerte Unckeched cast" qui explique le warning a la ligne ci-dessous
                memory.put((T) e, occur);
 
                //on met a jour le "flag" result pour dire que l'operation s'est bien passee.
                result = true;
            }
 
        }
 
        return result;
    }
 
    /**
     * {@inheritDoc}
     */
    @Override
    public boolean remove(Object e, int count) {
        //on recupere d'abord le nombre d'occurence deja stockee
        Integer occur = memory.get(e);
        boolean result = false;
 
        //seulement si le nombre d'occurence actuel existe
        if(occur != null){
            //si la suppression d'occurence est positive
            occur =- count;
            if(occur > 0) {
                //on met à jour
                //voir "Alerte Unckeched cast" qui explique le warning a la ligne ci-dessous
                memory.put((T)e, occur);
            }
 
            //sinon on supprime l'element
            else {
                memory.remove(e);
            }
            result = true;
        }
        return result;
    }
 
    /**
     * {@inheritDoc}
     */
    @Override
    public int count(T o) {
        Integer occurence = memory.get(o);
        //on renvoie le nombre d’occurrences de l’objet e dans la collection (0 si l’objet n’est pas
        //dans le multi-ensemble)
        return (occurence == null) ? 0 : occurence;
    }
 
    /**
     * {@inheritDoc}
     */
    @Override
    public void clear() {
        //on vide juste en se basant sur la methode existante de HashMap.
        memory.clear();
    }
 
    /**
     * indique la taille du multi-ensemble, c’est-à-dire la somme des nombres d’occurrences
     * des éléments
     */
    @Override
    public int size() {merc
    	return memory.size;
    }
 
}
 
//

merci pour vos réponses sur comment je dois faire pour cette question

**joel.drigo** · 19/11/2018, 12h25

Salut,

En résumé, tu as une classe qui représente un compteur d'éléments, stockés dans une map. Pour un élément donné, on associe un compteur d’occurrences. On te demande d'implémenter un itérateur sur le contenu de cette classe qui a la caractéristique suivante :

si un élément se trouve associé à un compteur qui vaut plus que 1, la méthode next de l'itérateur va retourner successivement l'élément autant de fois que le compteur le dit.

Par exemple, prenons la map (l'attribut memory de ton implémentation) suivante :

elem1 = 3
elem2 = 2
elem3 = 1

Le résultat de l'itération sera (à l'ordre près) :

elem1, elem1, elem1, elem2, elem2, elem3

Puisque qu'il semble trop tard pour te répondre, je te propose une solution avec le raisonnement pour y arriver. On te précise en plus que tu dois déléguer à l'itérateur standard de l'attribut de type map. Ce qui veut dire que tu dois commencer par utiliser "cet" itérateur, sachant qu'une map en a trois : un itérateur sur les clefs (keyset), un sur les valeurs, un sur les entrées (entrySet()), qui est plus adapté pour itérer sur clefs (les éléments) et valeurs (les compteurs associés).

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
public class HashMultiSet<T> implements MultiSet<T>, Iterator<T> {
 
   public Iterator<T> iterator() {
 
            return new Iterator<T> {
 
                     Map.Entry<T,Integer> entryIterator = memory.entrySet().iterator(); // on créé l'itérateur à qui on va déléguer
 
                     public boolean hasNext() {
                          // à implémenter
                     }
 
                     public T next() {
                          // à implémenter
                     }
 
 
            }
 
 
   }
 
}

Il faut implémenter au moins 2 méthodes pour implémenter un itérateur (il y a aussi remove() également mais je ne sais pas si tu dois le faire ou pas).

hasNext() doit répondre vrai s'il reste encore quelque chose à itérer, c'est-à-dire qu'on peut appeler next() sans obtenir d'exception NoSuchElementException.

next() doit retourner le prochain élément.
Si on voulait simplement itérer sur les éléments (soit les clefs),

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
   public Iterator<T> iterator() {
 
            return new Iterator<T> {
 
                     Map.Entry<T,Integer> entryIterator = memory.entrySet().iterator(); // on créé l'itérateur à qui on va déléguer
 
                     public boolean hasNext() {
                          entryIterator.hasNext();
                     }
 
                     public T next() {
                          entryIterator.next().getKey();
                     }
 
 
            }

On n'aurait d'ailleurs pas vraiment besoin de l'entrySet, mais plutôt du keyset().

Maintenant, on sait qu'on doit retourner chaque élément, mais autant de fois que le compteur le dit : ceci veut dire qu'à un moment on va faire next(), ça va prendre le prochain élément, et que le coup suivant on va devoir peut-être renvoyer le même, ce qui veut dire qu'il va falloir le stocker entre deux appels de next(). Ensuite, il nous faudra pouvoir le renvoyer autant de fois que le compteur le dit, ce qui veut dire qu'il va falloir savoir combien de fois on la déjà retourner, donc stocker le compteur et faire soit une décrémentation soit une incrémentation pour compter. Par décrémentation, on économisera une variable.

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
 
public Iterator<T> iterator() {
 
            return new Iterator<T> {
 
                     Map.Entry<T,Integer> entryIterator = memory.entrySet().iterator(); // on créé l'itérateur à qui on va déléguer
                     T element; // permet de stocker l'élément
                     int compteur; // permet de compter
 
                     public boolean hasNext() {
                     }
 
                     public T next() {
                     }
 
            }

Ensuite, on voit qu'on a deux états :

on n'a pas encore appeler next() sur l'itérateur de délégation
on a appeler next()

Dans le premier cas, c'est l'itérateur de délégation qui nous fournit les retours de hasNext() et next(). Dans le second, c'est la dernière entrée obtenue tant qu'elle n'est pas consommée complètement (que le compteur n'est pas atteint). Pour savoir qu'on est dans le premier cas, on peut utiliser element et le fait qu'il soit null, pour savoir qu'on est dans cet état.

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
eturn new Iterator<T> {
 
                     Map.Entry<T,Integer> entryIterator = memory.entrySet().iterator(); // on créé l'itérateur à qui on va déléguer
                     T element; // permet de stocker l'élément
                     int compteur; // permet de compter (on décrementera jusqu'à 0 pour itérer sur le bon nombre d'éléments)
 
                     public boolean hasNext() {
                           if ( element==null ) {
                                // c'est par l'itérateur de délégation qu'on sait s'il reste des éléments
                                return entryIterator.hasNext();
                           }
                           else {
                                return compteur>0; // dans l'autre cas, c'est le compteur qui permet de savoir s'il reste des éléments sur lesquels itérer
                           }
                     }
 
                     public T next() {
                           T next = null; // le prochain élément à retourner  
                           if ( element==null ) {
                                // on n'a pas encore d'élément courant, on n'en prend un
                                Map.Entry<T,Integer> nextEntry = entryIterator.next();
                                element=nextEntry.getKey();
                                compteur=nextEntry.getValuer();
                                // on va retourner l'élément, donc on le compte
                                next = element;
                                compteur--;
                           }
                           else {
                                // on a un élément courant, c'est lui qu'on va retourner
                                next = element;
                                compteur--;
                           }
                           if ( compteur<=0 ) {
                               // la prochaine fois, cet élément ne doit plus être retourné, mais en doit repartir sur l'itérateur de délégation
                               // c'est en plus le fait de le faire ici qui garanti que hasNext() retournera bien false au prochain appel si on est sur le dernier élément (element==null vrai)
                               element=null;
                           }
                           return next; 
                     }
 
            }

On ne gère pas le cas cas limite qui correspond à l'association element=0. Toutefois, il y a quelque chose qu'on devrait gérer pour être cohérent avec une map : si un compteur est modifiée pendant qu'on itère, on devrait soulever une exception (ConcurrentModificationException). On aura une lorsqu'on appelle .next() ou hasNext() sur entryIterator et qu'on a modifié le MultiSet (par add, remove, clear, etc). On n'a pas accès aux variables internes qui sont utilisées par une HashMap. On pourrait mettre en place le même mécanisme (basé sur un compteur qu'on incrémente dans toutes les méthodes de modification et qu'on sauve dès qu'on créé l'itérateur, et, donc qu'il suffit de comparer (la valeur stocker au moment où on créé l'itérateur et la valeur actuelle qui est modifiée à chaque fois qu'on modifie la map).

Enfin, on peut simplifier légèrement, pour éviter deux lignes de code dupliquées, (on perd juste la progression du raisonnement) en faisant :

Code :

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

1
2
3
4
5
6
7
8
                 if ( element==null ) {
                                // on n'a pas encore d'élément courant, on n'en prend un
                                Map.Entry<T,Integer> nextEntry = entryIterator.next();
                                element=nextEntry.getKey();
                                compteur=nextEntry.getValuer();
                           }
                           next = element;
                           compteur--;

**aertys** · 24/11/2018, 16h02

Merci
Cela m'a bien servi

J'ai réussi à faire 2 questions sur les 14.

Aujourd'hui je galère sur python

implémenter un Iterator spécial

avec Java

Discussions similaires

Partager

Partager