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]

merci pour ton temps