Horaire aplati (II)
ReCHor – étape 5
1. Introduction
Le but de cette étape est de continuer la rédaction les classes permettant de manipuler l'horaire aplati, en écrivant celles gérant les lignes, les courses, les liaisons et les changements.
2. Concepts
Cette étape est très similaire à la précédente, et seule la manière dont les différents types de données aplaties sont représentés doit être décrite, ce qui est fait dans les section suivantes.
2.1. Lignes
Pour mémoire, une ligne est un itinéraire le long duquel des véhicules de transport public se déplacent régulièrement. Un exemple est la ligne de métro m1 reliant la gare de Renens à celle du Flon.
Les deux seules caractéristiques des lignes qui nous intéressent pour ce projet sont leur nom et le type de véhicule qui les dessert. La structure des lignes aplaties est donc particulièrement simple :
I |
Champ | Type | Contenu |
|---|---|---|---|
| 0 | NAME_ID |
U16 |
Index de chaîne du nom de la ligne |
| 1 | KIND |
U8 |
Type de véhicule desservant la ligne |
Le type du véhicule est représenté comme un entier compris entre 0 (inclus) et 6 (inclus) qui correspond directement au type énuméré Vehicle défini à l'étape 1 — 0 correspond à TRAM, 1 à METRO, etc.
2.2. Courses
Pour mémoire, une course est un trajet effectué par un véhicule de transport public entre les deux extrémités d'une ligne, dans l'un des deux sens possibles.
Les deux seules caractéristiques des courses qui nous intéressent pour ce projet sont leur ligne et le nom de leur destination finale. La structure des courses aplaties est donc également simple :
I |
Champ | Type | Contenu |
|---|---|---|---|
| 0 | ROUTE_ID |
U16 |
Index de la ligne de la course |
| 1 | DESTINATION_ID |
U16 |
Index de chaîne de la destination finale |
ROUTE_ID est un index de ligne, donc il fait référence à un élément de la table des lignes dont la structure a été décrite à la section précédente. Sachant que dans les données horaires que nous utiliserons il y a un peu moins de 8 000 lignes, le type U16 convient bien pour représenter un tel index.
2.3. Liaisons
Pour mémoire, une liaison est un trajet effectué par un véhicule de transport public, dans le cadre d'une course, entre deux arrêts successifs — donc sans arrêt intermédiaire. Dans les données aplaties, les liaisons ont la structure suivante :
I |
Champ | Type | Contenu |
|---|---|---|---|
| 0 | DEP_STOP_ID |
U16 |
Index de l'arrêt de départ |
| 1 | DEP_MINUTES |
U16 |
Heure de départ, en minutes après minuit |
| 2 | ARR_STOP_ID |
U16 |
Index de l'arrêt d'arrivée |
| 3 | ARR_MINUTES |
U16 |
Heure d'arrivée, en minutes après minuit |
| 4 | TRIP_POS_ID |
S32 |
Index de la course et position en son sein |
Les champs DEP_STOP_ID et ARR_STOP_ID sont des index d'arrêts, qui pour mémoire peuvent soit référencer une gare, soit une voie/quai. Les données horaires que nous utiliserons comportant un peu plus de 54 000 arrêts au total — environ 33 000 gares et 21 000 voies/quai — le type U16 convient bien pour les indexer.
Les champs DEP_MINUTES et ARR_MINUTES contiennent les heures de départ et d'arrivée de la liaison, exprimées en minutes après minuit. Ces minutes sont forcément positives ou nulles dans les données horaires, donc le type U16 convient bien pour les représenter. Comme nous le verrons plus tard, le fait que des heures négatives puissent apparaître, et doivent donc être stockées dans les critères d'optimisation, est dû aux trajets à pied (changements).
Le champ TRIP_POS_ID contient une valeur empaquetée dont les 24 bits de poids fort sont l'index dans la table des courses de celle à laquelle la liaison appartient, et les 8 bits de poids faible sont la position de la liaison dans la course en question, à partir de 0. Sachant qu'il y a un peu moins de 3 millions de courses par jour, et que la plus longue course de Suisse comporte 78 liaisons, l'empaquetage utilisé convient tout à fait.
La table des liaisons aplaties est ordonnée, dans le sens où les liaisons y apparaissent ordonnées par heure de départ décroissante. Donc la première liaison, d'index 0, est celle partant le plus tard de toutes. Cet ordre est utilisé par l'algorithme de calcul de voyages optimaux, comme nous le verrons.
2.4. Liaison suivante
En examinant la structure des liaisons aplaties présentée à la section précédente, on constate qu'une information qu'il n'est pas évident d'en extraire est la liaison qui suit une liaison donnée dans une course. Or l'interface Connections possède justement une méthode permettant d'obtenir la liaison suivant une liaison donnée.
En théorie, cette information pourrait être déterminée à partir des liaisons aplaties, puisque chacune d'entre elles contient l'index de la course à laquelle elle appartient, ainsi que sa propre position dans cette course. Dès lors, pour déterminer la liaison suivant une liaison donnée, on pourrait chercher, parmi toutes les liaisons, celle ayant le même index de course mais la position suivante — qui existe pour toutes les liaisons sauf la dernière d'une course.
Bien que cela soit possible, procéder à une telle recherche serait coûteux sachant qu'il y a, pour un jour donné, entre 2 et 3 millions de liaisons. Il semble dès lors plus judicieux de pré-calculer, pour chaque liaison, l'index de celle qui la suit dans la course, et de stocker cette information dans les données aplaties.
C'est donc ce que nous ferons dans ce projet, mais plutôt que de stocker cette information directement dans la table des liaisons, nous utiliserons une table auxiliaire, ne contenant rien d'autre que cette information. Ce choix a été fait afin que la table des liaisons — décrite à la section précédente — ne contienne que les informations nécessaires à l'algorithme de calcul des voyages optimaux, et la liaison suivant une autre n'en fait pas partie. Cette séparation en deux tables permet à celle des liaisons d'être aussi petite que possible, ce qui accélère la recherche de voyages optimaux.
La structure de la table auxiliaire contenant, pour chaque liaison, l'index de la suivante dans la course est donc extrêmement simple :
I |
Champ | Type | Contenu |
|---|---|---|---|
| 0 | NEXT_CONNECTION_ID |
S32 |
Index de la liaison suivante / première |
Il faut noter que, comme la dernière liaison d'une course n'a pas de liaison suivante, cette table associe la première liaison d'une course à la dernière. En d'autres termes, les liaisons sont liées entre elles de manière circulaire.
2.5. Changements
Pour mémoire, un changement est un trajet à pied qui peut être effectué soit entre deux gares voisines, soit au sein d'une même gare. Dans les données aplaties, les changements ont la structure suivante :
I |
Champ | Type | Contenu |
|---|---|---|---|
| 0 | DEP_STATION_ID |
U16 |
Index de la gare de départ |
| 1 | ARR_STATION_ID |
U16 |
Index de la gare d'arrivée |
| 2 | TRANSFER_MINUTES |
U8 |
Durée du changement, en minutes |
Les champs DEP_STATION_ID et ARR_STATION_ID sont des index de gares (et jamais de voie/quai), car dans les données horaires à notre disposition, seuls les changements entre gares — ou au sein d'une seule gare — existent.
Le plus long changement dans les données horaires à notre disposition fait 99 minutes — une valeur au demeurant suspecte, qui indique probablement un problème — donc le type U8 convient bien à la représentation de la durée du changement.
La table des changements aplatis est ordonnée de manière à ce que tous les changements arrivant à la même gare y soient consécutifs. Cette propriété permet de représenter l'ensemble des changements arrivant à une gare donnée au moyen de l'intervalle des index des changements qui y arrivent.
3. Mise en œuvre Java
Comme celles de l'étape précédente, les classes de cette étape font toutes partie du sous-paquetage timetable.mapped. La plupart d'entre elles sont simples à mettre en œuvre, sauf peut-être celle donnant accès aux changements aplatis.
3.1. Classe BufferedRoutes
La classe BufferedRoutes du sous-paquetage timetable.mapped, publique et finale, implémente l'interface Routes et permet d'accéder à une table de lignes représentée de manière aplatie comme décrit à la §2.1. Elle possède un unique constructeur public :
BufferedRoutes(List<String> stringTable, ByteBuffer buffer)- qui construit une instance donnant accès aux données aplaties disponibles dans le tableau
buffer, en utilisant la table de chaînesstringTablepour déterminer la valeur des chaînes référencées par ces données.
Les seules méthodes publiques offertes par cette classe sont les versions concrètes des méthodes abstraites de Routes.
3.2. Classe BufferedTrips
La classe BufferedTrips du sous-paquetage timetable.mapped, publique et finale, implémente l'interface Trips et permet d'accéder à une table de courses représentée de manière aplatie comme décrit à la §2.2. Elle possède un unique constructeur public :
BufferedTrips(List<String> stringTable, ByteBuffer buffer)- qui construit une instance donnant accès aux données aplaties disponibles dans le tableau
buffer, en utilisant la table de chaînesstringTablepour déterminer la valeur des chaînes référencées par ces données.
Les seules méthodes publiques offertes par cette classe sont les versions concrètes des méthodes abstraites de Trips.
3.3. Classe BufferedConnections
La classe BufferedConnections du sous-paquetage timetable.mapped, publique et finale, implémente l'interface Connections et permet d'accéder à une table de liaisons représentée de manière aplatie comme décrit aux §2.3 et 2.4. Elle possède un unique constructeur public :
BufferedConnections(ByteBuffer buffer, ByteBuffer succBuffer)- qui construit une instance donnant accès aux données aplaties réparties entre le tableau
buffer, qui contient les liaisons aplaties (§2.3), et le tableausuccBuffer, qui contient les liaisons suivantes (§2.4).
Les seules méthodes publiques offertes par cette classe sont les versions concrètes des méthodes abstraites de Connections.
3.3.1. Conseils de programmation
Pour accéder aux données de la seconde table, qui contient uniquement les liaisons suivantes, il est bien entendu techniquement possible d'utiliser une instance de StructuredBuffer comme pour les autres tables. Toutefois, au vu de la structure extrêmement simple de cette table-ci, il est plus facile de transformer le tableau de type ByteBuffer passé au constructeur en un tableau de type IntBuffer, au moyen de la méthode asIntBuffer.
Au même titre que ByteBuffer est similaire à un tableau d'octets de type byte[], IntBuffer est similaire à un tableau d'entiers de type int[], et la méthode get permet d'obtenir un élément (de type int) d'index donné.
3.4. Classe BufferedTransfers
La classe BufferedTransfers du sous-paquetage timetable.mapped, publique et finale, implémente l'interface Transfers et permet d'accéder à une table de changements représentée de manière aplatie comme décrit à la §2.5. Elle possède un unique constructeur public :
BufferedTransfers(ByteBuffer buffer)- qui construit une instance donnant accès aux données aplaties disponibles dans le tableau
buffer.
Les seules méthodes publiques offertes par cette classe sont les versions concrètes des méthodes abstraites de Transfers.
3.4.1. Conseils de programmation
Pour mémoire, la méthode arrivingAt de l'interface Transfers retourne l'intervalle (empaqueté) des index de tous les changements arrivant à une gare donnée. Comme expliqué à la §2.5, la table des changements aplatis est organisée de manière à ce que tous les arrêts arrivant à une gare donnée soient consécutifs.
Malheureusement, à elle seule, cette propriété ne permet pas à arrivingAt de déterminer rapidement l'intervalle à retourner, car sans information supplémentaire, elle ne peut pas connaître l'intervalle correspondant à une gare d'arrivée et doit donc parcourir la totalité de la table à sa recherche.
Comme un tel parcours est cher et que la méthode arrivingAt — utilisée par l'algorithme de recherche des voyages optimaux — doit être efficace, une autre solution s'impose. Elle consiste à calculer, dans le constructeur de la classe, une table associant à toutes les gares l'intervalle des index des changements qui y arrivent.
Cette table est un simple tableau de type int[] contenant, à l'index i, l'intervalle empaqueté des index des changements arrivant à la gare d'index i. On peut la construire en parcourant deux fois la totalité des changements aplatis : la première fois pour déterminer la taille de la table, la seconde pour déterminer son contenu.
Grâce à cette table, la méthode arrivingAt est triviale à écrire puisqu'elle n'a rien d'autre à faire que retourner l'élément de la table dont l'index est celui de la gare, reçu en argument.
3.5. Tests
Comme d'habitude, 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 classes
BufferedRoutes,BufferedTrips,BufferedConnectionsetBufferedTransfersselon 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 21 mars 2025 à 18h00, au moyen du programme
Submit.javafourni 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.