Companion class 2026-10-24
View more
In Scala, a class paired with a same-named companion object in the appropriate source context. They can access each other's private members. This permits a companion object to hide implementation-node definitions while the corresponding class creates and manipulates those nodes.[ref]
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Imperative programming (resit) / 6 / b / i / Solution 2026-10-25
View more
Use a fixed-size count array and protected hooks defining a stable character-to-slot mapping. The default hooks count the ASCII lowercase interval. The document must start empty, and all subsequent edits must pass through the mixin methods, as they do for new DocImp with CharCountPlugin.
trait CharCountPlugin extends Doc {
  protected def firstCounted: Char = 'a'
  protected def numberCounted: Int = 26
  protected def slot(ch: Char): Int = {
    val k = ch.toInt - firstCounted.toInt
    if (0 <= k && k < numberCounted) k else -1
  }
  private lazy val totals = Array.fill(numberCounted)(0)

  abstract override def insert(pos: Int, ch: Char): Unit = {
    val k = slot(ch)
    super.insert(pos, ch)
    if (k >= 0) totals(k) += 1
  }

  abstract override def delete(pos: Int): Char = {
    val removed = super.delete(pos)
    val k = slot(removed)
    if (k >= 0) totals(k) -= 1
    removed
  }

  def count(ch: Char): Int = {
    val k = slot(ch)
    require(k >= 0, "character is outside the counted alphabet")
    totals(k)
  }
}
The additional representation invariant is that each array slot equals the number of corresponding characters in the current document. Initially all counts are zero. Each successful underlying edit changes exactly one relevant count, while a failed position check throws before any count is changed. Returning the actual deleted character lets deletion adjust the correct slot.
count takes time for the fixed alphabet, as do the mixin's additions to edit cost. The lazy array avoids reading subclass-overridden size hooks during trait construction; the hooks must remain stable. An extension can override the interval hooks, or override slot with another fixed finite mapping. This is stackable modification by a trait: abstract override permits the method to call the next implementation of super, supplied here by DocImp.[ref]
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Imperative programming / 3 / e / Solution 2026-10-25
View more
The following method belongs inside the source class and uses the helper from part (d). It preserves the existing outgoing count, and a newly encountered user starts with exactly one incoming and zero outgoing payments.
def recordIncoming(user: Int): Unit = {
  require(1 <= user && user <= 99999999, "invalid user identity")
  val bucket = hash(user)
  val p = find(user, table(bucket))
  if (p == null) {
    table(bucket) = new PaymentsHash.Node(user, 1, 0, table(bucket))
  } else {
    require(p.countIn < Int.MaxValue, "incoming count is full")
    p.countIn += 1
  }
}
On a hit, exactly one field is incremented after the overflow check. On a miss, inserting at the bucket head preserves all existing records and gives precisely the required change from implicit zero to one. The given hash function must return an index in consistently for a given user. Its actual formula is not needed by this method. The nested private node class is accessible to its companion class in Scala, so retaining the source's PaymentsHash.Node visibility is valid.[ref]
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Imperative programming / 6 / a / Solution 2026-10-25
View more
Method overloading gives one name several parameter signatures, such as show(A) and show(B). The compiler chooses an applicable signature using the receiver's static type and the argument expressions' static types, preferring a uniquely more specific applicable alternative. An argument whose type is a subtype of the parameter type is acceptable; ambiguous or inapplicable alternatives cause a compile-time error. The runtime type of an argument does not start a second overload search.
Method overriding replaces an inherited implementation of the same method signature. After overload selection, ordinary instance calls use dynamic dispatch on the receiver's runtime type to select the most-derived implementation of that signature. A concrete inherited method requires the override keyword in Scala; a super call invokes the corresponding superclass implementation instead of redispatching to the overriding body. In a trait stack, super follows the class's linearization.[ref][ref]
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Imperative programming / 7 / a / Solution 2026-10-25
View more
The Memento pattern supports saving and later restoring an object's state while preserving encapsulation. The originator creates a snapshot and knows how to restore it; the memento stores that snapshot; the caretaker retains mementos and decides when to request restoration, without depending on their representation. Undo history is a typical use.
Scala's nested class in object-oriented programming definitions, access qualifiers, immutable values and path-dependent types help keep snapshots opaque and associated with their originator. For example:
final class Editor {
  private var text = ""
  final class Snapshot private[Editor] (
    private[Editor] val saved: String
  )
  def current: String = text
  def edit(next: String): Unit = { text = next }
  def save(): Snapshot = new Snapshot(text)
  def restore(s: Snapshot): Unit = { text = s.saved }
}

val editor = new Editor
editor.edit("first version")
val saved: editor.Snapshot = editor.save()
editor.edit("later version")
editor.restore(saved)
assert(editor.current == "first version")
The caretaker can retain saved but cannot inspect its private contents or construct an arbitrary snapshot. editor.Snapshot is a type tied to the stable editor value; a snapshot from a different Editor is not interchangeable without an explicit type escape. An immutable string is safe to share in this example. If the originator held mutable arrays or mutable nodes, storing only references to them would not freeze their contents; the memento would need a deep copy or a persistent immutable representation.[ref][ref]
Read the full article