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/iterator_operations.h>
13#include <__algorithm/move.h>
14#include <__algorithm/move_backward.h>
15#include <__algorithm/swap_ranges.h>
16#include <__config>
17#include <__iterator/iterator_traits.h>
18#include <__type_traits/is_trivially_assignable.h>
19#include <__utility/move.h>
20#include <__utility/pair.h>
21
22#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
23# pragma GCC system_header
24#endif
25
26_LIBCPP_PUSH_MACROS
27#include <__undef_macros>
28
29_LIBCPP_BEGIN_NAMESPACE_STD
30
31template <class _AlgPolicy, class _ForwardIterator>
32_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _ForwardIterator
33__rotate_left(_ForwardIterator __first, _ForwardIterator __last) {
34 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
35 using _Ops = _IterOps<_AlgPolicy>;
36
37 value_type __tmp = _Ops::__iter_move(__first);
38 _ForwardIterator __lm1 = std::__move<_AlgPolicy>(_Ops::next(__first), __last, __first).second;
39 *__lm1 = std::move(__tmp);
40 return __lm1;
41}
42
43template <class _AlgPolicy, class _BidirectionalIterator>
44_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _BidirectionalIterator
45__rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last) {
46 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
47 using _Ops = _IterOps<_AlgPolicy>;
48
49 _BidirectionalIterator __lm1 = _Ops::prev(__last);
50 value_type __tmp = _Ops::__iter_move(__lm1);
51 _BidirectionalIterator __fp1 = std::__move_backward<_AlgPolicy>(__first, __lm1, std::move(__last)).second;
52 *__first = std::move(__tmp);
53 return __fp1;
54}
55
56template <class _AlgPolicy, class _ForwardIterator>
57_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 _ForwardIterator
58__rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last) {
59 _ForwardIterator __i = __middle;
60 while (true) {
61 _IterOps<_AlgPolicy>::iter_swap(__first, __i);
62 ++__first;
63 if (++__i == __last)
64 break;
65 if (__first == __middle)
66 __middle = __i;
67 }
68 _ForwardIterator __r = __first;
69 if (__first != __middle) {
70 __i = __middle;
71 while (true) {
72 _IterOps<_AlgPolicy>::iter_swap(__first, __i);
73 ++__first;
74 if (++__i == __last) {
75 if (__first == __middle)
76 break;
77 __i = __middle;
78 } else if (__first == __middle)
79 __middle = __i;
80 }
81 }
82 return __r;
83}
84
85template <typename _Integral>
86inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 _Integral __algo_gcd(_Integral __x, _Integral __y) {
87 do {
88 _Integral __t = __x % __y;
89 __x = __y;
90 __y = __t;
91 } while (__y);
92 return __x;
93}
94
95template <class _AlgPolicy, typename _RandomAccessIterator>
96_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 _RandomAccessIterator
97__rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last) {
98 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
99 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
100 using _Ops = _IterOps<_AlgPolicy>;
101
102 const difference_type __m1 = __middle - __first;
103 const difference_type __m2 = _Ops::distance(__middle, __last);
104 if (__m1 == __m2) {
105 std::__swap_ranges<_AlgPolicy>(__first, __middle, __middle, __last);
106 return __middle;
107 }
108 const difference_type __g = std::__algo_gcd(__m1, __m2);
109 for (_RandomAccessIterator __p = __first + __g; __p != __first;) {
110 value_type __t(_Ops::__iter_move(--__p));
111 _RandomAccessIterator __p1 = __p;
112 _RandomAccessIterator __p2 = __p1 + __m1;
113 do {
114 *__p1 = _Ops::__iter_move(__p2);
115 __p1 = __p2;
116 const difference_type __d = _Ops::distance(__p2, __last);
117 if (__m1 < __d)
118 __p2 += __m1;
119 else
120 __p2 = __first + (__m1 - __d);
121 } while (__p2 != __p);
122 *__p1 = std::move(__t);
123 }
124 return __first + __m2;
125}
126
127template <class _AlgPolicy, class _ForwardIterator>
128inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _ForwardIterator
129__rotate_impl(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, std::forward_iterator_tag) {
130 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
131 if (is_trivially_move_assignable<value_type>::value) {
132 if (_IterOps<_AlgPolicy>::next(__first) == __middle)
133 return std::__rotate_left<_AlgPolicy>(__first, __last);
134 }
135 return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last);
136}
137
138template <class _AlgPolicy, class _BidirectionalIterator>
139inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _BidirectionalIterator __rotate_impl(
140 _BidirectionalIterator __first,
141 _BidirectionalIterator __middle,
142 _BidirectionalIterator __last,
143 bidirectional_iterator_tag) {
144 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
145 if (is_trivially_move_assignable<value_type>::value) {
146 if (_IterOps<_AlgPolicy>::next(__first) == __middle)
147 return std::__rotate_left<_AlgPolicy>(__first, __last);
148 if (_IterOps<_AlgPolicy>::next(__middle) == __last)
149 return std::__rotate_right<_AlgPolicy>(__first, __last);
150 }
151 return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last);
152}
153
154template <class _AlgPolicy, class _RandomAccessIterator>
155inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _RandomAccessIterator __rotate_impl(
156 _RandomAccessIterator __first,
157 _RandomAccessIterator __middle,
158 _RandomAccessIterator __last,
159 random_access_iterator_tag) {
160 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
161 if (is_trivially_move_assignable<value_type>::value) {
162 if (_IterOps<_AlgPolicy>::next(__first) == __middle)
163 return std::__rotate_left<_AlgPolicy>(__first, __last);
164 if (_IterOps<_AlgPolicy>::next(__middle) == __last)
165 return std::__rotate_right<_AlgPolicy>(__first, __last);
166 return std::__rotate_gcd<_AlgPolicy>(__first, __middle, __last);
167 }
168 return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last);
169}
170
171template <class _AlgPolicy, class _Iterator, class _Sentinel>
172_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_Iterator, _Iterator>
173__rotate(_Iterator __first, _Iterator __middle, _Sentinel __last) {
174 using _Ret = pair<_Iterator, _Iterator>;
175 _Iterator __last_iter = _IterOps<_AlgPolicy>::next(__middle, __last);
176
177 if (__first == __middle)
178 return _Ret(__last_iter, __last_iter);
179 if (__middle == __last)
180 return _Ret(std::move(__first), std::move(__last_iter));
181
182 using _IterCategory = typename _IterOps<_AlgPolicy>::template __iterator_category<_Iterator>;
183 auto __result = std::__rotate_impl<_AlgPolicy>(std::move(__first), std::move(__middle), __last_iter, _IterCategory());
184
185 return _Ret(std::move(__result), std::move(__last_iter));
186}
187
188template <class _ForwardIterator>
189inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator
190rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last) {
191 return std::__rotate<_ClassicAlgPolicy>(std::move(__first), std::move(__middle), std::move(__last)).first;
192}
193
194_LIBCPP_END_NAMESPACE_STD
195
196_LIBCPP_POP_MACROS
197
198#endif // _LIBCPP___ALGORITHM_ROTATE_H
199