// qsort -- a parallel quicksort program
//   written using the Data-Parallel Programming Library for Education (DAPPLE)
//
// This parallel quicksort recurses through smaller and smaller subsets 
// of the list, as with any quicksort; we track the current subset by 
// using DAPPLE's dynamic active-set facility.  That is, only those processors
// in the current subset are active.  The recursive quicksort routine
// can tell the size of the list with an n_active reduction, pick a splitter, 
// and then compare all active elements against the splitter in parallel.
//    Each recursive call acts only on the elements that correspond to 
// active VPs, and assigns values to the permutation vector only for those
// VP.  On return from quicksortr, the permutation vector holds the 
// values of the eventual position in the sorted output list for each
// of the currently active VPs. 
//
// David Kotz 1994

// $Id: qsort.cc,v 2.15 95/02/26 18:34:34 dfk Exp $

#include <stdlib.h>
#include <iostream.h>
#include "dapple.h"

const int N = 11;

// which VP am I? useful for VP-specific math
const intVector VP(N, Identity);

const int data[N] = {16, 15, 19, 12, 14, 13, 15, 11, 17, 15, 18};

void quicksort(intVector& X);
intVector quicksortr(const intVector& X, const int left);

int
main(int argc, char **argv)
{
    intVector X(N, data);	// X the main data array, initialized here

    cout << "Initial:     " << X << endl;

    quicksort(X);

    cout << "Final:       " << X << endl;

    return(0);
}

// @SUBTITLE "quicksort - sort a vector"
// We call an auxiliary function quicksortr to determine the permutation 
// needed to sort X, and then we actually sort X by permuting it. 
// The permutation vector is simply a list of N values, one for each 
// data value in X, that are the *position* in the sorted list where that
// data element should go.
void
quicksort(intVector& X)		// X is input and output
{
    intVector P(N);		// a permutation vector

    P = quicksortr(X, 0);	// find the permutation needed to sort X

    cout << "Permutation: " << P << endl;

    X = permute(X, P);		// permute X according to P
}

// @SUBTITLE "quicksortr - the recursive part"
// X is not changed here.  We are responsible for filling in P;
// well, that part of P corresponding to the current active set.
//   X is the vector to sort.
//   "left" is the destination VP for the leftmost element of the sorted 
// set of integers represented by the current active set of VPs.
//   returns a permutation vector giving the final destination of 
// every element in the active set.

intVector				// a permutation vector
quicksortr(const intVector& X, const int left)
{
    int n = n_active(X);	// how big is this sublist?
    intVector P(N);		// the result

    // check the number of active processors (ie, size of our sublist)
    if (n <= 0)
      ;				// do nothing
    else if (n == 1)
      P = left;			// the one element goes right THERE
    else if (n == 2) {
	// too small to recurse, so just check to see if we need to swap
	ifp (VP == min_index(X))
	  P = left;		// left one get smallest
	else
	  P = left+1;		// next one gets largest
	
    } else {			// n >= 3
	int splitter;		// splitter value

	int splitVP;		// VP# that holds the splitter value
	int middle, right;	// starting position of subsets

	// pick a splitter; for simplicity I'll just use the first value
	splitter = first(X);
	splitVP = first_index(X); // which VP holds the splitter?
	
	// find the left half, those less than or equal to splitter
	// except for that first one...
	ifp (X <= splitter && VP != splitVP) {
	    // compute our destination in the result vector
	    P = quicksortr(X, left);
	    middle = left + n_active(X); // rest will begin here
	}
	
	// move the splitter into the middle
	ifp (VP == splitVP) {
	    P = middle;		// route it there
	    right = middle + 1;	// the rest will begin here
	}
	
	// do the right half, those greater than the splitter
	ifp (X > splitter) {
	    // compute our destination in the result vector 
	    P = quicksortr(X, right);
	}
    }
    
    return P;
}