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

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 `ListMap`s.

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