21 #ifndef ROCPRIM_DEVICE_DETAIL_DEVICE_BINARY_SEARCH_HPP_ 22 #define ROCPRIM_DEVICE_DETAIL_DEVICE_BINARY_SEARCH_HPP_ 24 BEGIN_ROCPRIM_NAMESPACE
30 ROCPRIM_DEVICE ROCPRIM_INLINE
31 Size get_binary_search_middle(Size left, Size right)
33 const Size d = right - left;
34 return left + d / 2 + d / 64;
37 template<
class RandomAccessIterator,
class Size,
class T,
class BinaryPredicate>
38 ROCPRIM_DEVICE ROCPRIM_INLINE
39 Size lower_bound_n(RandomAccessIterator first,
42 BinaryPredicate compare_op)
48 const Size mid = get_binary_search_middle(left, right);
49 if(compare_op(first[mid], value))
61 template<
class RandomAccessIterator,
class Size,
class T,
class BinaryPredicate>
62 ROCPRIM_DEVICE ROCPRIM_INLINE
63 Size upper_bound_n(RandomAccessIterator first,
66 BinaryPredicate compare_op)
72 const Size mid = get_binary_search_middle(left, right);
73 if(compare_op(value, first[mid]))
87 template<
class HaystackIterator,
class CompareOp,
class Size,
class T>
88 ROCPRIM_DEVICE ROCPRIM_INLINE
89 Size operator()(HaystackIterator haystack, Size size,
const T& value, CompareOp compare_op)
const 91 return lower_bound_n(haystack, size, value, compare_op);
97 template<
class HaystackIterator,
class CompareOp,
class Size,
class T>
98 ROCPRIM_DEVICE ROCPRIM_INLINE
99 Size operator()(HaystackIterator haystack, Size size,
const T& value, CompareOp compare_op)
const 101 return upper_bound_n(haystack, size, value, compare_op);
107 template<
class HaystackIterator,
class CompareOp,
class Size,
class T>
108 ROCPRIM_DEVICE ROCPRIM_INLINE
109 bool operator()(HaystackIterator haystack, Size size,
const T& value, CompareOp compare_op)
const 111 const Size n = lower_bound_n(haystack, size, value, compare_op);
112 return n != size && !compare_op(value, haystack[n]);
118 END_ROCPRIM_NAMESPACE
120 #endif // ROCPRIM_DEVICE_DETAIL_DEVICE_BINARY_SEARCH_HPP_ Definition: device_binary_search.hpp:105
Definition: device_binary_search.hpp:85
Definition: device_binary_search.hpp:95
Deprecated: Configuration of device-level scan primitives.
Definition: block_histogram.hpp:62