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

source code of libcxx/test/std/algorithms/alg.modifying.operations/alg.rotate/ranges_rotate.pass.cpp