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

Exam de Java Avance

Exercice 1 - DynamicArray

Les langages PHP et Javascript possèdent un seul objet pour représenter les tableaux dynamiques (qui s'agrandissent tout seul) et les tables de hachage. Cette implantation change sa représentation interne en fonction des appels qui sont effectués.
Avec l'exemple suivant

 
      array = {}
      array[0] = 'hello'
      array[1] = 'world'

la représentation interne utilise un tableau avec un index sur le dernier élement (comme ArrayList en fait) pour être plus compacte en mémoire, mais si le code suivant est ajouté

      array[12006] = 'blah'

alors l'implantion change pour utiliser une table de hachage qui à 0 associe 'hello', à 1 associe 'world' et à 12006 associe 'blah'.
On souhaite écrire une classe DynamicArray qui utilise le même concept. Pour simplifier l'implantation, la classe sera capable de changer son implantation interne d'un tableau dynamique vers une table de hachage mais ne sera pas capable de faire le chemin inverse.
Pour que l'implantation soit compacte, celle-ci possèdera seulement deux champs, un champ data qui à l'exécution contiendra soit un tableau d'objets soit une table de hachage en fonction de la représentation courante et un champs top qui contiendra l'index du prochain élément à insérer si aucun index n'est spécifié. On peut noter que dans le cas où data est un tableau, top correspond aussi au nombre d'élements dans le tableau.

    public class DynamicArray {
                            // as an array              | as a map
      private Object data;  // array of objects         | map of integer/object
      private int top;      // insertion index for push | insertion index for push

L'implantation de DynamicArray devra être paramétrée par le type d'élement et ne devra pas permettre de stocker null.
Enfin, on ne vous demande pas de ré-implanter une table de hachage (même si cela serait plus efficace en mémoire); utiliser une implantation déjà existante suffira pourvu qu'elle conserve l'ordre d'insertion des élements. Par contre, pour le tableau dynamique, on vous demande de ne pas utiliser ArrayList pour fournir une implantation plus compacte en mémoire, le tableau s'agrandira tout seul si nécessaire en doublant sa taille.
Les tests JUnit sont dans la classe DynamicArrayTest.java.

Ecrire la classe DynamicArray avec
- un constructeur public sans paramètre (qui dans ce cas créera un tableau vide de 8 cases),
- une méthode statique create premettant de créer un nouveau DynamicArray en prenant en paramètre des élements séparés par des virgules et utilisant la représentation par tableau.
  Note: top aura pour valeur 0 si il n'y a pas d'élement.
- une méthode createSparse sans paramètre, retournant un nouveau DynamicArray vide utilisant la représentation sous forme de table de hachage.
  Note: top aura pour valeur 0.
- une méthode push prenant un élement en paramètre et ajoutant celui-ci dans le DynamicArray courant (à la position top),
- et enfin une méthode isSparse qui renvoie vrai si l'implantation utilise une table de hachage ou faux si l'implantation utilise un tableau dynamique.
Modifier l'implantation pour permettre d'afficher le contenu d'un DynamicArray en affichant des couples index/élements en utilisant le même format que celui des map.
L'affichage du tableau array donné en exemple ci-dessus serait donc
```
        {0=hello, 1=world, 12006=blah}
      
```
L'ordre d'affichage des élements est l'ordre d'insertion des élements.
Ecrire une méthode statique createFromMap prenant une Map en paramètre dont on vérifiera que les clé et valeurs ne sont pas null et créant un nouveau DynamicArray utilisant la représentation sous forme de table de hachage, et dont les paires clé/valeur sont les mêmes que celles de la Map passée en argument.
Note: top aura pour valeur l'index maximum + 1 ou 0 si la map est vide.
Ecrire les méthodes
- size qui renvoie le nombre d'élements dans le DynamicArray.
- get qui prend un index et renvoie l'élement à l'index ou null si celui-ci n'existe pas.
  Note: array.get(-20) renvoie aussi null.
- Ecrire une méthode set qui prend en paramètre un index et un élement et permet de changer la valeur d'une case ou de créer une nouvelle case dans le DynamicArray courant.
  Dans le cas où l'implantation est un tableau dynamique:
  - si l'index correspond à l'index du dernier élement plus 1, le tableau sera agrandi si nécessaire,
  - si l'index est dans les bornes du tableau, la valeur de la case sera changée,
  - sinon, le DynamicArray changera d'implantation pour utiliser une table de hachage.
  Note: attention à ce que top soit bien mis à jour si nécesssaire.
Ecrire une méthode valueIterator qui renvoie un iterateur sur les valeurs dans l'ordre d'insertion de celles-ci. L'itérateur ne devra pas permettre de supprimer des élements.
Ecrire une méthode delete qui prend en paramètre un index et supprime l'élement à l'index indiqué. L'implantation interne devra être changée si nécessaire. La méthode delete devra retourner l'élement supprimé ou null si jamais il n'y aucun élement à l'index indiqué.
Note: attention à ce que top soit bien mis à jour si nécesssaire.