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 <__iterator/next.h> 19 #include <__iterator/prev.h> 20 #include <__utility/move.h> 21 #include <__utility/swap.h> 22 #include <type_traits> 23 24 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 25 # pragma GCC system_header 26 #endif 27 28 _LIBCPP_BEGIN_NAMESPACE_STD 29 30 template <class _AlgPolicy, class _ForwardIterator> 31 _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator 32 __rotate_left(_ForwardIterator __first, _ForwardIterator __last) 33 { 34 typedef typename iterator_traits<_ForwardIterator>::value_type value_type; 35 value_type __tmp = _IterOps<_AlgPolicy>::__iter_move(__first); 36 // TODO(ranges): pass `_AlgPolicy` to `move`. 37 _ForwardIterator __lm1 = _VSTD::move(_VSTD::next(__first), __last, __first); 38 *__lm1 = _VSTD::move(__tmp); 39 return __lm1; 40 } 41 42 template <class _AlgPolicy, class _BidirectionalIterator> 43 _LIBCPP_CONSTEXPR_AFTER_CXX11 _BidirectionalIterator 44 __rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last) 45 { 46 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 47 // TODO(ranges): pass `_AlgPolicy` to `prev`. 48 _BidirectionalIterator __lm1 = _VSTD::prev(__last); 49 value_type __tmp = _IterOps<_AlgPolicy>::__iter_move(__lm1); 50 // TODO(ranges): pass `_AlgPolicy` to `move_backward`. 51 _BidirectionalIterator __fp1 = _VSTD::move_backward(__first, __lm1, __last); 52 *__first = _VSTD::move(__tmp); 53 return __fp1; 54 } 55 56 template <class _AlgPolicy, class _ForwardIterator> 57 _LIBCPP_CONSTEXPR_AFTER_CXX14 _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_AFTER_CXX14 _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_CONSTEXPR_AFTER_CXX14 _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 112 const difference_type __m1 = __middle - __first; 113 const difference_type __m2 = __last - __middle; 114 if (__m1 == __m2) 115 { 116 // TODO(ranges): pass `_AlgPolicy` to `swap_ranges`. 117 _VSTD::swap_ranges(__first, __middle, __middle); 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(_IterOps<_AlgPolicy>::__iter_move(--__p)); 124 _RandomAccessIterator __p1 = __p; 125 _RandomAccessIterator __p2 = __p1 + __m1; 126 do 127 { 128 *__p1 = _IterOps<_AlgPolicy>::__iter_move(__p2); 129 __p1 = __p2; 130 const difference_type __d = __last - __p2; 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_AFTER_CXX11 _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_AFTER_CXX11 _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_AFTER_CXX11 _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 _RandomAccessIterator, class _IterCategory> 192 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 193 _RandomAccessIterator __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, 194 _RandomAccessIterator __last, _IterCategory __iter_category) { 195 if (__first == __middle) 196 return __last; 197 if (__middle == __last) 198 return __first; 199 200 return std::__rotate_impl<_AlgPolicy>(std::move(__first), std::move(__middle), std::move(__last), __iter_category); 201 } 202 203 template <class _ForwardIterator> 204 inline _LIBCPP_INLINE_VISIBILITY 205 _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator 206 rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last) 207 { 208 return std::__rotate<_ClassicAlgPolicy>(__first, __middle, __last, 209 typename iterator_traits<_ForwardIterator>::iterator_category()); 210 } 211 212 _LIBCPP_END_NAMESPACE_STD 213 214 #endif // _LIBCPP___ALGORITHM_ROTATE_H 215