CS-108 — Examen intermédiaire : corrigé

La définition du constructeur et des accesseurs est triviale :

public RotatedString(String string, int index) {
  if (! (0 <= index && index < string.length()))
    throw new IndexOutOfBoundsException();

  this.string = string;
  this.index = index;
}

public String string() { return string; }
public int index() { return index; }

La méthode charAt commence par calculer l'index du caractère désiré dans la chaîne avant rotation, puis appelle la méthode charAt sur cette chaîne afin de l'obtenir. Pour calculer l'index en question, il suffit d'ajouter l'index du début de la rotation à l'index du caractère, puis de ramener le résultat à une valeur valide au moyen du reste de la division. On obtient donc :

public char charAt(int i) {
  if (! (0 <= i && i < string.length()))
    throw new IndexOutOfBoundsException();
  return string.charAt((index + i) % string.length());
}

La manière la plus simple de définir la méthode equals consiste à utiliser la méthode compareTo et de voir si elle retourne 0. On obtient alors :

@Override
public boolean equals(Object thatO) {
  return (thatO instanceof RotatedString)
    && (compareTo((RotatedString)thatO) == 0);
}

Pour la méthode hashCode, la principale difficulté consiste à constater que la formule donnée, qui n'est pas totalement triviale, peut se calculer très facilement au moyen d'une boucle :

@Override
public int hashCode() {
  int h = 0;
  for (int i = 0; i < string.length(); ++i)
    h = h * 31 + charAt(i);
  return h;
}

Bien entendu, hashCode utilise la méthode charAt définie plus haut afin d'obtenir facilement le i^e caractère de la chaîne après rotation.

Une manière simple de mettre en œuvre l'ordre lexicographique consiste à parcourir en parallèle les caractères des deux chaînes, en les comparant deux à deux, et en s'arrêtant à la première différence ou lorsque la chaîne la plus courte est épuisée. A ce moment, de deux choses l'une :

• soit on a trouvé une différence entre deux caractères des chaînes, auquel cas il suffit de retourner le résultat de leur comparaison,
• soit on est arrivé au bout de la plus courte des deux chaînes, auquel cas il suffit de retourner le résultat de la comparaison de leur longueur.

@Override
public int compareTo(RotatedString that) {
  int l1 = this.string.length();
  int l2 = that.string.length();
  for (int i = 0; i < Math.min(l1, l2); ++i) {
    int cmp = Character.compare(this.charAt(i),
                                that.charAt(i));
    if (cmp != 0)
      return cmp;
  }
  return Integer.compare(l1, l2);
}

La méthode toString s'écrit très facilement au moyen d'un bâtisseur de chaîne et de la variante de la méthode append donnée dans le formulaire :

@Override
public String toString() {
  return new StringBuilder(string.length())
    .append(string, index, string.length())
    .append(string, 0, index)
    .toString();
}

Il est également possible d'utiliser la méthode substring de String, mais cela est légèrement moins efficace.

Le problème de cette définition de hashCode est qu'elle n'est pas compatible avec equals, dans le sens où il est possible d'avoir deux rotations considérée comme égales par equals mais ayant des valeur de hachage différentes. Il en va par exemple ainsi des rotations o1 et o2 suivantes :

RotatedString o1 = new RotatedString("EPFL", 0);
RotatedString o2 = new RotatedString("FLEP", 2);

Le premier problème à résoudre pour mettre en œuvre le tri par base est de savoir comment itérer sur les chiffres des nombres, du moins significatif au plus significatif. Pour ce faire, il faut bien entendu utiliser la division entière et son reste : le n^e chiffre (depuis la droite) d'un nombre s'obtient en le divisant par 10ⁿ puis en obtenant le reste de la division de cette valeur par 10. Dans le code ci-dessous, la variable d vaut 10ⁿ à la n^e itération de la boucle.

Pour stocker les sous-listes correspondant aux différents chiffres, on peut utiliser soit un tableau dynamique (comme ci-dessous), soit une table associative, la première solution étant probablement plus rapide.

void sort(List<Integer> ints) {
  for (int d = 1; d <= 1000000000; d *= 10) {
    List<List<Integer>> subLists = new ArrayList<>(10);
    for (int i = 0; i < 10; ++i)
      subLists.add(new ArrayList<>());

    for (int i: ints) {
      int digit = (i / d) % 10;
      subLists.get(digit).add(i);
    }

    ints.clear();
    for (List<Integer> subList: subLists)
      ints.addAll(subList);
  }
}

Pour utiliser la base 256 (ou n'importe quelle autre base), il faut changer la formule à utiliser pour extraire le n^e chiffre, et le nombre de sous-listes. L'intérêt d'utiliser une base qui soit une puissance de deux est que l'extraction du n^e chiffre peut se faire au moyen du décalage à droite et du masquage, plutôt qu'au moyen de la division entière et de son reste, plus coûteuse.

La variante ci-dessous de la méthode sort utilise cette constatation pour effectuer le tri en base 256.

void sortBase256(List<Integer> ints) {
  for (int b = 0; b < Integer.SIZE; b += 8) {
    List<List<Integer>> subLists = new ArrayList<>(0xFF);
    for (int i = 0; i <= 0xFF; ++i)
      subLists.add(new ArrayList<>());

    for (int i: ints) {
      int digit = (i >> b) & 0xFF;
      subLists.get(digit).add(i);
    }

    ints.clear();
    for (List<Integer> subList: subLists)
      ints.addAll(subList);
  }
}