Comment créer une carte bidirectionnelle en JavaScript

Une carte bidirectionnelle est un modèle de l’informatique où les paires clé-valeur ont une relation bijective 1-1 entre les clés et les valeurs. Cela nous permet non seulement d’interroger par clé et d’obtenir une valeur, mais également d’interroger par valeur et d’obtenir la clé. Voyons comment implémenter une carte bidirectionnelle en JavaScript et rendons-la plus tard sécurisée dans TypeScript

L’informatique et les mathématiques derrière

Prenons une définition de base d’une carte bidirectionnelle :

En informatique, une carte bidirectionnelle est une structure de données associative dans laquelle les paires clé-valeur forment une correspondance biunivoque. Ainsi, la relation binaire est fonctionnelle dans chaque direction: chaque valeur peut également être associée à une clé unique.

Crédit: Carte bidirectionnelle

La carte bidirectionnelle de l’informatique a ses racines dans une fonction mathématique appelée bijection. La relation entre les composants d’une paire avec chacun de ses composants dans différents ensembles est une fonction bijective, également appelée fonction inversible, qui est une fonction qui fonctionne dans les deux sens, associant exactement un élément d’un ensemble avec exactement un élément de l’autre ensemble :

Crédit: Bijection

Dans cet esprit, nous pouvons savoir qu’une fonction bijective pour les ensembles ci-dessus produira quelque chose comme :

f (1) = ré
f (C) = 3

Une autre chose qui découle de la fonction bijective est que les ensembles auront exactement la même longueur, sinon la bijection échouerait.

Initialiser la carte bidirectionnelle

Nous allons modéliser cela avec une classe JavaScript qui sera initialisée avec un objet de paires clé-valeur :

const bimap = new BidirectionalMap({
  a: 'A',
  b: 'B',
  c: 'C',
})

En interne, nous allons créer deux listes. Une liste stockera la liste des paires de ce que nous appellerons une carte directe, où la clé correspond à la valeur et sera une copie de l’objet que nous avons utilisé pour initialiser la carte bidirectionnelle. La deuxième liste sera ce que nous appellerons une carte inversée et stockera une version de l’objet utilisé pour initialiser la carte bidirectionnelle où les paires clé – valeur ont été inversées et la "valeur" correspond maintenant à la "clé":

Notez qu’en raison de la nature de l’objet qui initialise la carte bidirectionnelle, vous ne pouvez pas utiliser de nombre pour la clé, mais vous pouvez toujours l’utiliser comme valeur et vous pourrez plus tard interroger par celui-ci :

const bimap = new BidirectionalMap({
  a: 42,
  b: 'B',
  c: 'C',
})

Une version plus robuste mais aussi plus complexe pourrait être écrite avec le type de données Map de JavaScript et autoriser les clés qui sont des nombres, des fonctions ou même NaN.

Obtenir un élément d’une carte bidirectionnelle

Jusqu’à présent, nous avons une structure de données qui héberge deux objets, l’un d’eux étant un miroir de l’autre en termes de clé – valeurs. Nous avons maintenant besoin d’une méthode pour en tirer quelque chose. Implémentons une get()fonction :

  get( key) {
      return this.fwdMap[key] || this.revMap[key]
  }

C’est très simple: s’il existe dans la carte vers l’avant, nous le renvoyons, sinon nous le renvoyons depuis la carte inversée. S’il n’en existe pas, undefinedsera retourné.

Nous pouvons maintenant obtenir des éléments comme :

console.log( bimap.get('a')) console.log( bimap.get('A')) 

Ajouter un élément à une carte bidirectionnelle

Notre carte n’a actuellement aucun moyen d’ajouter plus d’éléments, alors ajoutons une fonction pour ajouter de nouveaux éléments à la carte :

  add( pair) {
    this.fwdMap[pair[0]] = pair[1]
    this.revMap[pair[1]] = pair[0]
  }

Cela recevra un tableau de deux éléments, que nous taperons plus tard comme un tuple avec TypeScript, et les affectera comme clé – valeurs dans les deux sens aux objets correspondants.

Et maintenant nous pouvons ajouter une paire et interroger cette nouvelle paire

bimap.add(['d', 'D'])
console.log( bimap.get('D')) 

Une carte bidirectionnelle de type sécurisé dans TypeScript

Pour améliorer les choses et taper en toute sécurité, nous pouvons réécrire cela dans TypeScript et ajouter des concepts de typage comme un objet générique lors de l’initialisation de la carte et un tuple lors de l’ajout d’un nouvel élément.

Ce typage rend maintenant notre carte parfaitement sûre et garantit, dans ce cas, que nous utiliserons toujours des chaînes pour les clés et les valeurs.