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

SchedDefineTask(QuickSort);

static void
check_data(DataPtr data, int length)
{
    for (int i = 0; i < length-1; i++) {
	if (data[i].index > data[i+1].index) {
	    printf("error!!\n");
	} else {
	    printf("%d < %d\n", data[i].index, data[i+1].index);
	}
    }
}

int
QuickSort::run(void* rbuff, void* wbuff) {
    int begin = 0;
    int end   = smanager->get_param(0);
    DataPtr r_data = (DataPtr)smanager->get_input(0);
    DataPtr w_data = (DataPtr)smanager->get_output(0);

    int real_start = smanager->get_param(1);
    
    quick_sort(r_data, begin, end-1);
    //check_data(r_data, end);
    //bubble_sort(r_data, begin, end-1);
    memcpy(w_data, r_data, sizeof(Data)*end);

    return 0;
}

void
QuickSort::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);
	    }
	}
    }
}

void
QuickSort::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);
    }
}

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