1// -*- C++ -*- 2//===-------------------------- algorithm ---------------------------------===// 3// 4// The LLVM Compiler Infrastructure 5// 6// This file is distributed under the University of Illinois Open Source 7// License. See LICENSE.TXT for details. 8// 9//===----------------------------------------------------------------------===// 10 11#ifndef _LIBCPP_ALGORITHM 12#define _LIBCPP_ALGORITHM 13 14/* 15 algorithm synopsis 16 17#include <initializer_list> 18 19namespace std 20{ 21 22template <class InputIterator, class Predicate> 23 bool 24 all_of(InputIterator first, InputIterator last, Predicate pred); 25 26template <class InputIterator, class Predicate> 27 bool 28 any_of(InputIterator first, InputIterator last, Predicate pred); 29 30template <class InputIterator, class Predicate> 31 bool 32 none_of(InputIterator first, InputIterator last, Predicate pred); 33 34template <class InputIterator, class Function> 35 Function 36 for_each(InputIterator first, InputIterator last, Function f); 37 38template <class InputIterator, class T> 39 InputIterator 40 find(InputIterator first, InputIterator last, const T& value); 41 42template <class InputIterator, class Predicate> 43 InputIterator 44 find_if(InputIterator first, InputIterator last, Predicate pred); 45 46template<class InputIterator, class Predicate> 47 InputIterator 48 find_if_not(InputIterator first, InputIterator last, Predicate pred); 49 50template <class ForwardIterator1, class ForwardIterator2> 51 ForwardIterator1 52 find_end(ForwardIterator1 first1, ForwardIterator1 last1, 53 ForwardIterator2 first2, ForwardIterator2 last2); 54 55template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> 56 ForwardIterator1 57 find_end(ForwardIterator1 first1, ForwardIterator1 last1, 58 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); 59 60template <class ForwardIterator1, class ForwardIterator2> 61 ForwardIterator1 62 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, 63 ForwardIterator2 first2, ForwardIterator2 last2); 64 65template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> 66 ForwardIterator1 67 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, 68 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); 69 70template <class ForwardIterator> 71 ForwardIterator 72 adjacent_find(ForwardIterator first, ForwardIterator last); 73 74template <class ForwardIterator, class BinaryPredicate> 75 ForwardIterator 76 adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred); 77 78template <class InputIterator, class T> 79 typename iterator_traits<InputIterator>::difference_type 80 count(InputIterator first, InputIterator last, const T& value); 81 82template <class InputIterator, class Predicate> 83 typename iterator_traits<InputIterator>::difference_type 84 count_if(InputIterator first, InputIterator last, Predicate pred); 85 86template <class InputIterator1, class InputIterator2> 87 pair<InputIterator1, InputIterator2> 88 mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); 89 90template <class InputIterator1, class InputIterator2, class BinaryPredicate> 91 pair<InputIterator1, InputIterator2> 92 mismatch(InputIterator1 first1, InputIterator1 last1, 93 InputIterator2 first2, BinaryPredicate pred); 94 95template <class InputIterator1, class InputIterator2> 96 bool 97 equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); 98 99template <class InputIterator1, class InputIterator2, class BinaryPredicate> 100 bool 101 equal(InputIterator1 first1, InputIterator1 last1, 102 InputIterator2 first2, BinaryPredicate pred); 103 104template<class ForwardIterator1, class ForwardIterator2> 105 bool 106 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, 107 ForwardIterator2 first2); 108 109template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> 110 bool 111 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, 112 ForwardIterator2 first2, BinaryPredicate pred); 113 114template <class ForwardIterator1, class ForwardIterator2> 115 ForwardIterator1 116 search(ForwardIterator1 first1, ForwardIterator1 last1, 117 ForwardIterator2 first2, ForwardIterator2 last2); 118 119template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> 120 ForwardIterator1 121 search(ForwardIterator1 first1, ForwardIterator1 last1, 122 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); 123 124template <class ForwardIterator, class Size, class T> 125 ForwardIterator 126 search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value); 127 128template <class ForwardIterator, class Size, class T, class BinaryPredicate> 129 ForwardIterator 130 search_n(ForwardIterator first, ForwardIterator last, 131 Size count, const T& value, BinaryPredicate pred); 132 133template <class InputIterator, class OutputIterator> 134 OutputIterator 135 copy(InputIterator first, InputIterator last, OutputIterator result); 136 137template<class InputIterator, class OutputIterator, class Predicate> 138 OutputIterator 139 copy_if(InputIterator first, InputIterator last, 140 OutputIterator result, Predicate pred); 141 142template<class InputIterator, class Size, class OutputIterator> 143 OutputIterator 144 copy_n(InputIterator first, Size n, OutputIterator result); 145 146template <class BidirectionalIterator1, class BidirectionalIterator2> 147 BidirectionalIterator2 148 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, 149 BidirectionalIterator2 result); 150 151template <class ForwardIterator1, class ForwardIterator2> 152 ForwardIterator2 153 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2); 154 155template <class ForwardIterator1, class ForwardIterator2> 156 void 157 iter_swap(ForwardIterator1 a, ForwardIterator2 b); 158 159template <class InputIterator, class OutputIterator, class UnaryOperation> 160 OutputIterator 161 transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op); 162 163template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation> 164 OutputIterator 165 transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, 166 OutputIterator result, BinaryOperation binary_op); 167 168template <class ForwardIterator, class T> 169 void 170 replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value); 171 172template <class ForwardIterator, class Predicate, class T> 173 void 174 replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value); 175 176template <class InputIterator, class OutputIterator, class T> 177 OutputIterator 178 replace_copy(InputIterator first, InputIterator last, OutputIterator result, 179 const T& old_value, const T& new_value); 180 181template <class InputIterator, class OutputIterator, class Predicate, class T> 182 OutputIterator 183 replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value); 184 185template <class ForwardIterator, class T> 186 void 187 fill(ForwardIterator first, ForwardIterator last, const T& value); 188 189template <class OutputIterator, class Size, class T> 190 OutputIterator 191 fill_n(OutputIterator first, Size n, const T& value); 192 193template <class ForwardIterator, class Generator> 194 void 195 generate(ForwardIterator first, ForwardIterator last, Generator gen); 196 197template <class OutputIterator, class Size, class Generator> 198 OutputIterator 199 generate_n(OutputIterator first, Size n, Generator gen); 200 201template <class ForwardIterator, class T> 202 ForwardIterator 203 remove(ForwardIterator first, ForwardIterator last, const T& value); 204 205template <class ForwardIterator, class Predicate> 206 ForwardIterator 207 remove_if(ForwardIterator first, ForwardIterator last, Predicate pred); 208 209template <class InputIterator, class OutputIterator, class T> 210 OutputIterator 211 remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value); 212 213template <class InputIterator, class OutputIterator, class Predicate> 214 OutputIterator 215 remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred); 216 217template <class ForwardIterator> 218 ForwardIterator 219 unique(ForwardIterator first, ForwardIterator last); 220 221template <class ForwardIterator, class BinaryPredicate> 222 ForwardIterator 223 unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred); 224 225template <class InputIterator, class OutputIterator> 226 OutputIterator 227 unique_copy(InputIterator first, InputIterator last, OutputIterator result); 228 229template <class InputIterator, class OutputIterator, class BinaryPredicate> 230 OutputIterator 231 unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred); 232 233template <class BidirectionalIterator> 234 void 235 reverse(BidirectionalIterator first, BidirectionalIterator last); 236 237template <class BidirectionalIterator, class OutputIterator> 238 OutputIterator 239 reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result); 240 241template <class ForwardIterator> 242 ForwardIterator 243 rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last); 244 245template <class ForwardIterator, class OutputIterator> 246 OutputIterator 247 rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result); 248 249template <class RandomAccessIterator> 250 void 251 random_shuffle(RandomAccessIterator first, RandomAccessIterator last); 252 253template <class RandomAccessIterator, class RandomNumberGenerator> 254 void 255 random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand); 256 257template<class RandomAccessIterator, class UniformRandomNumberGenerator> 258 void shuffle(RandomAccessIterator first, RandomAccessIterator last, 259 UniformRandomNumberGenerator& g); 260 261template <class InputIterator, class Predicate> 262 bool 263 is_partitioned(InputIterator first, InputIterator last, Predicate pred); 264 265template <class ForwardIterator, class Predicate> 266 ForwardIterator 267 partition(ForwardIterator first, ForwardIterator last, Predicate pred); 268 269template <class InputIterator, class OutputIterator1, 270 class OutputIterator2, class Predicate> 271 pair<OutputIterator1, OutputIterator2> 272 partition_copy(InputIterator first, InputIterator last, 273 OutputIterator1 out_true, OutputIterator2 out_false, 274 Predicate pred); 275 276template <class ForwardIterator, class Predicate> 277 ForwardIterator 278 stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred); 279 280template<class ForwardIterator, class Predicate> 281 ForwardIterator 282 partition_point(ForwardIterator first, ForwardIterator last, Predicate pred); 283 284template <class ForwardIterator> 285 bool 286 is_sorted(ForwardIterator first, ForwardIterator last); 287 288template <class ForwardIterator, class Compare> 289 bool 290 is_sorted(ForwardIterator first, ForwardIterator last, Compare comp); 291 292template<class ForwardIterator> 293 ForwardIterator 294 is_sorted_until(ForwardIterator first, ForwardIterator last); 295 296template <class ForwardIterator, class Compare> 297 ForwardIterator 298 is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp); 299 300template <class RandomAccessIterator> 301 void 302 sort(RandomAccessIterator first, RandomAccessIterator last); 303 304template <class RandomAccessIterator, class Compare> 305 void 306 sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 307 308template <class RandomAccessIterator> 309 void 310 stable_sort(RandomAccessIterator first, RandomAccessIterator last); 311 312template <class RandomAccessIterator, class Compare> 313 void 314 stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 315 316template <class RandomAccessIterator> 317 void 318 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last); 319 320template <class RandomAccessIterator, class Compare> 321 void 322 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp); 323 324template <class InputIterator, class RandomAccessIterator> 325 RandomAccessIterator 326 partial_sort_copy(InputIterator first, InputIterator last, 327 RandomAccessIterator result_first, RandomAccessIterator result_last); 328 329template <class InputIterator, class RandomAccessIterator, class Compare> 330 RandomAccessIterator 331 partial_sort_copy(InputIterator first, InputIterator last, 332 RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp); 333 334template <class RandomAccessIterator> 335 void 336 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); 337 338template <class RandomAccessIterator, class Compare> 339 void 340 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp); 341 342template <class ForwardIterator, class T> 343 ForwardIterator 344 lower_bound(ForwardIterator first, ForwardIterator last, const T& value); 345 346template <class ForwardIterator, class T, class Compare> 347 ForwardIterator 348 lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); 349 350template <class ForwardIterator, class T> 351 ForwardIterator 352 upper_bound(ForwardIterator first, ForwardIterator last, const T& value); 353 354template <class ForwardIterator, class T, class Compare> 355 ForwardIterator 356 upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); 357 358template <class ForwardIterator, class T> 359 pair<ForwardIterator, ForwardIterator> 360 equal_range(ForwardIterator first, ForwardIterator last, const T& value); 361 362template <class ForwardIterator, class T, class Compare> 363 pair<ForwardIterator, ForwardIterator> 364 equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); 365 366template <class ForwardIterator, class T> 367 bool 368 binary_search(ForwardIterator first, ForwardIterator last, const T& value); 369 370template <class ForwardIterator, class T, class Compare> 371 bool 372 binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); 373 374template <class InputIterator1, class InputIterator2, class OutputIterator> 375 OutputIterator 376 merge(InputIterator1 first1, InputIterator1 last1, 377 InputIterator2 first2, InputIterator2 last2, OutputIterator result); 378 379template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> 380 OutputIterator 381 merge(InputIterator1 first1, InputIterator1 last1, 382 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); 383 384template <class BidirectionalIterator> 385 void 386 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last); 387 388template <class BidirectionalIterator, class Compare> 389 void 390 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp); 391 392template <class InputIterator1, class InputIterator2> 393 bool 394 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); 395 396template <class InputIterator1, class InputIterator2, class Compare> 397 bool 398 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp); 399 400template <class InputIterator1, class InputIterator2, class OutputIterator> 401 OutputIterator 402 set_union(InputIterator1 first1, InputIterator1 last1, 403 InputIterator2 first2, InputIterator2 last2, OutputIterator result); 404 405template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> 406 OutputIterator 407 set_union(InputIterator1 first1, InputIterator1 last1, 408 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); 409 410template <class InputIterator1, class InputIterator2, class OutputIterator> 411 OutputIterator 412 set_intersection(InputIterator1 first1, InputIterator1 last1, 413 InputIterator2 first2, InputIterator2 last2, OutputIterator result); 414 415template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> 416 OutputIterator 417 set_intersection(InputIterator1 first1, InputIterator1 last1, 418 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); 419 420template <class InputIterator1, class InputIterator2, class OutputIterator> 421 OutputIterator 422 set_difference(InputIterator1 first1, InputIterator1 last1, 423 InputIterator2 first2, InputIterator2 last2, OutputIterator result); 424 425template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> 426 OutputIterator 427 set_difference(InputIterator1 first1, InputIterator1 last1, 428 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); 429 430template <class InputIterator1, class InputIterator2, class OutputIterator> 431 OutputIterator 432 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, 433 InputIterator2 first2, InputIterator2 last2, OutputIterator result); 434 435template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> 436 OutputIterator 437 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, 438 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); 439 440template <class RandomAccessIterator> 441 void 442 push_heap(RandomAccessIterator first, RandomAccessIterator last); 443 444template <class RandomAccessIterator, class Compare> 445 void 446 push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 447 448template <class RandomAccessIterator> 449 void 450 pop_heap(RandomAccessIterator first, RandomAccessIterator last); 451 452template <class RandomAccessIterator, class Compare> 453 void 454 pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 455 456template <class RandomAccessIterator> 457 void 458 make_heap(RandomAccessIterator first, RandomAccessIterator last); 459 460template <class RandomAccessIterator, class Compare> 461 void 462 make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 463 464template <class RandomAccessIterator> 465 void 466 sort_heap(RandomAccessIterator first, RandomAccessIterator last); 467 468template <class RandomAccessIterator, class Compare> 469 void 470 sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 471 472template <class RandomAccessIterator> 473 bool 474 is_heap(RandomAccessIterator first, RandomAccessiterator last); 475 476template <class RandomAccessIterator, class Compare> 477 bool 478 is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp); 479 480template <class RandomAccessIterator> 481 RandomAccessIterator 482 is_heap_until(RandomAccessIterator first, RandomAccessiterator last); 483 484template <class RandomAccessIterator, class Compare> 485 RandomAccessIterator 486 is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp); 487 488template <class ForwardIterator> 489 ForwardIterator 490 min_element(ForwardIterator first, ForwardIterator last); 491 492template <class ForwardIterator, class Compare> 493 ForwardIterator 494 min_element(ForwardIterator first, ForwardIterator last, Compare comp); 495 496template <class T> 497 const T& 498 min(const T& a, const T& b); 499 500template <class T, class Compare> 501 const T& 502 min(const T& a, const T& b, Compare comp); 503 504template<class T> 505 T 506 min(initializer_list<T> t); 507 508template<class T, class Compare> 509 T 510 min(initializer_list<T> t, Compare comp); 511 512template <class ForwardIterator> 513 ForwardIterator 514 max_element(ForwardIterator first, ForwardIterator last); 515 516template <class ForwardIterator, class Compare> 517 ForwardIterator 518 max_element(ForwardIterator first, ForwardIterator last, Compare comp); 519 520template <class T> 521 const T& 522 max(const T& a, const T& b); 523 524template <class T, class Compare> 525 const T& 526 max(const T& a, const T& b, Compare comp); 527 528template<class T> 529 T 530 max(initializer_list<T> t); 531 532template<class T, class Compare> 533 T 534 max(initializer_list<T> t, Compare comp); 535 536template<class ForwardIterator> 537 pair<ForwardIterator, ForwardIterator> 538 minmax_element(ForwardIterator first, ForwardIterator last); 539 540template<class ForwardIterator, class Compare> 541 pair<ForwardIterator, ForwardIterator> 542 minmax_element(ForwardIterator first, ForwardIterator last, Compare comp); 543 544template<class T> 545 pair<const T&, const T&> 546 minmax(const T& a, const T& b); 547 548template<class T, class Compare> 549 pair<const T&, const T&> 550 minmax(const T& a, const T& b, Compare comp); 551 552template<class T> 553 pair<T, T> 554 minmax(initializer_list<T> t); 555 556template<class T, class Compare> 557 pair<T, T> 558 minmax(initializer_list<T> t, Compare comp); 559 560template <class InputIterator1, class InputIterator2> 561 bool 562 lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); 563 564template <class InputIterator1, class InputIterator2, class Compare> 565 bool 566 lexicographical_compare(InputIterator1 first1, InputIterator1 last1, 567 InputIterator2 first2, InputIterator2 last2, Compare comp); 568 569template <class BidirectionalIterator> 570 bool 571 next_permutation(BidirectionalIterator first, BidirectionalIterator last); 572 573template <class BidirectionalIterator, class Compare> 574 bool 575 next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp); 576 577template <class BidirectionalIterator> 578 bool 579 prev_permutation(BidirectionalIterator first, BidirectionalIterator last); 580 581template <class BidirectionalIterator, class Compare> 582 bool 583 prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp); 584 585} // std 586 587*/ 588 589#include <__config> 590#include <initializer_list> 591#include <type_traits> 592#include <cstring> 593#include <utility> 594#include <memory> 595#include <iterator> 596#ifdef _LIBCPP_DEBUG 597#include <cassert> 598#endif 599#include <cstdlib> 600 601#pragma GCC system_header 602 603_LIBCPP_BEGIN_NAMESPACE_STD 604 605template <class _T1, class _T2 = _T1> 606struct __equal_to 607{ 608 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} 609 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T2& __y) const {return __x == __y;} 610 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T1& __y) const {return __x == __y;} 611 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T2& __y) const {return __x == __y;} 612}; 613 614template <class _T1> 615struct __equal_to<_T1, _T1> 616{ 617 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} 618}; 619 620template <class _T1> 621struct __equal_to<const _T1, _T1> 622{ 623 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} 624}; 625 626template <class _T1> 627struct __equal_to<_T1, const _T1> 628{ 629 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} 630}; 631 632template <class _T1, class _T2 = _T1> 633struct __less 634{ 635 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} 636 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T2& __y) const {return __x < __y;} 637 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T1& __y) const {return __x < __y;} 638 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T2& __y) const {return __x < __y;} 639}; 640 641template <class _T1> 642struct __less<_T1, _T1> 643{ 644 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} 645}; 646 647template <class _T1> 648struct __less<const _T1, _T1> 649{ 650 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} 651}; 652 653template <class _T1> 654struct __less<_T1, const _T1> 655{ 656 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} 657}; 658 659template <class _Predicate> 660class __negate 661{ 662private: 663 _Predicate __p_; 664public: 665 _LIBCPP_INLINE_VISIBILITY __negate() {} 666 667 _LIBCPP_INLINE_VISIBILITY 668 explicit __negate(_Predicate __p) : __p_(__p) {} 669 670 template <class _T1> 671 _LIBCPP_INLINE_VISIBILITY 672 bool operator()(const _T1& __x) {return !__p_(__x);} 673 674 template <class _T1, class _T2> 675 _LIBCPP_INLINE_VISIBILITY 676 bool operator()(const _T1& __x, const _T2& __y) {return !__p_(__x, __y);} 677}; 678 679#ifdef _LIBCPP_DEBUG 680 681template <class _Compare> 682struct __debug_less 683{ 684 _Compare __comp_; 685 __debug_less(_Compare& __c) : __comp_(__c) {} 686 template <class _Tp, class _Up> 687 bool operator()(const _Tp& __x, const _Up& __y) 688 { 689 bool __r = __comp_(__x, __y); 690 if (__r) 691 assert(!__comp_(__y, __x)); 692 return __r; 693 } 694}; 695 696#endif // _LIBCPP_DEBUG 697 698// Precondition: __x != 0 699inline _LIBCPP_INLINE_VISIBILITY unsigned __ctz(unsigned __x) {return __builtin_ctz (__x);} 700inline _LIBCPP_INLINE_VISIBILITY unsigned long __ctz(unsigned long __x) {return __builtin_ctzl (__x);} 701inline _LIBCPP_INLINE_VISIBILITY unsigned long long __ctz(unsigned long long __x) {return __builtin_ctzll(__x);} 702 703// Precondition: __x != 0 704inline _LIBCPP_INLINE_VISIBILITY unsigned __clz(unsigned __x) {return __builtin_clz (__x);} 705inline _LIBCPP_INLINE_VISIBILITY unsigned long __clz(unsigned long __x) {return __builtin_clzl (__x);} 706inline _LIBCPP_INLINE_VISIBILITY unsigned long long __clz(unsigned long long __x) {return __builtin_clzll(__x);} 707 708inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned __x) {return __builtin_popcount (__x);} 709inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long __x) {return __builtin_popcountl (__x);} 710inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long long __x) {return __builtin_popcountll(__x);} 711 712// all_of 713 714template <class _InputIterator, class _Predicate> 715inline _LIBCPP_INLINE_VISIBILITY 716bool 717all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) 718{ 719 for (; __first != __last; ++__first) 720 if (!__pred(*__first)) 721 return false; 722 return true; 723} 724 725// any_of 726 727template <class _InputIterator, class _Predicate> 728inline _LIBCPP_INLINE_VISIBILITY 729bool 730any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) 731{ 732 for (; __first != __last; ++__first) 733 if (__pred(*__first)) 734 return true; 735 return false; 736} 737 738// none_of 739 740template <class _InputIterator, class _Predicate> 741inline _LIBCPP_INLINE_VISIBILITY 742bool 743none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) 744{ 745 for (; __first != __last; ++__first) 746 if (__pred(*__first)) 747 return false; 748 return true; 749} 750 751// for_each 752 753template <class _InputIterator, class _Function> 754inline _LIBCPP_INLINE_VISIBILITY 755_Function 756for_each(_InputIterator __first, _InputIterator __last, _Function __f) 757{ 758 for (; __first != __last; ++__first) 759 __f(*__first); 760 return _STD::move(__f); 761} 762 763// find 764 765template <class _InputIterator, class _Tp> 766inline _LIBCPP_INLINE_VISIBILITY 767_InputIterator 768find(_InputIterator __first, _InputIterator __last, const _Tp& __value) 769{ 770 for (; __first != __last; ++__first) 771 if (*__first == __value) 772 break; 773 return __first; 774} 775 776// find_if 777 778template <class _InputIterator, class _Predicate> 779inline _LIBCPP_INLINE_VISIBILITY 780_InputIterator 781find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) 782{ 783 for (; __first != __last; ++__first) 784 if (__pred(*__first)) 785 break; 786 return __first; 787} 788 789// find_if_not 790 791template<class _InputIterator, class _Predicate> 792inline _LIBCPP_INLINE_VISIBILITY 793_InputIterator 794find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred) 795{ 796 for (; __first != __last; ++__first) 797 if (!__pred(*__first)) 798 break; 799 return __first; 800} 801 802// find_end 803 804template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2> 805_ForwardIterator1 806__find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 807 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred, 808 forward_iterator_tag, forward_iterator_tag) 809{ 810 // modeled after search algorithm 811 _ForwardIterator1 __r = __last1; // __last1 is the "default" answer 812 if (__first2 == __last2) 813 return __r; 814 while (true) 815 { 816 while (true) 817 { 818 if (__first1 == __last1) // if source exhausted return last correct answer 819 return __r; // (or __last1 if never found) 820 if (__pred(*__first1, *__first2)) 821 break; 822 ++__first1; 823 } 824 // *__first1 matches *__first2, now match elements after here 825 _ForwardIterator1 __m1 = __first1; 826 _ForwardIterator2 __m2 = __first2; 827 while (true) 828 { 829 if (++__m2 == __last2) 830 { // Pattern exhaused, record answer and search for another one 831 __r = __first1; 832 ++__first1; 833 break; 834 } 835 if (++__m1 == __last1) // Source exhausted, return last answer 836 return __r; 837 if (!__pred(*__m1, *__m2)) // mismatch, restart with a new __first 838 { 839 ++__first1; 840 break; 841 } // else there is a match, check next elements 842 } 843 } 844} 845 846template <class _BinaryPredicate, class _BidirectionalIterator1, class _BidirectionalIterator2> 847_BidirectionalIterator1 848__find_end(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, 849 _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BinaryPredicate __pred, 850 bidirectional_iterator_tag, bidirectional_iterator_tag) 851{ 852 // modeled after search algorithm (in reverse) 853 if (__first2 == __last2) 854 return __last1; // Everything matches an empty sequence 855 _BidirectionalIterator1 __l1 = __last1; 856 _BidirectionalIterator2 __l2 = __last2; 857 --__l2; 858 while (true) 859 { 860 // Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks 861 while (true) 862 { 863 if (__first1 == __l1) // return __last1 if no element matches *__first2 864 return __last1; 865 if (__pred(*--__l1, *__l2)) 866 break; 867 } 868 // *__l1 matches *__l2, now match elements before here 869 _BidirectionalIterator1 __m1 = __l1; 870 _BidirectionalIterator2 __m2 = __l2; 871 while (true) 872 { 873 if (__m2 == __first2) // If pattern exhausted, __m1 is the answer (works for 1 element pattern) 874 return __m1; 875 if (__m1 == __first1) // Otherwise if source exhaused, pattern not found 876 return __last1; 877 if (!__pred(*--__m1, *--__m2)) // if there is a mismatch, restart with a new __l1 878 { 879 break; 880 } // else there is a match, check next elements 881 } 882 } 883} 884 885template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2> 886_RandomAccessIterator1 887__find_end(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, 888 _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred, 889 random_access_iterator_tag, random_access_iterator_tag) 890{ 891 // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern 892 typename iterator_traits<_RandomAccessIterator2>::difference_type __len2 = __last2 - __first2; 893 if (__len2 == 0) 894 return __last1; 895 typename iterator_traits<_RandomAccessIterator1>::difference_type __len1 = __last1 - __first1; 896 if (__len1 < __len2) 897 return __last1; 898 const _RandomAccessIterator1 __s = __first1 + (__len2 - 1); // End of pattern match can't go before here 899 _RandomAccessIterator1 __l1 = __last1; 900 _RandomAccessIterator2 __l2 = __last2; 901 --__l2; 902 while (true) 903 { 904 while (true) 905 { 906 if (__s == __l1) 907 return __last1; 908 if (__pred(*--__l1, *__l2)) 909 break; 910 } 911 _RandomAccessIterator1 __m1 = __l1; 912 _RandomAccessIterator2 __m2 = __l2; 913 while (true) 914 { 915 if (__m2 == __first2) 916 return __m1; 917 // no need to check range on __m1 because __s guarantees we have enough source 918 if (!__pred(*--__m1, *--__m2)) 919 { 920 break; 921 } 922 } 923 } 924} 925 926template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> 927inline _LIBCPP_INLINE_VISIBILITY 928_ForwardIterator1 929find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 930 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred) 931{ 932 return _STD::__find_end<typename add_lvalue_reference<_BinaryPredicate>::type> 933 (__first1, __last1, __first2, __last2, __pred, 934 typename iterator_traits<_ForwardIterator1>::iterator_category(), 935 typename iterator_traits<_ForwardIterator2>::iterator_category()); 936} 937 938template <class _ForwardIterator1, class _ForwardIterator2> 939inline _LIBCPP_INLINE_VISIBILITY 940_ForwardIterator1 941find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 942 _ForwardIterator2 __first2, _ForwardIterator2 __last2) 943{ 944 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; 945 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; 946 return _STD::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); 947} 948 949// find_first_of 950 951template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> 952_ForwardIterator1 953find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 954 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred) 955{ 956 for (; __first1 != __last1; ++__first1) 957 for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j) 958 if (__pred(*__first1, *__j)) 959 return __first1; 960 return __last1; 961} 962 963template <class _ForwardIterator1, class _ForwardIterator2> 964inline _LIBCPP_INLINE_VISIBILITY 965_ForwardIterator1 966find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 967 _ForwardIterator2 __first2, _ForwardIterator2 __last2) 968{ 969 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; 970 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; 971 return _STD::find_first_of(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); 972} 973 974// adjacent_find 975 976template <class _ForwardIterator, class _BinaryPredicate> 977inline _LIBCPP_INLINE_VISIBILITY 978_ForwardIterator 979adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred) 980{ 981 if (__first != __last) 982 { 983 _ForwardIterator __i = __first; 984 while (++__i != __last) 985 { 986 if (__pred(*__first, *__i)) 987 return __first; 988 __first = __i; 989 } 990 } 991 return __last; 992} 993 994template <class _ForwardIterator> 995inline _LIBCPP_INLINE_VISIBILITY 996_ForwardIterator 997adjacent_find(_ForwardIterator __first, _ForwardIterator __last) 998{ 999 typedef typename iterator_traits<_ForwardIterator>::value_type __v; 1000 return _STD::adjacent_find(__first, __last, __equal_to<__v>()); 1001} 1002 1003// count 1004 1005template <class _InputIterator, class _Tp> 1006inline _LIBCPP_INLINE_VISIBILITY 1007typename iterator_traits<_InputIterator>::difference_type 1008count(_InputIterator __first, _InputIterator __last, const _Tp& __value) 1009{ 1010 typename iterator_traits<_InputIterator>::difference_type __r(0); 1011 for (; __first != __last; ++__first) 1012 if (*__first == __value) 1013 ++__r; 1014 return __r; 1015} 1016 1017// count_if 1018 1019template <class _InputIterator, class _Predicate> 1020inline _LIBCPP_INLINE_VISIBILITY 1021typename iterator_traits<_InputIterator>::difference_type 1022count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) 1023{ 1024 typename iterator_traits<_InputIterator>::difference_type __r(0); 1025 for (; __first != __last; ++__first) 1026 if (__pred(*__first)) 1027 ++__r; 1028 return __r; 1029} 1030 1031// mismatch 1032 1033template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate> 1034inline _LIBCPP_INLINE_VISIBILITY 1035pair<_InputIterator1, _InputIterator2> 1036mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 1037 _InputIterator2 __first2, _BinaryPredicate __pred) 1038{ 1039 for (; __first1 != __last1; ++__first1, ++__first2) 1040 if (!__pred(*__first1, *__first2)) 1041 break; 1042 return pair<_InputIterator1, _InputIterator2>(__first1, __first2); 1043} 1044 1045template <class _InputIterator1, class _InputIterator2> 1046inline _LIBCPP_INLINE_VISIBILITY 1047pair<_InputIterator1, _InputIterator2> 1048mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2) 1049{ 1050 typedef typename iterator_traits<_InputIterator1>::value_type __v1; 1051 typedef typename iterator_traits<_InputIterator2>::value_type __v2; 1052 return _STD::mismatch(__first1, __last1, __first2, __equal_to<__v1, __v2>()); 1053} 1054 1055// equal 1056 1057template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate> 1058inline _LIBCPP_INLINE_VISIBILITY 1059bool 1060equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred) 1061{ 1062 for (; __first1 != __last1; ++__first1, ++__first2) 1063 if (!__pred(*__first1, *__first2)) 1064 return false; 1065 return true; 1066} 1067 1068template <class _InputIterator1, class _InputIterator2> 1069inline _LIBCPP_INLINE_VISIBILITY 1070bool 1071equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2) 1072{ 1073 typedef typename iterator_traits<_InputIterator1>::value_type __v1; 1074 typedef typename iterator_traits<_InputIterator2>::value_type __v2; 1075 return _STD::equal(__first1, __last1, __first2, __equal_to<__v1, __v2>()); 1076} 1077 1078// is_permutation 1079 1080template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> 1081bool 1082is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 1083 _ForwardIterator2 __first2, _BinaryPredicate __pred) 1084{ 1085 // shorten sequences as much as possible by lopping of any equal parts 1086 for (; __first1 != __last1; ++__first1, ++__first2) 1087 if (!__pred(*__first1, *__first2)) 1088 goto __not_done; 1089 return true; 1090__not_done: 1091 // __first1 != __last1 && *__first1 != *__first2 1092 typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1; 1093 _D1 __l1 = _STD::distance(__first1, __last1); 1094 if (__l1 == _D1(1)) 1095 return false; 1096 _ForwardIterator2 __last2 = _STD::next(__first2, __l1); 1097 // For each element in [f1, l1) see if there are the same number of 1098 // equal elements in [f2, l2) 1099 for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i) 1100 { 1101 // Have we already counted the number of *__i in [f1, l1)? 1102 for (_ForwardIterator1 __j = __first1; __j != __i; ++__j) 1103 if (__pred(*__j, *__i)) 1104 goto __next_iter; 1105 { 1106 // Count number of *__i in [f2, l2) 1107 _D1 __c2 = 0; 1108 for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j) 1109 if (__pred(*__i, *__j)) 1110 ++__c2; 1111 if (__c2 == 0) 1112 return false; 1113 // Count number of *__i in [__i, l1) (we can start with 1) 1114 _D1 __c1 = 1; 1115 for (_ForwardIterator1 __j = _STD::next(__i); __j != __last1; ++__j) 1116 if (__pred(*__i, *__j)) 1117 ++__c1; 1118 if (__c1 != __c2) 1119 return false; 1120 } 1121__next_iter:; 1122 } 1123 return true; 1124} 1125 1126template<class _ForwardIterator1, class _ForwardIterator2> 1127inline _LIBCPP_INLINE_VISIBILITY 1128bool 1129is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 1130 _ForwardIterator2 __first2) 1131{ 1132 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; 1133 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; 1134 return _STD::is_permutation(__first1, __last1, __first2, __equal_to<__v1, __v2>()); 1135} 1136 1137// search 1138 1139template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2> 1140_ForwardIterator1 1141__search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 1142 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred, 1143 forward_iterator_tag, forward_iterator_tag) 1144{ 1145 if (__first2 == __last2) 1146 return __first1; // Everything matches an empty sequence 1147 while (true) 1148 { 1149 // Find first element in sequence 1 that matchs *__first2, with a mininum of loop checks 1150 while (true) 1151 { 1152 if (__first1 == __last1) // return __last1 if no element matches *__first2 1153 return __last1; 1154 if (__pred(*__first1, *__first2)) 1155 break; 1156 ++__first1; 1157 } 1158 // *__first1 matches *__first2, now match elements after here 1159 _ForwardIterator1 __m1 = __first1; 1160 _ForwardIterator2 __m2 = __first2; 1161 while (true) 1162 { 1163 if (++__m2 == __last2) // If pattern exhausted, __first1 is the answer (works for 1 element pattern) 1164 return __first1; 1165 if (++__m1 == __last1) // Otherwise if source exhaused, pattern not found 1166 return __last1; 1167 if (!__pred(*__m1, *__m2)) // if there is a mismatch, restart with a new __first1 1168 { 1169 ++__first1; 1170 break; 1171 } // else there is a match, check next elements 1172 } 1173 } 1174} 1175 1176template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2> 1177_RandomAccessIterator1 1178__search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, 1179 _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred, 1180 random_access_iterator_tag, random_access_iterator_tag) 1181{ 1182 typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _D1; 1183 typedef typename std::iterator_traits<_RandomAccessIterator2>::difference_type _D2; 1184 // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern 1185 _D2 __len2 = __last2 - __first2; 1186 if (__len2 == 0) 1187 return __first1; 1188 _D1 __len1 = __last1 - __first1; 1189 if (__len1 < __len2) 1190 return __last1; 1191 const _RandomAccessIterator1 __s = __last1 - (__len2 - 1); // Start of pattern match can't go beyond here 1192 while (true) 1193 { 1194#if !_LIBCPP_UNROLL_LOOPS 1195 while (true) 1196 { 1197 if (__first1 == __s) 1198 return __last1; 1199 if (__pred(*__first1, *__first2)) 1200 break; 1201 ++__first1; 1202 } 1203#else // !_LIBCPP_UNROLL_LOOPS 1204 for (_D1 __loop_unroll = (__s - __first1) / 4; __loop_unroll > 0; --__loop_unroll) 1205 { 1206 if (__pred(*__first1, *__first2)) 1207 goto __phase2; 1208 if (__pred(*++__first1, *__first2)) 1209 goto __phase2; 1210 if (__pred(*++__first1, *__first2)) 1211 goto __phase2; 1212 if (__pred(*++__first1, *__first2)) 1213 goto __phase2; 1214 ++__first1; 1215 } 1216 switch (__s - __first1) 1217 { 1218 case 3: 1219 if (__pred(*__first1, *__first2)) 1220 break; 1221 ++__first1; 1222 case 2: 1223 if (__pred(*__first1, *__first2)) 1224 break; 1225 ++__first1; 1226 case 1: 1227 if (__pred(*__first1, *__first2)) 1228 break; 1229 case 0: 1230 return __last1; 1231 } 1232 __phase2: 1233#endif // !_LIBCPP_UNROLL_LOOPS 1234 _RandomAccessIterator1 __m1 = __first1; 1235 _RandomAccessIterator2 __m2 = __first2; 1236#if !_LIBCPP_UNROLL_LOOPS 1237 while (true) 1238 { 1239 if (++__m2 == __last2) 1240 return __first1; 1241 ++__m1; // no need to check range on __m1 because __s guarantees we have enough source 1242 if (!__pred(*__m1, *__m2)) 1243 { 1244 ++__first1; 1245 break; 1246 } 1247 } 1248#else // !_LIBCPP_UNROLL_LOOPS 1249 ++__m2; 1250 ++__m1; 1251 for (_D2 __loop_unroll = (__last2 - __m2) / 4; __loop_unroll > 0; --__loop_unroll) 1252 { 1253 if (!__pred(*__m1, *__m2)) 1254 goto __continue; 1255 if (!__pred(*++__m1, *++__m2)) 1256 goto __continue; 1257 if (!__pred(*++__m1, *++__m2)) 1258 goto __continue; 1259 if (!__pred(*++__m1, *++__m2)) 1260 goto __continue; 1261 ++__m1; 1262 ++__m2; 1263 } 1264 switch (__last2 - __m2) 1265 { 1266 case 3: 1267 if (!__pred(*__m1, *__m2)) 1268 break; 1269 ++__m1; 1270 ++__m2; 1271 case 2: 1272 if (!__pred(*__m1, *__m2)) 1273 break; 1274 ++__m1; 1275 ++__m2; 1276 case 1: 1277 if (!__pred(*__m1, *__m2)) 1278 break; 1279 case 0: 1280 return __first1; 1281 } 1282 __continue: 1283 ++__first1; 1284#endif // !_LIBCPP_UNROLL_LOOPS 1285 } 1286} 1287 1288template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> 1289inline _LIBCPP_INLINE_VISIBILITY 1290_ForwardIterator1 1291search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 1292 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred) 1293{ 1294 return _STD::__search<typename add_lvalue_reference<_BinaryPredicate>::type> 1295 (__first1, __last1, __first2, __last2, __pred, 1296 typename std::iterator_traits<_ForwardIterator1>::iterator_category(), 1297 typename std::iterator_traits<_ForwardIterator2>::iterator_category()); 1298} 1299 1300template <class _ForwardIterator1, class _ForwardIterator2> 1301inline _LIBCPP_INLINE_VISIBILITY 1302_ForwardIterator1 1303search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 1304 _ForwardIterator2 __first2, _ForwardIterator2 __last2) 1305{ 1306 typedef typename std::iterator_traits<_ForwardIterator1>::value_type __v1; 1307 typedef typename std::iterator_traits<_ForwardIterator2>::value_type __v2; 1308 return _STD::search(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); 1309} 1310 1311// search_n 1312 1313template <class _BinaryPredicate, class _ForwardIterator, class _Size, class _Tp> 1314_ForwardIterator 1315__search_n(_ForwardIterator __first, _ForwardIterator __last, 1316 _Size __count, const _Tp& __value, _BinaryPredicate __pred, forward_iterator_tag) 1317{ 1318 if (__count <= 0) 1319 return __first; 1320 while (true) 1321 { 1322 // Find first element in sequence that matchs __value, with a mininum of loop checks 1323 while (true) 1324 { 1325 if (__first == __last) // return __last if no element matches __value 1326 return __last; 1327 if (__pred(*__first, __value)) 1328 break; 1329 ++__first; 1330 } 1331 // *__first matches __value, now match elements after here 1332 _ForwardIterator __m = __first; 1333 _Size __c(0); 1334 while (true) 1335 { 1336 if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern) 1337 return __first; 1338 if (++__m == __last) // Otherwise if source exhaused, pattern not found 1339 return __last; 1340 if (!__pred(*__m, __value)) // if there is a mismatch, restart with a new __first 1341 { 1342 __first = __m; 1343 ++__first; 1344 break; 1345 } // else there is a match, check next elements 1346 } 1347 } 1348} 1349 1350template <class _BinaryPredicate, class _RandomAccessIterator, class _Size, class _Tp> 1351_RandomAccessIterator 1352__search_n(_RandomAccessIterator __first, _RandomAccessIterator __last, 1353 _Size __count, const _Tp& __value, _BinaryPredicate __pred, random_access_iterator_tag) 1354{ 1355 if (__count <= 0) 1356 return __first; 1357 _Size __len = static_cast<_Size>(__last - __first); 1358 if (__len < __count) 1359 return __last; 1360 const _RandomAccessIterator __s = __last - (__count - 1); // Start of pattern match can't go beyond here 1361 while (true) 1362 { 1363 // Find first element in sequence that matchs __value, with a mininum of loop checks 1364 while (true) 1365 { 1366 if (__first == __s) // return __last if no element matches __value 1367 return __last; 1368 if (__pred(*__first, __value)) 1369 break; 1370 ++__first; 1371 } 1372 // *__first matches __value, now match elements after here 1373 _RandomAccessIterator __m = __first; 1374 _Size __c(0); 1375 while (true) 1376 { 1377 if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern) 1378 return __first; 1379 ++__m; // no need to check range on __m because __s guarantees we have enough source 1380 if (!__pred(*__m, __value)) // if there is a mismatch, restart with a new __first 1381 { 1382 __first = __m; 1383 ++__first; 1384 break; 1385 } // else there is a match, check next elements 1386 } 1387 } 1388} 1389 1390template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate> 1391inline _LIBCPP_INLINE_VISIBILITY 1392_ForwardIterator 1393search_n(_ForwardIterator __first, _ForwardIterator __last, 1394 _Size __count, const _Tp& __value, _BinaryPredicate __pred) 1395{ 1396 return _STD::__search_n<typename add_lvalue_reference<_BinaryPredicate>::type> 1397 (__first, __last, __count, __value, __pred, typename iterator_traits<_ForwardIterator>::iterator_category()); 1398} 1399 1400template <class _ForwardIterator, class _Size, class _Tp> 1401inline _LIBCPP_INLINE_VISIBILITY 1402_ForwardIterator 1403search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value) 1404{ 1405 typedef typename iterator_traits<_ForwardIterator>::value_type __v; 1406 return _STD::search_n(__first, __last, __count, __value, __equal_to<__v, _Tp>()); 1407} 1408 1409// copy 1410 1411template <class _Iter> 1412struct __libcpp_is_trivial_iterator 1413{ 1414 static const bool value = is_pointer<_Iter>::value; 1415}; 1416 1417template <class _Iter> 1418struct __libcpp_is_trivial_iterator<move_iterator<_Iter> > 1419{ 1420 static const bool value = is_pointer<_Iter>::value; 1421}; 1422 1423template <class _Iter> 1424struct __libcpp_is_trivial_iterator<__wrap_iter<_Iter> > 1425{ 1426 static const bool value = is_pointer<_Iter>::value; 1427}; 1428 1429template <class _Iter> 1430inline _LIBCPP_INLINE_VISIBILITY 1431_Iter 1432__unwrap_iter(_Iter __i) 1433{ 1434 return __i; 1435} 1436 1437template <class _Tp> 1438inline _LIBCPP_INLINE_VISIBILITY 1439typename enable_if 1440< 1441 has_trivial_copy_assign<_Tp>::value, 1442 _Tp* 1443>::type 1444__unwrap_iter(move_iterator<_Tp*> __i) 1445{ 1446 return __i.base(); 1447} 1448 1449template <class _Tp> 1450inline _LIBCPP_INLINE_VISIBILITY 1451typename enable_if 1452< 1453 has_trivial_copy_assign<_Tp>::value, 1454 _Tp* 1455>::type 1456__unwrap_iter(__wrap_iter<_Tp*> __i) 1457{ 1458 return __i.base(); 1459} 1460 1461template <class _InputIterator, class _OutputIterator> 1462inline _LIBCPP_INLINE_VISIBILITY 1463_OutputIterator 1464__copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) 1465{ 1466 for (; __first != __last; ++__first, ++__result) 1467 *__result = *__first; 1468 return __result; 1469} 1470 1471template <class _Tp, class _Up> 1472inline _LIBCPP_INLINE_VISIBILITY 1473typename enable_if 1474< 1475 is_same<typename remove_const<_Tp>::type, _Up>::value && 1476 has_trivial_copy_assign<_Up>::value, 1477 _Up* 1478>::type 1479__copy(_Tp* __first, _Tp* __last, _Up* __result) 1480{ 1481 const size_t __n = static_cast<size_t>(__last - __first); 1482 _STD::memmove(__result, __first, __n * sizeof(_Up)); 1483 return __result + __n; 1484} 1485 1486template <class _InputIterator, class _OutputIterator> 1487inline _LIBCPP_INLINE_VISIBILITY 1488_OutputIterator 1489copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) 1490{ 1491 return _STD::__copy(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result)); 1492} 1493 1494// copy_backward 1495 1496template <class _InputIterator, class _OutputIterator> 1497inline _LIBCPP_INLINE_VISIBILITY 1498_OutputIterator 1499__copy_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result) 1500{ 1501 while (__first != __last) 1502 *--__result = *--__last; 1503 return __result; 1504} 1505 1506template <class _Tp, class _Up> 1507inline _LIBCPP_INLINE_VISIBILITY 1508typename enable_if 1509< 1510 is_same<typename remove_const<_Tp>::type, _Up>::value && 1511 has_trivial_copy_assign<_Up>::value, 1512 _Up* 1513>::type 1514__copy_backward(_Tp* __first, _Tp* __last, _Up* __result) 1515{ 1516 const size_t __n = static_cast<size_t>(__last - __first); 1517 __result -= __n; 1518 _STD::memmove(__result, __first, __n * sizeof(_Up)); 1519 return __result; 1520} 1521 1522template <class _BidirectionalIterator1, class _BidirectionalIterator2> 1523inline _LIBCPP_INLINE_VISIBILITY 1524_BidirectionalIterator2 1525copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, 1526 _BidirectionalIterator2 __result) 1527{ 1528 return _STD::__copy_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result)); 1529} 1530 1531// copy_if 1532 1533template<class _InputIterator, class _OutputIterator, class _Predicate> 1534inline _LIBCPP_INLINE_VISIBILITY 1535_OutputIterator 1536copy_if(_InputIterator __first, _InputIterator __last, 1537 _OutputIterator __result, _Predicate __pred) 1538{ 1539 for (; __first != __last; ++__first) 1540 { 1541 if (__pred(*__first)) 1542 { 1543 *__result = *__first; 1544 ++__result; 1545 } 1546 } 1547 return __result; 1548} 1549 1550// copy_n 1551 1552template<class _InputIterator, class _Size, class _OutputIterator> 1553inline _LIBCPP_INLINE_VISIBILITY 1554typename enable_if 1555< 1556 __is_input_iterator<_InputIterator>::value && 1557 !__is_random_access_iterator<_InputIterator>::value, 1558 _OutputIterator 1559>::type 1560copy_n(_InputIterator __first, _Size __n, _OutputIterator __result) 1561{ 1562 for (; __n > 0; --__n, ++__first, ++__result) 1563 *__result = *__first; 1564 return __result; 1565} 1566 1567template<class _InputIterator, class _Size, class _OutputIterator> 1568inline _LIBCPP_INLINE_VISIBILITY 1569typename enable_if 1570< 1571 __is_random_access_iterator<_InputIterator>::value, 1572 _OutputIterator 1573>::type 1574copy_n(_InputIterator __first, _Size __n, _OutputIterator __result) 1575{ 1576 return copy(__first, __first + __n, __result); 1577} 1578 1579// move 1580 1581template <class _InputIterator, class _OutputIterator> 1582inline _LIBCPP_INLINE_VISIBILITY 1583_OutputIterator 1584__move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) 1585{ 1586 for (; __first != __last; ++__first, ++__result) 1587 *__result = _STD::move(*__first); 1588 return __result; 1589} 1590 1591template <class _Tp, class _Up> 1592inline _LIBCPP_INLINE_VISIBILITY 1593typename enable_if 1594< 1595 is_same<typename remove_const<_Tp>::type, _Up>::value && 1596 has_trivial_copy_assign<_Up>::value, 1597 _Up* 1598>::type 1599__move(_Tp* __first, _Tp* __last, _Up* __result) 1600{ 1601 const size_t __n = static_cast<size_t>(__last - __first); 1602 _STD::memmove(__result, __first, __n * sizeof(_Up)); 1603 return __result + __n; 1604} 1605 1606template <class _InputIterator, class _OutputIterator> 1607inline _LIBCPP_INLINE_VISIBILITY 1608_OutputIterator 1609move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) 1610{ 1611 return _STD::__move(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result)); 1612} 1613 1614// move_backward 1615 1616template <class _InputIterator, class _OutputIterator> 1617inline _LIBCPP_INLINE_VISIBILITY 1618_OutputIterator 1619__move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result) 1620{ 1621 while (__first != __last) 1622 *--__result = _STD::move(*--__last); 1623 return __result; 1624} 1625 1626template <class _Tp, class _Up> 1627inline _LIBCPP_INLINE_VISIBILITY 1628typename enable_if 1629< 1630 is_same<typename remove_const<_Tp>::type, _Up>::value && 1631 has_trivial_copy_assign<_Up>::value, 1632 _Up* 1633>::type 1634__move_backward(_Tp* __first, _Tp* __last, _Up* __result) 1635{ 1636 const size_t __n = static_cast<size_t>(__last - __first); 1637 __result -= __n; 1638 _STD::memmove(__result, __first, __n * sizeof(_Up)); 1639 return __result; 1640} 1641 1642template <class _BidirectionalIterator1, class _BidirectionalIterator2> 1643inline _LIBCPP_INLINE_VISIBILITY 1644_BidirectionalIterator2 1645move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, 1646 _BidirectionalIterator2 __result) 1647{ 1648 return _STD::__move_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result)); 1649} 1650 1651// iter_swap 1652 1653template <class _ForwardIterator1, class _ForwardIterator2> 1654inline _LIBCPP_INLINE_VISIBILITY 1655void 1656iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) 1657{ 1658 swap(*__a, *__b); 1659} 1660 1661// transform 1662 1663template <class _InputIterator, class _OutputIterator, class _UnaryOperation> 1664inline _LIBCPP_INLINE_VISIBILITY 1665_OutputIterator 1666transform(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _UnaryOperation __op) 1667{ 1668 for (; __first != __last; ++__first, ++__result) 1669 *__result = __op(*__first); 1670 return __result; 1671} 1672 1673template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _BinaryOperation> 1674inline _LIBCPP_INLINE_VISIBILITY 1675_OutputIterator 1676transform(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, 1677 _OutputIterator __result, _BinaryOperation __binary_op) 1678{ 1679 for (; __first1 != __last1; ++__first1, ++__first2, ++__result) 1680 *__result = __binary_op(*__first1, *__first2); 1681 return __result; 1682} 1683 1684// replace 1685 1686template <class _ForwardIterator, class _Tp> 1687inline _LIBCPP_INLINE_VISIBILITY 1688void 1689replace(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __old_value, const _Tp& __new_value) 1690{ 1691 for (; __first != __last; ++__first) 1692 if (*__first == __old_value) 1693 *__first = __new_value; 1694} 1695 1696// replace_if 1697 1698template <class _ForwardIterator, class _Predicate, class _Tp> 1699inline _LIBCPP_INLINE_VISIBILITY 1700void 1701replace_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, const _Tp& __new_value) 1702{ 1703 for (; __first != __last; ++__first) 1704 if (__pred(*__first)) 1705 *__first = __new_value; 1706} 1707 1708// replace_copy 1709 1710template <class _InputIterator, class _OutputIterator, class _Tp> 1711inline _LIBCPP_INLINE_VISIBILITY 1712_OutputIterator 1713replace_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, 1714 const _Tp& __old_value, const _Tp& __new_value) 1715{ 1716 for (; __first != __last; ++__first, ++__result) 1717 if (*__first == __old_value) 1718 *__result = __new_value; 1719 else 1720 *__result = *__first; 1721 return __result; 1722} 1723 1724// replace_copy_if 1725 1726template <class _InputIterator, class _OutputIterator, class _Predicate, class _Tp> 1727inline _LIBCPP_INLINE_VISIBILITY 1728_OutputIterator 1729replace_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, 1730 _Predicate __pred, const _Tp& __new_value) 1731{ 1732 for (; __first != __last; ++__first, ++__result) 1733 if (__pred(*__first)) 1734 *__result = __new_value; 1735 else 1736 *__result = *__first; 1737 return __result; 1738} 1739 1740// fill_n 1741 1742template <class _OutputIterator, class _Size, class _Tp> 1743inline _LIBCPP_INLINE_VISIBILITY 1744_OutputIterator 1745__fill_n(_OutputIterator __first, _Size __n, const _Tp& __value, false_type) 1746{ 1747 for (; __n > 0; ++__first, --__n) 1748 *__first = __value; 1749 return __first; 1750} 1751 1752template <class _OutputIterator, class _Size, class _Tp> 1753inline _LIBCPP_INLINE_VISIBILITY 1754_OutputIterator 1755__fill_n(_OutputIterator __first, _Size __n, const _Tp& __value, true_type) 1756{ 1757 if (__n > 0) 1758 _STD::memset(__first, (unsigned char)__value, (size_t)(__n)); 1759 return __first + __n; 1760} 1761 1762template <class _OutputIterator, class _Size, class _Tp> 1763inline _LIBCPP_INLINE_VISIBILITY 1764_OutputIterator 1765fill_n(_OutputIterator __first, _Size __n, const _Tp& __value) 1766{ 1767 return _STD::__fill_n(__first, __n, __value, integral_constant<bool, 1768 is_pointer<_OutputIterator>::value && 1769 has_trivial_copy_assign<_Tp>::value && 1770 sizeof(_Tp) == 1>()); 1771} 1772 1773// fill 1774 1775template <class _ForwardIterator, class _Tp> 1776inline _LIBCPP_INLINE_VISIBILITY 1777void 1778__fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, forward_iterator_tag) 1779{ 1780 for (; __first != __last; ++__first) 1781 *__first = __value; 1782} 1783 1784template <class _RandomAccessIterator, class _Tp> 1785inline _LIBCPP_INLINE_VISIBILITY 1786void 1787__fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value, random_access_iterator_tag) 1788{ 1789 _STD::fill_n(__first, __last - __first, __value); 1790} 1791 1792template <class _ForwardIterator, class _Tp> 1793inline _LIBCPP_INLINE_VISIBILITY 1794void 1795fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) 1796{ 1797 _STD::__fill(__first, __last, __value, typename iterator_traits<_ForwardIterator>::iterator_category()); 1798} 1799 1800// generate 1801 1802template <class _ForwardIterator, class _Generator> 1803inline _LIBCPP_INLINE_VISIBILITY 1804void 1805generate(_ForwardIterator __first, _ForwardIterator __last, _Generator __gen) 1806{ 1807 for (; __first != __last; ++__first) 1808 *__first = __gen(); 1809} 1810 1811// generate_n 1812 1813template <class _OutputIterator, class _Size, class _Generator> 1814inline _LIBCPP_INLINE_VISIBILITY 1815_OutputIterator 1816generate_n(_OutputIterator __first, _Size __n, _Generator __gen) 1817{ 1818 for (; __n > 0; ++__first, --__n) 1819 *__first = __gen(); 1820 return __first; 1821} 1822 1823// remove 1824 1825template <class _ForwardIterator, class _Tp> 1826_ForwardIterator 1827remove(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) 1828{ 1829 __first = _STD::find(__first, __last, __value); 1830 if (__first != __last) 1831 { 1832 _ForwardIterator __i = __first; 1833 while (++__i != __last) 1834 { 1835 if (!(*__i == __value)) 1836 { 1837 *__first = _STD::move(*__i); 1838 ++__first; 1839 } 1840 } 1841 } 1842 return __first; 1843} 1844 1845// remove_if 1846 1847template <class _ForwardIterator, class _Predicate> 1848_ForwardIterator 1849remove_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) 1850{ 1851 __first = _STD::find_if<_ForwardIterator, typename add_lvalue_reference<_Predicate>::type> 1852 (__first, __last, __pred); 1853 if (__first != __last) 1854 { 1855 _ForwardIterator __i = __first; 1856 while (++__i != __last) 1857 { 1858 if (!__pred(*__i)) 1859 { 1860 *__first = _STD::move(*__i); 1861 ++__first; 1862 } 1863 } 1864 } 1865 return __first; 1866} 1867 1868// remove_copy 1869 1870template <class _InputIterator, class _OutputIterator, class _Tp> 1871inline _LIBCPP_INLINE_VISIBILITY 1872_OutputIterator 1873remove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __value) 1874{ 1875 for (; __first != __last; ++__first) 1876 { 1877 if (!(*__first == __value)) 1878 { 1879 *__result = *__first; 1880 ++__result; 1881 } 1882 } 1883 return __result; 1884} 1885 1886// remove_copy_if 1887 1888template <class _InputIterator, class _OutputIterator, class _Predicate> 1889inline _LIBCPP_INLINE_VISIBILITY 1890_OutputIterator 1891remove_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred) 1892{ 1893 for (; __first != __last; ++__first) 1894 { 1895 if (!__pred(*__first)) 1896 { 1897 *__result = *__first; 1898 ++__result; 1899 } 1900 } 1901 return __result; 1902} 1903 1904// unique 1905 1906template <class _ForwardIterator, class _BinaryPredicate> 1907_ForwardIterator 1908unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred) 1909{ 1910 __first = _STD::adjacent_find<_ForwardIterator, typename add_lvalue_reference<_BinaryPredicate>::type> 1911 (__first, __last, __pred); 1912 if (__first != __last) 1913 { 1914 // ... a a ? ... 1915 // f i 1916 _ForwardIterator __i = __first; 1917 for (++__i; ++__i != __last;) 1918 if (!__pred(*__first, *__i)) 1919 *++__first = _STD::move(*__i); 1920 ++__first; 1921 } 1922 return __first; 1923} 1924 1925template <class _ForwardIterator> 1926inline _LIBCPP_INLINE_VISIBILITY 1927_ForwardIterator 1928unique(_ForwardIterator __first, _ForwardIterator __last) 1929{ 1930 typedef typename iterator_traits<_ForwardIterator>::value_type __v; 1931 return _STD::unique(__first, __last, __equal_to<__v>()); 1932} 1933 1934// unique_copy 1935 1936template <class _BinaryPredicate, class _InputIterator, class _OutputIterator> 1937_OutputIterator 1938__unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred, 1939 input_iterator_tag, output_iterator_tag) 1940{ 1941 if (__first != __last) 1942 { 1943 typename iterator_traits<_InputIterator>::value_type __t(*__first); 1944 *__result = __t; 1945 ++__result; 1946 while (++__first != __last) 1947 { 1948 if (!__pred(__t, *__first)) 1949 { 1950 __t = *__first; 1951 *__result = __t; 1952 ++__result; 1953 } 1954 } 1955 } 1956 return __result; 1957} 1958 1959template <class _BinaryPredicate, class _ForwardIterator, class _OutputIterator> 1960_OutputIterator 1961__unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __pred, 1962 forward_iterator_tag, output_iterator_tag) 1963{ 1964 if (__first != __last) 1965 { 1966 _ForwardIterator __i = __first; 1967 *__result = *__i; 1968 ++__result; 1969 while (++__first != __last) 1970 { 1971 if (!__pred(*__i, *__first)) 1972 { 1973 *__result = *__first; 1974 ++__result; 1975 __i = __first; 1976 } 1977 } 1978 } 1979 return __result; 1980} 1981 1982template <class _BinaryPredicate, class _InputIterator, class _ForwardIterator> 1983_ForwardIterator 1984__unique_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _BinaryPredicate __pred, 1985 input_iterator_tag, forward_iterator_tag) 1986{ 1987 if (__first != __last) 1988 { 1989 *__result = *__first; 1990 while (++__first != __last) 1991 if (!__pred(*__result, *__first)) 1992 *++__result = *__first; 1993 ++__result; 1994 } 1995 return __result; 1996} 1997 1998template <class _InputIterator, class _OutputIterator, class _BinaryPredicate> 1999inline _LIBCPP_INLINE_VISIBILITY 2000_OutputIterator 2001unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred) 2002{ 2003 return _STD::__unique_copy<typename add_lvalue_reference<_BinaryPredicate>::type> 2004 (__first, __last, __result, __pred, 2005 typename iterator_traits<_InputIterator>::iterator_category(), 2006 typename iterator_traits<_OutputIterator>::iterator_category()); 2007} 2008 2009template <class _InputIterator, class _OutputIterator> 2010inline _LIBCPP_INLINE_VISIBILITY 2011_OutputIterator 2012unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) 2013{ 2014 typedef typename iterator_traits<_InputIterator>::value_type __v; 2015 return _STD::unique_copy(__first, __last, __result, __equal_to<__v>()); 2016} 2017 2018// reverse 2019 2020template <class _BidirectionalIterator> 2021inline _LIBCPP_INLINE_VISIBILITY 2022void 2023__reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag) 2024{ 2025 while (__first != __last) 2026 { 2027 if (__first == --__last) 2028 break; 2029 swap(*__first, *__last); 2030 ++__first; 2031 } 2032} 2033 2034template <class _RandomAccessIterator> 2035inline _LIBCPP_INLINE_VISIBILITY 2036void 2037__reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag) 2038{ 2039 if (__first != __last) 2040 for (; __first < --__last; ++__first) 2041 swap(*__first, *__last); 2042} 2043 2044template <class _BidirectionalIterator> 2045inline _LIBCPP_INLINE_VISIBILITY 2046void 2047reverse(_BidirectionalIterator __first, _BidirectionalIterator __last) 2048{ 2049 _STD::__reverse(__first, __last, typename iterator_traits<_BidirectionalIterator>::iterator_category()); 2050} 2051 2052// reverse_copy 2053 2054template <class _BidirectionalIterator, class _OutputIterator> 2055inline _LIBCPP_INLINE_VISIBILITY 2056_OutputIterator 2057reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result) 2058{ 2059 for (; __first != __last; ++__result) 2060 *__result = *--__last; 2061 return __result; 2062} 2063 2064// rotate 2065 2066template <class _ForwardIterator> 2067_ForwardIterator 2068__rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, false_type) 2069{ 2070 if (__first == __middle) 2071 return __last; 2072 if (__middle == __last) 2073 return __first; 2074 _ForwardIterator __i = __middle; 2075 while (true) 2076 { 2077 swap(*__first, *__i); 2078 ++__first; 2079 if (++__i == __last) 2080 break; 2081 if (__first == __middle) 2082 __middle = __i; 2083 } 2084 _ForwardIterator __r = __first; 2085 if (__first != __middle) 2086 { 2087 __i = __middle; 2088 while (true) 2089 { 2090 swap(*__first, *__i); 2091 ++__first; 2092 if (++__i == __last) 2093 { 2094 if (__first == __middle) 2095 break; 2096 __i = __middle; 2097 } 2098 else if (__first == __middle) 2099 __middle = __i; 2100 } 2101 } 2102 return __r; 2103} 2104 2105template<typename _Integral> 2106inline _LIBCPP_INLINE_VISIBILITY 2107_Integral 2108__gcd(_Integral __x, _Integral __y) 2109{ 2110 do 2111 { 2112 _Integral __t = __x % __y; 2113 __x = __y; 2114 __y = __t; 2115 } while (__y); 2116 return __x; 2117} 2118 2119template<typename _RandomAccessIterator> 2120_RandomAccessIterator 2121__rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, true_type) 2122{ 2123 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 2124 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 2125 2126 if (__first == __middle) 2127 return __last; 2128 if (__middle == __last) 2129 return __first; 2130 const difference_type __m1 = __middle - __first; 2131 const difference_type __m2 = __last - __middle; 2132 if (__m1 == __m2) 2133 { 2134 _STD::swap_ranges(__first, __middle, __middle); 2135 return __middle; 2136 } 2137 const difference_type __g = __gcd(__m1, __m2); 2138 for (_RandomAccessIterator __p = __first + __g; __p != __first;) 2139 { 2140 value_type __t(*--__p); 2141 _RandomAccessIterator __p1 = __p; 2142 _RandomAccessIterator __p2 = __p1 + __m1; 2143 do 2144 { 2145 *__p1 = *__p2; 2146 __p1 = __p2; 2147 const difference_type __d = __last - __p2; 2148 if (__m1 < __d) 2149 __p2 += __m1; 2150 else 2151 __p2 = __first + (__m1 - __d); 2152 } while (__p2 != __p); 2153 *__p1 = __t; 2154 } 2155 return __first + __m2; 2156} 2157 2158template <class _ForwardIterator> 2159inline _LIBCPP_INLINE_VISIBILITY 2160_ForwardIterator 2161rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last) 2162{ 2163 return _STD::__rotate(__first, __middle, __last, 2164 integral_constant 2165 < 2166 bool, 2167 is_convertible 2168 < 2169 typename iterator_traits<_ForwardIterator>::iterator_category, 2170 random_access_iterator_tag 2171 >::value && 2172 has_trivial_copy_assign 2173 < 2174 typename iterator_traits<_ForwardIterator>::value_type 2175 >::value 2176 >()); 2177} 2178 2179// rotate_copy 2180 2181template <class _ForwardIterator, class _OutputIterator> 2182inline _LIBCPP_INLINE_VISIBILITY 2183_OutputIterator 2184rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, _OutputIterator __result) 2185{ 2186 return _STD::copy(__first, __middle, _STD::copy(__middle, __last, __result)); 2187} 2188 2189// min_element 2190 2191template <class _ForwardIterator, class _Compare> 2192inline _LIBCPP_INLINE_VISIBILITY 2193_ForwardIterator 2194min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) 2195{ 2196 if (__first != __last) 2197 { 2198 _ForwardIterator __i = __first; 2199 while (++__i != __last) 2200 if (__comp(*__i, *__first)) 2201 __first = __i; 2202 } 2203 return __first; 2204} 2205 2206template <class _ForwardIterator> 2207inline _LIBCPP_INLINE_VISIBILITY 2208_ForwardIterator 2209min_element(_ForwardIterator __first, _ForwardIterator __last) 2210{ 2211 return _STD::min_element(__first, __last, 2212 __less<typename iterator_traits<_ForwardIterator>::value_type>()); 2213} 2214 2215// min 2216 2217template <class _Tp, class _Compare> 2218inline _LIBCPP_INLINE_VISIBILITY 2219const _Tp& 2220min(const _Tp& __a, const _Tp& __b, _Compare __comp) 2221{ 2222 return __comp(__b, __a) ? __b : __a; 2223} 2224 2225template <class _Tp> 2226inline _LIBCPP_INLINE_VISIBILITY 2227const _Tp& 2228min(const _Tp& __a, const _Tp& __b) 2229{ 2230 return _STD::min(__a, __b, __less<_Tp>()); 2231} 2232 2233template<class _Tp, class _Compare> 2234inline _LIBCPP_INLINE_VISIBILITY 2235_Tp 2236min(initializer_list<_Tp> __t, _Compare __comp) 2237{ 2238 return *_STD::min_element(__t.begin(), __t.end(), __comp); 2239} 2240 2241template<class _Tp> 2242inline _LIBCPP_INLINE_VISIBILITY 2243_Tp 2244min(initializer_list<_Tp> __t) 2245{ 2246 return *_STD::min_element(__t.begin(), __t.end()); 2247} 2248 2249// max_element 2250 2251template <class _ForwardIterator, class _Compare> 2252inline _LIBCPP_INLINE_VISIBILITY 2253_ForwardIterator 2254max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) 2255{ 2256 if (__first != __last) 2257 { 2258 _ForwardIterator __i = __first; 2259 while (++__i != __last) 2260 if (__comp(*__first, *__i)) 2261 __first = __i; 2262 } 2263 return __first; 2264} 2265 2266template <class _ForwardIterator> 2267inline _LIBCPP_INLINE_VISIBILITY 2268_ForwardIterator 2269max_element(_ForwardIterator __first, _ForwardIterator __last) 2270{ 2271 return _STD::max_element(__first, __last, 2272 __less<typename iterator_traits<_ForwardIterator>::value_type>()); 2273} 2274 2275// max 2276 2277template <class _Tp, class _Compare> 2278inline _LIBCPP_INLINE_VISIBILITY 2279const _Tp& 2280max(const _Tp& __a, const _Tp& __b, _Compare __comp) 2281{ 2282 return __comp(__a, __b) ? __b : __a; 2283} 2284 2285template <class _Tp> 2286inline _LIBCPP_INLINE_VISIBILITY 2287const _Tp& 2288max(const _Tp& __a, const _Tp& __b) 2289{ 2290 return _STD::max(__a, __b, __less<_Tp>()); 2291} 2292 2293template<class _Tp, class _Compare> 2294inline _LIBCPP_INLINE_VISIBILITY 2295_Tp 2296max(initializer_list<_Tp> __t, _Compare __comp) 2297{ 2298 return *_STD::max_element(__t.begin(), __t.end(), __comp); 2299} 2300 2301template<class _Tp> 2302inline _LIBCPP_INLINE_VISIBILITY 2303_Tp 2304max(initializer_list<_Tp> __t) 2305{ 2306 return *_STD::max_element(__t.begin(), __t.end()); 2307} 2308 2309// minmax_element 2310 2311template <class _ForwardIterator, class _Compare> 2312std::pair<_ForwardIterator, _ForwardIterator> 2313minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) 2314{ 2315 std::pair<_ForwardIterator, _ForwardIterator> __result(__first, __first); 2316 if (__first != __last) 2317 { 2318 if (++__first != __last) 2319 { 2320 if (__comp(*__first, *__result.first)) 2321 { 2322 __result.second = __result.first; 2323 __result.first = __first; 2324 } 2325 else 2326 __result.second = __first; 2327 while (++__first != __last) 2328 { 2329 _ForwardIterator __i = __first; 2330 if (++__first == __last) 2331 { 2332 if (__comp(*__i, *__result.first)) 2333 __result.first = __i; 2334 else if (!__comp(*__i, *__result.second)) 2335 __result.second = __i; 2336 break; 2337 } 2338 else 2339 { 2340 if (__comp(*__first, *__i)) 2341 { 2342 if (__comp(*__first, *__result.first)) 2343 __result.first = __first; 2344 if (!__comp(*__i, *__result.second)) 2345 __result.second = __i; 2346 } 2347 else 2348 { 2349 if (__comp(*__i, *__result.first)) 2350 __result.first = __i; 2351 if (!__comp(*__first, *__result.second)) 2352 __result.second = __first; 2353 } 2354 } 2355 } 2356 } 2357 } 2358 return __result; 2359} 2360 2361template <class _ForwardIterator> 2362inline _LIBCPP_INLINE_VISIBILITY 2363std::pair<_ForwardIterator, _ForwardIterator> 2364minmax_element(_ForwardIterator __first, _ForwardIterator __last) 2365{ 2366 return _STD::minmax_element(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>()); 2367} 2368 2369// minmax 2370 2371template<class _Tp, class _Compare> 2372inline _LIBCPP_INLINE_VISIBILITY 2373pair<const _Tp&, const _Tp&> 2374minmax(const _Tp& __a, const _Tp& __b, _Compare __comp) 2375{ 2376 return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a) : 2377 pair<const _Tp&, const _Tp&>(__a, __b); 2378} 2379 2380template<class _Tp> 2381inline _LIBCPP_INLINE_VISIBILITY 2382pair<const _Tp&, const _Tp&> 2383minmax(const _Tp& __a, const _Tp& __b) 2384{ 2385 return _STD::minmax(__a, __b, __less<_Tp>()); 2386} 2387 2388template<class _Tp> 2389inline _LIBCPP_INLINE_VISIBILITY 2390pair<_Tp, _Tp> 2391minmax(initializer_list<_Tp> __t) 2392{ 2393 pair<const _Tp*, const _Tp*> __p = 2394 _STD::minmax_element(__t.begin(), __t.end()); 2395 return pair<_Tp, _Tp>(*__p.first, *__p.second); 2396} 2397 2398template<class _Tp, class _Compare> 2399inline _LIBCPP_INLINE_VISIBILITY 2400pair<_Tp, _Tp> 2401minmax(initializer_list<_Tp> __t, _Compare __comp) 2402{ 2403 pair<const _Tp*, const _Tp*> __p = 2404 _STD::minmax_element(__t.begin(), __t.end(), __comp); 2405 return pair<_Tp, _Tp>(*__p.first, *__p.second); 2406} 2407 2408// random_shuffle 2409 2410// __independent_bits_engine 2411 2412template <unsigned long long _X, size_t _R> 2413struct __log2_imp 2414{ 2415 static const size_t value = _X & ((unsigned long long)(1) << _R) ? _R 2416 : __log2_imp<_X, _R - 1>::value; 2417}; 2418 2419template <unsigned long long _X> 2420struct __log2_imp<_X, 0> 2421{ 2422 static const size_t value = 0; 2423}; 2424 2425template <size_t _R> 2426struct __log2_imp<0, _R> 2427{ 2428 static const size_t value = _R + 1; 2429}; 2430 2431template <class _UI, _UI _X> 2432struct __log2 2433{ 2434 static const size_t value = __log2_imp<_X, 2435 sizeof(_UI) * __CHAR_BIT__ - 1>::value; 2436}; 2437 2438template<class _Engine, class _UIntType> 2439class __independent_bits_engine 2440{ 2441public: 2442 // types 2443 typedef _UIntType result_type; 2444 2445private: 2446 typedef typename _Engine::result_type _Engine_result_type; 2447 typedef typename conditional 2448 < 2449 sizeof(_Engine_result_type) <= sizeof(result_type), 2450 result_type, 2451 _Engine_result_type 2452 >::type _Working_result_type; 2453 2454 _Engine& __e_; 2455 size_t __w_; 2456 size_t __w0_; 2457 size_t __n_; 2458 size_t __n0_; 2459 _Working_result_type __y0_; 2460 _Working_result_type __y1_; 2461 _Engine_result_type __mask0_; 2462 _Engine_result_type __mask1_; 2463 2464 static const _Working_result_type _R = _Engine::_Max - _Engine::_Min 2465 + _Working_result_type(1); 2466 static const size_t __m = __log2<_Working_result_type, _R>::value; 2467 static const size_t _WDt = numeric_limits<_Working_result_type>::digits; 2468 static const size_t _EDt = numeric_limits<_Engine_result_type>::digits; 2469 2470public: 2471 // constructors and seeding functions 2472 __independent_bits_engine(_Engine& __e, size_t __w); 2473 2474 // generating functions 2475 result_type operator()() {return __eval(integral_constant<bool, _R != 0>());} 2476 2477private: 2478 result_type __eval(false_type); 2479 result_type __eval(true_type); 2480}; 2481 2482template<class _Engine, class _UIntType> 2483__independent_bits_engine<_Engine, _UIntType> 2484 ::__independent_bits_engine(_Engine& __e, size_t __w) 2485 : __e_(__e), 2486 __w_(__w) 2487{ 2488 __n_ = __w_ / __m + (__w_ % __m != 0); 2489 __w0_ = __w_ / __n_; 2490 if (_R == 0) 2491 __y0_ = _R; 2492 else if (__w0_ < _WDt) 2493 __y0_ = (_R >> __w0_) << __w0_; 2494 else 2495 __y0_ = 0; 2496 if (_R - __y0_ > __y0_ / __n_) 2497 { 2498 ++__n_; 2499 __w0_ = __w_ / __n_; 2500 if (__w0_ < _WDt) 2501 __y0_ = (_R >> __w0_) << __w0_; 2502 else 2503 __y0_ = 0; 2504 } 2505 __n0_ = __n_ - __w_ % __n_; 2506 if (__w0_ < _WDt - 1) 2507 __y1_ = (_R >> (__w0_ + 1)) << (__w0_ + 1); 2508 else 2509 __y1_ = 0; 2510 __mask0_ = __w0_ > 0 ? _Engine_result_type(~0) >> (_EDt - __w0_) : 2511 _Engine_result_type(0); 2512 __mask1_ = __w0_ < _EDt - 1 ? 2513 _Engine_result_type(~0) >> (_EDt - (__w0_ + 1)) : 2514 _Engine_result_type(~0); 2515} 2516 2517template<class _Engine, class _UIntType> 2518inline 2519_UIntType 2520__independent_bits_engine<_Engine, _UIntType>::__eval(false_type) 2521{ 2522 return static_cast<result_type>(__e_() & __mask0_); 2523} 2524 2525template<class _Engine, class _UIntType> 2526_UIntType 2527__independent_bits_engine<_Engine, _UIntType>::__eval(true_type) 2528{ 2529 result_type _S = 0; 2530 for (size_t __k = 0; __k < __n0_; ++__k) 2531 { 2532 _Engine_result_type __u; 2533 do 2534 { 2535 __u = __e_() - _Engine::min(); 2536 } while (__u >= __y0_); 2537 if (__w0_ < _EDt) 2538 _S <<= __w0_; 2539 else 2540 _S = 0; 2541 _S += __u & __mask0_; 2542 } 2543 for (size_t __k = __n0_; __k < __n_; ++__k) 2544 { 2545 _Engine_result_type __u; 2546 do 2547 { 2548 __u = __e_() - _Engine::min(); 2549 } while (__u >= __y1_); 2550 if (__w0_ < _EDt - 1) 2551 _S <<= __w0_ + 1; 2552 else 2553 _S = 0; 2554 _S += __u & __mask1_; 2555 } 2556 return _S; 2557} 2558 2559// uniform_int_distribution 2560 2561template<class _IntType = int> 2562class uniform_int_distribution 2563{ 2564public: 2565 // types 2566 typedef _IntType result_type; 2567 2568 class param_type 2569 { 2570 result_type __a_; 2571 result_type __b_; 2572 public: 2573 typedef uniform_int_distribution distribution_type; 2574 2575 explicit param_type(result_type __a = 0, 2576 result_type __b = numeric_limits<result_type>::max()) 2577 : __a_(__a), __b_(__b) {} 2578 2579 result_type a() const {return __a_;} 2580 result_type b() const {return __b_;} 2581 2582 friend bool operator==(const param_type& __x, const param_type& __y) 2583 {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;} 2584 friend bool operator!=(const param_type& __x, const param_type& __y) 2585 {return !(__x == __y);} 2586 }; 2587 2588private: 2589 param_type __p_; 2590 2591public: 2592 // constructors and reset functions 2593 explicit uniform_int_distribution(result_type __a = 0, 2594 result_type __b = numeric_limits<result_type>::max()) 2595 : __p_(param_type(__a, __b)) {} 2596 explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {} 2597 void reset() {} 2598 2599 // generating functions 2600 template<class _URNG> result_type operator()(_URNG& __g) 2601 {return (*this)(__g, __p_);} 2602 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p); 2603 2604 // property functions 2605 result_type a() const {return __p_.a();} 2606 result_type b() const {return __p_.b();} 2607 2608 param_type param() const {return __p_;} 2609 void param(const param_type& __p) {__p_ = __p;} 2610 2611 result_type min() const {return a();} 2612 result_type max() const {return b();} 2613 2614 friend bool operator==(const uniform_int_distribution& __x, 2615 const uniform_int_distribution& __y) 2616 {return __x.__p_ == __y.__p_;} 2617 friend bool operator!=(const uniform_int_distribution& __x, 2618 const uniform_int_distribution& __y) 2619 {return !(__x == __y);} 2620}; 2621 2622template<class _IntType> 2623template<class _URNG> 2624typename uniform_int_distribution<_IntType>::result_type 2625uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p) 2626{ 2627 typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t), 2628 uint32_t, uint64_t>::type _UIntType; 2629 const _UIntType _R = __p.b() - __p.a() + _UIntType(1); 2630 if (_R == 1) 2631 return __p.a(); 2632 const size_t _Dt = numeric_limits<_UIntType>::digits; 2633 typedef __independent_bits_engine<_URNG, _UIntType> _Eng; 2634 if (_R == 0) 2635 return static_cast<result_type>(_Eng(__g, _Dt)()); 2636 size_t __w = _Dt - __clz(_R) - 1; 2637 if ((_R & (_UIntType(~0) >> (_Dt - __w))) != 0) 2638 ++__w; 2639 _Eng __e(__g, __w); 2640 _UIntType __u; 2641 do 2642 { 2643 __u = __e(); 2644 } while (__u >= _R); 2645 return static_cast<result_type>(__u + __p.a()); 2646} 2647 2648class __rs_default; 2649 2650__rs_default __rs_get(); 2651 2652class __rs_default 2653{ 2654 static unsigned __c_; 2655 2656 __rs_default(); 2657public: 2658 typedef unsigned result_type; 2659 2660 static const result_type _Min = 0; 2661 static const result_type _Max = 0xFFFFFFFF; 2662 2663 __rs_default(const __rs_default&); 2664 ~__rs_default(); 2665 2666 result_type operator()(); 2667 2668 static const/*expr*/ result_type min() {return _Min;} 2669 static const/*expr*/ result_type max() {return _Max;} 2670 2671 friend __rs_default __rs_get(); 2672}; 2673 2674__rs_default __rs_get(); 2675 2676template <class _RandomAccessIterator> 2677void 2678random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) 2679{ 2680 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 2681 typedef uniform_int_distribution<ptrdiff_t> _D; 2682 typedef typename _D::param_type _P; 2683 difference_type __d = __last - __first; 2684 if (__d > 1) 2685 { 2686 _D __uid; 2687 __rs_default __g = __rs_get(); 2688 for (--__last, --__d; __first < __last; ++__first, --__d) 2689 { 2690 difference_type __i = __uid(__g, _P(0, __d)); 2691 if (__i != difference_type(0)) 2692 swap(*__first, *(__first + __i)); 2693 } 2694 } 2695} 2696 2697template <class _RandomAccessIterator, class _RandomNumberGenerator> 2698void 2699random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 2700#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2701 _RandomNumberGenerator&& __rand) 2702#else 2703 _RandomNumberGenerator& __rand) 2704#endif 2705{ 2706 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 2707 difference_type __d = __last - __first; 2708 if (__d > 1) 2709 { 2710 for (--__last; __first < __last; ++__first, --__d) 2711 { 2712 difference_type __i = __rand(__d); 2713 swap(*__first, *(__first + __i)); 2714 } 2715 } 2716} 2717 2718template<class _RandomAccessIterator, class _UniformRandomNumberGenerator> 2719 void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 2720 _UniformRandomNumberGenerator& __g) 2721{ 2722 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 2723 typedef uniform_int_distribution<ptrdiff_t> _D; 2724 typedef typename _D::param_type _P; 2725 difference_type __d = __last - __first; 2726 if (__d > 1) 2727 { 2728 _D __uid; 2729 for (--__last, --__d; __first < __last; ++__first, --__d) 2730 { 2731 difference_type __i = __uid(__g, _P(0, __d)); 2732 if (__i != difference_type(0)) 2733 swap(*__first, *(__first + __i)); 2734 } 2735 } 2736} 2737 2738template <class _InputIterator, class _Predicate> 2739bool 2740is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred) 2741{ 2742 for (; __first != __last; ++__first) 2743 if (!__pred(*__first)) 2744 break; 2745 for (; __first != __last; ++__first) 2746 if (__pred(*__first)) 2747 return false; 2748 return true; 2749} 2750 2751// partition 2752 2753template <class _Predicate, class _ForwardIterator> 2754_ForwardIterator 2755__partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag) 2756{ 2757 while (true) 2758 { 2759 if (__first == __last) 2760 return __first; 2761 if (!__pred(*__first)) 2762 break; 2763 ++__first; 2764 } 2765 for (_ForwardIterator __p = __first; ++__p != __last;) 2766 { 2767 if (__pred(*__p)) 2768 { 2769 swap(*__first, *__p); 2770 ++__first; 2771 } 2772 } 2773 return __first; 2774} 2775 2776template <class _Predicate, class _BidirectionalIterator> 2777_BidirectionalIterator 2778__partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, 2779 bidirectional_iterator_tag) 2780{ 2781 while (true) 2782 { 2783 while (true) 2784 { 2785 if (__first == __last) 2786 return __first; 2787 if (!__pred(*__first)) 2788 break; 2789 ++__first; 2790 } 2791 do 2792 { 2793 if (__first == --__last) 2794 return __first; 2795 } while (!__pred(*__last)); 2796 swap(*__first, *__last); 2797 ++__first; 2798 } 2799} 2800 2801template <class _ForwardIterator, class _Predicate> 2802inline _LIBCPP_INLINE_VISIBILITY 2803_ForwardIterator 2804partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) 2805{ 2806 return _STD::__partition<typename add_lvalue_reference<_Predicate>::type> 2807 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category()); 2808} 2809 2810// partition_copy 2811 2812template <class _InputIterator, class _OutputIterator1, 2813 class _OutputIterator2, class _Predicate> 2814pair<_OutputIterator1, _OutputIterator2> 2815partition_copy(_InputIterator __first, _InputIterator __last, 2816 _OutputIterator1 __out_true, _OutputIterator2 __out_false, 2817 _Predicate __pred) 2818{ 2819 for (; __first != __last; ++__first) 2820 { 2821 if (__pred(*__first)) 2822 { 2823 *__out_true = *__first; 2824 ++__out_true; 2825 } 2826 else 2827 { 2828 *__out_false = *__first; 2829 ++__out_false; 2830 } 2831 } 2832 return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false); 2833} 2834 2835// partition_point 2836 2837template<class _ForwardIterator, class _Predicate> 2838_ForwardIterator 2839partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) 2840{ 2841 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 2842 difference_type __len = _STD::distance(__first, __last); 2843 while (__len != 0) 2844 { 2845 difference_type __l2 = __len / 2; 2846 _ForwardIterator __m = __first; 2847 _STD::advance(__m, __l2); 2848 if (__pred(*__m)) 2849 { 2850 __first = ++__m; 2851 __len -= __l2 + 1; 2852 } 2853 else 2854 __len = __l2; 2855 } 2856 return __first; 2857} 2858 2859// stable_partition 2860 2861template <class _Predicate, class _ForwardIterator, class _Distance, class _Pair> 2862_ForwardIterator 2863__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, 2864 _Distance __len, _Pair __p, forward_iterator_tag __fit) 2865{ 2866 // *__first is known to be false 2867 // __len >= 1 2868 if (__len == 1) 2869 return __first; 2870 if (__len == 2) 2871 { 2872 _ForwardIterator __m = __first; 2873 if (__pred(*++__m)) 2874 { 2875 swap(*__first, *__m); 2876 return __m; 2877 } 2878 return __first; 2879 } 2880 if (__len <= __p.second) 2881 { // The buffer is big enough to use 2882 typedef typename iterator_traits<_ForwardIterator>::value_type value_type; 2883 __destruct_n __d(0); 2884 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d); 2885 // Move the falses into the temporary buffer, and the trues to the front of the line 2886 // Update __first to always point to the end of the trues 2887 value_type* __t = __p.first; 2888 ::new(__t) value_type(_STD::move(*__first)); 2889 __d.__incr((value_type*)0); 2890 ++__t; 2891 _ForwardIterator __i = __first; 2892 while (++__i != __last) 2893 { 2894 if (__pred(*__i)) 2895 { 2896 *__first = _STD::move(*__i); 2897 ++__first; 2898 } 2899 else 2900 { 2901 ::new(__t) value_type(_STD::move(*__i)); 2902 __d.__incr((value_type*)0); 2903 ++__t; 2904 } 2905 } 2906 // All trues now at start of range, all falses in buffer 2907 // Move falses back into range, but don't mess up __first which points to first false 2908 __i = __first; 2909 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i) 2910 *__i = _STD::move(*__t2); 2911 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer 2912 return __first; 2913 } 2914 // Else not enough buffer, do in place 2915 // __len >= 3 2916 _ForwardIterator __m = __first; 2917 _Distance __len2 = __len / 2; // __len2 >= 2 2918 _STD::advance(__m, __len2); 2919 // recurse on [__first, __m), *__first know to be false 2920 // F????????????????? 2921 // f m l 2922 typedef typename add_lvalue_reference<_Predicate>::type _PredRef; 2923 _ForwardIterator __first_false = __stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit); 2924 // TTTFFFFF?????????? 2925 // f ff m l 2926 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true 2927 _ForwardIterator __m1 = __m; 2928 _ForwardIterator __second_false = __last; 2929 _Distance __len_half = __len - __len2; 2930 while (__pred(*__m1)) 2931 { 2932 if (++__m1 == __last) 2933 goto __second_half_done; 2934 --__len_half; 2935 } 2936 // TTTFFFFFTTTF?????? 2937 // f ff m m1 l 2938 __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit); 2939__second_half_done: 2940 // TTTFFFFFTTTTTFFFFF 2941 // f ff m sf l 2942 return _STD::rotate(__first_false, __m, __second_false); 2943 // TTTTTTTTFFFFFFFFFF 2944 // | 2945} 2946 2947struct __return_temporary_buffer 2948{ 2949 template <class _Tp> 2950 _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) const {_STD::return_temporary_buffer(__p);} 2951}; 2952 2953template <class _Predicate, class _ForwardIterator> 2954_ForwardIterator 2955__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, 2956 forward_iterator_tag) 2957{ 2958 const unsigned __alloc_limit = 3; // might want to make this a function of trivial assignment 2959 // Either prove all true and return __first or point to first false 2960 while (true) 2961 { 2962 if (__first == __last) 2963 return __first; 2964 if (!__pred(*__first)) 2965 break; 2966 ++__first; 2967 } 2968 // We now have a reduced range [__first, __last) 2969 // *__first is known to be false 2970 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 2971 typedef typename iterator_traits<_ForwardIterator>::value_type value_type; 2972 difference_type __len = _STD::distance(__first, __last); 2973 pair<value_type*, ptrdiff_t> __p(0, 0); 2974 unique_ptr<value_type, __return_temporary_buffer> __h; 2975 if (__len >= __alloc_limit) 2976 { 2977 __p = _STD::get_temporary_buffer<value_type>(__len); 2978 __h.reset(__p.first); 2979 } 2980 return __stable_partition<typename add_lvalue_reference<_Predicate>::type> 2981 (__first, __last, __pred, __len, __p, forward_iterator_tag()); 2982} 2983 2984template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair> 2985_BidirectionalIterator 2986__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, 2987 _Distance __len, _Pair __p, bidirectional_iterator_tag __bit) 2988{ 2989 // *__first is known to be false 2990 // *__last is known to be true 2991 // __len >= 2 2992 if (__len == 2) 2993 { 2994 swap(*__first, *__last); 2995 return __last; 2996 } 2997 if (__len == 3) 2998 { 2999 _BidirectionalIterator __m = __first; 3000 if (__pred(*++__m)) 3001 { 3002 swap(*__first, *__m); 3003 swap(*__m, *__last); 3004 return __last; 3005 } 3006 swap(*__m, *__last); 3007 swap(*__first, *__m); 3008 return __m; 3009 } 3010 if (__len <= __p.second) 3011 { // The buffer is big enough to use 3012 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 3013 __destruct_n __d(0); 3014 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d); 3015 // Move the falses into the temporary buffer, and the trues to the front of the line 3016 // Update __first to always point to the end of the trues 3017 value_type* __t = __p.first; 3018 ::new(__t) value_type(_STD::move(*__first)); 3019 __d.__incr((value_type*)0); 3020 ++__t; 3021 _BidirectionalIterator __i = __first; 3022 while (++__i != __last) 3023 { 3024 if (__pred(*__i)) 3025 { 3026 *__first = _STD::move(*__i); 3027 ++__first; 3028 } 3029 else 3030 { 3031 ::new(__t) value_type(_STD::move(*__i)); 3032 __d.__incr((value_type*)0); 3033 ++__t; 3034 } 3035 } 3036 // move *__last, known to be true 3037 *__first = _STD::move(*__i); 3038 __i = ++__first; 3039 // All trues now at start of range, all falses in buffer 3040 // Move falses back into range, but don't mess up __first which points to first false 3041 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i) 3042 *__i = _STD::move(*__t2); 3043 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer 3044 return __first; 3045 } 3046 // Else not enough buffer, do in place 3047 // __len >= 4 3048 _BidirectionalIterator __m = __first; 3049 _Distance __len2 = __len / 2; // __len2 >= 2 3050 _STD::advance(__m, __len2); 3051 // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false 3052 // F????????????????T 3053 // f m l 3054 _BidirectionalIterator __m1 = __m; 3055 _BidirectionalIterator __first_false = __first; 3056 _Distance __len_half = __len2; 3057 while (!__pred(*--__m1)) 3058 { 3059 if (__m1 == __first) 3060 goto __first_half_done; 3061 --__len_half; 3062 } 3063 // F???TFFF?????????T 3064 // f m1 m l 3065 typedef typename add_lvalue_reference<_Predicate>::type _PredRef; 3066 __first_false = __stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit); 3067__first_half_done: 3068 // TTTFFFFF?????????T 3069 // f ff m l 3070 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true 3071 __m1 = __m; 3072 _BidirectionalIterator __second_false = __last; 3073 ++__second_false; 3074 __len_half = __len - __len2; 3075 while (__pred(*__m1)) 3076 { 3077 if (++__m1 == __last) 3078 goto __second_half_done; 3079 --__len_half; 3080 } 3081 // TTTFFFFFTTTF?????T 3082 // f ff m m1 l 3083 __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit); 3084__second_half_done: 3085 // TTTFFFFFTTTTTFFFFF 3086 // f ff m sf l 3087 return _STD::rotate(__first_false, __m, __second_false); 3088 // TTTTTTTTFFFFFFFFFF 3089 // | 3090} 3091 3092template <class _Predicate, class _BidirectionalIterator> 3093_BidirectionalIterator 3094__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, 3095 bidirectional_iterator_tag) 3096{ 3097 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; 3098 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 3099 const difference_type __alloc_limit = 4; // might want to make this a function of trivial assignment 3100 // Either prove all true and return __first or point to first false 3101 while (true) 3102 { 3103 if (__first == __last) 3104 return __first; 3105 if (!__pred(*__first)) 3106 break; 3107 ++__first; 3108 } 3109 // __first points to first false, everything prior to __first is already set. 3110 // Either prove [__first, __last) is all false and return __first, or point __last to last true 3111 do 3112 { 3113 if (__first == --__last) 3114 return __first; 3115 } while (!__pred(*__last)); 3116 // We now have a reduced range [__first, __last] 3117 // *__first is known to be false 3118 // *__last is known to be true 3119 // __len >= 2 3120 difference_type __len = _STD::distance(__first, __last) + 1; 3121 pair<value_type*, ptrdiff_t> __p(0, 0); 3122 unique_ptr<value_type, __return_temporary_buffer> __h; 3123 if (__len >= __alloc_limit) 3124 { 3125 __p = _STD::get_temporary_buffer<value_type>(__len); 3126 __h.reset(__p.first); 3127 } 3128 return __stable_partition<typename add_lvalue_reference<_Predicate>::type> 3129 (__first, __last, __pred, __len, __p, bidirectional_iterator_tag()); 3130} 3131 3132template <class _ForwardIterator, class _Predicate> 3133inline _LIBCPP_INLINE_VISIBILITY 3134_ForwardIterator 3135stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) 3136{ 3137 return __stable_partition<typename add_lvalue_reference<_Predicate>::type> 3138 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category()); 3139} 3140 3141// is_sorted_until 3142 3143template <class _ForwardIterator, class _Compare> 3144_ForwardIterator 3145is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) 3146{ 3147 if (__first != __last) 3148 { 3149 _ForwardIterator __i = __first; 3150 while (++__i != __last) 3151 { 3152 if (__comp(*__i, *__first)) 3153 return __i; 3154 __first = __i; 3155 } 3156 } 3157 return __last; 3158} 3159 3160template<class _ForwardIterator> 3161inline _LIBCPP_INLINE_VISIBILITY 3162_ForwardIterator 3163is_sorted_until(_ForwardIterator __first, _ForwardIterator __last) 3164{ 3165 return _STD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>()); 3166} 3167 3168// is_sorted 3169 3170template <class _ForwardIterator, class _Compare> 3171inline _LIBCPP_INLINE_VISIBILITY 3172bool 3173is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) 3174{ 3175 return _STD::is_sorted_until(__first, __last, __comp) == __last; 3176} 3177 3178template<class _ForwardIterator> 3179inline _LIBCPP_INLINE_VISIBILITY 3180bool 3181is_sorted(_ForwardIterator __first, _ForwardIterator __last) 3182{ 3183 return _STD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>()); 3184} 3185 3186// sort 3187 3188// stable, 2-3 compares, 0-2 swaps 3189 3190template <class _Compare, class _ForwardIterator> 3191unsigned 3192__sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c) 3193{ 3194 unsigned __r = 0; 3195 if (!__c(*__y, *__x)) // if x <= y 3196 { 3197 if (!__c(*__z, *__y)) // if y <= z 3198 return __r; // x <= y && y <= z 3199 // x <= y && y > z 3200 swap(*__y, *__z); // x <= z && y < z 3201 __r = 1; 3202 if (__c(*__y, *__x)) // if x > y 3203 { 3204 swap(*__x, *__y); // x < y && y <= z 3205 __r = 2; 3206 } 3207 return __r; // x <= y && y < z 3208 } 3209 if (__c(*__z, *__y)) // x > y, if y > z 3210 { 3211 swap(*__x, *__z); // x < y && y < z 3212 __r = 1; 3213 return __r; 3214 } 3215 swap(*__x, *__y); // x > y && y <= z 3216 __r = 1; // x < y && x <= z 3217 if (__c(*__z, *__y)) // if y > z 3218 { 3219 swap(*__y, *__z); // x <= y && y < z 3220 __r = 2; 3221 } 3222 return __r; 3223} // x <= y && y <= z 3224 3225// stable, 3-6 compares, 0-5 swaps 3226 3227template <class _Compare, class _ForwardIterator> 3228unsigned 3229__sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, 3230 _ForwardIterator __x4, _Compare __c) 3231{ 3232 unsigned __r = __sort3<_Compare>(__x1, __x2, __x3, __c); 3233 if (__c(*__x4, *__x3)) 3234 { 3235 swap(*__x3, *__x4); 3236 ++__r; 3237 if (__c(*__x3, *__x2)) 3238 { 3239 swap(*__x2, *__x3); 3240 ++__r; 3241 if (__c(*__x2, *__x1)) 3242 { 3243 swap(*__x1, *__x2); 3244 ++__r; 3245 } 3246 } 3247 } 3248 return __r; 3249} 3250 3251// stable, 4-10 compares, 0-9 swaps 3252 3253template <class _Compare, class _ForwardIterator> 3254unsigned 3255__sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, 3256 _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c) 3257{ 3258 unsigned __r = __sort4<_Compare>(__x1, __x2, __x3, __x4, __c); 3259 if (__c(*__x5, *__x4)) 3260 { 3261 swap(*__x4, *__x5); 3262 ++__r; 3263 if (__c(*__x4, *__x3)) 3264 { 3265 swap(*__x3, *__x4); 3266 ++__r; 3267 if (__c(*__x3, *__x2)) 3268 { 3269 swap(*__x2, *__x3); 3270 ++__r; 3271 if (__c(*__x2, *__x1)) 3272 { 3273 swap(*__x1, *__x2); 3274 ++__r; 3275 } 3276 } 3277 } 3278 } 3279 return __r; 3280} 3281 3282// Assumes size > 0 3283template <class _Compare, class _BirdirectionalIterator> 3284void 3285__selection_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp) 3286{ 3287 _BirdirectionalIterator __lm1 = __last; 3288 for (--__lm1; __first != __lm1; ++__first) 3289 { 3290 _BirdirectionalIterator __i = _STD::min_element<_BirdirectionalIterator, 3291 typename add_lvalue_reference<_Compare>::type> 3292 (__first, __last, __comp); 3293 if (__i != __first) 3294 swap(*__first, *__i); 3295 } 3296} 3297 3298template <class _Compare, class _BirdirectionalIterator> 3299void 3300__insertion_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp) 3301{ 3302 typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type; 3303 if (__first != __last) 3304 { 3305 _BirdirectionalIterator __i = __first; 3306 for (++__i; __i != __last; ++__i) 3307 { 3308 _BirdirectionalIterator __j = __i; 3309 value_type __t(_STD::move(*__j)); 3310 for (_BirdirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j) 3311 *__j = _STD::move(*__k); 3312 *__j = _STD::move(__t); 3313 } 3314 } 3315} 3316 3317template <class _Compare, class _RandomAccessIterator> 3318void 3319__insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 3320{ 3321 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 3322 _RandomAccessIterator __j = __first+2; 3323 __sort3<_Compare>(__first, __first+1, __j, __comp); 3324 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i) 3325 { 3326 if (__comp(*__i, *__j)) 3327 { 3328 value_type __t(_STD::move(*__i)); 3329 _RandomAccessIterator __k = __j; 3330 __j = __i; 3331 do 3332 { 3333 *__j = _STD::move(*__k); 3334 __j = __k; 3335 } while (__j != __first && __comp(__t, *--__k)); 3336 *__j = _STD::move(__t); 3337 } 3338 __j = __i; 3339 } 3340} 3341 3342template <class _Compare, class _RandomAccessIterator> 3343bool 3344__insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 3345{ 3346 switch (__last - __first) 3347 { 3348 case 0: 3349 case 1: 3350 return true; 3351 case 2: 3352 if (__comp(*--__last, *__first)) 3353 swap(*__first, *__last); 3354 return true; 3355 case 3: 3356 _STD::__sort3<_Compare>(__first, __first+1, --__last, __comp); 3357 return true; 3358 case 4: 3359 _STD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp); 3360 return true; 3361 case 5: 3362 _STD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp); 3363 return true; 3364 } 3365 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 3366 _RandomAccessIterator __j = __first+2; 3367 __sort3<_Compare>(__first, __first+1, __j, __comp); 3368 const unsigned __limit = 8; 3369 unsigned __count = 0; 3370 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i) 3371 { 3372 if (__comp(*__i, *__j)) 3373 { 3374 value_type __t(_STD::move(*__i)); 3375 _RandomAccessIterator __k = __j; 3376 __j = __i; 3377 do 3378 { 3379 *__j = _STD::move(*__k); 3380 __j = __k; 3381 } while (__j != __first && __comp(__t, *--__k)); 3382 *__j = _STD::move(__t); 3383 if (++__count == __limit) 3384 return ++__i == __last; 3385 } 3386 __j = __i; 3387 } 3388 return true; 3389} 3390 3391template <class _Compare, class _BirdirectionalIterator> 3392void 3393__insertion_sort_move(_BirdirectionalIterator __first1, _BirdirectionalIterator __last1, 3394 typename iterator_traits<_BirdirectionalIterator>::value_type* __first2, _Compare __comp) 3395{ 3396 typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type; 3397 if (__first1 != __last1) 3398 { 3399 __destruct_n __d(0); 3400 unique_ptr<value_type, __destruct_n&> __h(__first2, __d); 3401 value_type* __last2 = __first2; 3402 ::new(__last2) value_type(_STD::move(*__first1)); 3403 __d.__incr((value_type*)0); 3404 for (++__last2; ++__first1 != __last1; ++__last2) 3405 { 3406 value_type* __j2 = __last2; 3407 value_type* __i2 = __j2; 3408 if (__comp(*__first1, *--__i2)) 3409 { 3410 ::new(__j2) value_type(_STD::move(*__i2)); 3411 __d.__incr((value_type*)0); 3412 for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2) 3413 *__j2 = _STD::move(*__i2); 3414 *__j2 = _STD::move(*__first1); 3415 } 3416 else 3417 { 3418 ::new(__j2) value_type(_STD::move(*__first1)); 3419 __d.__incr((value_type*)0); 3420 } 3421 } 3422 __h.release(); 3423 } 3424} 3425 3426template <class _Compare, class _RandomAccessIterator> 3427void 3428__sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 3429{ 3430 // _Compare is known to be a reference type 3431 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 3432 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 3433 const difference_type __limit = has_trivial_copy_constructor<value_type>::value && 3434 has_trivial_copy_assign<value_type>::value ? 30 : 6; 3435 while (true) 3436 { 3437 __restart: 3438 difference_type __len = __last - __first; 3439 switch (__len) 3440 { 3441 case 0: 3442 case 1: 3443 return; 3444 case 2: 3445 if (__comp(*--__last, *__first)) 3446 swap(*__first, *__last); 3447 return; 3448 case 3: 3449 _STD::__sort3<_Compare>(__first, __first+1, --__last, __comp); 3450 return; 3451 case 4: 3452 _STD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp); 3453 return; 3454 case 5: 3455 _STD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp); 3456 return; 3457 } 3458 if (__len <= __limit) 3459 { 3460 _STD::__insertion_sort_3<_Compare>(__first, __last, __comp); 3461 return; 3462 } 3463 // __len > 5 3464 _RandomAccessIterator __m = __first; 3465 _RandomAccessIterator __lm1 = __last; 3466 --__lm1; 3467 unsigned __n_swaps; 3468 { 3469 difference_type __delta; 3470 if (__len >= 1000) 3471 { 3472 __delta = __len/2; 3473 __m += __delta; 3474 __delta /= 2; 3475 __n_swaps = _STD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp); 3476 } 3477 else 3478 { 3479 __delta = __len/2; 3480 __m += __delta; 3481 __n_swaps = _STD::__sort3<_Compare>(__first, __m, __lm1, __comp); 3482 } 3483 } 3484 // *__m is median 3485 // partition [__first, __m) < *__m and *__m <= [__m, __last) 3486 // (this inhibits tossing elements equivalent to __m around unnecessarily) 3487 _RandomAccessIterator __i = __first; 3488 _RandomAccessIterator __j = __lm1; 3489 // j points beyond range to be tested, *__m is known to be <= *__lm1 3490 // The search going up is known to be guarded but the search coming down isn't. 3491 // Prime the downward search with a guard. 3492 if (!__comp(*__i, *__m)) // if *__first == *__m 3493 { 3494 // *__first == *__m, *__first doesn't go in first part 3495 // manually guard downward moving __j against __i 3496 while (true) 3497 { 3498 if (__i == --__j) 3499 { 3500 // *__first == *__m, *__m <= all other elements 3501 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last) 3502 ++__i; // __first + 1 3503 __j = __last; 3504 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1) 3505 { 3506 while (true) 3507 { 3508 if (__i == __j) 3509 return; // [__first, __last) all equivalent elements 3510 if (__comp(*__first, *__i)) 3511 { 3512 swap(*__i, *__j); 3513 ++__n_swaps; 3514 ++__i; 3515 break; 3516 } 3517 ++__i; 3518 } 3519 } 3520 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1 3521 if (__i == __j) 3522 return; 3523 while (true) 3524 { 3525 while (!__comp(*__first, *__i)) 3526 ++__i; 3527 while (__comp(*__first, *--__j)) 3528 ; 3529 if (__i >= __j) 3530 break; 3531 swap(*__i, *__j); 3532 ++__n_swaps; 3533 ++__i; 3534 } 3535 // [__first, __i) == *__first and *__first < [__i, __last) 3536 // The first part is sorted, sort the secod part 3537 // _STD::__sort<_Compare>(__i, __last, __comp); 3538 __first = __i; 3539 goto __restart; 3540 } 3541 if (__comp(*__j, *__m)) 3542 { 3543 swap(*__i, *__j); 3544 ++__n_swaps; 3545 break; // found guard for downward moving __j, now use unguarded partition 3546 } 3547 } 3548 } 3549 // It is known that *__i < *__m 3550 ++__i; 3551 // j points beyond range to be tested, *__m is known to be <= *__lm1 3552 // if not yet partitioned... 3553 if (__i < __j) 3554 { 3555 // known that *(__i - 1) < *__m 3556 // known that __i <= __m 3557 while (true) 3558 { 3559 // __m still guards upward moving __i 3560 while (__comp(*__i, *__m)) 3561 ++__i; 3562 // It is now known that a guard exists for downward moving __j 3563 while (!__comp(*--__j, *__m)) 3564 ; 3565 if (__i > __j) 3566 break; 3567 swap(*__i, *__j); 3568 ++__n_swaps; 3569 // It is known that __m != __j 3570 // If __m just moved, follow it 3571 if (__m == __i) 3572 __m = __j; 3573 ++__i; 3574 } 3575 } 3576 // [__first, __i) < *__m and *__m <= [__i, __last) 3577 if (__i != __m && __comp(*__m, *__i)) 3578 { 3579 swap(*__i, *__m); 3580 ++__n_swaps; 3581 } 3582 // [__first, __i) < *__i and *__i <= [__i+1, __last) 3583 // If we were given a perfect partition, see if insertion sort is quick... 3584 if (__n_swaps == 0) 3585 { 3586 bool __fs = _STD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp); 3587 if (_STD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp)) 3588 { 3589 if (__fs) 3590 return; 3591 __last = __i; 3592 continue; 3593 } 3594 else 3595 { 3596 if (__fs) 3597 { 3598 __first = ++__i; 3599 continue; 3600 } 3601 } 3602 } 3603 // sort smaller range with recursive call and larger with tail recursion elimination 3604 if (__i - __first < __last - __i) 3605 { 3606 _STD::__sort<_Compare>(__first, __i, __comp); 3607 // _STD::__sort<_Compare>(__i+1, __last, __comp); 3608 __first = ++__i; 3609 } 3610 else 3611 { 3612 _STD::__sort<_Compare>(__i+1, __last, __comp); 3613 // _STD::__sort<_Compare>(__first, __i, __comp); 3614 __last = __i; 3615 } 3616 } 3617} 3618 3619// This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare 3620template <class _RandomAccessIterator, class _Compare> 3621inline _LIBCPP_INLINE_VISIBILITY 3622void 3623sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 3624{ 3625#ifdef _LIBCPP_DEBUG 3626 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 3627 __debug_less<_Compare> __c(__comp); 3628 __sort<_Comp_ref>(__first, __last, __c); 3629#else // _LIBCPP_DEBUG 3630 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 3631 __sort<_Comp_ref>(__first, __last, __comp); 3632#endif // _LIBCPP_DEBUG 3633} 3634 3635template <class _RandomAccessIterator> 3636inline _LIBCPP_INLINE_VISIBILITY 3637void 3638sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 3639{ 3640 _STD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 3641} 3642 3643template <class _Tp> 3644inline _LIBCPP_INLINE_VISIBILITY 3645void 3646sort(_Tp** __first, _Tp** __last) 3647{ 3648 _STD::sort((size_t*)__first, (size_t*)__last, __less<size_t>()); 3649} 3650 3651template <class _Tp> 3652inline _LIBCPP_INLINE_VISIBILITY 3653void 3654sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last) 3655{ 3656 _STD::sort(__first.base(), __last.base()); 3657} 3658 3659extern template void __sort<__less<char>&, char*>(char*, char*, __less<char>&); 3660extern template void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&); 3661extern template void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&); 3662extern template void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&); 3663extern template void __sort<__less<short>&, short*>(short*, short*, __less<short>&); 3664extern template void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&); 3665extern template void __sort<__less<int>&, int*>(int*, int*, __less<int>&); 3666extern template void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&); 3667extern template void __sort<__less<long>&, long*>(long*, long*, __less<long>&); 3668extern template void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&); 3669extern template void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&); 3670extern template void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&); 3671extern template void __sort<__less<float>&, float*>(float*, float*, __less<float>&); 3672extern template void __sort<__less<double>&, double*>(double*, double*, __less<double>&); 3673extern template void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&); 3674 3675extern template bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&); 3676extern template bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&); 3677extern template bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&); 3678extern template bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&); 3679extern template bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&); 3680extern template bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&); 3681extern template bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&); 3682extern template bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&); 3683extern template bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&); 3684extern template bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&); 3685extern template bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&); 3686extern template bool __insertion_sort_incomplete<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&); 3687extern template bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&); 3688extern template bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&); 3689extern template bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&); 3690 3691extern template unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&); 3692 3693// lower_bound 3694 3695template <class _Compare, class _ForwardIterator, class _Tp> 3696_ForwardIterator 3697__lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp) 3698{ 3699 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 3700 difference_type __len = _STD::distance(__first, __last); 3701 while (__len != 0) 3702 { 3703 difference_type __l2 = __len / 2; 3704 _ForwardIterator __m = __first; 3705 _STD::advance(__m, __l2); 3706 if (__comp(*__m, __value)) 3707 { 3708 __first = ++__m; 3709 __len -= __l2 + 1; 3710 } 3711 else 3712 __len = __l2; 3713 } 3714 return __first; 3715} 3716 3717template <class _ForwardIterator, class _Tp, class _Compare> 3718inline _LIBCPP_INLINE_VISIBILITY 3719_ForwardIterator 3720lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp) 3721{ 3722#ifdef _LIBCPP_DEBUG 3723 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 3724 __debug_less<_Compare> __c(__comp); 3725 return __lower_bound<_Comp_ref>(__first, __last, __value, __c); 3726#else // _LIBCPP_DEBUG 3727 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 3728 return __lower_bound<_Comp_ref>(__first, __last, __value, __comp); 3729#endif // _LIBCPP_DEBUG 3730} 3731 3732template <class _ForwardIterator, class _Tp> 3733inline _LIBCPP_INLINE_VISIBILITY 3734_ForwardIterator 3735lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) 3736{ 3737 return _STD::lower_bound(__first, __last, __value, 3738 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); 3739} 3740 3741// upper_bound 3742 3743template <class _Compare, class _ForwardIterator, class _Tp> 3744_ForwardIterator 3745__upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp) 3746{ 3747 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 3748 difference_type __len = _STD::distance(__first, __last); 3749 while (__len != 0) 3750 { 3751 difference_type __l2 = __len / 2; 3752 _ForwardIterator __m = __first; 3753 _STD::advance(__m, __l2); 3754 if (__comp(__value, *__m)) 3755 __len = __l2; 3756 else 3757 { 3758 __first = ++__m; 3759 __len -= __l2 + 1; 3760 } 3761 } 3762 return __first; 3763} 3764 3765template <class _ForwardIterator, class _Tp, class _Compare> 3766inline _LIBCPP_INLINE_VISIBILITY 3767_ForwardIterator 3768upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp) 3769{ 3770#ifdef _LIBCPP_DEBUG 3771 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 3772 __debug_less<_Compare> __c(__comp); 3773 return __upper_bound<_Comp_ref>(__first, __last, __value, __c); 3774#else // _LIBCPP_DEBUG 3775 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 3776 return __upper_bound<_Comp_ref>(__first, __last, __value, __comp); 3777#endif // _LIBCPP_DEBUG 3778} 3779 3780template <class _ForwardIterator, class _Tp> 3781inline _LIBCPP_INLINE_VISIBILITY 3782_ForwardIterator 3783upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) 3784{ 3785 return _STD::upper_bound(__first, __last, __value, 3786 __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>()); 3787} 3788 3789// equal_range 3790 3791template <class _Compare, class _ForwardIterator, class _Tp> 3792pair<_ForwardIterator, _ForwardIterator> 3793__equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp) 3794{ 3795 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 3796 difference_type __len = _STD::distance(__first, __last); 3797 while (__len != 0) 3798 { 3799 difference_type __l2 = __len / 2; 3800 _ForwardIterator __m = __first; 3801 _STD::advance(__m, __l2); 3802 if (__comp(*__m, __value)) 3803 { 3804 __first = ++__m; 3805 __len -= __l2 + 1; 3806 } 3807 else if (__comp(__value, *__m)) 3808 { 3809 __last = __m; 3810 __len = __l2; 3811 } 3812 else 3813 { 3814 _ForwardIterator __mp1 = __m; 3815 return pair<_ForwardIterator, _ForwardIterator> 3816 ( 3817 __lower_bound<_Compare>(__first, __m, __value, __comp), 3818 __upper_bound<_Compare>(++__mp1, __last, __value, __comp) 3819 ); 3820 } 3821 } 3822 return pair<_ForwardIterator, _ForwardIterator>(__first, __first); 3823} 3824 3825template <class _ForwardIterator, class _Tp, class _Compare> 3826inline _LIBCPP_INLINE_VISIBILITY 3827pair<_ForwardIterator, _ForwardIterator> 3828equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp) 3829{ 3830#ifdef _LIBCPP_DEBUG 3831 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 3832 __debug_less<_Compare> __c(__comp); 3833 return __equal_range<_Comp_ref>(__first, __last, __value, __c); 3834#else // _LIBCPP_DEBUG 3835 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 3836 return __equal_range<_Comp_ref>(__first, __last, __value, __comp); 3837#endif // _LIBCPP_DEBUG 3838} 3839 3840template <class _ForwardIterator, class _Tp> 3841inline _LIBCPP_INLINE_VISIBILITY 3842pair<_ForwardIterator, _ForwardIterator> 3843equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) 3844{ 3845 return _STD::equal_range(__first, __last, __value, 3846 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); 3847} 3848 3849// binary_search 3850 3851template <class _Compare, class _ForwardIterator, class _Tp> 3852inline _LIBCPP_INLINE_VISIBILITY 3853bool 3854__binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp) 3855{ 3856 __first = __lower_bound<_Compare>(__first, __last, __value, __comp); 3857 return __first != __last && !__comp(__value, *__first); 3858} 3859 3860template <class _ForwardIterator, class _Tp, class _Compare> 3861inline _LIBCPP_INLINE_VISIBILITY 3862bool 3863binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp) 3864{ 3865#ifdef _LIBCPP_DEBUG 3866 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 3867 __debug_less<_Compare> __c(__comp); 3868 return __binary_search<_Comp_ref>(__first, __last, __value, __c); 3869#else // _LIBCPP_DEBUG 3870 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 3871 return __binary_search<_Comp_ref>(__first, __last, __value, __comp); 3872#endif // _LIBCPP_DEBUG 3873} 3874 3875template <class _ForwardIterator, class _Tp> 3876inline _LIBCPP_INLINE_VISIBILITY 3877bool 3878binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) 3879{ 3880 return _STD::binary_search(__first, __last, __value, 3881 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); 3882} 3883 3884// merge 3885 3886template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 3887_OutputIterator 3888__merge(_InputIterator1 __first1, _InputIterator1 __last1, 3889 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 3890{ 3891 for (; __first1 != __last1; ++__result) 3892 { 3893 if (__first2 == __last2) 3894 return _STD::copy(__first1, __last1, __result); 3895 if (__comp(*__first2, *__first1)) 3896 { 3897 *__result = *__first2; 3898 ++__first2; 3899 } 3900 else 3901 { 3902 *__result = *__first1; 3903 ++__first1; 3904 } 3905 } 3906 return _STD::copy(__first2, __last2, __result); 3907} 3908 3909template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 3910inline _LIBCPP_INLINE_VISIBILITY 3911_OutputIterator 3912merge(_InputIterator1 __first1, _InputIterator1 __last1, 3913 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 3914{ 3915#ifdef _LIBCPP_DEBUG 3916 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 3917 __debug_less<_Compare> __c(__comp); 3918 return _STD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c); 3919#else // _LIBCPP_DEBUG 3920 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 3921 return _STD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 3922#endif // _LIBCPP_DEBUG 3923} 3924 3925template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 3926inline _LIBCPP_INLINE_VISIBILITY 3927_OutputIterator 3928merge(_InputIterator1 __first1, _InputIterator1 __last1, 3929 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 3930{ 3931 typedef typename iterator_traits<_InputIterator1>::value_type __v1; 3932 typedef typename iterator_traits<_InputIterator2>::value_type __v2; 3933 return merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>()); 3934} 3935 3936// inplace_merge 3937 3938template <class _Compare, class _BidirectionalIterator> 3939void 3940__buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, 3941 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1, 3942 typename iterator_traits<_BidirectionalIterator>::difference_type __len2, 3943 typename iterator_traits<_BidirectionalIterator>::value_type* __buff) 3944{ 3945 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 3946 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; 3947 typedef typename iterator_traits<_BidirectionalIterator>::pointer pointer; 3948 __destruct_n __d(0); 3949 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d); 3950 if (__len1 <= __len2) 3951 { 3952 value_type* __p = __buff; 3953 for (_BidirectionalIterator __i = __first; __i != __middle; __d.__incr((value_type*)0), ++__i, ++__p) 3954 ::new(__p) value_type(_STD::move(*__i)); 3955 __merge<_Compare>(move_iterator<value_type*>(__buff), 3956 move_iterator<value_type*>(__p), 3957 move_iterator<_BidirectionalIterator>(__middle), 3958 move_iterator<_BidirectionalIterator>(__last), 3959 __first, __comp); 3960 } 3961 else 3962 { 3963 value_type* __p = __buff; 3964 for (_BidirectionalIterator __i = __middle; __i != __last; __d.__incr((value_type*)0), ++__i, ++__p) 3965 ::new(__p) value_type(_STD::move(*__i)); 3966 typedef reverse_iterator<_BidirectionalIterator> _RBi; 3967 typedef reverse_iterator<value_type*> _Rv; 3968 __merge(move_iterator<_RBi>(_RBi(__middle)), move_iterator<_RBi>(_RBi(__first)), 3969 move_iterator<_Rv>(_Rv(__p)), move_iterator<_Rv>(_Rv(__buff)), 3970 _RBi(__last), __negate<_Compare>(__comp)); 3971 } 3972} 3973 3974template <class _Compare, class _BidirectionalIterator> 3975void 3976__inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, 3977 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1, 3978 typename iterator_traits<_BidirectionalIterator>::difference_type __len2, 3979 typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size) 3980{ 3981 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 3982 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; 3983 while (true) 3984 { 3985 // if __middle == __last, we're done 3986 if (__len2 == 0) 3987 return; 3988 // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0 3989 for (; true; ++__first, --__len1) 3990 { 3991 if (__len1 == 0) 3992 return; 3993 if (__comp(*__middle, *__first)) 3994 break; 3995 } 3996 if (__len1 <= __buff_size || __len2 <= __buff_size) 3997 { 3998 __buffered_inplace_merge<_Compare>(__first, __middle, __last, __comp, __len1, __len2, __buff); 3999 return; 4000 } 4001 // __first < __middle < __last 4002 // *__first > *__middle 4003 // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that 4004 // all elements in: 4005 // [__first, __m1) <= [__middle, __m2) 4006 // [__middle, __m2) < [__m1, __middle) 4007 // [__m1, __middle) <= [__m2, __last) 4008 // and __m1 or __m2 is in the middle of its range 4009 _BidirectionalIterator __m1; // "median" of [__first, __middle) 4010 _BidirectionalIterator __m2; // "median" of [__middle, __last) 4011 difference_type __len11; // distance(__first, __m1) 4012 difference_type __len21; // distance(__middle, __m2) 4013 // binary search smaller range 4014 if (__len1 < __len2) 4015 { // __len >= 1, __len2 >= 2 4016 __len21 = __len2 / 2; 4017 __m2 = __middle; 4018 _STD::advance(__m2, __len21); 4019 __m1 = __upper_bound<_Compare>(__first, __middle, *__m2, __comp); 4020 __len11 = _STD::distance(__first, __m1); 4021 } 4022 else 4023 { 4024 if (__len1 == 1) 4025 { // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1 4026 // It is known *__first > *__middle 4027 swap(*__first, *__middle); 4028 return; 4029 } 4030 // __len1 >= 2, __len2 >= 1 4031 __len11 = __len1 / 2; 4032 __m1 = __first; 4033 _STD::advance(__m1, __len11); 4034 __m2 = __lower_bound<_Compare>(__middle, __last, *__m1, __comp); 4035 __len21 = _STD::distance(__middle, __m2); 4036 } 4037 difference_type __len12 = __len1 - __len11; // distance(__m1, __middle) 4038 difference_type __len22 = __len2 - __len21; // distance(__m2, __last) 4039 // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) 4040 // swap middle two partitions 4041 __middle = _STD::rotate(__m1, __middle, __m2); 4042 // __len12 and __len21 now have swapped meanings 4043 // merge smaller range with recurisve call and larger with tail recursion elimination 4044 if (__len11 + __len21 < __len12 + __len22) 4045 { 4046 __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size); 4047// __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size); 4048 __first = __middle; 4049 __middle = __m2; 4050 __len1 = __len12; 4051 __len2 = __len22; 4052 } 4053 else 4054 { 4055 __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size); 4056// __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size); 4057 __last = __middle; 4058 __middle = __m1; 4059 __len1 = __len11; 4060 __len2 = __len21; 4061 } 4062 } 4063} 4064 4065template <class _Tp> 4066struct __inplace_merge_switch 4067{ 4068 static const unsigned value = has_trivial_copy_assign<_Tp>::value; 4069}; 4070 4071template <class _BidirectionalIterator, class _Compare> 4072inline _LIBCPP_INLINE_VISIBILITY 4073void 4074inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, 4075 _Compare __comp) 4076{ 4077 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 4078 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; 4079 difference_type __len1 = _STD::distance(__first, __middle); 4080 difference_type __len2 = _STD::distance(__middle, __last); 4081 difference_type __buf_size = _STD::min(__len1, __len2); 4082 pair<value_type*, ptrdiff_t> __buf(0, 0); 4083 unique_ptr<value_type, __return_temporary_buffer> __h; 4084 if (__inplace_merge_switch<value_type>::value && __buf_size > 8) 4085 { 4086 __buf = _STD::get_temporary_buffer<value_type>(__buf_size); 4087 __h.reset(__buf.first); 4088 } 4089#ifdef _LIBCPP_DEBUG 4090 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4091 __debug_less<_Compare> __c(__comp); 4092 return _STD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __c, __len1, __len2, 4093 __buf.first, __buf.second); 4094#else // _LIBCPP_DEBUG 4095 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4096 return _STD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2, 4097 __buf.first, __buf.second); 4098#endif // _LIBCPP_DEBUG 4099} 4100 4101template <class _BidirectionalIterator> 4102inline _LIBCPP_INLINE_VISIBILITY 4103void 4104inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last) 4105{ 4106 _STD::inplace_merge(__first, __middle, __last, 4107 __less<typename iterator_traits<_BidirectionalIterator>::value_type>()); 4108} 4109 4110// stable_sort 4111 4112template <class _Compare, class _InputIterator1, class _InputIterator2> 4113void 4114__merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1, 4115 _InputIterator2 __first2, _InputIterator2 __last2, 4116 typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp) 4117{ 4118 typedef typename iterator_traits<_InputIterator1>::value_type value_type; 4119 __destruct_n __d(0); 4120 unique_ptr<value_type, __destruct_n&> __h(__result, __d); 4121 for (; true; ++__result) 4122 { 4123 if (__first1 == __last1) 4124 { 4125 for (; __first2 != __last2; ++__first2, ++__result, __d.__incr((value_type*)0)) 4126 ::new (__result) value_type(_STD::move(*__first2)); 4127 __h.release(); 4128 return; 4129 } 4130 if (__first2 == __last2) 4131 { 4132 for (; __first1 != __last1; ++__first1, ++__result, __d.__incr((value_type*)0)) 4133 ::new (__result) value_type(_STD::move(*__first1)); 4134 __h.release(); 4135 return; 4136 } 4137 if (__comp(*__first2, *__first1)) 4138 { 4139 ::new (__result) value_type(_STD::move(*__first2)); 4140 __d.__incr((value_type*)0); 4141 ++__first2; 4142 } 4143 else 4144 { 4145 ::new (__result) value_type(_STD::move(*__first1)); 4146 __d.__incr((value_type*)0); 4147 ++__first1; 4148 } 4149 } 4150} 4151 4152template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 4153void 4154__merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1, 4155 _InputIterator2 __first2, _InputIterator2 __last2, 4156 _OutputIterator __result, _Compare __comp) 4157{ 4158 for (; __first1 != __last1; ++__result) 4159 { 4160 if (__first2 == __last2) 4161 { 4162 for (; __first1 != __last1; ++__first1, ++__result) 4163 *__result = _STD::move(*__first1); 4164 return; 4165 } 4166 if (__comp(*__first2, *__first1)) 4167 { 4168 *__result = _STD::move(*__first2); 4169 ++__first2; 4170 } 4171 else 4172 { 4173 *__result = _STD::move(*__first1); 4174 ++__first1; 4175 } 4176 } 4177 for (; __first2 != __last2; ++__first2, ++__result) 4178 *__result = _STD::move(*__first2); 4179} 4180 4181template <class _Compare, class _RandomAccessIterator> 4182void 4183__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, 4184 typename iterator_traits<_RandomAccessIterator>::difference_type __len, 4185 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size); 4186 4187template <class _Compare, class _RandomAccessIterator> 4188void 4189__stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp, 4190 typename iterator_traits<_RandomAccessIterator>::difference_type __len, 4191 typename iterator_traits<_RandomAccessIterator>::value_type* __first2) 4192{ 4193 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4194 switch (__len) 4195 { 4196 case 0: 4197 return; 4198 case 1: 4199 ::new(__first2) value_type(_STD::move(*__first1)); 4200 return; 4201 case 2: 4202 __destruct_n __d(0); 4203 unique_ptr<value_type, __destruct_n&> __h2(__first2, __d); 4204 if (__comp(*--__last1, *__first1)) 4205 { 4206 ::new(__first2) value_type(_STD::move(*__last1)); 4207 __d.__incr((value_type*)0); 4208 ++__first2; 4209 ::new(__first2) value_type(_STD::move(*__first1)); 4210 } 4211 else 4212 { 4213 ::new(__first2) value_type(_STD::move(*__first1)); 4214 __d.__incr((value_type*)0); 4215 ++__first2; 4216 ::new(__first2) value_type(_STD::move(*__last1)); 4217 } 4218 __h2.release(); 4219 return; 4220 } 4221 if (__len <= 8) 4222 { 4223 __insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp); 4224 return; 4225 } 4226 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2; 4227 _RandomAccessIterator __m = __first1 + __l2; 4228 __stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2); 4229 __stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2); 4230 __merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp); 4231} 4232 4233template <class _Tp> 4234struct __stable_sort_switch 4235{ 4236 static const unsigned value = 128*has_trivial_copy_assign<_Tp>::value; 4237}; 4238 4239template <class _Compare, class _RandomAccessIterator> 4240void 4241__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, 4242 typename iterator_traits<_RandomAccessIterator>::difference_type __len, 4243 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size) 4244{ 4245 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4246 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4247 switch (__len) 4248 { 4249 case 0: 4250 case 1: 4251 return; 4252 case 2: 4253 if (__comp(*--__last, *__first)) 4254 swap(*__first, *__last); 4255 return; 4256 } 4257 if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value)) 4258 { 4259 __insertion_sort<_Compare>(__first, __last, __comp); 4260 return; 4261 } 4262 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2; 4263 _RandomAccessIterator __m = __first + __l2; 4264 if (__len <= __buff_size) 4265 { 4266 __destruct_n __d(0); 4267 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d); 4268 __stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff); 4269 __d.__set(__l2, (value_type*)0); 4270 __stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2); 4271 __d.__set(__len, (value_type*)0); 4272 __merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp); 4273// __merge<_Compare>(move_iterator<value_type*>(__buff), 4274// move_iterator<value_type*>(__buff + __l2), 4275// move_iterator<_RandomAccessIterator>(__buff + __l2), 4276// move_iterator<_RandomAccessIterator>(__buff + __len), 4277// __first, __comp); 4278 return; 4279 } 4280 __stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size); 4281 __stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size); 4282 __inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size); 4283} 4284 4285template <class _RandomAccessIterator, class _Compare> 4286inline _LIBCPP_INLINE_VISIBILITY 4287void 4288stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4289{ 4290 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4291 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4292 difference_type __len = __last - __first; 4293 pair<value_type*, ptrdiff_t> __buf(0, 0); 4294 unique_ptr<value_type, __return_temporary_buffer> __h; 4295 if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value)) 4296 { 4297 __buf = _STD::get_temporary_buffer<value_type>(__len); 4298 __h.reset(__buf.first); 4299 } 4300#ifdef _LIBCPP_DEBUG 4301 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4302 __debug_less<_Compare> __c(__comp); 4303 __stable_sort<_Comp_ref>(__first, __last, __c, __len, __buf.first, __buf.second); 4304#else // _LIBCPP_DEBUG 4305 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4306 __stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second); 4307#endif // _LIBCPP_DEBUG 4308} 4309 4310template <class _RandomAccessIterator> 4311inline _LIBCPP_INLINE_VISIBILITY 4312void 4313stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 4314{ 4315 _STD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4316} 4317 4318// is_heap_until 4319 4320template <class _RandomAccessIterator, class _Compare> 4321_RandomAccessIterator 4322is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4323{ 4324 typedef typename _STD::iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4325 difference_type __len = __last - __first; 4326 difference_type __p = 0; 4327 difference_type __c = 1; 4328 _RandomAccessIterator __pp = __first; 4329 while (__c < __len) 4330 { 4331 _RandomAccessIterator __cp = __first + __c; 4332 if (__comp(*__pp, *__cp)) 4333 return __cp; 4334 ++__c; 4335 ++__cp; 4336 if (__c == __len) 4337 return __last; 4338 if (__comp(*__pp, *__cp)) 4339 return __cp; 4340 ++__p; 4341 ++__pp; 4342 __c = 2 * __p + 1; 4343 } 4344 return __last; 4345} 4346 4347template<class _RandomAccessIterator> 4348inline _LIBCPP_INLINE_VISIBILITY 4349_RandomAccessIterator 4350is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last) 4351{ 4352 return _STD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4353} 4354 4355// is_heap 4356 4357template <class _RandomAccessIterator, class _Compare> 4358inline _LIBCPP_INLINE_VISIBILITY 4359bool 4360is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4361{ 4362 return _STD::is_heap_until(__first, __last, __comp) == __last; 4363} 4364 4365template<class _RandomAccessIterator> 4366inline _LIBCPP_INLINE_VISIBILITY 4367bool 4368is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 4369{ 4370 return _STD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4371} 4372 4373// push_heap 4374 4375template <class _Compare, class _RandomAccessIterator> 4376void 4377__push_heap_front(_RandomAccessIterator __first, _RandomAccessIterator, _Compare __comp, 4378 typename iterator_traits<_RandomAccessIterator>::difference_type __len) 4379{ 4380 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4381 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4382 if (__len > 1) 4383 { 4384 difference_type __p = 0; 4385 _RandomAccessIterator __pp = __first; 4386 difference_type __c = 2; 4387 _RandomAccessIterator __cp = __first + __c; 4388 if (__c == __len || __comp(*__cp, *(__cp - 1))) 4389 { 4390 --__c; 4391 --__cp; 4392 } 4393 if (__comp(*__pp, *__cp)) 4394 { 4395 value_type __t(_STD::move(*__pp)); 4396 do 4397 { 4398 *__pp = _STD::move(*__cp); 4399 __pp = __cp; 4400 __p = __c; 4401 __c = (__p + 1) * 2; 4402 if (__c > __len) 4403 break; 4404 __cp = __first + __c; 4405 if (__c == __len || __comp(*__cp, *(__cp - 1))) 4406 { 4407 --__c; 4408 --__cp; 4409 } 4410 } while (__comp(__t, *__cp)); 4411 *__pp = _STD::move(__t); 4412 } 4413 } 4414} 4415 4416template <class _Compare, class _RandomAccessIterator> 4417void 4418__push_heap_back(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, 4419 typename iterator_traits<_RandomAccessIterator>::difference_type __len) 4420{ 4421 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4422 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4423 if (__len > 1) 4424 { 4425 __len = (__len - 2) / 2; 4426 _RandomAccessIterator __ptr = __first + __len; 4427 if (__comp(*__ptr, *--__last)) 4428 { 4429 value_type __t(_STD::move(*__last)); 4430 do 4431 { 4432 *__last = _STD::move(*__ptr); 4433 __last = __ptr; 4434 if (__len == 0) 4435 break; 4436 __len = (__len - 1) / 2; 4437 __ptr = __first + __len; 4438 } while (__comp(*__ptr, __t)); 4439 *__last = _STD::move(__t); 4440 } 4441 } 4442} 4443 4444template <class _RandomAccessIterator, class _Compare> 4445inline _LIBCPP_INLINE_VISIBILITY 4446void 4447push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4448{ 4449#ifdef _LIBCPP_DEBUG 4450 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4451 __debug_less<_Compare> __c(__comp); 4452 __push_heap_back<_Comp_ref>(__first, __last, __c, __last - __first); 4453#else // _LIBCPP_DEBUG 4454 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4455 __push_heap_back<_Comp_ref>(__first, __last, __comp, __last - __first); 4456#endif // _LIBCPP_DEBUG 4457} 4458 4459template <class _RandomAccessIterator> 4460inline _LIBCPP_INLINE_VISIBILITY 4461void 4462push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 4463{ 4464 _STD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4465} 4466 4467// pop_heap 4468 4469template <class _Compare, class _RandomAccessIterator> 4470inline _LIBCPP_INLINE_VISIBILITY 4471void 4472__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, 4473 typename iterator_traits<_RandomAccessIterator>::difference_type __len) 4474{ 4475 if (__len > 1) 4476 { 4477 swap(*__first, *--__last); 4478 __push_heap_front<_Compare>(__first, __last, __comp, __len-1); 4479 } 4480} 4481 4482template <class _RandomAccessIterator, class _Compare> 4483inline _LIBCPP_INLINE_VISIBILITY 4484void 4485pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4486{ 4487#ifdef _LIBCPP_DEBUG 4488 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4489 __debug_less<_Compare> __c(__comp); 4490 __pop_heap<_Comp_ref>(__first, __last, __c, __last - __first); 4491#else // _LIBCPP_DEBUG 4492 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4493 __pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first); 4494#endif // _LIBCPP_DEBUG 4495} 4496 4497template <class _RandomAccessIterator> 4498inline _LIBCPP_INLINE_VISIBILITY 4499void 4500pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 4501{ 4502 _STD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4503} 4504 4505// make_heap 4506 4507template <class _Compare, class _RandomAccessIterator> 4508void 4509__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4510{ 4511 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4512 difference_type __n = __last - __first; 4513 if (__n > 1) 4514 { 4515 __last = __first; 4516 ++__last; 4517 for (difference_type __i = 1; __i < __n;) 4518 __push_heap_back<_Compare>(__first, ++__last, __comp, ++__i); 4519 } 4520} 4521 4522template <class _RandomAccessIterator, class _Compare> 4523inline _LIBCPP_INLINE_VISIBILITY 4524void 4525make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4526{ 4527#ifdef _LIBCPP_DEBUG 4528 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4529 __debug_less<_Compare> __c(__comp); 4530 __make_heap<_Comp_ref>(__first, __last, __c); 4531#else // _LIBCPP_DEBUG 4532 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4533 __make_heap<_Comp_ref>(__first, __last, __comp); 4534#endif // _LIBCPP_DEBUG 4535} 4536 4537template <class _RandomAccessIterator> 4538inline _LIBCPP_INLINE_VISIBILITY 4539void 4540make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 4541{ 4542 _STD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4543} 4544 4545// sort_heap 4546 4547template <class _Compare, class _RandomAccessIterator> 4548void 4549__sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4550{ 4551 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4552 for (difference_type __n = __last - __first; __n > 1; --__last, --__n) 4553 __pop_heap<_Compare>(__first, __last, __comp, __n); 4554} 4555 4556template <class _RandomAccessIterator, class _Compare> 4557inline _LIBCPP_INLINE_VISIBILITY 4558void 4559sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4560{ 4561#ifdef _LIBCPP_DEBUG 4562 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4563 __debug_less<_Compare> __c(__comp); 4564 __sort_heap<_Comp_ref>(__first, __last, __c); 4565#else // _LIBCPP_DEBUG 4566 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4567 __sort_heap<_Comp_ref>(__first, __last, __comp); 4568#endif // _LIBCPP_DEBUG 4569} 4570 4571template <class _RandomAccessIterator> 4572inline _LIBCPP_INLINE_VISIBILITY 4573void 4574sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 4575{ 4576 _STD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4577} 4578 4579// partial_sort 4580 4581template <class _Compare, class _RandomAccessIterator> 4582void 4583__partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, 4584 _Compare __comp) 4585{ 4586 __make_heap<_Compare>(__first, __middle, __comp); 4587 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first; 4588 for (_RandomAccessIterator __i = __middle; __i != __last; ++__i) 4589 { 4590 if (__comp(*__i, *__first)) 4591 { 4592 swap(*__i, *__first); 4593 __push_heap_front<_Compare>(__first, __middle, __comp, __len); 4594 } 4595 } 4596 __sort_heap<_Compare>(__first, __middle, __comp); 4597} 4598 4599template <class _RandomAccessIterator, class _Compare> 4600inline _LIBCPP_INLINE_VISIBILITY 4601void 4602partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, 4603 _Compare __comp) 4604{ 4605#ifdef _LIBCPP_DEBUG 4606 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4607 __debug_less<_Compare> __c(__comp); 4608 __partial_sort<_Comp_ref>(__first, __middle, __last, __c); 4609#else // _LIBCPP_DEBUG 4610 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4611 __partial_sort<_Comp_ref>(__first, __middle, __last, __comp); 4612#endif // _LIBCPP_DEBUG 4613} 4614 4615template <class _RandomAccessIterator> 4616inline _LIBCPP_INLINE_VISIBILITY 4617void 4618partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last) 4619{ 4620 _STD::partial_sort(__first, __middle, __last, 4621 __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4622} 4623 4624// partial_sort_copy 4625 4626template <class _Compare, class _InputIterator, class _RandomAccessIterator> 4627_RandomAccessIterator 4628__partial_sort_copy(_InputIterator __first, _InputIterator __last, 4629 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp) 4630{ 4631 _RandomAccessIterator __r = __result_first; 4632 if (__r != __result_last) 4633 { 4634 typename iterator_traits<_RandomAccessIterator>::difference_type __len = 0; 4635 for (; __first != __last && __r != __result_last; ++__first, ++__r, ++__len) 4636 *__r = *__first; 4637 __make_heap<_Compare>(__result_first, __r, __comp); 4638 for (; __first != __last; ++__first) 4639 if (__comp(*__first, *__result_first)) 4640 { 4641 *__result_first = *__first; 4642 __push_heap_front<_Compare>(__result_first, __r, __comp, __len); 4643 } 4644 __sort_heap<_Compare>(__result_first, __r, __comp); 4645 } 4646 return __r; 4647} 4648 4649template <class _InputIterator, class _RandomAccessIterator, class _Compare> 4650inline _LIBCPP_INLINE_VISIBILITY 4651_RandomAccessIterator 4652partial_sort_copy(_InputIterator __first, _InputIterator __last, 4653 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp) 4654{ 4655#ifdef _LIBCPP_DEBUG 4656 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4657 __debug_less<_Compare> __c(__comp); 4658 return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __c); 4659#else // _LIBCPP_DEBUG 4660 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4661 return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp); 4662#endif // _LIBCPP_DEBUG 4663} 4664 4665template <class _InputIterator, class _RandomAccessIterator> 4666inline _LIBCPP_INLINE_VISIBILITY 4667_RandomAccessIterator 4668partial_sort_copy(_InputIterator __first, _InputIterator __last, 4669 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last) 4670{ 4671 return _STD::partial_sort_copy(__first, __last, __result_first, __result_last, 4672 __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4673} 4674 4675// nth_element 4676 4677template <class _Compare, class _RandomAccessIterator> 4678void 4679__nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp) 4680{ 4681 // _Compare is known to be a reference type 4682 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4683 const difference_type __limit = 7; 4684 while (true) 4685 { 4686 __restart: 4687 difference_type __len = __last - __first; 4688 switch (__len) 4689 { 4690 case 0: 4691 case 1: 4692 return; 4693 case 2: 4694 if (__comp(*--__last, *__first)) 4695 swap(*__first, *__last); 4696 return; 4697 case 3: 4698 { 4699 _RandomAccessIterator __m = __first; 4700 _STD::__sort3<_Compare>(__first, ++__m, --__last, __comp); 4701 return; 4702 } 4703 } 4704 if (__len <= __limit) 4705 { 4706 __selection_sort<_Compare>(__first, __last, __comp); 4707 return; 4708 } 4709 // __len > __limit >= 3 4710 _RandomAccessIterator __m = __first + __len/2; 4711 _RandomAccessIterator __lm1 = __last; 4712 unsigned __n_swaps = _STD::__sort3<_Compare>(__first, __m, --__lm1, __comp); 4713 // *__m is median 4714 // partition [__first, __m) < *__m and *__m <= [__m, __last) 4715 // (this inhibits tossing elements equivalent to __m around unnecessarily) 4716 _RandomAccessIterator __i = __first; 4717 _RandomAccessIterator __j = __lm1; 4718 // j points beyond range to be tested, *__lm1 is known to be <= *__m 4719 // The search going up is known to be guarded but the search coming down isn't. 4720 // Prime the downward search with a guard. 4721 if (!__comp(*__i, *__m)) // if *__first == *__m 4722 { 4723 // *__first == *__m, *__first doesn't go in first part 4724 // manually guard downward moving __j against __i 4725 while (true) 4726 { 4727 if (__i == --__j) 4728 { 4729 // *__first == *__m, *__m <= all other elements 4730 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last) 4731 ++__i; // __first + 1 4732 __j = __last; 4733 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1) 4734 { 4735 while (true) 4736 { 4737 if (__i == __j) 4738 return; // [__first, __last) all equivalent elements 4739 if (__comp(*__first, *__i)) 4740 { 4741 swap(*__i, *__j); 4742 ++__n_swaps; 4743 ++__i; 4744 break; 4745 } 4746 ++__i; 4747 } 4748 } 4749 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1 4750 if (__i == __j) 4751 return; 4752 while (true) 4753 { 4754 while (!__comp(*__first, *__i)) 4755 ++__i; 4756 while (__comp(*__first, *--__j)) 4757 ; 4758 if (__i >= __j) 4759 break; 4760 swap(*__i, *__j); 4761 ++__n_swaps; 4762 ++__i; 4763 } 4764 // [__first, __i) == *__first and *__first < [__i, __last) 4765 // The first part is sorted, 4766 if (__nth < __i) 4767 return; 4768 // __nth_element the secod part 4769 // __nth_element<_Compare>(__i, __nth, __last, __comp); 4770 __first = __i; 4771 goto __restart; 4772 } 4773 if (__comp(*__j, *__m)) 4774 { 4775 swap(*__i, *__j); 4776 ++__n_swaps; 4777 break; // found guard for downward moving __j, now use unguarded partition 4778 } 4779 } 4780 } 4781 ++__i; 4782 // j points beyond range to be tested, *__lm1 is known to be <= *__m 4783 // if not yet partitioned... 4784 if (__i < __j) 4785 { 4786 // known that *(__i - 1) < *__m 4787 while (true) 4788 { 4789 // __m still guards upward moving __i 4790 while (__comp(*__i, *__m)) 4791 ++__i; 4792 // It is now known that a guard exists for downward moving __j 4793 while (!__comp(*--__j, *__m)) 4794 ; 4795 if (__i >= __j) 4796 break; 4797 swap(*__i, *__j); 4798 ++__n_swaps; 4799 // It is known that __m != __j 4800 // If __m just moved, follow it 4801 if (__m == __i) 4802 __m = __j; 4803 ++__i; 4804 } 4805 } 4806 // [__first, __i) < *__m and *__m <= [__i, __last) 4807 if (__i != __m && __comp(*__m, *__i)) 4808 { 4809 swap(*__i, *__m); 4810 ++__n_swaps; 4811 } 4812 // [__first, __i) < *__i and *__i <= [__i+1, __last) 4813 if (__nth == __i) 4814 return; 4815 if (__n_swaps == 0) 4816 { 4817 // We were given a perfectly partitioned sequence. Coincidence? 4818 if (__nth < __i) 4819 { 4820 // Check for [__first, __i) already sorted 4821 __j = __m = __first; 4822 while (++__j != __i) 4823 { 4824 if (__comp(*__j, *__m)) 4825 // not yet sorted, so sort 4826 goto not_sorted; 4827 __m = __j; 4828 } 4829 // [__first, __i) sorted 4830 return; 4831 } 4832 else 4833 { 4834 // Check for [__i, __last) already sorted 4835 __j = __m = __i; 4836 while (++__j != __last) 4837 { 4838 if (__comp(*__j, *__m)) 4839 // not yet sorted, so sort 4840 goto not_sorted; 4841 __m = __j; 4842 } 4843 // [__i, __last) sorted 4844 return; 4845 } 4846 } 4847not_sorted: 4848 // __nth_element on range containing __nth 4849 if (__nth < __i) 4850 { 4851 // __nth_element<_Compare>(__first, __nth, __i, __comp); 4852 __last = __i; 4853 } 4854 else 4855 { 4856 // __nth_element<_Compare>(__i+1, __nth, __last, __comp); 4857 __first = ++__i; 4858 } 4859 } 4860} 4861 4862template <class _RandomAccessIterator, class _Compare> 4863inline _LIBCPP_INLINE_VISIBILITY 4864void 4865nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp) 4866{ 4867#ifdef _LIBCPP_DEBUG 4868 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4869 __debug_less<_Compare> __c(__comp); 4870 __nth_element<_Comp_ref>(__first, __nth, __last, __c); 4871#else // _LIBCPP_DEBUG 4872 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4873 __nth_element<_Comp_ref>(__first, __nth, __last, __comp); 4874#endif // _LIBCPP_DEBUG 4875} 4876 4877template <class _RandomAccessIterator> 4878inline _LIBCPP_INLINE_VISIBILITY 4879void 4880nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last) 4881{ 4882 _STD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4883} 4884 4885// includes 4886 4887template <class _Compare, class _InputIterator1, class _InputIterator2> 4888bool 4889__includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, 4890 _Compare __comp) 4891{ 4892 for (; __first2 != __last2; ++__first1) 4893 { 4894 if (__first1 == __last1 || __comp(*__first2, *__first1)) 4895 return false; 4896 if (!__comp(*__first1, *__first2)) 4897 ++__first2; 4898 } 4899 return true; 4900} 4901 4902template <class _InputIterator1, class _InputIterator2, class _Compare> 4903inline _LIBCPP_INLINE_VISIBILITY 4904bool 4905includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, 4906 _Compare __comp) 4907{ 4908#ifdef _LIBCPP_DEBUG 4909 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4910 __debug_less<_Compare> __c(__comp); 4911 return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __c); 4912#else // _LIBCPP_DEBUG 4913 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4914 return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp); 4915#endif // _LIBCPP_DEBUG 4916} 4917 4918template <class _InputIterator1, class _InputIterator2> 4919inline _LIBCPP_INLINE_VISIBILITY 4920bool 4921includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) 4922{ 4923 return _STD::includes(__first1, __last1, __first2, __last2, 4924 __less<typename iterator_traits<_InputIterator1>::value_type, 4925 typename iterator_traits<_InputIterator2>::value_type>()); 4926} 4927 4928// set_union 4929 4930template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 4931_OutputIterator 4932__set_union(_InputIterator1 __first1, _InputIterator1 __last1, 4933 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 4934{ 4935 for (; __first1 != __last1; ++__result) 4936 { 4937 if (__first2 == __last2) 4938 return _STD::copy(__first1, __last1, __result); 4939 if (__comp(*__first2, *__first1)) 4940 { 4941 *__result = *__first2; 4942 ++__first2; 4943 } 4944 else 4945 { 4946 *__result = *__first1; 4947 if (!__comp(*__first1, *__first2)) 4948 ++__first2; 4949 ++__first1; 4950 } 4951 } 4952 return _STD::copy(__first2, __last2, __result); 4953} 4954 4955template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 4956inline _LIBCPP_INLINE_VISIBILITY 4957_OutputIterator 4958set_union(_InputIterator1 __first1, _InputIterator1 __last1, 4959 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 4960{ 4961#ifdef _LIBCPP_DEBUG 4962 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4963 __debug_less<_Compare> __c(__comp); 4964 return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c); 4965#else // _LIBCPP_DEBUG 4966 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4967 return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 4968#endif // _LIBCPP_DEBUG 4969} 4970 4971template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 4972inline _LIBCPP_INLINE_VISIBILITY 4973_OutputIterator 4974set_union(_InputIterator1 __first1, _InputIterator1 __last1, 4975 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 4976{ 4977 return _STD::set_union(__first1, __last1, __first2, __last2, __result, 4978 __less<typename iterator_traits<_InputIterator1>::value_type, 4979 typename iterator_traits<_InputIterator2>::value_type>()); 4980} 4981 4982// set_intersection 4983 4984template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 4985_OutputIterator 4986__set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 4987 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 4988{ 4989 while (__first1 != __last1 && __first2 != __last2) 4990 { 4991 if (__comp(*__first1, *__first2)) 4992 ++__first1; 4993 else 4994 { 4995 if (!__comp(*__first2, *__first1)) 4996 { 4997 *__result = *__first1; 4998 ++__result; 4999 ++__first1; 5000 } 5001 ++__first2; 5002 } 5003 } 5004 return __result; 5005} 5006 5007template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 5008inline _LIBCPP_INLINE_VISIBILITY 5009_OutputIterator 5010set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5011 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5012{ 5013#ifdef _LIBCPP_DEBUG 5014 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5015 __debug_less<_Compare> __c(__comp); 5016 return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c); 5017#else // _LIBCPP_DEBUG 5018 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5019 return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 5020#endif // _LIBCPP_DEBUG 5021} 5022 5023template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 5024inline _LIBCPP_INLINE_VISIBILITY 5025_OutputIterator 5026set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5027 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 5028{ 5029 return _STD::set_intersection(__first1, __last1, __first2, __last2, __result, 5030 __less<typename iterator_traits<_InputIterator1>::value_type, 5031 typename iterator_traits<_InputIterator2>::value_type>()); 5032} 5033 5034// set_difference 5035 5036template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 5037_OutputIterator 5038__set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5039 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5040{ 5041 while (__first1 != __last1) 5042 { 5043 if (__first2 == __last2) 5044 return _STD::copy(__first1, __last1, __result); 5045 if (__comp(*__first1, *__first2)) 5046 { 5047 *__result = *__first1; 5048 ++__result; 5049 ++__first1; 5050 } 5051 else 5052 { 5053 if (!__comp(*__first2, *__first1)) 5054 ++__first1; 5055 ++__first2; 5056 } 5057 } 5058 return __result; 5059} 5060 5061template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 5062inline _LIBCPP_INLINE_VISIBILITY 5063_OutputIterator 5064set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5065 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5066{ 5067#ifdef _LIBCPP_DEBUG 5068 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5069 __debug_less<_Compare> __c(__comp); 5070 return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c); 5071#else // _LIBCPP_DEBUG 5072 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5073 return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 5074#endif // _LIBCPP_DEBUG 5075} 5076 5077template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 5078inline _LIBCPP_INLINE_VISIBILITY 5079_OutputIterator 5080set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5081 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 5082{ 5083 return _STD::set_difference(__first1, __last1, __first2, __last2, __result, 5084 __less<typename iterator_traits<_InputIterator1>::value_type, 5085 typename iterator_traits<_InputIterator2>::value_type>()); 5086} 5087 5088// set_symmetric_difference 5089 5090template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 5091_OutputIterator 5092__set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5093 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5094{ 5095 while (__first1 != __last1) 5096 { 5097 if (__first2 == __last2) 5098 return _STD::copy(__first1, __last1, __result); 5099 if (__comp(*__first1, *__first2)) 5100 { 5101 *__result = *__first1; 5102 ++__result; 5103 ++__first1; 5104 } 5105 else 5106 { 5107 if (__comp(*__first2, *__first1)) 5108 { 5109 *__result = *__first2; 5110 ++__result; 5111 } 5112 else 5113 ++__first1; 5114 ++__first2; 5115 } 5116 } 5117 return _STD::copy(__first2, __last2, __result); 5118} 5119 5120template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 5121inline _LIBCPP_INLINE_VISIBILITY 5122_OutputIterator 5123set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5124 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5125{ 5126#ifdef _LIBCPP_DEBUG 5127 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5128 __debug_less<_Compare> __c(__comp); 5129 return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c); 5130#else // _LIBCPP_DEBUG 5131 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5132 return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 5133#endif // _LIBCPP_DEBUG 5134} 5135 5136template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 5137inline _LIBCPP_INLINE_VISIBILITY 5138_OutputIterator 5139set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5140 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 5141{ 5142 return _STD::set_symmetric_difference(__first1, __last1, __first2, __last2, __result, 5143 __less<typename iterator_traits<_InputIterator1>::value_type, 5144 typename iterator_traits<_InputIterator2>::value_type>()); 5145} 5146 5147// lexicographical_compare 5148 5149template <class _Compare, class _InputIterator1, class _InputIterator2> 5150bool 5151__lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, 5152 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp) 5153{ 5154 for (; __first2 != __last2; ++__first1, ++__first2) 5155 { 5156 if (__first1 == __last1 || __comp(*__first1, *__first2)) 5157 return true; 5158 if (__comp(*__first2, *__first1)) 5159 return false; 5160 } 5161 return false; 5162} 5163 5164template <class _InputIterator1, class _InputIterator2, class _Compare> 5165inline _LIBCPP_INLINE_VISIBILITY 5166bool 5167lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, 5168 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp) 5169{ 5170#ifdef _LIBCPP_DEBUG 5171 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5172 __debug_less<_Compare> __c(__comp); 5173 return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __c); 5174#else // _LIBCPP_DEBUG 5175 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5176 return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __comp); 5177#endif // _LIBCPP_DEBUG 5178} 5179 5180template <class _InputIterator1, class _InputIterator2> 5181inline _LIBCPP_INLINE_VISIBILITY 5182bool 5183lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, 5184 _InputIterator2 __first2, _InputIterator2 __last2) 5185{ 5186 return _STD::lexicographical_compare(__first1, __last1, __first2, __last2, 5187 __less<typename iterator_traits<_InputIterator1>::value_type, 5188 typename iterator_traits<_InputIterator2>::value_type>()); 5189} 5190 5191// next_permutation 5192 5193template <class _Compare, class _BidirectionalIterator> 5194bool 5195__next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 5196{ 5197 _BidirectionalIterator __i = __last; 5198 if (__first == __last || __first == --__i) 5199 return false; 5200 while (true) 5201 { 5202 _BidirectionalIterator __ip1 = __i; 5203 if (__comp(*--__i, *__ip1)) 5204 { 5205 _BidirectionalIterator __j = __last; 5206 while (!__comp(*__i, *--__j)) 5207 ; 5208 swap(*__i, *__j); 5209 _STD::reverse(__ip1, __last); 5210 return true; 5211 } 5212 if (__i == __first) 5213 { 5214 _STD::reverse(__first, __last); 5215 return false; 5216 } 5217 } 5218} 5219 5220template <class _BidirectionalIterator, class _Compare> 5221inline _LIBCPP_INLINE_VISIBILITY 5222bool 5223next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 5224{ 5225#ifdef _LIBCPP_DEBUG 5226 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5227 __debug_less<_Compare> __c(__comp); 5228 return __next_permutation<_Comp_ref>(__first, __last, __c); 5229#else // _LIBCPP_DEBUG 5230 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5231 return __next_permutation<_Comp_ref>(__first, __last, __comp); 5232#endif // _LIBCPP_DEBUG 5233} 5234 5235template <class _BidirectionalIterator> 5236inline _LIBCPP_INLINE_VISIBILITY 5237bool 5238next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last) 5239{ 5240 return _STD::next_permutation(__first, __last, 5241 __less<typename iterator_traits<_BidirectionalIterator>::value_type>()); 5242} 5243 5244// prev_permutation 5245 5246template <class _Compare, class _BidirectionalIterator> 5247bool 5248__prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 5249{ 5250 _BidirectionalIterator __i = __last; 5251 if (__first == __last || __first == --__i) 5252 return false; 5253 while (true) 5254 { 5255 _BidirectionalIterator __ip1 = __i; 5256 if (__comp(*__ip1, *--__i)) 5257 { 5258 _BidirectionalIterator __j = __last; 5259 while (!__comp(*--__j, *__i)) 5260 ; 5261 swap(*__i, *__j); 5262 _STD::reverse(__ip1, __last); 5263 return true; 5264 } 5265 if (__i == __first) 5266 { 5267 _STD::reverse(__first, __last); 5268 return false; 5269 } 5270 } 5271} 5272 5273template <class _BidirectionalIterator, class _Compare> 5274inline _LIBCPP_INLINE_VISIBILITY 5275bool 5276prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 5277{ 5278#ifdef _LIBCPP_DEBUG 5279 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5280 __debug_less<_Compare> __c(__comp); 5281 return __prev_permutation<_Comp_ref>(__first, __last, __c); 5282#else // _LIBCPP_DEBUG 5283 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5284 return __prev_permutation<_Comp_ref>(__first, __last, __comp); 5285#endif // _LIBCPP_DEBUG 5286} 5287 5288template <class _BidirectionalIterator> 5289inline _LIBCPP_INLINE_VISIBILITY 5290bool 5291prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last) 5292{ 5293 return _STD::prev_permutation(__first, __last, 5294 __less<typename iterator_traits<_BidirectionalIterator>::value_type>()); 5295} 5296 5297template <class _Tp> 5298inline _LIBCPP_INLINE_VISIBILITY 5299typename enable_if 5300< 5301 is_integral<_Tp>::value, 5302 _Tp 5303>::type 5304__rotate_left(_Tp __t, _Tp __n = 1) 5305{ 5306 const unsigned __bits = static_cast<unsigned>(sizeof(_Tp) * __CHAR_BIT__ - 1); 5307 __n &= __bits; 5308 return static_cast<_Tp>((__t << __n) | (static_cast<typename make_unsigned<_Tp>::type>(__t) >> (__bits - __n))); 5309} 5310 5311template <class _Tp> 5312inline _LIBCPP_INLINE_VISIBILITY 5313typename enable_if 5314< 5315 is_integral<_Tp>::value, 5316 _Tp 5317>::type 5318__rotate_right(_Tp __t, _Tp __n = 1) 5319{ 5320 const unsigned __bits = static_cast<unsigned>(sizeof(_Tp) * __CHAR_BIT__ - 1); 5321 __n &= __bits; 5322 return static_cast<_Tp>((__t << (__bits - __n)) | (static_cast<typename make_unsigned<_Tp>::type>(__t) >> __n)); 5323} 5324 5325_LIBCPP_END_NAMESPACE_STD 5326 5327#endif // _LIBCPP_ALGORITHM 5328