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