compute/algorithm/stable_sort.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_STABLE_SORT_HPP
0012 #define BOOST_COMPUTE_ALGORITHM_STABLE_SORT_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/detail/merge_sort_on_cpu.hpp>
0021 #include <boost/compute/algorithm/detail/merge_sort_on_gpu.hpp>
0022 #include <boost/compute/algorithm/detail/radix_sort.hpp>
0023 #include <boost/compute/algorithm/detail/insertion_sort.hpp>
0024 #include <boost/compute/algorithm/reverse.hpp>
0025 #include <boost/compute/functional/operator.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 Iterator, class Compare>
0034 inline void dispatch_gpu_stable_sort(Iterator first,
0035                                      Iterator last,
0036                                      Compare compare,
0037                                      command_queue &queue)
0038 {
0039     size_t count = detail::iterator_range_size(first, last);
0040
0041     if(count < 32){
0042         detail::serial_insertion_sort(
0043             first, last, compare, queue
0044         );
0045     } else {
0046         detail::merge_sort_on_gpu(
0047             first, last, compare, true /* stable */, queue
0048         );
0049     }
0050 }
0051
0052 template<class T>
0053 inline typename boost::enable_if_c<is_radix_sortable<T>::value>::type
0054 dispatch_gpu_stable_sort(buffer_iterator<T> first,
0055                          buffer_iterator<T> last,
0056                          less<T>,
0057                          command_queue &queue)
0058 {
0059     ::boost::compute::detail::radix_sort(first, last, queue);
0060 }
0061
0062 template<class T>
0063 inline typename boost::enable_if_c<is_radix_sortable<T>::value>::type
0064 dispatch_gpu_stable_sort(buffer_iterator<T> first,
0065                          buffer_iterator<T> last,
0066                          greater<T>,
0067                          command_queue &queue)
0068 {
0069     // radix sorts in descending order
0070     ::boost::compute::detail::radix_sort(first, last, false, queue);
0071 }
0072
0073 } // end detail namespace
0074
0075 /// Sorts the values in the range [\p first, \p last) according to
0076 /// \p compare. The relative order of identical values is preserved.
0077 ///
0078 /// Space complexity: \Omega(n)
0079 ///
0080 /// \see sort(), is_sorted()
0081 template<class Iterator, class Compare>
0082 inline void stable_sort(Iterator first,
0083                         Iterator last,
0084                         Compare compare,
0085                         command_queue &queue = system::default_queue())
0086 {
0087     BOOST_STATIC_ASSERT(is_device_iterator<Iterator>::value);
0088
0089     if(queue.get_device().type() & device::gpu) {
0090         ::boost::compute::detail::dispatch_gpu_stable_sort(
0091             first, last, compare, queue
0092         );
0093         return;
0094     }
0095     ::boost::compute::detail::merge_sort_on_cpu(first, last, compare, queue);
0096 }
0097
0098 /// \overload
0099 template<class Iterator>
0100 inline void stable_sort(Iterator first,
0101                         Iterator last,
0102                         command_queue &queue = system::default_queue())
0103 {
0104     BOOST_STATIC_ASSERT(is_device_iterator<Iterator>::value);
0105     typedef typename std::iterator_traits<Iterator>::value_type value_type;
0106
0107     ::boost::compute::less<value_type> less;
0108
0109     ::boost::compute::stable_sort(first, last, less, queue);
0110 }
0111
0112 } // end compute namespace
0113 } // end boost namespace
0114
0115 #endif // BOOST_COMPUTE_ALGORITHM_STABLE_SORT_HPP