Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Imperative programming (resit) / 6 / a

The missing preconditions are $0 \leq p os \leq ∣ d ∣$ for insertion and $0 \leq p os < ∣ d ∣$ for deletion and indexing. The inclusive endpoint permits appending; deletion or access at the length is invalid. Specify the initial state, for example

d = []

, as well as the read-only frame conditions: indexing returns the indicated character and preserves

d

, while length returns

∣ d ∣

and preserves

d

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

∣ d ∣ < I n t . M a x Va l u e

. These clauses complete the document abstract data type without prescribing one storage representation.

ii

 0  0

Solution

 0  0

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.

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 $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.^[ref]

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Imperative programming (resit) / 6 / a

i

Solution

ii

Solution

 Ancestors (11)

 Discussion (0)

 Articles by others on the same topic (0)

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Imperative programming (resit) / 6 / a

i

Solution

ii

Solution

 Ancestors (11)

 Discussion (0)  Subscribe (1)

 Articles by others on the same topic (0)

 Discussion (0)