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'indexelementIndex
; lèveIndexOutOfBoundsException
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 uneIllegalArgumentException
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'indexfieldIndex
de l'élément d'indexelementIndex
du tableau, ou lèveIndexOutOfBoundsException
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 typeU16
, int getS32(int fieldIndex, int elementIndex)
- qui fait la même chose que
getU8
mais pour un champ de typeS32
.
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înesstringTable
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înesstringTable
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înesstringTable
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
etBufferedPlatforms
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.