__cxx03/__algorithm/shift_right.h

0001 //===----------------------------------------------------------------------===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef _LIBCPP___CXX03___ALGORITHM_SHIFT_RIGHT_H
0010 #define _LIBCPP___CXX03___ALGORITHM_SHIFT_RIGHT_H
0011
0012 #include <__cxx03/__algorithm/move.h>
0013 #include <__cxx03/__algorithm/move_backward.h>
0014 #include <__cxx03/__algorithm/swap_ranges.h>
0015 #include <__cxx03/__config>
0016 #include <__cxx03/__iterator/iterator_traits.h>
0017 #include <__cxx03/__utility/swap.h>
0018
0019 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0020 #  pragma GCC system_header
0021 #endif
0022
0023 _LIBCPP_PUSH_MACROS
0024 #include <__cxx03/__undef_macros>
0025
0026 _LIBCPP_BEGIN_NAMESPACE_STD
0027
0028 #if _LIBCPP_STD_VER >= 20
0029
0030 template <class _ForwardIterator>
0031 inline _LIBCPP_HIDE_FROM_ABI constexpr _ForwardIterator
0032 shift_right(_ForwardIterator __first,
0033             _ForwardIterator __last,
0034             typename iterator_traits<_ForwardIterator>::difference_type __n) {
0035   if (__n == 0) {
0036     return __first;
0037   }
0038
0039   if constexpr (__has_random_access_iterator_category<_ForwardIterator>::value) {
0040     decltype(__n) __d = __last - __first;
0041     if (__n >= __d) {
0042       return __last;
0043     }
0044     _ForwardIterator __m = __first + (__d - __n);
0045     return std::move_backward(__first, __m, __last);
0046   } else if constexpr (__has_bidirectional_iterator_category<_ForwardIterator>::value) {
0047     _ForwardIterator __m = __last;
0048     for (; __n > 0; --__n) {
0049       if (__m == __first) {
0050         return __last;
0051       }
0052       --__m;
0053     }
0054     return std::move_backward(__first, __m, __last);
0055   } else {
0056     _ForwardIterator __ret = __first;
0057     for (; __n > 0; --__n) {
0058       if (__ret == __last) {
0059         return __last;
0060       }
0061       ++__ret;
0062     }
0063
0064     // We have an __n-element scratch space from __first to __ret.
0065     // Slide an __n-element window [__trail, __lead) from left to right.
0066     // We're essentially doing swap_ranges(__first, __ret, __trail, __lead)
0067     // over and over; but once __lead reaches __last we needn't bother
0068     // to save the values of elements [__trail, __last).
0069
0070     auto __trail = __first;
0071     auto __lead  = __ret;
0072     while (__trail != __ret) {
0073       if (__lead == __last) {
0074         std::move(__first, __trail, __ret);
0075         return __ret;
0076       }
0077       ++__trail;
0078       ++__lead;
0079     }
0080
0081     _ForwardIterator __mid = __first;
0082     while (true) {
0083       if (__lead == __last) {
0084         __trail = std::move(__mid, __ret, __trail);
0085         std::move(__first, __mid, __trail);
0086         return __ret;
0087       }
0088       swap(*__mid, *__trail);
0089       ++__mid;
0090       ++__trail;
0091       ++__lead;
0092       if (__mid == __ret) {
0093         __mid = __first;
0094       }
0095     }
0096   }
0097 }
0098
0099 #endif // _LIBCPP_STD_VER >= 20
0100
0101 _LIBCPP_END_NAMESPACE_STD
0102
0103 _LIBCPP_POP_MACROS
0104
0105 #endif // _LIBCPP___CXX03___ALGORITHM_SHIFT_RIGHT_H