Examen intermédiaire

Les méthodes capacity et size sont triviales à écrire pour peu qu'on se souvienne de la différence entre ces deux notions.

public int capacity() {
  return chars.length;
}

public int size() {
  return size;
}

La seule petite difficulté de la méthode charAt est qu'il ne faut pas oublier de valider l'index reçu, car on ne peut pas faire l'hypothèse qu'un index invalide va provoquer la levée d'une IndexOutOfBoundsException lors de l'accès au tableau. En effet, les index compris entre la taille et la capacité sont valides pour le tableau mais invalides pour le bâtisseur.

public char charAt(int index) {
  // Autre option : Objects.checkIndex(index, size)
  if (!(0 <= index && index < size))
    throw new IndexOutOfBoundsException();
  return chars[index];
}

La méthode append consiste en deux parties.

Premièrement, on « redimensionne » le tableau chars, par copie, si sa taille ne permet pas de stocker la totalité des caractères de la chaîne en cours de construction, après l'ajout. Pour cela, on fait progressivement doubler sa taille jusqu'à ce qu'elle soit suffisante.

Deuxièmement, une fois le tableau éventuellement « redimensionné », on y copie les caractères de la chaîne au moyen de la méthode getChars, avant de mettre à jour la taille de la chaîne en cours de construction.

public SStringBuilder append(String s) {
  int size1 = size + s.length();

  int capacity1 = chars.length;
  while (capacity1 < size1)
    capacity1 <<= 1; // autre option : capacity1 *= 2
  if (capacity1 != chars.length)
    chars = Arrays.copyOf(chars, capacity1);

  s.getChars(0, s.length(), chars, size);
  size = size1;
  return this;
}

La principale difficulté de la méthode removeIf est de ne faire qu'un seul parcours du tableau chars pour éliminer les éléments indésirés. Cela peut se faire au moyen de deux index, nommés src et dst ci-dessous.

L'index src parcourt tout le tableau et désigne le caractère en cours d'examen. L'index dst quant à lui désigne la position à laquelle le prochain caractère non supprimé doit être placé, et il est toujours inférieur ou égal à src.

Lorsque le caractère désigné par src doit être gardé, c.-à-d. que la méthode test du prédicat retourne faux pour lui, on le copie au besoin à la position désignée par dst, puis on avance dst.

Une fois la totalité du tableau parcouru par src, dst contient forcément l'index du caractère qui suit le dernier qui a été conservé, soit la nouvelle taille de la chaîne en cours de construction.

public SStringBuilder removeIf(Predicate<Character> predicate) {
  int dst = 0;
  for (int src = 0; src < size; src += 1) {
    if (predicate.test(chars[src])) continue;
    if (dst != src) chars[dst] = chars[src];
    dst += 1;
  }
  size = dst;
  return this;
}

La technique utilisée par removeIf est identique à celle utilisée, dans le projet, pour éliminer les tuples dominés par le nouveau lors d'un ajout.

La méthode build est triviale et consiste en un simple appel au constructeur de String mentionné dans l'énoncé.

public String build() {
  return new String(chars, 0, size);
}

L'écriture de la classe ByteArrayMSBF ne pose pas de problème particulier, si ce n'est que dans la méthode getShort il ne faut pas oublier d'appliquer toUnsignedInt à l'octet de poids faible, faute de quoi son bit de poids le plus fort est dupliqué dans les 8 bits de poids fort du résultat lors de l'extension de signe.

public final class ByteArrayMSBF implements ByteArray {
  private final byte[] array;

  public ByteArrayMSBF(byte[] array) {
    this.array = array;
  }

  @Override
  public int size() {
    return array.length;
  }

  @Override
  public byte getByte(int index) {
    // Optionnel:
    // if (!(0 <= index && index < size())) throw …
    return array[index];
  }

  @Override
  public short getShort(int index) {
    // Optionnel:
    // if (!(0 <= index && index < size() - 1)) throw …
    return (short) ((array[index] << 8)
                    | Byte.toUnsignedInt(array[index + 1]));
  }
}

La classe ByteArraySlice est plus complexe à écrire correctement que ByteArrayMSBF car ses méthodes getByte et getShort doivent obligatoirement valider l'index reçu. En effet, tout comme pour la méthode charAt de l'exercice précédent, il existe des index invalides pour une tranche mais valides pour le tableau sous-jacent.

Le constructeur doit lui aussi valider les index reçus, comme spécifié dans l'énoncé.

public final class ByteArraySlice implements ByteArray {
  private final ByteArray byteArray;
  private final int fromInclusive, size;

  public ByteArraySlice(ByteArray byteArray,
                        int fromInclusive,
                        int toExclusive) {
    if (!(0 <= fromInclusive
          && fromInclusive < byteArray.size()))
      throw new IndexOutOfBoundsException();
    if (!(fromInclusive <= toExclusive
          && toExclusive <= byteArray.size()))
      throw new IndexOutOfBoundsException();

    this.byteArray = byteArray;
    this.fromInclusive = fromInclusive;
    this.size = toExclusive - fromInclusive;
  }

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

  @Override
  public byte getByte(int index) {
    if (!(0 <= index && index < size()))
      throw new IndexOutOfBoundsException();
    return byteArray.getByte(fromInclusive + index);
  }

  @Override
  public short getShort(int index) {
    if (!(0 <= index && index + 1 < size()))
      throw new IndexOutOfBoundsException();
    return byteArray.getShort(fromInclusive + index);
  }
}

Étant donné l'existence de la classe ByteArraySlice, la méthode slice est triviale à écrire, il faut juste se rendre compte que le tableau à « trancher » n'est autre que le récepteur, this.

Aucune vérification d'index n'est à faire, car elles sont faites par le constructeur de ByteArraySlice.

default ByteArray slice(int fromInclusive, int toExclusive) {
  return new ByteArraySlice(this, fromInclusive, toExclusive);
}

Même si la méthode slice de ByteArray fonctionne dans tous les cas, elle n'est pas très efficace lorsqu'on obtient une tranche d'une tranche, par exemple ainsi :

byte[] a = …;
ByteArray byteArray = new ByteArrayMSBF(a);
ByteArray doubleSlice = byteArray;
doubleSlice = doubleSlice.slice(1, doubleSlice.size() - 1);
doubleSlice = doubleSlice.slice(1, doubleSlice.size() - 1);

En effet, l'objet référencé par doubleSlice est une tranche de type ByteArraySlice qui référence une seconde tranche du même type, qui référence le tableau byteArray. Dès lors, chaque appel à la méthode getByte ou getShort de cet objet implique d'effectuer 2 appels à la même méthode de ByteArraySlice. Et bien entendu, le problème s'aggrave encore si on empile plus de deux tranches.

Sachant qu'une tranche de tranche est équivalente à une unique tranche, on peut donc redéfinir la méthode slice dans ByteArraySlice afin qu'elle évite l'empilement de tranches. Ce faisant, il ne faut pas oublier de valider les index, car cette tâche ne peut plus être laissée au constructeur de ByteArraySlice comme précédemment, toujours pour les mêmes raisons.

@Override
public ByteArray slice(int fromInclusive, int toExclusive) {
  if (!(0 <= fromInclusive && fromInclusive < size()))
    throw new IndexOutOfBoundsException();
  if (!(fromInclusive <= toExclusive && toExclusive <= size()))
    throw new IndexOutOfBoundsException();

  int fromInclusive1 = this.fromInclusive + fromInclusive;
  int toExclusive1 = this.fromInclusive + toExclusive;
  return new ByteArraySlice(byteArray,
                            fromInclusive1,
                            toExclusive1);
}

La première variante de lineEnds doit lire les caractère du flot et faire le nécessaire chaque fois qu'un caractère LF ou CR est rencontré.

Lorsqu'un caractère CR est rencontré, le caractère suivant est également lu afin de voir s'il s'agit d'un LF. Si tel est le cas, l'élément CR_LF est ajoutée à l'ensemble, sinon c'est l'élément CR qui l'est. Finalement, si ce caractère est un CR, alors le test est répété.

Sachant que les caractères LF qui suivent un caractère CR sont traités par le cas précédent, les caractères LF restants provoquent simplement l'ajout de l'élément LF à l'ensemble.

Set<LineEnd> lineEnds(Reader reader) throws IOException {
  int nextChar;
  // Autre option : lineEnds = new HashSet<>()
  Set<LineEnd> lineEnds = EnumSet.noneOf(LineEnd.class);
  while ((nextChar = reader.read()) != -1) {
    switch (nextChar) {
      case '\n' -> lineEnds.add(LineEnd.LF);
      case '\r' -> {
        do {
          nextChar = reader.read();
          lineEnds.add(nextChar == '\n'
                       ? LineEnd.CR_LF
                       : LineEnd.CR);
        } while (nextChar == '\r');
      }
    }
  }
  return lineEnds;
}

Une autre manière d'écrire lineEnds consiste à utiliser une variable booléenne, nommée pendingCR ci-dessous, pour savoir si le caractère précédent était un CR.

Set<LineEnd> lineEnds(Reader reader) throws IOException {
  int nextChar;
  boolean pendingCR = false;
  // Autre option : lineEnds = new HashSet<>()
  Set<LineEnd> lineEnds = EnumSet.noneOf(LineEnd.class);
  while ((nextChar = reader.read()) != -1) {
    if (nextChar == '\n')
      lineEnds.add(pendingCR ? LineEnd.CR_LF : LineEnd.LF);
    else if (pendingCR)
      lineEnds.add(LineEnd.CR);
    pendingCR = (nextChar == '\r');
  }
  if (pendingCR) lineEnds.add(LineEnd.CR);
  return lineEnds;
}

La seconde variante de lineEnds consiste en un simple appel à la première qui est fait dans le contexte d'un try-with-resource qui garantit que le flot permettant de lire les caractères du fichier est fermé dans tous les cas.

Set<LineEnd> lineEnds(String fileName) throws IOException {
  try (Reader s = new FileReader(fileName)) {
    return lineEnds(s);
  }
}