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