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_SHIFT_RIGHT_H
10 #define _LIBCPP___ALGORITHM_SHIFT_RIGHT_H
11 
12 #include <__config>
13 #include <__algorithm/move.h>
14 #include <__algorithm/move_backward.h>
15 #include <__algorithm/swap_ranges.h>
16 #include <__iterator/iterator_traits.h>
17 #include <type_traits> // swap
18 
19 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
20 #pragma GCC system_header
21 #endif
22 
23 _LIBCPP_PUSH_MACROS
24 #include <__undef_macros>
25 
26 _LIBCPP_BEGIN_NAMESPACE_STD
27 
28 #if _LIBCPP_STD_VER > 17
29 
30 template <class _ForwardIterator>
31 inline _LIBCPP_INLINE_VISIBILITY constexpr
32 _ForwardIterator
shift_right(_ForwardIterator __first,_ForwardIterator __last,typename iterator_traits<_ForwardIterator>::difference_type __n)33 shift_right(_ForwardIterator __first, _ForwardIterator __last,
34             typename iterator_traits<_ForwardIterator>::difference_type __n)
35 {
36     if (__n == 0) {
37         return __first;
38     }
39 
40     if constexpr (__is_cpp17_random_access_iterator<_ForwardIterator>::value) {
41         decltype(__n) __d = __last - __first;
42         if (__n >= __d) {
43             return __last;
44         }
45         _ForwardIterator __m = __first + (__d - __n);
46         return _VSTD::move_backward(__first, __m, __last);
47     } else if constexpr (__is_cpp17_bidirectional_iterator<_ForwardIterator>::value) {
48         _ForwardIterator __m = __last;
49         for (; __n > 0; --__n) {
50             if (__m == __first) {
51                 return __last;
52             }
53             --__m;
54         }
55         return _VSTD::move_backward(__first, __m, __last);
56     } else {
57         _ForwardIterator __ret = __first;
58         for (; __n > 0; --__n) {
59             if (__ret == __last) {
60                 return __last;
61             }
62             ++__ret;
63         }
64 
65         // We have an __n-element scratch space from __first to __ret.
66         // Slide an __n-element window [__trail, __lead) from left to right.
67         // We're essentially doing swap_ranges(__first, __ret, __trail, __lead)
68         // over and over; but once __lead reaches __last we needn't bother
69         // to save the values of elements [__trail, __last).
70 
71         auto __trail = __first;
72         auto __lead = __ret;
73         while (__trail != __ret) {
74             if (__lead == __last) {
75                 _VSTD::move(__first, __trail, __ret);
76                 return __ret;
77             }
78             ++__trail;
79             ++__lead;
80         }
81 
82         _ForwardIterator __mid = __first;
83         while (true) {
84             if (__lead == __last) {
85                 __trail = _VSTD::move(__mid, __ret, __trail);
86                 _VSTD::move(__first, __mid, __trail);
87                 return __ret;
88             }
89             swap(*__mid, *__trail);
90             ++__mid;
91             ++__trail;
92             ++__lead;
93             if (__mid == __ret) {
94                 __mid = __first;
95             }
96         }
97     }
98 }
99 
100 #endif // _LIBCPP_STD_VER > 17
101 
102 _LIBCPP_END_NAMESPACE_STD
103 
104 _LIBCPP_POP_MACROS
105 
106 #endif // _LIBCPP___ALGORITHM_SHIFT_RIGHT_H
107