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

   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>
  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>
 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>
 136 constexpr void test_iter() {
 137   test_iter_sent<Iter, Iter>();
 138   test_iter_sent<Iter, sentinel_wrapper<Iter>>();
 139 }
 140
 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
 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
 185 int main(int, char**) {
 186   test();
 187   static_assert(test());
 188
 189   return 0;
 190 }