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