Examen final
corrigé

La classe UTF8OutputStreamWriter utilise le patron Adapter, puisqu'elle adapte un flot de sortie d'octets pour en faire un écrivain.

La classe UTF8OutputStreamWriter doit bien entendu stocker le flot de sortie sous-jacent, dans lequel elle écrit les octets correspondants aux caractères qu'on lui fournit, ce qui est fait dans le constructeur.

La méthode write est relativement simple : elle parcourt les caractères de la portion du tableau désignée par offset et length, encode chacun d'eux en 1 à 3 octets selon la description de l'énoncé, et écrit ceux-ci dans un tableau. Une fois l'encodage terminé, le contenu de ce tableau est écrit en une fois dans le flot sous-jacent.

Finalement, la méthode close ne fait rien d'autre que fermer le flot sous-jacent.

public final class UTF8OutputStreamWriter extends Writer {
  private final static int MSB_1 = 0b10000000;
  private final static int MSB_2 = 0b11000000;
  private final static int MSB_3 = 0b11100000;
  private final static int LSB_6 = 0b00111111;

  private final OutputStream s;

  public UTF8OutputStreamWriter(OutputStream s) {
    this.s = s;
  }

  @Override
  public void write(char[] chars, int offset, int length)
      throws IOException {
    byte[] bs = new byte[length * 3];
    int n = 0;

    for (int i = offset; i < offset + length; ++i) {
      char c = chars[i];
      if (c <= 0x7F) {
        bs[n++] = (byte) c;
      } else if (c <= 0x7FF) {
        bs[n++] = (byte) (MSB_2 | (c >> 6));
        bs[n++] = (byte) (MSB_1 | (c & LSB_6));
      } else {
        bs[n++] = (byte) (MSB_3 | (c >> 12));
        bs[n++] = (byte) (MSB_1 | ((c >> 6) & LSB_6));
        bs[n++] = (byte) (MSB_1 | (c & LSB_6));
      }
    }

    s.write(bs, 0, n);
  }

  @Override
  public void close() throws IOException {
    s.close();
  }
}

Pour pouvoir dessiner correctement les rayons, il faut tout d'abord déterminer l'angle de vue vertical. Pour ce faire, on calcule dans un premier temps l'angle séparant deux échantillons, au moyen de la formule donnée à l'étape 5 :

\[ \delta = \frac{v_h}{w - 1} = \frac{90°}{9} = 10° \]

Cela fait, étant donné que la hauteur du panorama est de 7 échantillons, on sait que l'angle de vue vertical est :

\[ v_f = v_h\,\frac{h - 1}{w - 1} = 90°\,\frac{6}{9} = 60° \]

Dès lors, comme l'angle d'élévation central est toujours 0°, les 7 rayons correspondant aux échantillons vont de -30° à +30° et sont séparés de 10°. Sachant cela, les dessiner ne pose pas de problème, il suffit de commencer à l'angle -30° puis de tracer les rayons partiels jusqu'à sortir du profil. Le 7^e rayon n'est jamais lancé.

Vu du dessus, la zone visible est en gros un triangle rectangle orienté plein nord, dont le sommet à 90° occupe la position de l'observateur.

Étant donnés les calculs effectués à la partie 1, annoter l'image du panorama ne pose pas de gros problème, il faut juste penser à utiliser des azimuts canoniques comme demandé dans l'énoncé.

Les patrons utilisés par les différentes classes sont :

1. StringRope : Adapter,
2. SubRope : Decorator,
3. ConcatRope : Composite.

La classe StringRope est triviale, sachant que les méthodes length et charAt ont un équivalent direct dans String et writeTo a un équivalent dans Writer.

final class StringRope implements Rope {
  private final String str;

  public StringRope(String s) {
    this.str = s;
  }

  @Override
  public int length() {
    return str.length();
  }

  @Override
  public char charAt(int i) {
    return str.charAt(i);
  }

  @Override
  public void writeTo(Writer w, int o, int l)
      throws IOException {
    w.write(str, o, l);
  }
}

La classe SubRope n'est pas beaucoup plus difficile à écrire que StringRope, puisqu'elle doit principalement ajuster les positions reçues par les différentes méthodes avant de les transmettre à la corde sous-jacente.

Il faut toutefois bien prendre garde à valider les index, positions de départ et longueurs passées aux différentes méthodes pour s'assurer qu'elles sont bien valides pour la sous-corde, et pas seulement pour la corde sous-jacente.

final class SubRope implements Rope {
  private final Rope rope;
  private final int offset, length;

  public SubRope(Rope rope, int offset, int length) {
    if (! (0 <= offset && offset <= rope.length()))
      throw new IndexOutOfBoundsException();
    if (! (0 <= offset + length
           && offset + length <= rope.length()))
      throw new IndexOutOfBoundsException();

    this.rope = rope;
    this.offset = offset;
    this.length = length;
  }

  @Override
  public int length() {
    return length;
  }

  @Override
  public char charAt(int i) {
    if (! (0 <= i && i < length))
      throw new IndexOutOfBoundsException();

    return rope.charAt(offset + i);
  }

  @Override
  public void writeTo(Writer w, int o, int l)
      throws IOException {
    if (! (0 <= o && o <= length))
      throw new IndexOutOfBoundsException();
    if (! (0 <= o + l && o + l <= length))
      throw new IndexOutOfBoundsException();

    rope.writeTo(w, offset + o, l);
  }
}

La classe ConcatRope est relativement simple à écrire, sauf sa méthode writeTo. La solution retenue ici pour cette dernière consiste à distinguer 3 cas :

1. la totalité de la portion à écrire est dans la sous-corde de gauche,
2. la totalité de la portion à écrire est dans la sous-corde de droite,
3. la portion à écrire chevauche les deux sous-cordes.

Une fois cette distinction faite, effectuer les bons appels à la méthode writeTo des deux sous-cordes n'est pas excessivement difficile.

final class ConcatRope implements Rope {
  private final Rope l, r;

  public ConcatRope(Rope l, Rope r) {
    this.l = l;
    this.r = r;
  }

  @Override
  public int length() {
    return l.length() + r.length();
  }

  @Override
  public char charAt(int i) {
    return i < l.length()
      ? l.charAt(i)
      : r.charAt(i - l.length());
  }

  @Override
  public void writeTo(Writer w, int offset, int length)
      throws IOException {
    if (offset + length <= l.length()) {
      l.writeTo(w, offset, length);
    } else if (l.length() <= offset) {
      r.writeTo(w, offset - l.length(), length);
    } else {
      int lLen = l.length() - offset;
      l.writeTo(w, offset, lLen);
      r.writeTo(w, 0, length - lLen);
    }
  }
}

La principale difficulté du constructeur de Intervals est la validation de la liste d'intervalles reçue. Cela dit, elle peut se faire relativement simplement en constatant qu'une condition nécessaire et suffisante pour qu'une liste d'intervalles soit valide est que la distance (signée) entre le début d'un intervalle et la fin de son précédesseur soit strictement supérieure à 1.

public Intervals(List<Interval1D> intervals) {
  Interval1D prevI = null;
  for (Interval1D currI: intervals) {
    int currFrom = currI.includedFrom();
    if (prevI != null
        && !(currFrom - prevI.includedTo() > 1))
      throw new IllegalArgumentException();
    prevI = currI;
  }

  this.intervals =
    unmodifiableList(new ArrayList<>(intervals));
}

public List<Interval1D> intervals() {
  return intervals;
}

La taille d'un ensemble est simplement la somme de la taille des intervalles, qui peut se calculer soit de manière classique :

public int size() {
  int size = 0;
  for (Interval1D i: intervals)
    size += i.size();
  return size;
}

soit au moyen de la programmation par flots :

public int size1() {
  return intervals.stream()
    .mapToInt(Interval1D::size)
    .sum();
}

Une version basique de la méthode contains n'est pas très difficile à écrire, il suffit de parcourir les intervalles et de voir si l'un d'eux contient l'élément recherché.

Pour obtenir la version optimisée demandée dans l'énoncé, il faut de plus retourner (la valeur false) dès que l'on sait qu'aucun des intervalles restants ne peut contenir l'élément recherché. Etant donné que les intervalles sont triés en ordre croissant, cela est le cas dès que la borne inférieure de celui en cours d'inspection est strictement plus grande que l'élément recherché.

public boolean contains(int v) {
  for (Interval1D i: intervals) {
    if (i.includedFrom() > v)
      return false;
    if (i.contains(v))
      return true;
  }
  return false;
}

La méthode union est de loin la plus compliquée de cet exercice, et même de tout l'examen.

La technique utilisée ici consiste à parcourir les deux listes d'intervalles en parallèle (l et r ci-dessous), tant qu'aucune d'entre-elles n'est vide, et à chaque itération, distinguer deux cas :

1. les intervalles en tête des deux listes sont unionables, auquel cas on les supprime de leur liste, calcule leur union et la place dans la liste qui contenait l'intervalle de tête se terminant en dernier, ce qui garantit que les deux listes restent canoniques,
2. les intervalles en tête des deux listes ne sont pas unionables, auquel cas le plus petit d'entre eux est retiré et ajouté au résultat partiel m.

Une fois ce processus terminé, l'une des deux listes est vide, et le contenu de l'autre peut être ajouté en queue du résultat partiel calculé jusque-là.

public Intervals union(Intervals that) {
  List<Interval1D> l = new LinkedList<>(this.intervals());
  List<Interval1D> r = new LinkedList<>(that.intervals());
  List<Interval1D> m = new ArrayList<>();

  while (! (l.isEmpty() || r.isEmpty())) {
    Interval1D i = l.get(0), j = r.get(0);
    if (i.isUnionableWith(j)) {
      Interval1D h = l.remove(0).union(r.remove(0));
      (h.includedTo() == i.includedTo() ? l : r)
        .add(0, h);
    } else
      m.add((i.includedFrom() < j.includedFrom() ? l : r)
            .remove(0));
  }
  m.addAll(l);
  m.addAll(r);
  return new Intervals(m);
}

Oui, la classe Intervals doit redéfinir les méthodes equals et hashCode, car il s'agit d'une classe immuable dont les instances doivent donc être comparées de manière structurelle.

Etant donné que chaque ensemble ne possède qu'une seule liste d'intervalles canonique le représentant, et que les intervalles et les listes Java sont comparés par structure, la définition de ces deux méthodes est triviale.

@Override
public int hashCode() {
  return intervals.hashCode();
}

@Override
public boolean equals(Object thatO) {
  return (thatO instanceof Intervals)
    && intervals.equals(((Intervals)thatO).intervals());
}