[ACCEPTED]-Immutable Scala Map implementation that preserves insertion order-immutability

Accepted answer
Score: 64

ListMap implements an immutable map using a list-based 3 data structure, and thus preserves insertion 2 order.

scala> import collection.immutable.ListMap
import collection.immutable.ListMap

scala> ListMap(1 -> 2) + (3 -> 4)
res31: scala.collection.immutable.ListMap[Int,Int] = Map(1 -> 2, 3 -> 4)

scala> res31 + (6 -> 9)
res32: scala.collection.immutable.ListMap[Int,Int] = Map(1 -> 2, 3 -> 4, 6 -> 9)

The following extension method - Seq#toListMap can 1 be quite useful when working with ListMaps.

scala> import scalaz._, Scalaz._, Liskov._
import scalaz._
import Scalaz._
import Liskov._

scala> :paste
// Entering paste mode (ctrl-D to finish)

implicit def seqW[A](xs: Seq[A]) = new SeqW(xs)
class SeqW[A](xs: Seq[A]) {
  def toListMap[B, C](implicit ev: A <~< (B, C)): ListMap[B, C] = {
    ListMap(co[Seq, A, (B, C)](ev)(xs) : _*)  
  }
}


// Exiting paste mode, now interpreting.

seqW: [A](xs: Seq[A])SeqW[A]
defined class SeqW

scala> Seq((2, 4), (11, 89)).toListMap
res33: scala.collection.immutable.ListMap[Int,Int] = Map(2 -> 4, 11 -> 89)
Score: 25

While ListMap will preserve insertion order, it 19 is not very efficient - e.g. lookup time 18 is linear. I suggest you create a new collection 17 class which wraps both the immutable.HashMap and the immutable.TreeMap. The 16 immutable map should be parametrized as 15 immutable.HashMap[Key, (Value, Long)], where the Long in the tuple gives you the 14 pointer to the corresponding entry in the 13 TreeMap[Long, Key]. You then keep an entry counter on the 12 side. This tree map will sort the entries 11 according to the insertion order.

You implement 10 insertion and lookup in the straightforward 9 way - increment the counter, insert into 8 the hash map and insert to the the counter-key 7 pair into the treemap. You use the hash 6 map for the lookup.

You implement iteration 5 by using the tree map.

To implement remove, you 4 have to remove the key-value pair from the 3 hash map and use the index from the tuple 2 to remove the corresponding entry from the 1 tree map.

More Related questions