200 lines · c
1// -*- C++ -*-2//===----------------------------------------------------------------------===//3//4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5// See https://llvm.org/LICENSE.txt for license information.6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___ITERATOR_ADVANCE_H11#define _LIBCPP___ITERATOR_ADVANCE_H12 13#include <__assert>14#include <__concepts/assignable.h>15#include <__concepts/same_as.h>16#include <__config>17#include <__iterator/concepts.h>18#include <__iterator/incrementable_traits.h>19#include <__iterator/iterator_traits.h>20#include <__type_traits/enable_if.h>21#include <__type_traits/is_integral.h>22#include <__utility/convert_to_integral.h>23#include <__utility/declval.h>24#include <__utility/move.h>25#include <__utility/unreachable.h>26#include <limits>27 28#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)29# pragma GCC system_header30#endif31 32_LIBCPP_PUSH_MACROS33#include <__undef_macros>34 35_LIBCPP_BEGIN_NAMESPACE_STD36 37template <class _InputIter>38_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 void39__advance(_InputIter& __i, typename iterator_traits<_InputIter>::difference_type __n, input_iterator_tag) {40 for (; __n > 0; --__n)41 ++__i;42}43 44template <class _BiDirIter>45_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 void46__advance(_BiDirIter& __i, typename iterator_traits<_BiDirIter>::difference_type __n, bidirectional_iterator_tag) {47 if (__n >= 0)48 for (; __n > 0; --__n)49 ++__i;50 else51 for (; __n < 0; ++__n)52 --__i;53}54 55template <class _RandIter>56_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 void57__advance(_RandIter& __i, typename iterator_traits<_RandIter>::difference_type __n, random_access_iterator_tag) {58 __i += __n;59}60 61template < class _InputIter,62 class _Distance,63 class _IntegralDistance = decltype(std::__convert_to_integral(std::declval<_Distance>())),64 __enable_if_t<is_integral<_IntegralDistance>::value, int> = 0>65_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 void advance(_InputIter& __i, _Distance __orig_n) {66 typedef typename iterator_traits<_InputIter>::difference_type _Difference;67 _Difference __n = static_cast<_Difference>(std::__convert_to_integral(__orig_n));68 _LIBCPP_ASSERT_PEDANTIC(__has_bidirectional_iterator_category<_InputIter>::value || __n >= 0,69 "std::advance: Can only pass a negative `n` with a bidirectional_iterator.");70 std::__advance(__i, __n, typename iterator_traits<_InputIter>::iterator_category());71}72 73#if _LIBCPP_STD_VER >= 2074 75// [range.iter.op.advance]76 77namespace ranges {78struct __advance {79private:80 template <class _Ip>81 _LIBCPP_HIDE_FROM_ABI static constexpr void __advance_forward(_Ip& __i, iter_difference_t<_Ip> __n) {82 while (__n > 0) {83 --__n;84 ++__i;85 }86 }87 88 template <class _Ip>89 _LIBCPP_HIDE_FROM_ABI static constexpr void __advance_backward(_Ip& __i, iter_difference_t<_Ip> __n) {90 while (__n < 0) {91 ++__n;92 --__i;93 }94 }95 96public:97 // Preconditions: If `I` does not model `bidirectional_iterator`, `n` is not negative.98 template <input_or_output_iterator _Ip>99 _LIBCPP_HIDE_FROM_ABI constexpr void operator()(_Ip& __i, iter_difference_t<_Ip> __n) const {100 _LIBCPP_ASSERT_PEDANTIC(bidirectional_iterator<_Ip> || __n >= 0,101 "ranges::advance: Can only pass a negative `n` with a bidirectional_iterator.");102 103 // If `I` models `random_access_iterator`, equivalent to `i += n`.104 if constexpr (random_access_iterator<_Ip>) {105 __i += __n;106 return;107 } else if constexpr (bidirectional_iterator<_Ip>) {108 // Otherwise, if `n` is non-negative, increments `i` by `n`.109 __advance_forward(__i, __n);110 // Otherwise, decrements `i` by `-n`.111 __advance_backward(__i, __n);112 return;113 } else {114 // Otherwise, if `n` is non-negative, increments `i` by `n`.115 __advance_forward(__i, __n);116 return;117 }118 }119 120 // Preconditions: Either `assignable_from<I&, S> || sized_sentinel_for<S, I>` is modeled, or [i, bound_sentinel)121 // denotes a range.122 template <input_or_output_iterator _Ip, sentinel_for<_Ip> _Sp>123 _LIBCPP_HIDE_FROM_ABI constexpr void operator()(_Ip& __i, _Sp __bound_sentinel) const {124 // If `I` and `S` model `assignable_from<I&, S>`, equivalent to `i = std::move(bound_sentinel)`.125 if constexpr (assignable_from<_Ip&, _Sp>) {126 __i = std::move(__bound_sentinel);127 }128 // Otherwise, if `S` and `I` model `sized_sentinel_for<S, I>`, equivalent to `ranges::advance(i, bound_sentinel -129 // i)`.130 else if constexpr (sized_sentinel_for<_Sp, _Ip>) {131 (*this)(__i, __bound_sentinel - __i);132 }133 // Otherwise, while `bool(i != bound_sentinel)` is true, increments `i`.134 else {135 while (__i != __bound_sentinel) {136 ++__i;137 }138 }139 }140 141 // Preconditions:142 // * If `n > 0`, [i, bound_sentinel) denotes a range.143 // * If `n == 0`, [i, bound_sentinel) or [bound_sentinel, i) denotes a range.144 // * If `n < 0`, [bound_sentinel, i) denotes a range, `I` models `bidirectional_iterator`, and `I` and `S` model145 // `same_as<I, S>`.146 // Returns: `n - M`, where `M` is the difference between the ending and starting position.147 template <input_or_output_iterator _Ip, sentinel_for<_Ip> _Sp>148 _LIBCPP_HIDE_FROM_ABI constexpr iter_difference_t<_Ip>149 operator()(_Ip& __i, iter_difference_t<_Ip> __n, _Sp __bound_sentinel) const {150 _LIBCPP_ASSERT_PEDANTIC(151 (bidirectional_iterator<_Ip> && same_as<_Ip, _Sp>) || (__n >= 0),152 "ranges::advance: Can only pass a negative `n` with a bidirectional_iterator coming from a common_range.");153 // If `S` and `I` model `sized_sentinel_for<S, I>`:154 if constexpr (sized_sentinel_for<_Sp, _Ip>) {155 // If |n| >= |bound_sentinel - i|, equivalent to `ranges::advance(i, bound_sentinel)`.156 // __magnitude_geq(a, b) returns |a| >= |b|, assuming they have the same sign.157 auto __magnitude_geq = [](auto __a, auto __b) { return __a == 0 ? __b == 0 : __a > 0 ? __a >= __b : __a <= __b; };158 if (const auto __m = __bound_sentinel - __i; __magnitude_geq(__n, __m)) {159 (*this)(__i, __bound_sentinel);160 return __n - __m;161 }162 163 // Otherwise, equivalent to `ranges::advance(i, n)`.164 (*this)(__i, __n);165 return 0;166 } else {167 // Otherwise, if `n` is non-negative, while `bool(i != bound_sentinel)` is true, increments `i` but at168 // most `n` times.169 while (__n > 0 && __i != __bound_sentinel) {170 ++__i;171 --__n;172 }173 174 // Otherwise, while `bool(i != bound_sentinel)` is true, decrements `i` but at most `-n` times.175 if constexpr (bidirectional_iterator<_Ip> && same_as<_Ip, _Sp>) {176 while (__n < 0 && __i != __bound_sentinel) {177 --__i;178 ++__n;179 }180 }181 return __n;182 }183 184 __libcpp_unreachable();185 }186};187 188inline namespace __cpo {189inline constexpr auto advance = __advance{};190} // namespace __cpo191} // namespace ranges192 193#endif // _LIBCPP_STD_VER >= 20194 195_LIBCPP_END_NAMESPACE_STD196 197_LIBCPP_POP_MACROS198 199#endif // _LIBCPP___ITERATOR_ADVANCE_H200