Batcher Odd-Even #2

module main;

import std.stdio;
import std.algorithm;
import std.conv;

struct cas_args {
    int arg0 = -1;
    int arg1 = -1;
};

void print_network( const ref cas_args[][] cas_net )
{
    for( int i=0; i<cas_net.length; ++i ) {
        for( int j=0; j<cas_net[i].length; ++j ) {
            if( cas_net[i][j] != cas_args(-1,-1) ) {
                write( "cas(", cas_net[i][j].arg0, ", ", cas_net[i][j].arg1, ")" );
            }
        }
        write("\n");
    }
}

// Ich bin mir nicht sicher, oder log2 garantiert, dass der nächste
// ganze Wert entsteht, wenn man 2^N als Argument verwendet, oder
// ob da auch einmal etwas echt kleineres als die ganze Zahl herauskommt
// und dann abgerundet wird...
int power2log( int N )
{
    int log=0;
    while( N > 1 ) { N/=2; ++log; }
    return log;
}

int CalculateDepth( int N )
{
    int x = power2log(N);
    return (x*(x+1))/2;
}

// leider funktioniert "reserve" nicht zur compile-zeit
// daher müssen die Elemente alle mit einem Spezial-Wert
// gefüllt werden und immer nach dem ersten freien
// gesucht werden (alternativ müsste man im ersten Element
// die größe speichern, aber dann müssten alle Algorithmen
// immer +1 ausschreiben...
int FirstFree( const ref cas_args[] cas_list )
{
    for( int i=0; i<cas_list.length; ++i ) {
        if( cas_list[i] != cas_args(-1,-1) ) return i;
    }
    return 0;
}

void GenerateMerge( ref cas_args[][] cas_net, int base, int N, int stride=1, int offset=0)
{
    int index = FirstFree(cas_net[base]);
    if( N > 2 ) {
        GenerateMerge( cas_net, base-1, N/2, stride*2, offset );
        GenerateMerge( cas_net, base-1, N/2, stride*2, offset+stride );
        for( int i = 1; i <= N-3; i += 2 ) {
            cas_net[base][index++] = cas_args(i*stride+offset,(i+1)*stride+offset);
        }
    } else  {
        cas_net[base][index] = cas_args(offset,stride+offset);
    }
}

void GenerateSort( ref cas_args[][] cas_net, int base, int N )
{
    if( N > 1 ) {
        int thismerge = power2log(N);
        // Oberen vorhergehenden Sort generieren
        GenerateSort( cas_net, base-thismerge, N/2 );
        // Unteren aus oberem erzeugen
        for( int j=0; j<=base-thismerge; ++j ) {
            for( int k=N/2; k<N; ++k ) {
                cas_net[j][k] = cas_net[j][k-N/2];
                if(cas_net[j][k]==cas_args(-1,-1)) continue;
                cas_net[j][k].arg0 += N/2;
                cas_net[j][k].arg1 += N/2;
            }
        }
        // Merge-Netzwerk
        GenerateMerge( cas_net, base, N );
    }
}

cas_args[][] GenerateNetwork(int N)
{
    int depth = CalculateDepth(N);
    cas_args[][] result;
    result.length = depth;
    for( int i=0; i<depth; ++i ) {
        result[i].length = N;
    }

    GenerateSort( result, depth-1, N );
    return result;
}

string GenerateNetworkMixin( string arr, string op, int size )
{
    cas_args[][] network = GenerateNetwork( size );

    string result;

    string arg0;
    string arg1;

    int pos = 0;

    // Diese Schleife zwingt den Compiler schnell in die Knie, offenbar
    // bricht er lieber ab, bevor er swappen müsste, weil auf unterschiedlichen
    // Rechner mit selbem Speicherausbau unterschiedliche Grenzen bestehen.
    // Wenn man mehr will, sollte man irgendwie
    // klug die Größe vorbestimmen (aber achtung, reserve funktioniert
    // ja nicht) und dann nur noch mit dem Feld arbeiten. to!string
    // müsste dann wahrscheinlich durch irgendein in-place-Algo
    // ersetzt werden...
    for( int i=0; i<network.length; ++i ) {
        for( int j=0; j<network[i].length; ++j ) {
            if( network[i][j] == cas_args(-1,-1) ) continue;
            arg0 = arr~"["~to!string(network[i][j].arg0)~"]";
            arg1 = arr~"["~to!string(network[i][j].arg1)~"]";
            result ~= "if("~arg0~op~arg1~") swap("~arg0~","~arg1~");\n";
            arg0.clear();
            arg1.clear();
        }
    }

    return result;
}

int main(string[] argv)
{
    int arr[512];
    mixin(GenerateNetworkMixin("arr", ">", arr.length));
    static cas_args[][] net = GenerateNetwork(4096); // -> 3 mb Netzwerkdatan plus minus
    print_network( net );

    return 0;
}