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
The missing preconditions are for insertion and for deletion and indexing. The inclusive endpoint permits appending; deletion or access at the length is invalid. Specify the initial state, for example , as well as the read-only frame conditions: indexing returns the indicated character and preserves , while
length returns and preserves .The insertion and deletion clauses already describe the new sequence, but their returned values and effects should be interpreted against the old state. For a machine-sized length, insertion also requires . These clauses complete the document abstract data type without prescribing one storage representation.
For the flattened Boolean array, the abstraction function selects the true cells. A suitable representation invariant requires the occupied cells to form a order ideal: an occupied implies occupancy of every with . Deleting a northeast rectangle preserves that property.
For column heights, the invariant is , and the abstraction function is . A legal move replaces every for by , preserving the invariant. This is an order-ideal board representation.
For a fair comparison, allow either representation a scalar cached token count:
Count and Legal then take in both. Without that cache, counting needs Boolean inspections versus height additions. A move takes in the worst case in the flattened representation and with heights. Displaying the full square takes character positions in either. Heights use array entries rather than , so they are superior for the requested operations; their initialization also takes only time.Within the sparse-vector implementation, use:
class Node(var value: Double, val index: Int,
var prev: Node, var next: Node)The header's
index is the fixed vector dimension, so it need not change after construction. For a data node it is the coordinate index. The representation invariant requires a finite simple cycle through the header, reciprocal predecessor/successor links, strictly increasing indices in the forward data-node traversal, indices in , and a nonzero value at every data node. The header's value is ignored. The abstraction function assigns stored values to their indices and zero to all missing coordinates.The numerical code below takes entries to be finite
Double values. Excluding NaN and infinities makes the relationship to a real sparse vector explicit; arithmetic results still follow ordinary floating-point arithmetic.def eaFast(n: Int): Double = {
require(n > 0)
var remaining = n
var base = 1.0 + 1.0 / n.toDouble
var result = 1.0
while (remaining > 0) {
if (remaining % 2 == 1) result *= base
base *= base
remaining /= 2
}
result
}Writing , the exact-arithmetic loop invariant is and . For an even integer exponent , replace the base by its square and the exponent by . For an odd integer exponent , first multiply the accumulator by the base and then make the same replacement. Both preserve the product. The loop variant is
remaining, which strictly decreases while positive. At exit the remaining exponent is zero, so the returned value approximates .There are iterations, squarings and one accumulator multiplication for each set bit of : between and multiplications. Thus the bound is as , or including the small case . All power variables are
Double; no unintended Int squaring occurs.Use a
Double base so that the reciprocal is not truncated by integer division. Repeated multiplication gives the requested linear-work approximation to Euler's number.def eaLinear(n: Int): Double = {
require(n > 0)
val base = 1.0 + 1.0 / n.toDouble
var i = 0
var result = 1.0
while (i < n) {
result *= base
i += 1
}
result
}In exact arithmetic over the real numbers, the loop invariant is and . It holds initially, one multiplication establishes the next exponent, and at exit gives the specified power. The nonnegative loop variant is . There are exactly loop multiplications, hence in asymptotic analysis, and one division to form the base. With floating-point arithmetic, the invariant describes the intended exact result; the actual output has the corresponding rounding errors.
There are unlisted articles, also show them or only show them.