Source paper: released examination archive, member 2017/T/a10098w1.pdf. The printed cover dates this examination to Wednesday 13 June 2018, Trinity Term; the archive directory does not determine its year. All eight questions and every printed option are covered. Examples use Scala 2 syntax. Arithmetic loop invariants describe exact arithmetic unless a floating-point arithmetic qualification is stated.
Keep a running product of the fixed base. In particular, 1.0/n uses floating-point arithmetic, avoiding the truncation that integer division would introduce:
def eaLinear(n: Int): Double = {
  require(n > 0)
  val base = 1.0 + 1.0 / n.toDouble
  var k = 0
  var result = 1.0
  while (k < n) {
    result *= base
    k += 1
  }
  result
}
The loop invariant is and . Initially the empty product is one. Multiplication by base and incrementing k preserve the invariant. The loop variant decreases by one. On exit , so the result is , with exactly multiplications and time complexity. With Double, the operational result is the rounded recurrence, rather than an exact real power; this distinction applies to the next two power computations too.
Use exponentiation by squaring, retaining the unprocessed exponent in k:
def eaBinary(n: Int): Double = {
  require(n > 0)
  var base = 1.0 + 1.0 / n.toDouble
  var k = n
  var result = 1.0
  while (k > 0) {
    if ((k & 1) != 0) result *= base
    k = k / 2
    if (k > 0) base *= base
  }
  result
}
Writing , the loop invariant is and . If the old exponent is , , multiplying the accumulator by and replacing the remaining power by preserves the invariant. When , the unused squaring may be omitted. The nonnegative integer k is a loop variant, since for . At exit the remaining power is one, giving . There are iterations, at most one accumulator multiplication and one squaring per iteration, hence multiplications and constant space.
Generate each reciprocal factorial from the preceding one, instead of recomputing a factorial for every summand:
def eb(n: Int): Double = {
  require(n >= 0)
  var i = 0
  var term = 1.0
  var sum = 1.0
  while (i < n) {
    i += 1
    term /= i.toDouble
    sum += term
  }
  sum
}
The loop invariant is , , and . Initially and . The division produces , which is then added to the previous partial sum. The loop variant is . Consequently the returned value is , using exactly divisions and additions, no multiplications, and time complexity. The slightly weaker precondition also permits the useful zero-term boundary case. For Double, small positive terms eventually cease to change sum because of floating-point rounding.
First rearrange the ratios so that the intermediate powers remain moderate:
(1)
This avoids separately forming enormous powers such as . Perform the two instances of exponentiation by squaring in one while loop, using coupled binary exponentiation:
def ec(n: Int): Double = {
  require(n > 1)
  val dn = n.toDouble
  var x = 1.0 + 1.0 / dn
  var y = 1.0 + 1.0 / (dn - 1.0)
  var k = n
  var l = n - 1
  var p = 1.0
  var q = 1.0
  while (k > 0 || l > 0) {
    if (k > 0) {
      if ((k & 1) != 0) p *= x
      k /= 2
      if (k > 0) x *= x
    }
    if (l > 0) {
      if ((l & 1) != 0) q *= y
      l /= 2
      if (l > 0) y *= y
    }
  }
  (dn + 1.0) * p - dn * q
}
With and , the loop invariant is , , and . Each active branch preserves its own power identity by the parity argument in part (a)(ii), and an inactive branch changes nothing. The loop variant is the mathematical integer , which need not be computed in a fixed-width variable: it decreases whenever either exponent is positive. At exit , , proving the returned expression is . There are iterations, at most four loop multiplications each, and two final multiplications. Converting n before adding one avoids integer overflow at Int.MaxValue.
The rearrangement avoids floating-point overflow in the original powers, but subtraction still combines two quantities of order to obtain one of order one. Catastrophic cancellation can amplify their accumulated roundoff error. The mathematical approximation error therefore does not imply that the Double implementation improves indefinitely as n grows.
Choose the reciprocal-factorial summation eb for asymptotically high accuracy, counting multiplications and divisions as arithmetic work. For tolerance , linear powering in part (a)(i) takes multiplications; binary exponentiation in part (a)(ii) reduces this to . Part (c) also has arithmetic work, since its required grows like , though its constants and cancellation error differ.
By the reciprocal-factorial series remainder bound, the omitted positive tail satisfies
(1)
Thus the factorial denominator grows much faster than an exponential in the number of iterations. For decimal places, setting of order gives by Stirling's approximation, rather than binary-power arithmetic steps. This is a comparison in an exact-arithmetic operation-count model; the stated Big O notation does not determine the exact winner for every small tolerance. Taken literally, eb uses zero multiplications and only divisions. Fixed double-precision floating-point format cannot deliver arbitrarily many correct decimal places, and the precision-dependent cost of arbitrary-precision arithmetic is a separate issue.
Linear search examines successive entries until a match or a stopping condition is reached; in the worst case it inspects entries. Binary search uses a sorted array to discard about half of the remaining candidates after each comparison, requiring comparisons. Its logarithmic guarantee also requires constant-cost indexed access, as supplied by an array; the same index operations on a linked list would not be constant-cost.
Return the lower-bound search boundary, permitting both zero and the array length:
def lowerBound(a: Array[Int], x: Int): Int = {
  require(a != null) // a is nondecreasing
  var lo = 0
  var hi = a.length
  while (lo < hi) {
    val mid = lo + (hi - lo) / 2
    if (a(mid) < x) lo = mid + 1
    else hi = mid
  }
  lo
}
The precondition includes nondecreasing order. The loop invariant is
(1)
Initially both excluded ranges are empty. If , sortedness justifies excluding every position through mid; otherwise it justifies excluding every position from mid onwards. The loop variant is a nonnegative integer that strictly decreases. When the old width is positive, mid is a valid array index. The midpoint expression avoids adding two potentially large indices. At exit , so lo satisfies the required partition, including when . Each new width is at most half the old width, rounded down; this gives time complexity and constant space, conventionally for nontrivial sizes.
A second binary search locates the first entry strictly greater than x:
def upperBound(a: Array[Int], x: Int): Int = {
  require(a != null) // a is nondecreasing
  var lo = 0
  var hi = a.length
  while (lo < hi) {
    val mid = lo + (hi - lo) / 2
    if (a(mid) <= x) lo = mid + 1
    else hi = mid
  }
  lo
}

def equalRange(a: Array[Int], x: Int): (Int, Int) =
  (lowerBound(a, x), upperBound(a, x))
For upper-bound search, the loop invariant is , , and ; its loop variant is again . The same midpoint and sortedness arguments prove preservation, termination and time complexity. The first binary search in part (b) already has its own loop invariant and loop variant.
Let the two boundaries be . There cannot be a value greater than before the first value at least , so . Every entry between them is simultaneously at least and at most , hence equals . Entries before are smaller and entries at or after are larger, so the interval cannot be extended at either end. This proves the equal-range search result is maximal. If x is absent, i == j, both equal to its insertion position; this can be zero, , or an interior gap. Two logarithmic searches still have logarithmic total time complexity. Computing an upper boundary as lowerBound(a, x+1) would introduce an unnecessary integer overflow bug at the largest integer.
Black-box testing chooses inputs and expected outputs from the public specification without using the implementation's control structure. Equivalence class testing partitions the input space into classes expected to exercise similar specified behavior, then chooses representatives; boundary cases test where that behavior changes. For equal-range search, use these concrete representatives:
  • Empty array: ([], 4) gives (0,0).
  • One entry, with the target below, equal, and above it: ([4],3), ([4],4), ([4],5) give (0,0), (0,1), (1,1).
  • An absent interior value: ([1,3,5],4) gives (2,2).
  • One interior match: ([1,3,5],3) gives (1,2).
  • A repeated interior block: ([1,3,3,3,5],3) gives (1,4).
  • A repeated block touching the left or right boundary: ([3,3,5],3) and ([1,3,3],3) give (0,2) and (1,3).
  • Every entry equal: ([3,3,3],3) gives (0,3); targets two and four give (0,0) and (3,3).
  • Extreme keys: ([Int.MinValue,0,Int.MaxValue],Int.MaxValue) gives (2,3), and searching for Int.MinValue gives (0,1).
For each result independently check , the strict inequalities outside the returned interval, and equality inside it. Unsorted inputs violate the precondition; they are not ordinary members of the specified valid-input classes. Software testing supplies evidence about implementations, while the loop invariant proof explains correctness for every valid input.
A list header is a permanent dummy linked list node, distinct from the ordinary elements. It gives a stable reference to the linked list and can store metadata such as its length. In a circular linked list, following successor links eventually returns to the starting point; with a list header, the last ordinary element links to the header, and the empty structure has the header linked to itself.
A singly linked list stores a successor reference per linked list node. A doubly linked list additionally stores a predecessor reference. The latter supports traversal in both directions and deletion of a known linked list node in constant time, without first searching for its predecessor. It costs another reference per linked list node and additional updates whose mutual consistency must be maintained. A list header makes insertion and deletion at an endpoint use the same local splicing rules as an interior change; the empty case does not require replacing an external head reference.
Use an immutable index and mutable value and links:
class Node(var value: Double, val index: Int,
           var prev: Node = null, var next: Node = null)
For the sparse linked vector representation, a header h has h.index >= 0, records that vector's dimension, and lies on a finite circular linked list. Every ordinary linked list node has an index in [0,h.index), a nonzero finite value, and a unique index; indices increase strictly from h.next to h.prev. For every reachable linked list node, including h, p.next.prev eq p and p.prev.next eq p. The abstraction function fills unspecified coordinates with zero. The header's value has no meaning. Finite real coordinates are assumed throughout; infinities and NaN are not ordinary real number coordinates for a mathematical inner product.
Only the list header is present: h.next eq h, h.prev eq h, and h.index is the dimension. This represents every coordinate as zero, including the unique zero-dimensional vector when the dimension is zero. The header is never treated as a nonzero coordinate.
The runtime precondition check rules out negative dimensions:
def makeZeroVector(size: Int): Node = {
  require(size >= 0)
  val h = new Node(0.0, size)
  h.prev = h
  h.next = h
  h
}
Both links point to the fresh list header, so all reciprocal-link conditions hold and there are no ordinary entries to violate ordering or nonzero-value requirements. The abstraction function therefore yields the zero vector of dimension size. Construction uses constant time and constant space.
Assume vector already satisfies the full representation invariant in part (b). Check the local bounds and value preconditions, then find the first index not smaller than the requested one:
def setElement(vector: Node, value: Double, index: Int): Unit = {
  require(vector != null)
  require(0 <= index && index < vector.index)
  require(value != 0.0 && !java.lang.Double.isNaN(value) &&
          !java.lang.Double.isInfinite(value))
  var p = vector.next
  while ((p ne vector) && p.index < index) p = p.next
  if ((p ne vector) && p.index == index) p.value = value
  else {
    val left = p.prev
    val fresh = new Node(value, index, left, p)
    left.next = fresh
    p.prev = fresh
  }
}
The search loop invariant says that the structure is unchanged and every ordinary linked list node passed has index smaller than index; p is the next candidate. The number of unpassed ordinary entries is a loop variant. The short-circuit evaluation prevents testing the header index as an ordinary entry. If an equal index exists, changing only its nonzero value preserves the representation invariant. Otherwise left and p delimit the unique insertion position: initializing both new links before redirecting their neighbors preserves reciprocal links and strict index order. Exactly the requested coordinate changes. With stored entries, the search costs and the splice costs constant time; checking the whole input structure is a caller obligation, rather than an unmentioned scan inside each call.
An already-zero entry needs no new linked list node:
def zeroElement(vector: Node, index: Int): Unit = {
  require(vector != null)
  require(0 <= index && index < vector.index)
  var p = vector.next
  while ((p ne vector) && p.index < index) p = p.next
  if ((p ne vector) && p.index == index) {
    val left = p.prev
    val right = p.next
    left.next = right
    right.prev = left
  }
}
The full input representation invariant is a precondition. The search has the same loop invariant and loop variant as in part (d). At exit, either p is the only stored entry with that index or none exists. In the first case, bypassing it in both directions removes exactly that coordinate and preserves the order of all remaining entries. This also works when its two neighbors are the same list header, leaving a self-linked empty structure. The header itself is never removed. The requested coordinate is zero and all others are unchanged, in time complexity.
Append entries in increasing index order, keeping a tail reference so that repeated searches do not make construction quadratic:
def makeVector(elems: Array[Double]): Node = {
  require(elems != null)
  val h = makeZeroVector(elems.length)
  var tail = h
  var i = 0
  while (i < elems.length) {
    val v = elems(i)
    require(!java.lang.Double.isNaN(v) &&
            !java.lang.Double.isInfinite(v))
    if (v != 0.0) {
      val fresh = new Node(v, i, tail, h)
      tail.next = fresh
      h.prev = fresh
      tail = fresh
    }
    i += 1
  }
  h
}
The loop invariant is , a valid circular representation of the nonzero entries in elems[0..i), a fixed header dimension elems.length, and tail eq h.prev. The next nonzero index is greater than every stored index; appending the fresh linked list node preserves reciprocal links, including tail.next eq h. The loop variant is elems.length-i. At exit the abstraction function yields exactly the input array as a vector. There is one pass and constant work per entry: time complexity for , including emptiness, and output storage for nonzero entries. Both signs of floating-point zero are represented by absence.
Use the sorted sparse dot product merge, processing a coordinate only when it appears in both supports of a vector:
def dotProduct(vec1: Node, vec2: Node): Double = {
  require(vec1 != null && vec2 != null)
  require(vec1.index == vec2.index)
  var p = vec1.next
  var q = vec2.next
  var result = 0.0
  while ((p ne vec1) && (q ne vec2)) {
    if (p.index < q.index) p = p.next
    else if (q.index < p.index) q = q.next
    else {
      result += p.value * q.value
      p = p.next
      q = q.next
    }
  }
  result
}
Both structures must satisfy the representation invariant; equal dimension is checked explicitly. The loop invariant says that result contains exactly the products for all matching indices already passed, and that every skipped unequal index has zero in the other vector. The latter follows from sortedness: if p.index < q.index, that index cannot appear at q or later, and all earlier entries of the other vector have already been settled. Equality contributes its product exactly once. The total number of remaining ordinary entries is a loop variant; every iteration advances at least one cursor. Once either cursor reaches its header, all remaining entries pair with zeros. Thus the exact-arithmetic result is . With stored entries, time complexity is and auxiliary space is constant. Floating-point products and additions may round or overflow even when input coordinates are finite; no exact real-arithmetic accuracy claim is made for Double.
Take the abstract state to be a finite sequence of integers, initially empty. Let denote the entry state, the empty sequence, and concatenation. A Scala trait presents the interface; its comments give the mathematical preconditions and postconditions:
trait DoubleEndedQueue {
  // Pre: true. Post: result == s0.isEmpty and s == s0.
  def isEmpty: Boolean
  // Pre: true. Post: s == [x] ++ s0.
  def addLeft(x: Int): Unit
  // Pre: s0.nonEmpty. Post: result == s0.head, s == s0.tail.
  def getLeft(): Int
  // Pre: true. Post: s == s0 ++ [x].
  def addRight(x: Int): Unit
  // Pre: s0.nonEmpty. Post: result == s0.last, s == s0.init.
  def getRight(): Int
}
The double-ended queue has no abstract capacity limit in this first specification. Both removals require nonemptiness; the query leaves the state unchanged, an instance of command-query separation.
A fixed-size array cannot implement unbounded successful insertion. Either specify a bounded double-ended queue with an extra not-full insertion precondition, or retain the unbounded interface and specify a possible full-capacity failure. Silently overwriting an endpoint would change the stated behavior. Here use the bounded contract, with a fixed positive capacity MAX and abstract state . Both additions require ; the other postconditions remain unchanged. The class declaration in part (c) is interpreted as implementing this explicitly revised contract, rather than as a behavioral subtype of the unrestricted contract in part (a).
The concrete state is an array a of length MAX, a first-position index head, and an occupied-entry count size. Its representation invariant is
(1)
The abstraction function is for . Unoccupied slots are unconstrained. Storing size distinguishes empty and full states even though their two circular endpoint positions coincide. MAX=1 is valid. Using a circular buffer avoids shifting entries and makes every endpoint operation constant time.
The following class uses the bounded insertion contract from part (b). slot performs mathematical circular indexing with a wider intermediate, so even large legal indices do not overflow before reduction:
class ArrayDoubleEndedQueue(val MAX: Int) extends DoubleEndedQueue {
  require(MAX > 0)
  private val a = new Array[Int](MAX)
  private var head = 0
  private var size = 0

  private def slot(offset: Int): Int =
    ((head.toLong + offset.toLong) % MAX.toLong).toInt

  private def before(i: Int): Int = if (i == 0) MAX - 1 else i - 1
  private def after(i: Int): Int = if (i == MAX - 1) 0 else i + 1

  def isEmpty: Boolean = size == 0

  def addLeft(x: Int): Unit = {
    require(size < MAX)
    head = before(head)
    a(head) = x
    size += 1
  }

  def addRight(x: Int): Unit = {
    require(size < MAX)
    a(slot(size)) = x
    size += 1
  }

  def getLeft(): Int = {
    require(size > 0)
    val x = a(head)
    head = after(head)
    size -= 1
    x
  }

  def getRight(): Int = {
    require(size > 0)
    val x = a(slot(size - 1))
    size -= 1
    x
  }
}
For addLeft, moving the first position back one slot makes the old position the new logical index one; inserting at the new position prepends x. For addRight, the old size is the first unoccupied logical index, so writing there appends x. The removals read the appropriate endpoint and exclude that slot from the occupied interval. Every operation preserves the representation invariant and realizes the abstraction function postcondition. Old contents in unused slots cannot be observed through this interface. Each operation performs a fixed number of accesses and arithmetic operations, hence has constant time and constant space per call, apart from the class's backing storage.
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 , unchanged representation, and output consisting of [ followed by precisely the first abstract values, separated by commas and spaces. The loop variant decreases. At exit the closing bracket completes the required display, including [] for emptiness. This takes output operations and constant space.
The successive abstract sequences are , , , , , , , , and finally . The three removals return , , and , respectively. With the display convention in part (i), the output is
20
10
10
Queue status: [30, 40, 15]
The capacity-four bound is never exceeded. The abstract trace is independent of which physical array slots wrap around.
Each binary tree entry stores its word, positive frequency, and two child references:
class Tree(val word: String, var count: Int,
           var left: Tree = null, var right: Tree = null)
A null reference denotes an empty subtree. A word is a non-null string data type value; its order below is the fixed lexicographic order used by String.compareTo.
The representation invariant says that root is either null or the root of a finite, acyclic binary search tree, with no software object shared between different child subtrees. Every reachable entry has a non-null word and a strictly positive frequency. For each entry , every word in its entire left subtree is strictly less than t.word, and every word in its entire right subtree is strictly greater. This is an inherited ordering condition on all descendants, rather than merely a comparison with immediate children. It implies that each distinct word has exactly one entry. The empty initial state satisfies it.
The abstraction function is the finite multiset assigning each stored word its positive count and assigning all other words zero. Frequencies and their increments must fit in Int; the implementation below explicitly rejects an increment at its representational limit instead of silently violating positivity through integer overflow.
Return the new root of the affected subtree, assigning that result back to the parent's child reference:
def addToTree(word: String, t: Tree): Tree = {
  require(word != null)
  if (t == null) new Tree(word, 1)
  else {
    val c = word.compareTo(t.word)
    if (c < 0) t.left = addToTree(word, t.left)
    else if (c > 0) t.right = addToTree(word, t.right)
    else {
      require(t.count < Int.MaxValue)
      t.count += 1
    }
    t
  }
}
// Updating the whole structure uses: root = addToTree(word, root)
Assume the input binary search tree satisfies part (b)'s representation invariant and, if the key already occurs, its count can be incremented. Structural induction proves the postcondition. For an empty subtree, the fresh entry represents one occurrence. Otherwise the word comparison identifies the only possible child subtree containing the word. The recursive call adds exactly one occurrence there, preserving the inherited strict bounds; in the equal case only the count changes. The number of entries in the current subtree strictly decreases in each recursive call, proving algorithm termination. The returned binary search tree represents the old multiset plus one occurrence of word. With height , at most comparisons are made; without balancing this can be linear in the number of words. Actual comparison work also depends on the compared string data type lengths.
start == null if and only if end == null. Otherwise there is a finite list of distinct software objects , with start eq v0, end eq v(m-1), v0.left == null, and v(m-1).right == null. For every valid adjacent pair, v(i).right eq v(i+1) and v(i+1).left eq v(i). These are exactly the entries reachable through the list links, so there is no extra cycle or branch. All counts are positive, all words are non-null, and words strictly increase from start to end.
This is the representation invariant for a null-terminated doubly linked list without a list header. The abstraction function reads the ordered word-count pairs from left to right. Conversion additionally requires the output entries, counts and words to be precisely those of the input binary search tree; that preservation property is an operation postcondition, rather than an invariant of an arbitrary list by itself.
Perform a destructive binary search tree flattening by converting both child subtrees and splicing their endpoints around the original root:
def flatten(t: Tree): (Tree, Tree) = {
  if (t == null) (null, null)
  else {
    val oldLeft = t.left
    val oldRight = t.right
    val (ls, le) = flatten(oldLeft)
    val (rs, re) = flatten(oldRight)
    t.left = le
    if (le != null) le.right = t
    t.right = rs
    if (rs != null) rs.left = t
    val start = if (ls == null) t else ls
    val end = if (re == null) t else re
    (start, end)
  }
}
Save the child references before changing their interpretation. The input is a finite binary search tree satisfying part (b), and no external client may simultaneously rely on the old tree links. By structural induction, the two recursive calls return disjoint, ordered doubly linked lists containing exactly their original entries. The binary search tree bounds place every left word before t.word and every right word after it. Splicing the left end, t, and the right start therefore preserves strict order and reciprocal links. A missing left list makes t.left null and t the start; a missing right list similarly makes t the end. The resulting outside links are null as required by part (i).
The recursive loop variant analogue is the strictly smaller number of entries in each child subtree. Every entry is processed once and incurs a constant number of link writes, so time complexity is and recursion uses auxiliary space. No new Tree entry is created; returning endpoint tuples and using a call stack are permitted auxiliary storage. The old binary search tree representation is consumed by this operation.
Replace suspended recursive calls by an explicit stack for an inorder traversal. Save each original right child before overwriting that link:
def flattenIterative(): (Tree, Tree) = {
  val pending = new scala.collection.mutable.Stack[Tree]
  var current = root
  var start: Tree = null
  var end: Tree = null
  while (current != null || pending.nonEmpty) {
    while (current != null) {
      pending.push(current)
      current = current.left
    }
    val t = pending.pop()
    val nextSubtree = t.right
    t.left = end
    if (end == null) start = t else end.right = t
    t.right = null
    end = t
    current = nextSubtree
  }
  root = null
  (start, end)
}
The method belongs to the concrete class owning root. Clearing root records that ownership has transferred to the returned doubly linked list; callers retain both returned endpoints. The inner loop invariant says that the current subtree lies before all its pending ancestors in inorder traversal; pushing and descending left preserves this fact. Its loop variant is the number of entries along the remaining left-child path, a finite decreasing quantity.
The outer loop invariant says that start through end is precisely the already emitted sorted prefix, with reciprocal links and null outside endpoints. current and the pending ancestors describe exactly the remaining traversal in order; original links that are still needed have been retained. A pending ancestor has not yet had its right child overwritten. The next popped entry is therefore the next sorted entry. Saving nextSubtree preserves its future work before assigning t.right = null; linking it to end extends the prefix by exactly one entry. The number of original entries not yet emitted is an outer loop variant, since each full outer iteration emits one. At exit nothing remains, proving the same preservation and ordering postconditions as the recursive version.
Each entry is pushed and popped once, giving time complexity and auxiliary space. No new Tree entries are allocated. The historical mutable stack interface provides the push and pop operations used here; its later deprecation does not change their meaning.[ref]
Use an inverse edit record with a common undo/redo interface. Positions are zero-based. For move(i,j), j is the song's final index after the move, so it is also the insertion index in the shortened sequence. For an original length , require ; insertion permits and deletion requires . As allowed, the caller guarantees validity.
trait Change {
  def undo(): Unit
  def redo(): Unit
}

class SongSuite(initial: Sequence[Song]) {
  private var songs = initial
  def length: Int = songs.length
  def elementAt(i: Int): Song = songs.elementAt(i)

  private def rawInsert(i: Int, x: Song): Unit = {
    songs = songs.insert(i, x)
  }
  private def rawDelete(i: Int): Unit = {
    songs = songs.delete(i)
  }
  private def rawMove(i: Int, j: Int): Unit = {
    val x = songs.elementAt(i)
    songs = songs.delete(i)
    songs = songs.insert(j, x)
  }
  private def perform(forward: () => Unit,
                      backward: () => Unit): Change = {
    forward()
    new Change {
      def undo(): Unit = backward()
      def redo(): Unit = forward()
    }
  }
  def insert(i: Int, x: Song): Change =
    perform(() => rawInsert(i, x), () => rawDelete(i))

  def delete(i: Int): Change = {
    val x = songs.elementAt(i)
    perform(() => rawDelete(i), () => rawInsert(i, x))
  }
  def move(i: Int, j: Int): Change =
    perform(() => rawMove(i, j), () => rawMove(j, i))
}
Song denotes the application's song type, whose internal fields are irrelevant to these operations. Sequence denotes the supplied interface; each returned sequence is assigned back, so the code does not discard the result of a functional implementation. SongSuite owns its current sequence; independent mutations through outside aliases are excluded. Atomic successful edits and an ordinary sequential history are assumed.
For inverse command correctness, inserting at is reversed by deleting at ; deleting at is reversed by reinserting the saved song there. After moving from to , removing the moved song at recovers the original sequence with that one entry missing, and reinserting it at restores the original. This also covers . Store the actual deleted song reference, rather than identifying it by title, since duplicate songs may occur.
The edits have already executed when returned. A history manager can enforce the chronological protocol with two stacks:
class History {
  private var done: List[Change] = Nil
  private var undone: List[Change] = Nil
  def record(c: Change): Unit = {
    done = c :: done
    undone = Nil
  }
  def undo(): Unit = {
    require(done.nonEmpty)
    val c = done.head
    c.undo()
    done = done.tail
    undone = c :: undone
  }
  def redo(): Unit = {
    require(undone.nonEmpty)
    val c = undone.head
    c.redo()
    undone = undone.tail
    done = c :: done
  }
}
For example, history.record(suite.move(i,j)) records an applied move. The history invariant says that the current playlist results from the applied prefix, the top of done is its last edit, and the top of undone is the first next edit available for redo. Each transfer preserves this invariant. A fresh edit clears the redo branch. Calling an arbitrary old inverse after unrelated edits is outside this protocol and need not be correct.
The Command pattern separates a request into a common command interface, concrete commands carrying arguments and execution behavior, a receiver doing the application work, an invoker requesting execution or retaining history, and a client assembling these software objects. A menu item, toolbar button or keyboard shortcut can invoke the same command without duplicating the playlist manipulation.
SongSuite is the receiver. The application/controller invokes its operations, and the returned Change software objects hold the concrete inverse/forward behavior. A command wrapper can expose an initial execute that calls the appropriate SongSuite operation and then delegates later undo/redo to its returned record. History is the history-managing part of the invoker. Separating these roles avoids making a graphical control know how the playlist representation is edited; requests can be retained and reversed through a common object interface.
If sequence versions are immutable, replace perform by the following method; the insert, delete and move entry points can stay as written:
private def perform(forward: () => Unit,
                    backward: () => Unit): Change = {
  val before = songs
  forward()
  val after = songs
  new Change {
    def undo(): Unit = { songs = before }
    def redo(): Unit = { songs = after }
  }
}
The unused inverse argument can subsequently be removed from perform and its callers. Each history record now captures two complete versions. Undo and redo restore the respective roots without replaying an operation, an instance of the Memento pattern. The same chronological history discipline still applies.
The supplied method signatures alone do not establish immutability or persistence. If insert or delete changes a shared mutable software object, merely storing its reference fails to freeze the earlier state. Then independent copies of the relevant state are needed, including any mutable song state intended to be undoable, or the implementation must provide immutable persistent data structure versions. This is a representation requirement, not a reason to invent a particular unavailable copying API.
Version snapshots simplify correctness: a complicated command restores the complete prior state, so a bespoke inverse cannot accidentally omit an auxiliary field. Redo restores the recorded result without re-executing behavior that might depend on time, randomness or external input. Restoring an immutable root takes constant time, though refreshing the display can cost more.
The storage comparison depends on the representation. A change-specific record for these elementary edits retains only a few indices and song references. Copying a length- array for each of edits can require storage and copying per edit. A persistent data structure with structural sharing can preserve many versions much more cheaply; balanced path copying can make small edits allocate new entries. Retaining versions also keeps their reachable data alive. Snapshot references are only constant-sized roots, not a guarantee of constant total retained memory. Neither scheme automatically reverses external effects such as playing audio or writing files. The desired undo boundary must be specified.
Programming language polymorphism means that one interface or program definition can be used with values of multiple types. In object-oriented programming, subtype polymorphism allows references with a common static type to denote instances of different concrete subclasses or implementers of a trait. An object method call uses dynamic dispatch to select the overriding implementation belonging to the receiver's runtime type. For example, different implementations of a playlist interface can respond to the same insert call without the client testing their concrete classes.
Parametric polymorphism uses type parameters, as in Sequence[A], so the same definition works uniformly for songs, integers, or other elements. Ad hoc polymorphism includes method overloading, where different parameter signatures share a name and the static types determine overload selection. These mechanisms are distinct: selecting an overloaded signature is not the same step as dispatching an override of that selected signature. Class inheritance can supply implementations, but the reusable interface and legal subtyping relationship determine what a polymorphic client may do.
Use pattern matching and an optional value to distinguish absence from a present result:
class PartialFn[T, U](val data: List[(T, U)]) {
  def get(x: T): Option[U] =
    data.find { case (key, _) => key == x }.map(_._2)

  def remove(x: T): PartialFn[T, U] =
    new PartialFn[T, U](data.filterNot { case (key, _) => key == x })

  def add(x: T, y: U): PartialFn[T, U] =
    new PartialFn[T, U]((x, y) ::
      data.filterNot { case (key, _) => key == x })
}
The representation precondition is that equal keys always have equal associated values, with a stable equality relation on keys. This permits harmless repeated identical pairs; it excludes conflicting outputs for one input. get therefore returns Some(y) exactly when the represented partial function is defined at x. Removing filters out every occurrence of the key and leaves all other pairs unchanged. Adding first removes every old occurrence and prepends exactly the new pair, proving the partial function update postcondition even if the input contains duplicate identical pairs. The immutable linked list representation leaves the original mapping unchanged. Each operation has worst-case time complexity for pairs under constant-cost key equality.
The second partial function accepts this one's outputs. Put this method inside the invariant class in part (b):
def compose[V](that: PartialFn[U, V]): PartialFn[T, V] = {
  val pairs: List[(T, V)] = data.flatMap {
    case (x, y) => that.get(y).map(z => (x, z)).toList
  }
  new PartialFn[T, V](pairs)
}
The represented mapping is , since the paper explicitly applies that second despite the method name. A pair is emitted exactly when this mapping supplies a y and that.get(y) supplies a z. Hence its domain of a partial function is and its value there is . This is strict composition of partial functions: either missing stage makes the composite undefined. Repeated equal input pairs still produce the same output, preserving the representation invariant. With and pairs, direct association-list lookup gives worst-case time complexity, not a hidden constant-cost dictionary lookup.
A covariant type parameter preserves subtyping: if , then PartialFn[T,A] <: PartialFn[T,B] when its second parameter is covariant. In Scala the class annotation is +U. A mapping that produces a narrower output can be used where a broader output is expected. Covariance describes a type relationship; it does not convert stored values or make mutation through a widened reference safe.[ref]
Declare +U, keep its stored linked list immutable, and generalize operations that need to accept output values by a fresh lower type bound:
class PartialFn[T, +U](val data: List[(T, U)]) {
  def get(x: T): Option[U] =
    data.find { case (key, _) => key == x }.map(_._2)

  def remove(x: T): PartialFn[T, U] =
    new PartialFn[T, U](data.filterNot { case (key, _) => key == x })

  def add[V >: U](x: T, y: V): PartialFn[T, V] =
    new PartialFn[T, V]((x, y) ::
      data.filterNot { case (key, _) => key == x })

  def compose[V >: U, W](that: PartialFn[V, W]): PartialFn[T, W] = {
    val pairs: List[(T, W)] = data.flatMap {
      case (x, y) => that.get(y).map(z => (x, z)).toList
    }
    new PartialFn[T, W](pairs)
  }
}
get, remove, and the immutable val data expose U in covariant result positions: Scala's immutable List, Tuple2 and Option preserve that position. The old add(x:T,y:U) consumed U directly, violating the variance-position rule. The new add accepts a value of a chosen supertype V and returns a new mapping with that widened output type; it never inserts the wider value into the old narrower mapping.
The original compose also mentions U as the first, invariant parameter of PartialFn[U,V]. Changing only add is therefore insufficient. Its new first type parameter V >: U is independent of the class's covariant parameter except for the allowed lower bound. Any stored y:U is acceptable to that.get as a V, while the result has output type W. This lower type bound solution avoids unchecked variance annotations or casts. The official variance rules illustrate the same lower-bound widening technique for an immutable collection's consuming method; the later 2.13 text corroborates the rule, without identifying an installed 2018 compiler version.[ref]
In the Observer pattern, an observable subject maintains subscriptions and sends notifications through a common observer interface when a relevant change occurs. Observers can then react to the event or query the subject's coherent new state. Registration and removal allow multiple dependants to change independently of the subject's application logic.
It is useful when one software object has several changing dependants, for example a document model with several views or a text field with an event handler. It avoids hard-coding every concrete dependant into the subject, reducing direct coupling and duplicated synchronization logic. Clients need not poll repeatedly to detect a change. This separation does not automatically prevent notification cycles, stale subscriptions, or inconsistent intermediate states: notification should occur after a coherent update, and observers should unregister when no longer needed. A reentrant event handler can otherwise commit recursively while refreshing a display.
A Scala Swing Publisher is the subject-side event source. Calling publish(e) notifies its subscribed reactors. A Reactor is the observer-side participant: listenTo(p1,p2) registers it with the specified sources, deafTo ends those subscriptions, and reactions contains the event-handling cases.
listenTo(pounds, euros, rate)
reactions += {
  case EditDone(source) => handleCommittedEdit(source)
}
Here the containing frame supplies the reactor behavior, and each text field supplies publication. Defining reactions without listenTo is insufficient to establish the subscription. The pattern-matching cases can handle only events of interest while other events are ignored. This is the Observer pattern expressed through event publication rather than a separate hand-written update method for every subject.[ref]
Choose a deterministic editing policy: editing pounds or the exchange rate preserves the pounds amount and recalculates euros; editing euros preserves the rate and recalculates pounds. A valid rate must be finite and positive; amounts may be any finite signed number. Keep an unrounded numeric model, so repeatedly refreshing a two-decimal display does not feed rounded text back into the computation. Place the following members inside the supplied MainFrame, after its fields are created:
private var poundsValue = 10.0
private var eurosValue = 11.5
private var rateValue = 1.15
private var refreshing = false

private def finite(x: Double): Boolean =
  !java.lang.Double.isNaN(x) && !java.lang.Double.isInfinite(x)

private def number(s: String): Option[Double] =
  scala.util.Try(s.trim.toDouble).toOption.filter(finite)

private def money(x: Double): String =
  java.lang.String.format(java.util.Locale.ROOT, "%.2f",
                          java.lang.Double.valueOf(x))

private def refresh(): Unit = {
  refreshing = true
  try {
    pounds.text = money(poundsValue)
    euros.text = money(eurosValue)
    rate.text = money(rateValue)
  } finally {
    refreshing = false
  }
}

private def commit(p: Double, e: Double, r: Double): Unit = {
  if (finite(p) && finite(e) && finite(r) && r > 0.0) {
    poundsValue = p
    eurosValue = e
    rateValue = r
    refresh()
  }
}

listenTo(pounds, euros, rate)
reactions += {
  case EditDone(source) if !refreshing =>
    number(source.text).foreach { value =>
      if (source eq pounds)
        commit(value, value * rateValue, rateValue)
      else if (source eq euros)
        commit(value / rateValue, value, rateValue)
      else if ((source eq rate) && value > 0.0)
        commit(poundsValue, poundsValue * value, value)
    }
}
The mathematical model invariant is with a positive rate. In floating-point arithmetic, each update establishes the corresponding rounded multiplication or division; a division followed by multiplication need not recover bitwise identical values. Pounds and rate edits calculate a matching euro amount, while euro edits calculate its matching pound amount. An invalid parse, a nonpositive rate, or a nonfinite calculated result leaves the last valid numeric model unchanged. An invalid text entry may remain visible until corrected or a subsequent valid refresh; a production interface could add a validation message.
Every accepted edit refreshes the fields from that model. Locale.ROOT makes the decimal separator match the toDouble parser, independently of the machine's locale. The guard prevents a synchronous reentrant event handler from interpreting a refresh as another user commit. The displayed values are rounded to two decimal places, including the rate, while the stored values retain full Double precision. Very small positive rates can therefore display as 0.00; using more rate digits is a reasonable presentation refinement. Pounds, euros and rate edits all propagate by the stated policy, with no parsing exception or division by zero.
EditDone handles completion of an edit, such as an action or focus-change notification, using the event type supplied in the paper. It is not a promise of recalculation after every keystroke. A character-by-character interface would subscribe to the corresponding text-change event instead. The publisher/reactor interaction follows the supplied contract and official Scala Swing documentation; no exact course library build or native graphical execution is presumed.[ref]
Model-view-controller divides an interactive application into a model containing application state and domain rules, a view rendering that state, and a controller interpreting user actions and requesting model operations. In the converter, the numeric amounts and exchange relation belong to the model, the text fields and labels form the view, and the edit handler parses input and chooses which quantity to preserve. A playlist model similarly owns song order independently of the controls used to change it.
A user acts through the view, the controller interprets that input, the model validates and commits a change, and the view then renders the resulting state. The exact packaging varies: a widget can combine view and controller responsibilities while still separating domain logic. Keeping the model independent of particular controls supports separation of concerns, encapsulation, reuse of the same model in several views, and unit testing of domain behavior without a graphical interface.
The Observer pattern often supplies the model-to-view notification path: views subscribe to model changes, so the model need not directly know every concrete view. It can also carry view input events to a controller, as in Scala Swing. Model-view-controller is an architectural separation of responsibilities; the Observer pattern is one mechanism for their communication. They are related without being identical, and small applications can implement the separation with direct calls where event subscriptions add no benefit.

Ancestors (9)

  1. 2018
  2. Past exam of the year 1 of the computer science course of the University of Oxford
  3. Year 1 of the computer science course of the University of Oxford
  4. Computer science course of the University of Oxford
  5. Undergraduate course of the University of Oxford
  6. Course of the University of Oxford
  7. University of Oxford
  8. List of universities
  9. Home

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version