MultiSet, MultiMap, BidiMap

Skip to first unread message


Dec 26, 2009, 5:42:34 AM12/26/09
to Scala Incubator

As suggested by Erik Engbrecht, I moved this topic from Scala-Debate
to this group. Here is the original message:

I think the new Scala Collection Framework could be a good reason to
discuss about additional data structures. I'm especially missing
MultiSet (a.k.a Bag), MultiMap and BidiMap. Of course it's easy to
come up with own implementations based on the existing classes (and
I'm pretty sure there are already some of these around), however I
think it is important that these classes fit into the new framework

What I want to discuss here is:
- Should these classes be part of the Scala distribution? If not, what
would be an approriate place?
- How should the interfaces look like, given the structure and the
limitations of the new framework?

What do you think?

I have already an ugly, but mostly working immutable proof-of-concept
implementation of MultiSet, using internally an immutable HashMap (the
Builder part makes still problems). However I'd prefer to start over
with a better, accepted interface design rather than bending the
existing mess in shape.


Miles Sabin

Dec 26, 2009, 9:47:22 AM12/26/09
On Sat, Dec 26, 2009 at 10:42 AM, Landei <> wrote:
> As suggested by Erik Engbrecht, I moved this topic from Scala-Debate
> to this group. Here is the original message:

Good idea.

I think discussion around these additional data structures would be
very appropriate here. If you have code that you'd like to share then
let me know and I'll set up a repository for it on the Scala Incubator
github account.



Miles Sabin
tel: +44 (0)7813 944 528
skype: milessabin


Dec 28, 2009, 5:13:57 PM12/28/09
to Scala Incubator

Instead of going crazy with MultiSet, I tried to solve an easier
problem, an immutable bidirectional Map. I think a separate collection
type for bidirectional maps would be quite stupid, so I extended Map.
I'm not really happy with the + method, maybe you can give me a hint
how to deal with the variance here.

The file is quite short, so I hope it's fine to include it directly:

package scala.collection.immutable

class BidiMap[A, B] private(private wrapped: Map[A, B],
private inverse: Map[B, A]) extends Map[A,
self => if (wrapped.size != inverse.size)
throw new IllegalArgumentException("Duplicate values are not

lazy val inverseMap:BidiMap[B, A] = new BidiMap[B, A](inverse,
wrapped) {
override lazy val inverseMap = self
def inverseIterator: Iterator[(B, A)] = inverseMap.iterator

override def get(key: A): Option[B] = wrapped.get(key)

override def iterator: Iterator[(A, B)] = wrapped.iterator

override def + [B1 >: B] (kv: (A, B1)): BidiMap[A, B1] = {
val inverseWidened: Map[B1, A] = inverse match {
case _: Map[B1, A] => inverse
case _ => Map[B1, A]() ++ inverse
new BidiMap[A, B1](
inverseWidened.get(kv._2).map(wrapped - _).getOrElse(wrapped) +
inverseWidened + kv.swap)

override def - (key: A): BidiMap[A, B] = wrapped.get(key).map(value
new BidiMap(wrapped - key, inverse - value)).getOrElse(this)

override def empty: BidiMap[A, B] = BidiMap[A, B]()

override def size = wrapped.size

object BidiMap {
def apply[K, V](): BidiMap[K, V] = new BidiMap(Map[K, V](), Map[V, K]
def apply[K, V](ws : (K, V)*): BidiMap[K, V] = BidiMap(Map[K,V]() ++
def apply[K, V](wrapped: Map[K,V]): BidiMap[K, V] =
new BidiMap(wrapped, => tuple.swap))

What do you think, could this be useful?


On 26 Dez., 15:47, Miles Sabin <> wrote:

Jeff Olson

Jan 4, 2012, 11:16:22 AM1/4/12
I have code for a (mutable) MultiMap I would be happy to contribute.

Along these lines I would like to see HashMap/HashSet collections that used an arbitrary Equiv[T] implicit rather than using == for determining equality. I have code for an IdentityHashMap that could be easily be converted.

Aleksandar Prokopec

Jan 5, 2012, 5:36:58 AM1/5/12

where is this code located, can we see it?


Jeff Olson

Jan 5, 2012, 12:35:05 PM1/5/12
it's here:

import scala.collection.mutable.{Set, Map, Iterable, Builder, Cloneable}
import scala.collection.generic.{CanBuildFrom, Shrinkable}
import scala.collection.{Iterator, IterableLike, breakOut}

object MultiMap {
  type Coll = MultiMap[_, _]

  implicit def canBuildFrom[A, B] = new CanBuildFrom[Coll, (A, B), MultiMap[A, B]] {
    def apply() = newBuilder[A, B]
    def apply(from: Coll) = newBuilder[A, B]

  def newBuilder[A, B]: Builder[(A, B), MultiMap[A, B]] = empty

  def empty[A, B] = new MultiMap(Map.empty[A, Set[B]])

  def apply[A, B](elems: (A, B)*) = (newBuilder[A, B] ++= elems).result()

  def apply[A, B](elems: TraversableOnce[(A, B)]): MultiMap[A, B] = (newBuilder[A, B] ++= elems).result()

  def buildFrom[A, B](from: TraversableOnce[(A, TraversableOnce[B])]) = {
    val m = empty[A, B]
    for ((k, vs) <- from) m.addBindings(k, vs)

  private val hashSeed = "MultiMap".hashCode

class MultiMap[A, B] private (m: Map[A, Set[B]])
    extends Iterable[(A, B)]
       with IterableLike[(A, B), MultiMap[A, B]]
       with Builder[(A, B), MultiMap[A, B]]
       with Shrinkable[(A, B)]
       with Cloneable[MultiMap[A, B]]
{ self =>

  def empty = MultiMap.empty

  override protected[this] def newBuilder = MultiMap.newBuilder

  override def clone = MultiMap.buildFrom(m)

  def iterator: Iterator[(A, B)] = for ((k, vs) <- m.iterator; v <- vs.iterator) yield (k, v)

  def get(key: A): Set[B] = m.getOrElse(key, Set.empty[B])

  def clear(): Unit = m.clear()

  def result() = this

  def contains(key: A): Boolean = get(key).nonEmpty
  def contains(key: A, value: B): Boolean = get(key).contains(value)
  def contains(kv: (A, B)): Boolean = contains(kv._1, kv._2)

  def + [B1 >: B] (kv: (A, B1)): MultiMap[A, B1] = clone.asInstanceOf[MultiMap[A, B1]] += kv

  def += (kv: (A, B)): this.type = {
    addBinding(kv._1, kv._2)

  def addBinding(key: A, value: B) {
    m.getOrElseUpdate(key, Set.empty[B]) += value

  def addBindings(key: A, values: TraversableOnce[B]) {
    m.getOrElseUpdate(key, Set.empty[B]) ++= values

  def - (key: A) = clone -= key

  /** Remove all bindings for the given key */
  def -= (key: A): this.type = {
    m -= key

  def -= (kv: (A, B)): this.type = {
    removeBinding(kv._1, kv._2)

  def removeBinding(key: A, value: B): Unit = m.get(key) match {
    case Some(vs) => if ((vs -= value).isEmpty) m -= key
    case None =>

  def removeBindings(key: A, values: Traversable[B]): Unit = m.get(key) match {
    case Some(vs) => if ((vs --= values).isEmpty) m -= key
    case None =>

  override def equals(that: Any): Boolean = that match {
    case that: MultiMap[a, _] => (this eq that) || (that canEqual this) && (this.size == that.size) && {
      try {
        m.forall { case (k, vs) => that.get(k.asInstanceOf[a]) == vs }
      catch { case _: ClassCastException => false }
    case _ => false

  override def hashCode = util.MurmurHash.symmetricHash(this, MultiMap.hashSeed)

  def asMap: Map[A, Set[B]] = m

  def inverse: MultiMap[B, A] = {
    val i = MultiMap.empty[B, A]
    foreach((k, v) => i.addBinding(v, k))

  def keys: collection.Iterable[A] = m.keys
  def keySet: collection.Set[A] = m.keySet
  def keysIterator: Iterator[A] = m.keysIterator

  def values: collection.Iterable[B] = new collection.Iterable[B] {
    def iterator = self.valuesIterator
    override def size = self.size
    override def foreach[U](f: B => U) = self.foreach((k, v) => f(v))
  def valueSet: collection.Set[B] = m.flatMap { case (_, vs) => vs } (breakOut)
  def valuesIterator: Iterator[B] = m.valuesIterator.flatMap(_.iterator)

  // overrides for efficiency

  override def foreach[U](f: ((A, B)) => U): Unit = foreach(Function.untupled(f))

  def foreach[U](f: (A, B) => U): Unit = for ((k, vs) <- m; v <- vs) f(k, v)

  override def size = m.foldLeft(0) { case (n, (_, vs)) => n + vs.size }

  override def stringPrefix = "MultiMap"

Jeff Olson

Jan 5, 2012, 12:37:07 PM1/5/12
and here: 

import scala.collection.generic.CanBuildFrom
import scala.collection.mutable.{MapLike, MapBuilder, HashMap}

final class IdentityHashMap[A <: AnyRef, B]() extends HashMap[A, B] with MapLike[A, B, IdentityHashMap[A, B]] {
  override protected def elemEquals(key1: A, key2: A): Boolean = key1 eq key2

  override protected def elemHashCode(key: A) = System.identityHashCode(key)

  override def empty: IdentityHashMap[A, B] = IdentityHashMap.empty

  //can't do this: resize is private in HashTable!!
  //override def sizeHint(size: Int): Unit = resize(size)

object IdentityHashMap {
  type Coll = IdentityHashMap[_, _]

  implicit def canBuildFrom[A <: AnyRef, B] = new CanBuildFrom[Coll, (A, B), IdentityHashMap[A, B]] {
    def apply() = newBuilder[A, B]
    def apply(from: Coll) = {
      val builder = newBuilder[A, B]

  def empty[A <: AnyRef, B]: IdentityHashMap[A, B] = new IdentityHashMap[A, B]

  def newBuilder[A <: AnyRef, B] = new MapBuilder[A, B, IdentityHashMap[A, B]](empty[A, B]) {
    override def +=(x: (A, B)): this.type = {
      elems += x
    override def sizeHint(size: Int): Unit = elems.sizeHint(size)

  def apply[A <: AnyRef, B](elems: (A, B)*) = (newBuilder[A, B] ++= elems).result()

Daniel Sobral

Jan 5, 2012, 12:55:27 PM1/5/12
Can't you put it in a gist at github, at least? If you don't have
github account, you can create one for free, click on new gist, and
paste this there.

Daniel C. Sobral

I travel to the future all the time.

Jeff Olson

Jan 5, 2012, 1:51:01 PM1/5/12
Reply all
Reply to author
0 new messages