= Solution
A mutable character buffer supplies a cached length and constant-time indexed access:
``
class DocImp extends Doc {
private val data = scala.collection.mutable.ArrayBuffer.empty[Char]
def insert(pos: Int, ch: Char): Unit = {
require(0 <= pos && pos <= data.length)
require(data.length < Int.MaxValue)
data.insert(pos, ch)
}
def delete(pos: Int): Char = {
require(0 <= pos && pos < data.length)
data.remove(pos)
}
def apply(pos: Int): Char = {
require(0 <= pos && pos < data.length)
data(pos)
}
def length: Int = data.length
}
``
The <representation invariant> is that `data` is a well-formed private <dynamic array> of at most `Int.MaxValue` characters. Its <abstraction function> is the buffer's character <sequence>. Initialization is empty; insertion and removal at the checked position implement exactly the required <sequence> edits, and the queries do not modify it.
\b[`length` and indexing are $O(1)$] because a <dynamic array> stores its used length and supports address arithmetic for indexed access. An insertion or deletion at position $p$ in a document of length $L$ shifts $O(L-p)$ entries; insertion can additionally resize the backing storage, giving amortized $O(L-p+1)$ time and worst-case $O(L)$ for one operation. Deletion is $O(L-p)$ with an additional constant term.
Building a document by appending the characters of a length-$L$ string costs \b[$O(L)$ amortized time], since geometric capacity growth copies a total of only $O(L)$ entries. Thus this implementation does not have the quadratic append behavior of repeated immutable-string concatenation. A known final length can also be reserved in advance. The bounds use the usual <amortized analysis> of a <dynamic array>.<Performance Characteristics of Scala 2.13 collections>[Mutable <sequence> table: ArrayBuffer constant indexed access and amortized constant append]{ref}
Back to article page
