Examen final

Le corps de la classe abstraite retournée par intArrayAsList est presque identique à celui de la classe ArrayAdapter du cours sur le patron Adapter. La seule différence est que, contrairement à ArrayAdapter, la classe dont une instance est retournée par intArrayAsList n'est pas générique, puisque les éléments de la liste qu'elle représente ont un type connu, à savoir Integer.

public static List<Integer> intArrayAsList(int[] array) {
  return new AbstractList<>() {
    @Override
    public Integer get(int index) {
      return array[index];
    }

    @Override
    public Integer set(int index, Integer element) {
      int oldElement = array[index];
      array[index] = element;
      return oldElement;
    }

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

Il faut noter que même si le code des méthodes de cette classe est en apparence identique à celui de ArrayAdapter, il ne l'est pas en réalité. En effet, en raison de l'emballage automatique (autoboxing), le code de la méthode get ci-dessus est récrit automatiquement pas Java en celui-ci :

public E get(int index) {
  return Integer.valueOf(array[index]);
}

et celui de set est récrit de manière similaire.

C'est la raison pour laquelle il n'est pas possible, comme dit dans l'énoncé de l'examen, d'utiliser ArrayAdapter — ou Arrays.asList de la bibliothèque Java — à la place de intArrayAsList.

La méthode shuffle est une traduction directe en Java de la description de l'algorithme donnée dans l'énoncé. La seule petite difficulté est d'échanger deux éléments du tableau, ce qui peut se faire au moyen d'une variable temporaire, nommée t ci-dessous.

static void shuffle(int[] array,
                    RandomGenerator randomGenerator) {
  for (int i = 0; i < array.length - 1; i += 1) {
    int j = randomGenerator.nextInt(i, array.length);
    int t = array[i];
    array[i] = array[j];
    array[j] = t;
  }
}

Cet algorithme de mélange est généralement connu sous le nom d'algorithme de Fisher-Yates, ou algorithme de Knuth.

La manière la plus simple de définir l'itérateur retourné par concat est d'utiliser une classe anonyme implémentant l'interface Iterator. Comme cette dernière possède une définition par défaut de la méthode remove qui fait déjà ce qui est demandé — c.-à-d. qu'elle lève une UnsupportedOperationException — seules les méthodes hasNext et next doivent être définies dans cette classe.

La méthode hasNext retourne vrai si au moins l'un des deux itérateurs à concaténer peut encore fournir une valeur, tandis que next fourni soit la prochaine valeur du premier itérateur — s'il en a encore une à fournir — soit celle du second itérateur.

Il faut noter qu'il n'est pas strictement nécessaire de vérifier, au début de la méthode next, que hasNext retourne vrai et de lever une exception si ce n'est pas le cas, car cela sera fait au besoin par la méthode next du second itérateur.

static <T> Iterator<T> concat(Iterator<T> it1,
                              Iterator<T> it2) {
  return new Iterator<T>() {
    @Override
    public boolean hasNext() {
      return it1.hasNext() || it2.hasNext();
    }

    @Override
    public T next() {
      if (it1.hasNext()) return it1.next();
      return it2.next();
    }
  };
}

Tout comme concat, map s'écrit relativement facilement au moyen d'une classe anonyme implémentant l'interface Iterator et redéfinissant ses méthodes hasNext et next.

La méthode hasNext retourne le résultat de la méthode hasNext de l'itérateur sous-jacent, tandis que la méthode next obtient le prochain élément de l'itérateur sous-jacent et le passe à la méthode apply de la fonction afin de le transformer, puis retourne la valeur ainsi obtenue.

static <T, R> Iterator<R> map(Iterator<T> it,
                              Function<T, R> f) {
  return new Iterator<R>() {
    @Override
    public boolean hasNext() {
      return it.hasNext();
    }

    @Override
    public R next() {
      return f.apply(it.next());
    }
  };
}

La méthode max commence par vérifier que l'itérateur donné peut fournir au moins une valeur, c.-à-d. que sa méthode hasNext retourne initialement vrai. Si ce n'est pas le cas, une NoSuchElementException est levée, comme demandé dans l'énoncé. (Cette vérification n'est pas strictement nécessaire, car next lève cette même exception si l'itérateur n'a aucun élément à fournir.)

Sinon, la première valeur fournie par l'itérateur est utilisée comme valeur initiale du maximum, après quoi les éventuels autres éléments sont parcourus, et si l'un d'entre eux est plus grand que le maximum actuel, il le remplace.

Une fois tous les éléments ainsi parcourus, le maximum actuel est retourné.

static <T extends Comparable<T>> T max(Iterator<T> it) {
  if (!it.hasNext()) throw new NoSuchElementException();
  T max = it.next();
  while (it.hasNext()) {
    T next = it.next();
    if (next.compareTo(max) > 0) max = next;
  }
  return max;
}

Il faut noter que l'appel next.compareTo(max) est valide car on sait que les éléments fournis par l'itérateur possèdent une méthode compareTo en raison de la borne inférieure placée sur le paramètre de type T (T extends Comparable<T>).

Sachant que la chaîne en cours de construction est constituée de tous les caractères du tableau sauf ceux du trou, et sachant que le trou a une taille de gapSize caractères, la méthode length s'écrit au moyen d'une simple soustraction :

int length() {
  return buffer.length - gapSize;
}

La méthode insert est assez similaire à la méthode add de la classe SArrayList, mais plus complexe en raison du fait que le trou — la capacité du tableau actuellement inutilisée — peut se trouver à une position quelconque.

La première chose que fait cette méthode est de valider l'index reçu, et elle lève une exception s'il n'est pas valide.

Cela fait, elle détermine ensuite si le trou a une taille nulle. Dans ce cas, elle créée un nouveau tableau deux fois plus grand que l'actuel et y copie les éléments de l'actuel de manière à ce que le trou débute à la position d'insertion.

Si le trou n'a pas une taille nulle, mais qu'il ne commence pas à la position d'insertion, insert le déplace afin que ce soit le cas. Pour cela, elle distingue les deux cas mentionnés dans l'énoncé, et fait les copies nécessaires.

Une fois ces ajustements effectués, le trou commence à la position d'insertion et il n'est pas vide. L'insertion du nouveau caractère se fait donc simplement en remplaçant le premier caractère du trou par celui à insérer, et en ajustant la position de départ et la taille du trou en fonction.

SStringBuilder insert(int i, char c) {
  if (!(0 <= i && i <= length()))
    throw new IndexOutOfBoundsException();

  if (gapSize == 0) {
    int newGapSize = buffer.length;
    char[] newBuffer = new char[buffer.length + newGapSize];
    System.arraycopy(buffer, 0,
                     newBuffer, 0,
                     i);
    System.arraycopy(buffer, i,
                     newBuffer, i + newGapSize,
                     buffer.length - i);
    buffer = newBuffer;
    gapSize = newGapSize;
    gapPos = i;
  } else if (gapPos < i) {
    System.arraycopy(buffer, gapPos + gapSize,
                     buffer, gapPos,
                     i - gapPos);
    gapPos = i;
  } else if (gapPos > i) {
    System.arraycopy(buffer, i,
                     buffer, i + gapSize,
                     gapPos - i);
    gapPos = i;
  }

  buffer[gapPos++] = c;
  gapSize -= 1;
  return this;
}

La méthode toString doit simplement concaténer les chaînes se trouvant des deux côtés du trou, qui peuvent être construites chacune au moyen d'un appel à la méthode valueOf mentionnée dans l'énoncé :

String toString() {
  return String.valueOf(buffer, 0, gapPos)
    + String.valueOf(buffer,
                     gapPos + gapSize,
                     buffer.length - (gapPos + gapSize));
}