//////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Vicente J. Botet Escriba 2008-2009. 
// Distributed under the Boost Software License, Version 1.0. 
// (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
//
// See http://www.boost.org/libs/interthreads for documentation.
//
// Based on the shared.cpp example from the threadalert library of Roland Schwarz 
//////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <algorithm>

#include <boost/progress.hpp>
#include <boost/bind.hpp>
#include <boost/tp/pool.hpp>
#include <boost/tp/unbounded_channel.hpp>
#include <boost/tp/fifo.hpp>
#include <boost/range/algorithm/sort.hpp>
#include <boost/range/algorithm/inplace_merge.hpp>
#include <boost/range/sub_range.hpp>
#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>

#define FIBO
//#define X_SORT
//#define COUT

#ifdef COUT
boost::mutex cout_sync;
#endif
typedef boost::tp::pool<
  boost::tp::unbounded_channel< boost::tp::fifo >
> pool_type;

#ifdef FIBO

class fibo
{
private:
  pool_type &  pool_;
  int          cutoff_;

  template <typename T>
  int seq_( T n)
  {
#ifdef COUT
    {
    boost::mutex::scoped_lock lk(cout_sync);
    std::cout << "<< seq_("<<n<<")" << std::endl;
    }
#endif
      
    if ( n <= 1) return n;
    else return seq_( n - 2) + seq_( n - 1);
  }

  template <typename T>
  int par_( T n)
  {
#ifdef COUT
    {
    boost::mutex::scoped_lock lk(cout_sync);
    std::cout << "<< par_("<<n<<")" << std::endl;
    }
#endif

    if ( n <= cutoff_) return seq_( n);
    else
    {
        // fork a new sub-action t1 in pool
        boost::tp::task< pool_type,  T > t1(
            pool_.submit(
                boost::bind(
                    & fibo::par_<T>,
                    boost::ref( * this),
                    n - 1) ) );

        // fork a new sub-action t2 in pool
        boost::tp::task< pool_type, T > t2(
            pool_.submit(
                boost::bind(
                    & fibo::par_<T>,
                    boost::ref( * this),
                    n - 2) ) );

        // joining the result of sub-action t1 and t2
        return t1.get() + t2.get();
    }
  }
public:
  fibo( pool_type & pool, int cutoff)
  : pool_( pool), cutoff_( cutoff)
  {}

  int execute( int n)
  {
    int result( par_( n) );
    return result;
  }
};

#endif
#ifdef X_SORT

struct sort_fct {
    template<class RandomAccessRange>
    RandomAccessRange& operator()(RandomAccessRange& rng) {
        return boost::sort(rng);
    }
};

struct inplace_merge_fct {
    template<class BidirectionalRange>
    BidirectionalRange&
    operator()( BidirectionalRange& rng,
                   typename boost::range_iterator<BidirectionalRange>::type middle ) {
        return boost::inplace_merge(rng, middle);
    }
};

class x_sort
{
private:
  pool_type &  pool_;
  int          cutoff_;

  template <typename Range>
  void seq_( Range& range)
  {
#ifdef COUT
    std::cout << "<< seq_("<<boost::size(range)<<")" << std::endl;
#endif      
    sort_fct()(range);
#ifdef COUT
    std::cout << "seq_("<<boost::size(range)<<") >>" << std::endl;
#endif      
  }

  template <typename Range>
  void par_( Range& range)
  {
#ifdef COUT
    std::cout << "<< par_("<<boost::size(range)<<")" << std::endl;
#endif      
    unsigned size = boost::size(range);
    if ( size <= cutoff_) return seq_( range);
    else
    {
        boost::sub_range<Range> left(boost::begin(range), boost::begin(range)+(size/2));
        // fork a new sub-action t1 in pool
        boost::tp::task< pool_type,  void > task(
            pool_.submit(
                boost::bind(
                    & x_sort::par_<Range>,
                    boost::ref( * this),
                    //left) ) );
                    boost::ref(left)) ) );

        boost::sub_range<Range> right(boost::begin(range)+(size/2)+1, boost::end(range));
        this->par_(right);
        task.wait();
        inplace_merge_fct()(range, boost::begin(range)+(size/2));
#ifdef COUT
        std::cout << "par_("<<boost::size(range)<<") >>" << std::endl;
#endif      
    }
  }
public:
  x_sort( pool_type & pool, int cutoff)
  : pool_( pool), cutoff_( cutoff)
  {}

  template <typename Range>
  void execute( Range& n)
  {
    par_( n);
  }
};

template <typename Range>
void parallel_sort(Range& range) {
    pool_type pool( boost::tp::poolsize( 2) );

    x_sort fct( pool, 100000);
    fct.execute(range);
}
#endif
#define NN 100000
   
    
int main() {
    //pool_type ae(boost::tp::poolsize(2));
    int values[NN];
    
    for (unsigned i=NN-1; i>0; --i) values[i]=NN-i;
    std::cout << "std::sort: reverse 0.." << NN << std::endl;
    {
    boost::progress_timer t;  // start timing
    std::sort(values, values+NN);
    }
#ifdef X_SORT
    for (unsigned i=NN-1; i>0; --i) values[i]=NN-i;
    std::cout << "sort_fct: reverse 0.."<<NN << std::endl;
    {
    boost::progress_timer t;  // start timing
    sort_fct()(values);
    }
#endif

// creates a threadpool with two worker-threads
pool_type pool( boost::tp::poolsize( 2) );

#ifdef X_SORT
    for (unsigned i=NN-1; i>0; --i) values[i]=NN-i;
    std::cout << "parallel_sort:  reverse 0.."<<NN << std::endl;
    {
    boost::progress_timer tmr;  // start timing
    x_sort xs( pool, 100000);
// submit an action
boost::tp::task< pool_type, void > t(
  pool.submit(
    boost::bind(
      & x_sort::execute<int [NN]>,
      boost::ref( xs),
      boost::ref(values)) ) );
t.wait() ;
std::cout << "end"<< std::endl; // prints 55
        
    //parallel_sort(values);
    }
#endif    

#ifdef FIBO

fibo fib( pool, 1);

// submit an action
// which calculates the fibonacci number of 10
boost::tp::task< pool_type, int > t(
  pool.submit(
    boost::bind(
      & fibo::execute,
      boost::ref( fib),
      10) ) );

std::cout << t.get() << std::endl; // prints 55
#endif    
    pool.shutdown();
    return 0;
}