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 // UNSUPPORTED: c++03, c++11, c++14, c++17
10
11 // <algorithm>
12
13 // template<permutable I, sentinel_for<I> S>
14 // constexpr subrange<I> rotate(I first, I middle, S last); // since C++20
15 //
16 // template<forward_range R>
17 // requires permutable<iterator_t<R>>
18 // constexpr borrowed_subrange_t<R> rotate(R&& r, iterator_t<R> middle); // Since C++20
19
20 #include <algorithm>
21 #include <array>
22 #include <cassert>
23 #include <ranges>
24
25 #include "almost_satisfies_types.h"
26 #include "test_iterators.h"
27
28 // Test constraints of the (iterator, sentinel) overload.
29 // ======================================================
30
31 template <class Iter = int*, class Sent = int*>
32 concept HasRotateIter =
33 requires(Iter&& iter, Sent&& sent) {
34 std::ranges::rotate(std::forward<Iter>(iter), std::forward<Iter>(iter), std::forward<Sent>(sent));
35 };
36
37 static_assert(HasRotateIter<int*, int*>);
38
39 // !permutable<I>
40 static_assert(!HasRotateIter<PermutableNotForwardIterator>);
41 static_assert(!HasRotateIter<PermutableNotSwappable>);
42
43 // !sentinel_for<S, I>
44 static_assert(!HasRotateIter<int*, SentinelForNotSemiregular>);
45 static_assert(!HasRotateIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
46
47 // Test constraints of the (range) overload.
48 // =========================================
49
50 template <class Range>
51 concept HasRotateRange =
52 requires(Range&& range, std::ranges::iterator_t<Range> iter) {
53 std::ranges::rotate(std::forward<Range>(range), iter);
54 };
55
56 template <class T>
57 using R = UncheckedRange<T>;
58
59 static_assert(HasRotateRange<R<int*>>);
60
61 // !forward_range<R>
62 static_assert(!HasRotateRange<ForwardRangeNotDerivedFrom>);
63 static_assert(!HasRotateRange<ForwardRangeNotIncrementable>);
64 static_assert(!HasRotateRange<ForwardRangeNotSentinelSemiregular>);
65 static_assert(!HasRotateRange<ForwardRangeNotSentinelEqualityComparableWith>);
66
67 // !permutable<iterator_t<R>>
68 static_assert(!HasRotateRange<PermutableRangeNotForwardIterator>);
69 static_assert(!HasRotateRange<PermutableRangeNotSwappable>);
70
71 template <class Iter, class Sent, std::size_t N>
test_one(const std::array<int,N> input,std::size_t mid_index,std::array<int,N> expected)72 constexpr void test_one(const std::array<int, N> input, std::size_t mid_index, std::array<int, N> expected) {
73 assert(mid_index <= N);
74
75 { // (iterator, sentinel) overload.
76 auto in = input;
77 auto begin = Iter(in.data());
78 auto mid = Iter(in.data() + mid_index);
79 auto end = Sent(Iter(in.data() + in.size()));
80
81 std::same_as<std::ranges::subrange<Iter>> decltype(auto) result = std::ranges::rotate(begin, mid, end);
82 assert(base(result.begin()) == in.data() + in.size() - mid_index);
83 assert(base(result.end()) == in.data() + in.size());
84 assert(in == expected);
85 }
86
87 { // (range) overload.
88 auto in = input;
89 auto begin = Iter(in.data());
90 auto mid = Iter(in.data() + mid_index);
91 auto end = Sent(Iter(in.data() + in.size()));
92 auto range = std::ranges::subrange(std::move(begin), std::move(end));
93
94 std::same_as<std::ranges::subrange<Iter>> decltype(auto) result = std::ranges::rotate(range, mid);
95 assert(base(result.begin()) == in.data() + in.size() - mid_index);
96 assert(base(result.end()) == in.data() + in.size());
97 assert(in == expected);
98 }
99 }
100
101 template <class Iter, class Sent>
test_iter_sent()102 constexpr void test_iter_sent() {
103 // Empty sequence.
104 test_one<Iter, Sent, 0>({}, 0, {});
105
106 // 1-element sequence.
107 test_one<Iter, Sent, 1>({1}, 0, {1});
108
109 // 2-element sequence.
110 test_one<Iter, Sent, 2>({1, 2}, 1, {2, 1});
111
112 // 3-element sequence.
113 test_one<Iter, Sent, 3>({1, 2, 3}, 1, {2, 3, 1});
114 test_one<Iter, Sent, 3>({1, 2, 3}, 2, {3, 1, 2});
115
116 // Longer sequence.
117 test_one<Iter, Sent, 7>({1, 2, 3, 4, 5, 6, 7}, 2, {3, 4, 5, 6, 7, 1, 2});
118
119 // Rotate around the middle.
120 test_one<Iter, Sent, 7>({1, 2, 3, 4, 5, 6, 7}, 3, {4, 5, 6, 7, 1, 2, 3});
121
122 // Rotate around the 1st element (no-op).
123 test_one<Iter, Sent, 7>({1, 2, 3, 4, 5, 6, 7}, 0, {1, 2, 3, 4, 5, 6, 7});
124
125 // Rotate around the 2nd element.
126 test_one<Iter, Sent, 7>({1, 2, 3, 4, 5, 6, 7}, 1, {2, 3, 4, 5, 6, 7, 1});
127
128 // Rotate around the last element.
129 test_one<Iter, Sent, 7>({1, 2, 3, 4, 5, 6, 7}, 6, {7, 1, 2, 3, 4, 5, 6});
130
131 // Pass `end()` as `mid` (no-op).
132 test_one<Iter, Sent, 7>({1, 2, 3, 4, 5, 6, 7}, 7, {1, 2, 3, 4, 5, 6, 7});
133 }
134
135 template <class Iter>
test_iter()136 constexpr void test_iter() {
137 test_iter_sent<Iter, Iter>();
138 test_iter_sent<Iter, sentinel_wrapper<Iter>>();
139 }
140
test_iterators()141 constexpr void test_iterators() {
142 test_iter<forward_iterator<int*>>();
143 test_iter<bidirectional_iterator<int*>>();
144 test_iter<random_access_iterator<int*>>();
145 test_iter<contiguous_iterator<int*>>();
146 test_iter<int*>();
147 }
148
test()149 constexpr bool test() {
150 test_iterators();
151
152 { // Complexity: at most `last - first` swaps.
153 const std::array input = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
154 auto expected = static_cast<int>(input.size());
155
156 {
157 auto in = input;
158 int swaps = 0;
159 auto begin = adl::Iterator::TrackSwaps(in.data(), swaps);
160 auto end = adl::Iterator::TrackSwaps(in.data() + in.size(), swaps);
161
162 for (std::size_t mid = 0; mid != input.size(); ++mid) {
163 std::ranges::rotate(begin, begin + mid, end);
164 assert(swaps <= expected);
165 }
166 }
167
168 {
169 auto in = input;
170 int swaps = 0;
171 auto begin = adl::Iterator::TrackSwaps(in.data(), swaps);
172 auto end = adl::Iterator::TrackSwaps(in.data() + in.size(), swaps);
173 auto range = std::ranges::subrange(begin, end);
174
175 for (std::size_t mid = 0; mid != input.size(); ++mid) {
176 std::ranges::rotate(range, begin + mid);
177 assert(swaps <= expected);
178 }
179 }
180 }
181
182 return true;
183 }
184
main(int,char **)185 int main(int, char**) {
186 test();
187 static_assert(test());
188
189 return 0;
190 }
191