Examen final

Les trois variantes de la méthode of doivent pouvoir créer un ensemble de type quelconque, et sont donc génériques. Une fois cette petite difficulté identifiée, leur écriture est simple et consiste en toujours en un énoncé return qui retourne une lambda dont le code correspond à la méthode contains de l'interface FunSet. (En cela, ces méthodes sont similaires à celles de l'interface Image de la seconde série sur les images continues.)

Pour un ensemble vide, la méthode contains retourne naturellement toujours faux :

static <E> FunSet<E> of() {
  return e -> false;
}

Pour un ensemble ne contenant d'un élément, elle ne retourne vrai que pour cet élément :

static <E> FunSet<E> of(E elem) {
  return e -> e.equals(elem);
}

Finalement, pour un ensemble Java, la méthode contains de FunSet retourne le même résultat que la méthode contains de l'ensemble Java. Cela peut s'exprimer très facilement au moyen d'une référence de méthode :

static <E> FunSet<E> of(Set<E> set) {
  return set::contains; // ou e -> set.contains(e)
}

Le complément d'un ensemble s'obtient simplement en inversant le résultat de sa méthode contains :

default FunSet<E> complement() {
  return e -> !this.contains(e);
}

L'union, l'intersection et la différence de deux ensembles s'obtient en combinant le résultat de leurs méthodes contains respectives, de la bonne manière, à savoir : au moyen d'un ou logique pour l'union, d'un et logique pour l'intersection, et d'un et logique encore mais cette fois avec le résultat inversé de la seconde méthode contains pour la différence.

default FunSet<E> union(FunSet<E> that) {
  return e -> this.contains(e) || that.contains(e);
}
default FunSet<E> intersection(FunSet<E> that) {
  return e -> this.contains(e) && that.contains(e);
}
default FunSet<E> difference(FunSet<E> that) {
  return e -> this.contains(e) && !that.contains(e);
}

On notera au passage que l'interface FunSet est très similaire à l'interface Predicate de la bibliothèque Java, la méthode contains correspondant à la méthode test, la méthode complement à la méthode negate, la méthode union à la méthode or, et la méthode intersection à la méthode and.

La méthode get est très simple à écrire, puisqu'elle ne doit que valider ses arguments avant de calculer l'index row-major qui leur correspond et le passer à getRowMajor, qui se charge du reste.

default double get(int r, int c) {
  if (!(0 <= r && r < rows()))
    throw new IndexOutOfBoundsException();
  if (!(0 <= c && c < columns()))
    throw new IndexOutOfBoundsException();

  return getRowMajor(r * columns() + c);
}

On notera que la validation des arguments est obligatoire, et ne peut pas être laissée à getRowMajor, car l'index row-major correspondant à une paire d'index (r, c) peut très bien être valide sans que la paire ne le soit. Par exemple, dans une matrice 2×2, la paire d'index (0, 3) est invalide, mais l'index row-major correspondant, 3, est valide.

La classe DenseMatrix est facile à écrire, il faut juste se rappeler que :

1. il s'agit d'une classe instanciable, et elle doit donc être finale,
2. il s'agit d'une classe immuable, ses attributs doivent donc être finaux et le tableau des coefficients passé au constructeur doit être copié avant d'être stocké.

La méthode getRowMajor n'a pas strictement besoin de valider son argument, sachant que l'accès à un élément d'index invalide d'un tableau lève déjà la bonne exception. Dans un programme réel, il serait toutefois plus propre de le faire.

public final class DenseMatrix implements Matrix {
  private final int rows, columns;
  private final double[] coefficients;

  public DenseMatrix(int rows,
		     int columns,
		     double[] coefficients) {
    if (rows <= 0
	|| columns <= 0
	|| coefficients.length != rows * columns)
      throw new IllegalArgumentException();

    this.rows = rows;
    this.columns = columns;
    // Autre option: this.coefficients = coefficients.clone()
    this.coefficients = Arrays.copyOf(coefficients,
				      coefficients.length);
  }

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

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

  @Override
  public double getRowMajor(int i) {
    // Optionnel :
    // if (!(0 <= i && i < rows * columns)) throw new …
    return coefficients[i];
  }
}

La classe SparseMatrix est plus difficile à écrire que DenseMatrix, principalement car la validation des arguments du constructeur n'est pas totalement triviale.

En particulier, il faut vérifier que les index des coefficients non nuls, passés dans le tableau n0Indices, sont valides, triés par ordre croissant, et sans doublons. Pour cela, on peut les parcourir en se souvenant toujours de l'index précédent (previousIndex) et en vérifiant que chaque nouvel index est bien strictement plus grand que le précédent et strictement plus petit que le nombre de coefficients de la matrice, y compris ceux valant 0 (coefsCount).

La méthode getRowMajor est également un peu plus compliquée que celle de DenseMatrix, premièrement car elle doit obligatoirement valider son argument, et deuxièmement car elle doit utiliser binarySearch pour rechercher l'index demandé dans le tableau des index. Si binarySearch retourne une valeur négative, cela signifie que le coefficient ne fait pas partie des non nuls, donc qu'il vaut 0. Sinon, sa valeur peut être extraite du tableau des coefficients non nuls, à la position retournée par binarySearch.

public final class SparseMatrix implements Matrix {
  private final int rows, columns;
  private final int[] n0Indices;
  private final double[] n0Coefficients;

  public SparseMatrix(int rows,
		      int columns,
		      int[] n0Indices,
		      double[] n0Coefficients) {
    if (rows <= 0
	|| columns <= 0
	|| n0Indices.length != n0Coefficients.length)
      throw new IllegalArgumentException();

    int coefsCount = rows * columns;
    int previousIndex = -1;
    for (int index : n0Indices) {
      if (!(previousIndex < index && index < coefsCount))
	throw new IllegalArgumentException();
      previousIndex = index;
    }

    for (double coefficient : n0Coefficients)
      if (coefficient == 0)
	throw new IllegalArgumentException();

    this.rows = rows;
    this.columns = columns;
    this.n0Indices =
      Arrays.copyOf(n0Indices, n0Indices.length);
    this.n0Coefficients =
      Arrays.copyOf(n0Coefficients, n0Coefficients.length);
  }

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

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

  @Override
  public double getRowMajor(int i) {
    if (!(0 <= i && i < rows * columns))
      throw new IndexOutOfBoundsException();
    int ci = Arrays.binarySearch(n0Indices, i);
    return ci >= 0 ? n0Coefficients[ci] : 0;
  }
}

Les lignes d'une matrice transposée sont les colonnes de la matrice originale, tandis que ses colonnes sont les lignes de l'originale. Logiquement, les méthodes rows et columns retournent dont respectivement le nombre de colonnes et le nombre de lignes de la matrice originale.

La méthode getRowMajor est un peu plus difficile à écrire, et il convient donc d'être systématique. La manière la plus simple de procéder est de commencer par calculer les index de ligne (r) et de colonne (c) correspondant à l'index row-major i passé en argument, ce qui se fait aisément au moyen de la division entière et de son reste. Cela fait, sachant que le rôle des lignes et des colonnes est inversé pour la transposée, on obtient immédiatement l'index de ligne (rM) et de colonne (cM) pour la matrice originale. Finalement, on peut en déduire l'index row-major de la même manière que la méthode get de la partie 1, et le passer à la méthode getRowMajor de la matrice originale.

Finalement, la méthode transposed est redéfinie afin de retourner la matrice originale, ce qui est bien entendu plus efficace que de « l'emballer » une deuxième fois dans une instance de TransposedMatrix.

public final class TransposedMatrix implements Matrix {
  private final Matrix matrix;

  TransposedMatrix(Matrix matrix) {
    this.matrix = matrix;
  }

  @Override
  public int rows() {
    return matrix.columns();
  }

  @Override
  public int columns() {
    return matrix.rows();
  }

  @Override
  public double getRowMajor(int i) {
    // Index (r,c) pour la transposée
    int r = i / columns();
    int c = i % columns();

    // Index (r,c) pour la matrice originale
    int rM = c, cM = r;
    // Index « row-major » pour la matrice originale
    int iM = rM * matrix.columns() + cM;
    return matrix.getRowMajor(iM);
  }

  @Override
  public Matrix transposed() {
    return matrix;
  }
}

La méthode getRowMajor ci-dessus a été écrite en suivant le raisonnement exposé plus haut, mais elle peut bien entendu être simplifiée en :

public double getRowMajor(int i) {
  return matrix.getRowMajor((i % columns()) * matrix.columns()
			    + i / columns());
}

TransposedMatrix utilise le patron décorateur (Decorator).

La classe MatrixBuilder n'est pas excessivement difficile à écrire, mais un peu longue. Les coefficients de la matrice en cours de construction y sont stockés en ordre row-major, ce qui rend très simple la création de la matrice dans la méthode build lorsque celle-ci est dense.

Pour déterminer si la matrice est dense ou creuse, la méthode build commence par compter le nombre de coefficients non nuls (n0Count). Cela fait, elle détermine si leur proportion (density) est strictement supérieure à 50%, et dans ce cas, retourne une matrice dense. Sinon, les tableaux des coefficients non nuls et leurs index doivent être créés, ce qui est facile car le nombre de coefficients non nuls est connu. Cela fait, il ne reste plus qu'à les remplir au moyen d'un parcours des coefficients durant lequel la valeur et l'index de tout coefficient non nul est stocké dans le tableau correspondant. Ces tableaux sont ensuite passés au constructeur de SparseMatrix.

public final class MatrixBuilder implements Matrix.Builder {
  private final int rows, columns;
  private final double[] coefficients;

  public MatrixBuilder(int rows, int columns) {
    if (rows <= 0 || columns <= 0)
      throw new IllegalArgumentException();

    this.rows = rows;
    this.columns = columns;
    this.coefficients = new double[rows * columns];
  }

  @Override
  public MatrixBuilder set(int r, int c, double v) {
    if (!(0 <= r && r < rows && 0 <= c && c < columns))
      throw new IndexOutOfBoundsException();
    coefficients[r * columns + c] = v;
    return this;
  }

  @Override
  public Matrix build() {
    int n0Count = 0;
    for (double c : coefficients)
      if (c != 0) n0Count += 1;

    double density = (double) n0Count / coefficients.length;
    if (density > 0.5) {
      return new DenseMatrix(rows, columns, coefficients);
    } else {
      int[] n0Indices = new int[n0Count];
      double[] n0Coefficients = new double[n0Count];
      int i = 0;
      for (int j = 0; j < coefficients.length; j++) {
	double c = coefficients[j];
	if (c != 0) {
	  n0Indices[i] = j;
	  n0Coefficients[i] = c;
	  i += 1;
	}
      }
      return new SparseMatrix(rows,
			      columns,
			      n0Indices,
			      n0Coefficients);
    }
  }
}

Les 32 bits d'une valeur de type float étant constitués de trois composantes, il est utile de définir des constantes, nommées masques, permettant de facilement isoler chaque composante au moyen d'un et bit à bit :

private static final int S_MASK =
  0b1000_0000_0000_0000_0000_0000_0000_0000;
private static final int E_MASK =
  0b0111_1111_1000_0000_0000_0000_0000_0000;
private static final int M_MASK =
  0b0000_0000_0111_1111_1111_1111_1111_1111;

Pour faciliter la lecture, ces trois masques sont définis sous forme de constantes binaires, mais il existe beaucoup d'autres manières de les définir : en hexadécimal, par calcul (en combinant décalages et soustractions), etc.

Une fois ces masques définis, une manière d'écrire la méthode isZero consiste à tester si les composantes e et m, ou autrement dit toutes les composantes sauf s, valent 0. Ces composantes peuvent s'extraire au moyen du complément du masque permettant d'extraire s, et la méthode isZero peut donc s'écrire ainsi :

public static boolean isZero(float f) {
  int i = floatToIntBits(f);
  return (i & ~S_MASK) == 0;
}

La méthode isInfinite peut s'écrire de manière similaire, puisqu'ici aussi il suffit d'ignorer le signe s et de vérifier si les composantes e et m sont celles représentant l'infini — l'infini positif pour être précis. On peut donc commencer par définir une nouvelle constante pour l'infini positif, qui se trouve être égale au masque permettant d'extraire e :

private static final int POS_INFINITY = E_MASK; // +∞

après quoi isInfinite s'écrit presque comme isZero :

public static boolean isInfinite(float f) {
  int i = floatToIntBits(f);
  return (i & ~S_MASK) == POS_INFINITY;
}

La méthode isNaN est similaire mais un tout petit peu plus complexe car, contrairement aux deux autres méthodes, les tests sur e et m doivent se faire séparément.

Le premier de ces tests consiste à déterminer si e vaut 11111111₂, ce qui peut se faire en extrayant les 8 bits de e puis en regardant s'ils valent tous 1. Une nouvelle constante est définie pour cela (SPECIAL_EXPONENT), mais elle est une fois encore égale à E_MASK.

Le second de ces tests consiste à déterminer si m est différent de zéro. Là aussi, un et bit à bit avec M_MASK permet de ne conserver que les bits de m, après quoi une comparaison avec 0 répond à la question.

private static final int SPECIAL_EXPONENT = E_MASK;

public static boolean isNaN(float f) {
  int i = floatToIntBits(f);
  return (i & E_MASK) == SPECIAL_EXPONENT
    && (i & M_MASK) != 0;
}

Calculer la valeur absolue d'un nombre en virgule flottante consiste simplement à mettre à 0 son bit de signe s. Pour cela, un simple et bit à bit avec le complément de S_MASK suffit.

Avant de mettre ce bit à 0, il faut toutefois s'assurer que la valeur n'est pas un NaN, car dans ce cas elle doit être retournée telle quelle. Cela se fait bien entendu via un appel à isNaN.

public static float abs(float f) {
  return isNaN(f)
    ? f
    : intBitsToFloat(floatToIntBits(f) & ~S_MASK);
}

Calculer la fonction signe d'un nombre à virgule flottante est d'une certaine manière complémentaire au calcul de sa valeur absolue, car ici le signe est la seule chose que l'on désire conserver, puisque les composantes e et m doivent être remplacées par celles représentant 1.

Une première question qui se pose est donc de savoir quelles sont les valeurs de e et m représentant 1. Pour y répondre, il faut regarder la formule donnée dans l'énoncé : \[ n = (-1)^s \times 1.m \times\,2^{e-127} \] et constater que les valeurs de s, e et m permettant d'obtenir \(n = 1\) sont \(s = m = 0\) et \(e = 127\), car on a alors : \[ n = (-1)^0 \times 1.0 \times\ 2^{127-127}\ = 1\times 1.0\times\,2^{0}\ = 1\times 1.0\times 1 = 1\] Ces valeurs étant déterminées, on peut définir une constante (POS_1 ci-dessous) représentant +1, après quoi la méthode signum n'a plus qu'à extraire le bit de signe de son argument et le combiner (au moyen d'un ou bit à bit) avec cette constante.

Là encore, il faut au préalable penser aux cas particuliers, qui sont ici 0 (négatif et positif) et les valeurs NaN, qui doivent être retournées telles quelles.

public static final int POS_1 =
  0b0011_1111_1000_0000_0000_0000_0000_0000; // +1
public static float signum(float f) {
  return isZero(f) || isNaN(f)
    ? f
    : intBitsToFloat((floatToIntBits(f) & S_MASK) | POS_1);
}

Comme le suggère l'énoncé, la classe Partition peut stocker les liens entre les éléments dans une table associative. Un lien allant d'un élément à autre y est représenté par une paire clef/valeur dont la clef est l'élément à la source du lien, et la valeur est l'élément à sa destination. Sachant que les clefs et les valeurs de cette table sont des éléments, et que ceux-ci ont le type E (le paramètre de type de Partition), la table a le type Map<E, E>.

Une fois cette table créée, la méthode (privée) representative s'écrit simplement en suivant ces liens jusqu'au représentant, qui se reconnaît au fait qu'aucun lien ne part de lui, c-à-d qu'il n'apparaît pas comme clef dans la table.

Au moyen de la méthode representative, la méthode inSameSubset s'écrit très facilement puisqu'il lui suffit de tester si les représentants des deux éléments qu'on lui passe sont égaux.

La méthode join n'est pas beaucoup plus difficile à écrire, mais il faut faire très attention à un point : si les deux éléments dont on désire joindre les sous-ensembles sont déjà dans le même sous-ensemble, alors il ne faut rien faire. Créer un lien allant du représentant à lui-même introduirait en effet un cycle, qui ferait boucler éternellement la méthode representative lors d'un prochain appel.

public final class Partition<E> {
  private final Map<E, E> parent = new HashMap<>();

  public boolean inSameSubset(E e1, E e2) {
    return representative(e1).equals(representative(e2));
  }

  public void join(E e1, E e2) {
    E r1 = representative(e1);
    E r2 = representative(e2);

    if (!r1.equals(r2))
      parent.put(r1, r2);
  }

  private E representative(E e) {
    E r = e;
    while (parent.containsKey(r))
      r = parent.get(r);
    return r;
  }
}

La compression des chemins se fait dans la méthode representative en parcourant une seconde fois le chemin allant de l'élément à son représentant, tout en modifiant les liens pour qu'ils référencent directement le représentant. Ce faisant, il faut faire bien attention à parcourir l'ancien chemin, ce qui n'est pas totalement trivial car on le modifie en même temps !

Une manière concise de faire cela consiste à tirer parti du fait que la méthode put de Map retourne l'ancienne valeur associée à la clef qu'on lui passe. La compression des chemins peut donc se faire en ajoutant les lignes suivantes juste avant le return :

E e2 = e;
while (!e2.equals(r))
  e2 = parent.put(e2, r);

Si on ne désire pas utiliser la valeur de retour de put de cette manière, on doit écrire une boucle similaire à celle-ci :

E e2 = e;
while (!e2.equals(r)) {
  E currentParent = parent.get(e2);
  parent.put(e2, r);
  e2 = currentParent;
}

Afin de pouvoir utiliser les rangs pour décider quel représentant utiliser lorsque deux sous-ensembles sont joints, il faut bien entendu stocker ces rangs quelque part. Comme suggéré dans l'énoncé, une table associative fait bien l'affaire, et son type est cette fois Map<E, Integer>, les clefs étant les éléments et les valeurs leur rang :

private final Map<E, Integer> rank = new HashMap<>();

Il faut noter que, comme cette table est initialement vide mais que le rang initial d'un élément est 0, le fait qu'un élément n'apparaisse pas dans cette table signifie que son rang vaut 0.

Au moyen de cette table, il n'est pas très difficile de modifier la méthode join pour qu'elle utilise les rangs des deux représentants pour choisir celui du sous-ensemble joint. En utilisant la méthode getOrDefault pour obtenir le rang d'un élément, on peut facilement s'assurer que son rang soit bien 0 s'il n'apparaît pas dans la table, comme expliqué ci-dessus.

public void join(E e1, E e2) {
  E r1 = representative(e1);
  E r2 = representative(e2);

  if (r1.equals(r2)) return;

  int k1 = rank.getOrDefault(r1, 0);
  int k2 = rank.getOrDefault(r2, 0);

  if (k1 >= k2) {
    parent.put(r2, r1);
    if (k1 == k2)
      rank.put(r1, k1 + 1);
  } else {
    parent.put(r1, r2);
  }
}