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