Test partie B

Classes et objets

Introduction

On souhaite réaliser une classe permettant de gérer des tableaux extensibles de valeurs Booléennes. Par tableau extensible, on entend qu’il est possible de lire ou d’écrire une valeur au-delà de la taille d’un tableau, ce que ne permettent pas les tableaux classiques.

Prenons un exemple. Je crée (dans une méthode) un tableau classique de boolean de longueur 5 comme ceci.

boolean[] tb = new boolean[5];

J’obtiens un tableau de 5 cellules, numérotées de 0 à 4, qui contiennent toutes la valeur false (c’est la valeur par défaut des cellules lorsqu’on crée un tableau de valeurs de type boolean).

Je peux facilement changer la valeur d’une cellule d’indice entre 0 et 4, mais si je tente d’écrire une valeur dans la cellule d’indice 7…

tb[7] = true;

… le programme s’arrête avec pertes et fracas en affichant un message d’erreur. Même problème si je tente de lire la valeur tb[10], par exemple.

Avec un tableau extensible, ces opérations sont autorisées. Imaginons que nous disposions d’une classe BoolExt représentant un tableau extensible de boolean. Pour créer un tel tableau, j’écris…

BoolExt te = new BoolExt();

… ce qui crée un tableau extensible de taille 1. Ce tableau n’a qu’une seule cellule et elle a la valeur false. Je ne peux pas l’utiliser avec les crochets car il ne s’agit pas d’un vrai tableau mais d’une instance de la classe BoolExt. Pour écrire ou lire des valeurs dans ce tableau extensible, je dois utiliser des méthodes spécifiques.

Je peux écrire une valeur à la position de mon choix, même au-delà de la taille actuelle du tableau, avec la méthode write. Par exemple…

te.write(4, true);

…a pour effet d’agrandir le tableau et de placer la valeur true en position 4. L’objet désigné par la variable te représente alors le tableau suivant.

Au lieu de produire une erreur, l’écriture dans la cellule d’indice 4 a provoqué l’agrandissement du tableau et les nouvelles cellules crées entre les indices 0 et 4 ont été remplie avec la valeur false.

Pour lire la valeur contenue dans une cellule, je dois utiliser la méthode read. Par exemple…

System.out.println(te.read(2));
System.out.println(te.read(4));

… produit l’affichage false true.

Mais il y a mieux encore. J’ai le droit de lire le contenu d’une cellule située au-delà de la fin du tableau. Au lieu de produire une erreur comme avec les tableaux ordinaires, cette opération retourne false, comme si le tableau avait une longueur illimitée et que toutes les valeurs situées après le dernier true étaient false. Ainsi, par exemple, la ligne…

System.out.println(te.read(7));

… produit l’affichage false.

Le fait d’écrire false à un emplacement situé après le dernier true, comme par exemple…

te.write(11, false);

…est équivalent à ne rien faire du tout puisque la position 11 est située au-delà de la position du dernier true (qui est à l’indice 4) et que toute lecture à cette position retournera false.

Récapitulons.

Tout se passe comme si un tableau extensible comportait une partie concrète, effectivement représentée en mémoire par un tableau de boolean, prolongé par une partie imaginaire infinie, non représentée en mémoire, dont toutes les cellules sont supposées contenir la valeur false.

On appelle taille du tableau le nombre de cellules de la partie concrète. Cette parie concrète sera effectivement représentée en mémoire par un tableau de boolean désigné par un attribut de la classe BoolExt. La partie imaginaire est le prolongement imaginaire infini de la partie concrète et toutes les cellules de cette partie imaginaire sont supposées contenir la valeur false.

Attention ! Il n’y a pas nécessairement la valeur true dans la dernière cellule de la partie concrète car pour ne pas compliquer le code, l’écriture d’une valeur false à la place du dernier true ne provoque pas le rétrécissement de la partie concrète.

Par exemple, à l’issue de l’exécution du code suivant…

BoolExt te = new BoolExt();
te.write(4, true);
te.write(3, true);
te.write(4, false);

… la partie concrète du tableau est la suivante.

Elle a une longueur égale à 5 parce qu’à un moment donné, la valeur true la plus éloignée du début était en position 4, bien qu’elle ait ensuite été remplacée par false.

Q1

Vous devez compléter la classe BoolExt en donnant les codes du constructeur et des méthodes adjust, et read. Pour comprendre le rôle de la méthode ajust, analysez le code de la méthode write.

public class BoolExt
{
   private boolean[] data;
 
   public BoolExt() 
   {
     // À compléter  
   }
 
   private void adjust(int newSize) 
   {
     // À compléter  
   }
 
   public void write(int index, boolean value) 
   {
      if((index >= data.length) && (value == true))
      {
        adjust(index+1);
      }
      data[index] = value;
   }
 
   public boolean read(int index) 
   {
     // À compléter 
   }
 
   public int size() 
   {
     return data.length;
   }
 
   public String toString()
   {
     String r = "";
     for(int i=0; i < data.length; i++)
     {
       if(data[i]) r = r + "1";
       else r = r + "0";
     }
     return r;
   }
}

La méthode ajust augmente la taille de la partie concrète, c’est-à-dire la taille du tableau désigné par l’attribut data, de manière à ce que la nouvelle taille soit égale à la valeur du paramètre newSize. En pratique, java ne permet pas de redimensionner un tableau, donc cette opération suppose de créer un nouveau tableau plus grand dans lequel le contenu de l’ancien tableau est recopié, puis de remplacer l’ancien tableau par le nouveau.

Cette méthode adjust est appelée par la méthode write lors d’une écriture d’une valeur true dans une cellule située au-delà de la limite de la partie concrète. (Dans le cas de l’écriture d’une valeur false, un agrandissement n’est pas nécessaire puisque toutes les valeurs situées dans la partie imaginaire sont considérées comme false).

Notez que la méthode toString utilise les caractères 0 et 1 à la place de false et true pour des raisons de lisibilité et concision.

Commencez par le constructeur, qui doit créer un tableau extensible de une cellule contenant false.