#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 = s->get_inputSize(0)/sizeof(Data);
    DataPtr r_data = (DataPtr)s->get_input(0);
#ifdef USE_MEMCPY
    DataPtr w_data = (DataPtr)s->get_output(0);
#endif
#endif

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

    quick_sort(r_data, begin, end-1);

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

    return 0;
}

void
qsort_test(Data *data, int begin, int end ) {
    quick_sort(data, begin, end);
    printf("end is %d\n",end);
}

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 */