diff --git a/libcxx/benchmarks/ranges_algorithms.bench.cpp b/libcxx/benchmarks/ranges_algorithms.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/ranges_algorithms.bench.cpp @@ -0,0 +1,38 @@ +#include +#include +#include +#include + +#include "benchmark/benchmark.h" + +namespace { + constexpr std::size_t size = 1'000'000'000; + std::vector const ints = []{ + auto ints = std::vector(size); + std::iota(ints.begin(), ints.end(), 0); + return ints; + }(); + int const sample = []{ + auto generator = std::mt19937_64(std::random_device()()); + auto distribution = std::uniform_int_distribution(0, static_cast(size)); + return distribution(generator); + }(); + + void std_lower_bound(benchmark::State& state) { + for (auto _ : state) { + auto result = std::lower_bound(ints.begin(), ints.end(), sample); + benchmark::DoNotOptimize(result); + } + } + + void ranges_lower_bound(benchmark::State& state) { + for (auto _ : state) { + auto result = std::lower_bound(ints.begin(), ints.end(), sample); + benchmark::DoNotOptimize(result); + } + } +} + +BENCHMARK(std_lower_bound); +BENCHMARK(ranges_lower_bound); +BENCHMARK_MAIN(); diff --git a/libcxx/include/__algorithm/lower_bound.h b/libcxx/include/__algorithm/lower_bound.h --- a/libcxx/include/__algorithm/lower_bound.h +++ b/libcxx/include/__algorithm/lower_bound.h @@ -9,10 +9,27 @@ #ifndef _LIBCPP___ALGORITHM_LOWER_BOUND_H #define _LIBCPP___ALGORITHM_LOWER_BOUND_H -#include <__config> #include <__algorithm/comp.h> #include <__algorithm/half_positive.h> -#include +#include <__algorithm/is_partitioned.h> +#include <__algorithm/partition_point.h> +#include <__config> +#include <__debug> +#include <__function_like.h> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/reference_wrapper.h> +#include <__functional/ranges_operations.h> +#include <__iterator/advance.h> +#include <__iterator/distance.h> +#include <__iterator/iterator_traits.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.h> +#include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header @@ -65,6 +82,42 @@ __less::value_type, _Tp>()); } +#if !defined(_LIBCPP_HAS_NO_RANGES) + +namespace ranges { + struct __lower_bound_fn final : __function_like { + constexpr explicit __lower_bound_fn(__tag __x) noexcept : __function_like(__x) {} + + template _Sp, class _Tp, class _Proj = identity, + indirect_strict_weak_order> _Comp = ranges::less> + _LIBCPP_NODISCARD_EXT constexpr + _Ip operator()(_Ip __first, _Sp __last, const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const { + auto __pred = [&__value, &__comp](const auto& __proj_elem){ + return _VSTD::invoke(__comp, __proj_elem, __value); + }; + // This assertion breaks the logarithmic complexity requirement, but since it is only evaluated + // when a user opts into a debug level, the non-conformance is deemed acceptable, since it is + // useful for catching violated precondition bugs. + _LIBCPP_ASSERT(ranges::is_partitioned(__first, __last, _VSTD::ref(__pred), _VSTD::ref(__proj)), + "lower_bound precondition:\n" + "\tthe projected elements of the range [`first`, `last`) are partitioned with respect to " + "`comp(*proj_elem, value)`."); + return ranges::partition_point(_VSTD::move(__first), _VSTD::move(__last), _VSTD::move(__pred), _VSTD::ref(__proj)); + } + + template, _Proj>> _Comp = ranges::less> + _LIBCPP_NODISCARD_EXT constexpr + borrowed_iterator_t<_Rp> operator()(_Rp&& __r, const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const { + return (*this)(ranges::begin(__r), ranges::end(__r), __value, _VSTD::ref(__comp), _VSTD::ref(__proj)); + } + }; + + inline constexpr auto lower_bound = __lower_bound_fn(__function_like::__tag()); +} // namespace ranges + +#endif // !defined(_LIBCPP_HAS_NO_RANGES) + _LIBCPP_END_NAMESPACE_STD _LIBCPP_POP_MACROS diff --git a/libcxx/include/__algorithm/upper_bound.h b/libcxx/include/__algorithm/upper_bound.h --- a/libcxx/include/__algorithm/upper_bound.h +++ b/libcxx/include/__algorithm/upper_bound.h @@ -9,10 +9,27 @@ #ifndef _LIBCPP___ALGORITHM_UPPER_BOUND_H #define _LIBCPP___ALGORITHM_UPPER_BOUND_H -#include <__config> #include <__algorithm/comp.h> #include <__algorithm/half_positive.h> -#include +#include <__algorithm/is_partitioned.h> +#include <__algorithm/partition_point.h> +#include <__config> +#include <__debug> +#include <__function_like.h> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/reference_wrapper.h> +#include <__functional/ranges_operations.h> +#include <__iterator/advance.h> +#include <__iterator/distance.h> +#include <__iterator/iterator_traits.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.h> +#include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header @@ -65,6 +82,42 @@ __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>()); } +#if !defined(_LIBCPP_HAS_NO_RANGES) + +namespace ranges { + struct __upper_bound_fn final : __function_like { + constexpr explicit __upper_bound_fn(__tag __x) noexcept : __function_like(__x) {} + + template _Sp, class _Tp, class _Proj = identity, + indirect_strict_weak_order> _Comp = ranges::less> + _LIBCPP_NODISCARD_EXT constexpr + _Ip operator()(_Ip __first, _Sp __last, const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const { + auto __pred = [&__value, &__comp](const auto& __proj_elem){ + return !_VSTD::invoke(__comp, __value, __proj_elem); + }; + // This assertion breaks the logarithmic complexity requirement, but since it is only evaluated + // when a user opts into a debug level, the non-conformance is deemed acceptable, since it is + // useful for catching violated precondition bugs. + _LIBCPP_ASSERT(ranges::is_partitioned(__first, __last, _VSTD::ref(__pred), _VSTD::ref(__proj)), + "upper_bound precondition:\n" + "\tthe projected elements of the range [`first`, `last`) are partitioned with respect to " + "`not comp(value, *proj_elem)`."); + return ranges::partition_point(_VSTD::move(__first), _VSTD::move(__last), _VSTD::move(__pred), _VSTD::ref(__proj)); + } + + template, _Proj>> _Comp = ranges::less> + _LIBCPP_NODISCARD_EXT constexpr + borrowed_iterator_t<_Rp> operator()(_Rp&& __r, const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const { + return (*this)(ranges::begin(__r), ranges::end(__r), __value, _VSTD::ref(__comp), _VSTD::ref(__proj)); + } + }; + + inline constexpr auto upper_bound = __upper_bound_fn(__function_like::__tag()); +} // namespace ranges + +#endif // !defined(_LIBCPP_HAS_NO_RANGES) + _LIBCPP_END_NAMESPACE_STD _LIBCPP_POP_MACROS diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -467,6 +467,17 @@ constexpr ForwardIterator // constexpr in C++20 lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); +template S, class T, class Proj = identity, + indirect_strict_weak_order> Comp = ranges::less> + constexpr I ranges::lower_bound(I first, S last, const T& value, Comp comp = {}, + Proj proj = {}); // since C++20 + +template, Proj>> Comp = + ranges::less> + constexpr borrowed_iterator_t + ranges::lower_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {}); // since C++20 + template constexpr ForwardIterator // constexpr in C++20 upper_bound(ForwardIterator first, ForwardIterator last, const T& value); @@ -475,6 +486,16 @@ constexpr ForwardIterator // constexpr in C++20 upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); +template S, class T, class Proj = identity, + indirect_strict_weak_order> Comp = ranges::less> + constexpr I ranges::upper_bound(I first, S last, const T& value, Comp comp = {}, Proj proj = {}); // since C++20 + +template, Proj>> Comp = + ranges::less> + constexpr borrowed_iterator_t + ranges::upper_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {}); // since C++20 + template constexpr pair // constexpr in C++20 equal_range(ForwardIterator first, ForwardIterator last, const T& value); diff --git a/libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.pass.cpp b/libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.pass.cpp --- a/libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.pass.cpp +++ b/libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.pass.cpp @@ -54,5 +54,11 @@ ranges::partition_point(ranges::begin(arr), ranges::end(arr), [](auto) { return true; }); ranges::partition_point(arr, [](auto) { return true; }); + ranges::lower_bound(arr.begin(), arr.end(), 0); + ranges::lower_bound(arr, 0); + + ranges::upper_bound(arr.begin(), arr.end(), 0); + ranges::upper_bound(arr, 0); + return 0; } diff --git a/libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.verify.cpp b/libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.verify.cpp --- a/libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.verify.cpp +++ b/libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.verify.cpp @@ -77,4 +77,16 @@ // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}} ranges::partition_point(arr, [](auto) { return true; }); + + // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}} + ranges::lower_bound(arr.begin(), arr.end(), 0); + + // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}} + ranges::lower_bound(arr, 0); + + // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}} + ranges::upper_bound(arr.begin(), arr.end(), 0); + + // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}} + ranges::upper_bound(arr, 0); } diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/ranges_lower_bound/ranges_lower_bound.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/ranges_lower_bound/ranges_lower_bound.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/ranges_lower_bound/ranges_lower_bound.pass.cpp @@ -0,0 +1,198 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-no-concepts +// UNSUPPORTED: gcc-10 + +// ranges::lower_bound + +#include + +#include +#include +#include +#include +#include +#include + +#include "test_algorithm.h" +#include "test_iterators.h" +#include "test_macros.h" + +namespace ranges = std::ranges; + +template +constexpr void check_complexity(R&& r, std::ptrdiff_t const count) +{ + auto const complexity = static_cast(libcxx_log2(ranges::ssize(r))) + 1; + // We halve the complexity so that each test case can check both `alg(first, last)` and `alg(r)` + // in the same lambda. + assert((count / 2) <= complexity); +} + +template class I, class T> +constexpr bool check_lower_bound() { + + auto no_duplicates = std::array{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; + + auto successor = [](T const x) { return x + 1; }; + + test_algorithm(no_duplicates, [](auto& input) { + assert(ranges::lower_bound(input.begin(), input.end(), static_cast(0)) == input.begin()); + assert(ranges::lower_bound(input, static_cast(0)) == input.begin()); + }); + test_algorithm(no_duplicates, [](auto& input) { + auto iterator_result = ranges::lower_bound(input.begin(), input.end(), static_cast(5)); + assert(iterator_result == ranges::next(input.begin(), 5)); + assert(ranges::lower_bound(input, static_cast(5)) == iterator_result); + }); + test_algorithm(no_duplicates, [](auto& input) { + assert(ranges::lower_bound(input.begin(), input.end(), static_cast(-10)) == input.begin()); + assert(ranges::lower_bound(input, static_cast(-10)) == input.begin()); + }); + test_algorithm(no_duplicates, [](auto& input) { + assert(ranges::lower_bound(input.begin(), input.end(), static_cast(100)) == input.end()); + assert(ranges::lower_bound(input, static_cast(100)) == input.end()); + }); + test_algorithm(no_duplicates, ranges::greater(), [](auto& input, auto& comp) { + auto comp_ref = std::ref(comp); + assert(ranges::lower_bound(input.begin(), input.end(), static_cast(5), comp_ref) == input.begin()); + assert(ranges::lower_bound(input, static_cast(5), comp_ref) == input.begin()); + }); + test_algorithm(no_duplicates, ranges::greater(), [](auto& input, auto& comp) { + auto comp_ref = std::ref(comp); + assert(ranges::lower_bound(input.begin(), input.end(), static_cast(-5), comp_ref) == input.end()); + assert(ranges::lower_bound(input, static_cast(-5), comp_ref) == input.end()); + }); + test_algorithm(no_duplicates, ranges::less(), successor, [](auto& input, auto& comp, auto& proj) { + auto comp_ref = std::ref(comp); + auto proj_ref = std::ref(proj); + + auto iterator_result = ranges::lower_bound(input.begin(), input.end(), static_cast(2), comp_ref, proj_ref); + assert(iterator_result == ranges::next(input.begin(), 1)); + assert(ranges::lower_bound(input, static_cast(2), comp_ref, proj_ref) == iterator_result); + }); + test_algorithm(no_duplicates, ranges::greater(), std::negate(), [](auto& input, auto& comp, auto& proj) { + auto comp_ref = std::ref(comp); + auto proj_ref = std::ref(proj); + auto iterator_result = ranges::lower_bound(input.begin(), input.end(), static_cast(-5), comp_ref, proj_ref); + assert(iterator_result == ranges::next(input.begin(), 5)); + assert(ranges::lower_bound(input, static_cast(-5), comp_ref, proj_ref) == iterator_result); + }); + + // Check duplicates by arranging ints into equivalence classes. To further ensure the integrity of + // `lower_bound`, we'll shuffle two of the equivalence classes, so that they're not sorted. + // The final equivalence class is omitted so that we can add tests using the pre-defined `successor` + // projection. + auto mod4_equivalence_classes = std::array{0, 4, 8, 16, 73, 13, 22, 110, 70}; + + // Check that we really do have equivalence classes and that 2/3 of them aren't sorted. + assert(ranges::is_partitioned(mod4_equivalence_classes.begin(), mod4_equivalence_classes.end(), + [](int const x) { return x % 4 == 0; })); + assert(std::is_sorted(mod4_equivalence_classes.begin(), mod4_equivalence_classes.begin() + 4)); + + assert(ranges::is_partitioned(mod4_equivalence_classes.begin() + 4, mod4_equivalence_classes.end(), + [](int const x) { return x % 4 == 1; })); + assert(!std::is_sorted(mod4_equivalence_classes.begin() + 4, mod4_equivalence_classes.begin() + 6)); + + assert(ranges::is_partitioned(mod4_equivalence_classes.begin() + 6, mod4_equivalence_classes.end(), + [](int const x) { return x % 4 == 2; })); + assert(!std::is_sorted(mod4_equivalence_classes.begin() + 6, mod4_equivalence_classes.end())); + + auto strict_weak_order = [](auto const x, auto const y) { + return (static_cast(x) % 4) < (static_cast(y) % 4); + }; + + test_algorithm(mod4_equivalence_classes, strict_weak_order, [](auto& input, auto& comp) { + auto comp_ref = std::ref(comp); + assert(ranges::lower_bound(input.begin(), input.end(), static_cast(0), comp_ref) == input.begin()); + assert(ranges::lower_bound(input, static_cast(0), comp_ref) == input.begin()); + }); + test_algorithm(mod4_equivalence_classes, strict_weak_order, [](auto& input, auto& comp) { + auto comp_ref = std::ref(comp); + auto const iterator_result = ranges::lower_bound(input.begin(), input.end(), static_cast(1), comp_ref); + assert(iterator_result == ranges::next(input.begin(), 4)); + assert(ranges::lower_bound(input, static_cast(1), comp_ref) == iterator_result); + }); + test_algorithm(mod4_equivalence_classes, strict_weak_order, [](auto& input, auto& comp) { + auto comp_ref = std::ref(comp); + auto const iterator_result = ranges::lower_bound(input.begin(), input.end(), static_cast(2), comp_ref); + assert(iterator_result == ranges::next(input.begin(), 6)); + assert(ranges::lower_bound(input, static_cast(2), comp_ref) == iterator_result); + }); + test_algorithm(mod4_equivalence_classes, strict_weak_order, [](auto& input, auto& comp) { + auto comp_ref = std::ref(comp); + assert(ranges::lower_bound(input.begin(), input.end(), static_cast(3), comp_ref) == input.end()); + assert(ranges::lower_bound(input, static_cast(3), comp_ref) == input.end()); + }); + + test_algorithm(mod4_equivalence_classes, strict_weak_order, successor, [](auto& input, auto& comp, auto& proj) { + auto comp_ref = std::ref(comp); + auto proj_ref = std::ref(proj); + assert(ranges::lower_bound(input.begin(), input.end(), static_cast(0), comp_ref, proj_ref) == input.begin()); + assert(ranges::lower_bound(input, static_cast(0), comp_ref, proj_ref) == input.begin()); + }); + test_algorithm(mod4_equivalence_classes, strict_weak_order, successor, [](auto& input, auto& comp, auto& proj) { + auto comp_ref = std::ref(comp); + auto proj_ref = std::ref(proj); + + auto const iterator_result = ranges::lower_bound(input.begin(), input.end(), static_cast(1), comp_ref, proj_ref); + assert(iterator_result == input.begin()); + assert(ranges::lower_bound(input, static_cast(1), comp_ref, proj_ref) == iterator_result); + }); + test_algorithm(mod4_equivalence_classes, strict_weak_order, successor, [](auto& input, auto& comp, auto& proj) { + auto comp_ref = std::ref(comp); + auto proj_ref = std::ref(proj); + + auto const iterator_result = ranges::lower_bound(input.begin(), input.end(), static_cast(2), comp_ref, proj_ref); + assert(iterator_result == ranges::next(input.begin(), 4)); + assert(ranges::lower_bound(input, static_cast(2), comp_ref, proj_ref) == iterator_result); + }); + test_algorithm(mod4_equivalence_classes, strict_weak_order, successor, [](auto& input, auto& comp, auto& proj) { + auto comp_ref = std::ref(comp); + auto proj_ref = std::ref(proj); + + auto const iterator_result = ranges::lower_bound(input.begin(), input.end(), static_cast(3), comp_ref, proj_ref); + assert(iterator_result == ranges::next(input.begin(), 6)); + assert(ranges::lower_bound(input, static_cast(3), comp_ref, proj_ref) == iterator_result); + }); + + return true; +} + +int main(int, char**) { + static_assert(check_lower_bound()); + static_assert(check_lower_bound()); + check_lower_bound(); + check_lower_bound(); + + static_assert(check_lower_bound()); + static_assert(check_lower_bound()); + check_lower_bound(); + check_lower_bound(); + + static_assert(check_lower_bound()); + static_assert(check_lower_bound()); + check_lower_bound(); + check_lower_bound(); + + static_assert(check_lower_bound()); + static_assert(check_lower_bound()); + check_lower_bound(); + check_lower_bound(); + + ASSERT_SAME_TYPE(decltype(ranges::lower_bound(std::vector(10), 0)), + ranges::dangling); + ASSERT_SAME_TYPE(decltype(ranges::lower_bound(std::vector(10), 0, {})), + ranges::dangling); + ASSERT_SAME_TYPE(decltype(ranges::lower_bound(std::vector(10), 0, {}, {})), + ranges::dangling); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/ranges_lower_bound/special_function.compile.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/ranges_lower_bound/special_function.compile.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/ranges_lower_bound/special_function.compile.pass.cpp @@ -0,0 +1,112 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-no-concepts +// UNSUPPORTED: gcc-10 + +// ranges::lower_bound + +#include + +#include +#include +#include +#include + +#include "test_range.h" +#include "test_standard_function.h" + +static_assert(is_function_like()); + +namespace ranges = std::ranges; + +namespace std::ranges { + template + class basic_istream_view { + struct iterator; + public: + iterator begin(); + default_sentinel_t end() const; + }; +} // namespace std::ranges + +auto f = [](auto, auto) { return true; }; + +// The entities defined in the std::ranges namespace in this Clause are not found by argument-dependent +// name lookup ([basic.lookup.argdep]). When found by unqualified ([basic.lookup.unqual]) name lookup for +// the postfix-expression in a function call ([expr.call]), they inhibit argument-dependent name lookup. +template +constexpr bool no_unqualified_lookup() { + auto identity = ranges::basic_istream_view(); + static_assert(!requires(T const value) { lower_bound(ranges::begin(identity), ranges::end(identity), value, f); }); + static_assert(!requires(T const value) { lower_bound(ranges::begin(identity), ranges::end(identity), value, f, &T::first); }); + static_assert(!requires(T const value) { lower_bound(identity, value, f); }); + static_assert(!requires(T const value) { lower_bound(identity, value, f, &T::first); }); + return true; +}; + +static_assert(no_unqualified_lookup>()); + +namespace test { +template +struct iterator { + using value_type = std::pair; + using difference_type = std::ptrdiff_t; + using iterator_category = std::forward_iterator_tag; + + iterator() = default; + + value_type operator*() const; + iterator& operator++(); + iterator operator++(int); + + bool operator==(iterator const&) const = default; +}; + +template +struct range { + std::pair const* begin() const; + std::pair const* end() const; +}; + +template +void lower_bound(iterator, iterator, auto, auto) { + static_assert(std::same_as); +} + +template +void lower_bound(iterator, iterator, auto, auto, auto) { + static_assert(std::same_as); +} + +template +void lower_bound(R&&, auto, auto) { + static_assert(std::same_as); +} + +template +void lower_bound(R&&, auto, auto, auto) { + static_assert(std::same_as); +} +} // namespace test + +// When found by unqualified ([basic.lookup.unqual]) name lookup for the postfix-expression in a +// function call ([expr.call]), they inhibit argument-dependent name lookup. +void adl_inhibition() { + using std::ranges::lower_bound; + + test::iterator*> x; + std::pair value; + (void)lower_bound(x, x, value, f); + (void)lower_bound(x, x, value, f, &std::pair::first); + + test::range r; + (void)lower_bound(r, value, f); + (void)lower_bound(r, value, f, &std::pair::first); +} diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/upper.bound/ranges_upper_bound/ranges_upper_bound.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/upper.bound/ranges_upper_bound/ranges_upper_bound.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/upper.bound/ranges_upper_bound/ranges_upper_bound.pass.cpp @@ -0,0 +1,204 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-no-concepts +// UNSUPPORTED: gcc-10 + +// ranges::upper_bound + +#include + +#include +#include +#include +#include +#include +#include + +#include "test_algorithm.h" +#include "test_iterators.h" +#include "test_macros.h" + +namespace ranges = std::ranges; + +template +constexpr void check_complexity(R&& r, std::ptrdiff_t const count) +{ + auto const complexity = static_cast(libcxx_log2(ranges::ssize(r))) + 1; + // We halve the complexity so that each test case can check both `alg(first, last)` and `alg(r)` + // in the same lambda. + assert((count / 2) <= complexity); +} + +template class I, class T> +constexpr bool check_upper_bound() { + + auto no_duplicates = std::array{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; + + auto successor = [](T const x) { return x + 1; }; + + test_algorithm(no_duplicates, [](auto& input) { + assert(ranges::upper_bound(input.begin(), input.end(), static_cast(0)) == ranges::next(input.begin())); + assert(ranges::upper_bound(input, static_cast(0)) == ranges::next(input.begin())); + }); + test_algorithm(no_duplicates, [](auto& input) { + auto result = ranges::upper_bound(input.begin(), input.end(), static_cast(5)); + assert(result == ranges::next(input.begin(), 6)); + assert(ranges::upper_bound(input, static_cast(5)) == result); + }); + test_algorithm(no_duplicates, [](auto& input) { + assert(ranges::upper_bound(input.begin(), input.end(), static_cast(-10)) == input.begin()); + assert(ranges::upper_bound(input, static_cast(-10)) == input.begin()); + }); + test_algorithm(no_duplicates, [](auto& input) { + assert(ranges::upper_bound(input.begin(), input.end(), static_cast(100)) == input.end()); + assert(ranges::upper_bound(input, static_cast(100)) == input.end()); + }); + test_algorithm(no_duplicates, ranges::less(), successor, [](auto& input, auto& comp, auto& proj) { + auto comp_ref = std::ref(comp); + auto proj_ref = std::ref(proj); + + auto result = ranges::upper_bound(input.begin(), input.end(), static_cast(2), comp_ref, proj_ref); + assert(result == ranges::next(input.begin(), 2)); + assert(ranges::upper_bound(input, static_cast(2), comp_ref, proj_ref) == result); + }); + + auto no_duplicates_reversed = std::array{9, 8, 7, 6, 5, 4, 3, 2, 1, 0}; + + test_algorithm(no_duplicates_reversed, ranges::greater(), [](auto& input, auto& comp) { + auto comp_ref = std::ref(comp); + auto const result = ranges::upper_bound(input.begin(), input.end(), static_cast(5), comp_ref); + assert(result == ranges::next(input.begin(), 5)); + assert(ranges::upper_bound(input, static_cast(5), comp_ref) == result); + }); + test_algorithm(no_duplicates_reversed, ranges::greater(), [](auto& input, auto& comp) { + auto comp_ref = std::ref(comp); + assert(ranges::upper_bound(input.begin(), input.end(), static_cast(-5), comp_ref) == input.end()); + assert(ranges::upper_bound(input, static_cast(-5), comp_ref) == input.end()); + }); + test_algorithm(no_duplicates_reversed, ranges::greater(), std::negate(), [](auto& input, auto& comp, auto& proj) { + auto comp_ref = std::ref(comp); + auto proj_ref = std::ref(proj); + auto result = ranges::upper_bound(input.begin(), input.end(), static_cast(-5), comp_ref, proj_ref); + assert(result == input.end()); + assert(ranges::upper_bound(input, static_cast(-5), comp_ref, proj_ref) == result); + }); + + // Check duplicates by arranging ints into equivalence classes. To further ensure the integrity of + // `upper_bound`, we'll shuffle two of the equivalence classes, so that they're not sorted. + // The final equivalence class is omitted so that we can add tests using the pre-defined `successor` + // projection. + auto mod4_equivalence_classes = std::array{0, 4, 8, 16, 73, 13, 22, 110, 70}; + + // Check that we really do have equivalence classes and that 2/3 of them aren't sorted. + assert(ranges::is_partitioned(mod4_equivalence_classes.begin(), mod4_equivalence_classes.end(), + [](int const x) { return x % 4 == 0; })); + assert(std::is_sorted(mod4_equivalence_classes.begin(), mod4_equivalence_classes.begin() + 4)); + + assert(ranges::is_partitioned(mod4_equivalence_classes.begin() + 4, mod4_equivalence_classes.end(), + [](int const x) { return x % 4 == 1; })); + assert(!std::is_sorted(mod4_equivalence_classes.begin() + 4, mod4_equivalence_classes.begin() + 6)); + + assert(ranges::is_partitioned(mod4_equivalence_classes.begin() + 6, mod4_equivalence_classes.end(), + [](int const x) { return x % 4 == 2; })); + assert(!std::is_sorted(mod4_equivalence_classes.begin() + 6, mod4_equivalence_classes.end())); + + auto strict_weak_order = [](auto const x, auto const y) { + return (static_cast(x) % 4) < (static_cast(y) % 4); + }; + + test_algorithm(mod4_equivalence_classes, strict_weak_order, [](auto& input, auto& comp) { + auto comp_ref = std::ref(comp); + auto const result = ranges::upper_bound(input.begin(), input.end(), static_cast(0), comp_ref); + assert(result == ranges::next(input.begin(), 4)); + assert(ranges::upper_bound(input, static_cast(0), comp_ref) == result); + }); + test_algorithm(mod4_equivalence_classes, strict_weak_order, [](auto& input, auto& comp) { + auto comp_ref = std::ref(comp); + auto const result = ranges::upper_bound(input.begin(), input.end(), static_cast(1), comp_ref); + assert(result == ranges::next(input.begin(), 6)); + assert(ranges::upper_bound(input, static_cast(1), comp_ref) == result); + }); + test_algorithm(mod4_equivalence_classes, strict_weak_order, [](auto& input, auto& comp) { + auto comp_ref = std::ref(comp); + auto const result = ranges::upper_bound(input.begin(), input.end(), static_cast(2), comp_ref); + assert(result == input.end()); + assert(ranges::upper_bound(input, static_cast(2), comp_ref) == result); + }); + test_algorithm(mod4_equivalence_classes, strict_weak_order, [](auto& input, auto& comp) { + auto comp_ref = std::ref(comp); + assert(ranges::upper_bound(input.begin(), input.end(), static_cast(3), comp_ref) == input.end()); + assert(ranges::upper_bound(input, static_cast(3), comp_ref) == input.end()); + }); + + test_algorithm(mod4_equivalence_classes, strict_weak_order, successor, [](auto& input, auto& comp, auto& proj) { + auto comp_ref = std::ref(comp); + auto proj_ref = std::ref(proj); + auto const result = ranges::upper_bound(input.begin(), input.end(), static_cast(0), comp_ref, proj_ref); + assert(result == input.begin()); + assert(ranges::upper_bound(input, static_cast(0), comp_ref, proj_ref) == result); + }); + test_algorithm(mod4_equivalence_classes, strict_weak_order, successor, [](auto& input, auto& comp, auto& proj) { + auto comp_ref = std::ref(comp); + auto proj_ref = std::ref(proj); + + auto const result = ranges::upper_bound(input.begin(), input.end(), static_cast(1), comp_ref, proj_ref); + assert(result == ranges::next(input.begin(), 4)); + assert(ranges::upper_bound(input, static_cast(1), comp_ref, proj_ref) == result); + }); + test_algorithm(mod4_equivalence_classes, strict_weak_order, successor, [](auto& input, auto& comp, auto& proj) { + auto comp_ref = std::ref(comp); + auto proj_ref = std::ref(proj); + + auto const result = ranges::upper_bound(input.begin(), input.end(), static_cast(2), comp_ref, proj_ref); + assert(result == ranges::next(input.begin(), 6)); + assert(ranges::upper_bound(input, static_cast(2), comp_ref, proj_ref) == result); + }); + test_algorithm(mod4_equivalence_classes, strict_weak_order, successor, [](auto& input, auto& comp, auto& proj) { + auto comp_ref = std::ref(comp); + auto proj_ref = std::ref(proj); + + auto const result = ranges::upper_bound(input.begin(), input.end(), static_cast(3), comp_ref, proj_ref); + assert(result == input.end()); + assert(ranges::upper_bound(input, static_cast(3), comp_ref, proj_ref) == result); + }); + + return true; +} + +int main(int, char**) { + static_assert(check_upper_bound()); + static_assert(check_upper_bound()); + check_upper_bound(); + check_upper_bound(); + + static_assert(check_upper_bound()); + static_assert(check_upper_bound()); + check_upper_bound(); + check_upper_bound(); + + static_assert(check_upper_bound()); + static_assert(check_upper_bound()); + check_upper_bound(); + check_upper_bound(); + + static_assert(check_upper_bound()); + static_assert(check_upper_bound()); + check_upper_bound(); + check_upper_bound(); + + ASSERT_SAME_TYPE(decltype(ranges::upper_bound(std::vector(10), 0)), + ranges::dangling); + ASSERT_SAME_TYPE(decltype(ranges::upper_bound(std::vector(10), 0, {})), + ranges::dangling); + ASSERT_SAME_TYPE(decltype(ranges::upper_bound(std::vector(10), 0, {}, {})), + ranges::dangling); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/upper.bound/ranges_upper_bound/special_function.compile.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/upper.bound/ranges_upper_bound/special_function.compile.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/upper.bound/ranges_upper_bound/special_function.compile.pass.cpp @@ -0,0 +1,112 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-no-concepts +// UNSUPPORTED: gcc-10 + +// ranges::upper_bound + +#include + +#include +#include +#include +#include + +#include "test_range.h" +#include "test_standard_function.h" + +static_assert(is_function_like()); + +namespace ranges = std::ranges; + +namespace std::ranges { + template + class basic_istream_view { + struct iterator; + public: + iterator begin(); + default_sentinel_t end() const; + }; +} // namespace std::ranges + +auto f = [](auto, auto) { return true; }; + +// The entities defined in the std::ranges namespace in this Clause are not found by argument-dependent +// name lookup ([basic.lookup.argdep]). When found by unqualified ([basic.lookup.unqual]) name lookup for +// the postfix-expression in a function call ([expr.call]), they inhibit argument-dependent name lookup. +template +constexpr bool no_unqualified_lookup() { + auto identity = ranges::basic_istream_view(); + static_assert(!requires(T const value) { upper_bound(ranges::begin(identity), ranges::end(identity), value, f); }); + static_assert(!requires(T const value) { upper_bound(ranges::begin(identity), ranges::end(identity), value, f, &T::first); }); + static_assert(!requires(T const value) { upper_bound(identity, value, f); }); + static_assert(!requires(T const value) { upper_bound(identity, value, f, &T::first); }); + return true; +}; + +static_assert(no_unqualified_lookup>()); + +namespace test { +template +struct iterator { + using value_type = std::pair; + using difference_type = std::ptrdiff_t; + using iterator_category = std::forward_iterator_tag; + + iterator() = default; + + value_type operator*() const; + iterator& operator++(); + iterator operator++(int); + + bool operator==(iterator const&) const = default; +}; + +template +struct range { + std::pair const* begin() const; + std::pair const* end() const; +}; + +template +void upper_bound(iterator, iterator, auto, auto) { + static_assert(std::same_as); +} + +template +void upper_bound(iterator, iterator, auto, auto, auto) { + static_assert(std::same_as); +} + +template +void upper_bound(R&&, auto, auto) { + static_assert(std::same_as); +} + +template +void upper_bound(R&&, auto, auto, auto) { + static_assert(std::same_as); +} +} // namespace test + +// When found by unqualified ([basic.lookup.unqual]) name lookup for the postfix-expression in a +// function call ([expr.call]), they inhibit argument-dependent name lookup. +void adl_inhibition() { + using std::ranges::upper_bound; + + test::iterator*> x; + std::pair value; + (void)upper_bound(x, x, value, f); + (void)upper_bound(x, x, value, f, &std::pair::first); + + test::range r; + (void)upper_bound(r, value, f); + (void)upper_bound(r, value, f, &std::pair::first); +}