• bearophile (51/51) Jan 10 2010 This is the sort() of Phobos2, a bit reformatted (a name changed, sortIm...
• bearophile (3/3) Jan 11 2010 Are the contents of this post too much stupid/useless?

bearophile <bearophileHUGS lycos.com> writes:

This is the sort() of Phobos2, a bit reformatted (a name changed, sortImpl =>
sortImplementation):

void sort(alias less = "a < b", SwapStrategy ss=SwapStrategy.unstable,
Range)(Range r) {
    alias binaryFun!(less) lessFun;

    static if (is(typeof(lessFun(r.front, r.front)) == bool)) {
        sortImplementation!(lessFun, ss)(r);
        assert(isSorted!(lessFun)(r));
    } else {
        static assert(false, "Invalid predicate passed to sort: " ~ less);
    }
}

That static assert at the end gives an error message if the given predicate is
wrong, or if the items are not sortable:
cdouble[] a = [2+0i, 5+0i, 7+0i, 9+0i, 11+0i];

That final static assert contains a ~less that doesn't work in general, because
the predicate is not always a string:
sort!((x, y){return x + y;})(a);


Thanks to the Bugzilla 2816 fix the compilation error messages are better, but
D2 has template constraints, so they may be used (code not tested):

void sort(alias less = "a < b", SwapStrategy ss=SwapStrategy.unstable,
Range)(Range r)
if (is(typeof(binaryFun!less(r.front, r.front)) == bool)) {
    alias binaryFun!less lessFun;
    sortImplementation!(lessFun, ss)(r);
    assert(isSorted!lessFun(r));
}

But isn't the typeof() of a callable different from its ReturnType!() ?

Or less nice looking (code not tested):

void sort(alias less = "a < b", SwapStrategy ss=SwapStrategy.unstable,
Range)(Range r)
if (__traits__(compiles, { bool b = binaryFun!less(r.front, r.front); })) {
    alias binaryFun!(less) lessFun;
    sortImplementation!(lessFun, ss)(r);
    assert(isSorted!(lessFun)(r));
}

That (if I have written correct code) correctly gives error messages at the
instantiation site only, but the error message is not specific.


So it may be possible to extend D2 semantics to add an else clause to the
template constraints, to print a message:

void sort(alias less = "a < b", SwapStrategy ss=SwapStrategy.unstable,
Range)(Range r)
if (__traits__(compiles, { bool b = binaryFun!less(r.front, r.front); })) {
    alias binaryFun!(less) lessFun;
    sortImplementation!(lessFun, ss)(r);
    assert(isSorted!(lessFun)(r));
} else {
	static assert(false, "Invalid predicate passed to sort: " ~ less);
	//pragma(msg, "Invalid predicate passed to sort: " ~ less);
}

I guess such else clause can't be present if there are other templated
functions named sort()... This is not fully nice.

-------------------

I've tried to sort some integers, but I don't understand the error message:

import std.algorithm: sort;
void main() {
    int[] a = [2, 5, 7, 9, 11];
    sort!("a <= b")(a);
}

core.exception.AssertError C:\...\dmd\src\phobos\std\array.d(253): Attempting
to fetch the front of an empty array

Bye,
bearophile

bearophile <bearophileHUGS lycos.com> writes:

Are the contents of this post too much stupid/useless?

Bye,
bearophile