Carte à valeurs multiples en Scala

Question

En Scala 2.8, j'ai une fonction immuable avec plusieurs valeurs pour chaque clé :

Map[T,Iterable[U]]

Y a-t-il une représentation supérieure ? Deuxièmement, comment générer une telle carte à partir de

Iterable[(T,U)]

? J'utilise actuellement :

def toGroupedMap[T,U](vals: Iterable[(T,U)]): Map[T,Iterable[U]] =
  vals.groupBy(_._1).map({ case (s,it) => (s,it.map(_._2)) }).toMap

Ce qui fonctionne, mais semble maladroit.

EDIT : Je dois préciser que je travaille avec des données immuables. Existe-t-il un équivalent immuable de MultiMap ?

Answer 1

Si vous n'avez pas vraiment besoin d'immuabilité, alors comme d'autres l'ont dit, MultiMap est la voie à suivre. Si vous avez vraiment besoin de l'immuabilité, alors l'approche que vous avez adoptée est aussi simple que n'importe quelle autre ; il n'y a rien d'intégré (AFAIK), et toute création d'un MultiMap immuable va demander beaucoup plus de travail que la méthode que vous avez là.

La supériorité de la représentation dépend de votre utilisation. Voulez-vous souvent faire des choses avec toutes les valeurs correspondant à une seule clé ? Pouvez-vous insérer la même valeur plusieurs fois dans votre carte ? Si vous répondez oui à ces deux questions, votre représentation est la bonne.

Si vous souhaitez que la même valeur soit insérée au maximum une fois sur une clé, vous devez utiliser la méthode suivante Set[U] au lieu de Iterable[U] (ce qui peut facilement être fait en ajoutant .toSet a it.map(_._2) ).

Si vous n'aimez pas avoir à gérer les ensembles/itérables et que vous vous en accommodez (c'est-à-dire que vous préférez vraiment avoir des paires clé-valeur plutôt que des paires clé-ensemble-de-valeurs), vous devrez écrire une classe enveloppante autour de la carte qui présente une seule interface de carte et qui fera la bonne chose avec +, - et itérateur.

Voici un exemple qui s'est avéré un peu plus long que prévu (ici formaté pour être coupé et collé dans le REPL) :

import scala.collection._
class MapSet[A,B](
  val sets: Map[A,Set[B]] = Map[A,Set[B]]()
) extends Map[A,B] with MapLike[A,B,MapSet[A,B]] {
  def get(key: A) = sets.getOrElse(key,Set[B]()).headOption
  def iterator = new Iterator[(A,B)] {
    private val seti = sets.iterator
    private var thiskey:Option[A] = None
    private var singles:Iterator[B] = Nil.iterator
    private def readyNext {
      while (seti.hasNext && !singles.hasNext) {
        val kv = seti.next
        thiskey = Some(kv._1)
        singles = kv._2.iterator
      }
    }
    def hasNext = {
      if (singles.hasNext) true
      else {
        readyNext
        singles.hasNext
      }
    }
    def next = {
      if (singles.hasNext) (thiskey.get , singles.next)
      else {
        readyNext
        (thiskey.get , singles.next)
      }
    }
  }
  def +[B1 >: B](kv: (A,B1)):MapSet[A,B] = {
    val value:B = kv._2.asInstanceOf[B]
    new MapSet( sets + ((kv._1 , sets.getOrElse(kv._1,Set[B]()) + value)) )
  }
  def -(key: A):MapSet[A,B] = new MapSet( sets - key )
  def -(kv: (A,B)):MapSet[A,B] = {
    val got = sets.get(kv._1)
    if (got.isEmpty || !got.get.contains(kv._2)) this
    else new MapSet( sets + ((kv._1 , got.get - kv._2)) )
  }
  override def empty = new MapSet( Map[A,Set[B]]() )
}

et nous pouvons voir que cela fonctionne comme souhaité comme ceci :

scala> new MapSet() ++ List(1->"Hi",2->"there",1->"Hello",3->"Bye")
res0: scala.collection.Map[Int,java.lang.String] = Map(1 -> Hi, 1 -> Hello, 2 -> there, 3 -> Bye)

scala> res0 + (2->"ya")
res1: scala.collection.Map[Int,java.lang.String] = Map(1 -> Hi, 1 -> Hello, 2 -> there, 2 -> ya, 3 -> Bye)

scala> res1 - 1
res2: scala.collection.Map[Int,java.lang.String] = Map(2 -> there, 2 -> ya, 3 -> Bye)

(cependant, si vous souhaitez récupérer un MapSet après ++, vous devrez surcharger ++ ; la hiérarchie Map n'a pas ses propres constructeurs pour s'occuper de ce genre de choses).

Answer 2

Examinez le mix-in MultiMap pour Map.

Answer 3

Une multimap est ce dont vous avez besoin. Voici un exemple pour en créer une et y ajouter des entrées à partir d'une liste[(String, Int)]. Je suis sûr qu'il y a un moyen plus joli.

scala> val a = new collection.mutable.HashMap[String, collection.mutable.Set[Int]]() with collection.mutable.MultiMap[String, Int]
a: scala.collection.mutable.HashMap[String,scala.collection.mutable.Set[Int]] with scala.collection.mutable.MultiMap[String,Int] = Map()

scala> List(("a", 1), ("a", 2), ("b", 3)).map(e => a.addBinding(e._1, e._2))                                                      
res0: List[scala.collection.mutable.HashMap[String,scala.collection.mutable.Set[Int]] with scala.collection.mutable.MultiMap[String,Int]] = List(Map(a -> Set(1, 2), b -> Set(3)), Map(a -> Set(1, 2), b -> Set(3)), Map(a -> Set(1, 2), b -> Set(3)))

scala> a("a")
res2: scala.collection.mutable.Set[Int] = Set(1, 2)