Exploration of Map data-structures

MBiMap.scala

import java.util.NoSuchElementException

trait MBiMap[K, V] {
  def insert(k: K, v: V): MBiMap[K,  V]
  def remove(k: K): MBiMap[K, V]
  def lookup(k: K): V
}

object MBiMap {

  private trait AbstractBiMap[K, V] extends MBiMap[K, V] {
    def insert(k: K, v: V) = InsertedElement(k, v, this)
    def remove(k: K) = RemovedElement(k, this)
  }
  
  def empty[K, V]: MBiMap[K, V] = new AbstractBiMap[K, V] {
    def lookup(k: K) = throw new NoSuchElementException("Key not found")
  }

  private case class InsertedElement[K, V]
          (k: K, v: V, next: MBiMap[K, V])
        extends AbstractBiMap[K, V]
  {
    def lookup(k: K): V = if(k == this.k) v else {
      val nv = next apply k
      if(nv == v) throw new NoSuchElementException("Key not found")
      else nv
    }
  }

  private case class RemovedElement[K, V]
          (k: K, next: MBiMap[K, V])
        extends AbstractBiMap[K, V]
  {
    def lookup(k: K): V =
      if(k != this.k) next apply k
      else throw new NoSuchElementException("Key not found")
  }
}

MMap.scala

import java.util.NoSuchElementException

trait MMap[K, V] {
  def insert(k: K, v: V): MMap[K,  V]
  def remove(k: K): MMap[K, V]
  def lookup(k: K): V
}

object MMap {

  private trait AbstractMap[K, V] extends MMap[K, V] {
    def insert(k: K, v: V) = InsertedElement(k, v, this)
    def remove(k: K) = RemovedElement(k, this)
  }
  
  def empty[K, V]: MMap[K, V] = new AbstractMap[K, V] {
    def lookup(k: K) = throw new NoSuchElementException("Key not found")
  }

  private case class InsertedElement[K, V]
          (k: K, v: V, next: MMap[K, V])
        extends AbstractMap[K, V]
  {
    def lookup(k: K): V = if(k == this.k) v else next apply k
  }

  private case class RemovedElement[K, V]
          (k: K, next: MMap[K, V])
        extends AbstractMap[K, V]
  {
    def lookup(k: K): V =
      if(k != this.k) next apply k
      else throw new NoSuchElementException("Key not found")
  }
}

MMultiMap.scala

import java.util.NoSuchElementException

trait MMultiMap[K, V] {
  def insert(k: K, v: V): MMultiMap[K, V]
  def remove(k: K, v: V): MMultiMap[K, V]
  def lookup(k: K): Set[V]
}

object MMultiMap {

  private trait AbstractMultiMap[K, V] extends MMultiMap[K, V] {
    def insert(k: K, v: V) = InsertedElement(k, v, this)
    def remove(k: K) = RemovedElement(k, v, this)
  }
  
  def empty[K, V]: MMultiMap[K, V] = new AbstractMultiMap[K, V] {
    def lookup(k: K) = Set.empty
  }

  private case class InsertedElement[K, V]
          (k: K, v: V, next: MMultiMap[K, V])
        extends AbstractMultiMap[K, V]
  {
    def lookup(k: K) =
      if(k == this.k) (next lookup k) + v
      else next lookup k
  }

  private case class RemovedElement[K, V]
          (k: K, v: V, next: MMultiMap[K, V])
        extends AbstractMultiMap[K, V]
  {
    def lookup(k: K): V =
      if(k == this.k) (next lookup k) - v
      else next lookup k
  }
}

MPriorityQueue.scala

import java.util.NoSuchElementException

trait MPriorityQueue[K, P] {
  def insert(k: K, p: P): MPriorityQueue[K,  P]
  def remove(k: K): MPriorityQueue[K, P]
  def lookup(k: K): P
}

object MPriorityQueue {

  private trait AbstractPriorityQueue[K, P] extends MPriorityQueue[K, P] {
    def insert(k: K, p: P) = InsertedElement(k, p, this)
    def remove(k: K) = RemovedElement(k, this)
  }
  
  def empty[K, P]: MPriorityQueue[K, P] = new AbstractPriorityQueue[K, P] {
    def lookup(k: K) = throw new NoSuchElementException("Key not found")
  }

  private case class InsertedElement[K, P]
          (k: K, p: P, next: MPriorityQueue[K, P])
        extends AbstractPriorityQueue[K, P]
  {
    def lookup(k: K): P =
      if(k == this.k) {
        try {
          val nv = next apply k
          if(v > nv) v else nv
        } catch {
          case e : NoSuchElementException => v
        }
      } else next apply k
  }

  private case class RemovedElement[K, V]
          (k: K, next: MPriorityQueue[K, V])
        extends AbstractPriorityQueue[K, V]
  {
    def lookup(k: K): V =
      if(k != this.k) next apply k
      else throw new NoSuchElementException("Key not found")
  }
}