#include "QuickSort.h"
#include <stdio.h>
#include <string.h>

SchedDefineTask(QuickSort);

static void quick_sort( Data *data, int begin, int end ) ;

static void
swap( Data *data, int left, int right )
{
    Data tmp	      = data[left];
    data[left]  = data[right];
    data[right] = tmp;
}

// #define USE_MEMCPY

static int
run(SchedTask *s, void* rbuff, void* wbuff) {
    // copy value
    int begin	= 0;
#if USE_SIMPLE_TASK
    int end = s->read_size()/sizeof(Data);
    Data *r_data = (Data*)rbuff;
#ifdef USE_MEMCPY
    Data *w_data = (Data*)wbuff;
#endif
#else
    int end   = (long)s->get_param(0);
    DataPtr r_data = (DataPtr)s->get_input(0);
#ifdef USE_MEMCPY
    DataPtr w_data = (DataPtr)s->get_output(0);
#endif
#endif

    //printf("[SPE] Quick: length:%d addr->%x \n",end, (int)rbuff);
    //printf("[PPE] Quick: data[0]: %d addr->%x\n",sizeof(r_data),r_data); 

    //show_data(r_data, end);
    quick_sort(r_data, begin, end-1);
#ifdef USE_MEMCPY
    memcpy(w_data, r_data, sizeof(Data)*end);
#else
    s->swap();
#endif

    return 0;
}

static void 
quick_sort( Data *data, int begin, int end ) {

    if (begin < end) {
	int where = (begin + end) / 2;
	int pivot = data[where].index;
	data[where].index = data[begin].index;
	int p = begin;
	int i;
	for (i=begin+1; i<=end; i++) {
	    if (data[i].index < pivot) { 
		p++; 
		swap(data, p, i); 
	    }
	}
	data[begin].index = data[p].index;
	data[p].index = pivot;
	
	quick_sort(data, begin, p-1);
	quick_sort(data, p+1, end); // tail call
    }
}


/* end */