Use an upper type bound requiring each element type to implement the supplied comparison interface for its own type. This is F-bounded polymorphism.Use this locally defined
trait Ordered[T] {
def <(that: T): Boolean
}
class MinSet[T <: Ordered[T]](contents: List[T])
extends Set[T](contents) {
def min: T = {
require(elems.nonEmpty)
var best = elems.head
var rest = elems.tail
while (rest.nonEmpty) {
if (rest.head < best) best = rest.head
rest = rest.tail
}
best
}
}Ordered, rather than silently substituting the standard library's different comparison interface. The type bound makes rest.head < best well typed. To interpret the result as a minimum, require the comparison to be a consistent strict total order; merely providing a method named < cannot establish its mathematical laws.The loop invariant is that
best is a minimum among the entries already inspected, and rest is exactly the uninspected suffix. Comparing its next head with best preserves that property. The loop variant is the length of rest. On termination,The method leaves the set unchanged, takes time complexity under constant-cost comparisons, and uses constant auxiliary space. It requires a nonempty set; inherited insertion and deletion continue to preserve the duplicate-free representation invariant. Articles by others on the same topic
There are currently no matching articles.