PrefixMap.scala

import scala.collection._
import scala.collection.generic.CanBuildFrom
import scala.collection.mutable.{Builder, MapBuilder}

case class Word(value: String) extends AnyVal

class WordMap extends PrefixMap[Word]

class PrefixMap[T]
  extends mutable.Map[String, T]
    with mutable.MapLike[String, T, PrefixMap[T]] {

  var suffixes: immutable.Map[Char, PrefixMap[T]] = Map.empty
  var value: Option[T] = None

  def get(s: String): Option[T] =
    if (s.isEmpty) value
    else suffixes get (s(0)) flatMap (_.get(s substring 1))

  def withPrefix(s: String): PrefixMap[T] =
    if (s.isEmpty) this
    else {
      val leading = s(0)
      suffixes get leading match {
        case None =>
          suffixes = suffixes + (leading -> empty)
        case _ =>
      }
      suffixes(leading) withPrefix (s substring 1)
    }

  override def update(s: String, elem: T) =
    withPrefix(s).value = Some(elem)

  override def remove(s: String): Option[T] =
    if (s.isEmpty) {
      val prev = value; value = None; prev
    }
    else suffixes get (s(0)) flatMap (_.remove(s substring 1))

  def iterator: Iterator[(String, T)] =
    (for (v <- value.iterator) yield ("", v)) ++
      (for ((chr, m) <- suffixes.iterator;
            (s, v) <- m.iterator) yield (chr +: s, v))

  def +=(kv: (String, T)): this.type = {
    update(kv._1, kv._2); this
  }

  def -=(s: String): this.type = {
    remove(s); this
  }

  override def empty = new PrefixMap[T]
}

object PrefixMap {
  def empty[T] = new PrefixMap[T]

  def apply[T](kvs: (String, T)*): PrefixMap[T] = {
    val m: PrefixMap[T] = empty
    for (kv <- kvs) m += kv
    m
  }

  def newBuilder[T]: Builder[(String, T), PrefixMap[T]] =
    new MapBuilder[String, T, PrefixMap[T]](empty)

  implicit def canBuildFrom[T]
  : CanBuildFrom[PrefixMap[_], (String, T), PrefixMap[T]] =
    new CanBuildFrom[PrefixMap[_], (String, T), PrefixMap[T]] {
      def apply(from: PrefixMap[_]) = newBuilder[T]

      def apply() = newBuilder[T]
    }
}

object Demo extends App {
}

I have something compiling at the expense of an asInstanceOf which I think is sound but I can't prove it :-( (so maybe I'm completely wrong):

package de.zalando.artmc.mi.config

import scala.collection.generic.CanBuildFrom
import scala.collection.{mutable, _}

case class Phrase(word: String)

class PhraseMap extends PrefixMap[Phrase] {
  type R = PhraseMap
  def self = this
  def emptyMap = new PhraseMap
}


abstract class PrefixMap[T] extends mutable.Map[String, T] with mutable.MapLike[String, T, PrefixMap[T]] {

  type R <: PrefixMap[T]
  def self: R
  def emptyMap: R

  override def empty: PrefixMap[T] = emptyMap


  var suffixes: immutable.Map[Char, R] = Map.empty
  var value: Option[T] = None

  def get(s: String): Option[T] =
    if (s.isEmpty) value
    else suffixes get s(0) flatMap (_.get(s substring 1))

  def withPrefix(s: String): R =
    if (s.isEmpty) self
    else {
      val leading = s(0)
      suffixes get leading match {
        case None =>
          suffixes = suffixes + (leading -> emptyMap)
        case _ =>
      }
      (suffixes(leading) withPrefix (s substring 1)).asInstanceOf[R]
    }

  override def update(s: String, elem: T): Unit =
    withPrefix(s).value = Some(elem)

  override def remove(s: String): Option[T] =
    if (s.isEmpty) {
      val prev = value
      value = None
      prev
    }
    else suffixes get s(0) flatMap (_.remove(s substring 1))

  def iterator: Iterator[(String, T)] =
    (for (v <- value.iterator) yield ("", v)) ++
      (for ((chr, m) <- suffixes.iterator;
            (s, v) <- m.iterator) yield (chr +: s, v))

  def +=(kv: (String, T)): this.type = {
    update(kv._1, kv._2)
    this
  }

  def -=(s: String): this.type = {
    remove(s)
    this
  }

}


object PrefixMap {
  def empty[T]: PrefixMap[T] = new PrefixMap[T] {
    type R = PrefixMap[T]
    def self = this
    def emptyMap = this
  }

  def apply[T](kvs: (String, T)*): PrefixMap[T] = {
    val m: PrefixMap[T] = empty
    for (kv <- kvs) m += kv
    m
  }

  def newBuilder[T]: mutable.Builder[(String, T), PrefixMap[T]] =
    new mutable.MapBuilder[String, T, PrefixMap[T]](empty)

  implicit def canBuildFrom[T]: CanBuildFrom[PrefixMap[_], (String, T), PrefixMap[T]] =
    new CanBuildFrom[PrefixMap[_], (String, T), PrefixMap[T]] {
      def apply(from: PrefixMap[_]) = newBuilder[T]

      def apply() = newBuilder[T]
    }
}