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.The representation invariant is that
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
}
}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 . Deletion requires , returns some , and leaves . ThusDeletion does not promise to choose a minimum. With this linked list representation, insertion takes time complexity because of its membership check, while deletion takes . Values should not mutate in a way that changes their equality while stored.
Articles by others on the same topic
There are currently no matching articles.