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