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