1 // Algorithm extensions -*- C++ -*- 2 3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 4 // Free Software Foundation, Inc. 5 // 6 // This file is part of the GNU ISO C++ Library. This library is free 7 // software; you can redistribute it and/or modify it under the 8 // terms of the GNU General Public License as published by the 9 // Free Software Foundation; either version 3, or (at your option) 10 // any later version. 11 12 // This library is distributed in the hope that it will be useful, 13 // but WITHOUT ANY WARRANTY; without even the implied warranty of 14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 // GNU General Public License for more details. 16 17 // Under Section 7 of GPL version 3, you are granted additional 18 // permissions described in the GCC Runtime Library Exception, version 19 // 3.1, as published by the Free Software Foundation. 20 21 // You should have received a copy of the GNU General Public License and 22 // a copy of the GCC Runtime Library Exception along with this program; 23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24 // <http://www.gnu.org/licenses/>. 25 26 /* 27 * 28 * Copyright (c) 1994 29 * Hewlett-Packard Company 30 * 31 * Permission to use, copy, modify, distribute and sell this software 32 * and its documentation for any purpose is hereby granted without fee, 33 * provided that the above copyright notice appear in all copies and 34 * that both that copyright notice and this permission notice appear 35 * in supporting documentation. Hewlett-Packard Company makes no 36 * representations about the suitability of this software for any 37 * purpose. It is provided "as is" without express or implied warranty. 38 * 39 * 40 * Copyright (c) 1996 41 * Silicon Graphics Computer Systems, Inc. 42 * 43 * Permission to use, copy, modify, distribute and sell this software 44 * and its documentation for any purpose is hereby granted without fee, 45 * provided that the above copyright notice appear in all copies and 46 * that both that copyright notice and this permission notice appear 47 * in supporting documentation. Silicon Graphics makes no 48 * representations about the suitability of this software for any 49 * purpose. It is provided "as is" without express or implied warranty. 50 */ 51 52 /** @file ext/algorithm 53 * This file is a GNU extension to the Standard C++ Library (possibly 54 * containing extensions from the HP/SGI STL subset). 55 */ 56 57 #ifndef _EXT_ALGORITHM 58 #define _EXT_ALGORITHM 1 59 60 #pragma GCC system_header 61 62 #include <algorithm> 63 64 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) 65 66 using std::ptrdiff_t; 67 using std::min; 68 using std::pair; 69 using std::input_iterator_tag; 70 using std::random_access_iterator_tag; 71 using std::iterator_traits; 72 73 //-------------------------------------------------- 74 // copy_n (not part of the C++ standard) 75 76 template<typename _InputIterator, typename _Size, typename _OutputIterator> 77 pair<_InputIterator, _OutputIterator> 78 __copy_n(_InputIterator __first, _Size __count, 79 _OutputIterator __result, 80 input_iterator_tag) 81 { 82 for ( ; __count > 0; --__count) 83 { 84 *__result = *__first; 85 ++__first; 86 ++__result; 87 } 88 return pair<_InputIterator, _OutputIterator>(__first, __result); 89 } 90 91 template<typename _RAIterator, typename _Size, typename _OutputIterator> 92 inline pair<_RAIterator, _OutputIterator> 93 __copy_n(_RAIterator __first, _Size __count, 94 _OutputIterator __result, 95 random_access_iterator_tag) 96 { 97 _RAIterator __last = __first + __count; 98 return pair<_RAIterator, _OutputIterator>(__last, std::copy(__first, 99 __last, 100 __result)); 101 } 102 103 /** 104 * @brief Copies the range [first,first+count) into [result,result+count). 105 * @param first An input iterator. 106 * @param count The number of elements to copy. 107 * @param result An output iterator. 108 * @return A std::pair composed of first+count and result+count. 109 * 110 * This is an SGI extension. 111 * This inline function will boil down to a call to @c memmove whenever 112 * possible. Failing that, if random access iterators are passed, then the 113 * loop count will be known (and therefore a candidate for compiler 114 * optimizations such as unrolling). 115 * @ingroup SGIextensions 116 */ 117 template<typename _InputIterator, typename _Size, typename _OutputIterator> 118 inline pair<_InputIterator, _OutputIterator> 119 copy_n(_InputIterator __first, _Size __count, _OutputIterator __result) 120 { 121 // concept requirements 122 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 123 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 124 typename iterator_traits<_InputIterator>::value_type>) 125 126 return __copy_n(__first, __count, __result, 127 std::__iterator_category(__first)); 128 } 129 130 template<typename _InputIterator1, typename _InputIterator2> 131 int 132 __lexicographical_compare_3way(_InputIterator1 __first1, 133 _InputIterator1 __last1, 134 _InputIterator2 __first2, 135 _InputIterator2 __last2) 136 { 137 while (__first1 != __last1 && __first2 != __last2) 138 { 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 else 149 return -1; 150 } 151 152 inline int 153 __lexicographical_compare_3way(const unsigned char* __first1, 154 const unsigned char* __last1, 155 const unsigned char* __first2, 156 const unsigned char* __last2) 157 { 158 const ptrdiff_t __len1 = __last1 - __first1; 159 const ptrdiff_t __len2 = __last2 - __first2; 160 const int __result = __builtin_memcmp(__first1, __first2, 161 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((const signed char*) __first1, 172 (const signed char*) __last1, 173 (const signed char*) __first2, 174 (const signed char*) __last2); 175 #else 176 return __lexicographical_compare_3way((const unsigned char*) __first1, 177 (const unsigned char*) __last1, 178 (const unsigned char*) __first2, 179 (const unsigned char*) __last2); 180 #endif 181 } 182 183 /** 184 * @brief @c memcmp on steroids. 185 * @param first1 An input iterator. 186 * @param last1 An input iterator. 187 * @param first2 An input iterator. 188 * @param last2 An input iterator. 189 * @return An int, as with @c memcmp. 190 * 191 * The return value will be less than zero if the first range is 192 * "lexigraphically less than" the second, greater than zero if the second 193 * range is "lexigraphically less than" the first, and zero otherwise. 194 * This is an SGI extension. 195 * @ingroup SGIextensions 196 */ 197 template<typename _InputIterator1, typename _InputIterator2> 198 int 199 lexicographical_compare_3way(_InputIterator1 __first1, 200 _InputIterator1 __last1, 201 _InputIterator2 __first2, 202 _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, 215 __last2); 216 } 217 218 // count and count_if: this version, whose return type is void, was present 219 // in the HP STL, and is retained as an extension for backward compatibility. 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, 263 typename _Distance> 264 _OutputIterator 265 random_sample_n(_ForwardIterator __first, _ForwardIterator __last, 266 _OutputIterator __out, const _Distance __n) 267 { 268 // concept requirements 269 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 270 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 271 typename iterator_traits<_ForwardIterator>::value_type>) 272 __glibcxx_requires_valid_range(__first, __last); 273 274 _Distance __remaining = std::distance(__first, __last); 275 _Distance __m = min(__n, __remaining); 276 277 while (__m > 0) 278 { 279 if ((std::rand() % __remaining) < __m) 280 { 281 *__out = *__first; 282 ++__out; 283 --__m; 284 } 285 --__remaining; 286 ++__first; 287 } 288 return __out; 289 } 290 291 /** 292 * This is an SGI extension. 293 * @ingroup SGIextensions 294 * @doctodo 295 */ 296 template<typename _ForwardIterator, typename _OutputIterator, 297 typename _Distance, typename _RandomNumberGenerator> 298 _OutputIterator 299 random_sample_n(_ForwardIterator __first, _ForwardIterator __last, 300 _OutputIterator __out, const _Distance __n, 301 _RandomNumberGenerator& __rand) 302 { 303 // concept requirements 304 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 305 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 306 typename iterator_traits<_ForwardIterator>::value_type>) 307 __glibcxx_function_requires(_UnaryFunctionConcept< 308 _RandomNumberGenerator, _Distance, _Distance>) 309 __glibcxx_requires_valid_range(__first, __last); 310 311 _Distance __remaining = std::distance(__first, __last); 312 _Distance __m = min(__n, __remaining); 313 314 while (__m > 0) 315 { 316 if (__rand(__remaining) < __m) 317 { 318 *__out = *__first; 319 ++__out; 320 --__m; 321 } 322 --__remaining; 323 ++__first; 324 } 325 return __out; 326 } 327 328 template<typename _InputIterator, typename _RandomAccessIterator, 329 typename _Distance> 330 _RandomAccessIterator 331 __random_sample(_InputIterator __first, _InputIterator __last, 332 _RandomAccessIterator __out, 333 const _Distance __n) 334 { 335 _Distance __m = 0; 336 _Distance __t = __n; 337 for ( ; __first != __last && __m < __n; ++__m, ++__first) 338 __out[__m] = *__first; 339 340 while (__first != __last) 341 { 342 ++__t; 343 _Distance __M = std::rand() % (__t); 344 if (__M < __n) 345 __out[__M] = *__first; 346 ++__first; 347 } 348 return __out + __m; 349 } 350 351 template<typename _InputIterator, typename _RandomAccessIterator, 352 typename _RandomNumberGenerator, typename _Distance> 353 _RandomAccessIterator 354 __random_sample(_InputIterator __first, _InputIterator __last, 355 _RandomAccessIterator __out, 356 _RandomNumberGenerator& __rand, 357 const _Distance __n) 358 { 359 // concept requirements 360 __glibcxx_function_requires(_UnaryFunctionConcept< 361 _RandomNumberGenerator, _Distance, _Distance>) 362 363 _Distance __m = 0; 364 _Distance __t = __n; 365 for ( ; __first != __last && __m < __n; ++__m, ++__first) 366 __out[__m] = *__first; 367 368 while (__first != __last) 369 { 370 ++__t; 371 _Distance __M = __rand(__t); 372 if (__M < __n) 373 __out[__M] = *__first; 374 ++__first; 375 } 376 return __out + __m; 377 } 378 379 /** 380 * This is an SGI extension. 381 * @ingroup SGIextensions 382 * @doctodo 383 */ 384 template<typename _InputIterator, typename _RandomAccessIterator> 385 inline _RandomAccessIterator 386 random_sample(_InputIterator __first, _InputIterator __last, 387 _RandomAccessIterator __out_first, 388 _RandomAccessIterator __out_last) 389 { 390 // concept requirements 391 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 392 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 393 _RandomAccessIterator>) 394 __glibcxx_requires_valid_range(__first, __last); 395 __glibcxx_requires_valid_range(__out_first, __out_last); 396 397 return __random_sample(__first, __last, 398 __out_first, __out_last - __out_first); 399 } 400 401 /** 402 * This is an SGI extension. 403 * @ingroup SGIextensions 404 * @doctodo 405 */ 406 template<typename _InputIterator, typename _RandomAccessIterator, 407 typename _RandomNumberGenerator> 408 inline _RandomAccessIterator 409 random_sample(_InputIterator __first, _InputIterator __last, 410 _RandomAccessIterator __out_first, 411 _RandomAccessIterator __out_last, 412 _RandomNumberGenerator& __rand) 413 { 414 // concept requirements 415 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 416 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 417 _RandomAccessIterator>) 418 __glibcxx_requires_valid_range(__first, __last); 419 __glibcxx_requires_valid_range(__out_first, __out_last); 420 421 return __random_sample(__first, __last, 422 __out_first, __rand, 423 __out_last - __out_first); 424 } 425 426 /** 427 * This is an SGI extension. 428 * @ingroup SGIextensions 429 * @doctodo 430 */ 431 template<typename _RandomAccessIterator> 432 inline bool 433 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 434 { 435 // concept requirements 436 __glibcxx_function_requires(_RandomAccessIteratorConcept< 437 _RandomAccessIterator>) 438 __glibcxx_function_requires(_LessThanComparableConcept< 439 typename iterator_traits<_RandomAccessIterator>::value_type>) 440 __glibcxx_requires_valid_range(__first, __last); 441 442 return std::__is_heap(__first, __last - __first); 443 } 444 445 /** 446 * This is an SGI extension. 447 * @ingroup SGIextensions 448 * @doctodo 449 */ 450 template<typename _RandomAccessIterator, typename _StrictWeakOrdering> 451 inline bool 452 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 453 _StrictWeakOrdering __comp) 454 { 455 // concept requirements 456 __glibcxx_function_requires(_RandomAccessIteratorConcept< 457 _RandomAccessIterator>) 458 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, 459 typename iterator_traits<_RandomAccessIterator>::value_type, 460 typename iterator_traits<_RandomAccessIterator>::value_type>) 461 __glibcxx_requires_valid_range(__first, __last); 462 463 return std::__is_heap(__first, __comp, __last - __first); 464 } 465 466 // is_sorted, a predicated testing whether a range is sorted in 467 // nondescending order. This is an extension, not part of the C++ 468 // standard. 469 470 /** 471 * This is an SGI extension. 472 * @ingroup SGIextensions 473 * @doctodo 474 */ 475 template<typename _ForwardIterator> 476 bool 477 is_sorted(_ForwardIterator __first, _ForwardIterator __last) 478 { 479 // concept requirements 480 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 481 __glibcxx_function_requires(_LessThanComparableConcept< 482 typename iterator_traits<_ForwardIterator>::value_type>) 483 __glibcxx_requires_valid_range(__first, __last); 484 485 if (__first == __last) 486 return true; 487 488 _ForwardIterator __next = __first; 489 for (++__next; __next != __last; __first = __next, ++__next) 490 if (*__next < *__first) 491 return false; 492 return true; 493 } 494 495 /** 496 * This is an SGI extension. 497 * @ingroup SGIextensions 498 * @doctodo 499 */ 500 template<typename _ForwardIterator, typename _StrictWeakOrdering> 501 bool 502 is_sorted(_ForwardIterator __first, _ForwardIterator __last, 503 _StrictWeakOrdering __comp) 504 { 505 // concept requirements 506 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 507 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, 508 typename iterator_traits<_ForwardIterator>::value_type, 509 typename iterator_traits<_ForwardIterator>::value_type>) 510 __glibcxx_requires_valid_range(__first, __last); 511 512 if (__first == __last) 513 return true; 514 515 _ForwardIterator __next = __first; 516 for (++__next; __next != __last; __first = __next, ++__next) 517 if (__comp(*__next, *__first)) 518 return false; 519 return true; 520 } 521 522 _GLIBCXX_END_NAMESPACE 523 524 #endif /* _EXT_ALGORITHM */ 525
