Порядок размещения элементов на месте

Question

Есть ли у Phobos некоторый вариационный алгоритм для заказа опорных аргументов l-value? Что-то вроде

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 

Также функциональный вариант, скажем order(a, b, c), который возвращает кортеж будет также приятно.

Если нет, я думаю, мы должны использовать std.algorithm:swap.

См. Также http://forum.dlang.org/thread/eweortsmcmibppmvtriw@forum.dlang.org#post-eweortsmcmibppmvtriw:40forum.dlang.org.

Answer 1

Решение Адама работает, хотя используется временная копия элементов. С small modification to std.algorithm, можно написать версию, которая сортирует элементы в месте:

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]); 
} 

Однако это имеет смысл только, если значения, передаваемые orderInPlace большие, не могущие быть переданным, уступленные, цедированные или иначе непрактичные для копирования.

Answer 2

Я не думаю, что Фобос имеет один, но вы можете сделать свой собственный вроде как это:

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, вроде нужен массив, но это достаточно легко - мы скопировали кортеж в стек, отсортировал его, а затем скопировал информацию обратно в кортеж. Так что, возможно, не идеально, но это сработает. Вы можете сделать его функциональным, просто вернув t вместо того, чтобы делать это ref.

Answer 3

Возможно, сортировочная сеть наиболее эффективна с учетом небольшого числа аргументов и того факта, что их число известно во время компиляции (без условий цикла).

Тип пузыря хорошо подходит для сортировки сети. Я бросил это вместе. Она работает, и это действительно просто:

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

Хотя, честно говоря, если это стандартная библиотека, любая сортировка сеть менее 10 аргументов должны быть рукописными.

EDIT: Я полностью изменил предыдущий алгоритм, который был на самом деле очень неопределенным. Сорт Bubble не оптимальный, но он действительно работает нормально для алгоритмов сортировки. Там есть некоторые прагмы, чтобы увидеть построенную сеть.