Examen final

La seule difficulté du constructeur est de créer correctement le tableau destiné à contenir l'échantillon. Idéalement, on aimerait créer un tableau dont les éléments ont le type T, en écrivant new T[size], mais cela est interdit en Java en raison de limitations de la généricité. Il faut donc créer un tableau dont les éléments ont le type Object puis le « transtyper » afin de pouvoir le stocker dans l'attribut samples.

public Sampler(RandomGenerator rng, int size) {
  if (!(size >= 0)) throw new IllegalArgumentException();

  this.rng = rng;
  this.count = 0; // Optionnel
  this.samples = (T[]) new Object[size];
}

La méthode accept doit distinguer deux cas, en fonction de si le nombre de valeurs qui lui ont été passées est inférieur ou non à la taille désirée de l'échantillon.

Lorsque le nombre de valeurs passées à accept est inférieur à la taille de l'échantillon, c.-à-d. que count < samples.length, on se contente de stocker l'élément dans la prochaine position libre du tableau samples.

Sinon, on tire un nombre aléatoire compris entre 0 et le nombre de valeurs passées à accept (inclus, d'où le count + 1 passé à nextInt), et si cette valeur est dans les bornes du tableau samples, on stocke le nouvel élément à cet index.

public void accept(T value) {
  if (count < samples.length) {
    samples[count] = value;
  } else {
    int j = rng.nextInt(count + 1);
    if (j < samples.length) samples[j] = value;
  }
  count += 1;
}

La seule petite difficulté de la méthode samples est qu'il faut tenir compte du cas où le nombre de valeurs passées à accept est inférieur à la taille désirée de l'échantillon, ce qui peut se faire en utilisant le minimum de ces deux valeurs pour déterminer la taille de la liste à retourner.

Il faut de plus se souvenir du fait qu'une liste immuable est demandée en résultat, que l'on peut obtenir soit en effectuant une copie immuable de la liste créée au moyen de List.copyOf, soit en retournant une vue immuable sur cette liste au moyen de Collections.unmodifiableList.

public List<T> samples() {
  List<T> samplesL = new ArrayList<>();
  for (int i = 0; i < Math.min(count, samples.length); i += 1)
    samplesL.addLast(samples[i]); // ou : samplesL.add(…)
  return List.copyOf(samplesL);   // ou : unmodifiableList(…)
}

Bien entendu, il est aussi possible — et passablement plus simple — d'utiliser la programmation par flots pour écrire cette méthode :

public List<T> samples() {
  return Arrays.stream(samples)
    .limit(count)
    .toList();
}

Produire l'image d'un rectangle n'est pas totalement trivial, car il faut trouver un moyen simple de déterminer si les coordonnées passées à charAt se trouvent sur le pourtour du rectangle ou non.

La solution retenue ci-dessous consiste à tout d'abord déterminer si ces coordonnées se trouvent à l'extérieur du rectangle. Si c'est le cas, une espace est retournée. Sinon, deux variables booléennes sont calculées : onH qui est vraie ssi les coordonnées se trouvent sur un bord horizontal du rectangle (haut ou bas) ; onV qui est vraie ssi les coordonnées se trouvent sur un bord vertical du rectangle (gauche ou droit).

Une fois ces deux valeurs booléennes calculées, déterminer le caractère à retourner se fait par simple disjonction de cas :

• si onH et onV sont vraies, les coordonnées correspondent à un coin, on retourne donc +,
• sinon, si onH est vraie, les cordonnées correspondent à un bord horizontal, on retourne donc -,
• sinon, si onV est vraie, les coordonnées correspondent à un bord vertical, on retourne donc |,
• sinon, les coordonnées sont celles d'un caractère situé (strictement) à l'intérieur du rectangle, on retourne donc une espace.

static TextImage rectangle(int width, int height) {
  if (!(width >= 2 && height >= 2))
    throw new IllegalArgumentException();

  return (r, c) -> {
    if (!(0 <= r && r < height && 0 <= c && c < width))
      return ' ';

    boolean onH = r == 0 || r == height - 1;
    boolean onV = c == 0 || c == width - 1;
    if (onH & onV) return '+';
    if (onH) return '-';
    if (onV) return '|';
    return ' ';
  };
}

La méthode over ne pose pas de problème particulier, il faut juste se souvenir que le récepteur est l'image d'avant-plan, et que pour obtenir son caractère aux coordonnées données, il faut donc appeler la méthode charAt de this. Une fois ce caractère obtenu, il est retourné tel quel sauf s'il s'agit d'une espace, auquel cas le caractère de l'image d'arrière-plan (that) est retourné.

default TextImage over(TextImage that) {
  return (r, c) -> {
    char thisC = this.charAt(r, c); // ou : charAt(r, c)
    return thisC != ' ' ? thisC : that.charAt(r, c);
  };
}

La seule difficulté pour écrire la méthode translated est de se souvenir du fait qu'il faut toujours appliquer aux coordonnées reçues la transformation inverse de celle que l'on désire appliquer à l'image, et donc que les déplacements passés à translated doivent être soustraits et pas ajoutés aux coordonnées.

default TextImage translated(int dR, int dC) {
  return (r, c) -> charAt(r - dR, c - dC);
}

La méthode get doit parcourir l'arbre pour trouver le nœud correspondant à la clef donnée, afin de retourner la valeur associée.

Pour cela, il suffit de commencer à la racine — qui n'est jamais null — puis, tant que tous les octets de la clef n'ont pas été parcourus, continuer avec l'enfant correspondant au prochain octet, nommé bS dans le code ci-dessous. Cet enfant s'obtient bien entendu du tableau children, à l'index bS, interprété de manière non signée.

Lors de ce parcours, il faut bien faire attention au fait que l'enfant sur lequel on désire se déplacer peut ne pas exister. Dans ce cas, cela signifie que la clef n'existe pas dans l'arbre, et il faut donc retourner NO_VALUE.

public int get(byte[] key) {
  Node n = root;
  for (byte bS : key) {
    n = n.children[Byte.toUnsignedInt(bS)];
    if (n == null) return Node.NO_VALUE;
  }
  return n.value;
}

La méthode put doit parcourir l'arbre pour trouver le nœud correspondant à la clef donnée, afin de lui attacher la valeur donnée.

Pour cela, elle procède de manière similaire à get, la différence étant que lorsqu'elle rencontre un enfant null, elle en crée un nouveau qu'elle stocke dans le tableau des enfants du nœud courant.

Une fois le nœud correspondant à la clef atteint, la valeur à associer à la clef y est stockée. Avant cela, la taille de l'arbre est incrémentée si et seulement si aucune valeur n'était précédemment associée au nœud.

public void put(byte[] key, int value) {
  if (value == Node.NO_VALUE)
    throw new IllegalArgumentException();

  Node n = root;
  for (byte bS : key) {
    int b = Byte.toUnsignedInt(bS);
    if (n.children[b] == null) n.children[b] = new Node();
    n = n.children[b];
  }
  if (n.value == Node.NO_VALUE) size += 1;
  n.value = value;
}

La manière la plus simple d'écrire la méthode forEach consiste à suivre les indications de l'énoncé et à utiliser une pile de paires de nœuds à visiter et de la clef qui leur correspond. Cette pile se nomme toVisit dans le code ci-dessous.

Initialement, cette pile ne contient que la racine de l'arbre, à laquelle la clef vide est associée.

Ensuite, tant que cette pile n'est pas vide, la paire clef/nœud qui se trouve à son sommet en est retirée. Tous les enfants du nœud sont ajoutés à la pile avec la clef qui leur correspond, puis le consommateur est appelé avec la paire clef/valeur ssi une valeur est associée au nœud courant.

public void forEach(BiConsumer<byte[], Integer> consumer) {
  List<KeyNode> toVisit = new ArrayList<>(
    List.of(new KeyNode(new byte[0], root)));
  while (!toVisit.isEmpty()) {
    KeyNode keyNode = toVisit.removeLast();
    Node[] children = keyNode.node.children;
    for (int i = 0; i < children.length; i += 1) {
      if (children[i] == null) continue;
      byte[] cKey = Arrays.copyOf(keyNode.key,
                                  keyNode.key.length + 1);
      cKey[cKey.length - 1] = (byte) i;
      toVisit.addLast(new KeyNode(cKey, children[i]));
    }
    if (keyNode.node.value != Node.NO_VALUE)
      consumer.accept(keyNode.key, keyNode.node.value);
  }
}

Comme souvent, la solution la plus simple pour écrire l'itérateur consiste à « traduire » la méthode forEach en un itérateur. Cela signifie que l'itérateur doit conserver un état similaire à celui utilisé par forEach pour son parcours — ici une pile de paires clef/nœud — et faire en sorte que l'itération puisse être contrôlée depuis l'extérieur — via des appels à la méthode next — plutôt que depuis l'intérieur comme dans forEach.

Lors de cette traduction, on constate qu'il n'est pas évident de déterminer, en utilisant uniquement toVisit, si l'itération est terminée ou non, et la rédaction de hasNext n'est donc pas évidente. La solution retenue ici est la même que celle utilisée dans les mises en œuvre des collections vues au cours, et consiste à ajouter à l'itérateur un attribut remaining contenant le nombre d'éléments qu'il lui reste à fournir.

public Iterator<KeyValue> iterator() {
  return new Iterator<>() {
    int remaining = size;
    final List<KeyNode> toVisit = new ArrayList<>(
      List.of(new KeyNode(new byte[0], root)));

    @Override
    public boolean hasNext() {
      return remaining > 0;
    }

    @Override
    public KeyValue next() {
      if (!hasNext()) throw new NoSuchElementException();
      KeyNode keyNode;
      do {
        keyNode = toVisit.removeLast();
        Node[] children = keyNode.node.children;
        for (int i = 0; i < children.length; i += 1) {
          if (children[i] == null) continue;
          byte[] cKey = Arrays.copyOf(keyNode.key,
                                      keyNode.key.length + 1);
          cKey[cKey.length - 1] = (byte) i;
          toVisit.addLast(new KeyNode(cKey, children[i]));
        }
      } while (keyNode.node.value == Node.NO_VALUE);
      remaining -= 1;
      return new KeyValue(keyNode.key, keyNode.node.value);
    }
  };
}