Horaire aplati

ReCHor – étape 4

1. Introduction

Le but de cette étape est d'écrire des classes facilitant la lecture des données horaires aplaties, et de les utiliser pour écrire celles permettant de manipuler les gares et voies représentées de cette manière.

2. Concepts

2.1. Données aplaties

Comme nous l'avons vu à l'étape précédente, les données horaire utilisées dans ce projet sont représentées d'une manière un peu particulière, que nous avons appelée aplatie.

L'idée de cette représentation est que les différents types de données de l'horaire (gares, voies/quais, liaisons, etc.) sont stockés dans des tableaux, chaque tableau contenant toutes les valeurs d'un type donné, p. ex. toutes les gares. De plus, au lieu de contenir des références vers des objets contenant les attributs des différentes instances — comme d'habitude en Java — ces tableaux contiennent directement les attributs des différentes instances.

À l'étape 3, pour simplifier les choses, nous avions fait l'hypothèse que les données représentées de manière aplatie étaient homogènes, dans le sens où tous leurs attributs pouvaient être représentés au moyen d'entiers du même type. Ainsi, dans l'exemple de la §2.1.3 de cette étape, les liaisons étaient composée de 4 attributs, et chacun d'entre eux pouvait être représenté au moyen d'un entier de type short. La totalité des liaisons pouvait donc être stockée dans un unique tableau de type short[], de taille égale à 4 fois le nombre de liaisons.

En réalité, les données aplaties que nous utiliserons dans ce projet seront hétérogènes, dans le sens où elles seront constituées d'un certain nombre d'attributs ayant chacun un type potentiellement différent. Nous nommerons ces attributs des champs (fields), et ils pourront être chacun d'un des trois types entiers suivant :

U8
8 bits (1 octet) interprétés comme un entier non signé, compris donc entre 0 (inclus) et 256 (exclu),
U16
16 bits (2 octets) interprétés comme un entier non signé, compris donc entre 0 (inclus) et 65 536 (exclu),
S32
32 bits (4 octets) interprétés comme un entier signé, compris donc entre
–2 147 483 648 (inclus) et 2 147 483 648 (exclu).

Ces trois types correspondent presque aux types byte, short et int de Java, la seule différence étant que les deux premiers sont interprétés de manière non signée.

Les données hétérogènes sont stockées dans des tableaux d'octets (bytes), et un champ de type U8 occupe donc un seul élément d'un tel tableau, un champ de type U16 en occupe deux consécutifs, et un champ de type S32 en occupe quatre consécutifs.

Comme les trois types de champs sont tous des types entiers, il faut trouver une manière de représenter toutes les données de l'horaire au moyen d'entiers, entre autres les nombreuses chaînes de caractères qu'elles contiennent.

2.2. Table des chaînes de caractères

De nombreuses données de l'horaire contiennent des chaînes de caractères, p. ex. les gares ont un nom qui est une chaîne, et il en va de même pour les voies ou quais, les courses, etc.

Pour pouvoir représenter ces chaînes de caractères dans des données aplaties, une solution simple consiste à établir une table de toutes les chaînes présentes dans les données, puis d'identifier une chaîne par son index dans cette table.

Les données horaires que nous utiliserons contiennent un peu plus de 40 000 chaînes différentes, et un index dans cette table peut donc être représenté par une valeur de type U16. Dans ce qui suit, nous nommerons ces index des index de chaîne.

2.3. Gares

Les gares sont représentées de manière aplatie au moyen des trois champs donnés dans la table ci-dessous, la colonne I donnant l'index du champ (à partir de 0) :

I Champ Type Contenu
0 NAME_ID U16 Index de chaîne du nom de la gare
1 LON S32 Longitude de la gare
2 LAT S32 Latitude de la gare

La représentation aplatie d'une gare nécessite donc 10 octets (sans compter ceux nécessaires à la représentation des chaînes dans la table des chaînes), et le tableau d'octets contenant la totalité des gares a donc une taille égale à 10 fois le nombre de gares.

La longitude et la latitude d'une gare aplatie ne sont pas exprimées en degrés, mais dans une unité anonyme, équivalente à \(360°\div 2^{32}\). En d'autres termes, une longitude ou une latitude \(l\) exprimée dans cette unité anonyme peut être convertie en sa version en degrés \(l°\) au moyen de la formule suivante :

\[ l° = \frac{360}{2^{32}}\,l \]

L'intérêt de cette unité est qu'elle permet de représenter les longitudes et latitudes au moyen d'entiers de 32 bits, avec une précision de l'ordre du centimètre. En effet, sachant qu'à l'équateur la Terre a une circonférence d'environ 40 000 km, la précision est d'au moins :

\[ \frac{40\,000}{2^{32}}\,\textrm{km} \approx 0.93\,\textrm{cm} \]

ce qui suffit très largement à nos besoins.

2.4. Noms alternatifs des gares

Comme nous l'avons vu, certaines gares ont des noms alternatifs qui doivent pouvoir être utilisés dans la recherche d'arrêts, p. ex. Losanna pour Lausanne, Soleure pour Solothurn, Anet pour Ins, etc.

Ces noms alternatifs sont représentés comme des paires composées du nom alternatif et du nom original. La structure de cette table est donc très simple :

I Champ Type Contenu
0 ALIAS_ID U16 Index de chaîne du nom alternatif
1 STATION_NAME_ID U16 Index de chaîne du nom de la gare

La représentation aplatie d'un nom alternatif d'une gare nécessite donc 4 octets.

2.5. Voies ou quais

Les voies ou quai ont un nom (p. ex. 70, 1AB, A) et une référence vers la gare à laquelle ils appartiennent, que nous appellerons la gare parente (parent station).

I Champ Type Contenu
0 NAME_ID U16 Index de chaîne du nom de la voie ou du quai
1 STATION_ID U16 Index de la gare parente

La représentation aplatie d'une voie ou d'un quai nécessite donc 4 octets.

Il est important de comprendre que le premier champ (NAME_ID) contient un index dans la table des chaînes, mais le second (STATION_ID) contient un index dans la table des gares, et pas dans celle des chaînes !

2.6. Exemple

Pour illustrer la représentation aplatie des gares, de leurs noms alternatifs et des gares ou quais, admettons que la table des chaînes de caractères contienne les éléments suivants :

I Chaîne
0 1
1 70
2 Anet
3 Ins
4 Lausanne
5 Losanna
6 Palézieux

et voyons ensuite comment représenter des gares, noms alternatifs et voies/quai aplatis.

2.6.1. Gares

Le tableau d'octets suivant, où chaque octet est donné en hexadécimal sur deux chiffres :

00 04 04 b6 ca 14 21 14 1f a1 00 06 04 dc cc 12 21 18 da 03

représente la table des gares :

I Nom Longitude Latitude
0 Lausanne 6.629092 46.516792
1 Palézieux 6.837875 46.542764

En effet, les deux premiers octets (00 04) représentent l'entier U16 qui vaut 4, et qui est l'index de la chaîne Lausanne dans la table des chaînes. Les quatre octets suivants (04 b6 ca 14) représentent l'entier S32 qui vaut 4b6ca1416, soit 7908814810. En convertissant cette valeur en degrés au moyen de la formule de la §2.3, on obtient 6.629092 (en arrondissant à 6 décimales). En faisant de même avec l'entier S32 représenté par les 4 octets suivants (21 14 1f a1), on obtient 46.516792. Et ainsi de suite.

2.6.2. Noms alternatifs

Le tableau d'octets suivants :

00 05 00 04 00 02 00 03

représente la table des noms alternatifs :

I Nom alternatif Nom de la gare
0 Losanna Lausanne
1 Anet Ins

En effet, les deux premiers octets (00 05) représentent l'entier U16 qui vaut 5, et qui est l'index de la chaîne Losanna dans la table des chaînes. Les deux octets suivants (00 04) représentent l'entier U16 4, qui est l'index de la chaîne Lausanne. Et ainsi de suite.

2.6.3. Voies ou quais

Le tableau d'octets suivant :

00 00 00 00 00 01 00 00 00 00 00 01

représente la table des voies ou quai :

I Nom Gare parente
0 1 Lausanne
1 70 Lausanne
2 1 Palézieux

En effet, les deux premiers octets (00 00) représentent l'entier U16 qui vaut 0, qui est l'index de la chaîne 1 dans la table des chaînes. Les deux octets suivants (00 00) représentent l'entier U16 qui vaut aussi 0, qui est l'index de la gare de Lausanne dans la table des gares (!). Et ainsi de suite.

3. Mise en œuvre Java

Les classes de cette étape font toutes partie du sous-paquetage timetable.mapped, dédié aux données horaires « mappées en mémoire ». La signification exacte de ce terme sera expliquée dans une étape ultérieure, lorsque nous examinerons le chargement des données.

3.1. Classe Structure

La classe Structure du sous-paquetage timetable.mapped a pour but de faciliter la description de la structure des données aplaties. Ainsi, une fois terminée, cette classe permet d'écrire le code suivant pour décrire les noms alternatifs des gares :

int ALIAS_ID = 0;
int STATION_NAME_ID = 1;

Structure STRUCTURE = new Structure(
    field(ALIAS_ID, U16),
    field(STATION_NAME_ID, U16));

qui est très proche de la table donnée à la §2.4, les constantes ALIAS_ID et STATION_NAME_ID contenant les index (colonne I) des différents champs.

Une fois cette définition écrite, il est par exemple possible de calculer l'index, dans le tableau d'octets contenant les données aplaties, du premier octet de l'index de chaîne du nom de gare du second nom alternatif d'une table (celui d'index 1), ainsi :

int offset = STRUCTURE.offset(STATION_NAME_ID, 1);

qui vaut 6.

Structure possède un type énuméré imbriqué public nommé FieldType représentant les trois types de champs possibles, à savoir U8, U16 et S32.

De plus, elle possède un enregistrement imbriqué public nommé Field, qui représente un champ et possède les deux attributs suivants, dans l'ordre :

int index
l'index du champ dans la structure (colonne I dans les tables plus haut),
FieldType type
le type du champ.

Field possède un constructeur compact qui lève une NullPointerException ssi type est null.

Structure possède de plus une méthode publique et statique dont le but est d'alléger un peu la création d'instances de Field, en omettant le new, comme dans l'exemple plus haut :

Field field(int index, FieldType type)
qui retourne une instance de Field avec les attributs donnés.

Structure possède un unique constructeur, qui prend en arguments la description des différents champs de la structure :

Structure(Field... fields)
qui retourne une structure dont les champs sont ceux donnés, ou lève une IllegalArgumentException si ces champs ne sont pas donnés dans l'ordre — c.-à-d. si le premier d'entre eux n'est pas celui d'index 0, le second celui d'index 1, etc.
int totalSize()
qui retourne la taille totale, en octets, de la structure — p. ex. 10 pour celle correspondant aux gares,
int offset(int fieldIndex, int elementIndex)
qui retourne l'index, dans le tableau d'octets contenant les données aplaties, du premier octet du champ d'index fieldIndex de l'élément d'index elementIndex ; lève IndexOutOfBoundsException si l'index du champ est invalide.

3.1.1. Conseils de programmation

La méthode offset doit être aussi efficace que possible, car elle est utilisée pour accéder à la totalité des attributs des données horaires lors de la recherche de voyages. Dès lors, il faut que les calculs qu'elle doive faire pour déterminer la position qu'elle retourne consistent en une simple multiplication suivie d'une addition.

Cela implique que le constructeur de Structure doit calculer, et stocker dans des attributs, d'une part un tableau contenant la position, en octets, du premier octet de chacun des champs dans la structure, et d'autre part la taille totale de la structure, en octets.

L'existence du tableau contenant la position du premier octet des différents champs implique que la méthode offset n'a pas besoin de valider explicitement l'argument fieldIndex qu'elle reçoit, car Java lèvera automatiquement la bonne exception si cet index est invalide.

3.2. Classe StructuredBuffer

La classe StructuredBuffer du sous-paquetage timetable.mapped, représente un « tableau d'octets structuré ». Son but est d'offrir un accès agréable à des données aplaties stockées dans un tableau d'octets, et dont la structure est décrite par une instance de Structure.

Une fois cette classe terminée, il sera possible de l'utiliser par exemple ainsi pour obtenir l'index de chaîne du nom alternatif d'index 1 :

StructuredBuffer buffer = …;
int stationNameStringIndex = buffer.getU16(STATION_NAME_ID, 1);

Dans l'exemple de la §2.6, stationNameStringIndex vaudrait 3, car c'est l'index de chaîne Ins.

StructuredBuffer possède un unique constructeur public :

StructuredBuffer(Structure structure, ByteBuffer buffer)
qui construit un tableau structuré dont les éléments ont la structure donnée, et dont les octets sont stockés dans le « tableau » buffer, ou lève une IllegalArgumentException si le nombre d'octets de ce tableau n'est pas un multiple de la taille totale de la structure.

La classe ByteBuffer, qui appartient à la bibliothèque Java, est décrite dans les conseils de programmation ci-dessous.

En plus de son constructeur, StructuredBuffer offre les méthodes publiques suivantes :

int size()
qui retourne le nombre d'éléments que contient le tableau, p. ex. 3 pour les voies/quais de la §2.6,
int getU8(int fieldIndex, int elementIndex)
qui retourne l'entier U8 correspondant au champ d'index fieldIndex de l'élément d'index elementIndex du tableau, ou lève IndexOutOfBoundsException si l'un des deux index est invalide,
int getU16(int fieldIndex, int elementIndex)
qui fait la même chose que getU8 mais pour un champ de type U16,
int getS32(int fieldIndex, int elementIndex)
qui fait la même chose que getU8 mais pour un champ de type S32.

N'oubliez pas que les valeurs retournées par getU8 et getU16 doivent être positives, car les champs de ces deux types sont interprétés de manière non signée. C'est la raison pour laquelle ces méthodes retournent une valeur de type int et pas byte ou short.

3.2.1. Conseils de programmation

La classe ByteBuffer de la bibliothèque Java représente ce que l'on appelle parfois une mémoire tampon (buffer) en informatique. En bref, il s'agit d'un tableau utilisé pour stocker temporairement certaines données, en général dans le but d'améliorer les performances d'un programme.

Cela dit, dans ce projet, nous utiliserons cette classe comme un simple tableau d'octets, donc comme quelque chose de très similaire à une valeur de type byte[]. La raison principale pour laquelle nous l'utilisons à la place d'un véritable tableau de type byte[] est que le « mappage mémoire » n'est possible qu'avec des instances de ByteBuffer. Or comme nous l'avons dit plus haut, nous utiliserons le mappage mémoire pour charger les données horaires simplement et rapidement.

ByteBuffer est relativement complexe à comprendre, mais seules quatre de ses méthodes sont utiles à l'écriture de StructuredBuffer. La première est capacity, qui donne la taille du tableau, donc le nombre d'octets qu'il contient. Les trois autres sont get, getShort et getInt, qui permettent respectivement d'obtenir un entier de type byte, short ou int en combinant 1, 2 ou 4 octets consécutifs du tableau. Sans surprise, ces méthodes sont très utiles pour écrire getU8, getU16 et getS32. Toutefois, pour getU8 et getU16, il ne faut pas oublier que nous désirons interpréter les entiers de manière non signée, et donc qu'un appel à Byte.toUnsignedInt ou Short.toUnsignedInt est nécessaire.

Notez que les méthodes get, getShort et getInt lèvent toutes les trois une IndexOutOfBoundsException si l'index qu'on leur donne est invalide, ce qui implique qu'aucune validation explicite n'est nécessaire dans les méthodes getU8, getU16 et getS32.

3.3. Classe BufferedStations

La classe BufferedStations du sous-paquetage timetable.mapped, publique et finale, implémente l'interface Stations et permet d'accéder à une table de gares représentée de manière aplatie comme décrit à la §2.3. Elle possède un unique constructeur public :

BufferedStations(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înes stringTable pour 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 Stations.

3.3.1. Conseils de programmation

Dans la définition de cette classe et des suivantes, il faut absolument définir des constantes nommées pour les index des différents champs, similaires aux constantes ALIAS_ID et STATION_NAME_ID de l'exemple plus haut, afin de rendre le code plus facile à lire.

Pour calculer la constante \(\tfrac{360}{2^{32}}\) nécessaire à la conversion d'unités des longitudes et latitudes, utilisez la méthode scalb qui permet de multiplier une valeur quelconque par une puissance de 2 entière (et éventuellement négative), de manière à la fois efficace et précise. On peut la voir comme une version des opérateurs de décalage (<< et >>) mais qui fonctionne avec des valeurs en virgule flottante de type double.

3.4. Classe BufferedStationAliases

La classe BufferedStationAliasess du sous-paquetage timetable.mapped, publique et finale, implémente l'interface StationAliases et permet d'accéder à une table de noms alternatifs de gares représentée de manière aplatie comme décrit à la §2.4. Elle possède un unique constructeur public :

BufferedStationAliases(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înes stringTable pour 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 StationAliases.

3.5. Classe BufferedPlatforms

La classe BufferedPlatforms du sous-paquetage timetable.mapped, publique et finale, implémente l'interface Platforms et permet d'accéder à une table de voies ou quais représentée de manière aplatie comme décrit à la §2.5. Elle possède un unique constructeur public :

BufferedPlatforms(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înes stringTable pour 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 Platforms.

3.6. Tests

Comme d'habitude, nous ne vous fournissons plus de tests mais un fichier de vérification de signatures à importer dans votre projet.

Pour écrire vos tests, vous pouvez entre autres vous aider des valeurs d'exemple données à la §2.6. Grâce à la classe HexFormat de la bibliothèque Java, il est très simple d'obtenir le tableau d'octets correspondant à une chaîne ayant le même format que celui de cette section. Par exemple, pour obtenir le tableau d'octets des noms alternatifs, on peut procéder ainsi :

HexFormat hexFormat = HexFormat.ofDelimiter(" ");
byte[] bytes = hexFormat.parseHex("00 05 00 04 00 02 00 03");

Une fois ce tableau obtenu, la méthode wrap de ByteBuffer permet d'obtenir une valeur de type ByteBuffer qui peut directement être passée au constructeur de BufferedStationAliases.

4. Résumé

Pour cette étape, vous devez :

  • écrire les classes Structure, StructuredBuffer, BufferedStations, BufferedStationAliases et BufferedPlatforms 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 14 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.