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