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

Last change on this file since c6f23a7 was b57ba05, checked in by Jiří Zárevúcky <zarevucky.jiri@…>, 3 years ago

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