rotate.h revision 1.1.1.1 
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
31template <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
42template <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
54template <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
89template<typename _Integral>
90inline _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
103template<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
138template <class _ForwardIterator>
139inline _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
153template <class _BidirectionalIterator>
154inline _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
170template <class _RandomAccessIterator>
171inline _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
188template <class _ForwardIterator>
189inline _LIBCPP_INLINE_VISIBILITY
190_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
191rotate(_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