= Solution
Maintain one <frequency count> for each lowercase alphabet character. Update only after a successful delegated operation:
``
trait CharTrackPlugIn extends Doc {
private val counts = Array.fill[Int](26)(0)
private def lower(x: Char): Boolean = 'a' <= x && x <= 'z'
abstract override def insert(x: Char, pos: Int): Unit = {
super.insert(x, pos)
if (lower(x)) counts(x - 'a') += 1
}
abstract override def delete(pos: Int): Char = {
val old = super.delete(pos)
if (lower(old)) counts(old - 'a') -= 1
old
}
def getCount(x: Char): Int = {
assert('a' <= x && x <= 'z')
counts(x - 'a')
}
}
``
For an initially empty underlying implementation that inserts the character it receives and returns the character actually deleted, the <representation invariant> is
$$
\mathrm{counts}(j)=\#\{i:0\leq i<\operatorname{size},\ \operatorname{read}(i)=\texttt{'a'}+j\},\quad0\leq j<26.
$$
Insertion increases exactly one applicable <frequency count>, and deletion decreases the count of the returned character. Uppercase and nonletter characters contribute nothing. Exceptions from failed underlying operations leave the counters unchanged. The <stackable trait modification> uses `abstract override` because it delegates to a concrete implementation elsewhere in the mixin chain.<Scala 2.11 classes and objects specification>[Modifiers, abstract override; Inheritance]{ref}
$$
\boxed{\operatorname{getCount}:\Theta(1),\qquad\text{extra storage: }26\text{ counters}.}
$$
The counters depend on the character seen by this <trait>. A later <trait> that transforms characters can break the stated underlying-operation assumption; part (d) deliberately exposes that order dependence.
Back to article page
