#include #include #include #include #include #include #include ////////////////////// // Vector Functions // ////////////////////// // convert xxx_vector to xxx_vector template struct vector_like { typedef typename ExampleVector::allocator_type alloc; typedef typename thrust::detail::allocator_traits alloc_traits; typedef typename alloc_traits::template rebind_alloc new_alloc; typedef thrust::detail::vector_base type; }; template void TestVectorLowerBoundSimple(void) { 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::difference_type int_type; typedef typename vector_like::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_EQUAL((output_end - integral_output.begin()), 10); ASSERT_EQUAL(integral_output[0], 0); ASSERT_EQUAL(integral_output[1], 1); ASSERT_EQUAL(integral_output[2], 1); ASSERT_EQUAL(integral_output[3], 2); ASSERT_EQUAL(integral_output[4], 2); ASSERT_EQUAL(integral_output[5], 2); ASSERT_EQUAL(integral_output[6], 3); ASSERT_EQUAL(integral_output[7], 3); ASSERT_EQUAL(integral_output[8], 4); ASSERT_EQUAL(integral_output[9], 5); // // test with interator output type // typedef typename vector_like::type IteratorVector; // IteratorVector iterator_output(10); // thrust::lower_bound(vec.begin(), vec.end(), input.begin(), input.end(), iterator_output.begin()); // // ASSERT_EQUAL(iterator_output[0] - vec.begin(), 0); // ASSERT_EQUAL(iterator_output[1] - vec.begin(), 1); // ASSERT_EQUAL(iterator_output[2] - vec.begin(), 1); // ASSERT_EQUAL(iterator_output[3] - vec.begin(), 2); // ASSERT_EQUAL(iterator_output[4] - vec.begin(), 2); // ASSERT_EQUAL(iterator_output[5] - vec.begin(), 2); // ASSERT_EQUAL(iterator_output[6] - vec.begin(), 3); // ASSERT_EQUAL(iterator_output[7] - vec.begin(), 3); // ASSERT_EQUAL(iterator_output[8] - vec.begin(), 4); // ASSERT_EQUAL(iterator_output[9] - vec.begin(), 5); } DECLARE_VECTOR_UNITTEST(TestVectorLowerBoundSimple); template OutputIterator lower_bound(my_system &system, ForwardIterator,ForwardIterator,InputIterator,InputIterator,OutputIterator output) { system.validate_dispatch(); return output; } void TestVectorLowerBoundDispatchExplicit() { thrust::device_vector vec(1); my_system sys(0); thrust::lower_bound(sys, vec.begin(), vec.end(), vec.begin(), vec.end(), vec.begin()); ASSERT_EQUAL(true, sys.is_valid()); } DECLARE_UNITTEST(TestVectorLowerBoundDispatchExplicit); template OutputIterator lower_bound(my_tag, ForwardIterator,ForwardIterator,InputIterator,InputIterator,OutputIterator output) { *output = 13; return output; } void TestVectorLowerBoundDispatchImplicit() { thrust::device_vector vec(1); thrust::lower_bound(thrust::retag(vec.begin()), thrust::retag(vec.end()), thrust::retag(vec.begin()), thrust::retag(vec.end()), thrust::retag(vec.begin())); ASSERT_EQUAL(13, vec.front()); } DECLARE_UNITTEST(TestVectorLowerBoundDispatchImplicit); template void TestVectorUpperBoundSimple(void) { 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::difference_type int_type; typedef typename vector_like::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_EQUAL((output_end - integral_output.begin()), 10); ASSERT_EQUAL(integral_output[0], 1); ASSERT_EQUAL(integral_output[1], 1); ASSERT_EQUAL(integral_output[2], 2); ASSERT_EQUAL(integral_output[3], 2); ASSERT_EQUAL(integral_output[4], 2); ASSERT_EQUAL(integral_output[5], 3); ASSERT_EQUAL(integral_output[6], 3); ASSERT_EQUAL(integral_output[7], 4); ASSERT_EQUAL(integral_output[8], 5); ASSERT_EQUAL(integral_output[9], 5); // // test with interator output type // typedef typename vector_like::type IteratorVector; // IteratorVector iterator_output(10); // thrust::lower_bound(vec.begin(), vec.end(), input.begin(), input.end(), iterator_output.begin()); // // ASSERT_EQUAL(iterator_output[0] - vec.begin(), 1); // ASSERT_EQUAL(iterator_output[1] - vec.begin(), 1); // ASSERT_EQUAL(iterator_output[2] - vec.begin(), 2); // ASSERT_EQUAL(iterator_output[3] - vec.begin(), 2); // ASSERT_EQUAL(iterator_output[4] - vec.begin(), 2); // ASSERT_EQUAL(iterator_output[5] - vec.begin(), 3); // ASSERT_EQUAL(iterator_output[6] - vec.begin(), 3); // ASSERT_EQUAL(iterator_output[7] - vec.begin(), 4); // ASSERT_EQUAL(iterator_output[8] - vec.begin(), 5); // ASSERT_EQUAL(iterator_output[9] - vec.begin(), 5); } DECLARE_VECTOR_UNITTEST(TestVectorUpperBoundSimple); template OutputIterator upper_bound(my_system &system, ForwardIterator,ForwardIterator,InputIterator,InputIterator,OutputIterator output) { system.validate_dispatch(); return output; } void TestVectorUpperBoundDispatchExplicit() { thrust::device_vector vec(1); my_system sys(0); thrust::upper_bound(sys, vec.begin(), vec.end(), vec.begin(), vec.end(), vec.begin()); ASSERT_EQUAL(true, sys.is_valid()); } DECLARE_UNITTEST(TestVectorUpperBoundDispatchExplicit); template OutputIterator upper_bound(my_tag, ForwardIterator,ForwardIterator,InputIterator,InputIterator,OutputIterator output) { *output = 13; return output; } void TestVectorUpperBoundDispatchImplicit() { thrust::device_vector vec(1); thrust::upper_bound(thrust::retag(vec.begin()), thrust::retag(vec.end()), thrust::retag(vec.begin()), thrust::retag(vec.end()), thrust::retag(vec.begin())); ASSERT_EQUAL(13, vec.front()); } DECLARE_UNITTEST(TestVectorUpperBoundDispatchImplicit); template void TestVectorBinarySearchSimple(void) { 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::type BoolVector; typedef typename Vector::difference_type int_type; typedef typename vector_like::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_EQUAL((bool_output_end - bool_output.begin()), 10); ASSERT_EQUAL(bool_output[0], true); ASSERT_EQUAL(bool_output[1], false); ASSERT_EQUAL(bool_output[2], true); ASSERT_EQUAL(bool_output[3], false); ASSERT_EQUAL(bool_output[4], false); ASSERT_EQUAL(bool_output[5], true); ASSERT_EQUAL(bool_output[6], false); ASSERT_EQUAL(bool_output[7], true); ASSERT_EQUAL(bool_output[8], true); ASSERT_EQUAL(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_EQUAL((int_output_end - integral_output.begin()), 10); ASSERT_EQUAL(integral_output[0], 1); ASSERT_EQUAL(integral_output[1], 0); ASSERT_EQUAL(integral_output[2], 1); ASSERT_EQUAL(integral_output[3], 0); ASSERT_EQUAL(integral_output[4], 0); ASSERT_EQUAL(integral_output[5], 1); ASSERT_EQUAL(integral_output[6], 0); ASSERT_EQUAL(integral_output[7], 1); ASSERT_EQUAL(integral_output[8], 1); ASSERT_EQUAL(integral_output[9], 0); } DECLARE_VECTOR_UNITTEST(TestVectorBinarySearchSimple); template OutputIterator binary_search(my_system &system, ForwardIterator,ForwardIterator,InputIterator,InputIterator,OutputIterator output) { system.validate_dispatch(); return output; } void TestVectorBinarySearchDispatchExplicit() { thrust::device_vector vec(1); my_system sys(0); thrust::binary_search(sys, vec.begin(), vec.end(), vec.begin(), vec.end(), vec.begin()); ASSERT_EQUAL(true, sys.is_valid()); } DECLARE_UNITTEST(TestVectorBinarySearchDispatchExplicit); template OutputIterator binary_search(my_tag, ForwardIterator,ForwardIterator,InputIterator,InputIterator,OutputIterator output) { *output = 13; return output; } void TestVectorBinarySearchDispatchImplicit() { thrust::device_vector vec(1); thrust::binary_search(thrust::retag(vec.begin()), thrust::retag(vec.end()), thrust::retag(vec.begin()), thrust::retag(vec.end()), thrust::retag(vec.begin())); ASSERT_EQUAL(13, vec.front()); } DECLARE_UNITTEST(TestVectorBinarySearchDispatchImplicit); template struct TestVectorLowerBound { void operator()(const size_t n) { thrust::host_vector h_vec = unittest::random_integers(n); thrust::sort(h_vec.begin(), h_vec.end()); thrust::device_vector d_vec = h_vec; thrust::host_vector h_input = unittest::random_integers(2*n); thrust::device_vector d_input = h_input; typedef typename thrust::host_vector::difference_type int_type; thrust::host_vector h_output(2*n); thrust::device_vector d_output(2*n); 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_EQUAL(h_output, d_output); } }; VariableUnitTest TestVectorLowerBoundInstance; template struct TestVectorUpperBound { void operator()(const size_t n) { thrust::host_vector h_vec = unittest::random_integers(n); thrust::sort(h_vec.begin(), h_vec.end()); thrust::device_vector d_vec = h_vec; thrust::host_vector h_input = unittest::random_integers(2*n); thrust::device_vector d_input = h_input; typedef typename thrust::host_vector::difference_type int_type; thrust::host_vector h_output(2*n); thrust::device_vector d_output(2*n); 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_EQUAL(h_output, d_output); } }; VariableUnitTest TestVectorUpperBoundInstance; template struct TestVectorBinarySearch { void operator()(const size_t n) { thrust::host_vector h_vec = unittest::random_integers(n); thrust::sort(h_vec.begin(), h_vec.end()); thrust::device_vector d_vec = h_vec; thrust::host_vector h_input = unittest::random_integers(2*n); thrust::device_vector d_input = h_input; typedef typename thrust::host_vector::difference_type int_type; thrust::host_vector h_output(2*n); thrust::device_vector d_output(2*n); 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_EQUAL(h_output, d_output); } }; VariableUnitTest TestVectorBinarySearchInstance; template struct TestVectorLowerBoundDiscardIterator { void operator()(const size_t n) { thrust::host_vector h_vec = unittest::random_integers(n); thrust::sort(h_vec.begin(), h_vec.end()); thrust::device_vector d_vec = h_vec; thrust::host_vector h_input = unittest::random_integers(2*n); thrust::device_vector 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*n); ASSERT_EQUAL_QUIET(reference, h_result); ASSERT_EQUAL_QUIET(reference, d_result); } }; VariableUnitTest TestVectorLowerBoundDiscardIteratorInstance; template struct TestVectorUpperBoundDiscardIterator { void operator()(const size_t n) { thrust::host_vector h_vec = unittest::random_integers(n); thrust::sort(h_vec.begin(), h_vec.end()); thrust::device_vector d_vec = h_vec; thrust::host_vector h_input = unittest::random_integers(2*n); thrust::device_vector 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*n); ASSERT_EQUAL_QUIET(reference, h_result); ASSERT_EQUAL_QUIET(reference, d_result); } }; VariableUnitTest TestVectorUpperBoundDiscardIteratorInstance; template struct TestVectorBinarySearchDiscardIterator { void operator()(const size_t n) { thrust::host_vector h_vec = unittest::random_integers(n); thrust::sort(h_vec.begin(), h_vec.end()); thrust::device_vector d_vec = h_vec; thrust::host_vector h_input = unittest::random_integers(2*n); thrust::device_vector 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*n); ASSERT_EQUAL_QUIET(reference, h_result); ASSERT_EQUAL_QUIET(reference, d_result); } }; VariableUnitTest TestVectorBinarySearchDiscardIteratorInstance;