4

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/[email protected]#post-eweortsmcmibppmvtriw:40forum.dlang.org.

3 Answers 3

6

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.

3
  • Maybe you should add a reference to this great answer in the github issue thread for more background on why the std.algorithm pull request is motivated?
    – Nordlöw
    Commented Jan 14, 2014 at 9:19
  • 1
    One reflection though... - doesn't all the elements have to be of the same type in order to be isAssignable to each other in all directions (combinations)? I believe !CommonType!T == void is not a sufficient requirement for this.
    – Nordlöw
    Commented Jan 14, 2014 at 9:23
  • You are right that the constraint is too lax, but this is because the pointers to each parameter need to have a common type. I updated the answer. Commented Jan 14, 2014 at 12:42
5

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.

3
  • I believe we need to define an overload (or static ifs) for each specific n if we want optimal performance, compared to reusing qsort. Thx anyway.
    – Nordlöw
    Commented Jan 13, 2014 at 23:14
  • 2
    Since this is a template, each different set of arguments will result in a specialized function anyway. Commented Jan 13, 2014 at 23:18
  • Aha, so Phobos sort contains these specializations then. Great.
    – Nordlöw
    Commented Jan 13, 2014 at 23:19
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.

1
  • Hum... I did some checking, and this solution actually generates a really high amount of comparators. It highly inefficient. Commented Jan 14, 2014 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.