compute/algorithm/stable_sort_by_key.hpp

0001 //---------------------------------------------------------------------------//
0002 // Copyright (c) 2016 Jakub Szuppe <j.szuppe@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_STABLE_SORT_BY_KEY_HPP
0012 #define BOOST_COMPUTE_ALGORITHM_STABLE_SORT_BY_KEY_HPP
0013
0014 #include <iterator>
0015
0016 #include <boost/static_assert.hpp>
0017
0018 #include <boost/compute/system.hpp>
0019 #include <boost/compute/command_queue.hpp>
0020 #include <boost/compute/algorithm/sort_by_key.hpp>
0021 #include <boost/compute/detail/iterator_range_size.hpp>
0022 #include <boost/compute/type_traits/is_device_iterator.hpp>
0023
0024 namespace boost {
0025 namespace compute {
0026
0027 namespace detail {
0028
0029 template<class KeyIterator, class ValueIterator>
0030 inline void
0031 dispatch_gpu_ssort_by_key(KeyIterator keys_first,
0032                           KeyIterator keys_last,
0033                           ValueIterator values_first,
0034                           less<typename std::iterator_traits<KeyIterator>::value_type> compare,
0035                           command_queue &queue,
0036                           typename boost::enable_if_c<
0037                               is_radix_sortable<
0038                                   typename std::iterator_traits<KeyIterator>::value_type
0039                               >::value
0040                           >::type* = 0)
0041 {
0042     size_t count = detail::iterator_range_size(keys_first, keys_last);
0043
0044     if(count < 32){
0045         detail::serial_insertion_sort_by_key(
0046             keys_first, keys_last, values_first, compare, queue
0047         );
0048     }
0049     else {
0050         detail::radix_sort_by_key(
0051             keys_first, keys_last, values_first, queue
0052         );
0053     }
0054 }
0055
0056 template<class KeyIterator, class ValueIterator>
0057 inline void
0058 dispatch_gpu_ssort_by_key(KeyIterator keys_first,
0059                           KeyIterator keys_last,
0060                           ValueIterator values_first,
0061                           greater<typename std::iterator_traits<KeyIterator>::value_type> compare,
0062                           command_queue &queue,
0063                           typename boost::enable_if_c<
0064                               is_radix_sortable<
0065                                   typename std::iterator_traits<KeyIterator>::value_type
0066                               >::value
0067                           >::type* = 0)
0068 {
0069     size_t count = detail::iterator_range_size(keys_first, keys_last);
0070
0071     if(count < 32){
0072         detail::serial_insertion_sort_by_key(
0073             keys_first, keys_last, values_first, compare, queue
0074         );
0075     }
0076     else {
0077         // radix sorts in descending order
0078         detail::radix_sort_by_key(
0079             keys_first, keys_last, values_first, false, queue
0080         );
0081     }
0082 }
0083
0084 template<class KeyIterator, class ValueIterator, class Compare>
0085 inline void dispatch_gpu_ssort_by_key(KeyIterator keys_first,
0086                                       KeyIterator keys_last,
0087                                       ValueIterator values_first,
0088                                       Compare compare,
0089                                       command_queue &queue)
0090 {
0091     size_t count = detail::iterator_range_size(keys_first, keys_last);
0092
0093     if(count < 32){
0094         detail::serial_insertion_sort_by_key(
0095             keys_first, keys_last, values_first,
0096             compare, queue
0097         );
0098     } else {
0099         detail::merge_sort_by_key_on_gpu(
0100             keys_first, keys_last, values_first,
0101             compare, true /* stable */, queue
0102         );
0103     }
0104 }
0105
0106 template<class KeyIterator, class ValueIterator, class Compare>
0107 inline void dispatch_ssort_by_key(KeyIterator keys_first,
0108                                   KeyIterator keys_last,
0109                                   ValueIterator values_first,
0110                                   Compare compare,
0111                                   command_queue &queue)
0112 {
0113     if(queue.get_device().type() & device::gpu) {
0114         dispatch_gpu_ssort_by_key(
0115             keys_first, keys_last, values_first, compare, queue
0116         );
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 stable 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 stable_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_ssort_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 stable_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::stable_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_STABLE_SORT_BY_KEY_HPP