compute/algorithm/sort_by_key.hpp

0001 //---------------------------------------------------------------------------//
0002 // Copyright (c) 2013 Kyle Lutz <kyle.r.lutz@gmail.com>
0003 //
0004 // Distributed under the Boost Software License, Version 1.0
0005 // See accompanying file LICENSE_1_0.txt or copy at
0006 // http://www.boost.org/LICENSE_1_0.txt
0007 //
0008 // See http://boostorg.github.com/compute for more information.
0009 //---------------------------------------------------------------------------//
0010
0011 #ifndef BOOST_COMPUTE_ALGORITHM_SORT_BY_KEY_HPP
0012 #define BOOST_COMPUTE_ALGORITHM_SORT_BY_KEY_HPP
0013
0014 #include <iterator>
0015
0016 #include <boost/static_assert.hpp>
0017 #include <boost/utility/enable_if.hpp>
0018
0019 #include <boost/compute/system.hpp>
0020 #include <boost/compute/command_queue.hpp>
0021 #include <boost/compute/algorithm/detail/merge_sort_on_cpu.hpp>
0022 #include <boost/compute/algorithm/detail/merge_sort_on_gpu.hpp>
0023 #include <boost/compute/algorithm/detail/insertion_sort.hpp>
0024 #include <boost/compute/algorithm/detail/radix_sort.hpp>
0025 #include <boost/compute/algorithm/reverse.hpp>
0026 #include <boost/compute/detail/iterator_range_size.hpp>
0027 #include <boost/compute/type_traits/is_device_iterator.hpp>
0028
0029 namespace boost {
0030 namespace compute {
0031 namespace detail {
0032
0033 template<class KeyIterator, class ValueIterator>
0034 inline void
0035 dispatch_gpu_sort_by_key(KeyIterator keys_first,
0036                          KeyIterator keys_last,
0037                          ValueIterator values_first,
0038                          less<typename std::iterator_traits<KeyIterator>::value_type> compare,
0039                          command_queue &queue,
0040                          typename boost::enable_if_c<
0041                              is_radix_sortable<
0042                                  typename std::iterator_traits<KeyIterator>::value_type
0043                              >::value
0044                          >::type* = 0)
0045 {
0046     size_t count = detail::iterator_range_size(keys_first, keys_last);
0047
0048     if(count < 32){
0049         detail::serial_insertion_sort_by_key(
0050             keys_first, keys_last, values_first, compare, queue
0051         );
0052     }
0053     else {
0054         detail::radix_sort_by_key(
0055             keys_first, keys_last, values_first, queue
0056         );
0057     }
0058 }
0059
0060 template<class KeyIterator, class ValueIterator>
0061 inline void
0062 dispatch_gpu_sort_by_key(KeyIterator keys_first,
0063                          KeyIterator keys_last,
0064                          ValueIterator values_first,
0065                          greater<typename std::iterator_traits<KeyIterator>::value_type> compare,
0066                          command_queue &queue,
0067                          typename boost::enable_if_c<
0068                              is_radix_sortable<
0069                                  typename std::iterator_traits<KeyIterator>::value_type
0070                              >::value
0071                          >::type* = 0)
0072 {
0073     size_t count = detail::iterator_range_size(keys_first, keys_last);
0074
0075     if(count < 32){
0076         detail::serial_insertion_sort_by_key(
0077             keys_first, keys_last, values_first, compare, queue
0078         );
0079     }
0080     else {
0081         // radix sorts in descending order
0082         detail::radix_sort_by_key(
0083             keys_first, keys_last, values_first, false, queue
0084         );
0085     }
0086 }
0087
0088 template<class KeyIterator, class ValueIterator, class Compare>
0089 inline void dispatch_gpu_sort_by_key(KeyIterator keys_first,
0090                                      KeyIterator keys_last,
0091                                      ValueIterator values_first,
0092                                      Compare compare,
0093                                      command_queue &queue)
0094 {
0095     size_t count = detail::iterator_range_size(keys_first, keys_last);
0096
0097     if(count < 32){
0098         detail::serial_insertion_sort_by_key(
0099             keys_first, keys_last, values_first, compare, queue
0100         );
0101     } else {
0102         detail::merge_sort_by_key_on_gpu(
0103             keys_first, keys_last, values_first, compare, queue
0104         );
0105     }
0106 }
0107
0108 template<class KeyIterator, class ValueIterator, class Compare>
0109 inline void dispatch_sort_by_key(KeyIterator keys_first,
0110                                  KeyIterator keys_last,
0111                                  ValueIterator values_first,
0112                                  Compare compare,
0113                                  command_queue &queue)
0114 {
0115     if(queue.get_device().type() & device::gpu) {
0116         dispatch_gpu_sort_by_key(keys_first, keys_last, values_first, compare, queue);
0117         return;
0118     }
0119     ::boost::compute::detail::merge_sort_by_key_on_cpu(
0120         keys_first, keys_last, values_first, compare, queue
0121     );
0122 }
0123
0124 } // end detail namespace
0125
0126 /// Performs a key-value sort using the keys in the range [\p keys_first,
0127 /// \p keys_last) on the values in the range [\p values_first,
0128 /// \p values_first \c + (\p keys_last \c - \p keys_first)) using \p compare.
0129 ///
0130 /// If no compare function is specified, \c less is used.
0131 ///
0132 /// Space complexity: \Omega(2n)
0133 ///
0134 /// \see sort()
0135 template<class KeyIterator, class ValueIterator, class Compare>
0136 inline void sort_by_key(KeyIterator keys_first,
0137                         KeyIterator keys_last,
0138                         ValueIterator values_first,
0139                         Compare compare,
0140                         command_queue &queue = system::default_queue())
0141 {
0142     BOOST_STATIC_ASSERT(is_device_iterator<KeyIterator>::value);
0143     BOOST_STATIC_ASSERT(is_device_iterator<ValueIterator>::value);
0144     ::boost::compute::detail::dispatch_sort_by_key(
0145         keys_first, keys_last, values_first, compare, queue
0146     );
0147 }
0148
0149 /// \overload
0150 template<class KeyIterator, class ValueIterator>
0151 inline void sort_by_key(KeyIterator keys_first,
0152                         KeyIterator keys_last,
0153                         ValueIterator values_first,
0154                         command_queue &queue = system::default_queue())
0155 {
0156     BOOST_STATIC_ASSERT(is_device_iterator<KeyIterator>::value);
0157     BOOST_STATIC_ASSERT(is_device_iterator<ValueIterator>::value);
0158     typedef typename std::iterator_traits<KeyIterator>::value_type key_type;
0159
0160     ::boost::compute::sort_by_key(
0161         keys_first, keys_last, values_first, less<key_type>(), queue
0162     );
0163 }
0164
0165 } // end compute namespace
0166 } // end boost namespace
0167
0168 #endif // BOOST_COMPUTE_ALGORITHM_SORT_BY_KEY_HPP