Examen final
corrigé

L'inversion des bits d'un vecteur s'obtient simplement en inversant les bits produits par sa méthode testBit.

public default BitVector not() {
  return i -> ! testBit(i);
}

La conjonction et la disjonction sont quasi-identiques, et s'obtiennent en effectuant la conjonction et la disjonction des bits individuels produits par testBit.

public default BitVector and(BitVector that) {
  return i -> this.testBit(i) && that.testBit(i);
}

public default BitVector or(BitVector that) {
  return i -> this.testBit(i) || that.testBit(i);
}

Le décalage se fait simplement en changeant l'index passé à la méthode testBit du vecteur à décaler. Il faut juste penser à traiter séparément le cas où le décalage est nul, comme demandé dans l'énoncé.

public default BitVector shift(int d) {
  return d == 0 ? this : i -> testBit(i - d);
}

La jointure se fait simplement en comparant l'index du bit demandé et en obtenant le bit de l'un ou l'autre des deux vecteurs en fonction de si cet index est inférieur ou non à celui de jointure.

public default BitVector join(BitVector that, int j) {
  return i -> (i < j ? this : that).testBit(i);
}

Pour faire en sorte que les bits du vecteur se répètent à l'infini, il faut bien entendu utiliser le reste de la division entière par la longueur de l'intervalle de répétition. Il faut toutefois prendre garde à utiliser la bonne définition de la division entière, à savoir la division entière par défaut (floored division), faute de quoi on obtient des résultats incorrects lorsque le numérateur est négatif.

public default BitVector cycling(int s, int l) {
  if (! (0 < l))
    throw new IllegalArgumentException();
  return i -> testBit(s + Math.floorMod(i - s, l));
}

La conversion en chaîne peut se faire très simplement en parcourant les index de l'intervalle pour lequel la conversion a été demandée, en ordre décroissant afin que les bits apparaissent dans le bon ordre.

public default String toString(int s, int l) {
  if (! (0 <= l))
    throw new IllegalArgumentException();

  StringBuilder b = new StringBuilder();
  for (int i = s + l - 1; i >= s; --i)
    b.append(testBit(i) ? '1' : '0');
  return b.toString();
}

La conversion d'un tableau d'octets en vecteur se fait en distinguant deux cas, en fonction de si l'index du bit demandé fait partie de la plage couverte par le tableau ou non.

S'il n'en fait pas partie, alors il suffit de retourner la valeur par défaut, d.

S'il en fait partie, alors il suffit de calculer l'index de l'octet contenant le bit, et l'index du bit dans cet octet. Cela se fait très facilement au moyen de la division entière et de son reste. Une fois encore, il faut toutefois penser à utiliser la division entière par défaut (les méthode floorDiv et floorMod) et pas la division tronquée (les opérateurs / et %), car cette dernière ne produit pas les résultats désirés avec les index négatifs.

public static BitVector ofBits(byte[] b, boolean d) {
  return i -> {
    int cI = Math.floorDiv(i, Byte.SIZE);
    if (0 <= cI && cI < b.length) {
      int bI = Math.floorMod(i, Byte.SIZE);
      return (b[cI] & (1 << bI)) != 0;
    } else {
      return d;
    }
  };
}

L'introduction du cache ne pose pas de problème particulier : il suffit de le consulter pour voir s'il ne contient pas encore d'entrée pour la ligne à convertir. Dans ce cas, on convertit la ligne au moyen de reallyConvertLine puis on insère l'entrée correspondante dans le cache. Une fois cela fait, on sait qu'une entrée se trouve dans le cache, et il ne reste plus qu'à la retourner.

private static int[] convertLine(LcdImageLine l) {
  if (! cache.containsKey(l))
    cache.put(l, reallyConvertLine(l));
  return cache.get(l);
}

A noter qu'en utilisant la méthode computeIfAbsent de Map et une référence de méthode, convertLine s'écrit de manière encore plus simple :

private static int[] convertLine(LcdImageLine l) {
  return cache.computeIfAbsent(l,
    ImageConverter::reallyConvertLine);
}

Pour supprimer aléatoirement 100 éléments lorsque le cache en contient 1000, il suffit d'ajouter un test au début de la méthode convertLine qui détermine si la purge est nécessaire et, dans ce cas :

1. place les clefs du cache dans une liste,
2. mélange aléatoirement cette liste,
3. supprime du cache les 100 premiers éléments de cette liste mélangée.

private static int[] convertLine(LcdImageLine l) {
  if (cache.size() == 1000) {
    List<LcdImageLine> ks = new ArrayList<>(cache.keySet());
    Collections.shuffle(ks);
    for (int i = 0; i < 100; ++i)
      cache.remove(ks.get(i));
  }
  return cache.computeIfAbsent(l,
    ImageConverter2::reallyConvertLine);
}

Comme expliqué dans l'énoncé, pour pouvoir supprimer les éléments les moins récemment utilisés du cache, il faut savoir à quand remonte la dernière utilisation de chacun d'entre eux.

Pour ce faire, on peut incrémenter un compteur à chaque appel à convertLine et utiliser la valeur de ce compteur comme une notion abstraite de temps. A chaque élément du cache est associée la valeur de ce compteur au moment de sa dernière utilisation.

Pour pouvoir stocker cette information supplémentaire, il faut définir une classe représentant une paire composée de la ligne convertie, et de la valeur du compteur au moment de la dernière utilisation. Cela se fait très facilement :

private static final class CacheEntry {
  public int lastUse;
  public int[] data;
  public CacheEntry(int[] data) {
    this.data = data;
  }
}

Cela fait, il faut également changer le type du cache, dont les valeurs ont désormais le type CacheEntry :

private static Map<LcdImageLine, CacheEntry> cache =
  new HashMap<>();

Finalement, il faut modifier convertLine pour gérer correctement le compteur et mettre à jour le temps de dernière utilisation de chaque élément obtenu du cache. Tout comme pour la partie 2, il faut supprimer 100 éléments du cache lorsque celui-ci en contient 1000, la seule différence étant que ces éléments sont obtenus en triant par dernière utilisation la liste des clefs plutôt qu'en la mélangeant.

private static int convertCount;

private static int[] convertLine(LcdImageLine l) {
  if (cache.size() == 1000) {
    List<LcdImageLine> lru = new ArrayList<>(cache.keySet());
    Collections.sort(lru, (l1, l2) ->
      Integer.compare(cache.get(l1).lastUse,
		      cache.get(l2).lastUse));
    for (int i = 0; i < 100; ++i)
      cache.remove(lru.get(i));
  }
  CacheEntry c = cache.computeIfAbsent(l, k ->
    new CacheEntry(reallyConvertLine(l)));
  c.lastUse = convertCount++;
  return c.data;
}