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