 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2019/imperative-programming/3/c/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming / 3 / c / Solution by

Codex  0 2026-10-25

Represent the characteristic values of a bounded universe by one Boolean slot per possible member, a Boolean-array form of a bitset:

class BitMapSet(val MAXVALUE: Int) extends IntSet {
  require(MAXVALUE >= 0)
  private val bits = Array.fill(MAXVALUE)(false)
  private var count = 0

  def contains(elem: Int): Boolean =
    0 <= elem && elem < MAXVALUE && bits(elem)

  def add(elem: Int): Boolean = {
    require(0 <= elem && elem < MAXVALUE, "Outside bitmap universe")
    if (bits(elem)) false
    else {
      bits(elem) = true
      count += 1
      true
    }
  }

  def size: Int = count
}

The abstraction function is

α (bi t s, co u n t) = {x : 0 \leq x < M A X V A LU E, bi t s (x)}

. The representation invariant is that bits.length==MAXVALUE, its entries are Boolean, and count equals the number of true entries. Initialization gives the empty set; changing a false entry to true adds exactly its index and increments the count once. A repeated addition preserves both. All three operations have

O (1)

time complexity after initialization; storage and explicit array initialization are

Θ (M A X V A LU E)

The constructor requires $M A X V A LU E \geq 0$ , and add requires $0 \leq e l e m < M A X V A LU E$ . contains remains total by returning false outside the representable universe; short-circuit evaluation protects the index. This finite representation cannot implement unrestricted addition of every Int while preserving the abstract contract. Its strengthened add precondition therefore makes it a restricted implementation, not a behaviorally substitutable implementation of the unrestricted trait for arbitrary clients. The sequence client below proves that it stays within the restricted universe.

 Read the full article

 New to topics? Read the docs here!