compute/algorithm/nth_element.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_NTH_ELEMENT_HPP
0012 #define BOOST_COMPUTE_ALGORITHM_NTH_ELEMENT_HPP
0013
0014 #include <boost/static_assert.hpp>
0015
0016 #include <boost/compute/command_queue.hpp>
0017 #include <boost/compute/algorithm/fill_n.hpp>
0018 #include <boost/compute/algorithm/find.hpp>
0019 #include <boost/compute/algorithm/partition.hpp>
0020 #include <boost/compute/algorithm/sort.hpp>
0021 #include <boost/compute/functional/bind.hpp>
0022 #include <boost/compute/type_traits/is_device_iterator.hpp>
0023
0024 namespace boost {
0025 namespace compute {
0026
0027 /// Rearranges the elements in the range [\p first, \p last) such that
0028 /// the \p nth element would be in that position in a sorted sequence.
0029 ///
0030 /// Space complexity: \Omega(3n)
0031 template<class Iterator, class Compare>
0032 inline void nth_element(Iterator first,
0033                         Iterator nth,
0034                         Iterator last,
0035                         Compare compare,
0036                         command_queue &queue = system::default_queue())
0037 {
0038     BOOST_STATIC_ASSERT(is_device_iterator<Iterator>::value);
0039     if(nth == last) return;
0040
0041     typedef typename std::iterator_traits<Iterator>::value_type value_type;
0042
0043     while(1)
0044     {
0045         value_type value = nth.read(queue);
0046
0047         using boost::compute::placeholders::_1;
0048         Iterator new_nth = partition(
0049             first, last, ::boost::compute::bind(compare, _1, value), queue
0050         );
0051
0052         Iterator old_nth = find(new_nth, last, value, queue);
0053
0054         value_type new_value = new_nth.read(queue);
0055
0056         fill_n(new_nth, 1, value, queue);
0057         fill_n(old_nth, 1, new_value, queue);
0058
0059         new_value = nth.read(queue);
0060
0061         if(value == new_value) break;
0062
0063         if(std::distance(first, nth) < std::distance(first, new_nth))
0064         {
0065             last = new_nth;
0066         }
0067         else
0068         {
0069             first = new_nth;
0070         }
0071     }
0072 }
0073
0074 /// \overload
0075 template<class Iterator>
0076 inline void nth_element(Iterator first,
0077                         Iterator nth,
0078                         Iterator last,
0079                         command_queue &queue = system::default_queue())
0080 {
0081     BOOST_STATIC_ASSERT(is_device_iterator<Iterator>::value);
0082     if(nth == last) return;
0083
0084     typedef typename std::iterator_traits<Iterator>::value_type value_type;
0085
0086     less<value_type> less_than;
0087
0088     return nth_element(first, nth, last, less_than, queue);
0089 }
0090
0091 } // end compute namespace
0092 } // end boost namespace
0093
0094 #endif // BOOST_COMPUTE_ALGORITHM_NTH_ELEMENT_HPP