Use an immutable list as private storage and cache its length. This makes the data refinement transparent without depending on library-specific dynamic array costs:The representation invariant is , with
class DocImpl extends Doc {
private var chars: List[Char] = Nil
private var length: Int = 0
def size: Int = length
def insert(x: Char, pos: Int): Unit = {
require(0 <= pos && pos <= length)
val parts = chars.splitAt(pos)
chars = parts._1 ::: (x :: parts._2)
length += 1
}
def delete(pos: Int): Char = {
require(0 <= pos && pos < length)
val parts = chars.splitAt(pos)
val old = parts._2.head
chars = parts._1 ::: parts._2.tail
length -= 1
old
}
def read(pos: Int): Char = {
require(0 <= pos && pos < length)
chars(pos)
}
}chars representing the abstract document sequence. splitAt(pos) isolates exactly the prefix before the selected array index-style position. Insertion retains that prefix and the old suffix, placing the new character between them. Deletion returns the old suffix head and retains its tail. Updating the cached length by one preserves the representation invariant. read and size preserve the abstract state.The preconditions permit insertion at the end, including position zero in an empty document, but forbid reading or deleting at the end.Maintain one frequency count for each lowercase alphabet character. Update only after a successful delegated operation:For an initially empty underlying implementation that inserts the character it receives and returns the character actually deleted, the representation invariant isInsertion 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
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')
}
}abstract override because it delegates to a concrete implementation elsewhere in the mixin chain.[ref]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.Apply capitalization before delegating insertion:Scala's
trait CapitalisePlugIn extends Doc {
abstract override def insert(x: Char, pos: Int): Unit = {
super.insert(x.toUpper, pos)
}
}Char.toUpper implements the hinted conversion and leaves ordinary nonletters unchanged. The stackable trait modification intercepts insertion without changing the position, result type or deletion behavior.For the implementations above, the output isIn
0
1A, the Scala trait linearization sends insert('a',0) first to CapitalisePlugIn, then to CharTrackPlugIn, then to DocImpl. The counter trait receives 'A', so it does not increment the lowercase 'a' count. The stored document is A.In
B, the counter trait receives 'a', delegates through CapitalisePlugIn, and increments its original argument's counter on return. The stored document is again A, but the counter records one lowercase insertion:This demonstrates a composition that violates the count-of-current-document representation invariant for B: an earlier counter cannot assume a later transforming trait inserts its argument unchanged. Subsequent deletion also receives uppercase 'A' and would leave that stale lowercase count. A different valid design could inspect read(pos) after insertion to count the actual stored character; that design would produce 0,0. The stated 0,1 follows the explicit implementation in part (b), whose correctness assumption has now failed in the second composition. Articles by others on the same topic
There are currently no matching articles.