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, c++20
12 
13 // template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
14 //          class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
15 //   requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
16 //   constexpr bool ranges::ends_with(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
17 //                                      Proj1 proj1 = {}, Proj2 proj2 = {});
18 // template<input_range R1, input_range R2, class Pred = ranges::equal_to, class Proj1 = identity,
19 //          class Proj2 = identity>
20 //   requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
21 //   constexpr bool ranges::ends_with(R1&& r1, R2&& r2, Pred pred = {},
22 //                                      Proj1 proj1 = {}, Proj2 proj2 = {});
23 
24 #include <algorithm>
25 #include <array>
26 #include <chrono>
27 #include <ranges>
28 #include "almost_satisfies_types.h"
29 #include "test_iterators.h"
30 
31 using namespace std::chrono;
32 
33 template <class Iter1, class Sent1 = Iter1, class Iter2 = int*, class Sent2 = Iter2>
34 concept HasEndsWithIt = requires(Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) {
35   std::ranges::ends_with(first1, last1, first2, last2);
36 };
37 
38 static_assert(HasEndsWithIt<int*>);
39 static_assert(!HasEndsWithIt<ForwardIteratorNotDerivedFrom>);
40 static_assert(!HasEndsWithIt<ForwardIteratorNotIncrementable>);
41 static_assert(HasEndsWithIt<int*, int*>);
42 static_assert(!HasEndsWithIt<int*, SentinelForNotSemiregular>);
43 static_assert(!HasEndsWithIt<int*, int*, int**>); // not indirectly comparable
44 static_assert(!HasEndsWithIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
45 static_assert(!HasEndsWithIt<int*, int*, ForwardIteratorNotDerivedFrom>);
46 static_assert(!HasEndsWithIt<int*, int*, ForwardIteratorNotIncrementable>);
47 static_assert(!HasEndsWithIt<int*, int*, int*, SentinelForNotSemiregular>);
48 static_assert(!HasEndsWithIt<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>);
49 
50 template <class Range1, class Range2 = UncheckedRange<int*>>
51 concept HasEndsWithR = requires(Range1&& range1, Range2&& range2) {
52     std::ranges::ends_with(std::forward<Range1>(range1), std::forward<Range2>(range2)); };
53 
54 static_assert(HasEndsWithR<UncheckedRange<int*>>);
55 static_assert(!HasEndsWithR<ForwardRangeNotDerivedFrom>);
56 static_assert(!HasEndsWithR<ForwardIteratorNotIncrementable>);
57 static_assert(!HasEndsWithR<ForwardRangeNotSentinelSemiregular>);
58 static_assert(!HasEndsWithR<ForwardRangeNotSentinelEqualityComparableWith>);
59 static_assert(HasEndsWithR<UncheckedRange<int*>, UncheckedRange<int*>>);
60 static_assert(!HasEndsWithR<UncheckedRange<int*>, UncheckedRange<int**>>); // not indirectly comparable
61 static_assert(!HasEndsWithR<UncheckedRange<int*>, ForwardRangeNotDerivedFrom>);
62 static_assert(!HasEndsWithR<UncheckedRange<int*>, ForwardRangeNotSentinelSemiregular>);
63 
64 // clang-format off
65 template <class Iter1, class Sent1 = Iter1, class Iter2, class Sent2 = Iter2>
test_iterators()66 constexpr void test_iterators() {
67   { // simple tests
68     int a[]          = {1, 2, 3, 4, 5, 6};
69     int p[]          = {4, 5, 6};
70     auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));
71     auto suffix  = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));
72     {
73       [[maybe_unused]] std::same_as<bool> decltype(auto) ret = std::ranges::ends_with(whole.begin(), whole.end(), suffix.begin(), suffix.end());
74       assert(ret);
75     }
76     {
77       [[maybe_unused]] std::same_as<bool> decltype(auto) ret = std::ranges::ends_with(whole, suffix);
78       assert(ret);
79     }
80   }
81 
82   { // suffix doesn't match
83     int a[] = {1, 2, 3, 4, 5, 6};
84     int p[] = {1, 2, 3};
85     auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));
86     auto suffix  = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));
87     {
88       bool ret = std::ranges::ends_with(whole.begin(), whole.end(), suffix.begin(), suffix.end());
89       assert(!ret);
90     }
91     {
92       bool ret = std::ranges::ends_with(whole, suffix);
93       assert(!ret);
94     }
95   }
96 
97   { // range consists of just one element
98     int a[] = {1};
99     int p[] = {1};
100     auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 1)));
101     auto suffix  = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 1)));
102     {
103       bool ret = std::ranges::ends_with(whole.begin(), whole.end(), suffix.begin(), suffix.end());
104       assert(ret);
105     }
106     {
107       bool ret = std::ranges::ends_with(whole, suffix);
108       assert(ret);
109     }
110   }
111 
112   { // suffix consists of just one element
113     int a[] = {5, 1, 2, 4, 3};
114     int p[] = {3};
115     auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5)));
116     auto suffix  = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 1)));
117     {
118       bool ret = std::ranges::ends_with(whole.begin(), whole.end(), suffix.begin(), suffix.end());
119       assert(ret);
120     }
121     {
122       bool ret = std::ranges::ends_with(whole, suffix);
123       assert(ret);
124     }
125   }
126 
127   { // range and suffix are identical
128     int a[] = {1, 2, 3, 4, 5, 6};
129     int p[] = {1, 2, 3, 4, 5, 6};
130     auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));
131     auto suffix  = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 6)));
132     {
133       bool ret = std::ranges::ends_with(whole.begin(), whole.end(), suffix.begin(), suffix.end());
134       assert(ret);
135     }
136     {
137       bool ret = std::ranges::ends_with(whole, suffix);
138       assert(ret);
139     }
140   }
141 
142   { // suffix is longer than range
143     int a[] = {3, 4, 5, 6, 7, 8};
144     int p[] = {1, 2, 3, 4, 5, 6, 7, 8};
145     auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));
146     auto suffix  = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 8)));
147     {
148       bool ret = std::ranges::ends_with(whole.begin(), whole.end(), suffix.begin(), suffix.end());
149       assert(!ret);
150     }
151     {
152       bool ret = std::ranges::ends_with(whole, suffix);
153       assert(!ret);
154     }
155  }
156 
157  { // suffix has zero length
158    int a[] = {1, 2, 3, 4, 5, 6};
159    std::array<int, 0> p = {};
160    auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));
161    auto suffix  = std::ranges::subrange(Iter2(p.data()), Sent2(Iter2(p.data())));
162    {
163      bool ret = std::ranges::ends_with(whole.begin(), whole.end(), suffix.begin(), suffix.end());
164      assert(ret);
165    }
166    {
167      bool ret = std::ranges::ends_with(whole, suffix);
168      assert(ret);
169    }
170  }
171 
172  { // range has zero length
173    std::array<int, 0> a = {};
174    int p[] = {1, 2, 3, 4, 5, 6, 7, 8};
175    auto whole = std::ranges::subrange(Iter1(a.data()), Sent1(Iter1(a.data())));
176    auto suffix  = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 8)));
177    {
178      bool ret = std::ranges::ends_with(whole.begin(), whole.end(), suffix.begin(), suffix.end());
179      assert(!ret);
180    }
181    {
182      bool ret = std::ranges::ends_with(whole, suffix);
183      assert(!ret);
184    }
185  }
186 
187  { // subarray
188    int a[] = {0, 3, 5, 10, 7, 3, 5, 89, 3, 5, 2, 1, 8, 6};
189    int p[] = {3, 5};
190    auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 13)));
191    auto suffix  = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 2)));
192    {
193      bool ret = std::ranges::ends_with(whole.begin(), whole.end(), suffix.begin(), suffix.end());
194      assert(!ret);
195    }
196    {
197      bool ret = std::ranges::ends_with(whole, suffix);
198      assert(!ret);
199    }
200  }
201 
202  { // repeated suffix
203    int a[] = {8, 6, 3, 5, 1, 2};
204    int p[] = {1, 2, 1, 2};
205    auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));
206    auto suffix  = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 4)));
207    {
208      bool ret = std::ranges::ends_with(whole.begin(), whole.end(), suffix.begin(), suffix.end());
209      assert(!ret);
210    }
211    {
212      bool ret = std::ranges::ends_with(whole, suffix);
213      assert(!ret);
214    }
215  }
216 
217  { // check that the predicate is used
218    int a[] = {5, 1, 3, 2, 7};
219    int p[] = {-2, -7};
220    auto pred = [](int l, int r) { return l * -1 == r; };
221    auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5)));
222    auto suffix  = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 2)));
223    {
224      bool ret = std::ranges::ends_with(whole.begin(), whole.end(), suffix.begin(), suffix.end(), pred);
225      assert(ret);
226    }
227    {
228      bool ret = std::ranges::ends_with(whole, suffix, pred);
229      assert(ret);
230    }
231  }
232 
233  { // check that the projections are used
234    int a[] = {1, 3, 15, 1, 2, 1};
235    int p[] = {2, 1, 2};
236    auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));
237    auto suffix  = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));
238    {
239      bool ret = std::ranges::ends_with(whole.begin(), whole.end(), suffix.begin(), suffix.end(), {},
240          [](int i) { return i - 3; },
241          [](int i) { return i * -1; });
242      assert(ret);
243    }
244    {
245      bool ret = std::ranges::ends_with(whole, suffix, {},
246          [](int i) { return i - 3; },
247          [](int i) { return i * -1; });
248      assert(ret);
249    }
250   }
251 }
252 
test()253 constexpr bool test() {
254   // This is to test (forward_iterator<_Iter1> || sized_sentinel_for<_Sent1, _Iter1>) condition.
255   types::for_each(types::cpp20_input_iterator_list<int*>{}, []<class Iter2>() {
256     types::for_each(types::cpp20_input_iterator_list<int*>{}, []<class Iter1>() {
257       if constexpr (std::forward_iterator<Iter1> && std::forward_iterator<Iter2>)
258         test_iterators<Iter1, Iter1, Iter2, Iter2>();
259       if constexpr (std::forward_iterator<Iter2>)
260         test_iterators<Iter1, sized_sentinel<Iter1>, Iter2, Iter2>();
261       if constexpr (std::forward_iterator<Iter1>)
262         test_iterators<Iter1, Iter1, Iter2, sized_sentinel<Iter2>>();
263       test_iterators<Iter1, sized_sentinel<Iter1>, Iter2, sized_sentinel<Iter2>>();
264     });
265   });
266 
267   return true;
268 }
269 
main(int,char **)270 int main(int, char**) {
271   test();
272   static_assert(test());
273 
274   return 0;
275 }
276