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