source: mainline/uspace/lib/cpp/include/impl/algorithm.hpp@ a1c35cc

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

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