Itérateur générique pour une interface et ses sous-classes et ses types et sous-types

Question

Comme le titre le dit, j'essaie de concevoir une structure de données personnalisée SearchTree qui devrait être Iterable sur les entrées telles que SearchTree.Entry<K, V>. Un SearchTree lui-même est juste une interface.

Ce que je veux faire est d'avoir que toute classe qui implémente SearchTree<K, V> avec ses propres sous-types de K et V est également en mesure de mettre en œuvre le iterator tel que défini dans une interface SearchTree<K, V>.

SearchTree.java

public interface SearchTree<K extends Comparable<? super K>, V> extends Iterable<SearchTree.Entry<K, V>> { 

    static interface Entry<K, V> { 

     K getKey(); 

     V getValue(); 

     void setValue(V value); 
    } 
} 

Et supposons maintenant que j'ai une classe qui implémente l'interface.

BST.java

public class BST<K extends Comparable<? super K>, V> implements SearchTree<K, V> { 

    @Override 
    public Iterator<Entry<K, V>> iterator() { 
     // return some bst specific iterator 
    } 
} 

BSTNode.java

public class BSTNode<K extends Comparable<? super K>, V> implements SearchTree.Entry<K, V> { // ... 
} 

Maintenant, évidemment, le BST Iterator doit itérer sur BSTNode objets, donc il serait logique de le déclarer comme quelque chose comme:

BSTIterator.java

public class BSTIterator<K extends Comparable<? super K>, V> implements Iterator<BSTNode<K, V>> { 
} 

Mais revenons au problème de BST.java où l'instance de BSTIterator doit être retourné quelque chose comme:

BST.java

public class BST<K extends Comparable<? super K>, V> implements SearchTree<K, V> { 

    @Override 
    public Iterator<Entry<K, V>> iterator() { 
     return new BSTIterator<>(); 
    } 
} 

Et maintenant cela ne fonctionne pas: Impossible de déduire des arguments de type pour BSTIterator <>. Y a-t-il un moyen sensé de contourner ce problème, de sorte que je puisse avoir un itérateur générique dans mon interface, et un retour des implémentations d'itérateur concret des classes implémentant le SearchTree de manière à ce que les types génériques puissent aussi être sous-classés?

Answer 1

Vous êtes proche. Votre itérateur BSTIterator doit implémenter Iterator<SearchTree.Entry<K, V>> au lieu de Iterator<BSTNode<K, V>>. Je pense que c'est parce que le type de votre itérateur retourné doit garantir qu'il est Entry<K, V>, pas spécifiquement BSTNode.

public class BSTIterator<K extends Comparable<? super K>, V> 
    implements Iterator<SearchTree.Entry<K, V>> { 
    // ... 
} 

public class BST<K extends Comparable<? super K>, V> 
    implements SearchTree<K, V> { 

    @Override 
    public Iterator<SearchTree.Entry<K, V>> iterator() { 
     return new BSTIterator<>(); 
    } 
} 

Answer 2

Il existe plusieurs façons d'aborder cette question. Le moyen le plus simple est ce que Neil describes in his answer. Mais cela jette des informations de type: par exemple, si vous souhaitez utiliser directement BSTIterator, vous devez renvoyer les éléments à BSTNode s si vous souhaitez les utiliser comme tels.

---

L'approche hacky (mais en réalité tout à fait sûr) est de noter qu'il n'y a pas de méthodes de consommation sur Iterator<T>: de ce que vous ne pouvez jamais obtenir une valeur par get() (ou vérifier s'il y a un autre élément, ou supprimer la élément précédemment obtenu). En tant que tel, il est totalement sûr d'utiliser un Iterator<SubclassOfT> comme Iterator<T>. Le système de type Java ne sait pas qu'il est sûr, donc vous devez jeter:

return (Iterator<SearchTree.Entry<K, V>>) (Iterator<?>) new BSTIterator<K, V>(); 

et ajouter @SuppressWarnings("unchecked").

---

La façon brute en un autre sens de le faire est de rendre le SearchTree itérables mettre en œuvre sur un type supérieur borné:

public interface SearchTree<K extends Comparable<K>, V> 
    extends Iterable<? extends SearchTree.Entry<K, V>> 

Ceci est un brut peu parce que maintenant la iterator() méthode va retourner un Iterator<? extends SearchTree.Entry<K, V>>: vous êtes coincé avec ce ?.

Il est revendiqué par Josh Bloch dans Effective Java 2nd Ed que si les utilisateurs de votre API doivent se soucier des caractères génériques, vous avez mal conçu. (Item 28, spécifiquement page 137, si vous en avez une copie à portée de main).

---

Une autre façon de le faire est d'ajouter explicitement une variable de type pour le type de l'élément dans le Iterator:

public interface SearchTree<K extends Comparable<K>, V, T extends SearchTree.Entry<K, V>> 
    extends Iterable<T> 

Maintenant, vous pouvez déclarer votre BST comme:

public class BST<K extends Comparable<K>, V> 
    implements SearchTree<K, V, BSTNode<K, V>> 

Cela transmet le plus d'informations de type, mais je ne dirais pas que c'est absolument mieux, car ayant 3 variables de type chaque fois que vous déclarez une variable SearchTree est juste encombrement générique, d'autant plus que le troisième contient souvent le premier et le second à nouveau, par exemple.

SearchTree<String, Integer, ? extends SearchTree.Entry<String, Integer>> 

---

Il n'y a pas d'option super-grand-propre ici. Personnellement, j'irais avec la première option, hacky, parce que a) c'est vraiment sûr! b) le hack est caché à l'intérieur de la classe d'implémentation.