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/copy.h> 13 #include <__algorithm/copy_backward.h> 14 #include <__algorithm/iterator_operations.h> 15 #include <__algorithm/move.h> 16 #include <__algorithm/move_backward.h> 17 #include <__algorithm/swap_ranges.h> 18 #include <__config> 19 #include <__cstddef/size_t.h> 20 #include <__fwd/bit_reference.h> 21 #include <__iterator/iterator_traits.h> 22 #include <__memory/construct_at.h> 23 #include <__memory/pointer_traits.h> 24 #include <__type_traits/is_constant_evaluated.h> 25 #include <__type_traits/is_trivially_assignable.h> 26 #include <__utility/move.h> 27 #include <__utility/pair.h> 28 29 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 30 # pragma GCC system_header 31 #endif 32 33 _LIBCPP_PUSH_MACROS 34 #include <__undef_macros> 35 36 _LIBCPP_BEGIN_NAMESPACE_STD 37 38 template <class _AlgPolicy, class _ForwardIterator> 39 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _ForwardIterator 40 __rotate_left(_ForwardIterator __first, _ForwardIterator __last) { 41 typedef typename iterator_traits<_ForwardIterator>::value_type value_type; 42 using _Ops = _IterOps<_AlgPolicy>; 43 44 value_type __tmp = _Ops::__iter_move(__first); 45 _ForwardIterator __lm1 = std::__move<_AlgPolicy>(_Ops::next(__first), __last, __first).second; 46 *__lm1 = std::move(__tmp); 47 return __lm1; 48 } 49 50 template <class _AlgPolicy, class _BidirectionalIterator> 51 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _BidirectionalIterator 52 __rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last) { 53 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 54 using _Ops = _IterOps<_AlgPolicy>; 55 56 _BidirectionalIterator __lm1 = _Ops::prev(__last); 57 value_type __tmp = _Ops::__iter_move(__lm1); 58 _BidirectionalIterator __fp1 = std::__move_backward<_AlgPolicy>(__first, __lm1, std::move(__last)).second; 59 *__first = std::move(__tmp); 60 return __fp1; 61 } 62 63 template <class _AlgPolicy, class _ForwardIterator> 64 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 _ForwardIterator 65 __rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last) { 66 _ForwardIterator __i = __middle; 67 while (true) { 68 _IterOps<_AlgPolicy>::iter_swap(__first, __i); 69 ++__first; 70 if (++__i == __last) 71 break; 72 if (__first == __middle) 73 __middle = __i; 74 } 75 _ForwardIterator __r = __first; 76 if (__first != __middle) { 77 __i = __middle; 78 while (true) { 79 _IterOps<_AlgPolicy>::iter_swap(__first, __i); 80 ++__first; 81 if (++__i == __last) { 82 if (__first == __middle) 83 break; 84 __i = __middle; 85 } else if (__first == __middle) 86 __middle = __i; 87 } 88 } 89 return __r; 90 } 91 92 template <typename _Integral> 93 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 _Integral __algo_gcd(_Integral __x, _Integral __y) { 94 do { 95 _Integral __t = __x % __y; 96 __x = __y; 97 __y = __t; 98 } while (__y); 99 return __x; 100 } 101 102 template <class _AlgPolicy, typename _RandomAccessIterator> 103 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 _RandomAccessIterator 104 __rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last) { 105 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 106 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 107 using _Ops = _IterOps<_AlgPolicy>; 108 109 const difference_type __m1 = __middle - __first; 110 const difference_type __m2 = _Ops::distance(__middle, __last); 111 if (__m1 == __m2) { 112 std::__swap_ranges<_AlgPolicy>(__first, __middle, __middle, __last); 113 return __middle; 114 } 115 const difference_type __g = std::__algo_gcd(__m1, __m2); 116 for (_RandomAccessIterator __p = __first + __g; __p != __first;) { 117 value_type __t(_Ops::__iter_move(--__p)); 118 _RandomAccessIterator __p1 = __p; 119 _RandomAccessIterator __p2 = __p1 + __m1; 120 do { 121 *__p1 = _Ops::__iter_move(__p2); 122 __p1 = __p2; 123 const difference_type __d = _Ops::distance(__p2, __last); 124 if (__m1 < __d) 125 __p2 += __m1; 126 else 127 __p2 = __first + (__m1 - __d); 128 } while (__p2 != __p); 129 *__p1 = std::move(__t); 130 } 131 return __first + __m2; 132 } 133 134 template <class _AlgPolicy, class _ForwardIterator> 135 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _ForwardIterator 136 __rotate_impl(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, std::forward_iterator_tag) { 137 typedef typename iterator_traits<_ForwardIterator>::value_type value_type; 138 if (is_trivially_move_assignable<value_type>::value) { 139 if (_IterOps<_AlgPolicy>::next(__first) == __middle) 140 return std::__rotate_left<_AlgPolicy>(__first, __last); 141 } 142 return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last); 143 } 144 145 template <class _AlgPolicy, class _BidirectionalIterator> 146 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _BidirectionalIterator __rotate_impl( 147 _BidirectionalIterator __first, 148 _BidirectionalIterator __middle, 149 _BidirectionalIterator __last, 150 bidirectional_iterator_tag) { 151 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 152 if (is_trivially_move_assignable<value_type>::value) { 153 if (_IterOps<_AlgPolicy>::next(__first) == __middle) 154 return std::__rotate_left<_AlgPolicy>(__first, __last); 155 if (_IterOps<_AlgPolicy>::next(__middle) == __last) 156 return std::__rotate_right<_AlgPolicy>(__first, __last); 157 } 158 return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last); 159 } 160 161 template <class _AlgPolicy, class _RandomAccessIterator> 162 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _RandomAccessIterator __rotate_impl( 163 _RandomAccessIterator __first, 164 _RandomAccessIterator __middle, 165 _RandomAccessIterator __last, 166 random_access_iterator_tag) { 167 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 168 if (is_trivially_move_assignable<value_type>::value) { 169 if (_IterOps<_AlgPolicy>::next(__first) == __middle) 170 return std::__rotate_left<_AlgPolicy>(__first, __last); 171 if (_IterOps<_AlgPolicy>::next(__middle) == __last) 172 return std::__rotate_right<_AlgPolicy>(__first, __last); 173 return std::__rotate_gcd<_AlgPolicy>(__first, __middle, __last); 174 } 175 return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last); 176 } 177 178 template <class _AlgPolicy, class _Iterator, class _Sentinel> 179 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_Iterator, _Iterator> 180 __rotate(_Iterator __first, _Iterator __middle, _Sentinel __last) { 181 using _Ret = pair<_Iterator, _Iterator>; 182 _Iterator __last_iter = _IterOps<_AlgPolicy>::next(__middle, __last); 183 184 if (__first == __middle) 185 return _Ret(__last_iter, __last_iter); 186 if (__middle == __last) 187 return _Ret(std::move(__first), std::move(__last_iter)); 188 189 using _IterCategory = typename _IterOps<_AlgPolicy>::template __iterator_category<_Iterator>; 190 auto __result = std::__rotate_impl<_AlgPolicy>(std::move(__first), std::move(__middle), __last_iter, _IterCategory()); 191 192 return _Ret(std::move(__result), std::move(__last_iter)); 193 } 194 195 template <class, class _Cp> 196 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<__bit_iterator<_Cp, false>, __bit_iterator<_Cp, false> > 197 __rotate(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __middle, __bit_iterator<_Cp, false> __last) { 198 using _I1 = __bit_iterator<_Cp, false>; 199 using difference_type = typename _I1::difference_type; 200 difference_type __d1 = __middle - __first; 201 difference_type __d2 = __last - __middle; 202 _I1 __r = __first + __d2; 203 while (__d1 != 0 && __d2 != 0) { 204 if (__d1 <= __d2) { 205 if (__d1 <= __bit_array<_Cp>::capacity()) { 206 __bit_array<_Cp> __b(__d1); 207 std::copy(__first, __middle, __b.begin()); 208 std::copy(__b.begin(), __b.end(), std::copy(__middle, __last, __first)); 209 break; 210 } else { 211 __bit_iterator<_Cp, false> __mp = std::swap_ranges(__first, __middle, __middle); 212 __first = __middle; 213 __middle = __mp; 214 __d2 -= __d1; 215 } 216 } else { 217 if (__d2 <= __bit_array<_Cp>::capacity()) { 218 __bit_array<_Cp> __b(__d2); 219 std::copy(__middle, __last, __b.begin()); 220 std::copy_backward(__b.begin(), __b.end(), std::copy_backward(__first, __middle, __last)); 221 break; 222 } else { 223 __bit_iterator<_Cp, false> __mp = __first + __d2; 224 std::swap_ranges(__first, __mp, __middle); 225 __first = __mp; 226 __d1 -= __d2; 227 } 228 } 229 } 230 return std::make_pair(__r, __last); 231 } 232 233 template <class _ForwardIterator> 234 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator 235 rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last) { 236 return std::__rotate<_ClassicAlgPolicy>(std::move(__first), std::move(__middle), std::move(__last)).first; 237 } 238 239 _LIBCPP_END_NAMESPACE_STD 240 241 _LIBCPP_POP_MACROS 242 243 #endif // _LIBCPP___ALGORITHM_ROTATE_H 244