Examen intermédiaire
corrigé

La manière la plus simple d'effectuer la conversion consiste à boucler en allant des chiffres de poids faible à ceux de poids fort, en collectant les caractères qui leur correspondent dans un bâtisseur de chaîne.

A chaque itération de la boucle, le chiffre des unités s'obtient simplement au moyen du reste de la division entière par 10, tandis que les chiffres restants s'obtiennent par la division elle-même.

Une fois la totalité des caractères collectés, il suffit de les mettre dans le bon ordre — poids fort en tête — en renversant le contenu du bâtisseur de chaîne au moyen de la méthode reverse.

Il faut toutefois noter que cette technique ne fonctionne pas avec 0, car aucun caractère n'est alors produit. Ce cas doit être traité séparément.

public static String posIntToStr(int i) {
  if (! (0 <= i))
    throw new IllegalArgumentException();

  if (i == 0)
    return "0";
  else {
    StringBuilder b = new StringBuilder();
    while (i != 0) {
      b.append((char) ('0' + (i % 10)));
      i /= 10;
    }
    return b.reverse().toString();
  }
}

Non, cette mise en œuvre n'est pas correcte. Le problème est que la plus petite valeur entière possible (–2³¹, soit –2147483648) n'a pas d'équivalent positif, et la négation se comporte comme l'identité pour cette valeur, ce qui provoque un appel à posIntToStr avec une valeur négative, et donc la levée d'une exception :

intToStr(-2147483648)
  => posIntToStr(- (-2147483648))
  => posIntToStr(-2147483648)
  => exception IllegalArgumentException

La conversion se fait relativement facilement caractère par caractère. Il faut toutefois prendre garde à bien gérer le cas où la chaîne est vide, et lever l'exception IllegalArgumentException plutôt que retourner 0.

public static int strToPosInt(String s) {
  if (s.isEmpty())
    throw new IllegalArgumentException();

  int r = 0;
  for (int i = 0; i < s.length(); ++i) {
    char c = s.charAt(i);
    if (! ('0' <= c && c <= '9'))
      throw new IllegalArgumentException();
    r = (r * 10) + c - '0';     // à changer pour la partie 4
  }
  return r;
}

Il suffit de changer la ligne qui met à jour la variable r, indiquée ci-dessus par un commentaire, ainsi :

r = (r << 4) + c - '0';

Il y a plusieurs manières d'écrire cette méthode, celle utilisée ci-dessous consiste à itérer sur tous les masques de 1 bit possibles au moyen d'une boucle.

En d'autres termes, la variable m ci-dessous est initialement un masque permettant d'isoler le bit 0, ensuite un masque permettant d'isoler le bit 1, et ainsi de suite jusqu'au bit 31 :

int bitCount(int v) {
  int c = 0;
  for (int m = 1; m != 0; m <<= 1) {
    if ((v & m) != 0)
      c += 1;
  }
  return c;
}

La seule difficulté de cet exercice est de constater que le « ou exclusif » bit à bit des deux vecteurs entre lesquels on désire calculer la distance de Hamming produit un vecteur ayant des 1 uniquement là où ils diffèrent. Il suffit donc de compter les bits à 1 de ce vecteur pour connaître la distance de Hamming :

int hammingDistance(int v1, int v2) {
  return bitCount(v1 ^ v2);
}

Le comptage de bits rapide dans un vecteur de 32 bits se fait en 5 étapes (car \(\log_2 32 = 5\)), comme dit dans l'énoncé. Pour chaque étape \(i\), \(i\) allant de 0 à 4, il faut :

1. isoler les groupes de \(2^i\) bits contigus d'index impair au moyen d'un premier « et » bit à bit,
2. isoler les groupes de \(2^i\) bits contigus d'index pair au moyen d'un décalage à droite de \(2^i\) bits suivi d'un second « et » bit à bit identique,
3. calculer (en parallèle) la somme de ces \(2^{4-i}\) groupes de bits au moyen d'une addition 32 bits.

La valeur de la dernière somme est le résultat désiré.

int bitCount(int x0) {
  int x1 = (x0 & 0x5555_5555) + ((x0 >>> 1) & 0x5555_5555);
  int x2 = (x1 & 0x3333_3333) + ((x1 >>> 2) & 0x3333_3333);
  int x4 = (x2 & 0x0F0F_0F0F) + ((x2 >>> 4) & 0x0F0F_0F0F);
  int x8 = (x4 & 0x00FF_00FF) + ((x4 >>> 8) & 0x00FF_00FF);
  int x16 = (x8 & 0x0000_FFFF) + (x8 >>> 16);
  return x16;
}

La méthode size est totalement triviale, et la méthode containsKey se met en œuvre très facilement au moyen de get, puisqu'il suffit de voir si elle retourne null ou non.

Notez qu'il aurait aussi été possible de se passer de la méthode get dans containsKey, en regardant si l'élément du tableau values à la position déterminée par la clef est null.

public int size() {
  return size;
}

public boolean containsKey(K k) {
  return get(k) != null;
}

La méthode get consulte simplement le tableau values à la position déterminée par la clef, qui s'obtient elle au moyen de la méthode ordinal.

La méthode getOrDefault utilise get et retourne la même valeur qu'elle si elle est non nulle, ou la valeur reçue en second argument sinon.

public V get(K key) {
  return values[key.ordinal()];
}

public V getOrDefault(K k, V d) {
  V maybeV = get(k);
  return maybeV != null ? maybeV : d;
}

La méthode put n'est pas très difficile à mettre en œuvre, il faut juste prendre garde à correctement mettre la taille (attribut size) à jour. En effet, si une valeur était déjà présente dans la table avant l'appel pour la clef donnée, alors la taille ne change pas ! Sinon, elle augmente d'une unité.

La méthode putAll se met en œuvre facilement à condition d'utiliser put. Il suffit en effet de regarder, pour chaque clef possible, si elle se trouve dans la table reçue (that). Si tel est le cas, on l'ajoute (au moyen de put) à la table actuelle, sinon on ne fait rien.

public void put(K k, V v) {
  int i = k.ordinal();
  if (values[i] == null)
    size += 1;
  values[i] = requireNonNull(v);
}

public void putAll(SimpleMap<K, V> that) {
  for (K k: allKeys) {
    V maybeV = that.get(k);
    if (maybeV != null)
      put(k, maybeV);
  }
}

La méthode remove présente la même petite difficulté que put, à savoir qu'il ne faut retirer une unité de la taille (attribut size) que si la clef est bien présente dans la table.

La méthode clear est très facile à mettre en œuvre en s'aidant de la méthode fill de la classe Arrays, même s'il est aussi possible (mais moins efficace) d'effectuer une boucle pour mettre tous les éléments du tableau values à null.

public V remove(K k) {
  V maybeV = get(k);
  if (maybeV != null)
    size -= 1;
  values[k.ordinal()] = null;
  return maybeV;
}

public void clear() {
  Arrays.fill(values, null);
  size = 0;
}

La méthode toString n'est pas difficile à mettre en œuvre, il suffit de parcourir les clefs de la même manière que dans putAll, en ajoutant la représentation de chaque paire dont la valeur n'est pas nulle au bâtisseur de chaîne.

Il faut toutefois prendre garde à correctement séparer les paires au moyen d'une virgule, ce qui peut se faire en ajoutant une virgule avant chaque paire, sauf la première. Ce cas se détecte facilement en consultant le nombre de caractères présents dans le bâtisseur de chaîne au moyen de sa méthode length.

public String toString() {
  StringBuilder b = new StringBuilder("{");
  for (K k: allKeys) {
    V maybeV = get(k);
    if (maybeV != null) {
      if (b.length() > 1)
	b.append(",");
      b.append(k).append("=").append(maybeV);
    }
  }
  return b.append("}").toString();
}