import java.lang.Iterable;
import java.util.Iterator;
import java.util.ArrayList;
/** Interface des listes (extrait). */
interface List<T> {
/** Renvoie l'élément d'indice [i]. */
T get(int i);
/** Ajoute l'élément [elt] à la fin de la liste. */
void add(T elt);
}
/** Interface désignant une itération en cours. */
/*
interface Iterator<T> {
// Renvoie vrai s'il existe un prochain élément.
boolean hasNext();
// Donne le prochain élément et prépare le passage au suivant.
T next();
}
*/
/** Interface des collections sur les éléments desquelles on peut itérer. */
/*
interface Iterable<T> {
Iterator<T> iterator();
}
*/
public class Iterators {
public static void main(String[] args) {
ArrayList<String> vent = new ArrayList<String>();
vent.add("' , , « - ».");
vent.add(" , , ' , ' , ' .");
vent.add(" , , .");
// Création d'un itérateur
Iterator<String> it = vent.iterator();
// Tant qu'il reste des éléments...
while (it.hasNext()) {
// prendre le prochain élément et l'afficher.
System.out.println(it.next());
}
// Deux fois chaque élément
// Création d'un itérateur
Iterator<String> it2 = vent.iterator();
// Tant qu'il reste des éléments...
while (it2.hasNext()) {
// prendre le prochain élément
String s = it2.next();
// et l'afficher deux fois
System.out.println(s);
System.out.println(s);
}
// Un élément sur deux
// Création d'un itérateur
Iterator<String> it3 = vent.iterator();
// Tant qu'il reste des éléments...
while (it3.hasNext()) {
// prendre le prochain élément et l'afficher
System.out.println(it3.next());
// puis passer au suivant s'il y en a un.
if (it3.hasNext()) { it3.next(); }
}
}
}
/** Première version : tableau non redimensionable, non paramétré. */
class FixedCapacityList implements List<Object>, Iterable<Object> {
// La capacité est immuable
private final int capacity;
private Object[] elements;
// Le champ [size] est déclaré visible dans le paquet, pour que les classes
// associées [AscendingIterator] et [DescendingIterator] puissent y avoir
// accès. Ce ne serait plus nécessaire si on définissait ces dernières
// comme des classes internes.
protected int size = 0;
public FixedCapacityList(int c) {
// Création d'un tableau de la capacité demandée.
this.capacity = c;
this.elements = new Object[c];
}
// Renvoyer l'élément, sans vérifier l'indice.
public Object get(int i) { return this.elements[i]; }
// Ajouter l'élément si la capacité n'est pas atteinte, et
// ne rien faire sinon.
public void add(Object elt) {
if (this.size < this.capacity) this.elements[this.size++] = elt;
}
// Création d'itérateurs
public Iterator<Object> iterator() {
// La liste est passée elle-même en paramètre, car elle va servir
// de base à l'itérateur.
return new AscendingIterator(this);
}
public Iterator<Object> reversedIterator() {
return new DescendingIterator(this);
}
}
/** Itérateur ascendant. */
class AscendingIterator implements Iterator<Object> {
// On garde une référence sur la liste sur laquelle on itère
private final FixedCapacityList list;
// On retient en plus la position courante
private int currentIndex = 0;
// La liste sur laquelle itérer est passée en paramètre à la construction
public AscendingIterator(FixedCapacityList l) {
this.list = l;
}
// Il reste des éléments tant que la position courante n'a pas atteint
// la fin de la liste
public boolean hasNext() { return this.currentIndex < list.size; }
// Extrait l'élément à la position courante, puis incrémente la position
public Object next() { return this.list.get(currentIndex++); }
}
/** Itérateur descendant. */
class DescendingIterator implements Iterator<Object> {
// Similaire au précédente, mais la position initiale est la dernière de
// la liste, et chaque appel à [next] décrémente la position.
private FixedCapacityList list;
private int currentIndex;
public DescendingIterator(FixedCapacityList l) {
this.list = l;
this.currentIndex = l.size;
}
public boolean hasNext() { return this.currentIndex > 0; }
public Object next() { return this.list.get(--currentIndex); }
}
/** Deuxième version : liste chaînée, paramétrée par un type [T] de contenu. */
/**
On définit d'abord une classe pour les blocs de la liste chaînée.
Note : on pourrait faire de cette classe une classe interne de [LinkedList].
*/
class Block<T> {
// Le contenu et le pointeur vers le bloc suivant sont visibles dans le
// paquet, car la classe principale [LinkedList] y fera référence.
protected T contents;
protected Block<T> nextBlock;
// Le constructeur prend en paramètres l'élément à placer dans le bloc
public Block(T elt) {
this.contents = elt;
this.nextBlock = null;
}
}
class LinkedList<T> implements List<T>, Iterable<T> {
// On maintient des références vers les premier et dernier blocs.
private Block<T> firstBlock, lastBlock;
// À l'origine on crée une liste vide : il n'y a ni premier ni dernier bloc
public LinkedList() {
this.firstBlock = null;
this.lastBlock = null;
}
// Ajout d'un élément
public void add(T elt) {
// On crée un nouveau bloc [b]
Block<T> b = new Block<T>(elt);
// Si la liste est vide [b] devient le premier bloc,
// sinon [b] devient le successeur du dernier bloc courant
if (this.firstBlock == null) {
this.firstBlock = b;
} else {
this.lastBlock.nextBlock = b;
}
// Dans tous les cas, [b] devient le dernier bloc
this.lastBlock = b;
}
// Accès à l'élément à un indice [i] donné
public T get(int i) {
// On mémorise un bloc courant,
Block<T> currentBlock = this.firstBlock;
// on avance [i] fois,
for (int j=0; j<i; j++) currentBlock = currentBlock.nextBlock;
// et on renvoie la valeur trouvée.
return currentBlock.contents;
}
// Création d'un itérateur à qui on fournit le premier bloc, à partir
// duquel il pourra accéder à tous les autres
public Iterator<T> iterator() {
return new LinkedListIterator<T>(this.firstBlock);
}
}
/** Itérateur de liste chaînée */
class LinkedListIterator<T> implements Iterator<T> {
// On mémorise uniquement le bloc courant, les champs [nextBlock]
// suffiront à atteindre les autres
private Block<T> currentBlock;
// À la construction, on fournit un bloc (a priori le premier)
public LinkedListIterator(Block<T> block) {
this.currentBlock = block;
}
// Il y a un prochain élément tant qu'il y a un bloc
public boolean hasNext() {
return currentBlock != null;
}
// Extrait l'élément du bloc courant, puis change le bloc courant. Si le
// bloc courant était le dernier, [currentBlock] prendra la valeur [null].
public T next() {
T elt = currentBlock.contents;
this.currentBlock = this.currentBlock.nextBlock;
return elt;
}
}