uspace/lib/cpp/include/__bits/algorithm.hpp

   1 /*
   2  * Copyright (c) 2018 Jaroslav Jindrak
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * - Redistributions of source code must retain the above copyright
  10  *   notice, this list of conditions and the following disclaimer.
  11  * - Redistributions in binary form must reproduce the above copyright
  12  *   notice, this list of conditions and the following disclaimer in the
  13  *   documentation and/or other materials provided with the distribution.
  14  * - The name of the author may not be used to endorse or promote products
  15  *   derived from this software without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 #ifndef LIBCPP_BITS_ALGORITHM
  30 #define LIBCPP_BITS_ALGORITHM
  31
  32 #include <iterator>
  33 #include <utility>
  34
  35 namespace std
  36 {
  37     template<class T>
  38     struct less;
  39
  40     /**
  41      * 25.2, non-modyfing sequence operations:
  42      */
  43
  44     /**
  45      * 25.2.1, all_of:
  46      */
  47
  48     template<class InputIterator, class Predicate>
  49     bool all_of(InputIterator first, InputIterator last, Predicate pred)
  50     {
  51         while (first != last)
  52         {
  53             if (!pred(*first++))
  54                 return false;
  55         }
  56
  57         return true;
  58     }
  59
  60     /**
  61      * 25.2.2, any_of:
  62      */
  63
  64     template<class InputIterator, class Predicate>
  65     bool any_of(InputIterator first, InputIterator last, Predicate pred)
  66     {
  67         while (first != last)
  68         {
  69             if (pred(*first++))
  70                 return true;
  71         }
  72
  73         return false;
  74     }
  75
  76     /**
  77      * 25.2.3, none_of:
  78      */
  79
  80     template<class InputIterator, class Predicate>
  81     bool none_of(InputIterator first, InputIterator last, Predicate pred)
  82     {
  83         return !any_of(first, last, pred);
  84     }
  85
  86     /**
  87      * 25.2.4, for_each:
  88      */
  89
  90     template<class InputIterator, class Function>
  91     Function for_each(InputIterator first, InputIterator last, Function f)
  92     {
  93         while (first != last)
  94             f(*first++);
  95
  96         return move(f);
  97     }
  98
  99     /**
 100      * 25.2.5, find:
 101      */
 102
 103     template<class InputIterator, class T>
 104     InputIterator find(InputIterator first, InputIterator last, const T& value)
 105     {
 106         while (first != last)
 107         {
 108             if (*first == value)
 109                 return first;
 110             ++first;
 111         }
 112
 113         return last;
 114     }
 115
 116     template<class InputIterator, class Predicate>
 117     InputIterator find_if(InputIterator first, InputIterator last, Predicate pred)
 118     {
 119         while (first != last)
 120         {
 121             if (pred(*first))
 122                 return first;
 123             ++first;
 124         }
 125
 126         return last;
 127     }
 128
 129     template<class InputIterator, class Predicate>
 130     InputIterator find_if_not(InputIterator first, InputIterator last, Predicate pred)
 131     {
 132         while (first != last)
 133         {
 134             if (!pred(*first))
 135                 return first;
 136             ++first;
 137         }
 138
 139         return last;
 140     }
 141
 142     /**
 143      * 25.2.6, find_end:
 144      */
 145
 146     // TODO: implement
 147
 148     /**
 149      * 25.2.7, find_first:
 150      */
 151
 152     // TODO: implement
 153
 154     /**
 155      * 25.2.8, adjacent_find:
 156      */
 157
 158     template<class ForwardIterator>
 159     ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last)
 160     {
 161         while (first != last)
 162         {
 163             if (*first == *(first + 1))
 164                 return first;
 165             ++first;
 166         }
 167
 168         return last;
 169     }
 170
 171     template<class ForwardIterator, class Predicate>
 172     ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, Predicate pred)
 173     {
 174         while (first != last)
 175         {
 176             if (pred(*first, *(first + 1)))
 177                 return first;
 178             ++first;
 179         }
 180
 181         return last;
 182     }
 183
 184     /**
 185      * 25.2.9, count:
 186      */
 187
 188     template<class InputIterator, class T>
 189     typename iterator_traits<InputIterator>::difference_type
 190     count(InputIterator first, InputIterator last, const T& value)
 191     {
 192         typename iterator_traits<InputIterator>::difference_type cnt{};
 193
 194         while (first != last)
 195         {
 196             if (*first++ == value)
 197                 ++cnt;
 198         }
 199
 200         return cnt;
 201     }
 202
 203     template<class InputIterator, class Predicate>
 204     typename iterator_traits<InputIterator>::difference_type
 205     count_if(InputIterator first, InputIterator last, Predicate pred)
 206     {
 207         typename iterator_traits<InputIterator>::difference_type cnt{};
 208
 209         while (first != last)
 210         {
 211             if (pred(*first++))
 212                 ++cnt;
 213         }
 214
 215         return cnt;
 216     }
 217
 218     /**
 219      * 25.2.10, mismatch:
 220      */
 221
 222     template<class InputIterator1, class InputIterator2>
 223     pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1,
 224                                                   InputIterator2 first2)
 225     {
 226         while (first1 != last1 && *first1 == *first2)
 227         {
 228             ++first1;
 229             ++first2;
 230         }
 231
 232         return make_pair(first1, first2);
 233     }
 234
 235     template<class InputIterator1, class InputIterator2, class BinaryPredicate>
 236     pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1,
 237                                                   InputIterator2 first2, BinaryPredicate pred)
 238     {
 239         while (first1 != last1 && pred(*first1, *first2))
 240         {
 241             ++first1;
 242             ++first2;
 243         }
 244
 245         return make_pair(first1, first2);
 246     }
 247
 248     template<class InputIterator1, class InputIterator2>
 249     pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1,
 250                                                   InputIterator2 first2, InputIterator2 last2)
 251     {
 252         while (first1 != last1 && first2 != last2 && *first1 == *first2)
 253         {
 254             ++first1;
 255             ++first2;
 256         }
 257
 258         return make_pair(first1, first2);
 259     }
 260
 261     template<class InputIterator1, class InputIterator2, class BinaryPredicate>
 262     pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1,
 263                                                   InputIterator2 first2, InputIterator2 last2,
 264                                                   BinaryPredicate pred)
 265     {
 266         while (first1 != last1 && first2 != last2 && pred(*first1, *first2))
 267         {
 268             ++first1;
 269             ++first2;
 270         }
 271
 272         return make_pair(first1, first2);
 273     }
 274
 275     /**
 276      * 25.2.11, equal:
 277      */
 278
 279     template<class InputIterator1, class InputIterator2>
 280     bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
 281     {
 282         while (first1 != last1)
 283         {
 284             if (*first1++ != *first2++)
 285                 return false;
 286         }
 287
 288         return true;
 289     }
 290
 291     template<class InputIterator1, class InputIterator2>
 292     bool equal(InputIterator1 first1, InputIterator1 last1,
 293                InputIterator2 first2, InputIterator2 last2)
 294     {
 295         while (first1 != last1 && first2 != last2)
 296         {
 297             if (*first1++ != *first2++)
 298                 return false;
 299         }
 300
 301         return true;
 302     }
 303
 304     template<class InputIterator1, class InputIterator2, class BinaryPredicate>
 305     bool equal(InputIterator1 first1, InputIterator1 last1,
 306                InputIterator2 first2, BinaryPredicate pred)
 307     {
 308         while (first1 != last1)
 309         {
 310             if (!pred(*first1++, *first2++))
 311                 return false;
 312         }
 313
 314         return true;
 315     }
 316
 317     template<class InputIterator1, class InputIterator2, class BinaryPredicate>
 318     bool equal(InputIterator1 first1, InputIterator1 last1,
 319                InputIterator2 first2, InputIterator2 last2,
 320                BinaryPredicate pred)
 321     {
 322         while (first1 != last1 && first2 != last2)
 323         {
 324             if (!pred(*first1++, *first2++))
 325                 return false;
 326         }
 327
 328         return true;
 329     }
 330
 331     /**
 332      * 25.2.12, is_permutation:
 333      */
 334
 335     // TODO: implement
 336
 337     /**
 338      * 25.2.13, search:
 339      */
 340
 341     // TODO: implement
 342
 343     /**
 344      * 25.3, mutating sequence operations:
 345      */
 346
 347     /**
 348      * 25.3.1, copy:
 349      */
 350
 351     template<class InputIterator, class OutputIterator>
 352     OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result)
 353     {
 354         while (first != last)
 355             *result++ = *first++;
 356
 357         return result;
 358     }
 359
 360     template<class InputIterator, class Size, class OutputIterator>
 361     OutputIterator copy_n(InputIterator first, Size count, OutputIterator result)
 362     {
 363         for (Size i = 0; i < count; ++i, ++first, ++result)
 364             *result = *first;
 365
 366         return result;
 367     }
 368
 369     template<class InputIterator, class OutputIterator, class Predicate>
 370     OutputIterator copy_if(InputIterator first, InputIterator last,
 371                            OutputIterator result, Predicate pred)
 372     {
 373         while (first != last)
 374         {
 375             if (pred(*first))
 376                 *result++ = *first;
 377             ++first;
 378         }
 379
 380         return result;
 381     }
 382
 383     template<class BidirectionalIterator1, class BidirectionalIterator2>
 384     BidirectionalIterator2 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
 385                                          BidirectionalIterator2 result)
 386     {
 387         // Note: We're copying [first, last) so we need to skip the initial value of last.
 388         while (last-- != first)
 389             *result-- = *last;
 390
 391         return result;
 392     }
 393
 394     /**
 395      * 25.3.2, move:
 396      */
 397
 398     template<class InputIterator, class OutputIterator>
 399     OutputIterator move(InputIterator first, InputIterator last, OutputIterator result)
 400     {
 401         while (first != last)
 402             *result++ = move(*first++);
 403
 404         return result;
 405     }
 406
 407     template<class BidirectionalIterator1, class BidirectionalIterator2>
 408     BidirectionalIterator2 move_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
 409                                          BidirectionalIterator2 result)
 410     {
 411         // Note: We're copying [first, last) so we need to skip the initial value of last.
 412         while (last-- != first)
 413             *result-- = move(*last);
 414     }
 415
 416     /**
 417      * 25.3.3, swap:
 418      */
 419
 420     template<class ForwardIterator1, class ForwardIterator2>
 421     ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1,
 422                                  ForwardIterator2 first2)
 423     {
 424         while (first1 != last1)
 425             swap(*first1++, *first2++);
 426
 427         return first2;
 428     }
 429
 430     template<class ForwardIterator1, class ForwardIterator2>
 431     void iter_swap(ForwardIterator1 iter1, ForwardIterator2 iter2)
 432     {
 433         swap(*iter1, *iter2);
 434     }
 435
 436     /**
 437      * 25.3.4, transform:
 438      */
 439
 440     template<class InputIterator, class OutputIterator, class UnaryOperation>
 441     OutputIterator transform(InputIterator first, InputIterator last,
 442                              OutputIterator result, UnaryOperation op)
 443     {
 444         while (first != last)
 445             *result++ = op(*first++);
 446
 447         return result;
 448     }
 449
 450     template<class InputIterator1, class InputIterator2,
 451              class OutputIterator, class BinaryOperation>
 452     OutputIterator transform(InputIterator1 first1, InputIterator1 last1,
 453                              InputIterator2 first2, OutputIterator result,
 454                              BinaryOperation op)
 455     {
 456         while (first1 != last1)
 457             *result++ = op(*first1++, *first2++);
 458
 459         return result;
 460     }
 461
 462     /**
 463      * 25.3.5, replace:
 464      */
 465
 466     template<class ForwardIterator, class T>
 467     void replace(ForwardIterator first, ForwardIterator last,
 468                  const T& old_value, const T& new_value)
 469     {
 470         while (first != last)
 471         {
 472             if (*first == old_value)
 473                 *first = new_value;
 474             ++first;
 475         }
 476     }
 477
 478     template<class ForwardIterator, class Predicate, class T>
 479     void replace_if(ForwardIterator first, ForwardIterator last,
 480                     Predicate pred, const T& new_value)
 481     {
 482         while (first != last)
 483         {
 484             if (pred(*first))
 485                 *first = new_value;
 486             ++first;
 487         }
 488     }
 489
 490     template<class InputIterator, class OutputIterator, class T>
 491     OutputIterator replace_copy(InputIterator first, InputIterator last,
 492                                 OutputIterator result, const T& old_value,
 493                                 const T& new_value)
 494     {
 495         while (first != last)
 496         {
 497             if (*first == old_value)
 498                 *result = new_value;
 499             else
 500                 *result = *first;
 501
 502             ++first;
 503             ++result;
 504         }
 505     }
 506
 507     template<class InputIterator, class OutputIterator, class Predicate, class T>
 508     OutputIterator replace_copy_if(InputIterator first, InputIterator last,
 509                                 OutputIterator result, Predicate pred,
 510                                 const T& new_value)
 511     {
 512         while (first != last)
 513         {
 514             if (pred(*first))
 515                 *result = new_value;
 516             else
 517                 *result = *first;
 518
 519             ++first;
 520             ++result;
 521         }
 522     }
 523
 524     /**
 525      * 25.3.6, fill:
 526      */
 527
 528     template<class ForwardIterator, class T>
 529     void fill(ForwardIterator first, ForwardIterator last, const T& value)
 530     {
 531         while (first != last)
 532             *first++ = value;
 533     }
 534
 535     template<class InputIterator, class Size, class T>
 536     void fill_n(InputIterator first, Size count, const T& value)
 537     {
 538         for (Size i = 0; i < count; ++i)
 539             *first++ = value;
 540     }
 541
 542     /**
 543      * 25.3.7, generate:
 544      */
 545
 546     template<class ForwardIterator, class Generator>
 547     void generate(ForwardIterator first, ForwardIterator last,
 548                   Generator gen)
 549     {
 550         while (first != last)
 551             *first++ = gen();
 552     }
 553
 554     template<class OutputIterator, class Size, class Generator>
 555     void generate(OutputIterator first, Size count, Generator gen)
 556     {
 557         for (Size i = 0; i < count; ++i)
 558             *first++ = gen();
 559     }
 560
 561     /**
 562      * 25.3.8, remove:
 563      */
 564
 565     template<class ForwardIterator, class T>
 566     ForwardIterator remove(ForwardIterator first, ForwardIterator last,
 567                            const T& value)
 568     {
 569         auto it = first;
 570         while (it != last)
 571         {
 572             if (*it != value)
 573                 *first++ = move(*it);
 574         }
 575
 576         return first;
 577     }
 578
 579     template<class ForwardIterator, class Predicate>
 580     ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,
 581                               Predicate pred)
 582     {
 583         auto it = first;
 584         while (it != last)
 585         {
 586             if (!pred(*it))
 587                 *first++ = move(*it);
 588         }
 589
 590         return first;
 591     }
 592
 593     template<class InputIterator, class OutputIterator, class T>
 594     OutputIterator remove_copy(InputIterator first, InputIterator last,
 595                                OutputIterator result, const T& value)
 596     {
 597         while (first != last)
 598         {
 599             if (*first != value)
 600                 *result++ = *first;
 601             ++first;
 602         }
 603
 604         return result;
 605     }
 606
 607     template<class InputIterator, class OutputIterator, class Predicate>
 608     OutputIterator remove_copy_if(InputIterator first, InputIterator last,
 609                                   OutputIterator result, Predicate pred)
 610     {
 611         while (first != last)
 612         {
 613             if (!pred(*first))
 614                 *result++ = *first;
 615             ++first;
 616         }
 617
 618         return result;
 619     }
 620
 621     /**
 622      * 25.3.9, unique:
 623      */
 624
 625     // TODO: implement
 626
 627     /**
 628      * 25.3.10, reverse:
 629      */
 630
 631     template<class BidirectionalIterator>
 632     void reverse(BidirectionalIterator first, BidirectionalIterator last)
 633     {
 634         if (first == last)
 635             return;
 636         auto mid_count = (last - first) / 2;
 637
 638         --last;
 639         for (decltype(mid_count) i = 0; i < mid_count; ++i)
 640             iter_swap(first++, last--);
 641     }
 642
 643     template<class BidirectionalIterator, class OutputIterator>
 644     OutputIterator reverse_copy(BidirectionalIterator first,
 645                                 BidirectionalIterator last,
 646                                 OutputIterator result)
 647     {
 648         while (--last != first)
 649             *result++ = *last;
 650     }
 651
 652     /**
 653      * 25.3.11, rotate:
 654      */
 655
 656     // TODO: implement
 657
 658     /**
 659      * 25.3.12, shuffle:
 660      */
 661
 662     // TODO: implement
 663
 664     /**
 665      * 25.3.13, partitions:
 666      */
 667
 668     // TODO: implement
 669
 670     /**
 671      * 25.4, sorting and related operations:
 672      */
 673
 674     /**
 675      * 25.4.1, sorting:
 676      */
 677
 678     /**
 679      * 25.4.1.1, sort:
 680      */
 681
 682     template<class RandomAccessIterator, class Compare>
 683     void make_heap(RandomAccessIterator, RandomAccessIterator,
 684                    Compare);
 685
 686     template<class RandomAccessIterator, class Compare>
 687     void sort_heap(RandomAccessIterator, RandomAccessIterator,
 688                    Compare);
 689
 690     template<class RandomAccessIterator>
 691     void sort(RandomAccessIterator first, RandomAccessIterator last)
 692     {
 693         using value_type = typename iterator_traits<RandomAccessIterator>::value_type;
 694
 695         sort(first, last, less<value_type>{});
 696     }
 697
 698     template<class RandomAccessIterator, class Compare>
 699     void sort(RandomAccessIterator first, RandomAccessIterator last,
 700               Compare comp)
 701     {
 702         /**
 703          * Note: This isn't the most effective approach,
 704          *       but since we already have these two functions
 705          *       and they satisfy asymptotic limitations
 706          *       imposed by the standard, we're using them at
 707          *       the moment. Might be good to change it to qsort
 708          *       or merge sort later.
 709          */
 710
 711         make_heap(first, last, comp);
 712         sort_heap(first, last, comp);
 713     }
 714
 715     /**
 716      * 25.4.1.2, stable_sort:
 717      */
 718
 719     // TODO: implement
 720
 721     /**
 722      * 25.4.1.3, partial_sort:
 723      */
 724
 725     // TODO: implement
 726
 727     /**
 728      * 25.4.1.4, partial_sort_copy:
 729      */
 730
 731     // TODO: implement
 732
 733     /**
 734      * 25.4.1.5, is_sorted:
 735      */
 736
 737     template<class ForwardIterator>
 738     bool is_sorted(ForwardIterator first, ForwardIterator last)
 739     {
 740         return is_sorted_until(first, last) == last;
 741     }
 742
 743     template<class ForwardIterator, class Comp>
 744     bool is_sorted(ForwardIterator first, ForwardIterator last,
 745                    Comp comp)
 746     {
 747         return is_sorted_until(first, last, comp) == last;
 748     }
 749
 750     template<class ForwardIterator>
 751     ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last)
 752     {
 753         if (distance(first, last) < 2)
 754             return last;
 755
 756         while (first != last)
 757         {
 758             if (*first > *(++first))
 759                 return first;
 760         }
 761
 762         return last;
 763     }
 764
 765     template<class ForwardIterator, class Comp>
 766     ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last,
 767                                     Comp comp)
 768     {
 769         if (distance(first, last) < 2)
 770             return last;
 771
 772         while (first != last)
 773         {
 774             if (!comp(*first, *(++first)))
 775                 return first;
 776         }
 777
 778         return last;
 779     }
 780
 781     /**
 782      * 25.4.2, nth_element:
 783      */
 784
 785     // TODO: implement
 786
 787     /**
 788      * 25.4.3, binary search:
 789      */
 790
 791     /**
 792      * 25.4.3.1, lower_bound
 793      */
 794
 795     // TODO: implement
 796
 797     /**
 798      * 25.4.3.2, upper_bound
 799      */
 800
 801     // TODO: implement
 802
 803     /**
 804      * 25.4.3.3, equal_range:
 805      */
 806
 807     // TODO: implement
 808
 809     /**
 810      * 25.4.3.4, binary_search:
 811      */
 812
 813     // TODO: implement
 814
 815     /**
 816      * 25.4.4, merge:
 817      */
 818
 819     // TODO: implement
 820
 821     /**
 822      * 25.4.5, set operations on sorted structures:
 823      */
 824
 825     /**
 826      * 25.4.5.1, includes:
 827      */
 828
 829     // TODO: implement
 830
 831     /**
 832      * 25.4.5.2, set_union:
 833      */
 834
 835     // TODO: implement
 836
 837     /**
 838      * 25.4.5.3, set_intersection:
 839      */
 840
 841     // TODO: implement
 842
 843     /**
 844      * 25.4.5.4, set_difference:
 845      */
 846
 847     // TODO: implement
 848
 849     /**
 850      * 25.4.5.5, set_symmetric_difference:
 851      */
 852
 853     // TODO: implement
 854
 855     /**
 856      * 25.4.6, heap operations:
 857      */
 858
 859     namespace aux
 860     {
 861         template<class T>
 862         T heap_parent(T idx)
 863         {
 864             return (idx - 1) / 2;
 865         }
 866
 867         template<class T>
 868         T heap_left_child(T idx)
 869         {
 870             return 2 * idx + 1;
 871         }
 872
 873         template<class T>
 874         T heap_right_child(T idx)
 875         {
 876             return 2 * idx + 2;
 877         }
 878
 879         template<class RandomAccessIterator, class Size, class Compare>
 880         void correct_children(RandomAccessIterator first,
 881                               Size idx, Size count, Compare comp)
 882         {
 883             using aux::heap_left_child;
 884             using aux::heap_right_child;
 885
 886             auto left = heap_left_child(idx);
 887             auto right = heap_right_child(idx);
 888
 889             bool left_incorrect{comp(first[idx], first[left])};
 890             bool right_incorrect{comp(first[idx], first[right])};
 891             while ((left < count && left_incorrect) ||
 892                    (right < count && right_incorrect))
 893             {
 894                 if (right >= count || (left_incorrect && comp(first[right], first[left])))
 895                 {
 896                     swap(first[idx], first[left]);
 897
 898                     idx = left;
 899                 }
 900                 else if (right < count && right_incorrect)
 901                 {
 902                     swap(first[idx], first[right]);
 903
 904                     idx = right;
 905                 } // Else should not happen because of the while condition.
 906
 907                 left = heap_left_child(idx);
 908                 right = heap_right_child(idx);
 909
 910                 left_incorrect = comp(first[idx], first[left]);
 911                 right_incorrect = comp(first[idx], first[right]);
 912             }
 913         }
 914     }
 915
 916     /**
 917      * 25.4.6.1, push_heap:
 918      */
 919
 920     template<class RandomAccessIterator>
 921     void push_heap(RandomAccessIterator first,
 922                    RandomAccessIterator last)
 923     {
 924         using value_type = typename iterator_traits<RandomAccessIterator>::value_type;
 925
 926         push_heap(first, last, less<value_type>{});
 927     }
 928
 929     template<class RandomAccessIterator, class Compare>
 930     void push_heap(RandomAccessIterator first,
 931                    RandomAccessIterator last,
 932                    Compare comp)
 933     {
 934         using aux::heap_parent;
 935
 936         auto count = distance(first, last);
 937         if (count <= 1)
 938             return;
 939
 940         auto idx = count - 1;
 941         auto parent = heap_parent(idx);
 942         while (idx > 0 && comp(first[parent], first[idx]))
 943         {
 944             swap(first[idx], first[parent]);
 945
 946             idx = parent;
 947             parent = heap_parent(idx);
 948         }
 949     }
 950
 951     /**
 952      * 25.4.6.2, pop_heap:
 953      */
 954
 955     template<class RandomAccessIterator>
 956     void pop_heap(RandomAccessIterator first,
 957                   RandomAccessIterator last)
 958     {
 959         using value_type = typename iterator_traits<RandomAccessIterator>::value_type;
 960
 961         pop_heap(first, last, less<value_type>{});
 962     }
 963
 964     template<class RandomAccessIterator, class Compare>
 965     void pop_heap(RandomAccessIterator first,
 966                   RandomAccessIterator last,
 967                   Compare comp)
 968     {
 969         auto count = distance(first, last);
 970         if (count <= 1)
 971             return;
 972
 973         swap(first[0], first[count - 1]);
 974         aux::correct_children(first, decltype(count){}, count - 2, comp);
 975     }
 976
 977     /**
 978      * 25.4.6.3, make_heap:
 979      */
 980
 981     template<class RandomAccessIterator>
 982     void make_heap(RandomAccessIterator first,
 983                    RandomAccessIterator last)
 984     {
 985         using value_type = typename iterator_traits<RandomAccessIterator>::value_type;
 986
 987         make_heap(first, last, less<value_type>{});
 988     }
 989
 990     template<class RandomAccessIterator, class Compare>
 991     void make_heap(RandomAccessIterator first,
 992                    RandomAccessIterator last,
 993                    Compare comp)
 994     {
 995         auto count = distance(first, last);
 996         if (count <= 1)
 997             return;
 998
 999         for (auto i = count; i > 0; --i)
1000         {
1001             auto idx = i - 1;
1002
1003             aux::correct_children(first, idx, count, comp);
1004         }
1005     }
1006
1007     /**
1008      * 25.4.6.4, sort_heap:
1009      */
1010
1011     template<class RandomAccessIterator>
1012     void sort_heap(RandomAccessIterator first,
1013                    RandomAccessIterator last)
1014     {
1015         using value_type = typename iterator_traits<RandomAccessIterator>::value_type;
1016
1017         sort_heap(first, last, less<value_type>{});
1018     }
1019
1020     template<class RandomAccessIterator, class Compare>
1021     void sort_heap(RandomAccessIterator first,
1022                    RandomAccessIterator last,
1023                    Compare comp)
1024     {
1025         while (first != last)
1026             pop_heap(first, last--, comp);
1027     }
1028
1029     /**
1030      * 25.4.6.5, is_heap:
1031      */
1032
1033     template<class RandomAccessIterator>
1034     auto is_heap_until(RandomAccessIterator first, RandomAccessIterator last)
1035     {
1036         using value_type = typename iterator_traits<RandomAccessIterator>::value_type;
1037
1038         return is_heap_until(first, last, less<value_type>{});
1039     }
1040
1041     template<class RandomAccessIterator, class Compare>
1042     auto is_heap_until(RandomAccessIterator first, RandomAccessIterator last,
1043                        Compare comp)
1044     {
1045         using aux::heap_left_child;
1046         using aux::heap_right_child;
1047
1048         auto count = distance(first, last);
1049         if (count < 2)
1050             return last;
1051
1052         auto res = first;
1053         for (decltype(count) idx = 0; idx < count; ++idx)
1054         {
1055             auto left = heap_left_child(idx);
1056             auto right = heap_right_child(idx);
1057
1058             if (left < count && comp(first[idx], first[left]))
1059                 return res;
1060             if (right < count && comp(first[idx], first[right]))
1061                 return res;
1062
1063             ++res;
1064         }
1065
1066         return res;
1067     }
1068
1069     template<class RandomAccessIterator>
1070     bool is_heap(RandomAccessIterator first, RandomAccessIterator last)
1071     {
1072         return is_heap_until(first, last) == last;
1073     }
1074
1075     template<class RandomAccessIterator, class Compare>
1076     bool is_heap(RandomAccessIterator first, RandomAccessIterator last,
1077                  Compare comp)
1078     {
1079         return is_heap_until(first, last, comp) == last;
1080     }
1081
1082     /**
1083      * 25.4.7, minimum and maximum:
1084      * // TODO: implement container versions when we have
1085      *          numeric limits and min/max element
1086      * // TODO: versions with comparators
1087      * // TODO: minmax
1088      */
1089
1090     template<class T>
1091     constexpr const T& min(const T& lhs, const T& rhs)
1092     {
1093         return (lhs < rhs) ? lhs : rhs;
1094     }
1095
1096     template<class T>
1097     constexpr const T& max(const T& lhs, const T& rhs)
1098     {
1099         return (lhs > rhs) ? lhs : rhs;
1100     }
1101
1102     /**
1103      * 25.4.8, lexicographical comparison:
1104      */
1105
1106     template<class InputIterator1, class InputIterator2>
1107     bool lexicographical_compare(InputIterator1 first1,
1108                                  InputIterator1 last1,
1109                                  InputIterator2 first2,
1110                                  InputIterator2 last2)
1111     {
1112         while ((first1 != last1) && (first2 != last2))
1113         {
1114             if (*first1 < *first2)
1115                 return true;
1116             if (*first2 < *first1)
1117                 return false;
1118
1119             ++first1;
1120             ++first2;
1121         }
1122
1123         /**
1124          * Up until now they are same, so we have to check
1125          * if we reached the end on one.
1126          */
1127         return (first1 == last1) && (first2 != last2);
1128     }
1129
1130     template<class InputIterator1, class InputIterator2, class Compare>
1131     bool lexicographical_compare(InputIterator1 first1,
1132                                  InputIterator1 last1,
1133                                  InputIterator2 first2,
1134                                  InputIterator2 last2,
1135                                  Compare comp)
1136     {
1137         while ((first1 != last1) && (first2 != last2))
1138         {
1139             if (comp(*first1, *first2))
1140                 return true;
1141             if (comp(*first2, *first1))
1142                 return false;
1143
1144             ++first1;
1145             ++first2;
1146         }
1147
1148         /**
1149          * Up until now they are same, so we have to check
1150          * if we reached the end on one.
1151          */
1152         return (first1 == last1) && (first2 != last2);
1153     }
1154
1155     /**
1156      * 25.4.9, permutation generators:
1157      */
1158
1159     // TODO: implement
1160 }
1161
1162 #endif