Ordering with Comparable

A type whose values sort in one order declares the Comparable trait. It asks for one method, compare(other), which returns a negative number, zero or a positive number as the value sorts before, with or after other, and gives the type the rest:

• the operators <, <=, > and >=;
• min(other), max(other) and clamp(low, high) (which panics when low sorts after high);
• a place as a Map key or Set element, in that order;
• the constraint T: Comparable in a generic function, whose body can then use all of the above on a T.

struct Version {
    var major: int;
    var minor: int;

    construct(this.major = 0, this.minor = 0) {}

    # The one method Comparable asks for.
    compare(other: Version): int {
        var order = major.compare(other.major);
        if (order != 0) {
            return order;
        }
        return minor.compare(other.minor);
    }
}

extend Version with Comparable;

# A generic function asks for an order with `T: Comparable`.
largest<T: Comparable>(items: Array<T>): T {
    var best = items[0];
    for (var item in items) {
        best = best.max(item);
    }
    return best;
}

main(): int {
    # `<`, `<=`, `>` and `>=` come from `compare`.
    assert(Version(1, 2) < Version(1, 10), "1.2 sorts before 1.10");
    assert(Version(2, 0).min(Version(1, 9)).major == 1, "min");
    assert(Version(3, 0).clamp(Version(1, 0), Version(2, 0)).major == 2, "clamp");

    # Numbers and strings are Comparable too.
    assert(largest([3, 9, 2]) == 9, "numbers");
    assert(largest(["pear", "apple"]) == "pear", "strings");
    assert((15).clamp(0, 10) == 10, "clamp a number");

    # A Comparable struct is a Map key, in its order.
    var releases = Map<Version, String>();
    releases[Version(2, 0)] = "second";
    releases[Version(1, 5)] = "first";
    assert(releases.first().value().1 == "first", "sorted by compare");

    # Sorting takes the order as a comparer.
    var versions = [Version(2, 1), Version(1, 5)];
    versions.sort((a, b) => a.compare(b));
    assert(versions[0].major == 1, "sorted");
    return 0;
}

A type that declares its own < (or min, or any of the others) keeps it; the trait’s version fills in only what the type leaves out.

compare must give a total, consistent order: the same two values always compare the same way, a.compare(b) has the opposite sign of b.compare(a), and if a sorts before b and b before c, a sorts before c. Map, Set and sorting depend on it.

Numbers, char and String

Every number type and char is Comparable by value, and String by content, the order of String.compare. Their compare returns -1, 0 or 1 (String.compare any negative or positive number).

float and double compare in a total order: NaN sorts after every number and with every other NaN, and -0.0 sorts with 0.0. Their <, <=, > and >= keep IEEE behavior, false whenever a NaN takes part, while compare, clamp and Map keys follow the total order, so a NaN key cannot break a map.

Not yet

• Array.sort() takes a comparer: items.sort((a, b) => a.compare(b)) sorts in the elements’ own order. A sort() with no comparer comes once the published toolchain that builds Pepper has the compiler fix this needs.
• Tuples and Optional are not Comparable, and Comparable is not derived from a struct’s fields: a struct writes its compare, as Version does above.