Store characters in a mutable dynamic array. Its length is maintained by the collection, giving constant-time The representation invariant requires a nonnull private dynamic array containing a finite sequence of characters, with its internal collection invariant maintained by the library. The abstraction function isInsertion allows the end position and shifts the suffix right; deletion returns exactly the removed character and shifts the suffix left.
size.class DocImpl extends Doc {
private val text = scala.collection.mutable.ArrayBuffer.empty[Char]
def insert(x: Char, pos: Int): Unit = {
require(0 <= pos && pos <= text.length)
text.insert(pos, x)
}
def delete(pos: Int): Char = {
require(0 <= pos && pos < text.length)
text.remove(pos)
}
def read(pos: Int): Char = {
require(0 <= pos && pos < text.length)
text(pos)
}
def size: Int = text.length
}read leaves the abstract state unchanged. size equals the abstract sequence length in time complexity. Indexed reads are also constant time; insertion and deletion may take linear time, which the question permits.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.Convert lowercase alphabet letters before passing them to the next implementation. Already uppercase letters and other characters pass through unchanged.The character conversion uses the paper's contiguous lowercase and uppercase Latin ranges. ThusDeletion, reading, and size need no overrides.
trait CapitalisePlugIn extends Doc {
abstract override def insert(x: Char, pos: Int): Unit = {
val y = if ('a' <= x && x <= 'z') ('A' + (x - 'a')).toChar else x
super.insert(y, pos)
}
}The rightmost trait intercepts insertion first. In
A, capitalization runs before counting, so the counter receives uppercase A and does not increment the lowercase count. In B, counting receives lowercase a, delegates to capitalization, and then increments the original lowercase argument's counter. Both concrete documents store uppercase A.The exact output isThis illustrates an order-sensitive stackable trait modification. In the second composition the cached count describes intercepted insertion arguments, and no longer the actual lowercase characters in the stored document. For example, deleting its uppercase
0
1A would not decrement the lowercase counter. A counter required to track actual contents under arbitrary transforming mixins would need a stronger composition contract or would inspect the stored character after insertion; such a change would alter the intended behavior of this example. Articles by others on the same topic
There are currently no matching articles.