21#ifndef RANGES_V3_ALGORITHM_ROTATE_HPP
22#define RANGES_V3_ALGORITHM_ROTATE_HPP
38#include <range/v3/utility/static_const.hpp>
42#include <range/v3/detail/prologue.hpp>
52 constexpr subrange<I> rotate_left(I first, I last)
54 iter_value_t<I> tmp = iter_move(first);
55 I lm1 = ranges::move(next(first), last, first).out;
56 *lm1 = std::move(tmp);
61 constexpr subrange<I> rotate_right(I first, I last)
64 iter_value_t<I> tmp = iter_move(lm1);
65 I fp1 = move_backward(first, lm1, last).out;
66 *
first = std::move(tmp);
70 template<
typename I,
typename S>
71 constexpr subrange<I> rotate_forward(I first, I middle, S last)
76 ranges::iter_swap(first, i);
89 ranges::iter_swap(first, j);
97 else if(first == middle)
105 constexpr D gcd(D x, D y)
117 constexpr subrange<I> rotate_gcd(I first, I middle, I last)
119 auto const m1 = middle -
first;
120 auto const m2 = last - middle;
123 swap_ranges(first, middle, middle);
124 return {middle, last};
126 auto const g = detail::gcd(m1, m2);
127 for(I p = first + g; p !=
first;)
129 iter_value_t<I> t = iter_move(--p);
136 auto const d = last - p2;
140 p2 =
first + (m1 - d);
144 return {
first + m2, last};
147 template<
typename I,
typename S>
148 constexpr subrange<I> rotate_(I first, I middle, S last, std::forward_iterator_tag)
150 return detail::rotate_forward(first, middle, last);
154 constexpr subrange<I> rotate_(I first, I middle, I last, std::forward_iterator_tag)
156 using value_type = iter_value_t<I>;
157 if(detail::is_trivially_move_assignable_v<value_type>)
159 if(next(first) == middle)
160 return detail::rotate_left(first, last);
162 return detail::rotate_forward(first, middle, last);
166 constexpr subrange<I> rotate_(I first, I middle, I last, std::bidirectional_iterator_tag)
168 using value_type = iter_value_t<I>;
169 if(detail::is_trivially_move_assignable_v<value_type>)
171 if(next(first) == middle)
172 return detail::rotate_left(first, last);
173 if(next(middle) == last)
174 return detail::rotate_right(first, last);
176 return detail::rotate_forward(first, middle, last);
180 constexpr subrange<I> rotate_(I first, I middle, I last, std::random_access_iterator_tag)
182 using value_type = iter_value_t<I>;
183 if(detail::is_trivially_move_assignable_v<value_type>)
185 if(next(first) == middle)
186 return detail::rotate_left(first, last);
187 if(next(middle) == last)
188 return detail::rotate_right(first, last);
189 return detail::rotate_gcd(first, middle, last);
191 return detail::rotate_forward(first, middle, last);
196 RANGES_FUNC_BEGIN(rotate)
199 template(
typename I,
typename S)(
200 requires permutable<I> AND sentinel_for<S, I>)
201 constexpr subrange<I> RANGES_FUNC(rotate)(I
first, I middle, S last)
205 first = ranges::next(std::move(first), last);
210 return {
first, middle};
212 return detail::rotate_(first, middle, last, iterator_tag_of<I>{});
216 template(
typename Rng,
typename I = iterator_t<Rng>)(
217 requires range<Rng> AND permutable<I>)
218 constexpr borrowed_subrange_t<Rng> RANGES_FUNC(rotate)(Rng && rng, I middle)
220 return (*
this)(begin(rng), std::move(middle), end(rng));
223 RANGES_FUNC_END(rotate)
227 using ranges::rotate;
232#include <range/v3/detail/epilogue.hpp>
front< Pair > first
Retrieve the first element of the pair Pair.
Definition meta.hpp:2251