Comb Sort with ranges

[bearophile]

As exercise to learn D2 ranges usage I've translated to D2 the C++ version of the Comb sort:
http://en.wikipedia.org/wiki/Comb_sort#C.2B.2B_Implementation

It wasn't easy, but on those tests it works!
Do you see errors or things that can be improved in this D2 code?

I have verified that the program performs the same swaps with the array and the single linked list (but unittests are missing still).

The combsort_impl inner function is a workaround for the lack of the "old" view of the input data in D postconditions.

In C++ the gap is of type std::iterator_traits<ForwardIterator>::difference_type, but in D I have used just an int, I don't know why they have used that type in C++.

In the C++ code itLeft and itRight are single items, probably single CPU words, while in D they can be two words or more (for example when data is a dynamic array). Can this cause some loss of performance compared to the C++ code? (I have not done benchmarks to compare the performance of the C++ version with the D version yet).


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 data)
    if (isForwardRange!Range && hasSwappableElements!Range) {

        static void combsort_impl(Range data) {
            // From: http://en.wikipedia.org/wiki/Comb_sort
            enum double SHRINK_FACTOR = 1.247330950103979;
            int 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 {
            auto data_copy = array(data);
            sort!(less)(data_copy);
            combsort_impl(data);
            enforce(equal(data, data_copy));
        } else {
            combsort_impl(data);
        }
    } // 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;

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();

    /*
    // doesn't work with static arrays
    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