244 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef _LIBCPP___ALGORITHM_ROTATE_H10#define _LIBCPP___ALGORITHM_ROTATE_H11 12#include <__algorithm/copy.h>13#include <__algorithm/copy_backward.h>14#include <__algorithm/iterator_operations.h>15#include <__algorithm/move.h>16#include <__algorithm/move_backward.h>17#include <__algorithm/swap_ranges.h>18#include <__config>19#include <__cstddef/size_t.h>20#include <__fwd/bit_reference.h>21#include <__iterator/iterator_traits.h>22#include <__memory/construct_at.h>23#include <__memory/pointer_traits.h>24#include <__type_traits/is_constant_evaluated.h>25#include <__type_traits/is_trivially_assignable.h>26#include <__utility/move.h>27#include <__utility/pair.h>28 29#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)30# pragma GCC system_header31#endif32 33_LIBCPP_PUSH_MACROS34#include <__undef_macros>35 36_LIBCPP_BEGIN_NAMESPACE_STD37 38template <class _AlgPolicy, class _ForwardIterator>39_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _ForwardIterator40__rotate_left(_ForwardIterator __first, _ForwardIterator __last) {41 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;42 using _Ops = _IterOps<_AlgPolicy>;43 44 value_type __tmp = _Ops::__iter_move(__first);45 _ForwardIterator __lm1 = std::__move<_AlgPolicy>(_Ops::next(__first), __last, __first).second;46 *__lm1 = std::move(__tmp);47 return __lm1;48}49 50template <class _AlgPolicy, class _BidirectionalIterator>51_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _BidirectionalIterator52__rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last) {53 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;54 using _Ops = _IterOps<_AlgPolicy>;55 56 _BidirectionalIterator __lm1 = _Ops::prev(__last);57 value_type __tmp = _Ops::__iter_move(__lm1);58 _BidirectionalIterator __fp1 = std::__move_backward<_AlgPolicy>(__first, __lm1, std::move(__last)).second;59 *__first = std::move(__tmp);60 return __fp1;61}62 63template <class _AlgPolicy, class _ForwardIterator>64_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 _ForwardIterator65__rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last) {66 _ForwardIterator __i = __middle;67 while (true) {68 _IterOps<_AlgPolicy>::iter_swap(__first, __i);69 ++__first;70 if (++__i == __last)71 break;72 if (__first == __middle)73 __middle = __i;74 }75 _ForwardIterator __r = __first;76 if (__first != __middle) {77 __i = __middle;78 while (true) {79 _IterOps<_AlgPolicy>::iter_swap(__first, __i);80 ++__first;81 if (++__i == __last) {82 if (__first == __middle)83 break;84 __i = __middle;85 } else if (__first == __middle)86 __middle = __i;87 }88 }89 return __r;90}91 92template <typename _Integral>93inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 _Integral __algo_gcd(_Integral __x, _Integral __y) {94 do {95 _Integral __t = __x % __y;96 __x = __y;97 __y = __t;98 } while (__y);99 return __x;100}101 102template <class _AlgPolicy, typename _RandomAccessIterator>103_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 _RandomAccessIterator104__rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last) {105 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;106 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;107 using _Ops = _IterOps<_AlgPolicy>;108 109 const difference_type __m1 = __middle - __first;110 const difference_type __m2 = _Ops::distance(__middle, __last);111 if (__m1 == __m2) {112 std::__swap_ranges<_AlgPolicy>(__first, __middle, __middle, __last);113 return __middle;114 }115 const difference_type __g = std::__algo_gcd(__m1, __m2);116 for (_RandomAccessIterator __p = __first + __g; __p != __first;) {117 value_type __t(_Ops::__iter_move(--__p));118 _RandomAccessIterator __p1 = __p;119 _RandomAccessIterator __p2 = __p1 + __m1;120 do {121 *__p1 = _Ops::__iter_move(__p2);122 __p1 = __p2;123 const difference_type __d = _Ops::distance(__p2, __last);124 if (__m1 < __d)125 __p2 += __m1;126 else127 __p2 = __first + (__m1 - __d);128 } while (__p2 != __p);129 *__p1 = std::move(__t);130 }131 return __first + __m2;132}133 134template <class _AlgPolicy, class _ForwardIterator>135inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _ForwardIterator136__rotate_impl(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, std::forward_iterator_tag) {137 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;138 if (is_trivially_move_assignable<value_type>::value) {139 if (_IterOps<_AlgPolicy>::next(__first) == __middle)140 return std::__rotate_left<_AlgPolicy>(__first, __last);141 }142 return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last);143}144 145template <class _AlgPolicy, class _BidirectionalIterator>146inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _BidirectionalIterator __rotate_impl(147 _BidirectionalIterator __first,148 _BidirectionalIterator __middle,149 _BidirectionalIterator __last,150 bidirectional_iterator_tag) {151 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;152 if (is_trivially_move_assignable<value_type>::value) {153 if (_IterOps<_AlgPolicy>::next(__first) == __middle)154 return std::__rotate_left<_AlgPolicy>(__first, __last);155 if (_IterOps<_AlgPolicy>::next(__middle) == __last)156 return std::__rotate_right<_AlgPolicy>(__first, __last);157 }158 return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last);159}160 161template <class _AlgPolicy, class _RandomAccessIterator>162inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _RandomAccessIterator __rotate_impl(163 _RandomAccessIterator __first,164 _RandomAccessIterator __middle,165 _RandomAccessIterator __last,166 random_access_iterator_tag) {167 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;168 if (is_trivially_move_assignable<value_type>::value) {169 if (_IterOps<_AlgPolicy>::next(__first) == __middle)170 return std::__rotate_left<_AlgPolicy>(__first, __last);171 if (_IterOps<_AlgPolicy>::next(__middle) == __last)172 return std::__rotate_right<_AlgPolicy>(__first, __last);173 return std::__rotate_gcd<_AlgPolicy>(__first, __middle, __last);174 }175 return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last);176}177 178template <class _AlgPolicy, class _Iterator, class _Sentinel>179_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_Iterator, _Iterator>180__rotate(_Iterator __first, _Iterator __middle, _Sentinel __last) {181 using _Ret = pair<_Iterator, _Iterator>;182 _Iterator __last_iter = _IterOps<_AlgPolicy>::next(__middle, __last);183 184 if (__first == __middle)185 return _Ret(__last_iter, __last_iter);186 if (__middle == __last)187 return _Ret(std::move(__first), std::move(__last_iter));188 189 using _IterCategory = typename _IterOps<_AlgPolicy>::template __iterator_category<_Iterator>;190 auto __result = std::__rotate_impl<_AlgPolicy>(std::move(__first), std::move(__middle), __last_iter, _IterCategory());191 192 return _Ret(std::move(__result), std::move(__last_iter));193}194 195template <class, class _Cp>196_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<__bit_iterator<_Cp, false>, __bit_iterator<_Cp, false> >197__rotate(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __middle, __bit_iterator<_Cp, false> __last) {198 using _I1 = __bit_iterator<_Cp, false>;199 using difference_type = typename _I1::difference_type;200 difference_type __d1 = __middle - __first;201 difference_type __d2 = __last - __middle;202 _I1 __r = __first + __d2;203 while (__d1 != 0 && __d2 != 0) {204 if (__d1 <= __d2) {205 if (__d1 <= __bit_array<_Cp>::capacity()) {206 __bit_array<_Cp> __b(__d1);207 std::copy(__first, __middle, __b.begin());208 std::copy(__b.begin(), __b.end(), std::copy(__middle, __last, __first));209 break;210 } else {211 __bit_iterator<_Cp, false> __mp = std::swap_ranges(__first, __middle, __middle);212 __first = __middle;213 __middle = __mp;214 __d2 -= __d1;215 }216 } else {217 if (__d2 <= __bit_array<_Cp>::capacity()) {218 __bit_array<_Cp> __b(__d2);219 std::copy(__middle, __last, __b.begin());220 std::copy_backward(__b.begin(), __b.end(), std::copy_backward(__first, __middle, __last));221 break;222 } else {223 __bit_iterator<_Cp, false> __mp = __first + __d2;224 std::swap_ranges(__first, __mp, __middle);225 __first = __mp;226 __d1 -= __d2;227 }228 }229 }230 return std::make_pair(__r, __last);231}232 233template <class _ForwardIterator>234inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator235rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last) {236 return std::__rotate<_ClassicAlgPolicy>(std::move(__first), std::move(__middle), std::move(__last)).first;237}238 239_LIBCPP_END_NAMESPACE_STD240 241_LIBCPP_POP_MACROS242 243#endif // _LIBCPP___ALGORITHM_ROTATE_H244