Como criar um mapa bidirecional em JavaScript

Um mapa bidirecional é um modelo da ciência da computação em que os pares chave-valor têm uma relação bijetiva 1-1 entre as chaves e os valores. Isso nos permite não apenas consultar por chave e obter um valor, mas também consultar pelo valor e obter a chave. Vamos ver como implementar um mapa bidirecional em JavaScript e vamos torná-lo mais tarde seguro no TypeScript

A ciência da computação e a matemática por trás

Vamos pegar uma definição básica de um mapa bidirecional:

Na ciência da computação, um mapa bidirecional é uma estrutura de dados associativa na qual os pares chave-valor formam uma correspondência um-para-um. Assim, a relação binária é funcional em cada direção: cada valor também pode ser mapeado para uma chave única.

Crédito: Mapa Bidirecional

O mapa bidirecional da ciência da computação tem suas raízes em uma função matemática chamada bijeção. A relação entre os componentes de um par com cada um de seus componentes em conjuntos diferentes é uma função bijetiva, também chamada de função invertível, que é uma função que funciona nos dois sentidos, emparelhando exatamente um elemento de um conjunto com exatamente um elemento de o outro conjunto:

Crédito: Bijeção

Com isso em mente, podemos saber que uma função bijetiva para os conjuntos acima produzirá algo como:

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

Outra coisa que surge da função bijetiva é que os conjuntos terão exatamente o mesmo comprimento, caso contrário a bijeção falharia.

Inicialize o mapa bidirecional

Vamos modelar isso com uma classe JavaScript que será inicializada com um objeto de pares chave-valor:

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

Internamente, criaremos duas listas. Uma lista armazenará a lista de pares do que chamaremos de mapa de encaminhamento, onde a chave mapeia para o valor e será uma cópia do objeto que usamos para inicializar o mapa bidirecional. A segunda lista será o que chamaremos de mapa reverso e armazenará uma versão do objeto usado para inicializar o mapa bidirecional onde os pares chave-valor foram invertidos e o “valor" agora mapeia para a “chave”:

Observe que, devido à natureza do objeto que inicializa o mapa bidirecional, você não pode usar um número para a chave, mas ainda pode usá-lo como um valor e depois poderá consultar por ele:

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

Uma versão mais robusta, embora também mais complexa, poderia ser escrita com o tipo de dados Map de JavaScript e permitir chaves que são números, funções ou mesmo NaN.

Obter um elemento de um mapa bidirecional

Até este ponto, temos uma estrutura de dados que hospeda dois objetos, sendo um deles um espelho do outro em termos de valores-chave. Agora precisamos de um método para tirar algo disso. Vamos implementar uma get()função:

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

É muito simples: se existir no mapa direto, nós o retornamos, caso contrário, retornamos do mapa invertido. Se não existir, undefinedserá devolvido.

Agora podemos obter alguns elementos como:

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

Adicionar um elemento a um mapa bidirecional

Nosso mapa atualmente não tem como adicionar mais elementos, então vamos adicionar uma função para adicionar novos elementos ao mapa:

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

Isso receberá uma matriz de dois elementos, que mais tarde digitaremos como uma tupla com TypeScript e os atribuiremos como valores-chave em ambas as direções para os objetos correspondentes.

E agora podemos adicionar um par e consultar este novo par

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

Um mapa bidirecional seguro de tipo no TypeScript

Para tornar as coisas melhores e com segurança de tipos, podemos reescrever isso no TypeScript e adicionar conceitos de digitação como um objeto genérico ao inicializar o mapa e uma tupla ao adicionar um novo elemento.

Essa digitação agora torna nosso mapa perfeitamente seguro e garante que, nesse caso, sempre usaremos strings para chaves e valores.