libcxx/include/__algorithm/rotate.h

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