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

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

cpp: fixed minor bugs
  • Property mode set to 100644
File size: 20.2 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 /**
38 * 25.2, non-modyfing sequence operations:
39 */
40
41 /**
42 * 25.2.1, all_of:
43 */
44
45 template<class InputIterator, class Predicate>
46 bool all_of(InputIterator first, InputIterator last, Predicate pred)
47 {
48 while (first != last)
49 {
50 if (!pred(*first++))
51 return false;
52 }
53
54 return true;
55 }
56
57 /**
58 * 25.2.2, any_of:
59 */
60
61 template<class InputIterator, class Predicate>
62 bool any_of(InputIterator first, InputIterator last, Predicate pred)
63 {
64 while (first != last)
65 {
66 if (pred(*first++))
67 return true;
68 }
69
70 return false;
71 }
72
73 /**
74 * 25.2.3, none_of:
75 */
76
77 template<class InputIterator, class Predicate>
78 bool none_of(InputIterator first, InputIterator last, Predicate pred)
79 {
80 return !any_of(first, last, pred);
81 }
82
83 /**
84 * 25.2.4, for_each:
85 */
86
87 // TODO: Function has to be MoveConstructible
88 template<class InputIterator, class Function>
89 Function for_each(InputIterator first, InputIterator last, Function f)
90 {
91 while (first != last)
92 f(*first++);
93
94 return move(f);
95 }
96
97 /**
98 * 25.2.5, find:
99 */
100
101 template<class InputIterator, class T>
102 InputIterator find(InputIterator first, InputIterator last, const T& value)
103 {
104 while (first != last)
105 {
106 if (*first == value)
107 return first;
108 ++first;
109 }
110
111 return last;
112 }
113
114 template<class InputIterator, class Predicate>
115 InputIterator find_if(InputIterator first, InputIterator last, Predicate pred)
116 {
117 while (first != last)
118 {
119 if (pred(*first))
120 return first;
121 ++first;
122 }
123
124 return last;
125 }
126
127 template<class InputIterator, class Predicate>
128 InputIterator find_if_not(InputIterator first, InputIterator last, Predicate pred)
129 {
130 while (first != last)
131 {
132 if (!pred(*first))
133 return first;
134 ++first;
135 }
136
137 return last;
138 }
139
140 /**
141 * 25.2.6, find_end:
142 */
143
144 // TODO: implement
145
146 /**
147 * 25.2.7, find_first:
148 */
149
150 // TODO: implement
151
152 /**
153 * 25.2.8, adjacent_find:
154 */
155
156 template<class ForwardIterator>
157 ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last)
158 {
159 while (first != last)
160 {
161 if (*first == *(first + 1))
162 return first;
163 ++first;
164 }
165
166 return last;
167 }
168
169 template<class ForwardIterator, class Predicate>
170 ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, Predicate pred)
171 {
172 while (first != last)
173 {
174 if (pred(*first, *(first + 1)))
175 return first;
176 ++first;
177 }
178
179 return last;
180 }
181
182 /**
183 * 25.2.9, count:
184 */
185
186 template<class InputIterator, class T>
187 typename iterator_traits<InputIterator>::difference_type
188 count(InputIterator first, InputIterator last, const T& value)
189 {
190 typename iterator_traits<InputIterator>::difference_type cnt{};
191
192 while (first != last)
193 {
194 if (*first++ == value)
195 ++cnt;
196 }
197
198 return cnt;
199 }
200
201 template<class InputIterator, class Predicate>
202 typename iterator_traits<InputIterator>::difference_type
203 count(InputIterator first, InputIterator last, Predicate pred)
204 {
205 typename iterator_traits<InputIterator>::difference_type cnt{};
206
207 while (first != last)
208 {
209 if (pred(*first++))
210 ++cnt;
211 }
212
213 return cnt;
214 }
215
216 /**
217 * 25.2.10, mismatch:
218 */
219
220 template<class InputIterator1, class InputIterator2>
221 pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1,
222 InputIterator2 first2)
223 {
224 while (first1 != last1 && *first1++ == *first2++)
225 { /* DUMMY BODY */ }
226
227 return make_pair(first1, first2);
228 }
229
230 template<class InputIterator1, class InputIterator2, class BinaryPredicate>
231 pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1,
232 InputIterator2 first2, BinaryPredicate pred)
233 {
234 while (first1 != last1 && pred(*first1++, *first2++))
235 { /* DUMMY BODY */ }
236
237 return make_pair(first1, first2);
238 }
239
240 template<class InputIterator1, class InputIterator2>
241 pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1,
242 InputIterator2 first2, InputIterator2 last2)
243 {
244 while (first1 != last1 && first2 != last2 && *first1++ == *first2++)
245 { /* DUMMY BODY */ }
246
247 return make_pair(first1, first2);
248 }
249
250 template<class InputIterator1, class InputIterator2, class BinaryPredicate>
251 pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1,
252 InputIterator2 first2, InputIterator2 last2,
253 BinaryPredicate pred)
254 {
255 while (first1 != last1 && first2 != last2 && pred(*first1++, *first2++))
256 { /* DUMMY BODY */ }
257
258 return make_pair(first1, first2);
259 }
260
261 /**
262 * 25.2.11, equal:
263 */
264
265 template<class InputIterator1, class InputIterator2>
266 bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
267 {
268 auto last2 = first2 + (last1 - first1);
269
270 return equal(first1, last1, first2, last2);
271 }
272
273 template<class InputIterator1, class InputIterator2>
274 bool equal(InputIterator1 first1, InputIterator1 last1,
275 InputIterator2 first2, InputIterator2 last2)
276 {
277 if ((last1 - first1) != (last2 - first2))
278 return false;
279
280 while (first1 != last1)
281 {
282 if (*first1++ != *first2++)
283 return false;
284 }
285
286 return true;
287 }
288
289 template<class InputIterator1, class InputIterator2, class BinaryPredicate>
290 bool equal(InputIterator1 first1, InputIterator1 last1,
291 InputIterator2 first2, BinaryPredicate pred)
292 {
293 auto last2 = first2 + (last1 - first1);
294
295 return equal(first1, last1, first2, last2, pred);
296 }
297
298 template<class InputIterator1, class InputIterator2, class BinaryPredicate>
299 bool equal(InputIterator1 first1, InputIterator1 last1,
300 InputIterator2 first2, InputIterator2 last2,
301 BinaryPredicate pred)
302 {
303 if ((last1 - first1) != (last2 - first2))
304 return false;
305
306 while (first1 != last1)
307 {
308 if (!pred(*first1++, *first2++))
309 return false;
310 }
311
312 return true;
313 }
314
315 /**
316 * 25.2.12, is_permutation:
317 */
318
319 // TODO: implement
320
321 /**
322 * 25.2.13, search:
323 */
324
325 // TODO: implement
326
327 /**
328 * 25.3, mutating sequence operations:
329 */
330
331 /**
332 * 25.3.1, copy:
333 */
334
335 template<class InputIterator, class OutputIterator>
336 OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result)
337 {
338 while (first != last)
339 *result++ = first++;
340
341 return result;
342 }
343
344 template<class InputIterator, class Size, class OutputIterator>
345 OutputIterator copy_n(InputIterator first, Size count, OutputIterator result)
346 {
347 for (Size i = 0; i < count; ++i, ++first, ++result)
348 *result = *first;
349
350 return result;
351 }
352
353 template<class InputIterator, class OutputIterator, class Predicate>
354 OutputIterator copy_if(InputIterator first, InputIterator last,
355 OutputIterator result, Predicate pred)
356 {
357 while (first != last)
358 {
359 if (pred(*first))
360 *result++ = *first;
361 ++first;
362 }
363
364 return result;
365 }
366
367 template<class BidirectionalIterator1, class BidirectionalIterator2>
368 BidirectionalIterator2 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
369 BidirectionalIterator2 result)
370 {
371 // Note: We're copying [first, last) so we need to skip the initial value of last.
372 while (last-- != first)
373 *result-- = *last;
374 }
375
376 /**
377 * 25.3.2, move:
378 */
379
380 template<class InputIterator, class OutputIterator>
381 OutputIterator move(InputIterator first, InputIterator last, OutputIterator result)
382 {
383 while (first != last)
384 *result++ = move(first++);
385
386 return result;
387 }
388
389 template<class BidirectionalIterator1, class BidirectionalIterator2>
390 BidirectionalIterator2 move_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
391 BidirectionalIterator2 result)
392 {
393 // Note: We're copying [first, last) so we need to skip the initial value of last.
394 while (last-- != first)
395 *result-- = move(*last);
396 }
397
398 /**
399 * 25.3.3, swap:
400 */
401
402 template<class ForwardIterator1, class ForwardIterator2>
403 ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1,
404 ForwardIterator2 first2)
405 {
406 while (first1 != last1)
407 swap(*first1++, *first2++);
408
409 return first2;
410 }
411
412 template<class ForwardIterator1, class ForwardIterator2>
413 void iter_swap(ForwardIterator1 iter1, ForwardIterator2 iter2)
414 {
415 swap(*iter1, *iter2);
416 }
417
418 /**
419 * 25.3.4, transform:
420 */
421
422 template<class InputIterator, class OutputIterator, class UnaryOperation>
423 OutputIterator transform(InputIterator first, InputIterator last,
424 OutputIterator result, UnaryOperation op)
425 {
426 while (first != last)
427 *result++ = op(*first++);
428 }
429
430 template<class InputIterator1, class InputIterator2,
431 class OutputIterator, class BinaryOperation>
432 OutputIterator transform(InputIterator1 first1, InputIterator1 last1,
433 InputIterator2 first2, OutputIterator result,
434 BinaryOperation op)
435 {
436 while (first1 != last1)
437 *result++ = op(*first1++, *first2++);
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 // TODO: implement
661
662 /**
663 * 25.4.1.2, stable_sort:
664 */
665
666 // TODO: implement
667
668 /**
669 * 25.4.1.3, partial_sort:
670 */
671
672 // TODO: implement
673
674 /**
675 * 25.4.1.4, partial_sort_copy:
676 */
677
678 // TODO: implement
679
680 /**
681 * 25.4.1.5, is_sorted:
682 */
683
684 template<class ForwardIterator>
685 bool is_sorted(ForwardIterator first, ForwardIterator last)
686 {
687 return is_sorted_until(first, last) == last;
688 }
689
690 template<class ForwardIterator, class Comp>
691 bool is_sorted(ForwardIterator first, ForwardIterator last,
692 Comp comp)
693 {
694 return is_sorted_until(first, last, comp) == last;
695 }
696
697 template<class ForwardIterator>
698 ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last)
699 {
700 if (distance(first, last) < 2)
701 return last;
702
703 while (first != last)
704 {
705 if (*first > *(++first))
706 return first;
707 }
708
709 return last;
710 }
711
712 template<class ForwardIterator, class Comp>
713 ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last,
714 Comp comp)
715 {
716 if (distance(first, last) < 2)
717 return last;
718
719 while (first != last)
720 {
721 if (!comp(*first, *(++first)))
722 return first;
723 }
724
725 return last;
726 }
727
728 /**
729 * 25.4.2, nth_element:
730 */
731
732 // TODO: implement
733
734 /**
735 * 25.4.3, binary search:
736 */
737
738 /**
739 * 25.4.3.1, lower_bound
740 */
741
742 // TODO: implement
743
744 /**
745 * 25.4.3.2, upper_bound
746 */
747
748 // TODO: implement
749
750 /**
751 * 25.4.3.3, equal_range:
752 */
753
754 // TODO: implement
755
756 /**
757 * 25.4.3.4, binary_search:
758 */
759
760 // TODO: implement
761
762 /**
763 * 25.4.4, merge:
764 */
765
766 // TODO: implement
767
768 /**
769 * 25.4.5, set operations on sorted structures:
770 */
771
772 /**
773 * 25.4.5.1, includes:
774 */
775
776 // TODO: implement
777
778 /**
779 * 25.4.5.2, set_union:
780 */
781
782 // TODO: implement
783
784 /**
785 * 25.4.5.3, set_intersection:
786 */
787
788 // TODO: implement
789
790 /**
791 * 25.4.5.4, set_difference:
792 */
793
794 // TODO: implement
795
796 /**
797 * 25.4.5.5, set_symmetric_difference:
798 */
799
800 // TODO: implement
801
802 /**
803 * 25.4.6, heap operations:
804 */
805
806 /**
807 * 25.4.6.1, push_heap:
808 */
809
810 // TODO: implement
811
812 /**
813 * 25.4.6.2, pop_heap:
814 */
815
816 // TODO: implement
817
818 /**
819 * 25.4.6.3, make_heap:
820 */
821
822 // TODO: implement
823
824 /**
825 * 25.4.6.4, sort_heap:
826 */
827
828 // TODO: implement
829
830 /**
831 * 25.4.6.5, is_heap:
832 */
833
834 // TODO: implement
835
836 /**
837 * 25.4.7, minimum and maximum:
838 * // TODO: implement container versions when we have
839 * numeric limits and min/max element
840 * // TODO: versions with comparators
841 * // TODO: minmax
842 */
843
844 template<class T>
845 constexpr const T& min(const T& lhs, const T& rhs)
846 {
847 return (lhs < rhs) ? lhs : rhs;
848 }
849
850 template<class T>
851 constexpr const T& max(const T& lhs, const T& rhs)
852 {
853 return (lhs > rhs) ? lhs : rhs;
854 }
855
856 /**
857 * 25.4.8, lexicographical comparison:
858 */
859
860 // TODO: implement
861
862 /**
863 * 25.4.9, permutation generators:
864 */
865
866 // TODO: implement
867}
868
869#endif
Note: See TracBrowser for help on using the repository browser.