= Solution
Store the number of positive buckets, initially zero:
``
private var distinct = 0
def size: Int = distinct
``
Extend the <representation invariant> by
$$
distinct=|\{i:0\leq i<MAX,\ c(i)>0\}|.
$$
The <abstraction function> for the <multiset> is unchanged. The size operation has no <precondition> beyond a valid receiver; it returns the <cardinality> of the <multiset support> and changes no state. Replace the modifying methods inside the class by
``
def add(x: Int): Unit = {
require(inRange(x))
require(c(x) < Int.MaxValue)
if (c(x) == 0) distinct += 1
c(x) += 1
}
def remove(x: Int): Unit = {
require(inRange(x))
require(c(x) > 0)
c(x) -= 1
if (c(x) == 0) distinct -= 1
}
``
Only transitions from zero to one or from one to zero change the support. <Additions> to an already positive bucket and removals leaving it positive preserve `distinct`. Thus \b[`size` takes $O(1)$ time, independently of `MAX`], and the other operations retain constant-time <array> access. Initialization still takes $O(MAX)$ time.
Back to article page
