Examen final

La déclaration de la classe ne pose pas de problème particulier, il faut juste penser à la déclarer comme finale (car elle est instanciable et immuable), de même que son attribut.

Comme expliqué dans l'énoncé, le constructeur ne copie pas l'argument qu'on lui passe, et c'est donc aux appelants de garantir qu'il ne changera jamais.

public final class ByteArray {
  private final byte[] bytes;

  private ByteArray(byte[] bytes) {
    this.bytes = bytes;
  }
}

La méthode of consiste en un simple appel au constructeur, auquel on passe un tableau dont le seul élément est l'octet constitué des 8 bits de poids faible de b, obtenus au moyen d'un transtypage.

public static ByteArray of(int b) {
  return new ByteArray(new byte[]{(byte) b});
}

Les méthodes hashCode et equals consistent presque uniquement en des appels aux méthodes du même nom de Arrays, la seule petite difficulté venant du fait que l'argument de equals a le type Object. Cela dit, le filtrage de motifs pour instanceof permet de résoudre ce problème de manière concise.

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

@Override
public boolean equals(Object thatO) {
  return thatO instanceof ByteArray that
    && Arrays.equals(this.bytes, that.bytes);
}

Si on ne désire pas utiliser le filtrage de motif pour instanceof, la méthode equals peut également s'écrire ainsi :

public boolean equals_2(Object thatO) {
  return (thatO instanceof ByteArray)
    && Arrays.equals(this.bytes, (((ByteArray) thatO).bytes));
}

Le bâtisseur ressemble beaucoup à une version simplifiée et non générique de la classe SArrayList vue au cours. Comme les ajouts d'éléments sont faits à la fin du tableau, il n'est même pas nécessaire d'utiliser arraycopy dans add, la méthode copyOf de Arrays suffit.

public static final class Builder {
  private byte[] bytes = new byte[8];
  private int size = 0;

  public boolean isEmpty() {
    return size == 0;
  }

  public int size() {
    return size;
  }

  public Builder add(int b) {
    if (size == bytes.length)
      bytes = Arrays.copyOf(bytes, 2 * bytes.length);
    bytes[size++] = (byte) b;
    return this;
  }

  public Builder removeLast() {
    if (isEmpty()) throw new IllegalStateException();
    size -= 1;
    return this;
  }

  public Builder clear() {
    size = 0;
    return this;
  }

  public ByteArray build() {
    return new ByteArray(Arrays.copyOf(bytes, size));
  }
}

La construction de l'index peut se faire en lisant le fichier contenant la base de données ligne à ligne, et en gardant dans une variable (toSkip ci-dessous) le nombre de caractères séparant le début du fichier et la ligne courante. Chaque fois qu'une ligne est lue, cette variable est augmentée de la longueur de la ligne, plus un — car la fin de la ligne est représentée par un caractère, comme expliqué dans l'énoncé.

L'adresse OACI de chaque aéronef s'obtient en extrayant les 6 premiers caractères de la ligne, puis en les convertissant en un entier au moyen de parseInt.

static Map<Integer, Integer> buildIndex(String fileName)
    throws IOException {
  Map<Integer, Integer> index = new HashMap<>();
  try (BufferedReader reader =
	 new BufferedReader(new FileReader(fileName))) {
    int toSkip = 0;
    String line = "";
    while ((line = reader.readLine()) != null) {
      String icaoString = line.substring(0, 6);
      int icao = Integer.parseInt(icaoString, 16);
      index.put(icao, toSkip);
      toSkip += line.length() + 1;
    }
  }
  // Note : le "unmodifiableMap" est optionnel
  return Collections.unmodifiableMap(index);
}

Une fois l'index construit, la méthode get n'est pas très difficile à écrire. On commence par vérifier si l'adresse OACI s'y trouve, et si non, on retourne null. Si elle s'y trouve, on ouvre le fichier, ignore les caractères précédant la ligne qui nous intéresse, puis lit cette dernière.

String get(int icaoAddress) throws IOException {
  int maybeToSkip = index.getOrDefault(icaoAddress, -1);
  if (maybeToSkip == -1) return null;

  try (BufferedReader reader =
	 new BufferedReader(new FileReader(fileName))) {
    reader.skip(maybeToSkip);
    return reader.readLine();
  }
}

La méthode pack consiste principalement en un décalage à gauche, suivi d'un « ou » bit à bit. Toutefois, il faut faire attention au fait que si l'on convertit la valeur en long au moyen d'un simple transtypage (éventuellement implicite), alors une valeur négative aurait les 32 bits de poids fort à 1. Pour éviter cela, il faut utiliser toUnsignedLong pour faire la conversion — ou un masquage équivalent.

(Cela n'est pas nécessaire pour la clef, car une fois convertie en une valeur de type long, elle est décalée à gauche de 32 bits, et ses 32 bits de poids fort sont donc éjectés.)

Il faut aussi penser à transtyper la clef en long avant de la décaler à gauche de 32 bits, faute de quoi le décalage est effectué sur une valeur de type int et n'a aucun effet.

static long pack(int key, int value) {
  return (((long) key) << Integer.SIZE)
    | Integer.toUnsignedLong(value);
}

La méthode ofMap peut s'écrire en remplissant tout d'abord un tableau (keysAndValues ci-dessous) avec les valeurs de type long correspondant aux paires clef/valeur — obtenues de la vue fournie par entrySet — puis en le triant.

static IntToIntMap ofMap(Map<Integer, Integer> map) {
  long[] keysAndValues = new long[map.size()];
  int i = 0;
  for (Map.Entry<Integer, Integer> e : map.entrySet())
    keysAndValues[i++] = pack(e.getKey(), e.getValue());
  Arrays.sort(keysAndValues);
  return new IntToIntMap(keysAndValues);
}

Cette méthode peut également s'écrire de manière élégante et concise en utilisant la programmation par flots :

static IntToIntMap ofMap(Map<Integer, Integer> map) {
  long[] keysAndValues = map.entrySet().stream()
    .mapToLong(e -> pack(e.getKey(), e.getValue()))
    .sorted()
    .toArray();
  return new IntToIntMap(keysAndValues);
}

La méthode getOrDefault n'est pas totalement triviale à écrire, car il faut tout d'abord décider que passer à binarySearch comme valeur à recherche, puis déterminer comment interpréter son résultat.

Il devrait être assez clair que les 32 bits de poids fort de la valeur passée à binarySearch doivent être ceux de la clef recherchée. Ses 32 bits de poids faible peuvent théoriquement être une constante quelconque, mais la valeur la plus logique à utiliser est 0, car elle garantit que la valeur recherchée est forcément plus petite ou égale à celle correspondant à la paire clef/valeur qui nous intéresse.

Dès lors, lorsque l'on recherche par exemple la valeur associée à la clef 004B1814 (en hexadécimal), la valeur de type long que l'on passe à binarySearch est 004B1814_00000000. Lorsque binarySearch retourne, deux cas peuvent se présenter :

• la valeur retournée par binarySearch est positive ou nulle, ce qui implique que la clef se trouve dans la table, et que la valeur qui lui correspond est 0 — car on a justement utilisé une paire clef/valeur dont la valeur vaut 0 pour la recherche,
• la valeur retournée par binarySearch est négative, ce qui implique que, si la clef recherchée se trouve dans la table, alors elle se trouve à la position suivant la position d'insertion.

Dans le second cas, il faut donc calculer la position d'insertion — égale à la négation de la valeur retournée, moins 1, comme dit dans le formulaire — puis vérifier si la valeur qui se trouve après elle existe, et que ses 32 bits de poids fort sont égaux à la clef recherchée. Si tel est le cas, on retourne les 32 bits de poids faible de cette valeur, sinon on retourne la valeur par défaut.

Pour illustrer ce second cas, imaginons que l'on passe la valeur de recherche 004B1814_00000000 mentionnée plus haut à binarySearch, et que le tableau soit celui constitué des trois valeurs données dans l'énoncé. La valeur de recherche ne se trouve pas dans ce tableau, mais la position à laquelle on devrait l'insérer pour que le tableau reste trié est la position 1 — ce qui implique que binarySearch retourne -2.

Étant donné que la position d'insertion (1) est plus petite que la taille du tableau, on sait que si la clef se trouve dans la table, elle se trouve à l'index 1. On extrait donc la valeur qui se trouve à cet index (004B1814_0000002C), compare ses 32 bits de poids fort avec ceux de la clef et, constatant qu'ils sont égaux, retourne ses 32 bits de poids faible (0000002C, soit 2C).

int getOrDefault(int key, int defaultValue) {
  int i = Arrays.binarySearch(keysAndValues, pack(key, 0));
  if (i >= 0) return 0;
  i = -i - 1;
  return i < keysAndValues.length
      && (int) (keysAndValues[i] >> Integer.SIZE) == key
    ? (int) keysAndValues[i]
    : defaultValue;
}

La méthode testBit peut s'écrire de différentes manières, par exemple en construisant un masque dont seul le bit d'index bitIndex vaut 1, puis en regardant si le résultat du masquage de la valeur avec ce masque est différent de 0.

static boolean testBit(int value, int bitIndex) {
  return (value & (1 << bitIndex)) != 0;
}

(Cette méthode testBit est rigoureusement identique à celle du projet.)

La manière la plus simple d'écrire la méthode extractSInt consiste à suivre les indications de l'énoncé, en :

• décalant tout d'abord la valeur à gauche pour placer le bit de poids fort de la plage à extraire à l'index 31,
• décalant — au moyen du décalage arithmétique — le résultat de cette opération à droite pour placer le bit de poids faible de la plage à extraire à l'index 0.

Le décalage à gauche permet d'une part d'éjecter les bits de poids fort non désirés de la valeur initiale, et d'autre part de garantir que le second décalage copiera le bit de poids fort de la plage à extraire dans tous les bits de poids fort du résultat, ce qui permet de l'interpréter de manière signée, comme demandé. Le décalage à droite éjecte quant à lui les bits de poids faible non désirés, et place ceux de la plage à extraire dans les bits de poids faible du résultat, comme désiré.

static int extractSInt(int value, int start, int size) {
  int unusedBits = Integer.SIZE - size;
  return (value << (unusedBits - start)) >> unusedBits;
}

Cette manière d'extraire une plage de bits en l'interprétant en complément à deux est probablement la plus simple à comprendre, mais il peut être utile de savoir qu'il en existe une autre, qui consiste à d'abord extraire la plage de manière non signée (dans la variable unsigned ci-dessous), puis de faire une extension de signe — c.-à-d. de copier le bit de poids fort de la valeur extraite dans tous les bits de poids plus fort qu'elle. Cette version s'écrit ainsi :

static int extractSInt(int value, int start, int size) {
  int unsigned = (value >> start) & ((1 << size) - 1);
  int m = 1 << (size - 1);
  return (unsigned ^ m) - m;
}

L'extension de signe est faite par la dernière ligne, qui utilise le masque m dont seul le bit correspondant au bit de poids le plus fort de la plage à extraire vaut 1. Ce bit est tout d'abord inversé au moyen d'un ou exclusif, puis le masque est soustrait. Pour comprendre pourquoi cela fonctionne, on peut distinguer deux cas :

1. le bit de poids le plus fort de la plage à extraire vaut 0, donc la valeur interprétée en complément à deux est positive ; dans ce cas, le ou exclusif fait passer ce bit à 1, puis la soustraction le refait passer à 0 sans modifier quoi que ce soit d'autre,
2. le bit de poids le plus fort de la plage à extraire vaut 1, donc la valeur interprétée en complément à deux est négative ; dans ce cas, le ou exclusif fait passer ce bit à 0, puis la soustraction le refait passer à 1 mais en faisant également passer tous les bits de poids supérieur à 1.

La méthode decompress est simple à écrire mais relativement longue. Elle ne doit en effet que distinguer les trois cas mentionnés dans l'énoncé, en testant tout d'abord le bit 15 — pour différencier le premier cas des deux autres — puis éventuellement le bit 14 — pour différencier les deux cas restants.

static int decompress(int value, short[] samples, int index) {
  short currentSample = samples[index];
  if (testBit(value, 15)) {
    // trois différences de 5 bits
    currentSample += extractSInt(value, 10, 5);
    samples[++index] = currentSample;
    currentSample += extractSInt(value, 5, 5);
    samples[++index] = currentSample;
    currentSample += extractSInt(value, 0, 5);
    samples[++index] = currentSample;
    return 3;
  } else if (!testBit(value, 14)) {
    // deux différences de 7 bits
    currentSample += extractSInt(value, 7, 7);
    samples[++index] = currentSample;
    currentSample += extractSInt(value, 0, 7);
    samples[++index] = currentSample;
    return 2;
  } else {
    // une différence de 12 bits
    currentSample += extractSInt(value, 0, 12);
    samples[++index] = currentSample;
    return 1;
  }
}

La définition de la classe Opt et de son constructeur ne posent pas de problème particulier si on pense à doter la classe d'un paramètre de type (E ci-dessous), que l'on utilise ensuite comme type de l'attribut et du paramètre du constructeur.

public final class Opt<E> {
  private final E value;

  private Opt(E value) {
    this.value = value;
  }
}

Les méthodes empty et of consistent presque exclusivement en des appels au constructeur, mais il faut là aussi penser à les rendre génériques en les dotant chacune de leur propre paramètre de type. Nous avons nommé ce paramètre E dans les deux cas ci-dessous, mais n'importe quel autre nom convient, bien entendu.

public static <E> Opt<E> empty() {
  return new Opt<>(null);
}

public static <E> Opt<E> of(E value) {
  if (value == null) throw new NullPointerException();
  return new Opt<>(value);
}

La méthode orElse ne pose pas de problème particulier.

public E orElse(E defaultValue) {
  return value != null ? value : defaultValue;
}

La méthode ifPresent ne pose pas de problème particulier, puisqu'elle fait simplement ce qui est mentionné dans l'énoncé.

public void ifPresent(Consumer<E> consumer) {
  if (value != null) consumer.accept(value);
}

La méthode map est un peu plus complexe que ifPresent, car elle retourne une valeur optionnelle dont le contenu peut avoir un type différent de celui du contenu du récepteur. Dès lors, elle doit être générique, et dans le cas où le récepteur est vide, elle ne peut pas simplement retourner this comme on pourrait peut-être le penser, car this a le type Opt<E> et pas Opt<F>.

public <F> Opt<F> map(Function<E, F> function) {
  return value == null
    ? new Opt<>(null)
    : new Opt<>(function.apply(value));
}