workaround for prepending to a LinkedHashMap in Scala?

Question

I have a LinkedHashMap which I've been using in a typical way: adding new key-value pairs to the end, and accessing them in order of insertion. However, now I have a special case where I need to add pairs to the "head" of the map. I think there's some functionality inside the LinkedHashMap source for doing this, but it has private accessibility.

I have a solution where I create a new map, add the pair, then add all the old mappings. In Java syntax:

newMap.put(newKey, newValue) 
newMap.putAll(this.map)
this.map = newMap

It works. But the problem here is that I then need to make my main data structure (this.map) a var rather than a val.

Can anyone think of a nicer solution? Note that I definitely need the fast lookup functionality provided by a Map collection. The performance of a prepending is not such a big deal.

More generally, as a Scala developer how hard would you fight to avoid a var in a case like this, assuming there's no foreseeable need for concurrency? Would you create your own version of LinkedHashMap? Looks like a hassle frankly.

Answer 1

Have you taken a look at the code of LinkedHashMap? The class has a field firstEntry, and just by taking a quick peek at updateLinkedEntries, it should be relatively easy to create a subclass of LinkedHashMap which only adds a new method prepend and updateLinkedEntriesPrepend resulting in the behavior you need, e.g. (not tested):

private def updateLinkedEntriesPrepend(e: Entry) {
    if (firstEntry == null) { firstEntry = e; lastEntry = e }
    else {
        val oldFirstEntry = firstEntry
        firstEntry = e
        firstEntry.later = oldFirstEntry
        oldFirstEntry.earlier = e
    }
}

---

Here is a sample implementation I threw together real quick (that is, not thoroughly tested!):

class MyLinkedHashMap[A, B] extends LinkedHashMap[A,B] {

  def prepend(key: A, value: B): Option[B] = {
    val e = findEntry(key)
    if (e == null) {
      val e = new Entry(key, value)
      addEntry(e)
      updateLinkedEntriesPrepend(e)
      None
    } else {
      // The key already exists, so we might as well call LinkedHashMap#put
      put(key, value)
    }
  }

  private def updateLinkedEntriesPrepend(e: Entry) {
    if (firstEntry == null) { firstEntry = e; lastEntry = e }
    else {
      val oldFirstEntry = firstEntry
      firstEntry = e

      firstEntry.later = oldFirstEntry
      oldFirstEntry.earlier = firstEntry
    }
  }

}

Tested like this:

object Main {

 def main(args:Array[String]) {
    val x = new MyLinkedHashMap[String, Int]();

    x.prepend("foo", 5)
    x.prepend("bar", 6)
    x.prepend("olol", 12)

    x.foreach(x => println("x:" + x._1 + " y: " + x._2  ));
  }

}

Which, on Scala 2.9.0 (yeah, need to update) results in

x:olol y: 12
x:bar y: 6
x:foo y: 5 

---

A quick benchmark shows order of magnitude in performance difference between the extended built-in class and the "map rewrite" approach (I used the code from Debilski's answer in "ExternalMethod" and mine in "BuiltIn"):

 benchmark length        us linear runtime
ExternalMethod     10   1218.44 =
ExternalMethod    100   1250.28 =
ExternalMethod   1000  19453.59 =
ExternalMethod  10000 349297.25 ==============================
       BuiltIn     10      3.10 =
       BuiltIn    100      2.48 =
       BuiltIn   1000      2.38 =
       BuiltIn  10000      3.28 =

The benchmark code:

  def timeExternalMethod(reps: Int) = {
    var r = reps
    while(r > 0) {
      for(i <- 1 to 100) prepend(map, (i, i))
      r -= 1
    }
  }

  def timeBuiltIn(reps: Int) = {
    var r = reps
    while(r > 0) {
      for(i <- 1 to 100) map.prepend(i, i)
      r -= 1
    }
  }

Using a scala benchmarking template.

Answer 2

This will work but is not especially nice either:

import scala.collection.mutable.LinkedHashMap

def prepend[K,V](map: LinkedHashMap[K,V], kv: (K, V)) = {
  val copy = map.toMap
  map.clear
  map += kv
  map ++= copy
}

val map = LinkedHashMap('b -> 2)
prepend(map, 'a -> 1)
map == LinkedHashMap('a -> 1, 'b -> 2)