//
// 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 Jun 21 08:28:20 2019
// Update Count     : 149
//

#include <fstream.hfa>
#include <stdlib.hfa>
#include <kernel.hfa>
#include <thread.hfa>
#include <string.h>										// strcmp

forall( T | { int ?<?( T, T ); } ) {
	thread Quicksort {
		T * values;										// communication variables
		int low, high, depth;
	};

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

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

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

		void sort( T values[], int low, int high, int depth ) {
			int left, right;							// index to left/right-hand side of the values
			T pivot;									// pivot value of values
			T 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(T) rqs = { values, low, right, depth }; // concurrently sort upper half
					//Quicksort lqs( values, left, high, depth ); // concurrently sort lower half
					sort( values, left, high, depth );	// concurrently sort lower 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
}

bool convert( int & val, const char * nptr ) {			// convert C string to integer
	char * eptr;
	int temp = strto( nptr, &eptr, 10 );				// do not change val on false
	// true => entire string valid with no extra characters
	return *nptr != '\0' && *eptr == '\0' ? val = temp, true : false;
} // convert

void usage( char * argv[] ) {
	sout | "Usage:" | argv[0] | "( -s unsorted-file [ sorted-file ] | -t size (>= 0) [ depth (>= 0) ] )";
	exit( EXIT_FAILURE );								// TERMINATE!
} // usage


#define ELEMTYPE int

int main( int argc, char * argv[] ) {
	ifstream & unsortedfile = sin;
	ofstream & sortedfile = sout;						// default value
	int depth = 0, size;

	if ( argc != 1 ) {									// do not use defaults
		if ( argc < 2 || argc > 4 ) usage( argv );		// wrong number of options
		if ( strcmp( argv[1], "-t" ) == 0 ) {			// timing ?
			&unsortedfile = (ifstream *)0;				// no input
			choose ( argc ) {
			  case 4:
				if ( ! convert( depth, argv[3] ) || depth < 0 ) usage( argv );
				fallthrough;
			  case 3:
				if ( ! convert( size, argv[2] ) || size < 0 ) usage( argv );
			} // choose
		} else {										// sort file
			choose ( argc ) {
			  case 3:
				&sortedfile = new( (const char *)argv[2] ); // open the output file
				if ( fail( sortedfile ) ) {
					serr | "Error! Could not open sorted output file \"" | argv[2] | "\"";
					usage( argv );
				} // if
				fallthrough;
			  case 2:
				&unsortedfile = new( (const char *)argv[1] ); // open the input file
				if ( fail( unsortedfile ) ) {
					serr | "Error! Could not open unsorted input file \"" | argv[1] | "\"";
					usage( argv );
				} // if
			} // choose
		} // if
	} // if
	sortedfile | nlOff;									// turn off auto newline

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

	if ( &unsortedfile ) {								// generate output ?
		for () {
			unsortedfile | size;						// read number of elements in the list
		  if ( eof( unsortedfile ) ) break;
			ELEMTYPE * values = alloc( 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(ELEMTYPE) 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 );
		} // for
		if ( &unsortedfile != &sin ) delete( &unsortedfile ); // close input/output files
		if ( &sortedfile != &sout ) delete( &sortedfile );
	} else {
		processor processors[ (1 << depth) - 1 ] __attribute__(( unused )); // create 2^depth-1 kernel threads

		ELEMTYPE * values = alloc( size );				// values to be sorted, too large to put on stack
		for ( counter; size ) {							// generate unsorted numbers
			values[counter] = size - counter;			// descending values
		} // for
		{
			Quicksort(ELEMTYPE) 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

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