Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 8 / a / Solution 2026-10-31
View more
The interval containment order compares the lower endpoints in reverse and the upper endpoints in their ordinary order. The smallest containing integer interval uses the smaller lower endpoint and the larger upper endpoint.
class Interval(val l: Int, val u: Int) extends Ordered[Interval] {
  require(l <= u)
  def <=(that: Interval): Boolean = that.l <= l && u <= that.u
  def lub(that: Interval): Interval =
    new Interval(math.min(l, that.l), math.max(u, that.u))
}
Endpoint comparison immediately proves reflexivity, transitivity, and antisymmetry on interval values. If two separately allocated instances have the same endpoints, they denote the same abstract interval; object identity is not the mathematical equality used by this partial order.
The returned interval contains both operands. Every other containing interval has a lower endpoint at most both original lower endpoints and an upper endpoint at least both original upper endpoints, so it also contains the returned hull. Hence
(1)
This least upper bound need not equal the ordinary union: the hull of and is , including the gap.
Read the full article