Série 1 – Listes

Cette série est la première du micro-projet consacré aux collections. Le but de ce micro-projet est d'écrire des classes mettant en œuvre les principales collections que nous examinerons au cours, à savoir les listes, les ensembles et les tables associatives. Vous placerez toutes ces classes dans un paquetage nommé ch.epfl.collections.

Cette première série est consacrée aux listes de chaînes de caractères, dont vous devez écrire les deux mises en œuvre vues au cours, à savoir les tableaux-listes et les listes chaînées. Vous ne devrez programmer que les opérations de base sur ces listes, regroupées dans l'interface StringList présentée au cours et rappelée ci-dessous. Il va de soi que vos classes devront implémenter cette interface.

package ch.epfl.collections;

public interface StringList {
    boolean isEmpty();
    int size();
    void add(String newElem);
    void remove(int index);
    String get(int index);
    void set(int index, String elem);
    StringIterator iterator();
}

Pour faciliter votre travail, nous mettons à votre disposition le fichier StringList.java contenant cette interface. Ce fichier contient de plus des commentaires spécifiant précisément le comportement de ces différentes méthodes.

Ecrivez une classe StringArrayList qui représente une liste de chaînes de caractères au moyen d'un tableau sous-jacent, selon la technique vue au cours. Vous devez bien entendu penser à augmenter la taille du tableau sous-jacent lorsqu'il est trop petit pour contenir tous les éléments, et vous pouvez pour ce faire vous aider de la méthode statique copyOf de la classe Arrays. Toutefois, il n'est pas nécessaire de rapetisser le tableau sous-jacent plus tard, même s'il devient beaucoup trop grand au vu du nombre d'éléments non-nuls qu'il contient. Pensez à systématiquement vérifier la validité de l'indice qui est passé aux différentes méthodes, et à lever l'exception prédéfinie IndexOutOfBoundsException lorsqu'il est invalide.

Notez qu'en plus des méthodes de l'interface StringList, il est conseillé de redéfinir la méthode toString héritée de Object, afin qu'elle produise une version lisible de la liste. Cela peut s'avérer utile lors du déboguage. Par exemple, une liste contenant les chaînes lundi, mardi et mercredi dans cet ordre pourrait être représentée par la chaîne [lundi,mardi,mercredi].

Pensez à ne pas rendre publique la classe des itérateurs, afin qu'elle ne soit pas visible en dehors du paquetage ch.epfl.collections. Cela est plus propre du point de vue de l'encapsulation, et permet également de définir la classe dans le même fichier que celui contenant la classe StringArrayList.

Une fois votre classe terminée, écrivez, en vous aidant de la bibliothèque JUnit, un test unitaire pour voir si elle semble fonctionner correctement. L'embryon de classe de test ci-dessous devrait vous permettre de démarrer :

package ch.epfl.collections;

import static org.junit.Assert.*;
import org.junit.Test;

public class StringArrayListTest {
    @Test
    public void testAdd() {
        StringList l = new StringArrayList();
        l.add("hello");
        assertEquals("hello", l.get(0));
        assertEquals(1, l.size());
    }

    // ... beaucoup d'autres tests
}

Notez qu'il vous faut entre autres vérifier que les méthodes qui devraient lever l'exception IndexOutOfBoundsException dans certaines conditions le font effectivement. Cela est très simple avec JUnit, car il suffit d'annoter correctement la méthode de test et JUnit se charge du reste. Par exemple, la méthode ci-dessous teste que l'exception IndexOutOfBoundsException est bien levée lorsqu'on essaie d'accéder au premier élément d'un tableau Java vide :

@Test(expected=java.lang.IndexOutOfBoundsException.class)
public void testArrayAccessException() {
    int[] a = new int[0];
    a[0] = 12;
}

Un tel test réussit si et seulement si l'exception IndexOutOfBoundsException est levée lors de son exécution. Si une autre exception est levée, ou si aucune exception n'est levée, le test échoue.

Ecrivez une classe StringLinkedList qui mette en œuvre les listes chaînées de chaînes de caractère, comme vu au cours. Nous vous demandons pour cela d'utiliser la représentation doublement chaînée circulaire. Comme vous le verrez, cette représentation possède quelques avantages. Par exemple, il est très facile de trouver le dernier élément de la liste, puisqu'il s'agit simplement du prédécesseur de la tête. D'autre part, il y a moins de cas particuliers à considérer dans les différentes méthodes, car on a la garantie que n'importe quel élément possède un successeur et un prédécesseur non nuls.

Une fois encore, pensez à bien vérifier que l'indice qui est passé aux différentes méthodes est valide. D'autre part, pensez à toujours traiter correctement le cas où la liste est vide, c'est-à-dire que sa tête vaut null.

Comme pour les tableaux-listes, pensez à ne pas rendre publique les classes des nœuds et des itérateurs, et de restreindre ainsi leur visibilité au paquetage ch.epfl.collections.

Une fois votre classe terminée, vous devriez bien entendu écrire à nouveau une classe de test pour cette nouvelle liste. Toutefois, étant donné que la classe StringLinkedList implémente l'interface StringList au même titre que la classe StringArrayList, il semble judicieux d'essayer de réutiliser autant que possible les tests écrits pour le premier exercice. Cela est moins facile qu'il n'y paraît, mais il vaut la peine de se creuser la tête un instant sur ce problème…