#include "tbb/task_scheduler_init.h"
#include "tbb/parallel_for.h"
#include "tbb/tick_count.h"
#include <iostream>
#include <algorithm>

using namespace std;
using namespace tbb;

#define N 500000

template<class T> class sort_task : public task {
	T *poczatek, *koniec;
	size_t min_rozmiar;
public:
	sort_task(T *poczatek_, T *koniec_, size_t rozmiar = 20) :
	  poczatek(poczatek_), koniec(koniec_), min_rozmiar(rozmiar)
	{}
	task* execute() {
		size_t rozmiar = koniec - poczatek;
		if ( rozmiar < min_rozmiar) {
			sort(poczatek, koniec);
			return NULL;
		} else {
			T m, *i, *j, *k;
			i = poczatek + rand() % rozmiar;
			j = poczatek + rand() % rozmiar;
			k = poczatek + rand() % rozmiar;
			m = (*i > *j) ? *i : *j;
			m = (m > *k) ? *k : m;
			i = poczatek;
			j = koniec - 1;
			do {
				while (*i < m) ++i;
				while (*j > m) --j;
				if (i <= j) {
					swap(*i, *j);
					++i;
					--j;
				}
			} while (i <= j);

			int cnt = 0;
			sort_task<T> *z1 = NULL;
			sort_task<T> *z2 = NULL;
			if (poczatek < i) {
				z1 = new (allocate_child()) sort_task(poczatek, i, min_rozmiar);
				cnt++;
			}
			if (koniec > i) {
				z2 = new (allocate_child()) sort_task(i, koniec, min_rozmiar);
				cnt++;
			}
			set_ref_count(cnt + 1);
			if (cnt == 1) spawn_and_wait_for_all((z1) ? *z1 : *z2);
			else {
				if (z1) spawn(*z1);
				if (z2) spawn_and_wait_for_all(*z2);
			}
			return NULL;
		}
	}
};

int main(int argc, char* argv[])
{
	double *tablica = new double[N];
	task_scheduler_init init;
	tick_count t0, t1;
	
	for (int i = 0; i < N; ++i)
		tablica[i] = (double)rand() / (double)RAND_MAX;
			
	t0 = tick_count::now();
	sort_task<double> &st = 
		*new (task::allocate_root()) sort_task<double>(tablica, tablica + N);
	task::spawn_root_and_wait(st);
	t1 = tick_count::now();
	
	cout << "Czas:  " << (t1 - t0).seconds() << " s" << endl;

	delete[] tablica;
	cin.get();
	return 0;
}
