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#ifndef _LIBCPP___ALGORITHM_ROTATE_H
10#define _LIBCPP___ALGORITHM_ROTATE_H
11
12#include <__algorithm/copy.h>
13#include <__algorithm/copy_backward.h>
14#include <__algorithm/iterator_operations.h>
15#include <__algorithm/min.h>
16#include <__algorithm/move.h>
17#include <__algorithm/move_backward.h>
18#include <__algorithm/swap_ranges.h>
19#include <__config>
20#include <__fwd/bit_reference.h>
21#include <__iterator/iterator_traits.h>
22#include <__type_traits/is_trivially_assignable.h>
23#include <__utility/move.h>
24#include <__utility/pair.h>
25
26#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
27# pragma GCC system_header
28#endif
29
30_LIBCPP_PUSH_MACROS
31#include <__undef_macros>
32
33_LIBCPP_BEGIN_NAMESPACE_STD
34
35template <class _AlgPolicy, class _ForwardIterator>
36_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _ForwardIterator
37__rotate_left(_ForwardIterator __first, _ForwardIterator __last) {
38 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
39 using _Ops = _IterOps<_AlgPolicy>;
40
41 value_type __tmp = _Ops::__iter_move(__first);
42 _ForwardIterator __lm1 = std::__move<_AlgPolicy>(_Ops::next(__first), __last, __first).second;
43 *__lm1 = std::move(__tmp);
44 return __lm1;
45}
46
47template <class _AlgPolicy, class _BidirectionalIterator>
48_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _BidirectionalIterator
49__rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last) {
50 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
51 using _Ops = _IterOps<_AlgPolicy>;
52
53 _BidirectionalIterator __lm1 = _Ops::prev(__last);
54 value_type __tmp = _Ops::__iter_move(__lm1);
55 _BidirectionalIterator __fp1 = std::__move_backward<_AlgPolicy>(__first, __lm1, std::move(__last)).second;
56 *__first = std::move(__tmp);
57 return __fp1;
58}
59
60template <class _AlgPolicy, class _ForwardIterator>
61_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 _ForwardIterator
62__rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last) {
63 _ForwardIterator __i = __middle;
64 while (true) {
65 _IterOps<_AlgPolicy>::iter_swap(__first, __i);
66 ++__first;
67 if (++__i == __last)
68 break;
69 if (__first == __middle)
70 __middle = __i;
71 }
72 _ForwardIterator __r = __first;
73 if (__first != __middle) {
74 __i = __middle;
75 while (true) {
76 _IterOps<_AlgPolicy>::iter_swap(__first, __i);
77 ++__first;
78 if (++__i == __last) {
79 if (__first == __middle)
80 break;
81 __i = __middle;
82 } else if (__first == __middle)
83 __middle = __i;
84 }
85 }
86 return __r;
87}
88
89template <class _AlgPolicy, class _Iter, class _Sent>
90_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 _Iter
91__rotate_random_access(_Iter __first, _Iter __middle, _Sent __sent) {
92 auto __left = _IterOps<_AlgPolicy>::distance(__first, __middle);
93 auto __right = _IterOps<_AlgPolicy>::distance(__middle, __sent);
94 auto __last = __first + __right;
95
96 auto __min_len = std::min(__left, __right);
97
98 while (__min_len > 0) {
99 if (__left <= __right) {
100 do {
101 std::__swap_ranges<_AlgPolicy>(__first, __first + __left, __first + __left);
102 __first += __left;
103 __right -= __left;
104 } while (__left <= __right);
105 __min_len = __right;
106 } else {
107 do {
108 std::__swap_ranges<_AlgPolicy>(__first + (__left - __right), __first + __left, __first + __left);
109 __left -= __right;
110 } while (__left > __right);
111 __min_len = __left;
112 }
113 }
114 return __last;
115}
116
117template <class _AlgPolicy, class _ForwardIterator>
118inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _ForwardIterator
119__rotate_impl(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, std::forward_iterator_tag) {
120 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
121 if (is_trivially_move_assignable<value_type>::value) {
122 if (_IterOps<_AlgPolicy>::next(__first) == __middle)
123 return std::__rotate_left<_AlgPolicy>(__first, __last);
124 }
125 return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last);
126}
127
128template <class _AlgPolicy, class _BidirectionalIterator>
129inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _BidirectionalIterator __rotate_impl(
130 _BidirectionalIterator __first,
131 _BidirectionalIterator __middle,
132 _BidirectionalIterator __last,
133 bidirectional_iterator_tag) {
134 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
135 if (is_trivially_move_assignable<value_type>::value) {
136 if (_IterOps<_AlgPolicy>::next(__first) == __middle)
137 return std::__rotate_left<_AlgPolicy>(__first, __last);
138 if (_IterOps<_AlgPolicy>::next(__middle) == __last)
139 return std::__rotate_right<_AlgPolicy>(__first, __last);
140 }
141 return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last);
142}
143
144template <class _AlgPolicy, class _RandomAccessIterator>
145inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _RandomAccessIterator __rotate_impl(
146 _RandomAccessIterator __first,
147 _RandomAccessIterator __middle,
148 _RandomAccessIterator __last,
149 random_access_iterator_tag) {
150 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
151 if (is_trivially_move_assignable<value_type>::value) {
152 if (_IterOps<_AlgPolicy>::next(__first) == __middle)
153 return std::__rotate_left<_AlgPolicy>(__first, __last);
154 if (_IterOps<_AlgPolicy>::next(__middle) == __last)
155 return std::__rotate_right<_AlgPolicy>(__first, __last);
156 return std::__rotate_random_access<_AlgPolicy>(__first, __middle, __last);
157 }
158 return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last);
159}
160
161template <class _AlgPolicy, class _Iterator, class _Sentinel>
162_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_Iterator, _Iterator>
163__rotate(_Iterator __first, _Iterator __middle, _Sentinel __last) {
164 using _Ret = pair<_Iterator, _Iterator>;
165 _Iterator __last_iter = _IterOps<_AlgPolicy>::next(__middle, __last);
166
167 if (__first == __middle)
168 return _Ret(__last_iter, __last_iter);
169 if (__middle == __last)
170 return _Ret(std::move(__first), std::move(__last_iter));
171
172 using _IterCategory = typename _IterOps<_AlgPolicy>::template __iterator_category<_Iterator>;
173 auto __result = std::__rotate_impl<_AlgPolicy>(std::move(__first), std::move(__middle), __last_iter, _IterCategory());
174
175 return _Ret(std::move(__result), std::move(__last_iter));
176}
177
178template <class, class _Cp>
179_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<__bit_iterator<_Cp, false>, __bit_iterator<_Cp, false> >
180__rotate(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __middle, __bit_iterator<_Cp, false> __last) {
181 using _I1 = __bit_iterator<_Cp, false>;
182 using difference_type = typename _I1::difference_type;
183 difference_type __d1 = __middle - __first;
184 difference_type __d2 = __last - __middle;
185 _I1 __r = __first + __d2;
186 while (__d1 != 0 && __d2 != 0) {
187 if (__d1 <= __d2) {
188 if (__d1 <= __bit_array<_Cp>::capacity()) {
189 __bit_array<_Cp> __b(__d1);
190 std::copy(__first, __middle, __b.begin());
191 std::copy(__b.begin(), __b.end(), std::copy(__middle, __last, __first));
192 break;
193 } else {
194 __bit_iterator<_Cp, false> __mp = std::swap_ranges(__first, __middle, __middle);
195 __first = __middle;
196 __middle = __mp;
197 __d2 -= __d1;
198 }
199 } else {
200 if (__d2 <= __bit_array<_Cp>::capacity()) {
201 __bit_array<_Cp> __b(__d2);
202 std::copy(__middle, __last, __b.begin());
203 std::copy_backward(__b.begin(), __b.end(), std::copy_backward(__first, __middle, __last));
204 break;
205 } else {
206 __bit_iterator<_Cp, false> __mp = __first + __d2;
207 std::swap_ranges(__first, __mp, __middle);
208 __first = __mp;
209 __d1 -= __d2;
210 }
211 }
212 }
213 return std::make_pair(__r, __last);
214}
215
216template <class _ForwardIterator>
217inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator
218rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last) {
219 return std::__rotate<_ClassicAlgPolicy>(std::move(__first), std::move(__middle), std::move(__last)).first;
220}
221
222_LIBCPP_END_NAMESPACE_STD
223
224_LIBCPP_POP_MACROS
225
226#endif // _LIBCPP___ALGORITHM_ROTATE_H
227