algorithm revision 102782
1// Algorithm extensions -*- C++ -*- 2 3// Copyright (C) 2001, 2002 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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). You should only 59 * include this header if you are using GCC 3 or later. 60 */ 61 62#ifndef _EXT_ALGORITHM 63#define _EXT_ALGORITHM 64 65#pragma GCC system_header 66#include <algorithm> 67 68namespace __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 _InputIter, typename _Size, typename _OutputIter> 81 pair<_InputIter, _OutputIter> 82 __copy_n(_InputIter __first, _Size __count, 83 _OutputIter __result, 84 input_iterator_tag) 85 { 86 for ( ; __count > 0; --__count) { 87 *__result = *__first; 88 ++__first; 89 ++__result; 90 } 91 return pair<_InputIter, _OutputIter>(__first, __result); 92 } 93 94 template<typename _RAIter, typename _Size, typename _OutputIter> 95 inline pair<_RAIter, _OutputIter> 96 __copy_n(_RAIter __first, _Size __count, 97 _OutputIter __result, 98 random_access_iterator_tag) 99 { 100 _RAIter __last = __first + __count; 101 return pair<_RAIter, _OutputIter>(__last, 102 std::copy(__first, __last, __result)); 103 } 104 105 /** 106 * @brief Copies the range [first,first+count) into [result,result+count). 107 * @param first An input iterator. 108 * @param count The number of elements to copy. 109 * @param result An output iterator. 110 * @return A std::pair composed of first+count and result+count. 111 * 112 * This is an SGI extension. 113 * This inline function will boil down to a call to @c memmove whenever 114 * possible. Failing that, if random access iterators are passed, then the 115 * loop count will be known (and therefore a candidate for compiler 116 * optimizations such as unrolling). 117 * @ingroup SGIextensions 118 */ 119 template<typename _InputIter, typename _Size, typename _OutputIter> 120 inline pair<_InputIter, _OutputIter> 121 copy_n(_InputIter __first, _Size __count, _OutputIter __result) 122 { 123 // concept requirements 124 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 125 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 126 typename iterator_traits<_InputIter>::value_type>) 127 128 return __copy_n(__first, __count, __result, 129 std::__iterator_category(__first)); 130 } 131 132 template<typename _InputIter1, typename _InputIter2> 133 int 134 __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1, 135 _InputIter2 __first2, _InputIter2 __last2) 136 { 137 while (__first1 != __last1 && __first2 != __last2) { 138 if (*__first1 < *__first2) 139 return -1; 140 if (*__first2 < *__first1) 141 return 1; 142 ++__first1; 143 ++__first2; 144 } 145 if (__first2 == __last2) { 146 return !(__first1 == __last1); 147 } 148 else { 149 return -1; 150 } 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 = std::memcmp(__first1, __first2, min(__len1, __len2)); 162 return __result != 0 ? __result 163 : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1)); 164 } 165 166 inline int 167 __lexicographical_compare_3way(const char* __first1, const char* __last1, 168 const char* __first2, const char* __last2) 169 { 170#if CHAR_MAX == SCHAR_MAX 171 return __lexicographical_compare_3way( 172 (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 * "lexigraphically less than" the second, greater than zero if the second 194 * range is "lexigraphically less than" the first, and zero otherwise. 195 * This is an SGI extension. 196 * @ingroup SGIextensions 197 */ 198 template<typename _InputIter1, typename _InputIter2> 199 int 200 lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1, 201 _InputIter2 __first2, _InputIter2 __last2) 202 { 203 // concept requirements 204 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 205 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 206 __glibcpp_function_requires(_LessThanComparableConcept< 207 typename iterator_traits<_InputIter1>::value_type>) 208 __glibcpp_function_requires(_LessThanComparableConcept< 209 typename iterator_traits<_InputIter2>::value_type>) 210 211 return __lexicographical_compare_3way(__first1, __last1, __first2, __last2); 212 } 213 214 // count and count_if: this version, whose return type is void, was present 215 // in the HP STL, and is retained as an extension for backward compatibility. 216 217 template<typename _InputIter, typename _Tp, typename _Size> 218 void 219 count(_InputIter __first, _InputIter __last, 220 const _Tp& __value, 221 _Size& __n) 222 { 223 // concept requirements 224 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 225 __glibcpp_function_requires(_EqualityComparableConcept< 226 typename iterator_traits<_InputIter>::value_type >) 227 __glibcpp_function_requires(_EqualityComparableConcept<_Tp>) 228 for ( ; __first != __last; ++__first) 229 if (*__first == __value) 230 ++__n; 231 } 232 233 template<typename _InputIter, typename _Predicate, typename _Size> 234 void 235 count_if(_InputIter __first, _InputIter __last, 236 _Predicate __pred, 237 _Size& __n) 238 { 239 // concept requirements 240 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 241 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 242 typename iterator_traits<_InputIter>::value_type>) 243 for ( ; __first != __last; ++__first) 244 if (__pred(*__first)) 245 ++__n; 246 } 247 248 // random_sample and random_sample_n (extensions, not part of the standard). 249 250 /** 251 * This is an SGI extension. 252 * @ingroup SGIextensions 253 * @doctodo 254 */ 255 template<typename _ForwardIter, typename _OutputIter, typename _Distance> 256 _OutputIter 257 random_sample_n(_ForwardIter __first, _ForwardIter __last, 258 _OutputIter __out, const _Distance __n) 259 { 260 // concept requirements 261 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 262 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 263 typename iterator_traits<_ForwardIter>::value_type>) 264 265 _Distance __remaining = std::distance(__first, __last); 266 _Distance __m = min(__n, __remaining); 267 268 while (__m > 0) { 269 if (std::__random_number(__remaining) < __m) { 270 *__out = *__first; 271 ++__out; 272 --__m; 273 } 274 275 --__remaining; 276 ++__first; 277 } 278 return __out; 279 } 280 281 /** 282 * This is an SGI extension. 283 * @ingroup SGIextensions 284 * @doctodo 285 */ 286 template<typename _ForwardIter, typename _OutputIter, typename _Distance, 287 typename _RandomNumberGenerator> 288 _OutputIter 289 random_sample_n(_ForwardIter __first, _ForwardIter __last, 290 _OutputIter __out, const _Distance __n, 291 _RandomNumberGenerator& __rand) 292 { 293 // concept requirements 294 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 295 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 296 typename iterator_traits<_ForwardIter>::value_type>) 297 __glibcpp_function_requires(_UnaryFunctionConcept< 298 _RandomNumberGenerator, _Distance, _Distance>) 299 300 _Distance __remaining = std::distance(__first, __last); 301 _Distance __m = min(__n, __remaining); 302 303 while (__m > 0) { 304 if (__rand(__remaining) < __m) { 305 *__out = *__first; 306 ++__out; 307 --__m; 308 } 309 310 --__remaining; 311 ++__first; 312 } 313 return __out; 314 } 315 316 template<typename _InputIter, typename _RandomAccessIter, typename _Distance> 317 _RandomAccessIter 318 __random_sample(_InputIter __first, _InputIter __last, 319 _RandomAccessIter __out, 320 const _Distance __n) 321 { 322 _Distance __m = 0; 323 _Distance __t = __n; 324 for ( ; __first != __last && __m < __n; ++__m, ++__first) 325 __out[__m] = *__first; 326 327 while (__first != __last) { 328 ++__t; 329 _Distance __M = std::__random_number(__t); 330 if (__M < __n) 331 __out[__M] = *__first; 332 ++__first; 333 } 334 335 return __out + __m; 336 } 337 338 template<typename _InputIter, typename _RandomAccessIter, 339 typename _RandomNumberGenerator, typename _Distance> 340 _RandomAccessIter 341 __random_sample(_InputIter __first, _InputIter __last, 342 _RandomAccessIter __out, 343 _RandomNumberGenerator& __rand, 344 const _Distance __n) 345 { 346 // concept requirements 347 __glibcpp_function_requires(_UnaryFunctionConcept< 348 _RandomNumberGenerator, _Distance, _Distance>) 349 350 _Distance __m = 0; 351 _Distance __t = __n; 352 for ( ; __first != __last && __m < __n; ++__m, ++__first) 353 __out[__m] = *__first; 354 355 while (__first != __last) { 356 ++__t; 357 _Distance __M = __rand(__t); 358 if (__M < __n) 359 __out[__M] = *__first; 360 ++__first; 361 } 362 363 return __out + __m; 364 } 365 366 /** 367 * This is an SGI extension. 368 * @ingroup SGIextensions 369 * @doctodo 370 */ 371 template<typename _InputIter, typename _RandomAccessIter> 372 inline _RandomAccessIter 373 random_sample(_InputIter __first, _InputIter __last, 374 _RandomAccessIter __out_first, _RandomAccessIter __out_last) 375 { 376 // concept requirements 377 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 378 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 379 _RandomAccessIter>) 380 381 return __random_sample(__first, __last, 382 __out_first, __out_last - __out_first); 383 } 384 385 /** 386 * This is an SGI extension. 387 * @ingroup SGIextensions 388 * @doctodo 389 */ 390 template<typename _InputIter, typename _RandomAccessIter, 391 typename _RandomNumberGenerator> 392 inline _RandomAccessIter 393 random_sample(_InputIter __first, _InputIter __last, 394 _RandomAccessIter __out_first, _RandomAccessIter __out_last, 395 _RandomNumberGenerator& __rand) 396 { 397 // concept requirements 398 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 399 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 400 _RandomAccessIter>) 401 402 return __random_sample(__first, __last, 403 __out_first, __rand, 404 __out_last - __out_first); 405 } 406 407 // is_heap, a predicate testing whether or not a range is 408 // a heap. This function is an extension, not part of the C++ 409 // standard. 410 411 template<typename _RandomAccessIter, typename _Distance> 412 bool 413 __is_heap(_RandomAccessIter __first, _Distance __n) 414 { 415 _Distance __parent = 0; 416 for (_Distance __child = 1; __child < __n; ++__child) { 417 if (__first[__parent] < __first[__child]) 418 return false; 419 if ((__child & 1) == 0) 420 ++__parent; 421 } 422 return true; 423 } 424 425 template<typename _RandomAccessIter, typename _Distance, 426 typename _StrictWeakOrdering> 427 bool 428 __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp, 429 _Distance __n) 430 { 431 _Distance __parent = 0; 432 for (_Distance __child = 1; __child < __n; ++__child) { 433 if (__comp(__first[__parent], __first[__child])) 434 return false; 435 if ((__child & 1) == 0) 436 ++__parent; 437 } 438 return true; 439 } 440 441 /** 442 * This is an SGI extension. 443 * @ingroup SGIextensions 444 * @doctodo 445 */ 446 template<typename _RandomAccessIter> 447 inline bool 448 is_heap(_RandomAccessIter __first, _RandomAccessIter __last) 449 { 450 // concept requirements 451 __glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>) 452 __glibcpp_function_requires(_LessThanComparableConcept< 453 typename iterator_traits<_RandomAccessIter>::value_type>) 454 455 return __is_heap(__first, __last - __first); 456 } 457 458 /** 459 * This is an SGI extension. 460 * @ingroup SGIextensions 461 * @doctodo 462 */ 463 template<typename _RandomAccessIter, typename _StrictWeakOrdering> 464 inline bool 465 is_heap(_RandomAccessIter __first, _RandomAccessIter __last, 466 _StrictWeakOrdering __comp) 467 { 468 // concept requirements 469 __glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>) 470 __glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, 471 typename iterator_traits<_RandomAccessIter>::value_type, 472 typename iterator_traits<_RandomAccessIter>::value_type>) 473 474 return __is_heap(__first, __comp, __last - __first); 475 } 476 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 _ForwardIter> 487 bool 488 is_sorted(_ForwardIter __first, _ForwardIter __last) 489 { 490 // concept requirements 491 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 492 __glibcpp_function_requires(_LessThanComparableConcept< 493 typename iterator_traits<_ForwardIter>::value_type>) 494 495 if (__first == __last) 496 return true; 497 498 _ForwardIter __next = __first; 499 for (++__next; __next != __last; __first = __next, ++__next) { 500 if (*__next < *__first) 501 return false; 502 } 503 504 return true; 505 } 506 507 /** 508 * This is an SGI extension. 509 * @ingroup SGIextensions 510 * @doctodo 511 */ 512 template<typename _ForwardIter, typename _StrictWeakOrdering> 513 bool 514 is_sorted(_ForwardIter __first, _ForwardIter __last, _StrictWeakOrdering __comp) 515 { 516 // concept requirements 517 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 518 __glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, 519 typename iterator_traits<_ForwardIter>::value_type, 520 typename iterator_traits<_ForwardIter>::value_type>) 521 522 if (__first == __last) 523 return true; 524 525 _ForwardIter __next = __first; 526 for (++__next; __next != __last; __first = __next, ++__next) { 527 if (__comp(*__next, *__first)) 528 return false; 529 } 530 531 return true; 532 } 533 534} // namespace __gnu_cxx 535 536#endif /* _EXT_ALGORITHM */ 537