Horizon
Loading...
Searching...
No Matches
rotate.hpp
Go to the documentation of this file.
1
2// Range v3 library
3//
4// Copyright Eric Niebler 2014-present
5//
6// Use, modification and distribution is subject to the
7// Boost Software License, Version 1.0. (See accompanying
8// file LICENSE_1_0.txt or copy at
9// http://www.boost.org/LICENSE_1_0.txt)
10//
11// Project home: https://github.com/ericniebler/range-v3
12//
13//===----------------------------------------------------------------------===//
14//
15// The LLVM Compiler Infrastructure
16//
17// This file is dual licensed under the MIT and the University of Illinois Open
18// Source Licenses. See LICENSE.TXT for details.
19//
20//===----------------------------------------------------------------------===//
21#ifndef RANGES_V3_ALGORITHM_ROTATE_HPP
22#define RANGES_V3_ALGORITHM_ROTATE_HPP
23
24#include <type_traits>
25#include <utility>
26
28
38#include <range/v3/utility/static_const.hpp>
41
42#include <range/v3/detail/prologue.hpp>
43
44namespace ranges
45{
49 namespace detail
50 {
51 template<typename I> // Forward
52 constexpr subrange<I> rotate_left(I first, I last)
53 {
54 iter_value_t<I> tmp = iter_move(first);
55 I lm1 = ranges::move(next(first), last, first).out;
56 *lm1 = std::move(tmp);
57 return {lm1, last};
58 }
59
60 template<typename I> // Bidirectional
61 constexpr subrange<I> rotate_right(I first, I last)
62 {
63 I lm1 = prev(last);
64 iter_value_t<I> tmp = iter_move(lm1);
65 I fp1 = move_backward(first, lm1, last).out;
66 *first = std::move(tmp);
67 return {fp1, last};
68 }
69
70 template<typename I, typename S> // Forward
71 constexpr subrange<I> rotate_forward(I first, I middle, S last)
72 {
73 I i = middle;
74 while(true)
75 {
76 ranges::iter_swap(first, i);
77 ++first;
78 if(++i == last)
79 break;
80 if(first == middle)
81 middle = i;
82 }
83 I r = first;
84 if(first != middle)
85 {
86 I j = middle;
87 while(true)
88 {
89 ranges::iter_swap(first, j);
90 ++first;
91 if(++j == last)
92 {
93 if(first == middle)
94 break;
95 j = middle;
96 }
97 else if(first == middle)
98 middle = j;
99 }
100 }
101 return {r, i};
102 }
103
104 template<typename D>
105 constexpr D gcd(D x, D y)
106 {
107 do
108 {
109 D t = x % y;
110 x = y;
111 y = t;
112 } while(y);
113 return x;
114 }
115
116 template<typename I> // Random
117 constexpr subrange<I> rotate_gcd(I first, I middle, I last)
118 {
119 auto const m1 = middle - first;
120 auto const m2 = last - middle;
121 if(m1 == m2)
122 {
123 swap_ranges(first, middle, middle);
124 return {middle, last};
125 }
126 auto const g = detail::gcd(m1, m2);
127 for(I p = first + g; p != first;)
128 {
129 iter_value_t<I> t = iter_move(--p);
130 I p1 = p;
131 I p2 = p1 + m1;
132 do
133 {
134 *p1 = iter_move(p2);
135 p1 = p2;
136 auto const d = last - p2;
137 if(m1 < d)
138 p2 += m1;
139 else
140 p2 = first + (m1 - d);
141 } while(p2 != p);
142 *p1 = std::move(t);
143 }
144 return {first + m2, last};
145 }
146
147 template<typename I, typename S>
148 constexpr subrange<I> rotate_(I first, I middle, S last, std::forward_iterator_tag)
149 {
150 return detail::rotate_forward(first, middle, last);
151 }
152
153 template<typename I>
154 constexpr subrange<I> rotate_(I first, I middle, I last, std::forward_iterator_tag)
155 {
156 using value_type = iter_value_t<I>;
157 if(detail::is_trivially_move_assignable_v<value_type>)
158 {
159 if(next(first) == middle)
160 return detail::rotate_left(first, last);
161 }
162 return detail::rotate_forward(first, middle, last);
163 }
164
165 template<typename I>
166 constexpr subrange<I> rotate_(I first, I middle, I last, std::bidirectional_iterator_tag)
167 {
168 using value_type = iter_value_t<I>;
169 if(detail::is_trivially_move_assignable_v<value_type>)
170 {
171 if(next(first) == middle)
172 return detail::rotate_left(first, last);
173 if(next(middle) == last)
174 return detail::rotate_right(first, last);
175 }
176 return detail::rotate_forward(first, middle, last);
177 }
178
179 template<typename I>
180 constexpr subrange<I> rotate_(I first, I middle, I last, std::random_access_iterator_tag)
181 {
182 using value_type = iter_value_t<I>;
183 if(detail::is_trivially_move_assignable_v<value_type>)
184 {
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);
190 }
191 return detail::rotate_forward(first, middle, last);
192 }
193 } // namespace detail
195
196 RANGES_FUNC_BEGIN(rotate)
197
198
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) //
202 {
203 if(first == middle)
204 {
205 first = ranges::next(std::move(first), last);
206 return {first, first};
207 }
208 if(middle == last)
209 {
210 return {first, middle};
211 }
212 return detail::rotate_(first, middle, last, iterator_tag_of<I>{});
213 }
214
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) //
219 {
220 return (*this)(begin(rng), std::move(middle), end(rng));
221 }
222
223 RANGES_FUNC_END(rotate)
224
225 namespace cpp20
226 {
227 using ranges::rotate;
228 }
230} // namespace ranges
231
232#include <range/v3/detail/epilogue.hpp>
233
234#endif
front< Pair > first
Retrieve the first element of the pair Pair.
Definition meta.hpp:2251