algorithm revision 97403
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 template<typename _ForwardIter, typename _OutputIter, typename _Distance> 251 _OutputIter 252 random_sample_n(_ForwardIter __first, _ForwardIter __last, 253 _OutputIter __out, const _Distance __n) 254 { 255 // concept requirements 256 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 257 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 258 typename iterator_traits<_ForwardIter>::value_type>) 259 260 _Distance __remaining = std::distance(__first, __last); 261 _Distance __m = min(__n, __remaining); 262 263 while (__m > 0) { 264 if (std::__random_number(__remaining) < __m) { 265 *__out = *__first; 266 ++__out; 267 --__m; 268 } 269 270 --__remaining; 271 ++__first; 272 } 273 return __out; 274 } 275 276 template<typename _ForwardIter, typename _OutputIter, typename _Distance, 277 typename _RandomNumberGenerator> 278 _OutputIter 279 random_sample_n(_ForwardIter __first, _ForwardIter __last, 280 _OutputIter __out, const _Distance __n, 281 _RandomNumberGenerator& __rand) 282 { 283 // concept requirements 284 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 285 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 286 typename iterator_traits<_ForwardIter>::value_type>) 287 __glibcpp_function_requires(_UnaryFunctionConcept< 288 _RandomNumberGenerator, _Distance, _Distance>) 289 290 _Distance __remaining = std::distance(__first, __last); 291 _Distance __m = min(__n, __remaining); 292 293 while (__m > 0) { 294 if (__rand(__remaining) < __m) { 295 *__out = *__first; 296 ++__out; 297 --__m; 298 } 299 300 --__remaining; 301 ++__first; 302 } 303 return __out; 304 } 305 306 template<typename _InputIter, typename _RandomAccessIter, typename _Distance> 307 _RandomAccessIter 308 __random_sample(_InputIter __first, _InputIter __last, 309 _RandomAccessIter __out, 310 const _Distance __n) 311 { 312 _Distance __m = 0; 313 _Distance __t = __n; 314 for ( ; __first != __last && __m < __n; ++__m, ++__first) 315 __out[__m] = *__first; 316 317 while (__first != __last) { 318 ++__t; 319 _Distance __M = std::__random_number(__t); 320 if (__M < __n) 321 __out[__M] = *__first; 322 ++__first; 323 } 324 325 return __out + __m; 326 } 327 328 template<typename _InputIter, typename _RandomAccessIter, 329 typename _RandomNumberGenerator, typename _Distance> 330 _RandomAccessIter 331 __random_sample(_InputIter __first, _InputIter __last, 332 _RandomAccessIter __out, 333 _RandomNumberGenerator& __rand, 334 const _Distance __n) 335 { 336 // concept requirements 337 __glibcpp_function_requires(_UnaryFunctionConcept< 338 _RandomNumberGenerator, _Distance, _Distance>) 339 340 _Distance __m = 0; 341 _Distance __t = __n; 342 for ( ; __first != __last && __m < __n; ++__m, ++__first) 343 __out[__m] = *__first; 344 345 while (__first != __last) { 346 ++__t; 347 _Distance __M = __rand(__t); 348 if (__M < __n) 349 __out[__M] = *__first; 350 ++__first; 351 } 352 353 return __out + __m; 354 } 355 356 template<typename _InputIter, typename _RandomAccessIter> 357 inline _RandomAccessIter 358 random_sample(_InputIter __first, _InputIter __last, 359 _RandomAccessIter __out_first, _RandomAccessIter __out_last) 360 { 361 // concept requirements 362 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 363 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 364 _RandomAccessIter>) 365 366 return __random_sample(__first, __last, 367 __out_first, __out_last - __out_first); 368 } 369 370 template<typename _InputIter, typename _RandomAccessIter, 371 typename _RandomNumberGenerator> 372 inline _RandomAccessIter 373 random_sample(_InputIter __first, _InputIter __last, 374 _RandomAccessIter __out_first, _RandomAccessIter __out_last, 375 _RandomNumberGenerator& __rand) 376 { 377 // concept requirements 378 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 379 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 380 _RandomAccessIter>) 381 382 return __random_sample(__first, __last, 383 __out_first, __rand, 384 __out_last - __out_first); 385 } 386 387 // is_heap, a predicate testing whether or not a range is 388 // a heap. This function is an extension, not part of the C++ 389 // standard. 390 391 template<typename _RandomAccessIter, typename _Distance> 392 bool 393 __is_heap(_RandomAccessIter __first, _Distance __n) 394 { 395 _Distance __parent = 0; 396 for (_Distance __child = 1; __child < __n; ++__child) { 397 if (__first[__parent] < __first[__child]) 398 return false; 399 if ((__child & 1) == 0) 400 ++__parent; 401 } 402 return true; 403 } 404 405 template<typename _RandomAccessIter, typename _Distance, 406 typename _StrictWeakOrdering> 407 bool 408 __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp, 409 _Distance __n) 410 { 411 _Distance __parent = 0; 412 for (_Distance __child = 1; __child < __n; ++__child) { 413 if (__comp(__first[__parent], __first[__child])) 414 return false; 415 if ((__child & 1) == 0) 416 ++__parent; 417 } 418 return true; 419 } 420 421 template<typename _RandomAccessIter> 422 inline bool 423 is_heap(_RandomAccessIter __first, _RandomAccessIter __last) 424 { 425 // concept requirements 426 __glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>) 427 __glibcpp_function_requires(_LessThanComparableConcept< 428 typename iterator_traits<_RandomAccessIter>::value_type>) 429 430 return __is_heap(__first, __last - __first); 431 } 432 433 template<typename _RandomAccessIter, typename _StrictWeakOrdering> 434 inline bool 435 is_heap(_RandomAccessIter __first, _RandomAccessIter __last, 436 _StrictWeakOrdering __comp) 437 { 438 // concept requirements 439 __glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>) 440 __glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, 441 typename iterator_traits<_RandomAccessIter>::value_type, 442 typename iterator_traits<_RandomAccessIter>::value_type>) 443 444 return __is_heap(__first, __comp, __last - __first); 445 } 446 447 // is_sorted, a predicated testing whether a range is sorted in 448 // nondescending order. This is an extension, not part of the C++ 449 // standard. 450 451 template<typename _ForwardIter> 452 bool 453 is_sorted(_ForwardIter __first, _ForwardIter __last) 454 { 455 // concept requirements 456 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 457 __glibcpp_function_requires(_LessThanComparableConcept< 458 typename iterator_traits<_ForwardIter>::value_type>) 459 460 if (__first == __last) 461 return true; 462 463 _ForwardIter __next = __first; 464 for (++__next; __next != __last; __first = __next, ++__next) { 465 if (*__next < *__first) 466 return false; 467 } 468 469 return true; 470 } 471 472 template<typename _ForwardIter, typename _StrictWeakOrdering> 473 bool 474 is_sorted(_ForwardIter __first, _ForwardIter __last, _StrictWeakOrdering __comp) 475 { 476 // concept requirements 477 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 478 __glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, 479 typename iterator_traits<_ForwardIter>::value_type, 480 typename iterator_traits<_ForwardIter>::value_type>) 481 482 if (__first == __last) 483 return true; 484 485 _ForwardIter __next = __first; 486 for (++__next; __next != __last; __first = __next, ++__next) { 487 if (__comp(*__next, *__first)) 488 return false; 489 } 490 491 return true; 492 } 493 494} // namespace __gnu_cxx 495 496#endif /* _EXT_ALGORITHM */ 497