= Solution
Represent the <set> by a private <list> containing each value once. Normalize the constructor input as well as checking future insertions; otherwise duplicate initial entries would violate the intended <set> behavior.
``
class Set[T](contents: List[T]) {
protected var elems: List[T] = contents.distinct
def add(x: T): Unit = {
if (!elems.contains(x)) elems = x :: elems
}
def delete(): T = {
require(elems.nonEmpty)
val x = elems.head
elems = elems.tail
x
}
}
``
The <representation invariant> is that `elems` contains no duplicates under the chosen stable value equality; the <abstraction function> forgets its ordering and returns its <set> of elements. The protected field allows the subclass in part (d) to inspect its contents; that subclass is responsible for preserving the <representation invariant> if it mutates them.
Insertion makes the represented <set> $S\cup\{x\}$. Deletion requires $S\ne\varnothing$, returns some $x\in S$, and leaves $S\setminus\{x\}$. Thus
$$
\boxed{add(x):S'=S\cup\{x\};\qquad delete():x\in S,\ S'=S\setminus\{x\}.}
$$
Deletion does not promise to choose a <minimum>. With this <linked list> representation, insertion takes $O(|S|)$ <time complexity> because of its membership check, while deletion takes $O(1)$. Values should not mutate in a way that changes their equality while stored.
Back to article page
