:: Enseignements :: ESIPE :: E4INFO :: 2013-2014 :: Java Avancé ::

TP noté de Java Avance

Le TP consiste à implanter de deux façons différentes un arbre lexicographique.
Rappel, vous devez utiliser eclipse-lambda, configurer le JRE pour qu'il pointe sur /usr/local/apps/Java8 et le compilateur pour utiliser la version 1.8. Enfin, vous devez configurer le workspace d'eclipse (File > Switch WorkSpace) pour qu'il corresponde au répertoire EXAM que vous avez dans le home de votre session de TP noté.

Exercice 1 - Arbre Lexicographique

Un arbre lexicographique, (trie en anglais) est un arbre qui permet de stocker des chaines de caractères avec la propriété que deux chaines de caractères ayant un préfix commun ("bab" est le préfix commun de "baba" et "baby") vont être représentées en utilisant des noeuds communs.
La première implémentation étudiée utilise un noeud contenant une lettre, une liste de noeuds fils et un booléen indiquant si le noeud correspond à la dernière lettre d'un mot. Un trie est initialisé avec un noeud racine qui stocke la lettre '\0' (par convention), qui a une liste vide de fils et qui n'est pas la dernière lettre d'un mot.
On peut donc représenter ce noeud racine comme ceci:

                 '\0' [] false

La classe ListTrie possède deux opérations de base, la méthode void add(String) qui permet d'ajouter une chaine à un arbre et une méthode boolean contains(String) qui indique si un mot se trouve dans l'arbre.
Par exemple, add("baba") correspond à l'arbre

                 '\0' [ ] false
                       |
                  'b' [ ] false
                       |
                  'a' [ ] false
                       |
                  'b' [ ] false                   <-------
                       |
                  'a' []  true

Donc un appel à contains("baba") va renvoyer true alors qu'un appel à contains("bab") va renvoyer false car le noeud fléché avec <------- indique que la lettre n'est pas la fin d'un mot.
et si on exécute add("baby") sur l'arbre, on obtient:

                  
                 '\0' [ ] false
                       |
                  'b' [ ] false
                       |
                  'a' [ ] false
                       |
                 'b' [ , ] false                  
                      / \
                     /   \
                    /     \
          'a' [] true    'y' [] true

Les tests JUnit sont dans la classe ListTrieTest.java.

Déclarer la classe ListTrie dans le package fr.umlv.tpnote, ainsi qu'un constructeur sans paramètre initialisant l'arbre lexicographique.
Pour représenter les noeuds de l'arbre, vous utiliserez une classe interne.
Attention, à utiliser les bons modificateurs dans votre code.
Ecrire la méthode add.
Rappel: il existe les méthodes length et charAt dans la classe java.lang.String.
Ecrire la méthode contains.
On cherche maintenant à écrire une méthode void forAll(Consumer<String>) qui appelle la méthode accept du consumer (de la classe java.util.function.Consumer) passé en paramètre, pour toutes les chaines de caractères stockées dans l'arbre lexicographique.
Par exemple, le code suivant doit afficher "baba" puis "baby".
```
        ListTrie trie = new ListTrie();
        trie.add("baba");
        trie.add("baby");
        trie.forAll(new Consumer<String>() {
          public void accept(String word) {
            System.out.println(word);
          }
        });
      
```
Ecrire une classe Main ainsi qu'une méthode main. Copier le code de la question précédente et modifiez le pour utiliser la syntaxe des lambdas.
Ajouter dans la méthode main un appel à forAll qui stocke les chaines de caractères dans une ArrayList en utilisant la syntaxe des méthodes références.
Ajouter dans la classe ListTrie une méthode ListTrie prefix(String) qui renvoie sans le dupliquer un arbre lexicographique correspondant à un préfix particulier. Le ListTrie renvoyé doit permettre de modifier le ListTrie à partir duquel il a été construit, donc par exemple, le code suivant doit fonctionner.
```
        ListTrie trie = new ListTrie();
        trie.add("baba");
        ListTrie trie2 = trie.prefix("bab");
        trie2.add("y");
        System.out.println(trie.contains("baby")); // true
      
```
Note: Penser à partager le code avec le code déjà existant.

Exercice 2 - Arbre Lexico 2

On souhaite créer une seconde implantation d'un arbre lexicographique dans la classe HashTrie.
Chaque noeud de l'arbre contient toujours le booléen indiquant si le noeud correspond à un mot mais la lettre a disparue et au lieu d'utiliser une liste, on utilise une table de hachage qui associe à une lettre le noeud correspondant.
L'arbre vide sera donc représenté par le noeud racine suivant:

                    {} false

Après un, add("baba") on obtiendra l'arbre suivant

                  {('b', )} false
                        |
                  {('a', )} false
                        |
                  {('b', )} false
                        |
                  {('a', )} false 
                        |
                      {} true

Puis si on exécute add("baby") sur l'arbre, on obtient:

                  {('b', )} false
                        |
                  {('a', )} false
                        |
                  {('b', )} false
                        |
               {('a', ), ('y', )} false 
                    /         \
                   /           \
               {} true       {} true

Les tests JUnit sont dans la classe HashTrieTest.java.

Ecrire la classe HashTrie toujours dans le package fr.umlv.tpnote ainsi que les méthodes add et contains.
Ecrire la méthode forAll.
Ecrire la méthode prefix.
Finalement, on veut manipuler indifféremment un ListTrie et un HashTrie en définissant le type abstrait Trie.
Modifier votre code en conséquence sachant que l'on peut remarquer qu'il est possible de partager le code des méthodes prefix entre les deux implantations.