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