Come creare una mappa bidirezionale in JavaScript

Una mappa bidirezionale è un modello dell’informatica in cui le coppie chiave-valore hanno una relazione biunivoca 1-1 tra le chiavi e i valori. Questo ci consente non solo di interrogare per chiave e ottenere un valore, ma anche di interrogare per valore e ottenere la chiave. Vediamo come implementare una mappa bidirezionale in JavaScript e in seguito rendiamola sicura in TypeScript

L’informatica e la matematica dietro

Prendiamo una definizione di base di una mappa bidirezionale:

In informatica, una mappa bidirezionale è una struttura di dati associativa in cui le coppie chiave-valore formano una corrispondenza uno-a-uno. Quindi la relazione binaria è funzionale in ogni direzione: ogni valore può anche essere mappato su una chiave univoca.

Credito: mappa bidirezionale

La mappa bidirezionale dell’informatica ha le sue radici in una funzione matematica chiamata biiezione. La relazione tra i componenti di una coppia con ciascuno dei suoi componenti in insiemi diversi è una funzione biiettiva, detta anche funzione invertibile, che è una funzione che funziona in entrambi i modi, accoppiando esattamente un elemento di un insieme con esattamente un elemento di l’altro set:

Credito: Biiezione

Con questo in mente possiamo sapere che una funzione biiettiva per gli insiemi sopra produrrà qualcosa come:

f (1) = D
f (C) = 3

Un’altra cosa che deriva dalla funzione biiettiva è che gli insiemi avranno esattamente la stessa lunghezza, altrimenti la biiezione fallirebbe.

Inizializzare la mappa bidirezionale

Lo modelleremo con una classe JavaScript che verrà inizializzata con un oggetto di coppie chiave – valore:

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

Internamente creeremo due liste. Una lista memorizzerà l’elenco di coppie di quella che chiameremo una mappa diretta, dove le mappe chiave da valutare e sarà una copia dell’oggetto che abbiamo usato per inizializzare la mappa bidirezionale. Il secondo elenco sarà quella che chiameremo mappa inversa e memorizzerà una versione dell’oggetto utilizzato per inizializzare la mappa bidirezionale in cui le coppie chiave-valore sono state capovolte e il "valore" ora viene mappato sulla "chiave":

Nota che a causa della natura dell’oggetto che inizializza la mappa bidirezionale non puoi usare un numero per la chiave ma puoi comunque usarlo come valore e sarai in seguito in grado di interrogarlo:

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

Una versione più robusta sebbene anche più complessa potrebbe essere scritta con il tipo di dati Map di JavaScript e consentire chiavi che sono numeri, funzioni o persino NaN.

Ottieni un elemento da una mappa bidirezionale

Fino a questo punto, abbiamo una struttura dati che ospita due oggetti, uno dei quali è lo specchio dell’altro in termini di valori chiave. Ora abbiamo bisogno di un metodo per ottenere qualcosa da esso. Implementiamo una get()funzione:

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

È molto semplice: se esiste nella mappa in avanti, lo restituiamo, altrimenti lo restituiamo dalla mappa invertita. Se non esiste, undefinedverrà restituito.

Ora possiamo ottenere alcuni elementi come:

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

Aggiungi un elemento a una mappa bidirezionale

La nostra mappa al momento non ha un modo per aggiungere più elementi, quindi aggiungiamo una funzione per aggiungere nuovi elementi alla mappa:

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

Questo riceverà una matrice di due elementi, che in seguito digiteremo come una tupla con TypeScript e li assegnerà come valori chiave in entrambe le direzioni agli oggetti corrispondenti.

E ora possiamo aggiungere una coppia e interrogare questa nuova coppia

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

Una mappa bidirezionale sicura per i tipi in TypeScript

Per migliorare le cose e digitare in modo sicuro possiamo riscriverlo in TypeScript e aggiungere concetti di digitazione come un oggetto generico durante l’inizializzazione della mappa e una tupla quando si aggiunge un nuovo elemento.

Questa digitazione ora rende la nostra mappa perfettamente sicura e garantisce, in questo caso, di utilizzare sempre le stringhe sia per le chiavi che per i valori.