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 | |
32 | 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> |
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 | |
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(x: 100-i); |
87 | std::list<int> r = parallel_quick_sort(input&: 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" |
106 | int main() |
107 | { |
108 | return 0; |
109 | } |
110 | #endif |
111 | |