Embedded Template Library 1.0
Loading...
Searching...
No Matches
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#include "gcd.h"
47
48#include <stdint.h>
49#include <string.h>
50
51#include "private/minmax_push.h"
52
53#if ETL_USING_STL
54 #include <algorithm>
55 #include <utility>
56 #include <iterator>
57 #include <functional>
58 #include <numeric>
59#endif
60
61namespace etl
62{
63 // Declare prototypes of the ETL's sort functions
64 template <typename TIterator>
65#if ETL_USING_STD_NAMESPACE
66 ETL_CONSTEXPR20
67#else
68 ETL_CONSTEXPR14
69#endif
70 void shell_sort(TIterator first, TIterator last);
71
72 template <typename TIterator, typename TCompare>
73#if ETL_USING_STD_NAMESPACE
74 ETL_CONSTEXPR20
75#else
76 ETL_CONSTEXPR14
77#endif
78 void shell_sort(TIterator first, TIterator last, TCompare compare);
79
80 template <typename TIterator>
81 ETL_CONSTEXPR14 void insertion_sort(TIterator first, TIterator last);
82
83 template <typename TIterator, typename TCompare>
84 ETL_CONSTEXPR14 void insertion_sort(TIterator first, TIterator last, TCompare compare);
85}
86
87//*****************************************************************************
88// Algorithms defined by the ETL
89//*****************************************************************************
90namespace etl
91{
92 namespace private_algorithm
93 {
94 template <bool use_swap>
95 struct swap_impl;
96
97 // Generic swap
98 template <>
99 struct swap_impl<false>
100 {
101 template <typename TIterator1, typename TIterator2>
102 static void do_swap(TIterator1 a, TIterator2 b)
103 {
104 typename etl::iterator_traits<TIterator1>::value_type tmp = *a;
105 *a = *b;
106 *b = tmp;
107 }
108 };
109
110 // Specialised swap
111 template <>
112 struct swap_impl<true>
113 {
114 template <typename TIterator1, typename TIterator2>
115 static void do_swap(TIterator1 a, TIterator2 b)
116 {
117 using ETL_OR_STD::swap; // Allow ADL
118 swap(*a, *b);
119 }
120 };
121 }
122
123 //***************************************************************************
124 // iter_swap
125 //***************************************************************************
126 template <typename TIterator1, typename TIterator2>
127#if ETL_USING_STD_NAMESPACE
128 ETL_CONSTEXPR20
129#else
130 ETL_CONSTEXPR14
131#endif
132 void iter_swap(TIterator1 a, TIterator2 b)
133 {
134 typedef etl::iterator_traits<TIterator1> traits1;
135 typedef etl::iterator_traits<TIterator2> traits2;
136
137 typedef typename traits1::value_type v1;
138 typedef typename traits2::value_type v2;
139
140 typedef typename traits1::reference r1;
141 typedef typename traits2::reference r2;
142
143 const bool use_swap = etl::is_same<v1, v2>::value &&
146
148 }
149
150 //***************************************************************************
151 // swap_ranges
152 //***************************************************************************
153 template <typename TIterator1, typename TIterator2>
154#if ETL_USING_STD_NAMESPACE
155 ETL_CONSTEXPR20
156#else
157 ETL_CONSTEXPR14
158#endif
159 TIterator2 swap_ranges(TIterator1 first1,
160 TIterator1 last1,
161 TIterator2 first2)
162 {
163 while (first1 != last1)
164 {
165 iter_swap(first1, first2);
166 ++first1;
167 ++first2;
168 }
169
170 return first2;
171 }
172
173 //***************************************************************************
174 // generate
175 template <typename TIterator, typename TFunction>
176 ETL_CONSTEXPR14
177 void generate(TIterator db, TIterator de, TFunction funct)
178 {
179 while (db != de)
180 {
181 *db++ = funct();
182 }
183 }
184
185 //***************************************************************************
186 // copy
187#if ETL_USING_STL && ETL_USING_CPP20
188 // Use the STL constexpr implementation.
189 template <typename TIterator1, typename TIterator2>
190 constexpr TIterator2 copy(TIterator1 sb, TIterator1 se, TIterator2 db)
191 {
192 return std::copy(sb, se, db);
193 }
194#else
195 // Non-pointer or not trivially copyable or not using builtin memcpy.
196 template <typename TIterator1, typename TIterator2>
197 ETL_CONSTEXPR14 TIterator2 copy(TIterator1 sb, TIterator1 se, TIterator2 db)
198 {
199 while (sb != se)
200 {
201 *db = *sb;
202 ++db;
203 ++sb;
204 }
205
206 return db;
207 }
208#endif
209
210 //***************************************************************************
211 // reverse_copy
212#if ETL_USING_STL && ETL_USING_CPP20
213 template <typename TIterator1, typename TIterator2>
214 constexpr TIterator2 reverse_copy(TIterator1 sb, TIterator1 se, TIterator2 db)
215 {
216 return std::reverse_copy(sb, se, db);
217 }
218#else
219 template <typename TIterator1, typename TIterator2>
220 ETL_CONSTEXPR14
221 TIterator2 reverse_copy(TIterator1 sb, TIterator1 se, TIterator2 db)
222 {
223 while (sb != se)
224 {
225 *db = *--se;
226 ++db;
227 }
228
229 return db;
230 }
231#endif
232
233 //***************************************************************************
234 // copy_n
235#if ETL_USING_STL && ETL_USING_CPP20
236 // Use the STL implementation
237 template <typename TIterator1, typename TSize, typename TIterator2>
238 constexpr TIterator2 copy_n(TIterator1 sb, TSize count, TIterator2 db)
239 {
240 return std::copy_n(sb, count, db);
241 }
242#else
243 // Non-pointer or not trivially copyable or not using builtin memcpy.
244 template <typename TIterator1, typename TSize, typename TIterator2>
245 ETL_CONSTEXPR14 TIterator2 copy_n(TIterator1 sb, TSize count, TIterator2 db)
246 {
247 while (count != 0)
248 {
249 *db = *sb;
250 ++db;
251 ++sb;
252 --count;
253 }
254
255 return db;
256 }
257#endif
258
259 //***************************************************************************
260 // copy_backward
261#if ETL_USING_STL && ETL_USING_CPP20
262 template <typename TIterator1, typename TIterator2>
263 constexpr TIterator2 copy_backward(TIterator1 sb, TIterator1 se, TIterator2 de)
264 {
265 return std::copy_backward(sb, se, de);
266 }
267#else
268 template <typename TIterator1, typename TIterator2>
269 ETL_CONSTEXPR14 TIterator2 copy_backward(TIterator1 sb, TIterator1 se, TIterator2 de)
270 {
271 while (se != sb)
272 {
273 *(--de) = *(--se);
274 }
275
276 return de;
277 }
278#endif
279
280 //***************************************************************************
281 // move
282#if ETL_USING_STL && ETL_USING_CPP20
283 template <typename TIterator1, typename TIterator2>
284 constexpr TIterator2 move(TIterator1 sb, TIterator1 se, TIterator2 db)
285 {
286 return std::move(sb, se, db);
287 }
288#elif ETL_USING_CPP11
289 // For C++11
290 template <typename TIterator1, typename TIterator2>
291 ETL_CONSTEXPR14 TIterator2 move(TIterator1 sb, TIterator1 se, TIterator2 db)
292 {
293 while (sb != se)
294 {
295 *db = etl::move(*sb);
296 ++db;
297 ++sb;
298 }
299
300 return db;
301 }
302#else
303 // For C++03
304 template <typename TIterator1, typename TIterator2>
305 ETL_CONSTEXPR14 TIterator2 move(TIterator1 sb, TIterator1 se, TIterator2 db)
306 {
307 return copy(sb, se, db);
308 }
309#endif
310
311 //***************************************************************************
312 // move_backward
313#if ETL_USING_STL && ETL_USING_CPP20
314 template <typename TIterator1, typename TIterator2>
315 ETL_CONSTEXPR20 TIterator2 move_backward(TIterator1 sb, TIterator1 se, TIterator2 de)
316 {
317 return std::move_backward(sb, se, de);
318 }
319#elif ETL_USING_CPP11
320 // For C++11
321 template <typename TIterator1, typename TIterator2>
322 ETL_CONSTEXPR14 TIterator2 move_backward(TIterator1 sb, TIterator1 se, TIterator2 de)
323 {
324 while (sb != se)
325 {
326 *(--de) = etl::move(*(--se));
327 }
328
329 return de;
330 }
331#else
332 // For C++03
333 template <typename TIterator1, typename TIterator2>
334 ETL_CONSTEXPR14 TIterator2 move_backward(TIterator1 sb, TIterator1 se, TIterator2 de)
335 {
336 return etl::copy_backward(sb, se, de);
337 }
338#endif
339
340 //***************************************************************************
341 // reverse
342 //***************************************************************************
343 // Pointers
344 template <typename TIterator>
345 ETL_CONSTEXPR14
347 reverse(TIterator b, TIterator e)
348 {
349 if (b != e)
350 {
351 while (b < --e)
352 {
353 etl::iter_swap(b, e);
354 ++b;
355 }
356 }
357 }
358
359 // Non-pointers
360 template <typename TIterator>
361 ETL_CONSTEXPR14
363 reverse(TIterator b, TIterator e)
364 {
365 while ((b != e) && (b != --e))
366 {
367 etl::iter_swap(b++, e);
368 }
369 }
370
371 //***************************************************************************
372 // lower_bound
373 //***************************************************************************
374 template<typename TIterator, typename TValue, typename TCompare>
375 ETL_NODISCARD
376 ETL_CONSTEXPR14
377 TIterator lower_bound(TIterator first, TIterator last, const TValue& value, TCompare compare)
378 {
379 typedef typename etl::iterator_traits<TIterator>::difference_type difference_t;
380
381 difference_t count = etl::distance(first, last);
382
383 while (count > 0)
384 {
385 TIterator itr = first;
386 difference_t step = count / 2;
387
388 etl::advance(itr, step);
389
390 if (compare(*itr, value))
391 {
392 first = ++itr;
393 count -= step + 1;
394 }
395 else
396 {
397 count = step;
398 }
399 }
400
401 return first;
402 }
403
404 template<typename TIterator, typename TValue>
405 ETL_NODISCARD
406 ETL_CONSTEXPR14
407 TIterator lower_bound(TIterator first, TIterator last, const TValue& value)
408 {
410
411 return etl::lower_bound(first, last, value, compare());
412 }
413
414 //***************************************************************************
415 // upper_bound
416 //***************************************************************************
417 template<typename TIterator, typename TValue, typename TCompare>
418 ETL_NODISCARD
419 ETL_CONSTEXPR14
420 TIterator upper_bound(TIterator first, TIterator last, const TValue& value, TCompare compare)
421 {
422 typedef typename etl::iterator_traits<TIterator>::difference_type difference_t;
423
424 difference_t count = etl::distance(first, last);
425
426 while (count > 0)
427 {
428 TIterator itr = first;
429 difference_t step = count / 2;
430
431 etl::advance(itr, step);
432
433 if (!compare(value, *itr))
434 {
435 first = ++itr;
436 count -= step + 1;
437 }
438 else
439 {
440 count = step;
441 }
442 }
443
444 return first;
445 }
446
447 template<typename TIterator, typename TValue>
448 ETL_NODISCARD
449 ETL_CONSTEXPR14
450 TIterator upper_bound(TIterator first, TIterator last, const TValue& value)
451 {
453
454 return etl::upper_bound(first, last, value, compare());
455 }
456
457 //***************************************************************************
458 // equal_range
459 //***************************************************************************
460 template<typename TIterator, typename TValue, typename TCompare>
461 ETL_NODISCARD
462 ETL_CONSTEXPR14
463 ETL_OR_STD::pair<TIterator, TIterator> equal_range(TIterator first, TIterator last, const TValue& value, TCompare compare)
464 {
465 return ETL_OR_STD::make_pair(etl::lower_bound(first, last, value, compare),
466 etl::upper_bound(first, last, value, compare));
467 }
468
469 template<typename TIterator, typename TValue>
470 ETL_NODISCARD
471 ETL_OR_STD::pair<TIterator, TIterator> equal_range(TIterator first, TIterator last, const TValue& value)
472 {
474
475 return ETL_OR_STD::make_pair(etl::lower_bound(first, last, value, compare()),
476 etl::upper_bound(first, last, value, compare()));
477 }
478
479 //***************************************************************************
480 // binary_search
481 //***************************************************************************
482 template <typename TIterator, typename T, typename Compare>
483 ETL_NODISCARD
484 bool binary_search(TIterator first, TIterator last, const T& value, Compare compare)
485 {
486 first = etl::lower_bound(first, last, value, compare);
487
488 return (!(first == last) && !(compare(value, *first)));
489 }
490
491 template <typename TIterator, typename T>
492 ETL_NODISCARD
493 bool binary_search(TIterator first, TIterator last, const T& value)
494 {
496
497 return binary_search(first, last, value, compare());
498 }
499
500 //***************************************************************************
501 // find_if
502 //***************************************************************************
503 template <typename TIterator, typename TUnaryPredicate>
504 ETL_NODISCARD
505 ETL_CONSTEXPR14
506 TIterator find_if(TIterator first, TIterator last, TUnaryPredicate predicate)
507 {
508 while (first != last)
509 {
510 if (predicate(*first))
511 {
512 return first;
513 }
514
515 ++first;
516 }
517
518 return last;
519 }
520
521 //***************************************************************************
522 // find
523 //***************************************************************************
524 template <typename TIterator, typename T>
525 ETL_NODISCARD
526 ETL_CONSTEXPR14
527 TIterator find(TIterator first, TIterator last, const T& value)
528 {
529 while (first != last)
530 {
531 if (*first == value)
532 {
533 return first;
534 }
535
536 ++first;
537 }
538
539 return last;
540 }
541
542 //***************************************************************************
543 // fill
544#if ETL_USING_STL && ETL_USING_CPP20
545 template<typename TIterator, typename TValue>
546 constexpr void fill(TIterator first, TIterator last, const TValue& value)
547 {
548 std::fill(first, last, value);
549 }
550#else
551 template<typename TIterator, typename TValue>
552 ETL_CONSTEXPR14 void fill(TIterator first, TIterator last, const TValue& value)
553 {
554 while (first != last)
555 {
556 *first = value;
557 ++first;
558 }
559 }
560#endif
561
562 //***************************************************************************
563 // fill_n
564#if ETL_USING_STL && ETL_USING_CPP20
565 template<typename TIterator, typename TSize, typename TValue>
566 constexpr TIterator fill_n(TIterator first, TSize count, const TValue& value)
567 {
568 return std::fill_n(first, count, value);
569 }
570#else
571 template<typename TIterator, typename TSize, typename TValue>
572 ETL_CONSTEXPR14 TIterator fill_n(TIterator first, TSize count, const TValue& value)
573 {
574 while (count != 0)
575 {
576 *first++ = value;
577 --count;
578 }
579
580 return first;
581 }
582#endif
583
584 //***************************************************************************
585 // count
586 //***************************************************************************
587 template <typename TIterator, typename T>
588 ETL_NODISCARD
589 ETL_CONSTEXPR14
590 typename etl::iterator_traits<TIterator>::difference_type count(TIterator first, TIterator last, const T& value)
591 {
592 typename iterator_traits<TIterator>::difference_type n = 0;
593
594 while (first != last)
595 {
596 if (*first == value)
597 {
598 ++n;
599 }
600
601 ++first;
602 }
603
604 return n;
605 }
606
607 //***************************************************************************
608 // count_if
609 //***************************************************************************
610 template <typename TIterator, typename TUnaryPredicate>
611 ETL_NODISCARD
612 ETL_CONSTEXPR14
613 typename etl::iterator_traits<TIterator>::difference_type
614 count_if(TIterator first, TIterator last, TUnaryPredicate predicate)
615 {
616 typename iterator_traits<TIterator>::difference_type n = 0;
617
618 while (first != last)
619 {
620 if (predicate(*first))
621 {
622 ++n;
623 }
624
625 ++first;
626 }
627
628 return n;
629 }
630
631 //***************************************************************************
632 // equal
633#if ETL_USING_STL && ETL_USING_CPP20
634 // Three parameter
635 template <typename TIterator1, typename TIterator2>
636 [[nodiscard]]
637 constexpr
638 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2)
639 {
640 return std::equal(first1, last1, first2);
641 }
642
643 // Three parameter + predicate
644 template <typename TIterator1, typename TIterator2, typename TPredicate>
645 [[nodiscard]]
646 constexpr
647 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2, TPredicate predicate)
648 {
649 return std::equal(first1, last1, first2, predicate);
650 }
651
652 // Four parameter
653 template <typename TIterator1, typename TIterator2>
654 [[nodiscard]]
655 constexpr
656 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2, TIterator2 last2)
657 {
658 return std::equal(first1, last1, first2, last2);
659 }
660
661 // Four parameter + Predicate
662 template <typename TIterator1, typename TIterator2, typename TPredicate>
663 [[nodiscard]]
664 constexpr
665 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2, TIterator2 last2, TPredicate predicate)
666 {
667 return std::equal(first1, last1, first2, last2, predicate);
668 }
669
670#else
671
672 template <typename TIterator1, typename TIterator2>
673 ETL_NODISCARD
674 ETL_CONSTEXPR14
675 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2)
676 {
677 while (first1 != last1)
678 {
679 if (*first1 != *first2)
680 {
681 return false;
682 }
683
684 ++first1;
685 ++first2;
686 }
687
688 return true;
689 }
690
691 // Predicate
692 template <typename TIterator1, typename TIterator2, typename TPredicate>
693 ETL_NODISCARD
694 ETL_CONSTEXPR14
695 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2, TPredicate predicate)
696 {
697 while (first1 != last1)
698 {
699 if (!predicate(*first1, *first2))
700 {
701 return false;
702 }
703
704 ++first1;
705 ++first2;
706 }
707
708 return true;
709 }
710
711 // Four parameter
712 template <typename TIterator1, typename TIterator2>
713 ETL_NODISCARD
714 ETL_CONSTEXPR14
715 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2, TIterator2 last2)
716 {
717 while ((first1 != last1) && (first2 != last2))
718 {
719 if (*first1 != *first2)
720 {
721 return false;
722 }
723
724 ++first1;
725 ++first2;
726 }
727
728 return (first1 == last1) && (first2 == last2);
729 }
730
731 // Four parameter, Predicate
732 template <typename TIterator1, typename TIterator2, typename TPredicate>
733 ETL_NODISCARD
734 ETL_CONSTEXPR14
735 bool equal(TIterator1 first1, TIterator1 last1, TIterator2 first2, TIterator2 last2, TPredicate predicate)
736 {
737 while ((first1 != last1) && (first2 != last2))
738 {
739 if (!predicate(*first1 , *first2))
740 {
741 return false;
742 }
743
744 ++first1;
745 ++first2;
746 }
747
748 return (first1 == last1) && (first2 == last2);
749 }
750#endif
751
752 //***************************************************************************
753 // lexicographical_compare
754 //***************************************************************************
755 template <typename TIterator1, typename TIterator2, typename TCompare>
756 ETL_NODISCARD
757 ETL_CONSTEXPR14
758 bool lexicographical_compare(TIterator1 first1, TIterator1 last1,
759 TIterator2 first2, TIterator2 last2,
760 TCompare compare)
761 {
762 while ((first1 != last1) && (first2 != last2))
763 {
764 if (compare(*first1, *first2))
765 {
766 return true;
767 }
768
769 if (compare(*first2, *first1))
770 {
771 return false;
772 }
773
774 ++first1;
775 ++first2;
776 }
777
778 return (first1 == last1) && (first2 != last2);
779 }
780
781 // lexicographical_compare
782 template <typename TIterator1, typename TIterator2>
783 ETL_NODISCARD
784 ETL_CONSTEXPR14
785 bool lexicographical_compare(TIterator1 first1, TIterator1 last1,
786 TIterator2 first2, TIterator2 last2)
787 {
789
790 return etl::lexicographical_compare(first1, last1, first2, last2, compare());
791 }
792
793 //***************************************************************************
794 // min
795 //***************************************************************************
796 template <typename T, typename TCompare>
797 ETL_NODISCARD
798 ETL_CONSTEXPR
799 const T& min(const T& a, const T& b, TCompare compare)
800 {
801 return (compare(a, b)) ? a : b;
802 }
803
804 template <typename T>
805 ETL_NODISCARD
806 ETL_CONSTEXPR
807 const T& min(const T& a, const T& b)
808 {
809 typedef etl::less<T> compare;
810
811 return etl::min(a, b, compare());
812 }
813
814 //***************************************************************************
815 // max
816 //***************************************************************************
817 template <typename T, typename TCompare>
818 ETL_NODISCARD
819 ETL_CONSTEXPR
820 const T& max(const T& a, const T& b, TCompare compare)
821 {
822 return (compare(a, b)) ? b : a;
823 }
824
825 template <typename T>
826 ETL_NODISCARD
827 ETL_CONSTEXPR
828 const T& max(const T& a, const T& b)
829 {
830 typedef etl::less<T> compare;
831
832 return etl::max(a, b, compare());
833 }
834
835 //***************************************************************************
836 // for_each
837 //***************************************************************************
838 template <typename TIterator, typename TUnaryOperation>
839 ETL_CONSTEXPR14
840 TUnaryOperation for_each(TIterator first, TIterator last, TUnaryOperation unary_operation)
841 {
842 while (first != last)
843 {
844 unary_operation(*first);
845 ++first;
846 }
847
848 return unary_operation;
849 }
850
851 //***************************************************************************
852 // transform
853 //***************************************************************************
854 template <typename TIteratorIn, typename TIteratorOut, typename TUnaryOperation>
855 ETL_CONSTEXPR14
856 TIteratorOut transform(TIteratorIn first1, TIteratorIn last1, TIteratorOut d_first, TUnaryOperation unary_operation)
857 {
858 while (first1 != last1)
859 {
860 *d_first = unary_operation(*first1);
861
862 ++d_first;
863 ++first1;
864 }
865
866 return d_first;
867 }
868
869 template <typename TIteratorIn1, typename TIteratorIn2, typename TIteratorOut, typename TBinaryOperation>
870 ETL_CONSTEXPR14
871 TIteratorOut transform(TIteratorIn1 first1, TIteratorIn1 last1, TIteratorIn2 first2, TIteratorOut d_first, TBinaryOperation binary_operation)
872 {
873 while (first1 != last1)
874 {
875 *d_first = binary_operation(*first1, *first2);
876
877 ++d_first;
878 ++first1;
879 ++first2;
880 }
881
882 return d_first;
883 }
884
885 //***************************************************************************
886 // replace
887 //***************************************************************************
888 template <typename TIterator, typename T>
889 ETL_CONSTEXPR14 void replace(TIterator first, TIterator last, const T& old_value, const T& new_value)
890 {
891 while (first != last)
892 {
893 if (*first == old_value)
894 {
895 *first = new_value;
896 }
897
898 ++first;
899 }
900 }
901
902 //***************************************************************************
903 // replace_if
904 //***************************************************************************
905 template <typename TIterator, typename TPredicate, typename T>
906 ETL_CONSTEXPR14 void replace_if(TIterator first, TIterator last, TPredicate predicate, const T& new_value)
907 {
908 while (first != last)
909 {
910 if (predicate(*first))
911 {
912 *first = new_value;
913 }
914
915 ++first;
916 }
917 }
918
919 //***************************************************************************
920 // Heap
921 //***************************************************************************
922 namespace private_heap
923 {
924 // Push Heap Helper
925 template <typename TIterator, typename TDistance, typename TValue, typename TCompare>
926 void push_heap(TIterator first, TDistance value_index, TDistance top_index, TValue value, TCompare compare)
927 {
928 TDistance parent = (value_index - 1) / 2;
929
930 while ((value_index > top_index) && compare(first[parent], value))
931 {
932 first[value_index] = etl::move(first[parent]);
933 value_index = parent;
934 parent = (value_index - 1) / 2;
935 }
936
937 first[value_index] = etl::move(value);
938 }
939
940 // Adjust Heap Helper
941 template <typename TIterator, typename TDistance, typename TValue, typename TCompare>
942 void adjust_heap(TIterator first, TDistance value_index, TDistance length, TValue value, TCompare compare)
943 {
944 TDistance top_index = value_index;
945 TDistance child2nd = (2 * value_index) + 2;
946
947 while (child2nd < length)
948 {
949 if (compare(first[child2nd], first[child2nd - 1]))
950 {
951 --child2nd;
952 }
953
954 first[value_index] = etl::move(first[child2nd]);
955 value_index = child2nd;
956 child2nd = 2 * (child2nd + 1);
957 }
958
959 if (child2nd == length)
960 {
961 first[value_index] = etl::move(first[child2nd - 1]);
962 value_index = child2nd - 1;
963 }
964
965 push_heap(first, value_index, top_index, etl::move(value), compare);
966 }
967
968 // Is Heap Helper
969 template <typename TIterator, typename TDistance, typename TCompare>
970 bool is_heap(const TIterator first, const TDistance n, TCompare compare)
971 {
972 TDistance parent = 0;
973
974 for (TDistance child = 1; child < n; ++child)
975 {
976 if (compare(first[parent], first[child]))
977 {
978 return false;
979 }
980
981 if ((child & 1) == 0)
982 {
983 ++parent;
984 }
985 }
986
987 return true;
988 }
989 }
990
991 // Pop Heap
992 template <typename TIterator, typename TCompare>
993 void pop_heap(TIterator first, TIterator last, TCompare compare)
994 {
995 typedef typename etl::iterator_traits<TIterator>::value_type value_t;
996 typedef typename etl::iterator_traits<TIterator>::difference_type distance_t;
997
998 value_t value = etl::move(last[-1]);
999 last[-1] = etl::move(first[0]);
1000
1001 private_heap::adjust_heap(first, distance_t(0), distance_t(last - first - 1), etl::move(value), compare);
1002 }
1003
1004 // Pop Heap
1005 template <typename TIterator>
1006 void pop_heap(TIterator first, TIterator last)
1007 {
1009
1010 etl::pop_heap(first, last, compare());
1011 }
1012
1013 // Push Heap
1014 template <typename TIterator, typename TCompare>
1015 void push_heap(TIterator first, TIterator last, TCompare compare)
1016 {
1017 typedef typename etl::iterator_traits<TIterator>::difference_type difference_t;
1018 typedef typename etl::iterator_traits<TIterator>::value_type value_t;
1019
1020 private_heap::push_heap(first, difference_t(last - first - 1), difference_t(0), value_t(etl::move(*(last - 1))), compare);
1021 }
1022
1023 // Push Heap
1024 template <typename TIterator>
1025 void push_heap(TIterator first, TIterator last)
1026 {
1028
1029 etl::push_heap(first, last, compare());
1030 }
1031
1032 // Make Heap
1033 template <typename TIterator, typename TCompare>
1034 void make_heap(TIterator first, TIterator last, TCompare compare)
1035 {
1036 typedef typename etl::iterator_traits<TIterator>::difference_type difference_t;
1037
1038 if ((last - first) < 2)
1039 {
1040 return;
1041 }
1042
1043 difference_t length = last - first;
1044 difference_t parent = (length - 2) / 2;
1045
1046 while (true)
1047 {
1048 private_heap::adjust_heap(first, parent, length, etl::move(*(first + parent)), compare);
1049
1050 if (parent == 0)
1051 {
1052 return;
1053 }
1054
1055 --parent;
1056 }
1057 }
1058
1059 // Make Heap
1060 template <typename TIterator>
1061 void make_heap(TIterator first, TIterator last)
1062 {
1064
1065 etl::make_heap(first, last, compare());
1066 }
1067
1068 // Is Heap
1069 template <typename TIterator>
1070 ETL_NODISCARD
1071 bool is_heap(TIterator first, TIterator last)
1072 {
1074
1075 return private_heap::is_heap(first, last - first, compare());
1076 }
1077
1078 // Is Heap
1079 template <typename TIterator, typename TCompare>
1080 ETL_NODISCARD
1081 bool is_heap(TIterator first, TIterator last, TCompare compare)
1082 {
1083 return private_heap::is_heap(first, last - first, compare);
1084 }
1085
1086 // Sort Heap
1087 template <typename TIterator>
1088 void sort_heap(TIterator first, TIterator last)
1089 {
1090 while (first != last)
1091 {
1092 etl::pop_heap(first, last);
1093 --last;
1094 }
1095 }
1096
1097 // Sort Heap
1098 template <typename TIterator, typename TCompare>
1099 void sort_heap(TIterator first, TIterator last, TCompare compare)
1100 {
1101 while (first != last)
1102 {
1103 etl::pop_heap(first, last, compare);
1104 --last;
1105 }
1106 }
1107
1108 //***************************************************************************
1109 // Search
1110 //***************************************************************************
1111 template<typename TIterator1, typename TIterator2, typename TCompare>
1112 ETL_NODISCARD
1113 ETL_CONSTEXPR14
1114 TIterator1 search(TIterator1 first, TIterator1 last, TIterator2 search_first, TIterator2 search_last, TCompare compare)
1115 {
1116 while (true)
1117 {
1118 TIterator1 itr = first;
1119 TIterator2 search_itr = search_first;
1120
1121 while (true)
1122 {
1123 if (search_itr == search_last)
1124 {
1125 return first;
1126 }
1127
1128 if (itr == last)
1129 {
1130 return last;
1131 }
1132
1133 if (!compare(*itr, *search_itr))
1134 {
1135 break;
1136 }
1137
1138 ++itr;
1139 ++search_itr;
1140 }
1141
1142 ++first;
1143 }
1144 }
1145
1146 // Search
1147 template<typename TIterator1, typename TIterator2>
1148 ETL_NODISCARD
1149 ETL_CONSTEXPR14
1150 TIterator1 search(TIterator1 first, TIterator1 last, TIterator2 search_first, TIterator2 search_last)
1151 {
1153
1154 return etl::search(first, last, search_first, search_last, compare());
1155 }
1156
1157 //***************************************************************************
1158 // Rotate
1159 //***************************************************************************
1160 namespace private_algorithm
1161 {
1162#if ETL_USING_CPP11
1163 //*********************************
1164 // For random access iterators
1165 template <typename TIterator>
1166 ETL_CONSTEXPR14
1168 rotate_general(TIterator first, TIterator middle, TIterator last)
1169 {
1170 if (first == middle || middle == last)
1171 {
1172 return first;
1173 }
1174
1175 typedef typename etl::iterator_traits<TIterator>::value_type value_type;
1176
1177 int n = last - first;
1178 int m = middle - first;
1179 int gcd_nm = (n == 0 || m == 0) ? n + m : etl::gcd(n, m);
1180
1181 TIterator result = first + (last - middle);
1182
1183 for (int i = 0; i < gcd_nm; i++)
1184 {
1185 value_type temp = etl::move(*(first + i));
1186 int j = i;
1187
1188 while (true)
1189 {
1190 int k = j + m;
1191
1192 if (k >= n)
1193 {
1194 k = k - n;
1195 }
1196
1197 if (k == i)
1198 {
1199 break;
1200 }
1201
1202 *(first + j) = etl::move(*(first + k));
1203 j = k;
1204 }
1205
1206 *(first + j) = etl::move(temp);
1207 }
1208
1209 return result;
1210 }
1211#else
1212 //*********************************
1213 // For random access iterators
1214 template <typename TIterator>
1215 ETL_CONSTEXPR14
1217 rotate_general(TIterator first, TIterator middle, TIterator last)
1218 {
1219 if (first == middle || middle == last)
1220 {
1221 return first;
1222 }
1223
1224 typedef typename etl::iterator_traits<TIterator>::value_type value_type;
1225
1226 int n = last - first;
1227 int m = middle - first;
1228 int gcd_nm = (n == 0 || m == 0) ? n + m : etl::gcd(n, m);
1229
1230 TIterator result = first + (last - middle);
1231
1232 for (int i = 0; i < gcd_nm; i++)
1233 {
1234 value_type temp = *(first + i);
1235 int j = i;
1236
1237 while (true)
1238 {
1239 int k = j + m;
1240
1241 if (k >= n)
1242 {
1243 k = k - n;
1244 }
1245
1246 if (k == i)
1247 {
1248 break;
1249 }
1250
1251 *(first + j) = *(first + k);
1252 j = k;
1253 }
1254
1255 *(first + j) = temp;
1256 }
1257
1258 return result;
1259 }
1260#endif
1261
1262 //*********************************
1263 // For bidirectional iterators
1264 template <typename TIterator>
1265 ETL_CONSTEXPR14
1267 rotate_general(TIterator first, TIterator middle, TIterator last)
1268 {
1269 if (first == middle || middle == last)
1270 {
1271 return first;
1272 }
1273
1274 TIterator result = first;
1275 etl::advance(result, etl::distance(middle, last));
1276
1277 reverse(first, middle);
1278 reverse(middle, last);
1279 reverse(first, last);
1280
1281 return result;
1282 }
1283
1284 //*********************************
1285 // For forward iterators
1286 template <typename TIterator>
1287 ETL_CONSTEXPR14
1289 rotate_general(TIterator first, TIterator middle, TIterator last)
1290 {
1291 if (first == middle || middle == last)
1292 {
1293 return first;
1294 }
1295
1296 TIterator next = middle;
1297 TIterator result = first;
1298 etl::advance(result, etl::distance(middle, last));
1299
1300 while (first != next)
1301 {
1302 using ETL_OR_STD::swap;
1303 swap(*first++, *next++);
1304
1305 if (next == last)
1306 {
1307 next = middle;
1308 }
1309 else if (first == middle)
1310 {
1311 middle = next;
1312 }
1313 }
1314
1315 return result;
1316 }
1317
1318 //*********************************
1319 // Simplified algorithm for rotate left by one
1320 template <typename TIterator>
1321 ETL_CONSTEXPR14
1322 TIterator rotate_left_by_one(TIterator first, TIterator last)
1323 {
1324 typedef typename etl::iterator_traits<TIterator>::value_type value_type;
1325
1326 // Save the first item.
1327 value_type temp(etl::move(*first));
1328
1329 // Move the rest.
1330 TIterator result = etl::move(etl::next(first), last, first);
1331
1332 // Restore the first item in its rotated position.
1333 *result = etl::move(temp);
1334
1335 // The new position of the first item.
1336 return result;
1337 }
1338
1339 //*********************************
1340 // Simplified for algorithm rotate right by one
1341 template <typename TIterator>
1342 ETL_CONSTEXPR14
1343 TIterator rotate_right_by_one(TIterator first, TIterator last)
1344 {
1345 typedef typename etl::iterator_traits<TIterator>::value_type value_type;
1346
1347 // Save the last item.
1348 TIterator previous = etl::prev(last);
1349 value_type temp(etl::move(*previous));
1350
1351 // Move the rest.
1352 TIterator result = etl::move_backward(first, previous, last);
1353
1354 // Restore the last item in its rotated position.
1355 *first = etl::move(temp);
1356
1357 // The new position of the first item.
1358 return result;
1359 }
1360 }
1361
1362 //*********************************
1363 template<typename TIterator>
1364 ETL_CONSTEXPR14
1365 TIterator rotate(TIterator first, TIterator middle, TIterator last)
1366 {
1367 if (etl::next(first) == middle)
1368 {
1369 return private_algorithm::rotate_left_by_one(first, last);
1370 }
1371
1372 if (etl::next(middle) == last)
1373 {
1374#if ETL_USING_CPP20
1376 {
1377 return private_algorithm::rotate_general(first, middle, last);
1378 }
1379 else
1380 {
1381 return private_algorithm::rotate_right_by_one(first, last);
1382 }
1383#else
1384 return private_algorithm::rotate_general(first, middle, last);
1385#endif
1386 }
1387
1388 return private_algorithm::rotate_general(first, middle, last);
1389 }
1390
1391 //***************************************************************************
1392 // find_end
1393 //***************************************************************************
1394 // Predicate
1395 template <typename TIterator1, typename TIterator2, typename TPredicate>
1396 ETL_NODISCARD
1397 ETL_CONSTEXPR14
1398 TIterator1 find_end(TIterator1 b, TIterator1 e,
1399 TIterator2 sb, TIterator2 se,
1400 TPredicate predicate)
1401 {
1402 if (sb == se)
1403 {
1404 return e;
1405 }
1406
1407 TIterator1 result = e;
1408
1409 while (true)
1410 {
1411 TIterator1 new_result = etl::search(b, e, sb, se, predicate);
1412
1413 if (new_result == e)
1414 {
1415 break;
1416 }
1417 else
1418 {
1419 result = new_result;
1420 b = result;
1421 ++b;
1422 }
1423 }
1424 return result;
1425 }
1426
1427 // Default
1428 template <typename TIterator1, typename TIterator2>
1429 ETL_NODISCARD
1430 ETL_CONSTEXPR14
1431 TIterator1 find_end(TIterator1 b, TIterator1 e,
1432 TIterator2 sb, TIterator2 se)
1433 {
1435
1436 return find_end(b, e, sb, se, predicate());
1437 }
1438
1439 //***************************************************************************
1443 //***************************************************************************
1444 template <typename TIterator, typename TCompare>
1445 ETL_NODISCARD
1446 ETL_CONSTEXPR14
1448 TIterator end,
1450 {
1452 ++begin;
1453
1454 while (begin != end)
1455 {
1456 if (compare(*begin, *minimum))
1457 {
1458 minimum = begin;
1459 }
1460
1461 ++begin;
1462 }
1463
1464 return minimum;
1465 }
1466
1467 //***************************************************************************
1471 //***************************************************************************
1472 template <typename TIterator>
1473 ETL_NODISCARD
1474 ETL_CONSTEXPR14
1476 TIterator end)
1477 {
1478 typedef typename etl::iterator_traits<TIterator>::value_type value_t;
1479
1481 }
1482
1483 //***************************************************************************
1487 //***************************************************************************
1488 template <typename TIterator, typename TCompare>
1489 ETL_NODISCARD
1490 ETL_CONSTEXPR14
1492 TIterator end,
1494 {
1495 TIterator maximum = begin;
1496 ++begin;
1497
1498 while (begin != end)
1499 {
1500 if (!compare(*begin, *maximum))
1501 {
1502 maximum = begin;
1503 }
1504
1505 ++begin;
1506 }
1507
1508 return maximum;
1509 }
1510
1511 //***************************************************************************
1515 //***************************************************************************
1516 template <typename TIterator>
1517 ETL_NODISCARD
1518 ETL_CONSTEXPR14
1520 TIterator end)
1521 {
1522 typedef typename etl::iterator_traits<TIterator>::value_type value_t;
1523
1525 }
1526
1527 //***************************************************************************
1531 //***************************************************************************
1532 template <typename TIterator, typename TCompare>
1533 ETL_NODISCARD
1534 ETL_CONSTEXPR14
1535 ETL_OR_STD::pair<TIterator, TIterator> minmax_element(TIterator begin,
1536 TIterator end,
1538 {
1540 TIterator maximum = begin;
1541 ++begin;
1542
1543 while (begin != end)
1544 {
1545 if (compare(*begin, *minimum))
1546 {
1547 minimum = begin;
1548 }
1549
1550 if (compare(*maximum, *begin))
1551 {
1552 maximum = begin;
1553 }
1554
1555 ++begin;
1556 }
1557
1558 return ETL_OR_STD::pair<TIterator, TIterator>(minimum, maximum);
1559 }
1560
1561 //***************************************************************************
1565 //***************************************************************************
1566 template <typename TIterator>
1567 ETL_NODISCARD
1568 ETL_CONSTEXPR14
1569 ETL_OR_STD::pair<TIterator, TIterator> minmax_element(TIterator begin,
1570 TIterator end)
1571 {
1572 typedef typename etl::iterator_traits<TIterator>::value_type value_t;
1573
1575 }
1576
1577 //***************************************************************************
1581 //***************************************************************************
1582 template <typename T>
1583 ETL_NODISCARD
1584 ETL_CONSTEXPR14
1585 ETL_OR_STD::pair<const T&, const T&> minmax(const T& a,
1586 const T& b)
1587 {
1588 return (b < a) ? ETL_OR_STD::pair<const T&, const T&>(b, a) : ETL_OR_STD::pair<const T&, const T&>(a, b);
1589 }
1590
1591 //***************************************************************************
1595 //***************************************************************************
1596 template <typename T, typename TCompare>
1597 ETL_NODISCARD
1598 ETL_CONSTEXPR14
1599 ETL_OR_STD::pair<const T&, const T&> minmax(const T& a,
1600 const T& b,
1602 {
1603 return compare(b, a) ? ETL_OR_STD::pair<const T&, const T&>(b, a) : ETL_OR_STD::pair<const T&, const T&>(a, b);
1604 }
1605
1606 //***************************************************************************
1610 //***************************************************************************
1611 template <typename TIterator>
1612 ETL_NODISCARD
1613 ETL_CONSTEXPR14
1615 TIterator end)
1616 {
1617 if (begin != end)
1618 {
1619 TIterator next = begin;
1620
1621 while (++next != end)
1622 {
1623 if (*next < *begin)
1624 {
1625 return next;
1626 }
1627
1628 ++begin;
1629 }
1630 }
1631
1632 return end;
1633 }
1634
1635 //***************************************************************************
1639 //***************************************************************************
1640 template <typename TIterator, typename TCompare>
1641 ETL_NODISCARD
1642 ETL_CONSTEXPR14
1644 TIterator end,
1646 {
1647 if (begin != end)
1648 {
1649 TIterator next = begin;
1650
1651 while (++next != end)
1652 {
1653 if (compare(*next, *begin))
1654 {
1655 return next;
1656 }
1657
1658 ++begin;
1659 }
1660 }
1661
1662 return end;
1663 }
1664
1665 //***************************************************************************
1669 //***************************************************************************
1670 template<typename TIterator>
1671 ETL_NODISCARD
1672 ETL_CONSTEXPR14
1674 TIterator end)
1675 {
1676 return etl::is_sorted_until(begin, end) == end;
1677 }
1678
1679 //***************************************************************************
1683 //***************************************************************************
1684 template<typename TIterator, typename TCompare>
1685 ETL_NODISCARD
1686 ETL_CONSTEXPR14
1688 TIterator end,
1690 {
1692 }
1693
1694 //***************************************************************************
1698 //***************************************************************************
1699 template <typename TIterator, typename TUnaryPredicate>
1700 ETL_NODISCARD
1701 ETL_CONSTEXPR14
1703 TIterator end,
1705 {
1706 while (begin != end)
1707 {
1708 if (!predicate(*begin))
1709 {
1710 return begin;
1711 }
1712
1713 ++begin;
1714 }
1715
1716 return end;
1717 }
1718
1719 //***************************************************************************
1723 //***************************************************************************
1724 template <typename TIterator1, typename TIterator2>
1725 ETL_NODISCARD
1726 ETL_CONSTEXPR14
1730 {
1731 if (begin1 != end1)
1732 {
1734
1735 etl::advance(end2, etl::distance(begin1, end1));
1736
1737 for (TIterator1 i = begin1; i != end1; ++i)
1738 {
1739 if (i == etl::find(begin1, i, *i))
1740 {
1741 size_t n = etl::count(begin2, end2, *i);
1742
1743 if (n == 0 || size_t(etl::count(i, end1, *i)) != n)
1744 {
1745 return false;
1746 }
1747 }
1748 }
1749 }
1750
1751 return true;
1752 }
1753
1754 //***************************************************************************
1758 //***************************************************************************
1759 template <typename TIterator1, typename TIterator2, typename TBinaryPredicate>
1760 ETL_NODISCARD
1761 ETL_CONSTEXPR14
1766 {
1767 if (begin1 != end1)
1768 {
1770
1771 etl::advance(end2, etl::distance(begin1, end1));
1772
1773 for (TIterator1 i = begin1; i != end1; ++i)
1774 {
1775 if (i == etl::find_if(begin1, i, etl::bind1st(predicate, *i)))
1776 {
1777 size_t n = etl::count(begin2, end2, *i);
1778
1779 if (n == 0 || size_t(etl::count(i, end1, *i)) != n)
1780 {
1781 return false;
1782 }
1783 }
1784 }
1785 }
1786
1787 return true;
1788 }
1789
1790 //***************************************************************************
1794 //***************************************************************************
1795 template <typename TIterator1, typename TIterator2>
1796 ETL_NODISCARD
1797 ETL_CONSTEXPR14
1802 {
1803 if (begin1 != end1)
1804 {
1805 for (TIterator1 i = begin1; i != end1; ++i)
1806 {
1807 if (i == etl::find(begin1, i, *i))
1808 {
1809 size_t n = etl::count(begin2, end2, *i);
1810
1811 if (n == 0 || size_t(etl::count(i, end1, *i)) != n)
1812 {
1813 return false;
1814 }
1815 }
1816 }
1817 }
1818
1819 return true;
1820 }
1821
1822 //***************************************************************************
1826 //***************************************************************************
1827 template <typename TIterator1, typename TIterator2, typename TBinaryPredicate>
1828 ETL_NODISCARD
1834 {
1835 if (begin1 != end1)
1836 {
1837 for (TIterator1 i = begin1; i != end1; ++i)
1838 {
1839 if (i == etl::find_if(begin1, i, etl::bind1st(predicate, *i)))
1840 {
1841 size_t n = etl::count(begin2, end2, *i);
1842
1843 if (n == 0 || size_t(etl::count(i, end1, *i)) != n)
1844 {
1845 return false;
1846 }
1847 }
1848 }
1849 }
1850
1851 return true;
1852 }
1853
1854 //***************************************************************************
1858 //***************************************************************************
1859 template <typename TIterator, typename TUnaryPredicate>
1860 ETL_NODISCARD
1861 ETL_CONSTEXPR14
1863 TIterator end,
1865 {
1866 while (begin != end)
1867 {
1868 if (!predicate(*begin))
1869 {
1870 break;
1871 }
1872
1873 ++begin;
1874 }
1875
1876 while (begin != end)
1877 {
1878 if (predicate(*begin))
1879 {
1880 return false;
1881 }
1882
1883 ++begin;
1884 }
1885
1886 return true;
1887 }
1888
1889 //***************************************************************************
1893 //***************************************************************************
1894 template <typename TIterator, typename TUnaryPredicate>
1895 ETL_NODISCARD
1896 ETL_CONSTEXPR14
1898 TIterator end,
1900 {
1901 while (begin != end)
1902 {
1903 if (!predicate(*begin))
1904 {
1905 return begin;
1906 }
1907
1908 ++begin;
1909 }
1910
1911 return begin;
1912 }
1913
1914 //***************************************************************************
1919 //***************************************************************************
1920 template <typename TSource, typename TDestinationTrue, typename TDestinationFalse, typename TUnaryPredicate>
1921 ETL_CONSTEXPR14
1922 ETL_OR_STD::pair<TDestinationTrue, TDestinationFalse> partition_copy(TSource begin,
1923 TSource end,
1927 {
1928 while (begin != end)
1929 {
1930 if (predicate(*begin))
1931 {
1934 }
1935 else
1936 {
1939 }
1940
1941 ++begin;
1942 }
1943
1944 return ETL_OR_STD::pair<TDestinationTrue, TDestinationFalse>(destination_true, destination_false);
1945 }
1946
1947 //***************************************************************************
1951 //***************************************************************************
1952 template <typename TIterator, typename TOutputIterator, typename TUnaryPredicate>
1953 ETL_CONSTEXPR14
1955 TIterator end,
1956 TOutputIterator out,
1958 {
1959 while (begin != end)
1960 {
1961 if (predicate(*begin))
1962 {
1963 *out = *begin;
1964 ++out;
1965 }
1966
1967 ++begin;
1968 }
1969
1970 return out;
1971 }
1972
1973 //***************************************************************************
1977 //***************************************************************************
1978 template <typename TIterator, typename TUnaryPredicate>
1979 ETL_NODISCARD
1980 ETL_CONSTEXPR14
1987
1988 //***************************************************************************
1992 //***************************************************************************
1993 template <typename TIterator, typename TUnaryPredicate>
1994 ETL_NODISCARD
1995 ETL_CONSTEXPR14
1997 TIterator end,
1999 {
2000 return etl::find_if(begin, end, predicate) != end;
2001 }
2002
2003 //***************************************************************************
2007 //***************************************************************************
2008 template <typename TIterator, typename TUnaryPredicate>
2009 ETL_NODISCARD
2010 ETL_CONSTEXPR14
2012 TIterator end,
2014 {
2015 return etl::find_if(begin, end, predicate) == end;
2016 }
2017
2018#if ETL_NOT_USING_STL
2019 //***************************************************************************
2023 //***************************************************************************
2024 template <typename TIterator, typename TCompare>
2025 void sort(TIterator first, TIterator last, TCompare compare)
2026 {
2027 etl::shell_sort(first, last, compare);
2028 }
2029
2030 //***************************************************************************
2033 //***************************************************************************
2034 template <typename TIterator>
2035 void sort(TIterator first, TIterator last)
2036 {
2037 etl::shell_sort(first, last, etl::less<typename etl::iterator_traits<TIterator>::value_type>());
2038 }
2039
2040 //***************************************************************************
2045 //***************************************************************************
2046 template <typename TIterator, typename TCompare>
2047 void stable_sort(TIterator first, TIterator last, TCompare compare)
2048 {
2049 etl::insertion_sort(first, last, compare);
2050 }
2051
2052 //***************************************************************************
2056 //***************************************************************************
2057 template <typename TIterator>
2058 void stable_sort(TIterator first, TIterator last)
2059 {
2060 etl::insertion_sort(first, last, etl::less<typename etl::iterator_traits<TIterator>::value_type>());
2061 }
2062#else
2063 //***************************************************************************
2067 //***************************************************************************
2068 template <typename TIterator, typename TCompare>
2070 {
2071 std::sort(first, last, compare);
2072 }
2073
2074 //***************************************************************************
2077 //***************************************************************************
2078 template <typename TIterator>
2079 void sort(TIterator first, TIterator last)
2080 {
2081 std::sort(first, last);
2082 }
2083
2084 //***************************************************************************
2089 //***************************************************************************
2090 template <typename TIterator, typename TCompare>
2092 {
2093 std::stable_sort(first, last, compare);
2094 }
2095
2096 //***************************************************************************
2100 //***************************************************************************
2101 template <typename TIterator>
2103 {
2104 std::stable_sort(first, last);
2105 }
2106#endif
2107
2108 //***************************************************************************
2111 //***************************************************************************
2112 template <typename TIterator, typename T>
2113 ETL_CONSTEXPR14
2115 {
2116 while (first != last)
2117 {
2118 sum = etl::move(sum) + *first;
2119 ++first;
2120 }
2121
2122 return sum;
2123 }
2124
2125 //***************************************************************************
2128 //***************************************************************************
2129 template <typename TIterator, typename T, typename TBinaryOperation>
2130 ETL_CONSTEXPR14
2131 T accumulate(TIterator first, TIterator last, T sum, TBinaryOperation operation)
2132 {
2133 while (first != last)
2134 {
2135 sum = operation(etl::move(sum), *first);
2136 ++first;
2137 }
2138
2139 return sum;
2140 }
2141
2142 //***************************************************************************
2145 //***************************************************************************
2146 template<typename T, typename TCompare>
2147 ETL_CONSTEXPR
2148 T clamp(const T& value, const T& low, const T& high, TCompare compare)
2149 {
2150 return compare(value, low) ? low : compare(high, value) ? high : value;
2151 }
2152
2153 template <typename T>
2154 ETL_CONSTEXPR
2155 T clamp(const T& value, const T& low, const T& high)
2156 {
2157 return clamp(value, low, high, etl::less<T>());
2158 }
2159
2160 template<typename T, T Low, T High, typename TCompare>
2161 ETL_CONSTEXPR
2162 T clamp(const T& value, TCompare compare)
2163 {
2164 return compare(value, Low) ? Low : compare(High, value) ? High : value;
2165 }
2166
2167 template <typename T, T Low, T High>
2168 ETL_CONSTEXPR
2169 T clamp(const T& value)
2170 {
2171 return clamp<T, Low, High>(value, etl::less<T>());
2172 }
2173
2174 //***************************************************************************
2177 //***************************************************************************
2178 template <typename TIterator, typename T>
2179 ETL_CONSTEXPR14
2180 TIterator remove(TIterator first, TIterator last, const T& value)
2181 {
2182 first = etl::find(first, last, value);
2183
2184 if (first != last)
2185 {
2186 TIterator itr = first;
2187
2188 while (++itr != last)
2189 {
2190 if (!(*itr == value))
2191 {
2192 *first++ = etl::move(*itr);
2193 }
2194 }
2195 }
2196
2197 return first;
2198 }
2199
2200 //***************************************************************************
2203 //***************************************************************************
2204 template <typename TIterator, typename TUnaryPredicate>
2205 ETL_CONSTEXPR14
2207 {
2208 first = etl::find_if(first, last, predicate);
2209
2210 if (first != last)
2211 {
2212 TIterator itr = first;
2213
2214 while (++itr != last)
2215 {
2216 if (!predicate(*itr))
2217 {
2218 *first++ = etl::move(*itr);
2219 }
2220 }
2221 }
2222
2223 return first;
2224 }
2225}
2226
2227//*****************************************************************************
2228// ETL extensions to the STL algorithms.
2229//*****************************************************************************
2230namespace etl
2231{
2232 //***************************************************************************
2242 //***************************************************************************
2243 template <typename TInputIterator,
2244 typename TOutputIterator>
2245 ETL_CONSTEXPR14
2252 {
2253 size_t s_size = etl::distance(i_begin, i_end);
2254 size_t d_size = etl::distance(o_begin, o_end);
2255 size_t size = (s_size < d_size) ? s_size : d_size;
2256
2257 return etl::copy(i_begin, i_begin + size, o_begin);
2258 }
2259
2260 //***************************************************************************
2270 //***************************************************************************
2271 template <typename TInputIterator,
2272 typename TOutputIterator>
2273 ETL_CONSTEXPR14
2280 {
2281 while ((i_begin != i_end) && (o_begin != o_end))
2282 {
2283 *o_begin = *i_begin;
2284 ++o_begin;
2285 ++i_begin;
2286 }
2287
2288 return o_begin;
2289 }
2290
2291 //***************************************************************************
2295 //***************************************************************************
2296 template <typename TInputIterator,
2297 typename TSize,
2298 typename TOutputIterator>
2299 ETL_CONSTEXPR14
2301 TSize n,
2304 {
2305 while ((n-- > 0) && (o_begin != o_end))
2306 {
2307 *o_begin = *i_begin;
2308 ++o_begin;
2309 ++i_begin;
2310 }
2311
2312 return o_begin;
2313 }
2314
2315 //***************************************************************************
2319 //***************************************************************************
2320 template <typename TInputIterator,
2321 typename TSize1,
2322 typename TOutputIterator,
2323 typename TSize2>
2324 ETL_CONSTEXPR14
2326 TSize1 n1,
2328 TSize2 n2)
2329 {
2330 while ((n1-- > 0) && (n2-- > 0))
2331 {
2332 *o_begin = *i_begin;
2333 ++o_begin;
2334 ++i_begin;
2335 }
2336
2337 return o_begin;
2338 }
2339
2340 //***************************************************************************
2345 //***************************************************************************
2346 template <typename TInputIterator,
2347 typename TOutputIterator,
2348 typename TUnaryPredicate>
2349 ETL_CONSTEXPR14
2355 {
2356 while ((i_begin != i_end) && (o_begin != o_end))
2357 {
2358 if (predicate(*i_begin))
2359 {
2360 *o_begin = *i_begin;
2361 ++o_begin;
2362 }
2363
2364 ++i_begin;
2365 }
2366
2367 return o_begin;
2368 }
2369
2370 //***************************************************************************
2374 //***************************************************************************
2375 template <typename TInputIterator,
2376 typename TSize,
2377 typename TOutputIterator,
2378 typename TUnaryPredicate>
2379 ETL_CONSTEXPR14
2381 TSize n,
2384 {
2385 while (n-- > 0)
2386 {
2387 if (predicate(*i_begin))
2388 {
2389 *o_begin = *i_begin;
2390 ++o_begin;
2391 }
2392
2393 ++i_begin;
2394 }
2395
2396 return o_begin;
2397 }
2398
2399#if ETL_USING_CPP11
2400 //***************************************************************************
2410 //***************************************************************************
2411 template <typename TInputIterator, typename TOutputIterator>
2412 ETL_CONSTEXPR14
2415 move_s(TInputIterator i_begin,
2416 TInputIterator i_end,
2417 TOutputIterator o_begin,
2418 TOutputIterator o_end)
2419 {
2420 size_t s_size = etl::distance(i_begin, i_end);
2421 size_t d_size = etl::distance(o_begin, o_end);
2422 size_t size = (s_size < d_size) ? s_size : d_size;
2423
2424 return etl::move(i_begin, i_begin + size, o_begin);
2425 }
2426
2427 //***************************************************************************
2437 //***************************************************************************
2438 template <typename TInputIterator, typename TOutputIterator>
2439 ETL_CONSTEXPR14
2442 move_s(TInputIterator i_begin,
2443 TInputIterator i_end,
2444 TOutputIterator o_begin,
2445 TOutputIterator o_end)
2446 {
2447 while ((i_begin != i_end) && (o_begin != o_end))
2448 {
2449 *o_begin = etl::move(*i_begin);
2450 ++i_begin;
2451 ++o_begin;
2452 }
2453
2454 return o_begin;
2455 }
2456#else
2457 //***************************************************************************
2468 //***************************************************************************
2469 template <typename TInputIterator, typename TOutputIterator>
2474 {
2475 // Move not supported. Defer to copy.
2477 }
2478#endif
2479
2480 //***************************************************************************
2484 //***************************************************************************
2485 template <typename TIterator, typename TValue>
2486 ETL_NODISCARD
2487 ETL_CONSTEXPR14
2489 TIterator end,
2490 const TValue& value)
2491 {
2492 TIterator it = etl::lower_bound(begin, end, value);
2493
2494 if ((it == end) || (*it != value))
2495 {
2496 it = end;
2497 }
2498
2499 return it;
2500 }
2501
2502 //***************************************************************************
2506 //***************************************************************************
2507 template <typename TIterator,
2508 typename TValue,
2509 typename TBinaryPredicate,
2510 typename TBinaryEquality>
2511 ETL_NODISCARD
2512 ETL_CONSTEXPR14
2514 TIterator end,
2515 const TValue& value,
2518 {
2519 TIterator it = etl::lower_bound(begin, end, value, predicate);
2520
2521 if ((it == end) || !equality(*it, value))
2522 {
2523 it = end;
2524 }
2525
2526 return it;
2527 }
2528
2529 //***************************************************************************
2532 //***************************************************************************
2533 template <typename TIterator,
2534 typename TUnaryFunction,
2535 typename TUnaryPredicate>
2536 ETL_CONSTEXPR14
2538 const TIterator end,
2541 {
2542 while (begin != end)
2543 {
2544 if (predicate(*begin))
2545 {
2546 function(*begin);
2547 }
2548
2549 ++begin;
2550 }
2551
2552 return function;
2553 }
2554
2555 //***************************************************************************
2558 //***************************************************************************
2559 template <typename TIterator,
2560 typename TSize,
2561 typename TUnaryFunction>
2562 ETL_CONSTEXPR14
2564 TSize n,
2566 {
2567 while (n-- > 0)
2568 {
2569 function(*begin);
2570 ++begin;
2571 }
2572
2573 return begin;
2574 }
2575
2576 //***************************************************************************
2579 //***************************************************************************
2580 template <typename TIterator,
2581 typename TSize,
2582 typename TUnaryFunction,
2583 typename TUnaryPredicate>
2584 ETL_CONSTEXPR14
2586 TSize n,
2589 {
2590 while (n-- > 0)
2591 {
2592 if (predicate(*begin))
2593 {
2594 function(*begin);
2595 }
2596
2597 ++begin;
2598 }
2599
2600 return begin;
2601 }
2602
2603 //***************************************************************************
2608 //***************************************************************************
2609 template <typename TInputIterator, typename TOutputIterator, typename TUnaryFunction>
2610 ETL_CONSTEXPR14
2616 {
2617 while ((i_begin != i_end) && (o_begin != o_end))
2618 {
2620 ++i_begin;
2621 ++o_begin;
2622 }
2623
2624 return o_begin;
2625 }
2626
2627 //***************************************************************************
2632 //***************************************************************************
2633 template <typename TInputIterator,
2634 typename TSize,
2635 typename TOutputIterator,
2636 typename TUnaryFunction>
2637 ETL_CONSTEXPR14
2639 TSize n,
2642 {
2644 etl::advance(i_end, n);
2645
2646 etl::transform(i_begin, i_end, o_begin, function);
2647 }
2648
2649 //***************************************************************************
2654 //***************************************************************************
2655 template <typename TInputIterator1,
2656 typename TInputIterator2,
2657 typename TSize,
2658 typename TOutputIterator,
2659 typename TBinaryFunction>
2660 ETL_CONSTEXPR14
2663 TSize n,
2666 {
2668 etl::advance(i_end1, n);
2669
2670 etl::transform(i_begin1, i_end1, i_begin2, o_begin, function);
2671 }
2672
2673 //***************************************************************************
2676 //***************************************************************************
2677 template <typename TInputIterator,
2678 typename TOutputIterator,
2679 typename TUnaryFunction,
2680 typename TUnaryPredicate>
2681 ETL_CONSTEXPR14
2683 const TInputIterator i_end,
2687 {
2688 while (i_begin != i_end)
2689 {
2690 if (predicate(*i_begin))
2691 {
2693 ++o_begin;
2694 }
2695
2696 ++i_begin;
2697 }
2698
2699 return o_begin;
2700 }
2701
2702 //***************************************************************************
2705 //***************************************************************************
2706 template <typename TInputIterator1,
2707 typename TInputIterator2,
2708 typename TOutputIterator,
2709 typename TBinaryFunction,
2710 typename TBinaryPredicate>
2711 ETL_CONSTEXPR14
2713 const TInputIterator1 i_end1,
2718 {
2719 while (i_begin1 != i_end1)
2720 {
2721 if (predicate(*i_begin1, *i_begin2))
2722 {
2724 ++o_begin;
2725 }
2726
2727 ++i_begin1;
2728 ++i_begin2;
2729 }
2730
2731 return o_begin;
2732 }
2733
2734 //***************************************************************************
2737 //***************************************************************************
2738 template <typename TInputIterator,
2739 typename TSize,
2740 typename TOutputIterator,
2741 typename TUnaryFunction,
2742 typename TUnaryPredicate>
2743 ETL_CONSTEXPR14
2745 TSize n,
2749 {
2750 while (n-- > 0)
2751 {
2752 if (predicate(*i_begin))
2753 {
2755 ++o_begin;
2756 }
2757
2758 ++i_begin;
2759 }
2760
2761 return o_begin;
2762 }
2763
2764 //***************************************************************************
2767 //***************************************************************************
2768 template <typename TInputIterator1,
2769 typename TInputIterator2,
2770 typename TSize,
2771 typename TOutputIterator,
2772 typename TBinaryFunction,
2773 typename TBinaryPredicate>
2774 ETL_CONSTEXPR14
2777 TSize n,
2781 {
2782 while (n-- > 0)
2783 {
2784 if (predicate(*i_begin1, *i_begin2))
2785 {
2787 }
2788
2789 ++i_begin1;
2790 ++i_begin2;
2791 }
2792
2793 return o_begin;
2794 }
2795
2796 //***************************************************************************
2800 //***************************************************************************
2801 template <typename TSource, typename TDestinationTrue, typename TDestinationFalse,
2802 typename TUnaryFunctionTrue, typename TUnaryFunctionFalse,
2803 typename TUnaryPredicate>
2804 ETL_CONSTEXPR14
2805 ETL_OR_STD::pair<TDestinationTrue, TDestinationFalse> partition_transform(TSource begin,
2806 TSource end,
2812 {
2813 while (begin != end)
2814 {
2815 if (predicate(*begin))
2816 {
2819 }
2820 else
2821 {
2824 }
2825
2826 ++begin;
2827 }
2828
2829 return ETL_OR_STD::pair<TDestinationTrue, TDestinationFalse>(destination_true, destination_false);
2830 }
2831
2832 //***************************************************************************
2836 //***************************************************************************
2837 template <typename TSource1,
2838 typename TSource2,
2839 typename TDestinationTrue,
2840 typename TDestinationFalse,
2841 typename TBinaryFunctionTrue,
2842 typename TBinaryFunctionFalse,
2843 typename TBinaryPredicate>
2844 ETL_CONSTEXPR14
2845 ETL_OR_STD::pair<TDestinationTrue, TDestinationFalse> partition_transform(TSource1 begin1,
2846 TSource1 end1,
2853 {
2854 while (begin1 != end1)
2855 {
2856 if (predicate(*begin1, *begin2))
2857 {
2860 }
2861 else
2862 {
2865 }
2866
2867 ++begin1;
2868 ++begin2;
2869 }
2870
2871 return ETL_OR_STD::pair<TDestinationTrue, TDestinationFalse>(destination_true, destination_false);
2872 }
2873
2874 //***************************************************************************
2878 //***************************************************************************
2879 template <typename TIterator, typename TCompare>
2880#if ETL_USING_STD_NAMESPACE
2881 ETL_CONSTEXPR20
2882#else
2883 ETL_CONSTEXPR14
2884#endif
2886 {
2887 if (first == last)
2888 {
2889 return;
2890 }
2891
2892 typedef typename etl::iterator_traits<TIterator>::difference_type difference_t;
2893
2894 difference_t n = etl::distance(first, last);
2895
2896 for (difference_t i = n / 2; i > 0; i /= 2)
2897 {
2898 for (difference_t j = i; j < n; ++j)
2899 {
2900 for (difference_t k = j - i; k >= 0; k -= i)
2901 {
2902 TIterator itr1 = first;
2903 TIterator itr2 = first;
2904
2905 etl::advance(itr1, k);
2906 etl::advance(itr2, k + i);
2907
2908 if (compare(*itr2, *itr1))
2909 {
2910 etl::iter_swap(itr1, itr2);
2911 }
2912 }
2913 }
2914 }
2915 }
2916
2917 //***************************************************************************
2920 //***************************************************************************
2921 template <typename TIterator>
2922#if ETL_USING_STD_NAMESPACE
2923 ETL_CONSTEXPR20
2924#else
2925 ETL_CONSTEXPR14
2926#endif
2928 {
2929 etl::shell_sort(first, last, etl::less<typename etl::iterator_traits<TIterator>::value_type>());
2930 }
2931
2932 //***************************************************************************
2936 //***************************************************************************
2937 template <typename TIterator, typename TCompare>
2938 ETL_CONSTEXPR14
2940 {
2941 for (TIterator itr = first; itr != last; ++itr)
2942 {
2943 etl::rotate(etl::upper_bound(first, itr, *itr, compare), itr, etl::next(itr));
2944 }
2945 }
2946
2947 //***************************************************************************
2950 //***************************************************************************
2951 template <typename TIterator>
2952 ETL_CONSTEXPR14
2954 {
2955 etl::insertion_sort(first, last, etl::less<typename etl::iterator_traits<TIterator>::value_type>());
2956 }
2957
2958 //***************************************************************************
2959 namespace private_algorithm
2960 {
2961 template <typename TIterator>
2962 ETL_CONSTEXPR14
2964 get_before_last(TIterator first_, TIterator last_)
2965 {
2966 TIterator last = first_;
2967 TIterator lastplus1 = first_;
2968 ++lastplus1;
2969
2970 while (lastplus1 != last_)
2971 {
2972 ++last;
2973 ++lastplus1;
2974 }
2975
2976 return last;
2977 }
2978
2979 template <typename TIterator>
2980 ETL_CONSTEXPR14
2982 get_before_last(TIterator /*first_*/, TIterator last_)
2983 {
2984 TIterator last = last_;
2985 --last;
2986
2987 return last;
2988 }
2989
2990 template <typename TIterator>
2991 ETL_CONSTEXPR14
2993 get_before_last(TIterator /*first_*/, TIterator last_)
2994 {
2995 return last_ - 1;
2996 }
2997 }
2998
2999 //***************************************************************************
3003 //***************************************************************************
3004 template <typename TIterator, typename TCompare>
3005 ETL_CONSTEXPR20
3007 {
3008 TIterator min;
3009 const TIterator ilast = private_algorithm::get_before_last(first, last);
3010 const TIterator jlast = last;
3011
3012 for (TIterator i = first; i != ilast; ++i)
3013 {
3014 min = i;
3015
3016 TIterator j = i;
3017 ++j;
3018
3019 for (; j != jlast; ++j)
3020 {
3021 if (compare(*j, *min))
3022 {
3023 min = j;
3024 }
3025 }
3026
3027 using ETL_OR_STD::swap; // Allow ADL
3028 swap(*i, *min);
3029 }
3030 }
3031
3032 //***************************************************************************
3035 //***************************************************************************
3036 template <typename TIterator>
3037 ETL_CONSTEXPR20
3039 {
3040 selection_sort(first, last, etl::less<typename etl::iterator_traits<TIterator>::value_type>());
3041 }
3042
3043 //***************************************************************************
3047 //***************************************************************************
3048 template <typename TIterator, typename TCompare>
3049 ETL_CONSTEXPR14
3051 {
3052 if (!etl::is_heap(first, last, compare))
3053 {
3054 etl::make_heap(first, last, compare);
3055 }
3056
3057 etl::sort_heap(first, last, compare);
3058 }
3059
3060 //***************************************************************************
3063 //***************************************************************************
3064 template <typename TIterator>
3065 ETL_CONSTEXPR14
3067 {
3068 if (!etl::is_heap(first, last))
3069 {
3070 etl::make_heap(first, last);
3071 }
3072
3073 etl::sort_heap(first, last);
3074 }
3075
3076 //***************************************************************************
3078 //***************************************************************************
3079#if ETL_USING_CPP11
3080 template <typename T>
3081 ETL_NODISCARD
3082 constexpr const T& multimax(const T& a, const T& b)
3083 {
3084 return a < b ? b : a;
3085 }
3086
3087 template <typename T, typename... Tx>
3088 ETL_NODISCARD
3089 constexpr const T& multimax(const T& t, const Tx&... tx)
3090 {
3091 return multimax(t, multimax(tx...));
3092 }
3093#endif
3094
3095 //***************************************************************************
3098 //***************************************************************************
3099#if ETL_USING_CPP11
3100 template <typename TCompare, typename T>
3101 ETL_NODISCARD
3102 constexpr const T& multimax_compare(TCompare compare, const T& a, const T& b)
3103 {
3104 return compare(a, b) ? b : a;
3105 }
3106
3107 template <typename TCompare, typename T, typename... Tx>
3108 ETL_NODISCARD
3109 constexpr const T& multimax_compare(TCompare compare, const T& t, const Tx&... tx)
3110 {
3111 return multimax_compare(compare, t, multimax_compare(compare, tx...));
3112 }
3113#endif
3114
3115 //***************************************************************************
3117 //***************************************************************************
3118#if ETL_USING_CPP11
3119 template <typename T>
3120 ETL_NODISCARD
3121 constexpr const T& multimin(const T& a, const T& b)
3122 {
3123 return a < b ? a : b;
3124 }
3125
3126 template <typename T, typename... Tx>
3127 ETL_NODISCARD
3128 constexpr const T& multimin(const T& t, const Tx&... tx)
3129 {
3130 return multimin(t, multimin(tx...));
3131 }
3132#endif
3133
3134 //***************************************************************************
3137 //***************************************************************************
3138#if ETL_USING_CPP11
3139 template <typename TCompare, typename T>
3140 ETL_NODISCARD
3141 constexpr const T& multimin_compare(TCompare compare, const T& a, const T& b)
3142 {
3143 return compare(a, b) ? a : b;
3144 }
3145
3146 template <typename TCompare, typename T, typename... Tx>
3147 ETL_NODISCARD
3148 constexpr const T& multimin_compare(TCompare compare, const T& t, const Tx&... tx)
3149 {
3150 return multimin_compare(compare, t, multimin_compare(compare, tx...));
3151 }
3152#endif
3153
3154 //***************************************************************************
3156 //***************************************************************************
3157#if ETL_USING_CPP11
3158 template <typename TIterator>
3159 ETL_NODISCARD
3160 constexpr const TIterator& multimax_iter(const TIterator& a, const TIterator& b)
3161 {
3162 return *a < *b ? b : a;
3163 }
3164
3165 template <typename TIterator, typename... TIteratorx>
3166 ETL_NODISCARD
3167 constexpr const TIterator& multimax_iter(const TIterator& t, const TIteratorx&... tx)
3168 {
3169 return multimax_iter(t, multimax_iter(tx...));
3170 }
3171#endif
3172
3173 //***************************************************************************
3176 //***************************************************************************
3177#if ETL_USING_CPP11
3178 template <typename TCompare, typename TIterator>
3179 ETL_NODISCARD
3180 constexpr const TIterator& multimax_iter_compare(TCompare compare, const TIterator& a, const TIterator& b)
3181 {
3182 return compare(*a, *b) ? b : a;
3183 }
3184
3185 template <typename TCompare, typename TIterator, typename... TIteratorx>
3186 ETL_NODISCARD
3187 constexpr const TIterator& multimax_iter_compare(TCompare compare, const TIterator& t, const TIteratorx&... tx)
3188 {
3189 return multimax_iter_compare(compare, t, multimax_iter_compare(compare, tx...));
3190 }
3191#endif
3192
3193 //***************************************************************************
3195 //***************************************************************************
3196#if ETL_USING_CPP11
3197 template <typename TIterator>
3198 ETL_NODISCARD
3199 constexpr const TIterator& multimin_iter(const TIterator& a, const TIterator& b)
3200 {
3201 return *a < *b ? a : b;
3202 }
3203
3204 template <typename TIterator, typename... Tx>
3205 ETL_NODISCARD
3206 constexpr const TIterator& multimin_iter(const TIterator& t, const Tx&... tx)
3207 {
3208 return multimin_iter(t, multimin_iter(tx...));
3209 }
3210#endif
3211
3212 //***************************************************************************
3215 //***************************************************************************
3216#if ETL_USING_CPP11
3217 template <typename TCompare, typename TIterator>
3218 ETL_NODISCARD
3219 constexpr const TIterator& multimin_iter_compare(TCompare compare, const TIterator& a, const TIterator& b)
3220 {
3221 return compare(*a, *b) ? a : b;
3222 }
3223
3224 template <typename TCompare, typename TIterator, typename... Tx>
3225 ETL_NODISCARD
3226 constexpr const TIterator& multimin_iter_compare(TCompare compare, const TIterator& t, const Tx&... tx)
3227 {
3228 return multimin_iter_compare(compare, t, multimin_iter_compare(compare, tx...));
3229 }
3230#endif
3231
3232 //***************************************************************************
3236 //***************************************************************************
3237 template <typename TIterator, typename TPredicate>
3238 ETL_CONSTEXPR14
3241 {
3242 first = etl::find_if_not(first, last, predicate);
3243
3244 if (first == last)
3245 {
3246 return first;
3247 }
3248
3249 for (TIterator i = etl::next(first); i != last; ++i)
3250 {
3251 if (predicate(*i))
3252 {
3253 using ETL_OR_STD::swap;
3254 swap(*i, *first);
3255 ++first;
3256 }
3257 }
3258
3259 return first;
3260 }
3261
3262 //***************************************************************************
3266 //***************************************************************************
3267 template <typename TIterator, typename TPredicate>
3268 ETL_CONSTEXPR14
3271 {
3272 while (first != last)
3273 {
3274 first = etl::find_if_not(first, last, predicate);
3275
3276 if (first == last)
3277 {
3278 break;
3279 }
3280
3281 last = etl::find_if(etl::reverse_iterator<TIterator>(last),
3283 predicate).base();
3284
3285 if (first == last)
3286 {
3287 break;
3288 }
3289
3290 --last;
3291 using ETL_OR_STD::swap;
3292 swap(*first, *last);
3293 ++first;
3294 }
3295
3296 return first;
3297 }
3298
3299 //*********************************************************
3300 namespace private_algorithm
3301 {
3302 using ETL_OR_STD::swap;
3303
3304 template <typename TIterator, typename TCompare>
3305#if (ETL_USING_CPP20 && ETL_USING_STL) || (ETL_USING_CPP14 && ETL_NOT_USING_STL && !defined(ETL_IN_UNIT_TEST))
3306 constexpr
3307#endif
3308 TIterator nth_partition(TIterator first, TIterator last, TCompare compare)
3309 {
3310 typedef typename etl::iterator_traits<TIterator>::value_type value_type;
3311
3312 TIterator pivot = last; // Maybe find a better pivot choice?
3313 value_type pivot_value = *pivot;
3314
3315 // Swap the pivot with the last, if necessary.
3316 if (pivot != last)
3317 {
3318 swap(*pivot, *last);
3319 }
3320
3321 TIterator i = first;
3322
3323 for (TIterator j = first; j < last; ++j)
3324 {
3325 if (!compare(pivot_value, *j)) // Hack to get '*j <= pivot_value' in terms of 'pivot_value < *j'
3326 {
3327 swap(*i, *j);
3328 ++i;
3329 }
3330 }
3331
3332 swap(*i, *last);
3333
3334 return i;
3335 }
3336 }
3337
3338 //*********************************************************
3341 //*********************************************************
3342#if ETL_USING_CPP11
3343 template <typename TIterator, typename TCompare = etl::less<typename etl::iterator_traits<TIterator>::value_type>>
3344#if (ETL_USING_CPP20 && ETL_USING_STL) || (ETL_USING_CPP14 && ETL_NOT_USING_STL && !defined(ETL_IN_UNIT_TEST))
3345 constexpr
3346#endif
3348 nth_element(TIterator first, TIterator nth, TIterator last, TCompare compare = TCompare())
3349 {
3350 if (first == last)
3351 {
3352 return;
3353 }
3354
3355 // 'last' must point to the actual last value.
3356 --last;
3357
3358 while (first <= last)
3359 {
3360 TIterator p = private_algorithm::nth_partition(first, last, compare);
3361
3362 if (p == nth)
3363 {
3364 return;
3365 }
3366 else if (p > nth)
3367 {
3368 last = p - 1;
3369 }
3370 else
3371 {
3372 first = p + 1;
3373 }
3374 }
3375 }
3376
3377#else
3378
3379 //*********************************************************
3380 template <typename TIterator, typename TCompare>
3383 {
3384 if (first == last)
3385 {
3386 return;
3387 }
3388
3389 // 'last' must point to the actual last value.
3390 --last;
3391
3392 while (first <= last)
3393 {
3394 TIterator p = private_algorithm::nth_partition(first, last, compare);
3395
3396 if (p == nth)
3397 {
3398 return;
3399 }
3400 else if (p > nth)
3401 {
3402 last = p - 1;
3403 }
3404 else
3405 {
3406 first = p + 1;
3407 }
3408 }
3409 }
3410
3411 //*********************************************************
3412 template <typename TIterator>
3414 nth_element(TIterator first, TIterator nth, TIterator last)
3415 {
3417
3418 nth_element(first, last, compare_t());
3419 }
3420#endif
3421}
3422
3423#include "private/minmax_pop.h"
3424
3425#endif
ETL_CONSTEXPR T clamp(const T &value, const T &low, const T &high, TCompare compare)
Definition algorithm.h:2148
ETL_CONSTEXPR20 void shell_sort(TIterator first, TIterator last)
Definition algorithm.h:2927
ETL_CONSTEXPR14 TOutputIterator copy_if(TIterator begin, TIterator end, TOutputIterator out, TUnaryPredicate predicate)
Definition algorithm.h:1954
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:2805
ETL_NODISCARD ETL_CONSTEXPR14 bool any_of(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition algorithm.h:1996
ETL_NODISCARD ETL_CONSTEXPR14 TIterator min_element(TIterator begin, TIterator end, TCompare compare)
Definition algorithm.h:1447
ETL_CONSTEXPR14 TOutputIterator transform_n_if(TInputIterator i_begin, TSize n, TOutputIterator o_begin, TUnaryFunction function, TUnaryPredicate predicate)
Definition algorithm.h:2744
ETL_CONSTEXPR14 T accumulate(TIterator first, TIterator last, T sum)
Definition algorithm.h:2114
ETL_NODISCARD ETL_CONSTEXPR14 bool all_of(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition algorithm.h:1981
ETL_NODISCARD ETL_CONSTEXPR14 ETL_OR_STD::pair< TIterator, TIterator > minmax_element(TIterator begin, TIterator end, TCompare compare)
Definition algorithm.h:1535
ETL_CONSTEXPR14 TOutputIterator transform_if(TInputIterator i_begin, const TInputIterator i_end, TOutputIterator o_begin, TUnaryFunction function, TUnaryPredicate predicate)
Definition algorithm.h:2682
ETL_CONSTEXPR14 TUnaryFunction for_each_if(TIterator begin, const TIterator end, TUnaryFunction function, TUnaryPredicate predicate)
Definition algorithm.h:2537
ETL_NODISCARD ETL_CONSTEXPR14 TIterator find_if_not(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition algorithm.h:1702
ETL_NODISCARD ETL_CONSTEXPR14 bool is_sorted(TIterator begin, TIterator end)
Definition algorithm.h:1673
ETL_CONSTEXPR14 TOutputIterator transform_s(TInputIterator i_begin, TInputIterator i_end, TOutputIterator o_begin, TOutputIterator o_end, TUnaryFunction function)
Definition algorithm.h:2611
ETL_CONSTEXPR14 TIterator remove(TIterator first, TIterator last, const T &value)
Definition algorithm.h:2180
ETL_CONSTEXPR14 void transform_n(TInputIterator i_begin, TSize n, TOutputIterator o_begin, TUnaryFunction function)
Definition algorithm.h:2638
ETL_CONSTEXPR14 TOutputIterator copy_n_if(TInputIterator i_begin, TSize n, TOutputIterator o_begin, TUnaryPredicate predicate)
Definition algorithm.h:2380
ETL_NODISCARD ETL_CONSTEXPR14 TIterator is_sorted_until(TIterator begin, TIterator end)
Definition algorithm.h:1614
ETL_CONSTEXPR14 void insertion_sort(TIterator first, TIterator last)
Definition algorithm.h:2953
void sort(TIterator first, TIterator last, TCompare compare)
Definition algorithm.h:2069
ETL_NODISCARD ETL_CONSTEXPR14 ETL_OR_STD::pair< const T &, const T & > minmax(const T &a, const T &b)
Definition algorithm.h:1585
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:2248
ETL_CONSTEXPR14 TIterator remove_if(TIterator first, TIterator last, TUnaryPredicate predicate)
Definition algorithm.h:2206
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:1922
ETL_CONSTEXPR14 TIterator for_each_n(TIterator begin, TSize n, TUnaryFunction function)
Definition algorithm.h:2563
ETL_NODISCARD ETL_CONSTEXPR14 TIterator binary_find(TIterator begin, TIterator end, const TValue &value)
Definition algorithm.h:2488
ETL_CONSTEXPR14 void heap_sort(TIterator first, TIterator last, TCompare compare)
Definition algorithm.h:3050
ETL_NODISCARD ETL_CONSTEXPR14 bool none_of(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition algorithm.h:2011
ETL_CONSTEXPR20 void selection_sort(TIterator first, TIterator last, TCompare compare)
Definition algorithm.h:3006
ETL_CONSTEXPR14 TOutputIterator copy_n_s(TInputIterator i_begin, TSize n, TOutputIterator o_begin, TOutputIterator o_end)
Definition algorithm.h:2300
TOutputIterator move_s(TInputIterator i_begin, TInputIterator i_end, TOutputIterator o_begin, TOutputIterator o_end)
Definition algorithm.h:2470
ETL_CONSTEXPR14 TOutputIterator copy_if_s(TInputIterator i_begin, TInputIterator i_end, TOutputIterator o_begin, TOutputIterator o_end, TUnaryPredicate predicate)
Definition algorithm.h:2350
ETL_CONSTEXPR14 TIterator for_each_n_if(TIterator begin, TSize n, TUnaryFunction function, TUnaryPredicate predicate)
Definition algorithm.h:2585
void stable_sort(TIterator first, TIterator last, TCompare compare)
Definition algorithm.h:2091
ETL_NODISCARD ETL_CONSTEXPR14 bool is_partitioned(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition algorithm.h:1862
ETL_NODISCARD ETL_CONSTEXPR14 TIterator max_element(TIterator begin, TIterator end, TCompare compare)
Definition algorithm.h:1491
ETL_NODISCARD ETL_CONSTEXPR14 TIterator partition_point(TIterator begin, TIterator end, TUnaryPredicate predicate)
Definition algorithm.h:1897
ETL_NODISCARD ETL_CONSTEXPR14 bool is_permutation(TIterator1 begin1, TIterator1 end1, TIterator2 begin2)
Definition algorithm.h:1727
Definition function.h:94
enable_if
Definition type_traits_generator.h:1191
is_reference
Definition type_traits_generator.h:1111
is_same
Definition type_traits_generator.h:1041
bitset_ext
Definition absolute.h:38
etl::enable_if< etl::is_random_access_iterator_concept< TIterator >::value, void >::type nth_element(TIterator first, TIterator nth, TIterator last, TCompare compare)
Definition algorithm.h:3382
void swap(etl::array< T, SIZE > &lhs, etl::array< T, SIZE > &rhs)
Template deduction guides.
Definition array.h:630
ETL_CONSTEXPR TContainer::size_type size(const TContainer &container)
Definition iterator.h:1187
ETL_CONSTEXPR TContainer::iterator begin(TContainer &container)
Definition iterator.h:962
ETL_CONSTEXPR14 etl::enable_if< etl::is_forward_iterator< TIterator >::value, TIterator >::type partition(TIterator first, TIterator last, TPredicate predicate)
Returns the maximum value.
Definition algorithm.h:3240
ETL_CONSTEXPR TContainer::iterator end(TContainer &container)
Definition iterator.h:992
Definition compare.h:51
Definition iterator.h:854
Definition iterator.h:873
Definition iterator.h:63
Definition functional.h:135
pair holds two objects of arbitrary type
Definition utility.h:164
Definition algorithm.h:95