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