summaryrefslogtreecommitdiff
path: root/boost/compute/algorithm/nth_element.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/compute/algorithm/nth_element.hpp')
-rw-r--r--boost/compute/algorithm/nth_element.hpp87
1 files changed, 87 insertions, 0 deletions
diff --git a/boost/compute/algorithm/nth_element.hpp b/boost/compute/algorithm/nth_element.hpp
new file mode 100644
index 0000000000..68f7a3dbc0
--- /dev/null
+++ b/boost/compute/algorithm/nth_element.hpp
@@ -0,0 +1,87 @@
+//---------------------------------------------------------------------------//
+// 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.
+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