Simple purely functional map that efficiently tracks insertion order

LinkedMap.scala

/**
 * A Map which tracks the insertion order of entries, so that entries may be
 * traversed in the order they were inserted. Uses just two purely functional
 * maps.
 */

import scala.collection.immutable.LongMap

class LinkedMap[K,V](
  entries: Map[K,(V,Long)],
  insertionOrder: LongMap[K],
  nextID: Long) {

  def get(k: K): Option[V] = entries.get(k).map(_._1)

  /** Insert an entry into this map, overriding any previous entry for the given `K`. */
  def updated(k: K, v: V): LinkedMap[K,V] =
    new LinkedMap(entries.updated(k, (v,nextID)), insertionOrder.updated(nextID, k), nextID+1)

  /** Remove this key from this map. */
  def -(k: K) = new LinkedMap(
    entries - k,
    entries.get(k).map { case (_,id) => insertionOrder - id }.getOrElse(insertionOrder),
    nextID)

  /** The keys of this map, in the order they were added. */
  def keys: Iterable[K] = insertionOrder.values

  /** The values in this map, in the order they were added. */
  def values: Iterable[V] = keys.flatMap(k => entries.get(k).toList.map(_._1))
}

object LinkedMap {
  def empty[K,V] = new LinkedMap[K,V](Map.empty, LongMap.empty, 0)
}

Why not make ctor private and LinkedMap a case class?

@ahjohannessen You could do that if you wanted.