Keep 26 cached counts, updating them after a successful delegated edit. Count exactly lowercase letters; the query alphabet does not make uppercase letters the same character.For an initially empty underlying document that stores inserted arguments unchanged, the representation invariant isInsertion increments precisely the inserted lowercase character's count. Deletion uses the returned character, avoiding an extra indexed read and decrementing the character actually removed. Updating after
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 x = super.delete(pos)
if (lower(x)) counts(x - 'a') -= 1
x
}
def getCount(x: Char): Int = {
assert(lower(x))
counts(x - 'a')
}
}super means a rejected edit leaves the counts unchanged. Both the added update work and getCount use time complexity and fixed storage.The
abstract override methods implement a stackable trait modification: they require a concrete document implementation further along the delegation chain. The invariant above depends on subsequent layers preserving inserted characters. Part (d) deliberately composes a transforming layer that can break this assumption; that is the transform-sensitive trait frequency counter phenomenon. Articles by others on the same topic
There are currently no matching articles.