¿Existe tal cosa como mapas bidireccionales en Scala?

collections scala-collections

Question

Me gustaría vincular 2 columnas de identificadores únicos y poder obtener un primer valor de columna por un segundo valor de columna así como un segundo valor de columna por un primer valor de columna. Algo como

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

¿Hay tal instalación en Scala?

En realidad necesito aún más: 3 columnas para seleccionar una en una triplete por otra en un triplete (los valores individuales nunca se cumplirán más de una vez en todo el mapa). Pero un mapa bidireccional de 2 columnas también puede ayudar.

Answer 1

Aquí hay un envoltorio rápido de Scala para BiMap de Guava.

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 2

La guayaba tiene un bimap que puedes usar junto con

import scala.collection.JavaConversions._

Answer 3

Mi enfoque BiMap:

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

Por supuesto, se puede agregar sintaxis para <-> lugar de -> .

Answer 4

No creo que exista fuera de la caja, porque el comportamiento genérico no es fácil de extraer

¿Cómo manejar valores que coincidan con varias claves en una api limpia?

Sin embargo, para casos específicos aquí es un buen ejercicio que podría ayudar. Debe actualizarse porque no se usa hash y obtener una clave o valor es O (n).

Pero la idea es dejarte escribir algo similar a lo que propones, pero usando Seq en lugar de Map ...

Con la ayuda de implícito y rasgo, además de encontrar, podría emular lo que necesita con una especie de api limpia ( fromKey , fromValue ).

La especificidad es que un valor no debe aparecer en varios lugares ... Al menos en esta implementación.

  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 5

Scala es inmutable y los valores se asignan como referencia, no para copia, por lo que la huella de memoria será solo para el almacenamiento de referencia / puntero, que es mejor usar en dos mapas, con el tipo A como clave para el primero y el tipo B para el segundo mapeado a B y A respectivamente, que el cambio de tiempo de tun de mapas. Y la implementación de intercambio también tiene su propia huella de memoria y el hash-map recién intercambiado también estará allí en la memoria hasta la ejecución de la devolución de la llamada principal y la llamada del recolector de basura. Y si el intercambio de mapas es necesario con frecuencia, virtualmente está usando igual o más memoria que la implementación ingenua de dos mapas en el inicio.

Un enfoque más que puede probar con un solo mapa es este (solo funcionará para obtener la clave utilizando el valor asignado):

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

Código para la implementación de Scala de buscar por clave:

/** 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 6

Tengo un BiMap realmente simple en 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)
  }

Uso:

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