1 // Core algorithmic facilities -*- C++ -*-
3 // Copyright (C) 2020 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_algobase.h
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly. @headername{algorithm}
30 #ifndef _RANGES_ALGOBASE_H
31 #define _RANGES_ALGOBASE_H 1
33 #if __cplusplus > 201703L
37 // #include <bits/range_concepts.h>
39 #include <bits/invoke.h>
40 #include <bits/cpp_type_traits.h> // __is_byte
42 #if __cpp_lib_concepts
43 namespace std
_GLIBCXX_VISIBILITY(default)
45 _GLIBCXX_BEGIN_NAMESPACE_VERSION
50 template<typename _Tp
>
51 constexpr inline bool __is_normal_iterator
= false;
53 template<typename _Iterator
, typename _Container
>
55 __is_normal_iterator
<__gnu_cxx::__normal_iterator
<_Iterator
,
58 template<typename _Tp
>
59 constexpr inline bool __is_reverse_iterator
= false;
61 template<typename _Iterator
>
63 __is_reverse_iterator
<reverse_iterator
<_Iterator
>> = true;
65 template<typename _Tp
>
66 constexpr inline bool __is_move_iterator
= false;
68 template<typename _Iterator
>
70 __is_move_iterator
<move_iterator
<_Iterator
>> = true;
71 } // namespace __detail
75 template<input_iterator _Iter1
, sentinel_for
<_Iter1
> _Sent1
,
76 input_iterator _Iter2
, sentinel_for
<_Iter2
> _Sent2
,
77 typename _Pred
= ranges::equal_to
,
78 typename _Proj1
= identity
, typename _Proj2
= identity
>
79 requires indirectly_comparable
<_Iter1
, _Iter2
, _Pred
, _Proj1
, _Proj2
>
81 operator()(_Iter1 __first1
, _Sent1 __last1
,
82 _Iter2 __first2
, _Sent2 __last2
, _Pred __pred
= {},
83 _Proj1 __proj1
= {}, _Proj2 __proj2
= {}) const
85 // TODO: implement more specializations to at least have parity with
87 if constexpr (__detail::__is_normal_iterator
<_Iter1
>
88 || __detail::__is_normal_iterator
<_Iter2
>)
89 return (*this)(std::__niter_base(std::move(__first1
)),
90 std::__niter_base(std::move(__last1
)),
91 std::__niter_base(std::move(__first2
)),
92 std::__niter_base(std::move(__last2
)),
94 std::move(__proj1
), std::move(__proj2
));
95 else if constexpr (sized_sentinel_for
<_Sent1
, _Iter1
>
96 && sized_sentinel_for
<_Sent2
, _Iter2
>)
98 auto __d1
= ranges::distance(__first1
, __last1
);
99 auto __d2
= ranges::distance(__first2
, __last2
);
103 using _ValueType1
= iter_value_t
<_Iter1
>;
104 using _ValueType2
= iter_value_t
<_Iter2
>;
105 constexpr bool __use_memcmp
106 = ((is_integral_v
<_ValueType1
> || is_pointer_v
<_ValueType1
>)
107 && is_same_v
<_ValueType1
, _ValueType2
>
108 && is_pointer_v
<_Iter1
>
109 && is_pointer_v
<_Iter2
>
110 && is_same_v
<_Pred
, ranges::equal_to
>
111 && is_same_v
<_Proj1
, identity
>
112 && is_same_v
<_Proj2
, identity
>);
113 if constexpr (__use_memcmp
)
115 if (const size_t __len
= (__last1
- __first1
))
116 return !std::__memcmp(__first1
, __first2
, __len
);
121 for (; __first1
!= __last1
; ++__first1
, (void)++__first2
)
122 if (!(bool)std::__invoke(__pred
,
123 std::__invoke(__proj1
, *__first1
),
124 std::__invoke(__proj2
, *__first2
)))
131 for (; __first1
!= __last1
&& __first2
!= __last2
;
132 ++__first1
, (void)++__first2
)
133 if (!(bool)std::__invoke(__pred
,
134 std::__invoke(__proj1
, *__first1
),
135 std::__invoke(__proj2
, *__first2
)))
137 return __first1
== __last1
&& __first2
== __last2
;
141 template<input_range _Range1
, input_range _Range2
,
142 typename _Pred
= ranges::equal_to
,
143 typename _Proj1
= identity
, typename _Proj2
= identity
>
144 requires indirectly_comparable
<iterator_t
<_Range1
>, iterator_t
<_Range2
>,
145 _Pred
, _Proj1
, _Proj2
>
147 operator()(_Range1
&& __r1
, _Range2
&& __r2
, _Pred __pred
= {},
148 _Proj1 __proj1
= {}, _Proj2 __proj2
= {}) const
150 return (*this)(ranges::begin(__r1
), ranges::end(__r1
),
151 ranges::begin(__r2
), ranges::end(__r2
),
153 std::move(__proj1
), std::move(__proj2
));
157 inline constexpr __equal_fn equal
{};
159 template<typename _Iter
, typename _Out
>
162 [[no_unique_address
]] _Iter in
;
163 [[no_unique_address
]] _Out out
;
165 template<typename _Iter2
, typename _Out2
>
166 requires convertible_to
<const _Iter
&, _Iter2
>
167 && convertible_to
<const _Out
&, _Out2
>
169 operator in_out_result
<_Iter2
, _Out2
>() const &
170 { return {in
, out
}; }
172 template<typename _Iter2
, typename _Out2
>
173 requires convertible_to
<_Iter
, _Iter2
>
174 && convertible_to
<_Out
, _Out2
>
176 operator in_out_result
<_Iter2
, _Out2
>() &&
177 { return {std::move(in
), std::move(out
)}; }
180 template<typename _Iter
, typename _Out
>
181 using copy_result
= in_out_result
<_Iter
, _Out
>;
183 template<typename _Iter
, typename _Out
>
184 using move_result
= in_out_result
<_Iter
, _Out
>;
186 template<typename _Iter1
, typename _Iter2
>
187 using move_backward_result
= in_out_result
<_Iter1
, _Iter2
>;
189 template<typename _Iter1
, typename _Iter2
>
190 using copy_backward_result
= in_out_result
<_Iter1
, _Iter2
>;
192 template<bool _IsMove
,
193 bidirectional_iterator _Iter
, sentinel_for
<_Iter
> _Sent
,
194 bidirectional_iterator _Out
>
196 ? indirectly_movable
<_Iter
, _Out
>
197 : indirectly_copyable
<_Iter
, _Out
>)
198 constexpr conditional_t
<_IsMove
,
199 move_backward_result
<_Iter
, _Out
>,
200 copy_backward_result
<_Iter
, _Out
>>
201 __copy_or_move_backward(_Iter __first
, _Sent __last
, _Out __result
);
203 template<bool _IsMove
,
204 input_iterator _Iter
, sentinel_for
<_Iter
> _Sent
,
205 weakly_incrementable _Out
>
207 ? indirectly_movable
<_Iter
, _Out
>
208 : indirectly_copyable
<_Iter
, _Out
>)
209 constexpr conditional_t
<_IsMove
,
210 move_result
<_Iter
, _Out
>,
211 copy_result
<_Iter
, _Out
>>
212 __copy_or_move(_Iter __first
, _Sent __last
, _Out __result
)
214 // TODO: implement more specializations to be at least on par with
215 // std::copy/std::move.
216 constexpr bool __normal_iterator_p
217 = (__detail::__is_normal_iterator
<_Iter
>
218 || __detail::__is_normal_iterator
<_Out
>);
219 constexpr bool __reverse_p
220 = (__detail::__is_reverse_iterator
<_Iter
>
221 && __detail::__is_reverse_iterator
<_Out
>);
222 constexpr bool __move_iterator_p
= __detail::__is_move_iterator
<_Iter
>;
223 if constexpr (__move_iterator_p
)
226 = ranges::__copy_or_move
<true>(std::move(__first
).base(),
227 std::move(__last
).base(),
228 std::move(__result
));
229 return {move_iterator
{std::move(__in
)}, std::move(__out
)};
231 else if constexpr (__reverse_p
)
234 = ranges::__copy_or_move_backward
<_IsMove
>(__last
.base(),
237 return {reverse_iterator
{std::move(__in
)},
238 reverse_iterator
{std::move(__out
)}};
240 else if constexpr (__normal_iterator_p
)
243 = ranges::__copy_or_move
<_IsMove
>(std::__niter_base(__first
),
244 std::__niter_base(__last
),
245 std::__niter_base(__result
));
246 return {std::__niter_wrap(__first
, std::move(__in
)),
247 std::__niter_wrap(__result
, std::move(__out
))};
249 else if constexpr (sized_sentinel_for
<_Sent
, _Iter
>)
251 using _ValueTypeI
= iter_value_t
<_Iter
>;
252 using _ValueTypeO
= iter_value_t
<_Out
>;
253 constexpr bool __use_memmove
254 = (is_trivially_copyable_v
<_ValueTypeI
>
255 && is_same_v
<_ValueTypeI
, _ValueTypeO
>
256 && is_pointer_v
<_Iter
>
257 && is_pointer_v
<_Out
>);
259 if constexpr (__use_memmove
)
261 static_assert(_IsMove
262 ? is_move_assignable_v
<_ValueTypeI
>
263 : is_copy_assignable_v
<_ValueTypeI
>);
264 auto __num
= __last
- __first
;
266 std::__memmove
<_IsMove
>(__result
, __first
, __num
);
267 return {__first
+ __num
, __result
+ __num
};
271 for (auto __n
= __last
- __first
; __n
> 0; --__n
)
273 if constexpr (_IsMove
)
274 *__result
= std::move(*__first
);
276 *__result
= *__first
;
280 return {std::move(__first
), std::move(__result
)};
285 while (__first
!= __last
)
287 if constexpr (_IsMove
)
288 *__result
= std::move(*__first
);
290 *__result
= *__first
;
294 return {std::move(__first
), std::move(__result
)};
300 template<input_iterator _Iter
, sentinel_for
<_Iter
> _Sent
,
301 weakly_incrementable _Out
>
302 requires indirectly_copyable
<_Iter
, _Out
>
303 constexpr copy_result
<_Iter
, _Out
>
304 operator()(_Iter __first
, _Sent __last
, _Out __result
) const
306 return ranges::__copy_or_move
<false>(std::move(__first
),
308 std::move(__result
));
311 template<input_range _Range
, weakly_incrementable _Out
>
312 requires indirectly_copyable
<iterator_t
<_Range
>, _Out
>
313 constexpr copy_result
<borrowed_iterator_t
<_Range
>, _Out
>
314 operator()(_Range
&& __r
, _Out __result
) const
316 return (*this)(ranges::begin(__r
), ranges::end(__r
),
317 std::move(__result
));
321 inline constexpr __copy_fn copy
{};
325 template<input_iterator _Iter
, sentinel_for
<_Iter
> _Sent
,
326 weakly_incrementable _Out
>
327 requires indirectly_movable
<_Iter
, _Out
>
328 constexpr move_result
<_Iter
, _Out
>
329 operator()(_Iter __first
, _Sent __last
, _Out __result
) const
331 return ranges::__copy_or_move
<true>(std::move(__first
),
333 std::move(__result
));
336 template<input_range _Range
, weakly_incrementable _Out
>
337 requires indirectly_movable
<iterator_t
<_Range
>, _Out
>
338 constexpr move_result
<borrowed_iterator_t
<_Range
>, _Out
>
339 operator()(_Range
&& __r
, _Out __result
) const
341 return (*this)(ranges::begin(__r
), ranges::end(__r
),
342 std::move(__result
));
346 inline constexpr __move_fn move
{};
348 template<bool _IsMove
,
349 bidirectional_iterator _Iter
, sentinel_for
<_Iter
> _Sent
,
350 bidirectional_iterator _Out
>
352 ? indirectly_movable
<_Iter
, _Out
>
353 : indirectly_copyable
<_Iter
, _Out
>)
354 constexpr conditional_t
<_IsMove
,
355 move_backward_result
<_Iter
, _Out
>,
356 copy_backward_result
<_Iter
, _Out
>>
357 __copy_or_move_backward(_Iter __first
, _Sent __last
, _Out __result
)
359 // TODO: implement more specializations to be at least on par with
360 // std::copy_backward/std::move_backward.
361 constexpr bool __normal_iterator_p
362 = (__detail::__is_normal_iterator
<_Iter
>
363 || __detail::__is_normal_iterator
<_Out
>);
364 constexpr bool __reverse_p
365 = (__detail::__is_reverse_iterator
<_Iter
>
366 && __detail::__is_reverse_iterator
<_Out
>);
367 if constexpr (__reverse_p
)
370 = ranges::__copy_or_move
<_IsMove
>(__last
.base(),
373 return {reverse_iterator
{std::move(__in
)},
374 reverse_iterator
{std::move(__out
)}};
376 else if constexpr (__normal_iterator_p
)
379 = ranges::__copy_or_move_backward
<_IsMove
>
380 (std::__niter_base(__first
),
381 std::__niter_base(__last
),
382 std::__niter_base(__result
));
383 return {std::__niter_wrap(__first
, std::move(__in
)),
384 std::__niter_wrap(__result
, std::move(__out
))};
386 else if constexpr (sized_sentinel_for
<_Sent
, _Iter
>)
388 using _ValueTypeI
= iter_value_t
<_Iter
>;
389 using _ValueTypeO
= iter_value_t
<_Out
>;
390 constexpr bool __use_memmove
391 = (is_trivially_copyable_v
<_ValueTypeI
>
392 && is_same_v
<_ValueTypeI
, _ValueTypeO
>
393 && is_pointer_v
<_Iter
>
394 && is_pointer_v
<_Out
>);
395 if constexpr (__use_memmove
)
397 static_assert(_IsMove
398 ? is_move_assignable_v
<_ValueTypeI
>
399 : is_copy_assignable_v
<_ValueTypeI
>);
400 auto __num
= __last
- __first
;
402 std::__memmove
<_IsMove
>(__result
- __num
, __first
, __num
);
403 return {__first
+ __num
, __result
- __num
};
407 auto __lasti
= ranges::next(__first
, __last
);
408 auto __tail
= __lasti
;
410 for (auto __n
= __last
- __first
; __n
> 0; --__n
)
414 if constexpr (_IsMove
)
415 *__result
= std::move(*__tail
);
419 return {std::move(__lasti
), std::move(__result
)};
424 auto __lasti
= ranges::next(__first
, __last
);
425 auto __tail
= __lasti
;
427 while (__first
!= __tail
)
431 if constexpr (_IsMove
)
432 *__result
= std::move(*__tail
);
436 return {std::move(__lasti
), std::move(__result
)};
440 struct __copy_backward_fn
442 template<bidirectional_iterator _Iter1
, sentinel_for
<_Iter1
> _Sent1
,
443 bidirectional_iterator _Iter2
>
444 requires indirectly_copyable
<_Iter1
, _Iter2
>
445 constexpr copy_backward_result
<_Iter1
, _Iter2
>
446 operator()(_Iter1 __first
, _Sent1 __last
, _Iter2 __result
) const
448 return ranges::__copy_or_move_backward
<false>(std::move(__first
),
450 std::move(__result
));
453 template<bidirectional_range _Range
, bidirectional_iterator _Iter
>
454 requires indirectly_copyable
<iterator_t
<_Range
>, _Iter
>
455 constexpr copy_backward_result
<borrowed_iterator_t
<_Range
>, _Iter
>
456 operator()(_Range
&& __r
, _Iter __result
) const
458 return (*this)(ranges::begin(__r
), ranges::end(__r
),
459 std::move(__result
));
463 inline constexpr __copy_backward_fn copy_backward
{};
465 struct __move_backward_fn
467 template<bidirectional_iterator _Iter1
, sentinel_for
<_Iter1
> _Sent1
,
468 bidirectional_iterator _Iter2
>
469 requires indirectly_movable
<_Iter1
, _Iter2
>
470 constexpr move_backward_result
<_Iter1
, _Iter2
>
471 operator()(_Iter1 __first
, _Sent1 __last
, _Iter2 __result
) const
473 return ranges::__copy_or_move_backward
<true>(std::move(__first
),
475 std::move(__result
));
478 template<bidirectional_range _Range
, bidirectional_iterator _Iter
>
479 requires indirectly_movable
<iterator_t
<_Range
>, _Iter
>
480 constexpr move_backward_result
<borrowed_iterator_t
<_Range
>, _Iter
>
481 operator()(_Range
&& __r
, _Iter __result
) const
483 return (*this)(ranges::begin(__r
), ranges::end(__r
),
484 std::move(__result
));
488 inline constexpr __move_backward_fn move_backward
{};
490 template<typename _Iter
, typename _Out
>
491 using copy_n_result
= in_out_result
<_Iter
, _Out
>;
495 template<input_iterator _Iter
, weakly_incrementable _Out
>
496 requires indirectly_copyable
<_Iter
, _Out
>
497 constexpr copy_n_result
<_Iter
, _Out
>
498 operator()(_Iter __first
, iter_difference_t
<_Iter
> __n
,
501 if constexpr (random_access_iterator
<_Iter
>)
502 return ranges::copy(__first
, __first
+ __n
, std::move(__result
));
505 for (; __n
> 0; --__n
, (void)++__result
, (void)++__first
)
506 *__result
= *__first
;
507 return {std::move(__first
), std::move(__result
)};
512 inline constexpr __copy_n_fn copy_n
{};
516 template<typename _Tp
, output_iterator
<const _Tp
&> _Out
>
518 operator()(_Out __first
, iter_difference_t
<_Out
> __n
,
519 const _Tp
& __value
) const
521 // TODO: implement more specializations to be at least on par with
526 // TODO: is __is_byte the best condition?
527 if constexpr (is_pointer_v
<_Out
> && __is_byte
<_Tp
>::__value
)
529 __builtin_memset(__first
, static_cast<unsigned char>(__value
), __n
);
530 return __first
+ __n
;
532 else if constexpr (is_scalar_v
<_Tp
>)
534 const auto __tmp
= __value
;
535 for (; __n
> 0; --__n
, (void)++__first
)
541 for (; __n
> 0; --__n
, (void)++__first
)
548 inline constexpr __fill_n_fn fill_n
{};
552 template<typename _Tp
,
553 output_iterator
<const _Tp
&> _Out
, sentinel_for
<_Out
> _Sent
>
555 operator()(_Out __first
, _Sent __last
, const _Tp
& __value
) const
557 // TODO: implement more specializations to be at least on par with
559 if constexpr (sized_sentinel_for
<_Sent
, _Out
>)
561 const auto __len
= __last
- __first
;
562 return ranges::fill_n(__first
, __len
, __value
);
564 else if constexpr (is_scalar_v
<_Tp
>)
566 const auto __tmp
= __value
;
567 for (; __first
!= __last
; ++__first
)
573 for (; __first
!= __last
; ++__first
)
579 template<typename _Tp
, output_range
<const _Tp
&> _Range
>
580 constexpr borrowed_iterator_t
<_Range
>
581 operator()(_Range
&& __r
, const _Tp
& __value
) const
583 return (*this)(ranges::begin(__r
), ranges::end(__r
), __value
);
587 inline constexpr __fill_fn fill
{};
589 _GLIBCXX_END_NAMESPACE_VERSION
593 #endif // _RANGES_ALGOBASE_H