1 //---------------------------------------------------------------------------//
2 // Copyright (c) 2013 Kyle Lutz <kyle.r.lutz@gmail.com>
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
8 // See http://boostorg.github.com/compute for more information.
9 //---------------------------------------------------------------------------//
11 #ifndef BOOST_COMPUTE_ALGORITHM_SORT_BY_KEY_HPP
12 #define BOOST_COMPUTE_ALGORITHM_SORT_BY_KEY_HPP
16 #include <boost/utility/enable_if.hpp>
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/insertion_sort.hpp>
23 #include <boost/compute/algorithm/detail/radix_sort.hpp>
24 #include <boost/compute/algorithm/reverse.hpp>
25 #include <boost/compute/detail/iterator_range_size.hpp>
32 template<class KeyIterator, class ValueIterator>
34 dispatch_gpu_sort_by_key(KeyIterator keys_first,
35 KeyIterator keys_last,
36 ValueIterator values_first,
37 less<typename std::iterator_traits<KeyIterator>::value_type> compare,
39 typename boost::enable_if_c<
41 typename std::iterator_traits<KeyIterator>::value_type
45 size_t count = detail::iterator_range_size(keys_first, keys_last);
48 detail::serial_insertion_sort_by_key(
49 keys_first, keys_last, values_first, compare, queue
53 detail::radix_sort_by_key(
54 keys_first, keys_last, values_first, queue
59 template<class KeyIterator, class ValueIterator>
61 dispatch_gpu_sort_by_key(KeyIterator keys_first,
62 KeyIterator keys_last,
63 ValueIterator values_first,
64 greater<typename std::iterator_traits<KeyIterator>::value_type> compare,
66 typename boost::enable_if_c<
68 typename std::iterator_traits<KeyIterator>::value_type
72 size_t count = detail::iterator_range_size(keys_first, keys_last);
75 detail::serial_insertion_sort_by_key(
76 keys_first, keys_last, values_first, compare, queue
80 // radix sorts in descending order
81 detail::radix_sort_by_key(
82 keys_first, keys_last, values_first, false, queue
87 template<class KeyIterator, class ValueIterator, class Compare>
88 inline void dispatch_gpu_sort_by_key(KeyIterator keys_first,
89 KeyIterator keys_last,
90 ValueIterator values_first,
94 size_t count = detail::iterator_range_size(keys_first, keys_last);
97 detail::serial_insertion_sort_by_key(
98 keys_first, keys_last, values_first, compare, queue
101 detail::merge_sort_by_key_on_gpu(
102 keys_first, keys_last, values_first, compare, queue
107 template<class KeyIterator, class ValueIterator, class Compare>
108 inline void dispatch_sort_by_key(KeyIterator keys_first,
109 KeyIterator keys_last,
110 ValueIterator values_first,
112 command_queue &queue)
114 if(queue.get_device().type() & device::gpu) {
115 dispatch_gpu_sort_by_key(keys_first, keys_last, values_first, compare, queue);
118 ::boost::compute::detail::merge_sort_by_key_on_cpu(
119 keys_first, keys_last, values_first, compare, queue
123 } // end detail namespace
125 /// Performs a key-value sort using the keys in the range [\p keys_first,
126 /// \p keys_last) on the values in the range [\p values_first,
127 /// \p values_first \c + (\p keys_last \c - \p keys_first)) using \p compare.
129 /// If no compare function is specified, \c less is used.
131 /// Space complexity: \Omega(2n)
134 template<class KeyIterator, class ValueIterator, class Compare>
135 inline void sort_by_key(KeyIterator keys_first,
136 KeyIterator keys_last,
137 ValueIterator values_first,
139 command_queue &queue = system::default_queue())
141 ::boost::compute::detail::dispatch_sort_by_key(
142 keys_first, keys_last, values_first, compare, queue
147 template<class KeyIterator, class ValueIterator>
148 inline void sort_by_key(KeyIterator keys_first,
149 KeyIterator keys_last,
150 ValueIterator values_first,
151 command_queue &queue = system::default_queue())
153 typedef typename std::iterator_traits<KeyIterator>::value_type key_type;
155 ::boost::compute::sort_by_key(
156 keys_first, keys_last, values_first, less<key_type>(), queue
160 } // end compute namespace
161 } // end boost namespace
163 #endif // BOOST_COMPUTE_ALGORITHM_SORT_BY_KEY_HPP