1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9// <algorithm>
10
11// UNSUPPORTED: c++03, c++11, c++14, c++17
12
13// template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
14// class Proj1 = identity, class Proj2 = identity,
15// indirect_strict_weak_order<projected<I1, Proj1>,
16// projected<I2, Proj2>> Comp = ranges::less>
17// constexpr bool
18// ranges::lexicographical_compare(I1 first1, S1 last1, I2 first2, S2 last2,
19// Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
20// template<input_range R1, input_range R2, class Proj1 = identity,
21// class Proj2 = identity,
22// indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
23// projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
24// constexpr bool
25// ranges::lexicographical_compare(R1&& r1, R2&& r2, Comp comp = {},
26// Proj1 proj1 = {}, Proj2 proj2 = {});
27
28#include <algorithm>
29#include <array>
30#include <cassert>
31#include <ranges>
32
33#include "almost_satisfies_types.h"
34#include "test_iterators.h"
35
36template <class Iter1, class Sent1 = Iter1, class Iter2 = int*, class Sent2 = int*>
37concept HasLexicographicalCompareIt = requires(Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) {
38 std::ranges::lexicographical_compare(first1, last1, first2, last2);
39};
40
41template <class Range1, class Range2 = UncheckedRange<int*>>
42concept HasLexicographicalCompareR = requires(Range1 range1, Range2 range2) {
43 std::ranges::lexicographical_compare(range1, range2);
44};
45
46static_assert(HasLexicographicalCompareIt<int*>);
47static_assert(!HasLexicographicalCompareIt<InputIteratorNotDerivedFrom>);
48static_assert(!HasLexicographicalCompareIt<InputIteratorNotIndirectlyReadable>);
49static_assert(!HasLexicographicalCompareIt<InputIteratorNotInputOrOutputIterator>);
50static_assert(!HasLexicographicalCompareIt<int*, SentinelForNotSemiregular>);
51static_assert(!HasLexicographicalCompareIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
52static_assert(!HasLexicographicalCompareIt<int*, int*, InputIteratorNotDerivedFrom>);
53static_assert(!HasLexicographicalCompareIt<int*, int*, InputIteratorNotIndirectlyReadable>);
54static_assert(!HasLexicographicalCompareIt<int*, int*, InputIteratorNotInputOrOutputIterator>);
55static_assert(!HasLexicographicalCompareIt<int*, int*, int*, SentinelForNotSemiregular>);
56static_assert(!HasLexicographicalCompareIt<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>);
57static_assert(!HasLexicographicalCompareIt<int*, int*, int**, int**>); // not indirect_strict_weak_order
58
59static_assert(HasLexicographicalCompareR<UncheckedRange<int*>>);
60static_assert(!HasLexicographicalCompareR<InputRangeNotDerivedFrom>);
61static_assert(!HasLexicographicalCompareR<InputRangeNotIndirectlyReadable>);
62static_assert(!HasLexicographicalCompareR<InputRangeNotInputOrOutputIterator>);
63static_assert(!HasLexicographicalCompareR<InputRangeNotSentinelSemiregular>);
64static_assert(!HasLexicographicalCompareR<InputRangeNotSentinelEqualityComparableWith>);
65static_assert(!HasLexicographicalCompareR<UncheckedRange<int*>, InputRangeNotDerivedFrom>);
66static_assert(!HasLexicographicalCompareR<UncheckedRange<int*>, InputRangeNotIndirectlyReadable>);
67static_assert(!HasLexicographicalCompareR<UncheckedRange<int*>, InputRangeNotInputOrOutputIterator>);
68static_assert(!HasLexicographicalCompareR<UncheckedRange<int*>, InputRangeNotSentinelSemiregular>);
69static_assert(!HasLexicographicalCompareR<UncheckedRange<int*>, InputRangeNotSentinelEqualityComparableWith>);
70static_assert(!HasLexicographicalCompareIt<UncheckedRange<int*>, UncheckedRange<int**>>); // not indirect_strict_weak_order
71
72template <int N, int M>
73struct Data {
74 std::array<int, N> input1;
75 std::array<int, M> input2;
76 bool expected;
77};
78
79template <class Iter1, class Sent1, class Iter2, class Sent2, int N, int M>
80constexpr void test(Data<N, M> d) {
81 {
82 std::same_as<bool> decltype(auto) ret =
83 std::ranges::lexicographical_compare(Iter1(d.input1.data()), Sent1(Iter1(d.input1.data() + d.input1.size())),
84 Iter2(d.input2.data()), Sent2(Iter2(d.input2.data() + d.input2.size())));
85 assert(ret == d.expected);
86 }
87 {
88 auto range1 = std::ranges::subrange(Iter1(d.input1.data()), Sent1(Iter1(d.input1.data() + d.input1.size())));
89 auto range2 = std::ranges::subrange(Iter2(d.input2.data()), Sent2(Iter2(d.input2.data() + d.input2.size())));
90 std::same_as<bool> decltype(auto) ret =
91 std::ranges::lexicographical_compare(range1, range2);
92 assert(ret == d.expected);
93 }
94}
95
96template <class Iter1, class Sent1, class Iter2, class Sent2 = Iter2>
97constexpr void test_iterators() {
98 // simple test
99 test<Iter1, Sent1, Iter2, Sent2, 4, 4>({.input1 = {1, 2}, .input2 = {1, 2, 3, 4}, .expected = true});
100 // ranges are identical
101 test<Iter1, Sent1, Iter2, Sent2, 4, 4>({.input1 = {1, 2, 3, 4}, .input2 = {1, 2, 3, 4}, .expected = false});
102 // first range is empty
103 test<Iter1, Sent1, Iter2, Sent2, 0, 4>({.input1 = {}, .input2 = {1, 2, 3, 4}, .expected = true});
104 // second range is empty
105 test<Iter1, Sent1, Iter2, Sent2, 4, 0>({.input1 = {1, 2, 3, 4}, .input2 = {}, .expected = false});
106 // both ranges are empty
107 test<Iter1, Sent1, Iter2, Sent2, 0, 0>({.input1 = {}, .input2 = {}, .expected = false});
108 // the first range compares less; first range is smaller
109 test<Iter1, Sent1, Iter2, Sent2, 3, 5>({.input1 = {1, 2, 3}, .input2 = {1, 2, 4, 5, 6}, .expected = true});
110 // the second range compares less; first range is smaller
111 test<Iter1, Sent1, Iter2, Sent2, 3, 5>({.input1 = {1, 2, 4}, .input2 = {1, 2, 3, 4, 5}, .expected = false});
112 // the first range compares less; second range is smaller
113 test<Iter1, Sent1, Iter2, Sent2, 5, 3>({.input1 = {1, 2, 3, 4, 5}, .input2 = {1, 2, 4}, .expected = true});
114 // the second range compares less; second range is smaller
115 test<Iter1, Sent1, Iter2, Sent2, 5, 3>({.input1 = {1, 2, 4, 5, 6}, .input2 = {1, 2, 3}, .expected = false});
116}
117
118template <class Iter1, class Sent1 = Iter1>
119constexpr void test_iterators2() {
120 test_iterators<Iter1, Sent1, cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>();
121 test_iterators<Iter1, Sent1, cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
122 test_iterators<Iter1, Sent1, forward_iterator<int*>>();
123 test_iterators<Iter1, Sent1, bidirectional_iterator<int*>>();
124 test_iterators<Iter1, Sent1, random_access_iterator<int*>>();
125 test_iterators<Iter1, Sent1, contiguous_iterator<int*>>();
126 test_iterators<Iter1, Sent1, int*>();
127 test_iterators<Iter1, Sent1, const int*>();
128}
129
130constexpr bool test() {
131 test_iterators2<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>();
132 test_iterators2<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
133 test_iterators2<forward_iterator<int*>>();
134 test_iterators2<bidirectional_iterator<int*>>();
135 test_iterators2<random_access_iterator<int*>>();
136 test_iterators2<contiguous_iterator<int*>>();
137 test_iterators2<int*>();
138 test_iterators2<const int*>();
139
140 { // check that custom projections and the comparator are used properly
141 {
142 int a[] = {3, 4, 5, 6};
143 int b[] = {24, 33, 42, 51};
144
145 auto ret = std::ranges::lexicographical_compare(std::begin(a), std::end(a),
146 std::begin(b), std::end(b),
147 [](int lhs, int rhs) { return lhs == rhs + 5; },
148 [](int v) { return v - 2; },
149 [](int v) { return v / 3; });
150 assert(!ret);
151 }
152 {
153 int a[] = {3, 4, 5, 6};
154 int b[] = {24, 33, 42, 51};
155
156 auto ret = std::ranges::lexicographical_compare(a, b,
157 [](int lhs, int rhs) { return lhs == rhs + 5; },
158 [](int v) { return v - 2; },
159 [](int v) { return v / 3; });
160 assert(!ret);
161 }
162 }
163
164 { // check that std::invoke is used
165 struct S {
166 constexpr S(int i_) : i(i_) {}
167 constexpr bool compare(const S& j) const { return j.i < i; }
168 constexpr const S& identity() const { return *this; }
169 int i;
170 };
171 {
172 S a[] = {1, 2, 3, 4};
173 auto ret = std::ranges::lexicographical_compare(std::begin(a), std::end(a),
174 std::begin(a), std::end(a),
175 &S::compare,
176 &S::identity,
177 &S::identity);
178 assert(!ret);
179 }
180 {
181 S a[] = {1, 2, 3, 4};
182 auto ret = std::ranges::lexicographical_compare(a, a, &S::compare, &S::identity, &S::identity);
183 assert(!ret);
184 }
185 }
186
187 { // check that the complexity requirements are met
188 {
189 int predCount = 0;
190 auto pred = [&](int i, int j) { ++predCount; return i < j; };
191 auto proj1Count = 0;
192 auto proj1 = [&](int i) { ++proj1Count; return i; };
193 auto proj2Count = 0;
194 auto proj2 = [&](int i) { ++proj2Count; return i; };
195 int a[] = {1, 2, 3, 4, 5};
196 auto ret = std::ranges::lexicographical_compare(std::begin(a), std::end(a), std::begin(a), std::end(a), pred, proj1, proj2);
197 assert(!ret);
198 assert(predCount == 10);
199 assert(proj1Count == 10);
200 assert(proj2Count == 10);
201 }
202 {
203 int predCount = 0;
204 auto pred = [&](int i, int j) { ++predCount; return i < j; };
205 auto proj1Count = 0;
206 auto proj1 = [&](int i) { ++proj1Count; return i; };
207 auto proj2Count = 0;
208 auto proj2 = [&](int i) { ++proj2Count; return i; };
209 int a[] = {1, 2, 3, 4, 5};
210 auto ret = std::ranges::lexicographical_compare(a, a, pred, proj1, proj2);
211 assert(!ret);
212 assert(predCount == 10);
213 assert(proj1Count == 10);
214 assert(proj2Count == 10);
215 }
216 }
217
218 return true;
219}
220
221int main(int, char**) {
222 test();
223 static_assert(test());
224
225 return 0;
226}
227

source code of libcxx/test/std/algorithms/alg.sorting/alg.lex.comparison/ranges.lexicographical_compare.pass.cpp