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 // UNSUPPORTED: libcpp-has-no-incomplete-ranges 11 12 // <algorithm> 13 14 // template<permutable I, sentinel_for<I> S> 15 // constexpr subrange<I> rotate(I first, I middle, S last); // since C++20 16 // 17 // template<forward_range R> 18 // requires permutable<iterator_t<R>> 19 // constexpr borrowed_subrange_t<R> rotate(R&& r, iterator_t<R> middle); // Since C++20 20 21 #include <algorithm> 22 #include <array> 23 #include <cassert> 24 #include <ranges> 25 26 #include "almost_satisfies_types.h" 27 #include "test_iterators.h" 28 29 // Test constraints of the (iterator, sentinel) overload. 30 // ====================================================== 31 32 template <class Iter = int*, class Sent = int*> 33 concept HasRotateIter = 34 requires(Iter&& iter, Sent&& sent) { 35 std::ranges::rotate(std::forward<Iter>(iter), std::forward<Iter>(iter), std::forward<Sent>(sent)); 36 }; 37 38 static_assert(HasRotateIter<int*, int*>); 39 40 // !permutable<I> 41 static_assert(!HasRotateIter<PermutableNotForwardIterator>); 42 static_assert(!HasRotateIter<PermutableNotSwappable>); 43 44 // !sentinel_for<S, I> 45 static_assert(!HasRotateIter<int*, SentinelForNotSemiregular>); 46 static_assert(!HasRotateIter<int*, SentinelForNotWeaklyEqualityComparableWith>); 47 48 // Test constraints of the (range) overload. 49 // ========================================= 50 51 template <class Range> 52 concept HasRotateRange = 53 requires(Range&& range, std::ranges::iterator_t<Range> iter) { 54 std::ranges::rotate(std::forward<Range>(range), iter); 55 }; 56 57 template <class T> 58 using R = UncheckedRange<T>; 59 60 static_assert(HasRotateRange<R<int*>>); 61 62 // !forward_range<R> 63 static_assert(!HasRotateRange<ForwardRangeNotDerivedFrom>); 64 static_assert(!HasRotateRange<ForwardRangeNotIncrementable>); 65 static_assert(!HasRotateRange<ForwardRangeNotSentinelSemiregular>); 66 static_assert(!HasRotateRange<ForwardRangeNotSentinelEqualityComparableWith>); 67 68 // !permutable<iterator_t<R>> 69 static_assert(!HasRotateRange<PermutableRangeNotForwardIterator>); 70 static_assert(!HasRotateRange<PermutableRangeNotSwappable>); 71 72 template <class Iter, class Sent, size_t N> 73 constexpr void test_one(const std::array<int, N> input, 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 102 template <class Iter, class Sent> 103 constexpr 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 template <class Iter> 137 constexpr void test_iter() { 138 test_iter_sent<Iter, Iter>(); 139 test_iter_sent<Iter, sentinel_wrapper<Iter>>(); 140 } 141 142 constexpr void test_iterators() { 143 test_iter<forward_iterator<int*>>(); 144 test_iter<bidirectional_iterator<int*>>(); 145 test_iter<random_access_iterator<int*>>(); 146 test_iter<contiguous_iterator<int*>>(); 147 test_iter<int*>(); 148 } 149 150 constexpr bool test() { 151 test_iterators(); 152 153 { // Complexity: at most `last - first` swaps. 154 const std::array input = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; 155 auto expected = static_cast<int>(input.size()); 156 157 { 158 auto in = input; 159 int swaps = 0; 160 auto begin = adl::Iterator::TrackSwaps(in.data(), swaps); 161 auto end = adl::Iterator::TrackSwaps(in.data() + in.size(), swaps); 162 163 for (size_t mid = 0; mid != input.size(); ++mid) { 164 std::ranges::rotate(begin, begin + mid, end); 165 assert(swaps <= expected); 166 } 167 } 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 auto range = std::ranges::subrange(begin, end); 175 176 for (size_t mid = 0; mid != input.size(); ++mid) { 177 std::ranges::rotate(range, begin + mid); 178 assert(swaps <= expected); 179 } 180 } 181 } 182 183 return true; 184 } 185 186 int main(int, char**) { 187 test(); 188 static_assert(test()); 189 190 return 0; 191 } 192