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.length and indexing are because a dynamic array stores its used length and supports address arithmetic for indexed access. An insertion or deletion at position in a document of length shifts entries; insertion can additionally resize the backing storage, giving amortized time and worst-case for one operation. Deletion is with an additional constant term.Building a document by appending the characters of a length- string costs amortized time, since geometric capacity growth copies a total of only 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.[ref]
Performance Characteristics of Scala 2.13 collections. Mutable sequence table: ArrayBuffer constant indexed access and amortized constant append
Articles by others on the same topic
There are currently no matching articles.