197 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___CXX03___ALGORITHM_ROTATE_H10#define _LIBCPP___CXX03___ALGORITHM_ROTATE_H11 12#include <__cxx03/__algorithm/iterator_operations.h>13#include <__cxx03/__algorithm/move.h>14#include <__cxx03/__algorithm/move_backward.h>15#include <__cxx03/__algorithm/swap_ranges.h>16#include <__cxx03/__config>17#include <__cxx03/__iterator/iterator_traits.h>18#include <__cxx03/__type_traits/is_trivially_assignable.h>19#include <__cxx03/__utility/move.h>20#include <__cxx03/__utility/pair.h>21 22#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)23# pragma GCC system_header24#endif25 26_LIBCPP_PUSH_MACROS27#include <__cxx03/__undef_macros>28 29_LIBCPP_BEGIN_NAMESPACE_STD30 31template <class _AlgPolicy, class _ForwardIterator>32_LIBCPP_HIDE_FROM_ABI _ForwardIterator __rotate_left(_ForwardIterator __first, _ForwardIterator __last) {33 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;34 using _Ops = _IterOps<_AlgPolicy>;35 36 value_type __tmp = _Ops::__iter_move(__first);37 _ForwardIterator __lm1 = std::__move<_AlgPolicy>(_Ops::next(__first), __last, __first).second;38 *__lm1 = std::move(__tmp);39 return __lm1;40}41 42template <class _AlgPolicy, class _BidirectionalIterator>43_LIBCPP_HIDE_FROM_ABI _BidirectionalIterator44__rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last) {45 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;46 using _Ops = _IterOps<_AlgPolicy>;47 48 _BidirectionalIterator __lm1 = _Ops::prev(__last);49 value_type __tmp = _Ops::__iter_move(__lm1);50 _BidirectionalIterator __fp1 = std::__move_backward<_AlgPolicy>(__first, __lm1, std::move(__last)).second;51 *__first = std::move(__tmp);52 return __fp1;53}54 55template <class _AlgPolicy, class _ForwardIterator>56_LIBCPP_HIDE_FROM_ABI _ForwardIterator57__rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last) {58 _ForwardIterator __i = __middle;59 while (true) {60 _IterOps<_AlgPolicy>::iter_swap(__first, __i);61 ++__first;62 if (++__i == __last)63 break;64 if (__first == __middle)65 __middle = __i;66 }67 _ForwardIterator __r = __first;68 if (__first != __middle) {69 __i = __middle;70 while (true) {71 _IterOps<_AlgPolicy>::iter_swap(__first, __i);72 ++__first;73 if (++__i == __last) {74 if (__first == __middle)75 break;76 __i = __middle;77 } else if (__first == __middle)78 __middle = __i;79 }80 }81 return __r;82}83 84template <typename _Integral>85inline _LIBCPP_HIDE_FROM_ABI _Integral __algo_gcd(_Integral __x, _Integral __y) {86 do {87 _Integral __t = __x % __y;88 __x = __y;89 __y = __t;90 } while (__y);91 return __x;92}93 94template <class _AlgPolicy, typename _RandomAccessIterator>95_LIBCPP_HIDE_FROM_ABI _RandomAccessIterator96__rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last) {97 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;98 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;99 using _Ops = _IterOps<_AlgPolicy>;100 101 const difference_type __m1 = __middle - __first;102 const difference_type __m2 = _Ops::distance(__middle, __last);103 if (__m1 == __m2) {104 std::__swap_ranges<_AlgPolicy>(__first, __middle, __middle, __last);105 return __middle;106 }107 const difference_type __g = std::__algo_gcd(__m1, __m2);108 for (_RandomAccessIterator __p = __first + __g; __p != __first;) {109 value_type __t(_Ops::__iter_move(--__p));110 _RandomAccessIterator __p1 = __p;111 _RandomAccessIterator __p2 = __p1 + __m1;112 do {113 *__p1 = _Ops::__iter_move(__p2);114 __p1 = __p2;115 const difference_type __d = _Ops::distance(__p2, __last);116 if (__m1 < __d)117 __p2 += __m1;118 else119 __p2 = __first + (__m1 - __d);120 } while (__p2 != __p);121 *__p1 = std::move(__t);122 }123 return __first + __m2;124}125 126template <class _AlgPolicy, class _ForwardIterator>127inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator128__rotate_impl(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, std::forward_iterator_tag) {129 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;130 if (is_trivially_move_assignable<value_type>::value) {131 if (_IterOps<_AlgPolicy>::next(__first) == __middle)132 return std::__rotate_left<_AlgPolicy>(__first, __last);133 }134 return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last);135}136 137template <class _AlgPolicy, class _BidirectionalIterator>138inline _LIBCPP_HIDE_FROM_ABI _BidirectionalIterator __rotate_impl(139 _BidirectionalIterator __first,140 _BidirectionalIterator __middle,141 _BidirectionalIterator __last,142 bidirectional_iterator_tag) {143 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;144 if (is_trivially_move_assignable<value_type>::value) {145 if (_IterOps<_AlgPolicy>::next(__first) == __middle)146 return std::__rotate_left<_AlgPolicy>(__first, __last);147 if (_IterOps<_AlgPolicy>::next(__middle) == __last)148 return std::__rotate_right<_AlgPolicy>(__first, __last);149 }150 return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last);151}152 153template <class _AlgPolicy, class _RandomAccessIterator>154inline _LIBCPP_HIDE_FROM_ABI _RandomAccessIterator __rotate_impl(155 _RandomAccessIterator __first,156 _RandomAccessIterator __middle,157 _RandomAccessIterator __last,158 random_access_iterator_tag) {159 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;160 if (is_trivially_move_assignable<value_type>::value) {161 if (_IterOps<_AlgPolicy>::next(__first) == __middle)162 return std::__rotate_left<_AlgPolicy>(__first, __last);163 if (_IterOps<_AlgPolicy>::next(__middle) == __last)164 return std::__rotate_right<_AlgPolicy>(__first, __last);165 return std::__rotate_gcd<_AlgPolicy>(__first, __middle, __last);166 }167 return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last);168}169 170template <class _AlgPolicy, class _Iterator, class _Sentinel>171_LIBCPP_HIDE_FROM_ABI pair<_Iterator, _Iterator> __rotate(_Iterator __first, _Iterator __middle, _Sentinel __last) {172 using _Ret = pair<_Iterator, _Iterator>;173 _Iterator __last_iter = _IterOps<_AlgPolicy>::next(__middle, __last);174 175 if (__first == __middle)176 return _Ret(__last_iter, __last_iter);177 if (__middle == __last)178 return _Ret(std::move(__first), std::move(__last_iter));179 180 using _IterCategory = typename _IterOps<_AlgPolicy>::template __iterator_category<_Iterator>;181 auto __result = std::__rotate_impl<_AlgPolicy>(std::move(__first), std::move(__middle), __last_iter, _IterCategory());182 183 return _Ret(std::move(__result), std::move(__last_iter));184}185 186template <class _ForwardIterator>187inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator188rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last) {189 return std::__rotate<_ClassicAlgPolicy>(std::move(__first), std::move(__middle), std::move(__last)).first;190}191 192_LIBCPP_END_NAMESPACE_STD193 194_LIBCPP_POP_MACROS195 196#endif // _LIBCPP___CXX03___ALGORITHM_ROTATE_H197