(Sorted)MultiMap impossible for 2.8?

[Barry Kaplan]

I'm trying to build a sorted multi-map. Unlike the the multi-map trait in 2.7, I need for methods like 'map' to handle the case of duplicate keys and add them to the map (not just overwrite an existing Set at the key).

As a jumpstart I took the TreeMap and used it as a template for the interface. I had to inline code from MapBuilder and ImmutableSortedMapFactory to handle the case of 'B' becoming a 'Set[B]'. But I'm now stuck with the few mutater methods -- the ones that are commented out in the code is below (and also at http://paste.pocoo.org/show/148953/).

For example, from SortedMapLike we have:

    override def updated [B1 >: B](key: A, value: B1): SortedMultiMap[A, B1]

I need something like:

    override def updated [B1 >: Set[B]](key: A, value: B1): SortedMultiMap[A, ??B1??]

But don't know how to get the return type correct. I've tried things like:

    override def updated [B1 >: B, SB1 <: Set[B1]](key: A, value: SB1): SortedMultiMap[A, B1]

This fails (at least) because adding the extra type parameter 'SB1' causes the method to no longer override. I've tried all kinds of stuff, but am quite stumped.

Any help would be greatly appreciated. I sure hope it turns out that it is not impossible.

-----

package systeminsights.infra
package collection

import scala.collection
import collection.SortedMapLike
import collection.immutable.{MapLike, SortedMap}
import collection.mutable.{Builder}
import collection.generic.{CanBuildFrom}

//SMELL Had to copy this code from scala.collection.mutable.MapBuilder to make B a Set[B]
class SortedMultiMapBuilder[A, B, Coll <: scala.collection.Map[A, Set[B]] with scala.collection.MapLike[A, Set[B], Coll]] (empty: Coll)(implicit ord: Ordering[A])
    extends Builder[(A, Set[B]), Coll] {

  protected var elems: Coll = empty

  def +=(x: (A, Set[B])): this.type = {
    elems = (elems + x).asInstanceOf[Coll]
      // the cast is necessary because right now we cannot enforce statically that
      // for every map of type Coll, `+` yields again a Coll. With better support
      // for hk-types we might be able to enforce this in the future, though.
    this
  }
  def clear() { elems = empty }
  def result: Coll = elems
}

//SMELL Had to copy/inline most of this code from scala.collection.generic.ImmutableSortedMapFactory to make B a Set[B]
object SortedMultiMap {

  def newBuilder[A, B](implicit ord: Ordering[A]): Builder[(A, Set[B]), SortedMultiMap[A, B]] = new SortedMultiMapBuilder[A, B, SortedMultiMap[A, B]](empty)(ord)
  def empty[A, B](implicit ord: Ordering[A]): SortedMultiMap[A, B] = new SortedMultiMap[A, B]
  def apply[A, B](elems: (A, Set[B])*)(implicit ord: Ordering[A]): SortedMultiMap[A, B] = (newBuilder[A, B](ord) ++= elems).result

  class SortedMultiMapCanBuildFrom[A, B](implicit ord: Ordering[A]) extends CanBuildFrom[SortedMultiMap[A, B], (A, Set[B]), SortedMultiMap[A, B]] {
    def apply(from: SortedMultiMap[A, B]) = newBuilder[A, B]
    def apply() = newBuilder[A, B]
  }
  implicit def canBuildFrom[A, B](implicit ord: Ordering[A]): CanBuildFrom[SortedMultiMap[A, B], (A, Set[B]), SortedMultiMap[A, B]] = new SortedMultiMapCanBuildFrom[A, B]
}

@serializable
class SortedMultiMap[A, B](implicit val ordering: Ordering[A])
  extends SortedMap[A, Set[B]]
     with SortedMapLike[A, Set[B], SortedMultiMap[A, B]]
     with MapLike[A, Set[B], SortedMultiMap[A, B]] {

  override protected[this] def newBuilder : Builder[(A, Set[B]), SortedMultiMap[A, B]] =
    SortedMultiMap.newBuilder[A, B](ordering)

  override def empty: SortedMultiMap[A, B] =  throw new UnsupportedOperationException

  override def get(key: A): Option[Set[B]] = throw new UnsupportedOperationException
  override def rangeImpl(from : Option[A], until : Option[A]): SortedMultiMap[A,B] =  throw new UnsupportedOperationException

  override def firstKey =  throw new UnsupportedOperationException
  override def lastKey = throw new UnsupportedOperationException
  override def compare(k0: A, k1: A): Int =  throw new UnsupportedOperationException

//  override def updated [B1 >: B](key: A, value: B1): SortedMultiMap[A, B1] = throw new UnsupportedOperationException
//  override def + [B1 >: B] (kv: (A, B1)): SortedMultiMap[A, B1] = throw new UnsupportedOperationException
//  override def + [B1 >: B] (elem1: (A, B1), elem2: (A, B1), elems: (A, B1) *): SortedMultiMap[A, B1] = throw new UnsupportedOperationException

  def - (key:A): SortedMultiMap[A, B] =  throw new UnsupportedOperationException

  def iterator: Iterator[(A, Set[B])] = throw new UnsupportedOperationException
  override def toStream: Stream[(A, Set[B])] = throw new UnsupportedOperationException
  override def foreach[U](f : ((A, Set[B])) =>  U) = throw new UnsupportedOperationException
}