CS-108 — Examen final : corrigé

La principale difficulté de cet exercice est de trouver comment stocker l'information permettant de déterminer la moyenne glissante. On peut faire deux constatations au sujet de son calcul :

• il nécessite les n dernières valeurs de la séquence — ce que l'énoncé appelle la fenêtre,
• chaque fois qu'une nouvelle valeur est produite, elle doit être ajoutée à la fenêtre, et la plus ancienne qui s'y trouve doit éventuellement en être supprimée.

En d'autres termes, il est nécessaire de stocker une séquence de valeurs, d'y ajouter de nouvelles valeurs et d'en retirer les plus anciennes. Cela suggère de les stocker dans une queue.

Une fois cette décision prise, l'adaptateur d'itérateur n'est plus très difficile à écrire. Il doit posséder les attributs suivants :

• l'itérateur sous-jacent, qui fournit les valeurs dont la moyenne glissante doit être calculée,
• la fenêtre (partielle), c-à-d la queue des (au plus) n dernières valeurs produites par l'itérateur sous-jacent,
• la taille de la fenêtre, n, nécessaire pour savoir quand la fenêtre contient effectivement assez de valeurs pour calculer la moyenne partielle.

La méthode hasNext de l'adaptateur se réfère simplement à celle de l'itérateur sous-jacent ; la méthode next fait de même mais ajoute en plus la valeur produite à la fenêtre et enlève au besoin la plus ancienne ; finalement la méthode movingAverage calcule et retourne la moyenne glissante si la fenêtre est pleine, ou alors retourne la valeur optionnelle vide. La méthode remove n'a même pas besoin d'être écrite, étant donné que la version par défaut de Iterator lève l'exception demandée.

public final class MovingAverageIteratorAdapter
    implements MovingAverageIterator {
  private final Iterator<Double> underlyingIt;
  private final int windowSize;
  private final Queue<Double> window;

  public MovingAverageIteratorAdapter(
           Iterator<Double> underlyingIt,
           int windowSize) {
    if (! (windowSize > 0))
      throw new IllegalArgumentException();
    this.underlyingIt = underlyingIt;
    this.windowSize = windowSize;
    this.window = new ArrayDeque<>(windowSize);
  }

  @Override
  public boolean hasNext() {
    return underlyingIt.hasNext();
  }

  @Override
  public Double next() {
    Double next = underlyingIt.next();
    if (window.size() == windowSize)
      window.remove();
    window.add(next);
    return next;
  }

  @Override
  public Optional<Double> movingAverage() {
    if (window.size() == windowSize) {
      double sum = 0;
      for (double e: window)
        sum += e;
      return Optional.of(sum / windowSize);
    } else
      return Optional.empty();
  }
}

La principale difficulté de cet exercice est de correctement déterminer la transformation à effectuer pour passer du repère de la fonction — le plan — à celui du composant. La manière la plus rigoureuse de déterminer les paramètres de ce changement de repère consiste à poser puis résoudre des équations liant des points dont les coordonnées sont connues dans les deux repères.

Etant donné que les axes des deux repères sont parallèles deux à deux, il est clair que le changement de repère peut se faire en combinant une translation et une dilatation. En notant \((x,y)\) les coordonnées d'un point dans le plan et \((x^\prime, y^\prime)\) ses coordonnées dans le repère du composant, on sait alors que les deux sont liés par les équations suivantes :

où \(s_x\) et \(s_y\) sont les paramètres de la dilatation et \(t_x\) et \(t_y\) ceux de la translation. Ces quatre valeurs sont les inconnues à déterminer. Pour ce faire, deux équations liant des points des deux repères suffisent, et deux points conviennent fort bien, à savoir :

1. le point en haut à gauche de la zone à afficher, qui a les coordonnées \((0,0)\) dans le repère du composant et \((x_{min}, y_{max})\) dans le plan,
2. le point en bas à droite de la zone à afficher, qui a les coordonnées \((w, h)\) dans le repère du composant — \(w\) étant la largeur et \(h\) la hauteur du composant — et \((x_{max}, y_{min})\) dans le plan.

Les équations à résoudre sont donc :

et en les résolvant, on obtient :

Une fois le changement de repère correctement déterminé, il reste à voir comment dessiner le graphe de la fonction. L'énoncé demande de le dessiner sous la forme de \(w - 1\) segments de droite, où \(w\) est la largeur du composant telle que retournée par getWidth. Dès lors, le dessin se fait naturellement au moyen d'une boucle sur les valeurs de \(x^\prime\), celles-ci étant simplement les entiers de 0 à \(w - 1\) (inclus).

Au moyen de la coordonnée \(x^\prime\) d'un point dans le repère du composant, on peut facilement déterminer sa coordonnée \(x\) dans le plan au moyen du changement de repère, puisqu'on a : \[x = \frac{1}{s_x}x^\prime - t_x = \frac{x_{max} - x_{min}}{w}x^\prime - t_x\]

En passant \(x\) à la méthode applyAsDouble de la fonction, on obtient la coordonnée \(y\) du point dans le repère du plan et il ne reste plus qu'à la repasser dans le repère du composant pour pouvoir dessiner le segment. Cela se fait au moyen de l'équation donnée plus haut, à savoir : \[ y^\prime = s_y(y + t_y) = \frac{h}{y_{min} - y_{max}}(y - y_{max}) \]

Avant de pouvoir traduire tout cela en code Java, il reste un problème à résoudre : le dessin d'un segment au moyen de la méthode drawLine nécessite bien entendu de connaître les coordonnées des deux extrémités du segment, donc d'avoir toujours une paire de points à disposition. Le plus simple pour cela consiste à stocker dans une variable (y1p ci-dessous) la coordonnée y du point de l'itération précédente, et à ne pas dessiner de segment lors de la première itération de la boucle.

En combinant ces différentes observations, on obtient finalement le code de la méthode paintComponent :

protected void paintComponent(Graphics g) {
  double fX = (maxX - minX) / getWidth();
  double fY = getHeight() / (minY - maxY);

  int y1p = 0;
  for (int x1 = 0; x1 < getWidth(); ++x1) {
    double x = fX * x1 + minX;
    double y = f.applyAsDouble(x);
    int y1 = (int) (fY * (y - maxY));
    if (x1 > 0)
      g.drawLine(x1 - 1, y1p, x1, y1);
    y1p = y1;
  }
}

La technique de sérialisation donnée dans l'énoncé ne devrait pas être très difficile à comprendre, mais sa traduction en Java est nettement moins évidente. Cela est principalement dû au fait que les bits à sérialiser sont stockés dans un entier de type int et qu'il faut utiliser les opérations bit-à-bit de Java pour y accéder.

Les explosions produites par la méthode bomb donnée dans l'énoncé diffèrent de celles du projet en trois points :

1. la portée de l'explosion est fixée à 3 cases,
2. la durée de l'explosion est fixée à 4 coups d'horloge,
3. un préfixe (a1 dans l'énoncé) est ajouté à la séquence des particules d'explosion.

Les deux premières différences sont mineures, mais la conséquence de la dernière doit être examinée en détail afin de savoir comment dessiner les particules d'explosion. Le préfixe a1 est calculé ainsi :

Sq.repeat(d.ordinal(), Sq.repeat(1, pos))

donc sa longueur dépend de la direction et vaut 0 pour N, 1 pour E, 2 pour S et 3 pour W ; son contenu est simplement une unique particule occupant la case de la bombe.

Dès lors, l'effet du préfixe a1 est de retarder le départ du train de particules constituant un bras de l'explosion, qui est lui stocké dans a2, et ce retard va de 0 coups d'horloge pour la direction N à 3 coups pour la direction W. Une fois ces constatations faites, il n'est plus très difficile de dessiner l'explosion et d'obtenir le résultat de la figure 1.