#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 );

static int
run(SchedTask *s, void* rbuff, void* wbuff) {
    // copy value
    int begin	= 0;
    long end = (long)s->get_param(0);

    Data *r_data = (Data*)s->get_input(rbuff, 0);
    Data *w_data = (Data*)s->get_output(wbuff, 0);

    //printf("[PPE] 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);
    memcpy(w_data, r_data, sizeof(Data)*end);

    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);
    }
}

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