1// Algorithm extensions -*- C++ -*- 2 3// Copyright (C) 2001, 2002, 2004, 2005 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 2, 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// You should have received a copy of the GNU General Public License along 17// with this library; see the file COPYING. If not, write to the Free 18// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 19// USA. 20 21// As a special exception, you may use this file as part of a free software 22// library without restriction. Specifically, if other files instantiate 23// templates or use macros or inline functions from this file, or you compile 24// this file and link it with other files to produce an executable, this 25// file does not by itself cause the resulting executable to be covered by 26// the GNU General Public License. This exception does not however 27// invalidate any other reasons why the executable file might be covered by 28// the GNU General Public License. 29 30/* 31 * 32 * Copyright (c) 1994 33 * Hewlett-Packard Company 34 * 35 * Permission to use, copy, modify, distribute and sell this software 36 * and its documentation for any purpose is hereby granted without fee, 37 * provided that the above copyright notice appear in all copies and 38 * that both that copyright notice and this permission notice appear 39 * in supporting documentation. Hewlett-Packard Company makes no 40 * representations about the suitability of this software for any 41 * purpose. It is provided "as is" without express or implied warranty. 42 * 43 * 44 * Copyright (c) 1996 45 * Silicon Graphics Computer Systems, Inc. 46 * 47 * Permission to use, copy, modify, distribute and sell this software 48 * and its documentation for any purpose is hereby granted without fee, 49 * provided that the above copyright notice appear in all copies and 50 * that both that copyright notice and this permission notice appear 51 * in supporting documentation. Silicon Graphics makes no 52 * representations about the suitability of this software for any 53 * purpose. It is provided "as is" without express or implied warranty. 54 */ 55 56/** @file ext/algorithm 57 * This file is a GNU extension to the Standard C++ Library (possibly 58 * containing extensions from the HP/SGI STL subset). 59 */ 60 61#ifndef _EXT_ALGORITHM 62#define _EXT_ALGORITHM 1 63 64#pragma GCC system_header 65 66#include <algorithm> 67 68_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) 69 70 using std::ptrdiff_t; 71 using std::min; 72 using std::pair; 73 using std::input_iterator_tag; 74 using std::random_access_iterator_tag; 75 using std::iterator_traits; 76 77 //-------------------------------------------------- 78 // copy_n (not part of the C++ standard) 79 80 template<typename _InputIterator, typename _Size, typename _OutputIterator> 81 pair<_InputIterator, _OutputIterator> 82 __copy_n(_InputIterator __first, _Size __count, 83 _OutputIterator __result, 84 input_iterator_tag) 85 { 86 for ( ; __count > 0; --__count) 87 { 88 *__result = *__first; 89 ++__first; 90 ++__result; 91 } 92 return pair<_InputIterator, _OutputIterator>(__first, __result); 93 } 94 95 template<typename _RAIterator, typename _Size, typename _OutputIterator> 96 inline pair<_RAIterator, _OutputIterator> 97 __copy_n(_RAIterator __first, _Size __count, 98 _OutputIterator __result, 99 random_access_iterator_tag) 100 { 101 _RAIterator __last = __first + __count; 102 return pair<_RAIterator, _OutputIterator>(__last, std::copy(__first, 103 __last, 104 __result)); 105 } 106 107 /** 108 * @brief Copies the range [first,first+count) into [result,result+count). 109 * @param first An input iterator. 110 * @param count The number of elements to copy. 111 * @param result An output iterator. 112 * @return A std::pair composed of first+count and result+count. 113 * 114 * This is an SGI extension. 115 * This inline function will boil down to a call to @c memmove whenever 116 * possible. Failing that, if random access iterators are passed, then the 117 * loop count will be known (and therefore a candidate for compiler 118 * optimizations such as unrolling). 119 * @ingroup SGIextensions 120 */ 121 template<typename _InputIterator, typename _Size, typename _OutputIterator> 122 inline pair<_InputIterator, _OutputIterator> 123 copy_n(_InputIterator __first, _Size __count, _OutputIterator __result) 124 { 125 // concept requirements 126 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 127 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 128 typename iterator_traits<_InputIterator>::value_type>) 129 130 return __copy_n(__first, __count, __result, 131 std::__iterator_category(__first)); 132 } 133 134 template<typename _InputIterator1, typename _InputIterator2> 135 int 136 __lexicographical_compare_3way(_InputIterator1 __first1, 137 _InputIterator1 __last1, 138 _InputIterator2 __first2, 139 _InputIterator2 __last2) 140 { 141 while (__first1 != __last1 && __first2 != __last2) 142 { 143 if (*__first1 < *__first2) 144 return -1; 145 if (*__first2 < *__first1) 146 return 1; 147 ++__first1; 148 ++__first2; 149 } 150 if (__first2 == __last2) 151 return !(__first1 == __last1); 152 else 153 return -1; 154 } 155 156 inline int 157 __lexicographical_compare_3way(const unsigned char* __first1, 158 const unsigned char* __last1, 159 const unsigned char* __first2, 160 const unsigned char* __last2) 161 { 162 const ptrdiff_t __len1 = __last1 - __first1; 163 const ptrdiff_t __len2 = __last2 - __first2; 164 const int __result = std::memcmp(__first1, __first2, 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 * "lexigraphically less than" the second, greater than zero if the second 196 * range is "lexigraphically less than" the first, and zero otherwise. 197 * This is an SGI extension. 198 * @ingroup SGIextensions 199 */ 200 template<typename _InputIterator1, typename _InputIterator2> 201 int 202 lexicographical_compare_3way(_InputIterator1 __first1, 203 _InputIterator1 __last1, 204 _InputIterator2 __first2, 205 _InputIterator2 __last2) 206 { 207 // concept requirements 208 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 209 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 210 __glibcxx_function_requires(_LessThanComparableConcept< 211 typename iterator_traits<_InputIterator1>::value_type>) 212 __glibcxx_function_requires(_LessThanComparableConcept< 213 typename iterator_traits<_InputIterator2>::value_type>) 214 __glibcxx_requires_valid_range(__first1, __last1); 215 __glibcxx_requires_valid_range(__first2, __last2); 216 217 return __lexicographical_compare_3way(__first1, __last1, __first2, 218 __last2); 219 } 220 221 // count and count_if: this version, whose return type is void, was present 222 // in the HP STL, and is retained as an extension for backward compatibility. 223 template<typename _InputIterator, typename _Tp, typename _Size> 224 void 225 count(_InputIterator __first, _InputIterator __last, 226 const _Tp& __value, 227 _Size& __n) 228 { 229 // concept requirements 230 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 231 __glibcxx_function_requires(_EqualityComparableConcept< 232 typename iterator_traits<_InputIterator>::value_type >) 233 __glibcxx_function_requires(_EqualityComparableConcept<_Tp>) 234 __glibcxx_requires_valid_range(__first, __last); 235 236 for ( ; __first != __last; ++__first) 237 if (*__first == __value) 238 ++__n; 239 } 240 241 template<typename _InputIterator, typename _Predicate, typename _Size> 242 void 243 count_if(_InputIterator __first, _InputIterator __last, 244 _Predicate __pred, 245 _Size& __n) 246 { 247 // concept requirements 248 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 249 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 250 typename iterator_traits<_InputIterator>::value_type>) 251 __glibcxx_requires_valid_range(__first, __last); 252 253 for ( ; __first != __last; ++__first) 254 if (__pred(*__first)) 255 ++__n; 256 } 257 258 // random_sample and random_sample_n (extensions, not part of the standard). 259 260 /** 261 * This is an SGI extension. 262 * @ingroup SGIextensions 263 * @doctodo 264 */ 265 template<typename _ForwardIterator, typename _OutputIterator, 266 typename _Distance> 267 _OutputIterator 268 random_sample_n(_ForwardIterator __first, _ForwardIterator __last, 269 _OutputIterator __out, const _Distance __n) 270 { 271 // concept requirements 272 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 273 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 274 typename iterator_traits<_ForwardIterator>::value_type>) 275 __glibcxx_requires_valid_range(__first, __last); 276 277 _Distance __remaining = std::distance(__first, __last); 278 _Distance __m = min(__n, __remaining); 279 280 while (__m > 0) 281 { 282 if ((std::rand() % __remaining) < __m) 283 { 284 *__out = *__first; 285 ++__out; 286 --__m; 287 } 288 --__remaining; 289 ++__first; 290 } 291 return __out; 292 } 293 294 /** 295 * This is an SGI extension. 296 * @ingroup SGIextensions 297 * @doctodo 298 */ 299 template<typename _ForwardIterator, typename _OutputIterator, 300 typename _Distance, typename _RandomNumberGenerator> 301 _OutputIterator 302 random_sample_n(_ForwardIterator __first, _ForwardIterator __last, 303 _OutputIterator __out, const _Distance __n, 304 _RandomNumberGenerator& __rand) 305 { 306 // concept requirements 307 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 308 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 309 typename iterator_traits<_ForwardIterator>::value_type>) 310 __glibcxx_function_requires(_UnaryFunctionConcept< 311 _RandomNumberGenerator, _Distance, _Distance>) 312 __glibcxx_requires_valid_range(__first, __last); 313 314 _Distance __remaining = std::distance(__first, __last); 315 _Distance __m = min(__n, __remaining); 316 317 while (__m > 0) 318 { 319 if (__rand(__remaining) < __m) 320 { 321 *__out = *__first; 322 ++__out; 323 --__m; 324 } 325 --__remaining; 326 ++__first; 327 } 328 return __out; 329 } 330 331 template<typename _InputIterator, typename _RandomAccessIterator, 332 typename _Distance> 333 _RandomAccessIterator 334 __random_sample(_InputIterator __first, _InputIterator __last, 335 _RandomAccessIterator __out, 336 const _Distance __n) 337 { 338 _Distance __m = 0; 339 _Distance __t = __n; 340 for ( ; __first != __last && __m < __n; ++__m, ++__first) 341 __out[__m] = *__first; 342 343 while (__first != __last) 344 { 345 ++__t; 346 _Distance __M = std::rand() % (__t); 347 if (__M < __n) 348 __out[__M] = *__first; 349 ++__first; 350 } 351 return __out + __m; 352 } 353 354 template<typename _InputIterator, typename _RandomAccessIterator, 355 typename _RandomNumberGenerator, typename _Distance> 356 _RandomAccessIterator 357 __random_sample(_InputIterator __first, _InputIterator __last, 358 _RandomAccessIterator __out, 359 _RandomNumberGenerator& __rand, 360 const _Distance __n) 361 { 362 // concept requirements 363 __glibcxx_function_requires(_UnaryFunctionConcept< 364 _RandomNumberGenerator, _Distance, _Distance>) 365 366 _Distance __m = 0; 367 _Distance __t = __n; 368 for ( ; __first != __last && __m < __n; ++__m, ++__first) 369 __out[__m] = *__first; 370 371 while (__first != __last) 372 { 373 ++__t; 374 _Distance __M = __rand(__t); 375 if (__M < __n) 376 __out[__M] = *__first; 377 ++__first; 378 } 379 return __out + __m; 380 } 381 382 /** 383 * This is an SGI extension. 384 * @ingroup SGIextensions 385 * @doctodo 386 */ 387 template<typename _InputIterator, typename _RandomAccessIterator> 388 inline _RandomAccessIterator 389 random_sample(_InputIterator __first, _InputIterator __last, 390 _RandomAccessIterator __out_first, 391 _RandomAccessIterator __out_last) 392 { 393 // concept requirements 394 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 395 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 396 _RandomAccessIterator>) 397 __glibcxx_requires_valid_range(__first, __last); 398 __glibcxx_requires_valid_range(__out_first, __out_last); 399 400 return __random_sample(__first, __last, 401 __out_first, __out_last - __out_first); 402 } 403 404 /** 405 * This is an SGI extension. 406 * @ingroup SGIextensions 407 * @doctodo 408 */ 409 template<typename _InputIterator, typename _RandomAccessIterator, 410 typename _RandomNumberGenerator> 411 inline _RandomAccessIterator 412 random_sample(_InputIterator __first, _InputIterator __last, 413 _RandomAccessIterator __out_first, 414 _RandomAccessIterator __out_last, 415 _RandomNumberGenerator& __rand) 416 { 417 // concept requirements 418 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 419 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 420 _RandomAccessIterator>) 421 __glibcxx_requires_valid_range(__first, __last); 422 __glibcxx_requires_valid_range(__out_first, __out_last); 423 424 return __random_sample(__first, __last, 425 __out_first, __rand, 426 __out_last - __out_first); 427 } 428 429 /** 430 * This is an SGI extension. 431 * @ingroup SGIextensions 432 * @doctodo 433 */ 434 template<typename _RandomAccessIterator> 435 inline bool 436 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 437 { 438 // concept requirements 439 __glibcxx_function_requires(_RandomAccessIteratorConcept< 440 _RandomAccessIterator>) 441 __glibcxx_function_requires(_LessThanComparableConcept< 442 typename iterator_traits<_RandomAccessIterator>::value_type>) 443 __glibcxx_requires_valid_range(__first, __last); 444 445 return std::__is_heap(__first, __last - __first); 446 } 447 448 /** 449 * This is an SGI extension. 450 * @ingroup SGIextensions 451 * @doctodo 452 */ 453 template<typename _RandomAccessIterator, typename _StrictWeakOrdering> 454 inline bool 455 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 456 _StrictWeakOrdering __comp) 457 { 458 // concept requirements 459 __glibcxx_function_requires(_RandomAccessIteratorConcept< 460 _RandomAccessIterator>) 461 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, 462 typename iterator_traits<_RandomAccessIterator>::value_type, 463 typename iterator_traits<_RandomAccessIterator>::value_type>) 464 __glibcxx_requires_valid_range(__first, __last); 465 466 return std::__is_heap(__first, __comp, __last - __first); 467 } 468 469 // is_sorted, a predicated testing whether a range is sorted in 470 // nondescending order. This is an extension, not part of the C++ 471 // standard. 472 473 /** 474 * This is an SGI extension. 475 * @ingroup SGIextensions 476 * @doctodo 477 */ 478 template<typename _ForwardIterator> 479 bool 480 is_sorted(_ForwardIterator __first, _ForwardIterator __last) 481 { 482 // concept requirements 483 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 484 __glibcxx_function_requires(_LessThanComparableConcept< 485 typename iterator_traits<_ForwardIterator>::value_type>) 486 __glibcxx_requires_valid_range(__first, __last); 487 488 if (__first == __last) 489 return true; 490 491 _ForwardIterator __next = __first; 492 for (++__next; __next != __last; __first = __next, ++__next) 493 if (*__next < *__first) 494 return false; 495 return true; 496 } 497 498 /** 499 * This is an SGI extension. 500 * @ingroup SGIextensions 501 * @doctodo 502 */ 503 template<typename _ForwardIterator, typename _StrictWeakOrdering> 504 bool 505 is_sorted(_ForwardIterator __first, _ForwardIterator __last, 506 _StrictWeakOrdering __comp) 507 { 508 // concept requirements 509 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 510 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, 511 typename iterator_traits<_ForwardIterator>::value_type, 512 typename iterator_traits<_ForwardIterator>::value_type>) 513 __glibcxx_requires_valid_range(__first, __last); 514 515 if (__first == __last) 516 return true; 517 518 _ForwardIterator __next = __first; 519 for (++__next; __next != __last; __first = __next, ++__next) 520 if (__comp(*__next, *__first)) 521 return false; 522 return true; 523 } 524 525_GLIBCXX_END_NAMESPACE 526 527#endif /* _EXT_ALGORITHM */ 528