#include "TaskManager.h"
#include "SchedTask.h"
#include "sort.h"
#include "Func.h"
#include <string.h>

static void sort_start(SchedTask *);
extern void check_data();

static DataPtr data;
static  int data_length;
static  int cpuNum;

/**
 * 一つの block にある data の数が MAX_BLOCK_SIZE 超えないような
 * len の分割数を返す
 *
 * @param  len  sort する data の総数
 * @param  num  使用する SPE の数
 *
 * @return data の分割数
 *
 * TODO:
 *   len が num 以下とか考えてません
 */
static int
get_split_num(int len, int num)
{
    if (len / num < MAX_BLOCK_SIZE) {
	return num;
    } else {
	// 切り上げ
	return (len + MAX_BLOCK_SIZE - 1) / MAX_BLOCK_SIZE;
    }
}	


HTaskPtr *fsort;
HTaskPtr *bsort;

#define ALL_TASK

#ifdef ALL_TASK

static void
sort_start(SchedTask *manager)
{
    int split_num = get_split_num(data_length, cpuNum); // data の分割数
    int half_num = split_num-1;
    static int sort_count = split_num; // sort 完了に必要な回数

    // 一つのタスクで sort する data 数
    int block_num = (data_length + split_num -1)/split_num;
    int half_block_num = block_num/2;

    int last_block_num = data_length - (split_num-1)*block_num;
    int last_half_block_num = half_block_num+(last_block_num/2);

    while (--sort_count > 0)  {

	for (int i = 0; i < split_num-1; i++) {
	    fsort[i] = manager->create_task(QUICK_SORT,
		(memaddr)&data[i*block_num], sizeof(Data)*block_num,
		(memaddr)&data[i*block_num], sizeof(Data)*block_num);
	    if (i>0 && bsort[i-1]) {
		fsort[i]->wait_for(bsort[i-1]);
	    }
	    if (i<split_num-2 && bsort[i]) {
		fsort[i]->wait_for(bsort[i]);
	    }
	    fsort[i]->set_cpu(SPE_ANY);
	}

	// 最後の block は端数なので last_block_num を使う
	{
	    int i = split_num-1;

	    fsort[i] = manager->create_task(QUICK_SORT,
		(memaddr)&data[i*block_num], sizeof(Data)*last_block_num,
		(memaddr)&data[i*block_num], sizeof(Data)*last_block_num);
	    if (i>0 && bsort[i-1]) {
		fsort[i]->wait_for(bsort[i-1]);
	    }
	    fsort[i]->set_cpu(SPE_ANY);
       }

	if (split_num > 1) {

	    for (int i = 0; i < half_num-1; i++) {
		bsort[i] = manager->create_task(QUICK_SORT,
		    (memaddr)&data[i*block_num+half_block_num], sizeof(Data)*block_num,
		    (memaddr)&data[i*block_num+half_block_num], sizeof(Data)*block_num);
		bsort[i]->set_cpu(SPE_ANY);
	    }

	    {
		int i = half_num-1;

		bsort[i] = manager->create_task(QUICK_SORT,
		    (memaddr)&data[i*block_num+half_block_num], sizeof(Data)*last_half_block_num,
		    (memaddr)&data[i*block_num+half_block_num], sizeof(Data)*last_half_block_num);
		bsort[i]->set_cpu(SPE_ANY);	
	    }
	    
	    for (int i = 0; i < half_num; i++) {
		bsort[i]->wait_for(fsort[i]);
		bsort[i]->wait_for(fsort[i+1]);
		bsort[i]->spawn();
	    }
	}

	for (int i = 0; i < split_num; i++) {
	    fsort[i]->spawn();
	}
    }
}

#else

/**
 * btask が全て終了したら、再び sort_start を実行する
 * @param d 生成された btask の数
 */
static void
sort_restart(SchedTask *s, void *d, void *e)
{
    static int cnt = 0;
    static int ccc = 0;
    long max = (long)d;

    if (++cnt == max) {	
        printf("restarted %d %% %ld\n",ccc++,max);
	cnt = 0;
	sort_start(s);
    }
}
#ifdef USE_SIMPLE_TASK

static void
sort_start(SchedTask *manager)
{
    int split_num = get_split_num(data_length, cpuNum); // data の分割数
    int half_num = split_num-1;
    static int sort_count = split_num; // sort 完了に必要な回数

    // 一つのタスクで sort する data 数
    int block_num = (data_length + split_num -1)/split_num;
    int half_block_num = block_num/2;

    int last_block_num = data_length - (split_num-1)*block_num;
    int last_half_block_num = half_block_num+(last_block_num/2);

    if (--sort_count < 0) {
	check_data();
	return;
    }


    for (int i = 0; i < split_num-1; i++) {
	fsort[i] = manager->create_task(QUICK_SORT,
	    (memaddr)&data[i*block_num], sizeof(Data)*block_num,
	    (memaddr)&data[i*block_num], sizeof(Data)*block_num);
	if (i>0 && bsort[i-1]) {
	    fsort[i]->wait_for(bsort[i-1]);
	}
	if (i<split_num-2 && bsort[i]) {
	    fsort[i]->wait_for(bsort[i]);
	}
	fsort[i]->set_cpu(SPE_ANY);
    }

    // 最後の block は端数なので last_block_num を使う
    {
	int i = split_num-1;

	fsort[i] = manager->create_task(QUICK_SORT,
	    (memaddr)&data[i*block_num], sizeof(Data)*last_block_num,
	    (memaddr)&data[i*block_num], sizeof(Data)*last_block_num);
	if (i>0 && bsort[i-1]) {
	    fsort[i]->wait_for(bsort[i-1]);
	}
	fsort[i]->set_cpu(SPE_ANY);
   }

    if (split_num > 1) {

	for (int i = 0; i < half_num-1; i++) {
	    bsort[i] = manager->create_task(QUICK_SORT,
		(memaddr)&data[i*block_num+half_block_num], sizeof(Data)*block_num,
		(memaddr)&data[i*block_num+half_block_num], sizeof(Data)*block_num);
	    bsort[i]->set_cpu(SPE_ANY);
	}

	{
	    int i = half_num-1;

	    bsort[i] = manager->create_task(QUICK_SORT,
		(memaddr)&data[i*block_num+half_block_num], sizeof(Data)*last_half_block_num,
		(memaddr)&data[i*block_num+half_block_num], sizeof(Data)*last_half_block_num);
	    bsort[i]->set_cpu(SPE_ANY);	
	}
	
	for (int i = 0; i < half_num; i++) {
	    bsort[i]->wait_for(fsort[i]);
	    bsort[i]->wait_for(fsort[i+1]);
	    bsort[i]->spawn();
	}
    }

    for (int i = 0; i < split_num; i++) {
	fsort[i]->set_post(sort_restart, (void*)(half_num),(void*)manager);
	fsort[i]->spawn();
    }
}

#else

static void
sort_start(SchedTask *manager)
{
    int split_num = get_split_num(data_length, cpuNum); // data の分割数
    int half_num = split_num-1;
    static int sort_count = split_num; // sort 完了に必要な回数

    // 一つのタスクで sort する data 数
    int block_num = (data_length + split_num -1)/split_num;
    int half_block_num = block_num/2;

    int last_block_num = data_length - (split_num-1)*block_num;
    int last_half_block_num = half_block_num+(last_block_num/2);


    if (--sort_count < 0) {
	check_data();
	return;
    }


    for (int i = 0; i < split_num-1; i++) {
	fsort[i] = manager->create_task(QUICK_SORT);
	fsort[i]->add_inData(&data[i*block_num], sizeof(Data)*block_num);
	fsort[i]->add_outData(&data[i*block_num], sizeof(Data)*block_num);
	fsort[i]->set_param(0,(memaddr)block_num);
	if (i>0 && bsort[i-1]) {
	    fsort[i]->wait_for(bsort[i-1]);
	}
	if (i<split_num-2 && bsort[i]) {
	    fsort[i]->wait_for(bsort[i]);
	}
	fsort[i]->set_cpu(SPE_ANY);
    }

    // 最後の block は端数なので last_block_num を使う
    {
	int i = split_num-1;

	fsort[i] = manager->create_task(QUICK_SORT);
	fsort[i]->add_inData(&data[i*block_num], sizeof(Data)*last_block_num);
	fsort[i]->add_outData(&data[i*block_num], sizeof(Data)*last_block_num);
	fsort[i]->set_param(0,(memaddr)last_block_num);
	if (i>0 && bsort[i-1]) {
	    fsort[i]->wait_for(bsort[i-1]);
	}
	fsort[i]->set_cpu(SPE_ANY);
   }

    if (split_num > 1) {
	HTaskPtr bsort[half_num];

	for (int i = 0; i < half_num-1; i++) {
	    bsort[i] = manager->create_task(QUICK_SORT);
	    bsort[i]->add_inData(&data[i*block_num+half_block_num],
				 sizeof(Data)*block_num);
	    bsort[i]->add_outData(&data[i*block_num+half_block_num],
				  sizeof(Data)*block_num);
	    bsort[i]->set_param(0,(memaddr)block_num);
	    bsort[i]->set_cpu(SPE_ANY);
	}

	{
	    int i = half_num-1;

	    bsort[i] = manager->create_task(QUICK_SORT);
	    bsort[i]->add_inData(&data[i*block_num+half_block_num],
				 sizeof(Data)*last_half_block_num);
	    bsort[i]->add_outData(&data[i*block_num+half_block_num],
				  sizeof(Data)*last_half_block_num);
	    bsort[i]->set_param(0,(memaddr)last_half_block_num);
	    bsort[i]->set_cpu(SPE_ANY);	
	}
	
	for (int i = 0; i < half_num; i++) {
	    bsort[i]->wait_for(fsort[i]);
	    bsort[i]->wait_for(fsort[i+1]);
	    bsort[i]->spawn();
	}
    }

    for (int i = 0; i < split_num; i++) {
	fsort[i]->set_post(sort_restart, (void*)(half_num),(void*)manager);
	fsort[i]->spawn();
    }
}
#endif
#endif

void check_data()
{
    int flag = 1;
    for(int i=0; i< data_length-1;i++) {
	if (data[i].index>data[i+1].index)  {
	    printf("Data are not sorted at %d. %d > %d \n",i, data[i].index,data[i+1].index);
	    flag = 0;
	    break;
	}
    }
    if (flag) printf("Data are sorted\n");
}

void
sort_init(SchedTask *manager, void *a, void *b)
{
    cpuNum = (int)a;
    int length = (int)b;

    data = (DataPtr)manager->allocate(sizeof(Data)*length);
    data_length = length;

    int split_num = get_split_num(data_length, cpuNum); // data の分割数
    int half_num = split_num-1;
    fsort = (HTaskPtr*)manager->allocate(sizeof(HTaskPtr)*split_num);
    bsort = (HTaskPtr*)manager->allocate(sizeof(HTaskPtr)*half_num);
    memset((void*)bsort,0, sizeof(HTaskPtr)*half_num);

    for (int i = 0; i < length; i++) { 
        data[i].index = manager->get_random()%10000;
        data[i].ptr   = i;
    }

    sort_start(manager);
}

/* end */