source: mainline/uspace/lib/cpp/include/__bits/algorithm.hpp@ a95e75e

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since a95e75e was b57a3ee, checked in by Dzejrou <dzejrou@…>, 7 years ago

cpp: refactored the library layout, everything from the impl directory was moved to the bits directory for the sake of consistency, updated copyright notices and include guards
  • Property mode set to 100644
File size: 28.5 KB
Line 
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
35namespace 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 /**
1113 * *first1 and *first2 can have different types
1114 * so we use a transparent comparator.
1115 */
1116 return lexicographical_compare(
1117 first1, last1, first2, last2,
1118 less<void>{}
1119 );
1120 }
1121
1122 template<class InputIterator1, class InputIterator2, class Compare>
1123 bool lexicographical_compare(InputIterator1 first1,
1124 InputIterator1 last1,
1125 InputIterator2 first2,
1126 InputIterator2 last2,
1127 Compare comp)
1128 {
1129 while ((first1 != last1) && (first2 != last2))
1130 {
1131 if (comp(*first1, *first2))
1132 return true;
1133 if (comp(*first2, *first1))
1134 return false;
1135
1136 ++first1;
1137 ++first2;
1138 }
1139
1140 /**
1141 * Up until now they are same, so we have to check
1142 * if we reached the end on one.
1143 */
1144 return (first1 == last1) && (first2 != last2);
1145 }
1146
1147 /**
1148 * 25.4.9, permutation generators:
1149 */
1150
1151 // TODO: implement
1152}
1153
1154#endif
Note: See TracBrowser for help on using the repository browser.