Discussion :

[Tuxico]

Bonjour,

j'ai fait cette après-midi un petit programme sur une implémentation des listes chainées (un type abstrait) mais j'obtiens une erreur localisée mais que je ne comprends pas, si vous pouviez m'éclairer.

donc, le package se nomme list et contient:

- IntList (classe abstraite de réprésentation d'une liste chainée)
- List = implémentation de IntList
- MyIterator = implémentation d'un Iterator pour parcourir la liste
- TestIntList = un bête programme qui test les méthodes de List

les codes correspondants:
(les specs sont en anglais par habitude)

Intlist:

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
package list;
 
import java.util.*;
 
public abstract class IntList implements Iterable {
	// OVERVIEW: IntLists are immutable lists of Objects. A typical
	// IntList is a sequence [x1, ..., xn].
 
	// methods
	public abstract Object first() throws EmptyException;
 
	// EFFECTS: if this is empty, throws EmptyException;
	// else returns first element of this.
	public abstract IntList rest() throws EmptyException;
 
	// EFFECTS: if this is empty throws EmptyException else returns
	// the list containing all but the first element of this, in the
	// original order.
	public abstract MyIterator elements();
 
	// EFFECTS: returns a generator that will produce the elements of
	// this, each exactly once, in their order in this
	public abstract IntList addEl(Object x);
 
	// EFFECTS: adds x to the beginning of this
	public abstract int size();
 
	// EFFECTS: returns a count of the number of elements of this
	public abstract boolean repOk();
 
	public String toString() {
		String s = "[ ";
		for (Object i : this)
			s += i.toString() + " ";
		return s + "]";
	}
 
	public boolean equals(Object o) {
		if(o instanceof IntList)
			return equals((IntList) o);
		else
			return false;
	}
 
	public boolean equals(IntList o) {
		Iterator i = this.elements();
		Iterator j = o.elements();
 
		while (i.hasNext() && j.hasNext()) {
			if (!i.next().equals(j.next()))
				return false;
		}
		return true;
	}
}

List:

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
42
43
44
45
46
47
48
49
50
51
package list;
 
import java.util.*;
 
public class List extends IntList{
	private Object head;
	private IntList tail;
	public static IntList empty = new List(null,null);
 
	private List(Object h, IntList t){
		head = h;
		tail = t;
	}
 
	public Object first() throws EmptyException{
		return 	head;
	}
 
	public IntList rest() throws EmptyException{
		return tail;
	}
 
	public MyIterator elements(){
		return new MyIterator(this);
	}
 
 
	public MyIterator iterator(){
		return new MyIterator(this);
	}
 
	public IntList addEl(Object x){
			return new List(x,this);
	}
 
	public int size(){
		if(this==empty){
			return 0;
		}else{
			if(tail==empty){
				return 1;
			}
			else return tail.size()+1;
		}
	}
 
	public boolean repOk(){
		return head==null?tail==null:tail!=null?tail.repOk():false;
	}
 
}

MyIterator:

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
package list;
 
import java.util.*;
 
public class MyIterator implements Iterator{
 
	private List i;
 
	MyIterator(List e){
		i = e;
	}
 
	public boolean hasNext(){
		try{
			if(i.rest()==null){
				return false;
			}else{
				return true;
			}
		}
		catch(EmptyException e){
			return false;
		}
	}
 
	public Object next() throws NoSuchElementException{
		try{
			return i.rest().first();
		}
		catch(EmptyException e){
			return e;
		}
		catch(NoSuchElementException e){
			return e;
		}
	}
 
	public void remove() throws UnsupportedOperationException,IllegalStateException{
	}
}

TestIntList:

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
package list;

public class TestIntList {
	public static void main(String[] args) throws EmptyException {
		IntList l = List.empty;

		for (int i = 0; i < 100; i++) {
			l = l.addEl(new Integer(i));
		}

		System.out.println(l);
		System.out.println("l=l? " + l.equals(l));
		System.out.println("l=l.hd? " + l.equals(l.first()));
		System.out.println("l=l.tl? " + l.equals(l.rest()));
		System.out.println("l.size(): " + l.size());		
		System.out.println("repOK(): " + l.repOk());
		
	}

}

le problème vient du bout de code surligné en rouge dans TestIntList, l'application compile, mais boucle infiniment dès l'entrée dans le for();
A mon avis le problème vient de l'ajout d'élément dans List.java (donc de addEl();

merci d'avance,

Tux

[Wydicule]

J'avoue que je ne vois pas trop le problème du for. L'heure y joue peut etre, je fatigue.

Ceci dit, un autre problème me saute au yeux : ton champs empty.

Un champs d'une classe devrait etre à de rares exceptions pret toujours privé.

Et là tu as un champs static qui est public, mais quand tu fait l = List.empty attention tu n'as pas créé une nouvelle liste vide là, mais tu est en train de manipulé empty, ta liste qui était vide et qui le sera plus !

Si tu veux une nouvelle liste, il faut que tu passes par un constructeur de la classe List :

Code :

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

1
2
3
4
5
6
 
/* Constructeur d'une liste vide */
public List() {
  head = null; // facultatif parce que par defaut mais bon pour comprendre
  tail = null; // idem
}

Mais bon, la comme ton main est simple, ca devrait pas poser plus de soucis que ca pour l'execution du reste ...

[Tuxico]

En fait le static me permets simplement d'avoir un constructeur privé.

[Wydicule]

En fait le static me permets simplement d'avoir un constructeur privé.

Pour quelle raison avoir un constructeur privé ? Le but d'un constructeur c'est de construire un objet justement ^^

Au pire, tu peux mettre une methode static qui retourne new List(null, null) mais si tu fais pas de new, tu vas modifier ta liste empty, qui ne sera plus empty du coup

[Tuxico]

simplement parce que le but d'un type abstrait est de masquer l'implémentation au maximum

enfin j'ai changé, si il n'y a que ça.

mais cela ne change pas le problème.


merci pour vos réponses

[Tuxico]

oups je viens de me rendre compte que j'avais mal copié le code de MyIterator ci -dessus


Sinon le problème vient bien de:

for (int i = 0; i < 100; i++) {
l = l.addEl(new Integer(i));
}

car quand je commente ces lignes ou que je crée une liste avec un seul élément, cela ne plante pas...
Le problème est apparemment quand la liste à plusieurs éléments


une idée?

[Tuxico]

Code :

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

		System.out.println("l=l? " + l.equals(l));

le problème vient de cette ligne en fait, je viens de vérifier.

Je vais essayer de voir ce qui ne va pas dans mon equals...

[Wydicule]

Le probleme dans ton equals c'est que tu l'appelles en boucle :

Code :

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

1
2
3
4
 
public boolean equals(Object o) {
   return equals(o);
}

Je savais bien que ton addEl n'avait pas de probleme :p

Pour ton equals il devrit plutot ressemblait à :

Code :

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

1
2
3
4
5
6
 
public boolean equals(Object o) {
   if (first().equals(o.first))
     return rest().equals(o.rest());
   return false;
}

Un truc dans ce genre là si j'ai bien compris ton code. Et encore, parce que le equals sur les Object ca va tester que c'est vraiment le même objet alloué dans la JVM. Il faudrait tester les valeurs de l'objet retourné par first()

[Tuxico]

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
	public boolean equals(Object o) {
		if(o instanceof IntList)
			return equals((IntList) o);
		else
			return false;
	}
 
	public boolean equals(IntList o) {
 
		try{
			MyIterator i = this.elements();
			MyIterator j = o.elements();
			while (i.hasNext() && j.hasNext()) {
				if (!i.next().equals(j.next()))
					return false;
				}
			}catch(NullPointerException e){
				return false;
			}
			return true;
	}

[Tuxico]

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
	public boolean equals(Object o) {
		if(o instanceof IntList)
			return equals((IntList) o);
		else
			return false;
	}
 
	public boolean equals(IntList o) {
 
		try{
			MyIterator i = this.elements();
			MyIterator j = o.elements();
			while (i.hasNext() && j.hasNext()) {
				if (!i.next().equals(j.next()))
					return false;
				}
			}catch(NullPointerException e){
				return false;
			}
			return true;
	}

pourtant je ne boucle pas, dans un cas j'appelle equals avec un paramètre IntList, et dans l'autre equals avec un Object.

je vais quand-même les revoir attentivement mais à première vue je ne vois pas le problème.


merci

[Wydicule]

Autant pour moi, j'avais pas vu la seconde methode equals

Mais bon dans tous les cas, c'est un peu le bordel ton code, tu cherches a faire un truc simple de maniere bien compliqué j'ai l'impression. Je suis déjà pas mal étonné que ca ne balance pas plein d'exceptions ... remarque ca le fait peut etre ^^

Deja par exemple :

Code :

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

1
2
3
4
5
6
7
 
 
		while (i.hasNext() && j.hasNext()) {
			if (!i.next().equals(j.next()))
				return false;
		}
                return true;

Ca ca ne marchera jamais, enfin ca retournera pas la valeur atendu.
Si i et j ne font pas la meme taille, l'un des deux retournera false sur le hasNext() et toi tu retournera true comme quoi ils sont egaux.

Mais bon supposons que tes listes soient de la meme taille ok.

Ensuite ton probleme le voila :
Dans le hasNext() tu dis qu'il y a une suite si le rest() n'est pas nulle, et dans le next() tu retournes le first de next, mais tu ne modifies pas i ! Du coup au prochain appelle de hasNext() qui lui se base sur i, il dira la meme chose, qu'il en reste, et tu boucles indefiniment.

Ceci dit, avec la remarque que je t'ai fait l'autre jour sur ta list empty, fait gaffe dans ton iterator tu utilises le meme objet list dans les deux. Donc attention dans le next quand tu modiferas ta list i, parce que tu vas egalement modifier celle de la list de l'autre iterateur je pense :]

Voila, j'espere avoir pu t'aider

[Tuxico]

Bon c'est réglé, pour finir Tous les problèmes venaient de mon next dans l'iterator

En fait, pour ce qui est du constructeur privé je me suis mal exprimé en me relisant maintenant:

il s'agit en fait d'une astuce qui permet de garantir que la classe ne
pourra pas être instanciée par :
new List() tout en autorisant l'instanciation par
List l = List.getInstance ()

Pour simplifier, un constructeur privé indique soit une classe qui ne
peut pas être instanciée par construction directe soit une classe qui ne
peut tout simplement pas être instanciée (classe utilitaire contenant
uniquement des méthodes statiques).



je trouve cela plus propre pour un Type abstrait. c'est le pattern singleton si je ne m'abuse

Mon dernier problème est le suivant:

lorsque je lance testIntList, il m'affiche ceci:

Code :

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

1
2
3
4
5
6
[ 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 ]
l=l? true
l=l.hd? false
l=l.tl? false
l.size(): 100
repOK(): true

bref, il commence à 98, au lieu de 99 mais affiche la bonne taille.

voici mon code modifié:

MyIterator:

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
package list;
 
import java.util.*;
 
public class MyIterator implements Iterator{
 
	private List i;
 
	MyIterator(List l){
		i = l;
	}
 
	public boolean hasNext(){
		try{
			if(i.rest()==i.empty){
				return false;
			}else{
				return true;
			}
		}
		catch(EmptyException e){
			return false;
		}
	}
 
	public Object next() throws NoSuchElementException{
		try{
			i = (List)i.rest();
			return i.first();
		}
		catch(EmptyException e){
			return e;
		}
		catch(NoSuchElementException e){
			return e;
		}
	}
 
	public void remove() throws UnsupportedOperationException,IllegalStateException{
	}
}

List:

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
42
43
44
45
46
47
48
49
50
51
package list;
 
import java.util.*;
 
public class List extends IntList{
	private Object head;
	private List tail;
	public static List empty = new List(null,null);
 
	private List(Object h, List t){
		head = h;
		tail = t;
	}
 
	public Object first() throws EmptyException{
		return 	head;
	}
 
	public List rest() throws EmptyException{
		return tail;
	}
 
	public MyIterator elements(){
		return new MyIterator(this);
	}
 
 
	public MyIterator iterator(){
		return new MyIterator(this);
	}
 
	public List addEl(Object x){
		return new List(x,this);
	}
 
	public int size(){
		if(this==empty){
			return 0;
		}else{
			if(tail==empty){
				return 1;
			}
			else return tail.size()+1;
		}
	}
 
	public boolean repOk(){
		return head==null?tail==null:tail!=null?tail.repOk():false;
	}
 
}

[Wydicule]

Je pense que ca vient de là :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
public Object next() throws NoSuchElementException{
		try{
			i = (List)i.rest();
			return i.first();
		}
		catch(EmptyException e){
			return e;
		}
		catch(NoSuchElementException e){
			return e;
		}
}

A la premiere itération, tu dis que i devient la fin, et tu renvoie le premier de i, mais comme tu as modifié i, ca sera le premier de la fin et tu perds ton vrai premier.

Essaye plutot comme ça :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
public Object next() throws NoSuchElementException{
		try{
                        Object tmp = i.first();
			i = (List)i.rest();
			return tmp;
		}
		catch(EmptyException e){
			return e;
		}
		catch(NoSuchElementException e){
			return e;
		}
}

Quand au design pattern singleton, il sert surtout quand on veut avoir qu'une seul instance de la classe. C'est pas vraiment ton cas pour la liste, et pour la liste abstraite, elle ne pourra de toute maniere pas etre instancié, puisque abstraite. Mais bon passons, si cela fait ce que tu souhaites

[Tuxico]

merci pour ton temps