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_move_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_BEGIN_NAMESPACE_STD
27 
28 template <class _AlgPolicy, class _ForwardIterator>
29 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _ForwardIterator
30 __rotate_left(_ForwardIterator __first, _ForwardIterator __last)
31 {
32     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
33     using _Ops = _IterOps<_AlgPolicy>;
34 
35     value_type __tmp = _Ops::__iter_move(__first);
36     _ForwardIterator __lm1 = std::__move<_AlgPolicy>(
37         _Ops::next(__first), __last, __first).second;
38     *__lm1 = _VSTD::move(__tmp);
39     return __lm1;
40 }
41 
42 template <class _AlgPolicy, class _BidirectionalIterator>
43 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _BidirectionalIterator
44 __rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last)
45 {
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 = _VSTD::move(__tmp);
53     return __fp1;
54 }
55 
56 template <class _AlgPolicy, class _ForwardIterator>
57 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 _ForwardIterator
58 __rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
59 {
60     _ForwardIterator __i = __middle;
61     while (true)
62     {
63         _IterOps<_AlgPolicy>::iter_swap(__first, __i);
64         ++__first;
65         if (++__i == __last)
66             break;
67         if (__first == __middle)
68             __middle = __i;
69     }
70     _ForwardIterator __r = __first;
71     if (__first != __middle)
72     {
73         __i = __middle;
74         while (true)
75         {
76             _IterOps<_AlgPolicy>::iter_swap(__first, __i);
77             ++__first;
78             if (++__i == __last)
79             {
80                 if (__first == __middle)
81                     break;
82                 __i = __middle;
83             }
84             else if (__first == __middle)
85                 __middle = __i;
86         }
87     }
88     return __r;
89 }
90 
91 template<typename _Integral>
92 inline _LIBCPP_INLINE_VISIBILITY
93 _LIBCPP_CONSTEXPR_SINCE_CXX17 _Integral
94 __algo_gcd(_Integral __x, _Integral __y)
95 {
96     do
97     {
98         _Integral __t = __x % __y;
99         __x = __y;
100         __y = __t;
101     } while (__y);
102     return __x;
103 }
104 
105 template <class _AlgPolicy, typename _RandomAccessIterator>
106 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 _RandomAccessIterator
107 __rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
108 {
109     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
110     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
111     using _Ops = _IterOps<_AlgPolicy>;
112 
113     const difference_type __m1 = __middle - __first;
114     const difference_type __m2 = _Ops::distance(__middle, __last);
115     if (__m1 == __m2)
116     {
117         std::__swap_ranges<_AlgPolicy>(__first, __middle, __middle, __last);
118         return __middle;
119     }
120     const difference_type __g = _VSTD::__algo_gcd(__m1, __m2);
121     for (_RandomAccessIterator __p = __first + __g; __p != __first;)
122     {
123         value_type __t(_Ops::__iter_move(--__p));
124         _RandomAccessIterator __p1 = __p;
125         _RandomAccessIterator __p2 = __p1 + __m1;
126         do
127         {
128             *__p1 = _Ops::__iter_move(__p2);
129             __p1 = __p2;
130             const difference_type __d = _Ops::distance(__p2, __last);
131             if (__m1 < __d)
132                 __p2 += __m1;
133             else
134                 __p2 = __first + (__m1 - __d);
135         } while (__p2 != __p);
136         *__p1 = _VSTD::move(__t);
137     }
138     return __first + __m2;
139 }
140 
141 template <class _AlgPolicy, class _ForwardIterator>
142 inline _LIBCPP_INLINE_VISIBILITY
143 _LIBCPP_CONSTEXPR_SINCE_CXX14 _ForwardIterator
144 __rotate_impl(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,
145          _VSTD::forward_iterator_tag)
146 {
147     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
148     if (is_trivially_move_assignable<value_type>::value)
149     {
150         if (_IterOps<_AlgPolicy>::next(__first) == __middle)
151             return std::__rotate_left<_AlgPolicy>(__first, __last);
152     }
153     return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last);
154 }
155 
156 template <class _AlgPolicy, class _BidirectionalIterator>
157 inline _LIBCPP_INLINE_VISIBILITY
158 _LIBCPP_CONSTEXPR_SINCE_CXX14 _BidirectionalIterator
159 __rotate_impl(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
160          bidirectional_iterator_tag)
161 {
162     typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
163     if (is_trivially_move_assignable<value_type>::value)
164     {
165         if (_IterOps<_AlgPolicy>::next(__first) == __middle)
166             return std::__rotate_left<_AlgPolicy>(__first, __last);
167         if (_IterOps<_AlgPolicy>::next(__middle) == __last)
168             return std::__rotate_right<_AlgPolicy>(__first, __last);
169     }
170     return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last);
171 }
172 
173 template <class _AlgPolicy, class _RandomAccessIterator>
174 inline _LIBCPP_INLINE_VISIBILITY
175 _LIBCPP_CONSTEXPR_SINCE_CXX14 _RandomAccessIterator
176 __rotate_impl(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
177          random_access_iterator_tag)
178 {
179     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
180     if (is_trivially_move_assignable<value_type>::value)
181     {
182         if (_IterOps<_AlgPolicy>::next(__first) == __middle)
183             return std::__rotate_left<_AlgPolicy>(__first, __last);
184         if (_IterOps<_AlgPolicy>::next(__middle) == __last)
185             return std::__rotate_right<_AlgPolicy>(__first, __last);
186         return std::__rotate_gcd<_AlgPolicy>(__first, __middle, __last);
187     }
188     return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last);
189 }
190 
191 template <class _AlgPolicy, class _Iterator, class _Sentinel>
192 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
193 pair<_Iterator, _Iterator>
194 __rotate(_Iterator __first, _Iterator __middle, _Sentinel __last) {
195   using _Ret = pair<_Iterator, _Iterator>;
196   _Iterator __last_iter = _IterOps<_AlgPolicy>::next(__middle, __last);
197 
198   if (__first == __middle)
199       return _Ret(__last_iter, __last_iter);
200   if (__middle == __last)
201       return _Ret(std::move(__first), std::move(__last_iter));
202 
203   using _IterCategory = typename _IterOps<_AlgPolicy>::template __iterator_category<_Iterator>;
204   auto __result = std::__rotate_impl<_AlgPolicy>(
205       std::move(__first), std::move(__middle), __last_iter, _IterCategory());
206 
207   return _Ret(std::move(__result), std::move(__last_iter));
208 }
209 
210 template <class _ForwardIterator>
211 inline _LIBCPP_INLINE_VISIBILITY
212 _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator
213 rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
214 {
215   return std::__rotate<_ClassicAlgPolicy>(
216       std::move(__first), std::move(__middle), std::move(__last)).first;
217 }
218 
219 _LIBCPP_END_NAMESPACE_STD
220 
221 #endif // _LIBCPP___ALGORITHM_ROTATE_H
222