21 #ifndef RANGES_V3_ALGORITHM_ROTATE_HPP
22 #define RANGES_V3_ALGORITHM_ROTATE_HPP
24 #include <type_traits>
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);
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)
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