Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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 ab einer Netzwerkbreite
- // von 1024 in die Knie. 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;
- result[pos..pos+2] = "[";
- 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(8192); // compile-time! -> 6mb executable
- print_network( net );
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement