Fixed the binary search and added tests
MODIFY
test/CMakeLists.txt
test/CMakeLists.txt
@@ -57,6 +57,8 @@ endfunction()
# ****************************************************************************
add_hipthrust_test("thrust.hip.allocator" test_allocator.cpp)
+add_hipthrust_test("thrust.hip.binary_search" test_binary_search.cpp)
+add_hipthrust_test("thrust.hip.binary_search_vector" test_binary_search_vector.cpp)
# add_hipthrust_test("thrust.hip.complex" test_complex.cpp)
# add_hipthrust_test("thrust.hip.complex_transform" test_complex_transform.cpp)
add_hipthrust_test("thrust.hip.constant_iterator" test_constant_iterator.cpp)

ADD
test/test_binary_search.cpp
+// MIT License
+//
+// Copyright (c) 2018 Advanced Micro Devices, Inc. All rights reserved.
+//
+// Permission is hereby granted, free of charge, to any person obtaining a copy
+// of this software and associated documentation files (the "Software"), to deal
+// in the Software without restriction, including without limitation the rights
+// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+// copies of the Software, and to permit persons to whom the Software is
+// furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in all
+// copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+// SOFTWARE.
+
+// Google Test
+#include <gtest/gtest.h>
+
+// Thrust
+#include <thrust/binary_search.h>
+#include <thrust/iterator/retag.h>
+#include <thrust/sequence.h>
+#include <thrust/sort.h>
+
+// HIP API
+#if THRUST_DEVICE_COMPILER == THRUST_DEVICE_COMPILER_HCC
+#include <hip/hip_runtime_api.h>
+
+#define HIP_CHECK(condition) ASSERT_EQ(condition, hipSuccess)
+#endif // THRUST_DEVICE_COMPILER == THRUST_DEVICE_COMPILER_HCC
+
+#include "test_utils.hpp"
+
+template<
+ class InputType
+>
+struct Params
+{
+ using input_type = InputType;
+};
+
+template<class Params>
+class BinarySearchTests : public ::testing::Test
+{
+public:
+ using input_type = typename Params::input_type;
+};
+
+typedef ::testing::Types<
+ Params<thrust::host_vector<short>>,
+ Params<thrust::host_vector<int>>,
+ Params<thrust::host_vector<long long>>,
+ Params<thrust::host_vector<unsigned short>>,
+ Params<thrust::host_vector<unsigned int>>,
+ Params<thrust::host_vector<unsigned long long>>,
+ Params<thrust::host_vector<float>>,
+ Params<thrust::host_vector<double>>,
+ Params<thrust::device_vector<short>>,
+ Params<thrust::device_vector<int>>,
+ Params<thrust::device_vector<long long>>,
+ Params<thrust::device_vector<unsigned short>>,
+ Params<thrust::device_vector<unsigned int>>,
+ Params<thrust::device_vector<unsigned long long>>,
+ Params<thrust::device_vector<float>>,
+ Params<thrust::device_vector<double>>
+> BinarySearchTestsParams;
+
+TYPED_TEST_CASE(BinarySearchTests, BinarySearchTestsParams);
+
+__THRUST_DISABLE_MSVC_POSSIBLE_LOSS_OF_DATA_WARNING_BEGIN
+
+TYPED_TEST(BinarySearchTests, TestScalarLowerBoundSimple)
+{
+ using Vector = typename TestFixture::input_type;
+ using T = typename Vector::value_type;
+
+ Vector vec(5);
+
+ vec[0] = 0;
+ vec[1] = 2;
+ vec[2] = 5;
+ vec[3] = 7;
+ vec[4] = 8;
+
+ ASSERT_EQ(thrust::lower_bound(vec.begin(), vec.end(), 0) - vec.begin(), 0);
+ ASSERT_EQ(thrust::lower_bound(vec.begin(), vec.end(), 1) - vec.begin(), 1);
+ ASSERT_EQ(thrust::lower_bound(vec.begin(), vec.end(), 2) - vec.begin(), 1);
+ ASSERT_EQ(thrust::lower_bound(vec.begin(), vec.end(), 3) - vec.begin(), 2);
+ ASSERT_EQ(thrust::lower_bound(vec.begin(), vec.end(), 4) - vec.begin(), 2);
+ ASSERT_EQ(thrust::lower_bound(vec.begin(), vec.end(), 5) - vec.begin(), 2);
+ ASSERT_EQ(thrust::lower_bound(vec.begin(), vec.end(), 6) - vec.begin(), 3);
+ ASSERT_EQ(thrust::lower_bound(vec.begin(), vec.end(), 7) - vec.begin(), 3);
+ ASSERT_EQ(thrust::lower_bound(vec.begin(), vec.end(), 8) - vec.begin(), 4);
+ ASSERT_EQ(thrust::lower_bound(vec.begin(), vec.end(), 9) - vec.begin(), 5);
+}
+
+template<typename ForwardIterator, typename LessThanComparable>
+ForwardIterator lower_bound(my_system &system, ForwardIterator first, ForwardIterator, const LessThanComparable &)
+{
+ system.validate_dispatch();
+ return first;
+}
+
+TEST(BinarySearchTests, TestScalarLowerBoundDispatchExplicit)
+{
+ thrust::device_vector<int> vec(1);
+
+ my_system sys(0);
+ thrust::lower_bound(sys,
+ vec.begin(),
+ vec.end(),
+ 0);
+
+ ASSERT_EQ(true, sys.is_valid());
+}
+
+template<typename ForwardIterator, typename LessThanComparable>
+ForwardIterator lower_bound(my_tag, ForwardIterator first, ForwardIterator, const LessThanComparable &)
+{
+ *first = 13;
+ return first;
+}
+
+TEST(BinarySearchTests, TestScalarLowerBoundDispatchImplicit)
+{
+ thrust::device_vector<int> vec(1);
+
+ thrust::lower_bound(thrust::retag<my_tag>(vec.begin()),
+ thrust::retag<my_tag>(vec.end()),
+ 0);
+
+ ASSERT_EQ(13, vec.front());
+}
+
+TYPED_TEST(BinarySearchTests, TestScalarUpperBoundSimple)
+{
+ using Vector = typename TestFixture::input_type;
+ Vector vec(5);
+
+ vec[0] = 0;
+ vec[1] = 2;
+ vec[2] = 5;
+ vec[3] = 7;
+ vec[4] = 8;
+
+ ASSERT_EQ(thrust::upper_bound(vec.begin(), vec.end(), 0) - vec.begin(), 1);
+ ASSERT_EQ(thrust::upper_bound(vec.begin(), vec.end(), 1) - vec.begin(), 1);
+ ASSERT_EQ(thrust::upper_bound(vec.begin(), vec.end(), 2) - vec.begin(), 2);
+ ASSERT_EQ(thrust::upper_bound(vec.begin(), vec.end(), 3) - vec.begin(), 2);
+ ASSERT_EQ(thrust::upper_bound(vec.begin(), vec.end(), 4) - vec.begin(), 2);
+ ASSERT_EQ(thrust::upper_bound(vec.begin(), vec.end(), 5) - vec.begin(), 3);
+ ASSERT_EQ(thrust::upper_bound(vec.begin(), vec.end(), 6) - vec.begin(), 3);
+ ASSERT_EQ(thrust::upper_bound(vec.begin(), vec.end(), 7) - vec.begin(), 4);
+ ASSERT_EQ(thrust::upper_bound(vec.begin(), vec.end(), 8) - vec.begin(), 5);
+ ASSERT_EQ(thrust::upper_bound(vec.begin(), vec.end(), 9) - vec.begin(), 5);
+}
+
+template<typename ForwardIterator, typename LessThanComparable>
+ForwardIterator upper_bound(my_system &system, ForwardIterator first, ForwardIterator, const LessThanComparable &)
+{
+ system.validate_dispatch();
+ return first;
+}
+
+TEST(BinarySearchTests, TestScalarUpperBoundDispatchExplicit)
+{
+ thrust::device_vector<int> vec(1);
+
+ my_system sys(0);
+ thrust::upper_bound(sys,
+ vec.begin(),
+ vec.end(),
+ 0);
+
+ ASSERT_EQ(true, sys.is_valid());
+}
+
+template<typename ForwardIterator, typename LessThanComparable>
+ForwardIterator upper_bound(my_tag, ForwardIterator first, ForwardIterator, const LessThanComparable &)
+{
+ *first = 13;
+ return first;
+}
+
+TEST(BinarySearchTests, TestScalarUpperBoundDispatchImplicit)
+{
+ thrust::device_vector<int> vec(1);
+
+ thrust::upper_bound(thrust::retag<my_tag>(vec.begin()),
+ thrust::retag<my_tag>(vec.end()),
+ 0);
+
+ ASSERT_EQ(13, vec.front());
+}
+
+TYPED_TEST(BinarySearchTests, TestScalarBinarySearchSimple)
+{
+ using Vector = typename TestFixture::input_type;
+ Vector vec(5);
+
+ vec[0] = 0;
+ vec[1] = 2;
+ vec[2] = 5;
+ vec[3] = 7;
+ vec[4] = 8;
+
+ ASSERT_EQ(thrust::binary_search(vec.begin(), vec.end(), 0), true);
+ ASSERT_EQ(thrust::binary_search(vec.begin(), vec.end(), 1), false);
+ ASSERT_EQ(thrust::binary_search(vec.begin(), vec.end(), 2), true);
+ ASSERT_EQ(thrust::binary_search(vec.begin(), vec.end(), 3), false);
+ ASSERT_EQ(thrust::binary_search(vec.begin(), vec.end(), 4), false);
+ ASSERT_EQ(thrust::binary_search(vec.begin(), vec.end(), 5), true);
+ ASSERT_EQ(thrust::binary_search(vec.begin(), vec.end(), 6), false);
+ ASSERT_EQ(thrust::binary_search(vec.begin(), vec.end(), 7), true);
+ ASSERT_EQ(thrust::binary_search(vec.begin(), vec.end(), 8), true);
+ ASSERT_EQ(thrust::binary_search(vec.begin(), vec.end(), 9), false);
+}
+
+template<typename ForwardIterator, typename LessThanComparable>
+bool binary_search(my_system &system, ForwardIterator, ForwardIterator, const LessThanComparable &)
+{
+ system.validate_dispatch();
+ return false;
+}
+
+TEST(BinarySearchTests, TestScalarBinarySearchDispatchExplicit)
+{
+ thrust::device_vector<int> vec(1);
+
+ my_system sys(0);
+ thrust::binary_search(sys,
+ vec.begin(),
+ vec.end(),
+ 0);
+
+ ASSERT_EQ(true, sys.is_valid());
+}
+
+template<typename ForwardIterator, typename LessThanComparable>
+bool binary_search(my_tag, ForwardIterator first, ForwardIterator, const LessThanComparable &)
+{
+ *first = 13;
+ return false;
+}
+
+TEST(BinarySearchTests, TestScalarBinarySearchDispatchImplicit)
+{
+ thrust::device_vector<int> vec(1);
+
+ thrust::binary_search(thrust::retag<my_tag>(vec.begin()),
+ thrust::retag<my_tag>(vec.end()),
+ 0);
+
+ ASSERT_EQ(13, vec.front());
+}
+
+TYPED_TEST(BinarySearchTests, TestScalarEqualRangeSimple)
+{
+ using Vector = typename TestFixture::input_type;
+ Vector vec(5);
+
+ vec[0] = 0;
+ vec[1] = 2;
+ vec[2] = 5;
+ vec[3] = 7;
+ vec[4] = 8;
+
+ ASSERT_EQ(thrust::equal_range(vec.begin(), vec.end(), 0).first - vec.begin(), 0);
+ ASSERT_EQ(thrust::equal_range(vec.begin(), vec.end(), 1).first - vec.begin(), 1);
+ ASSERT_EQ(thrust::equal_range(vec.begin(), vec.end(), 2).first - vec.begin(), 1);
+ ASSERT_EQ(thrust::equal_range(vec.begin(), vec.end(), 3).first - vec.begin(), 2);
+ ASSERT_EQ(thrust::equal_range(vec.begin(), vec.end(), 4).first - vec.begin(), 2);
+ ASSERT_EQ(thrust::equal_range(vec.begin(), vec.end(), 5).first - vec.begin(), 2);
+ ASSERT_EQ(thrust::equal_range(vec.begin(), vec.end(), 6).first - vec.begin(), 3);
+ ASSERT_EQ(thrust::equal_range(vec.begin(), vec.end(), 7).first - vec.begin(), 3);
+ ASSERT_EQ(thrust::equal_range(vec.begin(), vec.end(), 8).first - vec.begin(), 4);
+ ASSERT_EQ(thrust::equal_range(vec.begin(), vec.end(), 9).first - vec.begin(), 5);
+
+ ASSERT_EQ(thrust::equal_range(vec.begin(), vec.end(), 0).second - vec.begin(), 1);
+ ASSERT_EQ(thrust::equal_range(vec.begin(), vec.end(), 1).second - vec.begin(), 1);
+ ASSERT_EQ(thrust::equal_range(vec.begin(), vec.end(), 2).second - vec.begin(), 2);
+ ASSERT_EQ(thrust::equal_range(vec.begin(), vec.end(), 3).second - vec.begin(), 2);
+ ASSERT_EQ(thrust::equal_range(vec.begin(), vec.end(), 4).second - vec.begin(), 2);
+ ASSERT_EQ(thrust::equal_range(vec.begin(), vec.end(), 5).second - vec.begin(), 3);
+ ASSERT_EQ(thrust::equal_range(vec.begin(), vec.end(), 6).second - vec.begin(), 3);
+ ASSERT_EQ(thrust::equal_range(vec.begin(), vec.end(), 7).second - vec.begin(), 4);
+ ASSERT_EQ(thrust::equal_range(vec.begin(), vec.end(), 8).second - vec.begin(), 5);
+ ASSERT_EQ(thrust::equal_range(vec.begin(), vec.end(), 9).second - vec.begin(), 5);
+}
+
+template<typename ForwardIterator, typename LessThanComparable>
+thrust::pair<ForwardIterator,ForwardIterator> equal_range(my_system &system, ForwardIterator first, ForwardIterator, const LessThanComparable &)
+{
+ system.validate_dispatch();
+ return thrust::make_pair(first,first);
+}
+
+TEST(BinarySearchTests, TestScalarEqualRangeDispatchExplicit)
+{
+ thrust::device_vector<int> vec(1);
+
+ my_system sys(0);
+ thrust::equal_range(sys,
+ vec.begin(),
+ vec.end(),
+ 0);
+
+ ASSERT_EQ(true, sys.is_valid());
+}
+
+template<typename ForwardIterator, typename LessThanComparable>
+thrust::pair<ForwardIterator,ForwardIterator> equal_range(my_tag, ForwardIterator first, ForwardIterator, const LessThanComparable &)
+{
+ *first = 13;
+ return thrust::make_pair(first,first);
+}
+
+TEST(BinarySearchTests, TestScalarEqualRangeDispatchImplicit)
+{
+ thrust::device_vector<int> vec(1);
+
+ thrust::binary_search(thrust::retag<my_tag>(vec.begin()),
+ thrust::retag<my_tag>(vec.end()),
+ 0);
+
+ ASSERT_EQ(13, vec.front());
+}
+
+__THRUST_DISABLE_MSVC_POSSIBLE_LOSS_OF_DATA_WARNING_END

ADD
test/test_binary_search_vector.cpp
+// MIT License
+//
+// Copyright (c) 2018 Advanced Micro Devices, Inc. All rights reserved.
+//
+// Permission is hereby granted, free of charge, to any person obtaining a copy
+// of this software and associated documentation files (the "Software"), to deal
+// in the Software without restriction, including without limitation the rights
+// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+// copies of the Software, and to permit persons to whom the Software is
+// furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in all
+// copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+// SOFTWARE.
+
+// Google Test
+#include <gtest/gtest.h>
+
+// Thrust
+#include <thrust/binary_search.h>
+#include <thrust/sequence.h>
+#include <thrust/sort.h>
+#include <thrust/iterator/discard_iterator.h>
+#include <thrust/iterator/retag.h>
+
+// HIP API
+#if THRUST_DEVICE_COMPILER == THRUST_DEVICE_COMPILER_HCC
+#include <hip/hip_runtime_api.h>
+
+#define HIP_CHECK(condition) ASSERT_EQ(condition, hipSuccess)
+#endif // THRUST_DEVICE_COMPILER == THRUST_DEVICE_COMPILER_HCC
+
+#include "test_utils.hpp"
+#include "test_assertions.hpp"
+
+template<
+ class InputType
+>
+struct Params
+{
+ using input_type = InputType;
+};
+
+template<class Params>
+class BinarySearchVectorTests : public ::testing::Test
+{
+public:
+ using input_type = typename Params::input_type;
+};
+
+typedef ::testing::Types<
+ Params<thrust::host_vector<short>>,
+ Params<thrust::host_vector<int>>,
+ Params<thrust::host_vector<long long>>,
+ Params<thrust::host_vector<unsigned short>>,
+ Params<thrust::host_vector<unsigned int>>,
+ Params<thrust::host_vector<unsigned long long>>,
+ Params<thrust::host_vector<float>>,
+ Params<thrust::host_vector<double>>,
+ Params<thrust::device_vector<short>>,
+ Params<thrust::device_vector<int>>,
+ Params<thrust::device_vector<long long>>,
+ Params<thrust::device_vector<unsigned short>>,
+ Params<thrust::device_vector<unsigned int>>,
+ Params<thrust::device_vector<unsigned long long>>,
+ Params<thrust::device_vector<float>>,
+ Params<thrust::device_vector<double>>
+> BinarySearchVectorTestsParams;
+
+TYPED_TEST_CASE(BinarySearchVectorTests, BinarySearchVectorTestsParams);
+
+template<class Params>
+class BinarySearchVectorIntegerTests : public ::testing::Test
+{
+public:
+ using input_type = typename Params::input_type;
+};
+
+typedef ::testing::Types<
+ Params<short>,
+ Params<int>,
+ Params<long long>
+> BinarySearchVectorIntegerTestsParams;
+
+TYPED_TEST_CASE(BinarySearchVectorIntegerTests, BinarySearchVectorIntegerTestsParams);
+
+
+// convert xxx_vector<T1> to xxx_vector<T2>
+template <class ExampleVector, typename NewType>
+struct vector_like
+{
+ typedef typename ExampleVector::allocator_type alloc;
+ typedef typename alloc::template rebind<NewType>::other new_alloc;
+ typedef thrust::detail::vector_base<NewType, new_alloc> type;
+};
+
+TYPED_TEST(BinarySearchVectorTests, TestScalarLowerBoundSimple)
+{
+ using Vector = typename TestFixture::input_type;
+ Vector vec(5);
+
+ vec[0] = 0;
+ vec[1] = 2;
+ vec[2] = 5;
+ vec[3] = 7;
+ vec[4] = 8;
+
+ Vector input(10);
+ thrust::sequence(input.begin(), input.end());
+
+ typedef typename vector_like<Vector, int>::type IntVector;
+
+ // test with integral output type
+ IntVector integral_output(10);
+ thrust::lower_bound(vec.begin(), vec.end(), input.begin(), input.end(), integral_output.begin());
+
+ typename IntVector::iterator output_end = thrust::lower_bound(vec.begin(), vec.end(), input.begin(), input.end(), integral_output.begin());
+
+ ASSERT_EQ((output_end - integral_output.begin()), 10);
+
+ ASSERT_EQ(integral_output[0], 0);
+ ASSERT_EQ(integral_output[1], 1);
+ ASSERT_EQ(integral_output[2], 1);
+ ASSERT_EQ(integral_output[3], 2);
+ ASSERT_EQ(integral_output[4], 2);
+ ASSERT_EQ(integral_output[5], 2);
+ ASSERT_EQ(integral_output[6], 3);
+ ASSERT_EQ(integral_output[7], 3);
+ ASSERT_EQ(integral_output[8], 4);
+ ASSERT_EQ(integral_output[9], 5);
+
+ //// test with iterator output type
+ //typedef typename vector_like<Vector, typename Vector::iterator>::type IteratorVector;
+ //IteratorVector iterator_output(10);
+ //thrust::lower_bound(vec.begin(), vec.end(), input.begin(), input.end(), iterator_output.begin());
+
+ //ASSERT_EQ(iterator_output[0] - vec.begin(), 0);
+ //ASSERT_EQ(iterator_output[1] - vec.begin(), 1);
+ //ASSERT_EQ(iterator_output[2] - vec.begin(), 1);
+ //ASSERT_EQ(iterator_output[3] - vec.begin(), 2);
+ //ASSERT_EQ(iterator_output[4] - vec.begin(), 2);
+ //ASSERT_EQ(iterator_output[5] - vec.begin(), 2);
+ //ASSERT_EQ(iterator_output[6] - vec.begin(), 3);
+ //ASSERT_EQ(iterator_output[7] - vec.begin(), 3);
+ //ASSERT_EQ(iterator_output[8] - vec.begin(), 4);
+ //ASSERT_EQ(iterator_output[9] - vec.begin(), 5);
+}
+
+template<typename ForwardIterator, typename InputIterator, typename OutputIterator>
+OutputIterator lower_bound(my_system &system, ForwardIterator,ForwardIterator,InputIterator,InputIterator,OutputIterator output)
+{
+ system.validate_dispatch();
+ return output;
+}
+
+TEST(BinarySearchVectorTests, TestVectorLowerBoundDispatchExplicit)
+{
+ thrust::device_vector<int> vec(1);
+
+ my_system sys(0);
+ thrust::lower_bound(sys,
+ vec.begin(),
+ vec.end(),
+ vec.begin(),
+ vec.end(),
+ vec.begin());
+
+ ASSERT_EQ(true, sys.is_valid());
+}
+
+template<typename ForwardIterator, typename InputIterator, typename OutputIterator>
+OutputIterator lower_bound(my_tag, ForwardIterator,ForwardIterator,InputIterator,InputIterator,OutputIterator output)
+{
+ *output = 13;
+ return output;
+}
+
+TEST(BinarySearchVectorTests, TestVectorLowerBoundDispatchImplicit)
+{
+ thrust::device_vector<int> vec(1);
+
+ thrust::lower_bound(thrust::retag<my_tag>(vec.begin()),
+ thrust::retag<my_tag>(vec.end()),
+ thrust::retag<my_tag>(vec.begin()),
+ thrust::retag<my_tag>(vec.end()),
+ thrust::retag<my_tag>(vec.begin()));
+
+ ASSERT_EQ(13, vec.front());
+}
+
+TYPED_TEST(BinarySearchVectorTests, TestVectorUpperBoundSimple)
+{
+ using Vector = typename TestFixture::input_type;
+ Vector vec(5);
+
+ vec[0] = 0;
+ vec[1] = 2;
+ vec[2] = 5;
+ vec[3] = 7;
+ vec[4] = 8;
+
+ Vector input(10);
+ thrust::sequence(input.begin(), input.end());
+
+ typedef typename vector_like<Vector, int>::type IntVector;
+
+ // test with integral output type
+ IntVector integral_output(10);
+ typename IntVector::iterator output_end = thrust::upper_bound(vec.begin(), vec.end(), input.begin(), input.end(), integral_output.begin());
+
+ ASSERT_EQ((output_end - integral_output.begin()), 10);
+
+ ASSERT_EQ(integral_output[0], 1);
+ ASSERT_EQ(integral_output[1], 1);
+ ASSERT_EQ(integral_output[2], 2);
+ ASSERT_EQ(integral_output[3], 2);
+ ASSERT_EQ(integral_output[4], 2);
+ ASSERT_EQ(integral_output[5], 3);
+ ASSERT_EQ(integral_output[6], 3);
+ ASSERT_EQ(integral_output[7], 4);
+ ASSERT_EQ(integral_output[8], 5);
+ ASSERT_EQ(integral_output[9], 5);
+
+ //// test with iterator output type
+ //typedef typename vector_like<Vector, typename Vector::iterator>::type IteratorVector;
+ //IteratorVector iterator_output(10);
+ //thrust::upper_bound(vec.begin(), vec.end(), input.begin(), input.end(), iterator_output.begin());
+
+ //ASSERT_EQ(iterator_output[0] - vec.begin(), 1);
+ //ASSERT_EQ(iterator_output[1] - vec.begin(), 1);
+ //ASSERT_EQ(iterator_output[2] - vec.begin(), 2);
+ //ASSERT_EQ(iterator_output[3] - vec.begin(), 2);
+ //ASSERT_EQ(iterator_output[4] - vec.begin(), 2);
+ //ASSERT_EQ(iterator_output[5] - vec.begin(), 3);
+ //ASSERT_EQ(iterator_output[6] - vec.begin(), 3);
+ //ASSERT_EQ(iterator_output[7] - vec.begin(), 4);
+ //ASSERT_EQ(iterator_output[8] - vec.begin(), 5);
+ //ASSERT_EQ(iterator_output[9] - vec.begin(), 5);
+}
+
+template<typename ForwardIterator, typename InputIterator, typename OutputIterator>
+OutputIterator upper_bound(my_system &system, ForwardIterator,ForwardIterator,InputIterator,InputIterator,OutputIterator output)
+{
+ system.validate_dispatch();
+ return output;
+}
+
+TEST(BinarySearchVectorTests, TestVectorUpperBoundDispatchExplicit)
+{
+ thrust::device_vector<int> vec(1);
+
+ my_system sys(0);
+ thrust::upper_bound(sys,
+ vec.begin(),
+ vec.end(),
+ vec.begin(),
+ vec.end(),
+ vec.begin());
+
+ ASSERT_EQ(true, sys.is_valid());
+}
+
+template<typename ForwardIterator, typename InputIterator, typename OutputIterator>
+OutputIterator upper_bound(my_tag, ForwardIterator,ForwardIterator,InputIterator,InputIterator,OutputIterator output)
+{
+ *output = 13;
+ return output;
+}
+
+TEST(BinarySearchVectorTests, TestVectorUpperBoundDispatchImplicit)
+{
+ thrust::device_vector<int> vec(1);
+
+ thrust::upper_bound(thrust::retag<my_tag>(vec.begin()),
+ thrust::retag<my_tag>(vec.end()),
+ thrust::retag<my_tag>(vec.begin()),
+ thrust::retag<my_tag>(vec.end()),
+ thrust::retag<my_tag>(vec.begin()));
+
+ ASSERT_EQ(13, vec.front());
+}
+
+TYPED_TEST(BinarySearchVectorTests, TestVectorBinarySearchSimple)
+{
+ using Vector = typename TestFixture::input_type;
+ Vector vec(5);
+
+ vec[0] = 0;
+ vec[1] = 2;
+ vec[2] = 5;
+ vec[3] = 7;
+ vec[4] = 8;
+
+ Vector input(10);
+ thrust::sequence(input.begin(), input.end());
+
+ typedef typename vector_like<Vector, bool>::type BoolVector;
+ typedef typename vector_like<Vector, int>::type IntVector;
+
+ // test with boolean output type
+ BoolVector bool_output(10);
+ typename BoolVector::iterator bool_output_end = thrust::binary_search(vec.begin(), vec.end(), input.begin(), input.end(), bool_output.begin());
+
+ ASSERT_EQ((bool_output_end - bool_output.begin()), 10);
+
+ ASSERT_EQ(bool_output[0], true);
+ ASSERT_EQ(bool_output[1], false);
+ ASSERT_EQ(bool_output[2], true);
+ ASSERT_EQ(bool_output[3], false);
+ ASSERT_EQ(bool_output[4], false);
+ ASSERT_EQ(bool_output[5], true);
+ ASSERT_EQ(bool_output[6], false);
+ ASSERT_EQ(bool_output[7], true);
+ ASSERT_EQ(bool_output[8], true);
+ ASSERT_EQ(bool_output[9], false);
+
+ // test with integral output type
+ IntVector integral_output(10, 2);
+ typename IntVector::iterator int_output_end = thrust::binary_search(vec.begin(), vec.end(), input.begin(), input.end(), integral_output.begin());
+
+ ASSERT_EQ((int_output_end - integral_output.begin()), 10);
+
+ ASSERT_EQ(integral_output[0], 1);
+ ASSERT_EQ(integral_output[1], 0);
+ ASSERT_EQ(integral_output[2], 1);
+ ASSERT_EQ(integral_output[3], 0);
+ ASSERT_EQ(integral_output[4], 0);
+ ASSERT_EQ(integral_output[5], 1);
+ ASSERT_EQ(integral_output[6], 0);
+ ASSERT_EQ(integral_output[7], 1);
+ ASSERT_EQ(integral_output[8], 1);
+ ASSERT_EQ(integral_output[9], 0);
+}
+
+template<typename ForwardIterator, typename InputIterator, typename OutputIterator>
+OutputIterator binary_search(my_system &system, ForwardIterator,ForwardIterator,InputIterator,InputIterator,OutputIterator output)
+{
+ system.validate_dispatch();
+ return output;
+}
+
+TEST(BinarySearchVectorTests, TestVectorBinarySearchDispatchExplicit)
+{
+ thrust::device_vector<int> vec(1);
+
+ my_system sys(0);
+ thrust::binary_search(sys,
+ vec.begin(),
+ vec.end(),
+ vec.begin(),
+ vec.end(),
+ vec.begin());
+
+ ASSERT_EQ(true, sys.is_valid());
+}
+
+template<typename ForwardIterator, typename InputIterator, typename OutputIterator>
+OutputIterator binary_search(my_tag, ForwardIterator,ForwardIterator,InputIterator,InputIterator,OutputIterator output)
+{
+ *output = 13;
+ return output;
+}
+
+TEST(BinarySearchVectorTests, TestVectorBinarySearchDispatchImplicit)
+{
+ thrust::device_vector<int> vec(1);
+
+ thrust::binary_search(thrust::retag<my_tag>(vec.begin()),
+ thrust::retag<my_tag>(vec.end()),
+ thrust::retag<my_tag>(vec.begin()),
+ thrust::retag<my_tag>(vec.end()),
+ thrust::retag<my_tag>(vec.begin()));
+
+ ASSERT_EQ(13, vec.front());
+}
+
+TYPED_TEST(BinarySearchVectorIntegerTests, TestVectorLowerBound)
+{
+ using T = typename TestFixture::input_type;
+ for (auto size : get_sizes())
+ {
+ SCOPED_TRACE(testing::Message() << "with size = " << size);
+
+ thrust::host_vector<T> h_vec = get_random_data<T>(size,
+ std::numeric_limits<T>::min(),
+ std::numeric_limits<T>::max());
+ thrust::sort(h_vec.begin(), h_vec.end());
+ thrust::device_vector<T> d_vec = h_vec;
+
+ thrust::host_vector<T> h_input = get_random_data<T>(2*size,
+ std::numeric_limits<T>::min(),
+ std::numeric_limits<T>::max());
+ thrust::device_vector<T> d_input = h_input;
+
+ thrust::host_vector<int> h_output(2*size);
+ thrust::device_vector<int> d_output(2*size);
+
+ thrust::lower_bound(h_vec.begin(), h_vec.end(), h_input.begin(), h_input.end(), h_output.begin());
+ thrust::lower_bound(d_vec.begin(), d_vec.end(), d_input.begin(), d_input.end(), d_output.begin());
+
+ ASSERT_EQ(h_output, d_output);
+ }
+}
+
+TYPED_TEST(BinarySearchVectorIntegerTests, TestVectorUpperBound)
+{
+ using T = typename TestFixture::input_type;
+ for (auto size : get_sizes())
+ {
+ SCOPED_TRACE(testing::Message() << "with size = " << size);
+
+ thrust::host_vector<T> h_vec = get_random_data<T>(size,
+ std::numeric_limits<T>::min(),
+ std::numeric_limits<T>::max());
+ thrust::sort(h_vec.begin(), h_vec.end());
+ thrust::device_vector<T> d_vec = h_vec;
+
+ thrust::host_vector<T> h_input = get_random_data<T>(2*size,
+ std::numeric_limits<T>::min(),
+ std::numeric_limits<T>::max());
+ thrust::device_vector<T> d_input = h_input;
+
+ thrust::host_vector<int> h_output(2*size);
+ thrust::device_vector<int> d_output(2*size);
+
+ thrust::upper_bound(h_vec.begin(), h_vec.end(), h_input.begin(), h_input.end(), h_output.begin());
+ thrust::upper_bound(d_vec.begin(), d_vec.end(), d_input.begin(), d_input.end(), d_output.begin());
+
+ ASSERT_EQ(h_output, d_output);
+ }
+}
+
+TYPED_TEST(BinarySearchVectorIntegerTests, TestVectorBinarySearch)
+{
+ using T = typename TestFixture::input_type;
+ for (auto size : get_sizes())
+ {
+ SCOPED_TRACE(testing::Message() << "with size = " << size);
+
+ thrust::host_vector<T> h_vec = get_random_data<T>(size,
+ std::numeric_limits<T>::min(),
+ std::numeric_limits<T>::max());
+ thrust::sort(h_vec.begin(), h_vec.end());
+ thrust::device_vector<T> d_vec = h_vec;
+
+ thrust::host_vector<T> h_input = get_random_data<T>(2*size,
+ std::numeric_limits<T>::min(),
+ std::numeric_limits<T>::max());
+ thrust::device_vector<T> d_input = h_input;
+
+ thrust::host_vector<int> h_output(2*size);
+ thrust::device_vector<int> d_output(2*size);
+
+ thrust::binary_search(h_vec.begin(), h_vec.end(), h_input.begin(), h_input.end(), h_output.begin());
+ thrust::binary_search(d_vec.begin(), d_vec.end(), d_input.begin(), d_input.end(), d_output.begin());
+
+ ASSERT_EQ(h_output, d_output);
+ }
+}
+
+TYPED_TEST(BinarySearchVectorIntegerTests, TestVectorLowerBoundDiscardIterator)
+{
+ using T = typename TestFixture::input_type;
+ for (auto size : get_sizes())
+ {
+ SCOPED_TRACE(testing::Message() << "with size = " << size);
+
+ thrust::host_vector<T> h_vec = get_random_data<T>(size,
+ std::numeric_limits<T>::min(),
+ std::numeric_limits<T>::max());
+ thrust::sort(h_vec.begin(), h_vec.end());
+ thrust::device_vector<T> d_vec = h_vec;
+
+ thrust::host_vector<T> h_input = get_random_data<T>(2*size,
+ std::numeric_limits<T>::min(),
+ std::numeric_limits<T>::max());
+ thrust::device_vector<T> d_input = h_input;
+
+ thrust::discard_iterator<> h_result =
+ thrust::lower_bound(h_vec.begin(), h_vec.end(), h_input.begin(), h_input.end(), thrust::make_discard_iterator());
+ thrust::discard_iterator<> d_result =
+ thrust::lower_bound(d_vec.begin(), d_vec.end(), d_input.begin(), d_input.end(), thrust::make_discard_iterator());
+
+ thrust::discard_iterator<> reference(2*size);
+
+ ASSERT_EQ_QUIET(reference, h_result);
+ ASSERT_EQ_QUIET(reference, d_result);
+ }
+}
+
+TYPED_TEST(BinarySearchVectorIntegerTests, TestVectorUpperBoundDiscardIterator)
+{
+ using T = typename TestFixture::input_type;
+ for (auto size : get_sizes())
+ {
+ SCOPED_TRACE(testing::Message() << "with size = " << size);
+
+ thrust::host_vector<T> h_vec = get_random_data<T>(size,
+ std::numeric_limits<T>::min(),
+ std::numeric_limits<T>::max());
+ thrust::sort(h_vec.begin(), h_vec.end());
+ thrust::device_vector<T> d_vec = h_vec;
+
+ thrust::host_vector<T> h_input = get_random_data<T>(2*size,
+ std::numeric_limits<T>::min(),
+ std::numeric_limits<T>::max());
+ thrust::device_vector<T> d_input = h_input;
+
+ thrust::discard_iterator<> h_result =
+ thrust::upper_bound(h_vec.begin(), h_vec.end(), h_input.begin(), h_input.end(), thrust::make_discard_iterator());
+ thrust::discard_iterator<> d_result =
+ thrust::upper_bound(d_vec.begin(), d_vec.end(), d_input.begin(), d_input.end(), thrust::make_discard_iterator());
+
+ thrust::discard_iterator<> reference(2*size);
+
+ ASSERT_EQ_QUIET(reference, h_result);
+ ASSERT_EQ_QUIET(reference, d_result);
+ }
+}
+
+TYPED_TEST(BinarySearchVectorIntegerTests, TestVectorBinarySearchDiscardIterator)
+{
+ using T = typename TestFixture::input_type;
+ for (auto size : get_sizes())
+ {
+ SCOPED_TRACE(testing::Message() << "with size = " << size);
+
+ thrust::host_vector<T> h_vec = get_random_data<T>(size,
+ std::numeric_limits<T>::min(),
+ std::numeric_limits<T>::max());
+ thrust::sort(h_vec.begin(), h_vec.end());
+ thrust::device_vector<T> d_vec = h_vec;
+
+ thrust::host_vector<T> h_input = get_random_data<T>(2*size,
+ std::numeric_limits<T>::min(),
+ std::numeric_limits<T>::max());
+ thrust::device_vector<T> d_input = h_input;
+
+ thrust::discard_iterator<> h_result =
+ thrust::binary_search(h_vec.begin(), h_vec.end(), h_input.begin(), h_input.end(), thrust::make_discard_iterator());
+ thrust::discard_iterator<> d_result =
+ thrust::binary_search(d_vec.begin(), d_vec.end(), d_input.begin(), d_input.end(), thrust::make_discard_iterator());
+
+ thrust::discard_iterator<> reference(2*size);
+
+ ASSERT_EQ_QUIET(reference, h_result);
+ ASSERT_EQ_QUIET(reference, d_result);
+ }
+}

MODIFY
test/test_counting_iterator.cpp
test/test_counting_iterator.cpp
// Thrust
#include <thrust/iterator/counting_iterator.h>
#include <thrust/sort.h>
-// TODO: implement binary search
-//#include <thrust/binary_search.h>
+#include <thrust/binary_search.h>
#include <thrust/distance.h>
#include <thrust/detail/cstdint.h>
@@ -208,8 +207,7 @@ TEST(CountingIteratorTests, TestCountingIteratorUnsignedType)
ASSERT_EQ(iter1 < iter0, false);
}
-// TODO: implement binary search
-/*TEST(CountingIteratorTests, TestCountingIteratorLowerBound)
+TEST(CountingIteratorTests, TestCountingIteratorLowerBound)
{
size_t n = 10000;
const size_t M = 100;
@@ -235,7 +233,7 @@ TEST(CountingIteratorTests, TestCountingIteratorUnsignedType)
thrust::lower_bound(d_data.begin(), d_data.end(), search_begin, search_end, d_result.begin());
ASSERT_EQ(h_result, d_result);
-}*/
+}
TEST(CountingIteratorTests, TestCountingIteratorDifference)
{

MODIFY
thrust/system/hip/detail/binary_search.h
thrust/system/hip/detail/binary_search.h
@@ -40,7 +40,7 @@ template <class Policy,
class NeedlesIt,
class OutputIt,
class CompareOp>
-OutputIt __host__
+OutputIt THRUST_HIP_RUNTIME_FUNCTION
lower_bound(Policy& policy,
HaystackIt haystack_begin,
HaystackIt haystack_end,
@@ -104,7 +104,7 @@ template <class Policy,
class NeedlesIt,
class OutputIt,
class CompareOp>
-OutputIt __host__
+OutputIt THRUST_HIP_RUNTIME_FUNCTION
upper_bound(Policy& policy,
HaystackIt haystack_begin,
HaystackIt haystack_end,
@@ -168,7 +168,7 @@ template <class Policy,
class NeedlesIt,
class OutputIt,
class CompareOp>
-OutputIt __host__
+OutputIt THRUST_HIP_RUNTIME_FUNCTION
binary_search(Policy& policy,
HaystackIt haystack_begin,
HaystackIt haystack_end,
@@ -238,7 +238,7 @@ template <class Derived,
class NeedlesIt,
class OutputIt,
class CompareOp>
-OutputIt __host__ __device__
+OutputIt THRUST_HIP_FUNCTION
lower_bound(execution_policy<Derived>& policy,
HaystackIt first,
HaystackIt last,
@@ -275,7 +275,7 @@ template <class Derived,
class HaystackIt,
class NeedlesIt,
class OutputIt>
-OutputIt __host__ __device__
+OutputIt THRUST_HIP_FUNCTION
lower_bound(execution_policy<Derived>& policy,
HaystackIt first,
HaystackIt last,
@@ -297,7 +297,7 @@ template <class Derived,
class NeedlesIt,
class OutputIt,
class CompareOp>
-OutputIt __host__ __device__
+OutputIt THRUST_HIP_FUNCTION
upper_bound(execution_policy<Derived>& policy,
HaystackIt first,
HaystackIt last,
@@ -334,7 +334,7 @@ template <class Derived,
class HaystackIt,
class NeedlesIt,
class OutputIt>
-OutputIt __host__ __device__
+OutputIt THRUST_HIP_FUNCTION
upper_bound(execution_policy<Derived>& policy,
HaystackIt first,
HaystackIt last,
@@ -356,7 +356,7 @@ template <class Derived,
class NeedlesIt,
class OutputIt,
class CompareOp>
-OutputIt __host__ __device__
+OutputIt THRUST_HIP_FUNCTION
binary_search(execution_policy<Derived>& policy,
HaystackIt first,
HaystackIt last,
@@ -393,7 +393,7 @@ template <class Derived,
class HaystackIt,
class NeedlesIt,
class OutputIt>
-OutputIt __host__ __device__
+OutputIt THRUST_HIP_FUNCTION
binary_search(execution_policy<Derived>& policy,
HaystackIt first,
HaystackIt last,

MODIFY
thrust/system/hip/detail/util.h
thrust/system/hip/detail/util.h
@@ -45,7 +45,12 @@ template <class Policy>
__host__ __device__ hipError_t
synchronize(Policy &policy)
{
+#if __THRUST_HAS_HIPRT__
return synchronize_stream(derived_cast(policy));
+#else
+ THRUST_UNUSED_VAR(policy);
+ return hipSuccess;
+#endif
}
template <class Derived>

Fixed the binary search and added tests