Is there such a thing as bidirectional maps in Sca

Question

I'd like to link 2 columns of unique identifiers and be able to get a first column value by a second column value as well as a second column value by a first column value. Something like

Map(1 <-> "one", 2 <-> "two", 3 <-> "three")

Is there such a facility in Scala?

Actually I need even more: 3 columns to select any in a triplet by another in a triplet (individual values will never be met more than once in the entire map). But a 2-column bidirectional map can help too.

Answer 1

Scala is immutable and values are assigned as reference not copy, so memory footprint will for reference/pointer storage only, which it's better to use to two maps, with type A being key for first and type being B being key for second mapped to B and A respectively, than tun time swapping of maps. And the swapping implementation also has it's own memory footprint and the newly swapped hash-map will also be there in memory till the execution of parent call back and the garbage collector call. And if the the swapping of map is required frequently than virtually your are using equally or more memory than the naive two maps implementation at starting.

One more approach you can try with single map is this(will work only for getting key using mapped value):

def getKeyByValue[A,B](map: Map[A,B], value: B):Option[A] = hashMap.find((a:A,b:B) => b == value)

Code for Scala implementation of find by key:

/** Find entry with given key in table, null if not found.
   */
  @deprecatedOverriding("No sensible way to override findEntry as private findEntry0 is used in multiple places internally.", "2.11.0")
  protected def findEntry(key: A): Entry =
    findEntry0(key, index(elemHashCode(key)))

  private[this] def findEntry0(key: A, h: Int): Entry = {
    var e = table(h).asInstanceOf[Entry]
    while (e != null && !elemEquals(e.key, key)) e = e.next
    e
  }

Answer 2

I don't think it exists out of the box, because the generic behavior is not easy to extract

How to handle values matching several keys in a clean api?

However for specific cases here is a good exercise that might help. It must be updated because no hash is used and getting a key or value is O(n).

But the idea is to let you write something similar to what you propose, but using Seq instead of Map...

With the help of implicit and trait, plus find, you could emulate what you need with a kind of clean api (fromKey, fromValue).

The specificities is that a value is not supposed to appear in several places... In this implementation at least.

  trait BiMapEntry[K, V] {
    def key:K
    def value:V
  }

  trait Sem[K] {

    def k:K

    def <->[V](v:V):BiMapEntry[K, V] = new BiMapEntry[K,  V]() { val key = k; val value = v}
  }

  trait BiMap[K, V] {

    def fromKey(k:K):Option[V]

    def fromValue(v:V):Option[K]
  }


  object BiMap {
    implicit def fromInt(i:Int):Sem[Int] = new Sem[Int] {
      def k = i
    }

    implicit def fromSeq[K, V](s:Seq[BiMapEntry[K, V]]) = new BiMap[K, V] {
      def fromKey(k:K):Option[V] = s.find(_.key == k).map(_.value)
      def fromValue(v:V):Option[K] = s.find(_.value == v).map(_.key)
    }

  }




  object test extends App {

    import BiMap._



    val a = 1 <-> "a"

    val s = Seq(1 <-> "a", 2 <-> "b")

    println(s.fromKey(2))
    println(s.fromValue("a"))

  }

Answer 3

Here's a quick Scala wrapper for Guava's BiMap.

import com.google.common.{collect => guava}
import scala.collection.JavaConversions._
import scala.collection.mutable
import scala.languageFeature.implicitConversions

class MutableBiMap[A, B] private (
    private val g: guava.BiMap[A, B] = new guava.HashBiMap[A, B]()) {

  def inverse: MutableBiMap[B, A] = new MutableBiMap[B, A](g.inverse)
}

object MutableBiMap {

  def empty[A, B]: MutableBiMap[A, B] = new MutableBiMap()

  implicit def toMap[A, B] (x: MutableBiMap[A, B]): mutable.Map[A,B] = x.g
}

Answer 4

My BiMap approach:

object BiMap {
  private[BiMap] trait MethodDistinctor
  implicit object MethodDistinctor extends MethodDistinctor
}

case class BiMap[X, Y](map: Map[X, Y]) {
  def this(tuples: (X,Y)*) = this(tuples.toMap)
  private val reverseMap = map map (_.swap)
  require(map.size == reverseMap.size, "no 1 to 1 relation")
  def apply(x: X): Y = map(x)
  def apply(y: Y)(implicit d: BiMap.MethodDistinctor): X = reverseMap(y)
  val domain = map.keys
  val codomain = reverseMap.keys
}

val biMap = new BiMap(1 -> "A", 2 -> "B")
println(biMap(1)) // A
println(biMap("B")) // 2

Of course one can add syntax for <-> instead of ->.

Answer 5

I have a really simple BiMap in Scala:

  case class BiMap[A, B](elems: (A, B)*) {

    def groupBy[X, Y](pairs: Seq[(X, Y)]) = pairs groupBy {_._1} mapValues {_ map {_._2} toSet}

    val (left, right) = (groupBy(elems), groupBy(elems map {_.swap}))

    def apply(key: A) = left(key)
    def apply[C: ClassTag](key: B) = right(key)
  }

Usage:

  val biMap = BiMap(1 -> "x", 2 -> "y", 3 -> "x", 1 -> "y")
  assert(biMap(1) == Set("x", "y"))
  assert(biMap("x") == Set(1, 3))

Answer 6

Guava has a bimap that you can use along with

import scala.collection.JavaConversions._