| //===----------------------------------------------------------------------===// |
| // |
| // 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 |
| |
| // <algorithm> |
| |
| // template<class InputIterator1, class InputIterator2, class Cmp> |
| // constexpr auto |
| // lexicographical_compare_three_way(InputIterator1 first1, InputIterator1 last1, |
| // InputIterator2 first2, InputIterator2 last2, |
| // Cmp comp) |
| // -> decltype(comp(*b1, *b2)); |
| |
| #include <array> |
| #include <algorithm> |
| #include <cassert> |
| #include <compare> |
| #include <concepts> |
| #include <limits> |
| |
| #include "test_macros.h" |
| #include "test_iterators.h" |
| |
| using std::array; |
| |
| constexpr auto compare_last_digit_strong = [](int a, int b) -> std::strong_ordering { return (a % 10) <=> (b % 10); }; |
| constexpr auto compare_last_digit_weak = [](int a, int b) -> std::weak_ordering { return (a % 10) <=> (b % 10); }; |
| constexpr auto compare_last_digit_partial = [](int a, int b) -> std::partial_ordering { |
| if (a == std::numeric_limits<int>::min() || b == std::numeric_limits<int>::min()) |
| return std::partial_ordering::unordered; |
| return (a % 10) <=> (b % 10); |
| }; |
| constexpr auto compare_int_result = [](int a, int b) -> int { return (a % 10) - (b % 10); }; |
| |
| struct StructWithoutCallOperator {}; |
| |
| template <class T> |
| concept has_lexicographical_compare = |
| requires(int* ptr, T comp) { std::lexicographical_compare_three_way(ptr, ptr, ptr, ptr, comp); }; |
| |
| // `std::lexicographical_compare_three_way` accepts valid types |
| static_assert(has_lexicographical_compare<decltype(compare_last_digit_strong)>); |
| static_assert(has_lexicographical_compare<decltype(compare_last_digit_weak)>); |
| static_assert(has_lexicographical_compare<decltype(compare_last_digit_partial)>); |
| // `std::lexicographical_compare_three_way` rejects non-invocable comparators |
| static_assert(!has_lexicographical_compare<StructWithoutCallOperator>); |
| // `std::lexicographical_compare_three_way` accepts invalid comparators returning a wrong type. |
| // This will trigger a `static_assert` only when actually invoking `has_lexicographical_compare`. |
| static_assert(has_lexicographical_compare<decltype(compare_int_result)>); |
| |
| template <typename Iter1, typename Iter2, typename C1, typename C2, typename Order, typename Comparator> |
| constexpr void test_lexicographical_compare(C1 a, C2 b, Comparator comp, Order expected) { |
| std::same_as<Order> decltype(auto) result = |
| std::lexicographical_compare_three_way(Iter1{a.begin()}, Iter1{a.end()}, Iter2{b.begin()}, Iter2{b.end()}, comp); |
| assert(expected == result); |
| } |
| |
| template <typename Iter1, typename Iter2> |
| constexpr void test_given_iterator_types() { |
| auto cmp = compare_last_digit_strong; |
| // Both inputs empty |
| test_lexicographical_compare<Iter1, Iter2>( |
| std::array<int, 0>{}, std::array<int, 0>{}, cmp, std::strong_ordering::equal); |
| // Left input empty |
| test_lexicographical_compare<Iter1, Iter2>(std::array<int, 0>{}, std::array{0, 1}, cmp, std::strong_ordering::less); |
| // Right input empty |
| test_lexicographical_compare<Iter1, Iter2>( |
| std::array{0, 1}, std::array<int, 0>{}, cmp, std::strong_ordering::greater); |
| |
| // Identical arrays |
| test_lexicographical_compare<Iter1, Iter2>(std::array{0, 1}, std::array{0, 1}, cmp, std::strong_ordering::equal); |
| // "Less" on 2nd element |
| test_lexicographical_compare<Iter1, Iter2>(std::array{0, 1}, std::array{0, 2}, cmp, std::strong_ordering::less); |
| // "Greater" on 2nd element |
| test_lexicographical_compare<Iter1, Iter2>(std::array{0, 2}, std::array{0, 1}, cmp, std::strong_ordering::greater); |
| // "Greater" on 2nd element, but "less" on first entry |
| test_lexicographical_compare<Iter1, Iter2>(std::array{0, 2}, std::array{1, 1}, cmp, std::strong_ordering::less); |
| // Identical elements, but longer |
| test_lexicographical_compare<Iter1, Iter2>(std::array{0, 1}, std::array{0, 1, 2}, cmp, std::strong_ordering::less); |
| // Identical elements, but shorter |
| test_lexicographical_compare<Iter1, Iter2>(std::array{0, 1, 2}, std::array{0, 1}, cmp, std::strong_ordering::greater); |
| // Identical arrays, but only if we take the comparator |
| // into account instead of using the default comparator |
| test_lexicographical_compare<Iter1, Iter2>(std::array{10, 21}, std::array{10, 31}, cmp, std::strong_ordering::equal); |
| } |
| |
| template <typename Iter1> |
| constexpr void test_iterator_types1() { |
| test_given_iterator_types<Iter1, int*>(); |
| test_given_iterator_types<Iter1, const int*>(); |
| test_given_iterator_types<Iter1, cpp17_input_iterator<const int*>>(); |
| test_given_iterator_types<Iter1, forward_iterator<const int*>>(); |
| test_given_iterator_types<Iter1, bidirectional_iterator<const int*>>(); |
| test_given_iterator_types<Iter1, random_access_iterator<const int*>>(); |
| test_given_iterator_types<Iter1, contiguous_iterator<const int*>>(); |
| } |
| |
| constexpr void test_iterator_types() { |
| // Exhaustively test all combinations of `int*`, `const int*`, `cpp17_input_iterator`, |
| // `forward_iterator`, `bidirectional_iterator`, `random_access_iterator`, |
| // `contiguous_iterator`. |
| // |
| // `lexicographical_compare_three_way` has a fast path which triggers if both |
| // iterators are random access iterators. |
| |
| test_iterator_types1<int*>(); |
| test_iterator_types1<const int*>(); |
| test_iterator_types1<cpp17_input_iterator<const int*>>(); |
| test_iterator_types1<forward_iterator<const int*>>(); |
| test_iterator_types1<bidirectional_iterator<const int*>>(); |
| test_iterator_types1<random_access_iterator<const int*>>(); |
| test_iterator_types1<contiguous_iterator<const int*>>(); |
| } |
| |
| // Check for other comparison categories |
| constexpr void test_comparison_categories() { |
| test_lexicographical_compare<const int*, const int*>( |
| std::array{0, 1}, std::array{10, 11}, compare_last_digit_weak, std::weak_ordering::equivalent); |
| test_lexicographical_compare<const int*, const int*>( |
| std::array{0, 1}, std::array{20, 11}, compare_last_digit_partial, std::partial_ordering::equivalent); |
| |
| // Check for all comparison categories with arrays of different sizes |
| test_lexicographical_compare<const int*, const int*>( |
| std::array{0}, std::array{0, 1}, compare_last_digit_strong, std::strong_ordering::less); |
| test_lexicographical_compare<const int*, const int*>( |
| std::array{0}, std::array{0, 1}, compare_last_digit_weak, std::weak_ordering::less); |
| test_lexicographical_compare<const int*, const int*>( |
| std::array{0}, std::array{0, 1}, compare_last_digit_partial, std::partial_ordering::less); |
| |
| // Check for a `partial_ordering::unordered` result |
| test_lexicographical_compare<const int*, const int*>( |
| std::array{std::numeric_limits<int>::min(), 1}, |
| std::array{0, 1, 2}, |
| compare_last_digit_partial, |
| std::partial_ordering::unordered); |
| } |
| |
| // Test for "Complexity: At most N applications of comp." |
| constexpr void test_comparator_invocation_count() { |
| int compare_invocation_count = 0; |
| auto compare_last_digit_counting = [&](int a, int b) -> std::strong_ordering { |
| ++compare_invocation_count; |
| return (a % 10) <=> (b % 10); |
| }; |
| // If one of the ranges is empty, the comparator must not be called at all |
| compare_invocation_count = 0; |
| test_lexicographical_compare<const int*, const int*>( |
| std::array{0, 1, 2, 3}, std::array<int, 0>{}, compare_last_digit_counting, std::strong_ordering::greater); |
| assert(compare_invocation_count == 0); |
| // The comparator is invoked only `min(left.size(), right.size())` times |
| test_lexicographical_compare<const int*, const int*>( |
| std::array{0, 1, 2}, std::array{0, 1, 2, 3}, compare_last_digit_counting, std::strong_ordering::less); |
| assert(compare_invocation_count == 3); |
| } |
| |
| constexpr bool test() { |
| test_iterator_types(); |
| test_comparison_categories(); |
| test_comparator_invocation_count(); |
| |
| return true; |
| } |
| |
| int main(int, char**) { |
| test(); |
| static_assert(test()); |
| |
| return 0; |
| } |