Scala collections, single key multiple values

Question

I have a list of parent keys, each of which could possibly have zero or more associated values. I am not sure which collection to use.

I am using Map[Int,List[String]]

I am declaring the Map as

var nodes = new HashMap[Int, List[String]]

Then I have two methods to handle adding new elements. The first is to add new keys addNode and the second is to add new values addValue. Initially, the key will not have any values associated with it. Later on, during execution, new values will be associated.

def addNode(key: Int) = nodes += (key -> "")

def addValue(key: Int, value: String) = ???

I am not sure how to implement addValues

Update:

In response to @oxbow-lakes answer, This is the error I am receiving. Please note that keys need not have values associated with them.

scala> var nodes = Map.empty[Int, List[String]]
nodes: scala.collection.immutable.Map[Int,List[String]] = Map()

scala> nodes += (1->null)

scala> nodes += (1 -> ("one" :: (nodes get 1 getOrElse Nil)))
java.lang.NullPointerException
    at .<init>(<console>:9)
    at .<clinit>(<console>)
    at .<init>(<console>:11)
    at .<clinit>(<console>)
    at $print(<console>)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
    at java.lang.reflect.Method.invoke(Method.java:597)
    at scala.tools.nsc.interpreter.IMain$ReadEvalPrint.call(IMain.scala:704)
    at scala.tools.nsc.interpreter.IMain$Request$$anonfun$14.apply(IMain.scala:920)
    at scala.tools.nsc.interpreter.Line$$anonfun$1.apply$mcV$sp(Line.scala:43)
    at scala.tools.nsc.io.package$$anon$2.run(package.scala:25)
    at java.lang.Thread.run(Thread.java:680)

Update 2:

The problem with the code above is the line nodes += (1->null) the key should be associated with Nil instead. Below is the working code.

scala> var nodes = Map.empty[Int, List[String]]
nodes: scala.collection.immutable.Map[Int,List[String]] = Map()

scala> nodes += (1->Nil)

scala> nodes += (1 -> ("one" :: (nodes get 1 getOrElse Nil)))

scala> nodes
res27: scala.collection.immutable.Map[Int,List[String]] = Map(1 -> List(one))

Answer 1

Using MultiMap

You possibly want to use MultiMap, which is a mutable collection isomorphic to Map[K, Set[V]]. Use as follows:

import collection.mutable
val mm = new mutable.HashMap[Int, mutable.Set[String]] with mutable.MultiMap[Int, String]

Then you add your nodes:

mm addBinding (key, value)

Without MultiMap

The alternative is to stick with immutable values. Assuming you want to avoid using lenses (see scalaz), you can add nodes as follows:

nodes += (key -> (value :: (nodes get key getOrElse Nil)))

Here it is working (in response to your comment):

scala> var nodes = Map.empty[Int, List[String]]
nodes: scala.collection.immutable.Map[Int,List[String]] = Map()

scala> def addNode(key: Int, value: String) =
     | nodes += (key -> (value :: (nodes get key getOrElse Nil)))
addNode: (key: Int, value: String)Unit

scala> addNode(1, "Hi")

scala> addNode(1, "Bye")

scala> nodes
res2: scala.collection.immutable.Map[Int,List[String]] = Map(1 -> List(Bye, Hi))

Using Scalaz

Using the scalaz library, you can realize that this is simply using the Empty pattern:

nodes += (key -> (value :: ~(nodes get key)))

Or you could take advantage of the fact that Map is a monoid:

nodes = nodes |+| Map(key -> List(value))

Answer 2

In addition to @oxbow_lakes' answer, here's a idea for how you could use an addMap method that correctly adds two maps together (ie, combining lists for matching keys, adding new lists for new keys):

class EnhancedListMap(self: Map[Int,List[String]]) {
  def addMap(other: Map[Int,List[String]]) =
    (this.ungroup ++ enhanceListMap(other).ungroup)
      .groupBy(_._1)
      .mapValues(_.map(_._2))

  def ungroup() =
    self.toList.flatMap{ case (k,vs) => vs.map(k -> _) }
}

implicit def enhanceListMap(self: Map[Int,List[String]]) = new EnhancedListMap(self)

And you'd use it like this:

val a = Map(1 -> List("a","b"), 2 -> List("c","d"))
val b = Map(2 -> List("e","f"), 3 -> List("g","h"))
a addMap b
//Map(3 -> List(g, h), 1 -> List(a, b), 2 -> List(c, d, e, f))

You can include addNode, addValue, and addValues the same way (to EnhancedListMap above):

  def addNode(key: Int) =
    if(self contains key) self else self + (key -> Nil)

  def addValue(key: Int, value: String) =
    self + (key -> (value :: (self get key getOrElse Nil)))

  def addValues(key: Int, values: List[String]) =
    self + (key -> (values ::: (self get key getOrElse Nil)))

And then use them together:

var nodes = Map.empty[Int, List[String]]             
// Map()
nodes = nodes.addNode(1)                             
// Map(1 -> List())
nodes = nodes.addValue(1,"a")                        
// Map(1 -> List(a))
nodes = nodes.addValue(2,"b")                        
// Map(1 -> List(a), 2 -> List(b))
nodes = nodes.addValues(2,List("c","d"))             
// Map(1 -> List(a), 2 -> List(c, d, b))
nodes = nodes.addValues(3,List("e","f"))             
// Map(1 -> List(a), 2 -> List(c, d, b), 3 -> List(e, f))
nodes = nodes.addMap(Map(3 -> List("g","h"), 4-> List("i","j")))
// Map(1 -> List(a), 2 -> List(c, d, b), 3 -> List(e, f, g, h), 4 -> List(i, j))

Answer 3

I quite like the getOrElseUpdate method provided by mutable maps:

import scala.collection.mutable._

private val nodes = new HashMap[Int, Buffer[String]]

def addNode(key: Int): Unit =
  nodes.getOrElseUpdate(key, new ArrayBuffer)

def addValue(key: Int, value: String): Unit  =
  nodes.getOrElseUpdate(key, new ArrayBuffer) += value