trait MultiSet[T] extends CompleteMultiSet[T] {
  // Additional invariant: count(t) >= 0 for every t.
  // Inherited arithmetic still returns CompleteMultiSet[T].
}

class MultiSetImp[T](initial: Map[T, Int])
    extends CompleteMultiSetImp[T](initial) with MultiSet[T] {
  require(initial.values.forall(_ >= 0), "negative multiplicity")
}

def ms[T](ts: T*): MultiSet[T] =
  new MultiSetImp[T](ts.distinct.map(t => (t, 1)).toMap)

class CompleteMultiSetImp[T](initial: Map[T, Int]) extends CompleteMultiSet[T] {
  private val table = initial.filter { case (_, n) => n != 0 }
  override def count(t: T): Int = table.getOrElse(t, 0)
  override lazy val present: Seq[T] = table.keys.toVector
}

def cms[T](ts: T*): CompleteMultiSet[T] =
  new CompleteMultiSetImp[T](ts.distinct.map(t => (t, 1)).toMap)

trait CompleteMultiSet[T] {
  // Representation contract: finite, immutable, unique keys, nonzero counts.
  protected def entries: List[(T, Int)] = Nil

  def count(t: T): Int =
    entries.find { case (key, _) => key == t }.map(_._2).getOrElse(0)

  lazy val present: Seq[T] = entries.map(_._1)

  private def combine(other: CompleteMultiSet[T],
                      op: (Int, Int) => Int): CompleteMultiSet[T] = {
    val keys = (present.toList ++ other.present.toList).distinct
    val resultRows = keys.flatMap { t =>
      val n = op(count(t), other.count(t))
      if (n == 0) Nil else List((t, n))
    }
    new CompleteMultiSet[T] {
      override protected val entries: List[(T, Int)] = resultRows
    }
  }

  def +(other: CompleteMultiSet[T]): CompleteMultiSet[T] =
    combine(other, (a, b) => java.lang.Math.addExact(a, b))

  def -(other: CompleteMultiSet[T]): CompleteMultiSet[T] =
    combine(other, (a, b) => java.lang.Math.subtractExact(a, b))

  def max(other: CompleteMultiSet[T]): CompleteMultiSet[T] =
    combine(other, (a, b) => math.max(a, b))

  def min(other: CompleteMultiSet[T]): CompleteMultiSet[T] =
    combine(other, (a, b) => math.min(a, b))

  def <=(other: CompleteMultiSet[T]): Boolean =
    (present.toList ++ other.present.toList).distinct.forall { t =>
      count(t) <= other.count(t)
    }

  override def toString: String =
    present.distinct.filter(t => count(t) != 0)
      .map(t => s"$t:${count(t)}").mkString("{", ", ", "}")
}