Discussion :

[Bowbaq]

Tout d'abord Bonjour à tous, et merci d'avance à ceux qui prendrons le temps de m'aider.

Après un post sans succès sur les forums de VelocityReviews (que nos amis anglophiles pourrons consulter ici) je me suis dit que finalement, un forum français, c'était pas une mauvaise idée.

Posons donc rapidement le cadre : je dois dans le cadre d'un projet scolaire proposer plusieurs implémentations d'une file de priorité en Java. Après quelques recherches j'en suis arrivé à la conclusion qu'une implémentation basée sur un tas binaire était toute indiquée.

J'écrit donc une classe qui gère un tas binaire, comme ceci :

Code :

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

1
2
3
public class BinaryHeap<T extends Comparable<T>> {
...
}

Pour pouvoir maintenir la propriété de tas, j'ai besoin de pouvoir comparer les éléments, j'ai donc choisi de stocker des éléments qui implémentent l'interface Comparable (Question subsidiaire : "extends" équivaut à "implements" dans le cadre des generics?)

Après, dans un autre package, j'ai défini l'interface de ma file de priorité. J'ai aussi créé une classe abstraite element pour définir le squelette de base des éléments stockés par mes différentes files (tentative de factorisation de code) :

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 abstract class Element<T> implements Comparable<Element<T>> {
 
       private T content;
       private double priority;
 
       public int compareTo(Element<T> e) {
		if (getPriority() > e.getPriority())
			return 1;
		else if (getPriority() < e.getPriority())
			return -1;
		return 0;
	}
...
}

On approche du problème.
Je crée donc une classe qui hérite de ma classe abstraite Element afin de l'utiliser avec mon tas :

Code :

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

1
2
3
4
5
6
public class HeapElement<T> extends Element<T>{
 
	public ElementTas(T content, double priority) {
		super(content, priority);
	}
}

Et tout content, j'essaye de créer une instance de mon tas comme ceci :

Code :

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

BinaryHeap<HeapElement<T>> heap;

Et là, c'est le drame...
Le compilateur me sort l'erreur suivante :

Bound mismatch: The type HeapElement<T> is not a valid substitute for the bounded parameter <T extends Comparable<T>> of the type BinaryHeap<T>

Pourtant, ma classe abstraite implémente bien l'interface comparable, et en toute logique, ma classe fille aussi. D'ailleurs, si j'essaye de ré-implémenter l'interface Comparable au niveau de la classe fille comme ceci :

Code :

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

1
2
3
4
5
6
public class HeapElement<T> extends Element<T> implements Comparable<HeapElement<T>>{
 
	public ElementTas(T content, double priority) {
		super(content, priority);
	}
}

Le compilateur indique alors l'erreur suivante :

The interface Comparable cannot be implemented more than once with different arguments: Comparable<Element<T>> and Comparable<HeapElement<T>>

L'interface Comparable est donc bien implémentée par ma classe HeapElement. Je ne comprends donc pas pourquoi mon tas qui stocke des éléments qui implémentent Comparable justement, ne se laisse pas instancier si je le paramètre avec HeapElement.

Remarques :

• J'ai essayé de déclarer la méthode compareTo "final" dans la classe abstraite, pensant que l'erreur venait du fait que la méthode pouvait éventuellement être surchargée dans la classe fille, rien n'y fait.

• La solution provisoire que j'ai trouvé consiste à ne pas implémenter Comparable au niveau de la classe abstraite mais au niveau de chacune des classes filles. (Insatisfaisant à mon goût)

• Après quelques jours de réflexions, je me rends compte que ma démarche pour cette implémentation n'est sans doute pas optimale. Peut être une autre façon de faire m'aurait évité ce souci. Toute suggestion sur une autre manière d'envisager le problème est la bienvenue.

• La classe qui spécifie les Element stockés par la file est extérieure à la déclaration de la file elle même. Il me paraitrai plus judicieux de ne pas laisser cette partie visible, étant donné que ça relève d'un mécanisme interne. Est-ce possible? Si oui comment s'il vous plait?

Merci à ceux qui aurons pris le temps de lire ce (long) sujet. Merci d'avance à ceux qui pourront m'apporter (je l'espère) une réponse.

P.S Le code source complet est disponnible ici éventuellement pour ceux qui le souhaiteraient.

[CyberChouan]

Voilà la solution (attention, prévoir un aspirine et plusieurs relectures si tu n'as pas l'habitude de manipuler les Generics...)

Tu dois changer la signature de BinaryHeap de la manière suivante :

Code :

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

public class BinaryHeap<T extends Comparable<? super T>> {}

Tu verras que ton code tel que tu le postes compileras (monnayant la modification ci-dessus).

L'explication détaillée est la suivante :

Element<T> est une classe qui implémente Comparable<Element<T>> par définition : pas de problème.

En revanche, HeapElement<T> (qui étends Element<T>) n'étend pas Comparable<HeapElement<T>>. La nuance est subtile mais elle étend Comparable<Element<T>>, soit Comparable d'une classe parente de HeapElement<T>

C'est cette nuance qui est explicitée par "? super T".

Voilà le schéma pour clarifier les choses :
HeapElement<T> <-- Element<T> <-- Comparable<Element<T>>
C'est à dire :
HeapElement<T> <-- Comparable<Classe parente de HeapElement<T>>
HeapElement<T> <-- Comparable<? super HeapElement<T>> (en traduisant en Java)

J'espère avoir été clair...

[Bowbaq]

Merci pour cette réponse instructive et très claire.

Sa fonctionne parfaitement. Et je n'y aurais jamais pensé moi même... Je saurais la prochaine fois.

Merci beaucoup en tout cas d'avoir pris la peine de répondre

Edit : Il semblerait que la solution à la remarque 4 soit de déclarer HeapElement<T> en tant que classe interne.