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 
36 template <class Iter1, class Sent1 = Iter1, class Iter2 = int*, class Sent2 = int*>
37 concept HasLexicographicalCompareIt = requires(Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) {
38   std::ranges::lexicographical_compare(first1, last1, first2, last2);
39 };
40 
41 template <class Range1, class Range2 = UncheckedRange<int*>>
42 concept HasLexicographicalCompareR = requires(Range1 range1, Range2 range2) {
43   std::ranges::lexicographical_compare(range1, range2);
44 };
45 
46 static_assert(HasLexicographicalCompareIt<int*>);
47 static_assert(!HasLexicographicalCompareIt<InputIteratorNotDerivedFrom>);
48 static_assert(!HasLexicographicalCompareIt<InputIteratorNotIndirectlyReadable>);
49 static_assert(!HasLexicographicalCompareIt<InputIteratorNotInputOrOutputIterator>);
50 static_assert(!HasLexicographicalCompareIt<int*, SentinelForNotSemiregular>);
51 static_assert(!HasLexicographicalCompareIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
52 static_assert(!HasLexicographicalCompareIt<int*, int*, InputIteratorNotDerivedFrom>);
53 static_assert(!HasLexicographicalCompareIt<int*, int*, InputIteratorNotIndirectlyReadable>);
54 static_assert(!HasLexicographicalCompareIt<int*, int*, InputIteratorNotInputOrOutputIterator>);
55 static_assert(!HasLexicographicalCompareIt<int*, int*, int*, SentinelForNotSemiregular>);
56 static_assert(!HasLexicographicalCompareIt<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>);
57 static_assert(!HasLexicographicalCompareIt<int*, int*, int**, int**>); // not indirect_strict_weak_order
58 
59 static_assert(HasLexicographicalCompareR<UncheckedRange<int*>>);
60 static_assert(!HasLexicographicalCompareR<InputRangeNotDerivedFrom>);
61 static_assert(!HasLexicographicalCompareR<InputRangeNotIndirectlyReadable>);
62 static_assert(!HasLexicographicalCompareR<InputRangeNotInputOrOutputIterator>);
63 static_assert(!HasLexicographicalCompareR<InputRangeNotSentinelSemiregular>);
64 static_assert(!HasLexicographicalCompareR<InputRangeNotSentinelEqualityComparableWith>);
65 static_assert(!HasLexicographicalCompareR<UncheckedRange<int*>, InputRangeNotDerivedFrom>);
66 static_assert(!HasLexicographicalCompareR<UncheckedRange<int*>, InputRangeNotIndirectlyReadable>);
67 static_assert(!HasLexicographicalCompareR<UncheckedRange<int*>, InputRangeNotInputOrOutputIterator>);
68 static_assert(!HasLexicographicalCompareR<UncheckedRange<int*>, InputRangeNotSentinelSemiregular>);
69 static_assert(!HasLexicographicalCompareR<UncheckedRange<int*>, InputRangeNotSentinelEqualityComparableWith>);
70 static_assert(!HasLexicographicalCompareIt<UncheckedRange<int*>, UncheckedRange<int**>>); // not indirect_strict_weak_order
71 
72 template <int N, int M>
73 struct Data {
74   std::array<int, N> input1;
75   std::array<int, M> input2;
76   bool expected;
77 };
78 
79 template <class Iter1, class Sent1, class Iter2, class Sent2, int N, int M>
test(Data<N,M> d)80 constexpr 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 
96 template <class Iter1, class Sent1, class Iter2, class Sent2 = Iter2>
test_iterators()97 constexpr 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 
118 template <class Iter1, class Sent1 = Iter1>
test_iterators2()119 constexpr 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 
test()130 constexpr 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 
main(int,char **)221 int main(int, char**) {
222   test();
223   static_assert(test());
224 
225   return 0;
226 }
227