Implémentation de la classe `ArrayList`

Consignes pour démarrer le TP

Comme pour les TP précédents, on va utiliser git pour la gestion de versions. Il vous faut donc vous reporter aux consignes du premier TP. Le lien vers le projet à forker est le suivant : lien.

Une fois le dépôt téléchargé, vous pouvez compiler et tester le programme en cliquant deux fois sur array-list -> Tasks -> verification -> test dans l’onglet Gradle. Pour exécuter la méthode main de la classe Main, il faut cliquer deux fois sur array-list -> application -> run.

Objectifs du TP

L’objectif de ce TP est d’implémenter notre propre version de la classe ArrayList. Cela va nous permettre :

de mettre en pratique nos connaissances sur les génériques,
d’utiliser encore un peu les tableaux,
de s’habituer à tester les méthodes systématiquement,
à approfondir notre compréhension de la classe ArrayList que nous utilisons extrêmement souvent.

Toutes les méthodes que nous allons écrire seront testées en vérifiant les retours, comme nous savons déjà faire, mais aussi en comparant au résultat de la méthode correspondantes dans ArrayList. Pour cela, il suffira d’effectuer le même appel de méthode sur une instance d’ArrayList et sur une instance de MyArrayList égale, et de comparer que les valeurs retournées sont égales et que les deux instances sont toujours égales. Ainsi, nous testerons que les deux classes ont la même sémantique.

Consignes pour le début du TP

Modifiez le fichier README.md. Mettez votre nom, votre numéro de groupe ainsi que le nom et le numéro de groupe de votre éventuel co-équipier. Faites un commit avec pour message “inscription d’un membre de l’équipe”, puis un push.

N’oubliez pas de faire des commit régulièrement !

Tâche 1 : Mise en place

La classe MyArrayList est déjà créée dans le fichier correspondant, mais pour l’instant elle est vide.

Corriger sa déclaration, pour en faire une classe générique. Ajouter à la déclaration que cette classe implémente l’interface des listes. La classe est alors considérée erronée puisque pour l’instant elle ne contient pas l’implémentation des méthodes de l’interface.
En utilisant l’IDE pour corriger l’erreur, générer toutes les méthodes manquantes de l’interface, en veillant bien à cocher la case copy JavaDoc . Attention, les méthodes ainsi générées ne font rien et retourne des valeurs par défaut, il faut donc maintenant les compléter, ce que nous allons faire petit à petit. Notez que la documentation des opérations des listes a été copiée dans votre fichier, ce qui vous permettra de plus facilement savoir ce que font les méthodes à implémenter.
Ajouter une méthode toString. Pour l’instant elle retourne une chaîne vide. Un test est d’ailleurs présent dans la classe MyArrayListTest pour vérifier ce comportement.
Ajouter une méthode public boolean equals(Object o). Pour l’instant, elle doit retourner true si et seulement si l’objet passé en paramètre est this.
Il est temps de faire un push, si vous n’en avez pas encore fait.

Tâche 2 : Représentation et premières méthodes

Internement, une liste de la classe ArrayList est représentée par un tableau suffisamment long pour contenir tous les éléments de la liste, aux indices consécutifs à partir de 0. Autrement dit, si la liste contient size éléments, ils sont stockés dans les cases 0 à size - 1, mais le tableau peut être plus long. On doit donc retenir séparément la longueur du tableau, que nous appellerons capacité (capacity) et le nombre d’éléments actuellement dans la liste, que nous appellerons taille (size).

Par ailleurs, les éléments doivent être consécutifs et ordonnés dans le tableau. Ainsi, pour ajouter un élément en milieu de notre liste (avec add(int index,E element)), il faut décaler d’une case dans le tableau tous les éléments d’indices index ou plus. De même pour supprimer un élément de la liste avec remove. Enfin, il est possible (mais peu inspiré) de remplacer un élément de la liste par null pour créer un trou, qui compte néanmoins pour un élément, avec set(index, null). Heureusement, la méthode add ajoute l’élément en fin de liste, donc dans la première case disponible du tableau.

À titre d’exemple, voici une représentation possible de la liste [4,1,9,7,2,3] en ArrayList de capacité 10.

Dans un premier temps, nous implémenterons toutes les méthodes comme si le tableau était de longueur infinie. Plus tard nous verrons comment agrandir le tableau lorsqu’il devient plein.

Choisir les propriétés de MyArrayList qui permettront de représenter la liste (on peut faire mieux que dans le diagramme d’objets ci-dessus).
Ajouter deux constructeurs. Le premier prend en paramètre la capacité initiale du tableau interne. Le deuxième ne prend pas d’argument, et utilise comme capacité initiale une valeur par défaut (par exemple 100). Pour initialiser le tableau, qui est un tableau d’un type générique, il faut créer un tableau d’Object, puis faire une conversion du type vers le type désiré T[], en utilisant la syntaxe du cast : (T[]) new Object[capacity]. C’est le seul usage de cast que nous autoriserons lors de ce TP. N’oubliez pas que le deuxième constructeur peut appeler le premier constructeur avec la syntaxe this(args);
Ajouter un autre constructeur, prenant une collection en argument. Laissez ce constructeur non-implémenté pour l’instant.
À ce point, vos projets doit être compilable, et vous pouvez lancer les tests. Les tests devraient échouer pour la plupart, c’est normal étant donné que tout reste à implémenter.
Implémenter les méthodes de bases : add(E elt), size(), isEmpty(), get(int index). Créer des tests pour ces méthodes.
Implémenter le troisième constructeur, celui prenant une collection en paramètre, et remplissant l’objet en construction avec tous les objets de la collection, dans l’ordre de l’itération sur cette collection. La longueur du tableau peut être fixé à deux fois la taille de la collection. Utilisez la méthode add pour ajouter les éléments !
Implémenter la méthode iterator. Pour cela créer une classe générique ArrayIterator implémentant l’interface Iterator<E>. Son constructeur reçoit une copie de la partie utilisée du tableau contenant les éléments de la liste (la classe Arrays contient une méthode statique qui vous aidera pour la copie du sous-tableau, cherchez dans la documentation officielle). Compléter cette classe avec les méthodes d’Iterator. Vous aurez besoin de garder l’indice du prochain élément que next() doit retourner. Écrire des tests pour cette classe.
Implémenter toString en utilisant la classe StringBuilder pour construire la chaîne résultat (voir les transparents du cours de L1 si vous ne savez pas comment faire).
Vous pouvez maintenant tester le comportement de MyArrayList par rapport à ArrayList. Pour l’instant, les tests reposent sur la méthode equals de ArrayList, qui elle-même repose sur l’itérateur de MyArrayList. Il faut donc faire attention à bien avoir tester l’itérateur. Certains tests vont échouer car vous n’avez pas encore implémenté les méthodes nécessaires. Vérifiez que les tests concernant les méthodes que vous avez implémentées passent (faites les corrections nécessaires). D’autres tests vont échouer parce que la capacité du tableau est fixe, nous corrigerons cela dans la prochaine tâche.
Il est temps de faire un autre push si vous ne l’avez pas encore fait.

Tâche 3 : Gestion dynamique de la capacité

Lorsque le tableau devient trop petit pour contenir les éléments de la liste, il faut le remplacer par un tableau plus grand.

Ajouter une méthode ensureCapacity(int capacity), qui sans modifier la liste, s’assure que le tableau peut contenir capacity éléments. Pour cela, ensureCapacity peut au besoin remplacer le tableau par un nouveau tableau plus grand, dans lequel on aura pris soin de copier toutes les valeurs de la liste dans les cases de mêmes indices. Comme le coût de la copie est élevé, on ne veut pas avoir à redimensionner le tableau trop souvent. On fera donc en sorte que lorsque le tableau est redimensionné, sa capacité soit doublée. À nouveau, pensez à utiliser les méthodes de la classe Arrays.
Dans toutes les méthodes modifiant le nombre d’éléments dans la liste, ajouter un appel à ensureCapacity en première instruction pour s’assurer que la liste ne déborde jamais du tableau.

Tâche 4 : Davantage de méthodes

Implémenter equals. Pour cela, compléter les instructions suivantes :

  @Override
  public boolean equals(Object obj) {
    if (this == obj) {
      return true;
    }
    if (!(obj instanceof List<?>)) {
      return false;
    }
    List<?> other = (List<?>) obj;
    // TODO: check whether this and other are equals.
  }

Implémenter et tester les méthodes set et add(int index, E elt).
Implémenter et tester les méthodes contains, indexOf, lastIndexOf.
Implémenter et tester les méthodes remove(int), remove(Object)

Tâche 5 : optionnelle

Finir l’implémentation de la classe MyArrayList, et tester.

On voudrait aussi s’assurer que le tableau n’est pas trop grand par rapport à la liste, pour ne pas gâcher de la mémoire pour rien. Pour cela, modifier ensureCapacity pour réduire la taille du tableau de moitié lorsque seulement 25% de sa taille est utilisée.

Implémentation de la classe ArrayList