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

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

cpp: implemented quite a lot of algorithms
  • 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 <utility>
33
34namespace std
35{
36 /**
37 * 25.2, non-modyfing sequence operations:
38 */
39
40 /**
41 * 25.2.1, all_of:
42 */
43
44 template<class InputIterator, class Predicate>
45 bool all_of(InputIterator first, InputIterator last, Predicate pred)
46 {
47 while (first != last)
48 {
49 if (!pred(*first++))
50 return false;
51 }
52
53 return true;
54 }
55
56 /**
57 * 25.2.2, any_of:
58 */
59
60 template<class InputIterator, class Predicate>
61 bool any_of(InputIterator first, InputIterator last, Predicate pred)
62 {
63 while (first != last)
64 {
65 if (pred(*first++))
66 return true;
67 }
68
69 return false;
70 }
71
72 /**
73 * 25.2.3, none_of:
74 */
75
76 template<class InputIterator, class Predicate>
77 bool none_of(InputIterator first, InputIterator last, Predicate pred)
78 {
79 return !any_of(first, last, pred);
80 }
81
82 /**
83 * 25.2.4, for_each:
84 */
85
86 // TODO: Function has to be MoveConstructible
87 template<class InputIterator, class Function>
88 Function for_each(InputIterator first, InputIterator last, Function f)
89 {
90 while (first != last)
91 f(*first++);
92
93 return move(f);
94 }
95
96 /**
97 * 25.2.5, find:
98 */
99
100 template<class InputIterator, class T>
101 InputIterator find(InputIterator first, InputIterator last, const T& value)
102 {
103 while (first != last)
104 {
105 if (*first == value)
106 return first;
107 ++first;
108 }
109
110 return last;
111 }
112
113 template<class InputIterator, class Predicate>
114 InputIterator find_if(InputIterator first, InputIterator last, Predicate pred)
115 {
116 while (first != last)
117 {
118 if (pred(*first))
119 return first;
120 ++first;
121 }
122
123 return last;
124 }
125
126 template<class InputIterator, class Predicate>
127 InputIterator find_if_not(InputIterator first, InputIterator last, Predicate pred)
128 {
129 while (first != last)
130 {
131 if (!pred(*first))
132 return first;
133 ++first;
134 }
135
136 return last;
137 }
138
139 /**
140 * 25.2.6, find_end:
141 */
142
143 // TODO: implement
144
145 /**
146 * 25.2.7, find_first:
147 */
148
149 // TODO: implement
150
151 /**
152 * 25.2.8, adjacent_find:
153 */
154
155 template<class ForwardIterator>
156 ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last)
157 {
158 while (first != last)
159 {
160 if (*first == *(first + 1))
161 return first;
162 ++first;
163 }
164
165 return last;
166 }
167
168 template<class ForwardIterator, class Predicate>
169 ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, Predicate pred)
170 {
171 while (first != last)
172 {
173 if (pred(*first, *(first + 1)))
174 return first;
175 ++first;
176 }
177
178 return last;
179 }
180
181 /**
182 * 25.2.9, count:
183 */
184
185 template<class InputIterator, class T>
186 typename iterator_traits<InputIterator>::difference_type
187 count(InputIterator first, InputIterator last, const T& value)
188 {
189 typename iterator_traits<InputIterator>::difference_type cnt{};
190
191 while (first != last)
192 {
193 if (*first++ == value)
194 ++cnt;
195 }
196
197 return cnt;
198 }
199
200 template<class InputIterator, class Predicate>
201 typename iterator_traits<InputIterator>::difference_type
202 count(InputIterator first, InputIterator last, Predicate pred)
203 {
204 typename iterator_traits<InputIterator>::difference_type cnt{};
205
206 while (first != last)
207 {
208 if (pred(*first++))
209 ++cnt;
210 }
211
212 return cnt;
213 }
214
215 /**
216 * 25.2.10, mismatch:
217 */
218
219 template<class InputIterator1, class InputIterator2>
220 pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1,
221 InputIterator2 first2)
222 {
223 while (first1 != last1 && *first1++ == *first2++)
224 { /* DUMMY BODY */ }
225
226 return make_pair(first1, first2);
227 }
228
229 template<class InputIterator1, class InputIterator2, class BinaryPredicate>
230 pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1,
231 InputIterator2 first2, BinaryPredicate pred)
232 {
233 while (first1 != last1 && pred(*first1++, *first2++))
234 { /* DUMMY BODY */ }
235
236 return make_pair(first1, first2);
237 }
238
239 template<class InputIterator1, class InputIterator2>
240 pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1,
241 InputIterator2 first2, InputIterator2 last2)
242 {
243 while (first1 != last1 && first2 != last2 && *first1++ == *first2++)
244 { /* DUMMY BODY */ }
245
246 return make_pair(first1, first2);
247 }
248
249 template<class InputIterator1, class InputIterator2, class BinaryPredicate>
250 pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1,
251 InputIterator2 first2, InputIterator2 last2,
252 BinaryPredicate pred)
253 {
254 while (first1 != last1 && first2 != last2 && pred(*first1++, *first2++))
255 { /* DUMMY BODY */ }
256
257 return make_pair(first1, first2);
258 }
259
260 /**
261 * 25.2.11, equal:
262 */
263
264 template<class InputIterator1, class InputIterator2>
265 bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
266 {
267 auto last2 = first2 + (last1 - first1);
268
269 return equal(first1, last1, first2, last2);
270 }
271
272 template<class InputIterator1, class InputIterator2>
273 bool equal(InputIterator1 first1, InputIterator1 last1,
274 InputIterator2 first2, InputIterator2 last2)
275 {
276 if ((last1 - first1) != (last2 - first2))
277 return false;
278
279 while (first1 != last1)
280 {
281 if (*first1++ != *first2++)
282 return false;
283 }
284
285 return true;
286 }
287
288 template<class InputIterator1, class InputIterator2, class BinaryPredicate>
289 bool equal(InputIterator1 first1, InputIterator1 last1,
290 InputIterator2 first2, BinaryPredicate pred)
291 {
292 auto last2 = first2 + (last1 - first1);
293
294 return equal(first1, last1, first2, last2, pred);
295 }
296
297 template<class InputIterator1, class InputIterator2, class BinaryPredicate>
298 bool equal(InputIterator1 first1, InputIterator1 last1,
299 InputIterator2 first2, InputIterator2 last2,
300 BinaryPredicate pred)
301 {
302 if ((last1 - first1) != (last2 - first2))
303 return false;
304
305 while (first1 != last1)
306 {
307 if (!pred(*first1++, *first2++))
308 return false;
309 }
310
311 return true;
312 }
313
314 /**
315 * 25.2.12, is_permutation:
316 */
317
318 // TODO: implement
319
320 /**
321 * 25.2.13, search:
322 */
323
324 // TODO: implement
325
326 /**
327 * 25.3, mutating sequence operations:
328 */
329
330 /**
331 * 25.3.1, copy:
332 */
333
334 template<class InputIterator, class OutputIterator>
335 OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result)
336 {
337 while (first != last)
338 *result++ = first++;
339
340 return result;
341 }
342
343 template<class InputIterator, class Size, class OutputIterator>
344 OutputIterator copy_n(InputIterator first, Size count, OutputIterator result)
345 {
346 for (Size i = 0; i < count; ++i, ++first, ++result)
347 *result = *first;
348
349 return result;
350 }
351
352 template<class InputIterator, class OutputIterator, class Predicate>
353 OutputIterator copy_if(InputIterator first, InputIterator last,
354 OutputIterator result, Predicate pred)
355 {
356 while (first != last)
357 {
358 if (pred(*first))
359 *result++ = *first;
360 ++first;
361 }
362
363 return result;
364 }
365
366 template<class BidirectionalIterator1, class BidirectionalIterator2>
367 BidirectionalIterator2 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
368 BidirectionalIterator2 result)
369 {
370 // Note: We're copying [first, last) so we need to skip the initial value of last.
371 while (last-- != first)
372 *result-- = *last;
373 }
374
375 /**
376 * 25.3.2, move:
377 */
378
379 template<class InputIterator, class OutputIterator>
380 OutputIterator move(InputIterator first, InputIterator last, OutputIterator result)
381 {
382 while (first != last)
383 *result++ = move(first++);
384
385 return result;
386 }
387
388 template<class BidirectionalIterator1, class BidirectionalIterator2>
389 BidirectionalIterator2 move_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
390 BidirectionalIterator2 result)
391 {
392 // Note: We're copying [first, last) so we need to skip the initial value of last.
393 while (last-- != first)
394 *result-- = move(*last);
395 }
396
397 /**
398 * 25.3.3, swap:
399 */
400
401 template<class ForwardIterator1, class ForwardIterator2>
402 ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1,
403 ForwardIterator2 first2)
404 {
405 while (first1 != last1)
406 swap(*first1++, *first2++);
407
408 return first2;
409 }
410
411 template<class ForwardIterator1, class ForwardIterator2>
412 void iter_swap(ForwardIterator1 iter1, ForwardIterator2 iter2)
413 {
414 swap(*iter1, *iter2);
415 }
416
417 /**
418 * 25.3.4, transform:
419 */
420
421 template<class InputIterator, class OutputIterator, class UnaryOperation>
422 OutputIterator transform(InputIterator first, InputIterator last,
423 OutputIterator result, UnaryOperation op)
424 {
425 while (first != last)
426 *result++ = op(*first++);
427 }
428
429 template<class InputIterator1, class InputIterator2,
430 class OutputIterator, class BinaryOperation>
431 OutputIterator transform(InputIterator1 first1, InputIterator1 last1,
432 InputIterator2 first2, OutputIterator result,
433 BinaryOperation op)
434 {
435 while (first1 != last1)
436 *result++ = op(*first1++, *first2++);
437 }
438
439 /**
440 * 25.3.5, replace:
441 */
442
443 template<class ForwardIterator, class T>
444 void replace(ForwardIterator first, ForwardIterator last,
445 const T& old_value, const T& new_value)
446 {
447 while (first != last)
448 {
449 if (*first == old_value)
450 *first = new_value;
451 ++first;
452 }
453 }
454
455 template<class ForwardIterator, class Predicate, class T>
456 void replace_if(ForwardIterator first, ForwardIterator last,
457 Predicate pred, const T& new_value)
458 {
459 while (first != last)
460 {
461 if (pred(*first))
462 *first = new_value;
463 ++first;
464 }
465 }
466
467 template<class InputIterator, class OutputIterator, class T>
468 OutputIterator replace_copy(InputIterator first, InputIterator last,
469 OutputIterator result, const T& old_value,
470 const T& new_value)
471 {
472 while (first != last)
473 {
474 if (*first == old_value)
475 *result = new_value;
476 else
477 *result = *first;
478
479 ++first;
480 ++result;
481 }
482 }
483
484 template<class InputIterator, class OutputIterator, class Predicate, class T>
485 OutputIterator replace_copy_if(InputIterator first, InputIterator last,
486 OutputIterator result, Predicate pred,
487 const T& new_value)
488 {
489 while (first != last)
490 {
491 if (pred(*first))
492 *result = new_value;
493 else
494 *result = *first;
495
496 ++first;
497 ++result;
498 }
499 }
500
501 /**
502 * 25.3.6, fill:
503 */
504
505 template<class ForwardIterator, class T>
506 void fill(ForwardIterator first, ForwardIterator last, const T& value)
507 {
508 while (first != last)
509 *first++ = value;
510 }
511
512 template<class InputIterator, class Size, class T>
513 void fill_n(InputIterator first, Size count, const T& value)
514 {
515 for (Size i = 0; i < count; ++i)
516 *first++ = value;
517 }
518
519 /**
520 * 25.3.7, generate:
521 */
522
523 template<class ForwardIterator, class Generator>
524 void generate(ForwardIterator first, ForwardIterator last,
525 Generator gen)
526 {
527 while (first != last)
528 *first++ = gen();
529 }
530
531 template<class OutputIterator, class Size, class Generator>
532 void generate(OutputIterator first, Size count, Generator gen)
533 {
534 for (Size i = 0; i < count; ++i)
535 *first++ = gen();
536 }
537
538 /**
539 * 25.3.8, remove:
540 */
541
542 template<class ForwardIterator, class T>
543 ForwardIterator remove(ForwardIterator first, ForwardIterator last,
544 const T& value)
545 {
546 auto it = first;
547 while (it != last)
548 {
549 if (*it != value)
550 *first++ = move(*it);
551 }
552
553 return first;
554 }
555
556 template<class ForwardIterator, class Predicate>
557 ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,
558 Predicate pred)
559 {
560 auto it = first;
561 while (it != last)
562 {
563 if (!pred(*it))
564 *first++ = move(*it);
565 }
566
567 return first;
568 }
569
570 template<class InputIterator, class OutputIterator, class T>
571 OutputIterator remove_copy(InputIterator first, InputIterator last,
572 OutputIterator result, const T& value)
573 {
574 while (first != last)
575 {
576 if (*first != value)
577 *result++ = *first;
578 ++first;
579 }
580
581 return result;
582 }
583
584 template<class InputIterator, class OutputIterator, class Predicate>
585 OutputIterator remove_copy_if(InputIterator first, InputIterator last,
586 OutputIterator result, Predicate pred)
587 {
588 while (first != last)
589 {
590 if (!pred(*first))
591 *result++ = *first;
592 ++first;
593 }
594
595 return result;
596 }
597
598 /**
599 * 25.3.9, unique:
600 */
601
602 // TODO: implement
603
604 /**
605 * 25.3.10, reverse:
606 */
607
608 template<class BidirectionalIterator>
609 void reverse(BidirectionalIterator first, BidirectionalIterator last)
610 {
611 if (first == last)
612 return;
613 auto mid_count = (last - first) / 2;
614
615 --last;
616 for (decltype(mid_count) i = 0; i < mid_count; ++i)
617 iter_swap(first++, last--);
618 }
619
620 template<class BidirectionalIterator, class OutputIterator>
621 OutputIterator reverse_copy(BidirectionalIterator first,
622 BidirectionalIterator last,
623 OutputIterator result)
624 {
625 while (--last != first)
626 *result++ = *last;
627 }
628
629 /**
630 * 25.3.11, rotate:
631 */
632
633 // TODO: implement
634
635 /**
636 * 25.3.12, shuffle:
637 */
638
639 // TODO: implement
640
641 /**
642 * 25.3.13, partitions:
643 */
644
645 // TODO: implement
646
647 /**
648 * 25.4, sorting and related operations:
649 */
650
651 /**
652 * 25.4.1, sorting:
653 */
654
655 /**
656 * 25.4.1.1, sort:
657 */
658
659 // TODO: implement
660
661 /**
662 * 25.4.1.2, stable_sort:
663 */
664
665 // TODO: implement
666
667 /**
668 * 25.4.1.3, partial_sort:
669 */
670
671 // TODO: implement
672
673 /**
674 * 25.4.1.4, partial_sort_copy:
675 */
676
677 // TODO: implement
678
679 /**
680 * 25.4.1.5, is_sorted:
681 */
682
683 template<class ForwardIterator>
684 bool is_sorted(ForwardIterator first, ForwardIterator last)
685 {
686 return is_sorted_until(first, last) == last;
687 }
688
689 template<class ForwardIterator, class Comp>
690 bool is_sorted(ForwardIterator first, ForwardIterator last,
691 Comp comp)
692 {
693 return is_sorted_until(first, last, comp) == last;
694 }
695
696 template<class ForwardIterator>
697 ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last)
698 {
699 if (distance(first, last) < 2)
700 return last;
701
702 while (first != last)
703 {
704 if (*first > *(++first))
705 return first;
706 }
707
708 return last;
709 }
710
711 template<class ForwardIterator, class Comp>
712 ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last,
713 Comp comp)
714 {
715 if (distance(first, last) < 2)
716 return last;
717
718 while (first != last)
719 {
720 if (!comp(*first, *(++first)))
721 return first;
722 }
723
724 return last;
725 }
726
727 /**
728 * 25.4.2, nth_element:
729 */
730
731 // TODO: implement
732
733 /**
734 * 25.4.3, binary search:
735 */
736
737 /**
738 * 25.4.3.1, lower_bound
739 */
740
741 // TODO: implement
742
743 /**
744 * 25.4.3.2, upper_bound
745 */
746
747 // TODO: implement
748
749 /**
750 * 25.4.3.3, equal_range:
751 */
752
753 // TODO: implement
754
755 /**
756 * 25.4.3.4, binary_search:
757 */
758
759 // TODO: implement
760
761 /**
762 * 25.4.4, merge:
763 */
764
765 // TODO: implement
766
767 /**
768 * 25.4.5, set operations on sorted structures:
769 */
770
771 /**
772 * 25.4.5.1, includes:
773 */
774
775 // TODO: implement
776
777 /**
778 * 25.4.5.2, set_union:
779 */
780
781 // TODO: implement
782
783 /**
784 * 25.4.5.3, set_intersection:
785 */
786
787 // TODO: implement
788
789 /**
790 * 25.4.5.4, set_difference:
791 */
792
793 // TODO: implement
794
795 /**
796 * 25.4.5.5, set_symmetric_difference:
797 */
798
799 // TODO: implement
800
801 /**
802 * 25.4.6, heap operations:
803 */
804
805 /**
806 * 25.4.6.1, push_heap:
807 */
808
809 // TODO: implement
810
811 /**
812 * 25.4.6.2, pop_heap:
813 */
814
815 // TODO: implement
816
817 /**
818 * 25.4.6.3, make_heap:
819 */
820
821 // TODO: implement
822
823 /**
824 * 25.4.6.4, sort_heap:
825 */
826
827 // TODO: implement
828
829 /**
830 * 25.4.6.5, is_heap:
831 */
832
833 // TODO: implement
834
835 /**
836 * 25.4.7, minimum and maximum:
837 * // TODO: implement container versions when we have
838 * numeric limits and min/max element
839 * // TODO: versions with comparators
840 * // TODO: minmax
841 */
842
843 template<class T>
844 constexpr const T& min(const T& lhs, const T& rhs)
845 {
846 return (lhs < rhs) ? lhs : rhs;
847 }
848
849 template<class T>
850 constexpr const T& max(const T& lhs, const T& rhs)
851 {
852 return (lhs > rhs) ? lhs : rhs;
853 }
854
855 /**
856 * 25.4.8, lexicographical comparison:
857 */
858
859 // TODO: implement
860
861 /**
862 * 25.4.9, permutation generators:
863 */
864
865 // TODO: implement
866}
867
868#endif
Note: See TracBrowser for help on using the repository browser.