iCalendar et valeurs empaquetées

Le format iCalendar est un format textuel, c.-à-d. que les données qu'il permet de représenter le sont sous la forme d'une séquence de caractères — exactement comme les programmes Java qui, eux aussi, ne sont rien d'autre que du texte.

Dans le format iCalendar, le texte est composé d'une suite de lignes. Chacune d'entre elles est terminée par une « séquence CRLF », constituée de deux caractères spéciaux nommés CR (pour carriage return) et LF (pour line feed). CR et LF sont ce que l'on nomme des caractères de contrôle (control characters), notion examinée plus en détail dans le cours sur les entrées/sorties mais décrite brièvement ci-après.

Contrairement aux caractères « normaux » comme les lettres de l'alphabet latin, ou encore les chiffres, les caractères de contrôle n'ont pas de représentation propre et ne sont donc généralement pas visibles à l'écran. Leur but est simplement de contrôler l'affichage du texte dans lequel ils se trouvent, par exemple en terminant la ligne actuelle pour passer à la suivante.

Comme ces caractères n'ont pas de représentation propre, des séquences d'échappement (escape sequences) sont utilisées en Java et dans d'autres langages pour les représenter. Ainsi, en Java, LF est représenté par la séquence d'échappement \n que vous connaissez déjà, tandis que CR est représenté par la séquence d'échappement \r. Dès lors, une chaîne Java ne contenant rien d'autre que la séquence CRLF peut s'écrire ainsi :

String CRLF = "\r\n";

Il faut bien comprendre que même si 4 caractères sont nécessaires à l'écriture du contenu de cette chaîne en Java — deux barres obliques inverses (\) ainsi que les lettres r et n —, elle ne contient en fait que deux caractères, qui sont justement CR et LF. Dès lors, la méthode length appliquée à cette chaîne retourne 2.

Comme nous le verrons dans le cours sur les entrées/sorties, les caractères CR et LF sont souvent utilisés pour représenter la fin d'une ligne, et c'est la raison pour laquelle dans le format iCalendar, toutes les lignes — y compris la dernière — se terminent par une séquence CRLF.

Il en va d'ailleurs de même avec les autres formats textuels, comme les programmes Java. Ainsi, lorsque vous écrivez un programme dans IntelliJ et que vous appuyez sur la touche Entrée (⮐) pour terminer une ligne, IntelliJ insère une séquence CRLF à la position du curseur¹.

Dans le format iCalendar, les lignes sont composées d'un nom (name) et d'une valeur (value) qui lui est associée. Le nom et la valeur sont séparés l'un de l'autre par un deux-points (:). Par exemple, la ligne suivante :

SUMMARY:Ecublens VD, EPFL → Gruyères

est composée du nom SUMMARY auquel est associée la valeur Ecublens VD, EPFL → Gruyères.

Les noms qu'il est possible d'utiliser sont définis par la norme iCalendar. Dans le cadre de ce projet, nous n'en utiliserons qu'un petit nombre, décrits plus loin.

La norme iCalendar spécifie qu'une ligne ne devrait pas faire plus de 75 caractères². Cela peut poser problème si la valeur associée à un nom est un long texte. Dans un tel cas, la norme spécifie que la ligne doit être « pliée » (folded), c.-à-d. découpée en plusieurs lignes ne faisant pas plus de 75 caractères chacune et commençant toutes — sauf la première — par une espace. Lorsqu'une telle longue ligne « logique » est pliée en plusieurs lignes « physiques », les séquences CRLF à la fin de chaque ligne physique sont ignorées — sauf la dernière —, de même que les espaces initiales de toutes les lignes physiques dès la seconde.

Par exemple, la ligne « logique » donnée en exemple plus haut :

SUMMARY:Ecublens VD, EPFL → Gruyères

peut également être « pliée » en trois lignes « physiques » ainsi :

SUMMA
 RY:Ecublens VD, EPFL → Gr
 uyères

Ces deux représentations sont totalement équivalentes, mais en général un tel « pliage » n'est fait que pour les lignes dépassant effectivement les 75 caractères. Un exemple d'une telle ligne est visible dans l'exemple de la §2.1.8 plus bas.

La norme iCalendar définit deux notions très similaires qui sont les objets (objects) et les composants (components). Le terme « objet » doit être compris au sens large, et pas au sens restreint qu'il a en Java.

Tout objet (ou composant) iCalendar est entouré d'une paire de lignes ayant respectivement BEGIN et END comme nom, et le type de l'objet (ou composant) comme valeur. Les deux seuls types que nous utiliserons dans ce projet sont :

VCALENDAR

qui représente un « objet iCalendar »,

VEVENT

qui représente un composant « événement dans un calendrier ».

En général, une donnée iCalendar est constituée d'un seul objet VCALENDAR qui contient un ou plusieurs composants. Dans le cadre de ce projet, tout objet VCALENDAR contiendra un unique composant VEVENT représentant un événement, ainsi que des attributs qui lui sont propres.

Les lignes qui se trouvent entre les BEGIN et END d'un objet (ou composant) décrivent soit ses attributs (attributes), soit des composants imbriqués, entourés eux-même d'une paire de lignes BEGIN et END.

Pour les objets VCALENDAR, nous n'utiliserons que les deux attributs suivants :

VERSION

qui donne la version de la norme iCalendar à laquelle correspond l'objet et qui sera toujours 2.0 — la version actuelle — pour nous,

PRODID

qui identifie le logiciel utilisé pour créer l'objet, p. ex. ReCHor dans notre cas.

Pour les composants VEVENT, nous n'utiliserons que les six attributs suivants :

UID

qui identifie de manière unique l'événement,

DTSTAMP

qui donne la date et l'heure à laquelle l'événement a été créé ou modifié pour la dernière fois (et pas celle de l'événement lui-même !),

DTSTART

qui donne la date et l'heure du début de l'événement,

DTEND

qui donne la date et l'heure de la fin de l'événement,

SUMMARY

qui donne une description sommaire de l'événement, qui est généralement toujours visible dans un calendrier électronique,

DESCRIPTION

qui donne une description détaillée de l'événement, qui n'est généralement visible que pour l'éventuel événement sélectionné dans un calendrier électronique.

Ces attributs sont décrits plus en détail dans les sections qui suivent.

La valeur de l'attribut UID (pour unique identifier, soit identifiant unique) est une chaîne de caractères identifiant de manière unique l'événement. Il est utilisé par les gestionnaires de calendrier pour déterminer si deux événements sont les mêmes ou non. Par exemple, si on importe successivement deux événements dans un gestionnaire de calendrier, alors le second ne remplacera le premier que si la valeur de leur attribut UID est identique.

Le format exact de la chaîne à utiliser comme valeur de l'attribut UID n'est pas spécifié par la norme iCalendar, mais pour ce projet nous utiliserons un identifiant unique de type UUID (avec deux U). Il s'agit d'une valeur de 128 bits représentée comme un entier en base 16 séparé en 5 parties au moyen de tirets, par exemple :

EEBABA70-83B9-4342-A046-BC949F562DC0

La raison pour laquelle une telle valeur est séparée par des tirets importe peu, de même que la manière exacte dont elle peut être générée. Comme nous le verrons plus loin, la bibliothèque Java offre une classe permettant de créer un UUID aléatoire ayant une très grande probabilité d'être unique, que nous pourrons utiliser sans devoir comprendre son fonctionnement.

Les valeurs associées aux attributs DTSTAMP (pour date/time stamp), DTSTART (pour date/time start) et DTEND (pour date/time end) sont des couples date/heure. DTSTAMP spécifie le moment où l'événement a été créé ou modifié pour la dernière fois, DTSTART celui auquel il commence, DTEND celui auquel il se termine.

Les date/heure associées à ces attributs sont représentées sous forme textuelle en concaténant :

• l'année, sur 4 chiffres,
• le mois, sur 2 chiffres (de 01 à 12),
• le jour du mois, sur 2 chiffres (de 01 à 31),
• la lettre T,
• les heures, sur 2 chiffres (de 00 à 23),
• les minutes, sur 2 chiffres (de 00 à 59),
• les secondes, sur 2 chiffres (de 00 à 59).

Par exemple, le 18 février 2025 à 16h13 est représenté par la chaîne suivante :

20250218T161300

Une telle date/heure est flottante (floating) dans la terminologie iCalendar, car le fuseau horaire dans lequel elle est exprimée n'est pas spécifié. Il s'agit implicitement du fuseau dans lequel se trouve l'utilisateur du gestionnaire de calendrier.

L'utilisation de date/heure flottantes convient bien à ce projet, sachant que tous les voyages qu'il permet de créer se déroulent dans un seul fuseau horaire, sauf ceux chevauchant les changements d'heure (été/hiver), que nous ignorerons.

Les valeurs associées aux attributs SUMMARY et DESCRIPTION sont des chaînes de caractères qui représentent respectivement un résumé de l'événement et une description plus détaillée. La plupart des gestionnaires de calendrier affichent le résumé comme « nom » de l'événement, tandis que la description n'est visible que lorsque l'événement est sélectionné.

La chaîne associée à SUMMARY est généralement courte, et composée d'une seule ligne de texte. Celle associée à DESCRIPTION est par contre souvent longue, et peut comporter plusieurs lignes. Dans ce cas, les lignes doivent être séparées les unes des autres par la séquence de caractères \n, soit la même que celle utilisée par Java pour représenter le caractère LF — mais attention, il s'agit bien d'une séquence de 2 caractères, et pas d'un unique caractère LF.

L'événement iCalendar correspondant au voyage donné en exemple à l'étape précédente pourrait ressembler à ceci :

BEGIN:VCALENDAR
VERSION:2.0
PRODID:ReCHor
BEGIN:VEVENT
UID:bbff399f-d276-4052-8798-9c2f227353de
DTSTAMP:20250216T182750
DTSTART:20250218T161300
DTEND:20250218T175700
SUMMARY:Ecublens VD, EPFL → Gruyères
DESCRIPTION:16h13 Ecublens VD, EPFL → Renens VD, gare (arr. 16h19)\ntrajet 
 à pied (3 min)\n16h26 Renens VD (voie 4) → Lausanne (arr. 16h33 voie 5)\nc
 hangement (5 min)\n16h40 Lausanne (voie 1) → Romont FR (arr. 17h13 voie 2)
 \nchangement (3 min)\n17h22 Romont FR (voie 1) → Bulle (arr. 17h41 voie 2)
 \nchangement (3 min)\n17h50 Bulle (voie 4) → Gruyères (arr. 17h57 voie 2)
END:VEVENT
END:VCALENDAR

Notez bien qu'aucune des lignes ne fait plus de 75 caractères, et que pour garantir cela la ligne de l'attribut DESCRIPTION a été « pliée » en cinq lignes « physiques » dont toutes — sauf la première — commencent par une espace. Ni ces espaces initiales ni les séquences CRLF qui les précèdent ne font partie de la valeur elle-même.

Notez également la présence de plusieurs séquences de caractères \n dans la valeur associée au nom DESCRIPTION, qui représentent des retours à la ligne, visibles dans la copie d'écran ci-dessous.

Cet événement est disponible sous la forme d'un fichier que vous pouvez télécharger sur votre ordinateur si vous désirez l'examiner ou voir comment il est importé dans votre gestionnaire de calendrier. Par exemple, en l'important dans l'application Calendrier de macOS, cet événement est présenté ainsi :

Nous aurons ultérieurement besoin de représenter des intervalles d'entiers, par exemple tous les entiers allant de 1234 (inclus) à 1278 (exclu).

La manière naturelle de représenter de tels intervalles en Java serait de définir un enregistrement qui pourrait ressembler à ceci :

record IntInterval(int startInclusive, int endExclusive) {
  // … méthodes
}

L'intervalle mentionné en exemple plus haut pourrait alors être construit ainsi :

new IntInterval(1234, 1278)

Cette représentation est tout à fait valide et facile à utiliser, et c'est elle que nous vous recommanderions d'utiliser dans la plupart des cas.

Toutefois, dans ce projet, nous utiliserons des intervalles d'entiers dans l'algorithme de recherche de voyages, qui doit absolument être aussi rapide que possible. Il peut dès lors valoir la peine d'essayer de trouver une représentation plus compacte de ces intervalles, qui ne nécessite pas la création d'un nouvel objet pour chacun d'entre eux.

Une solution consiste bien entendu à représenter un intervalle de manière empaquetée. Comme nous le verrons, les intervalles que nous devrons représenter auront les caractéristiques suivantes :

1. leur borne inférieure est toujours positive ou nulle, et plus petite que 2²⁴,
2. leur taille — la différence entre la borne supérieure et inférieure — est toujours plus petite que 256.

Dès lors, ces intervalles peuvent être empaquetés dans un entier de type int (32 bits), en plaçant par exemple la taille de l'intervalle dans les 8 bits de poids faible, et la borne inférieure dans les 24 bits de poids fort.

Avec cette technique, l'intervalle mentionné plus haut serait représenté par les 32 bits suivants (les 8 bits de poids faible ont été séparés des 24 de poids fort pour faciliter la lecture) :

000000000000010011010010 00101100

En effet, en base 2, 1234₁₀ s'écrit 10011010010₂, tandis que 44₁₀ (la taille de l'intervalle) s'écrit 101100₂.

Par rapport à la représentation objet (enregistrement), cette représentation empaquetée a les avantages suivants :

• elle consomme moins de mémoire, puisqu'un intervalle se représente au moyen de 32 bits, alors qu'une instance d'une classe comme IntInterval en nécessite environ 3 ou 4 fois plus,
• la création d'un intervalle peut se faire par simple manipulation de bits, et ne nécessite pas d'allouer de la mémoire pour y stocker les attributs.

Bien entendu, la représentation empaquetée possède également de nombreux inconvénients par rapport à la représentation objet :

• aucun type spécifique n'existe pour les intervalles, qui sont de simples valeurs de type int qu'il est très facile de confondre avec d'autres valeurs du même type,
• il n'est pas possible de définir des méthodes sur les valeurs empaquetées, comme p.ex. toString, car ce ne sont pas des objets.

Dès lors, comme nous l'avons dit, une représentation empaquetée ne devrait être utilisée que lorsque les gains en performance sont conséquents et justifient ces inconvénients.

Une des caractéristiques importantes de ReCHor est que, lors de la recherche d'horaires, il essaie d'optimiser simultanément trois critères, qui sont :

• l'heure de départ, \(d\), que l'on désire maximiser,
• l'heure d'arrivée, \(a\), que l'on désire minimiser,
• le nombre de changements, \(c\), que l'on désire minimiser.

Nous grouperons généralement ces trois critères dans un triplet \((d, a, c)\).

Lorsqu'un triplet de critères est meilleur qu'un autre pour au moins l'un des trois critères, tout en étant au moins aussi bon pour les critères restants, on dit que le premier triplet domine (dominates) le second.

Par exemple, le triplet \((\textrm{8h05}, \textrm{9h00}, 1)\) domine le triplet \((\textrm{8h00}, \textrm{9h00}, 2)\) car il est meilleur pour au moins l'un des critères — ici l'heure de départ, car \(\textrm{8h05} > \textrm{8h00}\), et le nombre de changements, car \(1 < 2\) — et au moins aussi bon pour les critères restants — l'heure d'arrivée, qui est identique.

Comme nous le verrons plus en détail dans une étape ultérieure, les voyages affichés par ReCHor en réponse à une requête sont tous ceux dont le triplet de critères d'optimisation n'est pas dominé par celui d'un autre voyage. Ainsi, s'il n'y avait que deux voyages possibles pour relier un arrêt à un autre :

1. un partant à 8h05, arrivant à 9h00 et nécessitant 1 changement, et
2. un partant à 8h00, arrivant à 9h00 et nécessitant 2 changements,

alors ReCHor ne montrerait que le premier, car le second est dominé par lui, comme nous l'avons vu ci-dessus. Intuitivement, cela est tout à fait sensé : à quoi bon partir 5 minutes plut tôt et faire un changement de plus pour arriver à destination à la même heure ?

Formellement, un triplet \(t_1 = (d_1, a_1, c_1)\) domine un triplet \(t_2 = (d_2, a_2, c_2)\) si et seulement si :

\[(d_1 \ge d_2) \wedge (a_1 \le a_2) \wedge (c_1 \le c_2) \wedge (t_1\ne t_2)\]

ce que l'on note :

\[t_1\prec t_2\]

On dit également qu'un triplet \(t_1\) domine ou est égal à (dominates or is equal to) un triplet \(t_2\) si :

\[(d_1 \ge d_2) \wedge (a_1 \le a_2) \wedge (c_1 \le c_2)\]

ce que l'on note :

\[t_1\preceq t_2\]

En d'autres termes, on peut définir la domination ainsi :

\[t_1\prec t_2 \ \Leftrightarrow\ (t_1\preceq t_2) \wedge (t_1\ne t_2)\]

Il faut noter que, étant donné deux triplets, il est tout à fait possible qu'aucun des deux ne domine l'autre. Par exemple, le triplet \(t_1 = (\textrm{8h05}, \textrm{9h00}, 1)\) ne domine pas, ni n'est dominé par, le triplet \(t_2 = (\textrm{8h00}, \textrm{8h55}, 1)\). En effet, \(t_1\) est meilleur que \(t_2\) du point de vue de l'heure de départ, mais moins bon que lui du point de vue de l'heure d'arrivée, et équivalent du point de vue des changements.

En termes mathématiques, cela signifie que la relation de domination est un ordre partiel et pas un ordre total.

Comme les intervalles, les critères d'optimisation (triplets) pourraient être représentés naturellement en Java au moyen d'un enregistrement, qui pourrait ressembler à ceci :

record Criteria(LocalTime depTime,
                LocalTime arrTime,
                int changes) { /* … méthodes */ }

Toutefois, l'algorithme de recherche utilisé par ReCHor nécessite le calcul et le stockage de plusieurs millions de critères pour chaque requête, et donc l'utilisation d'une représentation empaquetée semble justifiée.

Pour trouver une représentation empaquetée qui convienne, il faut trouver comment représenter les heures de départ et d'arrivée sous la forme d'entiers. Sachant que, dans les horaires de transports publics, ces heures sont données à une précision qui ne dépasse pas la minute, il paraît naturel de les représenter au moyen du nombre de minutes écoulées depuis une origine arbitraire.

Même si le choix de l'origine est arbitraire, il semble raisonnable d'en choisir une qui garantisse que toutes les heures — exprimées en minutes depuis elle — soient positives. À première vue, on pourrait penser que minuit (0h00) convient, mais pour des raisons qui deviendront claires dans une étape ultérieure, il se trouve que nous devrons parfois représenter des heures avant minuit. Afin d'avoir un peu de marge, nous choisirons 4h avant minuit, soit –240 minutes, comme origine des heures.

Une fois l'origine choisie, il faut encore déterminer la plus grande heure possible afin de connaître la plage des heures qu'il faut pouvoir représenter. On pourrait penser que la plus grande heure qu'il est nécessaire de représenter est 23h59, mais ce n'est pas le cas. En effet, les transports publics utilisent généralement une notion de jour, appelé jour de service (service day), qui diffère de celle de jour civil.

L'une des raisons en est que la gestion des horaires est simplifiée si toutes les courses arrivent le même jour qu'elles sont parties, entre autres car cela évite de devoir stocker deux dates. Dès lors, toutes les courses se terminant après minuit utilisent des heures supérieures à 23h59. Par exemple, un train partant de Lausanne à 23h30 et arrivant à Genève à 0h23 le jour (civil) d'après sera considéré comme arrivant à 24h23 le même jour (de service).

En conséquence, et afin d'avoir un peu de marge, nous considérerons que la plus grande heure qui doit être représentable est 47h59, soit 3119 minutes après l'origine choisie (–240 min). Sachant que \(\log_2 3119 \approx 11.6\) on en conclut que les heures de départ et d'arrivée d'un triplet peuvent être représentées avec 12 bits chacune.

Une dernière amélioration peut encore être apportée à la représentation des heures. Comme cela a été dit plus haut, des trois critères d'optimisations utilisés, deux doivent être minimisés (l'heure d'arrivée et le nombre de changements), tandis que le dernier doit être maximisé (l'heure de départ). Cette asymétrie peut compliquer certaines choses, et il serait préférable que tous les critères doivent être soit minimisés, soit maximisés.

Pour garantir cela, nous pouvons remplacer l'heure de départ par ce que nous appellerons son complément, c.-à-d. le nombre de minutes qui sépare cette heure de l'heure maximale représentable, à savoir 4095 (\(2^{12}-1\)).

Ainsi, l'heure 12h34 sera représentée par l'entier 994 (\(240 + 12\cdot60 + 34\)) s'il s'agit d'une heure d'arrivée, mais par l'entier 3101 (\(4095 - 994\)) s'il s'agit d'une heure de départ.

La question des heures de départ et d'arrivée étant réglée, il nous reste maintenant à considérer le dernier critère d'optimisation, le nombre de changements. Il est clair que celui-ci est un entier positif ou nul, et on peut raisonnablement faire l'hypothèse qu'il est inférieur à 128. Dès lors, 7 bits suffisent à le représenter.

En résumé, un triplet de critères d'optimisation peut être représenté au moyen d'un total de 31 bits : 12 pour (le complément de) l'heure de départ, 12 pour l'heure d'arrivée, et 7 pour le nombre de changements. Il serait donc possible d'empaqueter un tel triplet dans un entier de type int ayant la structure suivante :

Le fait que le bit de poids le plus fort (d'index 31) vaille 0 garantit qu'un tel entier est toujours interprété comme positif, ce qui simplifiera certaines étapes ultérieures.

L'algorithme de recherche d'horaire utilisé par ReCHor devra associer aux critères d'optimisation des informations permettant de reconstruire les voyages.

Comme nous le verrons, les informations qui doivent être associées à un triplet tiennent dans 32 bits. Dès lors, il est possible de les empaqueter avec les critères dans un entier de 64 bits — de type long en Java — en plaçant les critères d'optimisation dans les 32 bits de poids fort, et les informations associées — que nous nommerons la charge utile (payload) — dans les 32 bits de poids faible. En résumé, ces « critères augmentés » seront empaquetés dans un entier de type long ayant la structure suivante :

Une dernière caractéristique de l'algorithme de recherche d'horaires utilisé par ReCHor est que dans certains cas, il devra représenter et stocker des paires de critères plutôt que des triplets. Ces paires sont composées uniquement d'une heure d'arrivée et d'un nombre de changements, sans heure de départ.

Nous pourrions bien entendu représenter ces paires de critères différemment des triplets, mais il est plus simple de les représenter en utilisant une valeur spéciale — et invalide — pour l'heure de départ, afin de signaler son absence. Dans un tel cas, les bits correspondant à l'heure de départ vaudront tous 0, et les paires de critères augmentés seront donc empaquetés dans un entier de type long ayant la structure suivante :

L'heure d'arrivée représentée par ces 12 bits valant 0 est 64h15, ce qui est effectivement au-delà de la limite de 47h59 que nous nous sommes fixé.

Pour illustrer la représentation empaquetée des critères d'optimisations, voyons comment représenter le triplet \((\textrm{8h00}, \textrm{9h00}, 2)\) donné en exemple plus haut.

L'heure de départ, 8h00, exprimée en minutes depuis l'origine à –4h, est 720. Son complément, qui est ce qui est stocké dans la représentation empaquetée, vaut 3375, soit 110100101111₂ en binaire.

L'heure d'arrivée, 9h00, exprimée en minutes depuis l'origine, est 780, soit 1100001100₂ en binaire.

Le nombre de changements est 2, soit 10₂ en binaire.

En combinant ces trois informations, on en déduit que les 32 bits de poids fort de la représentation empaquetée de ce triplet valent (avec des espaces séparant les différentes parties afin de faciliter la lecture) :

0 110100101111 001100001100 0000010

Quant aux 32 bits de poids faible, leur valeur est simplement celle de la charge utile, qui peut être quelconque.