Tableur

CS-108 — Corrigé de la série 7

Introduction

Le code du corrigé est disponible sous la forme d'une archive Zip, qui contient également le code de l'énoncé.

Exercice 1

Les interfaces Subject et Observer sont identiques à celles présentées dans le cours.

public interface Subject {
  public void addObserver(Observer o);
  public void removeObserver(Observer o);
}

public interface Observer {
  public void update(Subject s);
}

La classe AbstractSubject doit simplement stocker les observateurs dans une collection quelconque et offrir les méthodes d'ajout, de suppression et de notification des observateurs.

Ici, nous avons choisi de stocker les observateurs dans une liste, qui a l'avantage d'avoir un ordre de parcours déterministe et de tolérer les doublons. Cela est important car si un même observateur est ajouté plusieurs fois à un sujet, il est logique qu'il faille le même nombre de suppressions pour qu'il n'observe plus le sujet.

public abstract class AbstractSubject implements Subject {
  private final List<Observer> observers = new ArrayList<>();

  @Override
  public void addObserver(Observer o) {
    observers.add(o);
  }

  @Override
  public void removeObserver(Observer o) {
    observers.remove(o);
  }

  protected void notifyObservers() {
    for (Observer o : observers) o.update(this);
  }
}

Une fois ces classes écrites, il faut faire en sorte que les instances de la classe Cell soient observables. Cela consiste premièrement à la faire hériter de AbstractSubject et deuxièmement à faire en sorte qu'elle appelle la méthode notifyObservers lorsque sa valeur change. Cela se fait simplement dans la méthode setValue, et pour éviter les notifications inutiles, uniquement dans le cas où la nouvelle valeur diffère de l'ancienne. Les parties modifiées de la classe Cell sont donc :

public final class Cell extends AbstractSubject {

  // … autres méthodes

  public void setValue(int newValue) {
    if (newValue != value) {
      value = newValue;
      notifyObservers();
    }
  }
}

Les cellules étant désormais observables, il faut encore faire en sorte qu'elles observent les cellules dont elles dépendent.

Cela implique premièrement d'ajouter à la méthode setFormula des appels à removeObserver — pour ne plus observer les cellules dont on ne dépend plus — et des appels à addObserver — pour observer les cellules dont on dépend désormais.

D'autre part, il faut aussi écrire une méthode permettant de calculer la nouvelle valeur de la cellule, qui est appelée d'une part lorsqu'une cellule dont on dépend change de valeur et d'autre part lorsque la formule attachée à la cellule change. Cette méthode est nommée updateContent ci-dessous.

public final class Cell
  extends AbstractSubject
  implements Observer {

  // … autres méthodes

  public void setFormula(String newContentString,
			 List<Cell> newArguments,
			 IntBinaryOperator newOperator) {
    for (Cell arg : arguments) arg.removeObserver(this);
    for (Cell newArg : newArguments) newArg.addObserver(this);

    // … comme avant

    updateContent();
  }

  @Override
  public void update(Subject s) {
    updateContent();
  }

  private void updateContent() {
    int arg0 = arguments.size() > 0
      ? arguments.get(0).getValue()
      : 0;
    int arg1 = arguments.size() > 1
      ? arguments.get(1).getValue()
      : 0;

    setValue(operator.applyAsInt(arg0, arg1));
  }
}

Exercice 2

Lorsqu'on entre 1 dans C1, on obtient une StackOverflowError sur la console. Suivant comment la méthode setValue de Cell a été écrite, il est également possible que cette exception soit levée dès la modification de B1.

La raison de cette exception est que les formules des cellules A1 et B1 se référencent mutuellement et que dès qu'on entre 1 dans C1, une séquence (conceptuellement) infinie de mises à jour se produisent, ce qui provoque l'exception.

On peut comprendre le problème en regardant les valeurs successives que l'on attribue à A1 et B1, qui valent 0 juste avant la modification de C1, au moment où l'on attribue la valeur 1 à C1. En admettant que A1 soit mise à jour avant B1, on a :

  1. A1 = B1 + C1 = 0 + 1 = 1,
  2. B1 = A1 + C1 = 1 + 1 = 2,
  3. A1 = B1 + C1 = 2 + 1 = 3,
  4. B1 = A1 + C1 = 3 + 1 = 4,
  5. A1 = B1 + C1 = 4 + 1 = 5,
  6. B1 = A1 + C1 = 5 + 1 = 6,
  7. etc.

Si la pile d'exécution (stack) de l'ordinateur était illimitée, cette séquence de mise à jour continuerait à l'infini. Mais comme cette pile a une capacité limitée, elle devient pleine au bout d'un moment et on obtient alors l'exception qui signale ce fait (stack overflow).

Pour résoudre ce problème, il faudrait vérifier lors de chaque ajout d'un observateur que celui-ci ne crée pas un cycle dans le graphe d'observation, ce qui est assez difficile à mettre en œuvre avec le patron Observer tel qu'il existe.

Exercice 3

Lorsqu'on entre la valeur 4 dans A1, on obtient normalement une exception due à une division par zéro. C'est en tout cas ce qui se produit avec le code du corrigé, qui utilise une liste pour stocker les observateurs d'un sujet, et qui ajoute les nouveaux observateurs à la fin de cette liste.

Pour comprendre le pourquoi de cette division par zéro, il faut examiner les valeurs des cellules qui nous intéressent juste avant que 4 ne soit entré dans A1, et qui sont :

  1. A1 = 5,
  2. B1 = 1,
  3. C1 = 4,
  4. C2 = 1,
  5. C3 = 1.

Ensuite, lorsque 4 est entré dans A1, étant donné l'ordre dans lequel les cellules ont été modifiées, le premier observateur a être notifié du changement de valeur de A1 est C2, dont la valeur devient 0. Ce changement est propagé aux observateurs de C2, en l'occurrence la cellule C3 qui calcule la division B1/C3 qui provoque l'erreur.

Il est intéressant de constater que, si l'on voit les formules entrées dans les cellules du tableur comme des équations mathématiques, une division par zéro n'est normalement pas possible. En effet, en récrivant la formule donnant la valeur de C3, on obtient successivement :

C3 = B1 / C2
   = 1 / C2
   = 1 / (A1 - C1)
   = 1 / (A1 - (A1 - B1))
   = 1 / B1
   = 1 / 1
   = 1

Donc théoriquement, C3 devrait toujours valoir 1. Mais comme dans le tableur les nouvelles valeurs ne sont pas propagées instantanément, les cellules peuvent temporairement avoir une valeur théoriquement impossible. Ce problème est nommé glitch, en référence au problème similaire rencontré en électronique.