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