//
// Cforall Version 1.0.0 Copyright (C) 2017 University of Waterloo
//
// The contents of this file are covered under the licence agreement in the
// file "LICENCE" distributed with Cforall.
//
// quickSort.c -- In-place concurrent quick-sort: threads are created to partition to a specific depth, then sequential
//		recursive-calls are use to sort each partition.
//
// Author           : Peter A. Buhr
// Created On       : Wed Dec  6 12:15:52 2017
// Last Modified By : Peter A. Buhr
// Last Modified On : Fri Oct 18 16:43:26 2024
// Update Count     : 200
//

#include <fstream.hfa>									// sin/sout
#include <stdlib.hfa>									// convert
#include <thread.hfa>
#include <math.hfa>										// sqrt
#include <string.h>										// strcmp

thread Quicksort {
	int * values;										// communication variables
	int low, high, depth;
};

void ?{}( Quicksort & qs, int values[], int size, int depth ) {
	qs.[values, low, high, depth] = [values, 0, size, depth];
} // Quicksort

void main( Quicksort & qs ) {							// thread starts here
	// nested routines: information hiding

	void ?{}( Quicksort & qs, int values[], int low, int high, int depth ) {
		qs.values = values;  qs.low = low;  qs.high = high;  qs.depth = depth;
	} // Quicksort

	void sort( int values[], int low, int high, int depth ) {
		int left, right;								// index to left/right-hand side of the values
		int pivot;										// pivot value of values
		int swap;										// temporary

		//verify();										// check for stack overflow due to recursion

		// partition while 2 or more elements in the array
		if ( low < high ) {
			pivot = values[low + ( high - low ) / 2];
			left  = low;
			right = high;

			// partition: move values less < pivot before the pivot and values > pivot after the pivot
			do {
				while ( values[left] < pivot ) left += 1; // changed values[left] < pivot
				while ( pivot < values[right] ) right -= 1;
				if ( left <= right ) {
					swap = values[left];				// interchange values
					values[left]  = values[right];
					values[right] = swap;
					left += 1;
					right -= 1;
				} // if
			} while ( left <= right );

			// restrict number of tasks to slightly greater than number of processors
			if ( depth > 0 ) {
				depth -= 1;
				Quicksort lqs = { values, low, right, depth }; // concurrently sort lower half
				Quicksort rqs = { values, left, high, depth }; // concurrently sort upper half
				// Quicksort lqs = { values, low, right, depth }; // concurrently sort lower half
				// sort( values, left, high, depth );		// concurrently sort upper half
			} else {
				sort( values, low, right, 0 );			// sequentially sort lower half
				sort( values, left, high, 0 );			// sequentially sort upper half
			} // if
		} // if
	} // sort

	with( qs ) {
		sort( values, low, high, depth );
	} // with
} // main

// convert(...) throws out_of_range or invalid_argument
ExceptionDecl( cmd_error );

int main( int argc, char * argv[] ) {
	ifstream unsortedfile = sin;						// default values
	ofstream sortedfile = sout;
	// Must be signed because of the conversion routine.
	intmax_t depth = 0;
	intmax_t size = -1;									// -1 means time mode not activated

	try {
		if ( 1 < argc && strcmp( argv[1], "-t" ) == 0 ) { // time mode ?
			choose ( argc ) {
			  case 4:
				depth = convert( argv[3] );				// invalid integer ?
				if ( depth < 0 ) throw ExceptionInst( cmd_error );
				fallthrough;
			  case 3:
				size = convert( argv[2] );				// invalid integer ?
				if ( size < 0 ) throw ExceptionInst( cmd_error );
			  default:									// wrong number of options
				throw ExceptionInst( cmd_error );
			} // choose
		} else {										// sort file
			choose ( argc ) {
			  case 4:
				depth = convert( argv[3] );				// invalid integer ?
				if ( depth < 0 ) throw ExceptionInst( cmd_error );
				fallthrough;
			  case 3: case 2:
				// open input file first as output creates file
				if ( strcmp( argv[1], "d" ) != 0 ) {
					open( unsortedfile, argv[1] );
				} // if
				if ( argc > 2 && strcmp( argv[2], "d" ) != 0 ) {
					open( sortedfile, argv[2] );
				} // if
				fallthrough;
			  case 1: ;									// defaults
			  default:									// wrong number of options
				throw ExceptionInst( cmd_error );
			} // choose
		} // if
	} catch( open_failure * ) {			// open failed ?
		exit | "Error! Could not open unsorted input file \"" | argv[1] | "\"";
	} catch( open_failure * ) {			// open failed ?
		exit | "Error! Could not open sorted output file \"" | argv[2] | "\"";
	} catch( exception_t * ) {							// catch any
		exit | "Usage: " | argv[0] |					// TERMINATE
			" ( [ unsorted-file | 'd' [ sorted-file | 'd' [ depth (>= 0) ] ] ]"
			" | -t size (>= 0) [ depth (>= 0) ] )";
	} // try

	enum { ValuesPerLine = 22 };						// number of values printed per line

	sortedfile | nlOff;									// turn off auto newline

	if ( size == -1 ) {									// generate output ?
		int * values = 0p;
		try {
			for () {
				unsortedfile | size;					// read number of elements in the list
				values = aalloc( size );				// values to be sorted, too large to put on stack
				for ( counter; size ) {					// read unsorted numbers
					unsortedfile | values[counter];
					if ( counter != 0 && counter % ValuesPerLine == 0 ) sortedfile | nl | "  ";
					sortedfile | values[counter];
					if ( counter < size - 1 && (counter + 1) % ValuesPerLine != 0 ) sortedfile | ' ';
				} // for
				sortedfile | nl;

				if ( size > 0 ) {						// values to sort ?
					Quicksort QS = { values, size - 1, 0 }; // sort values
				} // wait until sort tasks terminate
				for ( counter; size ) {					// print sorted list
					if ( counter != 0 && counter % ValuesPerLine == 0 ) sortedfile | nl | "  ";
					sortedfile | values[counter];
					if ( counter < size - 1 && (counter + 1) % ValuesPerLine != 0 ) sortedfile | ' ';
				} // for
				sortedfile | nl | nl;

				delete( values );
				values = 0p;
			} // for
		} catch( end_of_file * ) {
			delete( values );
		} // try
	} else {											// timing
		PRNG prng;										
		processor processors[ (1 << depth) - 1 ] __attribute__(( unused )); // create 2^depth-1 kernel threads
		int * values = aalloc( size );					// values to be sorted, too large to put on stack

		for ( counter; size ) {							// generate unsorted numbers
			values[counter] = size - counter;			// descending values
		} // for

		unsigned int times = sqrt( size );
		for ( unsigned int counter = 0; counter < times; counter += 1 ) {
			swap( values[0], values[prng(size)] );		// randomize unsorted numbers
		} // for
		{
			Quicksort QS = { values, size - 1, depth }; // sort values
		} // wait until sort tasks terminate

		// for ( counter; size - 1 ) {				// check sorting
		// 	if ( values[counter] > values[counter + 1] ) abort();
		// } // for

		delete( values );
	} // if
} // main

// for depth in 0 1 2 3 4 5 ; do echo "sort 500000000 values with ${depth} depth" ; time -f "%Uu %Ss %E %Mkb" a.out -t 500000000 ${depth} ; done

// Local Variables: //
// tab-width: 4 //
// compile-command: "cfa quickSort.cfa" //
// End: //