 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2018/imperative-programming/4/d/i/solution

Place this object method inside the concrete class. Its precondition is the representation invariant; its postcondition is that the abstract data type state is unchanged and its left-to-right contents have been printed in bracket notation followed by a newline:

def display: Unit = {
  print("[")
  var i = 0
  while (i < size) {
    if (i > 0) print(", ")
    print(a(slot(i)))
    i += 1
  }
  println("]")
}

Assume ordinary sequential execution and successful output. The loop invariant is

0 \leq i \leq s i ze

, unchanged representation, and output consisting of [ followed by precisely the first

i

abstract values, separated by commas and spaces. The loop variant

s i ze - i

decreases. At exit the closing bracket completes the required display, including [] for emptiness. This takes

O (s i ze + 1)

output operations and constant space.

 New to topics? Read the docs here!