Contrôle Final 2 – Année 2022/2023
- Durée du contrôle : 1h30
- Tous les documents papier sont autorisés
Les deux exercices sont indépendants.
L'exécuteur de tâche (8 points, facile)
Le but de cet exercice est de concevoir un programme permettant d'exécuter des tâches. Une tâche est représentée par une instance de l'interface Task. Cette interface ne contient qu'une unique méthode void execute().
1 point
Donnez la définition de l'interface Task.
2 points
Donnez le code de la classe Add mettant en œuvre Task. Cette classe possède deux champs entiers a et b initialisés via un constructeur prenant deux arguments. Sa méthode execute doit retourner la somme de a et b.
2 points
Nous commençons à mettre en œuvre la classe Engine permettant d'exécuter plusieurs tâches. Engine possède un unique champ tasks. Ce champ référence une collection (classe Collection<T>) de tâches. Engine possède un unique constructeur sans argument. Ce constructeur doit initialiser tasks en lui affectant une référence vers une nouvelle instance de ArrayList<T>. Donnez le code de la classe Engine.
Pour la suite, on vous rappelle que :
- La méthode void add(T e) de Collection<T> permet d'ajouter l'élément e à la collection,
- for(T cur: tasks) { ... } où tasks est une instance de Collection<T> permet d'itérer avec cur sur chaque élément de la collection tasks.
1 points
Donnez le code de la méthode void add(Task task) de la classe Engine permettant d'ajouter une tâche à tasks.
2 points
Donnez le code de la méthode void execute() de la classe Engine permettant d'exécuter toutes les tâches stockées dans tasks.
L'arbre radix (12 points, moyen)
Un arbre radix est un arbre permettant d'associer des chaînes de caractères avec des objets. La figure ci-après illustre le principe.
La racine de l'arbre représente la chaîne vide. À chaque étage de l'arbre, on ajoute un (et un seul) caractère, par exemple le caractère "e" ou le caractère "m". Les nœuds enfants de "e" ont alors comme préfixe "e" ("em" et "ep" dans notre exemple). À chaque nœud de l'arbre peut être associé un objet. Lorsque l'objet est la référence null, c'est qu'aucune valeur n'est associée à l'étiquette. Lorsque l'objet n'est pas null, c'est qu'il existe une valeur associée à l'étiquette. Par exemple, avec l'arbre radix donné en exemple, des objets sont associés au étiquettes "m", "en", "ep", "epi".
(3 points)
La classe représentant un nœud de l'arbre s'appelle Node<T>, où T donne le type de la valeur associée au nœud. Cette classe possède un champ label de type char indiquant le caractère à ajouter au préfixe permettant d'atteindre le nœud. Par exemple, l'étiquette du nœud représenté par "epi" dans notre exemple est le caractère 'i'. Un nœud contient aussi en champ value donnant la valeur associée au nœud. Si aucune valeur n'est associé au nœud, alors value est null. Un nœud de l'arbre possède enfin des enfants: il s'agit d'un tableau de nœuds, indexé par la valeur ascii d'un caractère (on vous rappelle qu'un caractère est encodé par un nombre en Java, par exemple, le caractère 'a' est encodé par la valeur 97). Donnez :
- la définition de la classe Node<T> avec la définition de ses champs
- le code du constructeur avec un unique argument label permettant d'initialiser de façon adéquate le champ label et d'allouer le tableau des enfants.
Pour connaître la taille du tableau des enfants, il faut savoir que Character.SIZE donne le nombre de bits utilisés pour encoder un caractère en Java.
3 points
Donnez le code de la méthode void set(String str, T value) de la classe Node<T> permettant d'associer la valeur value à la chaîne de caractères str, en considérant que this est la racine. Il vous est vivement conseillé de faire un algorithme itératif. Pour accéder aux caractères de la chaîne de caractères, il faut savoir que String.toCharArray() renvoie un tableau de caractères contenant les caractères de la chaîne.
3 points
Donnez le code de la méthode T get(String str) de la classe Node<T> permettant de retourner la valeur associée à la chaîne de caractères str si une association existe, et null sinon.
3 points
Donnez le code de la méthode void enumerate(String prefix) permettant d'afficher sur le terminal l'ensemble des associations chaîne de caractères/valeur contenu dans le sous-arbre commençant par this, sachant que prefix est le préfixe permettant d'atteindre this. Vous supposerez (i) qu'ajouter le caractère associé à la racine de l'arbre à une chaîne de caractères n'a pas d'effet, et (ii) que pour énumérer l'ensemble des associations d'un arbre ayant pour racine root, l'utilisateur appelle root.enumerate(""). Pour répondre à cette question, il est nécessaire de concevoir un algorithme récursif. Il ne devrait pas être nécessaire d'utiliser une fonction annexe.
