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

SchedDefineTask(QuickSort);

static void bubble_sort(DataPtr data, int begin, int end);
static void quick_sort(DataPtr data, int begin, int end);

static void swap(Data *data, int left, int right);

static int
run(SchedTask *smanager, void* rbuff, void* wbuff) {
    int begin = 0;
    int end   = (long)smanager->get_param(0);
    DataPtr r_data = (DataPtr)smanager->get_input(0);
    DataPtr w_data = (DataPtr)smanager->get_output(0);
    //SpeProfile *prof = new SpeProfile;

    //prof->ProfStart();
    if (0) 
	bubble_sort(r_data, begin, end-1);
    else 
	quick_sort(r_data, begin, end-1);
    memcpy(w_data, r_data, sizeof(Data)*end);
    //prof->ProfStop();
    //prof->ProfPrint();

    //delete prof;
    return 0;
}

static void
bubble_sort(DataPtr data, int begin, int end)
{
    for (int i = 0; i < end; i++) {
	for (int j = end; j > i; j--) {
	    if (data[j].index < data[j-1].index) {
		swap(data, j, j-1);
	    }
	}
    }
}


static void
quick_sort(DataPtr 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;

	for (int 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;
}

/* end */