Examen intermédiaire

Pour appliquer une symétrie horizontale à une fonction, il suffit d'inverser le signe de son argument, comme l'exemple donné le montrait. La définition de l'enregistrement FlippedH est donc très simple :

public record FlippedH(DoubleUnaryOperator f)
  implements DoubleUnaryOperator {

  public double applyAsDouble(double x) {
    return f.applyAsDouble(-x);
  }
}

Comme nous l'avions vu dans la série Images continues, pour appliquer une transformation donnée à une fonction, il faut appliquer la transformation inverse à son argument. Dès lors, l'argument à passer à la méthode applyAsDouble de la fonction décorée est l'argument reçu moins la distance de translation.

public record Translated(DoubleUnaryOperator f,
			 double tX)
  implements DoubleUnaryOperator {

  public double applyAsDouble(double x) {
    return f.applyAsDouble(x - tX);
  }
}

Pour obtenir le profil inversé d'une arête à partir de son profil il suffit de lui appliquer une symétrie horizontale puis de le translater vers la droite d'une distance égale à sa longueur, afin que le dernier point du profil se trouve à l'origine. La méthode d'inversion de profil s'écrit donc ainsi :

static DoubleUnaryOperator invertedEdgeProfile(Edge edge) {
  return new Translated(new FlippedH(edge.profile()),
			edge.length());
}

Comme dit dans l'énoncé, la classe IndexedIterator est générique. Son paramètre de type, nommé E ci-dessous, représente le type des éléments fournis par l'itérateur sous-jacent.

Étant donné que la classe IndexedIterator est elle-même un itérateur, elle doit implémenter l'interface Iterator, et comme les éléments qu'elle fournit ont le type Indexed<E>, c'est ce type qui doit être passé en paramètre à Iterator.

public class IndexedIterator<E>
    implements Iterator<Indexed<E>> {}

Les attributs de IndexedIterator sont :

• l'itérateur sous-jacent, qui fournit les valeurs à indexer,
• l'index du prochain élément à fournir.

Le constructeur initialise le premier de ces attributs avec son argument, et initialise l'index à 0 — ce qui n'est pas indispensable, les attributs de type int étant automatiquement initialisés à 0, mais plus propre.

private final Iterator<E> underlyingIterator;
private int index;

public IndexedIterator(Iterator<E> underlyingIterator) {
  this.underlyingIterator = underlyingIterator;
  this.index = 0; // pas indispensable
}

La méthode hasNext est triviale, puisqu'elle ne fait qu'appler celle de l'itérateur sous-jacent. La méthode next est à peine plus complexe, puisqu'elle doit construire l'instance de Indexed à retourner avec l'index correct, puis mettre à jour l'index.

public boolean hasNext() {
  return underlyingIterator.hasNext();
}

public Indexed<E> next() {
  E next = underlyingIterator.next();
  return new Indexed<>(index++, next);
}

La méthode remove est similaire à next, en ce qu'elle appelle la méthode correspondante de l'itérateur sous-jacent puis met à jour l'index pour tenir compte de la suppression.

public void remove() {
  underlyingIterator.remove();
  index -= 1;
}

Le corps de la méthode over est très simple puisqu'elle n'a qu'à créer une nouvelle instance de IndexedIterator en lui passant un itérateur obtenu au moyen de la méthode iterator de l'itérable reçu en argument.

Comme over doit accepter un itérable de n'importe quel type, elle doit être générique, son paramètre de type (E ci-dessous) représentant le type des valeurs de l'itérable.

static <E> IndexedIterator<E> over(Iterable<E> iterable) {
  return new IndexedIterator<>(iterable.iterator());
}

L'idée de la méthode indexOf est simple :

• on obtient un itérateur indexé sur les éléments de la liste, p. ex. au moyen de over,
• tant que cet itérateur a encore un élément indexé à fournir, on l'obtient et regarde s'il est égal à celui recherché ; si oui, on retourne immédiatement son index,
• si la boucle se termine, cela signifie que l'élément recherché n'a pas été trouvé et on retourne donc -1.

Traduit en Java, cela donne :

static <E> int indexOf(List<E> list, E element) {
  Iterator<Indexed<E>> it = IndexedIterator.over(list);
  while (it.hasNext()) {
    Indexed<E> next = it.next();
    if (next.element().equals(element))
      return next.index();
  }
  return -1;
}

Il faut noter que cette méthode ne fonctionne pas si la liste contient une valeur null, mais il n'était pas nécessaire de gérer ce cas. Si on désirait néanmoins le faire, le plus simple serait d'utiliser la méthode equals de Objects pour comparer les deux éléments, en récrivant la condition du if ainsi :

Objects.equals(next.element(), element)

Les attributs à mémoriser sont :

• la valeur initiale des éléments,
• la taille totale du tableau,
• le tableau des morceaux.

Le constructeur doit simplement initialiser ces attributs en fonction des paramètres reçus, en vérifiant auparavant que la taille est bien supérieure ou égale à 0. La taille du tableau de morceaux s'obtient simplement en arrondissant par excès le résultat de la division de la taille du tableau par la taille d'un morceau (4096).

private final float initialValue;
private final int size;
private final float[][] chunks;

public SparseFloatArray(int size, float initialValue) {
  if (size < 0)
    throw new IllegalArgumentException();

  this.initialValue = initialValue;
  this.size = size;
  this.chunks = new float[ceilDiv(size, 4096)][];
}

L'existence de l'attribut size rend la méthode du même nom triviale :

public int size() {
  return size;
}

La méthode get commence par vérifier que l'index qu'elle reçoit est valide, même si cette vérification pourrait être omise sachant que la bonne exception serait de toute manière levée lors de l'accès au tableau des morceaux, mais avec un message moins clair.

Une fois cette vérification effectuée, elle détermine l'index du morceau contenant l'élément, en effectuant une division entière de l'index de l'élément par la taille d'un morceau. Comme cette taille est une puissance de deux, la division peut s'effectuer par un décalage à droite.

Lorsque l'index du morceau contenant l'élément est connu, il ne reste plus qu'à vérifier si ce morceau existe ou non. Si ce n'est pas le cas, alors l'élément est forcément égal à la valeur initiale. Si c'est le cas, il suffit d'obtenir son index dans le morceau, et à l'en extraire.

Bien entendu, l'index de l'élément dans le morceau est égal au reste de la division de l'index de l'élément dans le tableau par la taille d'un morceau. Là aussi, on peut tirer parti du fait que la taille d'un morceau est une puissance de deux pour calculer ce reste au moyen d'un simple masquage.

public float get(int i) {
  if (!(0 <= i && i < size)) // pas indispensable
    throw new IndexOutOfBoundsException();

  int chunkIndex = i >> 12; // ou : i / 4096
  return chunks[chunkIndex] == null
    ? initialValue
    : chunks[chunkIndex][i & 4095];  // ou : i % 4096
}

La méthode set commence également par vérifier que l'index qu'elle reçoit est valide, même si là encore cette vérification pourrait être omise.

Une fois cette vérification effectuée, elle calcule l'index du morceau contenant l'élément, comme get. Si ce morceau n'existe pas encore, et que la valeur reçue n'est pas égale à la valeur initiale, alors le morceau doit être créé. Sa taille est de 4096 éléments, sauf (peut-être) s'il s'agit du dernier morceau, dont la taille est égale à la taille totale du tableau moins celle des morceaux précédents. Après avoir été créé, le morceau doit être initialisé avec la valeur initiale, ce qui se fait facilement au moyen de la méthode fill de Arrays.

Finalement, une fois que l'existence du morceau contenant l'élément est garantie, sa valeur peut être modifiée au moyen d'une simple affectation.

public void set(int i, float value) {
  if (!(0 <= i && i < size)) // pas indispensable
    throw new IndexOutOfBoundsException();

  int chuckIndex = i >> 12; // ou : i / 4096
  if (chunks[chuckIndex] == null && value != initialValue) {
    chunks[chuckIndex] = (chuckIndex == chunks.length - 1)
      ? new float[size - (chuckIndex << 12)]
      : new float[4096];
    Arrays.fill(chunks[chuckIndex], initialValue);
  }
  if (chunks[chuckIndex] != null)
    chunks[chuckIndex][i & 4095] = value; // ou i % 4096
}

Si on prend soin d'utiliser la méthode get pour obtenir la valeur des éléments du tableau, et d'utiliser une instance de StringJoiner pour construire la chaîne, alors la méthode toString est triviale à écrire.

public String toString() {
  StringJoiner joiner = new StringJoiner(",", "[", "]");
  for (int i = 0; i < size(); i += 1)
    joiner.add(String.valueOf(get(i)));
  return joiner.toString();
}

La méthode density doit calculer les deux valeurs dont elle doit déterminer le rapport :

• le nombre total d'éléments présents dans les morceaux existants (ci-dessous totalElementCount),
• le nombre d'entre eux différents de la valeur initiale (ci-dessous nonDefaultElementCount).

Pour ce faire, elle parcourt le tableau des morceaux, en ignorant les morceaux inexistants. Pour chaque morceau rencontré, elle augmente totalElementCount de la taille du morceau, et nonDefaultElementCount du nombre de ses éléments différents de la valeur initiale.

Cela fait, elle peut simplement retourner leur rapport, en prenant bien soin de traiter le cas particulier où aucun morceau n'existe — et donc que totalElementCount vaut 0. Dans ce cas, comme dit dans l'énoncé, la densité vaut 1 par définition.

public double density() {
  int totalElementCount = 0;
  int nonDefaultElementCount = 0;
  for (float[] chunk : chunks) {
    if (chunk == null) continue;

    totalElementCount += chunk.length;
    for (float v : chunk)
      if (v != initialValue) nonDefaultElementCount += 1;
  }
  return totalElementCount == 0
    ? 1
    : nonDefaultElementCount / (double) totalElementCount;
}