1 // Algorithm extensions -*- C++ -*- 2 3 // Copyright (C) 2001-2024 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 /* 26 * 27 * Copyright (c) 1994 28 * Hewlett-Packard Company 29 * 30 * Permission to use, copy, modify, distribute and sell this software 31 * and its documentation for any purpose is hereby granted without fee, 32 * provided that the above copyright notice appear in all copies and 33 * that both that copyright notice and this permission notice appear 34 * in supporting documentation. Hewlett-Packard Company makes no 35 * representations about the suitability of this software for any 36 * purpose. It is provided "as is" without express or implied warranty. 37 * 38 * 39 * Copyright (c) 1996 40 * Silicon Graphics Computer Systems, Inc. 41 * 42 * Permission to use, copy, modify, distribute and sell this software 43 * and its documentation for any purpose is hereby granted without fee, 44 * provided that the above copyright notice appear in all copies and 45 * that both that copyright notice and this permission notice appear 46 * in supporting documentation. Silicon Graphics makes no 47 * representations about the suitability of this software for any 48 * purpose. It is provided "as is" without express or implied warranty. 49 */ 50 51 /** @file ext/algorithm 52 * This file is a GNU extension to the Standard C++ Library (possibly 53 * containing extensions from the HP/SGI STL subset). 54 */ 55 56 #ifndef _EXT_ALGORITHM 57 #define _EXT_ALGORITHM 1 58 59 #pragma GCC system_header 60 61 #include <bits/requires_hosted.h> // GNU extensions are currently omitted 62 63 #include <algorithm> 64 65 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) 66 { 67 _GLIBCXX_BEGIN_NAMESPACE_VERSION 68 69 //-------------------------------------------------- 70 // copy_n (not part of the C++ standard) 71 72 template<typename _InputIterator, typename _Size, typename _OutputIterator> 73 std::pair<_InputIterator, _OutputIterator> 74 __copy_n(_InputIterator __first, _Size __count, 75 _OutputIterator __result, 76 std::input_iterator_tag) 77 { 78 for ( ; __count > 0; --__count) 79 { 80 *__result = *__first; 81 ++__first; 82 ++__result; 83 } 84 return std::pair<_InputIterator, _OutputIterator>(__first, __result); 85 } 86 87 template<typename _RAIterator, typename _Size, typename _OutputIterator> 88 inline std::pair<_RAIterator, _OutputIterator> 89 __copy_n(_RAIterator __first, _Size __count, 90 _OutputIterator __result, 91 std::random_access_iterator_tag) 92 { 93 _RAIterator __last = __first + __count; 94 return std::pair<_RAIterator, _OutputIterator>(__last, std::copy(__first, 95 __last, 96 __result)); 97 } 98 99 /** 100 * @brief Copies the range [first,first+count) into [result,result+count). 101 * @param __first An input iterator. 102 * @param __count The number of elements to copy. 103 * @param __result An output iterator. 104 * @return A std::pair composed of first+count and result+count. 105 * 106 * This is an SGI extension. 107 * This inline function will boil down to a call to @c memmove whenever 108 * possible. Failing that, if random access iterators are passed, then the 109 * loop count will be known (and therefore a candidate for compiler 110 * optimizations such as unrolling). 111 * @ingroup SGIextensions 112 */ 113 template<typename _InputIterator, typename _Size, typename _OutputIterator> 114 inline std::pair<_InputIterator, _OutputIterator> 115 copy_n(_InputIterator __first, _Size __count, _OutputIterator __result) 116 { 117 // concept requirements 118 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 119 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 120 typename std::iterator_traits<_InputIterator>::value_type>) 121 122 return __gnu_cxx::__copy_n(__first, __count, __result, 123 std::__iterator_category(__first)); 124 } 125 126 template<typename _InputIterator1, typename _InputIterator2> 127 int 128 __lexicographical_compare_3way(_InputIterator1 __first1, 129 _InputIterator1 __last1, 130 _InputIterator2 __first2, 131 _InputIterator2 __last2) 132 { 133 while (__first1 != __last1 && __first2 != __last2) 134 { 135 if (*__first1 < *__first2) 136 return -1; 137 if (*__first2 < *__first1) 138 return 1; 139 ++__first1; 140 ++__first2; 141 } 142 if (__first2 == __last2) 143 return !(__first1 == __last1); 144 else 145 return -1; 146 } 147 148 inline int 149 __lexicographical_compare_3way(const unsigned char* __first1, 150 const unsigned char* __last1, 151 const unsigned char* __first2, 152 const unsigned char* __last2) 153 { 154 const std::ptrdiff_t __len1 = __last1 - __first1; 155 const std::ptrdiff_t __len2 = __last2 - __first2; 156 const int __result = __builtin_memcmp(__first1, __first2, 157 (std::min)(__len1, __len2)); 158 return __result != 0 ? __result 159 : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1)); 160 } 161 162 inline int 163 __lexicographical_compare_3way(const char* __first1, const char* __last1, 164 const char* __first2, const char* __last2) 165 { 166 #if CHAR_MAX == SCHAR_MAX 167 return __lexicographical_compare_3way((const signed char*) __first1, 168 (const signed char*) __last1, 169 (const signed char*) __first2, 170 (const signed char*) __last2); 171 #else 172 return __lexicographical_compare_3way((const unsigned char*) __first1, 173 (const unsigned char*) __last1, 174 (const unsigned char*) __first2, 175 (const unsigned char*) __last2); 176 #endif 177 } 178 179 /** 180 * @brief @c memcmp on steroids. 181 * @param __first1 An input iterator. 182 * @param __last1 An input iterator. 183 * @param __first2 An input iterator. 184 * @param __last2 An input iterator. 185 * @return An int, as with @c memcmp. 186 * 187 * The return value will be less than zero if the first range is 188 * <em>lexigraphically less than</em> the second, greater than zero 189 * if the second range is <em>lexigraphically less than</em> the 190 * first, and zero otherwise. 191 * This is an SGI extension. 192 * @ingroup SGIextensions 193 */ 194 template<typename _InputIterator1, typename _InputIterator2> 195 int 196 lexicographical_compare_3way(_InputIterator1 __first1, 197 _InputIterator1 __last1, 198 _InputIterator2 __first2, 199 _InputIterator2 __last2) 200 { 201 // concept requirements 202 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 203 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 204 __glibcxx_function_requires(_LessThanComparableConcept< 205 typename std::iterator_traits<_InputIterator1>::value_type>) 206 __glibcxx_function_requires(_LessThanComparableConcept< 207 typename std::iterator_traits<_InputIterator2>::value_type>) 208 __glibcxx_requires_valid_range(__first1, __last1); 209 __glibcxx_requires_valid_range(__first2, __last2); 210 211 return __lexicographical_compare_3way(__first1, __last1, __first2, 212 __last2); 213 } 214 215 // count and count_if: this version, whose return type is void, was present 216 // in the HP STL, and is retained as an extension for backward compatibility. 217 template<typename _InputIterator, typename _Tp, typename _Size> 218 void 219 count(_InputIterator __first, _InputIterator __last, 220 const _Tp& __value, 221 _Size& __n) 222 { 223 // concept requirements 224 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 225 __glibcxx_function_requires(_EqualityComparableConcept< 226 typename std::iterator_traits<_InputIterator>::value_type >) 227 __glibcxx_function_requires(_EqualityComparableConcept<_Tp>) 228 __glibcxx_requires_valid_range(__first, __last); 229 230 for ( ; __first != __last; ++__first) 231 if (*__first == __value) 232 ++__n; 233 } 234 235 template<typename _InputIterator, typename _Predicate, typename _Size> 236 void 237 count_if(_InputIterator __first, _InputIterator __last, 238 _Predicate __pred, 239 _Size& __n) 240 { 241 // concept requirements 242 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 243 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 244 typename std::iterator_traits<_InputIterator>::value_type>) 245 __glibcxx_requires_valid_range(__first, __last); 246 247 for ( ; __first != __last; ++__first) 248 if (__pred(*__first)) 249 ++__n; 250 } 251 252 // random_sample and random_sample_n (extensions, not part of the standard). 253 254 /** 255 * This is an SGI extension. 256 * @ingroup SGIextensions 257 * @doctodo 258 */ 259 template<typename _ForwardIterator, typename _OutputIterator, 260 typename _Distance> 261 _OutputIterator 262 random_sample_n(_ForwardIterator __first, _ForwardIterator __last, 263 _OutputIterator __out, const _Distance __n) 264 { 265 // concept requirements 266 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 267 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 268 typename std::iterator_traits<_ForwardIterator>::value_type>) 269 __glibcxx_requires_valid_range(__first, __last); 270 271 _Distance __remaining = std::distance(__first, __last); 272 _Distance __m = (std::min)(__n, __remaining); 273 274 while (__m > 0) 275 { 276 if ((std::rand() % __remaining) < __m) 277 { 278 *__out = *__first; 279 ++__out; 280 --__m; 281 } 282 --__remaining; 283 ++__first; 284 } 285 return __out; 286 } 287 288 /** 289 * This is an SGI extension. 290 * @ingroup SGIextensions 291 * @doctodo 292 */ 293 template<typename _ForwardIterator, typename _OutputIterator, 294 typename _Distance, typename _RandomNumberGenerator> 295 _OutputIterator 296 random_sample_n(_ForwardIterator __first, _ForwardIterator __last, 297 _OutputIterator __out, const _Distance __n, 298 _RandomNumberGenerator& __rand) 299 { 300 // concept requirements 301 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 302 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 303 typename std::iterator_traits<_ForwardIterator>::value_type>) 304 __glibcxx_function_requires(_UnaryFunctionConcept< 305 _RandomNumberGenerator, _Distance, _Distance>) 306 __glibcxx_requires_valid_range(__first, __last); 307 308 _Distance __remaining = std::distance(__first, __last); 309 _Distance __m = (std::min)(__n, __remaining); 310 311 while (__m > 0) 312 { 313 if (__rand(__remaining) < __m) 314 { 315 *__out = *__first; 316 ++__out; 317 --__m; 318 } 319 --__remaining; 320 ++__first; 321 } 322 return __out; 323 } 324 325 template<typename _InputIterator, typename _RandomAccessIterator, 326 typename _Distance> 327 _RandomAccessIterator 328 __random_sample(_InputIterator __first, _InputIterator __last, 329 _RandomAccessIterator __out, 330 const _Distance __n) 331 { 332 _Distance __m = 0; 333 _Distance __t = __n; 334 for ( ; __first != __last && __m < __n; ++__m, ++__first) 335 __out[__m] = *__first; 336 337 while (__first != __last) 338 { 339 ++__t; 340 _Distance __M = std::rand() % (__t); 341 if (__M < __n) 342 __out[__M] = *__first; 343 ++__first; 344 } 345 return __out + __m; 346 } 347 348 template<typename _InputIterator, typename _RandomAccessIterator, 349 typename _RandomNumberGenerator, typename _Distance> 350 _RandomAccessIterator 351 __random_sample(_InputIterator __first, _InputIterator __last, 352 _RandomAccessIterator __out, 353 _RandomNumberGenerator& __rand, 354 const _Distance __n) 355 { 356 // concept requirements 357 __glibcxx_function_requires(_UnaryFunctionConcept< 358 _RandomNumberGenerator, _Distance, _Distance>) 359 360 _Distance __m = 0; 361 _Distance __t = __n; 362 for ( ; __first != __last && __m < __n; ++__m, ++__first) 363 __out[__m] = *__first; 364 365 while (__first != __last) 366 { 367 ++__t; 368 _Distance __M = __rand(__t); 369 if (__M < __n) 370 __out[__M] = *__first; 371 ++__first; 372 } 373 return __out + __m; 374 } 375 376 /** 377 * This is an SGI extension. 378 * @ingroup SGIextensions 379 * @doctodo 380 */ 381 template<typename _InputIterator, typename _RandomAccessIterator> 382 inline _RandomAccessIterator 383 random_sample(_InputIterator __first, _InputIterator __last, 384 _RandomAccessIterator __out_first, 385 _RandomAccessIterator __out_last) 386 { 387 // concept requirements 388 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 389 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 390 _RandomAccessIterator>) 391 __glibcxx_requires_valid_range(__first, __last); 392 __glibcxx_requires_valid_range(__out_first, __out_last); 393 394 return __random_sample(__first, __last, 395 __out_first, __out_last - __out_first); 396 } 397 398 /** 399 * This is an SGI extension. 400 * @ingroup SGIextensions 401 * @doctodo 402 */ 403 template<typename _InputIterator, typename _RandomAccessIterator, 404 typename _RandomNumberGenerator> 405 inline _RandomAccessIterator 406 random_sample(_InputIterator __first, _InputIterator __last, 407 _RandomAccessIterator __out_first, 408 _RandomAccessIterator __out_last, 409 _RandomNumberGenerator& __rand) 410 { 411 // concept requirements 412 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 413 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 414 _RandomAccessIterator>) 415 __glibcxx_requires_valid_range(__first, __last); 416 __glibcxx_requires_valid_range(__out_first, __out_last); 417 418 return __random_sample(__first, __last, 419 __out_first, __rand, 420 __out_last - __out_first); 421 } 422 423 #if __cplusplus >= 201103L 424 using std::is_heap; 425 #else 426 /** 427 * This is an SGI extension. 428 * @ingroup SGIextensions 429 * @doctodo 430 */ 431 template<typename _RandomAccessIterator> 432 inline bool 433 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 434 { 435 // concept requirements 436 __glibcxx_function_requires(_RandomAccessIteratorConcept< 437 _RandomAccessIterator>) 438 __glibcxx_function_requires(_LessThanComparableConcept< 439 typename std::iterator_traits<_RandomAccessIterator>::value_type>) 440 __glibcxx_requires_valid_range(__first, __last); 441 442 return std::__is_heap(__first, __last - __first); 443 } 444 445 /** 446 * This is an SGI extension. 447 * @ingroup SGIextensions 448 * @doctodo 449 */ 450 template<typename _RandomAccessIterator, typename _StrictWeakOrdering> 451 inline bool 452 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 453 _StrictWeakOrdering __comp) 454 { 455 // concept requirements 456 __glibcxx_function_requires(_RandomAccessIteratorConcept< 457 _RandomAccessIterator>) 458 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, 459 typename std::iterator_traits<_RandomAccessIterator>::value_type, 460 typename std::iterator_traits<_RandomAccessIterator>::value_type>) 461 __glibcxx_requires_valid_range(__first, __last); 462 463 return std::__is_heap(__first, __comp, __last - __first); 464 } 465 #endif 466 467 #if __cplusplus >= 201103L 468 using std::is_sorted; 469 #else 470 // is_sorted, a predicated testing whether a range is sorted in 471 // nondescending order. This is an extension, not part of the C++ 472 // standard. 473 474 /** 475 * This is an SGI extension. 476 * @ingroup SGIextensions 477 * @doctodo 478 */ 479 template<typename _ForwardIterator> 480 bool 481 is_sorted(_ForwardIterator __first, _ForwardIterator __last) 482 { 483 // concept requirements 484 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 485 __glibcxx_function_requires(_LessThanComparableConcept< 486 typename std::iterator_traits<_ForwardIterator>::value_type>) 487 __glibcxx_requires_valid_range(__first, __last); 488 489 if (__first == __last) 490 return true; 491 492 _ForwardIterator __next = __first; 493 for (++__next; __next != __last; __first = __next, ++__next) 494 if (*__next < *__first) 495 return false; 496 return true; 497 } 498 499 /** 500 * This is an SGI extension. 501 * @ingroup SGIextensions 502 * @doctodo 503 */ 504 template<typename _ForwardIterator, typename _StrictWeakOrdering> 505 bool 506 is_sorted(_ForwardIterator __first, _ForwardIterator __last, 507 _StrictWeakOrdering __comp) 508 { 509 // concept requirements 510 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 511 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, 512 typename std::iterator_traits<_ForwardIterator>::value_type, 513 typename std::iterator_traits<_ForwardIterator>::value_type>) 514 __glibcxx_requires_valid_range(__first, __last); 515 516 if (__first == __last) 517 return true; 518 519 _ForwardIterator __next = __first; 520 for (++__next; __next != __last; __first = __next, ++__next) 521 if (__comp(*__next, *__first)) 522 return false; 523 return true; 524 } 525 #endif // C++11 526 527 /** 528 * @brief Find the median of three values. 529 * @param __a A value. 530 * @param __b A value. 531 * @param __c A value. 532 * @return One of @p a, @p b or @p c. 533 * 534 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n 535 * then the value returned will be @c m. 536 * This is an SGI extension. 537 * @ingroup SGIextensions 538 */ 539 template<typename _Tp> 540 const _Tp& 541 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) 542 { 543 // concept requirements 544 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 545 if (__a < __b) 546 if (__b < __c) 547 return __b; 548 else if (__a < __c) 549 return __c; 550 else 551 return __a; 552 else if (__a < __c) 553 return __a; 554 else if (__b < __c) 555 return __c; 556 else 557 return __b; 558 } 559 560 /** 561 * @brief Find the median of three values using a predicate for comparison. 562 * @param __a A value. 563 * @param __b A value. 564 * @param __c A value. 565 * @param __comp A binary predicate. 566 * @return One of @p a, @p b or @p c. 567 * 568 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m) 569 * and @p comp(m,n) are both true then the value returned will be @c m. 570 * This is an SGI extension. 571 * @ingroup SGIextensions 572 */ 573 template<typename _Tp, typename _Compare> 574 const _Tp& 575 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) 576 { 577 // concept requirements 578 __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool, 579 _Tp, _Tp>) 580 if (__comp(__a, __b)) 581 if (__comp(__b, __c)) 582 return __b; 583 else if (__comp(__a, __c)) 584 return __c; 585 else 586 return __a; 587 else if (__comp(__a, __c)) 588 return __a; 589 else if (__comp(__b, __c)) 590 return __c; 591 else 592 return __b; 593 } 594 595 _GLIBCXX_END_NAMESPACE_VERSION 596 } // namespace 597 598 #endif /* _EXT_ALGORITHM */ 599
Indexes created Sat Feb 28 05:31:39 UTC 2026