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