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