1 // Core algorithmic facilities -*- C++ -*- 2 3 // Copyright (C) 2020-2022 Free Software Foundation, Inc. 4 // 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) 9 // any later version. 10 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. 15 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. 19 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/>. 24 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} 28 */ 29 30 #ifndef _RANGES_ALGOBASE_H 31 #define _RANGES_ALGOBASE_H 1 32 33 #if __cplusplus > 201703L 34 35 #include <compare> 36 #include <bits/stl_iterator_base_types.h> 37 #include <bits/stl_iterator_base_funcs.h> 38 #include <bits/stl_iterator.h> 39 #include <bits/ranges_base.h> // ranges::begin, ranges::range etc. 40 #include <bits/invoke.h> // __invoke 41 #include <bits/cpp_type_traits.h> // __is_byte 42 43 #if __cpp_lib_concepts 44 namespace std _GLIBCXX_VISIBILITY(default) 45 { 46 _GLIBCXX_BEGIN_NAMESPACE_VERSION 47 namespace ranges 48 { 49 namespace __detail 50 { 51 template<typename _Tp> 52 constexpr inline bool __is_normal_iterator = false; 53 54 template<typename _Iterator, typename _Container> 55 constexpr inline bool 56 __is_normal_iterator<__gnu_cxx::__normal_iterator<_Iterator, 57 _Container>> = true; 58 59 template<typename _Tp> 60 constexpr inline bool __is_reverse_iterator = false; 61 62 template<typename _Iterator> 63 constexpr inline bool 64 __is_reverse_iterator<reverse_iterator<_Iterator>> = true; 65 66 template<typename _Tp> 67 constexpr inline bool __is_move_iterator = false; 68 69 template<typename _Iterator> 70 constexpr inline bool 71 __is_move_iterator<move_iterator<_Iterator>> = true; 72 } // namespace __detail 73 74 struct __equal_fn 75 { 76 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, 77 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, 78 typename _Pred = ranges::equal_to, 79 typename _Proj1 = identity, typename _Proj2 = identity> 80 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> 81 constexpr bool 82 operator()(_Iter1 __first1, _Sent1 __last1, 83 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {}, 84 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 85 { 86 // TODO: implement more specializations to at least have parity with 87 // std::equal. 88 if constexpr (__detail::__is_normal_iterator<_Iter1> 89 && same_as<_Iter1, _Sent1>) 90 return (*this)(__first1.base(), __last1.base(), 91 std::move(__first2), std::move(__last2), 92 std::move(__pred), 93 std::move(__proj1), std::move(__proj2)); 94 else if constexpr (__detail::__is_normal_iterator<_Iter2> 95 && same_as<_Iter2, _Sent2>) 96 return (*this)(std::move(__first1), std::move(__last1), 97 __first2.base(), __last2.base(), 98 std::move(__pred), 99 std::move(__proj1), std::move(__proj2)); 100 else if constexpr (sized_sentinel_for<_Sent1, _Iter1> 101 && sized_sentinel_for<_Sent2, _Iter2>) 102 { 103 auto __d1 = ranges::distance(__first1, __last1); 104 auto __d2 = ranges::distance(__first2, __last2); 105 if (__d1 != __d2) 106 return false; 107 108 using _ValueType1 = iter_value_t<_Iter1>; 109 constexpr bool __use_memcmp 110 = ((is_integral_v<_ValueType1> || is_pointer_v<_ValueType1>) 111 && __memcmpable<_Iter1, _Iter2>::__value 112 && is_same_v<_Pred, ranges::equal_to> 113 && is_same_v<_Proj1, identity> 114 && is_same_v<_Proj2, identity>); 115 if constexpr (__use_memcmp) 116 { 117 if (const size_t __len = (__last1 - __first1)) 118 return !std::__memcmp(__first1, __first2, __len); 119 return true; 120 } 121 else 122 { 123 for (; __first1 != __last1; ++__first1, (void)++__first2) 124 if (!(bool)std::__invoke(__pred, 125 std::__invoke(__proj1, *__first1), 126 std::__invoke(__proj2, *__first2))) 127 return false; 128 return true; 129 } 130 } 131 else 132 { 133 for (; __first1 != __last1 && __first2 != __last2; 134 ++__first1, (void)++__first2) 135 if (!(bool)std::__invoke(__pred, 136 std::__invoke(__proj1, *__first1), 137 std::__invoke(__proj2, *__first2))) 138 return false; 139 return __first1 == __last1 && __first2 == __last2; 140 } 141 } 142 143 template<input_range _Range1, input_range _Range2, 144 typename _Pred = ranges::equal_to, 145 typename _Proj1 = identity, typename _Proj2 = identity> 146 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, 147 _Pred, _Proj1, _Proj2> 148 constexpr bool 149 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, 150 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 151 { 152 return (*this)(ranges::begin(__r1), ranges::end(__r1), 153 ranges::begin(__r2), ranges::end(__r2), 154 std::move(__pred), 155 std::move(__proj1), std::move(__proj2)); 156 } 157 }; 158 159 inline constexpr __equal_fn equal{}; 160 161 template<typename _Iter, typename _Out> 162 struct in_out_result 163 { 164 [[no_unique_address]] _Iter in; 165 [[no_unique_address]] _Out out; 166 167 template<typename _Iter2, typename _Out2> 168 requires convertible_to<const _Iter&, _Iter2> 169 && convertible_to<const _Out&, _Out2> 170 constexpr 171 operator in_out_result<_Iter2, _Out2>() const & 172 { return {in, out}; } 173 174 template<typename _Iter2, typename _Out2> 175 requires convertible_to<_Iter, _Iter2> 176 && convertible_to<_Out, _Out2> 177 constexpr 178 operator in_out_result<_Iter2, _Out2>() && 179 { return {std::move(in), std::move(out)}; } 180 }; 181 182 template<typename _Iter, typename _Out> 183 using copy_result = in_out_result<_Iter, _Out>; 184 185 template<typename _Iter, typename _Out> 186 using move_result = in_out_result<_Iter, _Out>; 187 188 template<typename _Iter1, typename _Iter2> 189 using move_backward_result = in_out_result<_Iter1, _Iter2>; 190 191 template<typename _Iter1, typename _Iter2> 192 using copy_backward_result = in_out_result<_Iter1, _Iter2>; 193 194 template<bool _IsMove, 195 bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, 196 bidirectional_iterator _Out> 197 requires (_IsMove 198 ? indirectly_movable<_Iter, _Out> 199 : indirectly_copyable<_Iter, _Out>) 200 constexpr __conditional_t<_IsMove, 201 move_backward_result<_Iter, _Out>, 202 copy_backward_result<_Iter, _Out>> 203 __copy_or_move_backward(_Iter __first, _Sent __last, _Out __result); 204 205 template<bool _IsMove, 206 input_iterator _Iter, sentinel_for<_Iter> _Sent, 207 weakly_incrementable _Out> 208 requires (_IsMove 209 ? indirectly_movable<_Iter, _Out> 210 : indirectly_copyable<_Iter, _Out>) 211 constexpr __conditional_t<_IsMove, 212 move_result<_Iter, _Out>, 213 copy_result<_Iter, _Out>> 214 __copy_or_move(_Iter __first, _Sent __last, _Out __result) 215 { 216 // TODO: implement more specializations to be at least on par with 217 // std::copy/std::move. 218 using __detail::__is_move_iterator; 219 using __detail::__is_reverse_iterator; 220 using __detail::__is_normal_iterator; 221 if constexpr (__is_move_iterator<_Iter> && same_as<_Iter, _Sent>) 222 { 223 auto [__in, __out] 224 = ranges::__copy_or_move<true>(std::move(__first).base(), 225 std::move(__last).base(), 226 std::move(__result)); 227 return {move_iterator{std::move(__in)}, std::move(__out)}; 228 } 229 else if constexpr (__is_reverse_iterator<_Iter> && same_as<_Iter, _Sent> 230 && __is_reverse_iterator<_Out>) 231 { 232 auto [__in,__out] 233 = ranges::__copy_or_move_backward<_IsMove>(std::move(__last).base(), 234 std::move(__first).base(), 235 std::move(__result).base()); 236 return {reverse_iterator{std::move(__in)}, 237 reverse_iterator{std::move(__out)}}; 238 } 239 else if constexpr (__is_normal_iterator<_Iter> && same_as<_Iter, _Sent>) 240 { 241 auto [__in,__out] 242 = ranges::__copy_or_move<_IsMove>(__first.base(), __last.base(), 243 std::move(__result)); 244 return {decltype(__first){__in}, std::move(__out)}; 245 } 246 else if constexpr (__is_normal_iterator<_Out>) 247 { 248 auto [__in,__out] 249 = ranges::__copy_or_move<_IsMove>(std::move(__first), __last, __result.base()); 250 return {std::move(__in), decltype(__result){__out}}; 251 } 252 else if constexpr (sized_sentinel_for<_Sent, _Iter>) 253 { 254 if (!std::__is_constant_evaluated()) 255 { 256 if constexpr (__memcpyable<_Iter, _Out>::__value) 257 { 258 using _ValueTypeI = iter_value_t<_Iter>; 259 static_assert(_IsMove 260 ? is_move_assignable_v<_ValueTypeI> 261 : is_copy_assignable_v<_ValueTypeI>); 262 auto __num = __last - __first; 263 if (__num) 264 __builtin_memmove(__result, __first, 265 sizeof(_ValueTypeI) * __num); 266 return {__first + __num, __result + __num}; 267 } 268 } 269 270 for (auto __n = __last - __first; __n > 0; --__n) 271 { 272 if constexpr (_IsMove) 273 *__result = std::move(*__first); 274 else 275 *__result = *__first; 276 ++__first; 277 ++__result; 278 } 279 return {std::move(__first), std::move(__result)}; 280 } 281 else 282 { 283 while (__first != __last) 284 { 285 if constexpr (_IsMove) 286 *__result = std::move(*__first); 287 else 288 *__result = *__first; 289 ++__first; 290 ++__result; 291 } 292 return {std::move(__first), std::move(__result)}; 293 } 294 } 295 296 struct __copy_fn 297 { 298 template<input_iterator _Iter, sentinel_for<_Iter> _Sent, 299 weakly_incrementable _Out> 300 requires indirectly_copyable<_Iter, _Out> 301 constexpr copy_result<_Iter, _Out> 302 operator()(_Iter __first, _Sent __last, _Out __result) const 303 { 304 return ranges::__copy_or_move<false>(std::move(__first), 305 std::move(__last), 306 std::move(__result)); 307 } 308 309 template<input_range _Range, weakly_incrementable _Out> 310 requires indirectly_copyable<iterator_t<_Range>, _Out> 311 constexpr copy_result<borrowed_iterator_t<_Range>, _Out> 312 operator()(_Range&& __r, _Out __result) const 313 { 314 return (*this)(ranges::begin(__r), ranges::end(__r), 315 std::move(__result)); 316 } 317 }; 318 319 inline constexpr __copy_fn copy{}; 320 321 struct __move_fn 322 { 323 template<input_iterator _Iter, sentinel_for<_Iter> _Sent, 324 weakly_incrementable _Out> 325 requires indirectly_movable<_Iter, _Out> 326 constexpr move_result<_Iter, _Out> 327 operator()(_Iter __first, _Sent __last, _Out __result) const 328 { 329 return ranges::__copy_or_move<true>(std::move(__first), 330 std::move(__last), 331 std::move(__result)); 332 } 333 334 template<input_range _Range, weakly_incrementable _Out> 335 requires indirectly_movable<iterator_t<_Range>, _Out> 336 constexpr move_result<borrowed_iterator_t<_Range>, _Out> 337 operator()(_Range&& __r, _Out __result) const 338 { 339 return (*this)(ranges::begin(__r), ranges::end(__r), 340 std::move(__result)); 341 } 342 }; 343 344 inline constexpr __move_fn move{}; 345 346 template<bool _IsMove, 347 bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, 348 bidirectional_iterator _Out> 349 requires (_IsMove 350 ? indirectly_movable<_Iter, _Out> 351 : indirectly_copyable<_Iter, _Out>) 352 constexpr __conditional_t<_IsMove, 353 move_backward_result<_Iter, _Out>, 354 copy_backward_result<_Iter, _Out>> 355 __copy_or_move_backward(_Iter __first, _Sent __last, _Out __result) 356 { 357 // TODO: implement more specializations to be at least on par with 358 // std::copy_backward/std::move_backward. 359 using __detail::__is_reverse_iterator; 360 using __detail::__is_normal_iterator; 361 if constexpr (__is_reverse_iterator<_Iter> && same_as<_Iter, _Sent> 362 && __is_reverse_iterator<_Out>) 363 { 364 auto [__in,__out] 365 = ranges::__copy_or_move<_IsMove>(std::move(__last).base(), 366 std::move(__first).base(), 367 std::move(__result).base()); 368 return {reverse_iterator{std::move(__in)}, 369 reverse_iterator{std::move(__out)}}; 370 } 371 else if constexpr (__is_normal_iterator<_Iter> && same_as<_Iter, _Sent>) 372 { 373 auto [__in,__out] 374 = ranges::__copy_or_move_backward<_IsMove>(__first.base(), 375 __last.base(), 376 std::move(__result)); 377 return {decltype(__first){__in}, std::move(__out)}; 378 } 379 else if constexpr (__is_normal_iterator<_Out>) 380 { 381 auto [__in,__out] 382 = ranges::__copy_or_move_backward<_IsMove>(std::move(__first), 383 std::move(__last), 384 __result.base()); 385 return {std::move(__in), decltype(__result){__out}}; 386 } 387 else if constexpr (sized_sentinel_for<_Sent, _Iter>) 388 { 389 if (!std::__is_constant_evaluated()) 390 { 391 if constexpr (__memcpyable<_Out, _Iter>::__value) 392 { 393 using _ValueTypeI = iter_value_t<_Iter>; 394 static_assert(_IsMove 395 ? is_move_assignable_v<_ValueTypeI> 396 : is_copy_assignable_v<_ValueTypeI>); 397 auto __num = __last - __first; 398 if (__num) 399 __builtin_memmove(__result - __num, __first, 400 sizeof(_ValueTypeI) * __num); 401 return {__first + __num, __result - __num}; 402 } 403 } 404 405 auto __lasti = ranges::next(__first, __last); 406 auto __tail = __lasti; 407 408 for (auto __n = __last - __first; __n > 0; --__n) 409 { 410 --__tail; 411 --__result; 412 if constexpr (_IsMove) 413 *__result = std::move(*__tail); 414 else 415 *__result = *__tail; 416 } 417 return {std::move(__lasti), std::move(__result)}; 418 } 419 else 420 { 421 auto __lasti = ranges::next(__first, __last); 422 auto __tail = __lasti; 423 424 while (__first != __tail) 425 { 426 --__tail; 427 --__result; 428 if constexpr (_IsMove) 429 *__result = std::move(*__tail); 430 else 431 *__result = *__tail; 432 } 433 return {std::move(__lasti), std::move(__result)}; 434 } 435 } 436 437 struct __copy_backward_fn 438 { 439 template<bidirectional_iterator _Iter1, sentinel_for<_Iter1> _Sent1, 440 bidirectional_iterator _Iter2> 441 requires indirectly_copyable<_Iter1, _Iter2> 442 constexpr copy_backward_result<_Iter1, _Iter2> 443 operator()(_Iter1 __first, _Sent1 __last, _Iter2 __result) const 444 { 445 return ranges::__copy_or_move_backward<false>(std::move(__first), 446 std::move(__last), 447 std::move(__result)); 448 } 449 450 template<bidirectional_range _Range, bidirectional_iterator _Iter> 451 requires indirectly_copyable<iterator_t<_Range>, _Iter> 452 constexpr copy_backward_result<borrowed_iterator_t<_Range>, _Iter> 453 operator()(_Range&& __r, _Iter __result) const 454 { 455 return (*this)(ranges::begin(__r), ranges::end(__r), 456 std::move(__result)); 457 } 458 }; 459 460 inline constexpr __copy_backward_fn copy_backward{}; 461 462 struct __move_backward_fn 463 { 464 template<bidirectional_iterator _Iter1, sentinel_for<_Iter1> _Sent1, 465 bidirectional_iterator _Iter2> 466 requires indirectly_movable<_Iter1, _Iter2> 467 constexpr move_backward_result<_Iter1, _Iter2> 468 operator()(_Iter1 __first, _Sent1 __last, _Iter2 __result) const 469 { 470 return ranges::__copy_or_move_backward<true>(std::move(__first), 471 std::move(__last), 472 std::move(__result)); 473 } 474 475 template<bidirectional_range _Range, bidirectional_iterator _Iter> 476 requires indirectly_movable<iterator_t<_Range>, _Iter> 477 constexpr move_backward_result<borrowed_iterator_t<_Range>, _Iter> 478 operator()(_Range&& __r, _Iter __result) const 479 { 480 return (*this)(ranges::begin(__r), ranges::end(__r), 481 std::move(__result)); 482 } 483 }; 484 485 inline constexpr __move_backward_fn move_backward{}; 486 487 template<typename _Iter, typename _Out> 488 using copy_n_result = in_out_result<_Iter, _Out>; 489 490 struct __copy_n_fn 491 { 492 template<input_iterator _Iter, weakly_incrementable _Out> 493 requires indirectly_copyable<_Iter, _Out> 494 constexpr copy_n_result<_Iter, _Out> 495 operator()(_Iter __first, iter_difference_t<_Iter> __n, 496 _Out __result) const 497 { 498 if constexpr (random_access_iterator<_Iter>) 499 { 500 if (__n > 0) 501 return ranges::copy(__first, __first + __n, std::move(__result)); 502 } 503 else 504 { 505 for (; __n > 0; --__n, (void)++__result, (void)++__first) 506 *__result = *__first; 507 } 508 return {std::move(__first), std::move(__result)}; 509 } 510 }; 511 512 inline constexpr __copy_n_fn copy_n{}; 513 514 struct __fill_n_fn 515 { 516 template<typename _Tp, output_iterator<const _Tp&> _Out> 517 constexpr _Out 518 operator()(_Out __first, iter_difference_t<_Out> __n, 519 const _Tp& __value) const 520 { 521 // TODO: implement more specializations to be at least on par with 522 // std::fill_n 523 if (__n <= 0) 524 return __first; 525 526 if constexpr (is_scalar_v<_Tp>) 527 { 528 // TODO: Generalize this optimization to contiguous iterators. 529 if constexpr (is_pointer_v<_Out> 530 // Note that __is_byte already implies !is_volatile. 531 && __is_byte<remove_pointer_t<_Out>>::__value 532 && integral<_Tp>) 533 { 534 if (!std::__is_constant_evaluated()) 535 { 536 __builtin_memset(__first, 537 static_cast<unsigned char>(__value), 538 __n); 539 return __first + __n; 540 } 541 } 542 543 const auto __tmp = __value; 544 for (; __n > 0; --__n, (void)++__first) 545 *__first = __tmp; 546 return __first; 547 } 548 else 549 { 550 for (; __n > 0; --__n, (void)++__first) 551 *__first = __value; 552 return __first; 553 } 554 } 555 }; 556 557 inline constexpr __fill_n_fn fill_n{}; 558 559 struct __fill_fn 560 { 561 template<typename _Tp, 562 output_iterator<const _Tp&> _Out, sentinel_for<_Out> _Sent> 563 constexpr _Out 564 operator()(_Out __first, _Sent __last, const _Tp& __value) const 565 { 566 // TODO: implement more specializations to be at least on par with 567 // std::fill 568 if constexpr (sized_sentinel_for<_Sent, _Out>) 569 { 570 const auto __len = __last - __first; 571 return ranges::fill_n(__first, __len, __value); 572 } 573 else if constexpr (is_scalar_v<_Tp>) 574 { 575 const auto __tmp = __value; 576 for (; __first != __last; ++__first) 577 *__first = __tmp; 578 return __first; 579 } 580 else 581 { 582 for (; __first != __last; ++__first) 583 *__first = __value; 584 return __first; 585 } 586 } 587 588 template<typename _Tp, output_range<const _Tp&> _Range> 589 constexpr borrowed_iterator_t<_Range> 590 operator()(_Range&& __r, const _Tp& __value) const 591 { 592 return (*this)(ranges::begin(__r), ranges::end(__r), __value); 593 } 594 }; 595 596 inline constexpr __fill_fn fill{}; 597 } 598 _GLIBCXX_END_NAMESPACE_VERSION 599 } // namespace std 600 #endif // concepts 601 #endif // C++20 602 #endif // _RANGES_ALGOBASE_H 603