Le but de ce TD est de coder une structure de données semblable à LinkedList, sous la forme d'une classe Dequeue (pour double-ended queue).

Créer un projet td5. Dans ce projet, créer un package dequeue. Il contiendra la classe Dequeue. Les différentes classes de test seront placées dans le package par défaut.

Important : La plupart des programmes fournis pour tester votre code utilisent la construction assert de Java. Vous devez donc passer l'option -ea à la machine virtuelle Java (onglet VM Arguments de la configuration de lancement).

Structure de liste doublement chaînée

             first                                                last
               |                                                   |
               V                                                   V
     +------+----+----+     +---+----+----+                  +---+----+------+
     |      | x1 | o------> |   | x2 | o------>   ...        |   | xn | null |
     | null |    |    | <-----o |    |    |   ...        <-----o |    |      |
     +------+----+----+     +---+----+----+                  +---+----+------+

package dequeue;

class Cell<E> {
	final E element;
	Cell<E> prev, next;

	Cell(E e) {
		this.element = e;
		this.prev = this.next = null;
	}
}

Créer une classe publique Dequeue<E> dans Dequeue.java. Le type E est le celui des éléments. Dans cette classe, créer :

• un champ privé int size qui contient le nombre d'éléments dans la liste ;
• deux champs privés Cell<E> first, last.

Écrire un constructeur publique Dequeue() qui renvoie une liste ne contenant aucun élément.

Écrire les méthodes publiques suivantes :

• int size() : renvoie le nombre d'éléments ;
• boolean isEmpty() : indique si la liste est vide ;
• clear() : supprime tous les éléments de la liste.

Tester avec le code Test1.java (à placer dans le package par défaut).

Ajout et suppression d'éléments

Ajouter les méthodes publiques suivantes :

• void addFirst(E x) : ajoute l'élément x au début de la liste ;
• void addLast(E x) : ajoute l'élément x à la fin de la liste ;
• void addAll(Iterable<E> c) : ajoute tous les éléments de la structure itérable c à la fin de la liste, dans l'ordre où ils apparaissent dans c (on pourra se resservir de addLast).

Ajouter ensuite les méthodes publiques suivantes :

• E getFirst() : renvoie le premier élément de la liste, sans la modifier ;
• E getLast() : renvoie le dernier élément de la liste, sans la modifier ;
• E removeFirst() : supprime et renvoie le premier élément de la liste ;
• E removeLast() : supprime et renvoie le dernier élément de la liste.

Tester avec le code Test2.java (à placer dans le package par défaut).

Affichage

Écrire une méthode publique String toString() qui renvoie une chaîne de caractères de la forme "{s1, s2, ..., sn}" où s1, s2, etc., sont les chaînes de caractères obtenues avec la méthode toString des différents éléments. En particulier, si la liste est vide, cette méthode doit renvoyer la chaîne "{}". On notera qu'il n'y a pas de virgule (ni d'espace) après le dernier élément sn.

Tester avec le code Test3.java (à placer dans le package par défaut).

Itérateur

Nous allons maintenant faire en sorte de pouvoir parcourir les éléments de nos listes à l'aide de la construction for (E x : l) .... On rappelle qu'il s'agit là d'un sucre syntaxique pour

for (Iterator<E> it = l.iterator(); it.hasNext(); ) {
    E x = it.next();
    ...
}

Dans la classe Dequeue, il faut donc :

• ajouter une classe privée locale Iter qui implémente l'interface Iterator<E> (importée de java.util), de la manière suivante :

  public class Dequeue<E> {
    // des définitions de Dequeue
    ...
  
    private class Iter implements Iterator<E> {
      // définitions de Iter
      ...
    } // fin de Iter
  
    // d'autres définitions de Dequeue
    ...
  
  } // fin de Dequeue
  

• écrire le constructeur et les méthodes hasNext et next de la classe Iter (mais pas sa méthode remove, que l'on codera plus tard). La méthode next doit lever l'exception NoSuchElementException si on l'appelle alors qu'il n'y a plus d'élément à renvoyer.

  Un objet Iter est attaché à un objet Dequeue et il peut accéder directement à ses champs. Par exemple, dans une méthode de Iter, le champ first correspondant s'obtient par Dequeue.this.first (ou simplement first s'il n'y a pas d'ambiguïté et que l'on préfère omettre les this).

• déclarer que la classe Dequeue implémente l'interface Iterable<E> et, par conséquent, ajouter à la classe Dequeue une méthode publique Iterator<E> iterator().

Tester avec le code Test4.java puis avec Mergesort.java (à placer dans le package par défaut).

Robustesse

A priori, rien ne nous empêche de modifier une liste (avec clear, addFirst, removeLast, etc.) alors qu'on est en train de la parcourir à l'aide d'un itérateur. Pour y remédier, on se propose d'invalider un itérateur dès lors que la liste qu'il parcourt est modifiée (quelle que soit la modification). Pour cela

• ajouter une numéro de version à la structure de liste, qui sera incrémenté par toute méthode effectuant une modification de la liste ;
• modifier les deux méthodes hasNext et next de l'itérateur pour qu'elles lèvent l'exception ConcurrentModificationException dès lors que la liste a été modifiée après la création de l'itérateur. Dans la méthode next, l'exception ConcurrentModificationException prime sur l'exception NoSuchElementException.

Tester avec le code Test5.java (à placer dans le package par défaut).

Suppression pendant un parcours

Coder la méthode remove de la classe Iter. Elle doit permettre de supprimer de la liste l'élément que l'on vient de récupérer avec la méthode next de l'itérateur. Si un tel élément n'existe pas ou n'existe plus, alors remove doit lever l'exception IllegalStateException. Comme pour next, l'exception ConcurrentModificationException prime sur l'exception IllegalStateException.

L'utilisation de remove doit invalider l'utilisation de tout autre itérateur sur la liste. Il faut donc incrémenter le numéro de version de la liste (et donc également celui attendu par l'itérateur dont on vient d'appeler la méthode remove).

Tester avec le code Test6.java (à placer dans le package par défaut).