Série 8 – Itérateurs : corrigé

Le code du corrigé est disponible sous la forme d'une archive Zip. Les solutions aux différents exercices sont brièvement discutées ci-dessous.

La définition de la classe ReadOnlyIterator ne pose aucun problème, sa seule méthode étant triviale.

public abstract class ReadOnlyIterator<E> implements Iterator<E> {
    @Override
    final public void remove() {
        throw new UnsupportedOperationException();
    }
}

La définition de la classe InfiniteIterator ne pose pas plus de problème que celle de la classe ReadOnlyIterator.

public abstract class InfiniteIterator<E>
        extends ReadOnlyIterator<E> {
    @Override
    final public boolean hasNext() {
        return true;
    }
}

La classe IntIterator doit mémoriser deux informations : la valeur courante de l'itérateur (champ curr) et le pas (champ step). Ces deux valeurs sont initialisées dans le constructeur, et la méthode next calcule la prochaine valeur, la stocke dans le champ curr et retourne celui-ci.

public final class IntIterator extends InfiniteIterator<Integer> {
    private final int step;
    private int curr;

    public IntIterator(int start, int step) {
        this.curr = start - step;
        this.step = step;
    }

    @Override
    public Integer next() {
        curr += step;
        return curr;
    }
}

Bien entendu, il est également possible de mémoriser la prochaine valeur que next doit retourner, mais cela rend le code de cette méthode légèrement plus complexe, raison pour laquelle la solution de stocker la valeur courante (donc la valeur qui précède celle que next doit retourner) a été choisie.

L'itérateur filtrant est plus délicat à définir que les précédents. L'idée principale consiste à conserver le prochain élément que la méthode next doit retourner (champ next), obtenu de l'itérateur sous-jacent, ainsi qu'un booléen indiquant la validité de ce champ (champ isNextValid).

La méthode hasNext se charge d'obtenir de l'itérateur sous-jacent la prochaine valeur à retourner, s'il y en a une. Pour ce faire, elle obtient des valeurs de l'itérateur sous-jacent jusqu'à ce que l'une d'elles soit acceptée par shouldInclude. Si une telle valeur est trouvée, alors elle est gardée dans next et le booléen isNextValid est vrai. Si l'itérateur sous-jacent est épuisé avant qu'une telle valeur ne soit trouvée, le champ isNextValid est faux.

La méthode next quant à elle ne fait rien d'autre que retourner la valeur du champ next en remettant le champ isNextValid à faux, afin d'indiquer que celle contenue dans next est maintenant invalide (puisqu'elle a été fournie) et que la prochaine valeur doit donc être obtenue.

Notez bien que, étant donné que next commence par appeler hasNext, cette dernière peut être laissée seule responsable de l'obtention de la prochaine valeur.

public abstract class FilteringIterator<E>
        extends ReadOnlyIterator<E> {
    private final Iterator<E> underlyingIt;
    private E next;
    private boolean isNextValid;

    public FilteringIterator(Iterator<E> underlyingIt) {
        this.underlyingIt = underlyingIt;
        this.next = null;
        this.isNextValid = false;
    }

    public abstract boolean shouldInclude(E elem);

    @Override
    public boolean hasNext() {
        while (!isNextValid && underlyingIt.hasNext()) {
            next = underlyingIt.next();
            isNextValid = shouldInclude(next);
        }
        return isNextValid;
    }

    @Override
    public E next() {
        if (! hasNext())
            throw new NoSuchElementException();
        isNextValid = false;
        return next;
    }
}

La classe MultiplesFilteringIterator doit mémoriser la totalité des entiers qu'elle a déjà produits afin de ne jamais produire de multiple de l'un d'entre eux.

Les entiers produits sont stockés dans une collection (champ produced), ici une liste de type ArrayList. La méthode next est redéfinie afin d'ajouter chaque élément produit à cette collection avant de le retourner.

La méthode shouldInclude quant à elle ne retourne vrai que si l'élément candidat qu'elle reçoit n'est multiple d'aucun des éléments déjà fournis.

public class MultiplesFilteringIterator
        extends FilteringIterator<Integer> {
    private final List<Integer> produced = new ArrayList<>();

    public MultiplesFilteringIterator(Iterator<Integer> underIt) {
        super(underIt);
    }

    @Override
    public Integer next() {
        Integer n = super.next();
        produced.add(n);
        return n;
    }

    @Override
    public boolean shouldInclude(Integer elem) {
        for (int p: produced) {
            if (elem % p == 0)
                return false;
        }
        return true;
    }
}

Lorsqu'on applique cet itérateur filtrant à l'itérateur produisant les entiers à partir de 2, on obtient un itérateur sur les nombres premiers ! En effet, les seuls nombres acceptés par shouldInclude sont ceux qui ne sont multiple d'aucun entier supérieur ou égal à deux, ce qui est la définition d'un nombre premier.

L'idée utilisée par cet itérateur est similaire à celle du crible d'Eratosthène, mais moins efficace pour les raisons expliquées dans l'article The Genuine Sieve of Eratosthenes que les personnes intéressées (et très motivées) pourront lire.