= Solution
Use a fixed-size count <array> and protected hooks defining a stable character-to-slot mapping. The default hooks count the ASCII lowercase interval. The document must start empty, and all subsequent edits must pass through the <mixin> methods, as they do for `new DocImp with CharCountPlugin`.
``
trait CharCountPlugin extends Doc {
protected def firstCounted: Char = 'a'
protected def numberCounted: Int = 26
protected def slot(ch: Char): Int = {
val k = ch.toInt - firstCounted.toInt
if (0 <= k && k < numberCounted) k else -1
}
private lazy val totals = Array.fill(numberCounted)(0)
abstract override def insert(pos: Int, ch: Char): Unit = {
val k = slot(ch)
super.insert(pos, ch)
if (k >= 0) totals(k) += 1
}
abstract override def delete(pos: Int): Char = {
val removed = super.delete(pos)
val k = slot(removed)
if (k >= 0) totals(k) -= 1
removed
}
def count(ch: Char): Int = {
val k = slot(ch)
require(k >= 0, "character is outside the counted alphabet")
totals(k)
}
}
``
The additional <representation invariant> is that each <array> slot equals the number of corresponding characters in the current document. Initially all counts are zero. Each successful underlying edit changes exactly one relevant count, while a failed position check throws before any count is changed. Returning the actual deleted character lets deletion adjust the correct slot.
`count` takes \b[$O(1)$ time for the fixed alphabet], as do the <mixin>'s additions to edit cost. The lazy <array> avoids reading subclass-overridden size hooks during <trait> construction; the hooks must remain stable. An extension can override the interval hooks, or override `slot` with another fixed finite mapping. This is <stackable modification by a trait>: `abstract override` permits the method to call the next implementation of `super`, supplied here by `DocImp`.<Scala 2.13 classes and objects specification>[Abstract override and <trait> linearization]{ref}
Back to article page
