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_ITERATOR_OPERATIONS_H
10#define _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H
11
12#include <__algorithm/iter_swap.h>
13#include <__algorithm/ranges_iterator_concept.h>
14#include <__assert>
15#include <__config>
16#include <__iterator/advance.h>
17#include <__iterator/distance.h>
18#include <__iterator/incrementable_traits.h>
19#include <__iterator/iter_move.h>
20#include <__iterator/iter_swap.h>
21#include <__iterator/iterator_traits.h>
22#include <__iterator/next.h>
23#include <__iterator/prev.h>
24#include <__iterator/readable_traits.h>
25#include <__type_traits/enable_if.h>
26#include <__type_traits/is_reference.h>
27#include <__type_traits/is_same.h>
28#include <__type_traits/remove_cvref.h>
29#include <__utility/declval.h>
30#include <__utility/forward.h>
31#include <__utility/move.h>
32
33#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
34# pragma GCC system_header
35#endif
36
37_LIBCPP_PUSH_MACROS
38#include <__undef_macros>
39
40_LIBCPP_BEGIN_NAMESPACE_STD
41
42template <class _AlgPolicy>
43struct _IterOps;
44
45#if _LIBCPP_STD_VER >= 20
46struct _RangeAlgPolicy {};
47
48template <>
49struct _IterOps<_RangeAlgPolicy> {
50 template <class _Iter>
51 using __value_type _LIBCPP_NODEBUG = iter_value_t<_Iter>;
52
53 template <class _Iter>
54 using __iterator_category _LIBCPP_NODEBUG = ranges::__iterator_concept<_Iter>;
55
56 template <class _Iter>
57 using __difference_type _LIBCPP_NODEBUG = iter_difference_t<_Iter>;
58
59 static constexpr auto advance = ranges::advance;
60 static constexpr auto distance = ranges::distance;
61 static constexpr auto __iter_move = ranges::iter_move;
62 static constexpr auto iter_swap = ranges::iter_swap;
63 static constexpr auto next = ranges::next;
64 static constexpr auto prev = ranges::prev;
65 static constexpr auto __advance_to = ranges::advance;
66};
67
68#endif
69
70struct _ClassicAlgPolicy {};
71
72template <>
73struct _IterOps<_ClassicAlgPolicy> {
74 template <class _Iter>
75 using __value_type _LIBCPP_NODEBUG = typename iterator_traits<_Iter>::value_type;
76
77 template <class _Iter>
78 using __iterator_category _LIBCPP_NODEBUG = typename iterator_traits<_Iter>::iterator_category;
79
80 template <class _Iter>
81 using __difference_type _LIBCPP_NODEBUG = typename iterator_traits<_Iter>::difference_type;
82
83 // advance
84 template <class _Iter, class _Distance>
85 _LIBCPP_CONSTEXPR_SINCE_CXX14 static void advance(_Iter& __iter, _Distance __count) {
86 std::advance(__iter, __count);
87 }
88
89 // distance
90 template <class _Iter>
91 _LIBCPP_CONSTEXPR_SINCE_CXX14 static typename iterator_traits<_Iter>::difference_type
92 distance(_Iter __first, _Iter __last) {
93 return std::distance(__first, __last);
94 }
95
96 template <class _Iter>
97 using __deref_t _LIBCPP_NODEBUG = decltype(*std::declval<_Iter&>());
98
99 template <class _Iter>
100 using __move_t _LIBCPP_NODEBUG = decltype(std::move(*std::declval<_Iter&>()));
101
102 template <class _Iter>
103 _LIBCPP_CONSTEXPR_SINCE_CXX14 static void __validate_iter_reference() {
104 static_assert(
105 is_same<__deref_t<_Iter>, typename iterator_traits<__remove_cvref_t<_Iter> >::reference>::value,
106 "It looks like your iterator's `iterator_traits<It>::reference` does not match the return type of "
107 "dereferencing the iterator, i.e., calling `*it`. This is undefined behavior according to [input.iterators] "
108 "and can lead to dangling reference issues at runtime, so we are flagging this.");
109 }
110
111 // iter_move
112 template <class _Iter, __enable_if_t<is_reference<__deref_t<_Iter> >::value, int> = 0>
113 _LIBCPP_CONSTEXPR_SINCE_CXX14 static
114 // If the result of dereferencing `_Iter` is a reference type, deduce the result of calling `std::move` on it.
115 // Note that the C++03 mode doesn't support `decltype(auto)` as the return type.
116 __move_t<_Iter> __iter_move(_Iter&& __i) {
117 __validate_iter_reference<_Iter>();
118
119 return std::move(*std::forward<_Iter>(__i));
120 }
121
122 template <class _Iter, __enable_if_t<!is_reference<__deref_t<_Iter> >::value, int> = 0>
123 _LIBCPP_CONSTEXPR_SINCE_CXX14 static
124 // If the result of dereferencing `_Iter` is a value type, deduce the return value of this function to also be a
125 // value -- otherwise, after `operator*` returns a temporary, this function would return a dangling reference to
126 // that temporary. Note that the C++03 mode doesn't support `auto` as the return type.
127 __deref_t<_Iter> __iter_move(_Iter&& __i) {
128 __validate_iter_reference<_Iter>();
129
130 return *std::forward<_Iter>(__i);
131 }
132
133 // iter_swap
134 template <class _Iter1, class _Iter2>
135 _LIBCPP_CONSTEXPR_SINCE_CXX14 static void iter_swap(_Iter1&& __a, _Iter2&& __b) {
136 std::iter_swap(std::forward<_Iter1>(__a), std::forward<_Iter2>(__b));
137 }
138
139 // next
140 template <class _Iterator>
141 static _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iterator next(_Iterator, _Iterator __last) {
142 return __last;
143 }
144
145 template <class _Iter>
146 static _LIBCPP_CONSTEXPR_SINCE_CXX14 __remove_cvref_t<_Iter>
147 next(_Iter&& __it, typename iterator_traits<__remove_cvref_t<_Iter> >::difference_type __n = 1) {
148 return std::next(std::forward<_Iter>(__it), __n);
149 }
150
151 // prev
152 template <class _Iter>
153 static _LIBCPP_CONSTEXPR_SINCE_CXX14 __remove_cvref_t<_Iter>
154 prev(_Iter&& __iter, typename iterator_traits<__remove_cvref_t<_Iter> >::difference_type __n = 1) {
155 return std::prev(std::forward<_Iter>(__iter), __n);
156 }
157
158 template <class _Iter>
159 static _LIBCPP_CONSTEXPR_SINCE_CXX14 void __advance_to(_Iter& __first, _Iter __last) {
160 __first = __last;
161 }
162
163 // advance with sentinel, a la std::ranges::advance
164 template <class _Iter>
165 _LIBCPP_CONSTEXPR_SINCE_CXX14 static __difference_type<_Iter>
166 __advance_to(_Iter& __iter, __difference_type<_Iter> __count, const _Iter& __sentinel) {
167 return _IterOps::__advance_to(__iter, __count, __sentinel, typename iterator_traits<_Iter>::iterator_category());
168 }
169
170private:
171 // advance with sentinel, a la std::ranges::advance -- InputIterator specialization
172 template <class _InputIter>
173 _LIBCPP_CONSTEXPR_SINCE_CXX14 static __difference_type<_InputIter> __advance_to(
174 _InputIter& __iter, __difference_type<_InputIter> __count, const _InputIter& __sentinel, input_iterator_tag) {
175 __difference_type<_InputIter> __dist = 0;
176 for (; __dist < __count && __iter != __sentinel; ++__dist)
177 ++__iter;
178 return __count - __dist;
179 }
180
181 // advance with sentinel, a la std::ranges::advance -- BidirectionalIterator specialization
182 template <class _BiDirIter>
183 _LIBCPP_CONSTEXPR_SINCE_CXX14 static __difference_type<_BiDirIter>
184 __advance_to(_BiDirIter& __iter,
185 __difference_type<_BiDirIter> __count,
186 const _BiDirIter& __sentinel,
187 bidirectional_iterator_tag) {
188 __difference_type<_BiDirIter> __dist = 0;
189 if (__count >= 0)
190 for (; __dist < __count && __iter != __sentinel; ++__dist)
191 ++__iter;
192 else
193 for (__count = -__count; __dist < __count && __iter != __sentinel; ++__dist)
194 --__iter;
195 return __count - __dist;
196 }
197
198 // advance with sentinel, a la std::ranges::advance -- RandomIterator specialization
199 template <class _RandIter>
200 _LIBCPP_CONSTEXPR_SINCE_CXX14 static __difference_type<_RandIter>
201 __advance_to(_RandIter& __iter,
202 __difference_type<_RandIter> __count,
203 const _RandIter& __sentinel,
204 random_access_iterator_tag) {
205 auto __dist = _IterOps::distance(__iter, __sentinel);
206 _LIBCPP_ASSERT_VALID_INPUT_RANGE(
207 __count == 0 || (__dist < 0) == (__count < 0), "__sentinel must precede __iter when __count < 0");
208 if (__count < 0)
209 __dist = __dist > __count ? __dist : __count;
210 else
211 __dist = __dist < __count ? __dist : __count;
212 __iter += __dist;
213 return __count - __dist;
214 }
215};
216
217template <class _AlgPolicy, class _Iter>
218using __policy_iter_diff_t _LIBCPP_NODEBUG = typename _IterOps<_AlgPolicy>::template __difference_type<_Iter>;
219
220template <class _AlgPolicy, class _Iter>
221using __policy_value_type _LIBCPP_NODEBUG = typename _IterOps<_AlgPolicy>::template __value_type<_Iter>;
222
223_LIBCPP_END_NAMESPACE_STD
224
225_LIBCPP_POP_MACROS
226
227#endif // _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H
228