Embedded Template Library 1.0
algorithm.h
Go to the documentation of this file.
1
2
3/******************************************************************************
4The MIT License(MIT)
5
6Embedded Template Library.
7https://github.com/ETLCPP/etl
8https://www.etlcpp.com
9
10Documentation: https://www.etlcpp.com/algorithm.html
11
12Copyright(c) 2014 John Wellbelove
13
14Permission is hereby granted, free of charge, to any person obtaining a copy
15of this software and associated documentation files(the "Software"), to deal
16in the Software without restriction, including without limitation the rights
17to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
18copies of the Software, and to permit persons to whom the Software is
19furnished to do so, subject to the following conditions :
20
21The above copyright notice and this permission notice shall be included in all
22copies or substantial portions of the Software.
23
24THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
25IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
26FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
27AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
28LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
29OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
30SOFTWARE.
31******************************************************************************/
32
33#ifndef ETL_ALGORITHM_INCLUDED
34#define ETL_ALGORITHM_INCLUDED
35
40
41#include "platform.h"
42#include "type_traits.h"
43#include "iterator.h"
44#include "functional.h"
45#include "utility.h"
46
47#include <stdint.h>
48#include <string.h>
49
50#include "private/minmax_push.h"
51
52#if ETL_USING_STL
53 #include <algorithm>
54 #include <utility>
55 #include <iterator>
56 #include <functional>
57 #include <numeric>
58#endif
59
60namespace etl
61{
62 // Declare prototypes of the ETL's sort functions
63 template <typename TIterator>
64#if ETL_USING_STD_NAMESPACE
65 ETL_CONSTEXPR20
66#else
67 ETL_CONSTEXPR14
68#endif
69 void shell_sort(TIterator first, TIterator last);
70
71 template <typename TIterator, typename TCompare>
72#if ETL_USING_STD_NAMESPACE
73 ETL_CONSTEXPR20
74#else
75 ETL_CONSTEXPR14
76#endif
77 void shell_sort(TIterator first, TIterator last, TCompare compare);
78
79 template <typename TIterator>
80 ETL_CONSTEXPR14 void insertion_sort(TIterator first, TIterator last);
81
82 template <typename TIterator, typename TCompare>
83 ETL_CONSTEXPR14 void insertion_sort(TIterator first, TIterator last, TCompare compare);
84}
85
86//*****************************************************************************
87// Algorithms defined by the ETL
88//*****************************************************************************
89namespace etl
90{
91 //***************************************************************************
92 // iter_swap
93 //***************************************************************************
94 template <typename TIterator1, typename TIterator2>
95#if ETL_USING_STD_NAMESPACE
96 ETL_CONSTEXPR20
97#else
98 ETL_CONSTEXPR14
99#endif
100 void iter_swap(TIterator1 a, TIterator2 b)
101 {
102 using ETL_OR_STD::swap; // Allow ADL
103 swap(*a, *b);
104 }
105
106 //***************************************************************************
107 // swap_ranges
108 //***************************************************************************
109 template <typename TIterator1, typename TIterator2>
110#if ETL_USING_STD_NAMESPACE
111 ETL_CONSTEXPR20
112#else
113 ETL_CONSTEXPR14
114#endif
115 TIterator2 swap_ranges(TIterator1 first1,
116 TIterator1 last1,
117 TIterator2 first2)
118 {
119 while (first1 != last1)
120 {
121 iter_swap(first1, first2);
122 ++first1;
123 ++first2;
124 }
125
126 return first2;
127 }
128
129 //***************************************************************************
130 // copy
131#if ETL_USING_STL && ETL_USING_CPP20
132 // Use the STL constexpr implementation.
133 template <typename TIterator1, typename TIterator2>
134 constexpr TIterator2 copy(TIterator1 sb, TIterator1 se, TIterator2 db)
135 {
136 return std::copy(sb, se, db);
137 }
138#else
139 // Non-pointer or not trivially copyable or not using builtin memcpy.
140 template <typename TIterator1, typename TIterator2>
141 ETL_CONSTEXPR14 TIterator2 copy(TIterator1 sb, TIterator1 se, TIterator2 db)
142 {
143 while (sb != se)
144 {
145 *db = *sb;
146 ++db;
147 ++sb;
148 }
149
150 return db;
151 }
152#endif
153
154 //***************************************************************************
155 // reverse_copy
156#if ETL_USING_STL && ETL_USING_CPP20
157 template <typename TIterator1, typename TIterator2>
158 constexpr TIterator2 reverse_copy(TIterator1 sb, TIterator1 se, TIterator2 db)
159 {
160 return std::reverse_copy(sb, se, db);
161 }
162#else
163 template <typename TIterator1, typename TIterator2>
164 ETL_CONSTEXPR14
165 TIterator2 reverse_copy(TIterator1 sb, TIterator1 se, TIterator2 db)
166 {
167 while (sb != se)
168 {
169 *db = *--se;
170 ++db;
171 }
172
173 return db;
174 }
175#endif
176
177 //***************************************************************************
178 // copy_n
179#if ETL_USING_STL && ETL_USING_CPP20
180 // Use the STL implementation
181 template <typename TIterator1, typename TSize, typename TIterator2>
182 constexpr TIterator2 copy_n(TIterator1 sb, TSize count, TIterator2 db)
183 {
184 return std::copy_n(sb, count, db);
185 }
186#else
187 // Non-pointer or not trivially copyable or not using builtin memcpy.
188 template <typename TIterator1, typename TSize, typename TIterator2>
189 ETL_CONSTEXPR14 TIterator2 copy_n(TIterator1 sb, TSize count, TIterator2 db)
190 {
191 while (count != 0)
192 {
193 *db = *sb;
194 ++db;
195 ++sb;
196 --count;
197 }
198
199 return db;
200 }
201#endif
202
203 //***************************************************************************
204 // copy_backward
205#if ETL_USING_STL && ETL_USING_CPP20
206 template <typename TIterator1, typename TIterator2>
207 constexpr TIterator2 copy_backward(TIterator1 sb, TIterator1 se, TIterator2 de)
208 {
209 return std::copy_backward(sb, se, de);
210 }
211#else
212 template <typename TIterator1, typename TIterator2>
213 ETL_CONSTEXPR14 TIterator2 copy_backward(TIterator1 sb, TIterator1 se, TIterator2 de)
214 {
215 while (se != sb)
216 {
217 *(--de) = *(--se);
218 }
219
220 return de;
221 }
222#endif
223
224 //***************************************************************************
225 // move
226#if ETL_USING_STL && ETL_USING_CPP20
227 template <typename TIterator1, typename TIterator2>
228 constexpr TIterator2 move(TIterator1 sb, TIterator1 se, TIterator2 db)
229 {
230 return std::move(sb, se, db);
231 }
232#else
233 // non-pointer or not trivially copyable
234 template <typename TIterator1, typename TIterator2>
235 ETL_CONSTEXPR14 TIterator2 move(TIterator1 sb, TIterator1 se, TIterator2 db)
236 {
237 while (sb != se)
238 {
239 *db = etl::move(*sb);
240 ++db;
241 ++sb;
242 }
243
244 return db;
245 }
246#endif
247
248 //***************************************************************************
249 // move_backward
250#if ETL_USING_STL && ETL_USING_CPP20
251 template <typename TIterator1, typename TIterator2>
252 ETL_CONSTEXPR20
253 TIterator2 move_backward(TIterator1 sb, TIterator1 se, TIterator2 de)
254 {
255 return std::move_backward(sb, se, de);
256 }
257#else
258 // non-pointer or not trivially copyable
259 template <typename TIterator1, typename TIterator2>
260 ETL_CONSTEXPR14 TIterator2 move_backward(TIterator1 sb, TIterator1 se, TIterator2 de)
261 {
262 while (sb != se)
263 {
264 *(--de) = etl::move(*(--se));
265 }
266
267 return de;
268 }
269#endif
270
271 //***************************************************************************
272 // reverse
273 //***************************************************************************
274 // Pointers
275 template <typename TIterator>
277 reverse(TIterator b, TIterator e)
278 {
279 if (b != e)
280 {
281 while (b < --e)
282 {
283 etl::iter_swap(b, e);
284 ++b;
285 }
286 }
287 }
288
289 // Non-pointers
290 template <typename TIterator>
292 reverse(TIterator b, TIterator e)
293 {
294 while ((b != e) && (b != --e))
295 {
296 etl::iter_swap(b++, e);
297 }
298 }
299
300 //***************************************************************************
301 // lower_bound
302 //***************************************************************************
303 template<typename TIterator, typename TValue, typename TCompare>
304 ETL_NODISCARD
305 ETL_CONSTEXPR14
306 TIterator lower_bound(TIterator first, TIterator last, const TValue& value, TCompare compare)
307 {
308 typedef typename etl::iterator_traits<TIterator>::difference_type difference_t;
309
310 difference_t count = etl::distance(first, last);
311
312 while (count > 0)
313 {
314 TIterator itr = first;
315 difference_t step = count / 2;
316
317 etl::advance(itr, step);
318
319 if (compare(*itr, value))
320 {
321 first = ++itr;
322 count -= step + 1;
323 }
324 else
325 {
326 count = step;
327 }
328 }
329
330 return first;
331 }
332
333 template<typename TIterator, typename TValue>
334 ETL_NODISCARD
335 ETL_CONSTEXPR14
336 TIterator lower_bound(TIterator first, TIterator last, const TValue& value)
337 {
339
340 return etl::lower_bound(first, last, value, compare());
341 }
342
343 //***************************************************************************
344 // upper_bound
345 //***************************************************************************
346 template<typename TIterator, typename TValue, typename TCompare>
347 ETL_NODISCARD
348 ETL_CONSTEXPR14
349 TIterator upper_bound(TIterator first, TIterator last, const TValue& value, TCompare compare)
350 {
351 typedef typename etl::iterator_traits<TIterator>::difference_type difference_t;
352
353 difference_t count = etl::distance(first, last);
354
355 while (count > 0)
356 {
357 TIterator itr = first;
358 difference_t step = count / 2;
359
360 etl::advance(itr, step);
361
362 if (!compare(value, *itr))
363 {
364 first = ++itr;
365 count -= step + 1;
366 }
367 else
368 {
369 count = step;
370 }
371 }
372
373 return first;
374 }
375
376 template<typename TIterator, typename TValue>
377 ETL_NODISCARD
378 ETL_CONSTEXPR14
379 TIterator upper_bound(TIterator first, TIterator last, const TValue& value)
380 {
382
383 return etl::upper_bound(first, last, value, compare());
384 }
385
386 //***************************************************************************
387 // equal_range
388 //***************************************************************************
389 template<typename TIterator, typename TValue, typename TCompare>
390 ETL_NODISCARD
391 ETL_CONSTEXPR14
392 ETL_OR_STD::pair<TIterator, TIterator> equal_range(TIterator first, TIterator last, const TValue& value, TCompare compare)
393 {
394 return ETL_OR_STD::make_pair(etl::lower_bound(first, last, value, compare),
395 etl::upper_bound(first, last, value, compare));
396 }
397
398 template<typename TIterator, typename TValue>
399 ETL_NODISCARD
400 ETL_OR_STD::pair<TIterator, TIterator> equal_range(TIterator first, TIterator last, const TValue& value)
401 {
403
404 return ETL_OR_STD::make_pair(etl::lower_bound(first, last, value, compare()),
405 etl::upper_bound(first, last, value, compare()));
406 }
407
408 //***************************************************************************
409 // binary_search
410 //***************************************************************************
411 template <typename TIterator, typename T, typename Compare>
412 ETL_NODISCARD
413 bool binary_search(TIterator first, TIterator last, const T& value, Compare compare)
414 {
415 first = etl::lower_bound(first, last, value, compare);
416
417 return (!(first == last) && !(compare(value, *first)));
418 }
419
420 template <typename TIterator, typename T>
421 ETL_NODISCARD
422 bool binary_search(TIterator first, TIterator last, const T& value)
423 {
425
426 return binary_search(first, last, value, compare());
427 }
428
429 //***************************************************************************
430 // find_if
431 //***************************************************************************
432 template <typename TIterator, typename TUnaryPredicate>
433 ETL_NODISCARD
434 ETL_CONSTEXPR14
435 TIterator find_if(TIterator first, TIterator last, TUnaryPredicate predicate)
436 {
437 while (first != last)
438 {
439 if (predicate(*first))
440 {
441 return first;
442 }
443
444 ++first;
445 }
446
447 return last;
448 }
449
450 //***************************************************************************
451 // find
452 //***************************************************************************
453 template <typename TIterator, typename T>
454 ETL_NODISCARD
455 ETL_CONSTEXPR14
456 TIterator find(TIterator first, TIterator last, const T& value)
457 {
458 while (first != last)
459 {
460 if (*first == value)
461 {
462 return first;
463 }
464
465 ++first;
466 }
467
468 return last;
469 }
470
471 //***************************************************************************
472 // fill
473#if ETL_USING_STL && ETL_USING_CPP20
474 template<typename TIterator, typename TValue>
475 constexpr void fill(TIterator first, TIterator last, const TValue& value)
476 {
477 std::fill(first, last, value);
478 }
479#else
480 template<typename TIterator, typename TValue>
481 ETL_CONSTEXPR14 void fill(TIterator first, TIterator last, const TValue& value)
482 {
483 while (first != last)
484 {
485 *first = value;
486 ++first;
487 }
488 }
489#endif
490
491 //***************************************************************************
492 // fill_n
493#if ETL_USING_STL && ETL_USING_CPP20
494 template<typename TIterator, typename TSize, typename TValue>
495 constexpr TIterator fill_n(TIterator first, TSize count, const TValue& value)
496 {
497 return std::fill_n(first, count, value);
498 }
499#else
500 template<typename TIterator, typename TSize, typename TValue>
501 ETL_CONSTEXPR14 TIterator fill_n(TIterator first, TSize count, const TValue& value)
502 {
503 while (count != 0)
504 {
505 *first++ = value;
506 --count;
507 }
508
509 return first;
510 }
511#endif
512
513 //***************************************************************************
514 // count
515 //***************************************************************************
516 template <typename TIterator, typename T>
517 ETL_NODISCARD
518 ETL_CONSTEXPR14
519 typename etl::iterator_traits<TIterator>::difference_type count(TIterator first, TIterator last, const T& value)
520 {
521 typename iterator_traits<TIterator>::difference_type n = 0;
522
523 while (first != last)
524 {
525 if (*first == value)
526 {
527 ++n;
528 }
529
530 ++first;
531 }
532
533 return n;
534 }
535
536 //***************************************************************************
537 // count_if
538 //***************************************************************************
539 template <typename TIterator, typename TUnaryPredicate>
540 ETL_NODISCARD
541 ETL_CONSTEXPR14
542 typename etl::iterator_traits<TIterator>::difference_type
543 count_if(TIterator first, TIterator last, TUnaryPredicate predicate)
544 {
545 typename iterator_traits<TIterator>::difference_type n = 0;
546
547 while (first != last)
548 {
549 if (predicate(*first))
550 {
551 ++n;
552 }
553
554 ++first;
555 }
556
557 return n;
558 }
559
560 //***************************************************************************
561 // equal
562#if ETL_USING_STL && ETL_USING_CPP20
563 template <typename TIterator1, typename TIterator2>
564 [[nodiscard]]
565 constexpr
566 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2)
567 {
568 return std::equal(first1, last1, first2);
569 }
570
571 template <typename TIterator1, typename TIterator2, typename TPredicate>
572 [[nodiscard]]
573 constexpr
574 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2, TPredicate predicate)
575 {
576 return std::equal(first1, last1, first2, predicate);
577 }
578#else
579 // Not pointer types or not trivially copyable.
580 template <typename TIterator1, typename TIterator2>
581 ETL_NODISCARD
582 ETL_CONSTEXPR14
583 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2)
584 {
585 while (first1 != last1)
586 {
587 if (*first1 != *first2)
588 {
589 return false;
590 }
591
592 ++first1;
593 ++first2;
594 }
595
596 return true;
597 }
598
599 // Predicate
600 template <typename TIterator1, typename TIterator2, typename TPredicate>
601 ETL_NODISCARD
602 ETL_CONSTEXPR14
603 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2, TPredicate predicate)
604 {
605 while (first1 != last1)
606 {
607 if (!predicate(*first1, *first2))
608 {
609 return false;
610 }
611
612 ++first1;
613 ++first2;
614 }
615
616 return true;
617 }
618
619 // Four parameter
620 template <typename TIterator1, typename TIterator2>
621 ETL_NODISCARD
622 ETL_CONSTEXPR14
623 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2, TIterator2 last2)
624 {
625 while ((first1 != last1) && (first2 != last2))
626 {
627 if (*first1 != *first2)
628 {
629 return false;
630 }
631
632 ++first1;
633 ++first2;
634 }
635
636 return (first1 == last1) && (first2 == last2);
637 }
638
639 // Four parameter, Predicate
640 template <typename TIterator1, typename TIterator2, typename TPredicate>
641 ETL_NODISCARD
642 ETL_CONSTEXPR14
643 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2, TIterator2 last2, TPredicate predicate)
644 {
645 while ((first1 != last1) && (first2 != last2))
646 {
647 if (!predicate(*first1 , *first2))
648 {
649 return false;
650 }
651
652 ++first1;
653 ++first2;
654 }
655
656 return (first1 == last1) && (first2 == last2);
657 }
658#endif
659
660 //***************************************************************************
661 // lexicographical_compare
662 //***************************************************************************
663 template <typename TIterator1, typename TIterator2, typename TCompare>
664 ETL_NODISCARD
665 ETL_CONSTEXPR14
666 bool lexicographical_compare(TIterator1 first1, TIterator1 last1,
667 TIterator2 first2, TIterator2 last2,
668 TCompare compare)
669 {
670 while ((first1 != last1) && (first2 != last2))
671 {
672 if (compare(*first1, *first2))
673 {
674 return true;
675 }
676
677 if (compare(*first2, *first1))
678 {
679 return false;
680 }
681
682 ++first1;
683 ++first2;
684 }
685
686 return (first1 == last1) && (first2 != last2);
687 }
688
689 // lexicographical_compare
690 template <typename TIterator1, typename TIterator2>
691 ETL_NODISCARD
692 ETL_CONSTEXPR14
693 bool lexicographical_compare(TIterator1 first1, TIterator1 last1,
694 TIterator2 first2, TIterator2 last2)
695 {
697
698 return etl::lexicographical_compare(first1, last1, first2, last2, compare());
699 }
700
701 //***************************************************************************
702 // min
703 //***************************************************************************
704 template <typename T, typename TCompare>
705 ETL_NODISCARD
706 ETL_CONSTEXPR
707 const T& min(const T& a, const T& b, TCompare compare)
708 {
709 return (compare(a, b)) ? a : b;
710 }
711
712 template <typename T>
713 ETL_NODISCARD
714 ETL_CONSTEXPR
715 const T& min(const T& a, const T& b)
716 {
717 typedef etl::less<T> compare;
718
719 return etl::min(a, b, compare());
720 }
721
722 //***************************************************************************
723 // max
724 //***************************************************************************
725 template <typename T, typename TCompare>
726 ETL_NODISCARD
727 ETL_CONSTEXPR
728 const T& max(const T& a, const T& b, TCompare compare)
729 {
730 return (compare(a, b)) ? b : a;
731 }
732
733 template <typename T>
734 ETL_NODISCARD
735 ETL_CONSTEXPR
736 const T& max(const T& a, const T& b)
737 {
738 typedef etl::less<T> compare;
739
740 return etl::max(a, b, compare());
741 }
742
743 //***************************************************************************
744 // for_each
745 //***************************************************************************
746 template <typename TIterator, typename TUnaryOperation>
747 ETL_CONSTEXPR14
748 TUnaryOperation for_each(TIterator first, TIterator last, TUnaryOperation unary_operation)
749 {
750 while (first != last)
751 {
752 unary_operation(*first);
753 ++first;
754 }
755
756 return unary_operation;
757 }
758
759 //***************************************************************************
760 // transform
761 //***************************************************************************
762 template <typename TIteratorIn, typename TIteratorOut, typename TUnaryOperation>
763 ETL_CONSTEXPR14
764 TIteratorOut transform(TIteratorIn first1, TIteratorIn last1, TIteratorOut d_first, TUnaryOperation unary_operation)
765 {
766 while (first1 != last1)
767 {
768 *d_first = unary_operation(*first1);
769
770 ++d_first;
771 ++first1;
772 }
773
774 return d_first;
775 }
776
777 template <typename TIteratorIn1, typename TIteratorIn2, typename TIteratorOut, typename TBinaryOperation>
778 ETL_CONSTEXPR14
779 TIteratorOut transform(TIteratorIn1 first1, TIteratorIn1 last1, TIteratorIn2 first2, TIteratorOut d_first, TBinaryOperation binary_operation)
780 {
781 while (first1 != last1)
782 {
783 *d_first = binary_operation(*first1, *first2);
784
785 ++d_first;
786 ++first1;
787 ++first2;
788 }
789
790 return d_first;
791 }
792
793 //***************************************************************************
794 // replace
795 //***************************************************************************
796 template <typename TIterator, typename T>
797 ETL_CONSTEXPR14 void replace(TIterator first, TIterator last, const T& old_value, const T& new_value)
798 {
799 while (first != last)
800 {
801 if (*first == old_value)
802 {
803 *first = new_value;
804 }
805
806 ++first;
807 }
808 }
809
810 //***************************************************************************
811 // replace_if
812 //***************************************************************************
813 template <typename TIterator, typename TPredicate, typename T>
814 ETL_CONSTEXPR14 void replace_if(TIterator first, TIterator last, TPredicate predicate, const T& new_value)
815 {
816 while (first != last)
817 {
818 if (predicate(*first))
819 {
820 *first = new_value;
821 }
822
823 ++first;
824 }
825 }
826
827 //***************************************************************************
828 // Heap
829 //***************************************************************************
830 namespace private_heap
831 {
832 // Push Heap Helper
833 template <typename TIterator, typename TDistance, typename TValue, typename TCompare>
834 void push_heap(TIterator first, TDistance value_index, TDistance top_index, TValue value, TCompare compare)
835 {
836 TDistance parent = (value_index - 1) / 2;
837
838 while ((value_index > top_index) && compare(first[parent], value))
839 {
840 first[value_index] = etl::move(first[parent]);
841 value_index = parent;
842 parent = (value_index - 1) / 2;
843 }
844
845 first[value_index] = etl::move(value);
846 }
847
848 // Adjust Heap Helper
849 template <typename TIterator, typename TDistance, typename TValue, typename TCompare>
850 void adjust_heap(TIterator first, TDistance value_index, TDistance length, TValue value, TCompare compare)
851 {
852 TDistance top_index = value_index;
853 TDistance child2nd = (2 * value_index) + 2;
854
855 while (child2nd < length)
856 {
857 if (compare(first[child2nd], first[child2nd - 1]))
858 {
859 --child2nd;
860 }
861
862 first[value_index] = etl::move(first[child2nd]);
863 value_index = child2nd;
864 child2nd = 2 * (child2nd + 1);
865 }
866
867 if (child2nd == length)
868 {
869 first[value_index] = etl::move(first[child2nd - 1]);
870 value_index = child2nd - 1;
871 }
872
873 push_heap(first, value_index, top_index, etl::move(value), compare);
874 }
875
876 // Is Heap Helper
877 template <typename TIterator, typename TDistance, typename TCompare>
878 bool is_heap(const TIterator first, const TDistance n, TCompare compare)
879 {
880 TDistance parent = 0;
881
882 for (TDistance child = 1; child < n; ++child)
883 {
884 if (compare(first[parent], first[child]))
885 {
886 return false;
887 }
888
889 if ((child & 1) == 0)
890 {
891 ++parent;
892 }
893 }
894
895 return true;
896 }
897 }
898
899 // Pop Heap
900 template <typename TIterator, typename TCompare>
901 void pop_heap(TIterator first, TIterator last, TCompare compare)
902 {
903 typedef typename etl::iterator_traits<TIterator>::value_type value_t;
904 typedef typename etl::iterator_traits<TIterator>::difference_type distance_t;
905
906 value_t value = etl::move(last[-1]);
907 last[-1] = etl::move(first[0]);
908
909 private_heap::adjust_heap(first, distance_t(0), distance_t(last - first - 1), etl::move(value), compare);
910 }
911
912 // Pop Heap
913 template <typename TIterator>
914 void pop_heap(TIterator first, TIterator last)
915 {
917
918 etl::pop_heap(first, last, compare());
919 }
920
921 // Push Heap
922 template <typename TIterator, typename TCompare>
923 void push_heap(TIterator first, TIterator last, TCompare compare)
924 {
925 typedef typename etl::iterator_traits<TIterator>::difference_type difference_t;
926 typedef typename etl::iterator_traits<TIterator>::value_type value_t;
927
928 private_heap::push_heap(first, difference_t(last - first - 1), difference_t(0), value_t(etl::move(*(last - 1))), compare);
929 }
930
931 // Push Heap
932 template <typename TIterator>
933 void push_heap(TIterator first, TIterator last)
934 {
936
937 etl::push_heap(first, last, compare());
938 }
939
940 // Make Heap
941 template <typename TIterator, typename TCompare>
942 void make_heap(TIterator first, TIterator last, TCompare compare)
943 {
944 typedef typename etl::iterator_traits<TIterator>::difference_type difference_t;
945
946 if ((last - first) < 2)
947 {
948 return;
949 }
950
951 difference_t length = last - first;
952 difference_t parent = (length - 2) / 2;
953
954 while (true)
955 {
956 private_heap::adjust_heap(first, parent, length, etl::move(*(first + parent)), compare);
957
958 if (parent == 0)
959 {
960 return;
961 }
962
963 --parent;
964 }
965 }
966
967 // Make Heap
968 template <typename TIterator>
969 void make_heap(TIterator first, TIterator last)
970 {
972
973 etl::make_heap(first, last, compare());
974 }
975
976 // Is Heap
977 template <typename TIterator>
978 ETL_NODISCARD
979 bool is_heap(TIterator first, TIterator last)
980 {
982
983 return private_heap::is_heap(first, last - first, compare());
984 }
985
986 // Is Heap
987 template <typename TIterator, typename TCompare>
988 ETL_NODISCARD
989 bool is_heap(TIterator first, TIterator last, TCompare compare)
990 {
991 return private_heap::is_heap(first, last - first, compare);
992 }
993
994 // Sort Heap
995 template <typename TIterator>
996 void sort_heap(TIterator first, TIterator last)
997 {
998 while (first != last)
999 {
1000 etl::pop_heap(first, last);
1001 --last;
1002 }
1003 }
1004
1005 // Sort Heap
1006 template <typename TIterator, typename TCompare>
1007 void sort_heap(TIterator first, TIterator last, TCompare compare)
1008 {
1009 while (first != last)
1010 {
1011 etl::pop_heap(first, last, compare);
1012 --last;
1013 }
1014 }
1015
1016 //***************************************************************************
1017 // Search
1018 //***************************************************************************
1019 template<typename TIterator1, typename TIterator2, typename TCompare>
1020 ETL_NODISCARD
1021 ETL_CONSTEXPR14
1022 TIterator1 search(TIterator1 first, TIterator1 last, TIterator2 search_first, TIterator2 search_last, TCompare compare)
1023 {
1024 while (true)
1025 {
1026 TIterator1 itr = first;
1027 TIterator2 search_itr = search_first;
1028
1029 while (true)
1030 {
1031 if (search_itr == search_last)
1032 {
1033 return first;
1034 }
1035
1036 if (itr == last)
1037 {
1038 return last;
1039 }
1040
1041 if (!compare(*itr, *search_itr))
1042 {
1043 break;
1044 }
1045
1046 ++itr;
1047 ++search_itr;
1048 }
1049
1050 ++first;
1051 }
1052 }
1053
1054 // Search
1055 template<typename TIterator1, typename TIterator2>
1056 ETL_NODISCARD
1057 ETL_CONSTEXPR14
1058 TIterator1 search(TIterator1 first, TIterator1 last, TIterator2 search_first, TIterator2 search_last)
1059 {
1061
1062 return etl::search(first, last, search_first, search_last, compare());
1063 }
1064
1065 //***************************************************************************
1066 // Rotate
1067 //***************************************************************************
1068 namespace private_algorithm
1069 {
1070 //*********************************
1071 template <typename TIterator>
1072 ETL_CONSTEXPR14
1073 TIterator rotate_general(TIterator first, TIterator middle, TIterator last)
1074 {
1075 TIterator next = middle;
1076
1077 while (first != next)
1078 {
1079 using ETL_OR_STD::swap; // Allow ADL
1080
1081 swap(*first, *next);
1082
1083 ++first;
1084 ++next;
1085
1086 if (next == last)
1087 {
1088 next = middle;
1089 }
1090 else if (first == middle)
1091 {
1092 middle = next;
1093 }
1094 }
1095
1096 return first;
1097 }
1098
1099 //*********************************
1100 template <typename TIterator>
1101 ETL_CONSTEXPR14
1102 TIterator rotate_left_by_one(TIterator first, TIterator last)
1103 {
1104 typedef typename etl::iterator_traits<TIterator>::value_type value_type;
1105
1106 // Save the first item.
1107 value_type temp(etl::move(*first));
1108
1109 // Move the rest.
1110 TIterator result = etl::move(etl::next(first), last, first);
1111
1112 // Restore the first item in its rotated position.
1113 *result = etl::move(temp);
1114
1115 // The new position of the first item.
1116 return result;
1117 }
1118
1119 //*********************************
1120 template <typename TIterator>
1121 ETL_CONSTEXPR14
1122 TIterator rotate_right_by_one(TIterator first, TIterator last)
1123 {
1124 typedef typename etl::iterator_traits<TIterator>::value_type value_type;
1125
1126 // Save the last item.
1127 TIterator previous = etl::prev(last);
1128 value_type temp(etl::move(*previous));
1129
1130 // Move the rest.
1131 TIterator result = etl::move_backward(first, previous, last);
1132
1133 // Restore the last item in its rotated position.
1134 *first = etl::move(temp);
1135
1136 // The new position of the first item.
1137 return result;
1138 }
1139 }
1140
1141 //*********************************
1142 template<typename TIterator>
1143 ETL_CONSTEXPR14
1144 TIterator rotate(TIterator first, TIterator middle, TIterator last)
1145 {
1146 if (etl::next(first) == middle)
1147 {
1148 return private_algorithm::rotate_left_by_one(first, last);
1149 }
1150
1151 if (etl::next(middle) == last)
1152 {
1153 return private_algorithm::rotate_right_by_one(first, last);
1154 }
1155
1156 return private_algorithm::rotate_general(first, middle, last);
1157 }
1158
1159 //***************************************************************************
1160 // find_end
1161 //***************************************************************************
1162 // Predicate
1163 template <typename TIterator1, typename TIterator2, typename TPredicate>
1164 ETL_NODISCARD
1165 ETL_CONSTEXPR14
1166 TIterator1 find_end(TIterator1 b, TIterator1 e,
1167 TIterator2 sb, TIterator2 se,
1168 TPredicate predicate)
1169 {
1170 if (sb == se)
1171 {
1172 return e;
1173 }
1174
1175 TIterator1 result = e;
1176
1177 while (true)
1178 {
1179 TIterator1 new_result = etl::search(b, e, sb, se, predicate);
1180
1181 if (new_result == e)
1182 {
1183 break;
1184 }
1185 else
1186 {
1187 result = new_result;
1188 b = result;
1189 ++b;
1190 }
1191 }
1192 return result;
1193 }
1194
1195 // Default
1196 template <typename TIterator1, typename TIterator2>
1197 ETL_NODISCARD
1198 ETL_CONSTEXPR14
1199 TIterator1 find_end(TIterator1 b, TIterator1 e,
1200 TIterator2 sb, TIterator2 se)
1201 {
1203
1204 return find_end(b, e, sb, se, predicate());
1205 }
1206
1207 //***************************************************************************
1211 //***************************************************************************
1212 template <typename TIterator, typename TCompare>
1213 ETL_NODISCARD
1214 ETL_CONSTEXPR14
1215 TIterator min_element(TIterator begin,
1216 TIterator end,
1217 TCompare compare)
1218 {
1219 TIterator minimum = begin;
1220 ++begin;
1221
1222 while (begin != end)
1223 {
1224 if (compare(*begin, *minimum))
1225 {
1226 minimum = begin;
1227 }
1228
1229 ++begin;
1230 }
1231
1232 return minimum;
1233 }
1234
1235 //***************************************************************************
1239 //***************************************************************************
1240 template <typename TIterator>
1241 ETL_NODISCARD
1242 ETL_CONSTEXPR14
1243 TIterator min_element(TIterator begin,
1244 TIterator end)
1245 {
1246 typedef typename etl::iterator_traits<TIterator>::value_type value_t;
1247
1249 }
1250
1251 //***************************************************************************
1255 //***************************************************************************
1256 template <typename TIterator, typename TCompare>
1257 ETL_NODISCARD
1258 ETL_CONSTEXPR14
1259 TIterator max_element(TIterator begin,
1260 TIterator end,
1261 TCompare compare)
1262 {
1263 TIterator maximum = begin;
1264 ++begin;
1265
1266 while (begin != end)
1267 {
1268 if (!compare(*begin, *maximum))
1269 {
1270 maximum = begin;
1271 }
1272
1273 ++begin;
1274 }
1275
1276 return maximum;
1277 }
1278
1279 //***************************************************************************
1283 //***************************************************************************
1284 template <typename TIterator>
1285 ETL_NODISCARD
1286 ETL_CONSTEXPR14
1287 TIterator max_element(TIterator begin,
1288 TIterator end)
1289 {
1290 typedef typename etl::iterator_traits<TIterator>::value_type value_t;
1291
1293 }
1294
1295 //***************************************************************************
1299 //***************************************************************************
1300 template <typename TIterator, typename TCompare>
1301 ETL_NODISCARD
1302 ETL_CONSTEXPR14
1303 ETL_OR_STD::pair<TIterator, TIterator> minmax_element(TIterator begin,
1304 TIterator end,
1305 TCompare compare)
1306 {
1307 TIterator minimum = begin;
1308 TIterator maximum = begin;
1309 ++begin;
1310
1311 while (begin != end)
1312 {
1313 if (compare(*begin, *minimum))
1314 {
1315 minimum = begin;
1316 }
1317
1318 if (compare(*maximum, *begin))
1319 {
1320 maximum = begin;
1321 }
1322
1323 ++begin;
1324 }
1325
1326 return ETL_OR_STD::pair<TIterator, TIterator>(minimum, maximum);
1327 }
1328
1329 //***************************************************************************
1333 //***************************************************************************
1334 template <typename TIterator>
1335 ETL_NODISCARD
1336 ETL_CONSTEXPR14
1337 ETL_OR_STD::pair<TIterator, TIterator> minmax_element(TIterator begin,
1338 TIterator end)
1339 {
1340 typedef typename etl::iterator_traits<TIterator>::value_type value_t;
1341
1343 }
1344
1345 //***************************************************************************
1349 //***************************************************************************
1350 template <typename T>
1351 ETL_NODISCARD
1352 ETL_CONSTEXPR14
1353 ETL_OR_STD::pair<const T&, const T&> minmax(const T& a,
1354 const T& b)
1355 {
1356 return (b < a) ? ETL_OR_STD::pair<const T&, const T&>(b, a) : ETL_OR_STD::pair<const T&, const T&>(a, b);
1357 }
1358
1359 //***************************************************************************
1363 //***************************************************************************
1364 template <typename T, typename TCompare>
1365 ETL_NODISCARD
1366 ETL_CONSTEXPR14
1367 ETL_OR_STD::pair<const T&, const T&> minmax(const T& a,
1368 const T& b,
1369 TCompare compare)
1370 {
1371 return compare(b, a) ? ETL_OR_STD::pair<const T&, const T&>(b, a) : ETL_OR_STD::pair<const T&, const T&>(a, b);
1372 }
1373
1374 //***************************************************************************
1378 //***************************************************************************
1379 template <typename TIterator>
1380 ETL_NODISCARD
1381 ETL_CONSTEXPR14
1382 TIterator is_sorted_until(TIterator begin,
1383 TIterator end)
1384 {
1385 if (begin != end)
1386 {
1387 TIterator next = begin;
1388
1389 while (++next != end)
1390 {
1391 if (*next < *begin)
1392 {
1393 return next;
1394 }
1395
1396 ++begin;
1397 }
1398 }
1399
1400 return end;
1401 }
1402
1403 //***************************************************************************
1407 //***************************************************************************
1408 template <typename TIterator, typename TCompare>
1409 ETL_NODISCARD
1410 ETL_CONSTEXPR14
1411 TIterator is_sorted_until(TIterator begin,
1412 TIterator end,
1413 TCompare compare)
1414 {
1415 if (begin != end)
1416 {
1417 TIterator next = begin;
1418
1419 while (++next != end)
1420 {
1421 if (compare(*next, *begin))
1422 {
1423 return next;
1424 }
1425
1426 ++begin;
1427 }
1428 }
1429
1430 return end;
1431 }
1432
1433 //***************************************************************************
1437 //***************************************************************************
1438 template<typename TIterator>
1439 ETL_NODISCARD
1440 ETL_CONSTEXPR14
1441 bool is_sorted(TIterator begin,
1442 TIterator end)
1443 {
1444 return etl::is_sorted_until(begin, end) == end;
1445 }
1446
1447 //***************************************************************************
1451 //***************************************************************************
1452 template<typename TIterator, typename TCompare>
1453 ETL_NODISCARD
1454 ETL_CONSTEXPR14
1455 bool is_sorted(TIterator begin,
1456 TIterator end,
1457 TCompare compare)
1458 {
1460 }
1461
1462 //***************************************************************************
1466 //***************************************************************************
1467 template <typename TIterator, typename TUnaryPredicate>
1468 ETL_NODISCARD
1469 ETL_CONSTEXPR14
1470 TIterator find_if_not(TIterator begin,
1471 TIterator end,
1472 TUnaryPredicate predicate)
1473 {
1474 while (begin != end)
1475 {
1476 if (!predicate(*begin))
1477 {
1478 return begin;
1479 }
1480
1481 ++begin;
1482 }
1483
1484 return end;
1485 }
1486
1487 //***************************************************************************
1491 //***************************************************************************
1492 template <typename TIterator1, typename TIterator2>
1493 ETL_NODISCARD
1494 ETL_CONSTEXPR14
1495 bool is_permutation(TIterator1 begin1,
1496 TIterator1 end1,
1497 TIterator2 begin2)
1498 {
1499 if (begin1 != end1)
1500 {
1501 TIterator2 end2 = begin2;
1502
1503 etl::advance(end2, etl::distance(begin1, end1));
1504
1505 for (TIterator1 i = begin1; i != end1; ++i)
1506 {
1507 if (i == etl::find(begin1, i, *i))
1508 {
1509 size_t n = etl::count(begin2, end2, *i);
1510
1511 if (n == 0 || size_t(etl::count(i, end1, *i)) != n)
1512 {
1513 return false;
1514 }
1515 }
1516 }
1517 }
1518
1519 return true;
1520 }
1521
1522 //***************************************************************************
1526 //***************************************************************************
1527 template <typename TIterator1, typename TIterator2, typename TBinaryPredicate>
1528 ETL_NODISCARD
1529 ETL_CONSTEXPR14
1530 bool is_permutation(TIterator1 begin1,
1531 TIterator1 end1,
1532 TIterator2 begin2,
1533 TBinaryPredicate predicate)
1534 {
1535 if (begin1 != end1)
1536 {
1537 TIterator2 end2 = begin2;
1538
1539 etl::advance(end2, etl::distance(begin1, end1));
1540
1541 for (TIterator1 i = begin1; i != end1; ++i)
1542 {
1543 if (i == etl::find_if(begin1, i, etl::bind1st(predicate, *i)))
1544 {
1545 size_t n = etl::count(begin2, end2, *i);
1546
1547 if (n == 0 || size_t(etl::count(i, end1, *i)) != n)
1548 {
1549 return false;
1550 }
1551 }
1552 }
1553 }
1554
1555 return true;
1556 }
1557
1558 //***************************************************************************
1562 //***************************************************************************
1563 template <typename TIterator1, typename TIterator2>
1564 ETL_NODISCARD
1565 ETL_CONSTEXPR14
1566 bool is_permutation(TIterator1 begin1,
1567 TIterator1 end1,
1568 TIterator2 begin2,
1569 TIterator2 end2)
1570 {
1571 if (begin1 != end1)
1572 {
1573 for (TIterator1 i = begin1; i != end1; ++i)
1574 {
1575 if (i == etl::find(begin1, i, *i))
1576 {
1577 size_t n = etl::count(begin2, end2, *i);
1578
1579 if (n == 0 || size_t(etl::count(i, end1, *i)) != n)
1580 {
1581 return false;
1582 }
1583 }
1584 }
1585 }
1586
1587 return true;
1588 }
1589
1590 //***************************************************************************
1594 //***************************************************************************
1595 template <typename TIterator1, typename TIterator2, typename TBinaryPredicate>
1596 ETL_NODISCARD
1597 bool is_permutation(TIterator1 begin1,
1598 TIterator1 end1,
1599 TIterator2 begin2,
1600 TIterator2 end2,
1601 TBinaryPredicate predicate)
1602 {
1603 if (begin1 != end1)
1604 {
1605 for (TIterator1 i = begin1; i != end1; ++i)
1606 {
1607 if (i == etl::find_if(begin1, i, etl::bind1st(predicate, *i)))
1608 {
1609 size_t n = etl::count(begin2, end2, *i);
1610
1611 if (n == 0 || size_t(etl::count(i, end1, *i)) != n)
1612 {
1613 return false;
1614 }
1615 }
1616 }
1617 }
1618
1619 return true;
1620 }
1621
1622 //***************************************************************************
1626 //***************************************************************************
1627 template <typename TIterator, typename TUnaryPredicate>
1628 ETL_NODISCARD
1629 ETL_CONSTEXPR14
1630 bool is_partitioned(TIterator begin,
1631 TIterator end,
1632 TUnaryPredicate predicate)
1633 {
1634 while (begin != end)
1635 {
1636 if (!predicate(*begin))
1637 {
1638 break;
1639 }
1640
1641 ++begin;
1642 }
1643
1644 while (begin != end)
1645 {
1646 if (predicate(*begin))
1647 {
1648 return false;
1649 }
1650
1651 ++begin;
1652 }
1653
1654 return true;
1655 }
1656
1657 //***************************************************************************
1661 //***************************************************************************
1662 template <typename TIterator, typename TUnaryPredicate>
1663 ETL_NODISCARD
1664 ETL_CONSTEXPR14
1665 TIterator partition_point(TIterator begin,
1666 TIterator end,
1667 TUnaryPredicate predicate)
1668 {
1669 while (begin != end)
1670 {
1671 if (!predicate(*begin))
1672 {
1673 return begin;
1674 }
1675
1676 ++begin;
1677 }
1678
1679 return begin;
1680 }
1681
1682 //***************************************************************************
1687 //***************************************************************************
1688 template <typename TSource, typename TDestinationTrue, typename TDestinationFalse, typename TUnaryPredicate>
1689 ETL_CONSTEXPR14
1690 ETL_OR_STD::pair<TDestinationTrue, TDestinationFalse> partition_copy(TSource begin,
1691 TSource end,
1692 TDestinationTrue destination_true,
1693 TDestinationFalse destination_false,
1694 TUnaryPredicate predicate)
1695 {
1696 while (begin != end)
1697 {
1698 if (predicate(*begin))
1699 {
1700 *destination_true = *begin;
1701 ++destination_true;
1702 }
1703 else
1704 {
1705 *destination_false = *begin;
1706 ++destination_false;
1707 }
1708
1709 ++begin;
1710 }
1711
1712 return ETL_OR_STD::pair<TDestinationTrue, TDestinationFalse>(destination_true, destination_false);
1713 }
1714
1715 //***************************************************************************
1719 //***************************************************************************
1720 template <typename TIterator, typename TOutputIterator, typename TUnaryPredicate>
1721 ETL_CONSTEXPR14
1722 TOutputIterator copy_if(TIterator begin,
1723 TIterator end,
1724 TOutputIterator out,
1725 TUnaryPredicate predicate)
1726 {
1727 while (begin != end)
1728 {
1729 if (predicate(*begin))
1730 {
1731 *out = *begin;
1732 ++out;
1733 }
1734
1735 ++begin;
1736 }
1737
1738 return out;
1739 }
1740
1741 //***************************************************************************
1745 //***************************************************************************
1746 template <typename TIterator, typename TUnaryPredicate>
1747 ETL_NODISCARD
1748 ETL_CONSTEXPR14
1749 bool all_of(TIterator begin,
1750 TIterator end,
1751 TUnaryPredicate predicate)
1752 {
1753 return etl::find_if_not(begin, end, predicate) == end;
1754 }
1755
1756 //***************************************************************************
1760 //***************************************************************************
1761 template <typename TIterator, typename TUnaryPredicate>
1762 ETL_NODISCARD
1763 ETL_CONSTEXPR14
1764 bool any_of(TIterator begin,
1765 TIterator end,
1766 TUnaryPredicate predicate)
1767 {
1768 return etl::find_if(begin, end, predicate) != end;
1769 }
1770
1771 //***************************************************************************
1775 //***************************************************************************
1776 template <typename TIterator, typename TUnaryPredicate>
1777 ETL_NODISCARD
1778 ETL_CONSTEXPR14
1779 bool none_of(TIterator begin,
1780 TIterator end,
1781 TUnaryPredicate predicate)
1782 {
1783 return etl::find_if(begin, end, predicate) == end;
1784 }
1785
1786#if ETL_NOT_USING_STL
1787 //***************************************************************************
1791 //***************************************************************************
1792 template <typename TIterator, typename TCompare>
1793 void sort(TIterator first, TIterator last, TCompare compare)
1794 {
1795 etl::shell_sort(first, last, compare);
1796 }
1797
1798 //***************************************************************************
1801 //***************************************************************************
1802 template <typename TIterator>
1803 void sort(TIterator first, TIterator last)
1804 {
1805 etl::shell_sort(first, last, etl::less<typename etl::iterator_traits<TIterator>::value_type>());
1806 }
1807
1808 //***************************************************************************
1813 //***************************************************************************
1814 template <typename TIterator, typename TCompare>
1815 void stable_sort(TIterator first, TIterator last, TCompare compare)
1816 {
1817 etl::insertion_sort(first, last, compare);
1818 }
1819
1820 //***************************************************************************
1824 //***************************************************************************
1825 template <typename TIterator>
1826 void stable_sort(TIterator first, TIterator last)
1827 {
1828 etl::insertion_sort(first, last, etl::less<typename etl::iterator_traits<TIterator>::value_type>());
1829 }
1830#else
1831 //***************************************************************************
1835 //***************************************************************************
1836 template <typename TIterator, typename TCompare>
1837 void sort(TIterator first, TIterator last, TCompare compare)
1838 {
1839 std::sort(first, last, compare);
1840 }
1841
1842 //***************************************************************************
1845 //***************************************************************************
1846 template <typename TIterator>
1847 void sort(TIterator first, TIterator last)
1848 {
1849 std::sort(first, last);
1850 }
1851
1852 //***************************************************************************
1857 //***************************************************************************
1858 template <typename TIterator, typename TCompare>
1859 void stable_sort(TIterator first, TIterator last, TCompare compare)
1860 {
1861 std::stable_sort(first, last, compare);
1862 }
1863
1864 //***************************************************************************
1868 //***************************************************************************
1869 template <typename TIterator>
1870 void stable_sort(TIterator first, TIterator last)
1871 {
1872 std::stable_sort(first, last);
1873 }
1874#endif
1875
1876 //***************************************************************************
1879 //***************************************************************************
1880 template <typename TIterator, typename T>
1881 ETL_CONSTEXPR14
1882 T accumulate(TIterator first, TIterator last, T sum)
1883 {
1884 while (first != last)
1885 {
1886 sum = etl::move(sum) + *first;
1887 ++first;
1888 }
1889
1890 return sum;
1891 }
1892
1893 //***************************************************************************
1896 //***************************************************************************
1897 template <typename TIterator, typename T, typename TBinaryOperation>
1898 ETL_CONSTEXPR14
1899 T accumulate(TIterator first, TIterator last, T sum, TBinaryOperation operation)
1900 {
1901 while (first != last)
1902 {
1903 sum = operation(etl::move(sum), *first);
1904 ++first;
1905 }
1906
1907 return sum;
1908 }
1909
1910 //***************************************************************************
1913 //***************************************************************************
1914 template<typename T, typename TCompare>
1915 ETL_CONSTEXPR
1916 const T& clamp(const T& value, const T& low, const T& high, TCompare compare)
1917 {
1918 return compare(value, low) ? low : compare(high, value) ? high : value;
1919 }
1920
1921 template <typename T>
1922 ETL_CONSTEXPR
1923 const T& clamp(const T& value, const T& low, const T& high )
1924 {
1925 return clamp(value, low, high, etl::less<T>());
1926 }
1927
1928 //***************************************************************************
1931 //***************************************************************************
1932 template <typename TIterator, typename T>
1933 ETL_CONSTEXPR14
1934 TIterator remove(TIterator first, TIterator last, const T& value)
1935 {
1936 first = etl::find(first, last, value);
1937
1938 if (first != last)
1939 {
1940 TIterator itr = first;
1941
1942 while (itr != last)
1943 {
1944 if (!(*itr == value))
1945 {
1946 *first = etl::move(*itr);
1947 ++first;
1948 }
1949
1950 ++itr;
1951 }
1952 }
1953
1954 return first;
1955 }
1956
1957 //***************************************************************************
1960 //***************************************************************************
1961 template <typename TIterator, typename TUnaryPredicate>
1962 ETL_CONSTEXPR14
1963 TIterator remove_if(TIterator first, TIterator last, TUnaryPredicate predicate)
1964 {
1965 first = etl::find_if(first, last, predicate);
1966
1967 if (first != last)
1968 {
1969 TIterator itr = first;
1970
1971 while (itr != last)
1972 {
1973 if (!predicate(*itr))
1974 {
1975 *first = etl::move(*itr);
1976 ++first;
1977 }
1978
1979 ++itr;
1980 }
1981 }
1982
1983 return first;
1984 }
1985}
1986
1987//*****************************************************************************
1988// ETL extensions to the STL algorithms.
1989//*****************************************************************************
1990namespace etl
1991{
1992 //***************************************************************************
2002 //***************************************************************************
2003 template <typename TInputIterator,
2004 typename TOutputIterator>
2005 ETL_CONSTEXPR14
2008 copy_s(TInputIterator i_begin,
2009 TInputIterator i_end,
2010 TOutputIterator o_begin,
2011 TOutputIterator o_end)
2012 {
2013 size_t s_size = etl::distance(i_begin, i_end);
2014 size_t d_size = etl::distance(o_begin, o_end);
2015 size_t size = (s_size < d_size) ? s_size : d_size;
2016
2017 return etl::copy(i_begin, i_begin + size, o_begin);
2018 }
2019
2020 //***************************************************************************
2030 //***************************************************************************
2031 template <typename TInputIterator,
2032 typename TOutputIterator>
2033 ETL_CONSTEXPR14
2036 copy_s(TInputIterator i_begin,
2037 TInputIterator i_end,
2038 TOutputIterator o_begin,
2039 TOutputIterator o_end)
2040 {
2041 while ((i_begin != i_end) && (o_begin != o_end))
2042 {
2043 *o_begin = *i_begin;
2044 ++o_begin;
2045 ++i_begin;
2046 }
2047
2048 return o_begin;
2049 }
2050
2051 //***************************************************************************
2055 //***************************************************************************
2056 template <typename TInputIterator,
2057 typename TSize,
2058 typename TOutputIterator>
2059 ETL_CONSTEXPR14
2060 TOutputIterator copy_n_s(TInputIterator i_begin,
2061 TSize n,
2062 TOutputIterator o_begin,
2063 TOutputIterator o_end)
2064 {
2065 while ((n-- > 0) && (o_begin != o_end))
2066 {
2067 *o_begin = *i_begin;
2068 ++o_begin;
2069 ++i_begin;
2070 }
2071
2072 return o_begin;
2073 }
2074
2075 //***************************************************************************
2079 //***************************************************************************
2080 template <typename TInputIterator,
2081 typename TSize1,
2082 typename TOutputIterator,
2083 typename TSize2>
2084 ETL_CONSTEXPR14
2085 TOutputIterator copy_n_s(TInputIterator i_begin,
2086 TSize1 n1,
2087 TOutputIterator o_begin,
2088 TSize2 n2)
2089 {
2090 while ((n1-- > 0) && (n2-- > 0))
2091 {
2092 *o_begin = *i_begin;
2093 ++o_begin;
2094 ++i_begin;
2095 }
2096
2097 return o_begin;
2098 }
2099
2100 //***************************************************************************
2105 //***************************************************************************
2106 template <typename TInputIterator,
2107 typename TOutputIterator,
2108 typename TUnaryPredicate>
2109 ETL_CONSTEXPR14
2110 TOutputIterator copy_if_s(TInputIterator i_begin,
2111 TInputIterator i_end,
2112 TOutputIterator o_begin,
2113 TOutputIterator o_end,
2114 TUnaryPredicate predicate)
2115 {
2116 while ((i_begin != i_end) && (o_begin != o_end))
2117 {
2118 if (predicate(*i_begin))
2119 {
2120 *o_begin = *i_begin;
2121 ++o_begin;
2122 }
2123
2124 ++i_begin;
2125 }
2126
2127 return o_begin;
2128 }
2129
2130 //***************************************************************************
2134 //***************************************************************************
2135 template <typename TInputIterator,
2136 typename TSize,
2137 typename TOutputIterator,
2138 typename TUnaryPredicate>
2139 ETL_CONSTEXPR14
2140 TOutputIterator copy_n_if(TInputIterator i_begin,
2141 TSize n,
2142 TOutputIterator o_begin,
2143 TUnaryPredicate predicate)
2144 {
2145 while (n-- > 0)
2146 {
2147 if (predicate(*i_begin))
2148 {
2149 *o_begin = *i_begin;
2150 ++o_begin;
2151 }
2152
2153 ++i_begin;
2154 }
2155
2156 return o_begin;
2157 }
2158
2159#if ETL_USING_CPP11
2160 //***************************************************************************
2170 //***************************************************************************
2171 template <typename TInputIterator, typename TOutputIterator>
2172 ETL_CONSTEXPR14
2175 move_s(TInputIterator i_begin,
2176 TInputIterator i_end,
2177 TOutputIterator o_begin,
2178 TOutputIterator o_end)
2179 {
2180 size_t s_size = etl::distance(i_begin, i_end);
2181 size_t d_size = etl::distance(o_begin, o_end);
2182 size_t size = (s_size < d_size) ? s_size : d_size;
2183
2184 return etl::move(i_begin, i_begin + size, o_begin);
2185 }
2186
2187 //***************************************************************************
2197 //***************************************************************************
2198 template <typename TInputIterator, typename TOutputIterator>
2199 ETL_CONSTEXPR14
2202 move_s(TInputIterator i_begin,
2203 TInputIterator i_end,
2204 TOutputIterator o_begin,
2205 TOutputIterator o_end)
2206 {
2207 while ((i_begin != i_end) && (o_begin != o_end))
2208 {
2209 *o_begin = etl::move(*i_begin);
2210 ++i_begin;
2211 ++o_begin;
2212 }
2213
2214 return o_begin;
2215 }
2216#else
2217 //***************************************************************************
2228 //***************************************************************************
2229 template <typename TInputIterator, typename TOutputIterator>
2230 TOutputIterator move_s(TInputIterator i_begin,
2231 TInputIterator i_end,
2232 TOutputIterator o_begin,
2233 TOutputIterator o_end)
2234 {
2235 // Move not supported. Defer to copy.
2236 return etl::copy_s(i_begin, i_end, o_begin, o_end);
2237 }
2238#endif
2239
2240 //***************************************************************************
2244 //***************************************************************************
2245 template <typename TIterator, typename TValue>
2246 ETL_NODISCARD
2247 ETL_CONSTEXPR14
2248 TIterator binary_find(TIterator begin,
2249 TIterator end,
2250 const TValue& value)
2251 {
2252 TIterator it = etl::lower_bound(begin, end, value);
2253
2254 if ((it == end) || (*it != value))
2255 {
2256 it = end;
2257 }
2258
2259 return it;
2260 }
2261
2262 //***************************************************************************
2266 //***************************************************************************
2267 template <typename TIterator,
2268 typename TValue,
2269 typename TBinaryPredicate,
2270 typename TBinaryEquality>
2271 ETL_NODISCARD
2272 ETL_CONSTEXPR14
2273 TIterator binary_find(TIterator begin,
2274 TIterator end,
2275 const TValue& value,
2276 TBinaryPredicate predicate,
2277 TBinaryEquality equality)
2278 {
2279 TIterator it = etl::lower_bound(begin, end, value, predicate);
2280
2281 if ((it == end) || !equality(*it, value))
2282 {
2283 it = end;
2284 }
2285
2286 return it;
2287 }
2288
2289 //***************************************************************************
2292 //***************************************************************************
2293 template <typename TIterator,
2294 typename TUnaryFunction,
2295 typename TUnaryPredicate>
2296 ETL_CONSTEXPR14
2297 TUnaryFunction for_each_if(TIterator begin,
2298 const TIterator end,
2299 TUnaryFunction function,
2300 TUnaryPredicate predicate)
2301 {
2302 while (begin != end)
2303 {
2304 if (predicate(*begin))
2305 {
2306 function(*begin);
2307 }
2308
2309 ++begin;
2310 }
2311
2312 return function;
2313 }
2314
2315 //***************************************************************************
2318 //***************************************************************************
2319 template <typename TIterator,
2320 typename TSize,
2321 typename TUnaryFunction>
2322 ETL_CONSTEXPR14
2323 TIterator for_each_n(TIterator begin,
2324 TSize n,
2325 TUnaryFunction function)
2326 {
2327 while (n-- > 0)
2328 {
2329 function(*begin);
2330 ++begin;
2331 }
2332
2333 return begin;
2334 }
2335
2336 //***************************************************************************
2339 //***************************************************************************
2340 template <typename TIterator,
2341 typename TSize,
2342 typename TUnaryFunction,
2343 typename TUnaryPredicate>
2344 ETL_CONSTEXPR14
2345 TIterator for_each_n_if(TIterator begin,
2346 TSize n,
2347 TUnaryFunction function,
2348 TUnaryPredicate predicate)
2349 {
2350 while (n-- > 0)
2351 {
2352 if (predicate(*begin))
2353 {
2354 function(*begin);
2355 }
2356
2357 ++begin;
2358 }
2359
2360 return begin;
2361 }
2362
2363 //***************************************************************************
2368 //***************************************************************************
2369 template <typename TInputIterator, typename TOutputIterator, typename TUnaryFunction>
2370 ETL_CONSTEXPR14
2371 TOutputIterator transform_s(TInputIterator i_begin,
2372 TInputIterator i_end,
2373 TOutputIterator o_begin,
2374 TOutputIterator o_end,
2375 TUnaryFunction function)
2376 {
2377 while ((i_begin != i_end) && (o_begin != o_end))
2378 {
2379 *o_begin = function(*i_begin);
2380 ++i_begin;
2381 ++o_begin;
2382 }
2383
2384 return o_begin;
2385 }
2386
2387 //***************************************************************************
2392 //***************************************************************************
2393 template <typename TInputIterator,
2394 typename TSize,
2395 typename TOutputIterator,
2396 typename TUnaryFunction>
2397 ETL_CONSTEXPR14
2398 void transform_n(TInputIterator i_begin,
2399 TSize n,
2400 TOutputIterator o_begin,
2401 TUnaryFunction function)
2402 {
2403 TInputIterator i_end(i_begin);
2404 etl::advance(i_end, n);
2405
2406 etl::transform(i_begin, i_end, o_begin, function);
2407 }
2408
2409 //***************************************************************************
2414 //***************************************************************************
2415 template <typename TInputIterator1,
2416 typename TInputIterator2,
2417 typename TSize,
2418 typename TOutputIterator,
2419 typename TBinaryFunction>
2420 ETL_CONSTEXPR14
2421 void transform_n(TInputIterator1 i_begin1,
2422 TInputIterator2 i_begin2,
2423 TSize n,
2424 TOutputIterator o_begin,
2425 TBinaryFunction function)
2426 {
2427 TInputIterator1 i_end1(i_begin1);
2428 etl::advance(i_end1, n);
2429
2430 etl::transform(i_begin1, i_end1, i_begin2, o_begin, function);
2431 }
2432
2433 //***************************************************************************
2436 //***************************************************************************
2437 template <typename TInputIterator,
2438 typename TOutputIterator,
2439 typename TUnaryFunction,
2440 typename TUnaryPredicate>
2441 ETL_CONSTEXPR14
2442 TOutputIterator transform_if(TInputIterator i_begin,
2443 const TInputIterator i_end,
2444 TOutputIterator o_begin,
2445 TUnaryFunction function,
2446 TUnaryPredicate predicate)
2447 {
2448 while (i_begin != i_end)
2449 {
2450 if (predicate(*i_begin))
2451 {
2452 *o_begin = function(*i_begin);
2453 ++o_begin;
2454 }
2455
2456 ++i_begin;
2457 }
2458
2459 return o_begin;
2460 }
2461
2462 //***************************************************************************
2465 //***************************************************************************
2466 template <typename TInputIterator1,
2467 typename TInputIterator2,
2468 typename TOutputIterator,
2469 typename TBinaryFunction,
2470 typename TBinaryPredicate>
2471 ETL_CONSTEXPR14
2472 TOutputIterator transform_if(TInputIterator1 i_begin1,
2473 const TInputIterator1 i_end1,
2474 TInputIterator2 i_begin2,
2475 TOutputIterator o_begin,
2476 TBinaryFunction function,
2477 TBinaryPredicate predicate)
2478 {
2479 while (i_begin1 != i_end1)
2480 {
2481 if (predicate(*i_begin1, *i_begin2))
2482 {
2483 *o_begin = function(*i_begin1, *i_begin2);
2484 ++o_begin;
2485 }
2486
2487 ++i_begin1;
2488 ++i_begin2;
2489 }
2490
2491 return o_begin;
2492 }
2493
2494 //***************************************************************************
2497 //***************************************************************************
2498 template <typename TInputIterator,
2499 typename TSize,
2500 typename TOutputIterator,
2501 typename TUnaryFunction,
2502 typename TUnaryPredicate>
2503 ETL_CONSTEXPR14
2504 TOutputIterator transform_n_if(TInputIterator i_begin,
2505 TSize n,
2506 TOutputIterator o_begin,
2507 TUnaryFunction function,
2508 TUnaryPredicate predicate)
2509 {
2510 while (n-- > 0)
2511 {
2512 if (predicate(*i_begin))
2513 {
2514 *o_begin = function(*i_begin);
2515 ++o_begin;
2516 }
2517
2518 ++i_begin;
2519 }
2520
2521 return o_begin;
2522 }
2523
2524 //***************************************************************************
2527 //***************************************************************************
2528 template <typename TInputIterator1,
2529 typename TInputIterator2,
2530 typename TSize,
2531 typename TOutputIterator,
2532 typename TBinaryFunction,
2533 typename TBinaryPredicate>
2534 ETL_CONSTEXPR14
2535 TOutputIterator transform_n_if(TInputIterator1 i_begin1,
2536 TInputIterator2 i_begin2,
2537 TSize n,
2538 TOutputIterator o_begin,
2539 TBinaryFunction function,
2540 TBinaryPredicate predicate)
2541 {
2542 while (n-- > 0)
2543 {
2544 if (predicate(*i_begin1, *i_begin2))
2545 {
2546 *o_begin++ = function(*i_begin1, *i_begin2);
2547 }
2548
2549 ++i_begin1;
2550 ++i_begin2;
2551 }
2552
2553 return o_begin;
2554 }
2555
2556 //***************************************************************************
2560 //***************************************************************************
2561 template <typename TSource, typename TDestinationTrue, typename TDestinationFalse,
2562 typename TUnaryFunctionTrue, typename TUnaryFunctionFalse,
2563 typename TUnaryPredicate>
2564 ETL_CONSTEXPR14
2565 ETL_OR_STD::pair<TDestinationTrue, TDestinationFalse> partition_transform(TSource begin,
2566 TSource end,
2567 TDestinationTrue destination_true,
2568 TDestinationFalse destination_false,
2569 TUnaryFunctionTrue function_true,
2570 TUnaryFunctionFalse function_false,
2571 TUnaryPredicate predicate)
2572 {
2573 while (begin != end)
2574 {
2575 if (predicate(*begin))
2576 {
2577 *destination_true = function_true(*begin);
2578 ++destination_true;
2579 }
2580 else
2581 {
2582 *destination_false = function_false(*begin);
2583 ++destination_false;
2584 }
2585
2586 ++begin;
2587 }
2588
2589 return ETL_OR_STD::pair<TDestinationTrue, TDestinationFalse>(destination_true, destination_false);
2590 }
2591
2592 //***************************************************************************
2596 //***************************************************************************
2597 template <typename TSource1,
2598 typename TSource2,
2599 typename TDestinationTrue,
2600 typename TDestinationFalse,
2601 typename TBinaryFunctionTrue,
2602 typename TBinaryFunctionFalse,
2603 typename TBinaryPredicate>
2604 ETL_CONSTEXPR14
2605 ETL_OR_STD::pair<TDestinationTrue, TDestinationFalse> partition_transform(TSource1 begin1,
2606 TSource1 end1,
2607 TSource2 begin2,
2608 TDestinationTrue destination_true,
2609 TDestinationFalse destination_false,
2610 TBinaryFunctionTrue function_true,
2611 TBinaryFunctionFalse function_false,
2612 TBinaryPredicate predicate)
2613 {
2614 while (begin1 != end1)
2615 {
2616 if (predicate(*begin1, *begin2))
2617 {
2618 *destination_true = function_true(*begin1, *begin2);
2619 ++destination_true;
2620 }
2621 else
2622 {
2623 *destination_false = function_false(*begin1, *begin2);
2624 ++destination_false;
2625 }
2626
2627 ++begin1;
2628 ++begin2;
2629 }
2630
2631 return ETL_OR_STD::pair<TDestinationTrue, TDestinationFalse>(destination_true, destination_false);
2632 }
2633
2634 //***************************************************************************
2638 //***************************************************************************
2639 template <typename TIterator, typename TCompare>
2640#if ETL_USING_STD_NAMESPACE
2641 ETL_CONSTEXPR20
2642#else
2643 ETL_CONSTEXPR14
2644#endif
2645 void shell_sort(TIterator first, TIterator last, TCompare compare)
2646 {
2647 if (first == last)
2648 {
2649 return;
2650 }
2651
2652 typedef typename etl::iterator_traits<TIterator>::difference_type difference_t;
2653
2654 difference_t n = etl::distance(first, last);
2655
2656 for (difference_t i = n / 2; i > 0; i /= 2)
2657 {
2658 for (difference_t j = i; j < n; ++j)
2659 {
2660 for (difference_t k = j - i; k >= 0; k -= i)
2661 {
2662 TIterator itr1 = first;
2663 TIterator itr2 = first;
2664
2665 etl::advance(itr1, k);
2666 etl::advance(itr2, k + i);
2667
2668 if (compare(*itr2, *itr1))
2669 {
2670 etl::iter_swap(itr1, itr2);
2671 }
2672 }
2673 }
2674 }
2675 }
2676
2677 //***************************************************************************
2680 //***************************************************************************
2681 template <typename TIterator>
2682#if ETL_USING_STD_NAMESPACE
2683 ETL_CONSTEXPR20
2684#else
2685 ETL_CONSTEXPR14
2686#endif
2687 void shell_sort(TIterator first, TIterator last)
2688 {
2689 etl::shell_sort(first, last, etl::less<typename etl::iterator_traits<TIterator>::value_type>());
2690 }
2691
2692 //***************************************************************************
2696 //***************************************************************************
2697 template <typename TIterator, typename TCompare>
2698 ETL_CONSTEXPR14
2699 void insertion_sort(TIterator first, TIterator last, TCompare compare)
2700 {
2701 for (TIterator itr = first; itr != last; ++itr)
2702 {
2703 etl::rotate(etl::upper_bound(first, itr, *itr, compare), itr, etl::next(itr));
2704 }
2705 }
2706
2707 //***************************************************************************
2710 //***************************************************************************
2711 template <typename TIterator>
2712 ETL_CONSTEXPR14
2713 void insertion_sort(TIterator first, TIterator last)
2714 {
2715 etl::insertion_sort(first, last, etl::less<typename etl::iterator_traits<TIterator>::value_type>());
2716 }
2717
2718 //***************************************************************************
2719 namespace private_algorithm
2720 {
2721 template <typename TIterator>
2722 ETL_CONSTEXPR14
2724 get_before_last(TIterator first_, TIterator last_)
2725 {
2726 TIterator last = first_;
2727 TIterator lastplus1 = first_;
2728 ++lastplus1;
2729
2730 while (lastplus1 != last_)
2731 {
2732 ++last;
2733 ++lastplus1;
2734 }
2735
2736 return last;
2737 }
2738
2739 template <typename TIterator>
2740 ETL_CONSTEXPR14
2742 get_before_last(TIterator /*first_*/, TIterator last_)
2743 {
2744 TIterator last = last_;
2745 --last;
2746
2747 return last;
2748 }
2749
2750 template <typename TIterator>
2751 ETL_CONSTEXPR14
2753 get_before_last(TIterator /*first_*/, TIterator last_)
2754 {
2755 return last_ - 1;
2756 }
2757 }
2758
2759 //***************************************************************************
2763 //***************************************************************************
2764 template <typename TIterator, typename TCompare>
2765 ETL_CONSTEXPR20
2766 void selection_sort(TIterator first, TIterator last, TCompare compare)
2767 {
2768 TIterator min;
2769 const TIterator ilast = private_algorithm::get_before_last(first, last);
2770 const TIterator jlast = last;
2771
2772 for (TIterator i = first; i != ilast; ++i)
2773 {
2774 min = i;
2775
2776 TIterator j = i;
2777 ++j;
2778
2779 for (; j != jlast; ++j)
2780 {
2781 if (compare(*j, *min))
2782 {
2783 min = j;
2784 }
2785 }
2786
2787 using ETL_OR_STD::swap; // Allow ADL
2788 swap(*i, *min);
2789 }
2790 }
2791
2792 //***************************************************************************
2795 //***************************************************************************
2796 template <typename TIterator>
2797 ETL_CONSTEXPR20
2798 void selection_sort(TIterator first, TIterator last)
2799 {
2800 selection_sort(first, last, etl::less<typename etl::iterator_traits<TIterator>::value_type>());
2801 }
2802
2803 //***************************************************************************
2807 //***************************************************************************
2808 template <typename TIterator, typename TCompare>
2809 ETL_CONSTEXPR14
2810 void heap_sort(TIterator first, TIterator last, TCompare compare)
2811 {
2812 if (!etl::is_heap(first, last, compare))
2813 {
2814 etl::make_heap(first, last, compare);
2815 }
2816
2817 etl::sort_heap(first, last, compare);
2818 }
2819
2820 //***************************************************************************
2823 //***************************************************************************
2824 template <typename TIterator>
2825 ETL_CONSTEXPR14
2826 void heap_sort(TIterator first, TIterator last)
2827 {
2828 if (!etl::is_heap(first, last))
2829 {
2830 etl::make_heap(first, last);
2831 }
2832
2833 etl::sort_heap(first, last);
2834 }
2835
2836 //***************************************************************************
2838 //***************************************************************************
2839#if ETL_USING_CPP11
2840 template <typename T>
2841 ETL_NODISCARD
2842 constexpr const T& multimax(const T& a, const T& b)
2843 {
2844 return a < b ? b : a;
2845 }
2846
2847 template <typename T, typename... Tx>
2848 ETL_NODISCARD
2849 constexpr const T& multimax(const T& t, const Tx&... tx)
2850 {
2851 return multimax(t, multimax(tx...));
2852 }
2853#endif
2854
2855 //***************************************************************************
2858 //***************************************************************************
2859#if ETL_USING_CPP11
2860 template <typename TCompare, typename T>
2861 ETL_NODISCARD
2862 constexpr const T& multimax_compare(TCompare compare, const T& a, const T& b)
2863 {
2864 return compare(a, b) ? b : a;
2865 }
2866
2867 template <typename TCompare, typename T, typename... Tx>
2868 ETL_NODISCARD
2869 constexpr const T& multimax_compare(TCompare compare, const T& t, const Tx&... tx)
2870 {
2871 return multimax_compare(compare, t, multimax_compare(compare, tx...));
2872 }
2873#endif
2874
2875 //***************************************************************************
2877 //***************************************************************************
2878#if ETL_USING_CPP11
2879 template <typename T>
2880 ETL_NODISCARD
2881 constexpr const T& multimin(const T& a, const T& b)
2882 {
2883 return a < b ? a : b;
2884 }
2885
2886 template <typename T, typename... Tx>
2887 ETL_NODISCARD
2888 constexpr const T& multimin(const T& t, const Tx&... tx)
2889 {
2890 return multimin(t, multimin(tx...));
2891 }
2892#endif
2893
2894 //***************************************************************************
2897 //***************************************************************************
2898#if ETL_USING_CPP11
2899 template <typename TCompare, typename T>
2900 ETL_NODISCARD
2901 constexpr const T& multimin_compare(TCompare compare, const T& a, const T& b)
2902 {
2903 return compare(a, b) ? a : b;
2904 }
2905
2906 template <typename TCompare, typename T, typename... Tx>
2907 ETL_NODISCARD
2908 constexpr const T& multimin_compare(TCompare compare, const T& t, const Tx&... tx)
2909 {
2910 return multimin_compare(compare, t, multimin_compare(compare, tx...));
2911 }
2912#endif
2913
2914 //***************************************************************************
2916 //***************************************************************************
2917#if ETL_USING_CPP11
2918 template <typename TIterator>
2919 ETL_NODISCARD
2920 constexpr const TIterator& multimax_iter(const TIterator& a, const TIterator& b)
2921 {
2922 return *a < *b ? b : a;
2923 }
2924
2925 template <typename TIterator, typename... TIteratorx>
2926 ETL_NODISCARD
2927 constexpr const TIterator& multimax_iter(const TIterator& t, const TIteratorx&... tx)
2928 {
2929 return multimax_iter(t, multimax_iter(tx...));
2930 }
2931#endif
2932
2933 //***************************************************************************
2936 //***************************************************************************
2937#if ETL_USING_CPP11
2938 template <typename TCompare, typename TIterator>
2939 ETL_NODISCARD
2940 constexpr const TIterator& multimax_iter_compare(TCompare compare, const TIterator& a, const TIterator& b)
2941 {
2942 return compare(*a, *b) ? b : a;
2943 }
2944
2945 template <typename TCompare, typename TIterator, typename... TIteratorx>
2946 ETL_NODISCARD
2947 constexpr const TIterator& multimax_iter_compare(TCompare compare, const TIterator& t, const TIteratorx&... tx)
2948 {
2949 return multimax_iter_compare(compare, t, multimax_iter_compare(compare, tx...));
2950 }
2951#endif
2952
2953 //***************************************************************************
2955 //***************************************************************************
2956#if ETL_USING_CPP11
2957 template <typename TIterator>
2958 ETL_NODISCARD
2959 constexpr const TIterator& multimin_iter(const TIterator& a, const TIterator& b)
2960 {
2961 return *a < *b ? a : b;
2962 }
2963
2964 template <typename TIterator, typename... Tx>
2965 ETL_NODISCARD
2966 constexpr const TIterator& multimin_iter(const TIterator& t, const Tx&... tx)
2967 {
2968 return multimin_iter(t, multimin_iter(tx...));
2969 }
2970#endif
2971
2972 //***************************************************************************
2975 //***************************************************************************
2976#if ETL_USING_CPP11
2977 template <typename TCompare, typename TIterator>
2978 ETL_NODISCARD
2979 constexpr const TIterator& multimin_iter_compare(TCompare compare, const TIterator& a, const TIterator& b)
2980 {
2981 return compare(*a, *b) ? a : b;
2982 }
2983
2984 template <typename TCompare, typename TIterator, typename... Tx>
2985 ETL_NODISCARD
2986 constexpr const TIterator& multimin_iter_compare(TCompare compare, const TIterator& t, const Tx&... tx)
2987 {
2988 return multimin_iter_compare(compare, t, multimin_iter_compare(compare, tx...));
2989 }
2990#endif
2991}
2992
2993#include "private/minmax_pop.h"
2994
2995#endif
ETL_CONSTEXPR20 void shell_sort(TIterator first, TIterator last)
Definition: algorithm.h:2687
ETL_CONSTEXPR14 TOutputIterator copy_if(TIterator begin, TIterator end, TOutputIterator out, TUnaryPredicate predicate)
Definition: algorithm.h:1722
ETL_CONSTEXPR14 ETL_OR_STD::pair< TDestinationTrue, TDestinationFalse > partition_transform(TSource begin, TSource end, TDestinationTrue destination_true, TDestinationFalse destination_false, TUnaryFunctionTrue function_true, TUnaryFunctionFalse function_false, TUnaryPredicate predicate)
Definition: algorithm.h:2565
ETL_NODISCARD ETL_CONSTEXPR14 bool any_of(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition: algorithm.h:1764
ETL_NODISCARD ETL_CONSTEXPR14 TIterator min_element(TIterator begin, TIterator end, TCompare compare)
Definition: algorithm.h:1215
ETL_CONSTEXPR14 TOutputIterator transform_n_if(TInputIterator i_begin, TSize n, TOutputIterator o_begin, TUnaryFunction function, TUnaryPredicate predicate)
Definition: algorithm.h:2504
ETL_CONSTEXPR14 T accumulate(TIterator first, TIterator last, T sum)
Definition: algorithm.h:1882
ETL_NODISCARD ETL_CONSTEXPR14 bool all_of(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition: algorithm.h:1749
ETL_NODISCARD ETL_CONSTEXPR14 ETL_OR_STD::pair< TIterator, TIterator > minmax_element(TIterator begin, TIterator end, TCompare compare)
Definition: algorithm.h:1303
void sort(TIterator first, TIterator last)
Definition: algorithm.h:1847
ETL_CONSTEXPR14 TOutputIterator transform_if(TInputIterator i_begin, const TInputIterator i_end, TOutputIterator o_begin, TUnaryFunction function, TUnaryPredicate predicate)
Definition: algorithm.h:2442
ETL_CONSTEXPR14 TUnaryFunction for_each_if(TIterator begin, const TIterator end, TUnaryFunction function, TUnaryPredicate predicate)
Definition: algorithm.h:2297
ETL_NODISCARD ETL_CONSTEXPR14 TIterator find_if_not(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition: algorithm.h:1470
ETL_NODISCARD ETL_CONSTEXPR14 bool is_sorted(TIterator begin, TIterator end)
Definition: algorithm.h:1441
ETL_CONSTEXPR14 TOutputIterator transform_s(TInputIterator i_begin, TInputIterator i_end, TOutputIterator o_begin, TOutputIterator o_end, TUnaryFunction function)
Definition: algorithm.h:2371
ETL_CONSTEXPR14 TIterator remove(TIterator first, TIterator last, const T &value)
Definition: algorithm.h:1934
ETL_CONSTEXPR14 void transform_n(TInputIterator i_begin, TSize n, TOutputIterator o_begin, TUnaryFunction function)
Definition: algorithm.h:2398
ETL_CONSTEXPR14 TOutputIterator copy_n_if(TInputIterator i_begin, TSize n, TOutputIterator o_begin, TUnaryPredicate predicate)
Definition: algorithm.h:2140
ETL_NODISCARD ETL_CONSTEXPR14 TIterator is_sorted_until(TIterator begin, TIterator end)
Definition: algorithm.h:1382
ETL_CONSTEXPR14 void insertion_sort(TIterator first, TIterator last)
Definition: algorithm.h:2713
void sort(TIterator first, TIterator last, TCompare compare)
Definition: algorithm.h:1837
ETL_NODISCARD ETL_CONSTEXPR14 ETL_OR_STD::pair< const T &, const T & > minmax(const T &a, const T &b)
Definition: algorithm.h:1353
ETL_CONSTEXPR14 etl::enable_if< etl::is_random_iterator< TInputIterator >::value &&etl::is_random_iterator< TOutputIterator >::value, TOutputIterator >::type copy_s(TInputIterator i_begin, TInputIterator i_end, TOutputIterator o_begin, TOutputIterator o_end)
Definition: algorithm.h:2008
ETL_CONSTEXPR const T & clamp(const T &value, const T &low, const T &high, TCompare compare)
Definition: algorithm.h:1916
ETL_CONSTEXPR14 TIterator remove_if(TIterator first, TIterator last, TUnaryPredicate predicate)
Definition: algorithm.h:1963
ETL_CONSTEXPR14 ETL_OR_STD::pair< TDestinationTrue, TDestinationFalse > partition_copy(TSource begin, TSource end, TDestinationTrue destination_true, TDestinationFalse destination_false, TUnaryPredicate predicate)
Definition: algorithm.h:1690
ETL_CONSTEXPR14 TIterator for_each_n(TIterator begin, TSize n, TUnaryFunction function)
Definition: algorithm.h:2323
ETL_NODISCARD ETL_CONSTEXPR14 TIterator binary_find(TIterator begin, TIterator end, const TValue &value)
Definition: algorithm.h:2248
ETL_CONSTEXPR14 void heap_sort(TIterator first, TIterator last, TCompare compare)
Definition: algorithm.h:2810
ETL_NODISCARD ETL_CONSTEXPR14 bool none_of(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition: algorithm.h:1779
ETL_CONSTEXPR20 void selection_sort(TIterator first, TIterator last, TCompare compare)
Definition: algorithm.h:2766
ETL_CONSTEXPR14 TOutputIterator copy_n_s(TInputIterator i_begin, TSize n, TOutputIterator o_begin, TOutputIterator o_end)
Definition: algorithm.h:2060
TOutputIterator move_s(TInputIterator i_begin, TInputIterator i_end, TOutputIterator o_begin, TOutputIterator o_end)
Definition: algorithm.h:2230
ETL_CONSTEXPR14 TOutputIterator copy_if_s(TInputIterator i_begin, TInputIterator i_end, TOutputIterator o_begin, TOutputIterator o_end, TUnaryPredicate predicate)
Definition: algorithm.h:2110
ETL_CONSTEXPR14 TIterator for_each_n_if(TIterator begin, TSize n, TUnaryFunction function, TUnaryPredicate predicate)
Definition: algorithm.h:2345
void stable_sort(TIterator first, TIterator last, TCompare compare)
Definition: algorithm.h:1859
ETL_NODISCARD ETL_CONSTEXPR14 bool is_partitioned(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition: algorithm.h:1630
ETL_NODISCARD ETL_CONSTEXPR14 TIterator max_element(TIterator begin, TIterator end, TCompare compare)
Definition: algorithm.h:1259
ETL_NODISCARD ETL_CONSTEXPR14 TIterator partition_point(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition: algorithm.h:1665
ETL_NODISCARD ETL_CONSTEXPR14 bool is_permutation(TIterator1 begin1, TIterator1 end1, TIterator2 begin2)
Definition: algorithm.h:1495
void stable_sort(TIterator first, TIterator last)
Definition: algorithm.h:1870
Definition: function.h:94
enable_if
Definition: type_traits_generator.h:1191
bitset_ext
Definition: absolute.h:38
pair< T1, T2 > make_pair(T1 a, T2 b)
A convenience wrapper for creating a pair from two objects.
Definition: utility.h:322
void swap(etl::array< T, SIZE > &lhs, etl::array< T, SIZE > &rhs)
Template deduction guides.
Definition: array.h:621
ETL_CONSTEXPR TContainer::iterator begin(TContainer &container)
Definition: iterator.h:931
ETL_CONSTEXPR TContainer::iterator end(TContainer &container)
Definition: iterator.h:961
Definition: compare.h:52
Definition: functional.h:238
Definition: iterator.h:842
Definition: functional.h:134