algorithm revision 132720
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 1 64 65#pragma GCC system_header 66 67#include <algorithm> 68 69namespace __gnu_cxx 70{ 71 using std::ptrdiff_t; 72 using std::min; 73 using std::pair; 74 using std::input_iterator_tag; 75 using std::random_access_iterator_tag; 76 using std::iterator_traits; 77 78 //-------------------------------------------------- 79 // copy_n (not part of the C++ standard) 80 81 template<typename _InputIterator, typename _Size, typename _OutputIterator> 82 pair<_InputIterator, _OutputIterator> 83 __copy_n(_InputIterator __first, _Size __count, 84 _OutputIterator __result, 85 input_iterator_tag) 86 { 87 for ( ; __count > 0; --__count) { 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, 103 std::copy(__first, __last, __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 __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, _InputIterator1 __last1, 136 _InputIterator2 __first2, _InputIterator2 __last2) 137 { 138 while (__first1 != __last1 && __first2 != __last2) { 139 if (*__first1 < *__first2) 140 return -1; 141 if (*__first2 < *__first1) 142 return 1; 143 ++__first1; 144 ++__first2; 145 } 146 if (__first2 == __last2) { 147 return !(__first1 == __last1); 148 } 149 else { 150 return -1; 151 } 152 } 153 154 inline int 155 __lexicographical_compare_3way(const unsigned char* __first1, 156 const unsigned char* __last1, 157 const unsigned char* __first2, 158 const unsigned char* __last2) 159 { 160 const ptrdiff_t __len1 = __last1 - __first1; 161 const ptrdiff_t __len2 = __last2 - __first2; 162 const int __result = std::memcmp(__first1, __first2, 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( 173 (const signed char*) __first1, 174 (const signed char*) __last1, 175 (const signed char*) __first2, 176 (const signed char*) __last2); 177#else 178 return __lexicographical_compare_3way((const unsigned char*) __first1, 179 (const unsigned char*) __last1, 180 (const unsigned char*) __first2, 181 (const unsigned char*) __last2); 182#endif 183 } 184 185 /** 186 * @brief @c memcmp on steroids. 187 * @param first1 An input iterator. 188 * @param last1 An input iterator. 189 * @param first2 An input iterator. 190 * @param last2 An input iterator. 191 * @return An int, as with @c memcmp. 192 * 193 * The return value will be less than zero if the first range is 194 * "lexigraphically less than" the second, greater than zero if the second 195 * range is "lexigraphically less than" the 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, _InputIterator1 __last1, 202 _InputIterator2 __first2, _InputIterator2 __last2) 203 { 204 // concept requirements 205 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 206 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 207 __glibcxx_function_requires(_LessThanComparableConcept< 208 typename iterator_traits<_InputIterator1>::value_type>) 209 __glibcxx_function_requires(_LessThanComparableConcept< 210 typename iterator_traits<_InputIterator2>::value_type>) 211 __glibcxx_requires_valid_range(__first1, __last1); 212 __glibcxx_requires_valid_range(__first2, __last2); 213 214 return __lexicographical_compare_3way(__first1, __last1, __first2, __last2); 215 } 216 217 // count and count_if: this version, whose return type is void, was present 218 // in the HP STL, and is retained as an extension for backward compatibility. 219 220 template<typename _InputIterator, typename _Tp, typename _Size> 221 void 222 count(_InputIterator __first, _InputIterator __last, 223 const _Tp& __value, 224 _Size& __n) 225 { 226 // concept requirements 227 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 228 __glibcxx_function_requires(_EqualityComparableConcept< 229 typename iterator_traits<_InputIterator>::value_type >) 230 __glibcxx_function_requires(_EqualityComparableConcept<_Tp>) 231 __glibcxx_requires_valid_range(__first, __last); 232 233 for ( ; __first != __last; ++__first) 234 if (*__first == __value) 235 ++__n; 236 } 237 238 template<typename _InputIterator, typename _Predicate, typename _Size> 239 void 240 count_if(_InputIterator __first, _InputIterator __last, 241 _Predicate __pred, 242 _Size& __n) 243 { 244 // concept requirements 245 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 246 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 247 typename iterator_traits<_InputIterator>::value_type>) 248 __glibcxx_requires_valid_range(__first, __last); 249 250 for ( ; __first != __last; ++__first) 251 if (__pred(*__first)) 252 ++__n; 253 } 254 255 // random_sample and random_sample_n (extensions, not part of the standard). 256 257 /** 258 * This is an SGI extension. 259 * @ingroup SGIextensions 260 * @doctodo 261 */ 262 template<typename _ForwardIterator, typename _OutputIterator, typename _Distance> 263 _OutputIterator 264 random_sample_n(_ForwardIterator __first, _ForwardIterator __last, 265 _OutputIterator __out, const _Distance __n) 266 { 267 // concept requirements 268 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 269 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 270 typename iterator_traits<_ForwardIterator>::value_type>) 271 __glibcxx_requires_valid_range(__first, __last); 272 273 _Distance __remaining = std::distance(__first, __last); 274 _Distance __m = min(__n, __remaining); 275 276 while (__m > 0) { 277 if ((std::rand() % __remaining) < __m) { 278 *__out = *__first; 279 ++__out; 280 --__m; 281 } 282 283 --__remaining; 284 ++__first; 285 } 286 return __out; 287 } 288 289 /** 290 * This is an SGI extension. 291 * @ingroup SGIextensions 292 * @doctodo 293 */ 294 template<typename _ForwardIterator, typename _OutputIterator, typename _Distance, 295 typename _RandomNumberGenerator> 296 _OutputIterator 297 random_sample_n(_ForwardIterator __first, _ForwardIterator __last, 298 _OutputIterator __out, const _Distance __n, 299 _RandomNumberGenerator& __rand) 300 { 301 // concept requirements 302 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 303 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 304 typename iterator_traits<_ForwardIterator>::value_type>) 305 __glibcxx_function_requires(_UnaryFunctionConcept< 306 _RandomNumberGenerator, _Distance, _Distance>) 307 __glibcxx_requires_valid_range(__first, __last); 308 309 _Distance __remaining = std::distance(__first, __last); 310 _Distance __m = min(__n, __remaining); 311 312 while (__m > 0) { 313 if (__rand(__remaining) < __m) { 314 *__out = *__first; 315 ++__out; 316 --__m; 317 } 318 319 --__remaining; 320 ++__first; 321 } 322 return __out; 323 } 324 325 template<typename _InputIterator, typename _RandomAccessIterator, typename _Distance> 326 _RandomAccessIterator 327 __random_sample(_InputIterator __first, _InputIterator __last, 328 _RandomAccessIterator __out, 329 const _Distance __n) 330 { 331 _Distance __m = 0; 332 _Distance __t = __n; 333 for ( ; __first != __last && __m < __n; ++__m, ++__first) 334 __out[__m] = *__first; 335 336 while (__first != __last) { 337 ++__t; 338 _Distance __M = std::rand() % (__t); 339 if (__M < __n) 340 __out[__M] = *__first; 341 ++__first; 342 } 343 344 return __out + __m; 345 } 346 347 template<typename _InputIterator, typename _RandomAccessIterator, 348 typename _RandomNumberGenerator, typename _Distance> 349 _RandomAccessIterator 350 __random_sample(_InputIterator __first, _InputIterator __last, 351 _RandomAccessIterator __out, 352 _RandomNumberGenerator& __rand, 353 const _Distance __n) 354 { 355 // concept requirements 356 __glibcxx_function_requires(_UnaryFunctionConcept< 357 _RandomNumberGenerator, _Distance, _Distance>) 358 359 _Distance __m = 0; 360 _Distance __t = __n; 361 for ( ; __first != __last && __m < __n; ++__m, ++__first) 362 __out[__m] = *__first; 363 364 while (__first != __last) { 365 ++__t; 366 _Distance __M = __rand(__t); 367 if (__M < __n) 368 __out[__M] = *__first; 369 ++__first; 370 } 371 372 return __out + __m; 373 } 374 375 /** 376 * This is an SGI extension. 377 * @ingroup SGIextensions 378 * @doctodo 379 */ 380 template<typename _InputIterator, typename _RandomAccessIterator> 381 inline _RandomAccessIterator 382 random_sample(_InputIterator __first, _InputIterator __last, 383 _RandomAccessIterator __out_first, _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, _RandomAccessIterator __out_last, 406 _RandomNumberGenerator& __rand) 407 { 408 // concept requirements 409 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 410 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 411 _RandomAccessIterator>) 412 __glibcxx_requires_valid_range(__first, __last); 413 __glibcxx_requires_valid_range(__out_first, __out_last); 414 415 return __random_sample(__first, __last, 416 __out_first, __rand, 417 __out_last - __out_first); 418 } 419 420 /** 421 * This is an SGI extension. 422 * @ingroup SGIextensions 423 * @doctodo 424 */ 425 template<typename _RandomAccessIterator> 426 inline bool 427 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 428 { 429 // concept requirements 430 __glibcxx_function_requires(_RandomAccessIteratorConcept<_RandomAccessIterator>) 431 __glibcxx_function_requires(_LessThanComparableConcept< 432 typename iterator_traits<_RandomAccessIterator>::value_type>) 433 __glibcxx_requires_valid_range(__first, __last); 434 435 return std::__is_heap(__first, __last - __first); 436 } 437 438 /** 439 * This is an SGI extension. 440 * @ingroup SGIextensions 441 * @doctodo 442 */ 443 template<typename _RandomAccessIterator, typename _StrictWeakOrdering> 444 inline bool 445 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 446 _StrictWeakOrdering __comp) 447 { 448 // concept requirements 449 __glibcxx_function_requires(_RandomAccessIteratorConcept<_RandomAccessIterator>) 450 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, 451 typename iterator_traits<_RandomAccessIterator>::value_type, 452 typename iterator_traits<_RandomAccessIterator>::value_type>) 453 __glibcxx_requires_valid_range(__first, __last); 454 455 return std::__is_heap(__first, __comp, __last - __first); 456 } 457 458 // is_sorted, a predicated testing whether a range is sorted in 459 // nondescending order. This is an extension, not part of the C++ 460 // standard. 461 462 /** 463 * This is an SGI extension. 464 * @ingroup SGIextensions 465 * @doctodo 466 */ 467 template<typename _ForwardIterator> 468 bool 469 is_sorted(_ForwardIterator __first, _ForwardIterator __last) 470 { 471 // concept requirements 472 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 473 __glibcxx_function_requires(_LessThanComparableConcept< 474 typename iterator_traits<_ForwardIterator>::value_type>) 475 __glibcxx_requires_valid_range(__first, __last); 476 477 if (__first == __last) 478 return true; 479 480 _ForwardIterator __next = __first; 481 for (++__next; __next != __last; __first = __next, ++__next) { 482 if (*__next < *__first) 483 return false; 484 } 485 486 return true; 487 } 488 489 /** 490 * This is an SGI extension. 491 * @ingroup SGIextensions 492 * @doctodo 493 */ 494 template<typename _ForwardIterator, typename _StrictWeakOrdering> 495 bool 496 is_sorted(_ForwardIterator __first, _ForwardIterator __last, _StrictWeakOrdering __comp) 497 { 498 // concept requirements 499 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 500 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, 501 typename iterator_traits<_ForwardIterator>::value_type, 502 typename iterator_traits<_ForwardIterator>::value_type>) 503 __glibcxx_requires_valid_range(__first, __last); 504 505 if (__first == __last) 506 return true; 507 508 _ForwardIterator __next = __first; 509 for (++__next; __next != __last; __first = __next, ++__next) { 510 if (__comp(*__next, *__first)) 511 return false; 512 } 513 514 return true; 515 } 516} // namespace __gnu_cxx 517 518#endif /* _EXT_ALGORITHM */ 519