1 // Copyright (C) 2012-2013 Vicente Botet
2 //
3 // Distributed under the Boost Software License, Version 1.0. (See accompanying
4 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
5
6 #include <boost/config.hpp>
7
8 #define BOOST_THREAD_VERSION 4
9 #define BOOST_THREAD_PROVIDES_EXECUTORS
10 #define BOOST_THREAD_USES_LOG_THREAD_ID
11 #define BOOST_THREAD_QUEUE_DEPRECATE_OLD
12 #if ! defined BOOST_NO_CXX11_DECLTYPE
13 #define BOOST_RESULT_OF_USE_DECLTYPE
14 #endif
15
16 #include <boost/thread/executors/basic_thread_pool.hpp>
17 #include <boost/thread/future.hpp>
18 #if defined(BOOST_THREAD_PROVIDES_VARIADIC_THREAD)
19
20 #include <numeric>
21 #include <algorithm>
22 #include <functional>
23 #include <iostream>
24 #include <list>
25
26 template<typename T>
27 struct sorter
28 {
29 boost::basic_thread_pool pool;
30 typedef std::list<T> return_type;
31
do_sortsorter32 std::list<T> do_sort(std::list<T> chunk_data)
33 {
34 if(chunk_data.empty())
35 {
36 return chunk_data;
37 }
38
39 std::list<T> result;
40 result.splice(result.begin(),chunk_data, chunk_data.begin());
41 T const& partition_val=*result.begin();
42
43 typename std::list<T>::iterator divide_point=
44 std::partition(chunk_data.begin(), chunk_data.end(), [&](T const& val){return val<partition_val;});
45
46 std::list<T> new_lower_chunk;
47 new_lower_chunk.splice(new_lower_chunk.end(), chunk_data, chunk_data.begin(), divide_point);
48
49 boost::future<std::list<T> > new_lower = boost::async(pool, &sorter::do_sort, this, std::move(new_lower_chunk));
50 //boost::future<std::list<T> > new_lower = boost::async<return_type>(pool, &sorter::do_sort, this, std::move(new_lower_chunk));
51
52 std::list<T> new_higher(do_sort(chunk_data));
53
54 result.splice(result.end(),new_higher);
55 while(!new_lower.is_ready())
56 {
57 pool.schedule_one_or_yield();
58 }
59
60 result.splice(result.begin(),new_lower.get());
61 return result;
62 }
63 };
64
65
66 template<typename T>
parallel_quick_sort(std::list<T> & input)67 std::list<T> parallel_quick_sort(std::list<T>& input)
68 {
69 if(input.empty())
70 {
71 return input;
72 }
73 sorter<T> s;
74
75 return s.do_sort(input);
76 }
77
78
main()79 int main()
80 {
81 try
82 {
83 const int s = 101;
84 std::list<int> lst;
85 for (int i=0; i<s;++i)
86 lst.push_back(100-i);
87 std::list<int> r = parallel_quick_sort(lst);
88 for (std::list<int>::const_iterator it=r.begin(); it != r.end(); ++it)
89 std::cout << *it << std::endl;
90
91 }
92 catch (std::exception& ex)
93 {
94 std::cout << "ERROR= " << ex.what() << "" << std::endl;
95 return 1;
96 }
97 catch (...)
98 {
99 std::cout << " ERROR= exception thrown" << std::endl;
100 return 2;
101 }
102 return 0;
103 }
104 #else
105 //#warning "This compiler doesn't supports variadics and move semantics"
main()106 int main()
107 {
108 return 0;
109 }
110 #endif
111