Comb Sort with ranges

[bearophile]

This removes two of the three bugs. But this code doesn't work yet with a class that implements a collection, because code like:
auto right = data;
copies just the reference to the data object. Suggestions welcome.

I have also seen that some of the functions of std.range don't work with static arrays, so I've had to roll my own fixed versions, see the isSorted() below.

Bye,
bearophile



import std.algorithm: swap, binaryFun, sort;
import std.range: isForwardRange, walkLength, popFrontN, empty, front,
                  popFront, hasSwappableElements, equal;
import std.contracts: enforce;


void combsort(alias less="a < b", Range)(Range r)
    if (__traits(isStaticArray, Range) || (isForwardRange!Range && hasSwappableElements!Range)) {

        static void combsort_impl(Range2)(Range2 data) {
            // From: http://en.wikipedia.org/wiki/Comb_sort
            enum double SHRINK_FACTOR = 1.247330950103979;
            auto gap = walkLength(data);
            bool swapped = true;

            while ((gap > 1) || swapped) {
                if (gap > 1)
                    gap /= SHRINK_FACTOR;

                swapped = false;
                auto right = data;
                popFrontN(right, gap);

                for (auto left = data; !right.empty; left.popFront, right.popFront) {
                    if (binaryFun!(less)(right.front, left.front)) {
                        swap(left.front, right.front);
                        swapped = true;
                    }
                }
            }
        }

        // postcondition verified in debug mode only.
        // Workaround: necessary because D postconditions don't
        // support the "old" (original input data view) yet.
        debug {
            static if (__traits(isStaticArray, Range)) {
                auto r_copy = array(r[]);
                sort!(less)(r_copy);
                combsort_impl(r[]);
                enforce(equal(r[], r_copy));
            } else {
                auto r_copy = array(r);
                sort!(less)(r_copy);
                combsort_impl(r);
                enforce(equal(r, r_copy));
            }
        } else {
            static if (__traits(isStaticArray, Range))
                combsort_impl(r[]);
            else
                combsort_impl(r);
        }
    } // end combsort()


// no way to give a checked name to the unittest yet
unittest { // tests of combsort()
    // TODO
} // end tests of combsort()


//------------------------------------

// imports local to the main()
// function-local imports not supported yet
import std.stdio: writeln;
import std.range: SListRange, array;
import std.algorithm: isSorted_impl = isSorted;
import std.string: format;

bool isSorted(alias less="a < b", Range)(Range data)
    if (__traits(isStaticArray, Range) || isForwardRange!Range) {
        static if (__traits(isStaticArray, Range))
            return isSorted_impl!(less)(data[]);
        else
            return isSorted_impl!(less)(data);
}

void main() {
    int[] a = [10, 1, 5, 3, 7, -1, 5, 21, -3];
    writeln(isSorted(a), " ", a);
    combsort(a);
    writeln(isSorted(a), " ", a);
    writeln();

    auto lst = SListRange!int(10, 1, 5, 3, 7, -1, 5, 21, -3);
    writeln(isSorted(lst), " ", array(lst));
    combsort(lst);
    writeln(isSorted(lst), " ", array(lst));
    writeln();

    int[9] b = [10, 1, 5, 3, 7, -1, 5, 21, -3];
    writeln(isSorted(b), " ", b);
    combsort(b);
    writeln(isSorted(b), " ", b);
    writeln();
}

Bye,
bearophile