diff options
author | DongHun Kwak <dh0128.kwak@samsung.com> | 2016-10-06 10:38:45 +0900 |
---|---|---|
committer | DongHun Kwak <dh0128.kwak@samsung.com> | 2016-10-06 10:39:52 +0900 |
commit | 5cde13f21d36c7224b0e13d11c4b49379ae5210d (patch) | |
tree | e8269ac85a4b0f7d416e2565fa4f451b5cb41351 /boost/compute/algorithm/nth_element.hpp | |
parent | d9ec475d945d3035377a0d89ed42e382d8988891 (diff) | |
download | boost-5cde13f21d36c7224b0e13d11c4b49379ae5210d.tar.gz boost-5cde13f21d36c7224b0e13d11c4b49379ae5210d.tar.bz2 boost-5cde13f21d36c7224b0e13d11c4b49379ae5210d.zip |
Imported Upstream version 1.61.0
Change-Id: I96a1f878d1e6164f01e9aadd5147f38fca448d90
Signed-off-by: DongHun Kwak <dh0128.kwak@samsung.com>
Diffstat (limited to 'boost/compute/algorithm/nth_element.hpp')
-rw-r--r-- | boost/compute/algorithm/nth_element.hpp | 87 |
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 |