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

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

cpp: fixed copy iterator assignment and added a return statement to copy_backward
  • 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 return result;
376 }
377
378 /**
379 * 25.3.2, move:
380 */
381
382 template<class InputIterator, class OutputIterator>
383 OutputIterator move(InputIterator first, InputIterator last, OutputIterator result)
384 {
385 while (first != last)
386 *result++ = move(first++);
387
388 return result;
389 }
390
391 template<class BidirectionalIterator1, class BidirectionalIterator2>
392 BidirectionalIterator2 move_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
393 BidirectionalIterator2 result)
394 {
395 // Note: We're copying [first, last) so we need to skip the initial value of last.
396 while (last-- != first)
397 *result-- = move(*last);
398 }
399
400 /**
401 * 25.3.3, swap:
402 */
403
404 template<class ForwardIterator1, class ForwardIterator2>
405 ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1,
406 ForwardIterator2 first2)
407 {
408 while (first1 != last1)
409 swap(*first1++, *first2++);
410
411 return first2;
412 }
413
414 template<class ForwardIterator1, class ForwardIterator2>
415 void iter_swap(ForwardIterator1 iter1, ForwardIterator2 iter2)
416 {
417 swap(*iter1, *iter2);
418 }
419
420 /**
421 * 25.3.4, transform:
422 */
423
424 template<class InputIterator, class OutputIterator, class UnaryOperation>
425 OutputIterator transform(InputIterator first, InputIterator last,
426 OutputIterator result, UnaryOperation op)
427 {
428 while (first != last)
429 *result++ = op(*first++);
430 }
431
432 template<class InputIterator1, class InputIterator2,
433 class OutputIterator, class BinaryOperation>
434 OutputIterator transform(InputIterator1 first1, InputIterator1 last1,
435 InputIterator2 first2, OutputIterator result,
436 BinaryOperation op)
437 {
438 while (first1 != last1)
439 *result++ = op(*first1++, *first2++);
440 }
441
442 /**
443 * 25.3.5, replace:
444 */
445
446 template<class ForwardIterator, class T>
447 void replace(ForwardIterator first, ForwardIterator last,
448 const T& old_value, const T& new_value)
449 {
450 while (first != last)
451 {
452 if (*first == old_value)
453 *first = new_value;
454 ++first;
455 }
456 }
457
458 template<class ForwardIterator, class Predicate, class T>
459 void replace_if(ForwardIterator first, ForwardIterator last,
460 Predicate pred, const T& new_value)
461 {
462 while (first != last)
463 {
464 if (pred(*first))
465 *first = new_value;
466 ++first;
467 }
468 }
469
470 template<class InputIterator, class OutputIterator, class T>
471 OutputIterator replace_copy(InputIterator first, InputIterator last,
472 OutputIterator result, const T& old_value,
473 const T& new_value)
474 {
475 while (first != last)
476 {
477 if (*first == old_value)
478 *result = new_value;
479 else
480 *result = *first;
481
482 ++first;
483 ++result;
484 }
485 }
486
487 template<class InputIterator, class OutputIterator, class Predicate, class T>
488 OutputIterator replace_copy_if(InputIterator first, InputIterator last,
489 OutputIterator result, Predicate pred,
490 const T& new_value)
491 {
492 while (first != last)
493 {
494 if (pred(*first))
495 *result = new_value;
496 else
497 *result = *first;
498
499 ++first;
500 ++result;
501 }
502 }
503
504 /**
505 * 25.3.6, fill:
506 */
507
508 template<class ForwardIterator, class T>
509 void fill(ForwardIterator first, ForwardIterator last, const T& value)
510 {
511 while (first != last)
512 *first++ = value;
513 }
514
515 template<class InputIterator, class Size, class T>
516 void fill_n(InputIterator first, Size count, const T& value)
517 {
518 for (Size i = 0; i < count; ++i)
519 *first++ = value;
520 }
521
522 /**
523 * 25.3.7, generate:
524 */
525
526 template<class ForwardIterator, class Generator>
527 void generate(ForwardIterator first, ForwardIterator last,
528 Generator gen)
529 {
530 while (first != last)
531 *first++ = gen();
532 }
533
534 template<class OutputIterator, class Size, class Generator>
535 void generate(OutputIterator first, Size count, Generator gen)
536 {
537 for (Size i = 0; i < count; ++i)
538 *first++ = gen();
539 }
540
541 /**
542 * 25.3.8, remove:
543 */
544
545 template<class ForwardIterator, class T>
546 ForwardIterator remove(ForwardIterator first, ForwardIterator last,
547 const T& value)
548 {
549 auto it = first;
550 while (it != last)
551 {
552 if (*it != value)
553 *first++ = move(*it);
554 }
555
556 return first;
557 }
558
559 template<class ForwardIterator, class Predicate>
560 ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,
561 Predicate pred)
562 {
563 auto it = first;
564 while (it != last)
565 {
566 if (!pred(*it))
567 *first++ = move(*it);
568 }
569
570 return first;
571 }
572
573 template<class InputIterator, class OutputIterator, class T>
574 OutputIterator remove_copy(InputIterator first, InputIterator last,
575 OutputIterator result, const T& value)
576 {
577 while (first != last)
578 {
579 if (*first != value)
580 *result++ = *first;
581 ++first;
582 }
583
584 return result;
585 }
586
587 template<class InputIterator, class OutputIterator, class Predicate>
588 OutputIterator remove_copy_if(InputIterator first, InputIterator last,
589 OutputIterator result, Predicate pred)
590 {
591 while (first != last)
592 {
593 if (!pred(*first))
594 *result++ = *first;
595 ++first;
596 }
597
598 return result;
599 }
600
601 /**
602 * 25.3.9, unique:
603 */
604
605 // TODO: implement
606
607 /**
608 * 25.3.10, reverse:
609 */
610
611 template<class BidirectionalIterator>
612 void reverse(BidirectionalIterator first, BidirectionalIterator last)
613 {
614 if (first == last)
615 return;
616 auto mid_count = (last - first) / 2;
617
618 --last;
619 for (decltype(mid_count) i = 0; i < mid_count; ++i)
620 iter_swap(first++, last--);
621 }
622
623 template<class BidirectionalIterator, class OutputIterator>
624 OutputIterator reverse_copy(BidirectionalIterator first,
625 BidirectionalIterator last,
626 OutputIterator result)
627 {
628 while (--last != first)
629 *result++ = *last;
630 }
631
632 /**
633 * 25.3.11, rotate:
634 */
635
636 // TODO: implement
637
638 /**
639 * 25.3.12, shuffle:
640 */
641
642 // TODO: implement
643
644 /**
645 * 25.3.13, partitions:
646 */
647
648 // TODO: implement
649
650 /**
651 * 25.4, sorting and related operations:
652 */
653
654 /**
655 * 25.4.1, sorting:
656 */
657
658 /**
659 * 25.4.1.1, sort:
660 */
661
662 // TODO: implement
663
664 /**
665 * 25.4.1.2, stable_sort:
666 */
667
668 // TODO: implement
669
670 /**
671 * 25.4.1.3, partial_sort:
672 */
673
674 // TODO: implement
675
676 /**
677 * 25.4.1.4, partial_sort_copy:
678 */
679
680 // TODO: implement
681
682 /**
683 * 25.4.1.5, is_sorted:
684 */
685
686 template<class ForwardIterator>
687 bool is_sorted(ForwardIterator first, ForwardIterator last)
688 {
689 return is_sorted_until(first, last) == last;
690 }
691
692 template<class ForwardIterator, class Comp>
693 bool is_sorted(ForwardIterator first, ForwardIterator last,
694 Comp comp)
695 {
696 return is_sorted_until(first, last, comp) == last;
697 }
698
699 template<class ForwardIterator>
700 ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last)
701 {
702 if (distance(first, last) < 2)
703 return last;
704
705 while (first != last)
706 {
707 if (*first > *(++first))
708 return first;
709 }
710
711 return last;
712 }
713
714 template<class ForwardIterator, class Comp>
715 ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last,
716 Comp comp)
717 {
718 if (distance(first, last) < 2)
719 return last;
720
721 while (first != last)
722 {
723 if (!comp(*first, *(++first)))
724 return first;
725 }
726
727 return last;
728 }
729
730 /**
731 * 25.4.2, nth_element:
732 */
733
734 // TODO: implement
735
736 /**
737 * 25.4.3, binary search:
738 */
739
740 /**
741 * 25.4.3.1, lower_bound
742 */
743
744 // TODO: implement
745
746 /**
747 * 25.4.3.2, upper_bound
748 */
749
750 // TODO: implement
751
752 /**
753 * 25.4.3.3, equal_range:
754 */
755
756 // TODO: implement
757
758 /**
759 * 25.4.3.4, binary_search:
760 */
761
762 // TODO: implement
763
764 /**
765 * 25.4.4, merge:
766 */
767
768 // TODO: implement
769
770 /**
771 * 25.4.5, set operations on sorted structures:
772 */
773
774 /**
775 * 25.4.5.1, includes:
776 */
777
778 // TODO: implement
779
780 /**
781 * 25.4.5.2, set_union:
782 */
783
784 // TODO: implement
785
786 /**
787 * 25.4.5.3, set_intersection:
788 */
789
790 // TODO: implement
791
792 /**
793 * 25.4.5.4, set_difference:
794 */
795
796 // TODO: implement
797
798 /**
799 * 25.4.5.5, set_symmetric_difference:
800 */
801
802 // TODO: implement
803
804 /**
805 * 25.4.6, heap operations:
806 */
807
808 /**
809 * 25.4.6.1, push_heap:
810 */
811
812 // TODO: implement
813
814 /**
815 * 25.4.6.2, pop_heap:
816 */
817
818 // TODO: implement
819
820 /**
821 * 25.4.6.3, make_heap:
822 */
823
824 // TODO: implement
825
826 /**
827 * 25.4.6.4, sort_heap:
828 */
829
830 // TODO: implement
831
832 /**
833 * 25.4.6.5, is_heap:
834 */
835
836 // TODO: implement
837
838 /**
839 * 25.4.7, minimum and maximum:
840 * // TODO: implement container versions when we have
841 * numeric limits and min/max element
842 * // TODO: versions with comparators
843 * // TODO: minmax
844 */
845
846 template<class T>
847 constexpr const T& min(const T& lhs, const T& rhs)
848 {
849 return (lhs < rhs) ? lhs : rhs;
850 }
851
852 template<class T>
853 constexpr const T& max(const T& lhs, const T& rhs)
854 {
855 return (lhs > rhs) ? lhs : rhs;
856 }
857
858 /**
859 * 25.4.8, lexicographical comparison:
860 */
861
862 // TODO: implement
863
864 /**
865 * 25.4.9, permutation generators:
866 */
867
868 // TODO: implement
869}
870
871#endif
Note: See TracBrowser for help on using the repository browser.