O(1) conversion from mutable.Map to immutable.Map?

Is there a way to convert (wrap) a mutable Map to immutable in O(1) time (that is, not by copying the values, but simi开发者_如何学Clar to what is done in JavaConversions)

As Thomas points out, the read only view is O(1). But read-only doesn't equate to immutability.

The difference is well descrived in the "Fighting Bit Rot" paper:

All collection classes are kept in a package scala.collection. This package has three subpackages: mutable, immutable, and generic. Most collections exist in three forms, depending on their mutability.

A collection in package scala.collection.immutable is guaranteed to be immutable for everyone. That means one can rely on the fact that accessing the same collection value over time will always yield a collection with the same elements. A collection in package scala.collection.mutable is known to have some operations that change the collection in place.

A collection in package scala.collection can be either mutable or immutable. For instance, collection.Seq[T] is a superclass of both collection.immutable.Seq[T] and collection.mutable.Seq[T]. Generally, the root collections in package scala. collection define the same interface as the immutable collections, and the mutable collections in package scala.collection.mutable typically add some destructive modification operations to this immutable interface. The difference between root collections and immutable collections is that a user of an immutable collection has a guarantee that nobody can mutate the collection, whereas users of root collections have to assume modifications by others, even though they cannot do any modifications themselves.

Perhaps it's just a simple as up-casting.

scala> val mm = collection.mutable.Map(1 -> 2)
mm: scala.collection.mutable.Map[Int,Int] = Map(1 -> 2)

scala> val readOnly = mm : collection.Map[Int, Int]
readOnly: scala.collection.Map[Int,Int] = Map(1 -> 2)

There is a read only projection for mutable maps.

scala> collection.mutable.Map(1->2).readOnly
res0: scala.collection.Map[Int,Int] = ro-Map(1 -> 2)

As oxbow_lakes pointed out the underlying Map is still mutable and may change after the read-only projection is published to clients. The illusion of immutability has to addressed in code managing the map.

What you are asking for is inherently unsafe. You can either pass the mutable.Map around as a collection.Map which is immutable but "clients" using this form cannot be sure that their view will not change from under them.

One could in principle add a "freeze" method to a mutable data structure that prevented further mutation. This is the only even slightly-safe way to do the wrapping. (Only slightly because after that you'd have to throw exceptions when you tried to mutate it.) Scala's mutable collections don't have this capability, however. One could add it to e.g. mutable.HashMap by overriding all mutating methods (update, +=, ++=, etc.), but this would be a fair bit of work.

Philipp Haller's work on Capabilities for Uniqueness and Borrowing is related to this. There's a lot of other work in the domain of enforcing "ownership" through the type system, but Philipp actually provides a usable plugin to the Scala compiler.

Something like this should do, which is similar to ArraySeq.unsafeWrapArray.

class UnsafeWrappedMap[K, V](underlying: mutable.Map[K, V]) extends Map[K, V] with StrictOptimizedMapOps[K, V, Map, Map[K, V]] {
  def removed(key: K) = underlying.iterator.filter(_._1 != key).toMap

  def updated[V1 >: V](key: K, value: V1) = {
    underlying.iterator.map {
      case (`key`, _) => (key, value)
      case kv => kv
    }.toMap
  }

  def get(key: K) = underlying.get(key)

  def iterator = underlying.iterator
}

object UnsafeWrappedMap {
  def apply[K, V](underlying: mutable.Map[K, V]) = new UnsafeWrappedMap(underlying)
}

Obviously you must not touch the mutable map after creating this!

A more ambitious solution could be to create a map that, once a copy is created, sets an internal flag and any future mutation will cause the mutable instance to copy its internal state before performing mutations.