MultiSet, MultiMap, BidiMap

[Landei]

Hello,

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
structure.

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.

Cheers,
Daniel

[Miles Sabin]

On Sat, Dec 26, 2009 at 10:42 AM, Landei <daniel...@googlemail.com> 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.

Cheers,

Miles

--
Miles Sabin
tel: +44 (0)7813 944 528
skype: milessabin
http://www.chuusai.com/
http://twitter.com/milessabin

[Landei]

Hi!

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,
B]{
self => if (wrapped.size != inverse.size)
throw new IllegalArgumentException("Duplicate values are not
permitted.")

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) +
kv,
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]() ++
ws)
def apply[K, V](wrapped: Map[K,V]): BidiMap[K, V] =
new BidiMap(wrapped, wrapped.map(tuple => tuple.swap))
}
===========================

What do you think, could this be useful?

Cheers,
Daniel

On 26 Dez., 15:47, Miles Sabin <mi...@milessabin.com> wrote:

[Jeff Olson]

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]

Hi,

where is this code located, can we see it?

Cheers,

Alex

[Jeff Olson]

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)

    m

  }

  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)

    this

  }

  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

    this

  }

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

    removeBinding(kv._1, kv._2)

    this

  }

  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))

    i

  }

  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]

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]

      builder.sizeHint(from.size)

      builder

    }

  }

  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

      this

    }

    override def sizeHint(size: Int): Unit = elems.sizeHint(size)

  }

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

}

[Daniel Sobral]

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]

Here you go:

https://gist.github.com/1566605

https://gist.github.com/1566619

-Jeff