- Cours :
- TP (L2 informatique) :
- TP (L2 math-info) :
- Annales d'examens :
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. N’oubliez pas de prendre un nom d’équipe contenant les noms des membres de l’équipe.
Une fois le dépôt téléchargé, vous pouvez compiler et tester le programme en cliquant deux fois sur myArrayList-***
-> Tasks
-> verification
-> test
dans l’onglet Gradle (il faut pour cela avoir ajouter votre projet en tant que projet Gradle; si l’IDE ne l’a pas proposé, vous pouvez cliquer droit sur le fichier build.gradle
du projet et sélectionner l’option import gradle project
. Si l’onglet gradle ne s’affiche pas, aller dans le menu View
-> Tool windows
-> Gradle
). De base, le projet ne compile pas, c’est normal ! il manque de nombreuses méthodes.
Lien vers la classroom du TP : lien.
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.
Le TP sera noté. La note tiendra compte autant de l’implémentation que de la qualité des tests que vous écrirez. Comme pour tout TP noté, nous vous demandons de ne pas partager votre programme, complet ou partiel, avec des membres d’autres équipes que la votre. Le non-respect de cette consigne vous expose à recevoir une note nulle. Tout emprunt que vous effectuez doit être proprement documenté en indiquant quelle partie de votre programme est concerné et de quelle source elle provient (nom d’un autre étudiant, site internet, etc.).
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.Ajouter une méthode
public boolean equals(Object o)
. Pour l’instant, elle doit retournertrue
si et seulement si l’objet passé en paramètre estthis
.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 appelerons capacité (capacity
) et le nombre d’éléments actuellement dans la liste, que nous appelerons 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 syntaxethis(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ériqueArrayIterator
implémentant l’interfaceIterator<E>
. Son constructeur reçoit une copie de la partie utilisée du tableau contenant les éléments de la liste (la classeArrays
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 quenext()
doit retourner. Écrire des tests pour cette classe.Implémenter
toString
en utilisant la classeStringBuilder
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éthodeequals
deArrayList
, qui elle-même repose sur l’itérateur deMyArrayList
. 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 contenircapacity
é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 classeArrays
.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 : Plus 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
etadd(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.