Monday, March 28, 2011

JIT Adjusted Map

One of the things I am currently working on is a Scala Kyoto Cabinet API. Kyoto Cabinet is a C++ library for accessing a very fast persistent key value store. It has a Java library, and as a consequence you can use it from Scala without a problem, but the standard Java API isn't really all that Scala-esque.

Kyoto Cabinet DB as a Map

A key value store is not all that different than a mutable Map in Scala. You pass in a key, and a value comes out. That means you can actually wrap a Kyoto Cabinet DB object by an implementation of Scala's mutable Map interface.

However, Kyoto Cabinet API only supports storing two types of values: Strings and byte arrays. In both cases, both the key and the value need to be of the same type. That means that - without doing any transformations - you can only wrap its DB object inside a Map[String,String] or a Map[Array[Byte], Array[Byte]]. That clearly leaves a lot left to be desired.



So, whatever I am going to do, it should at least (1) allow me to wrap a DB object in a Map and (2) allow me to transform keys and values to the appropriate type. I want to be able to access a Kyoto Cabinet DB as a Map[Int,Date], - if I feel like it.

Instead of addressing both concerns inside a single class, I eventually opted for factoring it out into separate classes. It seemed having a mutable Map abstraction that on the fly transforms its keys and/or values to an alternative type would be useful in other circumstances as well.

The result works like this:

import scala.collection.mutable.Map
import nl.flotsam.collectionables.mutable.AdaptableMap._
val original = Map("1" -> "a", "2" -> "b", "3" -> "e")
val adapted = map.mapKey(_.toInt)(_.toString)
adapted += (1 -> "foobar")

How is this different than just mapping it?

Note that this is definitely not the same as this:

val adapted ={ case (x,y) => (i.toInt, y) }
adapted += (1 -> "foobar")

In the second case, the entire original map is replaced by a new map. After the transformation, all keys have been transformed to an Int. In the former case, operations on 'adapted' taking keys of type Int will transform the key on the fly to the same operation taking a key of type String on the underlying Map. In some cases, transforming the entire Map in a single go might be the better option. But if you have a Kyoto Cabinet database with millions of records, then this is the last thing you want to do.

Show me the code

This is is the latest version of the code. It still is in flux, but you get the picture:

class AdaptedMap[A, B, AA, BB](decorated: Map[AA, BB],
                               a2aa: (A) => AA,
                               b2bb: (B) => BB,
                               aa2a: (AA) => A,
                               bb2b: (BB) => B) extends Map[A, B] {

  def iterator = new AdaptedMapIterator[A, B, AA, BB](decorated.iterator, aa2a, bb2b)

  def get(key: A) = decorated.get(a2aa(key)) map (bb2b(_))

  def -=(key: A) = {
    decorated -= a2aa(key)

  def +=(kv: (A, B)) = {
    val (key, value) = kv
    val adapted = (a2aa(key), b2bb(value))
    decorated += adapted

  def mapKey[C](a2c: (A) => C)(implicit c2a: (C) => A) = {
    def c2aa(c: C) = a2aa(c2a(c))
    def aa2c(aa: AA) = a2c(aa2a(aa))
    new AdaptedMap[C, B, AA, BB](decorated, c2aa, b2bb, aa2c, bb2b)

  def mapValue[C](b2c: (B) => C)(implicit c2b: (C) => B) = {
    def c2bb(c: C) = b2bb(c2b(c))
    def bb2c(bb: BB) = b2c(bb2b(bb))
    new AdaptedMap[A, C, AA, BB](decorated, a2aa, c2bb, aa2a, bb2c)


 * Providing the implicit transformation allowing you to transform an existing mutable Map into an AdaptedMap, allowing
 * you to invoke mapKey an mapValue on it.
object AdaptedMap {

  implicit def map2adaptable[A, B](map: Map[A, B]) =
    new AdaptedMap[A, B, A, B](map, identity, identity, identity, identity)


No comments:

Post a Comment