Examen final

Les redéfinitions de hashCode et equals sont tout à fait standard et ne posent aucun problème.

@Override
public int hashCode() {
  return Objects.hash(id, name);
}

@Override
public boolean equals(Object thatO) {
  if (thatO instanceof Station) {
    Station that = (Station) thatO;
    return (this.id == that.id)
      && this.name.equals(that.name);
  } else
    return false;
}

Pour rendre impossible la création de deux instances différentes de Station ayant les mêmes attributs, il suffit de stocker toutes les instances créées dans une table associative, comme suggéré. La seule difficulté est de savoir quelle clef utiliser afin que chacune d'entre elles identifie une instance de manière unique. Une solution simple consiste à utiliser une chaîne de caractères formée à partir de l'identité et du nom de la gare, séparés par un espace.

La table contenant les instances doit bien entendu être stockée dans un attribut statique, afin d'être accessible à la méthode of :

private static final Map<String, Station> memoMap =
  new HashMap<>();

Cet attribut est nommé memoMap ici, car la technique utilisée ici se nomme memoization en anglais — ou parfois, pour d'obscures raisons historiques, hash consing.

Une fois cet attribut déclaré, la méthode of n'a plus qu'à consulter la table pour voir si une instance correspondant aux arguments reçus a déjà été créée. Si ce n'est pas le cas, elle est créée et ajoutée à la table. Finalement, l'instance est retournée :

public static Station of(int id, String name) {
  String key = id + " " + name;
  Station station = memoMap.get(key);
  if (station == null) {
    station = new Station(id, name);
    memoMap.put(key, station);
  }
  return station;
}

Cette méthode peut s'écrire de manière encore bien plus concise en utilisant la méthode computeIfAbsent de Map, prévue pour ce genre de situation :

public static Station of(int id, String name) {
  String key = id + " " + name;
  return memoMap.computeIfAbsent(key,
				 k -> new Station(id, name));
}

La méthode ofSortedArray doit tout d'abord valider le tableau qu'elle reçoit afin de vérifier qu'il est bien trié par ordre croissant et ne contient aucun doublon. Cela peut se faire en vérifiant que chaque élément est bien strictement supérieur à son prédécesseur.

Cela fait, ofSortedArray doit encore copier le tableau qu'elle reçoit en argument, afin de garantir l'immuabilité de la classe, car cela n'est pas fait par le constructeur.

public static StringSet ofSortedArray(String[] elements) {
  for (int i = 1; i < elements.length; i++) {
    if (elements[i - 1].compareTo(elements[i]) >= 0)
      throw new IllegalArgumentException();
  }
  return new StringSet(elements.clone());
}

Il est bien entendu aussi possible d'utiliser la méthode copyOf de Arrays pour copier le tableau, ainsi :

return new StringSet(Arrays.copyOf(elements,
				   elements.length));

Les méthodes size et isEmpty sont triviales à définir.

public int size() { return elements.length; }
public boolean isEmpty() { return size() == 0; }

Étant donné l'existence de la méthode binarySearch dans Arrays, la méthode contains est également triviale à définir. Il lui suffit de vérifier que l'index retourné par cette méthode n'est pas négatif.

public boolean contains(String e) {
  return Arrays.binarySearch(elements, e) >= 0;
}

Pour effectuer l'union de deux ensembles, on peut commencer par comparer le premier élément de leurs tableaux respectifs et :

• si le premier est strictement inférieur au second, alors on sait qu'il n'apparaît pas dans le second ensemble ; on peut donc l'inclure dans l'union et continuer en comparant, de la même manière, le second élément du premier tableau avec le premier du second tableau,
• si le second est strictement inférieur au premier, alors on sait qu'il n'apparaît pas dans le premier ensemble ; on peut donc l'inclure dans l'union et continuer en comparant, de la même manière, le premier élément du premier tableau avec le second du second tableau,
• si les deux éléments sont égaux, alors on sait que cet élément commun apparaît dans les deux ensembles ; on peut donc l'inclure dans l'union et continuer en comparant, de la même manière, le second élément du premier tableau avec le second du second tableau.

Une fois qu'on a parcouru ainsi la totalité des éléments d'au moins un des deux tableaux, on sait que les éventuels éléments restants dans l'autre tableau font tous partie de l'union.

Cette idée est mise en œuvre ci-dessous. Les éléments faisant partie de l'union sont stockés dans le tableau elementsU, dont la taille est égale à la somme des tailles des deux tableaux — la taille de l'union étant forcément plus petite ou égale à elle. La boucle while parcourt les deux tableaux en parallèle comme expliqué ci-dessus, tandis que les appels à arraycopy qui suivent se chargent de copier les éléments restants dans l'un des tableaux une fois que l'autre a été parcouru en totalité. Finalement, un appel à copyOf est fait pour « redimensionner » le tableau contenant l'union s'il est trop grand, afin de pouvoir le passer au constructeur de StringSet.

public StringSet union(StringSet that) {
  String[] elementsU = new String[this.size() + that.size()];
  int newSize = 0;

  int thisI = 0, thatI = 0;
  while (thisI < this.size() && thatI < that.size()) {
    String e1 = this.elements[thisI];
    String e2 = that.elements[thatI];
    int c = e1.compareTo(e2);
    if (c < 0) {
      elementsU[newSize++] = e1;
      thisI += 1;
    } else if (c > 0) {
      elementsU[newSize++] = e2;
      thatI += 1;
    } else {
      elementsU[newSize++] = e1;
      thisI += 1;
      thatI += 1;
    }
  }
  if (thisI < this.size()) {
    System.arraycopy(this.elements, thisI,
		     elementsU, newSize,
		     this.size() - thisI);
    newSize += this.size() - thisI;
  } else if (thatI < that.size()) {
    System.arraycopy(that.elements, thatI,
		     elementsU, newSize,
		     that.size() - thatI);
    newSize += that.size() - thatI;
  }

  if (newSize != elementsU.length)
    elementsU = Arrays.copyOf(elementsU, newSize);
  return new StringSet(elementsU);
}

La méthode iterator n'est pas très difficile à définir étant donné que les éléments de l'ensemble sont stockés dans un tableau, qu'il suffit de parcourir. L'itérateur de StringSet est donc similaire à celui de SArrayList donné dans le cours, mais encore plus simple puisque sa méthode remove ne doit rien faire d'autre que lever une exception.

public Iterator<String> iterator() {
  return new Iterator<String>() {
    int nextI = 0;

    public boolean hasNext() {
      return nextI < elements.length;
    }

    public String next() {
      if (!hasNext()) throw new NoSuchElementException();
      return elements[nextI++];
    }
  };
}

Notez qu'il n'est pas nécessaire de définir la méthode remove, car l'interface Iterator en possède une version par défaut, qui a le comportement attendu. Si on désire toutefois la redéfinir, il faut le faire ainsi :

public void remove() {
  throw new UnsupportedOperationException();
}

La méthode toString s'écrit aisément au moyen de la classe StringJoiner.

public String toString() {
  StringJoiner j = new StringJoiner(", ", "[", "]");
  for (String s : this) j.add(s);
  return j.toString();
}

Notez que comme StringSet implémente Iterable, il est aussi possible d'ajouter les éléments au StringJoiner en utilisant la méthode forEach, ainsi :

forEach(j::add);

Oui, StringSet doit redéfinir hashCode et equals afin que ses instances soient comparées par structure, car il s'agit d'une classe immuable. La redéfinition de ces méthodes ne pose aucun problème, il faut juste prendre garde à utiliser les méthodes de Arrays pour déterminer la valeur de hachage et effectuer le test d'égalité, car les méthodes hashCode et equals des tableaux fonctionnent par référence.

public int hashCode() {
  return Arrays.hashCode(elements);
}

public boolean equals(Object thatO) {
  if (thatO instanceof StringSet) {
    StringSet that = (StringSet) thatO;
    return Arrays.equals(this.elements, that.elements);
  } else
    return false;
}

Pour généraliser StringSet en une classe capable de stocker n'importe quel type d'éléments comparables, il faut bien entendu définir une classe générique. Son paramètre de type doit être borné pour garantir que les éléments sont effectivement comparables entre eux.

public final class ComparableSet<E extends Comparable<E>>
  implements Iterable<E> { … }

Étant donné que le bâtisseur de StringSet doit utiliser un tableau de type String[] pour stocker ses éléments, il peut le gérer de la même manière que la classe SArrayList décrite dans le cours. C'est-à-dire qu'un tableau d'une capacité initiale fixe (p.ex. 10) est créé, et dès qu'il devient trop petit pour contenir la totalité des éléments, son contenu est transféré dans un nouveau tableau deux fois plus grand.

Une fois cette constatation faite, la méthode add n'est pas très difficile à écrire, et est une version simplifiée de la méthode add de la classe SArrayList décrite dans le cours.

La méthode compact est quant à elle un peu plus difficile à écrire. Dans un premier temps, elle appelle simplement la méthode sort de Arrays afin de trier les éléments. Cela fait, elle doit encore éliminer les doublons. Une manière relativement simple (et efficace) de le faire consiste à parcourir les éléments du tableau en utilisant deux index :

• un premier index « lent » (slow ci-dessous), qui désigne toujours la position à laquelle le prochain élément unique (c-à-d qui n'est pas un doublon) pourra être inséré,
• un second index « rapide » (fast ci-dessous) qui parcourt la totalité des éléments du tableau, à la recherche de ceux qui sont uniques.

Les deux index commencent à 1, car l'élément à l'index 0 ne peut en aucun cas être un doublon. Comme le tableau est trié, les doublons se suivent forcément, et pour déterminer si l'élément désigné par l'index rapide est unique, il suffit de vérifier s'il est différent de son prédécesseur. Si c'est le cas, il est copié à la position désignée par l'index lent, qui est ensuite incrémenté.

Une fois tous les éléments ainsi examinés par l'index rapide, il ne reste plus qu'à effacer tous les éléments d'index supérieur à l'index lent. Cela n'est pas absolument nécessaire, mais fortement conseillé, car évite de conserver des références vers des objets (ici des chaînes) inutiles, ce qui peut diminuer la quantité de mémoire utilisée par le programme.

Finalement, la méthode build est facile à écrire puisqu'il lui suffit d'appeler compact pour garantir que le tableau est trié par ordre croissant et ne contient pas de doublons, avant d'appeler le constructeur de StringSet avec une copie de la partie du tableau contenant effectivement des éléments.

public static final class Builder {
  private String[] elements = new String[10];
  private int size = 0;

  public Builder add(String e) {
    if (size == elements.length)
      elements = Arrays.copyOf(elements, 2 * size);
    elements[size++] = e;
    return this;
  }

  public Builder compact() {
    Arrays.sort(elements, 0, size);
    int slow = 1;
    for (int fast = 1; fast < size; fast++) {
      if (elements[fast - 1].compareTo(elements[fast]) != 0)
	elements[slow++] = elements[fast];
    }
    // optionnel mais conseillé !
    Arrays.fill(elements, slow, size, null);
    size = slow;
    return this;
  }

  public StringSet build() {
    compact();
    return new StringSet(Arrays.copyOf(elements, size));
  }
}

Notez que cette solution utilise une variante de la méthode sort qui n'était malheureusement pas mentionnée dans le formulaire. Pour utiliser la version donnée dans le formulaire, il faut remplacer l'appel à sort au début de compact par les trois lignes suivantes :

if (size < elements.length)
  elements = Arrays.copyOf(elements, size);
Arrays.sort(elements);

Le but de la copie additionnelle de elements est de faire en sorte que le tableau passé à sort ne contienne plus aucun élément nul, car ceux-ci provoquent la levée d'une exception.

La méthode isCircularVia doit vérifier deux choses :

1. le chemin est bien circulaire,
2. le chemin passe par la gare donnée.

La première vérification se fait en comparant les gares aux extrémités du chemin (station1 et station2), tandis que la seconde se fait en parcourant les routes à la recherche d'une qui passe par la gare donnée.

private boolean isCircularVia(Station s) {
  if (station2.equals(station1))
    for (Route r : routes)
      if (r.stations().contains(s)) return true;
  return false;
}

La méthode circular est très similaire à longest, et ne diffère qu'en trois aspects :

1. les chemins construits à l'initialisation sont ceux qui débutent à la gare de départ uniquement,
2. lors de l'extension d'un chemin, si le chemin étendu est circulaire et passe par la gare donnée, on peut immédiatement le retourner,
3. lorsque tous les chemins possibles ont été générés, et qu'aucun satisfaisant les critères n'a été trouvé, on retourne null.

Ces trois différences signifient que la méthode circular diffère de la méthode longest en trois endroits : dans la boucle d'initialisation (lignes 3 à 6), dans la boucle d'extension (lignes 13 à 16) et à la fin (ligne 21). En faisant référence aux lignes inchangées de longest, on peut donc l'écrire ainsi :

public static Trail circular(List<Route> routes,
			     Station start,
			     Station via) {
  // ligne 2
  for (Route r : routes) {
    if (r.stations().contains(start)) {
      var s2 = r.stationOpposite(start);
      trails.add(new Trail(start, s2, List.of(r)));
    }
  }
  // lignes 8 à 12
  for (Route route : unusedRoutes) {
    Trail extended = trail.tryToExtendWith(route);
    if (extended != null) {
      if (extended.isCircularVia(via)) return extended;
      newTrails.add(extended);
    }
  }
  // lignes 18 à 20
  return null;
}

Les interfaces ressemblent beaucoup aux classes du même nom, la seule différence étant que leurs méthodes sont abstraites et qu'elles ne contiennent bien entendu aucun attribut. Pour qu'une valeur de type GameState soit utilisable partout où une valeur de type PublicGameState est attendue, il suffit de faire en sorte que cette première interface étende la seconde.

Notez que la méthode withShuffledCards donnée dans l'énoncé prenait un argument inutile, que nous avons reproduit ci-dessous mais qui peut aussi être supprimé.

public interface PublicGameState {
  int cardCount();
}
public interface GameState extends PublicGameState {
  GameState withShuffledCards(Card c);
}

La classe ConcretePublicGameState est identique à la classe PublicGameState de l'énoncé, à deux différences près :

1. elle est finale, comme toute classe immuable,
2. elle implémente l'interface PublicGameState.

public final class ConcretePublicGameState
    implements PublicGameState {
  private final int cardCount;

  public ConcretePublicGameState(int cardCount) {
    this.cardCount = cardCount;
  }

  public int cardCount() { return cardCount; }
}

La classe ConcreteGameState ressemble à la classe GameState de l'énoncé, les différences étant :

1. elle implémente GameState au lieu d'hériter de ConcretePublicGameState (ce qui ne serait pas possible),
2. elle n'appelle dès lors pas le super-constructeur dans son constructeur à elle,
3. elle contient une mise en œuvre de cardCount, car elle ne l'hérite plus de sa classe mère,
4. sa méthode withShuffledCards retourne une valeur de type GameState mais crée bien entendu une instance de ConcreteGameState.

public final class ConcreteGameState implements GameState {
  private final List<Card> cards;

  public ConcreteGameState(List<Card> cards) {
    this.cards = List.copyOf(cards);
  }

  public int cardCount() { return cards.size(); }

  public GameState withShuffledCards(Card c) {
    List<Card> newCards = new ArrayList<>(cards);
    Collections.shuffle(newCards);
    return new ConcreteGameState(newCards);
  }
}