]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | //---------------------------------------------------------------------------// |
2 | // Copyright (c) 2013 Kyle Lutz <kyle.r.lutz@gmail.com> | |
3 | // | |
4 | // Distributed under the Boost Software License, Version 1.0 | |
5 | // See accompanying file LICENSE_1_0.txt or copy at | |
6 | // http://www.boost.org/LICENSE_1_0.txt | |
7 | // | |
8 | // See http://boostorg.github.com/compute for more information. | |
9 | //---------------------------------------------------------------------------// | |
10 | ||
11 | #ifndef BOOST_COMPUTE_ALGORITHM_STABLE_SORT_HPP | |
12 | #define BOOST_COMPUTE_ALGORITHM_STABLE_SORT_HPP | |
13 | ||
14 | #include <iterator> | |
15 | ||
92f5a8d4 TL |
16 | #include <boost/static_assert.hpp> |
17 | ||
7c673cae FG |
18 | #include <boost/compute/system.hpp> |
19 | #include <boost/compute/command_queue.hpp> | |
20 | #include <boost/compute/algorithm/detail/merge_sort_on_cpu.hpp> | |
21 | #include <boost/compute/algorithm/detail/merge_sort_on_gpu.hpp> | |
22 | #include <boost/compute/algorithm/detail/radix_sort.hpp> | |
23 | #include <boost/compute/algorithm/detail/insertion_sort.hpp> | |
24 | #include <boost/compute/algorithm/reverse.hpp> | |
25 | #include <boost/compute/functional/operator.hpp> | |
26 | #include <boost/compute/detail/iterator_range_size.hpp> | |
92f5a8d4 | 27 | #include <boost/compute/type_traits/is_device_iterator.hpp> |
7c673cae FG |
28 | |
29 | namespace boost { | |
30 | namespace compute { | |
31 | namespace detail { | |
32 | ||
33 | template<class Iterator, class Compare> | |
34 | inline void dispatch_gpu_stable_sort(Iterator first, | |
35 | Iterator last, | |
36 | Compare compare, | |
37 | command_queue &queue) | |
38 | { | |
39 | size_t count = detail::iterator_range_size(first, last); | |
40 | ||
41 | if(count < 32){ | |
42 | detail::serial_insertion_sort( | |
43 | first, last, compare, queue | |
44 | ); | |
45 | } else { | |
46 | detail::merge_sort_on_gpu( | |
47 | first, last, compare, true /* stable */, queue | |
48 | ); | |
49 | } | |
50 | } | |
51 | ||
52 | template<class T> | |
53 | inline typename boost::enable_if_c<is_radix_sortable<T>::value>::type | |
54 | dispatch_gpu_stable_sort(buffer_iterator<T> first, | |
55 | buffer_iterator<T> last, | |
56 | less<T>, | |
57 | command_queue &queue) | |
58 | { | |
59 | ::boost::compute::detail::radix_sort(first, last, queue); | |
60 | } | |
61 | ||
62 | template<class T> | |
63 | inline typename boost::enable_if_c<is_radix_sortable<T>::value>::type | |
64 | dispatch_gpu_stable_sort(buffer_iterator<T> first, | |
65 | buffer_iterator<T> last, | |
66 | greater<T>, | |
67 | command_queue &queue) | |
68 | { | |
69 | // radix sorts in descending order | |
70 | ::boost::compute::detail::radix_sort(first, last, false, queue); | |
71 | } | |
72 | ||
73 | } // end detail namespace | |
74 | ||
75 | /// Sorts the values in the range [\p first, \p last) according to | |
76 | /// \p compare. The relative order of identical values is preserved. | |
77 | /// | |
b32b8144 FG |
78 | /// Space complexity: \Omega(n) |
79 | /// | |
7c673cae FG |
80 | /// \see sort(), is_sorted() |
81 | template<class Iterator, class Compare> | |
82 | inline void stable_sort(Iterator first, | |
83 | Iterator last, | |
84 | Compare compare, | |
85 | command_queue &queue = system::default_queue()) | |
86 | { | |
92f5a8d4 TL |
87 | BOOST_STATIC_ASSERT(is_device_iterator<Iterator>::value); |
88 | ||
7c673cae FG |
89 | if(queue.get_device().type() & device::gpu) { |
90 | ::boost::compute::detail::dispatch_gpu_stable_sort( | |
91 | first, last, compare, queue | |
92 | ); | |
93 | return; | |
94 | } | |
95 | ::boost::compute::detail::merge_sort_on_cpu(first, last, compare, queue); | |
96 | } | |
97 | ||
98 | /// \overload | |
99 | template<class Iterator> | |
100 | inline void stable_sort(Iterator first, | |
101 | Iterator last, | |
102 | command_queue &queue = system::default_queue()) | |
103 | { | |
92f5a8d4 | 104 | BOOST_STATIC_ASSERT(is_device_iterator<Iterator>::value); |
7c673cae FG |
105 | typedef typename std::iterator_traits<Iterator>::value_type value_type; |
106 | ||
107 | ::boost::compute::less<value_type> less; | |
108 | ||
109 | ::boost::compute::stable_sort(first, last, less, queue); | |
110 | } | |
111 | ||
112 | } // end compute namespace | |
113 | } // end boost namespace | |
114 | ||
115 | #endif // BOOST_COMPUTE_ALGORITHM_STABLE_SORT_HPP |