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/move.h>
13 #include <__algorithm/move_backward.h>
14 #include <__algorithm/swap_ranges.h>
15 #include <__config>
16 #include <__iterator/iterator_traits.h>
17 #include <__iterator/next.h>
18 #include <__iterator/prev.h>
19 #include <__utility/swap.h>
20 #include <iterator>
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 
31 template <class _ForwardIterator>
32 _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator
__rotate_left(_ForwardIterator __first,_ForwardIterator __last)33 __rotate_left(_ForwardIterator __first, _ForwardIterator __last)
34 {
35     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
36     value_type __tmp = _VSTD::move(*__first);
37     _ForwardIterator __lm1 = _VSTD::move(_VSTD::next(__first), __last, __first);
38     *__lm1 = _VSTD::move(__tmp);
39     return __lm1;
40 }
41 
42 template <class _BidirectionalIterator>
43 _LIBCPP_CONSTEXPR_AFTER_CXX11 _BidirectionalIterator
__rotate_right(_BidirectionalIterator __first,_BidirectionalIterator __last)44 __rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last)
45 {
46     typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
47     _BidirectionalIterator __lm1 = _VSTD::prev(__last);
48     value_type __tmp = _VSTD::move(*__lm1);
49     _BidirectionalIterator __fp1 = _VSTD::move_backward(__first, __lm1, __last);
50     *__first = _VSTD::move(__tmp);
51     return __fp1;
52 }
53 
54 template <class _ForwardIterator>
55 _LIBCPP_CONSTEXPR_AFTER_CXX14 _ForwardIterator
__rotate_forward(_ForwardIterator __first,_ForwardIterator __middle,_ForwardIterator __last)56 __rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
57 {
58     _ForwardIterator __i = __middle;
59     while (true)
60     {
61         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     {
71         __i = __middle;
72         while (true)
73         {
74             swap(*__first, *__i);
75             ++__first;
76             if (++__i == __last)
77             {
78                 if (__first == __middle)
79                     break;
80                 __i = __middle;
81             }
82             else if (__first == __middle)
83                 __middle = __i;
84         }
85     }
86     return __r;
87 }
88 
89 template<typename _Integral>
90 inline _LIBCPP_INLINE_VISIBILITY
91 _LIBCPP_CONSTEXPR_AFTER_CXX14 _Integral
__algo_gcd(_Integral __x,_Integral __y)92 __algo_gcd(_Integral __x, _Integral __y)
93 {
94     do
95     {
96         _Integral __t = __x % __y;
97         __x = __y;
98         __y = __t;
99     } while (__y);
100     return __x;
101 }
102 
103 template<typename _RandomAccessIterator>
104 _LIBCPP_CONSTEXPR_AFTER_CXX14 _RandomAccessIterator
__rotate_gcd(_RandomAccessIterator __first,_RandomAccessIterator __middle,_RandomAccessIterator __last)105 __rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
106 {
107     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
108     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
109 
110     const difference_type __m1 = __middle - __first;
111     const difference_type __m2 = __last - __middle;
112     if (__m1 == __m2)
113     {
114         _VSTD::swap_ranges(__first, __middle, __middle);
115         return __middle;
116     }
117     const difference_type __g = _VSTD::__algo_gcd(__m1, __m2);
118     for (_RandomAccessIterator __p = __first + __g; __p != __first;)
119     {
120         value_type __t(_VSTD::move(*--__p));
121         _RandomAccessIterator __p1 = __p;
122         _RandomAccessIterator __p2 = __p1 + __m1;
123         do
124         {
125             *__p1 = _VSTD::move(*__p2);
126             __p1 = __p2;
127             const difference_type __d = __last - __p2;
128             if (__m1 < __d)
129                 __p2 += __m1;
130             else
131                 __p2 = __first + (__m1 - __d);
132         } while (__p2 != __p);
133         *__p1 = _VSTD::move(__t);
134     }
135     return __first + __m2;
136 }
137 
138 template <class _ForwardIterator>
139 inline _LIBCPP_INLINE_VISIBILITY
140 _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator
__rotate(_ForwardIterator __first,_ForwardIterator __middle,_ForwardIterator __last,_VSTD::forward_iterator_tag)141 __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,
142          _VSTD::forward_iterator_tag)
143 {
144     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
145     if (is_trivially_move_assignable<value_type>::value)
146     {
147         if (_VSTD::next(__first) == __middle)
148             return _VSTD::__rotate_left(__first, __last);
149     }
150     return _VSTD::__rotate_forward(__first, __middle, __last);
151 }
152 
153 template <class _BidirectionalIterator>
154 inline _LIBCPP_INLINE_VISIBILITY
155 _LIBCPP_CONSTEXPR_AFTER_CXX11 _BidirectionalIterator
__rotate(_BidirectionalIterator __first,_BidirectionalIterator __middle,_BidirectionalIterator __last,bidirectional_iterator_tag)156 __rotate(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
157          bidirectional_iterator_tag)
158 {
159     typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
160     if (is_trivially_move_assignable<value_type>::value)
161     {
162         if (_VSTD::next(__first) == __middle)
163             return _VSTD::__rotate_left(__first, __last);
164         if (_VSTD::next(__middle) == __last)
165             return _VSTD::__rotate_right(__first, __last);
166     }
167     return _VSTD::__rotate_forward(__first, __middle, __last);
168 }
169 
170 template <class _RandomAccessIterator>
171 inline _LIBCPP_INLINE_VISIBILITY
172 _LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator
__rotate(_RandomAccessIterator __first,_RandomAccessIterator __middle,_RandomAccessIterator __last,random_access_iterator_tag)173 __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
174          random_access_iterator_tag)
175 {
176     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
177     if (is_trivially_move_assignable<value_type>::value)
178     {
179         if (_VSTD::next(__first) == __middle)
180             return _VSTD::__rotate_left(__first, __last);
181         if (_VSTD::next(__middle) == __last)
182             return _VSTD::__rotate_right(__first, __last);
183         return _VSTD::__rotate_gcd(__first, __middle, __last);
184     }
185     return _VSTD::__rotate_forward(__first, __middle, __last);
186 }
187 
188 template <class _ForwardIterator>
189 inline _LIBCPP_INLINE_VISIBILITY
190 _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
rotate(_ForwardIterator __first,_ForwardIterator __middle,_ForwardIterator __last)191 rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
192 {
193     if (__first == __middle)
194         return __last;
195     if (__middle == __last)
196         return __first;
197     return _VSTD::__rotate(__first, __middle, __last,
198                            typename iterator_traits<_ForwardIterator>::iterator_category());
199 }
200 
201 _LIBCPP_END_NAMESPACE_STD
202 
203 _LIBCPP_POP_MACROS
204 
205 #endif // _LIBCPP___ALGORITHM_ROTATE_H
206