1 // Utilities for representing and manipulating ranges -*- C++ -*-
3 // Copyright (C) 2019-2021 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 /** @file bits/ranges_util.h
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly. @headername{ranges}
30 #ifndef _RANGES_UTIL_H
31 #define _RANGES_UTIL_H 1
33 #if __cplusplus > 201703L
34 # include <bits/ranges_base.h>
36 #ifdef __cpp_lib_ranges
37 namespace std
_GLIBCXX_VISIBILITY(default)
39 _GLIBCXX_BEGIN_NAMESPACE_VERSION
42 // C++20 24.5 [range.utility] Range utilities
46 template<typename _Range
>
47 concept __simple_view
= view
<_Range
> && range
<const _Range
>
48 && same_as
<iterator_t
<_Range
>, iterator_t
<const _Range
>>
49 && same_as
<sentinel_t
<_Range
>, sentinel_t
<const _Range
>>;
51 template<typename _It
>
52 concept __has_arrow
= input_iterator
<_It
>
53 && (is_pointer_v
<_It
> || requires(_It __it
) { __it
.operator->(); });
55 template<typename _Tp
, typename _Up
>
57 = !same_as
<remove_cvref_t
<_Tp
>, remove_cvref_t
<_Up
>>;
58 } // namespace __detail
60 /// The ranges::view_interface class template
61 template<typename _Derived
>
62 requires is_class_v
<_Derived
> && same_as
<_Derived
, remove_cv_t
<_Derived
>>
63 class view_interface
: public view_base
66 constexpr _Derived
& _M_derived() noexcept
68 static_assert(derived_from
<_Derived
, view_interface
<_Derived
>>);
69 static_assert(view
<_Derived
>);
70 return static_cast<_Derived
&>(*this);
73 constexpr const _Derived
& _M_derived() const noexcept
75 static_assert(derived_from
<_Derived
, view_interface
<_Derived
>>);
76 static_assert(view
<_Derived
>);
77 return static_cast<const _Derived
&>(*this);
82 empty() requires forward_range
<_Derived
>
83 { return ranges::begin(_M_derived()) == ranges::end(_M_derived()); }
86 empty() const requires forward_range
<const _Derived
>
87 { return ranges::begin(_M_derived()) == ranges::end(_M_derived()); }
90 operator bool() requires requires
{ ranges::empty(_M_derived()); }
91 { return !ranges::empty(_M_derived()); }
94 operator bool() const requires requires
{ ranges::empty(_M_derived()); }
95 { return !ranges::empty(_M_derived()); }
98 data() requires contiguous_iterator
<iterator_t
<_Derived
>>
99 { return to_address(ranges::begin(_M_derived())); }
103 requires range
<const _Derived
>
104 && contiguous_iterator
<iterator_t
<const _Derived
>>
105 { return to_address(ranges::begin(_M_derived())); }
109 requires forward_range
<_Derived
>
110 && sized_sentinel_for
<sentinel_t
<_Derived
>, iterator_t
<_Derived
>>
111 { return ranges::end(_M_derived()) - ranges::begin(_M_derived()); }
115 requires forward_range
<const _Derived
>
116 && sized_sentinel_for
<sentinel_t
<const _Derived
>,
117 iterator_t
<const _Derived
>>
118 { return ranges::end(_M_derived()) - ranges::begin(_M_derived()); }
120 constexpr decltype(auto)
121 front() requires forward_range
<_Derived
>
123 __glibcxx_assert(!empty());
124 return *ranges::begin(_M_derived());
127 constexpr decltype(auto)
128 front() const requires forward_range
<const _Derived
>
130 __glibcxx_assert(!empty());
131 return *ranges::begin(_M_derived());
134 constexpr decltype(auto)
136 requires bidirectional_range
<_Derived
> && common_range
<_Derived
>
138 __glibcxx_assert(!empty());
139 return *ranges::prev(ranges::end(_M_derived()));
142 constexpr decltype(auto)
144 requires bidirectional_range
<const _Derived
>
145 && common_range
<const _Derived
>
147 __glibcxx_assert(!empty());
148 return *ranges::prev(ranges::end(_M_derived()));
151 template<random_access_range _Range
= _Derived
>
152 constexpr decltype(auto)
153 operator[](range_difference_t
<_Range
> __n
)
154 { return ranges::begin(_M_derived())[__n
]; }
156 template<random_access_range _Range
= const _Derived
>
157 constexpr decltype(auto)
158 operator[](range_difference_t
<_Range
> __n
) const
159 { return ranges::begin(_M_derived())[__n
]; }
164 template<class _From
, class _To
>
165 concept __convertible_to_non_slicing
= convertible_to
<_From
, _To
>
166 && !(is_pointer_v
<decay_t
<_From
>> && is_pointer_v
<decay_t
<_To
>>
167 && __not_same_as
<remove_pointer_t
<decay_t
<_From
>>,
168 remove_pointer_t
<decay_t
<_To
>>>);
170 template<typename _Tp
>
172 = !is_reference_v
<_Tp
> && requires(_Tp __t
)
174 typename tuple_size
<_Tp
>::type
;
175 requires derived_from
<tuple_size
<_Tp
>, integral_constant
<size_t, 2>>;
176 typename tuple_element_t
<0, remove_const_t
<_Tp
>>;
177 typename tuple_element_t
<1, remove_const_t
<_Tp
>>;
178 { get
<0>(__t
) } -> convertible_to
<const tuple_element_t
<0, _Tp
>&>;
179 { get
<1>(__t
) } -> convertible_to
<const tuple_element_t
<1, _Tp
>&>;
182 template<typename _Tp
, typename _Up
, typename _Vp
>
183 concept __pair_like_convertible_from
184 = !range
<_Tp
> && __pair_like
<_Tp
>
185 && constructible_from
<_Tp
, _Up
, _Vp
>
186 && __convertible_to_non_slicing
<_Up
, tuple_element_t
<0, _Tp
>>
187 && convertible_to
<_Vp
, tuple_element_t
<1, _Tp
>>;
189 template<typename _Tp
>
190 concept __iterator_sentinel_pair
191 = !range
<_Tp
> && __pair_like
<_Tp
>
192 && sentinel_for
<tuple_element_t
<1, _Tp
>, tuple_element_t
<0, _Tp
>>;
194 } // namespace __detail
196 enum class subrange_kind
: bool { unsized
, sized
};
198 /// The ranges::subrange class template
199 template<input_or_output_iterator _It
, sentinel_for
<_It
> _Sent
= _It
,
200 subrange_kind _Kind
= sized_sentinel_for
<_Sent
, _It
>
201 ? subrange_kind::sized
: subrange_kind::unsized
>
202 requires (_Kind
== subrange_kind::sized
|| !sized_sentinel_for
<_Sent
, _It
>)
203 class subrange
: public view_interface
<subrange
<_It
, _Sent
, _Kind
>>
206 // XXX: gcc complains when using constexpr here
207 static const bool _S_store_size
208 = _Kind
== subrange_kind::sized
&& !sized_sentinel_for
<_Sent
, _It
>;
210 _It _M_begin
= _It();
211 [[no_unique_address
]] _Sent _M_end
= _Sent();
213 template<typename
, bool = _S_store_size
>
217 template<typename _Tp
>
218 struct _Size
<_Tp
, true>
219 { __detail::__make_unsigned_like_t
<_Tp
> _M_size
; };
221 [[no_unique_address
]] _Size
<iter_difference_t
<_It
>> _M_size
= {};
224 subrange() = default;
227 subrange(__detail::__convertible_to_non_slicing
<_It
> auto __i
, _Sent __s
)
228 requires (!_S_store_size
)
229 : _M_begin(std::move(__i
)), _M_end(__s
)
233 subrange(__detail::__convertible_to_non_slicing
<_It
> auto __i
, _Sent __s
,
234 __detail::__make_unsigned_like_t
<iter_difference_t
<_It
>> __n
)
235 requires (_Kind
== subrange_kind::sized
)
236 : _M_begin(std::move(__i
)), _M_end(__s
)
238 using __detail::__to_unsigned_like
;
239 __glibcxx_assert(__n
== __to_unsigned_like(ranges::distance(__i
, __s
)));
240 if constexpr (_S_store_size
)
241 _M_size
._M_size
= __n
;
244 template<__detail::__not_same_as
<subrange
> _Rng
>
245 requires borrowed_range
<_Rng
>
246 && __detail::__convertible_to_non_slicing
<iterator_t
<_Rng
>, _It
>
247 && convertible_to
<sentinel_t
<_Rng
>, _Sent
>
249 subrange(_Rng
&& __r
) requires _S_store_size
&& sized_range
<_Rng
>
250 : subrange(__r
, ranges::size(__r
))
253 template<__detail::__not_same_as
<subrange
> _Rng
>
254 requires borrowed_range
<_Rng
>
255 && __detail::__convertible_to_non_slicing
<iterator_t
<_Rng
>, _It
>
256 && convertible_to
<sentinel_t
<_Rng
>, _Sent
>
258 subrange(_Rng
&& __r
) requires (!_S_store_size
)
259 : subrange
{ranges::begin(__r
), ranges::end(__r
)}
262 template<borrowed_range _Rng
>
263 requires
__detail::__convertible_to_non_slicing
<iterator_t
<_Rng
>, _It
>
264 && convertible_to
<sentinel_t
<_Rng
>, _Sent
>
267 __detail::__make_unsigned_like_t
<iter_difference_t
<_It
>> __n
)
268 requires (_Kind
== subrange_kind::sized
)
269 : subrange
{ranges::begin(__r
), ranges::end(__r
), __n
}
272 template<__detail::__not_same_as
<subrange
> _PairLike
>
273 requires
__detail::__pair_like_convertible_from
<_PairLike
, const _It
&,
276 operator _PairLike() const
277 { return _PairLike(_M_begin
, _M_end
); }
280 begin() const requires copyable
<_It
>
283 [[nodiscard
]] constexpr _It
284 begin() requires (!copyable
<_It
>)
285 { return std::move(_M_begin
); }
287 constexpr _Sent
end() const { return _M_end
; }
289 constexpr bool empty() const { return _M_begin
== _M_end
; }
291 constexpr __detail::__make_unsigned_like_t
<iter_difference_t
<_It
>>
292 size() const requires (_Kind
== subrange_kind::sized
)
294 if constexpr (_S_store_size
)
295 return _M_size
._M_size
;
297 return __detail::__to_unsigned_like(_M_end
- _M_begin
);
300 [[nodiscard
]] constexpr subrange
301 next(iter_difference_t
<_It
> __n
= 1) const &
302 requires forward_iterator
<_It
>
309 [[nodiscard
]] constexpr subrange
310 next(iter_difference_t
<_It
> __n
= 1) &&
313 return std::move(*this);
316 [[nodiscard
]] constexpr subrange
317 prev(iter_difference_t
<_It
> __n
= 1) const
318 requires bidirectional_iterator
<_It
>
326 advance(iter_difference_t
<_It
> __n
)
328 // _GLIBCXX_RESOLVE_LIB_DEFECTS
329 // 3433. subrange::advance(n) has UB when n < 0
330 if constexpr (bidirectional_iterator
<_It
>)
333 ranges::advance(_M_begin
, __n
);
334 if constexpr (_S_store_size
)
335 _M_size
._M_size
+= __detail::__to_unsigned_like(-__n
);
339 __glibcxx_assert(__n
>= 0);
340 auto __d
= __n
- ranges::advance(_M_begin
, __n
, _M_end
);
341 if constexpr (_S_store_size
)
342 _M_size
._M_size
-= __detail::__to_unsigned_like(__d
);
347 template<input_or_output_iterator _It
, sentinel_for
<_It
> _Sent
>
348 subrange(_It
, _Sent
) -> subrange
<_It
, _Sent
>;
350 template<input_or_output_iterator _It
, sentinel_for
<_It
> _Sent
>
352 __detail::__make_unsigned_like_t
<iter_difference_t
<_It
>>)
353 -> subrange
<_It
, _Sent
, subrange_kind::sized
>;
355 template<__detail::__iterator_sentinel_pair _Pr
>
357 -> subrange
<tuple_element_t
<0, _Pr
>, tuple_element_t
<1, _Pr
>>;
359 template<__detail::__iterator_sentinel_pair _Pr
>
360 subrange(_Pr
, __detail::__make_unsigned_like_t
<iter_difference_t
<
361 tuple_element_t
<0, _Pr
>>>)
362 -> subrange
<tuple_element_t
<0, _Pr
>, tuple_element_t
<1, _Pr
>,
363 subrange_kind::sized
>;
365 template<borrowed_range _Rng
>
367 -> subrange
<iterator_t
<_Rng
>, sentinel_t
<_Rng
>,
369 || sized_sentinel_for
<sentinel_t
<_Rng
>, iterator_t
<_Rng
>>)
370 ? subrange_kind::sized
: subrange_kind::unsized
>;
372 template<borrowed_range _Rng
>
374 __detail::__make_unsigned_like_t
<range_difference_t
<_Rng
>>)
375 -> subrange
<iterator_t
<_Rng
>, sentinel_t
<_Rng
>, subrange_kind::sized
>;
377 template<size_t _Num
, class _It
, class _Sent
, subrange_kind _Kind
>
380 get(const subrange
<_It
, _Sent
, _Kind
>& __r
)
382 if constexpr (_Num
== 0)
388 template<size_t _Num
, class _It
, class _Sent
, subrange_kind _Kind
>
391 get(subrange
<_It
, _Sent
, _Kind
>&& __r
)
393 if constexpr (_Num
== 0)
399 template<input_or_output_iterator _It
, sentinel_for
<_It
> _Sent
,
401 inline constexpr bool
402 enable_borrowed_range
<subrange
<_It
, _Sent
, _Kind
>> = true;
404 template<range _Range
>
405 using borrowed_subrange_t
= conditional_t
<borrowed_range
<_Range
>,
406 subrange
<iterator_t
<_Range
>>,
409 } // namespace ranges
413 template<typename _Iter
, typename _Sent
, ranges::subrange_kind _Kind
>
414 struct tuple_size
<ranges::subrange
<_Iter
, _Sent
, _Kind
>>
415 : integral_constant
<size_t, 2>
418 template<typename _Iter
, typename _Sent
, ranges::subrange_kind _Kind
>
419 struct tuple_element
<0, ranges::subrange
<_Iter
, _Sent
, _Kind
>>
420 { using type
= _Iter
; };
422 template<typename _Iter
, typename _Sent
, ranges::subrange_kind _Kind
>
423 struct tuple_element
<1, ranges::subrange
<_Iter
, _Sent
, _Kind
>>
424 { using type
= _Sent
; };
426 template<typename _Iter
, typename _Sent
, ranges::subrange_kind _Kind
>
427 struct tuple_element
<0, const ranges::subrange
<_Iter
, _Sent
, _Kind
>>
428 { using type
= _Iter
; };
430 template<typename _Iter
, typename _Sent
, ranges::subrange_kind _Kind
>
431 struct tuple_element
<1, const ranges::subrange
<_Iter
, _Sent
, _Kind
>>
432 { using type
= _Sent
; };
434 _GLIBCXX_END_NAMESPACE_VERSION
436 #endif // library concepts
438 #endif // _RANGES_UTIL_H