compute/algorithm/inplace_merge.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_INPLACE_MERGE_HPP
0012 #define BOOST_COMPUTE_ALGORITHM_INPLACE_MERGE_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/merge.hpp>
0021 #include <boost/compute/container/vector.hpp>
0022 #include <boost/compute/type_traits/is_device_iterator.hpp>
0023
0024 namespace boost {
0025 namespace compute {
0026
0027 /// Merges the sorted values in the range [\p first, \p middle) with
0028 /// the sorted values in the range [\p middle, \p last) in-place.
0029 ///
0030 /// Space complexity: \Omega(n)
0031 template<class Iterator>
0032 inline void inplace_merge(Iterator first,
0033                           Iterator middle,
0034                           Iterator last,
0035                           command_queue &queue = system::default_queue())
0036 {
0037     BOOST_STATIC_ASSERT(is_device_iterator<Iterator>::value);
0038     BOOST_ASSERT(first < middle && middle < last);
0039
0040     typedef typename std::iterator_traits<Iterator>::value_type T;
0041
0042     const context &context = queue.get_context();
0043
0044     ptrdiff_t left_size = std::distance(first, middle);
0045     ptrdiff_t right_size = std::distance(middle, last);
0046
0047     vector<T> left(left_size, context);
0048     vector<T> right(right_size, context);
0049
0050     copy(first, middle, left.begin(), queue);
0051     copy(middle, last, right.begin(), queue);
0052
0053     ::boost::compute::merge(
0054         left.begin(),
0055         left.end(),
0056         right.begin(),
0057         right.end(),
0058         first,
0059         queue
0060     );
0061 }
0062
0063 } // end compute namespace
0064 } // end boost namespace
0065
0066 #endif // BOOST_COMPUTE_ALGORITHM_INPLACE_MERGE_HPP