Problème iteration en java

Version imprimable

18/08/2018, 03h29
lvlarvin

Problème iteration en java
Bonjour,

je cherche a gérer une liste comme on le fait en C. Pour sauvegarder une position.
Faire quelque chose comme:
Code:

1 2 3 4 5 6 7 8 9 10 LinkedHashSet<A> ll=new LinkedHashSet<A>(); ll.add(a); ll.add(b); ll.add(c); Iterator<A> it1=ll.iterator(); Iterator<A> it2=it1; it1.next();
Ici avoir it1 sur le deuxième élément et it2 sur le premier.

Je me doute qu'il ne faut pas utiliser iterator.
Mais est-il possible de faire ca sans tous recopier dans un Object[] ou ArrayList?

Merci d'avance!
18/08/2018, 12h30
joel.drigo
Salut,

Citation:

Envoyé par lvlarvin

je cherche a gérer une liste comme on le fait en C.

C'est-à-dire, exactement ? Une liste simple, c'est à dire une liste chainée, c'est ça ?

Le principe de l'objet c'est que c'est sa conception qui définit sa gestion. Il est prévu pour être géré comme il l'est.

Citation:

Envoyé par lvlarvin

Pour sauvegarder une position.

C'est-à-dire ? Pouvoir retrouver la position qu'avait un élément après que l'ordre des éléments dans la liste ait changé ?
Code:

1 2 LinkedHashSet<A> ll=new LinkedHashSet<A>();
Un LinkedHashSet est un Set, pas une List. Une List est une collection à accès direct aux éléments par leur position. Un set une collection d'éléments sans accès direct et dont les éléments ne peuvent être en double (plusieurs éléments ajoutés au set étant "equals" entre eux n'apparaîtront qu'une fois (seulement l'un d'entre eux sera stocké dans un LinkedHashSet)).

Citation:

Envoyé par lvlarvin

Je me doute qu'il ne faut pas utiliser iterator.

Forcément, puisqu'il ne permet pas de connaître la position des éléments.
Code:

1 2 3 4 Iterator<A> it1=ll.iterator(); Iterator<A> it2=it1; it1.next();
Quand tu fais ça, l'Iterator référencé par it2 est aussi modifié, puisque c'est le même que celui référencé par it1.
Il est nécessaire de récupérer la valeur de retour de it1.next() à l'appel, car l'appel de cette méthode modifie l'état du curseur d'itération : il n'y a plus aucun moyen de la récupérer.
De plus, si tu changes l'ordre des éléments dans ll, l'Iterator n'est plus valide et tu obtiendras une exception en récupérant la valeur.

Citation:

Envoyé par lvlarvin

Mais est-il possible de faire ca sans tous recopier dans un Object[] ou ArrayList?

Si le but est de parcourir le LinkedHashSet en connaissant les positions des éléments, tu peux utiliser une variable supplémentaire qui représente cette position :
Code:

1 2 3 4 5 6 7 int index=0; for(A item : ll) { /** * traitement / index++; }
Si le but est de connaitre les positions à un instant t, une Map<A,Integer> :
Code:

1 2 3 4 5 Map<A,Integer> map = new HashMap<>(); int index=0; for(A item : ll) { map.put(item,index++); }
Tu peux connaître la position même après qu'elle ait changé dans le Set :
Code:

1 2 3 4 5 6 int index = 0; for(A item : ll ) { System.out.format("Ancienne position %d, Nouvelle position %d%n", map.getOrDefault(item,-1), index); index++ }
18/08/2018, 15h49
lvlarvin

Bonjour,

Merci de ta réponse.

Ce que je cherche a faire c'est reprendre le parcourt a partir d'une position mémorisé.
Et le faire sans avoir a repartir du début. Ni a recopier la collection dans un tableau et en mémoriser la position.

C'est ce que je voulais dire par comme en C. Puisque une liste est un pointeur sur une structure liste.

En théorie cela semble possible, mais est-ce qu'une méthode existe?

Merci!
18/08/2018, 17h42
joel.drigo
1. Est-ce que la structure doit être absolument un LinkedHashSet ?
2. Est-ce que la structure doit être absolument un Set ?
3. Autre question par rapport à la notion de position.
  Par exemple, si on a la liste (1,2,3,4,5), on stocke "la position de 3", puis la liste est modifiée pour obtenir (4,3,2,9) : le nouveau parcourt correspond à
  1. (2,9) (à partir de l'index 2)
  2. ou (3,2,9) ?
  Si elle modifiée pour (1,2,4,5), c'est-à-dire qu'on enlève 3, qu'est-ce qu'on fait ?
1. Si la réponse à la question 1 est oui, la solution peut passer éventuellement par un stream.
  
  La difficulté est de comment déterminer la "position". Si la position est déterminée par un entier (de 0 à taille-1):
  
  Code:
  
  set.stream().skip(position).forEach(consumer);
  
  S'il faut repartir d'un élément particulier, obtenu par exemple lors d'une précédente itération, il faudra itérer jusqu'à l'élément, puis continuer pour faire le traitement. Stocker l'élement donc, ou faire une petite classe qui gère ça.
  
  Éventuellement, il y a la solution de "simuler" un set avec un List (simplement empêche d'ajouter un élément s'il s'y trouve déjà), ce qui permet de repartir de la position qu'on veut. Et utiliser sublist().
2. Sinon, et si la réponse à la question 2 est oui, un TreeSet (voir sa méthode subset()), ou plus généralement un utiliser un NavigableSet, qui propose plus de richesse au niveau parcourt.
  Mais attention avec subset(). Si on a un set du type (1,2,3,4,5) et qu'on prend un subset (3,4,5), si on enlève 3, le subset devient (4,5) et on peut continuer à itérer dessus, malgré que l'élément supprimé ne s'y trouve plus.
3. Sinon, utiliser un List. Et utiliser sublist().
4. L'implémentation d'une liste chaînée simple est peut-être la solution (donc reproduire en Java l'équivalent de la liste simple en C). Faire éventuellement une classe implémentant Set pour gérer ça avec transparence.
  A voir dans quel algorithme on aurait besoin de ça et si la solution n'est pas ailleurs (plusieurs set, file, pile, queue, etc).
5. Chercher dans les Apache Commons s'il n'y a pas une structure adaptée (peut-être un SetUniqueList ?)
18/08/2018, 18h27
lvlarvin
Citation:
Envoyé par joel.drigo

Est-ce que la structure doit être absolument un LinkedHashSet ?
Est-ce que la structure doit être absolument un Set ?
Autre question par rapport à la notion de position.
Par exemple, si on a la liste (1,2,3,4,5), on stocke "la position de 3", puis la liste est modifiée pour obtenir (4,3,2,9) : le nouveau parcourt correspond à

(2,9) (à partir de l'index 2)
ou (3,2,9) ?

Si elle modifiée pour (1,2,4,5), c'est-à-dire qu'on enlève 3, qu'est-ce qu'on fait ?
La méthode doit fonctionner avec un HashSet et un HashMap. Donc un LinkedHashSet et LinkedHashMap me semblais un bon début de solution.
(C'est dommage NavigableSet a l'aire bien!)

La collection ne sera pas modifiée il s'agit simplement d'une lecture.

Je ne connais pas du tout le stream. Est-ce que .stream().skip(n) est en O(1)? (Sinon aucune différence avec repartir du début...)
Et peut on prélever notre n en O(1) ou dois-je mettre un compteur? (C'est un détail mais ça serais plus agréable.)

Merci!

Si ton set ne change pas pendant l'itération, la seule solution que je vois, hormis réécrire une classe de linkedhashset, c'est passer par de la réflexion, pour "cloner" l'itérateur.

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
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
import java.lang.reflect.Constructor;
import java.lang.reflect.Field;
import java.lang.reflect.InvocationTargetException;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.stream.Collectors;
import java.util.stream.Stream;
 
public class LinkedHashsetIteratorSaver {
 
	private static Class<?> IC = getIteratorClass("java.util.LinkedHashMap$LinkedKeyIterator");
	private static Class<?> MIC = getIteratorClass("java.util.LinkedHashMap$LinkedHashIterator");
	private static Class<?> getIteratorClass(String name) {
		try {
			return Class.forName(name);
		} catch (ClassNotFoundException e) {
			throw new RuntimeException(e);
		}
	}
 
	/**
         * Crée une copie de l'itérateur qui permet de recommencer l'itération même si on continue d'itérer sur celui passé en argumnt
         * @param iterator itérateur à copier
         * @param restartFromCurrent si true, on réintère à partir de la dernière valeur obtenur, sinon à partir de la prochaine et l'état est inchangé
         * @return
         */
	public static <T> Iterator<T> saveIterator(Iterator<T> iterator, boolean restartFromCurrent) {
		if ( !IC.isAssignableFrom(iterator.getClass()) ) {
			throw new IllegalArgumentException("Must be a LinkedHashSet iterator");
		}
 
		try {
			Object next = read("next",iterator);
			Object current = read("current",iterator);
			Object expectedModCount = read("expectedModCount",iterator);
			Object owner = read("this$0",iterator);
			Constructor<? extends Iterator> constr = iterator.getClass().getDeclaredConstructor(LinkedHashMap.class);
			constr.setAccessible(true);
			Object newiterator = constr.newInstance(owner);
			if ( restartFromCurrent && current!=null ) {
				set(newiterator, "next", current);
			}
			else {
				set(newiterator, "next", next);
			}
			set(newiterator, "expectedModCount", expectedModCount);
			return (Iterator<T>) newiterator;
		} catch (NoSuchFieldException | SecurityException | IllegalArgumentException | IllegalAccessException e) {
			throw new IllegalStateException(e);
		} 
		catch (InvocationTargetException | NoSuchMethodException e) {
			throw new IllegalStateException(e);
		}
		catch (InstantiationException e) {
			throw new IllegalStateException(e);
		}
 
	}
 
 
	private static void set(Object object, String name, Object value) throws NoSuchFieldException, SecurityException, IllegalArgumentException, IllegalAccessException {
		Field f = MIC.getDeclaredField(name); 
		f.setAccessible(true);
		f.set(object, value);
	}
 
	private static Object read(String name, Object object) throws NoSuchFieldException, SecurityException, IllegalArgumentException, IllegalAccessException {
		Field f = MIC.getDeclaredField(name); 
		f.setAccessible(true);
		return f.get(object);
	}
 
	public static void main(String[] args) {
		LinkedHashSet<Integer> set = Stream.iterate(0, x->x+1)
				                   .limit(10)
				                   .collect(Collectors.toCollection(LinkedHashSet::new));
 
		Iterator<Integer> iterator = set.iterator(); // un premier itérateur pour itérer sur le set
 
		Iterator<Integer> saved=null; // cet itérateur va permettre de recommencer l'itératiion à partir du suivant de 5
		Iterator<Integer> marked=null; // cet itérateur va permettre de recommencer l'itération à partir de 5
		System.out.print("Set: ");
		while(iterator.hasNext()) {
			int i = iterator.next();
			if( i==5 ) { // on a atteint 5
				saved = saveIterator(iterator, false); // itérateur pour recommencer à itérer à partir de l'élément courant de iterator, exclus
				marked = saveIterator(iterator, true); // itérateur pour recommencer à itérer à partir de l'élément courant de iterator, inclus
			}
			System.out.format("%d ",i);
		}
		System.out.println();
 
		System.out.print("Saved: ");
		while(saved.hasNext()) {
			int i = saved.next();
			System.out.format("%d ",i);
		}
		System.out.println();
 
		Iterator<Integer> marked2=null; // un itérateur qui va permettre de recommencer l'itération à partir de 7
		System.out.print("Marked: ");
		while(marked.hasNext()) {
			int i = marked.next();
			System.out.format("%d ",i);
			if( i==7 ) {
				marked2 = saveIterator(marked, true);
			}
		}
		System.out.println();
 
		System.out.print("Marked 2: ");
		while(marked2.hasNext()) {
			int i = marked2.next(); 
			System.out.format("%d ",i);
		}
		System.out.println();
 
	}
 
}

Résultat de l'exécution de la démo :

Citation:

Set: 0 1 2 3 4 5 6 7 8 9
Saved: 6 7 8 9
Marked: 5 6 7 8 9
Marked 2: 7 8 9

19/08/2018, 16h48
lvlarvin

Merci c'est parfait.

J'avais abandonné l'idée de cloner quand j'avais vu que c'était une interface.
Et je connaissais pas getDeclaredFields() ...

Bref, merci beaucoup!