Eine bidirektionale Map


Eine hin und wieder nützliche Datenstruktur ist eine bidirektionale Map, auch wenn sie in den Java und Scala Collections fehlt. Dafür findet man sie in den Apache Commons Collections oder den Google Collections. Eine bidirektionale Map sind eigentlich zwei Rücken-an-Rücken geklebte normale Maps, die automatisch synchron gehalten werden. Hat man etwa eine bidirektionale Map von Ländern und Hauptstädten, kann man nicht nur die Hauptstadt von einem Land, sondern auch das Land zu einer Hauptstadt finden.

Hier eine kleine Implementierung für unveränderliche bidirektionale Maps in Scala 2.8:

//Scala 2.8
package scala.collection.immutable

class BidiMap[A, B] private(private wrapped: Map[A, B], 
                            private inverse: Map[B, A]) extends Map[A, B]{
  self =>  if (wrapped.size != inverse.size) 
    throw new IllegalArgumentException("Duplicate values are not permitted.")

  lazy val inverseMap:BidiMap[B, A] = new BidiMap[B, A](inverse, wrapped) {
    override lazy val inverseMap = self
  }
  def inverseIterator: Iterator[(B, A)] = inverseMap.iterator

  override def get(key: A): Option[B] = wrapped.get(key)

  override def iterator: Iterator[(A, B)] = wrapped.iterator

  override def + [B1 >: B] (kv: (A, B1)): BidiMap[A, B1] = {
    val inverseWidened: Map[B1, A] = inverse match {
      case _: Map[B1, A] => inverse
      case _ => Map[B1, A]() ++ inverse
    }
    new BidiMap[A, B1](
      inverseWidened.get(kv._2).map(wrapped - _).getOrElse(wrapped) + kv,
      inverseWidened + kv.swap)
  }

  override def - (key: A): BidiMap[A, B] = wrapped.get(key).map(value =>
      new BidiMap(wrapped - key, inverse - value)).getOrElse(this)

  override def empty: BidiMap[A, B] = BidiMap[A, B]()

  override def size = wrapped.size

  override def stringPrefix: String = "BidiMap"
}

object BidiMap {
  def apply[K, V](): BidiMap[K, V] = new BidiMap(Map[K, V](), Map[V, K]())
  def apply[K, V](ws : (K, V)*): BidiMap[K, V] = BidiMap(Map[K,V]() ++ ws)
  def apply[K, V](wrapped: Map[K,V]): BidiMap[K, V] =
     new BidiMap(wrapped, wrapped.map(tuple => tuple.swap))
}

Ein kleiner Test:

val b1 = BidiMap(1 -> "one", 2 -> "two", 3 -> "three")
println(b1)
//--> BidiMap(1 -> one, 2 -> two, 3 -> three)
println(b1.inverseMap)
//--> BidiMap(one -> 1, two -> 2, three -> 3)
val b2 =  b1 + (4 -> "four")
println(b2)
//--> BidiMap(1 -> one, 2 -> two, 3 -> three, 4 -> four)
println(b2.inverseMap)
//--> BidiMap(one -> 1, two -> 2, three -> 3, four -> 4)

Wurde ja auch Zeit, dass ich mal wieder etwas praktischeres als Unlambda-Interpreter und so präsentiere…

Die Implementierung ist ziemlich minimalistisch und vermulich zu umständlich. Falls jemand Ideen dazu haben sollte, nur her damit (insbesondere, wie man die Varianz in der Plus-Methode eleganter behandeln kann).

So, dann wünsche ich allen einen unfallfreien Rutsch und ein gesundes, erfolgreiches und glückliches neues Jahr!

Advertisements

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s