Most high-level programming languages provide structures that implement associative arrays, otherwise known as dictionaries. These structures allow storing a set of values associated with objects - keys - in such a way that searching for values based on a key is very fast. Scala has standard dictionaries using hash tables(HashMap) and red-black trees(TreeMap). Both implementations are available in mutable and non-mutable versions.
But what if you want to associate more than one object-value with a single key? The easiest way is to use an ordinary dictionary but instead of a single value object use a set of values. For example, we want to construct a multi-dictionary storing information about user roles:
import scala.collection.mutable.HashMap case class User(name: String) case class Role(name: String) val roles = new HashMap[User, Set[Role]]
To add some data to such a dictionary, we can write:
roles += (User("Bob") -> Set(Role("User"))) roles += (User("Mike") -> Set(Role("User")))
What if we now want to promote Bob to Admin, but keeping all the other roles?
roles += (User("Bob")) -> (roles(User("Bob")) + Roles("Admin")))
Unfortunately, such a simple solution has a drawback. What happens if user Bob was not in the collection before? We will get an exception. Below is the corrected version:
roles += (User("Bob") -> (roles.getOrElse(User("Bob"), Set.empty) + Role("Admin")))
As you can see, there is a bit too much code for such a simple action. With help comes scala.collection.mutable.MultiMap. With MultiMap, we will be able to add new objects directly and, most importantly, we won't forget to handle the situation when there was no key in the collection before:
import scala.collection.mutable.{MultiMap, Set} val roles = new HashMap[User, Set[Role]] with MultiMap[User, Role] roles.addBinding(User("Bob"), Role("User")) roles.addBinding(User("Bob"), Role("Admin"))
Isn't that much simpler? However, two things should be noted in doing so: Set must be imported from the mutable package, not the default one, and we parameterize MultiMap directly with the Role class, not Set[Role]. Otherwise we will get a compilation error.
You can say that this is the end of this entry, because after all, the title multiword was finally created. However, we overlooked a detail: all the examples presented here are based on mutable collections. In Scala, on the other hand, the recommended way is to program with non-mutable collections (why this is so, and why it's an overall better application design strategy, is a topic for a separate entry). Unfortunately, as we look more closely at the API, we can't find there the interface scala.collection.immutable.MultiMap . Moreover, if we do not control the code that creates the dictionary, we have no way to decorate it with MultiMap goodness. So are we reliant on inconveniently operating a simple dictionary as if it were a MultiMap? Fortunately, no. Only this time we have to work a little harder.
Scala has a very powerful automatic conversion mechanism. When we need to call a non-existent method on an object, an attempt will be made to convert that object to another object that has that method. In this way, you can add new methods to classes, without modifying their code, by providing the appropriate conversions. That is, you can also add addBinding and removeBinding methods to any object of class Map[_, Set[_]]:
import collection.generic.CanBuildFrom object MultiMapUtil { class MultiMap[K, V, M <: Map[K, Set[V]]](map: M, emptySet: Set[V])
{
def addBinding(k: K, v: V): M =
(map + (k -> (map.getOrElse(k, emptySet) + v))).asInstanceOf[M] def removeBinding(k: K, v: V): M = { val r = (map.getOrElse(k, emptySet) - v) (if (r.isEmpty) map - k else map + (k -> r)).asInstanceOf[M] } } implicit def mapToMultiMap[K, V, S[V] <: Set[V], M[K, S] <: Map[K, S]] (map: M[K, S[V]])(implicit bf: CanBuildFrom[Nothing, V, S[V]]) = new MultiMap[K, V, M[K, S[V]]](map, bf.apply.result) }
What's going on here? We define a new MultiMap class, which provides the desired addBinding and removeBinding methods that operate on the dictionary object passed in the object constructor. The constructor additionally needs an object representing an empty collection. The default empty set Set.empty cannot be permanently written into the code, as the user may want to operate on another set implementation such as TreeSet.
The implicit mapToMultiMap method is responsible for creating objects of our MultiMap class from objects of any Map subclass. The implicit keyword tells the compiler that it can insert a call to this method on its own to perform the appropriate conversion. The parameters of the K, V, S and M types denote, in turn, the key type, the value type, the type of set used to store the value and the dictionary type. You don't need to specify them, the compiler will match the appropriate types on its own based on the type of object given as the method's argument.
The second argument of the mapToMultiMap method is an object implementing the CanBuildFrom interface. CanBuildFrom objects provide factories for producing collections - in this case, this object was used to create an empty collection of type S[V]. Scala's standard library contains CanBuildFrom implementations for all standard collection types. Since the argument has been marked as implicit, the corresponding implementation of CanBuildFrom will be substituted by the compiler automatically. It's worth getting to know this mechanism more thoroughly, because many methods in the standard library use it.
Finally, a REPL session showing the use of the above code:
scala> import MultiMapUtil._ import MultiMapUtil._ scala> val roles1 = Map.empty[User, Set[Role]] roles1: scala.collection.immutable.Map[User,Set[Role]]] = Map() scala> val roles2 = roles1.addBinding(User("Kowalski"), Role("User")) roles2: scala.collection.immutable.Map[User,Set[Role]] = Map((User(Kowalski),Set(Role(User)))) scala> val roles3 = roles2.addBinding(User("Kowalski"), Role("Admin")) roles3: scala.collection.immutable.Map[User,Set[Role]] = Map((User(Kowalski),Set(Role(User), Role(Admin))))
It works with other dictionary and set classes too - please pay attention to the result type and key order:
import scala.collection.immutable.TreeMap import scala.collection.immutable.TreeSet scala> val m = TreeMap[String, TreeSet[Int]]() m: scala.collection.immutable.TreeMap[String, scala.collection.immutable.TreeSet[Int]] = Map() scala> m.addBinding("a", 10).addBinding("b", 20).addBinding("a", 15) res3: scala.collection.immutable.TreeMap[String, scala.collection.immutable.TreeSet[Int]]] = Map((a,TreeSet(10, 15)), (b,TreeSet(20)))
