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