1/* 2 * 3 * Copyright (c) 1994 4 * Hewlett-Packard Company 5 * 6 * Permission to use, copy, modify, distribute and sell this software 7 * and its documentation for any purpose is hereby granted without fee, 8 * provided that the above copyright notice appear in all copies and 9 * that both that copyright notice and this permission notice appear 10 * in supporting documentation. Hewlett-Packard Company makes no 11 * representations about the suitability of this software for any 12 * purpose. It is provided "as is" without express or implied warranty. 13 * 14 * 15 * Copyright (c) 1996 16 * Silicon Graphics Computer Systems, Inc. 17 * 18 * Permission to use, copy, modify, distribute and sell this software 19 * and its documentation for any purpose is hereby granted without fee, 20 * provided that the above copyright notice appear in all copies and 21 * that both that copyright notice and this permission notice appear 22 * in supporting documentation. Silicon Graphics makes no 23 * representations about the suitability of this software for any 24 * purpose. It is provided "as is" without express or implied warranty. 25 */ 26 27/* NOTE: This is an internal header file, included by other STL headers. 28 * You should not attempt to use it directly. 29 */ 30 31#ifndef __SGI_STL_INTERNAL_ALGO_H 32#define __SGI_STL_INTERNAL_ALGO_H 33 34#include <stl_heap.h> 35 36__STL_BEGIN_NAMESPACE 37 38#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 39#pragma set woff 1209 40#endif 41 42// __median (an extension, not present in the C++ standard). 43 44template <class _Tp> 45inline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) { 46 if (__a < __b) 47 if (__b < __c) 48 return __b; 49 else if (__a < __c) 50 return __c; 51 else 52 return __a; 53 else if (__a < __c) 54 return __a; 55 else if (__b < __c) 56 return __c; 57 else 58 return __b; 59} 60 61template <class _Tp, class _Compare> 62inline const _Tp& 63__median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) { 64 if (__comp(__a, __b)) 65 if (__comp(__b, __c)) 66 return __b; 67 else if (__comp(__a, __c)) 68 return __c; 69 else 70 return __a; 71 else if (__comp(__a, __c)) 72 return __a; 73 else if (__comp(__b, __c)) 74 return __c; 75 else 76 return __b; 77} 78 79// for_each. Apply a function to every element of a range. 80template <class _InputIter, class _Function> 81_Function for_each(_InputIter __first, _InputIter __last, _Function __f) { 82 for ( ; __first != __last; ++__first) 83 __f(*__first); 84 return __f; 85} 86 87// find and find_if. 88 89template <class _InputIter, class _Tp> 90inline _InputIter find(_InputIter __first, _InputIter __last, 91 const _Tp& __val, 92 input_iterator_tag) 93{ 94 while (__first != __last && *__first != __val) 95 ++__first; 96 return __first; 97} 98 99template <class _InputIter, class _Predicate> 100inline _InputIter find_if(_InputIter __first, _InputIter __last, 101 _Predicate __pred, 102 input_iterator_tag) 103{ 104 while (__first != __last && !__pred(*__first)) 105 ++__first; 106 return __first; 107} 108 109#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION 110 111template <class _RandomAccessIter, class _Tp> 112_RandomAccessIter find(_RandomAccessIter __first, _RandomAccessIter __last, 113 const _Tp& __val, 114 random_access_iterator_tag) 115{ 116 typename iterator_traits<_RandomAccessIter>::difference_type __trip_count 117 = (__last - __first) >> 2; 118 119 for ( ; __trip_count > 0 ; --__trip_count) { 120 if (*__first == __val) return __first; 121 ++__first; 122 123 if (*__first == __val) return __first; 124 ++__first; 125 126 if (*__first == __val) return __first; 127 ++__first; 128 129 if (*__first == __val) return __first; 130 ++__first; 131 } 132 133 switch(__last - __first) { 134 case 3: 135 if (*__first == __val) return __first; 136 ++__first; 137 case 2: 138 if (*__first == __val) return __first; 139 ++__first; 140 case 1: 141 if (*__first == __val) return __first; 142 ++__first; 143 case 0: 144 default: 145 return __last; 146 } 147} 148 149template <class _RandomAccessIter, class _Predicate> 150_RandomAccessIter find_if(_RandomAccessIter __first, _RandomAccessIter __last, 151 _Predicate __pred, 152 random_access_iterator_tag) 153{ 154 typename iterator_traits<_RandomAccessIter>::difference_type __trip_count 155 = (__last - __first) >> 2; 156 157 for ( ; __trip_count > 0 ; --__trip_count) { 158 if (__pred(*__first)) return __first; 159 ++__first; 160 161 if (__pred(*__first)) return __first; 162 ++__first; 163 164 if (__pred(*__first)) return __first; 165 ++__first; 166 167 if (__pred(*__first)) return __first; 168 ++__first; 169 } 170 171 switch(__last - __first) { 172 case 3: 173 if (__pred(*__first)) return __first; 174 ++__first; 175 case 2: 176 if (__pred(*__first)) return __first; 177 ++__first; 178 case 1: 179 if (__pred(*__first)) return __first; 180 ++__first; 181 case 0: 182 default: 183 return __last; 184 } 185} 186 187#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 188 189template <class _InputIter, class _Tp> 190inline _InputIter find(_InputIter __first, _InputIter __last, 191 const _Tp& __val) 192{ 193 return find(__first, __last, __val, __ITERATOR_CATEGORY(__first)); 194} 195 196template <class _InputIter, class _Predicate> 197inline _InputIter find_if(_InputIter __first, _InputIter __last, 198 _Predicate __pred) { 199 return find_if(__first, __last, __pred, __ITERATOR_CATEGORY(__first)); 200} 201 202// adjacent_find. 203 204template <class _ForwardIter> 205_ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last) { 206 if (__first == __last) 207 return __last; 208 _ForwardIter __next = __first; 209 while(++__next != __last) { 210 if (*__first == *__next) 211 return __first; 212 __first = __next; 213 } 214 return __last; 215} 216 217template <class _ForwardIter, class _BinaryPredicate> 218_ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last, 219 _BinaryPredicate __binary_pred) { 220 if (__first == __last) 221 return __last; 222 _ForwardIter __next = __first; 223 while(++__next != __last) { 224 if (__binary_pred(*__first, *__next)) 225 return __first; 226 __first = __next; 227 } 228 return __last; 229} 230 231// count and count_if. There are two version of each, one whose return type 232// type is void and one (present only if we have partial specialization) 233// whose return type is iterator_traits<_InputIter>::difference_type. The 234// C++ standard only has the latter version, but the former, which was present 235// in the HP STL, is retained for backward compatibility. 236 237template <class _InputIter, class _Tp, class _Size> 238void count(_InputIter __first, _InputIter __last, const _Tp& __value, 239 _Size& __n) { 240 for ( ; __first != __last; ++__first) 241 if (*__first == __value) 242 ++__n; 243} 244 245template <class _InputIter, class _Predicate, class _Size> 246void count_if(_InputIter __first, _InputIter __last, _Predicate __pred, 247 _Size& __n) { 248 for ( ; __first != __last; ++__first) 249 if (__pred(*__first)) 250 ++__n; 251} 252 253#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION 254 255template <class _InputIter, class _Tp> 256typename iterator_traits<_InputIter>::difference_type 257count(_InputIter __first, _InputIter __last, const _Tp& __value) { 258 typename iterator_traits<_InputIter>::difference_type __n = 0; 259 for ( ; __first != __last; ++__first) 260 if (*__first == __value) 261 ++__n; 262 return __n; 263} 264 265template <class _InputIter, class _Predicate> 266typename iterator_traits<_InputIter>::difference_type 267count_if(_InputIter __first, _InputIter __last, _Predicate __pred) { 268 typename iterator_traits<_InputIter>::difference_type __n = 0; 269 for ( ; __first != __last; ++__first) 270 if (__pred(*__first)) 271 ++__n; 272 return __n; 273} 274 275 276#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 277 278// search. 279 280template <class _ForwardIter1, class _ForwardIter2> 281_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1, 282 _ForwardIter2 __first2, _ForwardIter2 __last2) 283{ 284 // Test for empty ranges 285 if (__first1 == __last1 || __first2 == __last2) 286 return __first1; 287 288 // Test for a pattern of length 1. 289 _ForwardIter2 __tmp(__first2); 290 ++__tmp; 291 if (__tmp == __last2) 292 return find(__first1, __last1, *__first2); 293 294 // General case. 295 296 _ForwardIter2 __p1, __p; 297 298 __p1 = __first2; ++__p1; 299 300 _ForwardIter1 __current = __first1; 301 302 while (__first1 != __last1) { 303 __first1 = find(__first1, __last1, *__first2); 304 if (__first1 == __last1) 305 return __last1; 306 307 __p = __p1; 308 __current = __first1; 309 if (++__current == __last1) 310 return __last1; 311 312 while (*__current == *__p) { 313 if (++__p == __last2) 314 return __first1; 315 if (++__current == __last1) 316 return __last1; 317 } 318 319 ++__first1; 320 } 321 return __first1; 322} 323 324template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred> 325_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1, 326 _ForwardIter2 __first2, _ForwardIter2 __last2, 327 _BinaryPred __predicate) 328{ 329 // Test for empty ranges 330 if (__first1 == __last1 || __first2 == __last2) 331 return __first1; 332 333 // Test for a pattern of length 1. 334 _ForwardIter2 __tmp(__first2); 335 ++__tmp; 336 if (__tmp == __last2) 337 return find(__first1, __last1, *__first2); 338 339 // General case. 340 341 _ForwardIter2 __p1, __p; 342 343 __p1 = __first2; ++__p1; 344 345 _ForwardIter1 __current = __first1; 346 347 while (__first1 != __last1) { 348 while (__first1 != __last1) { 349 if (__predicate(*__first1, *__first2)) 350 break; 351 ++__first1; 352 } 353 while (__first1 != __last1 && !__predicate(*__first1, *__first2)) 354 ++__first1; 355 if (__first1 == __last1) 356 return __last1; 357 358 __p = __p1; 359 __current = __first1; 360 if (++__current == __last1) return __last1; 361 362 while (__predicate(*__current, *__p)) { 363 if (++__p == __last2) 364 return __first1; 365 if (++__current == __last1) 366 return __last1; 367 } 368 369 ++__first1; 370 } 371 return __first1; 372} 373 374// search_n. Search for __count consecutive copies of __val. 375 376template <class _ForwardIter, class _Integer, class _Tp> 377_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last, 378 _Integer __count, const _Tp& __val) { 379 if (__count <= 0) 380 return __first; 381 else { 382 __first = find(__first, __last, __val); 383 while (__first != __last) { 384 _Integer __n = __count - 1; 385 _ForwardIter __i = __first; 386 ++__i; 387 while (__i != __last && __n != 0 && *__i == __val) { 388 ++__i; 389 --__n; 390 } 391 if (__n == 0) 392 return __first; 393 else 394 __first = find(__i, __last, __val); 395 } 396 return __last; 397 } 398} 399 400template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred> 401_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last, 402 _Integer __count, const _Tp& __val, 403 _BinaryPred __binary_pred) { 404 if (__count <= 0) 405 return __first; 406 else { 407 while (__first != __last) { 408 if (__binary_pred(*__first, __val)) 409 break; 410 ++__first; 411 } 412 while (__first != __last) { 413 _Integer __n = __count - 1; 414 _ForwardIter __i = __first; 415 ++__i; 416 while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) { 417 ++__i; 418 --__n; 419 } 420 if (__n == 0) 421 return __first; 422 else { 423 while (__i != __last) { 424 if (__binary_pred(*__i, __val)) 425 break; 426 ++__i; 427 } 428 __first = __i; 429 } 430 } 431 return __last; 432 } 433} 434 435// swap_ranges 436 437template <class _ForwardIter1, class _ForwardIter2> 438_ForwardIter2 swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1, 439 _ForwardIter2 __first2) { 440 for ( ; __first1 != __last1; ++__first1, ++__first2) 441 iter_swap(__first1, __first2); 442 return __first2; 443} 444 445// transform 446 447template <class _InputIter, class _OutputIter, class _UnaryOperation> 448_OutputIter transform(_InputIter __first, _InputIter __last, 449 _OutputIter __result, _UnaryOperation __oper) { 450 for ( ; __first != __last; ++__first, ++__result) 451 *__result = __oper(*__first); 452 return __result; 453} 454 455template <class _InputIter1, class _InputIter2, class _OutputIter, 456 class _BinaryOperation> 457_OutputIter transform(_InputIter1 __first1, _InputIter1 __last1, 458 _InputIter2 __first2, _OutputIter __result, 459 _BinaryOperation __binary_op) { 460 for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result) 461 *__result = __binary_op(*__first1, *__first2); 462 return __result; 463} 464 465// replace, replace_if, replace_copy, replace_copy_if 466 467template <class _ForwardIter, class _Tp> 468void replace(_ForwardIter __first, _ForwardIter __last, 469 const _Tp& __old_value, const _Tp& __new_value) { 470 for ( ; __first != __last; ++__first) 471 if (*__first == __old_value) 472 *__first = __new_value; 473} 474 475template <class _ForwardIter, class _Predicate, class _Tp> 476void replace_if(_ForwardIter __first, _ForwardIter __last, 477 _Predicate __pred, const _Tp& __new_value) { 478 for ( ; __first != __last; ++__first) 479 if (__pred(*__first)) 480 *__first = __new_value; 481} 482 483template <class _InputIter, class _OutputIter, class _Tp> 484_OutputIter replace_copy(_InputIter __first, _InputIter __last, 485 _OutputIter __result, 486 const _Tp& __old_value, const _Tp& __new_value) { 487 for ( ; __first != __last; ++__first, ++__result) 488 *__result = *__first == __old_value ? __new_value : *__first; 489 return __result; 490} 491 492template <class Iterator, class _OutputIter, class _Predicate, class _Tp> 493_OutputIter replace_copy_if(Iterator __first, Iterator __last, 494 _OutputIter __result, 495 _Predicate __pred, const _Tp& __new_value) { 496 for ( ; __first != __last; ++__first, ++__result) 497 *__result = __pred(*__first) ? __new_value : *__first; 498 return __result; 499} 500 501// generate and generate_n 502 503template <class _ForwardIter, class _Generator> 504void generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen) { 505 for ( ; __first != __last; ++__first) 506 *__first = __gen(); 507} 508 509template <class _OutputIter, class _Size, class _Generator> 510_OutputIter generate_n(_OutputIter __first, _Size __n, _Generator __gen) { 511 for ( ; __n > 0; --__n, ++__first) 512 *__first = __gen(); 513 return __first; 514} 515 516// remove, remove_if, remove_copy, remove_copy_if 517 518template <class _InputIter, class _OutputIter, class _Tp> 519_OutputIter remove_copy(_InputIter __first, _InputIter __last, 520 _OutputIter __result, const _Tp& __value) { 521 for ( ; __first != __last; ++__first) 522 if (*__first != __value) { 523 *__result = *__first; 524 ++__result; 525 } 526 return __result; 527} 528 529template <class _InputIter, class _OutputIter, class _Predicate> 530_OutputIter remove_copy_if(_InputIter __first, _InputIter __last, 531 _OutputIter __result, _Predicate __pred) { 532 for ( ; __first != __last; ++__first) 533 if (!__pred(*__first)) { 534 *__result = *__first; 535 ++__result; 536 } 537 return __result; 538} 539 540template <class _ForwardIter, class _Tp> 541_ForwardIter remove(_ForwardIter __first, _ForwardIter __last, 542 const _Tp& __value) { 543 __first = find(__first, __last, __value); 544 _ForwardIter __i = __first; 545 return __first == __last ? __first 546 : remove_copy(++__i, __last, __first, __value); 547} 548 549template <class _ForwardIter, class _Predicate> 550_ForwardIter remove_if(_ForwardIter __first, _ForwardIter __last, 551 _Predicate __pred) { 552 __first = find_if(__first, __last, __pred); 553 _ForwardIter __i = __first; 554 return __first == __last ? __first 555 : remove_copy_if(++__i, __last, __first, __pred); 556} 557 558// unique and unique_copy 559 560template <class _InputIter, class _OutputIter, class _Tp> 561_OutputIter __unique_copy(_InputIter __first, _InputIter __last, 562 _OutputIter __result, _Tp*) { 563 _Tp __value = *__first; 564 *__result = __value; 565 while (++__first != __last) 566 if (__value != *__first) { 567 __value = *__first; 568 *++__result = __value; 569 } 570 return ++__result; 571} 572 573template <class _InputIter, class _OutputIter> 574inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last, 575 _OutputIter __result, 576 output_iterator_tag) { 577 return __unique_copy(__first, __last, __result, __VALUE_TYPE(__first)); 578} 579 580template <class _InputIter, class _ForwardIter> 581_ForwardIter __unique_copy(_InputIter __first, _InputIter __last, 582 _ForwardIter __result, forward_iterator_tag) { 583 *__result = *__first; 584 while (++__first != __last) 585 if (*__result != *__first) *++__result = *__first; 586 return ++__result; 587} 588 589template <class _InputIter, class _OutputIter> 590inline _OutputIter unique_copy(_InputIter __first, _InputIter __last, 591 _OutputIter __result) { 592 if (__first == __last) return __result; 593 return __unique_copy(__first, __last, __result, 594 __ITERATOR_CATEGORY(__result)); 595} 596 597template <class _InputIter, class _OutputIter, class _BinaryPredicate, 598 class _Tp> 599_OutputIter __unique_copy(_InputIter __first, _InputIter __last, 600 _OutputIter __result, 601 _BinaryPredicate __binary_pred, _Tp*) { 602 _Tp __value = *__first; 603 *__result = __value; 604 while (++__first != __last) 605 if (!__binary_pred(__value, *__first)) { 606 __value = *__first; 607 *++__result = __value; 608 } 609 return ++__result; 610} 611 612template <class _InputIter, class _OutputIter, class _BinaryPredicate> 613inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last, 614 _OutputIter __result, 615 _BinaryPredicate __binary_pred, 616 output_iterator_tag) { 617 return __unique_copy(__first, __last, __result, __binary_pred, 618 __VALUE_TYPE(__first)); 619} 620 621template <class _InputIter, class _ForwardIter, class _BinaryPredicate> 622_ForwardIter __unique_copy(_InputIter __first, _InputIter __last, 623 _ForwardIter __result, 624 _BinaryPredicate __binary_pred, 625 forward_iterator_tag) { 626 *__result = *__first; 627 while (++__first != __last) 628 if (!__binary_pred(*__result, *__first)) *++__result = *__first; 629 return ++__result; 630} 631 632template <class _InputIter, class _OutputIter, class _BinaryPredicate> 633inline _OutputIter unique_copy(_InputIter __first, _InputIter __last, 634 _OutputIter __result, 635 _BinaryPredicate __binary_pred) { 636 if (__first == __last) return __result; 637 return __unique_copy(__first, __last, __result, __binary_pred, 638 __ITERATOR_CATEGORY(__result)); 639} 640 641template <class _ForwardIter> 642_ForwardIter unique(_ForwardIter __first, _ForwardIter __last) { 643 __first = adjacent_find(__first, __last); 644 return unique_copy(__first, __last, __first); 645} 646 647template <class _ForwardIter, class _BinaryPredicate> 648_ForwardIter unique(_ForwardIter __first, _ForwardIter __last, 649 _BinaryPredicate __binary_pred) { 650 __first = adjacent_find(__first, __last, __binary_pred); 651 return unique_copy(__first, __last, __first, __binary_pred); 652} 653 654// reverse and reverse_copy, and their auxiliary functions 655 656template <class _BidirectionalIter> 657void __reverse(_BidirectionalIter __first, _BidirectionalIter __last, 658 bidirectional_iterator_tag) { 659 while (true) 660 if (__first == __last || __first == --__last) 661 return; 662 else 663 iter_swap(__first++, __last); 664} 665 666template <class _RandomAccessIter> 667void __reverse(_RandomAccessIter __first, _RandomAccessIter __last, 668 random_access_iterator_tag) { 669 while (__first < __last) 670 iter_swap(__first++, --__last); 671} 672 673template <class _BidirectionalIter> 674inline void reverse(_BidirectionalIter __first, _BidirectionalIter __last) { 675 __reverse(__first, __last, __ITERATOR_CATEGORY(__first)); 676} 677 678template <class _BidirectionalIter, class _OutputIter> 679_OutputIter reverse_copy(_BidirectionalIter __first, 680 _BidirectionalIter __last, 681 _OutputIter __result) { 682 while (__first != __last) { 683 --__last; 684 *__result = *__last; 685 ++__result; 686 } 687 return __result; 688} 689 690// rotate and rotate_copy, and their auxiliary functions 691 692template <class _EuclideanRingElement> 693_EuclideanRingElement __gcd(_EuclideanRingElement __m, 694 _EuclideanRingElement __n) 695{ 696 while (__n != 0) { 697 _EuclideanRingElement __t = __m % __n; 698 __m = __n; 699 __n = __t; 700 } 701 return __m; 702} 703 704template <class _ForwardIter, class _Distance> 705_ForwardIter __rotate(_ForwardIter __first, 706 _ForwardIter __middle, 707 _ForwardIter __last, 708 _Distance*, 709 forward_iterator_tag) { 710 if (__first == __middle) 711 return __last; 712 if (__last == __middle) 713 return __first; 714 715 _ForwardIter __first2 = __middle; 716 do { 717 swap(*__first++, *__first2++); 718 if (__first == __middle) 719 __middle = __first2; 720 } while (__first2 != __last); 721 722 _ForwardIter __new_middle = __first; 723 724 __first2 = __middle; 725 726 while (__first2 != __last) { 727 swap (*__first++, *__first2++); 728 if (__first == __middle) 729 __middle = __first2; 730 else if (__first2 == __last) 731 __first2 = __middle; 732 } 733 734 return __new_middle; 735} 736 737 738template <class _BidirectionalIter, class _Distance> 739_BidirectionalIter __rotate(_BidirectionalIter __first, 740 _BidirectionalIter __middle, 741 _BidirectionalIter __last, 742 _Distance*, 743 bidirectional_iterator_tag) { 744 if (__first == __middle) 745 return __last; 746 if (__last == __middle) 747 return __first; 748 749 __reverse(__first, __middle, bidirectional_iterator_tag()); 750 __reverse(__middle, __last, bidirectional_iterator_tag()); 751 752 while (__first != __middle && __middle != __last) 753 swap (*__first++, *--__last); 754 755 if (__first == __middle) { 756 __reverse(__middle, __last, bidirectional_iterator_tag()); 757 return __last; 758 } 759 else { 760 __reverse(__first, __middle, bidirectional_iterator_tag()); 761 return __first; 762 } 763} 764 765template <class _RandomAccessIter, class _Distance, class _Tp> 766_RandomAccessIter __rotate(_RandomAccessIter __first, 767 _RandomAccessIter __middle, 768 _RandomAccessIter __last, 769 _Distance *, _Tp *) { 770 771 _Distance __n = __last - __first; 772 _Distance __k = __middle - __first; 773 _Distance __l = __n - __k; 774 _RandomAccessIter __result = __first + (__last - __middle); 775 776 if (__k == __l) { 777 swap_ranges(__first, __middle, __middle); 778 return __result; 779 } 780 781 _Distance __d = __gcd(__n, __k); 782 783 for (_Distance __i = 0; __i < __d; __i++) { 784 _Tp __tmp = *__first; 785 _RandomAccessIter __p = __first; 786 787 if (__k < __l) { 788 for (_Distance __j = 0; __j < __l/__d; __j++) { 789 if (__p > __first + __l) { 790 *__p = *(__p - __l); 791 __p -= __l; 792 } 793 794 *__p = *(__p + __k); 795 __p += __k; 796 } 797 } 798 799 else { 800 for (_Distance __j = 0; __j < __k/__d - 1; __j ++) { 801 if (__p < __last - __k) { 802 *__p = *(__p + __k); 803 __p += __k; 804 } 805 806 *__p = * (__p - __l); 807 __p -= __l; 808 } 809 } 810 811 *__p = __tmp; 812 ++__first; 813 } 814 815 return __result; 816} 817 818template <class _ForwardIter> 819inline _ForwardIter rotate(_ForwardIter __first, _ForwardIter __middle, 820 _ForwardIter __last) { 821 return __rotate(__first, __middle, __last, 822 __DISTANCE_TYPE(__first), 823 __ITERATOR_CATEGORY(__first)); 824} 825 826template <class _ForwardIter, class _OutputIter> 827_OutputIter rotate_copy(_ForwardIter __first, _ForwardIter __middle, 828 _ForwardIter __last, _OutputIter __result) { 829 return copy(__first, __middle, copy(__middle, __last, __result)); 830} 831 832// Return a random number in the range [0, __n). This function encapsulates 833// whether we're using rand (part of the standard C library) or lrand48 834// (not standard, but a much better choice whenever it's available). 835 836template <class _Distance> 837inline _Distance __random_number(_Distance __n) { 838#ifdef __STL_NO_DRAND48 839 return rand() % __n; 840#else 841 return lrand48() % __n; 842#endif 843} 844 845// random_shuffle 846 847template <class _RandomAccessIter> 848inline void random_shuffle(_RandomAccessIter __first, 849 _RandomAccessIter __last) { 850 if (__first == __last) return; 851 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) 852 iter_swap(__i, __first + __random_number((__i - __first) + 1)); 853} 854 855template <class _RandomAccessIter, class _RandomNumberGenerator> 856void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last, 857 _RandomNumberGenerator& __rand) { 858 if (__first == __last) return; 859 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) 860 iter_swap(__i, __first + __rand((__i - __first) + 1)); 861} 862 863// random_sample and random_sample_n (extensions, not part of the standard). 864 865template <class _ForwardIter, class _OutputIter, class _Distance> 866_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last, 867 _OutputIter __out, const _Distance __n) 868{ 869 _Distance __remaining = 0; 870 distance(__first, __last, __remaining); 871 _Distance __m = min(__n, __remaining); 872 873 while (__m > 0) { 874 if (__random_number(__remaining) < __m) { 875 *__out = *__first; 876 ++__out; 877 --__m; 878 } 879 880 --__remaining; 881 ++__first; 882 } 883 return __out; 884} 885 886template <class _ForwardIter, class _OutputIter, class _Distance, 887 class _RandomNumberGenerator> 888_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last, 889 _OutputIter __out, const _Distance __n, 890 _RandomNumberGenerator& __rand) 891{ 892 _Distance __remaining = 0; 893 distance(__first, __last, __remaining); 894 _Distance __m = min(__n, __remaining); 895 896 while (__m > 0) { 897 if (__rand(__remaining) < __m) { 898 *__out = *__first; 899 ++__out; 900 --__m; 901 } 902 903 --__remaining; 904 ++__first; 905 } 906 return __out; 907} 908 909template <class _InputIter, class _RandomAccessIter, class _Distance> 910_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last, 911 _RandomAccessIter __out, 912 const _Distance __n) 913{ 914 _Distance __m = 0; 915 _Distance __t = __n; 916 for ( ; __first != __last && __m < __n; ++__m, ++__first) 917 __out[__m] = *__first; 918 919 while (__first != __last) { 920 ++__t; 921 _Distance __M = __random_number(__t); 922 if (__M < __n) 923 __out[__M] = *__first; 924 ++__first; 925 } 926 927 return __out + __m; 928} 929 930template <class _InputIter, class _RandomAccessIter, 931 class _RandomNumberGenerator, class _Distance> 932_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last, 933 _RandomAccessIter __out, 934 _RandomNumberGenerator& __rand, 935 const _Distance __n) 936{ 937 _Distance __m = 0; 938 _Distance __t = __n; 939 for ( ; __first != __last && __m < __n; ++__m, ++__first) 940 __out[__m] = *__first; 941 942 while (__first != __last) { 943 ++__t; 944 _Distance __M = __rand(__t); 945 if (__M < __n) 946 __out[__M] = *__first; 947 ++__first; 948 } 949 950 return __out + __m; 951} 952 953template <class _InputIter, class _RandomAccessIter> 954inline _RandomAccessIter 955random_sample(_InputIter __first, _InputIter __last, 956 _RandomAccessIter __out_first, _RandomAccessIter __out_last) 957{ 958 return __random_sample(__first, __last, 959 __out_first, __out_last - __out_first); 960} 961 962 963template <class _InputIter, class _RandomAccessIter, 964 class _RandomNumberGenerator> 965inline _RandomAccessIter 966random_sample(_InputIter __first, _InputIter __last, 967 _RandomAccessIter __out_first, _RandomAccessIter __out_last, 968 _RandomNumberGenerator& __rand) 969{ 970 return __random_sample(__first, __last, 971 __out_first, __rand, 972 __out_last - __out_first); 973} 974 975// partition, stable_partition, and their auxiliary functions 976 977template <class _ForwardIter, class _Predicate> 978_ForwardIter __partition(_ForwardIter __first, 979 _ForwardIter __last, 980 _Predicate __pred, 981 forward_iterator_tag) { 982 if (__first == __last) return __first; 983 984 while (__pred(*__first)) 985 if (++__first == __last) return __first; 986 987 _ForwardIter __next = __first; 988 989 while (++__next != __last) 990 if (__pred(*__next)) { 991 swap(*__first, *__next); 992 ++__first; 993 } 994 995 return __first; 996} 997 998template <class _BidirectionalIter, class _Predicate> 999_BidirectionalIter __partition(_BidirectionalIter __first, 1000 _BidirectionalIter __last, 1001 _Predicate __pred, 1002 bidirectional_iterator_tag) { 1003 while (true) { 1004 while (true) 1005 if (__first == __last) 1006 return __first; 1007 else if (__pred(*__first)) 1008 ++__first; 1009 else 1010 break; 1011 --__last; 1012 while (true) 1013 if (__first == __last) 1014 return __first; 1015 else if (!__pred(*__last)) 1016 --__last; 1017 else 1018 break; 1019 iter_swap(__first, __last); 1020 ++__first; 1021 } 1022} 1023 1024template <class _ForwardIter, class _Predicate> 1025inline _ForwardIter partition(_ForwardIter __first, 1026 _ForwardIter __last, 1027 _Predicate __pred) { 1028 return __partition(__first, __last, __pred, __ITERATOR_CATEGORY(__first)); 1029} 1030 1031 1032template <class _ForwardIter, class _Predicate, class _Distance> 1033_ForwardIter __inplace_stable_partition(_ForwardIter __first, 1034 _ForwardIter __last, 1035 _Predicate __pred, _Distance __len) { 1036 if (__len == 1) 1037 return __pred(*__first) ? __last : __first; 1038 _ForwardIter __middle = __first; 1039 advance(__middle, __len / 2); 1040 return rotate(__inplace_stable_partition(__first, __middle, __pred, 1041 __len / 2), 1042 __middle, 1043 __inplace_stable_partition(__middle, __last, __pred, 1044 __len - __len / 2)); 1045} 1046 1047template <class _ForwardIter, class _Pointer, class _Predicate, 1048 class _Distance> 1049_ForwardIter __stable_partition_adaptive(_ForwardIter __first, 1050 _ForwardIter __last, 1051 _Predicate __pred, _Distance __len, 1052 _Pointer __buffer, 1053 _Distance __buffer_size) 1054{ 1055 if (__len <= __buffer_size) { 1056 _ForwardIter __result1 = __first; 1057 _Pointer __result2 = __buffer; 1058 for ( ; __first != __last ; ++__first) 1059 if (__pred(*__first)) { 1060 *__result1 = *__first; 1061 ++__result1; 1062 } 1063 else { 1064 *__result2 = *__first; 1065 ++__result2; 1066 } 1067 copy(__buffer, __result2, __result1); 1068 return __result1; 1069 } 1070 else { 1071 _ForwardIter __middle = __first; 1072 advance(__middle, __len / 2); 1073 return rotate(__stable_partition_adaptive( 1074 __first, __middle, __pred, 1075 __len / 2, __buffer, __buffer_size), 1076 __middle, 1077 __stable_partition_adaptive( 1078 __middle, __last, __pred, 1079 __len - __len / 2, __buffer, __buffer_size)); 1080 } 1081} 1082 1083template <class _ForwardIter, class _Predicate, class _Tp, class _Distance> 1084inline _ForwardIter 1085__stable_partition_aux(_ForwardIter __first, _ForwardIter __last, 1086 _Predicate __pred, _Tp*, _Distance*) 1087{ 1088 _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last); 1089 if (__buf.size() > 0) 1090 return __stable_partition_adaptive(__first, __last, __pred, 1091 _Distance(__buf.requested_size()), 1092 __buf.begin(), __buf.size()); 1093 else 1094 return __inplace_stable_partition(__first, __last, __pred, 1095 _Distance(__buf.requested_size())); 1096} 1097 1098template <class _ForwardIter, class _Predicate> 1099inline _ForwardIter stable_partition(_ForwardIter __first, 1100 _ForwardIter __last, 1101 _Predicate __pred) { 1102 if (__first == __last) 1103 return __first; 1104 else 1105 return __stable_partition_aux(__first, __last, __pred, 1106 __VALUE_TYPE(__first), 1107 __DISTANCE_TYPE(__first)); 1108} 1109 1110template <class _RandomAccessIter, class _Tp> 1111_RandomAccessIter __unguarded_partition(_RandomAccessIter __first, 1112 _RandomAccessIter __last, 1113 _Tp __pivot) 1114{ 1115 while (true) { 1116 while (*__first < __pivot) 1117 ++__first; 1118 --__last; 1119 while (__pivot < *__last) 1120 --__last; 1121 if (!(__first < __last)) 1122 return __first; 1123 iter_swap(__first, __last); 1124 ++__first; 1125 } 1126} 1127 1128template <class _RandomAccessIter, class _Tp, class _Compare> 1129_RandomAccessIter __unguarded_partition(_RandomAccessIter __first, 1130 _RandomAccessIter __last, 1131 _Tp __pivot, _Compare __comp) 1132{ 1133 while (true) { 1134 while (__comp(*__first, __pivot)) 1135 ++__first; 1136 --__last; 1137 while (__comp(__pivot, *__last)) 1138 --__last; 1139 if (!(__first < __last)) 1140 return __first; 1141 iter_swap(__first, __last); 1142 ++__first; 1143 } 1144} 1145 1146const int __stl_threshold = 16; 1147 1148// sort() and its auxiliary functions. 1149 1150template <class _RandomAccessIter, class _Tp> 1151void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) { 1152 _RandomAccessIter __next = __last; 1153 --__next; 1154 while (__val < *__next) { 1155 *__last = *__next; 1156 __last = __next; 1157 --__next; 1158 } 1159 *__last = __val; 1160} 1161 1162template <class _RandomAccessIter, class _Tp, class _Compare> 1163void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val, 1164 _Compare __comp) { 1165 _RandomAccessIter __next = __last; 1166 --__next; 1167 while (__comp(__val, *__next)) { 1168 *__last = *__next; 1169 __last = __next; 1170 --__next; 1171 } 1172 *__last = __val; 1173} 1174 1175template <class _RandomAccessIter, class _Tp> 1176inline void __linear_insert(_RandomAccessIter __first, 1177 _RandomAccessIter __last, _Tp*) { 1178 _Tp __val = *__last; 1179 if (__val < *__first) { 1180 copy_backward(__first, __last, __last + 1); 1181 *__first = __val; 1182 } 1183 else 1184 __unguarded_linear_insert(__last, __val); 1185} 1186 1187template <class _RandomAccessIter, class _Tp, class _Compare> 1188inline void __linear_insert(_RandomAccessIter __first, 1189 _RandomAccessIter __last, _Tp*, _Compare __comp) { 1190 _Tp __val = *__last; 1191 if (__comp(__val, *__first)) { 1192 copy_backward(__first, __last, __last + 1); 1193 *__first = __val; 1194 } 1195 else 1196 __unguarded_linear_insert(__last, __val, __comp); 1197} 1198 1199template <class _RandomAccessIter> 1200void __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) { 1201 if (__first == __last) return; 1202 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) 1203 __linear_insert(__first, __i, __VALUE_TYPE(__first)); 1204} 1205 1206template <class _RandomAccessIter, class _Compare> 1207void __insertion_sort(_RandomAccessIter __first, 1208 _RandomAccessIter __last, _Compare __comp) { 1209 if (__first == __last) return; 1210 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) 1211 __linear_insert(__first, __i, __VALUE_TYPE(__first), __comp); 1212} 1213 1214template <class _RandomAccessIter, class _Tp> 1215void __unguarded_insertion_sort_aux(_RandomAccessIter __first, 1216 _RandomAccessIter __last, _Tp*) { 1217 for (_RandomAccessIter __i = __first; __i != __last; ++__i) 1218 __unguarded_linear_insert(__i, _Tp(*__i)); 1219} 1220 1221template <class _RandomAccessIter> 1222inline void __unguarded_insertion_sort(_RandomAccessIter __first, 1223 _RandomAccessIter __last) { 1224 __unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first)); 1225} 1226 1227template <class _RandomAccessIter, class _Tp, class _Compare> 1228void __unguarded_insertion_sort_aux(_RandomAccessIter __first, 1229 _RandomAccessIter __last, 1230 _Tp*, _Compare __comp) { 1231 for (_RandomAccessIter __i = __first; __i != __last; ++__i) 1232 __unguarded_linear_insert(__i, _Tp(*__i), __comp); 1233} 1234 1235template <class _RandomAccessIter, class _Compare> 1236inline void __unguarded_insertion_sort(_RandomAccessIter __first, 1237 _RandomAccessIter __last, 1238 _Compare __comp) { 1239 __unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first), 1240 __comp); 1241} 1242 1243template <class _RandomAccessIter> 1244void __final_insertion_sort(_RandomAccessIter __first, 1245 _RandomAccessIter __last) { 1246 if (__last - __first > __stl_threshold) { 1247 __insertion_sort(__first, __first + __stl_threshold); 1248 __unguarded_insertion_sort(__first + __stl_threshold, __last); 1249 } 1250 else 1251 __insertion_sort(__first, __last); 1252} 1253 1254template <class _RandomAccessIter, class _Compare> 1255void __final_insertion_sort(_RandomAccessIter __first, 1256 _RandomAccessIter __last, _Compare __comp) { 1257 if (__last - __first > __stl_threshold) { 1258 __insertion_sort(__first, __first + __stl_threshold, __comp); 1259 __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp); 1260 } 1261 else 1262 __insertion_sort(__first, __last, __comp); 1263} 1264 1265template <class _Size> 1266inline _Size __lg(_Size __n) { 1267 _Size __k; 1268 for (__k = 0; __n != 1; __n >>= 1) ++__k; 1269 return __k; 1270} 1271 1272template <class _RandomAccessIter, class _Tp, class _Size> 1273void __introsort_loop(_RandomAccessIter __first, 1274 _RandomAccessIter __last, _Tp*, 1275 _Size __depth_limit) 1276{ 1277 while (__last - __first > __stl_threshold) { 1278 if (__depth_limit == 0) { 1279 partial_sort(__first, __last, __last); 1280 return; 1281 } 1282 --__depth_limit; 1283 _RandomAccessIter __cut = 1284 __unguarded_partition(__first, __last, 1285 _Tp(__median(*__first, 1286 *(__first + (__last - __first)/2), 1287 *(__last - 1)))); 1288 __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit); 1289 __last = __cut; 1290 } 1291} 1292 1293template <class _RandomAccessIter, class _Tp, class _Size, class _Compare> 1294void __introsort_loop(_RandomAccessIter __first, 1295 _RandomAccessIter __last, _Tp*, 1296 _Size __depth_limit, _Compare __comp) 1297{ 1298 while (__last - __first > __stl_threshold) { 1299 if (__depth_limit == 0) { 1300 partial_sort(__first, __last, __last, __comp); 1301 return; 1302 } 1303 --__depth_limit; 1304 _RandomAccessIter __cut = 1305 __unguarded_partition(__first, __last, 1306 _Tp(__median(*__first, 1307 *(__first + (__last - __first)/2), 1308 *(__last - 1), __comp)), 1309 __comp); 1310 __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit, __comp); 1311 __last = __cut; 1312 } 1313} 1314 1315template <class _RandomAccessIter> 1316inline void sort(_RandomAccessIter __first, _RandomAccessIter __last) { 1317 if (__first != __last) { 1318 __introsort_loop(__first, __last, 1319 __VALUE_TYPE(__first), 1320 __lg(__last - __first) * 2); 1321 __final_insertion_sort(__first, __last); 1322 } 1323} 1324 1325template <class _RandomAccessIter, class _Compare> 1326inline void sort(_RandomAccessIter __first, _RandomAccessIter __last, 1327 _Compare __comp) { 1328 if (__first != __last) { 1329 __introsort_loop(__first, __last, 1330 __VALUE_TYPE(__first), 1331 __lg(__last - __first) * 2, 1332 __comp); 1333 __final_insertion_sort(__first, __last, __comp); 1334 } 1335} 1336 1337// stable_sort() and its auxiliary functions. 1338 1339template <class _RandomAccessIter> 1340void __inplace_stable_sort(_RandomAccessIter __first, 1341 _RandomAccessIter __last) { 1342 if (__last - __first < 15) { 1343 __insertion_sort(__first, __last); 1344 return; 1345 } 1346 _RandomAccessIter __middle = __first + (__last - __first) / 2; 1347 __inplace_stable_sort(__first, __middle); 1348 __inplace_stable_sort(__middle, __last); 1349 __merge_without_buffer(__first, __middle, __last, 1350 __middle - __first, 1351 __last - __middle); 1352} 1353 1354template <class _RandomAccessIter, class _Compare> 1355void __inplace_stable_sort(_RandomAccessIter __first, 1356 _RandomAccessIter __last, _Compare __comp) { 1357 if (__last - __first < 15) { 1358 __insertion_sort(__first, __last, __comp); 1359 return; 1360 } 1361 _RandomAccessIter __middle = __first + (__last - __first) / 2; 1362 __inplace_stable_sort(__first, __middle, __comp); 1363 __inplace_stable_sort(__middle, __last, __comp); 1364 __merge_without_buffer(__first, __middle, __last, 1365 __middle - __first, 1366 __last - __middle, 1367 __comp); 1368} 1369 1370template <class _RandomAccessIter1, class _RandomAccessIter2, 1371 class _Distance> 1372void __merge_sort_loop(_RandomAccessIter1 __first, 1373 _RandomAccessIter1 __last, 1374 _RandomAccessIter2 __result, _Distance __step_size) { 1375 _Distance __two_step = 2 * __step_size; 1376 1377 while (__last - __first >= __two_step) { 1378 __result = merge(__first, __first + __step_size, 1379 __first + __step_size, __first + __two_step, 1380 __result); 1381 __first += __two_step; 1382 } 1383 1384 __step_size = min(_Distance(__last - __first), __step_size); 1385 merge(__first, __first + __step_size, __first + __step_size, __last, 1386 __result); 1387} 1388 1389template <class _RandomAccessIter1, class _RandomAccessIter2, 1390 class _Distance, class _Compare> 1391void __merge_sort_loop(_RandomAccessIter1 __first, 1392 _RandomAccessIter1 __last, 1393 _RandomAccessIter2 __result, _Distance __step_size, 1394 _Compare __comp) { 1395 _Distance __two_step = 2 * __step_size; 1396 1397 while (__last - __first >= __two_step) { 1398 __result = merge(__first, __first + __step_size, 1399 __first + __step_size, __first + __two_step, 1400 __result, 1401 __comp); 1402 __first += __two_step; 1403 } 1404 __step_size = min(_Distance(__last - __first), __step_size); 1405 1406 merge(__first, __first + __step_size, 1407 __first + __step_size, __last, 1408 __result, 1409 __comp); 1410} 1411 1412const int __stl_chunk_size = 7; 1413 1414template <class _RandomAccessIter, class _Distance> 1415void __chunk_insertion_sort(_RandomAccessIter __first, 1416 _RandomAccessIter __last, _Distance __chunk_size) 1417{ 1418 while (__last - __first >= __chunk_size) { 1419 __insertion_sort(__first, __first + __chunk_size); 1420 __first += __chunk_size; 1421 } 1422 __insertion_sort(__first, __last); 1423} 1424 1425template <class _RandomAccessIter, class _Distance, class _Compare> 1426void __chunk_insertion_sort(_RandomAccessIter __first, 1427 _RandomAccessIter __last, 1428 _Distance __chunk_size, _Compare __comp) 1429{ 1430 while (__last - __first >= __chunk_size) { 1431 __insertion_sort(__first, __first + __chunk_size, __comp); 1432 __first += __chunk_size; 1433 } 1434 __insertion_sort(__first, __last, __comp); 1435} 1436 1437template <class _RandomAccessIter, class _Pointer, class _Distance> 1438void __merge_sort_with_buffer(_RandomAccessIter __first, 1439 _RandomAccessIter __last, 1440 _Pointer __buffer, _Distance*) { 1441 _Distance __len = __last - __first; 1442 _Pointer __buffer_last = __buffer + __len; 1443 1444 _Distance __step_size = __stl_chunk_size; 1445 __chunk_insertion_sort(__first, __last, __step_size); 1446 1447 while (__step_size < __len) { 1448 __merge_sort_loop(__first, __last, __buffer, __step_size); 1449 __step_size *= 2; 1450 __merge_sort_loop(__buffer, __buffer_last, __first, __step_size); 1451 __step_size *= 2; 1452 } 1453} 1454 1455template <class _RandomAccessIter, class _Pointer, class _Distance, 1456 class _Compare> 1457void __merge_sort_with_buffer(_RandomAccessIter __first, 1458 _RandomAccessIter __last, _Pointer __buffer, 1459 _Distance*, _Compare __comp) { 1460 _Distance __len = __last - __first; 1461 _Pointer __buffer_last = __buffer + __len; 1462 1463 _Distance __step_size = __stl_chunk_size; 1464 __chunk_insertion_sort(__first, __last, __step_size, __comp); 1465 1466 while (__step_size < __len) { 1467 __merge_sort_loop(__first, __last, __buffer, __step_size, __comp); 1468 __step_size *= 2; 1469 __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp); 1470 __step_size *= 2; 1471 } 1472} 1473 1474template <class _RandomAccessIter, class _Pointer, class _Distance> 1475void __stable_sort_adaptive(_RandomAccessIter __first, 1476 _RandomAccessIter __last, _Pointer __buffer, 1477 _Distance __buffer_size) { 1478 _Distance __len = (__last - __first + 1) / 2; 1479 _RandomAccessIter __middle = __first + __len; 1480 if (__len > __buffer_size) { 1481 __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size); 1482 __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size); 1483 } 1484 else { 1485 __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0); 1486 __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0); 1487 } 1488 __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first), 1489 _Distance(__last - __middle), __buffer, __buffer_size); 1490} 1491 1492template <class _RandomAccessIter, class _Pointer, class _Distance, 1493 class _Compare> 1494void __stable_sort_adaptive(_RandomAccessIter __first, 1495 _RandomAccessIter __last, _Pointer __buffer, 1496 _Distance __buffer_size, _Compare __comp) { 1497 _Distance __len = (__last - __first + 1) / 2; 1498 _RandomAccessIter __middle = __first + __len; 1499 if (__len > __buffer_size) { 1500 __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size, 1501 __comp); 1502 __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size, 1503 __comp); 1504 } 1505 else { 1506 __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0, 1507 __comp); 1508 __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0, 1509 __comp); 1510 } 1511 __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first), 1512 _Distance(__last - __middle), __buffer, __buffer_size, 1513 __comp); 1514} 1515 1516template <class _RandomAccessIter, class _Tp, class _Distance> 1517inline void __stable_sort_aux(_RandomAccessIter __first, 1518 _RandomAccessIter __last, _Tp*, _Distance*) { 1519 _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last); 1520 if (buf.begin() == 0) 1521 __inplace_stable_sort(__first, __last); 1522 else 1523 __stable_sort_adaptive(__first, __last, buf.begin(), 1524 _Distance(buf.size())); 1525} 1526 1527template <class _RandomAccessIter, class _Tp, class _Distance, class _Compare> 1528inline void __stable_sort_aux(_RandomAccessIter __first, 1529 _RandomAccessIter __last, _Tp*, _Distance*, 1530 _Compare __comp) { 1531 _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last); 1532 if (buf.begin() == 0) 1533 __inplace_stable_sort(__first, __last, __comp); 1534 else 1535 __stable_sort_adaptive(__first, __last, buf.begin(), 1536 _Distance(buf.size()), 1537 __comp); 1538} 1539 1540template <class _RandomAccessIter> 1541inline void stable_sort(_RandomAccessIter __first, 1542 _RandomAccessIter __last) { 1543 __stable_sort_aux(__first, __last, 1544 __VALUE_TYPE(__first), 1545 __DISTANCE_TYPE(__first)); 1546} 1547 1548template <class _RandomAccessIter, class _Compare> 1549inline void stable_sort(_RandomAccessIter __first, 1550 _RandomAccessIter __last, _Compare __comp) { 1551 __stable_sort_aux(__first, __last, 1552 __VALUE_TYPE(__first), 1553 __DISTANCE_TYPE(__first), 1554 __comp); 1555} 1556 1557// partial_sort, partial_sort_copy, and auxiliary functions. 1558 1559template <class _RandomAccessIter, class _Tp> 1560void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle, 1561 _RandomAccessIter __last, _Tp*) { 1562 make_heap(__first, __middle); 1563 for (_RandomAccessIter __i = __middle; __i < __last; ++__i) 1564 if (*__i < *__first) 1565 __pop_heap(__first, __middle, __i, _Tp(*__i), 1566 __DISTANCE_TYPE(__first)); 1567 sort_heap(__first, __middle); 1568} 1569 1570template <class _RandomAccessIter> 1571inline void partial_sort(_RandomAccessIter __first, 1572 _RandomAccessIter __middle, 1573 _RandomAccessIter __last) { 1574 __partial_sort(__first, __middle, __last, __VALUE_TYPE(__first)); 1575} 1576 1577template <class _RandomAccessIter, class _Tp, class _Compare> 1578void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle, 1579 _RandomAccessIter __last, _Tp*, _Compare __comp) { 1580 make_heap(__first, __middle, __comp); 1581 for (_RandomAccessIter __i = __middle; __i < __last; ++__i) 1582 if (__comp(*__i, *__first)) 1583 __pop_heap(__first, __middle, __i, _Tp(*__i), __comp, 1584 __DISTANCE_TYPE(__first)); 1585 sort_heap(__first, __middle, __comp); 1586} 1587 1588template <class _RandomAccessIter, class _Compare> 1589inline void partial_sort(_RandomAccessIter __first, 1590 _RandomAccessIter __middle, 1591 _RandomAccessIter __last, _Compare __comp) { 1592 __partial_sort(__first, __middle, __last, __VALUE_TYPE(__first), __comp); 1593} 1594 1595template <class _InputIter, class _RandomAccessIter, class _Distance, 1596 class _Tp> 1597_RandomAccessIter __partial_sort_copy(_InputIter __first, 1598 _InputIter __last, 1599 _RandomAccessIter __result_first, 1600 _RandomAccessIter __result_last, 1601 _Distance*, _Tp*) { 1602 if (__result_first == __result_last) return __result_last; 1603 _RandomAccessIter __result_real_last = __result_first; 1604 while(__first != __last && __result_real_last != __result_last) { 1605 *__result_real_last = *__first; 1606 ++__result_real_last; 1607 ++__first; 1608 } 1609 make_heap(__result_first, __result_real_last); 1610 while (__first != __last) { 1611 if (*__first < *__result_first) 1612 __adjust_heap(__result_first, _Distance(0), 1613 _Distance(__result_real_last - __result_first), 1614 _Tp(*__first)); 1615 ++__first; 1616 } 1617 sort_heap(__result_first, __result_real_last); 1618 return __result_real_last; 1619} 1620 1621template <class _InputIter, class _RandomAccessIter> 1622inline _RandomAccessIter 1623partial_sort_copy(_InputIter __first, _InputIter __last, 1624 _RandomAccessIter __result_first, 1625 _RandomAccessIter __result_last) { 1626 return __partial_sort_copy(__first, __last, __result_first, __result_last, 1627 __DISTANCE_TYPE(__result_first), 1628 __VALUE_TYPE(__first)); 1629} 1630 1631template <class _InputIter, class _RandomAccessIter, class _Compare, 1632 class _Distance, class _Tp> 1633_RandomAccessIter __partial_sort_copy(_InputIter __first, 1634 _InputIter __last, 1635 _RandomAccessIter __result_first, 1636 _RandomAccessIter __result_last, 1637 _Compare __comp, _Distance*, _Tp*) { 1638 if (__result_first == __result_last) return __result_last; 1639 _RandomAccessIter __result_real_last = __result_first; 1640 while(__first != __last && __result_real_last != __result_last) { 1641 *__result_real_last = *__first; 1642 ++__result_real_last; 1643 ++__first; 1644 } 1645 make_heap(__result_first, __result_real_last, __comp); 1646 while (__first != __last) { 1647 if (__comp(*__first, *__result_first)) 1648 __adjust_heap(__result_first, _Distance(0), 1649 _Distance(__result_real_last - __result_first), 1650 _Tp(*__first), 1651 __comp); 1652 ++__first; 1653 } 1654 sort_heap(__result_first, __result_real_last, __comp); 1655 return __result_real_last; 1656} 1657 1658template <class _InputIter, class _RandomAccessIter, class _Compare> 1659inline _RandomAccessIter 1660partial_sort_copy(_InputIter __first, _InputIter __last, 1661 _RandomAccessIter __result_first, 1662 _RandomAccessIter __result_last, _Compare __comp) { 1663 return __partial_sort_copy(__first, __last, __result_first, __result_last, 1664 __comp, 1665 __DISTANCE_TYPE(__result_first), 1666 __VALUE_TYPE(__first)); 1667} 1668 1669// nth_element() and its auxiliary functions. 1670 1671template <class _RandomAccessIter, class _Tp> 1672void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, 1673 _RandomAccessIter __last, _Tp*) { 1674 while (__last - __first > 3) { 1675 _RandomAccessIter __cut = 1676 __unguarded_partition(__first, __last, 1677 _Tp(__median(*__first, 1678 *(__first + (__last - __first)/2), 1679 *(__last - 1)))); 1680 if (__cut <= __nth) 1681 __first = __cut; 1682 else 1683 __last = __cut; 1684 } 1685 __insertion_sort(__first, __last); 1686} 1687 1688template <class _RandomAccessIter> 1689inline void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, 1690 _RandomAccessIter __last) { 1691 __nth_element(__first, __nth, __last, __VALUE_TYPE(__first)); 1692} 1693 1694template <class _RandomAccessIter, class _Tp, class _Compare> 1695void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, 1696 _RandomAccessIter __last, _Tp*, _Compare __comp) { 1697 while (__last - __first > 3) { 1698 _RandomAccessIter __cut = 1699 __unguarded_partition(__first, __last, 1700 _Tp(__median(*__first, 1701 *(__first + (__last - __first)/2), 1702 *(__last - 1), 1703 __comp)), 1704 __comp); 1705 if (__cut <= __nth) 1706 __first = __cut; 1707 else 1708 __last = __cut; 1709 } 1710 __insertion_sort(__first, __last, __comp); 1711} 1712 1713template <class _RandomAccessIter, class _Compare> 1714inline void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, 1715 _RandomAccessIter __last, _Compare __comp) { 1716 __nth_element(__first, __nth, __last, __VALUE_TYPE(__first), __comp); 1717} 1718 1719 1720// Binary search (lower_bound, upper_bound, equal_range, binary_search). 1721 1722template <class _ForwardIter, class _Tp, class _Distance> 1723_ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, 1724 const _Tp& __val, _Distance*) 1725{ 1726 _Distance __len = 0; 1727 distance(__first, __last, __len); 1728 _Distance __half; 1729 _ForwardIter __middle; 1730 1731 while (__len > 0) { 1732 __half = __len >> 1; 1733 __middle = __first; 1734 advance(__middle, __half); 1735 if (*__middle < __val) { 1736 __first = __middle; 1737 ++__first; 1738 __len = __len - __half - 1; 1739 } 1740 else 1741 __len = __half; 1742 } 1743 return __first; 1744} 1745 1746template <class _ForwardIter, class _Tp> 1747inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last, 1748 const _Tp& __val) { 1749 return __lower_bound(__first, __last, __val, 1750 __DISTANCE_TYPE(__first)); 1751} 1752 1753template <class _ForwardIter, class _Tp, class _Compare, class _Distance> 1754_ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, 1755 const _Tp& __val, _Compare __comp, _Distance*) 1756{ 1757 _Distance __len = 0; 1758 distance(__first, __last, __len); 1759 _Distance __half; 1760 _ForwardIter __middle; 1761 1762 while (__len > 0) { 1763 __half = __len >> 1; 1764 __middle = __first; 1765 advance(__middle, __half); 1766 if (__comp(*__middle, __val)) { 1767 __first = __middle; 1768 ++__first; 1769 __len = __len - __half - 1; 1770 } 1771 else 1772 __len = __half; 1773 } 1774 return __first; 1775} 1776 1777template <class _ForwardIter, class _Tp, class _Compare> 1778inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last, 1779 const _Tp& __val, _Compare __comp) { 1780 return __lower_bound(__first, __last, __val, __comp, 1781 __DISTANCE_TYPE(__first)); 1782} 1783 1784template <class _ForwardIter, class _Tp, class _Distance> 1785_ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, 1786 const _Tp& __val, _Distance*) 1787{ 1788 _Distance __len = 0; 1789 distance(__first, __last, __len); 1790 _Distance __half; 1791 _ForwardIter __middle; 1792 1793 while (__len > 0) { 1794 __half = __len >> 1; 1795 __middle = __first; 1796 advance(__middle, __half); 1797 if (__val < *__middle) 1798 __len = __half; 1799 else { 1800 __first = __middle; 1801 ++__first; 1802 __len = __len - __half - 1; 1803 } 1804 } 1805 return __first; 1806} 1807 1808template <class _ForwardIter, class _Tp> 1809inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last, 1810 const _Tp& __val) { 1811 return __upper_bound(__first, __last, __val, 1812 __DISTANCE_TYPE(__first)); 1813} 1814 1815template <class _ForwardIter, class _Tp, class _Compare, class _Distance> 1816_ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, 1817 const _Tp& __val, _Compare __comp, _Distance*) 1818{ 1819 _Distance __len = 0; 1820 distance(__first, __last, __len); 1821 _Distance __half; 1822 _ForwardIter __middle; 1823 1824 while (__len > 0) { 1825 __half = __len >> 1; 1826 __middle = __first; 1827 advance(__middle, __half); 1828 if (__comp(__val, *__middle)) 1829 __len = __half; 1830 else { 1831 __first = __middle; 1832 ++__first; 1833 __len = __len - __half - 1; 1834 } 1835 } 1836 return __first; 1837} 1838 1839template <class _ForwardIter, class _Tp, class _Compare> 1840inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last, 1841 const _Tp& __val, _Compare __comp) { 1842 return __upper_bound(__first, __last, __val, __comp, 1843 __DISTANCE_TYPE(__first)); 1844} 1845 1846template <class _ForwardIter, class _Tp, class _Distance> 1847pair<_ForwardIter, _ForwardIter> 1848__equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, 1849 _Distance*) 1850{ 1851 _Distance __len = 0; 1852 distance(__first, __last, __len); 1853 _Distance __half; 1854 _ForwardIter __middle, __left, __right; 1855 1856 while (__len > 0) { 1857 __half = __len >> 1; 1858 __middle = __first; 1859 advance(__middle, __half); 1860 if (*__middle < __val) { 1861 __first = __middle; 1862 ++__first; 1863 __len = __len - __half - 1; 1864 } 1865 else if (__val < *__middle) 1866 __len = __half; 1867 else { 1868 __left = lower_bound(__first, __middle, __val); 1869 advance(__first, __len); 1870 __right = upper_bound(++__middle, __first, __val); 1871 return pair<_ForwardIter, _ForwardIter>(__left, __right); 1872 } 1873 } 1874 return pair<_ForwardIter, _ForwardIter>(__first, __first); 1875} 1876 1877template <class _ForwardIter, class _Tp> 1878inline pair<_ForwardIter, _ForwardIter> 1879equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) { 1880 return __equal_range(__first, __last, __val, 1881 __DISTANCE_TYPE(__first)); 1882} 1883 1884template <class _ForwardIter, class _Tp, class _Compare, class _Distance> 1885pair<_ForwardIter, _ForwardIter> 1886__equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, 1887 _Compare __comp, _Distance*) 1888{ 1889 _Distance __len = 0; 1890 distance(__first, __last, __len); 1891 _Distance __half; 1892 _ForwardIter __middle, __left, __right; 1893 1894 while (__len > 0) { 1895 __half = __len >> 1; 1896 __middle = __first; 1897 advance(__middle, __half); 1898 if (__comp(*__middle, __val)) { 1899 __first = __middle; 1900 ++__first; 1901 __len = __len - __half - 1; 1902 } 1903 else if (__comp(__val, *__middle)) 1904 __len = __half; 1905 else { 1906 __left = lower_bound(__first, __middle, __val, __comp); 1907 advance(__first, __len); 1908 __right = upper_bound(++__middle, __first, __val, __comp); 1909 return pair<_ForwardIter, _ForwardIter>(__left, __right); 1910 } 1911 } 1912 return pair<_ForwardIter, _ForwardIter>(__first, __first); 1913} 1914 1915template <class _ForwardIter, class _Tp, class _Compare> 1916inline pair<_ForwardIter, _ForwardIter> 1917equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, 1918 _Compare __comp) { 1919 return __equal_range(__first, __last, __val, __comp, 1920 __DISTANCE_TYPE(__first)); 1921} 1922 1923template <class _ForwardIter, class _Tp> 1924bool binary_search(_ForwardIter __first, _ForwardIter __last, 1925 const _Tp& __val) { 1926 _ForwardIter __i = lower_bound(__first, __last, __val); 1927 return __i != __last && !(__val < *__i); 1928} 1929 1930template <class _ForwardIter, class _Tp, class _Compare> 1931bool binary_search(_ForwardIter __first, _ForwardIter __last, 1932 const _Tp& __val, 1933 _Compare __comp) { 1934 _ForwardIter __i = lower_bound(__first, __last, __val, __comp); 1935 return __i != __last && !__comp(__val, *__i); 1936} 1937 1938// merge, with and without an explicitly supplied comparison function. 1939 1940template <class _InputIter1, class _InputIter2, class _OutputIter> 1941_OutputIter merge(_InputIter1 __first1, _InputIter1 __last1, 1942 _InputIter2 __first2, _InputIter2 __last2, 1943 _OutputIter __result) { 1944 while (__first1 != __last1 && __first2 != __last2) { 1945 if (*__first2 < *__first1) { 1946 *__result = *__first2; 1947 ++__first2; 1948 } 1949 else { 1950 *__result = *__first1; 1951 ++__first1; 1952 } 1953 ++__result; 1954 } 1955 return copy(__first2, __last2, copy(__first1, __last1, __result)); 1956} 1957 1958template <class _InputIter1, class _InputIter2, class _OutputIter, 1959 class _Compare> 1960_OutputIter merge(_InputIter1 __first1, _InputIter1 __last1, 1961 _InputIter2 __first2, _InputIter2 __last2, 1962 _OutputIter __result, _Compare __comp) { 1963 while (__first1 != __last1 && __first2 != __last2) { 1964 if (__comp(*__first2, *__first1)) { 1965 *__result = *__first2; 1966 ++__first2; 1967 } 1968 else { 1969 *__result = *__first1; 1970 ++__first1; 1971 } 1972 ++__result; 1973 } 1974 return copy(__first2, __last2, copy(__first1, __last1, __result)); 1975} 1976 1977// inplace_merge and its auxiliary functions. 1978 1979template <class _BidirectionalIter, class _Distance> 1980void __merge_without_buffer(_BidirectionalIter __first, 1981 _BidirectionalIter __middle, 1982 _BidirectionalIter __last, 1983 _Distance __len1, _Distance __len2) { 1984 if (__len1 == 0 || __len2 == 0) 1985 return; 1986 if (__len1 + __len2 == 2) { 1987 if (*__middle < *__first) 1988 iter_swap(__first, __middle); 1989 return; 1990 } 1991 _BidirectionalIter __first_cut = __first; 1992 _BidirectionalIter __second_cut = __middle; 1993 _Distance __len11 = 0; 1994 _Distance __len22 = 0; 1995 if (__len1 > __len2) { 1996 __len11 = __len1 / 2; 1997 advance(__first_cut, __len11); 1998 __second_cut = lower_bound(__middle, __last, *__first_cut); 1999 distance(__middle, __second_cut, __len22); 2000 } 2001 else { 2002 __len22 = __len2 / 2; 2003 advance(__second_cut, __len22); 2004 __first_cut = upper_bound(__first, __middle, *__second_cut); 2005 distance(__first, __first_cut, __len11); 2006 } 2007 _BidirectionalIter __new_middle 2008 = rotate(__first_cut, __middle, __second_cut); 2009 __merge_without_buffer(__first, __first_cut, __new_middle, 2010 __len11, __len22); 2011 __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11, 2012 __len2 - __len22); 2013} 2014 2015template <class _BidirectionalIter, class _Distance, class _Compare> 2016void __merge_without_buffer(_BidirectionalIter __first, 2017 _BidirectionalIter __middle, 2018 _BidirectionalIter __last, 2019 _Distance __len1, _Distance __len2, 2020 _Compare __comp) { 2021 if (__len1 == 0 || __len2 == 0) 2022 return; 2023 if (__len1 + __len2 == 2) { 2024 if (__comp(*__middle, *__first)) 2025 iter_swap(__first, __middle); 2026 return; 2027 } 2028 _BidirectionalIter __first_cut = __first; 2029 _BidirectionalIter __second_cut = __middle; 2030 _Distance __len11 = 0; 2031 _Distance __len22 = 0; 2032 if (__len1 > __len2) { 2033 __len11 = __len1 / 2; 2034 advance(__first_cut, __len11); 2035 __second_cut = lower_bound(__middle, __last, *__first_cut, __comp); 2036 distance(__middle, __second_cut, __len22); 2037 } 2038 else { 2039 __len22 = __len2 / 2; 2040 advance(__second_cut, __len22); 2041 __first_cut = upper_bound(__first, __middle, *__second_cut, __comp); 2042 distance(__first, __first_cut, __len11); 2043 } 2044 _BidirectionalIter __new_middle 2045 = rotate(__first_cut, __middle, __second_cut); 2046 __merge_without_buffer(__first, __first_cut, __new_middle, __len11, __len22, 2047 __comp); 2048 __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11, 2049 __len2 - __len22, __comp); 2050} 2051 2052template <class _BidirectionalIter1, class _BidirectionalIter2, 2053 class _Distance> 2054_BidirectionalIter1 __rotate_adaptive(_BidirectionalIter1 __first, 2055 _BidirectionalIter1 __middle, 2056 _BidirectionalIter1 __last, 2057 _Distance __len1, _Distance __len2, 2058 _BidirectionalIter2 __buffer, 2059 _Distance __buffer_size) { 2060 _BidirectionalIter2 __buffer_end; 2061 if (__len1 > __len2 && __len2 <= __buffer_size) { 2062 __buffer_end = copy(__middle, __last, __buffer); 2063 copy_backward(__first, __middle, __last); 2064 return copy(__buffer, __buffer_end, __first); 2065 } 2066 else if (__len1 <= __buffer_size) { 2067 __buffer_end = copy(__first, __middle, __buffer); 2068 copy(__middle, __last, __first); 2069 return copy_backward(__buffer, __buffer_end, __last); 2070 } 2071 else 2072 return rotate(__first, __middle, __last); 2073} 2074 2075template <class _BidirectionalIter1, class _BidirectionalIter2, 2076 class _BidirectionalIter3> 2077_BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1, 2078 _BidirectionalIter1 __last1, 2079 _BidirectionalIter2 __first2, 2080 _BidirectionalIter2 __last2, 2081 _BidirectionalIter3 __result) { 2082 if (__first1 == __last1) 2083 return copy_backward(__first2, __last2, __result); 2084 if (__first2 == __last2) 2085 return copy_backward(__first1, __last1, __result); 2086 --__last1; 2087 --__last2; 2088 while (true) { 2089 if (*__last2 < *__last1) { 2090 *--__result = *__last1; 2091 if (__first1 == __last1) 2092 return copy_backward(__first2, ++__last2, __result); 2093 --__last1; 2094 } 2095 else { 2096 *--__result = *__last2; 2097 if (__first2 == __last2) 2098 return copy_backward(__first1, ++__last1, __result); 2099 --__last2; 2100 } 2101 } 2102} 2103 2104template <class _BidirectionalIter1, class _BidirectionalIter2, 2105 class _BidirectionalIter3, class _Compare> 2106_BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1, 2107 _BidirectionalIter1 __last1, 2108 _BidirectionalIter2 __first2, 2109 _BidirectionalIter2 __last2, 2110 _BidirectionalIter3 __result, 2111 _Compare __comp) { 2112 if (__first1 == __last1) 2113 return copy_backward(__first2, __last2, __result); 2114 if (__first2 == __last2) 2115 return copy_backward(__first1, __last1, __result); 2116 --__last1; 2117 --__last2; 2118 while (true) { 2119 if (__comp(*__last2, *__last1)) { 2120 *--__result = *__last1; 2121 if (__first1 == __last1) 2122 return copy_backward(__first2, ++__last2, __result); 2123 --__last1; 2124 } 2125 else { 2126 *--__result = *__last2; 2127 if (__first2 == __last2) 2128 return copy_backward(__first1, ++__last1, __result); 2129 --__last2; 2130 } 2131 } 2132} 2133 2134template <class _BidirectionalIter, class _Distance, class _Pointer> 2135void __merge_adaptive(_BidirectionalIter __first, 2136 _BidirectionalIter __middle, 2137 _BidirectionalIter __last, 2138 _Distance __len1, _Distance __len2, 2139 _Pointer __buffer, _Distance __buffer_size) { 2140 if (__len1 <= __len2 && __len1 <= __buffer_size) { 2141 _Pointer __buffer_end = copy(__first, __middle, __buffer); 2142 merge(__buffer, __buffer_end, __middle, __last, __first); 2143 } 2144 else if (__len2 <= __buffer_size) { 2145 _Pointer __buffer_end = copy(__middle, __last, __buffer); 2146 __merge_backward(__first, __middle, __buffer, __buffer_end, __last); 2147 } 2148 else { 2149 _BidirectionalIter __first_cut = __first; 2150 _BidirectionalIter __second_cut = __middle; 2151 _Distance __len11 = 0; 2152 _Distance __len22 = 0; 2153 if (__len1 > __len2) { 2154 __len11 = __len1 / 2; 2155 advance(__first_cut, __len11); 2156 __second_cut = lower_bound(__middle, __last, *__first_cut); 2157 distance(__middle, __second_cut, __len22); 2158 } 2159 else { 2160 __len22 = __len2 / 2; 2161 advance(__second_cut, __len22); 2162 __first_cut = upper_bound(__first, __middle, *__second_cut); 2163 distance(__first, __first_cut, __len11); 2164 } 2165 _BidirectionalIter __new_middle = 2166 __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11, 2167 __len22, __buffer, __buffer_size); 2168 __merge_adaptive(__first, __first_cut, __new_middle, __len11, 2169 __len22, __buffer, __buffer_size); 2170 __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11, 2171 __len2 - __len22, __buffer, __buffer_size); 2172 } 2173} 2174 2175template <class _BidirectionalIter, class _Distance, class _Pointer, 2176 class _Compare> 2177void __merge_adaptive(_BidirectionalIter __first, 2178 _BidirectionalIter __middle, 2179 _BidirectionalIter __last, 2180 _Distance __len1, _Distance __len2, 2181 _Pointer __buffer, _Distance __buffer_size, 2182 _Compare __comp) { 2183 if (__len1 <= __len2 && __len1 <= __buffer_size) { 2184 _Pointer __buffer_end = copy(__first, __middle, __buffer); 2185 merge(__buffer, __buffer_end, __middle, __last, __first, __comp); 2186 } 2187 else if (__len2 <= __buffer_size) { 2188 _Pointer __buffer_end = copy(__middle, __last, __buffer); 2189 __merge_backward(__first, __middle, __buffer, __buffer_end, __last, 2190 __comp); 2191 } 2192 else { 2193 _BidirectionalIter __first_cut = __first; 2194 _BidirectionalIter __second_cut = __middle; 2195 _Distance __len11 = 0; 2196 _Distance __len22 = 0; 2197 if (__len1 > __len2) { 2198 __len11 = __len1 / 2; 2199 advance(__first_cut, __len11); 2200 __second_cut = lower_bound(__middle, __last, *__first_cut, __comp); 2201 distance(__middle, __second_cut, __len22); 2202 } 2203 else { 2204 __len22 = __len2 / 2; 2205 advance(__second_cut, __len22); 2206 __first_cut = upper_bound(__first, __middle, *__second_cut, __comp); 2207 distance(__first, __first_cut, __len11); 2208 } 2209 _BidirectionalIter __new_middle = 2210 __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11, 2211 __len22, __buffer, __buffer_size); 2212 __merge_adaptive(__first, __first_cut, __new_middle, __len11, 2213 __len22, __buffer, __buffer_size, __comp); 2214 __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11, 2215 __len2 - __len22, __buffer, __buffer_size, __comp); 2216 } 2217} 2218 2219template <class _BidirectionalIter, class _Tp, class _Distance> 2220inline void __inplace_merge_aux(_BidirectionalIter __first, 2221 _BidirectionalIter __middle, 2222 _BidirectionalIter __last, _Tp*, _Distance*) { 2223 _Distance __len1 = 0; 2224 distance(__first, __middle, __len1); 2225 _Distance __len2 = 0; 2226 distance(__middle, __last, __len2); 2227 2228 _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last); 2229 if (__buf.begin() == 0) 2230 __merge_without_buffer(__first, __middle, __last, __len1, __len2); 2231 else 2232 __merge_adaptive(__first, __middle, __last, __len1, __len2, 2233 __buf.begin(), _Distance(__buf.size())); 2234} 2235 2236template <class _BidirectionalIter, class _Tp, 2237 class _Distance, class _Compare> 2238inline void __inplace_merge_aux(_BidirectionalIter __first, 2239 _BidirectionalIter __middle, 2240 _BidirectionalIter __last, _Tp*, _Distance*, 2241 _Compare __comp) { 2242 _Distance __len1 = 0; 2243 distance(__first, __middle, __len1); 2244 _Distance __len2 = 0; 2245 distance(__middle, __last, __len2); 2246 2247 _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last); 2248 if (__buf.begin() == 0) 2249 __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp); 2250 else 2251 __merge_adaptive(__first, __middle, __last, __len1, __len2, 2252 __buf.begin(), _Distance(__buf.size()), 2253 __comp); 2254} 2255 2256template <class _BidirectionalIter> 2257inline void inplace_merge(_BidirectionalIter __first, 2258 _BidirectionalIter __middle, 2259 _BidirectionalIter __last) { 2260 if (__first == __middle || __middle == __last) 2261 return; 2262 __inplace_merge_aux(__first, __middle, __last, 2263 __VALUE_TYPE(__first), __DISTANCE_TYPE(__first)); 2264} 2265 2266template <class _BidirectionalIter, class _Compare> 2267inline void inplace_merge(_BidirectionalIter __first, 2268 _BidirectionalIter __middle, 2269 _BidirectionalIter __last, _Compare __comp) { 2270 if (__first == __middle || __middle == __last) 2271 return; 2272 __inplace_merge_aux(__first, __middle, __last, 2273 __VALUE_TYPE(__first), __DISTANCE_TYPE(__first), 2274 __comp); 2275} 2276 2277// Set algorithms: includes, set_union, set_intersection, set_difference, 2278// set_symmetric_difference. All of these algorithms have the precondition 2279// that their input ranges are sorted and the postcondition that their output 2280// ranges are sorted. 2281 2282template <class _InputIter1, class _InputIter2> 2283bool includes(_InputIter1 __first1, _InputIter1 __last1, 2284 _InputIter2 __first2, _InputIter2 __last2) { 2285 while (__first1 != __last1 && __first2 != __last2) 2286 if (*__first2 < *__first1) 2287 return false; 2288 else if(*__first1 < *__first2) 2289 ++__first1; 2290 else 2291 ++__first1, ++__first2; 2292 2293 return __first2 == __last2; 2294} 2295 2296template <class _InputIter1, class _InputIter2, class _Compare> 2297bool includes(_InputIter1 __first1, _InputIter1 __last1, 2298 _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) { 2299 while (__first1 != __last1 && __first2 != __last2) 2300 if (__comp(*__first2, *__first1)) 2301 return false; 2302 else if(__comp(*__first1, *__first2)) 2303 ++__first1; 2304 else 2305 ++__first1, ++__first2; 2306 2307 return __first2 == __last2; 2308} 2309 2310template <class _InputIter1, class _InputIter2, class _OutputIter> 2311_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1, 2312 _InputIter2 __first2, _InputIter2 __last2, 2313 _OutputIter __result) { 2314 while (__first1 != __last1 && __first2 != __last2) { 2315 if (*__first1 < *__first2) { 2316 *__result = *__first1; 2317 ++__first1; 2318 } 2319 else if (*__first2 < *__first1) { 2320 *__result = *__first2; 2321 ++__first2; 2322 } 2323 else { 2324 *__result = *__first1; 2325 ++__first1; 2326 ++__first2; 2327 } 2328 ++__result; 2329 } 2330 return copy(__first2, __last2, copy(__first1, __last1, __result)); 2331} 2332 2333template <class _InputIter1, class _InputIter2, class _OutputIter, 2334 class _Compare> 2335_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1, 2336 _InputIter2 __first2, _InputIter2 __last2, 2337 _OutputIter __result, _Compare __comp) { 2338 while (__first1 != __last1 && __first2 != __last2) { 2339 if (__comp(*__first1, *__first2)) { 2340 *__result = *__first1; 2341 ++__first1; 2342 } 2343 else if (__comp(*__first2, *__first1)) { 2344 *__result = *__first2; 2345 ++__first2; 2346 } 2347 else { 2348 *__result = *__first1; 2349 ++__first1; 2350 ++__first2; 2351 } 2352 ++__result; 2353 } 2354 return copy(__first2, __last2, copy(__first1, __last1, __result)); 2355} 2356 2357template <class _InputIter1, class _InputIter2, class _OutputIter> 2358_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1, 2359 _InputIter2 __first2, _InputIter2 __last2, 2360 _OutputIter __result) { 2361 while (__first1 != __last1 && __first2 != __last2) 2362 if (*__first1 < *__first2) 2363 ++__first1; 2364 else if (*__first2 < *__first1) 2365 ++__first2; 2366 else { 2367 *__result = *__first1; 2368 ++__first1; 2369 ++__first2; 2370 ++__result; 2371 } 2372 return __result; 2373} 2374 2375template <class _InputIter1, class _InputIter2, class _OutputIter, 2376 class _Compare> 2377_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1, 2378 _InputIter2 __first2, _InputIter2 __last2, 2379 _OutputIter __result, _Compare __comp) { 2380 while (__first1 != __last1 && __first2 != __last2) 2381 if (__comp(*__first1, *__first2)) 2382 ++__first1; 2383 else if (__comp(*__first2, *__first1)) 2384 ++__first2; 2385 else { 2386 *__result = *__first1; 2387 ++__first1; 2388 ++__first2; 2389 ++__result; 2390 } 2391 return __result; 2392} 2393 2394template <class _InputIter1, class _InputIter2, class _OutputIter> 2395_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1, 2396 _InputIter2 __first2, _InputIter2 __last2, 2397 _OutputIter __result) { 2398 while (__first1 != __last1 && __first2 != __last2) 2399 if (*__first1 < *__first2) { 2400 *__result = *__first1; 2401 ++__first1; 2402 ++__result; 2403 } 2404 else if (*__first2 < *__first1) 2405 ++__first2; 2406 else { 2407 ++__first1; 2408 ++__first2; 2409 } 2410 return copy(__first1, __last1, __result); 2411} 2412 2413template <class _InputIter1, class _InputIter2, class _OutputIter, 2414 class _Compare> 2415_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1, 2416 _InputIter2 __first2, _InputIter2 __last2, 2417 _OutputIter __result, _Compare __comp) { 2418 while (__first1 != __last1 && __first2 != __last2) 2419 if (__comp(*__first1, *__first2)) { 2420 *__result = *__first1; 2421 ++__first1; 2422 ++__result; 2423 } 2424 else if (__comp(*__first2, *__first1)) 2425 ++__first2; 2426 else { 2427 ++__first1; 2428 ++__first2; 2429 } 2430 return copy(__first1, __last1, __result); 2431} 2432 2433template <class _InputIter1, class _InputIter2, class _OutputIter> 2434_OutputIter 2435set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, 2436 _InputIter2 __first2, _InputIter2 __last2, 2437 _OutputIter __result) { 2438 while (__first1 != __last1 && __first2 != __last2) 2439 if (*__first1 < *__first2) { 2440 *__result = *__first1; 2441 ++__first1; 2442 ++__result; 2443 } 2444 else if (*__first2 < *__first1) { 2445 *__result = *__first2; 2446 ++__first2; 2447 ++__result; 2448 } 2449 else { 2450 ++__first1; 2451 ++__first2; 2452 } 2453 return copy(__first2, __last2, copy(__first1, __last1, __result)); 2454} 2455 2456template <class _InputIter1, class _InputIter2, class _OutputIter, 2457 class _Compare> 2458_OutputIter 2459set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, 2460 _InputIter2 __first2, _InputIter2 __last2, 2461 _OutputIter __result, 2462 _Compare __comp) { 2463 while (__first1 != __last1 && __first2 != __last2) 2464 if (__comp(*__first1, *__first2)) { 2465 *__result = *__first1; 2466 ++__first1; 2467 ++__result; 2468 } 2469 else if (__comp(*__first2, *__first1)) { 2470 *__result = *__first2; 2471 ++__first2; 2472 ++__result; 2473 } 2474 else { 2475 ++__first1; 2476 ++__first2; 2477 } 2478 return copy(__first2, __last2, copy(__first1, __last1, __result)); 2479} 2480 2481// min_element and max_element, with and without an explicitly supplied 2482// comparison function. 2483 2484template <class _ForwardIter> 2485_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) { 2486 if (__first == __last) return __first; 2487 _ForwardIter __result = __first; 2488 while (++__first != __last) 2489 if (*__result < *__first) 2490 __result = __first; 2491 return __result; 2492} 2493 2494template <class _ForwardIter, class _Compare> 2495_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last, 2496 _Compare __comp) { 2497 if (__first == __last) return __first; 2498 _ForwardIter __result = __first; 2499 while (++__first != __last) 2500 if (__comp(*__result, *__first)) __result = __first; 2501 return __result; 2502} 2503 2504template <class _ForwardIter> 2505_ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) { 2506 if (__first == __last) return __first; 2507 _ForwardIter __result = __first; 2508 while (++__first != __last) 2509 if (*__first < *__result) 2510 __result = __first; 2511 return __result; 2512} 2513 2514template <class _ForwardIter, class _Compare> 2515_ForwardIter min_element(_ForwardIter __first, _ForwardIter __last, 2516 _Compare __comp) { 2517 if (__first == __last) return __first; 2518 _ForwardIter __result = __first; 2519 while (++__first != __last) 2520 if (__comp(*__first, *__result)) 2521 __result = __first; 2522 return __result; 2523} 2524 2525// next_permutation and prev_permutation, with and without an explicitly 2526// supplied comparison function. 2527 2528template <class _BidirectionalIter> 2529bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) { 2530 if (__first == __last) 2531 return false; 2532 _BidirectionalIter __i = __first; 2533 ++__i; 2534 if (__i == __last) 2535 return false; 2536 __i = __last; 2537 --__i; 2538 2539 for(;;) { 2540 _BidirectionalIter __ii = __i; 2541 --__i; 2542 if (*__i < *__ii) { 2543 _BidirectionalIter __j = __last; 2544 while (!(*__i < *--__j)) 2545 {} 2546 iter_swap(__i, __j); 2547 reverse(__ii, __last); 2548 return true; 2549 } 2550 if (__i == __first) { 2551 reverse(__first, __last); 2552 return false; 2553 } 2554 } 2555} 2556 2557template <class _BidirectionalIter, class _Compare> 2558bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last, 2559 _Compare __comp) { 2560 if (__first == __last) 2561 return false; 2562 _BidirectionalIter __i = __first; 2563 ++__i; 2564 if (__i == __last) 2565 return false; 2566 __i = __last; 2567 --__i; 2568 2569 for(;;) { 2570 _BidirectionalIter __ii = __i; 2571 --__i; 2572 if (__comp(*__i, *__ii)) { 2573 _BidirectionalIter __j = __last; 2574 while (!__comp(*__i, *--__j)) 2575 {} 2576 iter_swap(__i, __j); 2577 reverse(__ii, __last); 2578 return true; 2579 } 2580 if (__i == __first) { 2581 reverse(__first, __last); 2582 return false; 2583 } 2584 } 2585} 2586 2587template <class _BidirectionalIter> 2588bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) { 2589 if (__first == __last) 2590 return false; 2591 _BidirectionalIter __i = __first; 2592 ++__i; 2593 if (__i == __last) 2594 return false; 2595 __i = __last; 2596 --__i; 2597 2598 for(;;) { 2599 _BidirectionalIter __ii = __i; 2600 --__i; 2601 if (*__ii < *__i) { 2602 _BidirectionalIter __j = __last; 2603 while (!(*--__j < *__i)) 2604 {} 2605 iter_swap(__i, __j); 2606 reverse(__ii, __last); 2607 return true; 2608 } 2609 if (__i == __first) { 2610 reverse(__first, __last); 2611 return false; 2612 } 2613 } 2614} 2615 2616template <class _BidirectionalIter, class _Compare> 2617bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last, 2618 _Compare __comp) { 2619 if (__first == __last) 2620 return false; 2621 _BidirectionalIter __i = __first; 2622 ++__i; 2623 if (__i == __last) 2624 return false; 2625 __i = __last; 2626 --__i; 2627 2628 for(;;) { 2629 _BidirectionalIter __ii = __i; 2630 --__i; 2631 if (__comp(*__ii, *__i)) { 2632 _BidirectionalIter __j = __last; 2633 while (!__comp(*--__j, *__i)) 2634 {} 2635 iter_swap(__i, __j); 2636 reverse(__ii, __last); 2637 return true; 2638 } 2639 if (__i == __first) { 2640 reverse(__first, __last); 2641 return false; 2642 } 2643 } 2644} 2645 2646// find_first_of, with and without an explicitly supplied comparison function. 2647 2648template <class _InputIter, class _ForwardIter> 2649_InputIter find_first_of(_InputIter __first1, _InputIter __last1, 2650 _ForwardIter __first2, _ForwardIter __last2) 2651{ 2652 for ( ; __first1 != __last1; ++__first1) 2653 for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) 2654 if (*__first1 == *__iter) 2655 return __first1; 2656 return __last1; 2657} 2658 2659template <class _InputIter, class _ForwardIter, class _BinaryPredicate> 2660_InputIter find_first_of(_InputIter __first1, _InputIter __last1, 2661 _ForwardIter __first2, _ForwardIter __last2, 2662 _BinaryPredicate __comp) 2663{ 2664 for ( ; __first1 != __last1; ++__first1) 2665 for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) 2666 if (__comp(*__first1, *__iter)) 2667 return __first1; 2668 return __last1; 2669} 2670 2671 2672// find_end, with and without an explicitly supplied comparison function. 2673// Search [first2, last2) as a subsequence in [first1, last1), and return 2674// the *last* possible match. Note that find_end for bidirectional iterators 2675// is much faster than for forward iterators. 2676 2677// find_end for forward iterators. 2678template <class _ForwardIter1, class _ForwardIter2> 2679_ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 2680 _ForwardIter2 __first2, _ForwardIter2 __last2, 2681 forward_iterator_tag, forward_iterator_tag) 2682{ 2683 if (__first2 == __last2) 2684 return __last1; 2685 else { 2686 _ForwardIter1 __result = __last1; 2687 while (1) { 2688 _ForwardIter1 __new_result 2689 = search(__first1, __last1, __first2, __last2); 2690 if (__new_result == __last1) 2691 return __result; 2692 else { 2693 __result = __new_result; 2694 __first1 = __new_result; 2695 ++__first1; 2696 } 2697 } 2698 } 2699} 2700 2701template <class _ForwardIter1, class _ForwardIter2, 2702 class _BinaryPredicate> 2703_ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 2704 _ForwardIter2 __first2, _ForwardIter2 __last2, 2705 forward_iterator_tag, forward_iterator_tag, 2706 _BinaryPredicate __comp) 2707{ 2708 if (__first2 == __last2) 2709 return __last1; 2710 else { 2711 _ForwardIter1 __result = __last1; 2712 while (1) { 2713 _ForwardIter1 __new_result 2714 = search(__first1, __last1, __first2, __last2, __comp); 2715 if (__new_result == __last1) 2716 return __result; 2717 else { 2718 __result = __new_result; 2719 __first1 = __new_result; 2720 ++__first1; 2721 } 2722 } 2723 } 2724} 2725 2726// find_end for bidirectional iterators. Requires partial specialization. 2727#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION 2728 2729template <class _BidirectionalIter1, class _BidirectionalIter2> 2730_BidirectionalIter1 2731__find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, 2732 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, 2733 bidirectional_iterator_tag, bidirectional_iterator_tag) 2734{ 2735 typedef reverse_iterator<_BidirectionalIter1> _RevIter1; 2736 typedef reverse_iterator<_BidirectionalIter2> _RevIter2; 2737 2738 _RevIter1 __rlast1(__first1); 2739 _RevIter2 __rlast2(__first2); 2740 _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1, 2741 _RevIter2(__last2), __rlast2); 2742 2743 if (__rresult == __rlast1) 2744 return __last1; 2745 else { 2746 _BidirectionalIter1 __result = __rresult.base(); 2747 advance(__result, -distance(__first2, __last2)); 2748 return __result; 2749 } 2750} 2751 2752template <class _BidirectionalIter1, class _BidirectionalIter2, 2753 class _BinaryPredicate> 2754_BidirectionalIter1 2755__find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, 2756 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, 2757 bidirectional_iterator_tag, bidirectional_iterator_tag, 2758 _BinaryPredicate __comp) 2759{ 2760 typedef reverse_iterator<_BidirectionalIter1> _RevIter1; 2761 typedef reverse_iterator<_BidirectionalIter2> _RevIter2; 2762 2763 _RevIter1 __rlast1(__first1); 2764 _RevIter2 __rlast2(__first2); 2765 _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1, 2766 _RevIter2(__last2), __rlast2, 2767 __comp); 2768 2769 if (__rresult == __rlast1) 2770 return __last1; 2771 else { 2772 _BidirectionalIter1 __result = __rresult.base(); 2773 advance(__result, -distance(__first2, __last2)); 2774 return __result; 2775 } 2776} 2777#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 2778 2779// Dispatching functions for find_end. 2780 2781template <class _ForwardIter1, class _ForwardIter2> 2782inline _ForwardIter1 2783find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 2784 _ForwardIter2 __first2, _ForwardIter2 __last2) 2785{ 2786 return __find_end(__first1, __last1, __first2, __last2, 2787 __ITERATOR_CATEGORY(__first1), 2788 __ITERATOR_CATEGORY(__first2)); 2789} 2790 2791template <class _ForwardIter1, class _ForwardIter2, 2792 class _BinaryPredicate> 2793inline _ForwardIter1 2794find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 2795 _ForwardIter2 __first2, _ForwardIter2 __last2, 2796 _BinaryPredicate __comp) 2797{ 2798 return __find_end(__first1, __last1, __first2, __last2, 2799 __ITERATOR_CATEGORY(__first1), 2800 __ITERATOR_CATEGORY(__first2), 2801 __comp); 2802} 2803 2804// is_heap, a predicate testing whether or not a range is 2805// a heap. This function is an extension, not part of the C++ 2806// standard. 2807 2808template <class _RandomAccessIter, class _Distance> 2809bool __is_heap(_RandomAccessIter __first, _Distance __n) 2810{ 2811 _Distance __parent = 0; 2812 for (_Distance __child = 1; __child < __n; ++__child) { 2813 if (__first[__parent] < __first[__child]) 2814 return false; 2815 if ((__child & 1) == 0) 2816 ++__parent; 2817 } 2818 return true; 2819} 2820 2821template <class _RandomAccessIter, class _Distance, class _StrictWeakOrdering> 2822bool __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp, 2823 _Distance __n) 2824{ 2825 _Distance __parent = 0; 2826 for (_Distance __child = 1; __child < __n; ++__child) { 2827 if (__comp(__first[__parent], __first[__child])) 2828 return false; 2829 if ((__child & 1) == 0) 2830 ++__parent; 2831 } 2832 return true; 2833} 2834 2835template <class _RandomAccessIter> 2836inline bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last) 2837{ 2838 return __is_heap(__first, __last - __first); 2839} 2840 2841 2842template <class _RandomAccessIter, class _StrictWeakOrdering> 2843inline bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last, 2844 _StrictWeakOrdering __comp) 2845{ 2846 return __is_heap(__first, __comp, __last - __first); 2847} 2848 2849// is_sorted, a predicated testing whether a range is sorted in 2850// nondescending order. This is an extension, not part of the C++ 2851// standard. 2852 2853template <class _ForwardIter> 2854bool is_sorted(_ForwardIter __first, _ForwardIter __last) 2855{ 2856 if (__first == __last) 2857 return true; 2858 2859 _ForwardIter __next = __first; 2860 for (++__next; __next != __last; __first = __next, ++__next) { 2861 if (*__next < *__first) 2862 return false; 2863 } 2864 2865 return true; 2866} 2867 2868template <class _ForwardIter, class _StrictWeakOrdering> 2869bool is_sorted(_ForwardIter __first, _ForwardIter __last, 2870 _StrictWeakOrdering __comp) 2871{ 2872 if (__first == __last) 2873 return true; 2874 2875 _ForwardIter __next = __first; 2876 for (++__next; __next != __last; __first = __next, ++__next) { 2877 if (__comp(*__next, *__first)) 2878 return false; 2879 } 2880 2881 return true; 2882} 2883 2884#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 2885#pragma reset woff 1209 2886#endif 2887 2888__STL_END_NAMESPACE 2889 2890#endif /* __SGI_STL_INTERNAL_ALGO_H */ 2891 2892// Local Variables: 2893// mode:C++ 2894// End: 2895