#pragma once

#include <algorithm>

#include <boost/bind.hpp>

#include <boost/lambda/lambda.hpp>
#include <boost/lambda/bind.hpp>

#include <boost/tp/default_pool.hpp>
#include <boost/tp/pool.hpp>
#include <boost/tp/unbounded_channel.hpp>
#include <boost/tp/fifo.hpp>

#include "../boost/find_pivot.hpp"

// we start with something simple

template <typename RandomIterator, typename Value>
void parallel_fill(RandomIterator first, RandomIterator last, Value v)
{
	typedef typename RandomIterator::difference_type difference_type;

	difference_type n = std::distance(first, last);

	boost::tp::default_pool & p = boost::tp::get_default_pool();

	RandomIterator l = first;
	
	const difference_type block_size = 1000;

	for(RandomIterator i = l; i != last; l = i)
	{
		std::advance(i, std::min BOOST_PREVENT_MACRO_SUBSTITUTION(std::distance(i, last), block_size));

		BOOST_ASSERT(l < i);
		BOOST_ASSERT(l != last);
		BOOST_ASSERT(i != first);

		p.submit(boost::bind(&std::fill<RandomIterator, Value>, l, i, v));
	}

	p.shutdown();

}

template <typename RandomIterator>
RandomIterator pivot_partition(RandomIterator first, RandomIterator last)
{
	typedef RandomIterator iterator_type;
	typedef typename iterator_type::difference_type difference_type;
	typedef typename iterator_type::value_type value_type;

	iterator_type pivot = first + std::distance(first, last) / 2;

	// we partition
	value_type pivot_value = *pivot;

	// we "save" the pivot in putting it to the first place
	std::iter_swap(first, pivot);

	// we skip the pivot otherwise the partitioning won't work as expected
	iterator_type par_start = first + 1;

	std::less<value_type> pred;

	pivot = std::partition(par_start, last, std::bind2nd(pred, pivot_value));

	// we restore the pivot
	std::iter_swap(--pivot, first);

	return pivot;
}

template <typename RandomIterator, typename Pool, typename Tasks>
void rec_pivot_partition(RandomIterator first, RandomIterator last, Pool & p, Tasks & t)
{
	if (std::distance(first, last) > 1000)
	{
		RandomIterator pivot = pivot_partition(first, last);
		rec_pivot_partition(first, pivot, p, t);
		rec_pivot_partition(pivot, last, p, t);
	}
	else
	{
		t.push_back(p.submit(boost::bind(&std::sort<iterator_type>, first, last)).result());
	}
	
};

template <typename RandomIterator>
void parallel_tp(RandomIterator first, RandomIterator last)
{

	typedef RandomIterator iterator_type;
	typedef typename iterator_type::difference_type difference_type;
	typedef typename iterator_type::value_type value_type;

	difference_type n = std::distance(first, last);

	RandomIterator l = first;
	
	const difference_type block_size = 1000;

	typedef boost::shared_future<void> task_type;

	std::list<task_type> tasks;

	// we partition until we have "atoms", ie block of size < block_size
	boost::tp::default_pool & p = boost::tp::get_default_pool();

	rec_pivot_partition(first, last, p, tasks);

	boost::wait_for_all(tasks.begin(), tasks.end());

}