Horaire et frontière de Pareto

ReCHor – étape 3

1. Introduction

Le but de cette troisième étape est double : d'une part définir des interfaces représentant l'horaire de transport public et ses composants ; d'autre part, écrire une classe permettant de représenter ce que l'on nomme la frontière de Pareto, et qui joue un rôle crucial dans l'algorithme de recherche de voyages optimaux.

2. Concepts

2.1. Horaire

Les données horaires que nous utiliserons dans ce projet pour rechercher les voyages optimaux sont une version légèrement simplifiée de celles de l'horaire suisse officiel. Elles sont constituées de :

l'ensemble des liaisons (concept décrit plus bas) effectuées un jour donné,
l'ensemble des courses effectuées un jour donné,
l'ensemble des lignes existantes,
l'ensemble des arrêts existants, constitué de deux sous-ensembles disjoints, celui des gares et celui des voies/quais,
l'ensemble des noms alternatifs des gares, c.-à-d. des noms qui permettent d'identifier une gare mais qui ne sont pas son nom officiel (p. ex. Losanna, le nom italien de Lausanne, est un nom alternatif de la gare de Lausanne dans les données que nous utiliserons),
l'ensemble des changements qu'il est possible d'effectuer, à pied, soit au sein d'une même gare, soit entre deux gares distinctes mais voisines.

Ces différents concepts ont déjà été introduits dans les étapes précédentes, sauf celui de liaison (connection), qui est un trajet effectué par un véhicule de transport en commun entre deux arrêts successifs, c.-à-d. sans arrêt intermédiaire. Une course n'est donc rien d'autre qu'une succession de liaisons.

Par exemple, nous avons vu que la ligne IR 15 des CFF relie Genève-Aéroport à Lucerne. De nombreux trains parcourent cette ligne chaque jour, chacun effectuant une course dans l'un des deux sens possible. Par exemple, le lundi 24 février 2025, un train effectuera une course partant de Genève-Aéroport à 9h45 et arrivant à Lucerne à 13h01. Lors de cette course, il s'arrêtera à 10 arrêts intermédiaires, les 5 premiers étant Genève, Nyon, Morges, Lausanne et Palézieux. Dès lors, cette course est constituée de 11 liaisons, les cinq premières étant :

celle partant de Genève-Aéroport à 9h45 et arrivant à Genève à 9h52,
celle partant de Genève à 9h54 et arrivant à Nyon à 10h07,
celle partant de Nyon à 10h09 et arrivant à Morges à 10h24,
celle partant de Morges à 10h26 et arrivant à Lausanne à 10h37,
celle partant de Lausanne à 10h40 et arrivant à Palézieux à 10h56.

Comme cet exemple l'illustre, une course comportant un total de n arrêts — en comptant les deux aux extrémités — est constituée de n – 1 liaisons.

2.1.1. Représentation des données

Pour avoir une idée de la taille des données, la table ci-dessous donne le nombre des entités des différents types pour le lundi 24 février 2025 — la date importe car le nombre de liaisons et de courses varie de jour en jour :

Données	Nombre
Liaisons	2 751 634
Courses	198 788
Lignes	7 723
Gares	33 275
Voies/quais	20 753
Changements	40 232

On le voit, la quantité de données est assez conséquente, et il est donc important de réfléchir à leur représentation. Cela est d'autant plus vrai que l'algorithme de recherche de voyage que nous utiliserons parcourt la totalité des liaisons, et comme il y en a près de 3 millions, cela doit pouvoir se faire rapidement.

2.1.2. Représentation standard

La manière naturelle de représenter les données d'un horaire en Java serait d'utiliser des enregistrements pour chacun des concepts mentionnés plus haut.

Par exemple, une liaison pourrait être représentée par l'enregistrement Connection ci-dessous, qui n'est pas sans rappeler l'enregistrement Leg.Transport de l'étape 1 (certains attributs ont été omis pour simplifier la discussion) :

record Connection(Stop depStop,
                  LocalTime depTime,
                  Stop arrStop,
                  LocalTime arrTime) { /* … */ }

Une fois cet enregistrement défini, l'ensemble de toutes les liaisons d'un horaire pourrait être représenté au moyen d'un tableau de type Connection[] ou d'un tableau dynamique de type ArrayList<Connection>. En mémoire, ce tableau et ses composants seraient organisés de la manière présentée à la figure 1 ci-dessous.

connections-as-records;8.png — Figure 1 : Liaisons représentées au moyen d'enregistrements

Même si cette représentation des liaisons au moyen d'enregistrements est naturelle en Java, et donc agréable à utiliser, elle n'est pas très efficace, pour deux raisons.

La première est qu'un objet distinct doit être créé pour chaque liaison, donc un total de près de 3 millions d'objets devraient être créés pour l'horaire suisse, ce qui est conséquent.

La seconde est que l'accès aux attributs de ces objets est relativement lent. Par exemple, pour obtenir l'heure de départ de la première liaison, il faut extraire le premier élément du tableau les contenant, qui est une référence vers un objet Connection, puis accéder à l'attribut depTime de cet objet. Cela ne pose pas de problème si de tels accès sont peu fréquents, mais quand il faut en faire plusieurs millions par requête, cela peut avoir un impact important sur les performances.

Pour cette raison, nous utiliserons une représentation dite « aplatie » (flat) des données, décrites ci-dessous.

2.1.3. Représentation aplatie

L'idée de la représentation aplatie est de ne pas représenter les liaisons individuelles au moyen d'un enregistrement comme Connection, mais de représenter uniquement la totalité des liaisons, en stockant leurs attributs consécutivement dans un unique tableau.

Les détails de cette représentation seront décrits dans une étape ultérieure, car ils n'importent pas pour celle-ci, mais pour donner une idée, on pourrait imaginer représenter la totalité des liaisons au moyen d'un tableau d'entiers de type short[]. Les données de la première liaison pourraient y être stockés dans les quatre premiers éléments du tableau, ainsi :

dans l'élément d'index 0, l'arrêt de départ (depStop), représenté par son index dans la représentation aplatie des arrêts,
dans l'élément d'index 1, l'heure de départ (depTime), représentée en nombre de minutes écoulées depuis minuit,
dans l'élément d'index 2, l'arrêt d'arrivée (arrStop), représenté par son index dans la représentation aplatie des arrêts,
dans l'élément d'index 3, l'heure d'arrivée (arrTime), représentée en nombre de minutes écoulées depuis minuit.

L'index de l'arrêt de départ de la seconde liaison serait ensuite placé dans l'élément d'index 4, et ainsi de suite. En d'autres termes, chaque liaison occuperait 4 entiers consécutifs de type short dans le tableau les contenant toutes, et qui contiendrait donc quelque chose comme 12 millions d'éléments. Le début de ce tableau est illustré dans la figure 1 ci-dessous — où 481 est la représentation de 8h01, 552 celle de 9h12, 7782 est supposé être l'index de l'arrêt de départ, 10172 celui de l'arrêt d'arrivée.

connections-in-array;8.png — Figure 2 : Liaisons représentées de manière aplatie

L'avantage de cette représentation par rapport à la représentation naturelle est que la totalité des liaisons est représentée par un unique objet — le tableau de type short[] — et que l'accès à un attribut d'une liaison ne requiert qu'un seul accès à un élément de ce tableau.

Une simple comparaison visuelle des figures 1 et 2 devrait permettre de se rendre compte que la représentation aplatie est beaucoup plus compacte que la naturelle, et il semble donc raisonnable d'en conclure que l'accès à ses éléments sera passablement plus rapide.

2.1.4. Impact du choix de la représentation

L'utilisation d'une représentation aplatie pour les données horaires a un impact important sur le code du projet. En effet, une telle représentation implique qu'il n'existe pas de représentation des éléments individuels — liaisons, arrêts, etc. — sous forme d'objets Java. Au lieu de cela, il existe une représentation de la totalité des éléments, et il est possible d'obtenir les différents attributs d'un élément dont on connaît l'index¹.

Ainsi, dans le cas des liaisons, l'utilisation d'une représentation aplatie implique l'existence d'une interface (ou d'une classe) représentant la totalité des liaisons. Cette interface pourrait ressembler à ceci :

interface Connections {
  int depStopId(int id);
  int depMins(int id);
  int arrStopId(int id);
  int arrMins(int id);
}

où la méthode depMins, par exemple, prend en argument l'index d'une liaison et retourne son heure de départ, en minutes après minuit. Dès lors, si l'on désire par exemple calculer la durée de la première liaison, on peut le faire en écrivant quelque chose comme :

Connections connections = …;
int firstConnectionDuration =
  connections.arrMins(0) - connections.depMins(0);

En comparaison, si on avait opté pour une représentation par enregistrements, on pourrait faire ce calcul ainsi :

ArrayList<Connection> connections = …;
Connection c0 = connections.get(0);
Duration firstConnectionDuration =
  Duration.between(c0.arrTime(), c0.depTime());

2.2. Frontière de Pareto

Nous avons vu à l'étape précédente que la recherche de voyages optimaux se fait en considérant trois critères : l'heure de départ, l'heure d'arrivée et le nombre de changements. Dans certains cas, qui seront décrits ultérieurement, seuls l'heure d'arrivée et le nombre de changements sont pris en compte.

Pour simplifier la discussion qui suit, nous ferons l'hypothèse que nous sommes justement dans une situation dans laquelle l'heure de départ n'est pas prise en compte. Notre but est donc uniquement d'optimiser l'heure d'arrivée \(a\) et le nombre de changements \(c\), que l'on désire tous deux minimiser afin d'arriver à destination aussi tôt, et en effectuant aussi peu de changements, que possible. Admettons maintenant que l'on ait les six possibilités suivantes pour se rendre à notre destination :

arriver à 8h00 en faisant 3 changements,
arriver à 8h00 en faisant 4 changements,
arriver à 8h01 en faisant 2 changements,
arriver à 8h02 en faisant 1 changement,
arriver à 8h03 en ne faisant aucun changement,
arriver à 8h04 en faisant 1 changement.

Ces possibilités correspondent à l'ensemble de 6 paires \((a, c)\) suivant :

\[\{(\textrm{8h00}, 3), (\textrm{8h00}, 4), (\textrm{8h01}, 2), (\textrm{8h02}, 1), (\textrm{8h03}, 0), (\textrm{8h04}, 1) \} \]

En examinant cet ensemble, on constate que certaines paires sont dominées par d'autres. Par exemple, la paire \((\textrm{8h00}, 4)\) est dominée par la paire \((\textrm{8h00}, 3)\). De même, la paire \((\textrm{8h04}, 1)\) est dominée par les paires \((\textrm{8h03}, 0)\) et \((\textrm{8h02}, 1)\). Ces paires dominées correspondent à des possibilités sans aucun intérêt pour le voyageur. Par exemple, la possibilité \((\textrm{8h00}, 4)\) n'a aucun intérêt car la possibilité \((\textrm{8h00}, 3)\), qui la domine, permet d'arriver à la même heure avec un changement de moins.

Sachant que les paires dominées ne sont pas intéressantes pour le voyageur, il semble raisonnable de ne conserver que celles qui ne le sont pas, et qui forment ce que l'on nomme la frontière de Pareto (Pareto front ou Pareto frontier).

La frontière de Pareto peut être visualisée sur un graphe dont l'axe horizontal représente l'heure d'arrivée et le vertical le nombre de changements, et sur lequel les différentes possibilités apparaissent comme des points. C'est ce qui a été fait à la figure 3 ci-dessous, sur laquelle la zone dominée par chacun des points — un rectangle infini² dont le point constitue le coin bas-gauche — a été coloriée en rouge partiellement transparent. On constate ainsi aisément que le point 2 se trouve dans la zone dominée par le point 1, et que le point 6 se trouve dans les zones dominées par les points 4 et 5. Il est dès lors facile de déterminer que la frontière de Pareto est constituée des points 1, 3, 4 et 5.

pareto-front;16.png — Figure 3 : Frontière de Pareto

Bien entendu, un graphique similaire pourrait être fait pour le cas où les critères d'optimisation incluent l'heure de départ. Il faudrait pour cela utiliser une troisième dimension, et les zones dominées seraient des cubes infinis.

2.3. Représentation des frontières immuables

L'algorithme de recherche de voyages optimaux que nous utiliserons calcule, étant donné un arrêt d'arrivée et une date de voyage, la frontière de Pareto de tous les voyages permettant d'atteindre cet arrêt ce jour-là, et ce pour chaque « gare » (au sens large) du réseau, ainsi que pour chaque course.

Sachant que les données que nous utiliserons comportent plus de 30 000 « gares » et 200 000 courses par jour, il importe de représenter les frontières de Pareto de manière efficace. Nous utiliserons donc une représentation optimisée, basée bien entendu sur les critères empaquetés de l'étape précédente.

Comme un tuple (paire ou triplet) de critères (augmenté) est représenté par une valeur de type long, et qu'une frontière de Pareto est un ensemble de critères, il semble logique d'utiliser un tableau de type long[] pour représenter une telle frontière. Une fois cette décision prise, la question qui se pose est de savoir si l'ordre dans lequel les critères apparaissent dans le tableau est important ou non.

A priori, étant donné que les éléments d'un ensemble ne sont pas ordonnés en mathématiques, on pourrait penser que l'ordre dans lequel les tuples sont stockés dans le tableau importe peu. Et cela est effectivement le cas lorsque les frontières de Pareto que l'on désire représenter sont immuables. Toutefois, pour représenter des frontières de Pareto non immuables — des bâtisseurs de frontières, en réalité — il peut être intéressant d'ordonner les tuples de manière à obtenir des performances aussi bonnes que possible.

2.4. Représentation des frontières non immuables

L'algorithme de recherche utilisé par ReCHor construit petit à petit les frontières de Pareto correspondant aux voyages optimaux, et ce pour chaque gare et chaque course.

En d'autres termes, il commence avec des frontières de Pareto vides associées à chaque gare et course, puis leur ajoute progressivement des tuples correspondant à des voyages nouvellement découverts. Chaque fois qu'un nouveau tuple est ajouté à une frontière, deux cas peuvent se présenter :

le nouveau tuple est dominé par au moins un tuple de la frontière, auquel cas le nouveau tuple n'appartient pas à la frontière, qui ne change donc pas,
le nouveau tuple n'est dominé par aucun tuple de la frontière, auquel cas il lui est ajouté, tandis que les éventuels tuples dominés par le nouveau en sont retirés.

Pour illustrer ce processus, voyons comment une frontière de Pareto initialement vide évolue si on lui ajoute les tuples plus haut, dans l'ordre 1, 2, 6, 3, 4, 5 :

initialement, la frontière est vide : \(\{\}\),
on lui ajoute le tuple 1, \((\textrm{8h00}, 3)\), qui n'est dominé par aucun de la frontière (vide), et qui n'en domine aucun autre, donc la frontière ne contient maintenant que lui : \(\{(\textrm{8h00}, 3)\}\),
on lui ajoute le tuple 2, \((\textrm{8h00}, 4)\), qui est dominé par le seul tuple de la frontière, donc elle ne change pas : \(\{(\textrm{8h00}, 3)\}\),
on lui ajoute le tuple 6, \((\textrm{8h04}, 1)\), qui n'est dominé par aucun de la frontière, et qui n'en domine aucun autre, donc la frontière devient : \(\{(\textrm{8h00}, 3), (\textrm{8h04}, 1)\}\),
on lui ajoute le tuple 3, \((\textrm{8h01}, 2)\), qui n'est dominé par aucun de la frontière, et qui n'en domine aucun autre, donc la frontière devient : \(\{(\textrm{8h00}, 3), (\textrm{8h01}, 2), (\textrm{8h04}, 1)\}\),
on lui ajoute le tuple 4, \((\textrm{8h02}, 1)\), qui n'est dominé par aucun de la frontière, mais qui domine le tuple \((\textrm{8h04}, 1)\), qui doit donc être supprimé de la frontière, qui devient : \(\{(\textrm{8h00}, 3), (\textrm{8h01}, 2), (\textrm{8h02}, 1)\}\),
on lui ajoute le tuple 5, \((\textrm{8h03}, 0)\), qui n'est dominé par aucun de la frontière, et qui n'en domine aucun autre, donc la frontière devient : \(\{(\textrm{8h00}, 3), (\textrm{8h01}, 2), (\textrm{8h02}, 1), (\textrm{8h03}, 0)\}\).

Dans cet exemple, les éléments de la frontière ont toujours été placés dans l'ordre lexicographique (lexical order), c.-à-d. triés d'abord par heure d'arrivée (croissante) puis par nombre de changements (croissant). Le fait de toujours ordonner les tuples de la frontière ainsi est intéressant car cela permet d'ajouter un nouvel élément de manière relativement efficace.

En effet, lorsqu'on désire ajouter un nouveau tuple à une frontière dont les tuples sont ordonnés en ordre lexicographique, on sait que tous les tuples qui pourraient dominer le nouveau se trouvent forcément avant la position à laquelle le nouveau devrait être inséré.

On peut s'en convaincre en regardant la figure 4 ci-dessous, qui montre la totalité des points entre \((\textrm{8h00}, 0)\) et \((\textrm{8h05}, 4)\). L'ordre de parcours lexicographique est indiqué par les flèches traitillées. De plus, le point correspondant à \((\textrm{8h02}, 2)\) est colorié en noir, tous ceux qui le précèdent dans l'ordre lexicographique en rouge, et tous ceux qui le suivent en bleu.

pareto-front-lexical;32.png — Figure 4 : Parcours des points dans l'ordre lexicographique

En regardant cette figure, il devrait être clair que les seuls points qui peuvent dominer le noir sont les rouges, c.-à-d. ceux qui le précèdent dans l'ordre lexicographique. A l'inverse, les seuls points que le noir peut dominer sont les bleus, c.-à-d. ceux qui le suivent dans l'ordre lexicographique.

Pour résumer, en stockant les tuples composant une frontière de Pareto dans l'ordre lexicographique, on peut ajouter un nouveau tuple de manière assez efficace en procédant ainsi :

on parcourt tous les tuples de la frontière se trouvant avant celui à insérer dans l'ordre lexicographique,
si, lors de ce parcours, un tuple dominant ou égal au nouveau est trouvé, on termine immédiatement l'ajout, car le nouveau tuple n'appartient pas à la frontière,
une fois tous les tuples précédents parcourus, on parcourt tous ceux qui suivent le nouveau, et on élimine de la frontière tous ceux qui sont dominés par lui.

Dès lors, dans ce projet, nous ordonnerons toujours les tuples des (bâtisseurs de) frontières de Pareto en ordre lexicographique. Il faut noter que le format d'empaquetage que nous avons choisi rend cela extrêmement simple, car un tuple \(t_1\) se trouve avant un autre tuple \(t_2\) dans l'ordre lexicographique si et seulement si la version empaquetée de \(t_1\), interprétée comme un entier, est plus petite que la version empaquetée de \(t_2\).

3. Mise en œuvre Java

La mise en œuvre de cette étape est composée de deux parties : l'écriture d'interfaces représentant les différentes composantes d'un horaire ainsi que l'horaire lui-même ; et l'écriture d'une classe immuable représentant un front de Pareto et d'un bâtisseur pour cette classe.

L'écriture des interfaces est triviale, puisqu'elles ne contiennent presque aucun code. Il est toutefois important de bien comprendre la signification et l'utilité des différentes méthodes qu'elles offrent, car cela sera important pour la suite.

L'écriture de la classe représentant le front de Pareto, et surtout de son bâtisseur, sont considérablement plus complexes et demandent beaucoup d'attention.

3.1. Interface `Indexed`

L'interface Indexed, du sous-paquetage timetable, est destinée à être étendue par toutes les interfaces représentant des données indexées. Par « données indexées » on entend toutes les données de l'horaire qui, conceptuellement en tout cas, sont stockées dans un tableau et identifiées par un index allant de 0 (inclus) à la taille du tableau (exclue).

Indexed ne possède qu'une seule méthode (publique et abstraite) :

int size(): qui retourne la taille — c.-à-d. le nombre d'éléments — des données.

3.2. Interface `Stations`

L'interface Stations du sous-paquetage timetable, publique et étendant Indexed, représente des gares indexées. Elle possède les méthodes abstraites suivantes :

String name(int id): qui retourne le nom de la gare d'index donné,
double longitude(int id): qui retourne la longitude, en degrés, de la gare d'index donné,
double latitude(int id): qui retourne la latitude, en degrés, de la gare d'index donné.

Toutes ces méthodes lèvent une IndexOutOfBoundsException si l'index qu'on leur passe (nommé id ci-dessous) est invalide, c.-à-d. inférieur à 0 ou supérieur ou égal à la taille retournée par size().

3.3. Interface `StationAliases`

L'interface StationAliases du sous-paquetage timetable, publique et étendant Indexed, représente les noms alternatifs des gares. Elle possède les méthodes abstraites suivantes :

String alias(int id): qui retourne le nom alternatif d'index donné (p. ex. Losanna),
String stationName(int id): qui retourne le nom de la gare à laquelle correspond le nom alternatif d'index donné (p. ex. Lausanne).

3.4. Interface `Platforms`

L'interface Platforms du sous-paquetage timetable, publique et étendant Indexed, représente des voies/quais indexés. Elle possède les méthodes abstraites suivantes :

String name(int id): qui retourne le nom de la voie (p. ex. 70) ou du quai (p. ex. A), qui peut être vide,
int stationId(int id): qui retourne l'index de la gare à laquelle cette voie ou ce quai appartient.

3.5. Interface `Routes`

L'interface Routes du sous-paquetage timetable, publique et étendant Indexed, représente des lignes de transport public indexées. Elle possède les méthodes abstraites suivantes :

Vehicle vehicle(int id): qui retourne le type de véhicule desservant la ligne d'index donné,
String name(int id): qui retourne le nom de la ligne d'index donné (p. ex. IR 15).

3.6. Interface `Transfers`

L'interface Transfers du sous-paquetage timetable, publique et étendant Indexed, représente des changements indexés. Il faut noter que, dans les données que nous utiliserons, des changements ne sont possibles qu'entre (ou au sein de) gares, et pas entre des voies ou quais.

Transfers possède les méthodes abstraites suivantes :

int depStationId(int id): qui retourne l'index de la gare de départ du changement d'index donné,
int minutes(int id): qui retourne la durée, en minutes, du changement d'index donné,
int arrivingAt(int stationId): qui retourne l'intervalle empaqueté — selon la convention utilisée par PackedRange — des index des changements dont la gare d'arrivée est celle d'index donné,
int minutesBetween(int depStationId, int arrStationId): qui retourne la durée, en minutes, du changement entre les deux gares d'index donnés, ou lève NoSuchElementException si aucun changement n'est possible entre ces deux gares.

Toutes ces méthodes lèvent une IndexOutOfBoundsException si l'un des index qu'on leur passe est invalide.

3.7. Interface `Trips`

L'interface Trips du sous-paquetage timetable, publique et étendant Indexed, représente des courses de transport public indexées. Elle possède les méthodes abstraites suivantes :

int routeId(int id): qui retourne l'index de la ligne à laquelle la course d'index donné appartient,
String destination(int id): qui retourne le nom de la destination finale de la course.

3.8. Interface `Connections`

L'interface Connections du sous-paquetage timetable, publique et étendant Indexed, représente des liaisons indexées. Pour les besoins de l'algorithme de recherche de voyages, les liaisons doivent être ordonnées par heure de départ décroissante.

Connections possède les méthodes abstraites suivantes :

int depStopId(int id): qui retourne l'index de l'arrêt de départ de la liaison d'index donné,
int depMins(int id): qui retourne l'heure de départ de la liaison d'index donné, exprimée en minutes après minuit,
int arrStopId(int id): qui retourne l'index de l'arrêt d'arrivée de la liaison d'index donné,
int arrMins(int id): qui retourne l'heure d'arrivée de la liaison d'index donné, exprimée en minutes après minuit,
int tripId(int id): qui retourne l'index de la course à laquelle appartient la liaison d'index donné,
int tripPos(int id): qui retourne la position de la liaison d'index donné dans la course à laquelle elle appartient, la première liaison d'une course ayant l'index 0,
int nextConnectionId(int id): qui retourne l'index de la liaison suivant celle d'index donné dans la course à laquelle elle appartient, ou l'index de la première liaison de la course si la liaison d'index donné est la dernière de la course.

Les index des arrêts de départ et d'arrivée retournés par depStopId et arrStopId peuvent soit désigner des gares, soit des voies ou quais. Si un tel index est inférieur au nombre de gares existant dans l'horaire, alors il représente un index de gare. Sinon, il représente un index de voie ou de quai, qui peut être calculé en soustrayant de l'index d'arrêt le nombre de gares existant dans l'horaire.

Par exemple, s'il y a 1000 gares et 2000 voies ou quais, l'index d'arrêt 500 représente la gare d'index 500, tandis que l'index d'arrêt 1700 représente l'index de la voie/quai 700.

3.9. Interface `TimeTable`

L'interface TimeTable du sous-paquetage timetable, publique, représente un horaire de transport public. Elle possède les méthodes abstraites suivantes :

Stations stations(): qui retourne les gares indexées de l'horaire,
StationAliases stationAliases(): qui retourne les noms alternatifs indexés des gares de l'horaire,
Platforms platforms(): qui retourne les voies/quais indexées de l'horaire,
Routes routes(): qui retourne les lignes indexées de l'horaire,
Transfers transfers(): qui retourne les changements indexés de l'horaire,
Trips tripsFor(LocalDate date): qui retourne les courses indexées de l'horaire actives le jour donné,
Connections connectionsFor(LocalDate date): qui retourne les liaisons indexées de l'horaire actives le jour donné.

En plus de ces méthodes abstraites, TimeTable possède également les méthodes par défaut suivantes :

default boolean isStationId(int stopId): qui retourne vrai si et seulement si l'index d'arrêt donné est un index de gare (et pas un index de voie ou de quai),
default boolean isPlatformId(int stopId): qui retourne vrai si et seulement si l'index d'arrêt donné est un index de voie ou de quai (et pas un index de gare),
default int stationId(int stopId): qui retourne l'index de la gare de l'arrêt d'index donné (qui peut être identique si l'arrêt en question est une gare),
default String platformName(int stopId): qui retourne le nom de voie ou de quai de l'arrêt d'index donné, ou null si cet arrêt est une gare.

3.10. Classe `ParetoFront`

La classe ParetoFront du sous-paquetage journey, publique et immuable, représente une frontière de Pareto de critères d'optimisation. Les tuples de la frontière sont stockés sous forme empaquetée, dans un tableau de type long[] privé.

ParetoFront possède l'attribut public, statique et final suivant :

ParetoFront EMPTY: qui contient une frontière de Pareto vide.

ParetoFront ne possède pas de constructeur public, car ses instances ne sont destinées à être construites que par le bâtisseur décrit à la section suivante. Elle possède toutefois un constructeur privé qui prend en argument un tableau de type long[] contenant les critères empaquetés, qu'elle stocke sans le copier. Pour garantir l'immuabilité de la classe, il est donc fondamental que ce tableau ne change pas après l'appel du constructeur. En particulier, la méthode build du bâtisseur décrit plus bas doit garantir cela, en passant au constructeur une copie de son tableau interne.

En plus de ce constructeur privé, ParetoFront offre les méthodes publiques suivantes :

int size(): qui retourne la taille de la frontière de Pareto, c.-à-d. le nombre de tuples (paires ou triplets de critères d'optimisation) qu'elle contient,
long get(int arrMins, int changes): qui retourne les critères d'optimisation empaquetés dont l'heure d'arrivée et le nombre de changements sont ceux donnés, ou lève une NoSuchElementException si ces critères ne font pas partie de la frontière,
void forEach(LongConsumer action): qui appelle la méthode accept de l'action de type LongConsumer donnée avec chacun des critères de la frontière, dans l'ordre.

En plus de ces méthodes, il est très fortement conseillé d'ajouter à ParetoFront une redéfinition de la méthode toString qui produit une représentation textuelle de la frontière de Pareto, afin de faciliter le débogage. Le format de cette représentation textuelle n'est pas spécifié, mais il est conseillé de présenter les critères de la frontière de manière aussi lisible que possible, en montrant pour chacun d'eux l'heure de départ (si elle est présente), l'heure d'arrivée et le nombre de changements.

3.10.1. Conseils de programmation

La méthode forEach permet de parcourir les éléments de la frontière et d'effectuer une action pour chacun d'eux. Par exemple, si on désirait afficher les critères à l'écran, un par ligne, on pourrait procéder ainsi :

class MyPrinter implements LongConsumer {
  @Override
  void accept(long value) {
    System.out.println(value);
  }
}

ParetoFront paretoFront = …;
paretoFront.forEach(new MyPrinter());

Toutefois, cette manière de faire est très lourde, et en réalité la méthode forEach est destinée à être utilisée avec une lambda. Ce concept n'a malheureusement pas encore été vu au cours, mais il faut savoir qu'en l'utilisant, le code ci-dessus peut s'écrire simplement ainsi :

ParetoFront paretoFront = …;
paretoFront.forEach(value -> { System.out.println(value); });

Dès lors, si vous voulez utiliser la méthode forEach dans votre code, vous pouvez vous inspirer de cet exemple pour écrire le code de manière plus concise, en attendant que les lambdas soient décrites en détail au cours.

3.11. Classe `ParetoFront.Builder`

La classe Builder imbriquée statiquement dans ParetoFront, publique, représente un bâtisseur de frontière de Pareto. La frontière en cours de construction est stockée dans un tableau de type long[] qui contient les tuples et est « redimensionné » au besoin selon la technique décrite dans les conseils de programmation plus bas.

Builder offre deux constructeurs publics :

Builder(): qui retourne un bâtisseur dont la frontière en cours de construction est vide,
Builder(Builder that): qui retourne un nouveau bâtisseur avec les mêmes attributs que celui reçu en argument (constructeur de copie).

En plus de ces constructeurs, Builder offre les méthodes publiques ci-dessous, toutes celles modifiant la frontière retournent le bâtisseur lui-même afin de permettre le chaînage des appels :

boolean isEmpty(): qui retourne vrai si et seulement si la frontière en cours de construction est vide,
Builder clear(): qui vide la frontière en cours de construction en supprimant tous ses éléments,
Builder add(long packedTuple): qui ajoute à la frontière le tuple de critères empaquetés donné ; cet ajout n'est fait que si le nouveau tuple n'est pas dominé ou égal à un de la frontière, et tous les éventuels tuples existants et dominés par le nouveau en sont supprimés,
Builder add(int arrMins, int changes, int payload): qui ajoute à la frontière un tuple de critères augmentés ayant l'heure d'arrivée, le nombre de changements et la charge utile donnés, mais pas d'heure de départ ; l'ajout est fait de la même manière que dans la méthode précédente,
Builder addAll(Builder that): qui ajoute à la frontière tous les tuples présents dans la frontière en cours de construction par le bâtisseur donné,
boolean fullyDominates(Builder that, int depMins): qui retourne vrai si et seulement si chacun des tuples de la frontière donnée, une fois son heure de départ fixée sur celle donnée, est dominé par, ou égal à, au moins un tuple du récepteur (le récepteur étant l'objet auquel on applique la méthode),
void forEach(LongConsumer action): qui fait la même chose que la méthode forEach de ParetoFront,
ParetoFront build(): qui retourne la frontière de Pareto en cours de construction par ce bâtisseur.

Tout comme pour ParetoFront, il est très fortement conseillé d'ajouter à Builder une redéfinition de la méthode toString afin de faciliter le débogage. La plupart du code peut être partagée entre les deux méthodes toString.

3.11.1. Conseils de programmation

Pour que cette classe soit efficace, elle doit impérativement stocker les critères (tuples) sous forme empaquetée, dans un tableau de type long[], triés par ordre lexicographique. Toutefois, cela n'est pas très simple à mettre en œuvre, pour les raisons décrites ci-après, et vous pouvez donc, si vous le désirez, utiliser temporairement une autre solution de stockage, comme un tableau dynamique de type ArrayList<Long>. Sachez néanmoins que pour obtenir la totalité des points au rendu intermédiaire (semaine 7), vous devrez impérativement utiliser un tableau de type long[] géré comme décrit ci-après.

Il y a deux raisons principales pour lesquelles l'utilisation d'un tableau de type long[] pour stocker les critères est difficile : premièrement, un tel tableau ne peut pas être redimensionné ; et deuxièmement, il n'est pas facile d'insérer ou de supprimer des éléments au milieu d'un tel tableau. Or ces deux opérations — redimensionnement et insertion ou suppression au milieu — sont nécessaires à la mise en œuvre de la méthode add.

Pour stocker les critères dans un tableau de type long[], l'idée est d'en utiliser un ayant une taille — nommée sa capacité (capacity) — supérieure ou égale au nombre de tuples qu'il contient effectivement. Par exemple, sa capacité initiale, lorsque la frontière en cours de construction est vide, pourrait être fixée à 2. Un second attribut, de type int, doit donc être ajouté au bâtisseur pour connaître la taille effective de la frontière. Les tuples sont toujours stockés dans les premiers éléments du tableau, en ordre lexicographique.

Lors de l'ajout d'un tuple, le tableau est parcouru à partir du début, à la recherche du premier élément supérieur (dans l'ordre lexicographique) à celui à insérer. Comme nous l'avons vu, l'ordre lexicographique sur les tuples est équivalent à l'ordre mathématique standard sur les entiers contenant les tuples empaquetés. Autrement dit, utiliser par exemple l'opérateur < pour comparer deux entiers long représentant des tuples empaquetés permet de déterminer si le premier tuple se trouve avant le second dans l'ordre lexicographique.

Cela fonctionne car nous avons pris soin d'empaqueter les critères de manière à ce qu'ils soient toujours positifs, et de stocker le complément de l'heure de départ plutôt que l'heure de départ elle-même. Il faut toutefois prendre garde au fait que la charge utile, présente dans les 32 bits de poids faible des tuples empaquetés, détermine le résultat de la comparaison lorsque deux tuples ont exactement les mêmes critères. Une manière simple de tenir compte de cela est de remplacer temporairement la charge utile du tuple à insérer, soit par la plus petite valeur possible (0), soit par la plus grande, en fonction de l'effet désiré.

Durant le parcours des tuples de la frontière à la recherche de la position d'insertion du nouveau, si un tuple dominant ou égal à celui à insérer est trouvé, l'ajout se termine sans modifier la frontière en cours de construction. Sinon, une fois que la position d'insertion du nouvel élément a été trouvée, les éléments qui se trouvent après cette position et qui sont dominés par le nouveau doivent être éliminés avant que le nouveau puisse être inséré.

L'élimination des éléments dominés par le nouveau peut se faire en parcourant ceux qui suivent la position d'insertion et en les « compactant », c.-à-d. en copiant ceux qui ne sont pas dominés vers le bas, afin qu'ils se trouvent juste après la position d'insertion.

Le code pour faire cela n'étant pas totalement trivial à écrire, vous pouvez vous inspirer de la méthode suivante, qui « compacte » un tableau d'entiers qu'on lui passe en ne gardant que les éléments supérieurs ou égaux à 10, qui sont placés dans les premiers éléments du tableau. Le nombre d'éléments conservés est retourné en résultat de la méthode.

int compact(int[] array) {
  int dst = 0;
  for (int src = 0; src < array.length; src += 1) {
    if (array[src] < 10) continue;
    if (dst != src) array[dst] = array[src];
    dst += 1;
  }
  return dst;
}

Par exemple, si on applique cette méthode au tableau suivant :

int[] array = {1, 5, 10, 11, 3, 1, 20, 30, 2};

elle retourne le nombre d'éléments du tableau supérieurs ou égaux à 10 — donc 4 — et déplace ces éléments, dans le même ordre, dans les 4 premiers éléments du tableau.

Une fois le tableau des tuples ainsi « compacté », deux cas peuvent se présenter : soit sa capacité est suffisante pour insérer le nouveau tuple, soit elle ne l'est pas.

Si la capacité est suffisante, les éléments d'index supérieur ou égal à la position d'insertion doivent être décalés d'une position vers le haut, afin de laisser une place pour le nouvel élément. Ce décalage peut se faire au moyen de la méthode arraycopy.

Si la capacité est insuffisante, alors un nouveau tableau de taille supérieure — p. ex. 1.5 fois plus grand — à l'actuel doit être créé. Tous les tuples de l'ancien tableau doivent y être copiés, ainsi que le nouveau, en préservant l'ordre lexicographique. Là aussi, la copie peut se faire au moyen de la méthode arraycopy.

Avant de vous lancer dans la programmation de la méthode add, soyez sûrs de bien comprendre ce qui précède, et faites des dessins pour avoir une idée claire des opérations à effectuer.

3.12. Tests

Comme pour l'étape précédente, nous ne vous fournissons plus de tests mais un fichier de vérification de signatures à importer dans votre projet.

4. Résumé

Pour cette étape, vous devez :

écrire les interfaces Indexed, Stations, StationAliases, Platforms, Routes, Transfers, Trips, Connections et TimeTable, ainsi que les classes ParetoFront et ParetoFront.Builder selon les indications données plus haut,
tester votre code,
documenter la totalité des entités publiques que vous avez définies,
rendre votre code au plus tard le 7 mars 2025 à 18h00, au moyen du programme Submit.java fourni et des jetons disponibles sur votre page privée.

Ce rendu est un rendu testé, auquel 20 points sont attribués, au prorata des tests unitaires passés avec succès.

N'attendez surtout pas le dernier moment pour effectuer votre rendu, car vous n'êtes pas à l'abri d'imprévus.

Si vous manquez la date limite de rendu, vous avez encore la possibilité de faire un rendu tardif au moyen des jetons prévus à cet effet, et ce durant les 2 heures qui suivent, mais il vous en coûtera une pénalité inconditionnelle de 2 points.

Notes de bas de page

Cette affirmation peut sembler étrange au vu de l'existence de l'enregistrement Stop écrit à l'étape 1. Il faut toutefois comprendre que cet enregistrement n'est destiné qu'à être utilisé pour représenter les arrêts qui font partie d'un voyage, et pas la totalité des arrêts de l'horaire, dont il est question ici.

En réalité, comme l'heure d'arrivée et le nombre de changements sont tous les deux bornés, les rectangles de domination ne sont pas infinis, mais c'est un détail.