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