1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
|
//---------------------------------------------------------------------------//
// Copyright (c) 2013 Kyle Lutz <kyle.r.lutz@gmail.com>
//
// Distributed under the Boost Software License, Version 1.0
// See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt
//
// See http://boostorg.github.com/compute for more information.
//---------------------------------------------------------------------------//
#ifndef BOOST_COMPUTE_ALGORITHM_NTH_ELEMENT_HPP
#define BOOST_COMPUTE_ALGORITHM_NTH_ELEMENT_HPP
#include <boost/compute/command_queue.hpp>
#include <boost/compute/algorithm/fill_n.hpp>
#include <boost/compute/algorithm/find.hpp>
#include <boost/compute/algorithm/partition.hpp>
#include <boost/compute/algorithm/sort.hpp>
#include <boost/compute/functional/bind.hpp>
namespace boost {
namespace compute {
/// Rearranges the elements in the range [\p first, \p last) such that
/// the \p nth element would be in that position in a sorted sequence.
///
/// Space complexity: \Omega(3n)
template<class Iterator, class Compare>
inline void nth_element(Iterator first,
Iterator nth,
Iterator last,
Compare compare,
command_queue &queue = system::default_queue())
{
if(nth == last) return;
typedef typename std::iterator_traits<Iterator>::value_type value_type;
while(1)
{
value_type value = nth.read(queue);
using boost::compute::placeholders::_1;
Iterator new_nth = partition(
first, last, ::boost::compute::bind(compare, _1, value), queue
);
Iterator old_nth = find(new_nth, last, value, queue);
value_type new_value = new_nth.read(queue);
fill_n(new_nth, 1, value, queue);
fill_n(old_nth, 1, new_value, queue);
new_value = nth.read(queue);
if(value == new_value) break;
if(std::distance(first, nth) < std::distance(first, new_nth))
{
last = new_nth;
}
else
{
first = new_nth;
}
}
}
/// \overload
template<class Iterator>
inline void nth_element(Iterator first,
Iterator nth,
Iterator last,
command_queue &queue = system::default_queue())
{
if(nth == last) return;
typedef typename std::iterator_traits<Iterator>::value_type value_type;
less<value_type> less_than;
return nth_element(first, nth, last, less_than, queue);
}
} // end compute namespace
} // end boost namespace
#endif // BOOST_COMPUTE_ALGORITHM_NTH_ELEMENT_HPP
|
