A complete multiset is a finite-support signed count function. An absent key has count zero; negative counts are allowed. One simple default implementation uses a protected immutable association list with unique keys and nonzero values. Its default is empty, and optimized subclasses may override the public queries.
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("{", ", ", "}")
}The representation invariant and abstraction function assign the association-list value at a stored key and zero elsewhere. Every operation preserves both operands and returns a fresh immutable value. The finite-support pointwise operations principle makes the support union sufficient because every operation sends to zero. It is necessary for signed counts: the empty value is not at most a value having count at one key, although the empty left support alone would give a vacuous true comparison. Likewise, pointwise minimum can retain a negative count appearing only in the other operand.
present == List() represents the all-zero, empty complete multiset. The list-backed default count takes time for a first-entry hit or an empty list, and in the worst case for a missing or final key, assuming constant-cost key equality. The default binary operations can consequently take quadratic time; they are deliberately simple defaults, not optimized implementations. The lazy present avoids an early call to a subclass's representation during initialization.Counts use
Int, so addition and subtraction explicitly throw ArithmeticException when the mathematical result is unrepresentable instead of silently wrapping. Equivalently, their mathematical precondition requires representable result counts. This machine-size restriction is separate from permitting negative counts. Articles by others on the same topic
There are currently no matching articles.