In-Place Ordering of Elements

Question

Does Phobos have some variadic algorithm to order l-value reference arguments in place? Something like

int a=3;
int b=2;
int c=1;

orderInPlace(a,b,c);

// a is now 1
// b is now 2
// c is now 3

Also a functional variant, say order(a, b, c), that returns a tuple would also be nice.

If not, I guess we should make use of std.algorithm:swap.

See also http://forum.dlang.org/thread/eweortsmcmibppmvtriw@forum.dlang.org#post-eweortsmcmibppmvtriw:40forum.dlang.org.

Answer 1

Adam's solution works, although it uses a temporary copy of the elements. With a small modification to std.algorithm, it's possible to write a version which sorts the elements in-place:

import std.algorithm;
import std.stdio;
import std.traits;
import std.typecons;

struct SortableRef(T)
{
    private T * _p;
    @property ref T value() { return *_p; }
    alias value this;
    void opAssign(T * value) { _p = value; }
    @disable void opAssign(SortableRef!T value);
    void proxySwap(SortableRef!T other) { swap(*_p, *other._p); }
}

template PointerTo(T) { alias T* PointerTo; }
void orderInPlace(T...)(ref T values)
    if (!is(CommonType!(staticMap!(PointerTo, T)) == void))
{
    alias CommonType!T E;
    SortableRef!E[values.length] references;
    foreach (i, ref v; values)
        references[i] = &v;
    references[].sort();
}

void main()
{
    int a=3;
    int b=1;
    int c=2;
    orderInPlace(a, b, c);
    writeln([a, b, c]);
}

However, it is only practical if the values passed to orderInPlace are large, unassignable, or otherwise impractical to copy.

Answer 2

I don't think Phobos has one, but you could make your own kinda like this:

void orderInPlace(T...)(ref T t) {
    import std.algorithm;
    T[0][T.length] buffer;
    foreach(idx, a; t)
        buffer[idx] = a;
    auto sorted = sort(buffer[]);
    foreach(idx, a; t)
        t[idx] = sorted[idx];
}

std.algorithm,sort needs an array, but that's easy enough - we copied the tuple into a stack array, sorted it, then copied the info back into the tuple. So maybe not perfect but it'd work. You can make it functional by just returning t instead of doing it ref.

Answer 3

A sorting network here is probably what would be most efficient given the low number of arguments, and the fact that their number is compile-time known (no loop conditions).

bubble sort lends itself well to being sort network'ed. I threw this together. It works and is really simple:

import std.stdio, std.string;

void bubbleSort(T...)(ref T values)
{
    static if (T.length > 1)
    {
        foreach(I, _; T[0 .. $ - 1])
        {
            pragma(msg, format("[%s %s]", I, I + 1));
            compareAndSwap(values[I], values[I + 1]);
        }
        bubbleSort(values[0 .. $ - 1]);
    }
}
void compareAndSwap(T)(ref T a, ref T b)
{
    import std.algorithm;
    if(a > b)
        swap(a, b);
}

void main()
{
    int a =  10;
    int b =  30;
    int c =  11;
    int d =  20;
    int e =   4;
    int f = 330;
    int g =  21;
    int h = 110;
    shellSort(a, b, c, d, e, f, g, h);
    writefln("%s %s %s %s %s %s %s %s!", a, b, c, d, e, f, g, h);
}

Although to be honest, if this was standard library, any sorting network of less than 10 arguments should be hand written.

EDIT: I completely changed the previous algorithm, which was actually highly ineficient. Bubble sort is not optimal, but it actually works OK for sorting algorithms. There's some pragmas in there to see the network that's built.