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.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.
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))
}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. HenceThis least upper bound need not equal the ordinary union: the hull of and is , including the gap.
Keep precisely those elements with no strictly smaller element in the input. Express strictness using the partial order itself, avoiding reliance on Scala reference equality.In a partial order, means and . ThereforeThe empty set produces the empty set. An incomparable pair is retained in full; a minimal element need not be a least element. At most order comparisons are needed, and only the supplied F-bounded generic interface is required.
def minimal[T <: Ordered[T]](xs: Set[T]): Set[T] =
xs.filter { x =>
!xs.exists(y => (y <= x) && !(x <= y))
}Store the minimal elements of the finite generating set. The represented upper set itself may be infinite; the code manipulates its finite basis.The abstraction function and representation invariant areRemoving nonminimal generators preserves the upward closure: in a finite generating set, repeatedly descending below any discarded element must reach a retained minimal element. Thus the constructor represents exactly the required finitely generated upper set.
class UpSet[T <: Ordered[T]](c: Set[T]) extends Ordered[UpSet[T]] {
private val basis: Set[T] = minimal(c)
def contains(x: T): Boolean = basis.exists(a => a <= x)
def intersection(that: UpSet[T]): UpSet[T] = {
val generators: Set[T] =
for (a <- basis; b <- that.basis) yield a.lub(b)
new UpSet[T](generators)
}
def <=(that: UpSet[T]): Boolean = basis.forall(a => that.contains(a))
def lub(that: UpSet[T]): UpSet[T] =
new UpSet[T](basis union that.basis)
}Membership follows directly from the abstraction function. For intersection, an element lies above some and some exactly when it lies above their least upper bound:The forward implication is the defining leastness property; the reverse uses that is an upper bound and transitivity. ConsequentlyRecomputing minimal elements therefore yields a finite basis for the exact intersection.
For subset inclusion, it suffices that every generator of the left-hand upper set belongs to the right-hand upper set. Necessity holds because each generator belongs to its own closure by reflexivity. Sufficiency holds because the right-hand set is upward closed. Finally,Thus
lub computes union, which is the least upper bound under subset inclusion. The empty basis represents the empty set; all four methods handle it without a special case. As in part (a), two distinct Scala objects may denote the same abstract ordered value. Retaining several equivalent representatives is harmless: they generate the same upward closure, and the strict-comparison test removes only genuinely nonminimal values. Articles by others on the same topic
There are currently no matching articles.