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-exception
7 //
8 //===----------------------------------------------------------------------===//
9 #ifndef _LIBCPP___ITERATOR_COUNTED_ITERATOR_H
10 #define _LIBCPP___ITERATOR_COUNTED_ITERATOR_H
11 
12 #include <__assert>
13 #include <__config>
14 #include <__iterator/concepts.h>
15 #include <__iterator/default_sentinel.h>
16 #include <__iterator/incrementable_traits.h>
17 #include <__iterator/iter_move.h>
18 #include <__iterator/iter_swap.h>
19 #include <__iterator/iterator_traits.h>
20 #include <__iterator/readable_traits.h>
21 #include <__memory/pointer_traits.h>
22 #include <__utility/move.h>
23 #include <compare>
24 #include <concepts>
25 #include <type_traits>
26 
27 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
28 #  pragma GCC system_header
29 #endif
30 
31 _LIBCPP_BEGIN_NAMESPACE_STD
32 
33 #if _LIBCPP_STD_VER > 17
34 
35 template<class>
36 struct __counted_iterator_concept {};
37 
38 template<class _Iter>
39   requires requires { typename _Iter::iterator_concept; }
40 struct __counted_iterator_concept<_Iter> {
41   using iterator_concept = typename _Iter::iterator_concept;
42 };
43 
44 template<class>
45 struct __counted_iterator_category {};
46 
47 template<class _Iter>
48   requires requires { typename _Iter::iterator_category; }
49 struct __counted_iterator_category<_Iter> {
50   using iterator_category = typename _Iter::iterator_category;
51 };
52 
53 template<class>
54 struct __counted_iterator_value_type {};
55 
56 template<indirectly_readable _Iter>
57 struct __counted_iterator_value_type<_Iter> {
58   using value_type = iter_value_t<_Iter>;
59 };
60 
61 template<input_or_output_iterator _Iter>
62 class counted_iterator
63   : public __counted_iterator_concept<_Iter>
64   , public __counted_iterator_category<_Iter>
65   , public __counted_iterator_value_type<_Iter>
66 {
67 public:
68   _LIBCPP_NO_UNIQUE_ADDRESS _Iter __current_ = _Iter();
69   iter_difference_t<_Iter> __count_ = 0;
70 
71   using iterator_type = _Iter;
72   using difference_type = iter_difference_t<_Iter>;
73 
74   _LIBCPP_HIDE_FROM_ABI
75   constexpr counted_iterator() requires default_initializable<_Iter> = default;
76 
77   _LIBCPP_HIDE_FROM_ABI
78   constexpr counted_iterator(_Iter __iter, iter_difference_t<_Iter> __n)
79    : __current_(_VSTD::move(__iter)), __count_(__n) {
80     _LIBCPP_ASSERT(__n >= 0, "__n must not be negative.");
81   }
82 
83   template<class _I2>
84     requires convertible_to<const _I2&, _Iter>
85   _LIBCPP_HIDE_FROM_ABI
86   constexpr counted_iterator(const counted_iterator<_I2>& __other)
87    : __current_(__other.__current_), __count_(__other.__count_) {}
88 
89   template<class _I2>
90     requires assignable_from<_Iter&, const _I2&>
91   _LIBCPP_HIDE_FROM_ABI
92   constexpr counted_iterator& operator=(const counted_iterator<_I2>& __other) {
93     __current_ = __other.__current_;
94     __count_ = __other.__count_;
95     return *this;
96   }
97 
98   _LIBCPP_HIDE_FROM_ABI
99   constexpr const _Iter& base() const& noexcept { return __current_; }
100 
101   _LIBCPP_HIDE_FROM_ABI
102   constexpr _Iter base() && { return _VSTD::move(__current_); }
103 
104   _LIBCPP_HIDE_FROM_ABI
105   constexpr iter_difference_t<_Iter> count() const noexcept { return __count_; }
106 
107   _LIBCPP_HIDE_FROM_ABI
108   constexpr decltype(auto) operator*() {
109     _LIBCPP_ASSERT(__count_ > 0, "Iterator is equal to or past end.");
110     return *__current_;
111   }
112 
113   _LIBCPP_HIDE_FROM_ABI
114   constexpr decltype(auto) operator*() const
115     requires __dereferenceable<const _Iter>
116   {
117     _LIBCPP_ASSERT(__count_ > 0, "Iterator is equal to or past end.");
118     return *__current_;
119   }
120 
121   _LIBCPP_HIDE_FROM_ABI
122   constexpr auto operator->() const noexcept
123     requires contiguous_iterator<_Iter>
124   {
125     return _VSTD::to_address(__current_);
126   }
127 
128   _LIBCPP_HIDE_FROM_ABI
129   constexpr counted_iterator& operator++() {
130     _LIBCPP_ASSERT(__count_ > 0, "Iterator already at or past end.");
131     ++__current_;
132     --__count_;
133     return *this;
134   }
135 
136   _LIBCPP_HIDE_FROM_ABI
137   decltype(auto) operator++(int) {
138     _LIBCPP_ASSERT(__count_ > 0, "Iterator already at or past end.");
139     --__count_;
140 #ifndef _LIBCPP_NO_EXCEPTIONS
141     try { return __current_++; }
142     catch(...) { ++__count_; throw; }
143 #else
144     return __current_++;
145 #endif // _LIBCPP_NO_EXCEPTIONS
146   }
147 
148   _LIBCPP_HIDE_FROM_ABI
149   constexpr counted_iterator operator++(int)
150     requires forward_iterator<_Iter>
151   {
152     _LIBCPP_ASSERT(__count_ > 0, "Iterator already at or past end.");
153     counted_iterator __tmp = *this;
154     ++*this;
155     return __tmp;
156   }
157 
158   _LIBCPP_HIDE_FROM_ABI
159   constexpr counted_iterator& operator--()
160     requires bidirectional_iterator<_Iter>
161   {
162     --__current_;
163     ++__count_;
164     return *this;
165   }
166 
167   _LIBCPP_HIDE_FROM_ABI
168   constexpr counted_iterator operator--(int)
169     requires bidirectional_iterator<_Iter>
170   {
171     counted_iterator __tmp = *this;
172     --*this;
173     return __tmp;
174   }
175 
176   _LIBCPP_HIDE_FROM_ABI
177   constexpr counted_iterator operator+(iter_difference_t<_Iter> __n) const
178     requires random_access_iterator<_Iter>
179   {
180     return counted_iterator(__current_ + __n, __count_ - __n);
181   }
182 
183   _LIBCPP_HIDE_FROM_ABI
184   friend constexpr counted_iterator operator+(
185     iter_difference_t<_Iter> __n, const counted_iterator& __x)
186     requires random_access_iterator<_Iter>
187   {
188     return __x + __n;
189   }
190 
191   _LIBCPP_HIDE_FROM_ABI
192   constexpr counted_iterator& operator+=(iter_difference_t<_Iter> __n)
193     requires random_access_iterator<_Iter>
194   {
195     _LIBCPP_ASSERT(__n <= __count_, "Cannot advance iterator past end.");
196     __current_ += __n;
197     __count_ -= __n;
198     return *this;
199   }
200 
201   _LIBCPP_HIDE_FROM_ABI
202   constexpr counted_iterator operator-(iter_difference_t<_Iter> __n) const
203     requires random_access_iterator<_Iter>
204   {
205     return counted_iterator(__current_ - __n, __count_ + __n);
206   }
207 
208   template<common_with<_Iter> _I2>
209   _LIBCPP_HIDE_FROM_ABI
210   friend constexpr iter_difference_t<_I2> operator-(
211     const counted_iterator& __lhs, const counted_iterator<_I2>& __rhs)
212   {
213     return __rhs.__count_ - __lhs.__count_;
214   }
215 
216   _LIBCPP_HIDE_FROM_ABI
217   friend constexpr iter_difference_t<_Iter> operator-(
218     const counted_iterator& __lhs, default_sentinel_t)
219   {
220     return -__lhs.__count_;
221   }
222 
223   _LIBCPP_HIDE_FROM_ABI
224   friend constexpr iter_difference_t<_Iter> operator-(
225     default_sentinel_t, const counted_iterator& __rhs)
226   {
227     return __rhs.__count_;
228   }
229 
230   _LIBCPP_HIDE_FROM_ABI
231   constexpr counted_iterator& operator-=(iter_difference_t<_Iter> __n)
232     requires random_access_iterator<_Iter>
233   {
234     _LIBCPP_ASSERT(-__n <= __count_, "Attempt to subtract too large of a size: "
235                                      "counted_iterator would be decremented before the "
236                                      "first element of its range.");
237     __current_ -= __n;
238     __count_ += __n;
239     return *this;
240   }
241 
242   _LIBCPP_HIDE_FROM_ABI
243   constexpr decltype(auto) operator[](iter_difference_t<_Iter> __n) const
244     requires random_access_iterator<_Iter>
245   {
246     _LIBCPP_ASSERT(__n < __count_, "Subscript argument must be less than size.");
247     return __current_[__n];
248   }
249 
250   template<common_with<_Iter> _I2>
251   _LIBCPP_HIDE_FROM_ABI
252   friend constexpr bool operator==(
253     const counted_iterator& __lhs, const counted_iterator<_I2>& __rhs)
254   {
255     return __lhs.__count_ == __rhs.__count_;
256   }
257 
258   _LIBCPP_HIDE_FROM_ABI
259   friend constexpr bool operator==(
260     const counted_iterator& __lhs, default_sentinel_t)
261   {
262     return __lhs.__count_ == 0;
263   }
264 
265   template<common_with<_Iter> _I2>
266   friend constexpr strong_ordering operator<=>(
267     const counted_iterator& __lhs, const counted_iterator<_I2>& __rhs)
268   {
269     return __rhs.__count_ <=> __lhs.__count_;
270   }
271 
272   _LIBCPP_HIDE_FROM_ABI
273   friend constexpr iter_rvalue_reference_t<_Iter> iter_move(const counted_iterator& __i)
274     noexcept(noexcept(ranges::iter_move(__i.__current_)))
275       requires input_iterator<_Iter>
276   {
277     _LIBCPP_ASSERT(__i.__count_ > 0, "Iterator must not be past end of range.");
278     return ranges::iter_move(__i.__current_);
279   }
280 
281   template<indirectly_swappable<_Iter> _I2>
282   _LIBCPP_HIDE_FROM_ABI
283   friend constexpr void iter_swap(const counted_iterator& __x, const counted_iterator<_I2>& __y)
284     noexcept(noexcept(ranges::iter_swap(__x.__current_, __y.__current_)))
285   {
286     _LIBCPP_ASSERT(__x.__count_ > 0 && __y.__count_ > 0,
287                    "Iterators must not be past end of range.");
288     return ranges::iter_swap(__x.__current_, __y.__current_);
289   }
290 };
291 
292 template<input_iterator _Iter>
293   requires same_as<_ITER_TRAITS<_Iter>, iterator_traits<_Iter>>
294 struct iterator_traits<counted_iterator<_Iter>> : iterator_traits<_Iter> {
295   using pointer = conditional_t<contiguous_iterator<_Iter>,
296                                 add_pointer_t<iter_reference_t<_Iter>>, void>;
297 };
298 
299 #endif // _LIBCPP_STD_VER > 17
300 
301 _LIBCPP_END_NAMESPACE_STD
302 
303 #endif // _LIBCPP___ITERATOR_COUNTED_ITERATOR_H
304